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, 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 = wk }
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 = NoDiscardId }
203 zapSpecPragInfo info = case flavourInfo info of
204 SpecPragmaId -> info { flavourInfo = VanillaId }
210 vanillaIdInfo :: IdInfo
211 vanillaIdInfo = mkIdInfo VanillaId
213 mkIdInfo :: IdFlavour -> IdInfo
214 mkIdInfo flv = IdInfo {
216 arityInfo = UnknownArity,
218 specInfo = emptyCoreRules,
219 tyGenInfo = noTyGenInfo,
220 workerInfo = NoWorker,
221 strictnessInfo = NoStrictnessInfo,
222 unfoldingInfo = noUnfolding,
223 cafInfo = MayHaveCafRefs,
225 lbvarInfo = NoLBVarInfo,
226 inlinePragInfo = NoInlinePragInfo,
232 %************************************************************************
236 %************************************************************************
240 = VanillaId -- Locally defined, not exported
241 | ExportedId -- Locally defined, exported
242 | SpecPragmaId -- Locally defined, RHS holds specialised call
244 | ImportedId -- Imported from elsewhere
246 | DataConId DataCon -- The Id for a data constructor *worker*
247 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
248 -- [the only reasons we need to know is so that
249 -- a) we can suppress printing a definition in the interface file
250 -- b) when typechecking a pattern we can get from the
251 -- Id back to the data con]
252 | PrimOpId PrimOp -- The Id for a primitive operator
253 | RecordSelId FieldLabel -- The Id for a record selector
256 ppFlavourInfo :: IdFlavour -> SDoc
257 ppFlavourInfo VanillaId = empty
258 ppFlavourInfo ExportedId = ptext SLIT("[Exported]")
259 ppFlavourInfo SpecPragmaId = ptext SLIT("[SpecPrag]")
260 ppFlavourInfo ImportedId = ptext SLIT("[Imported]")
261 ppFlavourInfo (DataConId _) = ptext SLIT("[DataCon]")
262 ppFlavourInfo (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
263 ppFlavourInfo (PrimOpId _) = ptext SLIT("[PrimOp]")
264 ppFlavourInfo (RecordSelId _) = ptext SLIT("[RecSel]")
266 seqFlavour :: IdFlavour -> ()
267 seqFlavour f = f `seq` ()
270 The @SpecPragmaId@ exists only to make Ids that are
271 on the *LHS* of bindings created by SPECIALISE pragmas;
273 The SpecPragmaId is never itself mentioned; it
274 exists solely so that the specialiser will find
275 the call to f, and make specialised version of it.
276 The SpecPragmaId binding is discarded by the specialiser
277 when it gathers up overloaded calls.
278 Meanwhile, it is not discarded as dead code.
281 %************************************************************************
283 \subsection[arity-IdInfo]{Arity info about an @Id@}
285 %************************************************************************
287 For locally-defined Ids, the code generator maintains its own notion
288 of their arities; so it should not be asking... (but other things
289 besides the code-generator need arity info!)
293 = UnknownArity -- No idea
295 | ArityExactly Arity -- Arity is exactly this. We use this when importing a
296 -- function; it's already been compiled and we know its
299 | ArityAtLeast Arity -- A partial application of this Id to up to n-1 value arguments
300 -- does essentially no work. That is not necessarily the
301 -- same as saying that it has n leading lambdas, because coerces
302 -- may get in the way.
304 -- functions in the module being compiled. Their arity
305 -- might increase later in the compilation process, if
306 -- an extra lambda floats up to the binding site.
309 seqArity :: ArityInfo -> ()
310 seqArity a = arityLowerBound a `seq` ()
312 exactArity = ArityExactly
313 atLeastArity = ArityAtLeast
314 unknownArity = UnknownArity
316 arityLowerBound :: ArityInfo -> Arity
317 arityLowerBound UnknownArity = 0
318 arityLowerBound (ArityAtLeast n) = n
319 arityLowerBound (ArityExactly n) = n
321 hasArity :: ArityInfo -> Bool
322 hasArity UnknownArity = False
323 hasArity other = True
325 ppArityInfo UnknownArity = empty
326 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("__A"), int arity]
327 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("__AL"), int arity]
330 %************************************************************************
332 \subsection{Inline-pragma information}
334 %************************************************************************
339 | IMustNotBeINLINEd Bool -- True <=> came from an INLINE prag, False <=> came from a NOINLINE prag
340 (Maybe Int) -- Phase number from pragma, if any
342 -- The True, Nothing case doesn't need to be recorded
344 -- SEE COMMENTS WITH CoreUnfold.blackListed on the
345 -- exact significance of the IMustNotBeINLINEd pragma
347 isNeverInlinePrag :: InlinePragInfo -> Bool
348 isNeverInlinePrag (IMustNotBeINLINEd _ Nothing) = True
349 isNeverInlinePrag other = False
351 neverInlinePrag :: InlinePragInfo
352 neverInlinePrag = IMustNotBeINLINEd True{-should be False? --SDM -} Nothing
354 instance Outputable InlinePragInfo where
355 -- This is now parsed in interface files
356 ppr NoInlinePragInfo = empty
357 ppr other_prag = ptext SLIT("__U") <> pprInlinePragInfo other_prag
359 pprInlinePragInfo NoInlinePragInfo = empty
360 pprInlinePragInfo (IMustNotBeINLINEd True Nothing) = empty
361 pprInlinePragInfo (IMustNotBeINLINEd True (Just n)) = brackets (int n)
362 pprInlinePragInfo (IMustNotBeINLINEd False Nothing) = brackets (char '!')
363 pprInlinePragInfo (IMustNotBeINLINEd False (Just n)) = brackets (char '!' <> int n)
365 instance Show InlinePragInfo where
366 showsPrec p prag = showsPrecSDoc p (ppr prag)
370 %************************************************************************
372 \subsection[TyGen-IdInfo]{Type generalisation info about an @Id@}
374 %************************************************************************
376 Certain passes (notably usage inference) may change the type of an
377 identifier, modifying all in-scope uses of that identifier
378 appropriately to maintain type safety.
380 However, some identifiers must not have their types changed in this
381 way, because their types are conjured up in the front end of the
382 compiler rather than being read from the interface file. Default
383 methods, dictionary functions, record selectors, and others are in
384 this category. (see comment at TcClassDcl.tcClassSig).
386 To indicate this property, such identifiers are marked TyGenNever.
388 Furthermore, if the usage inference generates a usage-specialised
389 variant of a function, we must NOT re-infer a fully-generalised type
390 at the next inference. This finer property is indicated by a
391 TyGenUInfo on the identifier.
395 = NoTyGenInfo -- no restriction on type generalisation
397 | TyGenUInfo [Maybe Type] -- restrict generalisation of this Id to
398 -- preserve specified usage annotations
400 | TyGenNever -- never generalise the type of this Id
405 For TyGenUInfo, the list has one entry for each usage annotation on
406 the type of the Id, in left-to-right pre-order (annotations come
407 before the type they annotate). Nothing means no restriction; Just
408 usOnce or Just usMany forces that annotation to that value. Other
409 usage annotations are illegal.
412 seqTyGenInfo :: TyGenInfo -> ()
413 seqTyGenInfo NoTyGenInfo = ()
414 seqTyGenInfo (TyGenUInfo us) = seqList us ()
415 seqTyGenInfo TyGenNever = ()
417 noTyGenInfo :: TyGenInfo
418 noTyGenInfo = NoTyGenInfo
420 isNoTyGenInfo :: TyGenInfo -> Bool
421 isNoTyGenInfo NoTyGenInfo = True
422 isNoTyGenInfo _ = False
424 -- NB: There's probably no need to write this information out to the interface file.
425 -- Why? Simply because imported identifiers never get their types re-inferred.
426 -- But it's definitely nice to see in dumps, it for debugging purposes.
428 ppTyGenInfo :: TyGenInfo -> SDoc
429 ppTyGenInfo NoTyGenInfo = empty
430 ppTyGenInfo (TyGenUInfo us) = ptext SLIT("__G") <+> text (tyGenInfoString us)
431 ppTyGenInfo TyGenNever = ptext SLIT("__G N")
433 tyGenInfoString us = map go us
434 where go Nothing = 'x' -- for legibility, choose
435 go (Just u) | u == usOnce = '1' -- chars with identity
436 | u == usMany = 'M' -- Z-encoding.
437 go other = pprPanic "IdInfo.tyGenInfoString: unexpected annotation" (ppr other)
439 instance Outputable TyGenInfo where
442 instance Show TyGenInfo where
443 showsPrec p c = showsPrecSDoc p (ppr c)
447 %************************************************************************
449 \subsection[worker-IdInfo]{Worker info about an @Id@}
451 %************************************************************************
453 If this Id has a worker then we store a reference to it. Worker
454 functions are generated by the worker/wrapper pass. This uses
455 information from the strictness and CPR analyses.
457 There might not be a worker, even for a strict function, because:
458 (a) the function might be small enough to inline, so no need
460 (b) the strictness info might be "SSS" or something, so no w/w split.
464 data WorkerInfo = NoWorker
466 -- The Arity is the arity of the *wrapper* at the moment of the
467 -- w/w split. See comments in MkIface.ifaceId, with the 'Worker' code.
469 seqWorker :: WorkerInfo -> ()
470 seqWorker (HasWorker id _) = id `seq` ()
471 seqWorker NoWorker = ()
473 ppWorkerInfo NoWorker = empty
474 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("__P") <+> ppr wk_id
476 noWorkerInfo = NoWorker
478 workerExists :: WorkerInfo -> Bool
479 workerExists NoWorker = False
480 workerExists (HasWorker _ _) = True
482 workerId :: WorkerInfo -> Id
483 workerId (HasWorker id _) = id
485 wrapperArity :: WorkerInfo -> Arity
486 wrapperArity (HasWorker _ a) = a
490 %************************************************************************
492 \subsection[CAF-IdInfo]{CAF-related information}
494 %************************************************************************
496 This information is used to build Static Reference Tables (see
497 simplStg/ComputeSRT.lhs).
501 = MayHaveCafRefs -- either:
502 -- (1) A function or static constructor
503 -- that refers to one or more CAFs,
504 -- (2) A real live CAF
506 | NoCafRefs -- A function or static constructor
507 -- that refers to no CAFs.
509 -- LATER: not sure how easy this is...
513 seqCaf c = c `seq` ()
515 ppCafInfo NoCafRefs = ptext SLIT("__C")
516 ppCafInfo MayHaveCafRefs = empty
520 %************************************************************************
522 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
524 %************************************************************************
526 If the @Id@ is a function then it may have CPR info. A CPR analysis
527 phase detects whether:
531 The function's return value has a product type, i.e. an algebraic type
532 with a single constructor. Examples of such types are tuples and boxed
535 The function always 'constructs' the value that it is returning. It
536 must do this on every path through, and it's OK if it calls another
537 function which constructs the result.
540 If this is the case then we store a template which tells us the
541 function has the CPR property and which components of the result are
547 | ReturnsCPR -- Yes, this function returns a constructed product
548 -- Implicitly, this means "after the function has been applied
549 -- to all its arguments", so the worker/wrapper builder in
550 -- WwLib.mkWWcpr checks that that it is indeed saturated before
551 -- making use of the CPR info
553 -- We used to keep nested info about sub-components, but
554 -- we never used it so I threw it away
558 seqCpr :: CprInfo -> ()
559 seqCpr ReturnsCPR = ()
560 seqCpr NoCPRInfo = ()
562 noCprInfo = NoCPRInfo
564 ppCprInfo NoCPRInfo = empty
565 ppCprInfo ReturnsCPR = ptext SLIT("__M")
567 instance Outputable CprInfo where
570 instance Show CprInfo where
571 showsPrec p c = showsPrecSDoc p (ppr c)
575 %************************************************************************
577 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
579 %************************************************************************
581 If the @Id@ is a lambda-bound variable then it may have lambda-bound
582 var info. The usage analysis (UsageSP) detects whether the lambda
583 binding this var is a ``one-shot'' lambda; that is, whether it is
584 applied at most once.
586 This information may be useful in optimisation, as computations may
587 safely be floated inside such a lambda without risk of duplicating
594 | LBVarInfo Type -- The lambda that binds this Id has this usage
595 -- annotation (i.e., if ==usOnce, then the
596 -- lambda is applied at most once).
597 -- The annotation's kind must be `$'
598 -- HACK ALERT! placing this info here is a short-term hack,
599 -- but it minimises changes to the rest of the compiler.
600 -- Hack agreed by SLPJ/KSW 1999-04.
602 seqLBVar l = l `seq` ()
606 noLBVarInfo = NoLBVarInfo
608 -- not safe to print or parse LBVarInfo because it is not really a
609 -- property of the definition, but a property of the context.
610 pprLBVarInfo NoLBVarInfo = empty
611 pprLBVarInfo (LBVarInfo u) | u == usOnce
612 = getPprStyle $ \ sty ->
615 else ptext SLIT("OneShot")
619 instance Outputable LBVarInfo where
622 instance Show LBVarInfo where
623 showsPrec p c = showsPrecSDoc p (ppr c)
627 %************************************************************************
629 \subsection{Bulk operations on IdInfo}
631 %************************************************************************
633 zapFragileInfo is used when cloning binders, mainly in the
634 simplifier. We must forget about used-once information because that
635 isn't necessarily correct in the transformed program.
636 Also forget specialisations and unfoldings because they would need
637 substitution to be correct. (They get pinned back on separately.)
640 zapFragileInfo :: IdInfo -> Maybe IdInfo
641 zapFragileInfo info@(IdInfo {occInfo = occ,
644 unfoldingInfo = unfolding})
645 | not (isFragileOcc occ)
646 -- We must forget about whether it was marked safe-to-inline,
647 -- because that isn't necessarily true in the simplified expression.
648 -- This is important because expressions may be re-simplified
649 -- We don't zap deadness or loop-breaker-ness.
650 -- The latter is important because it tells MkIface not to
651 -- spit out an inlining for the thing. The former doesn't
652 -- seem so important, but there's no harm.
654 && isEmptyCoreRules rules
655 -- Specialisations would need substituting. They get pinned
656 -- back on separately.
658 && not (workerExists wrkr)
660 && not (hasUnfolding unfolding)
661 -- This is very important; occasionally a let-bound binder is used
662 -- as a binder in some lambda, in which case its unfolding is utterly
663 -- bogus. Also the unfolding uses old binders so if we left it we'd
664 -- have to substitute it. Much better simply to give the Id a new
665 -- unfolding each time, which is what the simplifier does.
669 = Just (info {occInfo = robust_occ_info,
670 workerInfo = noWorkerInfo,
671 specInfo = emptyCoreRules,
672 unfoldingInfo = noUnfolding})
674 -- It's important to keep the loop-breaker info,
675 -- because the substitution doesn't remember it.
676 robust_occ_info = case occ of
677 OneOcc _ _ -> NoOccInfo
681 @zapLamInfo@ is used for lambda binders that turn out to to be
682 part of an unsaturated lambda
685 zapLamInfo :: IdInfo -> Maybe IdInfo
686 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
687 | is_safe_occ && not (isStrict demand)
690 = Just (info {occInfo = safe_occ,
691 demandInfo = wwLazy})
693 -- The "unsafe" occ info is the ones that say I'm not in a lambda
694 -- because that might not be true for an unsaturated lambda
695 is_safe_occ = case occ of
696 OneOcc in_lam once -> in_lam
699 safe_occ = case occ of
700 OneOcc _ once -> OneOcc insideLam once
705 copyIdInfo is used when shorting out a top-level binding
708 where f is exported. We are going to swizzle it around to
712 BUT (a) we must be careful about messing up rules
713 (b) we must ensure f's IdInfo ends up right
715 (a) Messing up the rules
717 The example that went bad on me was this one:
719 iterate :: (a -> a) -> a -> [a]
720 iterate = iterateList
722 iterateFB c f x = x `c` iterateFB c f (f x)
723 iterateList f x = x : iterateList f (f x)
726 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
727 "iterateFB" iterateFB (:) = iterateList
730 This got shorted out to:
732 iterateList :: (a -> a) -> a -> [a]
733 iterateList = iterate
735 iterateFB c f x = x `c` iterateFB c f (f x)
736 iterate f x = x : iterate f (f x)
739 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
740 "iterateFB" iterateFB (:) = iterate
743 And now we get an infinite loop in the rule system
744 iterate f x -> build (\cn -> iterateFB c f x
748 Tiresome solution: don't do shorting out if f has rewrite rules.
749 Hence shortableIdInfo.
751 (b) Keeping the IdInfo right
752 ~~~~~~~~~~~~~~~~~~~~~~~~
753 We want to move strictness/worker info from f_local to f, but keep the rest.
757 shortableIdInfo :: IdInfo -> Bool
758 shortableIdInfo info = isEmptyCoreRules (specInfo info)
760 copyIdInfo :: IdInfo -- f_local
761 -> IdInfo -- f (the exported one)
762 -> IdInfo -- New info for f
763 copyIdInfo f_local f = f { strictnessInfo = strictnessInfo f_local,
764 workerInfo = workerInfo f_local,
765 cprInfo = cprInfo f_local