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, copyIdInfo,
19 IdFlavour(..), flavourInfo,
25 exactArity, atLeastArity, unknownArity, hasArity,
26 arityInfo, setArityInfo, ppArityInfo, arityLowerBound,
29 StrictnessInfo(..), -- Non-abstract
31 noStrictnessInfo, strictnessInfo,
32 ppStrictnessInfo, setStrictnessInfo,
33 isBottomingStrictness, appIsBottom,
36 WorkerInfo, workerExists,
37 workerInfo, setWorkerInfo, ppWorkerInfo,
40 unfoldingInfo, setUnfoldingInfo,
43 demandInfo, setDemandInfo,
47 inlinePragInfo, setInlinePragInfo, pprInlinePragInfo,
50 OccInfo(..), InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
51 occInfo, setOccInfo, isFragileOccInfo,
54 specInfo, setSpecInfo,
57 UpdateInfo, UpdateSpec,
58 mkUpdateInfo, updateInfo, updateInfoMaybe, ppUpdateInfo, setUpdateInfo,
61 CafInfo(..), cafInfo, setCafInfo, ppCafInfo,
63 -- Constructed Product Result Info
64 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
66 -- Lambda-bound variable info
67 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo
70 #include "HsVersions.h"
73 import {-# SOURCE #-} CoreUnfold ( Unfolding, noUnfolding, hasUnfolding, seqUnfolding )
74 import {-# SOURCE #-} CoreSyn ( CoreExpr, CoreRules, emptyCoreRules, isEmptyCoreRules, seqRules )
75 import {-# SOURCE #-} Const ( Con )
78 import VarSet ( IdOrTyVarSet )
79 import FieldLabel ( FieldLabel )
80 import Demand ( Demand, isStrict, isLazy, wwLazy, pprDemands, seqDemand, seqDemands )
82 import Maybe ( isJust )
84 infixl 1 `setUpdateInfo`,
95 -- infixl so you can say (id `set` a `set` b)
98 An @IdInfo@ gives {\em optional} information about an @Id@. If
99 present it never lies, but it may not be present, in which case there
100 is always a conservative assumption which can be made.
102 There is one exception: the 'flavour' is *not* optional.
103 You must not discard it.
104 It used to be in Var.lhs, but that seems unclean.
106 Two @Id@s may have different info even though they have the same
107 @Unique@ (and are hence the same @Id@); for example, one might lack
108 the properties attached to the other.
110 The @IdInfo@ gives information about the value, or definition, of the
111 @Id@. It does {\em not} contain information about the @Id@'s usage
112 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
118 flavourInfo :: IdFlavour, -- NOT OPTIONAL
119 arityInfo :: ArityInfo, -- Its arity
120 demandInfo :: Demand, -- Whether or not it is definitely demanded
121 specInfo :: CoreRules, -- Specialisations of this function which exist
122 strictnessInfo :: StrictnessInfo, -- Strictness properties
123 workerInfo :: WorkerInfo, -- Pointer to Worker Function
124 unfoldingInfo :: Unfolding, -- Its unfolding
125 updateInfo :: UpdateInfo, -- Which args should be updated
127 cprInfo :: CprInfo, -- Function always constructs a product result
128 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
129 inlinePragInfo :: InlinePragInfo, -- Inline pragma
130 occInfo :: OccInfo -- How it occurs
133 seqIdInfo :: IdInfo -> ()
134 seqIdInfo (IdInfo {}) = ()
136 megaSeqIdInfo :: IdInfo -> ()
138 = seqFlavour (flavourInfo info) `seq`
139 seqArity (arityInfo info) `seq`
140 seqDemand (demandInfo info) `seq`
141 seqRules (specInfo info) `seq`
142 seqStrictness (strictnessInfo info) `seq`
143 seqWorker (workerInfo info) `seq`
145 -- seqUnfolding (unfoldingInfo info) `seq`
146 -- Omitting this improves runtimes a little, presumably because
147 -- some unfoldings are not calculated at all
149 seqCaf (cafInfo info) `seq`
150 seqCpr (cprInfo info) `seq`
151 seqLBVar (lbvarInfo info) `seq`
152 seqOccInfo (occInfo info)
158 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
159 setSpecInfo info sp = PSEQ sp (info { specInfo = sp })
160 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
161 setOccInfo info oc = oc `seq` info { occInfo = oc }
162 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
163 -- Try to avoid spack leaks by seq'ing
165 setUnfoldingInfo info uf = info { unfoldingInfo = uf }
166 -- We do *not* seq on the unfolding info, For some reason, doing so
167 -- actually increases residency significantly.
169 setUpdateInfo info ud = info { updateInfo = ud }
170 setDemandInfo info dd = info { demandInfo = dd }
171 setArityInfo info ar = info { arityInfo = ar }
172 setCafInfo info cf = info { cafInfo = cf }
173 setCprInfo info cp = info { cprInfo = cp }
174 setLBVarInfo info lb = info { lbvarInfo = lb }
176 setNoDiscardInfo info = case flavourInfo info of
177 VanillaId -> info { flavourInfo = NoDiscardId }
179 zapSpecPragInfo info = case flavourInfo info of
180 SpecPragmaId -> info { flavourInfo = VanillaId }
187 vanillaIdInfo :: IdInfo
188 vanillaIdInfo = mkIdInfo VanillaId
190 mkIdInfo :: IdFlavour -> IdInfo
191 mkIdInfo flv = IdInfo {
193 arityInfo = UnknownArity,
195 specInfo = emptyCoreRules,
196 workerInfo = Nothing,
197 strictnessInfo = NoStrictnessInfo,
198 unfoldingInfo = noUnfolding,
199 updateInfo = NoUpdateInfo,
200 cafInfo = MayHaveCafRefs,
202 lbvarInfo = NoLBVarInfo,
203 inlinePragInfo = NoInlinePragInfo,
209 %************************************************************************
213 %************************************************************************
217 = VanillaId -- Most Ids are like this
218 | ConstantId Con -- The Id for a constant (data constructor or primop)
219 | RecordSelId FieldLabel -- The Id for a record selector
220 | SpecPragmaId -- Don't discard these
221 | NoDiscardId -- Don't discard these either
223 ppFlavourInfo :: IdFlavour -> SDoc
224 ppFlavourInfo VanillaId = empty
225 ppFlavourInfo (ConstantId _) = ptext SLIT("[Constr]")
226 ppFlavourInfo (RecordSelId _) = ptext SLIT("[RecSel]")
227 ppFlavourInfo SpecPragmaId = ptext SLIT("[SpecPrag]")
228 ppFlavourInfo NoDiscardId = ptext SLIT("[NoDiscard]")
230 seqFlavour :: IdFlavour -> ()
231 seqFlavour f = f `seq` ()
234 The @SpecPragmaId@ exists only to make Ids that are
235 on the *LHS* of bindings created by SPECIALISE pragmas;
237 The SpecPragmaId is never itself mentioned; it
238 exists solely so that the specialiser will find
239 the call to f, and make specialised version of it.
240 The SpecPragmaId binding is discarded by the specialiser
241 when it gathers up overloaded calls.
242 Meanwhile, it is not discarded as dead code.
245 %************************************************************************
247 \subsection[arity-IdInfo]{Arity info about an @Id@}
249 %************************************************************************
251 For locally-defined Ids, the code generator maintains its own notion
252 of their arities; so it should not be asking... (but other things
253 besides the code-generator need arity info!)
257 = UnknownArity -- No idea
259 | ArityExactly Int -- Arity is exactly this. We use this when importing a
260 -- function; it's already been compiled and we know its
263 | ArityAtLeast Int -- Arity is this or greater. We attach this arity to
264 -- functions in the module being compiled. Their arity
265 -- might increase later in the compilation process, if
266 -- an extra lambda floats up to the binding site.
268 seqArity :: ArityInfo -> ()
269 seqArity a = arityLowerBound a `seq` ()
271 exactArity = ArityExactly
272 atLeastArity = ArityAtLeast
273 unknownArity = UnknownArity
275 arityLowerBound :: ArityInfo -> Int
276 arityLowerBound UnknownArity = 0
277 arityLowerBound (ArityAtLeast n) = n
278 arityLowerBound (ArityExactly n) = n
280 hasArity :: ArityInfo -> Bool
281 hasArity UnknownArity = False
282 hasArity other = True
284 ppArityInfo UnknownArity = empty
285 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("__A"), int arity]
286 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("__AL"), int arity]
289 %************************************************************************
291 \subsection{Inline-pragma information}
293 %************************************************************************
298 | IMustNotBeINLINEd Bool -- True <=> came from an INLINE prag, False <=> came from a NOINLINE prag
299 (Maybe Int) -- Phase number from pragma, if any
300 -- The True, Nothing case doesn't need to be recorded
302 instance Outputable InlinePragInfo where
303 -- This is now parsed in interface files
304 ppr NoInlinePragInfo = empty
305 ppr other_prag = ptext SLIT("__U") <> pprInlinePragInfo other_prag
307 pprInlinePragInfo NoInlinePragInfo = empty
308 pprInlinePragInfo (IMustNotBeINLINEd True Nothing) = empty
309 pprInlinePragInfo (IMustNotBeINLINEd True (Just n)) = brackets (int n)
310 pprInlinePragInfo (IMustNotBeINLINEd False Nothing) = brackets (char '!')
311 pprInlinePragInfo (IMustNotBeINLINEd False (Just n)) = brackets (char '!' <> int n)
313 instance Show InlinePragInfo where
314 showsPrec p prag = showsPrecSDoc p (ppr prag)
318 %************************************************************************
320 \subsection{Occurrence information}
322 %************************************************************************
328 | IAmDead -- Marks unused variables. Sometimes useful for
329 -- lambda and case-bound variables.
335 | IAmALoopBreaker -- Used by the occurrence analyser to mark loop-breakers
336 -- in a group of recursive definitions
338 seqOccInfo :: OccInfo -> ()
339 seqOccInfo (OneOcc in_lam once) = in_lam `seq` once `seq` ()
342 type InsideLam = Bool -- True <=> Occurs inside a non-linear lambda
343 -- Substituting a redex for this occurrence is
344 -- dangerous because it might duplicate work.
348 type OneBranch = Bool -- True <=> Occurs in only one case branch
349 -- so no code-duplication issue to worry about
353 isFragileOccInfo :: OccInfo -> Bool
354 isFragileOccInfo (OneOcc _ _) = True
355 isFragileOccInfo other = False
359 instance Outputable OccInfo where
360 -- only used for debugging; never parsed. KSW 1999-07
361 ppr NoOccInfo = empty
362 ppr IAmALoopBreaker = ptext SLIT("_Kx")
363 ppr IAmDead = ptext SLIT("_Kd")
364 ppr (OneOcc inside_lam one_branch) | inside_lam = ptext SLIT("_Kl")
365 | one_branch = ptext SLIT("_Ks")
366 | otherwise = ptext SLIT("_Ks*")
368 instance Show OccInfo where
369 showsPrec p occ = showsPrecSDoc p (ppr occ)
372 %************************************************************************
374 \subsection[strictness-IdInfo]{Strictness info about an @Id@}
376 %************************************************************************
378 We specify the strictness of a function by giving information about
379 each of the ``wrapper's'' arguments (see the description about
380 worker/wrapper-style transformations in the PJ/Launchbury paper on
383 The list of @Demands@ specifies: (a)~the strictness properties of a
384 function's arguments; and (b)~the type signature of that worker (if it
385 exists); i.e. its calling convention.
387 Note that the existence of a worker function is now denoted by the Id's
394 | StrictnessInfo [Demand]
395 Bool -- True <=> the function diverges regardless of its arguments
396 -- Useful for "error" and other disguised variants thereof.
397 -- BUT NB: f = \x y. error "urk"
398 -- will have info SI [SS] True
399 -- but still (f) and (f 2) are not bot; only (f 3 2) is bot
401 seqStrictness :: StrictnessInfo -> ()
402 seqStrictness (StrictnessInfo ds b) = b `seq` seqDemands ds
403 seqStrictness other = ()
407 mkStrictnessInfo :: ([Demand], Bool) -> StrictnessInfo
409 mkStrictnessInfo (xs, is_bot)
410 | all isLazy xs && not is_bot = NoStrictnessInfo -- Uninteresting
411 | otherwise = StrictnessInfo xs is_bot
413 noStrictnessInfo = NoStrictnessInfo
415 isBottomingStrictness (StrictnessInfo _ bot) = bot
416 isBottomingStrictness NoStrictnessInfo = False
418 -- appIsBottom returns true if an application to n args would diverge
419 appIsBottom (StrictnessInfo ds bot) n = bot && (n >= length ds)
420 appIsBottom NoStrictnessInfo n = False
422 ppStrictnessInfo NoStrictnessInfo = empty
423 ppStrictnessInfo (StrictnessInfo wrapper_args bot)
424 = hsep [ptext SLIT("__S"), pprDemands wrapper_args bot]
427 %************************************************************************
429 \subsection[worker-IdInfo]{Worker info about an @Id@}
431 %************************************************************************
433 If this Id has a worker then we store a reference to it. Worker
434 functions are generated by the worker/wrapper pass. This uses
435 information from the strictness and CPR analyses.
437 There might not be a worker, even for a strict function, because:
438 (a) the function might be small enough to inline, so no need
440 (b) the strictness info might be "SSS" or something, so no w/w split.
444 type WorkerInfo = Maybe Id
447 mkWorkerInfo :: Id -> WorkerInfo
448 mkWorkerInfo wk_id = Just wk_id
451 seqWorker :: WorkerInfo -> ()
452 seqWorker (Just id) = id `seq` ()
453 seqWorker Nothing = ()
455 ppWorkerInfo Nothing = empty
456 ppWorkerInfo (Just wk_id) = ptext SLIT("__P") <+> ppr wk_id
458 noWorkerInfo = Nothing
460 workerExists :: WorkerInfo -> Bool
461 workerExists = isJust
465 %************************************************************************
467 \subsection[update-IdInfo]{Update-analysis info about an @Id@}
469 %************************************************************************
474 | SomeUpdateInfo UpdateSpec
476 -- we need Eq/Ord to cross-chk update infos in interfaces
478 -- the form in which we pass update-analysis info between modules:
479 type UpdateSpec = [Int]
483 mkUpdateInfo = SomeUpdateInfo
485 updateInfoMaybe NoUpdateInfo = Nothing
486 updateInfoMaybe (SomeUpdateInfo []) = Nothing
487 updateInfoMaybe (SomeUpdateInfo u) = Just u
490 Text instance so that the update annotations can be read in.
493 ppUpdateInfo NoUpdateInfo = empty
494 ppUpdateInfo (SomeUpdateInfo []) = empty
495 ppUpdateInfo (SomeUpdateInfo spec) = (<>) (ptext SLIT("__UA ")) (hcat (map int spec))
496 -- was "__U "; changed to avoid conflict with unfoldings. KSW 1999-07.
499 %************************************************************************
501 \subsection[CAF-IdInfo]{CAF-related information}
503 %************************************************************************
505 This information is used to build Static Reference Tables (see
506 simplStg/ComputeSRT.lhs).
510 = MayHaveCafRefs -- either:
511 -- (1) A function or static constructor
512 -- that refers to one or more CAFs,
513 -- (2) A real live CAF
515 | NoCafRefs -- A function or static constructor
516 -- that refers to no CAFs.
518 -- LATER: not sure how easy this is...
522 seqCaf c = c `seq` ()
524 ppCafInfo NoCafRefs = ptext SLIT("__C")
525 ppCafInfo MayHaveCafRefs = empty
529 %************************************************************************
531 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
533 %************************************************************************
535 If the @Id@ is a function then it may have CPR info. A CPR analysis
536 phase detects whether:
540 The function's return value has a product type, i.e. an algebraic type
541 with a single constructor. Examples of such types are tuples and boxed
544 The function always 'constructs' the value that it is returning. It
545 must do this on every path through, and it's OK if it calls another
546 function which constructs the result.
549 If this is the case then we store a template which tells us the
550 function has the CPR property and which components of the result are
559 -- e.g. const 5 == CPRInfo [NoCPRInfo]
566 -- CPRInfo [CPRInfo [NoCPRInfo],
567 -- CPRInfo [NoCprInfo,
568 -- CPRInfo [NoCPRInfo],
575 seqCpr :: CprInfo -> ()
576 seqCpr (CPRInfo cs) = seqCprs cs
577 seqCpr NoCPRInfo = ()
580 seqCprs (c:cs) = seqCpr c `seq` seqCprs cs
583 noCprInfo = NoCPRInfo
585 ppCprInfo NoCPRInfo = empty
586 ppCprInfo c@(CPRInfo _)
587 = hsep [ptext SLIT("__M"), ppCprInfo' c]
589 ppCprInfo' NoCPRInfo = char '-'
590 ppCprInfo' (CPRInfo args) = parens (hcat (map ppCprInfo' args))
592 instance Outputable CprInfo where
595 instance Show CprInfo where
596 showsPrec p c = showsPrecSDoc p (ppr c)
600 %************************************************************************
602 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
604 %************************************************************************
606 If the @Id@ is a lambda-bound variable then it may have lambda-bound
607 var info. The usage analysis (UsageSP) detects whether the lambda
608 binding this var is a ``one-shot'' lambda; that is, whether it is
609 applied at most once.
611 This information may be useful in optimisation, as computations may
612 safely be floated inside such a lambda without risk of duplicating
619 | IsOneShotLambda -- The lambda that binds this Id is applied
621 -- HACK ALERT! placing this info here is a short-term hack,
622 -- but it minimises changes to the rest of the compiler.
623 -- Hack agreed by SLPJ/KSW 1999-04.
625 seqLBVar l = l `seq` ()
629 noLBVarInfo = NoLBVarInfo
631 -- not safe to print or parse LBVarInfo because it is not really a
632 -- property of the definition, but a property of the context.
633 pprLBVarInfo NoLBVarInfo = empty
634 pprLBVarInfo IsOneShotLambda = getPprStyle $ \ sty ->
635 if ifaceStyle sty then empty
636 else ptext SLIT("OneShot")
638 instance Outputable LBVarInfo where
641 instance Show LBVarInfo where
642 showsPrec p c = showsPrecSDoc p (ppr c)
646 %************************************************************************
648 \subsection{Bulk operations on IdInfo}
650 %************************************************************************
652 zapFragileInfo is used when cloning binders, mainly in the
653 simplifier. We must forget about used-once information because that
654 isn't necessarily correct in the transformed program.
655 Also forget specialisations and unfoldings because they would need
656 substitution to be correct. (They get pinned back on separately.)
659 zapFragileInfo :: IdInfo -> Maybe IdInfo
660 zapFragileInfo info@(IdInfo {occInfo = occ,
663 unfoldingInfo = unfolding})
664 | not (isFragileOccInfo occ)
665 -- We must forget about whether it was marked safe-to-inline,
666 -- because that isn't necessarily true in the simplified expression.
667 -- This is important because expressions may be re-simplified
668 -- We don't zap deadness or loop-breaker-ness.
669 -- The latter is important because it tells MkIface not to
670 -- spit out an inlining for the thing. The former doesn't
671 -- seem so important, but there's no harm.
673 && isEmptyCoreRules rules
674 -- Specialisations would need substituting. They get pinned
675 -- back on separately.
677 && not (workerExists wrkr)
679 && not (hasUnfolding unfolding)
680 -- This is very important; occasionally a let-bound binder is used
681 -- as a binder in some lambda, in which case its unfolding is utterly
682 -- bogus. Also the unfolding uses old binders so if we left it we'd
683 -- have to substitute it. Much better simply to give the Id a new
684 -- unfolding each time, which is what the simplifier does.
688 = Just (info {occInfo = robust_occ_info,
689 workerInfo = noWorkerInfo,
690 specInfo = emptyCoreRules,
691 unfoldingInfo = noUnfolding})
693 -- It's important to keep the loop-breaker info,
694 -- because the substitution doesn't remember it.
695 robust_occ_info = case occ of
696 OneOcc _ _ -> NoOccInfo
700 @zapLamInfo@ is used for lambda binders that turn out to to be
701 part of an unsaturated lambda
704 zapLamInfo :: IdInfo -> Maybe IdInfo
705 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
706 | is_safe_occ && not (isStrict demand)
709 = Just (info {occInfo = safe_occ,
710 demandInfo = wwLazy})
712 -- The "unsafe" occ info is the ones that say I'm not in a lambda
713 -- because that might not be true for an unsaturated lambda
714 is_safe_occ = case occ of
715 OneOcc in_lam once -> in_lam
718 safe_occ = case occ of
719 OneOcc _ once -> OneOcc insideLam once
724 copyIdInfo is used when shorting out a top-level binding
727 where f is exported. We are going to swizzle it around to
730 but we must be careful to combine their IdInfos right.
731 The fact that things can go wrong here is a bad sign, but I can't see
732 how to make it 'patently right', so copyIdInfo is derived (pretty much) by trial and error
734 Here 'from' is f_local, 'to' is f, and the result is attached to f
737 copyIdInfo :: IdInfo -- From
739 -> IdInfo -- To, updated with stuff from From; except flavour unchanged
740 copyIdInfo from to = from { flavourInfo = flavourInfo to,
741 specInfo = specInfo to,
742 inlinePragInfo = inlinePragInfo to
744 -- It's important to preserve the inline pragma on 'f'; e.g. consider
745 -- {-# NOINLINE f #-}
748 -- similarly, transformation rules may be attached to f
749 -- and we want to preserve them.
751 -- On the other hand, we want the strictness info from f_local.