2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1996
4 \section[Specialise]{Stamping out overloading, and (optionally) polymorphism}
7 #include "HsVersions.h"
17 IMPORT_1_3(List(partition))
19 import Bag ( emptyBag, unitBag, isEmptyBag, unionBags,
20 partitionBag, listToBag, bagToList, Bag
22 import Class ( GenClass{-instance Eq-}, SYN_IE(Class) )
23 import CmdLineOpts ( opt_SpecialiseImports, opt_D_simplifier_stats,
24 opt_CompilingGhcInternals, opt_SpecialiseTrace
26 import CoreLift ( mkLiftedId, liftExpr, bindUnlift, applyBindUnlifts )
28 import CoreUtils ( coreExprType, squashableDictishCcExpr )
29 import FiniteMap ( addListToFM_C, FiniteMap )
30 import Kind ( mkBoxedTypeKind, isBoxedTypeKind )
31 import Id ( idType, isDefaultMethodId_maybe, toplevelishId,
32 isSuperDictSelId_maybe, isBottomingId,
33 isConstMethodId_maybe, isDataCon,
34 isImportedId, mkIdWithNewUniq,
35 dataConTyCon, applyTypeEnvToId,
36 nullIdEnv, addOneToIdEnv, growIdEnvList,
37 lookupIdEnv, SYN_IE(IdEnv),
38 emptyIdSet, mkIdSet, unitIdSet,
39 elementOfIdSet, minusIdSet,
40 unionIdSets, unionManyIdSets, SYN_IE(IdSet),
41 GenId{-instance Eq-}, SYN_IE(Id)
43 import Literal ( Literal{-instance Outputable-} )
44 import Maybes ( catMaybes, firstJust, maybeToBool )
45 import Name ( isLocallyDefined )
46 import Outputable ( interppSP, Outputable(..){-instance * []-} )
47 import PprStyle ( PprStyle(..) )
48 import PprType ( pprGenType, pprParendGenType, pprMaybeTy,
49 GenType{-instance Outputable-}, GenTyVar{-ditto-},
52 import Pretty ( hang, hsep, text, vcat, hcat, ptext, char,
53 int, space, empty, Doc
55 import PrimOp ( PrimOp(..) )
57 import Type ( mkTyVarTy, mkTyVarTys, isTyVarTy, getAppDataTyConExpandingDicts,
58 tyVarsOfTypes, applyTypeEnvToTy, isUnboxedType, isDictTy,
61 import TyCon ( TyCon{-instance Eq-} )
62 import TyVar ( cloneTyVar, mkSysTyVar,
63 elementOfTyVarSet, SYN_IE(TyVarSet),
64 nullTyVarEnv, growTyVarEnvList, SYN_IE(TyVarEnv),
65 GenTyVar{-instance Eq-}
67 import TysWiredIn ( liftDataCon )
68 import Unique ( Unique{-instance Eq-} )
69 import UniqSet ( mkUniqSet, unionUniqSets, uniqSetToList )
70 import UniqSupply ( splitUniqSupply, getUniques, getUnique )
71 import Util ( equivClasses, mapAccumL, assoc, zipEqual, zipWithEqual,
72 thenCmp, panic, pprTrace, pprPanic, assertPanic
77 specProgram = panic "SpecProgram"
80 data SpecInfo = SpecInfo [Maybe Type] Int Id
84 lookupSpecEnv = panic "Specialise.lookupSpecEnv (ToDo)"
85 addIdSpecialisation = panic "Specialise.addIdSpecialisation (ToDo)"
86 cmpUniTypeMaybeList = panic "Specialise.cmpUniTypeMaybeList (ToDo)"
87 getIdSpecialisation = panic "Specialise.getIdSpecialisation (ToDo)"
88 isClassOpId = panic "Specialise.isClassOpId (ToDo)"
89 isLocalGenTyCon = panic "Specialise.isLocalGenTyCon (ToDo)"
90 isLocalSpecTyCon = panic "Specialise.isLocalSpecTyCon (ToDo)"
91 isSpecId_maybe = panic "Specialise.isSpecId_maybe (ToDo)"
92 isSpecPragmaId_maybe = panic "Specialise.isSpecPragmaId_maybe (ToDo)"
93 lookupClassInstAtSimpleType = panic "Specialise.lookupClassInstAtSimpleType (ToDo)"
94 mkSpecEnv = panic "Specialise.mkSpecEnv (ToDo)"
95 mkSpecId = panic "Specialise.mkSpecId (ToDo)"
96 selectIdInfoForSpecId = panic "Specialise.selectIdInfoForSpecId (ToDo)"
97 specialiseTy = panic "Specialise.specialiseTy (ToDo)"
100 %************************************************************************
102 \subsection[notes-Specialise]{Implementation notes [SLPJ, Aug 18 1993]}
104 %************************************************************************
106 These notes describe how we implement specialisation to eliminate
107 overloading, and optionally to eliminate unboxed polymorphism, and
110 The specialisation pass is a partial evaluator which works on Core
111 syntax, complete with all the explicit dictionary application,
112 abstraction and construction as added by the type checker. The
113 existing type checker remains largely as it is.
115 One important thought: the {\em types} passed to an overloaded
116 function, and the {\em dictionaries} passed are mutually redundant.
117 If the same function is applied to the same type(s) then it is sure to
118 be applied to the same dictionary(s)---or rather to the same {\em
119 values}. (The arguments might look different but they will evaluate
122 Second important thought: we know that we can make progress by
123 treating dictionary arguments as static and worth specialising on. So
124 we can do without binding-time analysis, and instead specialise on
125 dictionary arguments and no others.
134 and suppose f is overloaded.
136 STEP 1: CALL-INSTANCE COLLECTION
138 We traverse <body>, accumulating all applications of f to types and
141 (Might there be partial applications, to just some of its types and
142 dictionaries? In principle yes, but in practice the type checker only
143 builds applications of f to all its types and dictionaries, so partial
144 applications could only arise as a result of transformation, and even
145 then I think it's unlikely. In any case, we simply don't accumulate such
146 partial applications.)
148 There's a choice of whether to collect details of all *polymorphic* functions
149 or simply all *overloaded* ones. How to sort this out?
150 Pass in a predicate on the function to say if it is "interesting"?
151 This is dependent on the user flags: SpecialiseOverloaded
157 So now we have a collection of calls to f:
161 Notice that f may take several type arguments. To avoid ambiguity, we
162 say that f is called at type t1/t2 and t3/t4.
164 We take equivalence classes using equality of the *types* (ignoring
165 the dictionary args, which as mentioned previously are redundant).
167 STEP 3: SPECIALISATION
169 For each equivalence class, choose a representative (f t1 t2 d1 d2),
170 and create a local instance of f, defined thus:
172 f@t1/t2 = <f_rhs> t1 t2 d1 d2
174 (f_rhs presumably has some big lambdas and dictionary lambdas, so lots
175 of simplification will now result.) Then we should recursively do
178 The new id has its own unique, but its print-name (if exported) has
179 an explicit representation of the instance types t1/t2.
181 Add this new id to f's IdInfo, to record that f has a specialised version.
183 Before doing any of this, check that f's IdInfo doesn't already
184 tell us about an existing instance of f at the required type/s.
185 (This might happen if specialisation was applied more than once, or
186 it might arise from user SPECIALIZE pragmas.)
190 Wait a minute! What if f is recursive? Then we can't just plug in
191 its right-hand side, can we?
193 But it's ok. The type checker *always* creates non-recursive definitions
194 for overloaded recursive functions. For example:
196 f x = f (x+x) -- Yes I know its silly
200 f a (d::Num a) = let p = +.sel a d
202 letrec fl (y::a) = fl (p y y)
206 We still have recusion for non-overloadd functions which we
207 speciailise, but the recursive call should get speciailised to the
208 same recursive version.
214 All this is crystal clear when the function is applied to *constant
215 types*; that is, types which have no type variables inside. But what if
216 it is applied to non-constant types? Suppose we find a call of f at type
217 t1/t2. There are two possibilities:
219 (a) The free type variables of t1, t2 are in scope at the definition point
220 of f. In this case there's no problem, we proceed just as before. A common
221 example is as follows. Here's the Haskell:
226 After typechecking we have
228 g a (d::Num a) (y::a) = let f b (d'::Num b) (x::b) = +.sel b d' x x
229 in +.sel a d (f a d y) (f a d y)
231 Notice that the call to f is at type type "a"; a non-constant type.
232 Both calls to f are at the same type, so we can specialise to give:
234 g a (d::Num a) (y::a) = let f@a (x::a) = +.sel a d x x
235 in +.sel a d (f@a y) (f@a y)
238 (b) The other case is when the type variables in the instance types
239 are *not* in scope at the definition point of f. The example we are
240 working with above is a good case. There are two instances of (+.sel a d),
241 but "a" is not in scope at the definition of +.sel. Can we do anything?
242 Yes, we can "common them up", a sort of limited common sub-expression deal.
245 g a (d::Num a) (y::a) = let +.sel@a = +.sel a d
246 f@a (x::a) = +.sel@a x x
247 in +.sel@a (f@a y) (f@a y)
249 This can save work, and can't be spotted by the type checker, because
250 the two instances of +.sel weren't originally at the same type.
254 * There are quite a few variations here. For example, the defn of
255 +.sel could be floated ouside the \y, to attempt to gain laziness.
256 It certainly mustn't be floated outside the \d because the d has to
259 * We don't want to inline f_rhs in this case, because
260 that will duplicate code. Just commoning up the call is the point.
262 * Nothing gets added to +.sel's IdInfo.
264 * Don't bother unless the equivalence class has more than one item!
266 Not clear whether this is all worth it. It is of course OK to
267 simply discard call-instances when passing a big lambda.
269 Polymorphism 2 -- Overloading
271 Consider a function whose most general type is
273 f :: forall a b. Ord a => [a] -> b -> b
275 There is really no point in making a version of g at Int/Int and another
276 at Int/Bool, because it's only instancing the type variable "a" which
277 buys us any efficiency. Since g is completely polymorphic in b there
278 ain't much point in making separate versions of g for the different
281 That suggests that we should identify which of g's type variables
282 are constrained (like "a") and which are unconstrained (like "b").
283 Then when taking equivalence classes in STEP 2, we ignore the type args
284 corresponding to unconstrained type variable. In STEP 3 we make
285 polymorphic versions. Thus:
287 f@t1/ = /\b -> <f_rhs> t1 b d1 d2
289 This seems pretty simple, and a Good Thing.
291 Polymorphism 3 -- Unboxed
294 If we are speciailising at unboxed types we must speciailise
295 regardless of the overloading constraint. In the exaple above it is
296 worth speciailising at types Int/Int#, Int/Bool# and a/Int#, Int#/Int#
299 Note that specialising an overloaded type at an uboxed type requires
300 an unboxed instance -- we cannot default to an unspecialised version!
307 f x = let g p q = p==q
313 Before specialisation, leaving out type abstractions we have
315 f df x = let g :: Eq a => a -> a -> Bool
317 h :: Num a => a -> a -> (a, Bool)
318 h dh r s = let deq = eqFromNum dh
319 in (+ dh r s, g deq r s)
323 After specialising h we get a specialised version of h, like this:
325 h' r s = let deq = eqFromNum df
326 in (+ df r s, g deq r s)
328 But we can't naively make an instance for g from this, because deq is not in scope
329 at the defn of g. Instead, we have to float out the (new) defn of deq
330 to widen its scope. Notice that this floating can't be done in advance -- it only
331 shows up when specialisation is done.
333 DELICATE MATTER: the way we tell a dictionary binding is by looking to
334 see if it has a Dict type. If the type has been "undictify'd", so that
335 it looks like a tuple, then the dictionary binding won't be floated, and
336 an opportunity to specialise might be lost.
338 User SPECIALIZE pragmas
339 ~~~~~~~~~~~~~~~~~~~~~~~
340 Specialisation pragmas can be digested by the type checker, and implemented
341 by adding extra definitions along with that of f, in the same way as before
343 f@t1/t2 = <f_rhs> t1 t2 d1 d2
345 Indeed the pragmas *have* to be dealt with by the type checker, because
346 only it knows how to build the dictionaries d1 and d2! For example
348 g :: Ord a => [a] -> [a]
349 {-# SPECIALIZE f :: [Tree Int] -> [Tree Int] #-}
351 Here, the specialised version of g is an application of g's rhs to the
352 Ord dictionary for (Tree Int), which only the type checker can conjure
353 up. There might not even *be* one, if (Tree Int) is not an instance of
354 Ord! (All the other specialision has suitable dictionaries to hand
357 Problem. The type checker doesn't have to hand a convenient <f_rhs>, because
358 it is buried in a complex (as-yet-un-desugared) binding group.
361 f@t1/t2 = f* t1 t2 d1 d2
363 where f* is the Id f with an IdInfo which says "inline me regardless!".
364 Indeed all the specialisation could be done in this way.
365 That in turn means that the simplifier has to be prepared to inline absolutely
366 any in-scope let-bound thing.
369 Again, the pragma should permit polymorphism in unconstrained variables:
371 h :: Ord a => [a] -> b -> b
372 {-# SPECIALIZE h :: [Int] -> b -> b #-}
374 We *insist* that all overloaded type variables are specialised to ground types,
375 (and hence there can be no context inside a SPECIALIZE pragma).
376 We *permit* unconstrained type variables to be specialised to
378 - or left as a polymorphic type variable
379 but nothing in between. So
381 {-# SPECIALIZE h :: [Int] -> [c] -> [c] #-}
383 is *illegal*. (It can be handled, but it adds complication, and gains the
387 SPECIALISING INSTANCE DECLARATIONS
388 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
391 instance Foo a => Foo [a] where
393 {-# SPECIALIZE instance Foo [Int] #-}
395 The original instance decl creates a dictionary-function
398 dfun.Foo.List :: forall a. Foo a -> Foo [a]
400 The SPECIALIZE pragma just makes a specialised copy, just as for
401 ordinary function definitions:
403 dfun.Foo.List@Int :: Foo [Int]
404 dfun.Foo.List@Int = dfun.Foo.List Int dFooInt
406 The information about what instance of the dfun exist gets added to
407 the dfun's IdInfo in the same way as a user-defined function too.
409 In fact, matters are a little bit more complicated than this.
410 When we make one of these specialised instances, we are defining
411 a constant dictionary, and so we want immediate access to its constant
412 methods and superclasses. Indeed, these constant methods and superclasses
413 must be in the IdInfo for the class selectors! We need help from the
414 typechecker to sort this out, perhaps by generating a separate IdInfo
417 Automatic instance decl specialisation?
418 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
419 Can instance decls be specialised automatically? It's tricky.
420 We could collect call-instance information for each dfun, but
421 then when we specialised their bodies we'd get new call-instances
422 for ordinary functions; and when we specialised their bodies, we might get
423 new call-instances of the dfuns, and so on. This all arises because of
424 the unrestricted mutual recursion between instance decls and value decls.
426 Furthermore, instance decls are usually exported and used non-locally,
427 so we'll want to compile enough to get those specialisations done.
429 Lastly, there's no such thing as a local instance decl, so we can
430 survive solely by spitting out *usage* information, and then reading that
431 back in as a pragma when next compiling the file. So for now,
432 we only specialise instance decls in response to pragmas.
434 That means that even if an instance decl ain't otherwise exported it
435 needs to be spat out as with a SPECIALIZE pragma. Furthermore, it needs
436 something to say which module defined the instance, so the usage info
437 can be fed into the right reqts info file. Blegh.
440 SPECIAILISING DATA DECLARATIONS
441 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
443 With unboxed specialisation (or full specialisation) we also require
444 data types (and their constructors) to be speciailised on unboxed
447 In addition to normal call instances we gather TyCon call instances at
448 unboxed types, determine equivalence classes for the locally defined
449 TyCons and build speciailised data constructor Ids for each TyCon and
450 substitute these in the Con calls.
452 We need the list of local TyCons to partition the TyCon instance info.
453 We pass out a FiniteMap from local TyCons to Specialised Instances to
454 give to the interface and code genertors.
456 N.B. The specialised data constructors reference the original data
457 constructor and type constructor which do not have the updated
458 specialisation info attached. Any specialisation info must be
459 extracted from the TyCon map returned.
462 SPITTING OUT USAGE INFORMATION
463 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
465 To spit out usage information we need to traverse the code collecting
466 call-instance information for all imported (non-prelude?) functions
467 and data types. Then we equivalence-class it and spit it out.
469 This is done at the top-level when all the call instances which escape
470 must be for imported functions and data types.
473 Partial specialisation by pragmas
474 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
475 What about partial specialisation:
477 k :: (Ord a, Eq b) => [a] -> b -> b -> [a]
478 {-# SPECIALIZE k :: Eq b => [Int] -> b -> b -> [a] #-}
482 {-# SPECIALIZE k :: Eq b => [Int] -> [b] -> [b] -> [a] #-}
484 Seems quite reasonable. Similar things could be done with instance decls:
486 instance (Foo a, Foo b) => Foo (a,b) where
488 {-# SPECIALIZE instance Foo a => Foo (a,Int) #-}
489 {-# SPECIALIZE instance Foo b => Foo (Int,b) #-}
491 Ho hum. Things are complex enough without this. I pass.
494 Requirements for the simplifer
495 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
496 The simplifier has to be able to take advantage of the specialisation.
498 * When the simplifier finds an application of a polymorphic f, it looks in
499 f's IdInfo in case there is a suitable instance to call instead. This converts
501 f t1 t2 d1 d2 ===> f_t1_t2
503 Note that the dictionaries get eaten up too!
505 * Dictionary selection operations on constant dictionaries must be
508 +.sel Int d ===> +Int
510 The obvious way to do this is in the same way as other specialised
511 calls: +.sel has inside it some IdInfo which tells that if it's applied
512 to the type Int then it should eat a dictionary and transform to +Int.
514 In short, dictionary selectors need IdInfo inside them for constant
517 * Exactly the same applies if a superclass dictionary is being
520 Eq.sel Int d ===> dEqInt
522 * Something similar applies to dictionary construction too. Suppose
523 dfun.Eq.List is the function taking a dictionary for (Eq a) to
524 one for (Eq [a]). Then we want
526 dfun.Eq.List Int d ===> dEq.List_Int
528 Where does the Eq [Int] dictionary come from? It is built in
529 response to a SPECIALIZE pragma on the Eq [a] instance decl.
531 In short, dfun Ids need IdInfo with a specialisation for each
532 constant instance of their instance declaration.
535 What does the specialisation IdInfo look like?
536 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
539 [Maybe Type] -- Instance types
540 Int -- No of dicts to eat
541 Id -- Specialised version
543 For example, if f has this SpecInfo:
545 SpecInfo [Just t1, Nothing, Just t3] 2 f'
549 f t1 t2 t3 d1 d2 ===> f t2
551 The "Nothings" identify type arguments in which the specialised
552 version is polymorphic.
554 What can't be done this way?
555 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
556 There is no way, post-typechecker, to get a dictionary for (say)
557 Eq a from a dictionary for Eq [a]. So if we find
561 we can't transform to
566 eqList :: (a->a->Bool) -> [a] -> [a] -> Bool
568 Of course, we currently have no way to automatically derive
569 eqList, nor to connect it to the Eq [a] instance decl, but you
570 can imagine that it might somehow be possible. Taking advantage
571 of this is permanently ruled out.
573 Still, this is no great hardship, because we intend to eliminate
574 overloading altogether anyway!
579 What about types/classes mentioned in SPECIALIZE pragmas spat out,
580 but not otherwise exported. Even if they are exported, what about
581 their original names.
583 Suggestion: use qualified names in pragmas, omitting module for
584 prelude and "this module".
591 f a (d::Num a) = let g = ...
593 ...(let d1::Ord a = Num.Ord.sel a d in g a d1)...
595 Here, g is only called at one type, but the dictionary isn't in scope at the
596 definition point for g. Usually the type checker would build a
597 definition for d1 which enclosed g, but the transformation system
598 might have moved d1's defn inward.
604 What should we do when a value is specialised to a *strict* unboxed value?
606 map_*_* f (x:xs) = let h = f x
610 Could convert let to case:
612 map_*_Int# f (x:xs) = case f x of h# ->
616 This may be undesirable since it forces evaluation here, but the value
617 may not be used in all branches of the body. In the general case this
618 transformation is impossible since the mutual recursion in a letrec
619 cannot be expressed as a case.
621 There is also a problem with top-level unboxed values, since our
622 implementation cannot handle unboxed values at the top level.
624 Solution: Lift the binding of the unboxed value and extract it when it
627 map_*_Int# f (x:xs) = let h = case (f x) of h# -> _Lift h#
632 Now give it to the simplifier and the _Lifting will be optimised away.
634 The benfit is that we have given the specialised "unboxed" values a
635 very simple lifted semantics and then leave it up to the simplifier to
636 optimise it --- knowing that the overheads will be removed in nearly
639 In particular, the value will only be evaluted in the branches of the
640 program which use it, rather than being forced at the point where the
641 value is bound. For example:
643 filtermap_*_* p f (x:xs)
650 filtermap_*_Int# p f (x:xs)
651 = let h = case (f x) of h# -> _Lift h#
654 True -> case h of _Lift h#
658 The binding for h can still be inlined in the one branch and the
662 Question: When won't the _Lifting be eliminated?
664 Answer: When they at the top-level (where it is necessary) or when
665 inlining would duplicate work (or possibly code depending on
666 options). However, the _Lifting will still be eliminated if the
667 strictness analyser deems the lifted binding strict.
670 A note about non-tyvar dictionaries
671 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
672 Some Ids have types like
674 forall a,b,c. Eq a -> Ord [a] -> tau
676 This seems curious at first, because we usually only have dictionary
677 args whose types are of the form (C a) where a is a type variable.
678 But this doesn't hold for the functions arising from instance decls,
679 which sometimes get arguements with types of form (C (T a)) for some
682 Should we specialise wrt this compound-type dictionary? We used to say
684 "This is a heuristic judgement, as indeed is the fact that we
685 specialise wrt only dictionaries. We choose *not* to specialise
686 wrt compound dictionaries because at the moment the only place
687 they show up is in instance decls, where they are simply plugged
688 into a returned dictionary. So nothing is gained by specialising
691 But it is simpler and more uniform to specialise wrt these dicts too;
692 and in future GHC is likely to support full fledged type signatures
694 f ;: Eq [(a,b)] => ...
697 %************************************************************************
699 \subsubsection[CallInstances]{@CallInstances@ data type}
701 %************************************************************************
704 type FreeVarsSet = IdSet
705 type FreeTyVarsSet = TyVarSet
709 Id -- This Id; *new* ie *cloned* id
710 [Maybe Type] -- Specialised at these types (*new*, cloned)
711 -- Nothing => no specialisation on this type arg
712 -- is required (flag dependent).
713 [CoreArg] -- And these dictionaries; all ValArgs
714 FreeVarsSet -- Free vars of the dict-args in terms of *new* ids
715 (Maybe SpecInfo) -- For specialisation with explicit SpecId
719 pprCI :: CallInstance -> Doc
720 pprCI (CallInstance id spec_tys dicts _ maybe_specinfo)
721 = hang (hsep [ptext SLIT("Call inst for"), ppr PprDebug id])
722 4 (vcat [hsep (text "types" : [pprMaybeTy PprDebug ty | ty <- spec_tys]),
723 case maybe_specinfo of
724 Nothing -> hsep (text "dicts" : [ppr_arg PprDebug dict | dict <- dicts])
725 Just (SpecInfo _ _ spec_id)
726 -> hsep [ptext SLIT("Explicit SpecId"), ppr PprDebug spec_id]
729 -- ToDo: instance Outputable CoreArg?
730 ppr_arg sty (TyArg t) = ppr sty t
731 ppr_arg sty (LitArg i) = ppr sty i
732 ppr_arg sty (VarArg v) = ppr sty v
734 isUnboxedCI :: CallInstance -> Bool
735 isUnboxedCI (CallInstance _ spec_tys _ _ _)
736 = any isUnboxedType (catMaybes spec_tys)
738 isExplicitCI :: CallInstance -> Bool
739 isExplicitCI (CallInstance _ _ _ _ (Just _))
741 isExplicitCI (CallInstance _ _ _ _ Nothing)
745 Comparisons are based on the {\em types}, ignoring the dictionary args:
749 cmpCI :: CallInstance -> CallInstance -> TAG_
750 cmpCI (CallInstance id1 tys1 _ _ _) (CallInstance id2 tys2 _ _ _)
751 = cmp id1 id2 `thenCmp` cmpUniTypeMaybeList tys1 tys2
753 cmpCI_tys :: CallInstance -> CallInstance -> TAG_
754 cmpCI_tys (CallInstance _ tys1 _ _ _) (CallInstance _ tys2 _ _ _)
755 = cmpUniTypeMaybeList tys1 tys2
757 eqCI_tys :: CallInstance -> CallInstance -> Bool
759 = case cmpCI_tys c1 c2 of { EQ_ -> True; other -> False }
761 isCIofTheseIds :: [Id] -> CallInstance -> Bool
762 isCIofTheseIds ids (CallInstance ci_id _ _ _ _)
763 = any ((==) ci_id) ids
765 singleCI :: Id -> [Maybe Type] -> [CoreArg] -> UsageDetails
766 singleCI id tys dicts
767 = UsageDetails (unitBag (CallInstance id tys dicts fv_set Nothing))
768 emptyBag [] emptyIdSet 0 0
770 fv_set = mkIdSet (id : [dict | (VarArg dict) <- dicts])
772 explicitCI :: Id -> [Maybe Type] -> SpecInfo -> UsageDetails
773 explicitCI id tys specinfo
774 = UsageDetails (unitBag call_inst) emptyBag [] emptyIdSet 0 0
776 call_inst = CallInstance id tys dicts fv_set (Just specinfo)
777 dicts = panic "Specialise:explicitCI:dicts"
778 fv_set = unitIdSet id
780 -- We do not process the CIs for top-level dfuns or defms
781 -- Instead we require an explicit SPEC inst pragma for dfuns
782 -- and an explict method within any instances for the defms
784 getCIids :: Bool -> [Id] -> [Id]
785 getCIids True ids = filter not_dict_or_defm ids
789 = not (isDictTy (idType id) || maybeToBool (isDefaultMethodId_maybe id))
791 getCIs :: Bool -> [Id] -> UsageDetails -> ([CallInstance], UsageDetails)
792 getCIs top_lev ids (UsageDetails cis tycon_cis dbs fvs c i)
794 (cis_here, cis_not_here) = partitionBag (isCIofTheseIds (getCIids top_lev ids)) cis
795 cis_here_list = bagToList cis_here
797 -- pprTrace "getCIs:"
798 -- (hang (hcat [char '{',
799 -- interppSP PprDebug ids,
801 -- 4 (vcat (map pprCI cis_here_list)))
802 (cis_here_list, UsageDetails cis_not_here tycon_cis dbs fvs c i)
804 dumpCIs :: Bag CallInstance -- The call instances
805 -> Bool -- True <=> top level bound Ids
806 -> Bool -- True <=> dict bindings to be floated (specBind only)
807 -> [CallInstance] -- Call insts for bound ids (instBind only)
808 -> [Id] -- Bound ids *new*
809 -> [Id] -- Full bound ids: includes dumped dicts
810 -> Bag CallInstance -- Kept call instances
812 -- CIs are dumped if:
813 -- 1) they are a CI for one of the bound ids, or
814 -- 2) they mention any of the dicts in a local unfloated binding
816 -- For top-level bindings we allow the call instances to
817 -- float past a dict bind and place all the top-level binds
818 -- in a *global* Rec.
819 -- We leave it to the simplifier will sort it all out ...
821 dumpCIs cis top_lev floating inst_cis bound_ids full_ids
822 = (if not (isEmptyBag cis_of_bound_id) &&
823 not (isEmptyBag cis_of_bound_id_without_inst_cis)
825 pprTrace ("dumpCIs: dumping CI which was not instantiated ... \n" ++
826 " (may be a non-HM recursive call)\n")
827 (hang (hcat [char '{',
828 interppSP PprDebug bound_ids,
830 4 (vcat [ptext SLIT("Dumping CIs:"),
831 vcat (map pprCI (bagToList cis_of_bound_id)),
832 ptext SLIT("Instantiating CIs:"),
833 vcat (map pprCI inst_cis)]))
835 if top_lev || floating then
838 (if not (isEmptyBag cis_dump_unboxed)
839 then pprTrace "dumpCIs: bound dictionary arg ... WITH UNBOXED TYPES!\n"
840 (hang (hcat [char '{',
841 interppSP PprDebug full_ids,
843 4 (vcat (map pprCI (bagToList cis_dump))))
845 cis_keep_not_bound_id
848 (cis_of_bound_id, cis_not_bound_id)
849 = partitionBag (isCIofTheseIds (getCIids top_lev bound_ids)) cis
851 (cis_dump, cis_keep_not_bound_id)
852 = partitionBag ok_to_dump_ci cis_not_bound_id
854 ok_to_dump_ci (CallInstance _ _ _ fv_set _)
855 = any (\ i -> i `elementOfIdSet` fv_set) full_ids
857 (_, cis_of_bound_id_without_inst_cis) = partitionBag have_inst_ci cis_of_bound_id
858 have_inst_ci ci = any (eqCI_tys ci) inst_cis
860 (cis_dump_unboxed, _) = partitionBag isUnboxedCI cis_dump
864 Any call instances of a bound_id can be safely dumped, because any
865 recursive calls should be at the same instance as the parent instance.
867 letrec f = /\a -> \x::a -> ...(f t x')...
869 Here, the type, t, at which f is used in its own RHS should be
870 just "a"; that is, the recursive call is at the same type as
871 the original call. That means that when specialising f at some
872 type, say Int#, we shouldn't find any *new* instances of f
873 arising from specialising f's RHS. The only instance we'll find
874 is another call of (f Int#).
876 We check this in dumpCIs by passing in all the instantiated call
877 instances (inst_cis) and reporting any dumped cis (cis_of_bound_id)
878 for which there is no such instance.
880 We also report CIs dumped due to a bound dictionary arg if they
881 contain unboxed types.
883 %************************************************************************
885 \subsubsection[TyConInstances]{@TyConInstances@ data type}
887 %************************************************************************
891 = TyConInstance TyCon -- Type Constructor
892 [Maybe Type] -- Applied to these specialising types
894 cmpTyConI :: TyConInstance -> TyConInstance -> TAG_
895 cmpTyConI (TyConInstance tc1 tys1) (TyConInstance tc2 tys2)
896 = cmp tc1 tc2 `thenCmp` cmpUniTypeMaybeList tys1 tys2
898 cmpTyConI_tys :: TyConInstance -> TyConInstance -> TAG_
899 cmpTyConI_tys (TyConInstance _ tys1) (TyConInstance _ tys2)
900 = cmpUniTypeMaybeList tys1 tys2
902 singleTyConI :: TyCon -> [Maybe Type] -> UsageDetails
903 singleTyConI ty_con spec_tys
904 = UsageDetails emptyBag (unitBag (TyConInstance ty_con spec_tys)) [] emptyIdSet 0 0
906 isTyConIofThisTyCon :: TyCon -> TyConInstance -> Bool
907 isTyConIofThisTyCon ty_con (TyConInstance inst_ty_con _) = ty_con == inst_ty_con
909 isLocalSpecTyConI :: Bool -> TyConInstance -> Bool
910 isLocalSpecTyConI comp_prel (TyConInstance inst_ty_con _) = isLocalSpecTyCon comp_prel inst_ty_con
912 getLocalSpecTyConIs :: Bool -> UsageDetails -> ([TyConInstance], UsageDetails)
913 getLocalSpecTyConIs comp_prel (UsageDetails cis tycon_cis dbs fvs c i)
915 (tycon_cis_local, tycon_cis_global)
916 = partitionBag (isLocalSpecTyConI comp_prel) tycon_cis
917 tycon_cis_local_list = bagToList tycon_cis_local
919 (tycon_cis_local_list, UsageDetails cis tycon_cis_global dbs fvs c i)
923 %************************************************************************
925 \subsubsection[UsageDetails]{@UsageDetails@ data type}
927 %************************************************************************
932 (Bag CallInstance) -- The collection of call-instances
933 (Bag TyConInstance) -- Constructor call-instances
934 [DictBindDetails] -- Dictionary bindings in data-dependence order!
935 FreeVarsSet -- Free variables (excl imported ones, incl top level) (cloned)
936 Int -- no. of spec calls
937 Int -- no. of spec insts
940 The DictBindDetails are fully processed; their call-instance
941 information is incorporated in the call-instances of the UsageDetails
942 which includes the DictBindDetails. The free vars in a usage details
943 will *include* the binders of the DictBind details.
945 A @DictBindDetails@ contains bindings for dictionaries *only*.
950 [Id] -- Main binders, originally visible in scope of binding (cloned)
951 CoreBinding -- Fully processed
952 FreeVarsSet -- Free in binding group (cloned)
953 FreeTyVarsSet -- Free in binding group
957 emptyUDs :: UsageDetails
958 unionUDs :: UsageDetails -> UsageDetails -> UsageDetails
959 unionUDList :: [UsageDetails] -> UsageDetails
961 -- tickSpecCall :: Bool -> UsageDetails -> UsageDetails
962 tickSpecInsts :: UsageDetails -> UsageDetails
964 -- tickSpecCall found (UsageDetails cis ty_cis dbs fvs c i)
965 -- = UsageDetails cis ty_cis dbs fvs (c + (if found then 1 else 0)) i
967 tickSpecInsts (UsageDetails cis ty_cis dbs fvs c i)
968 = UsageDetails cis ty_cis dbs fvs c (i+1)
970 emptyUDs = UsageDetails emptyBag emptyBag [] emptyIdSet 0 0
972 unionUDs (UsageDetails cis1 tycon_cis1 dbs1 fvs1 c1 i1) (UsageDetails cis2 tycon_cis2 dbs2 fvs2 c2 i2)
973 = UsageDetails (unionBags cis1 cis2) (unionBags tycon_cis1 tycon_cis2)
974 (dbs1 ++ dbs2) (fvs1 `unionIdSets` fvs2) (c1+c2) (i1+i2)
975 -- The append here is really redundant, since the bindings don't
976 -- scope over each other. ToDo.
978 unionUDList = foldr unionUDs emptyUDs
980 singleFvUDs (VarArg v) | not (isImportedId v)
981 = UsageDetails emptyBag emptyBag [] (unitIdSet v) 0 0
985 singleConUDs con = UsageDetails emptyBag emptyBag [] (unitIdSet con) 0 0
987 dumpDBs :: [DictBindDetails]
988 -> Bool -- True <=> top level bound Ids
989 -> [TyVar] -- TyVars being bound (cloned)
990 -> [Id] -- Ids being bound (cloned)
991 -> FreeVarsSet -- Fvs of body
992 -> ([CoreBinding], -- These ones have to go here
993 [DictBindDetails], -- These can float further
994 [Id], -- Incoming list + names of dicts bound here
995 FreeVarsSet -- Incoming fvs + fvs of dicts bound here
998 -- It is just to complex to try to float top-level
999 -- dict bindings with constant methods, inst methods,
1000 -- auxillary derived instance defns and user instance
1001 -- defns all getting in the way.
1002 -- So we dump all dbinds as soon as we get to the top
1003 -- level and place them in a *global* Rec.
1004 -- We leave it to the simplifier will sort it all out ...
1006 dumpDBs [] top_lev bound_tyvars bound_ids fvs
1007 = ([], [], bound_ids, fvs)
1009 dumpDBs ((db@(DictBindDetails dbinders dbind db_fvs db_ftv)):dbs)
1010 top_lev bound_tyvars bound_ids fvs
1012 || any (\ i -> i `elementOfIdSet` db_fvs) bound_ids
1013 || any (\ t -> t `elementOfTyVarSet` db_ftv) bound_tyvars
1014 = let -- Ha! Dump it!
1015 (dbinds_here, dbs_outer, full_bound_ids, full_fvs)
1016 = dumpDBs dbs top_lev bound_tyvars (dbinders ++ bound_ids) (db_fvs `unionIdSets` fvs)
1018 (dbind : dbinds_here, dbs_outer, full_bound_ids, full_fvs)
1020 | otherwise -- This one can float out further
1022 (dbinds_here, dbs_outer, full_bound_ids, full_fvs)
1023 = dumpDBs dbs top_lev bound_tyvars bound_ids fvs
1025 (dbinds_here, db : dbs_outer, full_bound_ids, full_fvs)
1029 dumpUDs :: UsageDetails
1030 -> Bool -- True <=> top level bound Ids
1031 -> Bool -- True <=> dict bindings to be floated (specBind only)
1032 -> [CallInstance] -- Call insts for bound Ids (instBind only)
1033 -> [Id] -- Ids which are just being bound; *new*
1034 -> [TyVar] -- TyVars which are just being bound
1035 -> ([CoreBinding], -- Bindings from UsageDetails which mention the ids
1036 UsageDetails) -- The above bindings removed, and
1037 -- any call-instances which mention the ids dumped too
1039 dumpUDs (UsageDetails cis tycon_cis dbs fvs c i) top_lev floating inst_cis bound_ids tvs
1041 (dict_binds_here, dbs_outer, full_bound_ids, full_fvs)
1042 = dumpDBs dbs top_lev tvs bound_ids fvs
1043 cis_outer = dumpCIs cis top_lev floating inst_cis bound_ids full_bound_ids
1044 fvs_outer = full_fvs `minusIdSet` (mkIdSet full_bound_ids)
1046 (dict_binds_here, UsageDetails cis_outer tycon_cis dbs_outer fvs_outer c i)
1050 addDictBinds :: [Id] -> CoreBinding -> UsageDetails -- Dict binding and RHS usage
1051 -> UsageDetails -- The usage to augment
1053 addDictBinds dbinders dbind (UsageDetails db_cis db_tycon_cis db_dbs db_fvs db_c db_i)
1054 (UsageDetails cis tycon_cis dbs fvs c i)
1055 = UsageDetails (db_cis `unionBags` cis)
1056 (db_tycon_cis `unionBags` tycon_cis)
1057 (db_dbs ++ [DictBindDetails dbinders dbind db_fvs db_ftvs] ++ dbs)
1059 -- NB: We ignore counts from dictbinds since it is not user code
1061 -- The free tyvars of the dictionary bindings should really be
1062 -- gotten from the RHSs, but I'm pretty sure it's good enough just
1063 -- to look at the type of the dictionary itself.
1064 -- Doing the proper job would entail keeping track of free tyvars as
1065 -- well as free vars, which would be a bore.
1066 db_ftvs = tyVarsOfTypes (map idType dbinders)
1069 %************************************************************************
1071 \subsection[cloning-binders]{The Specialising IdEnv and CloneInfo}
1073 %************************************************************************
1075 @SpecIdEnv@ maps old Ids to their new "clone". There are three cases:
1077 1) (NoLift LitArg l) : an Id which is bound to a literal
1079 2) (NoLift LitArg l) : an Id bound to a "new" Id
1080 The new Id is a possibly-type-specialised clone of the original
1082 3) Lifted lifted_id unlifted_id :
1084 This indicates that the original Id has been specialised to an
1085 unboxed value which must be lifted (see "Unboxed bindings" above)
1086 @unlifted_id@ is the unboxed clone of the original Id
1087 @lifted_id@ is a *lifted* version of the original Id
1089 When you lookup Ids which are Lifted, you have to insert a case
1090 expression to un-lift the value (done with @bindUnlift@)
1092 You also have to insert a case to lift the value in the binding
1093 (done with @liftExpr@)
1097 type SpecIdEnv = IdEnv CloneInfo
1100 = NoLift CoreArg -- refers to cloned id or literal
1102 | Lifted Id -- lifted, cloned id
1103 Id -- unlifted, cloned id
1107 %************************************************************************
1109 \subsection[specialise-data]{Data returned by specialiser}
1111 %************************************************************************
1118 -- True <=> Specialisation performed
1120 -- False <=> Specialisation completed with errors
1123 -- Local tycons declared in this module
1126 -- Those in-scope data types for which we want to
1127 -- generate code for their constructors.
1128 -- Namely: data types declared in this module +
1129 -- any big tuples used in this module
1130 -- The initial (and default) value is the local tycons
1132 (FiniteMap TyCon [(Bool, [Maybe Type])])
1133 -- TyCon specialisations to be generated
1134 -- We generate specialialised code (Bool=True) for data types
1135 -- defined in this module and any tuples used in this module
1136 -- The initial (and default) value is the specialisations
1137 -- requested by source-level SPECIALIZE data pragmas (Bool=True)
1138 -- and _SPECIALISE_ pragmas (Bool=False) in the interface files
1140 (Bag (Id,[Maybe Type]))
1141 -- Imported specialisation errors
1142 (Bag (Id,[Maybe Type]))
1143 -- Imported specialisation warnings
1144 (Bag (TyCon,[Maybe Type]))
1145 -- Imported TyCon specialisation errors
1147 initSpecData local_tycons tycon_specs
1148 = SpecData False True local_tycons local_tycons tycon_specs emptyBag emptyBag emptyBag
1153 ToDo[sansom]: Transformation data to process specialisation requests.
1155 %************************************************************************
1157 \subsection[specProgram]{Specialising a core program}
1159 %************************************************************************
1162 specProgram :: UniqSupply
1163 -> [CoreBinding] -- input ...
1165 -> ([CoreBinding], -- main result
1166 SpecialiseData) -- result specialise data
1168 specProgram uniqs binds
1169 (SpecData False _ local_tycons _ init_specs init_errs init_warn init_tyerrs)
1170 = case (initSM (specTyConsAndScope (specTopBinds binds)) uniqs) of
1171 (final_binds, tycon_specs_list,
1172 UsageDetails import_cis import_tycis _ fvs spec_calls spec_insts)
1174 used_conids = filter isDataCon (uniqSetToList fvs)
1175 used_tycons = map dataConTyCon used_conids
1176 used_gen = filter isLocalGenTyCon used_tycons
1177 gen_tycons = uniqSetToList (mkUniqSet local_tycons `unionUniqSets` mkUniqSet used_gen)
1179 result_specs = addListToFM_C (++) init_specs tycon_specs_list
1181 uniq_cis = map head (equivClasses cmpCI (bagToList import_cis))
1182 cis_list = [(id, tys) | CallInstance id tys _ _ _ <- uniq_cis]
1183 (cis_unboxed, cis_other) = partition (isUnboxedSpecialisation . snd) cis_list
1184 cis_warn = init_warn `unionBags` listToBag cis_other
1185 cis_errs = init_errs `unionBags` listToBag cis_unboxed
1187 uniq_tycis = map head (equivClasses cmpTyConI (bagToList import_tycis))
1188 tycis_unboxed = [(con, tys) | TyConInstance con tys <- uniq_tycis]
1189 tycis_errs = init_tyerrs `unionBags` listToBag tycis_unboxed
1191 no_errs = isEmptyBag cis_errs && isEmptyBag tycis_errs
1192 && (not opt_SpecialiseImports || isEmptyBag cis_warn)
1194 (if opt_D_simplifier_stats then
1195 pprTrace "\nSpecialiser Stats:\n" (vcat [
1196 hcat [ptext SLIT("SpecCalls "), int spec_calls],
1197 hcat [ptext SLIT("SpecInsts "), int spec_insts],
1202 SpecData True no_errs local_tycons gen_tycons result_specs
1203 cis_errs cis_warn tycis_errs)
1205 specProgram uniqs binds (SpecData True _ _ _ _ _ _ _)
1206 = panic "Specialise:specProgram: specialiser called more than once"
1208 -- It may be possible safely to call the specialiser more than once,
1209 -- but I am not sure there is any benefit in doing so (Patrick)
1211 -- ToDo: What about unfoldings performed after specialisation ???
1214 %************************************************************************
1216 \subsection[specTyConsAndScope]{Specialising data constructors within tycons}
1218 %************************************************************************
1220 In the specialiser we just collect up the specialisations which will
1221 be required. We don't create the specialised constructors in
1222 Core. These are only introduced when we convert to StgSyn.
1224 ToDo: Perhaps this collection should be done in CoreToStg to ensure no inconsistencies!
1227 specTyConsAndScope :: SpecM ([CoreBinding], UsageDetails)
1228 -> SpecM ([CoreBinding], [(TyCon,[(Bool,[Maybe Type])])], UsageDetails)
1230 specTyConsAndScope scopeM
1231 = scopeM `thenSM` \ (binds, scope_uds) ->
1233 (tycons_cis, gotci_scope_uds)
1234 = getLocalSpecTyConIs opt_CompilingGhcInternals scope_uds
1236 tycon_specs_list = collectTyConSpecs tycons_cis
1238 (if opt_SpecialiseTrace && not (null tycon_specs_list) then
1239 pprTrace "Specialising TyCons:\n"
1240 (vcat [ if not (null specs) then
1241 hang (hsep [(ppr PprDebug tycon), ptext SLIT("at types")])
1242 4 (vcat (map pp_specs specs))
1244 | (tycon, specs) <- tycon_specs_list])
1246 returnSM (binds, tycon_specs_list, gotci_scope_uds)
1249 collectTyConSpecs []
1251 collectTyConSpecs tycons_cis@(TyConInstance tycon _ : _)
1252 = (tycon, tycon_specs) : collectTyConSpecs other_tycons_cis
1254 (tycon_cis, other_tycons_cis) = partition (isTyConIofThisTyCon tycon) tycons_cis
1255 uniq_cis = map head (equivClasses cmpTyConI_tys tycon_cis)
1256 tycon_specs = [(False, spec_tys) | TyConInstance _ spec_tys <- uniq_cis]
1258 pp_specs (False, spec_tys) = hsep [pprMaybeTy PprDebug spec_ty | spec_ty <- spec_tys]
1262 %************************************************************************
1264 \subsection[specTopBinds]{Specialising top-level bindings}
1266 %************************************************************************
1269 specTopBinds :: [CoreBinding]
1270 -> SpecM ([CoreBinding], UsageDetails)
1273 = spec_top_binds binds `thenSM` \ (binds, UsageDetails cis tycis dbind_details fvs c i) ->
1275 -- Add bindings for floated dbinds and collect fvs
1276 -- In actual fact many of these bindings are dead code since dict
1277 -- arguments are dropped when a specialised call is created
1278 -- The simplifier should be able to cope ...
1280 (dbinders_s, dbinds, dfvs_s)
1281 = unzip3 [(dbinders, dbind, dfvs) | DictBindDetails dbinders dbind dfvs _ <- dbind_details]
1283 full_fvs = fvs `unionIdSets` unionManyIdSets dfvs_s
1284 fvs_outer = full_fvs `minusIdSet` (mkIdSet (concat dbinders_s))
1286 -- It is just to complex to try to sort out top-level dependencies
1287 -- So we just place all the top-level binds in a *global* Rec and
1288 -- leave it to the simplifier to sort it all out ...
1291 returnSM ([Rec (pairsFromCoreBinds binds)], UsageDetails cis tycis [] fvs_outer c i)
1294 spec_top_binds (first_bind:rest_binds)
1295 = specBindAndScope True first_bind (
1296 spec_top_binds rest_binds `thenSM` \ (rest_binds, rest_uds) ->
1297 returnSM (ItsABinds rest_binds, rest_uds)
1298 ) `thenSM` \ (first_binds, ItsABinds rest_binds, all_uds) ->
1299 returnSM (first_binds ++ rest_binds, all_uds)
1302 = returnSM ([], emptyUDs)
1305 %************************************************************************
1307 \subsection[specExpr]{Specialising expressions}
1309 %************************************************************************
1312 specExpr :: CoreExpr
1313 -> [CoreArg] -- The arguments:
1314 -- TypeArgs are speced
1315 -- ValArgs are unprocessed
1316 -> SpecM (CoreExpr, -- Result expression with specialised versions installed
1317 UsageDetails)-- Details of usage of enclosing binders in the result
1320 specExpr (Var v) args
1321 = specId v $ \ v_arg ->
1323 LitArg lit -> ASSERT( null args )
1324 returnSM (Lit lit, emptyUDs)
1326 VarArg new_v -> mkCallInstance v new_v args `thenSM` \ uds ->
1327 returnSM (mkGenApp (Var new_v) args, uds)
1329 specExpr expr@(Lit _) null_args
1330 = ASSERT (null null_args)
1331 returnSM (expr, emptyUDs)
1333 specExpr (Con con args) null_args
1334 = ASSERT (null null_args)
1335 specArgs args $ \ args' ->
1336 mkTyConInstance con args' `thenSM` \ con_uds ->
1337 returnSM (Con con args', con_uds)
1339 specExpr (Prim op@(CCallOp str is_asm may_gc arg_tys res_ty) args) null_args
1340 = ASSERT (null null_args)
1341 specArgs args $ \ args' ->
1342 mapSM specTy arg_tys `thenSM` \ arg_tys' ->
1343 specTy res_ty `thenSM` \ res_ty' ->
1344 returnSM (Prim (CCallOp str is_asm may_gc arg_tys' res_ty') args', emptuUDs)
1346 specExpr (Prim prim args) null_args
1347 = ASSERT (null null_args)
1348 specArgs args $ \ args' ->
1349 -- specPrimOp prim tys `thenSM` \ (prim, tys, prim_uds) ->
1350 returnSM (Prim prim args', emptyUDs {-`unionUDs` prim_uds-} )
1354 specPrimOp :: PrimOp
1360 -- Checks that PrimOp can handle (possibly unboxed) tys passed
1361 -- and/or chooses PrimOp specialised to any unboxed tys
1362 -- Errors are dealt with by returning a PrimOp call instance
1363 -- which will result in a cis_errs message
1365 -- ToDo: Deal with checkSpecTyApp for Prim in CoreLint
1369 specExpr (App fun arg) args
1370 = specArg arg `thenSM` \ new_arg ->
1371 specExpr fun (new_arg : args) `thenSM` \ (expr,uds) ->
1372 returnSM (expr, uds)
1374 specExpr (Lam (ValBinder binder) body) (arg : args) | isValArg arg
1375 = lookup_arg arg `thenSM` \ arg ->
1376 bindId binder arg (specExpr body args)
1378 lookup_arg (LitArg l) = returnSM (NoLift (LitArg l))
1379 lookup_arg (VarArg v) = lookupId v
1381 specExpr (Lam (ValBinder binder) body) []
1382 = specLambdaOrCaseBody [binder] body [] `thenSM` \ ([binder], body, uds) ->
1383 returnSM (Lam (ValBinder binder) body, uds)
1385 specExpr (Lam (TyBinder tyvar) body) (TyArg ty : args)
1386 = -- Type lambda with argument; argument already spec'd
1387 bindTyVar tyvar ty ( specExpr body args )
1389 specExpr (Lam (TyBinder tyvar) body) []
1391 cloneTyVarSM tyvar `thenSM` \ new_tyvar ->
1392 bindTyVar tyvar (mkTyVarTy new_tyvar) (
1393 specExpr body [] `thenSM` \ (body, body_uds) ->
1395 (binds_here, final_uds) = dumpUDs body_uds False False [] [] [new_tyvar]
1397 returnSM (Lam (TyBinder new_tyvar)
1398 (mkCoLetsNoUnboxed binds_here body),
1402 specExpr (Case scrutinee alts) args
1403 = specExpr scrutinee [] `thenSM` \ (scrutinee, scrut_uds) ->
1404 specAlts alts scrutinee_type args `thenSM` \ (alts, alts_uds) ->
1405 returnSM (Case scrutinee alts, scrut_uds `unionUDs` alts_uds)
1407 scrutinee_type = coreExprType scrutinee
1409 specExpr (Let bind body) args
1410 = specBindAndScope False bind (
1411 specExpr body args `thenSM` \ (body, body_uds) ->
1412 returnSM (ItsAnExpr body, body_uds)
1413 ) `thenSM` \ (binds, ItsAnExpr body, all_uds) ->
1414 returnSM (mkCoLetsUnboxedToCase binds body, all_uds)
1416 specExpr (SCC cc expr) args
1417 = specExpr expr [] `thenSM` \ (expr, expr_uds) ->
1418 mapAndUnzip3SM specOutArg args `thenSM` \ (args, args_uds_s, unlifts) ->
1421 = if squashableDictishCcExpr cc expr -- can toss the _scc_
1425 returnSM (applyBindUnlifts unlifts (mkGenApp scc_expr args),
1426 unionUDList args_uds_s `unionUDs` expr_uds)
1428 specExpr (Coerce _ _ _) args = panic "Specialise.specExpr:Coerce"
1430 -- ToDo: This may leave some unspec'd dictionaries!!
1433 %************************************************************************
1435 \subsubsection{Specialising a lambda}
1437 %************************************************************************
1440 specLambdaOrCaseBody :: [Id] -- The binders
1441 -> CoreExpr -- The body
1442 -> [CoreArg] -- Its args
1443 -> SpecM ([Id], -- New binders
1444 CoreExpr, -- New body
1447 specLambdaOrCaseBody bound_ids body args
1448 = cloneLambdaOrCaseBinders bound_ids `thenSM` \ (new_ids, clone_infos) ->
1449 bindIds bound_ids clone_infos (
1451 specExpr body args `thenSM` \ (body, body_uds) ->
1454 -- Dump any dictionary bindings (and call instances)
1455 -- from the scope which mention things bound here
1456 (binds_here, final_uds) = dumpUDs body_uds False False [] new_ids []
1458 returnSM (new_ids, mkCoLetsNoUnboxed binds_here body, final_uds)
1461 -- ToDo: Opportunity here to common-up dictionaries with same type,
1462 -- thus avoiding recomputation.
1465 A variable bound in a lambda or case is normally monomorphic so no
1466 specialised versions will be required. This is just as well since we
1467 do not know what code to specialise!
1469 Unfortunately this is not always the case. For example a class Foo
1470 with polymorphic methods gives rise to a dictionary with polymorphic
1471 components as follows:
1478 instance Foo Int where
1486 d.Foo.Int :: ( \/b . Int -> b -> Int, \/c . Int -> c -> Int )
1487 d.Foo.Int = (op1_Int, op2_Int)
1489 op1 = /\ a b -> \ dFoo -> case dFoo of (meth1, _) -> meth1 b
1491 ... op1 {Int Int#} d.Foo.Int 1 3# ...
1494 N.B. The type of the dictionary is not Hindley Milner!
1496 Now we must specialise op1 at {* Int#} which requires a version of
1497 meth1 at {Int#}. But since meth1 was extracted from a dictionary we do
1498 not have access to its code to create the specialised version.
1500 If we specialise on overloaded types as well we specialise op1 at
1501 {Int Int#} d.Foo.Int:
1503 op1_Int_Int# = case d.Foo.Int of (meth1, _) -> meth1 {Int#}
1505 Though this is still invalid, after further simplification we get:
1507 op1_Int_Int# = opInt1 {Int#}
1509 Another round of specialisation will result in the specialised
1510 version of op1Int being called directly.
1512 For now we PANIC if a polymorphic lambda/case bound variable is found
1513 in a call instance with an unboxed type. Other call instances, arising
1514 from overloaded type arguments, are discarded since the unspecialised
1515 version extracted from the method can be called as normal.
1517 ToDo: Implement and test second round of specialisation.
1520 %************************************************************************
1522 \subsubsection{Specialising case alternatives}
1524 %************************************************************************
1528 specAlts (AlgAlts alts deflt) scrutinee_ty args
1529 = mapSM specTy ty_args `thenSM` \ ty_args ->
1530 mapAndUnzipSM (specAlgAlt ty_args) alts `thenSM` \ (alts, alts_uds_s) ->
1531 specDeflt deflt args `thenSM` \ (deflt, deflt_uds) ->
1532 returnSM (AlgAlts alts deflt,
1533 unionUDList alts_uds_s `unionUDs` deflt_uds)
1535 -- We use ty_args of scrutinee type to identify specialisation of
1538 (_, ty_args, _) = --trace "Specialise.specAlts:getAppData..." $
1539 getAppDataTyConExpandingDicts scrutinee_ty
1541 specAlgAlt ty_args (con,binders,rhs)
1542 = specLambdaOrCaseBody binders rhs args `thenSM` \ (binders, rhs, rhs_uds) ->
1543 mkTyConInstance con ty_args `thenSM` \ con_uds ->
1544 returnSM ((con,binders,rhs), rhs_uds `unionUDs` con_uds)
1546 specAlts (PrimAlts alts deflt) scrutinee_ty args
1547 = mapAndUnzipSM specPrimAlt alts `thenSM` \ (alts, alts_uds_s) ->
1548 specDeflt deflt args `thenSM` \ (deflt, deflt_uds) ->
1549 returnSM (PrimAlts alts deflt,
1550 unionUDList alts_uds_s `unionUDs` deflt_uds)
1552 specPrimAlt (lit,rhs) = specExpr rhs args `thenSM` \ (rhs, uds) ->
1553 returnSM ((lit,rhs), uds)
1556 specDeflt NoDefault args = returnSM (NoDefault, emptyUDs)
1557 specDeflt (BindDefault binder rhs) args
1558 = specLambdaOrCaseBody [binder] rhs args `thenSM` \ ([binder], rhs, uds) ->
1559 returnSM (BindDefault binder rhs, uds)
1563 %************************************************************************
1565 \subsubsection{Specialising an atom}
1567 %************************************************************************
1570 partition_args :: [CoreArg] -> ([CoreArg], [CoreArg])
1572 = span is_ty_arg args
1574 is_ty_arg (TyArg _) = True
1579 -> (CoreArg -> SpecM (CoreExpr, UsageDetails))
1580 -> SpecM (CoreExpr, UsageDetails)
1582 = lookupId v `thenSM` \ vlookup ->
1586 -> thing_inside (VarArg vu) `thenSM` \ (expr, uds) ->
1587 returnSM (bindUnlift vl vu expr, singleFvUDs (VarArg vl) `unionUDs` uds)
1590 -> thing_inside vatom `thenSM` \ (expr, uds) ->
1591 returnSM (expr, singleFvUDs vatom `unionUDs` uds)
1594 -> (CoreArg -> SpecM (CoreExpr, UsageDetails))
1595 -> SpecM (CoreExpr, UsageDetails))
1597 specArg (TyArg ty) thing_inside
1598 = specTy ty `thenSM` \ new_ty ->
1599 thing_inside (TyArg new_ty)
1601 specArg (LitArg lit)
1602 = thing_inside (LitArg lit)
1607 specArgs [] thing_inside
1610 specArgs (arg:args) thing_inside
1611 = specArg arg $ \ arg' ->
1612 specArgs args $ \ args' ->
1613 thing_inside (arg' : args')
1617 %************************************************************************
1619 \subsubsection{Specialising bindings}
1621 %************************************************************************
1623 A classic case of when having a polymorphic recursive function would help!
1626 data BindsOrExpr = ItsABinds [CoreBinding]
1627 | ItsAnExpr CoreExpr
1632 :: Bool -- True <=> a top level group
1633 -> CoreBinding -- As yet unprocessed
1634 -> SpecM (BindsOrExpr, UsageDetails) -- Something to do the scope of the bindings
1635 -> SpecM ([CoreBinding], -- Processed
1636 BindsOrExpr, -- Combined result
1637 UsageDetails) -- Usage details of the whole lot
1639 specBindAndScope top_lev bind scopeM
1640 = cloneLetBinders top_lev (is_rec bind) binders
1641 `thenSM` \ (new_binders, clone_infos) ->
1643 -- Two cases now: either this is a bunch of local dictionaries,
1644 -- in which case we float them; or its a bunch of other values,
1645 -- in which case we see if they correspond to any call-instances
1646 -- we have from processing the scope
1648 if not top_lev && all (isDictTy . idType) binders
1650 -- Ha! A group of local dictionary bindings
1652 bindIds binders clone_infos (
1654 -- Process the dictionary bindings themselves
1655 specBind False True new_binders [] bind `thenSM` \ (bind, rhs_uds) ->
1657 -- Process their scope
1658 scopeM `thenSM` \ (thing, scope_uds) ->
1660 -- Add the bindings to the current stuff
1661 final_uds = addDictBinds new_binders bind rhs_uds scope_uds
1663 returnSM ([], thing, final_uds)
1666 -- Ho! A group of bindings
1668 fixSM (\ ~(_, _, _, rec_spec_infos) ->
1670 bindSpecIds binders clone_infos rec_spec_infos (
1671 -- It's ok to have new binders in scope in
1672 -- non-recursive decls too, cos name shadowing is gone by now
1674 -- Do the scope of the bindings
1675 scopeM `thenSM` \ (thing, scope_uds) ->
1677 (call_insts, gotci_scope_uds) = getCIs top_lev new_binders scope_uds
1679 equiv_ciss = equivClasses cmpCI_tys call_insts
1680 inst_cis = map head equiv_ciss
1683 -- Do the bindings themselves
1684 specBind top_lev False new_binders inst_cis bind
1685 `thenSM` \ (spec_bind, spec_uds) ->
1687 -- Create any necessary instances
1688 instBind top_lev new_binders bind equiv_ciss inst_cis
1689 `thenSM` \ (inst_binds, inst_uds, spec_infos) ->
1692 -- NB: dumpUDs only worries about new_binders since the free var
1693 -- stuff only records free new_binders
1694 -- The spec_ids only appear in SpecInfos and final speced calls
1696 -- Build final binding group and usage details
1697 (final_binds, final_uds)
1699 -- For a top-level binding we have to dumpUDs from
1700 -- spec_uds and inst_uds and scope_uds creating
1701 -- *global* dict bindings
1703 (scope_dict_binds, final_scope_uds)
1704 = dumpUDs gotci_scope_uds True False [] new_binders []
1705 (spec_dict_binds, final_spec_uds)
1706 = dumpUDs spec_uds True False inst_cis new_binders []
1707 (inst_dict_binds, final_inst_uds)
1708 = dumpUDs inst_uds True False inst_cis new_binders []
1710 ([spec_bind] ++ inst_binds ++ scope_dict_binds
1711 ++ spec_dict_binds ++ inst_dict_binds,
1712 final_spec_uds `unionUDs` final_scope_uds `unionUDs` final_inst_uds)
1714 -- For a local binding we only have to dumpUDs from
1715 -- scope_uds since the UDs from spec_uds and inst_uds
1716 -- have already been dumped by specBind and instBind
1718 (scope_dict_binds, final_scope_uds)
1719 = dumpUDs gotci_scope_uds False False [] new_binders []
1721 ([spec_bind] ++ inst_binds ++ scope_dict_binds,
1722 spec_uds `unionUDs` final_scope_uds `unionUDs` inst_uds)
1724 -- inst_uds comes last, because there may be dict bindings
1725 -- floating outward in scope_uds which are mentioned
1726 -- in the call-instances, and hence in spec_uds.
1727 -- This ordering makes sure that the precedence order
1728 -- among the dict bindings finally floated out is maintained.
1730 returnSM (final_binds, thing, final_uds, spec_infos)
1732 ) `thenSM` \ (binds, thing, final_uds, spec_infos) ->
1733 returnSM (binds, thing, final_uds)
1735 binders = bindersOf bind
1737 is_rec (NonRec _ _) = False
1742 specBind :: Bool -> Bool -> [Id] -> [CallInstance]
1744 -> SpecM (CoreBinding, UsageDetails)
1745 -- The UsageDetails returned has already had stuff to do with this group
1746 -- of binders deleted; that's why new_binders is passed in.
1747 specBind top_lev floating new_binders inst_cis (NonRec binder rhs)
1748 = specOneBinding top_lev floating new_binders inst_cis (binder,rhs)
1749 `thenSM` \ ((binder,rhs), rhs_uds) ->
1750 returnSM (NonRec binder rhs, rhs_uds)
1752 specBind top_lev floating new_binders inst_cis (Rec pairs)
1753 = mapAndUnzipSM (specOneBinding top_lev floating new_binders inst_cis) pairs
1754 `thenSM` \ (pairs, rhs_uds_s) ->
1755 returnSM (Rec pairs, unionUDList rhs_uds_s)
1758 specOneBinding :: Bool -> Bool -> [Id] -> [CallInstance]
1760 -> SpecM ((Id,CoreExpr), UsageDetails)
1762 specOneBinding top_lev floating new_binders inst_cis (binder, rhs)
1763 = lookupId binder `thenSM` \ blookup ->
1764 specExpr rhs [] `thenSM` \ (rhs, rhs_uds) ->
1766 specid_maybe_maybe = isSpecPragmaId_maybe binder
1767 is_specid = maybeToBool specid_maybe_maybe
1768 Just specinfo_maybe = specid_maybe_maybe
1769 specid_with_info = maybeToBool specinfo_maybe
1770 Just spec_info = specinfo_maybe
1772 -- If we have a SpecInfo stored in a SpecPragmaId binder
1773 -- it will contain a SpecInfo with an explicit SpecId
1774 -- We add the explicit ci to the usage details
1775 -- Any ordinary cis for orig_id (there should only be one)
1776 -- will be ignored later
1779 = if is_specid && specid_with_info then
1781 (SpecInfo spec_tys _ spec_id) = spec_info
1782 Just (orig_id, _) = isSpecId_maybe spec_id
1784 ASSERT(toplevelishId orig_id) -- must not be cloned!
1785 explicitCI orig_id spec_tys spec_info
1789 -- For a local binding we dump the usage details, creating
1790 -- any local dict bindings required
1791 -- At the top-level the uds will be dumped in specBindAndScope
1792 -- and the dict bindings made *global*
1794 (local_dict_binds, final_uds)
1795 = if not top_lev then
1796 dumpUDs rhs_uds False floating inst_cis new_binders []
1801 Lifted lift_binder unlift_binder
1802 -> -- We may need to record an unboxed instance of
1803 -- the _Lift data type in the usage details
1804 mkTyConInstance liftDataCon [idType unlift_binder]
1805 `thenSM` \ lift_uds ->
1806 returnSM ((lift_binder,
1807 mkCoLetsNoUnboxed local_dict_binds (liftExpr unlift_binder rhs)),
1808 final_uds `unionUDs` pragma_uds `unionUDs` lift_uds)
1810 NoLift (VarArg binder)
1811 -> returnSM ((binder, mkCoLetsNoUnboxed local_dict_binds rhs),
1812 final_uds `unionUDs` pragma_uds)
1816 %************************************************************************
1818 \subsection{@instBind@}
1820 %************************************************************************
1823 instBind top_lev new_ids@(first_binder:other_binders) bind equiv_ciss inst_cis
1825 = returnSM ([], emptyUDs, [])
1827 | all same_overloading other_binders
1828 = -- For each call_inst, build an instance
1829 mapAndUnzip3SM do_this_class equiv_ciss
1830 `thenSM` \ (inst_binds, inst_uds_s, spec_infos) ->
1832 -- Add in the remaining UDs
1833 returnSM (catMaybes inst_binds,
1834 unionUDList inst_uds_s,
1838 | otherwise -- Incompatible overloadings; see below by same_overloading
1839 = (if not (null (filter isUnboxedCI (concat equiv_ciss)))
1840 then pprTrace "dumpCIs: not same overloading ... WITH UNBOXED TYPES!\n"
1842 then pprTrace "dumpCIs: not same overloading ... top level \n"
1844 ) (hang (hcat [ptext SLIT("{"),
1845 interppSP PprDebug new_ids,
1847 4 (vcat [vcat (map (pprGenType PprDebug . idType) new_ids),
1848 vcat (map pprCI (concat equiv_ciss))]))
1849 (returnSM ([], emptyUDs, []))
1852 (tyvar_tmpls, class_tyvar_pairs) = getIdOverloading first_binder
1853 tyvar_tmpl_tys = mkTyVarTys tyvar_tmpls
1855 no_of_tyvars = length tyvar_tmpls
1856 no_of_dicts = length class_tyvar_pairs
1858 do_this_class equiv_cis
1859 = mkOneInst do_cis explicit_cis no_of_dicts top_lev inst_cis new_ids bind
1861 (explicit_cis, normal_cis) = partition isExplicitCI equiv_cis
1862 do_cis = head (normal_cis ++ explicit_cis)
1863 -- must choose a normal_cis in preference since dict_args will
1864 -- not be defined for an explicit_cis
1866 -- same_overloading tests whether the types of all the binders
1867 -- are "compatible"; ie have the same type and dictionary abstractions
1868 -- Almost always this is the case, because a recursive group is abstracted
1869 -- all together. But, it can happen that it ain't the case, because of
1870 -- code generated from instance decls:
1873 -- dfun.Foo.Int :: (forall a. a -> Int, Int)
1874 -- dfun.Foo.Int = (const.op1.Int, const.op2.Int)
1876 -- const.op1.Int :: forall a. a -> Int
1877 -- const.op1.Int a = defm.Foo.op1 Int a dfun.Foo.Int
1879 -- const.op2.Int :: Int
1880 -- const.op2.Int = 3
1882 -- Note that the first two defns have different polymorphism, but they are
1883 -- mutually recursive!
1885 same_overloading :: Id -> Bool
1887 = no_of_tyvars == length this_id_tyvars
1888 -- Same no of tyvars
1889 && no_of_dicts == length this_id_class_tyvar_pairs
1890 -- Same no of vdicts
1891 && and (zipWith same_ov class_tyvar_pairs this_id_class_tyvar_pairs)
1892 && length class_tyvar_pairs == length this_id_class_tyvar_pairs
1895 (this_id_tyvars, this_id_class_tyvar_pairs) = getIdOverloading id
1896 tyvar_pairs = this_id_tyvars `zip` tyvar_tmpls
1898 same_ov (clas1,tyvar1) (clas2,tyvar2)
1900 tyvar1 == assoc "same_overloading" tyvar_pairs tyvar2
1904 - a call instance eg f [t1,t2,t3] [d1,d2]
1905 - the rhs of the function eg orig_rhs
1906 - a constraint vector, saying which of eg [T,F,T]
1907 the functions type args are constrained
1910 We return a new definition
1912 $f1 = /\a -> orig_rhs t1 a t3 d1 d2
1914 The SpecInfo for f will be:
1916 SpecInfo [t1, a, t3] (\d1 d2 -> $f1 a)
1918 Based on this SpecInfo, a call instance of f
1922 should get replaced by
1924 ...(\d1 d2 -> $f1 t2)...
1926 (But that is the business of the simplifier.)
1929 mkOneInst :: CallInstance
1930 -> [CallInstance] -- Any explicit cis for this inst
1931 -> Int -- No of dicts to specialise
1932 -> Bool -- Top level binders?
1933 -> [CallInstance] -- Instantiated call insts for binders
1934 -> [Id] -- New binders
1935 -> CoreBinding -- Unprocessed
1936 -> SpecM (Maybe CoreBinding, -- Instantiated version of input
1938 [Maybe SpecInfo] -- One for each id in the original binding
1941 mkOneInst do_cis@(CallInstance _ spec_tys dict_args _ _) explicit_cis
1942 no_of_dicts_to_specialise top_lev inst_cis new_ids orig_bind
1943 = newSpecIds new_ids spec_tys no_of_dicts_to_specialise
1944 `thenSM` \ spec_ids ->
1945 newTyVars (length [() | Nothing <- spec_tys]) `thenSM` \ poly_tyvars ->
1947 -- arg_tys is spec_tys with tyvars instead of the Nothing spec_tys
1948 -- which correspond to unspecialised args
1950 (_,arg_tys) = mapAccumL do_the_wotsit poly_tyvars spec_tys
1953 args = map TyArg arg_tys ++ dict_args
1955 (new_id:_) = new_ids
1956 (spec_id:_) = spec_ids
1958 do_bind (NonRec orig_id rhs)
1959 = do_one_rhs (spec_id, new_id, (orig_id,rhs))
1960 `thenSM` \ (maybe_spec, rhs_uds, spec_info) ->
1962 Just (spec_id, rhs) -> returnSM (Just (NonRec spec_id rhs), rhs_uds, [spec_info])
1963 Nothing -> returnSM (Nothing, rhs_uds, [spec_info])
1966 = mapAndUnzip3SM do_one_rhs (zip3 spec_ids new_ids pairs)
1967 `thenSM` \ (maybe_pairs, rhss_uds_s, spec_infos) ->
1968 returnSM (Just (Rec (catMaybes maybe_pairs)),
1969 unionUDList rhss_uds_s, spec_infos)
1971 do_one_rhs (spec_id, new_id, (orig_id, orig_rhs))
1973 -- Avoid duplicating a spec which has already been created ...
1974 -- This can arise in a Rec involving a dfun for which a
1975 -- a specialised instance has been created but specialisation
1976 -- "required" by one of the other Ids in the Rec
1977 | top_lev && maybeToBool lookup_orig_spec
1978 = (if opt_SpecialiseTrace
1979 then trace_nospec " Exists: " orig_id
1982 returnSM (Nothing, emptyUDs, Nothing)
1985 -- Check for a (single) explicit call instance for this id
1986 | not (null explicit_cis_for_this_id)
1987 = ASSERT (length explicit_cis_for_this_id == 1)
1988 (if opt_SpecialiseTrace
1989 then trace_nospec " Explicit: " explicit_id
1992 returnSM (Nothing, tickSpecInsts emptyUDs, Just explicit_spec_info)
1995 -- Apply the specialiser to (orig_rhs t1 a t3 d1 d2)
1997 = ASSERT (no_of_dicts_to_specialise == length dict_args)
1998 specExpr orig_rhs args `thenSM` \ (inst_rhs, inst_uds) ->
2000 -- For a local binding we dump the usage details, creating
2001 -- any local dict bindings required
2002 -- At the top-level the uds will be dumped in specBindAndScope
2003 -- and the dict bindings made *global*
2005 (local_dict_binds, final_uds)
2006 = if not top_lev then
2007 dumpUDs inst_uds False False inst_cis new_ids []
2011 spec_info = Just (SpecInfo spec_tys no_of_dicts_to_specialise spec_id)
2013 if isUnboxedType (idType spec_id) then
2014 ASSERT (null poly_tyvars)
2015 liftId spec_id `thenSM` \ (lift_spec_id, unlift_spec_id) ->
2016 mkTyConInstance liftDataCon [idType unlift_spec_id]
2017 `thenSM` \ lift_uds ->
2018 returnSM (Just (lift_spec_id,
2019 mkCoLetsNoUnboxed local_dict_binds (liftExpr unlift_spec_id inst_rhs)),
2020 tickSpecInsts (final_uds `unionUDs` lift_uds), spec_info)
2022 returnSM (Just (spec_id,
2023 mkCoLetsNoUnboxed local_dict_binds (mkTyLam poly_tyvars inst_rhs)),
2024 tickSpecInsts final_uds, spec_info)
2026 lookup_orig_spec = lookupSpecEnv (getIdSpecialisation orig_id) arg_tys
2028 explicit_cis_for_this_id = filter (isCIofTheseIds [new_id]) explicit_cis
2029 [CallInstance _ _ _ _ (Just explicit_spec_info)] = explicit_cis_for_this_id
2030 SpecInfo _ _ explicit_id = explicit_spec_info
2032 trace_nospec :: String -> Id -> a -> a
2033 trace_nospec str spec_id
2035 (hsep [ppr PprDebug new_id, hsep (map pp_ty arg_tys),
2036 ptext SLIT("==>"), ppr PprDebug spec_id])
2038 (if opt_SpecialiseTrace then
2039 pprTrace "Specialising:"
2040 (hang (hcat [char '{',
2041 interppSP PprDebug new_ids,
2044 hcat [ptext SLIT("types: "), hsep (map pp_ty arg_tys)],
2045 if isExplicitCI do_cis then empty else
2046 hcat [ptext SLIT("dicts: "), hsep (map pp_dict dict_args)],
2047 hcat [ptext SLIT("specs: "), ppr PprDebug spec_ids]]))
2050 do_bind orig_bind `thenSM` \ (maybe_inst_bind, inst_uds, spec_infos) ->
2052 returnSM (maybe_inst_bind, inst_uds, spec_infos)
2055 pp_dict d = ppr_arg PprDebug d
2056 pp_ty t = pprParendGenType PprDebug t
2058 do_the_wotsit (tyvar:tyvars) Nothing = (tyvars, mkTyVarTy tyvar)
2059 do_the_wotsit tyvars (Just ty) = (tyvars, ty)
2063 %************************************************************************
2065 \subsection[Misc]{Miscellaneous junk}
2067 %************************************************************************
2070 mkCallInstance :: Id
2073 -> SpecM UsageDetails
2075 mkCallInstance id new_id args
2076 | null args || -- No args at all
2077 idWantsToBeINLINEd id || -- It's going to be inlined anyway
2078 not enough_args || -- Not enough type and dict args
2079 not interesting_overloading -- Overloaded types are just tyvars
2083 = returnSM (singleCI new_id spec_tys dicts)
2086 (tyvars, theta, _) = splitSigmaTy (idType id)
2087 constrained_tyvars = tyvarsOfTypes (map snd class_tyvar_pairs)
2089 arg_res = take_type_args tyvars class_tyvar_pairs args
2090 enough_args = maybeToBool arg_res
2091 (Just (tys, dicts, rest_args)) = arg_res
2093 interesting_overloading = not (null (catMaybes spec_tys))
2094 spec_tys = zipWithEqual "spec_ty" spec_ty tyvars tys
2096 ---------------------------------------------------------------
2097 -- Should we specialise on this type argument?
2098 spec_ty tyvar ty | isTyVarTy ty = Nothing
2100 spec_ty tyvar ty | opt_SpecialiseAll
2101 || (opt_SpecialiseUnboxed
2103 && isBoxedTypeKind (tyVarKind tyvar))
2104 || (opt_SpecialiseOverloaded
2105 && tyvar `elemTyVarSet` constrained_tyvars)
2108 | otherwise = Nothing
2110 ----------------- Rather a gruesome help-function ---------------
2111 take_type_args (_:tyvars) (TyArg ty : args)
2112 = case (take_type_args tyvars args) of
2114 Just (tys, dicts, others) -> Just (ty:tys, dicts, others)
2116 take_type_args (_:tyvars) [] = Nothing
2118 take_type_args [] args
2119 = case (take_dict_args class_tyvar_pairs args) of
2121 Just (dicts, others) -> Just ([], dicts, others)
2123 take_dict_args (_:class_tyvar_pairs) (dict : args) | isValArg dict
2124 = case (take_dict_args class_tyvar_pairs args) of
2126 Just (dicts, others) -> Just (dict:dicts, others)
2128 take_dict_args (_:class_tyvar_pairs) args = Nothing
2130 take_dict_args [] args = Just ([], args)
2135 mkTyConInstance :: Id
2137 -> SpecM UsageDetails
2138 mkTyConInstance con tys
2139 = recordTyConInst con tys `thenSM` \ record_inst ->
2141 Nothing -- No TyCon instance
2142 -> -- pprTrace "NoTyConInst:"
2143 -- (hsep [ppr PprDebug tycon, ptext SLIT("at"),
2144 -- ppr PprDebug con, hsep (map (ppr PprDebug) tys)])
2145 (returnSM (singleConUDs con))
2147 Just spec_tys -- Record TyCon instance
2148 -> -- pprTrace "TyConInst:"
2149 -- (hsep [ppr PprDebug tycon, ptext SLIT("at"),
2150 -- ppr PprDebug con, hsep (map (ppr PprDebug) tys),
2152 -- hsep [pprMaybeTy PprDebug ty | ty <- spec_tys],
2154 (returnSM (singleTyConI tycon spec_tys `unionUDs` singleConUDs con))
2156 tycon = dataConTyCon con
2160 recordTyConInst :: Id
2162 -> SpecM (Maybe [Maybe Type])
2164 recordTyConInst con tys
2166 spec_tys = specialiseConstrTys tys
2168 do_tycon_spec = maybeToBool (firstJust spec_tys)
2170 spec_exists = maybeToBool (lookupSpecEnv
2171 (getIdSpecialisation con)
2174 -- pprTrace "ConSpecExists?: "
2175 -- (vcat [ptext (if spec_exists then SLIT("True") else SLIT("False")),
2176 -- ppr PprShowAll con, hsep (map (ppr PprDebug) tys)])
2177 (if (not spec_exists && do_tycon_spec)
2178 then returnSM (Just spec_tys)
2179 else returnSM Nothing)
2182 %************************************************************************
2184 \subsection[monad-Specialise]{Monad used in specialisation}
2186 %************************************************************************
2190 inherited: control flags and
2191 recordInst functions with flags cached
2193 environment mapping tyvars to types
2194 environment mapping Ids to Atoms
2196 threaded in and out: unique supply
2199 type TypeEnv = TyVarEnv Type
2207 initSM m uniqs = m nullTyVarEnv nullIdEnv uniqs
2209 returnSM :: a -> SpecM a
2210 thenSM :: SpecM a -> (a -> SpecM b) -> SpecM b
2211 fixSM :: (a -> SpecM a) -> SpecM a
2213 thenSM m k tvenv idenv us
2214 = case splitUniqSupply us of { (s1, s2) ->
2215 case (m tvenv idenv s1) of { r ->
2216 k r tvenv idenv s2 }}
2218 returnSM r tvenv idenv us = r
2220 fixSM k tvenv idenv us
2223 r = k r tvenv idenv us -- Recursive in r!
2226 The only interesting bit is figuring out the type of the SpecId!
2229 newSpecIds :: [Id] -- The id of which to make a specialised version
2230 -> [Maybe Type] -- Specialise to these types
2231 -> Int -- No of dicts to specialise
2234 newSpecIds new_ids maybe_tys dicts_to_ignore tvenv idenv us
2235 = [ mkSpecId uniq id maybe_tys (spec_id_ty id) (selectIdInfoForSpecId id)
2236 | (id,uniq) <- zipEqual "newSpecIds" new_ids uniqs ]
2238 uniqs = getUniques (length new_ids) us
2239 spec_id_ty id = specialiseTy (idType id) maybe_tys dicts_to_ignore
2241 newTyVars :: Int -> SpecM [TyVar]
2242 newTyVars n tvenv idenv us
2243 = [mkSysTyVar uniq mkBoxedTypeKind | uniq <- getUniques n us]
2246 @cloneLambdaOrCaseBinders@ and @cloneLetBinders@ take a bunch of
2247 binders, and build ``clones'' for them. The clones differ from the
2248 originals in three ways:
2250 (a) they have a fresh unique
2251 (b) they have the current type environment applied to their type
2252 (c) for Let binders which have been specialised to unboxed values
2253 the clone will have a lifted type
2255 As well as returning the list of cloned @Id@s they also return a list of
2256 @CloneInfo@s which the original binders should be bound to.
2259 cloneLambdaOrCaseBinders :: [Id] -- Old binders
2260 -> SpecM ([Id], [CloneInfo]) -- New ones
2262 cloneLambdaOrCaseBinders old_ids tvenv idenv us
2264 uniqs = getUniques (length old_ids) us
2266 unzip (zipWithEqual "cloneLambdaOrCaseBinders" clone_it old_ids uniqs)
2268 clone_it old_id uniq
2269 = (new_id, NoLift (VarArg new_id))
2271 new_id = applyTypeEnvToId tvenv (mkIdWithNewUniq old_id uniq)
2273 cloneLetBinders :: Bool -- Top level ?
2274 -> Bool -- Recursice
2275 -> [Id] -- Old binders
2276 -> SpecM ([Id], [CloneInfo]) -- New ones
2278 cloneLetBinders top_lev is_rec old_ids tvenv idenv us
2280 uniqs = getUniques (2 * length old_ids) us
2282 unzip (clone_them old_ids uniqs)
2284 clone_them [] [] = []
2286 clone_them (old_id:olds) (u1:u2:uniqs)
2289 NoLift (VarArg old_id)) : clone_rest
2291 -- Don't clone if it is a top-level thing. Why not?
2292 -- (a) we don't want to change the uniques
2294 -- (b) we don't have to be paranoid about name capture
2295 -- (c) the thing is polymorphic so no need to subst
2298 = if (is_rec && isUnboxedType new_ty && not (isUnboxedType old_ty))
2300 Lifted lifted_id unlifted_id) : clone_rest
2302 NoLift (VarArg new_id)) : clone_rest
2305 clone_rest = clone_them olds uniqs
2307 new_id = applyTypeEnvToId tvenv (mkIdWithNewUniq old_id u1)
2308 new_ty = idType new_id
2309 old_ty = idType old_id
2311 (lifted_id, unlifted_id) = mkLiftedId new_id u2
2314 cloneTyVarSM :: TyVar -> SpecM TyVar
2316 cloneTyVarSM old_tyvar tvenv idenv us
2320 cloneTyVar old_tyvar uniq -- new_tyvar
2322 bindId :: Id -> CloneInfo -> SpecM thing -> SpecM thing
2324 bindId id val specm tvenv idenv us
2325 = specm tvenv (addOneToIdEnv idenv id val) us
2327 bindIds :: [Id] -> [CloneInfo] -> SpecM thing -> SpecM thing
2329 bindIds olds news specm tvenv idenv us
2330 = specm tvenv (growIdEnvList idenv (zip olds news)) us
2332 bindSpecIds :: [Id] -- Old
2333 -> [(CloneInfo)] -- New
2334 -> [[Maybe SpecInfo]] -- Corresponding specialisations
2335 -- Each sub-list corresponds to a different type,
2336 -- and contains one Maybe spec_info for each id
2340 bindSpecIds olds clones spec_infos specm tvenv idenv us
2341 = specm tvenv (growIdEnvList idenv old_to_clone) us
2343 old_to_clone = mk_old_to_clone olds clones spec_infos
2345 -- The important thing here is that we are *lazy* in spec_infos
2346 mk_old_to_clone [] [] _ = []
2347 mk_old_to_clone (old:rest_olds) (clone:rest_clones) spec_infos
2348 = (old, add_spec_info clone) :
2349 mk_old_to_clone rest_olds rest_clones spec_infos_rest
2351 add_spec_info (NoLift (VarArg new))
2352 = NoLift (VarArg (new `addIdSpecialisation`
2353 (mkSpecEnv spec_infos_this_id)))
2354 add_spec_info lifted
2355 = lifted -- no specialised instances for unboxed lifted values
2357 spec_infos_this_id = catMaybes (map head spec_infos)
2358 spec_infos_rest = map tail spec_infos
2361 bindTyVar :: TyVar -> Type -> SpecM thing -> SpecM thing
2363 bindTyVar tyvar ty specm tvenv idenv us
2364 = specm (growTyVarEnvList tvenv [(tyvar,ty)]) idenv us
2368 lookupId :: Id -> SpecM CloneInfo
2370 lookupId id tvenv idenv us
2371 = case lookupIdEnv idenv id of
2372 Nothing -> NoLift (VarArg id)
2377 specTy :: Type -> SpecM Type -- Apply the current type envt to the type
2379 specTy ty tvenv idenv us
2380 = applyTypeEnvToTy tvenv ty
2384 liftId :: Id -> SpecM (Id, Id)
2385 liftId id tvenv idenv us
2392 In other monads these @mapSM@ things are usually called @listM@.
2393 I think @mapSM@ is a much better name. The `2' and `3' variants are
2394 when you want to return two or three results, and get at them
2395 separately. It saves you having to do an (unzip stuff) right after.
2398 mapSM :: (a -> SpecM b) -> [a] -> SpecM [b]
2399 mapAndUnzipSM :: (a -> SpecM (b1, b2)) -> [a] -> SpecM ([b1],[b2])
2400 mapAndUnzip3SM :: (a -> SpecM (b1, b2, b3)) -> [a] -> SpecM ([b1],[b2],[b3])
2401 mapAndUnzip4SM :: (a -> SpecM (b1, b2, b3, b4)) -> [a] -> SpecM ([b1],[b2],[b3],[b4])
2403 mapSM f [] = returnSM []
2404 mapSM f (x:xs) = f x `thenSM` \ r ->
2405 mapSM f xs `thenSM` \ rs ->
2408 mapAndUnzipSM f [] = returnSM ([],[])
2409 mapAndUnzipSM f (x:xs) = f x `thenSM` \ (r1, r2) ->
2410 mapAndUnzipSM f xs `thenSM` \ (rs1,rs2) ->
2411 returnSM ((r1:rs1),(r2:rs2))
2413 mapAndUnzip3SM f [] = returnSM ([],[],[])
2414 mapAndUnzip3SM f (x:xs) = f x `thenSM` \ (r1,r2,r3) ->
2415 mapAndUnzip3SM f xs `thenSM` \ (rs1,rs2,rs3) ->
2416 returnSM ((r1:rs1),(r2:rs2),(r3:rs3))
2418 mapAndUnzip4SM f [] = returnSM ([],[],[],[])
2419 mapAndUnzip4SM f (x:xs) = f x `thenSM` \ (r1,r2,r3,r4) ->
2420 mapAndUnzip4SM f xs `thenSM` \ (rs1,rs2,rs3,rs4) ->
2421 returnSM ((r1:rs1),(r2:rs2),(r3:rs3),(r4:rs4))
2427 ===================== OLD CODE, scheduled for deletion =================
2432 -> [(CoreArg, UsageDetails, CoreExpr -> CoreExpr)]
2435 mkCall new_id arg_infos = returnSM (
2437 | maybeToBool (isSuperDictSelId_maybe new_id)
2438 && any isUnboxedType ty_args
2439 -- No specialisations for super-dict selectors
2440 -- Specialise unboxed calls to SuperDictSelIds by extracting
2441 -- the super class dictionary directly form the super class
2442 -- NB: This should be dead code since all uses of this dictionary should
2443 -- have been specialised. We only do this to keep core-lint happy.
2445 Just (_, super_class) = isSuperDictSelId_maybe new_id
2446 super_dict_id = case lookupClassInstAtSimpleType super_class (head ty_args) of
2447 Nothing -> panic "Specialise:mkCall:SuperDictId"
2450 returnSM (False, Var super_dict_id)
2453 = case lookupSpecEnv (getIdSpecialisation new_id) ty_args of
2454 Nothing -> checkUnspecOK new_id ty_args (
2455 returnSM (False, unspec_call)
2458 Just spec_1_details@(spec_id_1, tys_left_1, dicts_to_toss_1)
2460 -- It may be necessary to specialsie a constant method spec_id again
2461 (spec_id, tys_left, dicts_to_toss) =
2462 case (maybeToBool (isConstMethodId_maybe spec_id_1),
2463 lookupSpecEnv (getIdSpecialisation spec_id_1) tys_left_1) of
2464 (False, _ ) -> spec_1_details
2465 (True, Nothing) -> spec_1_details
2466 (True, Just (spec_id_2, tys_left_2, dicts_to_toss_2))
2467 -> (spec_id_2, tys_left_2, dicts_to_toss_1 + dicts_to_toss_2)
2469 args_left = toss_dicts dicts_to_toss val_args
2471 checkSpecOK new_id ty_args spec_id tys_left (
2473 -- The resulting spec_id may be a top-level unboxed value
2474 -- This can arise for:
2475 -- 1) constant method values
2476 -- eq: class Num a where pi :: a
2477 -- instance Num Double# where pi = 3.141#
2478 -- 2) specilised overloaded values
2479 -- eq: i1 :: Num a => a
2480 -- i1 Int# d.Num.Int# ==> i1.Int#
2481 -- These top level defns should have been lifted.
2482 -- We must add code to unlift such a spec_id.
2484 if isUnboxedType (idType spec_id) then
2485 ASSERT (null tys_left && null args_left)
2486 if toplevelishId spec_id then
2487 liftId spec_id `thenSM` \ (lift_spec_id, unlift_spec_id) ->
2488 returnSM (True, bindUnlift lift_spec_id unlift_spec_id
2489 (Var unlift_spec_id))
2491 pprPanic "Specialise:mkCall: unboxed spec_id not top-level ...\n"
2492 (hsep [ppr PprDebug new_id,
2493 hsep (map (pprParendGenType PprDebug) ty_args),
2495 ppr PprDebug spec_id])
2498 (vals_left, _, unlifts_left) = unzip3 args_left
2499 applied_tys = mkTyApp (Var spec_id) tys_left
2500 applied_vals = mkGenApp applied_tys vals_left
2502 returnSM (True, applyBindUnlifts unlifts_left applied_vals)
2505 (tys_and_vals, _, unlifts) = unzip3 args
2506 unspec_call = applyBindUnlifts unlifts (mkGenApp (Var new_id) tys_and_vals)
2509 -- ty_args is the types at the front of the arg list
2510 -- val_args is the rest of the arg-list
2512 (ty_args, val_args) = get args
2514 get ((TyArg ty,_,_) : args) = (ty : tys, rest) where (tys,rest) = get args
2515 get args = ([], args)
2518 -- toss_dicts chucks away dict args, checking that they ain't types!
2519 toss_dicts 0 args = args
2520 toss_dicts n ((a,_,_) : args)
2521 | isValArg a = toss_dicts (n-1) args
2526 checkUnspecOK :: Id -> [Type] -> a -> a
2527 checkUnspecOK check_id tys
2528 = if isLocallyDefined check_id && any isUnboxedType tys
2529 then pprPanic "Specialise:checkUnspecOK: unboxed instance for local id not found\n"
2530 (hsep [ppr PprDebug check_id,
2531 hsep (map (pprParendGenType PprDebug) tys)])
2534 checkSpecOK :: Id -> [Type] -> Id -> [Type] -> a -> a
2535 checkSpecOK check_id tys spec_id tys_left
2536 = if any isUnboxedType tys_left
2537 then pprPanic "Specialise:checkSpecOK: unboxed type args in specialised application\n"
2538 (vcat [hsep [ppr PprDebug check_id,
2539 hsep (map (pprParendGenType PprDebug) tys)],
2540 hsep [ppr PprDebug spec_id,
2541 hsep (map (pprParendGenType PprDebug) tys_left)]])