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,
25 exactArity, atLeastArity, unknownArity, hasArity,
26 arityInfo, setArityInfo, ppArityInfo, arityLowerBound,
28 -- Strictness; imported from Demand
30 mkStrictnessInfo, noStrictnessInfo,
31 ppStrictnessInfo,isBottomingStrictness,
33 strictnessInfo, setStrictnessInfo,
36 WorkerInfo(..), workerExists, wrapperArity, workerId,
37 workerInfo, setWorkerInfo, ppWorkerInfo,
40 unfoldingInfo, setUnfoldingInfo,
43 demandInfo, setDemandInfo,
47 inlinePragInfo, setInlinePragInfo, pprInlinePragInfo,
48 isNeverInlinePrag, neverInlinePrag,
51 OccInfo(..), isFragileOcc, isDeadOcc, isLoopBreaker,
52 InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
56 specInfo, setSpecInfo,
59 CafInfo(..), cafInfo, setCafInfo, ppCafInfo,
61 -- Constructed Product Result Info
62 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
64 -- Lambda-bound variable info
65 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo
68 #include "HsVersions.h"
72 import PrimOp ( PrimOp )
74 import BasicTypes ( OccInfo(..), isFragileOcc, isDeadOcc, seqOccInfo, isLoopBreaker,
75 InsideLam, insideLam, notInsideLam,
76 OneBranch, oneBranch, notOneBranch,
79 import DataCon ( DataCon )
80 import FieldLabel ( FieldLabel )
81 import Demand -- Lots of stuff
83 import Maybe ( isJust )
85 infixl 1 `setDemandInfo`,
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
126 cprInfo :: CprInfo, -- Function always constructs a product result
127 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
128 inlinePragInfo :: InlinePragInfo, -- Inline pragma
129 occInfo :: OccInfo -- How it occurs
132 seqIdInfo :: IdInfo -> ()
133 seqIdInfo (IdInfo {}) = ()
135 megaSeqIdInfo :: IdInfo -> ()
137 = seqFlavour (flavourInfo info) `seq`
138 seqArity (arityInfo info) `seq`
139 seqDemand (demandInfo info) `seq`
140 seqRules (specInfo info) `seq`
141 seqStrictnessInfo (strictnessInfo info) `seq`
142 seqWorker (workerInfo info) `seq`
144 -- seqUnfolding (unfoldingInfo info) `seq`
145 -- Omitting this improves runtimes a little, presumably because
146 -- some unfoldings are not calculated at all
148 seqCaf (cafInfo info) `seq`
149 seqCpr (cprInfo info) `seq`
150 seqLBVar (lbvarInfo info) `seq`
151 seqOccInfo (occInfo info)
157 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
158 setSpecInfo info sp = PSEQ sp (info { specInfo = sp })
159 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
160 setOccInfo info oc = oc `seq` info { occInfo = oc }
161 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
162 -- Try to avoid spack leaks by seq'ing
164 setUnfoldingInfo info uf
165 | isEvaldUnfolding uf && isStrict (demandInfo info)
166 -- If the unfolding is a value, the demand info may
167 -- go pear-shaped, so we nuke it. Example:
169 -- case x of (p,q) -> h p q x
170 -- Here x is certainly demanded. But after we've nuked
171 -- the case, we'll get just
172 -- let x = (a,b) in h a b x
173 -- and now x is not demanded (I'm assuming h is lazy)
174 -- This really happens. The solution here is a bit ad hoc...
175 = info { unfoldingInfo = uf, demandInfo = wwLazy }
178 -- We do *not* seq on the unfolding info, For some reason, doing so
179 -- actually increases residency significantly.
180 = info { unfoldingInfo = uf }
182 setDemandInfo info dd = info { demandInfo = dd }
183 setArityInfo info ar = info { arityInfo = ar }
184 setCafInfo info cf = info { cafInfo = cf }
185 setCprInfo info cp = info { cprInfo = cp }
186 setLBVarInfo info lb = info { lbvarInfo = lb }
188 setNoDiscardInfo info = case flavourInfo info of
189 VanillaId -> info { flavourInfo = NoDiscardId }
191 zapSpecPragInfo info = case flavourInfo info of
192 SpecPragmaId -> info { flavourInfo = VanillaId }
198 vanillaIdInfo :: IdInfo
199 vanillaIdInfo = mkIdInfo VanillaId
201 mkIdInfo :: IdFlavour -> IdInfo
202 mkIdInfo flv = IdInfo {
204 arityInfo = UnknownArity,
206 specInfo = emptyCoreRules,
207 workerInfo = NoWorker,
208 strictnessInfo = NoStrictnessInfo,
209 unfoldingInfo = noUnfolding,
210 cafInfo = MayHaveCafRefs,
212 lbvarInfo = NoLBVarInfo,
213 inlinePragInfo = NoInlinePragInfo,
219 %************************************************************************
223 %************************************************************************
227 = VanillaId -- Most Ids are like this
228 | DataConId DataCon -- The Id for a data constructor *worker*
229 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
230 -- [the only reasons we need to know is so that
231 -- a) we can suppress printing a definition in the interface file
232 -- b) when typechecking a pattern we can get from the
233 -- Id back to the data con]
234 | PrimOpId PrimOp -- The Id for a primitive operator
235 | RecordSelId FieldLabel -- The Id for a record selector
236 | SpecPragmaId -- Don't discard these
237 | NoDiscardId -- Don't discard these either
239 ppFlavourInfo :: IdFlavour -> SDoc
240 ppFlavourInfo VanillaId = empty
241 ppFlavourInfo (DataConId _) = ptext SLIT("[DataCon]")
242 ppFlavourInfo (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
243 ppFlavourInfo (PrimOpId _) = ptext SLIT("[PrimOp]")
244 ppFlavourInfo (RecordSelId _) = ptext SLIT("[RecSel]")
245 ppFlavourInfo SpecPragmaId = ptext SLIT("[SpecPrag]")
246 ppFlavourInfo NoDiscardId = ptext SLIT("[NoDiscard]")
248 seqFlavour :: IdFlavour -> ()
249 seqFlavour f = f `seq` ()
252 The @SpecPragmaId@ exists only to make Ids that are
253 on the *LHS* of bindings created by SPECIALISE pragmas;
255 The SpecPragmaId is never itself mentioned; it
256 exists solely so that the specialiser will find
257 the call to f, and make specialised version of it.
258 The SpecPragmaId binding is discarded by the specialiser
259 when it gathers up overloaded calls.
260 Meanwhile, it is not discarded as dead code.
263 %************************************************************************
265 \subsection[arity-IdInfo]{Arity info about an @Id@}
267 %************************************************************************
269 For locally-defined Ids, the code generator maintains its own notion
270 of their arities; so it should not be asking... (but other things
271 besides the code-generator need arity info!)
275 = UnknownArity -- No idea
277 | ArityExactly Arity -- Arity is exactly this. We use this when importing a
278 -- function; it's already been compiled and we know its
281 | ArityAtLeast Arity -- A partial application of this Id to up to n-1 value arguments
282 -- does essentially no work. That is not necessarily the
283 -- same as saying that it has n leading lambdas, because coerces
284 -- may get in the way.
286 -- functions in the module being compiled. Their arity
287 -- might increase later in the compilation process, if
288 -- an extra lambda floats up to the binding site.
291 seqArity :: ArityInfo -> ()
292 seqArity a = arityLowerBound a `seq` ()
294 exactArity = ArityExactly
295 atLeastArity = ArityAtLeast
296 unknownArity = UnknownArity
298 arityLowerBound :: ArityInfo -> Arity
299 arityLowerBound UnknownArity = 0
300 arityLowerBound (ArityAtLeast n) = n
301 arityLowerBound (ArityExactly n) = n
303 hasArity :: ArityInfo -> Bool
304 hasArity UnknownArity = False
305 hasArity other = True
307 ppArityInfo UnknownArity = empty
308 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("__A"), int arity]
309 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("__AL"), int arity]
312 %************************************************************************
314 \subsection{Inline-pragma information}
316 %************************************************************************
321 | IMustNotBeINLINEd Bool -- True <=> came from an INLINE prag, False <=> came from a NOINLINE prag
322 (Maybe Int) -- Phase number from pragma, if any
324 -- The True, Nothing case doesn't need to be recorded
326 -- SEE COMMENTS WITH CoreUnfold.blackListed on the
327 -- exact significance of the IMustNotBeINLINEd pragma
329 isNeverInlinePrag :: InlinePragInfo -> Bool
330 isNeverInlinePrag (IMustNotBeINLINEd _ Nothing) = True
331 isNeverInlinePrag other = False
333 neverInlinePrag :: InlinePragInfo
334 neverInlinePrag = IMustNotBeINLINEd True{-should be False? --SDM -} Nothing
336 instance Outputable InlinePragInfo where
337 -- This is now parsed in interface files
338 ppr NoInlinePragInfo = empty
339 ppr other_prag = ptext SLIT("__U") <> pprInlinePragInfo other_prag
341 pprInlinePragInfo NoInlinePragInfo = empty
342 pprInlinePragInfo (IMustNotBeINLINEd True Nothing) = empty
343 pprInlinePragInfo (IMustNotBeINLINEd True (Just n)) = brackets (int n)
344 pprInlinePragInfo (IMustNotBeINLINEd False Nothing) = brackets (char '!')
345 pprInlinePragInfo (IMustNotBeINLINEd False (Just n)) = brackets (char '!' <> int n)
347 instance Show InlinePragInfo where
348 showsPrec p prag = showsPrecSDoc p (ppr prag)
352 %************************************************************************
354 \subsection[worker-IdInfo]{Worker info about an @Id@}
356 %************************************************************************
358 If this Id has a worker then we store a reference to it. Worker
359 functions are generated by the worker/wrapper pass. This uses
360 information from the strictness and CPR analyses.
362 There might not be a worker, even for a strict function, because:
363 (a) the function might be small enough to inline, so no need
365 (b) the strictness info might be "SSS" or something, so no w/w split.
369 data WorkerInfo = NoWorker
371 -- The Arity is the arity of the *wrapper* at the moment of the
372 -- w/w split. See comments in MkIface.ifaceId, with the 'Worker' code.
374 seqWorker :: WorkerInfo -> ()
375 seqWorker (HasWorker id _) = id `seq` ()
376 seqWorker NoWorker = ()
378 ppWorkerInfo NoWorker = empty
379 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("__P") <+> ppr wk_id
381 noWorkerInfo = NoWorker
383 workerExists :: WorkerInfo -> Bool
384 workerExists NoWorker = False
385 workerExists (HasWorker _ _) = True
387 workerId :: WorkerInfo -> Id
388 workerId (HasWorker id _) = id
390 wrapperArity :: WorkerInfo -> Arity
391 wrapperArity (HasWorker _ a) = a
395 %************************************************************************
397 \subsection[CAF-IdInfo]{CAF-related information}
399 %************************************************************************
401 This information is used to build Static Reference Tables (see
402 simplStg/ComputeSRT.lhs).
406 = MayHaveCafRefs -- either:
407 -- (1) A function or static constructor
408 -- that refers to one or more CAFs,
409 -- (2) A real live CAF
411 | NoCafRefs -- A function or static constructor
412 -- that refers to no CAFs.
414 -- LATER: not sure how easy this is...
418 seqCaf c = c `seq` ()
420 ppCafInfo NoCafRefs = ptext SLIT("__C")
421 ppCafInfo MayHaveCafRefs = empty
425 %************************************************************************
427 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
429 %************************************************************************
431 If the @Id@ is a function then it may have CPR info. A CPR analysis
432 phase detects whether:
436 The function's return value has a product type, i.e. an algebraic type
437 with a single constructor. Examples of such types are tuples and boxed
440 The function always 'constructs' the value that it is returning. It
441 must do this on every path through, and it's OK if it calls another
442 function which constructs the result.
445 If this is the case then we store a template which tells us the
446 function has the CPR property and which components of the result are
452 | ReturnsCPR -- Yes, this function returns a constructed product
453 -- Implicitly, this means "after the function has been applied
454 -- to all its arguments", so the worker/wrapper builder in
455 -- WwLib.mkWWcpr checks that that it is indeed saturated before
456 -- making use of the CPR info
458 -- We used to keep nested info about sub-components, but
459 -- we never used it so I threw it away
463 seqCpr :: CprInfo -> ()
464 seqCpr ReturnsCPR = ()
465 seqCpr NoCPRInfo = ()
467 noCprInfo = NoCPRInfo
469 ppCprInfo NoCPRInfo = empty
470 ppCprInfo ReturnsCPR = ptext SLIT("__M")
472 instance Outputable CprInfo where
475 instance Show CprInfo where
476 showsPrec p c = showsPrecSDoc p (ppr c)
480 %************************************************************************
482 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
484 %************************************************************************
486 If the @Id@ is a lambda-bound variable then it may have lambda-bound
487 var info. The usage analysis (UsageSP) detects whether the lambda
488 binding this var is a ``one-shot'' lambda; that is, whether it is
489 applied at most once.
491 This information may be useful in optimisation, as computations may
492 safely be floated inside such a lambda without risk of duplicating
499 | IsOneShotLambda -- The lambda that binds this Id is applied
501 -- HACK ALERT! placing this info here is a short-term hack,
502 -- but it minimises changes to the rest of the compiler.
503 -- Hack agreed by SLPJ/KSW 1999-04.
505 seqLBVar l = l `seq` ()
509 noLBVarInfo = NoLBVarInfo
511 -- not safe to print or parse LBVarInfo because it is not really a
512 -- property of the definition, but a property of the context.
513 pprLBVarInfo NoLBVarInfo = empty
514 pprLBVarInfo IsOneShotLambda = getPprStyle $ \ sty ->
515 if ifaceStyle sty then empty
516 else ptext SLIT("OneShot")
518 instance Outputable LBVarInfo where
521 instance Show LBVarInfo where
522 showsPrec p c = showsPrecSDoc p (ppr c)
526 %************************************************************************
528 \subsection{Bulk operations on IdInfo}
530 %************************************************************************
532 zapFragileInfo is used when cloning binders, mainly in the
533 simplifier. We must forget about used-once information because that
534 isn't necessarily correct in the transformed program.
535 Also forget specialisations and unfoldings because they would need
536 substitution to be correct. (They get pinned back on separately.)
539 zapFragileInfo :: IdInfo -> Maybe IdInfo
540 zapFragileInfo info@(IdInfo {occInfo = occ,
543 unfoldingInfo = unfolding})
544 | not (isFragileOcc occ)
545 -- We must forget about whether it was marked safe-to-inline,
546 -- because that isn't necessarily true in the simplified expression.
547 -- This is important because expressions may be re-simplified
548 -- We don't zap deadness or loop-breaker-ness.
549 -- The latter is important because it tells MkIface not to
550 -- spit out an inlining for the thing. The former doesn't
551 -- seem so important, but there's no harm.
553 && isEmptyCoreRules rules
554 -- Specialisations would need substituting. They get pinned
555 -- back on separately.
557 && not (workerExists wrkr)
559 && not (hasUnfolding unfolding)
560 -- This is very important; occasionally a let-bound binder is used
561 -- as a binder in some lambda, in which case its unfolding is utterly
562 -- bogus. Also the unfolding uses old binders so if we left it we'd
563 -- have to substitute it. Much better simply to give the Id a new
564 -- unfolding each time, which is what the simplifier does.
568 = Just (info {occInfo = robust_occ_info,
569 workerInfo = noWorkerInfo,
570 specInfo = emptyCoreRules,
571 unfoldingInfo = noUnfolding})
573 -- It's important to keep the loop-breaker info,
574 -- because the substitution doesn't remember it.
575 robust_occ_info = case occ of
576 OneOcc _ _ -> NoOccInfo
580 @zapLamInfo@ is used for lambda binders that turn out to to be
581 part of an unsaturated lambda
584 zapLamInfo :: IdInfo -> Maybe IdInfo
585 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
586 | is_safe_occ && not (isStrict demand)
589 = Just (info {occInfo = safe_occ,
590 demandInfo = wwLazy})
592 -- The "unsafe" occ info is the ones that say I'm not in a lambda
593 -- because that might not be true for an unsaturated lambda
594 is_safe_occ = case occ of
595 OneOcc in_lam once -> in_lam
598 safe_occ = case occ of
599 OneOcc _ once -> OneOcc insideLam once
604 copyIdInfo is used when shorting out a top-level binding
607 where f is exported. We are going to swizzle it around to
611 BUT (a) we must be careful about messing up rules
612 (b) we must ensure f's IdInfo ends up right
614 (a) Messing up the rules
616 The example that went bad on me was this one:
618 iterate :: (a -> a) -> a -> [a]
619 iterate = iterateList
621 iterateFB c f x = x `c` iterateFB c f (f x)
622 iterateList f x = x : iterateList f (f x)
625 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
626 "iterateFB" iterateFB (:) = iterateList
629 This got shorted out to:
631 iterateList :: (a -> a) -> a -> [a]
632 iterateList = iterate
634 iterateFB c f x = x `c` iterateFB c f (f x)
635 iterate f x = x : iterate f (f x)
638 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
639 "iterateFB" iterateFB (:) = iterate
642 And now we get an infinite loop in the rule system
643 iterate f x -> build (\cn -> iterateFB c f x
647 Tiresome solution: don't do shorting out if f has rewrite rules.
648 Hence shortableIdInfo.
650 (b) Keeping the IdInfo right
651 ~~~~~~~~~~~~~~~~~~~~~~~~
652 We want to move strictness/worker info from f_local to f, but keep the rest.
656 shortableIdInfo :: IdInfo -> Bool
657 shortableIdInfo info = isEmptyCoreRules (specInfo info)
659 copyIdInfo :: IdInfo -- f_local
660 -> IdInfo -- f (the exported one)
661 -> IdInfo -- New info for f
662 copyIdInfo f_local f = f { strictnessInfo = strictnessInfo f_local,
663 workerInfo = workerInfo f_local,
664 cprInfo = cprInfo f_local