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
11 GlobalIdDetails(..), notGlobalId, -- Not abstract
14 vanillaIdInfo, noCafIdInfo, hasCafIdInfo,
15 seqIdInfo, megaSeqIdInfo,
18 zapLamInfo, zapDemandInfo,
19 shortableIdInfo, copyIdInfo,
24 arityInfo, setArityInfo, ppArityInfo,
26 -- New demand and strictness info
27 newStrictnessInfo, setNewStrictnessInfo,
28 newDemandInfo, setNewDemandInfo, pprNewStrictness,
30 -- Strictness; imported from Demand
32 mkStrictnessInfo, noStrictnessInfo,
33 ppStrictnessInfo,isBottomingStrictness,
37 WorkerInfo(..), workerExists, wrapperArity, workerId,
38 workerInfo, setWorkerInfo, ppWorkerInfo,
41 unfoldingInfo, setUnfoldingInfo,
44 -- Old DemandInfo and StrictnessInfo
45 demandInfo, setDemandInfo,
46 strictnessInfo, setStrictnessInfo,
47 cprInfoFromNewStrictness,
48 oldStrictnessFromNew, newStrictnessFromOld,
51 -- Constructed Product Result Info
52 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
57 inlinePragInfo, setInlinePragInfo,
60 OccInfo(..), isFragileOcc, isDeadOcc, isLoopBreaker,
61 InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
65 specInfo, setSpecInfo,
68 CgInfo(..), cgInfo, setCgInfo, pprCgInfo,
69 cgCafInfo, vanillaCgInfo,
70 CgInfoEnv, lookupCgInfo,
73 CafInfo(..), ppCafInfo, setCafInfo, mayHaveCafRefs,
75 -- Lambda-bound variable info
76 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo, hasNoLBVarInfo
79 #include "HsVersions.h"
83 import Type ( Type, usOnce, eqUsage )
84 import PrimOp ( PrimOp )
85 import NameEnv ( NameEnv, lookupNameEnv )
88 import BasicTypes ( OccInfo(..), isFragileOcc, isDeadOcc, seqOccInfo, isLoopBreaker,
89 InsideLam, insideLam, notInsideLam,
90 OneBranch, oneBranch, notOneBranch,
94 import DataCon ( DataCon )
95 import ForeignCall ( ForeignCall )
96 import FieldLabel ( FieldLabel )
97 import Type ( usOnce )
98 import Demand hiding( Demand, seqDemand )
99 import qualified Demand
102 import Maybe ( isJust )
103 #ifdef OLD_STRICTNESS
104 import Util ( listLengthCmp )
105 import List ( replicate )
108 -- infixl so you can say (id `set` a `set` b)
109 infixl 1 `setSpecInfo`,
118 `setNewStrictnessInfo`,
119 `setAllStrictnessInfo`,
121 #ifdef OLD_STRICTNESS
124 , `setStrictnessInfo`
128 %************************************************************************
130 \subsection{New strictness info}
132 %************************************************************************
137 -- setAllStrictnessInfo :: IdInfo -> Maybe StrictSig -> IdInfo
138 -- Set old and new strictness info
139 setAllStrictnessInfo info Nothing
140 = info { newStrictnessInfo = Nothing
141 #ifdef OLD_STRICTNESS
142 , strictnessInfo = NoStrictnessInfo
143 , cprInfo = NoCPRInfo
147 setAllStrictnessInfo info (Just sig)
148 = info { newStrictnessInfo = Just sig
149 #ifdef OLD_STRICTNESS
150 , strictnessInfo = oldStrictnessFromNew sig
151 , cprInfo = cprInfoFromNewStrictness sig
155 seqNewStrictnessInfo Nothing = ()
156 seqNewStrictnessInfo (Just ty) = seqStrictSig ty
158 pprNewStrictness Nothing = empty
159 pprNewStrictness (Just sig) = ftext FSLIT("Str:") <+> ppr sig
161 #ifdef OLD_STRICTNESS
162 oldStrictnessFromNew :: StrictSig -> Demand.StrictnessInfo
163 oldStrictnessFromNew sig = mkStrictnessInfo (map oldDemand dmds, isBotRes res_info)
165 (dmds, res_info) = splitStrictSig sig
167 cprInfoFromNewStrictness :: StrictSig -> CprInfo
168 cprInfoFromNewStrictness sig = case strictSigResInfo sig of
172 newStrictnessFromOld :: Name -> Arity -> Demand.StrictnessInfo -> CprInfo -> StrictSig
173 newStrictnessFromOld name arity (Demand.StrictnessInfo ds res) cpr
174 | listLengthCmp ds arity /= GT -- length ds <= arity
175 -- Sometimes the old strictness analyser has more
176 -- demands than the arity justifies
177 = mk_strict_sig name arity $
178 mkTopDmdType (map newDemand ds) (newRes res cpr)
180 newStrictnessFromOld name arity other cpr
181 = -- Either no strictness info, or arity is too small
182 -- In either case we can't say anything useful
183 mk_strict_sig name arity $
184 mkTopDmdType (replicate arity lazyDmd) (newRes False cpr)
186 mk_strict_sig name arity dmd_ty
187 = WARN( arity /= dmdTypeDepth dmd_ty, ppr name <+> (ppr arity $$ ppr dmd_ty) )
190 newRes True _ = BotRes
191 newRes False ReturnsCPR = retCPR
192 newRes False NoCPRInfo = TopRes
194 newDemand :: Demand.Demand -> NewDemand.Demand
195 newDemand (WwLazy True) = Abs
196 newDemand (WwLazy False) = lazyDmd
197 newDemand WwStrict = evalDmd
198 newDemand (WwUnpack unpk ds) = Eval (Prod (map newDemand ds))
199 newDemand WwPrim = lazyDmd
200 newDemand WwEnum = evalDmd
202 oldDemand :: NewDemand.Demand -> Demand.Demand
203 oldDemand Abs = WwLazy True
204 oldDemand Top = WwLazy False
205 oldDemand Bot = WwStrict
206 oldDemand (Box Bot) = WwStrict
207 oldDemand (Box Abs) = WwLazy False
208 oldDemand (Box (Eval _)) = WwStrict -- Pass box only
209 oldDemand (Defer d) = WwLazy False
210 oldDemand (Eval (Prod ds)) = WwUnpack True (map oldDemand ds)
211 oldDemand (Eval (Poly _)) = WwStrict
212 oldDemand (Call _) = WwStrict
214 #endif /* OLD_STRICTNESS */
219 seqNewDemandInfo Nothing = ()
220 seqNewDemandInfo (Just dmd) = seqDemand dmd
224 %************************************************************************
226 \subsection{GlobalIdDetails
228 %************************************************************************
230 This type is here (rather than in Id.lhs) mainly because there's
231 an IdInfo.hi-boot, but no Id.hi-boot, and GlobalIdDetails is imported
232 (recursively) by Var.lhs.
236 = VanillaGlobal -- Imported from elsewhere, a default method Id.
238 | RecordSelId FieldLabel -- The Id for a record selector
239 | DataConId DataCon -- The Id for a data constructor *worker*
240 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
241 -- [the only reasons we need to know is so that
242 -- a) we can suppress printing a definition in the interface file
243 -- b) when typechecking a pattern we can get from the
244 -- Id back to the data con]
246 | PrimOpId PrimOp -- The Id for a primitive operator
247 | FCallId ForeignCall -- The Id for a foreign call
249 | NotGlobalId -- Used as a convenient extra return value from globalIdDetails
251 notGlobalId = NotGlobalId
253 instance Outputable GlobalIdDetails where
254 ppr NotGlobalId = ptext SLIT("[***NotGlobalId***]")
255 ppr VanillaGlobal = ptext SLIT("[GlobalId]")
256 ppr (DataConId _) = ptext SLIT("[DataCon]")
257 ppr (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
258 ppr (PrimOpId _) = ptext SLIT("[PrimOp]")
259 ppr (FCallId _) = ptext SLIT("[ForeignCall]")
260 ppr (RecordSelId _) = ptext SLIT("[RecSel]")
264 %************************************************************************
266 \subsection{The main IdInfo type}
268 %************************************************************************
270 An @IdInfo@ gives {\em optional} information about an @Id@. If
271 present it never lies, but it may not be present, in which case there
272 is always a conservative assumption which can be made.
274 Two @Id@s may have different info even though they have the same
275 @Unique@ (and are hence the same @Id@); for example, one might lack
276 the properties attached to the other.
278 The @IdInfo@ gives information about the value, or definition, of the
279 @Id@. It does {\em not} contain information about the @Id@'s usage
280 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
286 arityInfo :: !ArityInfo, -- Its arity
287 specInfo :: CoreRules, -- Specialisations of this function which exist
288 #ifdef OLD_STRICTNESS
289 cprInfo :: CprInfo, -- Function always constructs a product result
290 demandInfo :: Demand.Demand, -- Whether or not it is definitely demanded
291 strictnessInfo :: StrictnessInfo, -- Strictness properties
293 workerInfo :: WorkerInfo, -- Pointer to Worker Function
294 unfoldingInfo :: Unfolding, -- Its unfolding
295 cgInfo :: CgInfo, -- Code generator info (arity, CAF info)
296 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
297 inlinePragInfo :: InlinePragInfo, -- Inline pragma
298 occInfo :: OccInfo, -- How it occurs
300 newStrictnessInfo :: Maybe StrictSig, -- Reason for Maybe: the DmdAnal phase needs to
301 -- know whether whether this is the first visit,
302 -- so it can assign botSig. Other customers want
303 -- topSig. So Nothing is good.
305 newDemandInfo :: Maybe Demand -- Similarly we want to know if there's no
306 -- known demand yet, for when we are looking for
310 seqIdInfo :: IdInfo -> ()
311 seqIdInfo (IdInfo {}) = ()
313 megaSeqIdInfo :: IdInfo -> ()
315 = seqRules (specInfo info) `seq`
316 seqWorker (workerInfo info) `seq`
318 -- Omitting this improves runtimes a little, presumably because
319 -- some unfoldings are not calculated at all
320 -- seqUnfolding (unfoldingInfo info) `seq`
322 seqNewDemandInfo (newDemandInfo info) `seq`
323 seqNewStrictnessInfo (newStrictnessInfo info) `seq`
325 #ifdef OLD_STRICTNESS
326 Demand.seqDemand (demandInfo info) `seq`
327 seqStrictnessInfo (strictnessInfo info) `seq`
328 seqCpr (cprInfo info) `seq`
331 -- CgInfo is involved in a loop, so we have to be careful not to seq it
333 -- seqCg (cgInfo info) `seq`
334 seqLBVar (lbvarInfo info) `seq`
335 seqOccInfo (occInfo info)
341 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
342 setSpecInfo info sp = sp `seq` info { specInfo = sp }
343 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
344 setOccInfo info oc = oc `seq` info { occInfo = oc }
345 #ifdef OLD_STRICTNESS
346 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
348 -- Try to avoid spack leaks by seq'ing
350 setUnfoldingInfo info uf
351 | isEvaldUnfolding uf
352 -- If the unfolding is a value, the demand info may
353 -- go pear-shaped, so we nuke it. Example:
355 -- case x of (p,q) -> h p q x
356 -- Here x is certainly demanded. But after we've nuked
357 -- the case, we'll get just
358 -- let x = (a,b) in h a b x
359 -- and now x is not demanded (I'm assuming h is lazy)
360 -- This really happens. The solution here is a bit ad hoc...
361 = info { unfoldingInfo = uf, newDemandInfo = Nothing }
364 -- We do *not* seq on the unfolding info, For some reason, doing so
365 -- actually increases residency significantly.
366 = info { unfoldingInfo = uf }
368 #ifdef OLD_STRICTNESS
369 setDemandInfo info dd = info { demandInfo = dd }
370 setCprInfo info cp = info { cprInfo = cp }
373 setArityInfo info ar = info { arityInfo = ar }
374 setCgInfo info cg = info { cgInfo = cg }
376 setLBVarInfo info lb = {-lb `seq`-} info { lbvarInfo = lb }
378 setNewDemandInfo info dd = dd `seq` info { newDemandInfo = dd }
379 setNewStrictnessInfo info dd = dd `seq` info { newStrictnessInfo = dd }
384 vanillaIdInfo :: IdInfo
388 arityInfo = unknownArity,
389 #ifdef OLD_STRICTNESS
392 strictnessInfo = NoStrictnessInfo,
394 specInfo = emptyCoreRules,
395 workerInfo = NoWorker,
396 unfoldingInfo = noUnfolding,
397 lbvarInfo = NoLBVarInfo,
398 inlinePragInfo = AlwaysActive,
400 newDemandInfo = Nothing,
401 newStrictnessInfo = Nothing
404 hasCafIdInfo = vanillaIdInfo `setCgInfo` CgInfo MayHaveCafRefs
405 noCafIdInfo = vanillaIdInfo `setCgInfo` CgInfo NoCafRefs
406 -- Used for built-in type Ids in MkId.
407 -- These must have a valid CgInfo set, so you can't
408 -- use vanillaIdInfo!
412 %************************************************************************
414 \subsection[arity-IdInfo]{Arity info about an @Id@}
416 %************************************************************************
418 For locally-defined Ids, the code generator maintains its own notion
419 of their arities; so it should not be asking... (but other things
420 besides the code-generator need arity info!)
423 type ArityInfo = Arity
424 -- A partial application of this Id to up to n-1 value arguments
425 -- does essentially no work. That is not necessarily the
426 -- same as saying that it has n leading lambdas, because coerces
427 -- may get in the way.
429 -- The arity might increase later in the compilation process, if
430 -- an extra lambda floats up to the binding site.
432 unknownArity = 0 :: Arity
434 ppArityInfo 0 = empty
435 ppArityInfo n = hsep [ptext SLIT("Arity"), int n]
438 %************************************************************************
440 \subsection{Inline-pragma information}
442 %************************************************************************
445 type InlinePragInfo = Activation
446 -- Tells when the inlining is active
447 -- When it is active the thing may be inlined, depending on how
450 -- If there was an INLINE pragma, then as a separate matter, the
451 -- RHS will have been made to look small with a CoreSyn Inline Note
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 strictness analysis.
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.
470 Sometimes the arity of a wrapper changes from the original arity from
471 which it was generated, so we always emit the "original" arity into
472 the interface file, as part of the worker info.
474 How can this happen? Sometimes we get
475 f = coerce t (\x y -> $wf x y)
476 at the moment of w/w split; but the eta reducer turns it into
478 which is perfectly fine except that the exposed arity so far as
479 the code generator is concerned (zero) differs from the arity
480 when we did the split (2).
482 All this arises because we use 'arity' to mean "exactly how many
483 top level lambdas are there" in interface files; but during the
484 compilation of this module it means "how many things can I apply
489 data WorkerInfo = NoWorker
491 -- The Arity is the arity of the *wrapper* at the moment of the
492 -- w/w split. See comments in MkIface.ifaceId, with the 'Worker' code.
494 seqWorker :: WorkerInfo -> ()
495 seqWorker (HasWorker id a) = id `seq` a `seq` ()
496 seqWorker NoWorker = ()
498 ppWorkerInfo NoWorker = empty
499 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("__P") <+> ppr wk_id
501 workerExists :: WorkerInfo -> Bool
502 workerExists NoWorker = False
503 workerExists (HasWorker _ _) = True
505 workerId :: WorkerInfo -> Id
506 workerId (HasWorker id _) = id
508 wrapperArity :: WorkerInfo -> Arity
509 wrapperArity (HasWorker _ a) = a
513 %************************************************************************
515 \subsection[CG-IdInfo]{Code generator-related information}
517 %************************************************************************
519 CgInfo encapsulates calling-convention information produced by the code
520 generator. It is pasted into the IdInfo of each emitted Id by CoreTidy,
521 but only as a thunk --- the information is only actually produced further
522 downstream, by the code generator.
525 #ifndef OLD_STRICTNESS
526 newtype CgInfo = CgInfo CafInfo -- We are back to only having CafRefs in CgInfo
527 noCgInfo = panic "NoCgInfo!"
529 data CgInfo = CgInfo CafInfo
530 | NoCgInfo -- In debug mode we don't want a black hole here
532 -- noCgInfo is used for local Ids, which shouldn't need any CgInfo
536 cgCafInfo (CgInfo caf_info) = caf_info
538 setCafInfo info caf_info = info `setCgInfo` CgInfo caf_info
540 seqCg c = c `seq` () -- fields are strict anyhow
542 vanillaCgInfo = CgInfo MayHaveCafRefs -- Definitely safe
544 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.lhs).
547 = MayHaveCafRefs -- either:
548 -- (1) A function or static constructor
549 -- that refers to one or more CAFs,
550 -- (2) A real live CAF
552 | NoCafRefs -- A function or static constructor
553 -- that refers to no CAFs.
555 mayHaveCafRefs MayHaveCafRefs = True
556 mayHaveCafRefs _ = False
558 seqCaf c = c `seq` ()
560 pprCgInfo (CgInfo caf_info) = ppCafInfo caf_info
563 ppArity n = hsep [ptext SLIT("__A"), int n]
565 ppCafInfo NoCafRefs = ptext SLIT("__C")
566 ppCafInfo MayHaveCafRefs = empty
570 type CgInfoEnv = NameEnv CgInfo
572 lookupCgInfo :: NameEnv CgInfo -> Name -> CgInfo
573 lookupCgInfo env n = case lookupNameEnv env n of
575 Nothing -> pprTrace "Urk! Not in CgInfo env" (ppr n) vanillaCgInfo
579 %************************************************************************
581 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
583 %************************************************************************
585 If the @Id@ is a function then it may have CPR info. A CPR analysis
586 phase detects whether:
590 The function's return value has a product type, i.e. an algebraic type
591 with a single constructor. Examples of such types are tuples and boxed
594 The function always 'constructs' the value that it is returning. It
595 must do this on every path through, and it's OK if it calls another
596 function which constructs the result.
599 If this is the case then we store a template which tells us the
600 function has the CPR property and which components of the result are
604 #ifdef OLD_STRICTNESS
607 | ReturnsCPR -- Yes, this function returns a constructed product
608 -- Implicitly, this means "after the function has been applied
609 -- to all its arguments", so the worker/wrapper builder in
610 -- WwLib.mkWWcpr checks that that it is indeed saturated before
611 -- making use of the CPR info
613 -- We used to keep nested info about sub-components, but
614 -- we never used it so I threw it away
616 seqCpr :: CprInfo -> ()
617 seqCpr ReturnsCPR = ()
618 seqCpr NoCPRInfo = ()
620 noCprInfo = NoCPRInfo
622 ppCprInfo NoCPRInfo = empty
623 ppCprInfo ReturnsCPR = ptext SLIT("__M")
625 instance Outputable CprInfo where
628 instance Show CprInfo where
629 showsPrec p c = showsPrecSDoc p (ppr c)
634 %************************************************************************
636 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
638 %************************************************************************
640 If the @Id@ is a lambda-bound variable then it may have lambda-bound
641 var info. The usage analysis (UsageSP) detects whether the lambda
642 binding this var is a ``one-shot'' lambda; that is, whether it is
643 applied at most once.
645 This information may be useful in optimisation, as computations may
646 safely be floated inside such a lambda without risk of duplicating
653 | LBVarInfo Type -- The lambda that binds this Id has this usage
654 -- annotation (i.e., if ==usOnce, then the
655 -- lambda is applied at most once).
656 -- The annotation's kind must be `$'
657 -- HACK ALERT! placing this info here is a short-term hack,
658 -- but it minimises changes to the rest of the compiler.
659 -- Hack agreed by SLPJ/KSW 1999-04.
661 seqLBVar l = l `seq` ()
665 hasNoLBVarInfo NoLBVarInfo = True
666 hasNoLBVarInfo other = False
668 noLBVarInfo = NoLBVarInfo
670 -- not safe to print or parse LBVarInfo because it is not really a
671 -- property of the definition, but a property of the context.
672 pprLBVarInfo NoLBVarInfo = empty
673 pprLBVarInfo (LBVarInfo u) | u `eqUsage` usOnce
674 = ptext SLIT("OneShot")
678 instance Outputable LBVarInfo where
681 instance Show LBVarInfo where
682 showsPrec p c = showsPrecSDoc p (ppr c)
686 %************************************************************************
688 \subsection{Bulk operations on IdInfo}
690 %************************************************************************
692 @zapLamInfo@ is used for lambda binders that turn out to to be
693 part of an unsaturated lambda
696 zapLamInfo :: IdInfo -> Maybe IdInfo
697 zapLamInfo info@(IdInfo {occInfo = occ, newDemandInfo = demand})
698 | is_safe_occ occ && is_safe_dmd demand
701 = Just (info {occInfo = safe_occ, newDemandInfo = Nothing})
703 -- The "unsafe" occ info is the ones that say I'm not in a lambda
704 -- because that might not be true for an unsaturated lambda
705 is_safe_occ (OneOcc in_lam once) = in_lam
706 is_safe_occ other = True
708 safe_occ = case occ of
709 OneOcc _ once -> OneOcc insideLam once
712 is_safe_dmd Nothing = True
713 is_safe_dmd (Just dmd) = not (isStrictDmd dmd)
717 zapDemandInfo :: IdInfo -> Maybe IdInfo
718 zapDemandInfo info@(IdInfo {newDemandInfo = dmd})
719 | isJust dmd = Just (info {newDemandInfo = Nothing})
720 | otherwise = Nothing
724 copyIdInfo is used when shorting out a top-level binding
727 where f is exported. We are going to swizzle it around to
731 BUT (a) we must be careful about messing up rules
732 (b) we must ensure f's IdInfo ends up right
734 (a) Messing up the rules
736 The example that went bad on me was this one:
738 iterate :: (a -> a) -> a -> [a]
739 iterate = iterateList
741 iterateFB c f x = x `c` iterateFB c f (f x)
742 iterateList f x = x : iterateList f (f x)
745 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
746 "iterateFB" iterateFB (:) = iterateList
749 This got shorted out to:
751 iterateList :: (a -> a) -> a -> [a]
752 iterateList = iterate
754 iterateFB c f x = x `c` iterateFB c f (f x)
755 iterate f x = x : iterate f (f x)
758 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
759 "iterateFB" iterateFB (:) = iterate
762 And now we get an infinite loop in the rule system
763 iterate f x -> build (\cn -> iterateFB c f x)
767 Tiresome solution: don't do shorting out if f has rewrite rules.
768 Hence shortableIdInfo.
770 (b) Keeping the IdInfo right
771 ~~~~~~~~~~~~~~~~~~~~~~~~
772 We want to move strictness/worker info from f_local to f, but keep the rest.
776 shortableIdInfo :: IdInfo -> Bool
777 shortableIdInfo info = isEmptyCoreRules (specInfo info)
779 copyIdInfo :: IdInfo -- f_local
780 -> IdInfo -- f (the exported one)
781 -> IdInfo -- New info for f
782 copyIdInfo f_local f = f { newStrictnessInfo = newStrictnessInfo f_local,
783 #ifdef OLD_STRICTNESS
784 strictnessInfo = strictnessInfo f_local,
785 cprInfo = cprInfo f_local,
787 workerInfo = workerInfo f_local