[project @ 1998-05-22 15:23:11 by simonm]
[ghc-hetmet.git] / ghc / compiler / coreSyn / CoreUnfold.lhs
1 %
2 % (c) The AQUA Project, Glasgow University, 1994-1996
3 %
4 \section[CoreUnfold]{Core-syntax unfoldings}
5
6 Unfoldings (which can travel across module boundaries) are in Core
7 syntax (namely @CoreExpr@s).
8
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.
14
15 \begin{code}
16 module CoreUnfold (
17         Unfolding(..), UnfoldingGuidance(..), -- types
18
19         FormSummary(..), mkFormSummary, whnfOrBottom, exprSmallEnoughToDup, 
20         exprIsTrivial,
21
22         noUnfolding, mkMagicUnfolding, mkUnfolding, getUnfoldingTemplate,
23
24         smallEnoughToInline, couldBeSmallEnoughToInline, 
25         certainlySmallEnoughToInline, inlineUnconditionally, okToInline,
26
27         calcUnfoldingGuidance
28     ) where
29
30 #include "HsVersions.h"
31
32 import {-# SOURCE #-} MagicUFs  ( MagicUnfoldingFun, mkMagicUnfoldingFun )
33
34 import CmdLineOpts      ( opt_UnfoldingCreationThreshold,
35                           opt_UnfoldingUseThreshold,
36                           opt_UnfoldingConDiscount,
37                           opt_UnfoldingKeenessFactor
38                         )
39 import Constants        ( uNFOLDING_CHEAP_OP_COST,
40                           uNFOLDING_DEAR_OP_COST,
41                           uNFOLDING_NOREP_LIT_COST
42                         )
43 import BinderInfo       ( BinderInfo, isOneSameSCCFunOcc, isDeadOcc,
44                           isInlinableOcc, isOneSafeFunOcc
45                         )
46 import CoreSyn
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,
53                           IdSet )
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 )
62 import UniqFM
63 import Outputable
64
65 import List             ( maximumBy )
66 import GlaExts --tmp
67 \end{code}
68
69 %************************************************************************
70 %*                                                                      *
71 \subsection{@Unfolding@ and @UnfoldingGuidance@ types}
72 %*                                                                      *
73 %************************************************************************
74
75 \begin{code}
76 data Unfolding
77   = NoUnfolding
78
79   | OtherLit [Literal]          -- It ain't one of these
80   | OtherCon [Id]               -- It ain't one of these
81
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
86
87   | MagicUnfolding
88         Unique                          -- Unique of the Id whose magic unfolding this is
89         MagicUnfoldingFun
90 \end{code}
91
92 \begin{code}
93 noUnfolding = NoUnfolding
94
95 mkUnfolding expr
96   = let
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
101                                           
102      cont = case occ of { Var _ -> cuf; _ -> cuf }
103     in
104     case ufg of { UnfoldAlways -> cont; _ -> cont }
105
106 mkMagicUnfolding :: Unique -> Unfolding
107 mkMagicUnfolding tag  = MagicUnfolding tag (mkMagicUnfoldingFun tag)
108
109 getUnfoldingTemplate :: Unfolding -> CoreExpr
110 getUnfoldingTemplate (CoreUnfolding _ _ expr)
111   = unTagBinders expr
112 getUnfoldingTemplate other = panic "getUnfoldingTemplate"
113
114
115 data UnfoldingGuidance
116   = UnfoldNever
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.
121
122   | UnfoldIfGoodArgs    Int     -- if "m" type args 
123                         Int     -- and "n" value args
124
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.
128
129                         Int     -- The "size" of the unfolding; to be elaborated
130                                 -- later. ToDo
131
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.)
135 \end{code}
136
137 \begin{code}
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*
143                 then char 'X'
144                 else hcat (map (text . show) cs),
145                int size,
146                int discount ]
147 \end{code}
148
149
150 %************************************************************************
151 %*                                                                      *
152 \subsection{Figuring out things about expressions}
153 %*                                                                      *
154 %************************************************************************
155
156 \begin{code}
157 data FormSummary
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
163
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")
169
170 mkFormSummary ::GenCoreExpr bndr Id flexi -> FormSummary
171
172 mkFormSummary expr
173   = go (0::Int) expr            -- The "n" is the number of (value) arguments so far
174   where
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
179
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
184
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
188
189     go n (App fun arg) | isValArg arg = go (n+1) fun
190     go n (App fun other_arg)          = go n fun
191
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
198                                           other                  -> OtherForm
199
200 whnfOrBottom :: FormSummary -> Bool
201 whnfOrBottom VarForm    = True
202 whnfOrBottom ValueForm  = True
203 whnfOrBottom BottomForm = True
204 whnfOrBottom OtherForm  = False
205 \end{code}
206
207 @exprIsTrivial@ is true of expressions we are unconditionally happy to duplicate;
208 simple variables and constants, and type applications.
209
210 \begin{code}
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
216 \end{code}
217
218 \begin{code}
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) ->
225     case fun of
226       Var v | length vargs <= 4 -> True
227       _                         -> False
228     }
229
230 \end{code}
231
232
233 %************************************************************************
234 %*                                                                      *
235 \subsection[calcUnfoldingGuidance]{Calculate ``unfolding guidance'' for an expression}
236 %*                                                                      *
237 %************************************************************************
238
239 \begin{code}
240 calcUnfoldingGuidance
241         :: Int                  -- bomb out if size gets bigger than this
242         -> CoreExpr             -- expression to look at
243         -> UnfoldingGuidance
244
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
248
249       TooBig -> UnfoldNever
250
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)) $ -}
254            UnfoldIfGoodArgs
255                         (length ty_binders)
256                         (length val_binders)
257                         (map discount_for val_binders)
258                         (I# size)
259                         (I# scrut_discount)
260         where        
261             discount_for b
262                  | is_data = case lookupUFM cased_args b of
263                                 Nothing -> 0
264                                 Just d  -> d
265                  | otherwise = 0
266                  where
267                    (is_data, tycon)
268                      = case (splitAlgTyConApp_maybe (idType b)) of
269                           Nothing       -> (False, panic "discount")
270                           Just (tc,_,_) -> (True,  tc)
271     }
272 \end{code}
273
274 \begin{code}
275 sizeExpr :: Int             -- Bomb out if it gets bigger than this
276          -> [Id]            -- Arguments; we're interested in which of these
277                             -- get case'd
278          -> CoreExpr
279          -> ExprSize
280
281 sizeExpr (I# bOMB_OUT_SIZE) args expr
282   = size_up expr
283   where
284     size_up (Var v)                    = sizeZero
285     size_up (Lit lit) | isNoRepLit lit = sizeN uNFOLDING_NOREP_LIT_COST
286                       | otherwise      = sizeZero
287
288     size_up (Note _ body)  = size_up body               -- Notes cost nothing
289
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
293
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
297                              
298     size_up (Prim op args) = sizeN op_cost -- NB: no charge for PrimOp args
299       where
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
305
306     size_up expr@(Lam _ _)
307       = let
308             (tyvars, args, body) = collectBinders expr
309         in
310         size_up body `addSizeN` length args
311
312     size_up (Let (NonRec binder rhs) body)
313       = nukeScrutDiscount (size_up rhs)
314                 `addSize`
315         size_up body
316                 `addSizeN`
317         1       -- For the allocation
318
319     size_up (Let (Rec pairs) body)
320       = nukeScrutDiscount (foldr addSize sizeZero [size_up rhs | (_,rhs) <- pairs])
321                 `addSize`
322         size_up body
323                 `addSizeN`
324         length pairs    -- For the allocation
325
326     size_up (Case scrut alts)
327       = nukeScrutDiscount (size_up scrut)
328                 `addSize`
329         size_up_alts scrut (coreExprType scrut) alts
330             -- We charge for the "case" itself in "size_up_alts"
331
332     ------------
333         -- In an application we charge  0 for type application
334         --                              1 for most anything else
335         --                              N for norep_lits
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
339
340     ------------
341     size_up_alts scrut scrut_ty (AlgAlts alts deflt)
342       = total_size
343         `addSize`
344         scrut_discount scrut
345         `addSizeN`
346         alt_cost
347       where
348         alts_sizes = size_up_deflt deflt : map size_alg_alt alts
349         total_size = foldr addSize sizeZero alts_sizes
350
351         biggest_alt = maximumBy (\a b -> if ltSize a b then b else a) alts_sizes
352
353         scrut_discount (Var v) | v `is_elem` args = 
354                 scrutArg v (minusSize total_size biggest_alt + alt_cost)
355         scrut_discount _ = sizeZero
356                                 
357
358         size_alg_alt (con,args,rhs) = size_up rhs
359             -- Don't charge for args, so that wrappers look cheap
360
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 }
368
369         alt_cost :: Int
370         alt_cost
371           = case (splitAlgTyConApp_maybe scrut_ty) of
372               Nothing       -> 1
373               Just (tc,_,_) -> tyConFamilySize tc
374
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"!
378       where
379         size_prim_alt (lit,rhs) = size_up rhs
380
381     ------------
382     size_up_deflt NoDefault                = sizeZero
383     size_up_deflt (BindDefault binder rhs) = size_up rhs
384
385     ------------
386     is_elem :: Id -> [Id] -> Bool
387     is_elem = isIn "size_up_scrut"
388
389     ------------
390         -- These addSize things have to be here because
391         -- I don't want to give them bOMB_OUT_SIZE as an argument
392
393     addSizeN TooBig          _ = TooBig
394     addSizeN (SizeIs n xs d) (I# m)
395       | n_tot -# d <# bOMB_OUT_SIZE = SizeIs n_tot xs d
396       | otherwise                   = TooBig
397       where
398         n_tot = n +# m
399     
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)
407
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
412       | otherwise                         = TooBig
413       where
414         n_tot = n1 +# n2
415         d_tot = d1 +# d2
416         xys   = combineArgDiscounts xs ys
417
418     
419
420 \end{code}
421
422 Code for manipulating sizes
423
424 \begin{code}
425
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
431
432 ltSize a TooBig = True
433 ltSize TooBig a = False
434 ltSize (SizeIs s1# _ _) (SizeIs s2# _ _) = s1# <=# s2#
435
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#
441
442 nukeScrutDiscount (SizeIs n vs d) = SizeIs n vs 0#
443 nukeScrutDiscount TooBig          = TooBig
444
445 combineArgDiscounts :: UniqFM Int -> UniqFM Int -> UniqFM Int
446 combineArgDiscounts = plusUFM_C (+)
447 \end{code}
448
449 %************************************************************************
450 %*                                                                      *
451 \subsection[considerUnfolding]{Given all the info, do (not) do the unfolding}
452 %*                                                                      *
453 %************************************************************************
454
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. 
463
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].
470
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
477 is computed).
478
479 \begin{code}
480 smallEnoughToInline :: Id                       -- The function (trace msg only)
481                     -> [Bool]                   -- Evaluated-ness of value arguments
482                     -> Bool                     -- Result is scrutinised
483                     -> UnfoldingGuidance
484                     -> Bool                     -- True => unfold it
485
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
492     then
493        -- pprTrace "small enough" (ppr id <+> int size <+> int discount) 
494        True
495     else
496        False
497   where
498
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
501
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.
506     discount :: Int
507     discount = round (
508                       opt_UnfoldingKeenessFactor * 
509                       fromInt (args_discount + result_discount)
510                      )
511
512     args_discount = sum (zipWith arg_discount discount_vec arg_is_evald_s)
513     result_discount | result_is_scruted = scrut_discount
514                     | otherwise         = 0
515
516     arg_discount discount is_evald
517       | is_evald  = discount
518       | otherwise = 0
519 \end{code}
520
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.
524
525 \begin{code}
526 couldBeSmallEnoughToInline :: Id -> UnfoldingGuidance -> Bool
527 couldBeSmallEnoughToInline id guidance = smallEnoughToInline id (repeat True) True guidance
528
529 certainlySmallEnoughToInline :: Id -> UnfoldingGuidance -> Bool
530 certainlySmallEnoughToInline id guidance = smallEnoughToInline id (repeat False) False guidance
531 \end{code}
532
533 Predicates
534 ~~~~~~~~~~
535
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 
541
542 \begin{code}
543 inlineUnconditionally :: (Id,BinderInfo) -> Bool
544
545 inlineUnconditionally (id, occ_info)
546   |  idMustNotBeINLINEd id 
547   || isExported id
548   =  False
549
550   |  isOneSameSCCFunOcc occ_info
551   && idWantsToBeINLINEd id = True
552
553   |  isOneSafeFunOcc occ_info
554   =  True
555
556   |  otherwise
557   = False
558 \end{code}
559
560 okToInline is used at call sites, so it is a bit more generous
561
562 \begin{code}
563 okToInline :: Id                -- The Id
564            -> Bool              -- The thing is WHNF or bottom; 
565            -> Bool              -- It's small enough to duplicate the code
566            -> BinderInfo
567            -> Bool              -- True <=> inline it
568
569 okToInline id _ _ _             -- Check the Id first
570   | idWantsToBeINLINEd id = True
571   | idMustNotBeINLINEd id = False
572
573 okToInline id whnf small binder_info 
574 #ifdef DEBUG
575   | isDeadOcc binder_info
576   = pprTrace "okToInline: dead" (ppr id) False
577   | otherwise
578 #endif
579   = isInlinableOcc whnf small binder_info
580 \end{code}