CoreUnfold.lhs 49.4 KB
Newer Older
1
%
Simon Marlow's avatar
Simon Marlow committed
2
% (c) The University of Glasgow 2006
3
4
% (c) The AQUA Project, Glasgow University, 1994-1998
%
Simon Marlow's avatar
Simon Marlow committed
5
6

Core-syntax unfoldings
7
8
9
10
11
12
13
14
15
16
17
18

Unfoldings (which can travel across module boundaries) are in Core
syntax (namely @CoreExpr@s).

The type @Unfolding@ sits ``above'' simply-Core-expressions
unfoldings, capturing ``higher-level'' things we know about a binding,
usually things that the simplifier found out (e.g., ``it's a
literal'').  In the corner of a @CoreUnfolding@ unfolding, you will
find, unsurprisingly, a Core expression.

\begin{code}
module CoreUnfold (
19
	Unfolding, UnfoldingGuidance,	-- Abstract types
20

21
	noUnfolding, mkImplicitUnfolding, 
22
23
24
        mkUnfolding, mkCoreUnfolding,
	mkTopUnfolding, mkSimpleUnfolding,
	mkInlineUnfolding, mkInlinableUnfolding, mkWwInlineRule,
25
	mkCompulsoryUnfolding, mkDFunUnfolding,
26

27
28
	interestingArg, ArgSummary(..),

29
	couldBeSmallEnoughToInline, inlineBoringOk,
30
	certainlyWillInline, smallEnoughToInline,
31

32
	callSiteInline, CallCtxt(..), 
33

34
35
	exprIsConApp_maybe

36
37
    ) where

38
39
#include "HsVersions.h"

Simon Marlow's avatar
Simon Marlow committed
40
41
import StaticFlags
import DynFlags
42
import CoreSyn
43
import PprCore		()	-- Instances
44
45
import TcType           ( tcSplitDFunTy )
import OccurAnal        ( occurAnalyseExpr )
46
import CoreSubst hiding( substTy )
47
import CoreFVs         ( exprFreeVars )
48
import CoreArity       ( manifestArity, exprBotStrictness_maybe )
Simon Marlow's avatar
Simon Marlow committed
49
50
51
import CoreUtils
import Id
import DataCon
52
import TyCon
Simon Marlow's avatar
Simon Marlow committed
53
54
55
import Literal
import PrimOp
import IdInfo
56
import BasicTypes	( Arity )
57
import Type
58
import Coercion
Simon Marlow's avatar
Simon Marlow committed
59
import PrelNames
60
import VarEnv           ( mkInScopeSet )
61
import Bag
62
import Util
63
import FastTypes
64
import FastString
65
import Outputable
66
import Data.Maybe
67
68
\end{code}

69

70
71
%************************************************************************
%*									*
72
\subsection{Making unfoldings}
73
74
75
76
%*									*
%************************************************************************

\begin{code}
77
mkTopUnfolding :: Bool -> CoreExpr -> Unfolding
78
mkTopUnfolding = mkUnfolding InlineRhs True {- Top level -}
79

80
81
mkImplicitUnfolding :: CoreExpr -> Unfolding
-- For implicit Ids, do a tiny bit of optimising first
82
mkImplicitUnfolding expr = mkTopUnfolding False (simpleOptExpr expr) 
Simon Marlow's avatar
Simon Marlow committed
83

84
85
86
87
88
-- Note [Top-level flag on inline rules]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Slight hack: note that mk_inline_rules conservatively sets the
-- top-level flag to True.  It gets set more accurately by the simplifier
-- Simplify.simplUnfolding.
89

90
91
mkSimpleUnfolding :: CoreExpr -> Unfolding
mkSimpleUnfolding = mkUnfolding InlineRhs False False
92

93
mkDFunUnfolding :: Type -> [DFunArg CoreExpr] -> Unfolding
94
95
96
mkDFunUnfolding dfun_ty ops 
  = DFunUnfolding dfun_nargs data_con ops
  where
97
98
    (tvs, n_theta, cls, _) = tcSplitDFunTy dfun_ty
    dfun_nargs = length tvs + n_theta
99
    data_con   = classDataCon cls
Simon Marlow's avatar
Simon Marlow committed
100

101
102
mkWwInlineRule :: Id -> CoreExpr -> Arity -> Unfolding
mkWwInlineRule id expr arity
103
  = mkCoreUnfolding (InlineWrapper id) True
104
105
                   (simpleOptExpr expr) arity
                   (UnfWhen unSaturatedOk boringCxtNotOk)
106

twanvl's avatar
twanvl committed
107
mkCompulsoryUnfolding :: CoreExpr -> Unfolding
108
mkCompulsoryUnfolding expr	   -- Used for things that absolutely must be unfolded
109
  = mkCoreUnfolding InlineCompulsory True
110
111
                    expr 0    -- Arity of unfolding doesn't matter
                    (UnfWhen unSaturatedOk boringCxtOk)
112

113
114
mkInlineUnfolding :: Maybe Arity -> CoreExpr -> Unfolding
mkInlineUnfolding mb_arity expr 
115
116
  = mkCoreUnfolding InlineStable
    		    True 	 -- Note [Top-level flag on inline rules]
117
                    expr' arity 
118
		    (UnfWhen unsat_ok boring_ok)
119
120
  where
    expr' = simpleOptExpr expr
121
122
123
124
    (unsat_ok, arity) = case mb_arity of
                          Nothing -> (unSaturatedOk, manifestArity expr')
                          Just ar -> (needSaturated, ar)
              
125
    boring_ok = inlineBoringOk expr'
126
127
128

mkInlinableUnfolding :: CoreExpr -> Unfolding
mkInlinableUnfolding expr
129
  = mkUnfolding InlineStable True is_bot expr'
130
  where
131
132
    expr' = simpleOptExpr expr
    is_bot = isJust (exprBotStrictness_maybe expr')
133
\end{code}
134

135
136
137
Internal functions

\begin{code}
138
mkCoreUnfolding :: UnfoldingSource -> Bool -> CoreExpr
139
140
                -> Arity -> UnfoldingGuidance -> Unfolding
-- Occurrence-analyses the expression before capturing it
141
mkCoreUnfolding src top_lvl expr arity guidance 
142
143
144
145
146
147
148
149
150
151
152
153
154
155
  = CoreUnfolding { uf_tmpl   	  = occurAnalyseExpr expr,
    		    uf_src        = src,
    		    uf_arity      = arity,
		    uf_is_top 	  = top_lvl,
		    uf_is_value   = exprIsHNF        expr,
                    uf_is_conlike = exprIsConLike    expr,
		    uf_is_cheap   = exprIsCheap      expr,
		    uf_expandable = exprIsExpandable expr,
		    uf_guidance   = guidance }

mkUnfolding :: UnfoldingSource -> Bool -> Bool -> CoreExpr -> Unfolding
-- Calculates unfolding guidance
-- Occurrence-analyses the expression before capturing it
mkUnfolding src top_lvl is_bottoming expr
156
157
158
159
  | top_lvl && is_bottoming
  , not (exprIsTrivial expr)
  = NoUnfolding    -- See Note [Do not inline top-level bottoming functions]
  | otherwise
160
161
162
163
164
165
166
167
168
169
170
  = CoreUnfolding { uf_tmpl   	  = occurAnalyseExpr expr,
    		    uf_src        = src,
    		    uf_arity      = arity,
		    uf_is_top 	  = top_lvl,
		    uf_is_value   = exprIsHNF        expr,
                    uf_is_conlike = exprIsConLike    expr,
		    uf_expandable = exprIsExpandable expr,
		    uf_is_cheap   = is_cheap,
		    uf_guidance   = guidance }
  where
    is_cheap = exprIsCheap expr
171
    (arity, guidance) = calcUnfoldingGuidance is_cheap
172
173
174
175
176
177
178
179
180
181
182
                                              opt_UF_CreationThreshold expr
	-- Sometimes during simplification, there's a large let-bound thing	
	-- which has been substituted, and so is now dead; so 'expr' contains
	-- two copies of the thing while the occurrence-analysed expression doesn't
	-- Nevertheless, we *don't* occ-analyse before computing the size because the
	-- size computation bales out after a while, whereas occurrence analysis does not.
	--
	-- This can occasionally mean that the guidance is very pessimistic;
	-- it gets fixed up next round.  And it should be rare, because large
	-- let-bound things that are dead are usually caught by preInlineUnconditionally
\end{code}
183

184
185
186
187
188
%************************************************************************
%*									*
\subsection{The UnfoldingGuidance type}
%*									*
%************************************************************************
189
190

\begin{code}
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
inlineBoringOk :: CoreExpr -> Bool
-- See Note [INLINE for small functions]
-- True => the result of inlining the expression is 
--         no bigger than the expression itself
--     eg      (\x y -> f y x)
-- This is a quick and dirty version. It doesn't attempt
-- to deal with  (\x y z -> x (y z))
-- The really important one is (x `cast` c)
inlineBoringOk e
  = go 0 e
  where
    go :: Int -> CoreExpr -> Bool
    go credit (Lam x e) | isId x           = go (credit+1) e
                        | otherwise        = go credit e
    go credit (App f (Type {}))            = go credit f
    go credit (App f a) | credit > 0  
                        , exprIsTrivial a  = go (credit-1) f
    go credit (Note _ e) 		   = go credit e     
    go credit (Cast e _) 		   = go credit e
    go _      (Var {})         		   = boringCxtOk
    go _      _                		   = boringCxtNotOk

213
calcUnfoldingGuidance
214
215
216
217
	:: Bool		-- True <=> the rhs is cheap, or we want to treat it
	   		--          as cheap (INLINE things)	 
        -> Int		-- Bomb out if size gets bigger than this
	-> CoreExpr    	-- Expression to look at
218
	-> (Arity, UnfoldingGuidance)
219
calcUnfoldingGuidance expr_is_cheap bOMB_OUT_SIZE expr
220
  = case collectBinders expr of { (bndrs, body) ->
221
    let
222
223
224
225
226
227
228
        val_bndrs   = filter isId bndrs
	n_val_bndrs = length val_bndrs

    	guidance 
          = case (sizeExpr (iUnbox bOMB_OUT_SIZE) val_bndrs body) of
      	      TooBig -> UnfNever
      	      SizeIs size cased_bndrs scrut_discount
229
230
231
      	        | uncondInline n_val_bndrs (iBox size)
                , expr_is_cheap
      	        -> UnfWhen unSaturatedOk boringCxtOk   -- Note [INLINE for small functions]
232
233
234
235
236
237
238
239
	        | otherwise
      	        -> UnfIfGoodArgs { ug_args  = map (discount cased_bndrs) val_bndrs
      	                         , ug_size  = iBox size
      	        	  	 , ug_res   = iBox scrut_discount }

        discount cbs bndr
           = foldlBag (\acc (b',n) -> if bndr==b' then acc+n else acc) 
		      0 cbs
240
    in
241
    (n_val_bndrs, guidance) }
242
243
\end{code}

244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
Note [Computing the size of an expression]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The basic idea of sizeExpr is obvious enough: count nodes.  But getting the
heuristics right has taken a long time.  Here's the basic strategy:

    * Variables, literals: 0
      (Exception for string literals, see litSize.)

    * Function applications (f e1 .. en): 1 + #value args

    * Constructor applications: 1, regardless of #args

    * Let(rec): 1 + size of components

    * Note, cast: 0

Examples

  Size	Term
  --------------
    0	  42#
    0	  x
266
    0     True
267
268
269
270
271
272
273
274
    2	  f x
    1	  Just x
    4 	  f (g x)

Notice that 'x' counts 0, while (f x) counts 2.  That's deliberate: there's
a function call to account for.  Notice also that constructor applications 
are very cheap, because exposing them to a caller is so valuable.

275
276
277
278
279
280
281
282
283

Note [Do not inline top-level bottoming functions]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The FloatOut pass has gone to some trouble to float out calls to 'error' 
and similar friends.  See Note [Bottoming floats] in SetLevels.
Do not re-inline them!  But we *do* still inline if they are very small
(the uncondInline stuff).


284
285
286
287
288
289
290
291
292
293
294
295
296
297
Note [INLINE for small functions]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider	{-# INLINE f #-}
                f x = Just x
                g y = f y
Then f's RHS is no larger than its LHS, so we should inline it into
even the most boring context.  In general, f the function is
sufficiently small that its body is as small as the call itself, the
inline unconditionally, regardless of how boring the context is.

Things to note:

 * We inline *unconditionally* if inlined thing is smaller (using sizeExpr)
   than the thing it's replacing.  Notice that
298
299
300
301
302
303
      (f x) --> (g 3) 		  -- YES, unconditionally
      (f x) --> x : []		  -- YES, *even though* there are two
      	    	    		  --      arguments to the cons
      x     --> g 3		  -- NO
      x	    --> Just v		  -- NO

304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
  It's very important not to unconditionally replace a variable by
  a non-atomic term.

* We do this even if the thing isn't saturated, else we end up with the
  silly situation that
     f x y = x
     ...map (f 3)...
  doesn't inline.  Even in a boring context, inlining without being
  saturated will give a lambda instead of a PAP, and will be more
  efficient at runtime.

* However, when the function's arity > 0, we do insist that it 
  has at least one value argument at the call site.  Otherwise we find this:
       f = /\a \x:a. x
       d = /\b. MkD (f b)
  If we inline f here we get
       d = /\b. MkD (\x:b. x)
  and then prepareRhs floats out the argument, abstracting the type
  variables, so we end up with the original again!

324
325
326
327
328

\begin{code}
uncondInline :: Arity -> Int -> Bool
-- Inline unconditionally if there no size increase
-- Size of call is arity (+1 for the function)
329
-- See Note [INLINE for small functions]
330
331
332
333
uncondInline arity size 
  | arity == 0 = size == 0
  | otherwise  = size <= arity + 1
\end{code}
334
335


336
\begin{code}
337
sizeExpr :: FastInt 	    -- Bomb out if it gets bigger than this
338
339
340
341
342
	 -> [Id]	    -- Arguments; we're interested in which of these
			    -- get case'd
	 -> CoreExpr
	 -> ExprSize

343
344
-- Note [Computing the size of an expression]

345
sizeExpr bOMB_OUT_SIZE top_args expr
346
347
  = size_up expr
  where
348
349
    size_up (Cast e _) = size_up e
    size_up (Note _ e) = size_up e
350
351
    size_up (Type _)   = sizeZero           -- Types cost nothing
    size_up (Lit lit)  = sizeN (litSize lit)
352
    size_up (Var f)    = size_up_call f []  -- Make sure we get constructor
353
    	    	       	 	      	    -- discounts even on nullary constructors
Simon Marlow's avatar
Simon Marlow committed
354

twanvl's avatar
twanvl committed
355
    size_up (App fun (Type _)) = size_up fun
356
357
    size_up (App fun arg)      = size_up arg  `addSizeNSD`
                                 size_up_app fun [arg]
358

359
    size_up (Lam b e) | isId b    = lamScrutDiscount (size_up e `addSizeN` 1)
360
361
362
		      | otherwise = size_up e

    size_up (Let (NonRec binder rhs) body)
363
364
      = size_up rhs		`addSizeNSD`
	size_up body		`addSizeN`
365
366
367
	(if isUnLiftedType (idType binder) then 0 else 1)
		-- For the allocation
		-- If the binder has an unlifted type there is no allocation
368
369

    size_up (Let (Rec pairs) body)
370
371
372
      = foldr (addSizeNSD . size_up . snd) 
              (size_up body `addSizeN` length pairs)	-- (length pairs) for the allocation
              pairs
373

374
    size_up (Case (Var v) _ _ alts) 
375
	| v `elem` top_args		-- We are scrutinising an argument variable
376
	= alts_size (foldr1 addAltSize alt_sizes)
377
		    (foldr1 maxSize alt_sizes)
378
379
380
381
382
383
		-- Good to inline if an arg is scrutinised, because
		-- that may eliminate allocation in the caller
		-- And it eliminates the case itself
	where
	  alt_sizes = map size_up_alt alts

384
385
		-- alts_size tries to compute a good discount for
		-- the case when we are scrutinising an argument variable
386
387
388
	  alts_size (SizeIs tot tot_disc tot_scrut)  -- Size of all alternatives
		    (SizeIs max _        _)          -- Size of biggest alternative
	 	= SizeIs tot (unitBag (v, iBox (_ILIT(2) +# tot -# max)) `unionBags` tot_disc) tot_scrut
389
			-- If the variable is known, we produce a discount that
390
			-- will take us back to 'max', the size of the largest alternative
391
			-- The 1+ is a little discount for reduced allocation in the caller
392
393
394
395
			--
			-- Notice though, that we return tot_disc, the total discount from 
			-- all branches.  I think that's right.

396
397
	  alts_size tot_size _ = tot_size

398
399
    size_up (Case e _ _ alts) = size_up e  `addSizeNSD` 
                                foldr (addAltSize . size_up_alt) sizeZero alts
400
401
402
403
404
	  	-- We don't charge for the case itself
		-- It's a strict thing, and the price of the call
		-- is paid by scrut.  Also consider
		--	case f x of DEFAULT -> e
		-- This is just ';'!  Don't charge for it.
405
406
		--
		-- Moreover, we charge one per alternative.
407
408

    ------------ 
409
410
411
    -- size_up_app is used when there's ONE OR MORE value args
    size_up_app (App fun arg) args 
	| isTypeArg arg		   = size_up_app fun args
412
413
	| otherwise		   = size_up arg  `addSizeNSD`
                                     size_up_app fun (arg:args)
414
    size_up_app (Var fun)     args = size_up_call fun args
415
416
417
    size_up_app other         args = size_up other `addSizeN` length args

    ------------ 
418
419
    size_up_call :: Id -> [CoreExpr] -> ExprSize
    size_up_call fun val_args
420
421
       = case idDetails fun of
           FCallId _        -> sizeN opt_UF_DearOp
422
423
424
425
           DataConWorkId dc -> conSize    dc (length val_args)
           PrimOpId op      -> primOpSize op (length val_args)
	   ClassOpId _ 	    -> classOpSize top_args val_args
	   _     	    -> funSize top_args fun (length val_args)
426
427

    ------------ 
428
    size_up_alt (_con, _bndrs, rhs) = size_up rhs `addSizeN` 1
429
430
 	-- Don't charge for args, so that wrappers look cheap
	-- (See comments about wrappers with Case)
431
432
433
434
	--
	-- IMPORATANT: *do* charge 1 for the alternative, else we 
	-- find that giant case nests are treated as practically free
	-- A good example is Foreign.C.Error.errrnoToIOError
435
436
437
438

    ------------
	-- These addSize things have to be here because
	-- I don't want to give them bOMB_OUT_SIZE as an argument
439
440
    addSizeN TooBig          _  = TooBig
    addSizeN (SizeIs n xs d) m 	= mkSizeIs bOMB_OUT_SIZE (n +# iUnbox m) xs d
441
    
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
        -- addAltSize is used to add the sizes of case alternatives
    addAltSize TooBig	         _	= TooBig
    addAltSize _		 TooBig	= TooBig
    addAltSize (SizeIs n1 xs d1) (SizeIs n2 ys d2) 
	= mkSizeIs bOMB_OUT_SIZE (n1 +# n2) 
                                 (xs `unionBags` ys) 
                                 (d1 +# d2)   -- Note [addAltSize result discounts]

        -- This variant ignores the result discount from its LEFT argument
	-- It's used when the second argument isn't part of the result
    addSizeNSD TooBig	         _	= TooBig
    addSizeNSD _		 TooBig	= TooBig
    addSizeNSD (SizeIs n1 xs _) (SizeIs n2 ys d2) 
	= mkSizeIs bOMB_OUT_SIZE (n1 +# n2) 
                                 (xs `unionBags` ys) 
                                 d2  -- Ignore d1
458
459
460
\end{code}

\begin{code}
461
462
463
464
465
466
467
468
469
470
471
-- | Finds a nominal size of a string literal.
litSize :: Literal -> Int
-- Used by CoreUnfold.sizeExpr
litSize (MachStr str) = 1 + ((lengthFS str + 3) `div` 4)
	-- If size could be 0 then @f "x"@ might be too small
	-- [Sept03: make literal strings a bit bigger to avoid fruitless 
	--  duplication of little strings]
litSize _other = 0    -- Must match size of nullary constructors
	       	      -- Key point: if  x |-> 4, then x must inline unconditionally
		      --     	    (eg via case binding)

472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
classOpSize :: [Id] -> [CoreExpr] -> ExprSize
-- See Note [Conlike is interesting]
classOpSize _ [] 
  = sizeZero
classOpSize top_args (arg1 : other_args)
  = SizeIs (iUnbox size) arg_discount (_ILIT(0))
  where
    size = 2 + length other_args
    -- If the class op is scrutinising a lambda bound dictionary then
    -- give it a discount, to encourage the inlining of this function
    -- The actual discount is rather arbitrarily chosen
    arg_discount = case arg1 of
    		     Var dict | dict `elem` top_args 
		     	      -> unitBag (dict, opt_UF_DictDiscount)
		     _other   -> emptyBag
    		     
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
funSize :: [Id] -> Id -> Int -> ExprSize
-- Size for functions that are not constructors or primops
-- Note [Function applications]
funSize top_args fun n_val_args
  | fun `hasKey` buildIdKey   = buildSize
  | fun `hasKey` augmentIdKey = augmentSize
  | otherwise = SizeIs (iUnbox size) arg_discount (iUnbox res_discount)
  where
    some_val_args = n_val_args > 0

    arg_discount | some_val_args && fun `elem` top_args
    		 = unitBag (fun, opt_UF_FunAppDiscount)
		 | otherwise = emptyBag
	-- If the function is an argument and is applied
	-- to some values, give it an arg-discount

    res_discount | idArity fun > n_val_args = opt_UF_FunAppDiscount
    		 | otherwise   	 	    = 0
        -- If the function is partially applied, show a result discount

    size | some_val_args = 1 + n_val_args
         | otherwise     = 0
	-- The 1+ is for the function itself
	-- Add 1 for each non-trivial arg;
	-- the allocation cost, as in let(rec)
  

conSize :: DataCon -> Int -> ExprSize
conSize dc n_val_args
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
517
518
519
  | n_val_args == 0 = SizeIs (_ILIT(0)) emptyBag (_ILIT(1))	-- Like variables

-- See Note [Constructor size]
520
  | isUnboxedTupleCon dc = SizeIs (_ILIT(0)) emptyBag (iUnbox n_val_args +# _ILIT(1))
521

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
-- See Note [Unboxed tuple result discount]
--  | isUnboxedTupleCon dc = SizeIs (_ILIT(0)) emptyBag (_ILIT(0))

-- See Note [Constructor size]
  | otherwise = SizeIs (_ILIT(1)) emptyBag (iUnbox n_val_args +# _ILIT(1))
\end{code}

Note [Constructor size]
~~~~~~~~~~~~~~~~~~~~~~~
Treat a constructors application as size 1, regardless of how many
arguments it has; we are keen to expose them (and we charge separately
for their args).  We can't treat them as size zero, else we find that
(Just x) has size 0, which is the same as a lone variable; and hence
'v' will always be replaced by (Just x), where v is bound to Just x.

However, unboxed tuples count as size zero. I found occasions where we had 
	f x y z = case op# x y z of { s -> (# s, () #) }
and f wasn't getting inlined.

Note [Unboxed tuple result discount]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I tried giving unboxed tuples a *result discount* of zero (see the
commented-out line).  Why?  When returned as a result they do not
allocate, so maybe we don't want to charge so much for them If you
have a non-zero discount here, we find that workers often get inlined
back into wrappers, because it look like
    f x = case $wf x of (# a,b #) -> (a,b)
and we are keener because of the case.  However while this change
shrank binary sizes by 0.5% it also made spectral/boyer allocate 5%
more. All other changes were very small. So it's not a big deal but I
didn't adopt the idea.

\begin{code}
twanvl's avatar
twanvl committed
555
primOpSize :: PrimOp -> Int -> ExprSize
556
primOpSize op n_val_args
557
 | not (primOpIsDupable op) = sizeN opt_UF_DearOp
558
 | not (primOpOutOfLine op) = sizeN 1
559
	-- Be very keen to inline simple primops.
560
561
562
563
564
565
566
567
	-- We give a discount of 1 for each arg so that (op# x y z) costs 2.
	-- We can't make it cost 1, else we'll inline let v = (op# x y z) 
	-- at every use of v, which is excessive.
	--
	-- A good example is:
	--	let x = +# p q in C {x}
	-- Even though x get's an occurrence of 'many', its RHS looks cheap,
	-- and there's a good chance it'll get inlined back into C's RHS. Urgh!
568
569
570

 | otherwise = sizeN n_val_args

571

twanvl's avatar
twanvl committed
572
buildSize :: ExprSize
573
buildSize = SizeIs (_ILIT(0)) emptyBag (_ILIT(4))
574
575
576
577
	-- We really want to inline applications of build
	-- build t (\cn -> e) should cost only the cost of e (because build will be inlined later)
	-- Indeed, we should add a result_discount becuause build is 
	-- very like a constructor.  We don't bother to check that the
578
	-- build is saturated (it usually is).  The "-2" discounts for the \c n, 
579
	-- The "4" is rather arbitrary.
580

twanvl's avatar
twanvl committed
581
augmentSize :: ExprSize
582
augmentSize = SizeIs (_ILIT(0)) emptyBag (_ILIT(4))
583
584
	-- Ditto (augment t (\cn -> e) ys) should cost only the cost of
	-- e plus ys. The -2 accounts for the \cn 
twanvl's avatar
twanvl committed
585

586
-- When we return a lambda, give a discount if it's used (applied)
twanvl's avatar
twanvl committed
587
lamScrutDiscount :: ExprSize -> ExprSize
588
lamScrutDiscount (SizeIs n vs _) = SizeIs n vs (iUnbox opt_UF_FunAppDiscount)
twanvl's avatar
twanvl committed
589
lamScrutDiscount TooBig          = TooBig
590
591
\end{code}

592
593
594
595
596
597
598
599
600
Note [addAltSize result discounts]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When adding the size of alternatives, we *add* the result discounts
too, rather than take the *maximum*.  For a multi-branch case, this
gives a discount for each branch that returns a constructor, making us
keener to inline.  I did try using 'max' instead, but it makes nofib 
'rewrite' and 'puzzle' allocate significantly more, and didn't make
binary sizes shrink significantly either.

601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
Note [Discounts and thresholds]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Constants for discounts and thesholds are defined in main/StaticFlags,
all of form opt_UF_xxxx.   They are:

opt_UF_CreationThreshold (45)
     At a definition site, if the unfolding is bigger than this, we
     may discard it altogether

opt_UF_UseThreshold (6)
     At a call site, if the unfolding, less discounts, is smaller than
     this, then it's small enough inline

opt_UF_KeennessFactor (1.5)
     Factor by which the discounts are multiplied before 
     subtracting from size

opt_UF_DictDiscount (1)
     The discount for each occurrence of a dictionary argument
     as an argument of a class method.  Should be pretty small
     else big functions may get inlined

opt_UF_FunAppDiscount (6)
     Discount for a function argument that is applied.  Quite
     large, because if we inline we avoid the higher-order call.

opt_UF_DearOp (4)
     The size of a foreign call or not-dupable PrimOp

630

631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
Note [Function applications]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In a function application (f a b)

  - If 'f' is an argument to the function being analysed, 
    and there's at least one value arg, record a FunAppDiscount for f

  - If the application if a PAP (arity > 2 in this example)
    record a *result* discount (because inlining
    with "extra" args in the call may mean that we now 
    get a saturated application)

Code for manipulating sizes

\begin{code}
data ExprSize = TooBig
	      | SizeIs FastInt		-- Size found
		       (Bag (Id,Int))	-- Arguments cased herein, and discount for each such
		       FastInt		-- Size to subtract if result is scrutinised 
					-- by a case expression

instance Outputable ExprSize where
  ppr TooBig         = ptext (sLit "TooBig")
  ppr (SizeIs a _ c) = brackets (int (iBox a) <+> int (iBox c))

-- subtract the discount before deciding whether to bale out. eg. we
-- want to inline a large constructor application into a selector:
--  	tup = (a_1, ..., a_99)
--  	x = case tup of ...
--
mkSizeIs :: FastInt -> FastInt -> Bag (Id, Int) -> FastInt -> ExprSize
mkSizeIs max n xs d | (n -# d) ># max = TooBig
		    | otherwise	      = SizeIs n xs d
 
maxSize :: ExprSize -> ExprSize -> ExprSize
maxSize TooBig         _ 				  = TooBig
maxSize _              TooBig				  = TooBig
maxSize s1@(SizeIs n1 _ _) s2@(SizeIs n2 _ _) | n1 ># n2  = s1
					      | otherwise = s2

671
sizeZero :: ExprSize
672
673
674
675
676
677
678
sizeN :: Int -> ExprSize

sizeZero = SizeIs (_ILIT(0))  emptyBag (_ILIT(0))
sizeN n  = SizeIs (iUnbox n) emptyBag (_ILIT(0))
\end{code}


679
680
681
682
683
684
%************************************************************************
%*									*
\subsection[considerUnfolding]{Given all the info, do (not) do the unfolding}
%*									*
%************************************************************************

685
686
687
688
We use 'couldBeSmallEnoughToInline' to avoid exporting inlinings that
we ``couldn't possibly use'' on the other side.  Can be overridden w/
flaggery.  Just the same as smallEnoughToInline, except that it has no
actual arguments.
689
690

\begin{code}
691
couldBeSmallEnoughToInline :: Int -> CoreExpr -> Bool
692
couldBeSmallEnoughToInline threshold rhs 
693
694
695
696
697
  = case sizeExpr (iUnbox threshold) [] body of
       TooBig -> False
       _      -> True
  where
    (_, body) = collectBinders rhs
698

699
----------------
700
smallEnoughToInline :: Unfolding -> Bool
701
smallEnoughToInline (CoreUnfolding {uf_guidance = UnfIfGoodArgs {ug_size = size}})
702
  = size <= opt_UF_UseThreshold
twanvl's avatar
twanvl committed
703
smallEnoughToInline _
704
  = False
705
706
707
708
709
710

----------------
certainlyWillInline :: Unfolding -> Bool
  -- Sees if the unfolding is pretty certain to inline	
certainlyWillInline (CoreUnfolding { uf_is_cheap = is_cheap, uf_arity = n_vals, uf_guidance = guidance })
  = case guidance of
711
712
713
      UnfNever      -> False
      UnfWhen {}    -> True
      UnfIfGoodArgs { ug_size = size} 
714
715
716
717
                    -> is_cheap && size - (n_vals +1) <= opt_UF_UseThreshold

certainlyWillInline _
  = False
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
\end{code}

%************************************************************************
%*									*
\subsection{callSiteInline}
%*									*
%************************************************************************

This is the key function.  It decides whether to inline a variable at a call site

callSiteInline is used at call sites, so it is a bit more generous.
It's a very important function that embodies lots of heuristics.
A non-WHNF can be inlined if it doesn't occur inside a lambda,
and occurs exactly once or 
    occurs once in each branch of a case and is small

If the thing is in WHNF, there's no danger of duplicating work, 
so we can inline if it occurs once, or is small

737
NOTE: we don't want to inline top-level functions that always diverge.
738
It just makes the code bigger.  Tt turns out that the convenient way to prevent
739
740
741
them inlining is to give them a NOINLINE pragma, which we do in 
StrictAnal.addStrictnessInfoToTopId

742
\begin{code}
743
callSiteInline :: DynFlags
744
	       -> Id			-- The Id
745
	       -> Bool			-- True <=> unfolding is active
746
	       -> Bool			-- True if there are are no arguments at all (incl type args)
747
	       -> [ArgSummary]		-- One for each value arg; True if it is interesting
748
	       -> CallCtxt		-- True <=> continuation is interesting
749
750
	       -> Maybe CoreExpr	-- Unfolding, if any

751
752
753
754
755
instance Outputable ArgSummary where
  ppr TrivArg    = ptext (sLit "TrivArg")
  ppr NonTrivArg = ptext (sLit "NonTrivArg")
  ppr ValueArg   = ptext (sLit "ValueArg")

756
data CallCtxt = BoringCtxt
757

758
759
760
761
762
763
764
	      | ArgCtxt		-- We are somewhere in the argument of a function
                        Bool	-- True  <=> we're somewhere in the RHS of function with rules
				-- False <=> we *are* the argument of a function with non-zero
				-- 	     arg discount
                                --        OR 
                                --           we *are* the RHS of a let  Note [RHS of lets]
                                -- In both cases, be a little keener to inline
765

766
767
768
769
	      | ValAppCtxt 	-- We're applied to at least one value arg
				-- This arises when we have ((f x |> co) y)
				-- Then the (f x) has argument 'x' but in a ValAppCtxt

770
771
772
773
	      | CaseCtxt	-- We're the scrutinee of a case
				-- that decomposes its scrutinee

instance Outputable CallCtxt where
774
775
776
777
  ppr BoringCtxt      = ptext (sLit "BoringCtxt")
  ppr (ArgCtxt rules) = ptext (sLit "ArgCtxt") <+> ppr rules
  ppr CaseCtxt 	      = ptext (sLit "CaseCtxt")
  ppr ValAppCtxt      = ptext (sLit "ValAppCtxt")
778

779
780
781
782
783
784
785
callSiteInline dflags id active_unfolding lone_variable arg_infos cont_info
  = case idUnfolding id of 
      -- idUnfolding checks for loop-breakers, returning NoUnfolding
      -- Things with an INLINE pragma may have an unfolding *and* 
      -- be a loop breaker  (maybe the knot is not yet untied)
	CoreUnfolding { uf_tmpl = unf_template, uf_is_top = is_top 
		      , uf_is_cheap = is_cheap, uf_arity = uf_arity
786
                      , uf_guidance = guidance, uf_expandable = is_exp }
787
788
          | active_unfolding -> tryUnfolding dflags id lone_variable 
                                    arg_infos cont_info unf_template is_top 
789
                                    is_cheap is_exp uf_arity guidance
790
791
792
793
794
795
          | otherwise    -> Nothing
	NoUnfolding 	 -> Nothing 
	OtherCon {} 	 -> Nothing 
	DFunUnfolding {} -> Nothing 	-- Never unfold a DFun

tryUnfolding :: DynFlags -> Id -> Bool -> [ArgSummary] -> CallCtxt
796
             -> CoreExpr -> Bool -> Bool -> Bool -> Arity -> UnfoldingGuidance
797
798
799
	     -> Maybe CoreExpr	
tryUnfolding dflags id lone_variable 
             arg_infos cont_info unf_template is_top 
800
             is_cheap is_exp uf_arity guidance
801
802
			-- uf_arity will typically be equal to (idArity id), 
			-- but may be less for InlineRules
803
804
 | dopt Opt_D_dump_inlinings dflags && dopt Opt_D_verbose_core2core dflags
 = pprTrace ("Considering inlining: " ++ showSDoc (ppr id))
805
806
		 (vcat [text "arg infos" <+> ppr arg_infos,
			text "uf arity" <+> ppr uf_arity,
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
807
			text "interesting continuation" <+> ppr cont_info,
808
			text "some_benefit" <+> ppr some_benefit,
809
                        text "is exp:" <+> ppr is_exp,
810
                        text "is cheap:" <+> ppr is_cheap,
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
811
			text "guidance" <+> ppr guidance,
812
			extra_doc,
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
813
			text "ANSWER =" <+> if yes_or_no then text "YES" else text "NO"])
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
	         result
  | otherwise  = result

  where
    n_val_args = length arg_infos
    saturated  = n_val_args >= uf_arity

    result | yes_or_no = Just unf_template
           | otherwise = Nothing

    interesting_args = any nonTriv arg_infos 
    	-- NB: (any nonTriv arg_infos) looks at the
    	-- over-saturated args too which is "wrong"; 
    	-- but if over-saturated we inline anyway.

           -- some_benefit is used when the RHS is small enough
           -- and the call has enough (or too many) value
           -- arguments (ie n_val_args >= arity). But there must
           -- be *something* interesting about some argument, or the
           -- result context, to make it worth inlining
    some_benefit 
       | not saturated = interesting_args	-- Under-saturated
    	   	      		     	-- Note [Unsaturated applications]
       | n_val_args > uf_arity = True	-- Over-saturated
       | otherwise = interesting_args	-- Saturated
                  || interesting_saturated_call 

    interesting_saturated_call 
      = case cont_info of
843
          BoringCtxt -> not is_top && uf_arity > 0	  -- Note [Nested functions]
844
          CaseCtxt   -> not (lone_variable && is_cheap)   -- Note [Lone variables]
845
846
          ArgCtxt {} -> uf_arity > 0     		  -- Note [Inlining in ArgCtxt]
          ValAppCtxt -> True			          -- Note [Cast then apply]
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864

    (yes_or_no, extra_doc)
      = case guidance of
          UnfNever -> (False, empty)

          UnfWhen unsat_ok boring_ok 
             -> (enough_args && (boring_ok || some_benefit), empty )
             where      -- See Note [INLINE for small functions]
               enough_args = saturated || (unsat_ok && n_val_args > 0)

          UnfIfGoodArgs { ug_args = arg_discounts, ug_res = res_discount, ug_size = size }
      	     -> ( is_cheap && some_benefit && small_enough
                , (text "discounted size =" <+> int discounted_size) )
    	     where
    	       discounted_size = size - discount
    	       small_enough = discounted_size <= opt_UF_UseThreshold
    	       discount = computeDiscount uf_arity arg_discounts 
    	         		          res_discount arg_infos cont_info
865
866
\end{code}

867
868
869
870
871
872
873
874
875
Note [RHS of lets]
~~~~~~~~~~~~~~~~~~
Be a tiny bit keener to inline in the RHS of a let, because that might
lead to good thing later
     f y = (y,y,y)
     g y = let x = f y in ...(case x of (a,b,c) -> ...) ...
We'd inline 'f' if the call was in a case context, and it kind-of-is,
only we can't see it.  So we treat the RHS of a let as not-totally-boring.
    
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
Note [Unsaturated applications]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When a call is not saturated, we *still* inline if one of the
arguments has interesting structure.  That's sometimes very important.
A good example is the Ord instance for Bool in Base:

 Rec {
    $fOrdBool =GHC.Classes.D:Ord
        	 @ Bool
      		 ...
      		 $cmin_ajX

    $cmin_ajX [Occ=LoopBreaker] :: Bool -> Bool -> Bool
    $cmin_ajX = GHC.Classes.$dmmin @ Bool $fOrdBool
  }

But the defn of GHC.Classes.$dmmin is:

  $dmmin :: forall a. GHC.Classes.Ord a => a -> a -> a
    {- Arity: 3, HasNoCafRefs, Strictness: SLL,
       Unfolding: (\ @ a $dOrd :: GHC.Classes.Ord a x :: a y :: a ->
                   case @ a GHC.Classes.<= @ a $dOrd x y of wild {
Ian Lynagh's avatar
Ian Lynagh committed
898
                     GHC.Types.False -> y GHC.Types.True -> x }) -}
899
900
901
902
903

We *really* want to inline $dmmin, even though it has arity 3, in
order to unravel the recursion.


904
905
906
907
908
909
910
911
912
913
914
Note [Things to watch]
~~~~~~~~~~~~~~~~~~~~~~
*   { y = I# 3; x = y `cast` co; ...case (x `cast` co) of ... }
    Assume x is exported, so not inlined unconditionally.
    Then we want x to inline unconditionally; no reason for it 
    not to, and doing so avoids an indirection.

*   { x = I# 3; ....f x.... }
    Make sure that x does not inline unconditionally!  
    Lest we get extra allocation.

915
916
917
Note [Inlining an InlineRule]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
An InlineRules is used for
918
  (a) programmer INLINE pragmas
919
920
921
922
923
924
925
926
927
928
929
  (b) inlinings from worker/wrapper

For (a) the RHS may be large, and our contract is that we *only* inline
when the function is applied to all the arguments on the LHS of the
source-code defn.  (The uf_arity in the rule.)

However for worker/wrapper it may be worth inlining even if the 
arity is not satisfied (as we do in the CoreUnfolding case) so we don't
require saturation.


930
931
932
933
934
935
936
937
938
939
940
941
Note [Nested functions]
~~~~~~~~~~~~~~~~~~~~~~~
If a function has a nested defn we also record some-benefit, on the
grounds that we are often able to eliminate the binding, and hence the
allocation, for the function altogether; this is good for join points.
But this only makes sense for *functions*; inlining a constructor
doesn't help allocation unless the result is scrutinised.  UNLESS the
constructor occurs just once, albeit possibly in multiple case
branches.  Then inlining it doesn't increase allocation, but it does
increase the chance that the constructor won't be allocated at all in
the branches that don't use it.

942
943
944
945
946
947
948
949
950
951
Note [Cast then apply]
~~~~~~~~~~~~~~~~~~~~~~
Consider
   myIndex = __inline_me ( (/\a. <blah>) |> co )
   co :: (forall a. a -> a) ~ (forall a. T a)
     ... /\a.\x. case ((myIndex a) |> sym co) x of { ... } ...

We need to inline myIndex to unravel this; but the actual call (myIndex a) has
no value arguments.  The ValAppCtxt gives it enough incentive to inline.

952
953
Note [Inlining in ArgCtxt]
~~~~~~~~~~~~~~~~~~~~~~~~~~
954
The condition (arity > 0) here is very important, because otherwise
955
956
957
958
959
960
961
962
963
964
we end up inlining top-level stuff into useless places; eg
   x = I# 3#
   f = \y.  g x
This can make a very big difference: it adds 16% to nofib 'integer' allocs,
and 20% to 'power'.

At one stage I replaced this condition by 'True' (leading to the above 
slow-down).  The motivation was test eyeball/inline1.hs; but that seems
to work ok now.

965
966
967
968
969
NOTE: arguably, we should inline in ArgCtxt only if the result of the
call is at least CONLIKE.  At least for the cases where we use ArgCtxt
for the RHS of a 'let', we only profit from the inlining if we get a 
CONLIKE thing (modulo lets).

970
971
Note [Lone variables]	See also Note [Interaction of exprIsCheap and lone variables]
~~~~~~~~~~~~~~~~~~~~~   which appears below
972
973
974
The "lone-variable" case is important.  I spent ages messing about
with unsatisfactory varaints, but this is nice.  The idea is that if a
variable appears all alone
975
976
977
978

	as an arg of lazy fn, or rhs	BoringCtxt
	as scrutinee of a case		CaseCtxt
	as arg of a fn			ArgCtxt
979
AND
980
	it is bound to a cheap expression
981

982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
then we should not inline it (unless there is some other reason,
e.g. is is the sole occurrence).  That is what is happening at 
the use of 'lone_variable' in 'interesting_saturated_call'.

Why?  At least in the case-scrutinee situation, turning
	let x = (a,b) in case x of y -> ...
into
	let x = (a,b) in case (a,b) of y -> ...
and thence to 
	let x = (a,b) in let y = (a,b) in ...
is bad if the binding for x will remain.

Another example: I discovered that strings
were getting inlined straight back into applications of 'error'
because the latter is strict.
	s = "foo"
	f = \x -> ...(error s)...

Fundamentally such contexts should not encourage inlining because the
context can ``see'' the unfolding of the variable (e.g. case or a
RULE) so there's no gain.  If the thing is bound to a value.

However, watch out:

 * Consider this:
	foo = _inline_ (\n. [n])
	bar = _inline_ (foo 20)
	baz = \n. case bar of { (m:_) -> m + n }
   Here we really want to inline 'bar' so that we can inline 'foo'
   and the whole thing unravels as it should obviously do.  This is 
   important: in the NDP project, 'bar' generates a closure data
   structure rather than a list. 

1015
1016
1017
1018
1019
   So the non-inlining of lone_variables should only apply if the
   unfolding is regarded as cheap; because that is when exprIsConApp_maybe
   looks through the unfolding.  Hence the "&& is_cheap" in the
   InlineRule branch.

1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
 * Even a type application or coercion isn't a lone variable.
   Consider
	case $fMonadST @ RealWorld of { :DMonad a b c -> c }
   We had better inline that sucker!  The case won't see through it.

   For now, I'm treating treating a variable applied to types 
   in a *lazy* context "lone". The motivating example was
	f = /\a. \x. BIG
	g = /\a. \y.  h (f a)
   There's no advantage in inlining f here, and perhaps
   a significant disadvantage.  Hence some_val_args in the Stop case
1031

1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
Note [Interaction of exprIsCheap and lone variables]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The lone-variable test says "don't inline if a case expression
scrutines a lone variable whose unfolding is cheap".  It's very 
important that, under these circumstances, exprIsConApp_maybe
can spot a constructor application. So, for example, we don't
consider
	let x = e in (x,x)
to be cheap, and that's good because exprIsConApp_maybe doesn't
think that expression is a constructor application.

I used to test is_value rather than is_cheap, which was utterly
wrong, because the above expression responds True to exprIsHNF.

This kind of thing can occur if you have

	{-# INLINE foo #-}
	foo = let x = e in (x,x)

which Roman did.

1053
\begin{code}
1054
1055
computeDiscount :: Int -> [Int] -> Int -> [ArgSummary] -> CallCtxt -> Int
computeDiscount n_vals_wanted arg_discounts res_discount arg_infos cont_info
1056
1057
 	-- We multiple the raw discounts (args_discount and result_discount)
	-- ty opt_UnfoldingKeenessFactor because the former have to do with
1058
1059
	--  *size* whereas the discounts imply that there's some extra 
	--  *efficiency* to be gained (e.g. beta reductions, case reductions) 
1060
1061
	-- by inlining.

1062
1063
1064
1065
1066
1067
1068
1069
1070
  = 1 		-- Discount of 1 because the result replaces the call
		-- so we count 1 for the function itself

    + length (take n_vals_wanted arg_infos)
      	       -- Discount of (un-scaled) 1 for each arg supplied, 
   	       -- because the result replaces the call

    + round (opt_UF_KeenessFactor * 
	     fromIntegral (arg_discount + res_discount'))
1071
1072
1073
  where
    arg_discount = sum (zipWith mk_arg_discount arg_discounts arg_infos)

1074
1075
1076
1077
1078
1079
1080
1081
1082
    mk_arg_discount _ 	     TrivArg    = 0 
    mk_arg_discount _ 	     NonTrivArg = 1   
    mk_arg_discount discount ValueArg   = discount 

    res_discount' = case cont_info of
			BoringCtxt  -> 0
			CaseCtxt    -> res_discount
			_other      -> 4 `min` res_discount
		-- res_discount can be very large when a function returns
1083
		-- constructors; but we only want to invoke that large discount
1084
1085
1086
1087
		-- when there's a case continuation.
		-- Otherwise we, rather arbitrarily, threshold it.  Yuk.
		-- But we want to aovid inlining large functions that return 
		-- constructors into contexts that are simply "interesting"
1088
\end{code}
1089

1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
%************************************************************************
%*									*
	Interesting arguments
%*									*
%************************************************************************

Note [Interesting arguments]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
An argument is interesting if it deserves a discount for unfoldings
with a discount in that argument position.  The idea is to avoid
unfolding a function that is applied only to variables that have no
unfolding (i.e. they are probably lambda bound): f x y z There is
little point in inlining f here.

Generally, *values* (like (C a b) and (\x.e)) deserve discounts.  But
we must look through lets, eg (let x = e in C a b), because the let will
float, exposing the value, if we inline.  That makes it different to
exprIsHNF.

Before 2009 we said it was interesting if the argument had *any* structure
at all; i.e. (hasSomeUnfolding v).  But does too much inlining; see Trac #3016.

But we don't regard (f x y) as interesting, unless f is unsaturated.
If it's saturated and f hasn't inlined, then it's probably not going
to now!

1116
1117
1118
1119
1120
Note [Conlike is interesting]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider
	f d = ...((*) d x y)...
	... f (df d')...
1121
where df is con-like. Then we'd really like to inline 'f' so that the
1122
1123
1124
1125
rule for (*) (df d) can fire.  To do this 
  a) we give a discount for being an argument of a class-op (eg (*) d)
  b) we say that a con-like argument (eg (df d)) is interesting

1126
1127
1128
1129
\begin{code}
data ArgSummary = TrivArg	-- Nothing interesting
     		| NonTrivArg	-- Arg has structure
		| ValueArg	-- Arg is a con-app or PAP
1130
		  		-- ..or con-like. Note [Conlike is interesting]
1131
1132
1133
1134
1135
1136
1137
1138

interestingArg :: CoreExpr -> ArgSummary
-- See Note [Interesting arguments]
interestingArg e = go e 0
  where
    -- n is # value args to which the expression is applied
    go (Lit {}) _   	   = ValueArg
    go (Var v)  n
1139
1140
       | isConLikeId v     = ValueArg	-- Experimenting with 'conlike' rather that
       	 	     	     		--    data constructors here
1141
1142
       | idArity v > n	   = ValueArg	-- Catches (eg) primops with arity but no unfolding
       | n > 0	           = NonTrivArg	-- Saturated or unknown call
1143
       | conlike_unfolding = ValueArg	-- n==0; look for an interesting unfolding
1144
                                        -- See Note [Conlike is interesting]
1145
1146
       | otherwise	   = TrivArg	-- n==0, no useful unfolding
       where
1147
         conlike_unfolding = isConLikeUnfolding (idUnfolding v)
1148
1149
1150
1151
1152
1153
1154

    go (Type _)          _ = TrivArg
    go (App fn (Type _)) n = go fn n    
    go (App fn _)        n = go fn (n+1)
    go (Note _ a) 	 n = go a n
    go (Cast e _) 	 n = go e n
    go (Lam v e)  	 n 
1155
       | isTyCoVar v	   = go e n
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
       | n>0	 	   = go e (n-1)
       | otherwise	   = ValueArg
    go (Let _ e)  	 n = case go e n of { ValueArg -> ValueArg; _ -> NonTrivArg }
    go (Case {})  	 _ = NonTrivArg

nonTriv ::  ArgSummary -> Bool
nonTriv TrivArg = False
nonTriv _       = True
\end{code}

Simon Marlow's avatar
Simon Marlow committed
1166
1167
%************************************************************************
%*									*
1168
         exprIsConApp_maybe
Simon Marlow's avatar
Simon Marlow committed
1169
1170
1171
%*									*
%************************************************************************

1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
Note [exprIsConApp_maybe]
~~~~~~~~~~~~~~~~~~~~~~~~~
exprIsConApp_maybe is a very important function.  There are two principal
uses:
  * case e of { .... }
  * cls_op e, where cls_op is a class operation

In both cases you want to know if e is of form (C e1..en) where C is
a data constructor.

However e might not *look* as if 
Simon Marlow's avatar
Simon Marlow committed
1183
1184

\begin{code}
1185
1186
1187
-- | Returns @Just (dc, [t1..tk], [x1..xn])@ if the argument expression is 
-- a *saturated* constructor application of the form @dc t1..tk x1 .. xn@,
-- where t1..tk are the *universally-qantified* type args of 'dc'
1188
exprIsConApp_maybe :: IdUnfoldingFun -> CoreExpr -> Maybe (DataCon, [Type], [CoreExpr])
1189

1190
1191
exprIsConApp_maybe id_unf (Note note expr)
  | notSccNote note
1192
  = exprIsConApp_maybe id_unf expr
1193
	-- We ignore all notes except SCCs.  For example,
1194
1195
	--  	case _scc_ "foo" (C a b) of
	--			C a b -> e
1196
1197
	-- should not be optimised away, because we'll lose the
	-- entry count on 'foo'; see Trac #4414
1198

1199
exprIsConApp_maybe id_unf (Cast expr co)
1200
1201
1202
1203
1204
1205
1206
  =     -- Here we do the KPush reduction rule as described in the FC paper
	-- The transformation applies iff we have
	--	(C e1 ... en) `cast` co
	-- where co :: (T t1 .. tn) ~ to_ty
	-- The left-hand one must be a T, because exprIsConApp returned True
	-- but the right-hand one might not be.  (Though it usually will.)

1207
    case exprIsConApp_maybe id_unf expr of {
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
	Nothing 	                 -> Nothing ;
	Just (dc, _dc_univ_args, dc_args) -> 

    let (_from_ty, to_ty) = coercionKind co
	dc_tc = dataConTyCon dc
    in
    case splitTyConApp_maybe to_ty of {
	Nothing -> Nothing ;
	Just (to_tc, to_tc_arg_tys) 
		| dc_tc /= to_tc -> Nothing
		-- These two Nothing cases are possible; we might see 
		--	(C x y) `cast` (g :: T a ~ S [a]),
		-- where S is a type function.  In fact, exprIsConApp
		-- will probably not be called in such circumstances,
		-- but there't nothing wrong with it 

	 	| otherwise  ->
    let
	tc_arity       = tyConArity dc_tc
	dc_univ_tyvars = dataConUnivTyVars dc
        dc_ex_tyvars   = dataConExTyVars dc
        arg_tys        = dataConRepArgTys dc

        dc_eqs :: [(Type,Type)]	  -- All equalities from the DataCon
        dc_eqs = [(mkTyVarTy tv, ty)   | (tv,ty) <- dataConEqSpec dc] ++
                 [getEqPredTys eq_pred | eq_pred <- dataConEqTheta dc]

        (ex_args, rest1)    = splitAtList dc_ex_tyvars dc_args
	(co_args, val_args) = splitAtList dc_eqs rest1

	-- Make the "theta" from Fig 3 of the paper
        gammas = decomposeCo tc_arity co
        theta  = zipOpenTvSubst (dc_univ_tyvars ++ dc_ex_tyvars)
                                (gammas         ++ stripTypeArgs ex_args)

          -- Cast the existential coercion arguments
        cast_co (ty1, ty2) (Type co) 
          = Type $ mkSymCoercion (substTy theta ty1)
		   `mkTransCoercion` co
		   `mkTransCoercion` (substTy theta ty2)
        cast_co _ other_arg = pprPanic "cast_co" (ppr other_arg)
        new_co_args = zipWith cast_co dc_eqs co_args
  
          -- Cast the value arguments (which include dictionaries)
	new_val_args = zipWith cast_arg arg_tys val_args
	cast_arg arg_ty arg = mkCoerce (substTy theta arg_ty) arg
    in
#ifdef DEBUG
    let dump_doc = vcat [ppr dc,      ppr dc_univ_tyvars, ppr dc_ex_tyvars,
                         ppr arg_tys, ppr dc_args,        ppr _dc_univ_args,
                         ppr ex_args, ppr val_args]
1259
1260
    in
    ASSERT2( coreEqType _from_ty (mkTyConApp dc_tc _dc_univ_args), dump_doc )
1261
1262
1263
1264
1265
1266
1267
    ASSERT2( all isTypeArg (ex_args ++ co_args), dump_doc )
    ASSERT2( equalLength val_args arg_tys, dump_doc )
#endif

    Just (dc, to_tc_arg_tys, ex_args ++ new_co_args ++ new_val_args)
    }}

1268
exprIsConApp_maybe id_unf expr 
1269
  = analyse expr [] 
Simon Marlow's avatar
Simon Marlow committed
1270
  where
1271
1272
1273
1274
1275
    analyse (App fun arg) args = analyse fun (arg:args)
    analyse fun@(Lam {})  args = beta fun [] args 

    analyse (Var fun) args
	| Just con <- isDataConWorkId_maybe fun
1276
        , count isValArg args == idArity fun
1277
1278
1279
1280
	, let (univ_ty_args, rest_args) = splitAtList (dataConUnivTyVars con) args
	= Just (con, stripTypeArgs univ_ty_args, rest_args)

	-- Look through dictionary functions; see Note [Unfolding DFuns]
1281
1282
1283
1284
        | DFunUnfolding dfun_nargs con ops <- unfolding
        , let sat = length args == dfun_nargs    -- See Note [DFun arity check]
          in if sat then True else 
             pprTrace "Unsaturated dfun" (ppr fun <+> int dfun_nargs $$ ppr args) False   
1285
        , let (dfun_tvs, _n_theta, _cls, dfun_res_tys) = tcSplitDFunTy (idType fun)
1286
1287
1288
1289
1290
              subst    = zipOpenTvSubst dfun_tvs (stripTypeArgs (takeList dfun_tvs args))
              mk_arg (DFunConstArg e) = e
              mk_arg (DFunLamArg i)   = args !! i
              mk_arg (DFunPolyArg e)  = mkApps e args
        = Just (con, substTys subst dfun_res_tys, map mk_arg ops)
1291
1292
1293

	-- Look through unfoldings, but only cheap ones, because
	-- we are effectively duplicating the unfolding
1294
1295
1296
	| Just rhs <- expandUnfolding_maybe unfolding
	= -- pprTrace "expanding" (ppr fun $$ ppr rhs) $
          analyse rhs args
1297
        where
1298
	  unfolding = id_unf fun
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310

    analyse _ _ = Nothing

    -----------
    beta (Lam v body) pairs (arg : args) 
        | isTypeArg arg
        = beta body ((v,arg):pairs) args 

    beta (Lam {}) _ _    -- Un-saturated, or not a type lambda
	= Nothing

    beta fun pairs args
1311
        = analyse (substExpr (text "subst-expr-is-con-app") subst fun) args
1312
        where
1313
          subst = mkOpenSubst (mkInScopeSet (exprFreeVars fun)) pairs
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
	  -- doc = vcat [ppr fun, ppr expr, ppr pairs, ppr args]


stripTypeArgs :: [CoreExpr] -> [Type]
stripTypeArgs args = ASSERT2( all isTypeArg args, ppr args )
                     [ty | Type ty <- args]
\end{code}

Note [Unfolding DFuns]
~~~~~~~~~~~~~~~~~~~~~~
DFuns look like

  df :: forall a b. (Eq a, Eq b) -> Eq (a,b)
  df a b d_a d_b = MkEqD (a,b) ($c1 a b d_a d_b)
                               ($c2 a b d_a d_b)

So to split it up we just need to apply the ops $c1, $c2 etc
to the very same args as the dfun.  It takes a little more work
to compute the type arguments to the dictionary constructor.

1334
1335
1336
1337
Note [DFun arity check]
~~~~~~~~~~~~~~~~~~~~~~~
Here we check that the total number of supplied arguments (inclding 
type args) matches what the dfun is expecting.  This may be *less*
1338
than the ordinary arity of the dfun: see Note [DFun unfoldings] in CoreSyn