Zap Call Arity info in the simplifier
[ghc.git] / compiler / basicTypes / IdInfo.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
4
5 \section[IdInfo]{@IdInfos@: Non-essential information about @Ids@}
6
7 (And a pretty good illustration of quite a few things wrong with
8 Haskell. [WDP 94/11])
9 -}
10
11 {-# LANGUAGE CPP #-}
12 {-# LANGUAGE FlexibleContexts #-}
13
14 module IdInfo (
15 -- * The IdDetails type
16 IdDetails(..), pprIdDetails, coVarDetails, isCoVarDetails,
17 JoinArity, isJoinIdDetails_maybe,
18 RecSelParent(..),
19
20 -- * The IdInfo type
21 IdInfo, -- Abstract
22 vanillaIdInfo, noCafIdInfo,
23
24 -- ** The OneShotInfo type
25 OneShotInfo(..),
26 oneShotInfo, noOneShotInfo, hasNoOneShotInfo,
27 setOneShotInfo,
28
29 -- ** Zapping various forms of Info
30 zapLamInfo, zapFragileInfo,
31 zapDemandInfo, zapUsageInfo, zapUsageEnvInfo, zapUsedOnceInfo,
32 zapTailCallInfo, zapCallArityInfo,
33
34 -- ** The ArityInfo type
35 ArityInfo,
36 unknownArity,
37 arityInfo, setArityInfo, ppArityInfo,
38
39 callArityInfo, setCallArityInfo,
40
41 -- ** Demand and strictness Info
42 strictnessInfo, setStrictnessInfo,
43 demandInfo, setDemandInfo, pprStrictness,
44
45 -- ** Unfolding Info
46 unfoldingInfo, setUnfoldingInfo,
47
48 -- ** The InlinePragInfo type
49 InlinePragInfo,
50 inlinePragInfo, setInlinePragInfo,
51
52 -- ** The OccInfo type
53 OccInfo(..),
54 isDeadOcc, isStrongLoopBreaker, isWeakLoopBreaker,
55 occInfo, setOccInfo,
56
57 InsideLam, OneBranch,
58 insideLam, notInsideLam, oneBranch, notOneBranch,
59
60 TailCallInfo(..),
61 tailCallInfo, isAlwaysTailCalled,
62
63 -- ** The RuleInfo type
64 RuleInfo(..),
65 emptyRuleInfo,
66 isEmptyRuleInfo, ruleInfoFreeVars,
67 ruleInfoRules, setRuleInfoHead,
68 ruleInfo, setRuleInfo,
69
70 -- ** The CAFInfo type
71 CafInfo(..),
72 ppCafInfo, mayHaveCafRefs,
73 cafInfo, setCafInfo,
74
75 -- ** Tick-box Info
76 TickBoxOp(..), TickBoxId,
77
78 -- ** Levity info
79 LevityInfo, levityInfo, setNeverLevPoly, setLevityInfoWithType,
80 isNeverLevPolyIdInfo
81 ) where
82
83 #include "HsVersions.h"
84
85 import CoreSyn
86
87 import Class
88 import {-# SOURCE #-} PrimOp (PrimOp)
89 import Name
90 import VarSet
91 import BasicTypes
92 import DataCon
93 import TyCon
94 import PatSyn
95 import Type
96 import ForeignCall
97 import Outputable
98 import Module
99 import Demand
100 import Util
101
102 -- infixl so you can say (id `set` a `set` b)
103 infixl 1 `setRuleInfo`,
104 `setArityInfo`,
105 `setInlinePragInfo`,
106 `setUnfoldingInfo`,
107 `setOneShotInfo`,
108 `setOccInfo`,
109 `setCafInfo`,
110 `setStrictnessInfo`,
111 `setDemandInfo`,
112 `setNeverLevPoly`,
113 `setLevityInfoWithType`
114
115 {-
116 ************************************************************************
117 * *
118 IdDetails
119 * *
120 ************************************************************************
121 -}
122
123 -- | Identifier Details
124 --
125 -- The 'IdDetails' of an 'Id' give stable, and necessary,
126 -- information about the Id.
127 data IdDetails
128 = VanillaId
129
130 -- | The 'Id' for a record selector
131 | RecSelId
132 { sel_tycon :: RecSelParent
133 , sel_naughty :: Bool -- True <=> a "naughty" selector which can't actually exist, for example @x@ in:
134 -- data T = forall a. MkT { x :: a }
135 } -- See Note [Naughty record selectors] in TcTyClsDecls
136
137 | DataConWorkId DataCon -- ^ The 'Id' is for a data constructor /worker/
138 | DataConWrapId DataCon -- ^ The 'Id' is for a data constructor /wrapper/
139
140 -- [the only reasons we need to know is so that
141 -- a) to support isImplicitId
142 -- b) when desugaring a RecordCon we can get
143 -- from the Id back to the data con]
144 | ClassOpId Class -- ^ The 'Id' is a superclass selector,
145 -- or class operation of a class
146
147 | PrimOpId PrimOp -- ^ The 'Id' is for a primitive operator
148 | FCallId ForeignCall -- ^ The 'Id' is for a foreign call.
149 -- Type will be simple: no type families, newtypes, etc
150
151 | TickBoxOpId TickBoxOp -- ^ The 'Id' is for a HPC tick box (both traditional and binary)
152
153 | DFunId Bool -- ^ A dictionary function.
154 -- Bool = True <=> the class has only one method, so may be
155 -- implemented with a newtype, so it might be bad
156 -- to be strict on this dictionary
157
158 | CoVarId -- ^ A coercion variable
159 -- This only covers /un-lifted/ coercions, of type
160 -- (t1 ~# t2) or (t1 ~R# t2), not their lifted variants
161 | JoinId JoinArity -- ^ An 'Id' for a join point taking n arguments
162 -- Note [Join points] in CoreSyn
163
164 -- | Recursive Selector Parent
165 data RecSelParent = RecSelData TyCon | RecSelPatSyn PatSyn deriving Eq
166 -- Either `TyCon` or `PatSyn` depending
167 -- on the origin of the record selector.
168 -- For a data type family, this is the
169 -- /instance/ 'TyCon' not the family 'TyCon'
170
171 instance Outputable RecSelParent where
172 ppr p = case p of
173 RecSelData ty_con -> ppr ty_con
174 RecSelPatSyn ps -> ppr ps
175
176 -- | Just a synonym for 'CoVarId'. Written separately so it can be
177 -- exported in the hs-boot file.
178 coVarDetails :: IdDetails
179 coVarDetails = CoVarId
180
181 -- | Check if an 'IdDetails' says 'CoVarId'.
182 isCoVarDetails :: IdDetails -> Bool
183 isCoVarDetails CoVarId = True
184 isCoVarDetails _ = False
185
186 isJoinIdDetails_maybe :: IdDetails -> Maybe JoinArity
187 isJoinIdDetails_maybe (JoinId join_arity) = Just join_arity
188 isJoinIdDetails_maybe _ = Nothing
189
190 instance Outputable IdDetails where
191 ppr = pprIdDetails
192
193 pprIdDetails :: IdDetails -> SDoc
194 pprIdDetails VanillaId = empty
195 pprIdDetails other = brackets (pp other)
196 where
197 pp VanillaId = panic "pprIdDetails"
198 pp (DataConWorkId _) = text "DataCon"
199 pp (DataConWrapId _) = text "DataConWrapper"
200 pp (ClassOpId {}) = text "ClassOp"
201 pp (PrimOpId _) = text "PrimOp"
202 pp (FCallId _) = text "ForeignCall"
203 pp (TickBoxOpId _) = text "TickBoxOp"
204 pp (DFunId nt) = text "DFunId" <> ppWhen nt (text "(nt)")
205 pp (RecSelId { sel_naughty = is_naughty })
206 = brackets $ text "RecSel" <>
207 ppWhen is_naughty (text "(naughty)")
208 pp CoVarId = text "CoVarId"
209 pp (JoinId arity) = text "JoinId" <> parens (int arity)
210
211 {-
212 ************************************************************************
213 * *
214 \subsection{The main IdInfo type}
215 * *
216 ************************************************************************
217 -}
218
219 -- | Identifier Information
220 --
221 -- An 'IdInfo' gives /optional/ information about an 'Id'. If
222 -- present it never lies, but it may not be present, in which case there
223 -- is always a conservative assumption which can be made.
224 --
225 -- Two 'Id's may have different info even though they have the same
226 -- 'Unique' (and are hence the same 'Id'); for example, one might lack
227 -- the properties attached to the other.
228 --
229 -- Most of the 'IdInfo' gives information about the value, or definition, of
230 -- the 'Id', independent of its usage. Exceptions to this
231 -- are 'demandInfo', 'occInfo', 'oneShotInfo' and 'callArityInfo'.
232 --
233 -- Performance note: when we update 'IdInfo', we have to reallocate this
234 -- entire record, so it is a good idea not to let this data structure get
235 -- too big.
236 data IdInfo
237 = IdInfo {
238 arityInfo :: !ArityInfo, -- ^ 'Id' arity
239 ruleInfo :: RuleInfo, -- ^ Specialisations of the 'Id's function which exist
240 -- See Note [Specialisations and RULES in IdInfo]
241 unfoldingInfo :: Unfolding, -- ^ The 'Id's unfolding
242 cafInfo :: CafInfo, -- ^ 'Id' CAF info
243 oneShotInfo :: OneShotInfo, -- ^ Info about a lambda-bound variable, if the 'Id' is one
244 inlinePragInfo :: InlinePragma, -- ^ Any inline pragma atached to the 'Id'
245 occInfo :: OccInfo, -- ^ How the 'Id' occurs in the program
246
247 strictnessInfo :: StrictSig, -- ^ A strictness signature
248
249 demandInfo :: Demand, -- ^ ID demand information
250 callArityInfo :: !ArityInfo, -- ^ How this is called.
251 -- n <=> all calls have at least n arguments
252
253 levityInfo :: LevityInfo -- ^ when applied, will this Id ever have a levity-polymorphic type?
254 }
255
256 -- Setters
257
258 setRuleInfo :: IdInfo -> RuleInfo -> IdInfo
259 setRuleInfo info sp = sp `seq` info { ruleInfo = sp }
260 setInlinePragInfo :: IdInfo -> InlinePragma -> IdInfo
261 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
262 setOccInfo :: IdInfo -> OccInfo -> IdInfo
263 setOccInfo info oc = oc `seq` info { occInfo = oc }
264 -- Try to avoid spack leaks by seq'ing
265
266 setUnfoldingInfo :: IdInfo -> Unfolding -> IdInfo
267 setUnfoldingInfo info uf
268 = -- We don't seq the unfolding, as we generate intermediate
269 -- unfoldings which are just thrown away, so evaluating them is a
270 -- waste of time.
271 -- seqUnfolding uf `seq`
272 info { unfoldingInfo = uf }
273
274 setArityInfo :: IdInfo -> ArityInfo -> IdInfo
275 setArityInfo info ar = info { arityInfo = ar }
276 setCallArityInfo :: IdInfo -> ArityInfo -> IdInfo
277 setCallArityInfo info ar = info { callArityInfo = ar }
278 setCafInfo :: IdInfo -> CafInfo -> IdInfo
279 setCafInfo info caf = info { cafInfo = caf }
280
281 setOneShotInfo :: IdInfo -> OneShotInfo -> IdInfo
282 setOneShotInfo info lb = {-lb `seq`-} info { oneShotInfo = lb }
283
284 setDemandInfo :: IdInfo -> Demand -> IdInfo
285 setDemandInfo info dd = dd `seq` info { demandInfo = dd }
286
287 setStrictnessInfo :: IdInfo -> StrictSig -> IdInfo
288 setStrictnessInfo info dd = dd `seq` info { strictnessInfo = dd }
289
290 -- | Basic 'IdInfo' that carries no useful information whatsoever
291 vanillaIdInfo :: IdInfo
292 vanillaIdInfo
293 = IdInfo {
294 cafInfo = vanillaCafInfo,
295 arityInfo = unknownArity,
296 ruleInfo = emptyRuleInfo,
297 unfoldingInfo = noUnfolding,
298 oneShotInfo = NoOneShotInfo,
299 inlinePragInfo = defaultInlinePragma,
300 occInfo = noOccInfo,
301 demandInfo = topDmd,
302 strictnessInfo = nopSig,
303 callArityInfo = unknownArity,
304 levityInfo = NoLevityInfo
305 }
306
307 -- | More informative 'IdInfo' we can use when we know the 'Id' has no CAF references
308 noCafIdInfo :: IdInfo
309 noCafIdInfo = vanillaIdInfo `setCafInfo` NoCafRefs
310 -- Used for built-in type Ids in MkId.
311
312 {-
313 ************************************************************************
314 * *
315 \subsection[arity-IdInfo]{Arity info about an @Id@}
316 * *
317 ************************************************************************
318
319 For locally-defined Ids, the code generator maintains its own notion
320 of their arities; so it should not be asking... (but other things
321 besides the code-generator need arity info!)
322 -}
323
324 -- | Arity Information
325 --
326 -- An 'ArityInfo' of @n@ tells us that partial application of this
327 -- 'Id' to up to @n-1@ value arguments does essentially no work.
328 --
329 -- That is not necessarily the same as saying that it has @n@ leading
330 -- lambdas, because coerces may get in the way.
331 --
332 -- The arity might increase later in the compilation process, if
333 -- an extra lambda floats up to the binding site.
334 type ArityInfo = Arity
335
336 -- | It is always safe to assume that an 'Id' has an arity of 0
337 unknownArity :: Arity
338 unknownArity = 0
339
340 ppArityInfo :: Int -> SDoc
341 ppArityInfo 0 = empty
342 ppArityInfo n = hsep [text "Arity", int n]
343
344 {-
345 ************************************************************************
346 * *
347 \subsection{Inline-pragma information}
348 * *
349 ************************************************************************
350 -}
351
352 -- | Inline Pragma Information
353 --
354 -- Tells when the inlining is active.
355 -- When it is active the thing may be inlined, depending on how
356 -- big it is.
357 --
358 -- If there was an @INLINE@ pragma, then as a separate matter, the
359 -- RHS will have been made to look small with a Core inline 'Note'
360 --
361 -- The default 'InlinePragInfo' is 'AlwaysActive', so the info serves
362 -- entirely as a way to inhibit inlining until we want it
363 type InlinePragInfo = InlinePragma
364
365 {-
366 ************************************************************************
367 * *
368 Strictness
369 * *
370 ************************************************************************
371 -}
372
373 pprStrictness :: StrictSig -> SDoc
374 pprStrictness sig = ppr sig
375
376 {-
377 ************************************************************************
378 * *
379 RuleInfo
380 * *
381 ************************************************************************
382
383 Note [Specialisations and RULES in IdInfo]
384 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
385 Generally speaking, a GlobalId has an *empty* RuleInfo. All their
386 RULES are contained in the globally-built rule-base. In principle,
387 one could attach the to M.f the RULES for M.f that are defined in M.
388 But we don't do that for instance declarations and so we just treat
389 them all uniformly.
390
391 The EXCEPTION is PrimOpIds, which do have rules in their IdInfo. That is
392 jsut for convenience really.
393
394 However, LocalIds may have non-empty RuleInfo. We treat them
395 differently because:
396 a) they might be nested, in which case a global table won't work
397 b) the RULE might mention free variables, which we use to keep things alive
398
399 In TidyPgm, when the LocalId becomes a GlobalId, its RULES are stripped off
400 and put in the global list.
401 -}
402
403 -- | Rule Information
404 --
405 -- Records the specializations of this 'Id' that we know about
406 -- in the form of rewrite 'CoreRule's that target them
407 data RuleInfo
408 = RuleInfo
409 [CoreRule]
410 DVarSet -- Locally-defined free vars of *both* LHS and RHS
411 -- of rules. I don't think it needs to include the
412 -- ru_fn though.
413 -- Note [Rule dependency info] in OccurAnal
414
415 -- | Assume that no specilizations exist: always safe
416 emptyRuleInfo :: RuleInfo
417 emptyRuleInfo = RuleInfo [] emptyDVarSet
418
419 isEmptyRuleInfo :: RuleInfo -> Bool
420 isEmptyRuleInfo (RuleInfo rs _) = null rs
421
422 -- | Retrieve the locally-defined free variables of both the left and
423 -- right hand sides of the specialization rules
424 ruleInfoFreeVars :: RuleInfo -> DVarSet
425 ruleInfoFreeVars (RuleInfo _ fvs) = fvs
426
427 ruleInfoRules :: RuleInfo -> [CoreRule]
428 ruleInfoRules (RuleInfo rules _) = rules
429
430 -- | Change the name of the function the rule is keyed on on all of the 'CoreRule's
431 setRuleInfoHead :: Name -> RuleInfo -> RuleInfo
432 setRuleInfoHead fn (RuleInfo rules fvs)
433 = RuleInfo (map (setRuleIdName fn) rules) fvs
434
435 {-
436 ************************************************************************
437 * *
438 \subsection[CG-IdInfo]{Code generator-related information}
439 * *
440 ************************************************************************
441 -}
442
443 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.hs).
444
445 -- | Constant applicative form Information
446 --
447 -- Records whether an 'Id' makes Constant Applicative Form references
448 data CafInfo
449 = MayHaveCafRefs -- ^ Indicates that the 'Id' is for either:
450 --
451 -- 1. A function or static constructor
452 -- that refers to one or more CAFs, or
453 --
454 -- 2. A real live CAF
455
456 | NoCafRefs -- ^ A function or static constructor
457 -- that refers to no CAFs.
458 deriving (Eq, Ord)
459
460 -- | Assumes that the 'Id' has CAF references: definitely safe
461 vanillaCafInfo :: CafInfo
462 vanillaCafInfo = MayHaveCafRefs
463
464 mayHaveCafRefs :: CafInfo -> Bool
465 mayHaveCafRefs MayHaveCafRefs = True
466 mayHaveCafRefs _ = False
467
468 instance Outputable CafInfo where
469 ppr = ppCafInfo
470
471 ppCafInfo :: CafInfo -> SDoc
472 ppCafInfo NoCafRefs = text "NoCafRefs"
473 ppCafInfo MayHaveCafRefs = empty
474
475 {-
476 ************************************************************************
477 * *
478 \subsection{Bulk operations on IdInfo}
479 * *
480 ************************************************************************
481 -}
482
483 -- | This is used to remove information on lambda binders that we have
484 -- setup as part of a lambda group, assuming they will be applied all at once,
485 -- but turn out to be part of an unsaturated lambda as in e.g:
486 --
487 -- > (\x1. \x2. e) arg1
488 zapLamInfo :: IdInfo -> Maybe IdInfo
489 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
490 | is_safe_occ occ && is_safe_dmd demand
491 = Nothing
492 | otherwise
493 = Just (info {occInfo = safe_occ, demandInfo = topDmd})
494 where
495 -- The "unsafe" occ info is the ones that say I'm not in a lambda
496 -- because that might not be true for an unsaturated lambda
497 is_safe_occ occ | isAlwaysTailCalled occ = False
498 is_safe_occ (OneOcc { occ_in_lam = in_lam }) = in_lam
499 is_safe_occ _other = True
500
501 safe_occ = case occ of
502 OneOcc{} -> occ { occ_in_lam = True
503 , occ_tail = NoTailCallInfo }
504 IAmALoopBreaker{}
505 -> occ { occ_tail = NoTailCallInfo }
506 _other -> occ
507
508 is_safe_dmd dmd = not (isStrictDmd dmd)
509
510 -- | Remove all demand info on the 'IdInfo'
511 zapDemandInfo :: IdInfo -> Maybe IdInfo
512 zapDemandInfo info = Just (info {demandInfo = topDmd})
513
514 -- | Remove usage (but not strictness) info on the 'IdInfo'
515 zapUsageInfo :: IdInfo -> Maybe IdInfo
516 zapUsageInfo info = Just (info {demandInfo = zapUsageDemand (demandInfo info)})
517
518 -- | Remove usage environment info from the strictness signature on the 'IdInfo'
519 zapUsageEnvInfo :: IdInfo -> Maybe IdInfo
520 zapUsageEnvInfo info
521 | hasDemandEnvSig (strictnessInfo info)
522 = Just (info {strictnessInfo = zapUsageEnvSig (strictnessInfo info)})
523 | otherwise
524 = Nothing
525
526 zapUsedOnceInfo :: IdInfo -> Maybe IdInfo
527 zapUsedOnceInfo info
528 = Just $ info { strictnessInfo = zapUsedOnceSig (strictnessInfo info)
529 , demandInfo = zapUsedOnceDemand (demandInfo info) }
530
531 zapFragileInfo :: IdInfo -> Maybe IdInfo
532 -- ^ Zap info that depends on free variables
533 zapFragileInfo info@(IdInfo { occInfo = occ, unfoldingInfo = unf })
534 = new_unf `seq` -- The unfolding field is not (currently) strict, so we
535 -- force it here to avoid a (zapFragileUnfolding unf) thunk
536 -- which might leak space
537 Just (info `setRuleInfo` emptyRuleInfo
538 `setUnfoldingInfo` new_unf
539 `setOccInfo` zapFragileOcc occ)
540 where
541 new_unf = zapFragileUnfolding unf
542
543 zapFragileUnfolding :: Unfolding -> Unfolding
544 zapFragileUnfolding unf
545 | isFragileUnfolding unf = noUnfolding
546 | otherwise = unf
547
548 zapTailCallInfo :: IdInfo -> Maybe IdInfo
549 zapTailCallInfo info
550 = case occInfo info of
551 occ | isAlwaysTailCalled occ -> Just (info `setOccInfo` safe_occ)
552 | otherwise -> Nothing
553 where
554 safe_occ = occ { occ_tail = NoTailCallInfo }
555
556 zapCallArityInfo :: IdInfo -> IdInfo
557 zapCallArityInfo info = setCallArityInfo info 0
558
559 {-
560 ************************************************************************
561 * *
562 \subsection{TickBoxOp}
563 * *
564 ************************************************************************
565 -}
566
567 type TickBoxId = Int
568
569 -- | Tick box for Hpc-style coverage
570 data TickBoxOp
571 = TickBox Module {-# UNPACK #-} !TickBoxId
572
573 instance Outputable TickBoxOp where
574 ppr (TickBox mod n) = text "tick" <+> ppr (mod,n)
575
576 {-
577 ************************************************************************
578 * *
579 Levity
580 * *
581 ************************************************************************
582
583 Note [Levity info]
584 ~~~~~~~~~~~~~~~~~~
585
586 Ids store whether or not they can be levity-polymorphic at any amount
587 of saturation. This is helpful in optimizing the levity-polymorphism check
588 done in the desugarer, where we can usually learn that something is not
589 levity-polymorphic without actually figuring out its type. See
590 isExprLevPoly in CoreUtils for where this info is used. Storing
591 this is required to prevent perf/compiler/T5631 from blowing up.
592
593 -}
594
595 -- See Note [Levity info]
596 data LevityInfo = NoLevityInfo -- always safe
597 | NeverLevityPolymorphic
598 deriving Eq
599
600 instance Outputable LevityInfo where
601 ppr NoLevityInfo = text "NoLevityInfo"
602 ppr NeverLevityPolymorphic = text "NeverLevityPolymorphic"
603
604 -- | Marks an IdInfo describing an Id that is never levity polymorphic (even when
605 -- applied). The Type is only there for checking that it's really never levity
606 -- polymorphic
607 setNeverLevPoly :: HasDebugCallStack => IdInfo -> Type -> IdInfo
608 setNeverLevPoly info ty
609 = ASSERT2( not (resultIsLevPoly ty), ppr ty )
610 info { levityInfo = NeverLevityPolymorphic }
611
612 setLevityInfoWithType :: IdInfo -> Type -> IdInfo
613 setLevityInfoWithType info ty
614 | not (resultIsLevPoly ty)
615 = info { levityInfo = NeverLevityPolymorphic }
616 | otherwise
617 = info
618
619 isNeverLevPolyIdInfo :: IdInfo -> Bool
620 isNeverLevPolyIdInfo info
621 | NeverLevityPolymorphic <- levityInfo info = True
622 | otherwise = False