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,
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,
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, usMany )
98 import Demand hiding( Demand, seqDemand )
99 import qualified Demand
102 import Util ( seqList, listLengthCmp )
103 import Maybe ( isJust )
104 import List ( replicate )
106 -- infixl so you can say (id `set` a `set` b)
107 infixl 1 `setSpecInfo`,
116 `setNewStrictnessInfo`,
117 `setAllStrictnessInfo`,
119 #ifdef OLD_STRICTNESS
122 , `setStrictnessInfo`
126 %************************************************************************
128 \subsection{New strictness info}
130 %************************************************************************
135 -- setAllStrictnessInfo :: IdInfo -> Maybe StrictSig -> IdInfo
136 -- Set old and new strictness info
137 setAllStrictnessInfo info Nothing
138 = info { newStrictnessInfo = Nothing
139 #ifdef OLD_STRICTNESS
140 , strictnessInfo = NoStrictnessInfo
141 , cprInfo = NoCPRInfo
145 setAllStrictnessInfo info (Just sig)
146 = info { newStrictnessInfo = Just sig
147 #ifdef OLD_STRICTNESS
148 , strictnessInfo = oldStrictnessFromNew sig
149 , cprInfo = cprInfoFromNewStrictness sig
153 seqNewStrictnessInfo Nothing = ()
154 seqNewStrictnessInfo (Just ty) = seqStrictSig ty
156 #ifdef OLD_STRICTNESS
157 oldStrictnessFromNew :: StrictSig -> Demand.StrictnessInfo
158 oldStrictnessFromNew sig = mkStrictnessInfo (map oldDemand dmds, isBotRes res_info)
160 (dmds, res_info) = splitStrictSig sig
162 cprInfoFromNewStrictness :: StrictSig -> CprInfo
163 cprInfoFromNewStrictness sig = case strictSigResInfo sig of
167 newStrictnessFromOld :: Name -> Arity -> Demand.StrictnessInfo -> CprInfo -> StrictSig
168 newStrictnessFromOld name arity (Demand.StrictnessInfo ds res) cpr
169 | listLengthCmp ds arity /= GT -- length ds <= arity
170 -- Sometimes the old strictness analyser has more
171 -- demands than the arity justifies
172 = mk_strict_sig name arity $
173 mkTopDmdType (map newDemand ds) (newRes res cpr)
175 newStrictnessFromOld name arity other cpr
176 = -- Either no strictness info, or arity is too small
177 -- In either case we can't say anything useful
178 mk_strict_sig name arity $
179 mkTopDmdType (replicate arity lazyDmd) (newRes False cpr)
181 mk_strict_sig name arity dmd_ty
182 = WARN( arity /= dmdTypeDepth dmd_ty, ppr name <+> (ppr arity $$ ppr dmd_ty) )
185 newRes True _ = BotRes
186 newRes False ReturnsCPR = retCPR
187 newRes False NoCPRInfo = TopRes
189 newDemand :: Demand.Demand -> NewDemand.Demand
190 newDemand (WwLazy True) = Abs
191 newDemand (WwLazy False) = lazyDmd
192 newDemand WwStrict = evalDmd
193 newDemand (WwUnpack unpk ds) = Eval (Prod (map newDemand ds))
194 newDemand WwPrim = lazyDmd
195 newDemand WwEnum = evalDmd
197 oldDemand :: NewDemand.Demand -> Demand.Demand
198 oldDemand Abs = WwLazy True
199 oldDemand Top = WwLazy False
200 oldDemand Bot = WwStrict
201 oldDemand (Box Bot) = WwStrict
202 oldDemand (Box Abs) = WwLazy False
203 oldDemand (Box (Eval _)) = WwStrict -- Pass box only
204 oldDemand (Defer d) = WwLazy False
205 oldDemand (Eval (Prod ds)) = WwUnpack True (map oldDemand ds)
206 oldDemand (Eval (Poly _)) = WwStrict
207 oldDemand (Call _) = WwStrict
209 #endif /* OLD_STRICTNESS */
214 seqNewDemandInfo Nothing = ()
215 seqNewDemandInfo (Just dmd) = seqDemand dmd
219 %************************************************************************
221 \subsection{GlobalIdDetails
223 %************************************************************************
225 This type is here (rather than in Id.lhs) mainly because there's
226 an IdInfo.hi-boot, but no Id.hi-boot, and GlobalIdDetails is imported
227 (recursively) by Var.lhs.
231 = VanillaGlobal -- Imported from elsewhere, a default method Id.
233 | RecordSelId FieldLabel -- The Id for a record selector
234 | DataConId DataCon -- The Id for a data constructor *worker*
235 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
236 -- [the only reasons we need to know is so that
237 -- a) we can suppress printing a definition in the interface file
238 -- b) when typechecking a pattern we can get from the
239 -- Id back to the data con]
241 | PrimOpId PrimOp -- The Id for a primitive operator
242 | FCallId ForeignCall -- The Id for a foreign call
244 | NotGlobalId -- Used as a convenient extra return value from globalIdDetails
246 notGlobalId = NotGlobalId
248 instance Outputable GlobalIdDetails where
249 ppr NotGlobalId = ptext SLIT("[***NotGlobalId***]")
250 ppr VanillaGlobal = ptext SLIT("[GlobalId]")
251 ppr (DataConId _) = ptext SLIT("[DataCon]")
252 ppr (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
253 ppr (PrimOpId _) = ptext SLIT("[PrimOp]")
254 ppr (FCallId _) = ptext SLIT("[ForeignCall]")
255 ppr (RecordSelId _) = ptext SLIT("[RecSel]")
259 %************************************************************************
261 \subsection{The main IdInfo type}
263 %************************************************************************
265 An @IdInfo@ gives {\em optional} information about an @Id@. If
266 present it never lies, but it may not be present, in which case there
267 is always a conservative assumption which can be made.
269 Two @Id@s may have different info even though they have the same
270 @Unique@ (and are hence the same @Id@); for example, one might lack
271 the properties attached to the other.
273 The @IdInfo@ gives information about the value, or definition, of the
274 @Id@. It does {\em not} contain information about the @Id@'s usage
275 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
281 arityInfo :: !ArityInfo, -- Its arity
282 specInfo :: CoreRules, -- Specialisations of this function which exist
283 #ifdef OLD_STRICTNESS
284 cprInfo :: CprInfo, -- Function always constructs a product result
285 demandInfo :: Demand.Demand, -- Whether or not it is definitely demanded
286 strictnessInfo :: StrictnessInfo, -- Strictness properties
288 workerInfo :: WorkerInfo, -- Pointer to Worker Function
289 unfoldingInfo :: Unfolding, -- Its unfolding
290 cgInfo :: CgInfo, -- Code generator info (arity, CAF info)
291 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
292 inlinePragInfo :: InlinePragInfo, -- Inline pragma
293 occInfo :: OccInfo, -- How it occurs
295 newStrictnessInfo :: Maybe StrictSig, -- Reason for Maybe: the DmdAnal phase needs to
296 -- know whether whether this is the first visit,
297 -- so it can assign botSig. Other customers want
298 -- topSig. So Nothing is good.
300 newDemandInfo :: Maybe Demand -- Similarly we want to know if there's no
301 -- known demand yet, for when we are looking for
305 seqIdInfo :: IdInfo -> ()
306 seqIdInfo (IdInfo {}) = ()
308 megaSeqIdInfo :: IdInfo -> ()
310 = seqRules (specInfo info) `seq`
311 seqWorker (workerInfo info) `seq`
313 -- Omitting this improves runtimes a little, presumably because
314 -- some unfoldings are not calculated at all
315 -- seqUnfolding (unfoldingInfo info) `seq`
317 seqNewDemandInfo (newDemandInfo info) `seq`
318 seqNewStrictnessInfo (newStrictnessInfo info) `seq`
320 #ifdef OLD_STRICTNESS
321 Demand.seqDemand (demandInfo info) `seq`
322 seqStrictnessInfo (strictnessInfo info) `seq`
323 seqCpr (cprInfo info) `seq`
326 -- CgInfo is involved in a loop, so we have to be careful not to seq it
328 -- seqCg (cgInfo info) `seq`
329 seqLBVar (lbvarInfo info) `seq`
330 seqOccInfo (occInfo info)
336 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
337 setSpecInfo info sp = sp `seq` info { specInfo = sp }
338 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
339 setOccInfo info oc = oc `seq` info { occInfo = oc }
340 #ifdef OLD_STRICTNESS
341 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
343 -- Try to avoid spack leaks by seq'ing
345 setUnfoldingInfo info uf
346 | isEvaldUnfolding uf
347 -- If the unfolding is a value, the demand info may
348 -- go pear-shaped, so we nuke it. Example:
350 -- case x of (p,q) -> h p q x
351 -- Here x is certainly demanded. But after we've nuked
352 -- the case, we'll get just
353 -- let x = (a,b) in h a b x
354 -- and now x is not demanded (I'm assuming h is lazy)
355 -- This really happens. The solution here is a bit ad hoc...
356 = info { unfoldingInfo = uf, newDemandInfo = Nothing }
359 -- We do *not* seq on the unfolding info, For some reason, doing so
360 -- actually increases residency significantly.
361 = info { unfoldingInfo = uf }
363 #ifdef OLD_STRICTNESS
364 setDemandInfo info dd = info { demandInfo = dd }
365 setCprInfo info cp = info { cprInfo = cp }
368 setArityInfo info ar = info { arityInfo = ar }
369 setCgInfo info cg = info { cgInfo = cg }
371 setLBVarInfo info lb = {-lb `seq`-} info { lbvarInfo = lb }
373 setNewDemandInfo info dd = dd `seq` info { newDemandInfo = dd }
374 setNewStrictnessInfo info dd = dd `seq` info { newStrictnessInfo = dd }
379 vanillaIdInfo :: IdInfo
383 arityInfo = unknownArity,
384 #ifdef OLD_STRICTNESS
387 strictnessInfo = NoStrictnessInfo,
389 specInfo = emptyCoreRules,
390 workerInfo = NoWorker,
391 unfoldingInfo = noUnfolding,
392 lbvarInfo = NoLBVarInfo,
393 inlinePragInfo = AlwaysActive,
395 newDemandInfo = Nothing,
396 newStrictnessInfo = Nothing
399 noCafIdInfo = vanillaIdInfo `setCgInfo` CgInfo NoCafRefs
400 -- Used for built-in type Ids in MkId.
401 -- Many built-in things have fixed types, so we shouldn't
402 -- run around generalising them
406 %************************************************************************
408 \subsection[arity-IdInfo]{Arity info about an @Id@}
410 %************************************************************************
412 For locally-defined Ids, the code generator maintains its own notion
413 of their arities; so it should not be asking... (but other things
414 besides the code-generator need arity info!)
417 type ArityInfo = Arity
418 -- A partial application of this Id to up to n-1 value arguments
419 -- does essentially no work. That is not necessarily the
420 -- same as saying that it has n leading lambdas, because coerces
421 -- may get in the way.
423 -- The arity might increase later in the compilation process, if
424 -- an extra lambda floats up to the binding site.
426 unknownArity = 0 :: Arity
428 ppArityInfo 0 = empty
429 ppArityInfo n = hsep [ptext SLIT("Arity"), int n]
432 %************************************************************************
434 \subsection{Inline-pragma information}
436 %************************************************************************
439 type InlinePragInfo = Activation
440 -- Tells when the inlining is active
441 -- When it is active the thing may be inlined, depending on how
444 -- If there was an INLINE pragma, then as a separate matter, the
445 -- RHS will have been made to look small with a CoreSyn Inline Note
449 %************************************************************************
451 \subsection[worker-IdInfo]{Worker info about an @Id@}
453 %************************************************************************
455 If this Id has a worker then we store a reference to it. Worker
456 functions are generated by the worker/wrapper pass. This uses
457 information from strictness analysis.
459 There might not be a worker, even for a strict function, because:
460 (a) the function might be small enough to inline, so no need
462 (b) the strictness info might be "SSS" or something, so no w/w split.
464 Sometimes the arity of a wrapper changes from the original arity from
465 which it was generated, so we always emit the "original" arity into
466 the interface file, as part of the worker info.
468 How can this happen? Sometimes we get
469 f = coerce t (\x y -> $wf x y)
470 at the moment of w/w split; but the eta reducer turns it into
472 which is perfectly fine except that the exposed arity so far as
473 the code generator is concerned (zero) differs from the arity
474 when we did the split (2).
476 All this arises because we use 'arity' to mean "exactly how many
477 top level lambdas are there" in interface files; but during the
478 compilation of this module it means "how many things can I apply
483 data WorkerInfo = NoWorker
485 -- The Arity is the arity of the *wrapper* at the moment of the
486 -- w/w split. See comments in MkIface.ifaceId, with the 'Worker' code.
488 seqWorker :: WorkerInfo -> ()
489 seqWorker (HasWorker id a) = id `seq` a `seq` ()
490 seqWorker NoWorker = ()
492 ppWorkerInfo NoWorker = empty
493 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("__P") <+> ppr wk_id
495 workerExists :: WorkerInfo -> Bool
496 workerExists NoWorker = False
497 workerExists (HasWorker _ _) = True
499 workerId :: WorkerInfo -> Id
500 workerId (HasWorker id _) = id
502 wrapperArity :: WorkerInfo -> Arity
503 wrapperArity (HasWorker _ a) = a
507 %************************************************************************
509 \subsection[CG-IdInfo]{Code generator-related information}
511 %************************************************************************
513 CgInfo encapsulates calling-convention information produced by the code
514 generator. It is pasted into the IdInfo of each emitted Id by CoreTidy,
515 but only as a thunk --- the information is only actually produced further
516 downstream, by the code generator.
519 #ifndef OLD_STRICTNESS
520 newtype CgInfo = CgInfo CafInfo -- We are back to only having CafRefs in CgInfo
521 noCgInfo = panic "NoCgInfo!"
523 data CgInfo = CgInfo CafInfo
524 | NoCgInfo -- In debug mode we don't want a black hole here
526 -- noCgInfo is used for local Ids, which shouldn't need any CgInfo
530 cgCafInfo (CgInfo caf_info) = caf_info
532 setCafInfo info caf_info = info `setCgInfo` CgInfo caf_info
534 seqCg c = c `seq` () -- fields are strict anyhow
536 vanillaCgInfo = CgInfo MayHaveCafRefs -- Definitely safe
538 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.lhs).
541 = MayHaveCafRefs -- either:
542 -- (1) A function or static constructor
543 -- that refers to one or more CAFs,
544 -- (2) A real live CAF
546 | NoCafRefs -- A function or static constructor
547 -- that refers to no CAFs.
549 mayHaveCafRefs MayHaveCafRefs = True
550 mayHaveCafRefs _ = False
552 seqCaf c = c `seq` ()
554 pprCgInfo (CgInfo caf_info) = ppCafInfo caf_info
557 ppArity n = hsep [ptext SLIT("__A"), int n]
559 ppCafInfo NoCafRefs = ptext SLIT("__C")
560 ppCafInfo MayHaveCafRefs = empty
564 type CgInfoEnv = NameEnv CgInfo
566 lookupCgInfo :: NameEnv CgInfo -> Name -> CgInfo
567 lookupCgInfo env n = case lookupNameEnv env n of
569 Nothing -> pprTrace "Urk! Not in CgInfo env" (ppr n) vanillaCgInfo
573 %************************************************************************
575 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
577 %************************************************************************
579 If the @Id@ is a function then it may have CPR info. A CPR analysis
580 phase detects whether:
584 The function's return value has a product type, i.e. an algebraic type
585 with a single constructor. Examples of such types are tuples and boxed
588 The function always 'constructs' the value that it is returning. It
589 must do this on every path through, and it's OK if it calls another
590 function which constructs the result.
593 If this is the case then we store a template which tells us the
594 function has the CPR property and which components of the result are
598 #ifdef OLD_STRICTNESS
601 | ReturnsCPR -- Yes, this function returns a constructed product
602 -- Implicitly, this means "after the function has been applied
603 -- to all its arguments", so the worker/wrapper builder in
604 -- WwLib.mkWWcpr checks that that it is indeed saturated before
605 -- making use of the CPR info
607 -- We used to keep nested info about sub-components, but
608 -- we never used it so I threw it away
610 seqCpr :: CprInfo -> ()
611 seqCpr ReturnsCPR = ()
612 seqCpr NoCPRInfo = ()
614 noCprInfo = NoCPRInfo
616 ppCprInfo NoCPRInfo = empty
617 ppCprInfo ReturnsCPR = ptext SLIT("__M")
619 instance Outputable CprInfo where
622 instance Show CprInfo where
623 showsPrec p c = showsPrecSDoc p (ppr c)
628 %************************************************************************
630 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
632 %************************************************************************
634 If the @Id@ is a lambda-bound variable then it may have lambda-bound
635 var info. The usage analysis (UsageSP) detects whether the lambda
636 binding this var is a ``one-shot'' lambda; that is, whether it is
637 applied at most once.
639 This information may be useful in optimisation, as computations may
640 safely be floated inside such a lambda without risk of duplicating
647 | LBVarInfo Type -- The lambda that binds this Id has this usage
648 -- annotation (i.e., if ==usOnce, then the
649 -- lambda is applied at most once).
650 -- The annotation's kind must be `$'
651 -- HACK ALERT! placing this info here is a short-term hack,
652 -- but it minimises changes to the rest of the compiler.
653 -- Hack agreed by SLPJ/KSW 1999-04.
655 seqLBVar l = l `seq` ()
659 hasNoLBVarInfo NoLBVarInfo = True
660 hasNoLBVarInfo other = False
662 noLBVarInfo = NoLBVarInfo
664 -- not safe to print or parse LBVarInfo because it is not really a
665 -- property of the definition, but a property of the context.
666 pprLBVarInfo NoLBVarInfo = empty
667 pprLBVarInfo (LBVarInfo u) | u `eqUsage` usOnce
668 = ptext SLIT("OneShot")
672 instance Outputable LBVarInfo where
675 instance Show LBVarInfo where
676 showsPrec p c = showsPrecSDoc p (ppr c)
680 %************************************************************************
682 \subsection{Bulk operations on IdInfo}
684 %************************************************************************
686 @zapLamInfo@ is used for lambda binders that turn out to to be
687 part of an unsaturated lambda
690 zapLamInfo :: IdInfo -> Maybe IdInfo
691 zapLamInfo info@(IdInfo {occInfo = occ, newDemandInfo = demand})
692 | is_safe_occ occ && is_safe_dmd demand
695 = Just (info {occInfo = safe_occ, newDemandInfo = Nothing})
697 -- The "unsafe" occ info is the ones that say I'm not in a lambda
698 -- because that might not be true for an unsaturated lambda
699 is_safe_occ (OneOcc in_lam once) = in_lam
700 is_safe_occ other = True
702 safe_occ = case occ of
703 OneOcc _ once -> OneOcc insideLam once
706 is_safe_dmd Nothing = True
707 is_safe_dmd (Just dmd) = not (isStrictDmd dmd)
711 zapDemandInfo :: IdInfo -> Maybe IdInfo
712 zapDemandInfo info@(IdInfo {newDemandInfo = dmd})
713 | isJust dmd = Just (info {newDemandInfo = Nothing})
714 | otherwise = Nothing
718 copyIdInfo is used when shorting out a top-level binding
721 where f is exported. We are going to swizzle it around to
725 BUT (a) we must be careful about messing up rules
726 (b) we must ensure f's IdInfo ends up right
728 (a) Messing up the rules
730 The example that went bad on me was this one:
732 iterate :: (a -> a) -> a -> [a]
733 iterate = iterateList
735 iterateFB c f x = x `c` iterateFB c f (f x)
736 iterateList f x = x : iterateList f (f x)
739 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
740 "iterateFB" iterateFB (:) = iterateList
743 This got shorted out to:
745 iterateList :: (a -> a) -> a -> [a]
746 iterateList = iterate
748 iterateFB c f x = x `c` iterateFB c f (f x)
749 iterate f x = x : iterate f (f x)
752 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
753 "iterateFB" iterateFB (:) = iterate
756 And now we get an infinite loop in the rule system
757 iterate f x -> build (\cn -> iterateFB c f x)
761 Tiresome solution: don't do shorting out if f has rewrite rules.
762 Hence shortableIdInfo.
764 (b) Keeping the IdInfo right
765 ~~~~~~~~~~~~~~~~~~~~~~~~
766 We want to move strictness/worker info from f_local to f, but keep the rest.
770 shortableIdInfo :: IdInfo -> Bool
771 shortableIdInfo info = isEmptyCoreRules (specInfo info)
773 copyIdInfo :: IdInfo -- f_local
774 -> IdInfo -- f (the exported one)
775 -> IdInfo -- New info for f
776 copyIdInfo f_local f = f { newStrictnessInfo = newStrictnessInfo f_local,
777 #ifdef OLD_STRICTNESS
778 strictnessInfo = strictnessInfo f_local,
779 cprInfo = cprInfo f_local,
781 workerInfo = workerInfo f_local