Create a deterministic version of tyVarsOfType
[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 module IdInfo (
12 -- * The IdDetails type
13 IdDetails(..), pprIdDetails, coVarDetails,
14 RecSelParent(..),
15
16 -- * The IdInfo type
17 IdInfo, -- Abstract
18 vanillaIdInfo, noCafIdInfo,
19
20 -- ** The OneShotInfo type
21 OneShotInfo(..),
22 oneShotInfo, noOneShotInfo, hasNoOneShotInfo,
23 setOneShotInfo,
24
25 -- ** Zapping various forms of Info
26 zapLamInfo, zapFragileInfo,
27 zapDemandInfo, zapUsageInfo,
28
29 -- ** The ArityInfo type
30 ArityInfo,
31 unknownArity,
32 arityInfo, setArityInfo, ppArityInfo,
33
34 callArityInfo, setCallArityInfo,
35
36 -- ** Demand and strictness Info
37 strictnessInfo, setStrictnessInfo,
38 demandInfo, setDemandInfo, pprStrictness,
39
40 -- ** Unfolding Info
41 unfoldingInfo, setUnfoldingInfo, setUnfoldingInfoLazily,
42
43 -- ** The InlinePragInfo type
44 InlinePragInfo,
45 inlinePragInfo, setInlinePragInfo,
46
47 -- ** The OccInfo type
48 OccInfo(..),
49 isDeadOcc, isStrongLoopBreaker, isWeakLoopBreaker,
50 occInfo, setOccInfo,
51
52 InsideLam, OneBranch,
53 insideLam, notInsideLam, oneBranch, notOneBranch,
54
55 -- ** The RuleInfo type
56 RuleInfo(..),
57 emptyRuleInfo,
58 isEmptyRuleInfo, ruleInfoFreeVars,
59 ruleInfoRules, setRuleInfoHead,
60 ruleInfo, setRuleInfo,
61
62 -- ** The CAFInfo type
63 CafInfo(..),
64 ppCafInfo, mayHaveCafRefs,
65 cafInfo, setCafInfo,
66
67 -- ** Tick-box Info
68 TickBoxOp(..), TickBoxId,
69 ) where
70
71 import CoreSyn
72
73 import Class
74 import {-# SOURCE #-} PrimOp (PrimOp)
75 import Name
76 import VarSet
77 import BasicTypes
78 import DataCon
79 import TyCon
80 import {-# SOURCE #-} PatSyn
81 import ForeignCall
82 import Outputable
83 import Module
84 import FastString
85 import Demand
86
87 -- infixl so you can say (id `set` a `set` b)
88 infixl 1 `setRuleInfo`,
89 `setArityInfo`,
90 `setInlinePragInfo`,
91 `setUnfoldingInfo`,
92 `setOneShotInfo`,
93 `setOccInfo`,
94 `setCafInfo`,
95 `setStrictnessInfo`,
96 `setDemandInfo`
97
98 {-
99 ************************************************************************
100 * *
101 IdDetails
102 * *
103 ************************************************************************
104 -}
105
106 -- | The 'IdDetails' of an 'Id' give stable, and necessary,
107 -- information about the Id.
108 data IdDetails
109 = VanillaId
110
111 -- | The 'Id' for a record selector
112 | RecSelId
113 { sel_tycon :: RecSelParent
114 , sel_naughty :: Bool -- True <=> a "naughty" selector which can't actually exist, for example @x@ in:
115 -- data T = forall a. MkT { x :: a }
116 } -- See Note [Naughty record selectors] in TcTyClsDecls
117
118 | DataConWorkId DataCon -- ^ The 'Id' is for a data constructor /worker/
119 | DataConWrapId DataCon -- ^ The 'Id' is for a data constructor /wrapper/
120
121 -- [the only reasons we need to know is so that
122 -- a) to support isImplicitId
123 -- b) when desugaring a RecordCon we can get
124 -- from the Id back to the data con]
125 | ClassOpId Class -- ^ The 'Id' is a superclass selector,
126 -- or class operation of a class
127
128 | PrimOpId PrimOp -- ^ The 'Id' is for a primitive operator
129 | FCallId ForeignCall -- ^ The 'Id' is for a foreign call
130
131 | TickBoxOpId TickBoxOp -- ^ The 'Id' is for a HPC tick box (both traditional and binary)
132
133 | DFunId Bool -- ^ A dictionary function.
134 -- Bool = True <=> the class has only one method, so may be
135 -- implemented with a newtype, so it might be bad
136 -- to be strict on this dictionary
137
138 -- The rest are distinguished only for debugging reasons
139 -- e.g. to suppress them in -ddump-types
140 -- Currently we don't persist these through interface file
141 -- (see MkIface.toIfaceIdDetails), but we easily could if it mattered
142
143 | DefMethId -- ^ A default-method Id, either polymorphic or generic
144
145 | ReflectionId -- ^ A top-level Id to support runtime reflection
146 -- e.g. $trModule, or $tcT
147
148 | PatSynId -- ^ A top-level Id to support pattern synonyms;
149 -- the builder or matcher for the patern synonym
150
151
152 data RecSelParent = RecSelData TyCon | RecSelPatSyn PatSyn deriving Eq
153 -- Either `TyCon` or `PatSyn` depending
154 -- on the origin of the record selector.
155 -- For a data type family, this is the
156 -- /instance/ 'TyCon' not the family 'TyCon'
157
158 instance Outputable RecSelParent where
159 ppr p = case p of
160 RecSelData ty_con -> ppr ty_con
161 RecSelPatSyn ps -> ppr ps
162
163
164
165 coVarDetails :: IdDetails
166 coVarDetails = VanillaId
167
168 instance Outputable IdDetails where
169 ppr = pprIdDetails
170
171 pprIdDetails :: IdDetails -> SDoc
172 pprIdDetails VanillaId = empty
173 pprIdDetails other = brackets (pp other)
174 where
175 pp VanillaId = panic "pprIdDetails"
176 pp DefMethId = ptext (sLit "DefMethId")
177 pp ReflectionId = ptext (sLit "ReflectionId")
178 pp PatSynId = ptext (sLit "PatSynId")
179 pp (DataConWorkId _) = ptext (sLit "DataCon")
180 pp (DataConWrapId _) = ptext (sLit "DataConWrapper")
181 pp (ClassOpId {}) = ptext (sLit "ClassOp")
182 pp (PrimOpId _) = ptext (sLit "PrimOp")
183 pp (FCallId _) = ptext (sLit "ForeignCall")
184 pp (TickBoxOpId _) = ptext (sLit "TickBoxOp")
185 pp (DFunId nt) = ptext (sLit "DFunId") <> ppWhen nt (ptext (sLit "(nt)"))
186 pp (RecSelId { sel_naughty = is_naughty })
187 = brackets $ ptext (sLit "RecSel")
188 <> ppWhen is_naughty (ptext (sLit "(naughty)"))
189
190 {-
191 ************************************************************************
192 * *
193 \subsection{The main IdInfo type}
194 * *
195 ************************************************************************
196 -}
197
198 -- | An 'IdInfo' gives /optional/ information about an 'Id'. If
199 -- present it never lies, but it may not be present, in which case there
200 -- is always a conservative assumption which can be made.
201 --
202 -- Two 'Id's may have different info even though they have the same
203 -- 'Unique' (and are hence the same 'Id'); for example, one might lack
204 -- the properties attached to the other.
205 --
206 -- Most of the 'IdInfo' gives information about the value, or definition, of
207 -- the 'Id', independent of its usage. Exceptions to this
208 -- are 'demandInfo', 'occInfo', 'oneShotInfo' and 'callArityInfo'.
209 data IdInfo
210 = IdInfo {
211 arityInfo :: !ArityInfo, -- ^ 'Id' arity
212 ruleInfo :: RuleInfo, -- ^ Specialisations of the 'Id's function which exist
213 -- See Note [Specialisations and RULES in IdInfo]
214 unfoldingInfo :: Unfolding, -- ^ The 'Id's unfolding
215 cafInfo :: CafInfo, -- ^ 'Id' CAF info
216 oneShotInfo :: OneShotInfo, -- ^ Info about a lambda-bound variable, if the 'Id' is one
217 inlinePragInfo :: InlinePragma, -- ^ Any inline pragma atached to the 'Id'
218 occInfo :: OccInfo, -- ^ How the 'Id' occurs in the program
219
220 strictnessInfo :: StrictSig, -- ^ A strictness signature
221
222 demandInfo :: Demand, -- ^ ID demand information
223 callArityInfo :: !ArityInfo -- ^ How this is called.
224 -- n <=> all calls have at least n arguments
225 }
226
227 -- Setters
228
229 setRuleInfo :: IdInfo -> RuleInfo -> IdInfo
230 setRuleInfo info sp = sp `seq` info { ruleInfo = sp }
231 setInlinePragInfo :: IdInfo -> InlinePragma -> IdInfo
232 setInlinePragInfo info pr = pr `seq` info { inlinePragInfo = pr }
233 setOccInfo :: IdInfo -> OccInfo -> IdInfo
234 setOccInfo info oc = oc `seq` info { occInfo = oc }
235 -- Try to avoid spack leaks by seq'ing
236
237 setUnfoldingInfoLazily :: IdInfo -> Unfolding -> IdInfo
238 setUnfoldingInfoLazily info uf -- Lazy variant to avoid looking at the
239 = -- unfolding of an imported Id unless necessary
240 info { unfoldingInfo = uf } -- (In this case the demand-zapping is redundant.)
241
242 setUnfoldingInfo :: IdInfo -> Unfolding -> IdInfo
243 setUnfoldingInfo info uf
244 = -- We don't seq the unfolding, as we generate intermediate
245 -- unfoldings which are just thrown away, so evaluating them is a
246 -- waste of time.
247 -- seqUnfolding uf `seq`
248 info { unfoldingInfo = uf }
249
250 setArityInfo :: IdInfo -> ArityInfo -> IdInfo
251 setArityInfo info ar = info { arityInfo = ar }
252 setCallArityInfo :: IdInfo -> ArityInfo -> IdInfo
253 setCallArityInfo info ar = info { callArityInfo = ar }
254 setCafInfo :: IdInfo -> CafInfo -> IdInfo
255 setCafInfo info caf = info { cafInfo = caf }
256
257 setOneShotInfo :: IdInfo -> OneShotInfo -> IdInfo
258 setOneShotInfo info lb = {-lb `seq`-} info { oneShotInfo = lb }
259
260 setDemandInfo :: IdInfo -> Demand -> IdInfo
261 setDemandInfo info dd = dd `seq` info { demandInfo = dd }
262
263 setStrictnessInfo :: IdInfo -> StrictSig -> IdInfo
264 setStrictnessInfo info dd = dd `seq` info { strictnessInfo = dd }
265
266 -- | Basic 'IdInfo' that carries no useful information whatsoever
267 vanillaIdInfo :: IdInfo
268 vanillaIdInfo
269 = IdInfo {
270 cafInfo = vanillaCafInfo,
271 arityInfo = unknownArity,
272 ruleInfo = emptyRuleInfo,
273 unfoldingInfo = noUnfolding,
274 oneShotInfo = NoOneShotInfo,
275 inlinePragInfo = defaultInlinePragma,
276 occInfo = NoOccInfo,
277 demandInfo = topDmd,
278 strictnessInfo = nopSig,
279 callArityInfo = unknownArity
280 }
281
282 -- | More informative 'IdInfo' we can use when we know the 'Id' has no CAF references
283 noCafIdInfo :: IdInfo
284 noCafIdInfo = vanillaIdInfo `setCafInfo` NoCafRefs
285 -- Used for built-in type Ids in MkId.
286
287 {-
288 ************************************************************************
289 * *
290 \subsection[arity-IdInfo]{Arity info about an @Id@}
291 * *
292 ************************************************************************
293
294 For locally-defined Ids, the code generator maintains its own notion
295 of their arities; so it should not be asking... (but other things
296 besides the code-generator need arity info!)
297 -}
298
299 -- | An 'ArityInfo' of @n@ tells us that partial application of this
300 -- 'Id' to up to @n-1@ value arguments does essentially no work.
301 --
302 -- That is not necessarily the same as saying that it has @n@ leading
303 -- lambdas, because coerces may get in the way.
304 --
305 -- The arity might increase later in the compilation process, if
306 -- an extra lambda floats up to the binding site.
307 type ArityInfo = Arity
308
309 -- | It is always safe to assume that an 'Id' has an arity of 0
310 unknownArity :: Arity
311 unknownArity = 0 :: Arity
312
313 ppArityInfo :: Int -> SDoc
314 ppArityInfo 0 = empty
315 ppArityInfo n = hsep [ptext (sLit "Arity"), int n]
316
317 {-
318 ************************************************************************
319 * *
320 \subsection{Inline-pragma information}
321 * *
322 ************************************************************************
323 -}
324
325 -- | Tells when the inlining is active.
326 -- When it is active the thing may be inlined, depending on how
327 -- big it is.
328 --
329 -- If there was an @INLINE@ pragma, then as a separate matter, the
330 -- RHS will have been made to look small with a Core inline 'Note'
331 --
332 -- The default 'InlinePragInfo' is 'AlwaysActive', so the info serves
333 -- entirely as a way to inhibit inlining until we want it
334 type InlinePragInfo = InlinePragma
335
336 {-
337 ************************************************************************
338 * *
339 Strictness
340 * *
341 ************************************************************************
342 -}
343
344 pprStrictness :: StrictSig -> SDoc
345 pprStrictness sig = ppr sig
346
347 {-
348 ************************************************************************
349 * *
350 RuleInfo
351 * *
352 ************************************************************************
353
354 Note [Specialisations and RULES in IdInfo]
355 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
356 Generally speaking, a GlobalId has an *empty* RuleInfo. All their
357 RULES are contained in the globally-built rule-base. In principle,
358 one could attach the to M.f the RULES for M.f that are defined in M.
359 But we don't do that for instance declarations and so we just treat
360 them all uniformly.
361
362 The EXCEPTION is PrimOpIds, which do have rules in their IdInfo. That is
363 jsut for convenience really.
364
365 However, LocalIds may have non-empty RuleInfo. We treat them
366 differently because:
367 a) they might be nested, in which case a global table won't work
368 b) the RULE might mention free variables, which we use to keep things alive
369
370 In TidyPgm, when the LocalId becomes a GlobalId, its RULES are stripped off
371 and put in the global list.
372 -}
373
374 -- | Records the specializations of this 'Id' that we know about
375 -- in the form of rewrite 'CoreRule's that target them
376 data RuleInfo
377 = RuleInfo
378 [CoreRule]
379 DVarSet -- Locally-defined free vars of *both* LHS and RHS
380 -- of rules. I don't think it needs to include the
381 -- ru_fn though.
382 -- Note [Rule dependency info] in OccurAnal
383
384 -- | Assume that no specilizations exist: always safe
385 emptyRuleInfo :: RuleInfo
386 emptyRuleInfo = RuleInfo [] emptyDVarSet
387
388 isEmptyRuleInfo :: RuleInfo -> Bool
389 isEmptyRuleInfo (RuleInfo rs _) = null rs
390
391 -- | Retrieve the locally-defined free variables of both the left and
392 -- right hand sides of the specialization rules
393 ruleInfoFreeVars :: RuleInfo -> DVarSet
394 ruleInfoFreeVars (RuleInfo _ fvs) = fvs
395
396 ruleInfoRules :: RuleInfo -> [CoreRule]
397 ruleInfoRules (RuleInfo rules _) = rules
398
399 -- | Change the name of the function the rule is keyed on on all of the 'CoreRule's
400 setRuleInfoHead :: Name -> RuleInfo -> RuleInfo
401 setRuleInfoHead fn (RuleInfo rules fvs)
402 = RuleInfo (map (setRuleIdName fn) rules) fvs
403
404 {-
405 ************************************************************************
406 * *
407 \subsection[CG-IdInfo]{Code generator-related information}
408 * *
409 ************************************************************************
410 -}
411
412 -- CafInfo is used to build Static Reference Tables (see simplStg/SRT.hs).
413
414 -- | Records whether an 'Id' makes Constant Applicative Form references
415 data CafInfo
416 = MayHaveCafRefs -- ^ Indicates that the 'Id' is for either:
417 --
418 -- 1. A function or static constructor
419 -- that refers to one or more CAFs, or
420 --
421 -- 2. A real live CAF
422
423 | NoCafRefs -- ^ A function or static constructor
424 -- that refers to no CAFs.
425 deriving (Eq, Ord)
426
427 -- | Assumes that the 'Id' has CAF references: definitely safe
428 vanillaCafInfo :: CafInfo
429 vanillaCafInfo = MayHaveCafRefs
430
431 mayHaveCafRefs :: CafInfo -> Bool
432 mayHaveCafRefs MayHaveCafRefs = True
433 mayHaveCafRefs _ = False
434
435 instance Outputable CafInfo where
436 ppr = ppCafInfo
437
438 ppCafInfo :: CafInfo -> SDoc
439 ppCafInfo NoCafRefs = ptext (sLit "NoCafRefs")
440 ppCafInfo MayHaveCafRefs = empty
441
442 {-
443 ************************************************************************
444 * *
445 \subsection{Bulk operations on IdInfo}
446 * *
447 ************************************************************************
448 -}
449
450 -- | This is used to remove information on lambda binders that we have
451 -- setup as part of a lambda group, assuming they will be applied all at once,
452 -- but turn out to be part of an unsaturated lambda as in e.g:
453 --
454 -- > (\x1. \x2. e) arg1
455 zapLamInfo :: IdInfo -> Maybe IdInfo
456 zapLamInfo info@(IdInfo {occInfo = occ, demandInfo = demand})
457 | is_safe_occ occ && is_safe_dmd demand
458 = Nothing
459 | otherwise
460 = Just (info {occInfo = safe_occ, demandInfo = topDmd})
461 where
462 -- The "unsafe" occ info is the ones that say I'm not in a lambda
463 -- because that might not be true for an unsaturated lambda
464 is_safe_occ (OneOcc in_lam _ _) = in_lam
465 is_safe_occ _other = True
466
467 safe_occ = case occ of
468 OneOcc _ once int_cxt -> OneOcc insideLam once int_cxt
469 _other -> occ
470
471 is_safe_dmd dmd = not (isStrictDmd dmd)
472
473 -- | Remove all demand info on the 'IdInfo'
474 zapDemandInfo :: IdInfo -> Maybe IdInfo
475 zapDemandInfo info = Just (info {demandInfo = topDmd})
476
477 -- | Remove usage (but not strictness) info on the 'IdInfo'
478 zapUsageInfo :: IdInfo -> Maybe IdInfo
479 zapUsageInfo info = Just (info {demandInfo = zapUsageDemand (demandInfo info)})
480
481 zapFragileInfo :: IdInfo -> Maybe IdInfo
482 -- ^ Zap info that depends on free variables
483 zapFragileInfo info
484 = Just (info `setRuleInfo` emptyRuleInfo
485 `setUnfoldingInfo` noUnfolding
486 `setOccInfo` zapFragileOcc occ)
487 where
488 occ = occInfo info
489
490 {-
491 ************************************************************************
492 * *
493 \subsection{TickBoxOp}
494 * *
495 ************************************************************************
496 -}
497
498 type TickBoxId = Int
499
500 -- | Tick box for Hpc-style coverage
501 data TickBoxOp
502 = TickBox Module {-# UNPACK #-} !TickBoxId
503
504 instance Outputable TickBoxOp where
505 ppr (TickBox mod n) = ptext (sLit "tick") <+> ppr (mod,n)