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
13 vanillaIdInfo, constantIdInfo, mkIdInfo, seqIdInfo, megaSeqIdInfo,
16 zapFragileInfo, zapLamInfo, zapSpecPragInfo, shortableIdInfo, copyIdInfo,
19 IdFlavour(..), flavourInfo,
20 setNoDiscardInfo, setFlavourInfo,
25 exactArity, atLeastArity, unknownArity, hasArity,
26 arityInfo, setArityInfo, ppArityInfo, arityLowerBound,
28 -- Strictness; imported from Demand
30 mkStrictnessInfo, noStrictnessInfo,
31 ppStrictnessInfo,isBottomingStrictness,
32 strictnessInfo, setStrictnessInfo,
34 -- Usage generalisation
36 tyGenInfo, setTyGenInfo,
37 noTyGenInfo, isNoTyGenInfo, ppTyGenInfo, tyGenInfoString,
40 WorkerInfo(..), workerExists, wrapperArity, workerId,
41 workerInfo, setWorkerInfo, ppWorkerInfo,
44 unfoldingInfo, setUnfoldingInfo,
47 demandInfo, setDemandInfo,
51 inlinePragInfo, setInlinePragInfo, pprInlinePragInfo,
52 isNeverInlinePrag, neverInlinePrag,
55 OccInfo(..), isFragileOcc, isDeadOcc, isLoopBreaker,
56 InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
60 specInfo, setSpecInfo,
63 CafInfo(..), cafInfo, setCafInfo, ppCafInfo,
65 -- Constructed Product Result Info
66 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
68 -- Lambda-bound variable info
69 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo
72 #include "HsVersions.h"
76 import Type ( Type, usOnce )
77 import PrimOp ( PrimOp )
79 import BasicTypes ( OccInfo(..), isFragileOcc, isDeadOcc, seqOccInfo, isLoopBreaker,
80 InsideLam, insideLam, notInsideLam,
81 OneBranch, oneBranch, notOneBranch,
84 import DataCon ( DataCon )
85 import FieldLabel ( FieldLabel )
86 import Type ( usOnce, usMany )
87 import Demand -- Lots of stuff
89 import Util ( seqList )
91 infixl 1 `setDemandInfo`,
103 -- infixl so you can say (id `set` a `set` b)
106 An @IdInfo@ gives {\em optional} information about an @Id@. If
107 present it never lies, but it may not be present, in which case there
108 is always a conservative assumption which can be made.
110 There is one exception: the 'flavour' is *not* optional.
111 You must not discard it.
112 It used to be in Var.lhs, but that seems unclean.
114 Two @Id@s may have different info even though they have the same
115 @Unique@ (and are hence the same @Id@); for example, one might lack
116 the properties attached to the other.
118 The @IdInfo@ gives information about the value, or definition, of the
119 @Id@. It does {\em not} contain information about the @Id@'s usage
120 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
126 flavourInfo :: IdFlavour, -- NOT OPTIONAL
127 arityInfo :: ArityInfo, -- Its arity
128 demandInfo :: Demand, -- Whether or not it is definitely demanded
129 specInfo :: CoreRules, -- Specialisations of this function which exist
130 tyGenInfo :: TyGenInfo, -- Restrictions on usage-generalisation of this Id
131 strictnessInfo :: StrictnessInfo, -- Strictness properties
132 workerInfo :: WorkerInfo, -- Pointer to Worker Function
133 unfoldingInfo :: Unfolding, -- Its unfolding
135 cprInfo :: CprInfo, -- Function always constructs a product result
136 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
137 inlinePragInfo :: InlinePragInfo, -- Inline pragma
138 occInfo :: OccInfo -- How it occurs
141 seqIdInfo :: IdInfo -> ()
142 seqIdInfo (IdInfo {}) = ()
144 megaSeqIdInfo :: IdInfo -> ()
146 = seqFlavour (flavourInfo info) `seq`
147 seqArity (arityInfo info) `seq`
148 seqDemand (demandInfo info) `seq`
149 seqRules (specInfo info) `seq`
150 seqTyGenInfo (tyGenInfo info) `seq`
151 seqStrictnessInfo (strictnessInfo info) `seq`
152 seqWorker (workerInfo info) `seq`
154 -- seqUnfolding (unfoldingInfo info) `seq`
155 -- Omitting this improves runtimes a little, presumably because
156 -- some unfoldings are not calculated at all
158 seqCaf (cafInfo info) `seq`
159 seqCpr (cprInfo info) `seq`
160 seqLBVar (lbvarInfo info) `seq`
161 seqOccInfo (occInfo info)
167 setFlavourInfo info fl = fl `seq` info { flavourInfo = fl }
168 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
169 setSpecInfo info sp = PSEQ sp (info { specInfo = sp })
170 setTyGenInfo info tg = tg `seq` info { tyGenInfo = tg }
171 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
172 setOccInfo info oc = oc `seq` info { occInfo = oc }
173 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
174 -- Try to avoid spack leaks by seq'ing
176 setUnfoldingInfo info uf
177 | isEvaldUnfolding uf && isStrict (demandInfo info)
178 -- If the unfolding is a value, the demand info may
179 -- go pear-shaped, so we nuke it. Example:
181 -- case x of (p,q) -> h p q x
182 -- Here x is certainly demanded. But after we've nuked
183 -- the case, we'll get just
184 -- let x = (a,b) in h a b x
185 -- and now x is not demanded (I'm assuming h is lazy)
186 -- This really happens. The solution here is a bit ad hoc...
187 = info { unfoldingInfo = uf, demandInfo = wwLazy }
190 -- We do *not* seq on the unfolding info, For some reason, doing so
191 -- actually increases residency significantly.
192 = info { unfoldingInfo = uf }
194 setDemandInfo info dd = info { demandInfo = dd }
195 setArityInfo info ar = info { arityInfo = ar }
196 setCafInfo info cf = info { cafInfo = cf }
197 setCprInfo info cp = info { cprInfo = cp }
198 setLBVarInfo info lb = info { lbvarInfo = lb }
200 setNoDiscardInfo info = case flavourInfo info of
201 VanillaId -> info { flavourInfo = ExportedId }
203 zapSpecPragInfo info = case flavourInfo info of
204 SpecPragmaId -> info { flavourInfo = VanillaId }
210 vanillaIdInfo :: IdInfo
211 vanillaIdInfo = mkIdInfo VanillaId
213 constantIdInfo :: IdInfo
214 constantIdInfo = mkIdInfo ConstantId
216 mkIdInfo :: IdFlavour -> IdInfo
217 mkIdInfo flv = IdInfo {
219 arityInfo = UnknownArity,
221 specInfo = emptyCoreRules,
222 tyGenInfo = noTyGenInfo,
223 workerInfo = NoWorker,
224 strictnessInfo = NoStrictnessInfo,
225 unfoldingInfo = noUnfolding,
226 cafInfo = MayHaveCafRefs,
228 lbvarInfo = NoLBVarInfo,
229 inlinePragInfo = NoInlinePragInfo,
235 %************************************************************************
239 %************************************************************************
243 = VanillaId -- Locally defined, not exported
244 | ExportedId -- Locally defined, exported
245 | SpecPragmaId -- Locally defined, RHS holds specialised call
247 | ConstantId -- Imported from elsewhere, or a default method Id.
249 | DictFunId -- We flag dictionary functions so that we can
250 -- conveniently extract the DictFuns from a set of
251 -- bindings when building a module's interface
253 | DataConId DataCon -- The Id for a data constructor *worker*
254 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
255 -- [the only reasons we need to know is so that
256 -- a) we can suppress printing a definition in the interface file
257 -- b) when typechecking a pattern we can get from the
258 -- Id back to the data con]
259 | PrimOpId PrimOp -- The Id for a primitive operator
260 | RecordSelId FieldLabel -- The Id for a record selector
263 ppFlavourInfo :: IdFlavour -> SDoc
264 ppFlavourInfo VanillaId = empty
265 ppFlavourInfo ExportedId = ptext SLIT("[Exported]")
266 ppFlavourInfo SpecPragmaId = ptext SLIT("[SpecPrag]")
267 ppFlavourInfo ConstantId = ptext SLIT("[Constant]")
268 ppFlavourInfo DictFunId = ptext SLIT("[DictFun]")
269 ppFlavourInfo (DataConId _) = ptext SLIT("[DataCon]")
270 ppFlavourInfo (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
271 ppFlavourInfo (PrimOpId _) = ptext SLIT("[PrimOp]")
272 ppFlavourInfo (RecordSelId _) = ptext SLIT("[RecSel]")
274 seqFlavour :: IdFlavour -> ()
275 seqFlavour f = f `seq` ()
278 The @SpecPragmaId@ exists only to make Ids that are
279 on the *LHS* of bindings created by SPECIALISE pragmas;
281 The SpecPragmaId is never itself mentioned; it
282 exists solely so that the specialiser will find
283 the call to f, and make specialised version of it.
284 The SpecPragmaId binding is discarded by the specialiser
285 when it gathers up overloaded calls.
286 Meanwhile, it is not discarded as dead code.
289 %************************************************************************
291 \subsection[arity-IdInfo]{Arity info about an @Id@}
293 %************************************************************************
295 For locally-defined Ids, the code generator maintains its own notion
296 of their arities; so it should not be asking... (but other things
297 besides the code-generator need arity info!)
301 = UnknownArity -- No idea
303 | ArityExactly Arity -- Arity is exactly this. We use this when importing a
304 -- function; it's already been compiled and we know its
307 | ArityAtLeast Arity -- A partial application of this Id to up to n-1 value arguments
308 -- does essentially no work. That is not necessarily the
309 -- same as saying that it has n leading lambdas, because coerces
310 -- may get in the way.
312 -- functions in the module being compiled. Their arity
313 -- might increase later in the compilation process, if
314 -- an extra lambda floats up to the binding site.
317 seqArity :: ArityInfo -> ()
318 seqArity a = arityLowerBound a `seq` ()
320 exactArity = ArityExactly
321 atLeastArity = ArityAtLeast
322 unknownArity = UnknownArity
324 arityLowerBound :: ArityInfo -> Arity
325 arityLowerBound UnknownArity = 0
326 arityLowerBound (ArityAtLeast n) = n
327 arityLowerBound (ArityExactly n) = n
329 hasArity :: ArityInfo -> Bool
330 hasArity UnknownArity = False
331 hasArity other = True
333 ppArityInfo UnknownArity = empty
334 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("__A"), int arity]
335 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("__AL"), int arity]
338 %************************************************************************
340 \subsection{Inline-pragma information}
342 %************************************************************************
347 | IMustNotBeINLINEd Bool -- True <=> came from an INLINE prag, False <=> came from a NOINLINE prag
348 (Maybe Int) -- Phase number from pragma, if any
350 -- The True, Nothing case doesn't need to be recorded
352 -- SEE COMMENTS WITH CoreUnfold.blackListed on the
353 -- exact significance of the IMustNotBeINLINEd pragma
355 isNeverInlinePrag :: InlinePragInfo -> Bool
356 isNeverInlinePrag (IMustNotBeINLINEd _ Nothing) = True
357 isNeverInlinePrag other = False
359 neverInlinePrag :: InlinePragInfo
360 neverInlinePrag = IMustNotBeINLINEd True{-should be False? --SDM -} Nothing
362 instance Outputable InlinePragInfo where
363 -- This is now parsed in interface files
364 ppr NoInlinePragInfo = empty
365 ppr other_prag = ptext SLIT("__U") <> pprInlinePragInfo other_prag
367 pprInlinePragInfo NoInlinePragInfo = empty
368 pprInlinePragInfo (IMustNotBeINLINEd True Nothing) = empty
369 pprInlinePragInfo (IMustNotBeINLINEd True (Just n)) = brackets (int n)
370 pprInlinePragInfo (IMustNotBeINLINEd False Nothing) = brackets (char '!')
371 pprInlinePragInfo (IMustNotBeINLINEd False (Just n)) = brackets (char '!' <> int n)
373 instance Show InlinePragInfo where
374 showsPrec p prag = showsPrecSDoc p (ppr prag)
378 %************************************************************************
380 \subsection[TyGen-IdInfo]{Type generalisation info about an @Id@}
382 %************************************************************************
384 Certain passes (notably usage inference) may change the type of an
385 identifier, modifying all in-scope uses of that identifier
386 appropriately to maintain type safety.
388 However, some identifiers must not have their types changed in this
389 way, because their types are conjured up in the front end of the
390 compiler rather than being read from the interface file. Default
391 methods, dictionary functions, record selectors, and others are in
392 this category. (see comment at TcClassDcl.tcClassSig).
394 To indicate this property, such identifiers are marked TyGenNever.
396 Furthermore, if the usage inference generates a usage-specialised
397 variant of a function, we must NOT re-infer a fully-generalised type
398 at the next inference. This finer property is indicated by a
399 TyGenUInfo on the identifier.
403 = NoTyGenInfo -- no restriction on type generalisation
405 | TyGenUInfo [Maybe Type] -- restrict generalisation of this Id to
406 -- preserve specified usage annotations
408 | TyGenNever -- never generalise the type of this Id
413 For TyGenUInfo, the list has one entry for each usage annotation on
414 the type of the Id, in left-to-right pre-order (annotations come
415 before the type they annotate). Nothing means no restriction; Just
416 usOnce or Just usMany forces that annotation to that value. Other
417 usage annotations are illegal.
420 seqTyGenInfo :: TyGenInfo -> ()
421 seqTyGenInfo NoTyGenInfo = ()
422 seqTyGenInfo (TyGenUInfo us) = seqList us ()
423 seqTyGenInfo TyGenNever = ()
425 noTyGenInfo :: TyGenInfo
426 noTyGenInfo = NoTyGenInfo
428 isNoTyGenInfo :: TyGenInfo -> Bool
429 isNoTyGenInfo NoTyGenInfo = True
430 isNoTyGenInfo _ = False
432 -- NB: There's probably no need to write this information out to the interface file.
433 -- Why? Simply because imported identifiers never get their types re-inferred.
434 -- But it's definitely nice to see in dumps, it for debugging purposes.
436 ppTyGenInfo :: TyGenInfo -> SDoc
437 ppTyGenInfo NoTyGenInfo = empty
438 ppTyGenInfo (TyGenUInfo us) = ptext SLIT("__G") <+> text (tyGenInfoString us)
439 ppTyGenInfo TyGenNever = ptext SLIT("__G N")
441 tyGenInfoString us = map go us
442 where go Nothing = 'x' -- for legibility, choose
443 go (Just u) | u == usOnce = '1' -- chars with identity
444 | u == usMany = 'M' -- Z-encoding.
445 go other = pprPanic "IdInfo.tyGenInfoString: unexpected annotation" (ppr other)
447 instance Outputable TyGenInfo where
450 instance Show TyGenInfo where
451 showsPrec p c = showsPrecSDoc p (ppr c)
455 %************************************************************************
457 \subsection[worker-IdInfo]{Worker info about an @Id@}
459 %************************************************************************
461 If this Id has a worker then we store a reference to it. Worker
462 functions are generated by the worker/wrapper pass. This uses
463 information from the strictness and CPR analyses.
465 There might not be a worker, even for a strict function, because:
466 (a) the function might be small enough to inline, so no need
468 (b) the strictness info might be "SSS" or something, so no w/w split.
472 data WorkerInfo = NoWorker
474 -- The Arity is the arity of the *wrapper* at the moment of the
475 -- w/w split. See comments in MkIface.ifaceId, with the 'Worker' code.
477 seqWorker :: WorkerInfo -> ()
478 seqWorker (HasWorker id _) = id `seq` ()
479 seqWorker NoWorker = ()
481 ppWorkerInfo NoWorker = empty
482 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("__P") <+> ppr wk_id
484 noWorkerInfo = NoWorker
486 workerExists :: WorkerInfo -> Bool
487 workerExists NoWorker = False
488 workerExists (HasWorker _ _) = True
490 workerId :: WorkerInfo -> Id
491 workerId (HasWorker id _) = id
493 wrapperArity :: WorkerInfo -> Arity
494 wrapperArity (HasWorker _ a) = a
498 %************************************************************************
500 \subsection[CAF-IdInfo]{CAF-related information}
502 %************************************************************************
504 This information is used to build Static Reference Tables (see
505 simplStg/ComputeSRT.lhs).
509 = MayHaveCafRefs -- either:
510 -- (1) A function or static constructor
511 -- that refers to one or more CAFs,
512 -- (2) A real live CAF
514 | NoCafRefs -- A function or static constructor
515 -- that refers to no CAFs.
517 -- LATER: not sure how easy this is...
521 seqCaf c = c `seq` ()
523 ppCafInfo NoCafRefs = ptext SLIT("__C")
524 ppCafInfo MayHaveCafRefs = empty
528 %************************************************************************
530 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
532 %************************************************************************
534 If the @Id@ is a function then it may have CPR info. A CPR analysis
535 phase detects whether:
539 The function's return value has a product type, i.e. an algebraic type
540 with a single constructor. Examples of such types are tuples and boxed
543 The function always 'constructs' the value that it is returning. It
544 must do this on every path through, and it's OK if it calls another
545 function which constructs the result.
548 If this is the case then we store a template which tells us the
549 function has the CPR property and which components of the result are
555 | ReturnsCPR -- Yes, this function returns a constructed product
556 -- Implicitly, this means "after the function has been applied
557 -- to all its arguments", so the worker/wrapper builder in
558 -- WwLib.mkWWcpr checks that that it is indeed saturated before
559 -- making use of the CPR info
561 -- We used to keep nested info about sub-components, but
562 -- we never used it so I threw it away
566 seqCpr :: CprInfo -> ()
567 seqCpr ReturnsCPR = ()
568 seqCpr NoCPRInfo = ()
570 noCprInfo = NoCPRInfo
572 ppCprInfo NoCPRInfo = empty
573 ppCprInfo ReturnsCPR = ptext SLIT("__M")
575 instance Outputable CprInfo where
578 instance Show CprInfo where
579 showsPrec p c = showsPrecSDoc p (ppr c)
583 %************************************************************************
585 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
587 %************************************************************************
589 If the @Id@ is a lambda-bound variable then it may have lambda-bound
590 var info. The usage analysis (UsageSP) detects whether the lambda
591 binding this var is a ``one-shot'' lambda; that is, whether it is
592 applied at most once.
594 This information may be useful in optimisation, as computations may
595 safely be floated inside such a lambda without risk of duplicating
602 | LBVarInfo Type -- The lambda that binds this Id has this usage
603 -- annotation (i.e., if ==usOnce, then the
604 -- lambda is applied at most once).
605 -- The annotation's kind must be `$'
606 -- HACK ALERT! placing this info here is a short-term hack,
607 -- but it minimises changes to the rest of the compiler.
608 -- Hack agreed by SLPJ/KSW 1999-04.
610 seqLBVar l = l `seq` ()
614 noLBVarInfo = NoLBVarInfo
616 -- not safe to print or parse LBVarInfo because it is not really a
617 -- property of the definition, but a property of the context.
618 pprLBVarInfo NoLBVarInfo = empty
619 pprLBVarInfo (LBVarInfo u) | u == usOnce
620 = getPprStyle $ \ sty ->
623 else ptext SLIT("OneShot")
627 instance Outputable LBVarInfo where
630 instance Show LBVarInfo where
631 showsPrec p c = showsPrecSDoc p (ppr c)
635 %************************************************************************
637 \subsection{Bulk operations on IdInfo}
639 %************************************************************************
641 zapFragileInfo is used when cloning binders, mainly in the
642 simplifier. We must forget about used-once information because that
643 isn't necessarily correct in the transformed program.
644 Also forget specialisations and unfoldings because they would need
645 substitution to be correct. (They get pinned back on separately.)
648 zapFragileInfo :: IdInfo -> Maybe IdInfo
649 zapFragileInfo info@(IdInfo {occInfo = occ,
652 unfoldingInfo = unfolding})
653 | not (isFragileOcc occ)
654 -- We must forget about whether it was marked safe-to-inline,
655 -- because that isn't necessarily true in the simplified expression.
656 -- This is important because expressions may be re-simplified
657 -- We don't zap deadness or loop-breaker-ness.
658 -- The latter is important because it tells MkIface not to
659 -- spit out an inlining for the thing. The former doesn't
660 -- seem so important, but there's no harm.
662 && isEmptyCoreRules rules
663 -- Specialisations would need substituting. They get pinned
664 -- back on separately.
666 && not (workerExists wrkr)
668 && not (hasUnfolding unfolding)
669 -- This is very important; occasionally a let-bound binder is used
670 -- as a binder in some lambda, in which case its unfolding is utterly
671 -- bogus. Also the unfolding uses old binders so if we left it we'd
672 -- have to substitute it. Much better simply to give the Id a new
673 -- unfolding each time, which is what the simplifier does.
677 = Just (info {occInfo = robust_occ_info,
678 workerInfo = noWorkerInfo,
679 specInfo = emptyCoreRules,
680 unfoldingInfo = noUnfolding})
682 -- It's important to keep the loop-breaker info,
683 -- because the substitution doesn't remember it.
684 robust_occ_info = case occ of
685 OneOcc _ _ -> NoOccInfo
689 @zapLamInfo@ is used for lambda binders that turn out to to be
690 part of an unsaturated lambda
693 zapLamInfo :: IdInfo -> Maybe IdInfo
694 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
695 | is_safe_occ && not (isStrict demand)
698 = Just (info {occInfo = safe_occ,
699 demandInfo = wwLazy})
701 -- The "unsafe" occ info is the ones that say I'm not in a lambda
702 -- because that might not be true for an unsaturated lambda
703 is_safe_occ = case occ of
704 OneOcc in_lam once -> in_lam
707 safe_occ = case occ of
708 OneOcc _ once -> OneOcc insideLam once
713 copyIdInfo is used when shorting out a top-level binding
716 where f is exported. We are going to swizzle it around to
720 BUT (a) we must be careful about messing up rules
721 (b) we must ensure f's IdInfo ends up right
723 (a) Messing up the rules
725 The example that went bad on me was this one:
727 iterate :: (a -> a) -> a -> [a]
728 iterate = iterateList
730 iterateFB c f x = x `c` iterateFB c f (f x)
731 iterateList f x = x : iterateList f (f x)
734 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
735 "iterateFB" iterateFB (:) = iterateList
738 This got shorted out to:
740 iterateList :: (a -> a) -> a -> [a]
741 iterateList = iterate
743 iterateFB c f x = x `c` iterateFB c f (f x)
744 iterate f x = x : iterate f (f x)
747 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
748 "iterateFB" iterateFB (:) = iterate
751 And now we get an infinite loop in the rule system
752 iterate f x -> build (\cn -> iterateFB c f x
756 Tiresome solution: don't do shorting out if f has rewrite rules.
757 Hence shortableIdInfo.
759 (b) Keeping the IdInfo right
760 ~~~~~~~~~~~~~~~~~~~~~~~~
761 We want to move strictness/worker info from f_local to f, but keep the rest.
765 shortableIdInfo :: IdInfo -> Bool
766 shortableIdInfo info = isEmptyCoreRules (specInfo info)
768 copyIdInfo :: IdInfo -- f_local
769 -> IdInfo -- f (the exported one)
770 -> IdInfo -- New info for f
771 copyIdInfo f_local f = f { strictnessInfo = strictnessInfo f_local,
772 workerInfo = workerInfo f_local,
773 cprInfo = cprInfo f_local