2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
5 \section[IdInfo]{@IdInfos@: Non-essential information about @Ids@}
7 (And a pretty good illustration of quite a few things wrong with
12 GlobalIdDetails(..), notGlobalId, -- Not abstract
15 vanillaIdInfo, noCafIdInfo,
16 seqIdInfo, megaSeqIdInfo,
19 zapLamInfo, zapDemandInfo, zapFragileInfo,
24 arityInfo, setArityInfo, ppArityInfo,
26 -- New demand and strictness info
27 newStrictnessInfo, setNewStrictnessInfo,
28 newDemandInfo, setNewDemandInfo, pprNewStrictness,
32 -- Strictness; imported from Demand
34 mkStrictnessInfo, noStrictnessInfo,
35 ppStrictnessInfo,isBottomingStrictness,
39 WorkerInfo(..), workerExists, wrapperArity, workerId,
40 workerInfo, setWorkerInfo, ppWorkerInfo,
43 unfoldingInfo, setUnfoldingInfo, setUnfoldingInfoLazily,
46 -- Old DemandInfo and StrictnessInfo
47 demandInfo, setDemandInfo,
48 strictnessInfo, setStrictnessInfo,
49 cprInfoFromNewStrictness,
50 oldStrictnessFromNew, newStrictnessFromOld,
53 -- Constructed Product Result Info
54 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
59 inlinePragInfo, setInlinePragInfo,
62 OccInfo(..), isFragileOcc, isDeadOcc, isLoopBreaker,
63 InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
67 SpecInfo(..), specInfo, setSpecInfo, isEmptySpecInfo,
68 specInfoFreeVars, specInfoRules, seqSpecInfo,
71 CafInfo(..), cafInfo, ppCafInfo, setCafInfo, mayHaveCafRefs,
73 -- Lambda-bound variable info
74 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo, hasNoLBVarInfo,
77 TickBoxOp(..), TickBoxId,
80 #include "HsVersions.h"
100 import qualified Demand
105 -- infixl so you can say (id `set` a `set` b)
106 infixl 1 `setSpecInfo`,
114 `setNewStrictnessInfo`,
115 `setAllStrictnessInfo`,
117 #ifdef OLD_STRICTNESS
120 , `setStrictnessInfo`
124 %************************************************************************
126 \subsection{New strictness info}
128 %************************************************************************
133 -- setAllStrictnessInfo :: IdInfo -> Maybe StrictSig -> IdInfo
134 -- Set old and new strictness info
135 setAllStrictnessInfo info Nothing
136 = info { newStrictnessInfo = Nothing
137 #ifdef OLD_STRICTNESS
138 , strictnessInfo = NoStrictnessInfo
139 , cprInfo = NoCPRInfo
143 setAllStrictnessInfo info (Just sig)
144 = info { newStrictnessInfo = Just sig
145 #ifdef OLD_STRICTNESS
146 , strictnessInfo = oldStrictnessFromNew sig
147 , cprInfo = cprInfoFromNewStrictness sig
151 seqNewStrictnessInfo Nothing = ()
152 seqNewStrictnessInfo (Just ty) = seqStrictSig ty
154 pprNewStrictness Nothing = empty
155 pprNewStrictness (Just sig) = ftext FSLIT("Str:") <+> ppr sig
157 #ifdef OLD_STRICTNESS
158 oldStrictnessFromNew :: StrictSig -> Demand.StrictnessInfo
159 oldStrictnessFromNew sig = mkStrictnessInfo (map oldDemand dmds, isBotRes res_info)
161 (dmds, res_info) = splitStrictSig sig
163 cprInfoFromNewStrictness :: StrictSig -> CprInfo
164 cprInfoFromNewStrictness sig = case strictSigResInfo sig of
168 newStrictnessFromOld :: Name -> Arity -> Demand.StrictnessInfo -> CprInfo -> StrictSig
169 newStrictnessFromOld name arity (Demand.StrictnessInfo ds res) cpr
170 | listLengthCmp ds arity /= GT -- length ds <= arity
171 -- Sometimes the old strictness analyser has more
172 -- demands than the arity justifies
173 = mk_strict_sig name arity $
174 mkTopDmdType (map newDemand ds) (newRes res cpr)
176 newStrictnessFromOld name arity other cpr
177 = -- Either no strictness info, or arity is too small
178 -- In either case we can't say anything useful
179 mk_strict_sig name arity $
180 mkTopDmdType (replicate arity lazyDmd) (newRes False cpr)
182 mk_strict_sig name arity dmd_ty
183 = WARN( arity /= dmdTypeDepth dmd_ty, ppr name <+> (ppr arity $$ ppr dmd_ty) )
186 newRes True _ = BotRes
187 newRes False ReturnsCPR = retCPR
188 newRes False NoCPRInfo = TopRes
190 newDemand :: Demand.Demand -> NewDemand.Demand
191 newDemand (WwLazy True) = Abs
192 newDemand (WwLazy False) = lazyDmd
193 newDemand WwStrict = evalDmd
194 newDemand (WwUnpack unpk ds) = Eval (Prod (map newDemand ds))
195 newDemand WwPrim = lazyDmd
196 newDemand WwEnum = evalDmd
198 oldDemand :: NewDemand.Demand -> Demand.Demand
199 oldDemand Abs = WwLazy True
200 oldDemand Top = WwLazy False
201 oldDemand Bot = WwStrict
202 oldDemand (Box Bot) = WwStrict
203 oldDemand (Box Abs) = WwLazy False
204 oldDemand (Box (Eval _)) = WwStrict -- Pass box only
205 oldDemand (Defer d) = WwLazy False
206 oldDemand (Eval (Prod ds)) = WwUnpack True (map oldDemand ds)
207 oldDemand (Eval (Poly _)) = WwStrict
208 oldDemand (Call _) = WwStrict
210 #endif /* OLD_STRICTNESS */
215 seqNewDemandInfo Nothing = ()
216 seqNewDemandInfo (Just dmd) = seqDemand dmd
220 %************************************************************************
222 \subsection{GlobalIdDetails}
224 %************************************************************************
226 This type is here (rather than in Id.lhs) mainly because there's
227 an IdInfo.hi-boot, but no Id.hi-boot, and GlobalIdDetails is imported
228 (recursively) by Var.lhs.
232 = VanillaGlobal -- Imported from elsewhere, a default method Id.
234 | RecordSelId -- The Id for a record selector
235 { sel_tycon :: TyCon -- For a data type family, this is the *instance* TyCon
236 -- not the family TyCon
237 , sel_label :: FieldLabel
238 , sel_naughty :: Bool -- True <=> naughty
239 } -- See Note [Naughty record selectors]
240 -- with MkId.mkRecordSelectorId
242 | DataConWorkId DataCon -- The Id for a data constructor *worker*
243 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
244 -- [the only reasons we need to know is so that
245 -- a) to support isImplicitId
246 -- b) when desugaring a RecordCon we can get
247 -- from the Id back to the data con]
249 | ClassOpId Class -- An operation of a class
251 | PrimOpId PrimOp -- The Id for a primitive operator
252 | FCallId ForeignCall -- The Id for a foreign call
254 | TickBoxOpId TickBoxOp -- The Id for a tick box (both traditional and binary)
256 | NotGlobalId -- Used as a convenient extra return value from globalIdDetails
258 notGlobalId = NotGlobalId
260 instance Outputable GlobalIdDetails where
261 ppr NotGlobalId = ptext SLIT("[***NotGlobalId***]")
262 ppr VanillaGlobal = ptext SLIT("[GlobalId]")
263 ppr (DataConWorkId _) = ptext SLIT("[DataCon]")
264 ppr (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
265 ppr (ClassOpId _) = ptext SLIT("[ClassOp]")
266 ppr (PrimOpId _) = ptext SLIT("[PrimOp]")
267 ppr (FCallId _) = ptext SLIT("[ForeignCall]")
268 ppr (TickBoxOpId _) = ptext SLIT("[TickBoxOp]")
269 ppr (RecordSelId {}) = ptext SLIT("[RecSel]")
273 %************************************************************************
275 \subsection{The main IdInfo type}
277 %************************************************************************
279 An @IdInfo@ gives {\em optional} information about an @Id@. If
280 present it never lies, but it may not be present, in which case there
281 is always a conservative assumption which can be made.
283 Two @Id@s may have different info even though they have the same
284 @Unique@ (and are hence the same @Id@); for example, one might lack
285 the properties attached to the other.
287 The @IdInfo@ gives information about the value, or definition, of the
288 @Id@. It does {\em not} contain information about the @Id@'s usage
289 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
295 arityInfo :: !ArityInfo, -- Its arity
296 specInfo :: SpecInfo, -- Specialisations of this function which exist
297 #ifdef OLD_STRICTNESS
298 cprInfo :: CprInfo, -- Function always constructs a product result
299 demandInfo :: Demand.Demand, -- Whether or not it is definitely demanded
300 strictnessInfo :: StrictnessInfo, -- Strictness properties
302 workerInfo :: WorkerInfo, -- Pointer to Worker Function
303 -- Within one module this is irrelevant; the
304 -- inlining of a worker is handled via the Unfolding
305 -- WorkerInfo is used *only* to indicate the form of
306 -- the RHS, so that interface files don't actually
307 -- need to contain the RHS; it can be derived from
308 -- the strictness info
310 unfoldingInfo :: Unfolding, -- Its unfolding
311 cafInfo :: CafInfo, -- CAF info
312 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
313 inlinePragInfo :: InlinePragInfo, -- Inline pragma
314 occInfo :: OccInfo, -- How it occurs
316 newStrictnessInfo :: Maybe StrictSig, -- Reason for Maybe: the DmdAnal phase needs to
317 -- know whether whether this is the first visit,
318 -- so it can assign botSig. Other customers want
319 -- topSig. So Nothing is good.
321 newDemandInfo :: Maybe Demand -- Similarly we want to know if there's no
322 -- known demand yet, for when we are looking for
326 seqIdInfo :: IdInfo -> ()
327 seqIdInfo (IdInfo {}) = ()
329 megaSeqIdInfo :: IdInfo -> ()
331 = seqSpecInfo (specInfo info) `seq`
332 seqWorker (workerInfo info) `seq`
334 -- Omitting this improves runtimes a little, presumably because
335 -- some unfoldings are not calculated at all
336 -- seqUnfolding (unfoldingInfo info) `seq`
338 seqNewDemandInfo (newDemandInfo info) `seq`
339 seqNewStrictnessInfo (newStrictnessInfo info) `seq`
341 #ifdef OLD_STRICTNESS
342 Demand.seqDemand (demandInfo info) `seq`
343 seqStrictnessInfo (strictnessInfo info) `seq`
344 seqCpr (cprInfo info) `seq`
347 seqCaf (cafInfo info) `seq`
348 seqLBVar (lbvarInfo info) `seq`
349 seqOccInfo (occInfo info)
355 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
356 setSpecInfo info sp = sp `seq` info { specInfo = sp }
357 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
358 setOccInfo info oc = oc `seq` info { occInfo = oc }
359 #ifdef OLD_STRICTNESS
360 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
362 -- Try to avoid spack leaks by seq'ing
364 setUnfoldingInfoLazily info uf -- Lazy variant to avoid looking at the
365 = -- unfolding of an imported Id unless necessary
366 info { unfoldingInfo = uf } -- (In this case the demand-zapping is redundant.)
368 setUnfoldingInfo info uf
369 -- We do *not* seq on the unfolding info, For some reason, doing so
370 -- actually increases residency significantly.
371 = info { unfoldingInfo = uf }
373 #ifdef OLD_STRICTNESS
374 setDemandInfo info dd = info { demandInfo = dd }
375 setCprInfo info cp = info { cprInfo = cp }
378 setArityInfo info ar = info { arityInfo = ar }
379 setCafInfo info caf = info { cafInfo = caf }
381 setLBVarInfo info lb = {-lb `seq`-} info { lbvarInfo = lb }
383 setNewDemandInfo info dd = dd `seq` info { newDemandInfo = dd }
384 setNewStrictnessInfo info dd = dd `seq` info { newStrictnessInfo = dd }
389 vanillaIdInfo :: IdInfo
392 cafInfo = vanillaCafInfo,
393 arityInfo = unknownArity,
394 #ifdef OLD_STRICTNESS
397 strictnessInfo = NoStrictnessInfo,
399 specInfo = emptySpecInfo,
400 workerInfo = NoWorker,
401 unfoldingInfo = noUnfolding,
402 lbvarInfo = NoLBVarInfo,
403 inlinePragInfo = AlwaysActive,
405 newDemandInfo = Nothing,
406 newStrictnessInfo = Nothing
409 noCafIdInfo = vanillaIdInfo `setCafInfo` NoCafRefs
410 -- Used for built-in type Ids in MkId.
414 %************************************************************************
416 \subsection[arity-IdInfo]{Arity info about an @Id@}
418 %************************************************************************
420 For locally-defined Ids, the code generator maintains its own notion
421 of their arities; so it should not be asking... (but other things
422 besides the code-generator need arity info!)
425 type ArityInfo = Arity
426 -- A partial application of this Id to up to n-1 value arguments
427 -- does essentially no work. That is not necessarily the
428 -- same as saying that it has n leading lambdas, because coerces
429 -- may get in the way.
431 -- The arity might increase later in the compilation process, if
432 -- an extra lambda floats up to the binding site.
434 unknownArity = 0 :: Arity
436 ppArityInfo 0 = empty
437 ppArityInfo n = hsep [ptext SLIT("Arity"), int n]
440 %************************************************************************
442 \subsection{Inline-pragma information}
444 %************************************************************************
447 type InlinePragInfo = Activation
448 -- Tells when the inlining is active
449 -- When it is active the thing may be inlined, depending on how
452 -- If there was an INLINE pragma, then as a separate matter, the
453 -- RHS will have been made to look small with a CoreSyn Inline Note
455 -- The default InlinePragInfo is AlwaysActive, so the info serves
456 -- entirely as a way to inhibit inlining until we want it
460 %************************************************************************
464 %************************************************************************
470 VarSet -- Locally-defined free vars of *both* LHS and RHS of rules
471 -- Note [Rule dependency info]
473 emptySpecInfo :: SpecInfo
474 emptySpecInfo = SpecInfo [] emptyVarSet
476 isEmptySpecInfo :: SpecInfo -> Bool
477 isEmptySpecInfo (SpecInfo rs _) = null rs
479 specInfoFreeVars :: SpecInfo -> VarSet
480 specInfoFreeVars (SpecInfo _ fvs) = fvs
482 specInfoRules :: SpecInfo -> [CoreRule]
483 specInfoRules (SpecInfo rules _) = rules
485 seqSpecInfo (SpecInfo rules fvs) = seqRules rules `seq` seqVarSet fvs
488 Note [Rule dependency info]
489 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
490 THe VarSet in a SpecInfo is used for dependency analysis in the
491 occurrence analyser. We must track free vars in *both* lhs and rhs. Why both?
495 Then if we substitute y for x, we'd better do so in the
496 rule's LHS too, so we'd better ensure the dependency is respsected
500 %************************************************************************
502 \subsection[worker-IdInfo]{Worker info about an @Id@}
504 %************************************************************************
506 If this Id has a worker then we store a reference to it. Worker
507 functions are generated by the worker/wrapper pass. This uses
508 information from strictness analysis.
510 There might not be a worker, even for a strict function, because:
511 (a) the function might be small enough to inline, so no need
513 (b) the strictness info might be "SSS" or something, so no w/w split.
515 Sometimes the arity of a wrapper changes from the original arity from
516 which it was generated, so we always emit the "original" arity into
517 the interface file, as part of the worker info.
519 How can this happen? Sometimes we get
520 f = coerce t (\x y -> $wf x y)
521 at the moment of w/w split; but the eta reducer turns it into
523 which is perfectly fine except that the exposed arity so far as
524 the code generator is concerned (zero) differs from the arity
525 when we did the split (2).
527 All this arises because we use 'arity' to mean "exactly how many
528 top level lambdas are there" in interface files; but during the
529 compilation of this module it means "how many things can I apply
534 data WorkerInfo = NoWorker
536 -- The Arity is the arity of the *wrapper* at the moment of the
537 -- w/w split. See notes above.
539 seqWorker :: WorkerInfo -> ()
540 seqWorker (HasWorker id a) = id `seq` a `seq` ()
541 seqWorker NoWorker = ()
543 ppWorkerInfo NoWorker = empty
544 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("Worker") <+> ppr wk_id
546 workerExists :: WorkerInfo -> Bool
547 workerExists NoWorker = False
548 workerExists (HasWorker _ _) = True
550 workerId :: WorkerInfo -> Id
551 workerId (HasWorker id _) = id
553 wrapperArity :: WorkerInfo -> Arity
554 wrapperArity (HasWorker _ a) = a
558 %************************************************************************
560 \subsection[CG-IdInfo]{Code generator-related information}
562 %************************************************************************
565 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.lhs).
568 = MayHaveCafRefs -- either:
569 -- (1) A function or static constructor
570 -- that refers to one or more CAFs,
571 -- (2) A real live CAF
573 | NoCafRefs -- A function or static constructor
574 -- that refers to no CAFs.
576 vanillaCafInfo = MayHaveCafRefs -- Definitely safe
578 mayHaveCafRefs MayHaveCafRefs = True
579 mayHaveCafRefs _ = False
581 seqCaf c = c `seq` ()
583 ppCafInfo NoCafRefs = ptext SLIT("NoCafRefs")
584 ppCafInfo MayHaveCafRefs = empty
587 %************************************************************************
589 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
591 %************************************************************************
593 If the @Id@ is a function then it may have CPR info. A CPR analysis
594 phase detects whether:
598 The function's return value has a product type, i.e. an algebraic type
599 with a single constructor. Examples of such types are tuples and boxed
602 The function always 'constructs' the value that it is returning. It
603 must do this on every path through, and it's OK if it calls another
604 function which constructs the result.
607 If this is the case then we store a template which tells us the
608 function has the CPR property and which components of the result are
612 #ifdef OLD_STRICTNESS
615 | ReturnsCPR -- Yes, this function returns a constructed product
616 -- Implicitly, this means "after the function has been applied
617 -- to all its arguments", so the worker/wrapper builder in
618 -- WwLib.mkWWcpr checks that that it is indeed saturated before
619 -- making use of the CPR info
621 -- We used to keep nested info about sub-components, but
622 -- we never used it so I threw it away
624 seqCpr :: CprInfo -> ()
625 seqCpr ReturnsCPR = ()
626 seqCpr NoCPRInfo = ()
628 noCprInfo = NoCPRInfo
630 ppCprInfo NoCPRInfo = empty
631 ppCprInfo ReturnsCPR = ptext SLIT("__M")
633 instance Outputable CprInfo where
636 instance Show CprInfo where
637 showsPrec p c = showsPrecSDoc p (ppr c)
642 %************************************************************************
644 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
646 %************************************************************************
648 If the @Id@ is a lambda-bound variable then it may have lambda-bound
649 var info. Sometimes we know whether the lambda binding this var is a
650 ``one-shot'' lambda; that is, whether it is applied at most once.
652 This information may be useful in optimisation, as computations may
653 safely be floated inside such a lambda without risk of duplicating
657 data LBVarInfo = NoLBVarInfo
658 | IsOneShotLambda -- The lambda is applied at most once).
660 seqLBVar l = l `seq` ()
664 hasNoLBVarInfo NoLBVarInfo = True
665 hasNoLBVarInfo IsOneShotLambda = False
667 noLBVarInfo = NoLBVarInfo
669 pprLBVarInfo NoLBVarInfo = empty
670 pprLBVarInfo IsOneShotLambda = 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 _ _) = in_lam
700 is_safe_occ other = True
702 safe_occ = case occ of
703 OneOcc _ once int_cxt -> OneOcc insideLam once int_cxt
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 zapFragileInfo :: IdInfo -> Maybe IdInfo
719 -- Zap info that depends on free variables
720 zapFragileInfo info = Just (info `setSpecInfo` emptySpecInfo
721 `setWorkerInfo` NoWorker
722 `setUnfoldingInfo` NoUnfolding)
725 %************************************************************************
727 \subsection{TickBoxOp}
729 %************************************************************************
735 = TickBox Module {-# UNPACK #-} !TickBoxId
736 -- ^Tick box for Hpc-style coverage
738 instance Outputable TickBoxOp where
739 ppr (TickBox mod n) = ptext SLIT("tick") <+> ppr (mod,n)