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 IdFlavour(..), flavourInfo,
17 setNoDiscardInfo, zapSpecPragInfo, copyIdInfo,
22 exactArity, atLeastArity, unknownArity, hasArity,
23 arityInfo, setArityInfo, ppArityInfo, arityLowerBound,
26 StrictnessInfo(..), -- Non-abstract
28 noStrictnessInfo, strictnessInfo,
29 ppStrictnessInfo, setStrictnessInfo,
30 isBottomingStrictness, appIsBottom,
33 WorkerInfo, workerExists,
34 workerInfo, setWorkerInfo, ppWorkerInfo,
37 unfoldingInfo, setUnfoldingInfo,
40 demandInfo, setDemandInfo,
43 InlinePragInfo(..), OccInfo(..),
44 inlinePragInfo, setInlinePragInfo, notInsideLambda,
47 specInfo, setSpecInfo,
50 UpdateInfo, UpdateSpec,
51 mkUpdateInfo, updateInfo, updateInfoMaybe, ppUpdateInfo, setUpdateInfo,
54 CafInfo(..), cafInfo, setCafInfo, ppCafInfo,
56 -- Constructed Product Result Info
57 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
60 zapLamIdInfo, zapFragileIdInfo, zapIdInfoForStg,
62 -- Lambda-bound variable info
63 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo
66 #include "HsVersions.h"
69 import {-# SOURCE #-} CoreUnfold ( Unfolding, noUnfolding, hasUnfolding, seqUnfolding )
70 import {-# SOURCE #-} CoreSyn ( CoreExpr, CoreRules, emptyCoreRules, isEmptyCoreRules, seqRules )
71 import {-# SOURCE #-} Const ( Con )
74 import FieldLabel ( FieldLabel )
75 import Demand ( Demand, isStrict, isLazy, wwLazy, pprDemands, seqDemand, seqDemands )
76 import Type ( UsageAnn )
78 import Maybe ( isJust )
80 infixl 1 `setUpdateInfo`,
90 -- infixl so you can say (id `set` a `set` b)
93 An @IdInfo@ gives {\em optional} information about an @Id@. If
94 present it never lies, but it may not be present, in which case there
95 is always a conservative assumption which can be made.
97 There is one exception: the 'flavour' is *not* optional.
98 You must not discard it.
99 It used to be in Var.lhs, but that seems unclean.
101 Two @Id@s may have different info even though they have the same
102 @Unique@ (and are hence the same @Id@); for example, one might lack
103 the properties attached to the other.
105 The @IdInfo@ gives information about the value, or definition, of the
106 @Id@. It does {\em not} contain information about the @Id@'s usage
107 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
113 flavourInfo :: IdFlavour, -- NOT OPTIONAL
114 arityInfo :: ArityInfo, -- Its arity
115 demandInfo :: Demand, -- Whether or not it is definitely demanded
116 specInfo :: CoreRules, -- Specialisations of this function which exist
117 strictnessInfo :: StrictnessInfo, -- Strictness properties
118 workerInfo :: WorkerInfo, -- Pointer to Worker Function
119 unfoldingInfo :: Unfolding, -- Its unfolding
120 updateInfo :: UpdateInfo, -- Which args should be updated
122 cprInfo :: CprInfo, -- Function always constructs a product result
123 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
124 inlinePragInfo :: InlinePragInfo -- Inline pragmas
127 seqIdInfo :: IdInfo -> ()
128 seqIdInfo (IdInfo {}) = ()
130 megaSeqIdInfo :: IdInfo -> ()
132 = seqFlavour (flavourInfo info) `seq`
133 seqArity (arityInfo info) `seq`
134 seqDemand (demandInfo info) `seq`
135 seqRules (specInfo info) `seq`
136 seqStrictness (strictnessInfo info) `seq`
137 seqWorker (workerInfo info) `seq`
139 -- seqUnfolding (unfoldingInfo info) `seq`
140 -- Omitting this improves runtimes a little, presumably because
141 -- some unfoldings are not calculated at all
143 seqCaf (cafInfo info) `seq`
144 seqCpr (cprInfo info) `seq`
145 seqLBVar (lbvarInfo info) `seq`
146 seqInlinePrag (inlinePragInfo info)
152 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
153 setSpecInfo info sp = sp `seq` info { specInfo = sp }
154 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
155 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
156 -- Try to avoid spack leaks by seq'ing
158 setUnfoldingInfo info uf = info { unfoldingInfo = uf }
159 -- We do *not* seq on the unfolding info, For some reason, doing so
160 -- actually increases residency significantly.
162 setUpdateInfo info ud = info { updateInfo = ud }
163 setDemandInfo info dd = info { demandInfo = dd }
164 setArityInfo info ar = info { arityInfo = ar }
165 setCafInfo info cf = info { cafInfo = cf }
166 setCprInfo info cp = info { cprInfo = cp }
167 setLBVarInfo info lb = info { lbvarInfo = lb }
169 setNoDiscardInfo info = case flavourInfo info of
170 VanillaId -> info { flavourInfo = NoDiscardId }
172 zapSpecPragInfo info = case flavourInfo info of
173 SpecPragmaId -> info { flavourInfo = VanillaId }
176 copyIdInfo :: IdInfo -- From
178 -> IdInfo -- To updated with stuff from From; except flavour unchanged
179 -- copyIdInfo is used when shorting out a top-level binding
182 -- where f is exported. We are going to swizzle it around to
185 -- but we must be careful to combine their IdInfos right.
186 -- The fact that things can go wrong here is a bad sign, but I can't see
187 -- how to make it 'patently right', so copyIdInfo is derived (pretty much) by trial and error
189 -- Here 'from' is f_local, 'to' is f.
191 copyIdInfo from to = from { flavourInfo = flavourInfo to,
192 specInfo = specInfo to
194 -- It's important to propagate the inline pragmas from bndr
195 -- to exportd_id. Ditto strictness etc. This "bites" when we use an INLNE pragma:
199 -- This becomes (where the "*" means INLINE prag)
201 -- M.f = /\a -> let mf* = \x -> (x,x) in mf
203 -- Now the mf floats out and we end up with the trivial binding
205 -- mf* = /\a -> \x -> (x,x)
208 -- Now, when we short out the M.f = mf binding we must preserve the inline
209 -- pragma on the mf binding.
211 -- On the other hand, transformation rules may be attached to the
212 -- 'to' Id, and we want to preserve them.
217 vanillaIdInfo :: IdInfo
218 vanillaIdInfo = mkIdInfo VanillaId
220 mkIdInfo :: IdFlavour -> IdInfo
221 mkIdInfo flv = IdInfo {
223 arityInfo = UnknownArity,
225 specInfo = emptyCoreRules,
226 workerInfo = Nothing,
227 strictnessInfo = NoStrictnessInfo,
228 unfoldingInfo = noUnfolding,
229 updateInfo = NoUpdateInfo,
230 cafInfo = MayHaveCafRefs,
232 lbvarInfo = NoLBVarInfo,
233 inlinePragInfo = NoInlinePragInfo
238 %************************************************************************
242 %************************************************************************
246 = VanillaId -- Most Ids are like this
247 | ConstantId Con -- The Id for a constant (data constructor or primop)
248 | RecordSelId FieldLabel -- The Id for a record selector
249 | SpecPragmaId -- Don't discard these
250 | NoDiscardId -- Don't discard these either
252 ppFlavourInfo :: IdFlavour -> SDoc
253 ppFlavourInfo VanillaId = empty
254 ppFlavourInfo (ConstantId _) = ptext SLIT("[Constr]")
255 ppFlavourInfo (RecordSelId _) = ptext SLIT("[RecSel]")
256 ppFlavourInfo SpecPragmaId = ptext SLIT("[SpecPrag]")
257 ppFlavourInfo NoDiscardId = ptext SLIT("[NoDiscard]")
259 seqFlavour :: IdFlavour -> ()
260 seqFlavour f = f `seq` ()
263 The @SpecPragmaId@ exists only to make Ids that are
264 on the *LHS* of bindings created by SPECIALISE pragmas;
266 The SpecPragmaId is never itself mentioned; it
267 exists solely so that the specialiser will find
268 the call to f, and make specialised version of it.
269 The SpecPragmaId binding is discarded by the specialiser
270 when it gathers up overloaded calls.
271 Meanwhile, it is not discarded as dead code.
274 %************************************************************************
276 \subsection[arity-IdInfo]{Arity info about an @Id@}
278 %************************************************************************
280 For locally-defined Ids, the code generator maintains its own notion
281 of their arities; so it should not be asking... (but other things
282 besides the code-generator need arity info!)
286 = UnknownArity -- No idea
287 | ArityExactly Int -- Arity is exactly this
288 | ArityAtLeast Int -- Arity is this or greater
290 seqArity :: ArityInfo -> ()
291 seqArity a = arityLowerBound a `seq` ()
293 exactArity = ArityExactly
294 atLeastArity = ArityAtLeast
295 unknownArity = UnknownArity
297 arityLowerBound :: ArityInfo -> Int
298 arityLowerBound UnknownArity = 0
299 arityLowerBound (ArityAtLeast n) = n
300 arityLowerBound (ArityExactly n) = n
302 hasArity :: ArityInfo -> Bool
303 hasArity UnknownArity = False
304 hasArity other = True
306 ppArityInfo UnknownArity = empty
307 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("__A"), int arity]
308 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("__AL"), int arity]
311 %************************************************************************
313 \subsection{Inline-pragma information}
315 %************************************************************************
321 | IMustNotBeINLINEd -- User NOINLINE pragma
323 | IAmALoopBreaker -- Used by the occurrence analyser to mark loop-breakers
324 -- in a group of recursive definitions
326 | ICanSafelyBeINLINEd -- Used by the occurrence analyser to mark things
327 -- that manifesly occur once, not inside SCCs,
328 -- not in constructor arguments
330 OccInfo -- Says whether the occurrence is inside a lambda
331 -- If so, must only substitute WHNFs
333 Bool -- False <=> occurs in more than one case branch
334 -- If so, there's a code-duplication issue
336 | IAmDead -- Marks unused variables. Sometimes useful for
337 -- lambda and case-bound variables.
339 | IMustBeINLINEd -- Absolutely must inline; used for PrimOps and
340 -- constructors only.
342 seqInlinePrag :: InlinePragInfo -> ()
343 seqInlinePrag (ICanSafelyBeINLINEd occ alts)
344 = occ `seq` alts `seq` ()
348 instance Outputable InlinePragInfo where
349 ppr NoInlinePragInfo = empty
350 ppr IMustBeINLINEd = ptext SLIT("__UU")
351 ppr IMustNotBeINLINEd = ptext SLIT("__Unot")
352 ppr IAmALoopBreaker = ptext SLIT("__Ux")
353 ppr IAmDead = ptext SLIT("__Ud")
354 ppr (ICanSafelyBeINLINEd InsideLam _) = ptext SLIT("__Ul")
355 ppr (ICanSafelyBeINLINEd _ _) = ptext SLIT("__Us")
357 instance Show InlinePragInfo where
358 showsPrec p prag = showsPrecSDoc p (ppr prag)
365 | InsideLam -- Inside a non-linear lambda (that is, a lambda which
366 -- is sure to be instantiated only once).
367 -- Substituting a redex for this occurrence is
368 -- dangerous because it might duplicate work.
370 instance Outputable OccInfo where
371 ppr NotInsideLam = empty
372 ppr InsideLam = text "l"
375 notInsideLambda :: OccInfo -> Bool
376 notInsideLambda NotInsideLam = True
377 notInsideLambda InsideLam = False
380 %************************************************************************
382 \subsection[strictness-IdInfo]{Strictness info about an @Id@}
384 %************************************************************************
386 We specify the strictness of a function by giving information about
387 each of the ``wrapper's'' arguments (see the description about
388 worker/wrapper-style transformations in the PJ/Launchbury paper on
391 The list of @Demands@ specifies: (a)~the strictness properties of a
392 function's arguments; and (b)~the type signature of that worker (if it
393 exists); i.e. its calling convention.
395 Note that the existence of a worker function is now denoted by the Id's
402 | StrictnessInfo [Demand]
403 Bool -- True <=> the function diverges regardless of its arguments
404 -- Useful for "error" and other disguised variants thereof.
405 -- BUT NB: f = \x y. error "urk"
406 -- will have info SI [SS] True
407 -- but still (f) and (f 2) are not bot; only (f 3 2) is bot
409 seqStrictness :: StrictnessInfo -> ()
410 seqStrictness (StrictnessInfo ds b) = b `seq` seqDemands ds
411 seqStrictness other = ()
415 mkStrictnessInfo :: ([Demand], Bool) -> StrictnessInfo
417 mkStrictnessInfo (xs, is_bot)
418 | all isLazy xs && not is_bot = NoStrictnessInfo -- Uninteresting
419 | otherwise = StrictnessInfo xs is_bot
421 noStrictnessInfo = NoStrictnessInfo
423 isBottomingStrictness (StrictnessInfo _ bot) = bot
424 isBottomingStrictness NoStrictnessInfo = False
426 -- appIsBottom returns true if an application to n args would diverge
427 appIsBottom (StrictnessInfo ds bot) n = bot && (n >= length ds)
428 appIsBottom NoStrictnessInfo n = False
430 ppStrictnessInfo NoStrictnessInfo = empty
431 ppStrictnessInfo (StrictnessInfo wrapper_args bot)
432 = hsep [ptext SLIT("__S"), pprDemands wrapper_args bot]
435 %************************************************************************
437 \subsection[worker-IdInfo]{Worker info about an @Id@}
439 %************************************************************************
441 If this Id has a worker then we store a reference to it. Worker
442 functions are generated by the worker/wrapper pass. This uses
443 information from the strictness and CPR analyses.
445 There might not be a worker, even for a strict function, because:
446 (a) the function might be small enough to inline, so no need
448 (b) the strictness info might be "SSS" or something, so no w/w split.
452 type WorkerInfo = Maybe Id
455 mkWorkerInfo :: Id -> WorkerInfo
456 mkWorkerInfo wk_id = Just wk_id
459 seqWorker :: WorkerInfo -> ()
460 seqWorker (Just id) = id `seq` ()
461 seqWorker Nothing = ()
463 ppWorkerInfo Nothing = empty
464 ppWorkerInfo (Just wk_id) = ptext SLIT("__P") <+> ppr wk_id
466 noWorkerInfo = Nothing
468 workerExists :: Maybe Id -> Bool
469 workerExists = isJust
473 %************************************************************************
475 \subsection[update-IdInfo]{Update-analysis info about an @Id@}
477 %************************************************************************
482 | SomeUpdateInfo UpdateSpec
484 -- we need Eq/Ord to cross-chk update infos in interfaces
486 -- the form in which we pass update-analysis info between modules:
487 type UpdateSpec = [Int]
491 mkUpdateInfo = SomeUpdateInfo
493 updateInfoMaybe NoUpdateInfo = Nothing
494 updateInfoMaybe (SomeUpdateInfo []) = Nothing
495 updateInfoMaybe (SomeUpdateInfo u) = Just u
498 Text instance so that the update annotations can be read in.
501 ppUpdateInfo NoUpdateInfo = empty
502 ppUpdateInfo (SomeUpdateInfo []) = empty
503 ppUpdateInfo (SomeUpdateInfo spec) = (<>) (ptext SLIT("__U ")) (hcat (map int spec))
506 %************************************************************************
508 \subsection[CAF-IdInfo]{CAF-related information}
510 %************************************************************************
512 This information is used to build Static Reference Tables (see
513 simplStg/ComputeSRT.lhs).
517 = MayHaveCafRefs -- either:
518 -- (1) A function or static constructor
519 -- that refers to one or more CAFs,
520 -- (2) A real live CAF
522 | NoCafRefs -- A function or static constructor
523 -- that refers to no CAFs.
525 -- LATER: not sure how easy this is...
529 seqCaf c = c `seq` ()
531 ppCafInfo NoCafRefs = ptext SLIT("__C")
532 ppCafInfo MayHaveCafRefs = empty
536 %************************************************************************
538 \subsection[CAF-IdInfo]{CAF-related information}
540 %************************************************************************
542 zapFragileIdInfo is used when cloning binders, mainly in the
543 simplifier. We must forget about used-once information because that
544 isn't necessarily correct in the transformed program.
545 Also forget specialisations and unfoldings because they would need
546 substitution to be correct. (They get pinned back on separately.)
549 zapFragileIdInfo :: IdInfo -> Maybe IdInfo
550 zapFragileIdInfo info@(IdInfo {inlinePragInfo = inline_prag,
553 unfoldingInfo = unfolding})
554 | not is_fragile_inline_prag
555 -- We must forget about whether it was marked safe-to-inline,
556 -- because that isn't necessarily true in the simplified expression.
557 -- This is important because expressions may be re-simplified
559 && isEmptyCoreRules rules
560 -- Specialisations would need substituting. They get pinned
561 -- back on separately.
563 && not (workerExists wrkr)
565 && not (hasUnfolding unfolding)
566 -- This is very important; occasionally a let-bound binder is used
567 -- as a binder in some lambda, in which case its unfolding is utterly
568 -- bogus. Also the unfolding uses old binders so if we left it we'd
569 -- have to substitute it. Much better simply to give the Id a new
570 -- unfolding each time, which is what the simplifier does.
574 = Just (info {inlinePragInfo = safe_inline_prag,
575 workerInfo = noWorkerInfo,
576 specInfo = emptyCoreRules,
577 unfoldingInfo = noUnfolding})
580 is_fragile_inline_prag = case inline_prag of
581 ICanSafelyBeINLINEd _ _ -> True
583 -- We used to say the dead-ness was fragile, but I don't
584 -- see why it is. Furthermore, deadness is a pain to lose;
585 -- see Simplify.mkDupableCont (Select ...)
590 -- Be careful not to destroy real 'pragma' info
591 safe_inline_prag | is_fragile_inline_prag = NoInlinePragInfo
592 | otherwise = inline_prag
596 @zapLamIdInfo@ is used for lambda binders that turn out to to be
597 part of an unsaturated lambda
600 zapLamIdInfo :: IdInfo -> Maybe IdInfo
601 zapLamIdInfo info@(IdInfo {inlinePragInfo = inline_prag, demandInfo = demand})
602 | is_safe_inline_prag && not (isStrict demand)
605 = Just (info {inlinePragInfo = safe_inline_prag,
606 demandInfo = wwLazy})
608 -- The "unsafe" prags are the ones that say I'm not in a lambda
609 -- because that might not be true for an unsaturated lambda
610 is_safe_inline_prag = case inline_prag of
611 ICanSafelyBeINLINEd NotInsideLam nalts -> False
614 safe_inline_prag = case inline_prag of
615 ICanSafelyBeINLINEd _ nalts
616 -> ICanSafelyBeINLINEd InsideLam nalts
621 zapIdInfoForStg :: IdInfo -> IdInfo
622 -- Return only the info needed for STG stuff
623 -- Namely, nothing, I think
624 zapIdInfoForStg info = vanillaIdInfo
628 %************************************************************************
630 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
632 %************************************************************************
634 If the @Id@ is a function then it may have CPR info. A CPR analysis
635 phase detects whether:
639 The function's return value has a product type, i.e. an algebraic type
640 with a single constructor. Examples of such types are tuples and boxed
643 The function always 'constructs' the value that it is returning. It
644 must do this on every path through, and it's OK if it calls another
645 function which constructs the result.
648 If this is the case then we store a template which tells us the
649 function has the CPR property and which components of the result are
658 -- e.g. const 5 == CPRInfo [NoCPRInfo]
665 -- CPRInfo [CPRInfo [NoCPRInfo],
666 -- CPRInfo [NoCprInfo,
667 -- CPRInfo [NoCPRInfo],
674 seqCpr :: CprInfo -> ()
675 seqCpr (CPRInfo cs) = seqCprs cs
676 seqCpr NoCPRInfo = ()
679 seqCprs (c:cs) = seqCpr c `seq` seqCprs cs
682 noCprInfo = NoCPRInfo
684 ppCprInfo NoCPRInfo = empty
685 ppCprInfo c@(CPRInfo _)
686 = hsep [ptext SLIT("__M"), ppCprInfo' c]
688 ppCprInfo' NoCPRInfo = char '-'
689 ppCprInfo' (CPRInfo args) = parens (hcat (map ppCprInfo' args))
691 instance Outputable CprInfo where
694 instance Show CprInfo where
695 showsPrec p c = showsPrecSDoc p (ppr c)
699 %************************************************************************
701 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
703 %************************************************************************
705 If the @Id@ is a lambda-bound variable then it may have lambda-bound
706 var info. The usage analysis (UsageSP) detects whether the lambda
707 binding this var is a ``one-shot'' lambda; that is, whether it is
708 applied at most once.
710 This information may be useful in optimisation, as computations may
711 safely be floated inside such a lambda without risk of duplicating
718 | IsOneShotLambda -- The lambda that binds this Id is applied
720 -- HACK ALERT! placing this info here is a short-term hack,
721 -- but it minimises changes to the rest of the compiler.
722 -- Hack agreed by SLPJ/KSW 1999-04.
724 seqLBVar l = l `seq` ()
728 noLBVarInfo = NoLBVarInfo
730 -- not safe to print or parse LBVarInfo because it is not really a
731 -- property of the definition, but a property of the context.
732 pprLBVarInfo NoLBVarInfo = empty
733 pprLBVarInfo IsOneShotLambda = getPprStyle $ \ sty ->
734 if ifaceStyle sty then empty
735 else ptext SLIT("OneShot")
737 instance Outputable LBVarInfo where
740 instance Show LBVarInfo where
741 showsPrec p c = showsPrecSDoc p (ppr c)