2 % (c) The AQUA Project, Glasgow University, 1994-1996
4 \section[CoreUnfold]{Core-syntax unfoldings}
6 Unfoldings (which can travel across module boundaries) are in Core
7 syntax (namely @CoreExpr@s).
9 The type @Unfolding@ sits ``above'' simply-Core-expressions
10 unfoldings, capturing ``higher-level'' things we know about a binding,
11 usually things that the simplifier found out (e.g., ``it's a
12 literal''). In the corner of a @CoreUnfolding@ unfolding, you will
13 find, unsurprisingly, a Core expression.
17 Unfolding(..), UnfoldingGuidance(..), -- types
19 FormSummary(..), mkFormSummary, whnfOrBottom, exprSmallEnoughToDup,
22 noUnfolding, mkMagicUnfolding, mkUnfolding, getUnfoldingTemplate,
24 smallEnoughToInline, couldBeSmallEnoughToInline,
25 certainlySmallEnoughToInline, inlineUnconditionally, okToInline,
30 #include "HsVersions.h"
32 import {-# SOURCE #-} MagicUFs ( MagicUnfoldingFun, mkMagicUnfoldingFun )
34 import CmdLineOpts ( opt_UnfoldingCreationThreshold,
35 opt_UnfoldingUseThreshold,
36 opt_UnfoldingConDiscount,
37 opt_UnfoldingKeenessFactor
39 import Constants ( uNFOLDING_CHEAP_OP_COST,
40 uNFOLDING_DEAR_OP_COST,
41 uNFOLDING_NOREP_LIT_COST
43 import BinderInfo ( BinderInfo, isOneSameSCCFunOcc, isDeadOcc,
44 isInlinableOcc, isOneSafeFunOcc
47 import Literal ( Literal )
48 import CoreUtils ( unTagBinders )
49 import OccurAnal ( occurAnalyseGlobalExpr )
50 import CoreUtils ( coreExprType )
51 import Id ( Id, idType, getIdArity, isBottomingId, isDataCon,
52 idWantsToBeINLINEd, idMustBeINLINEd, idMustNotBeINLINEd,
54 import PrimOp ( fragilePrimOp, primOpCanTriggerGC )
55 import IdInfo ( ArityInfo(..), InlinePragInfo(..) )
56 import Name ( isExported )
57 import Literal ( isNoRepLit )
58 import TyCon ( tyConFamilySize )
59 import Type ( splitAlgTyConApp_maybe )
60 import Unique ( Unique )
61 import Util ( isIn, panic, assertPanic )
65 import List ( maximumBy )
69 %************************************************************************
71 \subsection{@Unfolding@ and @UnfoldingGuidance@ types}
73 %************************************************************************
79 | OtherLit [Literal] -- It ain't one of these
80 | OtherCon [Id] -- It ain't one of these
82 | CoreUnfolding -- An unfolding with redundant cached information
83 FormSummary -- Tells whether the template is a WHNF or bottom
84 UnfoldingGuidance -- Tells about the *size* of the template.
85 SimplifiableCoreExpr -- Template
88 Unique -- Unique of the Id whose magic unfolding this is
93 noUnfolding = NoUnfolding
97 -- strictness mangling (depends on there being no CSE)
98 ufg = calcUnfoldingGuidance opt_UnfoldingCreationThreshold expr
99 occ = occurAnalyseGlobalExpr expr
100 cuf = CoreUnfolding (mkFormSummary expr) ufg occ
102 cont = case occ of { Var _ -> cuf; _ -> cuf }
104 case ufg of { UnfoldAlways -> cont; _ -> cont }
106 mkMagicUnfolding :: Unique -> Unfolding
107 mkMagicUnfolding tag = MagicUnfolding tag (mkMagicUnfoldingFun tag)
109 getUnfoldingTemplate :: Unfolding -> CoreExpr
110 getUnfoldingTemplate (CoreUnfolding _ _ expr)
112 getUnfoldingTemplate other = panic "getUnfoldingTemplate"
115 data UnfoldingGuidance
117 | UnfoldAlways -- There is no "original" definition,
118 -- so you'd better unfold. Or: something
119 -- so cheap to unfold (e.g., 1#) that
120 -- you should do it absolutely always.
122 | UnfoldIfGoodArgs Int -- if "m" type args
123 Int -- and "n" value args
125 [Int] -- Discount if the argument is evaluated.
126 -- (i.e., a simplification will definitely
127 -- be possible). One elt of the list per *value* arg.
129 Int -- The "size" of the unfolding; to be elaborated
132 Int -- Scrutinee discount: the discount to substract if the thing is in
133 -- a context (case (thing args) of ...),
134 -- (where there are the right number of arguments.)
138 instance Outputable UnfoldingGuidance where
139 ppr UnfoldAlways = ptext SLIT("_ALWAYS_")
140 ppr (UnfoldIfGoodArgs t v cs size discount)
141 = hsep [ptext SLIT("_IF_ARGS_"), int t, int v,
142 if null cs -- always print *something*
144 else hcat (map (text . show) cs),
150 %************************************************************************
152 \subsection{Figuring out things about expressions}
154 %************************************************************************
158 = VarForm -- Expression is a variable (or scc var, etc)
159 | ValueForm -- Expression is a value: i.e. a value-lambda,constructor, or literal
160 | BottomForm -- Expression is guaranteed to be bottom. We're more gung
161 -- ho about inlining such things, because it can't waste work
162 | OtherForm -- Anything else
164 instance Outputable FormSummary where
165 ppr VarForm = ptext SLIT("Var")
166 ppr ValueForm = ptext SLIT("Value")
167 ppr BottomForm = ptext SLIT("Bot")
168 ppr OtherForm = ptext SLIT("Other")
170 mkFormSummary ::GenCoreExpr bndr Id flexi -> FormSummary
173 = go (0::Int) expr -- The "n" is the number of (value) arguments so far
175 go n (Lit _) = ASSERT(n==0) ValueForm
176 go n (Con _ _) = ASSERT(n==0) ValueForm
177 go n (Prim _ _) = OtherForm
178 go n (Note _ e) = go n e
180 go n (Let (NonRec b r) e) | exprIsTrivial r = go n e -- let f = f' alpha in (f,g)
181 -- should be treated as a value
182 go n (Let _ e) = OtherForm
183 go n (Case _ _) = OtherForm
185 go 0 (Lam (ValBinder x) e) = ValueForm -- NB: \x.bottom /= bottom!
186 go n (Lam (ValBinder x) e) = go (n-1) e -- Applied lambda
187 go n (Lam other_binder e) = go n e
189 go n (App fun arg) | isValArg arg = go (n+1) fun
190 go n (App fun other_arg) = go n fun
192 go n (Var f) | isBottomingId f = BottomForm
193 | isDataCon f = ValueForm -- Can happen inside imported unfoldings
194 go 0 (Var f) = VarForm
195 go n (Var f) = case getIdArity f of
196 ArityExactly a | n < a -> ValueForm
197 ArityAtLeast a | n < a -> ValueForm
200 whnfOrBottom :: FormSummary -> Bool
201 whnfOrBottom VarForm = True
202 whnfOrBottom ValueForm = True
203 whnfOrBottom BottomForm = True
204 whnfOrBottom OtherForm = False
207 @exprIsTrivial@ is true of expressions we are unconditionally happy to duplicate;
208 simple variables and constants, and type applications.
211 exprIsTrivial (Var v) = True
212 exprIsTrivial (Lit lit) = not (isNoRepLit lit)
213 exprIsTrivial (App e (TyArg _)) = exprIsTrivial e
214 exprIsTrivial (Note _ e) = exprIsTrivial e
215 exprIsTrivial other = False
219 exprSmallEnoughToDup (Con _ _) = True -- Could check # of args
220 exprSmallEnoughToDup (Prim op _) = not (fragilePrimOp op) -- Could check # of args
221 exprSmallEnoughToDup (Lit lit) = not (isNoRepLit lit)
222 exprSmallEnoughToDup (Note _ e) = exprSmallEnoughToDup e
223 exprSmallEnoughToDup expr
224 = case (collectArgs expr) of { (fun, _, vargs) ->
226 Var v | length vargs <= 4 -> True
233 %************************************************************************
235 \subsection[calcUnfoldingGuidance]{Calculate ``unfolding guidance'' for an expression}
237 %************************************************************************
240 calcUnfoldingGuidance
241 :: Int -- bomb out if size gets bigger than this
242 -> CoreExpr -- expression to look at
245 calcUnfoldingGuidance bOMB_OUT_SIZE expr
246 = case collectBinders expr of { (ty_binders, val_binders, body) ->
247 case (sizeExpr bOMB_OUT_SIZE val_binders body) of
249 TooBig -> UnfoldNever
251 SizeIs size cased_args scrut_discount
252 -> {- trace ("calcUnfoldingGuidance: \n" ++ showSDoc (ppr expr) ++ "\n"
253 ++ show (I# size) ++ "\n" ++ show (map discount_for val_binders)) $ -}
257 (map discount_for val_binders)
262 | is_data = case lookupUFM cased_args b of
268 = case (splitAlgTyConApp_maybe (idType b)) of
269 Nothing -> (False, panic "discount")
270 Just (tc,_,_) -> (True, tc)
275 sizeExpr :: Int -- Bomb out if it gets bigger than this
276 -> [Id] -- Arguments; we're interested in which of these
281 sizeExpr (I# bOMB_OUT_SIZE) args expr
284 size_up (Var v) = sizeZero
285 size_up (Lit lit) | isNoRepLit lit = sizeN uNFOLDING_NOREP_LIT_COST
286 | otherwise = sizeZero
288 size_up (Note _ body) = size_up body -- Notes cost nothing
290 size_up (App fun arg) = size_up fun `addSize` size_up_arg arg
291 -- NB Zero cost for for type applications;
292 -- others cost 1 or more
294 size_up (Con con args) = conSizeN (numValArgs args)
295 -- We don't count 1 for the constructor because we're
296 -- quite keen to get constructors into the open
298 size_up (Prim op args) = sizeN op_cost -- NB: no charge for PrimOp args
300 op_cost = if primOpCanTriggerGC op
301 then uNFOLDING_DEAR_OP_COST
302 -- these *tend* to be more expensive;
303 -- number chosen to avoid unfolding (HACK)
304 else uNFOLDING_CHEAP_OP_COST
306 size_up expr@(Lam _ _)
308 (tyvars, args, body) = collectBinders expr
310 size_up body `addSizeN` length args
312 size_up (Let (NonRec binder rhs) body)
313 = nukeScrutDiscount (size_up rhs)
317 1 -- For the allocation
319 size_up (Let (Rec pairs) body)
320 = nukeScrutDiscount (foldr addSize sizeZero [size_up rhs | (_,rhs) <- pairs])
324 length pairs -- For the allocation
326 size_up (Case scrut alts)
327 = nukeScrutDiscount (size_up scrut)
329 size_up_alts scrut (coreExprType scrut) alts
330 -- We charge for the "case" itself in "size_up_alts"
333 -- In an application we charge 0 for type application
334 -- 1 for most anything else
336 size_up_arg (LitArg lit) | isNoRepLit lit = sizeN uNFOLDING_NOREP_LIT_COST
337 size_up_arg (TyArg _) = sizeZero
338 size_up_arg other = sizeOne
341 size_up_alts scrut scrut_ty (AlgAlts alts deflt)
348 alts_sizes = size_up_deflt deflt : map size_alg_alt alts
349 total_size = foldr addSize sizeZero alts_sizes
351 biggest_alt = maximumBy (\a b -> if ltSize a b then b else a) alts_sizes
353 scrut_discount (Var v) | v `is_elem` args =
354 scrutArg v (minusSize total_size biggest_alt + alt_cost)
355 scrut_discount _ = sizeZero
358 size_alg_alt (con,args,rhs) = size_up rhs
359 -- Don't charge for args, so that wrappers look cheap
361 -- NB: we charge N for an alg. "case", where N is
362 -- the number of constructors in the thing being eval'd.
363 -- (You'll eventually get a "discount" of N if you
364 -- think the "case" is likely to go away.)
365 -- It's important to charge for alternatives. If you don't then you
366 -- get size 1 for things like:
367 -- case x of { A -> 1#; B -> 2#; ... lots }
371 = case (splitAlgTyConApp_maybe scrut_ty) of
373 Just (tc,_,_) -> tyConFamilySize tc
375 size_up_alts _ _ (PrimAlts alts deflt)
376 = foldr (addSize . size_prim_alt) (size_up_deflt deflt) alts
377 -- *no charge* for a primitive "case"!
379 size_prim_alt (lit,rhs) = size_up rhs
382 size_up_deflt NoDefault = sizeZero
383 size_up_deflt (BindDefault binder rhs) = size_up rhs
386 is_elem :: Id -> [Id] -> Bool
387 is_elem = isIn "size_up_scrut"
390 -- These addSize things have to be here because
391 -- I don't want to give them bOMB_OUT_SIZE as an argument
393 addSizeN TooBig _ = TooBig
394 addSizeN (SizeIs n xs d) (I# m)
395 | n_tot -# d <# bOMB_OUT_SIZE = SizeIs n_tot xs d
400 -- trying to find a reasonable discount for eliminating this case.
401 -- if the case is eliminated, in the worse case we end up with the
402 -- largest alternative, so subtract the size of the largest alternative
403 -- from the total size of the case to end up with the discount
404 minusSize TooBig _ = 0
405 minusSize _ TooBig = panic "CoreUnfold: minusSize" -- shouldn't happen
406 minusSize (SizeIs n1 xs d1) (SizeIs n2 ys d2) = I# (n1 -# n2)
408 addSize TooBig _ = TooBig
409 addSize _ TooBig = TooBig
410 addSize (SizeIs n1 xs d1) (SizeIs n2 ys d2)
411 | (n_tot -# d_tot) <# bOMB_OUT_SIZE = SizeIs n_tot xys d_tot
416 xys = combineArgDiscounts xs ys
422 Code for manipulating sizes
426 data ExprSize = TooBig
427 | SizeIs Int# -- Size found
428 (UniqFM Int) -- discount for each argument
429 Int# -- Size to subtract if result is scrutinised
430 -- by a case expression
432 ltSize a TooBig = True
433 ltSize TooBig a = False
434 ltSize (SizeIs s1# _ _) (SizeIs s2# _ _) = s1# <=# s2#
436 sizeZero = SizeIs 0# emptyUFM 0#
437 sizeOne = SizeIs 1# emptyUFM 0#
438 sizeN (I# n) = SizeIs n emptyUFM 0#
439 conSizeN (I# n) = SizeIs n emptyUFM n
440 scrutArg v d = SizeIs 0# (unitUFM v d) 0#
442 nukeScrutDiscount (SizeIs n vs d) = SizeIs n vs 0#
443 nukeScrutDiscount TooBig = TooBig
445 combineArgDiscounts :: UniqFM Int -> UniqFM Int -> UniqFM Int
446 combineArgDiscounts = plusUFM_C (+)
449 %************************************************************************
451 \subsection[considerUnfolding]{Given all the info, do (not) do the unfolding}
453 %************************************************************************
455 We have very limited information about an unfolding expression: (1)~so
456 many type arguments and so many value arguments expected---for our
457 purposes here, we assume we've got those. (2)~A ``size'' or ``cost,''
458 a single integer. (3)~An ``argument info'' vector. For this, what we
459 have at the moment is a Boolean per argument position that says, ``I
460 will look with great favour on an explicit constructor in this
461 position.'' (4)~The ``discount'' to subtract if the expression
462 is being scrutinised.
464 Assuming we have enough type- and value arguments (if not, we give up
465 immediately), then we see if the ``discounted size'' is below some
466 (semi-arbitrary) threshold. It works like this: for every argument
467 position where we're looking for a constructor AND WE HAVE ONE in our
468 hands, we get a (again, semi-arbitrary) discount [proportion to the
469 number of constructors in the type being scrutinized].
471 If we're in the context of a scrutinee ( \tr{(case <expr > of A .. -> ...;.. )})
472 and the expression in question will evaluate to a constructor, we use
473 the computed discount size *for the result only* rather than
474 computing the argument discounts. Since we know the result of
475 the expression is going to be taken apart, discounting its size
476 is more accurate (see @sizeExpr@ above for how this discount size
480 smallEnoughToInline :: Id -- The function (trace msg only)
481 -> [Bool] -- Evaluated-ness of value arguments
482 -> Bool -- Result is scrutinised
484 -> Bool -- True => unfold it
486 smallEnoughToInline _ _ _ UnfoldAlways = True
487 smallEnoughToInline _ _ _ UnfoldNever = False
488 smallEnoughToInline id arg_is_evald_s result_is_scruted
489 (UnfoldIfGoodArgs m_tys_wanted n_vals_wanted discount_vec size scrut_discount)
490 = if enough_args n_vals_wanted arg_is_evald_s &&
491 size - discount <= opt_UnfoldingUseThreshold
493 -- pprTrace "small enough" (ppr id <+> int size <+> int discount)
499 enough_args n [] | n > 0 = False -- A function with no value args => don't unfold
500 enough_args _ _ = True -- Otherwise it's ok to try
502 -- We multiple the raw discounts (args_discount and result_discount)
503 -- ty opt_UnfoldingKeenessFactor because the former have to do with
504 -- *size* whereas the discounts imply that there's some extra *efficiency*
505 -- to be gained (e.g. beta reductions, case reductions) by inlining.
508 opt_UnfoldingKeenessFactor *
509 fromInt (args_discount + result_discount)
512 args_discount = sum (zipWith arg_discount discount_vec arg_is_evald_s)
513 result_discount | result_is_scruted = scrut_discount
516 arg_discount discount is_evald
517 | is_evald = discount
521 We use this one to avoid exporting inlinings that we ``couldn't possibly
522 use'' on the other side. Can be overridden w/ flaggery.
523 Just the same as smallEnoughToInline, except that it has no actual arguments.
526 couldBeSmallEnoughToInline :: Id -> UnfoldingGuidance -> Bool
527 couldBeSmallEnoughToInline id guidance = smallEnoughToInline id (repeat True) True guidance
529 certainlySmallEnoughToInline :: Id -> UnfoldingGuidance -> Bool
530 certainlySmallEnoughToInline id guidance = smallEnoughToInline id (repeat False) False guidance
536 @inlineUnconditionally@ decides whether a let-bound thing can
537 *definitely* be inlined at each of its call sites. If so, then
538 we can drop the binding right away. But remember, you have to be
539 certain that every use can be inlined. So, notably, any ArgOccs
540 rule this out. Since ManyOcc doesn't record FunOcc/ArgOcc
543 inlineUnconditionally :: (Id,BinderInfo) -> Bool
545 inlineUnconditionally (id, occ_info)
546 | idMustNotBeINLINEd id
550 | isOneSameSCCFunOcc occ_info
551 && idWantsToBeINLINEd id = True
553 | isOneSafeFunOcc occ_info
560 okToInline is used at call sites, so it is a bit more generous
563 okToInline :: Id -- The Id
564 -> Bool -- The thing is WHNF or bottom;
565 -> Bool -- It's small enough to duplicate the code
567 -> Bool -- True <=> inline it
569 okToInline id _ _ _ -- Check the Id first
570 | idWantsToBeINLINEd id = True
571 | idMustNotBeINLINEd id = False
573 okToInline id whnf small binder_info
575 | isDeadOcc binder_info
576 = pprTrace "okToInline: dead" (ppr id) False
579 = isInlinableOcc whnf small binder_info