2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
4 \section[IdInfo]{@IdInfos@: Non-essential information about @Ids@}
6 (And a pretty good illustration of quite a few things wrong with
11 GlobalIdDetails(..), notGlobalId, -- Not abstract
14 vanillaIdInfo, noCafNoTyGenIdInfo,
15 seqIdInfo, megaSeqIdInfo,
18 zapLamInfo, zapDemandInfo,
19 shortableIdInfo, copyIdInfo,
23 exactArity, atLeastArity, unknownArity, hasArity,
24 arityInfo, setArityInfo, ppArityInfo, arityLowerBound,
26 -- Strictness; imported from Demand
28 mkStrictnessInfo, noStrictnessInfo,
29 ppStrictnessInfo,isBottomingStrictness,
30 strictnessInfo, setStrictnessInfo,
32 -- Usage generalisation
34 tyGenInfo, setTyGenInfo,
35 noTyGenInfo, isNoTyGenInfo, ppTyGenInfo, tyGenInfoString,
38 WorkerInfo(..), workerExists, wrapperArity, workerId,
39 workerInfo, setWorkerInfo, ppWorkerInfo,
42 unfoldingInfo, setUnfoldingInfo,
45 demandInfo, setDemandInfo,
49 inlinePragInfo, setInlinePragInfo, pprInlinePragInfo,
50 isNeverInlinePrag, neverInlinePrag,
53 OccInfo(..), isFragileOcc, isDeadOcc, isLoopBreaker,
54 InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
58 specInfo, setSpecInfo,
61 CgInfo(..), cgInfo, setCgInfo, cgMayHaveCafRefs, pprCgInfo,
62 cgArity, cgCafInfo, vanillaCgInfo,
63 CgInfoEnv, lookupCgInfo,
67 CafInfo(..), ppCafInfo, setCafInfo, mayHaveCafRefs,
69 -- Constructed Product Result Info
70 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
72 -- Lambda-bound variable info
73 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo, hasNoLBVarInfo
76 #include "HsVersions.h"
80 import Type ( Type, usOnce )
81 import PrimOp ( PrimOp )
82 import NameEnv ( NameEnv, lookupNameEnv )
85 import BasicTypes ( OccInfo(..), isFragileOcc, isDeadOcc, seqOccInfo, isLoopBreaker,
86 InsideLam, insideLam, notInsideLam,
87 OneBranch, oneBranch, notOneBranch,
90 import DataCon ( DataCon )
91 import FieldLabel ( FieldLabel )
92 import Type ( usOnce, usMany )
93 import Demand -- Lots of stuff
95 import Util ( seqList )
97 infixl 1 `setDemandInfo`,
111 -- infixl so you can say (id `set` a `set` b)
114 %************************************************************************
116 \subsection{GlobalIdDetails
118 %************************************************************************
120 This type is here (rather than in Id.lhs) mainly because there's
121 an IdInfo.hi-boot, but no Id.hi-boot, and GlobalIdDetails is imported
122 (recursively) by Var.lhs.
126 = VanillaGlobal -- Imported from elsewhere, a default method Id.
128 | RecordSelId FieldLabel -- The Id for a record selector
129 | DataConId DataCon -- The Id for a data constructor *worker*
130 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
131 -- [the only reasons we need to know is so that
132 -- a) we can suppress printing a definition in the interface file
133 -- b) when typechecking a pattern we can get from the
134 -- Id back to the data con]
136 | PrimOpId PrimOp -- The Id for a primitive operator
138 | NotGlobalId -- Used as a convenient extra return value from globalIdDetails
140 notGlobalId = NotGlobalId
142 instance Outputable GlobalIdDetails where
143 ppr NotGlobalId = ptext SLIT("[***NotGlobalId***]")
144 ppr VanillaGlobal = ptext SLIT("[GlobalId]")
145 ppr (DataConId _) = ptext SLIT("[DataCon]")
146 ppr (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
147 ppr (PrimOpId _) = ptext SLIT("[PrimOp]")
148 ppr (RecordSelId _) = ptext SLIT("[RecSel]")
152 %************************************************************************
154 \subsection{The main IdInfo type}
156 %************************************************************************
158 An @IdInfo@ gives {\em optional} information about an @Id@. If
159 present it never lies, but it may not be present, in which case there
160 is always a conservative assumption which can be made.
162 Two @Id@s may have different info even though they have the same
163 @Unique@ (and are hence the same @Id@); for example, one might lack
164 the properties attached to the other.
166 The @IdInfo@ gives information about the value, or definition, of the
167 @Id@. It does {\em not} contain information about the @Id@'s usage
168 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
174 arityInfo :: ArityInfo, -- Its arity
175 demandInfo :: Demand, -- Whether or not it is definitely demanded
176 specInfo :: CoreRules, -- Specialisations of this function which exist
177 tyGenInfo :: TyGenInfo, -- Restrictions on usage-generalisation of this Id
178 strictnessInfo :: StrictnessInfo, -- Strictness properties
179 workerInfo :: WorkerInfo, -- Pointer to Worker Function
180 unfoldingInfo :: Unfolding, -- Its unfolding
181 cgInfo :: CgInfo, -- Code generator info (arity, CAF info)
182 cprInfo :: CprInfo, -- Function always constructs a product result
183 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
184 inlinePragInfo :: InlinePragInfo, -- Inline pragma
185 occInfo :: OccInfo -- How it occurs
188 seqIdInfo :: IdInfo -> ()
189 seqIdInfo (IdInfo {}) = ()
191 megaSeqIdInfo :: IdInfo -> ()
193 = seqArity (arityInfo info) `seq`
194 seqDemand (demandInfo info) `seq`
195 seqRules (specInfo info) `seq`
196 seqTyGenInfo (tyGenInfo info) `seq`
197 seqStrictnessInfo (strictnessInfo info) `seq`
198 seqWorker (workerInfo info) `seq`
200 -- seqUnfolding (unfoldingInfo info) `seq`
201 -- Omitting this improves runtimes a little, presumably because
202 -- some unfoldings are not calculated at all
204 -- CgInfo is involved in a loop, so we have to be careful not to seq it
206 -- seqCg (cgInfo info) `seq`
207 seqCpr (cprInfo info) `seq`
208 seqLBVar (lbvarInfo info) `seq`
209 seqOccInfo (occInfo info)
215 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
216 setSpecInfo info sp = PSEQ sp (info { specInfo = sp })
217 setTyGenInfo info tg = tg `seq` info { tyGenInfo = tg }
218 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
219 setOccInfo info oc = oc `seq` info { occInfo = oc }
220 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
221 -- Try to avoid spack leaks by seq'ing
223 setUnfoldingInfo info uf
224 | isEvaldUnfolding uf && isStrict (demandInfo info)
225 -- If the unfolding is a value, the demand info may
226 -- go pear-shaped, so we nuke it. Example:
228 -- case x of (p,q) -> h p q x
229 -- Here x is certainly demanded. But after we've nuked
230 -- the case, we'll get just
231 -- let x = (a,b) in h a b x
232 -- and now x is not demanded (I'm assuming h is lazy)
233 -- This really happens. The solution here is a bit ad hoc...
234 = info { unfoldingInfo = uf, demandInfo = wwLazy }
237 -- We do *not* seq on the unfolding info, For some reason, doing so
238 -- actually increases residency significantly.
239 = info { unfoldingInfo = uf }
241 setDemandInfo info dd = info { demandInfo = dd }
242 setArityInfo info ar = info { arityInfo = ar }
243 setCgInfo info cg = info { cgInfo = cg }
244 setCprInfo info cp = info { cprInfo = cp }
245 setLBVarInfo info lb = info { lbvarInfo = lb }
250 vanillaIdInfo :: IdInfo
254 arityInfo = UnknownArity,
256 specInfo = emptyCoreRules,
257 tyGenInfo = noTyGenInfo,
258 workerInfo = NoWorker,
259 strictnessInfo = NoStrictnessInfo,
260 unfoldingInfo = noUnfolding,
262 lbvarInfo = NoLBVarInfo,
263 inlinePragInfo = NoInlinePragInfo,
267 noCafNoTyGenIdInfo = vanillaIdInfo `setTyGenInfo` TyGenNever
268 `setCgInfo` (CgInfo 0 NoCafRefs)
269 -- Used for built-in type Ids in MkId.
270 -- Many built-in things have fixed types, so we shouldn't
271 -- run around generalising them
275 %************************************************************************
277 \subsection[arity-IdInfo]{Arity info about an @Id@}
279 %************************************************************************
281 For locally-defined Ids, the code generator maintains its own notion
282 of their arities; so it should not be asking... (but other things
283 besides the code-generator need arity info!)
287 = UnknownArity -- No idea
289 | ArityExactly Arity -- Arity is exactly this. We use this when importing a
290 -- function; it's already been compiled and we know its
293 | ArityAtLeast Arity -- A partial application of this Id to up to n-1 value arguments
294 -- does essentially no work. That is not necessarily the
295 -- same as saying that it has n leading lambdas, because coerces
296 -- may get in the way.
298 -- functions in the module being compiled. Their arity
299 -- might increase later in the compilation process, if
300 -- an extra lambda floats up to the binding site.
303 seqArity :: ArityInfo -> ()
304 seqArity a = arityLowerBound a `seq` ()
306 exactArity = ArityExactly
307 atLeastArity = ArityAtLeast
308 unknownArity = UnknownArity
310 arityLowerBound :: ArityInfo -> Arity
311 arityLowerBound UnknownArity = 0
312 arityLowerBound (ArityAtLeast n) = n
313 arityLowerBound (ArityExactly n) = n
315 hasArity :: ArityInfo -> Bool
316 hasArity UnknownArity = False
317 hasArity other = True
319 ppArityInfo UnknownArity = empty
320 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("ArityExactly"), int arity]
321 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("ArityAtLeast"), int arity]
324 %************************************************************************
326 \subsection{Inline-pragma information}
328 %************************************************************************
333 | IMustNotBeINLINEd Bool -- True <=> came from an INLINE prag, False <=> came from a NOINLINE prag
334 (Maybe Int) -- Phase number from pragma, if any
336 -- The True, Nothing case doesn't need to be recorded
338 -- SEE COMMENTS WITH CoreUnfold.blackListed on the
339 -- exact significance of the IMustNotBeINLINEd pragma
341 isNeverInlinePrag :: InlinePragInfo -> Bool
342 isNeverInlinePrag (IMustNotBeINLINEd _ Nothing) = True
343 isNeverInlinePrag other = False
345 neverInlinePrag :: InlinePragInfo
346 neverInlinePrag = IMustNotBeINLINEd True{-should be False? --SDM -} Nothing
348 instance Outputable InlinePragInfo where
349 -- This is now parsed in interface files
350 ppr NoInlinePragInfo = empty
351 ppr other_prag = ptext SLIT("__U") <> pprInlinePragInfo other_prag
353 pprInlinePragInfo NoInlinePragInfo = empty
354 pprInlinePragInfo (IMustNotBeINLINEd True Nothing) = empty
355 pprInlinePragInfo (IMustNotBeINLINEd True (Just n)) = brackets (int n)
356 pprInlinePragInfo (IMustNotBeINLINEd False Nothing) = brackets (char '!')
357 pprInlinePragInfo (IMustNotBeINLINEd False (Just n)) = brackets (char '!' <> int n)
359 instance Show InlinePragInfo where
360 showsPrec p prag = showsPrecSDoc p (ppr prag)
364 %************************************************************************
366 \subsection[TyGen-IdInfo]{Type generalisation info about an @Id@}
368 %************************************************************************
370 Certain passes (notably usage inference) may change the type of an
371 identifier, modifying all in-scope uses of that identifier
372 appropriately to maintain type safety.
374 However, some identifiers must not have their types changed in this
375 way, because their types are conjured up in the front end of the
376 compiler rather than being read from the interface file. Default
377 methods, dictionary functions, record selectors, and others are in
378 this category. (see comment at TcClassDcl.tcClassSig).
380 To indicate this property, such identifiers are marked TyGenNever.
382 Furthermore, if the usage inference generates a usage-specialised
383 variant of a function, we must NOT re-infer a fully-generalised type
384 at the next inference. This finer property is indicated by a
385 TyGenUInfo on the identifier.
389 = NoTyGenInfo -- no restriction on type generalisation
391 | TyGenUInfo [Maybe Type] -- restrict generalisation of this Id to
392 -- preserve specified usage annotations
394 | TyGenNever -- never generalise the type of this Id
399 For TyGenUInfo, the list has one entry for each usage annotation on
400 the type of the Id, in left-to-right pre-order (annotations come
401 before the type they annotate). Nothing means no restriction; Just
402 usOnce or Just usMany forces that annotation to that value. Other
403 usage annotations are illegal.
406 seqTyGenInfo :: TyGenInfo -> ()
407 seqTyGenInfo NoTyGenInfo = ()
408 seqTyGenInfo (TyGenUInfo us) = seqList us ()
409 seqTyGenInfo TyGenNever = ()
411 noTyGenInfo :: TyGenInfo
412 noTyGenInfo = NoTyGenInfo
414 isNoTyGenInfo :: TyGenInfo -> Bool
415 isNoTyGenInfo NoTyGenInfo = True
416 isNoTyGenInfo _ = False
418 -- NB: There's probably no need to write this information out to the interface file.
419 -- Why? Simply because imported identifiers never get their types re-inferred.
420 -- But it's definitely nice to see in dumps, it for debugging purposes.
422 ppTyGenInfo :: TyGenInfo -> SDoc
423 ppTyGenInfo NoTyGenInfo = empty
424 ppTyGenInfo (TyGenUInfo us) = ptext SLIT("__G") <+> text (tyGenInfoString us)
425 ppTyGenInfo TyGenNever = ptext SLIT("__G N")
427 tyGenInfoString us = map go us
428 where go Nothing = 'x' -- for legibility, choose
429 go (Just u) | u == usOnce = '1' -- chars with identity
430 | u == usMany = 'M' -- Z-encoding.
431 go other = pprPanic "IdInfo.tyGenInfoString: unexpected annotation" (ppr other)
433 instance Outputable TyGenInfo where
436 instance Show TyGenInfo where
437 showsPrec p c = showsPrecSDoc p (ppr c)
441 %************************************************************************
443 \subsection[worker-IdInfo]{Worker info about an @Id@}
445 %************************************************************************
447 If this Id has a worker then we store a reference to it. Worker
448 functions are generated by the worker/wrapper pass. This uses
449 information from the strictness and CPR analyses.
451 There might not be a worker, even for a strict function, because:
452 (a) the function might be small enough to inline, so no need
454 (b) the strictness info might be "SSS" or something, so no w/w split.
456 Sometimes the arity of a wrapper changes from the original arity from
457 which it was generated, so we always emit the "original" arity into
458 the interface file, as part of the worker info.
460 How can this happen? Sometimes we get
461 f = coerce t (\x y -> $wf x y)
462 at the moment of w/w split; but the eta reducer turns it into
464 which is perfectly fine except that the exposed arity so far as
465 the code generator is concerned (zero) differs from the arity
466 when we did the split (2).
468 All this arises because we use 'arity' to mean "exactly how many
469 top level lambdas are there" in interface files; but during the
470 compilation of this module it means "how many things can I apply
475 data WorkerInfo = NoWorker
477 -- The Arity is the arity of the *wrapper* at the moment of the
478 -- w/w split. See comments in MkIface.ifaceId, with the 'Worker' code.
480 seqWorker :: WorkerInfo -> ()
481 seqWorker (HasWorker id _) = id `seq` ()
482 seqWorker NoWorker = ()
484 ppWorkerInfo NoWorker = empty
485 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("__P") <+> ppr wk_id
487 workerExists :: WorkerInfo -> Bool
488 workerExists NoWorker = False
489 workerExists (HasWorker _ _) = True
491 workerId :: WorkerInfo -> Id
492 workerId (HasWorker id _) = id
494 wrapperArity :: WorkerInfo -> Arity
495 wrapperArity (HasWorker _ a) = a
499 %************************************************************************
501 \subsection[CG-IdInfo]{Code generator-related information}
503 %************************************************************************
505 CgInfo encapsulates calling-convention information produced by the code
506 generator. It is pasted into the IdInfo of each emitted Id by CoreTidy,
507 but only as a thunk --- the information is only actually produced further
508 downstream, by the code generator.
512 !Arity -- Exact arity for calling purposes
515 cgArity (CgInfo arity _) = arity
516 cgCafInfo (CgInfo _ caf_info) = caf_info
518 setCafInfo info caf_info =
519 case cgInfo info of { CgInfo arity _ ->
520 info `setCgInfo` CgInfo arity caf_info }
522 setCgArity info arity =
523 case cgInfo info of { CgInfo _ caf_info ->
524 info `setCgInfo` CgInfo arity caf_info }
526 -- Used for local Ids, which shouldn't need any CgInfo
527 noCgInfo = panic "noCgInfo!"
529 cgMayHaveCafRefs (CgInfo _ caf_info) = mayHaveCafRefs caf_info
531 seqCg c = c `seq` () -- fields are strict anyhow
533 vanillaCgInfo = CgInfo 0 MayHaveCafRefs -- Definitely safe
535 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.lhs).
538 = MayHaveCafRefs -- either:
539 -- (1) A function or static constructor
540 -- that refers to one or more CAFs,
541 -- (2) A real live CAF
543 | NoCafRefs -- A function or static constructor
544 -- that refers to no CAFs.
546 mayHaveCafRefs MayHaveCafRefs = True
547 mayHaveCafRefs _ = False
549 seqCaf c = c `seq` ()
551 pprCgInfo (CgInfo arity caf_info) = ppArity arity <+> ppCafInfo caf_info
554 ppArity n = hsep [ptext SLIT("__A"), int n]
556 ppCafInfo NoCafRefs = ptext SLIT("__C")
557 ppCafInfo MayHaveCafRefs = empty
561 type CgInfoEnv = NameEnv CgInfo
563 lookupCgInfo :: NameEnv CgInfo -> Name -> CgInfo
564 lookupCgInfo env n = case lookupNameEnv env n of
566 Nothing -> pprTrace "Urk! Not in CgInfo env" (ppr n) vanillaCgInfo
570 %************************************************************************
572 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
574 %************************************************************************
576 If the @Id@ is a function then it may have CPR info. A CPR analysis
577 phase detects whether:
581 The function's return value has a product type, i.e. an algebraic type
582 with a single constructor. Examples of such types are tuples and boxed
585 The function always 'constructs' the value that it is returning. It
586 must do this on every path through, and it's OK if it calls another
587 function which constructs the result.
590 If this is the case then we store a template which tells us the
591 function has the CPR property and which components of the result are
597 | ReturnsCPR -- Yes, this function returns a constructed product
598 -- Implicitly, this means "after the function has been applied
599 -- to all its arguments", so the worker/wrapper builder in
600 -- WwLib.mkWWcpr checks that that it is indeed saturated before
601 -- making use of the CPR info
603 -- We used to keep nested info about sub-components, but
604 -- we never used it so I threw it away
608 seqCpr :: CprInfo -> ()
609 seqCpr ReturnsCPR = ()
610 seqCpr NoCPRInfo = ()
612 noCprInfo = NoCPRInfo
614 ppCprInfo NoCPRInfo = empty
615 ppCprInfo ReturnsCPR = ptext SLIT("__M")
617 instance Outputable CprInfo where
620 instance Show CprInfo where
621 showsPrec p c = showsPrecSDoc p (ppr c)
625 %************************************************************************
627 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
629 %************************************************************************
631 If the @Id@ is a lambda-bound variable then it may have lambda-bound
632 var info. The usage analysis (UsageSP) detects whether the lambda
633 binding this var is a ``one-shot'' lambda; that is, whether it is
634 applied at most once.
636 This information may be useful in optimisation, as computations may
637 safely be floated inside such a lambda without risk of duplicating
644 | LBVarInfo Type -- The lambda that binds this Id has this usage
645 -- annotation (i.e., if ==usOnce, then the
646 -- lambda is applied at most once).
647 -- The annotation's kind must be `$'
648 -- HACK ALERT! placing this info here is a short-term hack,
649 -- but it minimises changes to the rest of the compiler.
650 -- Hack agreed by SLPJ/KSW 1999-04.
652 seqLBVar l = l `seq` ()
656 hasNoLBVarInfo NoLBVarInfo = True
657 hasNoLBVarInfo other = False
659 noLBVarInfo = NoLBVarInfo
661 -- not safe to print or parse LBVarInfo because it is not really a
662 -- property of the definition, but a property of the context.
663 pprLBVarInfo NoLBVarInfo = empty
664 pprLBVarInfo (LBVarInfo u) | u == usOnce
665 = getPprStyle $ \ sty ->
668 else ptext SLIT("OneShot")
672 instance Outputable LBVarInfo where
675 instance Show LBVarInfo where
676 showsPrec p c = showsPrecSDoc p (ppr c)
680 %************************************************************************
682 \subsection{Bulk operations on IdInfo}
684 %************************************************************************
686 @zapLamInfo@ is used for lambda binders that turn out to to be
687 part of an unsaturated lambda
690 zapLamInfo :: IdInfo -> Maybe IdInfo
691 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
692 | is_safe_occ && not (isStrict demand)
695 = Just (info {occInfo = safe_occ,
696 demandInfo = wwLazy})
698 -- The "unsafe" occ info is the ones that say I'm not in a lambda
699 -- because that might not be true for an unsaturated lambda
700 is_safe_occ = case occ of
701 OneOcc in_lam once -> in_lam
704 safe_occ = case occ of
705 OneOcc _ once -> OneOcc insideLam once
710 zapDemandInfo :: IdInfo -> Maybe IdInfo
711 zapDemandInfo info@(IdInfo {demandInfo = demand})
712 | not (isStrict demand) = Nothing
713 | otherwise = Just (info {demandInfo = wwLazy})
717 copyIdInfo is used when shorting out a top-level binding
720 where f is exported. We are going to swizzle it around to
724 BUT (a) we must be careful about messing up rules
725 (b) we must ensure f's IdInfo ends up right
727 (a) Messing up the rules
729 The example that went bad on me was this one:
731 iterate :: (a -> a) -> a -> [a]
732 iterate = iterateList
734 iterateFB c f x = x `c` iterateFB c f (f x)
735 iterateList f x = x : iterateList f (f x)
738 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
739 "iterateFB" iterateFB (:) = iterateList
742 This got shorted out to:
744 iterateList :: (a -> a) -> a -> [a]
745 iterateList = iterate
747 iterateFB c f x = x `c` iterateFB c f (f x)
748 iterate f x = x : iterate f (f x)
751 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
752 "iterateFB" iterateFB (:) = iterate
755 And now we get an infinite loop in the rule system
756 iterate f x -> build (\cn -> iterateFB c f x
760 Tiresome solution: don't do shorting out if f has rewrite rules.
761 Hence shortableIdInfo.
763 (b) Keeping the IdInfo right
764 ~~~~~~~~~~~~~~~~~~~~~~~~
765 We want to move strictness/worker info from f_local to f, but keep the rest.
769 shortableIdInfo :: IdInfo -> Bool
770 shortableIdInfo info = isEmptyCoreRules (specInfo info)
772 copyIdInfo :: IdInfo -- f_local
773 -> IdInfo -- f (the exported one)
774 -> IdInfo -- New info for f
775 copyIdInfo f_local f = f { strictnessInfo = strictnessInfo f_local,
776 workerInfo = workerInfo f_local,
777 cprInfo = cprInfo f_local