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 -- The above warning supression flag is a temporary kludge.
13 -- While working on this module you are encouraged to remove it and fix
14 -- any warnings in the module. See
15 -- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
19 GlobalIdDetails(..), notGlobalId, -- Not abstract
22 vanillaIdInfo, noCafIdInfo,
23 seqIdInfo, megaSeqIdInfo,
26 zapLamInfo, zapDemandInfo, zapFragileInfo,
31 arityInfo, setArityInfo, ppArityInfo,
33 -- New demand and strictness info
34 newStrictnessInfo, setNewStrictnessInfo,
35 newDemandInfo, setNewDemandInfo, pprNewStrictness,
39 -- Strictness; imported from Demand
41 mkStrictnessInfo, noStrictnessInfo,
42 ppStrictnessInfo,isBottomingStrictness,
46 WorkerInfo(..), workerExists, wrapperArity, workerId,
47 workerInfo, setWorkerInfo, ppWorkerInfo,
50 unfoldingInfo, setUnfoldingInfo, setUnfoldingInfoLazily,
53 -- Old DemandInfo and StrictnessInfo
54 demandInfo, setDemandInfo,
55 strictnessInfo, setStrictnessInfo,
56 cprInfoFromNewStrictness,
57 oldStrictnessFromNew, newStrictnessFromOld,
60 -- Constructed Product Result Info
61 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo,
66 inlinePragInfo, setInlinePragInfo,
69 OccInfo(..), isFragileOcc, isDeadOcc, isLoopBreaker,
70 InsideLam, OneBranch, insideLam, notInsideLam, oneBranch, notOneBranch,
74 SpecInfo(..), specInfo, setSpecInfo, isEmptySpecInfo,
75 specInfoFreeVars, specInfoRules, seqSpecInfo, setSpecInfoHead,
78 CafInfo(..), cafInfo, ppCafInfo, setCafInfo, mayHaveCafRefs,
80 -- Lambda-bound variable info
81 LBVarInfo(..), lbvarInfo, setLBVarInfo, noLBVarInfo, hasNoLBVarInfo,
84 TickBoxOp(..), TickBoxId,
87 #include "HsVersions.h"
105 #ifdef OLD_STRICTNESS
107 import qualified Demand
112 -- infixl so you can say (id `set` a `set` b)
113 infixl 1 `setSpecInfo`,
121 `setNewStrictnessInfo`,
122 `setAllStrictnessInfo`,
124 #ifdef OLD_STRICTNESS
127 , `setStrictnessInfo`
131 %************************************************************************
133 \subsection{New strictness info}
135 %************************************************************************
140 -- setAllStrictnessInfo :: IdInfo -> Maybe StrictSig -> IdInfo
141 -- Set old and new strictness info
142 setAllStrictnessInfo info Nothing
143 = info { newStrictnessInfo = Nothing
144 #ifdef OLD_STRICTNESS
145 , strictnessInfo = NoStrictnessInfo
146 , cprInfo = NoCPRInfo
150 setAllStrictnessInfo info (Just sig)
151 = info { newStrictnessInfo = Just sig
152 #ifdef OLD_STRICTNESS
153 , strictnessInfo = oldStrictnessFromNew sig
154 , cprInfo = cprInfoFromNewStrictness sig
158 seqNewStrictnessInfo Nothing = ()
159 seqNewStrictnessInfo (Just ty) = seqStrictSig ty
161 pprNewStrictness Nothing = empty
162 pprNewStrictness (Just sig) = ftext FSLIT("Str:") <+> ppr sig
164 #ifdef OLD_STRICTNESS
165 oldStrictnessFromNew :: StrictSig -> Demand.StrictnessInfo
166 oldStrictnessFromNew sig = mkStrictnessInfo (map oldDemand dmds, isBotRes res_info)
168 (dmds, res_info) = splitStrictSig sig
170 cprInfoFromNewStrictness :: StrictSig -> CprInfo
171 cprInfoFromNewStrictness sig = case strictSigResInfo sig of
175 newStrictnessFromOld :: Name -> Arity -> Demand.StrictnessInfo -> CprInfo -> StrictSig
176 newStrictnessFromOld name arity (Demand.StrictnessInfo ds res) cpr
177 | listLengthCmp ds arity /= GT -- length ds <= arity
178 -- Sometimes the old strictness analyser has more
179 -- demands than the arity justifies
180 = mk_strict_sig name arity $
181 mkTopDmdType (map newDemand ds) (newRes res cpr)
183 newStrictnessFromOld name arity other cpr
184 = -- Either no strictness info, or arity is too small
185 -- In either case we can't say anything useful
186 mk_strict_sig name arity $
187 mkTopDmdType (replicate arity lazyDmd) (newRes False cpr)
189 mk_strict_sig name arity dmd_ty
190 = WARN( arity /= dmdTypeDepth dmd_ty, ppr name <+> (ppr arity $$ ppr dmd_ty) )
193 newRes True _ = BotRes
194 newRes False ReturnsCPR = retCPR
195 newRes False NoCPRInfo = TopRes
197 newDemand :: Demand.Demand -> NewDemand.Demand
198 newDemand (WwLazy True) = Abs
199 newDemand (WwLazy False) = lazyDmd
200 newDemand WwStrict = evalDmd
201 newDemand (WwUnpack unpk ds) = Eval (Prod (map newDemand ds))
202 newDemand WwPrim = lazyDmd
203 newDemand WwEnum = evalDmd
205 oldDemand :: NewDemand.Demand -> Demand.Demand
206 oldDemand Abs = WwLazy True
207 oldDemand Top = WwLazy False
208 oldDemand Bot = WwStrict
209 oldDemand (Box Bot) = WwStrict
210 oldDemand (Box Abs) = WwLazy False
211 oldDemand (Box (Eval _)) = WwStrict -- Pass box only
212 oldDemand (Defer d) = WwLazy False
213 oldDemand (Eval (Prod ds)) = WwUnpack True (map oldDemand ds)
214 oldDemand (Eval (Poly _)) = WwStrict
215 oldDemand (Call _) = WwStrict
217 #endif /* OLD_STRICTNESS */
222 seqNewDemandInfo Nothing = ()
223 seqNewDemandInfo (Just dmd) = seqDemand dmd
227 %************************************************************************
229 \subsection{GlobalIdDetails}
231 %************************************************************************
233 This type is here (rather than in Id.lhs) mainly because there's
234 an IdInfo.hi-boot, but no Id.hi-boot, and GlobalIdDetails is imported
235 (recursively) by Var.lhs.
239 = VanillaGlobal -- Imported from elsewhere, a default method Id.
241 | RecordSelId -- The Id for a record selector
242 { sel_tycon :: TyCon -- For a data type family, this is the *instance* TyCon
243 -- not the family TyCon
244 , sel_label :: FieldLabel
245 , sel_naughty :: Bool -- True <=> naughty
246 } -- See Note [Naughty record selectors]
247 -- with MkId.mkRecordSelectorId
249 | DataConWorkId DataCon -- The Id for a data constructor *worker*
250 | DataConWrapId DataCon -- The Id for a data constructor *wrapper*
251 -- [the only reasons we need to know is so that
252 -- a) to support isImplicitId
253 -- b) when desugaring a RecordCon we can get
254 -- from the Id back to the data con]
256 | ClassOpId Class -- An operation of a class
258 | PrimOpId PrimOp -- The Id for a primitive operator
259 | FCallId ForeignCall -- The Id for a foreign call
261 | TickBoxOpId TickBoxOp -- The Id for a tick box (both traditional and binary)
263 | NotGlobalId -- Used as a convenient extra return value from globalIdDetails
265 notGlobalId = NotGlobalId
267 instance Outputable GlobalIdDetails where
268 ppr NotGlobalId = ptext SLIT("[***NotGlobalId***]")
269 ppr VanillaGlobal = ptext SLIT("[GlobalId]")
270 ppr (DataConWorkId _) = ptext SLIT("[DataCon]")
271 ppr (DataConWrapId _) = ptext SLIT("[DataConWrapper]")
272 ppr (ClassOpId _) = ptext SLIT("[ClassOp]")
273 ppr (PrimOpId _) = ptext SLIT("[PrimOp]")
274 ppr (FCallId _) = ptext SLIT("[ForeignCall]")
275 ppr (TickBoxOpId _) = ptext SLIT("[TickBoxOp]")
276 ppr (RecordSelId {}) = ptext SLIT("[RecSel]")
280 %************************************************************************
282 \subsection{The main IdInfo type}
284 %************************************************************************
286 An @IdInfo@ gives {\em optional} information about an @Id@. If
287 present it never lies, but it may not be present, in which case there
288 is always a conservative assumption which can be made.
290 Two @Id@s may have different info even though they have the same
291 @Unique@ (and are hence the same @Id@); for example, one might lack
292 the properties attached to the other.
294 The @IdInfo@ gives information about the value, or definition, of the
295 @Id@. It does {\em not} contain information about the @Id@'s usage
296 (except for @DemandInfo@? ToDo). (@lbvarInfo@ is also a marginal
302 arityInfo :: !ArityInfo, -- Its arity
303 specInfo :: SpecInfo, -- Specialisations of this function which exist
304 #ifdef OLD_STRICTNESS
305 cprInfo :: CprInfo, -- Function always constructs a product result
306 demandInfo :: Demand.Demand, -- Whether or not it is definitely demanded
307 strictnessInfo :: StrictnessInfo, -- Strictness properties
309 workerInfo :: WorkerInfo, -- Pointer to Worker Function
310 -- Within one module this is irrelevant; the
311 -- inlining of a worker is handled via the Unfolding
312 -- WorkerInfo is used *only* to indicate the form of
313 -- the RHS, so that interface files don't actually
314 -- need to contain the RHS; it can be derived from
315 -- the strictness info
317 unfoldingInfo :: Unfolding, -- Its unfolding
318 cafInfo :: CafInfo, -- CAF info
319 lbvarInfo :: LBVarInfo, -- Info about a lambda-bound variable
320 inlinePragInfo :: InlinePragInfo, -- Inline pragma
321 occInfo :: OccInfo, -- How it occurs
323 newStrictnessInfo :: Maybe StrictSig, -- Reason for Maybe: the DmdAnal phase needs to
324 -- know whether whether this is the first visit,
325 -- so it can assign botSig. Other customers want
326 -- topSig. So Nothing is good.
328 newDemandInfo :: Maybe Demand -- Similarly we want to know if there's no
329 -- known demand yet, for when we are looking for
333 seqIdInfo :: IdInfo -> ()
334 seqIdInfo (IdInfo {}) = ()
336 megaSeqIdInfo :: IdInfo -> ()
338 = seqSpecInfo (specInfo info) `seq`
339 seqWorker (workerInfo info) `seq`
341 -- Omitting this improves runtimes a little, presumably because
342 -- some unfoldings are not calculated at all
343 -- seqUnfolding (unfoldingInfo info) `seq`
345 seqNewDemandInfo (newDemandInfo info) `seq`
346 seqNewStrictnessInfo (newStrictnessInfo info) `seq`
348 #ifdef OLD_STRICTNESS
349 Demand.seqDemand (demandInfo info) `seq`
350 seqStrictnessInfo (strictnessInfo info) `seq`
351 seqCpr (cprInfo info) `seq`
354 seqCaf (cafInfo info) `seq`
355 seqLBVar (lbvarInfo info) `seq`
356 seqOccInfo (occInfo info)
362 setWorkerInfo info wk = wk `seq` info { workerInfo = wk }
363 setSpecInfo info sp = sp `seq` info { specInfo = sp }
364 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
365 setOccInfo info oc = oc `seq` info { occInfo = oc }
366 #ifdef OLD_STRICTNESS
367 setStrictnessInfo info st = st `seq` info { strictnessInfo = st }
369 -- Try to avoid spack leaks by seq'ing
371 setUnfoldingInfoLazily info uf -- Lazy variant to avoid looking at the
372 = -- unfolding of an imported Id unless necessary
373 info { unfoldingInfo = uf } -- (In this case the demand-zapping is redundant.)
375 setUnfoldingInfo info uf
376 -- We do *not* seq on the unfolding info, For some reason, doing so
377 -- actually increases residency significantly.
378 = info { unfoldingInfo = uf }
380 #ifdef OLD_STRICTNESS
381 setDemandInfo info dd = info { demandInfo = dd }
382 setCprInfo info cp = info { cprInfo = cp }
385 setArityInfo info ar = info { arityInfo = ar }
386 setCafInfo info caf = info { cafInfo = caf }
388 setLBVarInfo info lb = {-lb `seq`-} info { lbvarInfo = lb }
390 setNewDemandInfo info dd = dd `seq` info { newDemandInfo = dd }
391 setNewStrictnessInfo info dd = dd `seq` info { newStrictnessInfo = dd }
396 vanillaIdInfo :: IdInfo
399 cafInfo = vanillaCafInfo,
400 arityInfo = unknownArity,
401 #ifdef OLD_STRICTNESS
404 strictnessInfo = NoStrictnessInfo,
406 specInfo = emptySpecInfo,
407 workerInfo = NoWorker,
408 unfoldingInfo = noUnfolding,
409 lbvarInfo = NoLBVarInfo,
410 inlinePragInfo = AlwaysActive,
412 newDemandInfo = Nothing,
413 newStrictnessInfo = Nothing
416 noCafIdInfo = vanillaIdInfo `setCafInfo` NoCafRefs
417 -- Used for built-in type Ids in MkId.
421 %************************************************************************
423 \subsection[arity-IdInfo]{Arity info about an @Id@}
425 %************************************************************************
427 For locally-defined Ids, the code generator maintains its own notion
428 of their arities; so it should not be asking... (but other things
429 besides the code-generator need arity info!)
432 type ArityInfo = Arity
433 -- A partial application of this Id to up to n-1 value arguments
434 -- does essentially no work. That is not necessarily the
435 -- same as saying that it has n leading lambdas, because coerces
436 -- may get in the way.
438 -- The arity might increase later in the compilation process, if
439 -- an extra lambda floats up to the binding site.
441 unknownArity = 0 :: Arity
443 ppArityInfo 0 = empty
444 ppArityInfo n = hsep [ptext SLIT("Arity"), int n]
447 %************************************************************************
449 \subsection{Inline-pragma information}
451 %************************************************************************
454 type InlinePragInfo = Activation
455 -- Tells when the inlining is active
456 -- When it is active the thing may be inlined, depending on how
459 -- If there was an INLINE pragma, then as a separate matter, the
460 -- RHS will have been made to look small with a CoreSyn Inline Note
462 -- The default InlinePragInfo is AlwaysActive, so the info serves
463 -- entirely as a way to inhibit inlining until we want it
467 %************************************************************************
471 %************************************************************************
477 VarSet -- Locally-defined free vars of *both* LHS and RHS
478 -- of rules. I don't think it needs to include the
480 -- Note [Rule dependency info]
482 emptySpecInfo :: SpecInfo
483 emptySpecInfo = SpecInfo [] emptyVarSet
485 isEmptySpecInfo :: SpecInfo -> Bool
486 isEmptySpecInfo (SpecInfo rs _) = null rs
488 specInfoFreeVars :: SpecInfo -> VarSet
489 specInfoFreeVars (SpecInfo _ fvs) = fvs
491 specInfoRules :: SpecInfo -> [CoreRule]
492 specInfoRules (SpecInfo rules _) = rules
494 setSpecInfoHead :: Name -> SpecInfo -> SpecInfo
495 setSpecInfoHead fn (SpecInfo rules fvs)
496 = SpecInfo (map set_head rules) fvs
498 set_head rule = rule { ru_fn = fn }
500 seqSpecInfo (SpecInfo rules fvs) = seqRules rules `seq` seqVarSet fvs
503 Note [Rule dependency info]
504 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
505 THe VarSet in a SpecInfo is used for dependency analysis in the
506 occurrence analyser. We must track free vars in *both* lhs and rhs. Why both?
510 Then if we substitute y for x, we'd better do so in the
511 rule's LHS too, so we'd better ensure the dependency is respected
515 %************************************************************************
517 \subsection[worker-IdInfo]{Worker info about an @Id@}
519 %************************************************************************
521 If this Id has a worker then we store a reference to it. Worker
522 functions are generated by the worker/wrapper pass. This uses
523 information from strictness analysis.
525 There might not be a worker, even for a strict function, because:
526 (a) the function might be small enough to inline, so no need
528 (b) the strictness info might be "SSS" or something, so no w/w split.
530 Sometimes the arity of a wrapper changes from the original arity from
531 which it was generated, so we always emit the "original" arity into
532 the interface file, as part of the worker info.
534 How can this happen? Sometimes we get
535 f = coerce t (\x y -> $wf x y)
536 at the moment of w/w split; but the eta reducer turns it into
538 which is perfectly fine except that the exposed arity so far as
539 the code generator is concerned (zero) differs from the arity
540 when we did the split (2).
542 All this arises because we use 'arity' to mean "exactly how many
543 top level lambdas are there" in interface files; but during the
544 compilation of this module it means "how many things can I apply
549 data WorkerInfo = NoWorker
551 -- The Arity is the arity of the *wrapper* at the moment of the
552 -- w/w split. See notes above.
554 seqWorker :: WorkerInfo -> ()
555 seqWorker (HasWorker id a) = id `seq` a `seq` ()
556 seqWorker NoWorker = ()
558 ppWorkerInfo NoWorker = empty
559 ppWorkerInfo (HasWorker wk_id _) = ptext SLIT("Worker") <+> ppr wk_id
561 workerExists :: WorkerInfo -> Bool
562 workerExists NoWorker = False
563 workerExists (HasWorker _ _) = True
565 workerId :: WorkerInfo -> Id
566 workerId (HasWorker id _) = id
568 wrapperArity :: WorkerInfo -> Arity
569 wrapperArity (HasWorker _ a) = a
573 %************************************************************************
575 \subsection[CG-IdInfo]{Code generator-related information}
577 %************************************************************************
580 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.lhs).
583 = MayHaveCafRefs -- either:
584 -- (1) A function or static constructor
585 -- that refers to one or more CAFs,
586 -- (2) A real live CAF
588 | NoCafRefs -- A function or static constructor
589 -- that refers to no CAFs.
591 vanillaCafInfo = MayHaveCafRefs -- Definitely safe
593 mayHaveCafRefs MayHaveCafRefs = True
594 mayHaveCafRefs _ = False
596 seqCaf c = c `seq` ()
598 ppCafInfo NoCafRefs = ptext SLIT("NoCafRefs")
599 ppCafInfo MayHaveCafRefs = empty
602 %************************************************************************
604 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
606 %************************************************************************
608 If the @Id@ is a function then it may have CPR info. A CPR analysis
609 phase detects whether:
613 The function's return value has a product type, i.e. an algebraic type
614 with a single constructor. Examples of such types are tuples and boxed
617 The function always 'constructs' the value that it is returning. It
618 must do this on every path through, and it's OK if it calls another
619 function which constructs the result.
622 If this is the case then we store a template which tells us the
623 function has the CPR property and which components of the result are
627 #ifdef OLD_STRICTNESS
630 | ReturnsCPR -- Yes, this function returns a constructed product
631 -- Implicitly, this means "after the function has been applied
632 -- to all its arguments", so the worker/wrapper builder in
633 -- WwLib.mkWWcpr checks that that it is indeed saturated before
634 -- making use of the CPR info
636 -- We used to keep nested info about sub-components, but
637 -- we never used it so I threw it away
639 seqCpr :: CprInfo -> ()
640 seqCpr ReturnsCPR = ()
641 seqCpr NoCPRInfo = ()
643 noCprInfo = NoCPRInfo
645 ppCprInfo NoCPRInfo = empty
646 ppCprInfo ReturnsCPR = ptext SLIT("__M")
648 instance Outputable CprInfo where
651 instance Show CprInfo where
652 showsPrec p c = showsPrecSDoc p (ppr c)
657 %************************************************************************
659 \subsection[lbvar-IdInfo]{Lambda-bound var info about an @Id@}
661 %************************************************************************
663 If the @Id@ is a lambda-bound variable then it may have lambda-bound
664 var info. Sometimes we know whether the lambda binding this var is a
665 ``one-shot'' lambda; that is, whether it is applied at most once.
667 This information may be useful in optimisation, as computations may
668 safely be floated inside such a lambda without risk of duplicating
672 data LBVarInfo = NoLBVarInfo
673 | IsOneShotLambda -- The lambda is applied at most once).
675 seqLBVar l = l `seq` ()
679 hasNoLBVarInfo NoLBVarInfo = True
680 hasNoLBVarInfo IsOneShotLambda = False
682 noLBVarInfo = NoLBVarInfo
684 pprLBVarInfo NoLBVarInfo = empty
685 pprLBVarInfo IsOneShotLambda = ptext SLIT("OneShot")
687 instance Outputable LBVarInfo where
690 instance Show LBVarInfo where
691 showsPrec p c = showsPrecSDoc p (ppr c)
695 %************************************************************************
697 \subsection{Bulk operations on IdInfo}
699 %************************************************************************
701 @zapLamInfo@ is used for lambda binders that turn out to to be
702 part of an unsaturated lambda
705 zapLamInfo :: IdInfo -> Maybe IdInfo
706 zapLamInfo info@(IdInfo {occInfo = occ, newDemandInfo = demand})
707 | is_safe_occ occ && is_safe_dmd demand
710 = Just (info {occInfo = safe_occ, newDemandInfo = Nothing})
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 (OneOcc in_lam _ _) = in_lam
715 is_safe_occ _other = True
717 safe_occ = case occ of
718 OneOcc _ once int_cxt -> OneOcc insideLam once int_cxt
721 is_safe_dmd Nothing = True
722 is_safe_dmd (Just dmd) = not (isStrictDmd dmd)
726 zapDemandInfo :: IdInfo -> Maybe IdInfo
727 zapDemandInfo info@(IdInfo {newDemandInfo = dmd})
728 | isJust dmd = Just (info {newDemandInfo = Nothing})
729 | otherwise = Nothing
733 zapFragileInfo :: IdInfo -> Maybe IdInfo
734 -- Zap info that depends on free variables
736 = Just (info `setSpecInfo` emptySpecInfo
737 `setWorkerInfo` NoWorker
738 `setUnfoldingInfo` NoUnfolding
739 `setOccInfo` if isFragileOcc occ then NoOccInfo else occ)
744 %************************************************************************
746 \subsection{TickBoxOp}
748 %************************************************************************
754 = TickBox Module {-# UNPACK #-} !TickBoxId
755 -- ^Tick box for Hpc-style coverage
757 instance Outputable TickBoxOp where
758 ppr (TickBox mod n) = ptext SLIT("tick") <+> ppr (mod,n)