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
17 exactArity, atLeastArity, unknownArity,
18 arityInfo, setArityInfo, ppArityInfo, arityLowerBound,
21 StrictnessInfo(..), -- Non-abstract
23 noStrictnessInfo, strictnessInfo,
24 ppStrictnessInfo, setStrictnessInfo,
25 isBottomingStrictness, appIsBottom,
28 WorkerInfo, workerExists,
29 workerInfo, setWorkerInfo,
32 unfoldingInfo, setUnfoldingInfo,
35 demandInfo, setDemandInfo,
38 InlinePragInfo(..), OccInfo(..),
39 inlinePragInfo, setInlinePragInfo, notInsideLambda,
42 IdSpecEnv, specInfo, setSpecInfo,
45 UpdateInfo, UpdateSpec,
46 mkUpdateInfo, updateInfo, updateInfoMaybe, ppUpdateInfo, setUpdateInfo,
49 CafInfo(..), cafInfo, setCafInfo, ppCafInfo,
51 -- Constructed Product Result Info
52 CprInfo(..), cprInfo, setCprInfo, ppCprInfo, noCprInfo
55 #include "HsVersions.h"
58 import {-# SOURCE #-} CoreUnfold ( Unfolding, noUnfolding )
59 import {-# SOURCE #-} CoreSyn ( CoreExpr )
62 import SpecEnv ( SpecEnv, emptySpecEnv )
63 import Demand ( Demand, isLazy, wwLazy, pprDemands )
66 import Maybe ( isJust )
70 An @IdInfo@ gives {\em optional} information about an @Id@. If
71 present it never lies, but it may not be present, in which case there
72 is always a conservative assumption which can be made.
74 Two @Id@s may have different info even though they have the same
75 @Unique@ (and are hence the same @Id@); for example, one might lack
76 the properties attached to the other.
78 The @IdInfo@ gives information about the value, or definition, of the
79 @Id@. It does {\em not} contain information about the @Id@'s usage
80 (except for @DemandInfo@? ToDo).
85 arityInfo :: ArityInfo, -- Its arity
86 demandInfo :: Demand, -- Whether or not it is definitely demanded
87 specInfo :: IdSpecEnv, -- Specialisations of this function which exist
88 strictnessInfo :: StrictnessInfo, -- Strictness properties
89 workerInfo :: WorkerInfo, -- Pointer to Worker Function
90 unfoldingInfo :: Unfolding, -- Its unfolding
91 updateInfo :: UpdateInfo, -- Which args should be updated
93 cprInfo :: CprInfo, -- Function always constructs a product result
94 inlinePragInfo :: !InlinePragInfo -- Inline pragmas
101 setUpdateInfo ud info = info { updateInfo = ud }
102 setDemandInfo dd info = info { demandInfo = dd }
103 setStrictnessInfo st info = info { strictnessInfo = st }
104 setWorkerInfo wk info = info { workerInfo = wk }
105 setSpecInfo sp info = info { specInfo = sp }
106 setArityInfo ar info = info { arityInfo = ar }
107 setInlinePragInfo pr info = info { inlinePragInfo = pr }
108 setUnfoldingInfo uf info = info { unfoldingInfo = uf }
109 setCafInfo cf info = info { cafInfo = cf }
110 setCprInfo cp info = info { cprInfo = cp }
116 arityInfo = UnknownArity,
118 specInfo = emptySpecEnv,
119 strictnessInfo = NoStrictnessInfo,
120 workerInfo = noWorkerInfo,
121 unfoldingInfo = noUnfolding,
122 updateInfo = NoUpdateInfo,
123 cafInfo = MayHaveCafRefs,
125 inlinePragInfo = NoInlinePragInfo
129 %************************************************************************
131 \subsection[arity-IdInfo]{Arity info about an @Id@}
133 %************************************************************************
135 For locally-defined Ids, the code generator maintains its own notion
136 of their arities; so it should not be asking... (but other things
137 besides the code-generator need arity info!)
141 = UnknownArity -- No idea
142 | ArityExactly Int -- Arity is exactly this
143 | ArityAtLeast Int -- Arity is this or greater
145 exactArity = ArityExactly
146 atLeastArity = ArityAtLeast
147 unknownArity = UnknownArity
149 arityLowerBound :: ArityInfo -> Int
150 arityLowerBound UnknownArity = 0
151 arityLowerBound (ArityAtLeast n) = n
152 arityLowerBound (ArityExactly n) = n
155 ppArityInfo UnknownArity = empty
156 ppArityInfo (ArityExactly arity) = hsep [ptext SLIT("__A"), int arity]
157 ppArityInfo (ArityAtLeast arity) = hsep [ptext SLIT("__AL"), int arity]
160 %************************************************************************
162 \subsection{Inline-pragma information}
164 %************************************************************************
170 | IAmASpecPragmaId -- Used for spec-pragma Ids; don't discard or inline
172 | IWantToBeINLINEd -- User INLINE pragma
173 | IMustNotBeINLINEd -- User NOINLINE pragma
175 | IAmALoopBreaker -- Used by the occurrence analyser to mark loop-breakers
176 -- in a group of recursive definitions
178 | ICanSafelyBeINLINEd -- Used by the occurrence analyser to mark things
179 -- that manifesly occur once, not inside SCCs,
180 -- not in constructor arguments
182 OccInfo -- Says whether the occurrence is inside a lambda
183 -- If so, must only substitute WHNFs
185 Bool -- False <=> occurs in more than one case branch
186 -- If so, there's a code-duplication issue
188 | IAmDead -- Marks unused variables. Sometimes useful for
189 -- lambda and case-bound variables.
191 | IMustBeINLINEd -- Absolutely must inline; used for PrimOps and
192 -- constructors only.
194 instance Outputable InlinePragInfo where
195 ppr NoInlinePragInfo = empty
196 ppr IMustBeINLINEd = ptext SLIT("__UU")
197 ppr IWantToBeINLINEd = ptext SLIT("__U")
198 ppr IMustNotBeINLINEd = ptext SLIT("__Unot")
199 ppr IAmALoopBreaker = ptext SLIT("__Ux")
200 ppr IAmDead = ptext SLIT("__Ud")
201 ppr (ICanSafelyBeINLINEd InsideLam _) = ptext SLIT("__Ul")
202 ppr (ICanSafelyBeINLINEd _ _) = ptext SLIT("__Us")
203 ppr IAmASpecPragmaId = ptext SLIT("__US")
205 instance Show InlinePragInfo where
206 showsPrec p prag = showsPrecSDoc p (ppr prag)
209 The @IMustNotBeDiscarded@ exists only to make Ids that are
210 on the *LHS* of bindings created by SPECIALISE pragmas;
212 The SpecPragmaId is never itself mentioned; it
213 exists solely so that the specialiser will find
214 the call to f, and make specialised version of it.
215 The SpecPragmaId binding is discarded by the specialiser
216 when it gathers up overloaded calls.
217 Meanwhile, it is not discarded as dead code.
221 = StrictOcc -- Occurs syntactically strictly;
222 -- i.e. in a function position or case scrutinee
224 | LazyOcc -- Not syntactically strict (*even* that of a strict function)
225 -- or in a case branch where there's more than one alternative
227 | InsideLam -- Inside a non-linear lambda (that is, a lambda which
228 -- is sure to be instantiated only once).
229 -- Substituting a redex for this occurrence is
230 -- dangerous because it might duplicate work.
232 instance Outputable OccInfo where
233 ppr StrictOcc = text "s"
235 ppr InsideLam = text "l"
238 notInsideLambda :: OccInfo -> Bool
239 notInsideLambda StrictOcc = True
240 notInsideLambda LazyOcc = True
241 notInsideLambda InsideLam = False
244 %************************************************************************
246 \subsection[specialisation-IdInfo]{Specialisation info about an @Id@}
248 %************************************************************************
250 A @IdSpecEnv@ holds details of an @Id@'s specialisations.
253 type IdSpecEnv = SpecEnv CoreExpr
256 For example, if \tr{f}'s @SpecEnv@ contains the mapping:
258 [List a, b] ===> (\d -> f' a b)
260 then when we find an application of f to matching types, we simply replace
261 it by the matching RHS:
263 f (List Int) Bool ===> (\d -> f' Int Bool)
265 All the stuff about how many dictionaries to discard, and what types
266 to apply the specialised function to, are handled by the fact that the
267 SpecEnv contains a template for the result of the specialisation.
269 There is one more exciting case, which is dealt with in exactly the same
270 way. If the specialised value is unboxed then it is lifted at its
271 definition site and unlifted at its uses. For example:
273 pi :: forall a. Num a => a
275 might have a specialisation
277 [Int#] ===> (case pi' of Lift pi# -> pi#)
279 where pi' :: Lift Int# is the specialised version of pi.
282 %************************************************************************
284 \subsection[strictness-IdInfo]{Strictness info about an @Id@}
286 %************************************************************************
288 We specify the strictness of a function by giving information about
289 each of the ``wrapper's'' arguments (see the description about
290 worker/wrapper-style transformations in the PJ/Launchbury paper on
293 The list of @Demands@ specifies: (a)~the strictness properties of a
294 function's arguments; and (b)~the type signature of that worker (if it
295 exists); i.e. its calling convention.
297 Note that the existence of a worker function is now denoted by the Id's
304 | StrictnessInfo [Demand]
305 Bool -- True <=> the function diverges regardless of its arguments
306 -- Useful for "error" and other disguised variants thereof.
307 -- BUT NB: f = \x y. error "urk"
308 -- will have info SI [SS] True
309 -- but still (f) and (f 2) are not bot; only (f 3 2) is bot
313 mkStrictnessInfo :: ([Demand], Bool) -> StrictnessInfo
315 mkStrictnessInfo (xs, is_bot)
316 | all isLazy xs && not is_bot = NoStrictnessInfo -- Uninteresting
317 | otherwise = StrictnessInfo xs is_bot
319 noStrictnessInfo = NoStrictnessInfo
321 isBottomingStrictness (StrictnessInfo _ bot) = bot
322 isBottomingStrictness NoStrictnessInfo = False
324 -- appIsBottom returns true if an application to n args would diverge
325 appIsBottom (StrictnessInfo ds bot) n = bot && (n >= length ds)
326 appIsBottom NoStrictnessInfo n = False
328 ppStrictnessInfo NoStrictnessInfo = empty
329 ppStrictnessInfo (StrictnessInfo wrapper_args bot)
330 = hsep [ptext SLIT("__S"), pprDemands wrapper_args bot]
333 %************************************************************************
335 \subsection[worker-IdInfo]{Worker info about an @Id@}
337 %************************************************************************
339 If this Id has a worker then we store a reference to it. Worker
340 functions are generated by the worker/wrapper pass. This uses
341 information from the strictness and CPR analyses.
343 There might not be a worker, even for a strict function, because:
344 (a) the function might be small enough to inline, so no need
346 (b) the strictness info might be "SSS" or something, so no w/w split.
350 type WorkerInfo = Maybe Id
353 mkWorkerInfo :: Id -> WorkerInfo
354 mkWorkerInfo wk_id = Just wk_id
356 ppWorkerInfo Nothing = empty
357 ppWorkerInfo (Just wk_id) = ppr wk_id
360 noWorkerInfo = Nothing
362 workerExists :: Maybe Id -> Bool
363 workerExists = isJust
367 %************************************************************************
369 \subsection[update-IdInfo]{Update-analysis info about an @Id@}
371 %************************************************************************
376 | SomeUpdateInfo UpdateSpec
378 -- we need Eq/Ord to cross-chk update infos in interfaces
380 -- the form in which we pass update-analysis info between modules:
381 type UpdateSpec = [Int]
385 mkUpdateInfo = SomeUpdateInfo
387 updateInfoMaybe NoUpdateInfo = Nothing
388 updateInfoMaybe (SomeUpdateInfo []) = Nothing
389 updateInfoMaybe (SomeUpdateInfo u) = Just u
392 Text instance so that the update annotations can be read in.
395 ppUpdateInfo NoUpdateInfo = empty
396 ppUpdateInfo (SomeUpdateInfo []) = empty
397 ppUpdateInfo (SomeUpdateInfo spec) = (<>) (ptext SLIT("__U ")) (hcat (map int spec))
400 %************************************************************************
402 \subsection[CAF-IdInfo]{CAF-related information}
404 %************************************************************************
406 This information is used to build Static Reference Tables (see
407 simplStg/ComputeSRT.lhs).
411 = MayHaveCafRefs -- either:
412 -- (1) A function or static constructor
413 -- that refers to one or more CAFs,
414 -- (2) A real live CAF
416 | NoCafRefs -- A function or static constructor
417 -- that refers to no CAFs.
419 -- LATER: not sure how easy this is...
423 ppCafInfo NoCafRefs = ptext SLIT("__C")
424 ppCafInfo MayHaveCafRefs = empty
427 %************************************************************************
429 \subsection[cpr-IdInfo]{Constructed Product Result info about an @Id@}
431 %************************************************************************
433 If the @Id@ is a function then it may have CPR info. A CPR analysis
434 phase detects whether:
438 The function's return value has a product type, i.e. an algebraic type
439 with a single constructor. Examples of such types are tuples and boxed
442 The function always 'constructs' the value that it is returning. It
443 must do this on every path through, and it's OK if it calls another
444 function which constructs the result.
447 If this is the case then we store a template which tells us the
448 function has the CPR property and which components of the result are
457 -- e.g. const 5 == CPRInfo [NoCPRInfo]
464 -- CPRInfo [CPRInfo [NoCPRInfo],
465 -- CPRInfo [NoCprInfo,
466 -- CPRInfo [NoCPRInfo],
474 noCprInfo = NoCPRInfo
476 ppCprInfo NoCPRInfo = empty
477 ppCprInfo c@(CPRInfo _)
478 = hsep [ptext SLIT("__M"), ppCprInfo' c]
480 ppCprInfo' NoCPRInfo = char '-'
481 ppCprInfo' (CPRInfo args) = parens (hcat (map ppCprInfo' args))
483 instance Outputable CprInfo where
486 instance Show CprInfo where
487 showsPrec p c = showsPrecSDoc p (ppr c)