SimplMonad.lhs 33.4 KB
Newer Older
1
%
2
% (c) The AQUA Project, Glasgow University, 1993-1998
3
4
5
6
7
%
\section[SimplMonad]{The simplifier Monad}

\begin{code}
module SimplMonad (
8
	InId, InBind, InExpr, InAlt, InArg, InType, InBinder,
9
10
	OutId, OutTyVar, OutBind, OutExpr, OutAlt, OutArg, OutType, OutBinder,
	FloatsWith, FloatsWithExpr,
11
12
13

	-- The monad
	SimplM,
14
	initSmpl, returnSmpl, thenSmpl, thenSmpl_,
15
	mapSmpl, mapAndUnzipSmpl, mapAccumLSmpl,
16
	getDOptsSmpl,
17

18
19
	-- The simplifier mode
	setMode, getMode, 
20

21
        -- Unique supply
22
        getUniqueSmpl, getUniquesSmpl, getUniqSupplySmpl,
23

24
	-- Counting
25
	SimplCount, Tick(..),
26
	tick, freeTick,
27
28
29
30
	getSimplCount, zeroSimplCount, pprSimplCount, 
	plusSimplCount, isZeroSimplCount,

	-- Switch checker
31
32
	SwitchChecker, SwitchResult(..), getSwitchChecker, getSimplIntSwitch,
	isAmongSimpl, intSwitchSet, switchIsOn,
33
34
35
36
37

	-- Cost centres
	getEnclosingCC, setEnclosingCC,

	-- Environments
38
	SimplEnv, emptySimplEnv, getSubst, setSubst,
39
	getSubstEnv, extendSubst, extendSubstList,
40
	getInScope, setInScope, modifyInScope, addNewInScopeIds,
41
	setSubstEnv, zapSubstEnv,
42

43
44
45
46
47
48
49
50
	-- Floats
  	Floats, emptyFloats, isEmptyFloats, unitFloat, addFloats, flattenFloats,
	allLifted, wrapFloats, floatBinds,
	addAuxiliaryBind,

	-- Inlining,
	preInlineUnconditionally, postInlineUnconditionally, activeInline, activeRule,
	inlineMode
51
52
    ) where

53
#include "HsVersions.h"
54

55
import Id		( Id, idType, idOccInfo, idInlinePragma	)
56
import CoreSyn
57
import CoreUtils	( needsCaseBinding, exprIsTrivial )
58
import PprCore		()	-- Instances
59
import CostCentre	( CostCentreStack, subsumedCCS )
60
import Var	
61
62
import VarEnv
import VarSet
63
import OrdList
64
import qualified Subst
65
import Subst		( Subst, mkSubst, substEnv, 
apt's avatar
apt committed
66
67
			  InScopeSet, mkInScopeSet, substInScope,
			  isInScope 
68
			)
69
import Type             ( Type, isUnLiftedType )
70
import UniqSupply	( uniqsFromSupply, uniqFromSupply, splitUniqSupply,
71
72
			  UniqSupply
			)
73
import FiniteMap
74
import BasicTypes	( TopLevelFlag, isTopLevel, isLoopBreaker,
75
			  Activation, isActive, isAlwaysActive,
76
			  OccInfo(..), isOneOcc
77
78
79
80
			)
import CmdLineOpts	( SimplifierSwitch(..), SimplifierMode(..),
			  DynFlags, DynFlag(..), dopt, 
			  opt_PprStyle_Debug, opt_HistorySize, opt_SimplNoPreInlining,
81
			)
82
import Unique		( Unique )
83
import Maybes		( expectJust )
84
import Outputable
85
86
87
88
import Array		( array, (//) )
import FastTypes
import GlaExts		( indexArray# )

89
#if __GLASGOW_HASKELL__ < 503
90
import PrelArr  ( Array(..) )
91
92
#else
import GHC.Arr  ( Array(..) )
93
#endif
94

95
infixr 0  `thenSmpl`, `thenSmpl_`
96
97
\end{code}

98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
%************************************************************************
%*									*
\subsection[Simplify-types]{Type declarations}
%*									*
%************************************************************************

\begin{code}
type InBinder  = CoreBndr
type InId      = Id			-- Not yet cloned
type InType    = Type			-- Ditto
type InBind    = CoreBind
type InExpr    = CoreExpr
type InAlt     = CoreAlt
type InArg     = CoreArg

type OutBinder  = CoreBndr
type OutId	= Id			-- Cloned
115
type OutTyVar	= TyVar			-- Cloned
116
117
118
119
120
type OutType	= Type			-- Cloned
type OutBind	= CoreBind
type OutExpr	= CoreExpr
type OutAlt	= CoreAlt
type OutArg	= CoreArg
121
\end{code}
122

123
124
125
126
127
%************************************************************************
%*									*
\subsection{Floats}
%*									*
%************************************************************************
128

129
130
131
\begin{code}
type FloatsWithExpr = FloatsWith OutExpr
type FloatsWith a   = (Floats, a)
132
133
134
	-- We return something equivalent to (let b in e), but
	-- in pieces to avoid the quadratic blowup when floating 
	-- incrementally.  Comments just before simplExprB in Simplify.lhs
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

data Floats = Floats (OrdList OutBind) 
		     InScopeSet		-- Environment "inside" all the floats
		     Bool		-- True <=> All bindings are lifted

allLifted :: Floats -> Bool
allLifted (Floats _ _ is_lifted) = is_lifted

wrapFloats :: Floats -> OutExpr -> OutExpr
wrapFloats (Floats bs _ _) body = foldrOL Let body bs

isEmptyFloats :: Floats -> Bool
isEmptyFloats (Floats bs _ _) = isNilOL bs 

floatBinds :: Floats -> [OutBind]
floatBinds (Floats bs _ _) = fromOL bs

flattenFloats :: Floats -> Floats
-- Flattens into a single Rec group
flattenFloats (Floats bs is is_lifted) 
  = ASSERT2( is_lifted, ppr (fromOL bs) )
    Floats (unitOL (Rec (flattenBinds (fromOL bs)))) is is_lifted
157
158
\end{code}

159
\begin{code}
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
emptyFloats :: SimplEnv -> Floats
emptyFloats env = Floats nilOL (getInScope env) True

unitFloat :: SimplEnv -> OutId -> OutExpr -> Floats
-- A single non-rec float; extend the in-scope set
unitFloat env var rhs = Floats (unitOL (NonRec var rhs))
			       (Subst.extendInScopeSet (getInScope env) var)
			       (not (isUnLiftedType (idType var)))

addFloats :: SimplEnv -> Floats 
	  -> (SimplEnv -> SimplM (FloatsWith a))
	  -> SimplM (FloatsWith a)
addFloats env (Floats b1 is1 l1) thing_inside
  | isNilOL b1 
  = thing_inside env
  | otherwise
  = thing_inside (setInScopeSet env is1)	`thenSmpl` \ (Floats b2 is2 l2, res) ->
    returnSmpl (Floats (b1 `appOL` b2) is2 (l1 && l2), res)

addLetBind :: OutBind -> Floats -> Floats
addLetBind bind (Floats binds in_scope lifted) 
  = Floats (bind `consOL` binds) in_scope (lifted && is_lifted_bind bind)

is_lifted_bind (Rec _)      = True
is_lifted_bind (NonRec b r) = not (isUnLiftedType (idType b))

-- addAuxiliaryBind 	* takes already-simplified things (bndr and rhs)
--			* extends the in-scope env
--			* assumes it's a let-bindable thing
addAuxiliaryBind :: SimplEnv -> OutBind
		 -> (SimplEnv -> SimplM (FloatsWith a))
	 	 -> SimplM (FloatsWith a)
192
	-- Extends the in-scope environment as well as wrapping the bindings
193
194
195
196
addAuxiliaryBind env bind thing_inside
  = ASSERT( case bind of { NonRec b r -> not (needsCaseBinding (idType b) r) ; Rec _ -> True } )
    thing_inside (addNewInScopeIds env (bindersOf bind))	`thenSmpl` \ (floats, x) ->
    returnSmpl (addLetBind bind floats, x)
197
198
\end{code}

199

200
201
%************************************************************************
%*									*
202
\subsection{Monad plumbing}
203
204
205
206
207
208
209
%*									*
%************************************************************************

For the simplifier monad, we want to {\em thread} a unique supply and a counter.
(Command-line switches move around through the explicitly-passed SimplEnv.)

\begin{code}
210
type SimplM result
211
  =  DynFlags		-- We thread the unique supply because
212
  -> UniqSupply		-- constantly splitting it is rather expensive
213
214
  -> SimplCount 
  -> (result, UniqSupply, SimplCount)
215
216
217
\end{code}

\begin{code}
218
initSmpl :: DynFlags
219
220
221
222
	 -> UniqSupply		-- No init count; set to 0
	 -> SimplM a
	 -> (a, SimplCount)

223
224
initSmpl dflags us m
  = case m dflags us (zeroSimplCount dflags) of 
225
	(result, _, count) -> (result, count)
226
227
228
229
230
231


{-# INLINE thenSmpl #-}
{-# INLINE thenSmpl_ #-}
{-# INLINE returnSmpl #-}

232
returnSmpl :: a -> SimplM a
233
returnSmpl e dflags us sc = (e, us, sc)
234

235
236
thenSmpl  :: SimplM a -> (a -> SimplM b) -> SimplM b
thenSmpl_ :: SimplM a -> SimplM b -> SimplM b
237

238
239
240
thenSmpl m k dflags us0 sc0
  = case (m dflags us0 sc0) of 
	(m_result, us1, sc1) -> k m_result dflags us1 sc1
241

242
243
244
thenSmpl_ m k dflags us0 sc0
  = case (m dflags us0 sc0) of 
	(_, us1, sc1) -> k dflags us1 sc1
245
\end{code}
246

247
248
249
250

\begin{code}
mapSmpl	    	:: (a -> SimplM b) -> [a] -> SimplM [b]
mapAndUnzipSmpl :: (a -> SimplM (b, c)) -> [a] -> SimplM ([b],[c])
251
252
253
254
255
256
257
258
259
260
261
262

mapSmpl f [] = returnSmpl []
mapSmpl f (x:xs)
  = f x		    `thenSmpl` \ x'  ->
    mapSmpl f xs    `thenSmpl` \ xs' ->
    returnSmpl (x':xs')

mapAndUnzipSmpl f [] = returnSmpl ([],[])
mapAndUnzipSmpl f (x:xs)
  = f x			    `thenSmpl` \ (r1,  r2)  ->
    mapAndUnzipSmpl f xs    `thenSmpl` \ (rs1, rs2) ->
    returnSmpl (r1:rs1, r2:rs2)
263
264
265
266
267

mapAccumLSmpl f acc []     = returnSmpl (acc, [])
mapAccumLSmpl f acc (x:xs) = f acc x	`thenSmpl` \ (acc', x') ->
			     mapAccumLSmpl f acc' xs	`thenSmpl` \ (acc'', xs') ->
			     returnSmpl (acc'', x':xs')
268
\end{code}
269
270


271
272
273
274
275
276
277
%************************************************************************
%*									*
\subsection{The unique supply}
%*									*
%************************************************************************

\begin{code}
278
getUniqSupplySmpl :: SimplM UniqSupply
279
getUniqSupplySmpl dflags us sc 
280
281
282
   = case splitUniqSupply us of
        (us1, us2) -> (us1, us2, sc)

283
getUniqueSmpl :: SimplM Unique
284
getUniqueSmpl dflags us sc 
285
286
   = case splitUniqSupply us of
        (us1, us2) -> (uniqFromSupply us1, us2, sc)
287

288
getUniquesSmpl :: SimplM [Unique]
289
getUniquesSmpl dflags us sc 
290
   = case splitUniqSupply us of
291
        (us1, us2) -> (uniqsFromSupply us1, us2, sc)
292
293

getDOptsSmpl :: SimplM DynFlags
294
getDOptsSmpl dflags us sc 
295
   = (dflags, us, sc)
296
297
298
299
300
\end{code}


%************************************************************************
%*									*
301
\subsection{Counting up what we've done}
302
303
304
%*									*
%************************************************************************

305
306
\begin{code}
getSimplCount :: SimplM SimplCount
307
getSimplCount dflags us sc = (sc, us, sc)
308

309
tick :: Tick -> SimplM ()
310
tick t dflags us sc 
311
312
313
   = sc' `seq` ((), us, sc')
     where
        sc' = doTick t sc
314
315
316
317

freeTick :: Tick -> SimplM ()
-- Record a tick, but don't add to the total tick count, which is
-- used to decide when nothing further has happened
318
freeTick t dflags us sc 
319
320
321
   = sc' `seq` ((), us, sc')
        where
           sc' = doFreeTick t sc
322
\end{code}
323

324
325
326
\begin{code}
verboseSimplStats = opt_PprStyle_Debug		-- For now, anyway

327
zeroSimplCount	   :: DynFlags -> SimplCount
328
329
330
331
332
isZeroSimplCount   :: SimplCount -> Bool
pprSimplCount	   :: SimplCount -> SDoc
doTick, doFreeTick :: Tick -> SimplCount -> SimplCount
plusSimplCount     :: SimplCount -> SimplCount -> SimplCount
\end{code}
333
334

\begin{code}
335
336
337
data SimplCount = VerySimplZero		-- These two are used when 
		| VerySimplNonZero	-- we are only interested in 
					-- termination info
338

339
		| SimplCount	{
340
341
342
343
344
345
			ticks   :: !Int,		-- Total ticks
			details :: !TickCounts,		-- How many of each type
			n_log	:: !Int,		-- N
			log1	:: [Tick],		-- Last N events; <= opt_HistorySize
			log2	:: [Tick]		-- Last opt_HistorySize events before that
		  }
346

347
348
type TickCounts = FiniteMap Tick Int

349
350
zeroSimplCount dflags
		-- This is where we decide whether to do
351
		-- the VerySimpl version or the full-stats version
352
353
354
355
356
  | dopt Opt_D_dump_simpl_stats dflags
  = SimplCount {ticks = 0, details = emptyFM,
                n_log = 0, log1 = [], log2 = []}
  | otherwise
  = VerySimplZero
357

358
359
360
isZeroSimplCount VerySimplZero    	    = True
isZeroSimplCount (SimplCount { ticks = 0 }) = True
isZeroSimplCount other			    = False
361
362
363
364
365

doFreeTick tick sc@SimplCount { details = dts } 
  = dts' `seqFM` sc { details = dts' }
  where
    dts' = dts `addTick` tick 
366
doFreeTick tick sc = sc 
367
368
369
370
371
372
373
374
375
376
377

-- Gross hack to persuade GHC 3.03 to do this important seq
seqFM fm x | isEmptyFM fm = x
	   | otherwise    = x

doTick tick sc@SimplCount { ticks = tks, details = dts, n_log = nl, log1 = l1, log2 = l2 }
  | nl >= opt_HistorySize = sc1 { n_log = 1, log1 = [tick], log2 = l1 }
  | otherwise		  = sc1 { n_log = nl+1, log1 = tick : l1 }
  where
    sc1 = sc { ticks = tks+1, details = dts `addTick` tick }

378
379
380
doTick tick sc = VerySimplNonZero	-- The very simple case


381
382
383
384
385
386
387
388
389
-- Don't use plusFM_C because that's lazy, and we want to 
-- be pretty strict here!
addTick :: TickCounts -> Tick -> TickCounts
addTick fm tick = case lookupFM fm tick of
			Nothing -> addToFM fm tick 1
			Just n  -> n1 `seq` addToFM fm tick n1
				where
				   n1 = n+1

390

391
392
393
plusSimplCount sc1@(SimplCount { ticks = tks1, details = dts1 })
	       sc2@(SimplCount { ticks = tks2, details = dts2 })
  = log_base { ticks = tks1 + tks2, details = plusFM_C (+) dts1 dts2 }
394
  where
395
396
397
398
399
	-- A hackish way of getting recent log info
    log_base | null (log1 sc2) = sc1	-- Nothing at all in sc2
	     | null (log2 sc2) = sc2 { log2 = log1 sc1 }
	     | otherwise       = sc2

400
401
plusSimplCount VerySimplZero VerySimplZero = VerySimplZero
plusSimplCount sc1	     sc2	   = VerySimplNonZero
402

403
404
pprSimplCount VerySimplZero    = ptext SLIT("Total ticks: ZERO!")
pprSimplCount VerySimplNonZero = ptext SLIT("Total ticks: NON-ZERO!")
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
pprSimplCount (SimplCount { ticks = tks, details = dts, log1 = l1, log2 = l2 })
  = vcat [ptext SLIT("Total ticks:    ") <+> int tks,
	  text "",
	  pprTickCounts (fmToList dts),
	  if verboseSimplStats then
		vcat [text "",
		      ptext SLIT("Log (most recent first)"),
		      nest 4 (vcat (map ppr l1) $$ vcat (map ppr l2))]
	  else empty
    ]

pprTickCounts :: [(Tick,Int)] -> SDoc
pprTickCounts [] = empty
pprTickCounts ((tick1,n1):ticks)
  = vcat [int tot_n <+> text (tickString tick1),
	  pprTCDetails real_these,
	  pprTickCounts others
    ]
  where
    tick1_tag		= tickToTag tick1
    (these, others)	= span same_tick ticks
    real_these		= (tick1,n1):these
    same_tick (tick2,_) = tickToTag tick2 == tick1_tag
    tot_n		= sum [n | (_,n) <- real_these]

pprTCDetails ticks@((tick,_):_)
  | verboseSimplStats || isRuleFired tick
  = nest 4 (vcat [int n <+> pprTickCts tick | (tick,n) <- ticks])
  | otherwise
  = empty
\end{code}

%************************************************************************
%*									*
\subsection{Ticks}
%*									*
%************************************************************************

\begin{code}
data Tick
  = PreInlineUnconditionally	Id
  | PostInlineUnconditionally	Id

  | UnfoldingDone    		Id
  | RuleFired			FAST_STRING	-- Rule name

451
  | LetFloatFromLet
452
453
454
455
456
457
458
459
  | EtaExpansion		Id	-- LHS binder
  | EtaReduction		Id	-- Binder on outer lambda
  | BetaReduction		Id	-- Lambda binder


  | CaseOfCase			Id	-- Bndr on *inner* case
  | KnownBranch			Id	-- Case binder
  | CaseMerge			Id	-- Binder on outer case
460
  | AltMerge			Id	-- Case binder
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
  | CaseElim			Id	-- Case binder
  | CaseIdentity		Id	-- Case binder
  | FillInCaseDefault		Id	-- Case binder

  | BottomFound		
  | SimplifierDone		-- Ticked at each iteration of the simplifier

isRuleFired (RuleFired _) = True
isRuleFired other	  = False

instance Outputable Tick where
  ppr tick = text (tickString tick) <+> pprTickCts tick

instance Eq Tick where
  a == b = case a `cmpTick` b of { EQ -> True; other -> False }

instance Ord Tick where
  compare = cmpTick

tickToTag :: Tick -> Int
tickToTag (PreInlineUnconditionally _)	= 0
tickToTag (PostInlineUnconditionally _)	= 1
tickToTag (UnfoldingDone _)		= 2
tickToTag (RuleFired _)			= 3
485
tickToTag LetFloatFromLet		= 4
486
487
488
489
490
491
492
493
494
495
496
tickToTag (EtaExpansion _)		= 5
tickToTag (EtaReduction _)		= 6
tickToTag (BetaReduction _)		= 7
tickToTag (CaseOfCase _)		= 8
tickToTag (KnownBranch _)		= 9
tickToTag (CaseMerge _)			= 10
tickToTag (CaseElim _)			= 11
tickToTag (CaseIdentity _)		= 12
tickToTag (FillInCaseDefault _)		= 13
tickToTag BottomFound			= 14
tickToTag SimplifierDone		= 16
497
tickToTag (AltMerge _)			= 17
498
499
500
501
502
503

tickString :: Tick -> String
tickString (PreInlineUnconditionally _)	= "PreInlineUnconditionally"
tickString (PostInlineUnconditionally _)= "PostInlineUnconditionally"
tickString (UnfoldingDone _)		= "UnfoldingDone"
tickString (RuleFired _)		= "RuleFired"
504
tickString LetFloatFromLet		= "LetFloatFromLet"
505
506
507
508
509
510
tickString (EtaExpansion _)		= "EtaExpansion"
tickString (EtaReduction _)		= "EtaReduction"
tickString (BetaReduction _)		= "BetaReduction"
tickString (CaseOfCase _)		= "CaseOfCase"
tickString (KnownBranch _)		= "KnownBranch"
tickString (CaseMerge _)		= "CaseMerge"
511
tickString (AltMerge _)			= "AltMerge"
512
513
514
515
516
517
518
519
520
521
522
tickString (CaseElim _)			= "CaseElim"
tickString (CaseIdentity _)		= "CaseIdentity"
tickString (FillInCaseDefault _)	= "FillInCaseDefault"
tickString BottomFound			= "BottomFound"
tickString SimplifierDone		= "SimplifierDone"

pprTickCts :: Tick -> SDoc
pprTickCts (PreInlineUnconditionally v)	= ppr v
pprTickCts (PostInlineUnconditionally v)= ppr v
pprTickCts (UnfoldingDone v)		= ppr v
pprTickCts (RuleFired v)		= ppr v
523
pprTickCts LetFloatFromLet		= empty
524
525
526
527
528
529
pprTickCts (EtaExpansion v)		= ppr v
pprTickCts (EtaReduction v)		= ppr v
pprTickCts (BetaReduction v)		= ppr v
pprTickCts (CaseOfCase v)		= ppr v
pprTickCts (KnownBranch v)		= ppr v
pprTickCts (CaseMerge v)		= ppr v
530
pprTickCts (AltMerge v)			= ppr v
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
pprTickCts (CaseElim v)			= ppr v
pprTickCts (CaseIdentity v)		= ppr v
pprTickCts (FillInCaseDefault v)	= ppr v
pprTickCts other			= empty

cmpTick :: Tick -> Tick -> Ordering
cmpTick a b = case (tickToTag a `compare` tickToTag b) of
		GT -> GT
		EQ | isRuleFired a || verboseSimplStats -> cmpEqTick a b
		   | otherwise				-> EQ
		LT -> LT
	-- Always distinguish RuleFired, so that the stats
	-- can report them even in non-verbose mode

cmpEqTick :: Tick -> Tick -> Ordering
cmpEqTick (PreInlineUnconditionally a)	(PreInlineUnconditionally b)	= a `compare` b
cmpEqTick (PostInlineUnconditionally a)	(PostInlineUnconditionally b)	= a `compare` b
cmpEqTick (UnfoldingDone a)		(UnfoldingDone b)		= a `compare` b
cmpEqTick (RuleFired a)			(RuleFired b)			= a `compare` b
cmpEqTick (EtaExpansion a)		(EtaExpansion b)		= a `compare` b
cmpEqTick (EtaReduction a)		(EtaReduction b)		= a `compare` b
cmpEqTick (BetaReduction a)		(BetaReduction b)		= a `compare` b
cmpEqTick (CaseOfCase a)		(CaseOfCase b)			= a `compare` b
cmpEqTick (KnownBranch a)		(KnownBranch b)			= a `compare` b
cmpEqTick (CaseMerge a)			(CaseMerge b)			= a `compare` b
556
cmpEqTick (AltMerge a)			(AltMerge b)			= a `compare` b
557
558
559
560
cmpEqTick (CaseElim a)			(CaseElim b)			= a `compare` b
cmpEqTick (CaseIdentity a)		(CaseIdentity b)		= a `compare` b
cmpEqTick (FillInCaseDefault a)		(FillInCaseDefault b)		= a `compare` b
cmpEqTick other1			other2				= EQ
561
562
563
\end{code}


564

565
566
%************************************************************************
%*									*
567
\subsubsection{The @SimplEnv@ type}
568
569
570
%*									*
%************************************************************************

571

572
\begin{code}
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
data SimplEnv
  = SimplEnv {
	seMode 	    :: SimplifierMode,
	seChkr      :: SwitchChecker,
	seCC        :: CostCentreStack,	-- The enclosing CCS (when profiling)
	seSubst     :: Subst		-- The current substitution
    }
	-- The range of the substitution is OutType and OutExpr resp
	-- 
	-- The substitution is idempotent
	-- It *must* be applied; things in its domain simply aren't
	-- bound in the result.
	--
	-- The substitution usually maps an Id to its clone,
	-- but if the orig defn is a let-binding, and
	-- the RHS of the let simplifies to an atom,
	-- we just add the binding to the substitution and elide the let.
590

591
592
593
594
595
	-- The in-scope part of Subst includes *all* in-scope TyVars and Ids
	-- The elements of the set may have better IdInfo than the
	-- occurrences of in-scope Ids, and (more important) they will
	-- have a correctly-substituted type.  So we use a lookup in this
	-- set to replace occurrences
596

597
598
599
600
601
emptySimplEnv :: SimplifierMode -> [SimplifierSwitch] -> VarSet -> SimplEnv
emptySimplEnv mode switches in_scope
  = SimplEnv { seChkr = isAmongSimpl switches, seCC = subsumedCCS, seMode = mode,
	       seSubst = mkSubst (mkInScopeSet in_scope) emptySubstEnv }
	-- The top level "enclosing CC" is "SUBSUMED".
602

603
604
605
---------------------
getSwitchChecker :: SimplEnv -> SwitchChecker
getSwitchChecker env = seChkr env
606

607
608
609
---------------------
getMode :: SimplEnv -> SimplifierMode
getMode env = seMode env
610

611
612
setMode :: SimplifierMode -> SimplEnv -> SimplEnv
setMode mode env = env { seMode = mode }
613

614
615
616
---------------------
getEnclosingCC :: SimplEnv -> CostCentreStack
getEnclosingCC env = seCC env
617

618
619
setEnclosingCC :: SimplEnv -> CostCentreStack -> SimplEnv
setEnclosingCC env cc = env {seCC = cc}
sof's avatar
sof committed
620

621
622
623
---------------------
getSubst :: SimplEnv -> Subst
getSubst env = seSubst env
sof's avatar
sof committed
624

625
626
setSubst :: SimplEnv -> Subst -> SimplEnv
setSubst env subst = env {seSubst = subst}
sof's avatar
sof committed
627

628
629
630
631
632
633
634
extendSubst :: SimplEnv -> CoreBndr -> SubstResult -> SimplEnv
extendSubst env@(SimplEnv {seSubst = subst}) var res
  = env {seSubst = Subst.extendSubst subst var res}

extendSubstList :: SimplEnv -> [CoreBndr] -> [SubstResult] -> SimplEnv
extendSubstList env@(SimplEnv {seSubst = subst}) vars ress
  = env {seSubst = Subst.extendSubstList subst vars ress}
sof's avatar
sof committed
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
---------------------
getInScope :: SimplEnv -> InScopeSet
getInScope env = substInScope (seSubst env)

setInScope :: SimplEnv -> SimplEnv -> SimplEnv
setInScope env env_with_in_scope = setInScopeSet env (getInScope env_with_in_scope)

setInScopeSet :: SimplEnv -> InScopeSet -> SimplEnv
setInScopeSet env@(SimplEnv {seSubst = subst}) in_scope
  = env {seSubst = Subst.setInScope subst in_scope}

addNewInScopeIds :: SimplEnv -> [CoreBndr] -> SimplEnv
	-- The new Ids are guaranteed to be freshly allocated
addNewInScopeIds env@(SimplEnv {seSubst = subst}) vs
  = env {seSubst = Subst.extendNewInScopeList subst vs}

modifyInScope :: SimplEnv -> CoreBndr -> CoreBndr -> SimplEnv
modifyInScope env@(SimplEnv {seSubst = subst}) v v'
  = env {seSubst = Subst.modifyInScope subst v v'}

---------------------
getSubstEnv :: SimplEnv -> SubstEnv
getSubstEnv env = substEnv (seSubst env)

setSubstEnv :: SimplEnv -> SubstEnv -> SimplEnv
setSubstEnv env@(SimplEnv {seSubst = subst}) senv
  = env {seSubst = Subst.setSubstEnv subst senv}

zapSubstEnv :: SimplEnv -> SimplEnv
zapSubstEnv env@(SimplEnv {seSubst = subst})
  = env {seSubst = Subst.zapSubstEnv subst}
667
\end{code}
sof's avatar
sof committed
668

669

670
671
%************************************************************************
%*									*
672
\subsection{Decisions about inlining}
673
674
%*									*
%************************************************************************
sof's avatar
sof committed
675

676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
Inlining is controlled partly by the SimplifierMode switch.  This has two
settings:

	SimplGently	(a) Simplifying before specialiser/full laziness
			(b) Simplifiying inside INLINE pragma
			(c) Simplifying the LHS of a rule

	SimplPhase n	Used at all other times

The key thing about SimplGently is that it does no call-site inlining.
Before full laziness we must be careful not to inline wrappers,
because doing so inhibits floating
    e.g. ...(case f x of ...)...
    ==> ...(case (case x of I# x# -> fw x#) of ...)...
    ==> ...(case x of I# x# -> case fw x# of ...)...
and now the redex (f x) isn't floatable any more.

INLINE pragmas
~~~~~~~~~~~~~~
SimplGently is also used as the mode to simplify inside an InlineMe note.
sof's avatar
sof committed
696

697
\begin{code}
698
699
700
inlineMode :: SimplifierMode
inlineMode = SimplGently
\end{code}
701

702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
It really is important to switch off inlinings inside such
expressions.  Consider the following example 

     	let f = \pq -> BIG
     	in
     	let g = \y -> f y y
	    {-# INLINE g #-}
     	in ...g...g...g...g...g...

Now, if that's the ONLY occurrence of f, it will be inlined inside g,
and thence copied multiple times when g is inlined.


This function may be inlinined in other modules, so we
don't want to remove (by inlining) calls to functions that have
specialisations, or that may have transformation rules in an importing
scope.

E.g. 	{-# INLINE f #-}
		f x = ...g...

and suppose that g is strict *and* has specialisations.  If we inline
g's wrapper, we deny f the chance of getting the specialised version
of g when f is inlined at some call site (perhaps in some other
module).

It's also important not to inline a worker back into a wrapper.
A wrapper looks like
	wraper = inline_me (\x -> ...worker... )
Normally, the inline_me prevents the worker getting inlined into
the wrapper (initially, the worker's only call site!).  But,
if the wrapper is sure to be called, the strictness analyser will
mark it 'demanded', so when the RHS is simplified, it'll get an ArgOf
continuation.  That's why the keep_inline predicate returns True for
ArgOf continuations.  It shouldn't do any harm not to dissolve the
inline-me note under these circumstances.

Note that the result is that we do very little simplification
inside an InlineMe.  

	all xs = foldr (&&) True xs
	any p = all . map p  {-# INLINE any #-}

Problem: any won't get deforested, and so if it's exported and the
importer doesn't use the inlining, (eg passes it as an arg) then we
won't get deforestation at all.  We havn't solved this problem yet!


preInlineUnconditionally
~~~~~~~~~~~~~~~~~~~~~~~~
@preInlineUnconditionally@ examines a bndr to see if it is used just
once in a completely safe way, so that it is safe to discard the
binding inline its RHS at the (unique) usage site, REGARDLESS of how
big the RHS might be.  If this is the case we don't simplify the RHS
first, but just inline it un-simplified.

This is much better than first simplifying a perhaps-huge RHS and then
759
760
761
762
763
764
765
766
767
768
inlining and re-simplifying it.  Indeed, it can be at least quadratically
better.  Consider

	x1 = e1
	x2 = e2[x1]
	x3 = e3[x2]
	...etc...
	xN = eN[xN-1]

We may end up simplifying e1 N times, e2 N-1 times, e3 N-3 times etc.
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795

NB: we don't even look at the RHS to see if it's trivial
We might have
			x = y
where x is used many times, but this is the unique occurrence of y.
We should NOT inline x at all its uses, because then we'd do the same
for y -- aargh!  So we must base this pre-rhs-simplification decision
solely on x's occurrences, not on its rhs.

Evne RHSs labelled InlineMe aren't caught here, because there might be
no benefit from inlining at the call site.

[Sept 01] Don't unconditionally inline a top-level thing, because that
can simply make a static thing into something built dynamically.  E.g.
	x = (a,b)
	main = \s -> h x

[Remember that we treat \s as a one-shot lambda.]  No point in
inlining x unless there is something interesting about the call site.

But watch out: if you aren't careful, some useful foldr/build fusion
can be lost (most notably in spectral/hartel/parstof) because the
foldr didn't see the build.  Doing the dynamic allocation isn't a big
deal, in fact, but losing the fusion can be.  But the right thing here
seems to be to do a callSiteInline based on the fact that there is
something interesting about the call site (it's strict).  Hmm.  That
seems a bit fragile.
796

797
798
799
Conclusion: inline top level things gaily until Phase 0 (the last
phase), at which point don't.

800
801
802
\begin{code}
preInlineUnconditionally :: SimplEnv -> TopLevelFlag -> InId -> Bool
preInlineUnconditionally env top_lvl bndr
803
  | isTopLevel top_lvl, SimplPhase 0 <- phase = False
804
805
806
807
808
809
-- If we don't have this test, consider
--	x = length [1,2,3]
-- The full laziness pass carefully floats all the cons cells to
-- top level, and preInlineUnconditionally floats them all back in.
-- Result is (a) static allocation replaced by dynamic allocation
--	     (b) many simplifier iterations because this tickles
810
--		 a related problem; only one inlining per pass
811
812
813
-- 
-- On the other hand, I have seen cases where top-level fusion is
-- lost if we don't inline top level thing (e.g. string constants)
814
815
816
817
-- Hence the test for phase zero (which is the phase for all the final
-- simplifications).  Until phase zero we take no special notice of
-- top level things, but then we become more leery about inlining
-- them.  
818

819
820
821
822
823
824
825
826
  | not active 		   = False
  | opt_SimplNoPreInlining = False
  | otherwise = case idOccInfo bndr of
		  IAmDead	     -> True	-- Happens in ((\x.1) v)
	  	  OneOcc in_lam once -> not in_lam && once
			-- Not inside a lambda, one occurrence ==> safe!
		  other 	     -> False
  where
827
828
    phase = getMode env
    active = case phase of
829
830
831
832
		   SimplGently  -> isAlwaysActive prag
		   SimplPhase n -> isActive n prag
    prag = idInlinePragma bndr
\end{code}
833

834
835
836
837
838
postInlineUnconditionally
~~~~~~~~~~~~~~~~~~~~~~~~~
@postInlineUnconditionally@ decides whether to unconditionally inline
a thing based on the form of its RHS; in particular if it has a
trivial RHS.  If so, we can inline and discard the binding altogether.
839

840
841
842
843
844
845
NB: a loop breaker has must_keep_binding = True and non-loop-breakers
only have *forward* references Hence, it's safe to discard the binding
	
NOTE: This isn't our last opportunity to inline.  We're at the binding
site right now, and we'll get another opportunity when we get to the
ocurrence(s)
846

847
848
849
850
Note that we do this unconditional inlining only for trival RHSs.
Don't inline even WHNFs inside lambdas; doing so may simply increase
allocation when the function is called. This isn't the last chance; see
NOTE above.
851

852
853
854
NB: Even inline pragmas (e.g. IMustBeINLINEd) are ignored here Why?
Because we don't even want to inline them into the RHS of constructor
arguments. See NOTE above
855

856
857
858
859
860
NB: At one time even NOINLINE was ignored here: if the rhs is trivial
it's best to inline it anyway.  We often get a=E; b=a from desugaring,
with both a and b marked NOINLINE.  But that seems incompatible with
our new view that inlining is like a RULE, so I'm sticking to the 'active'
story for now.
861

862
\begin{code}
863
864
postInlineUnconditionally :: SimplEnv -> OutId -> OccInfo -> OutExpr -> Bool
postInlineUnconditionally env bndr occ_info rhs 
865
866
867
868
869
870
871
872
873
874
875
876
877
878
  =  exprIsTrivial rhs
  && active
  && not (isLoopBreaker occ_info)
  && not (isExportedId bndr)
	-- We used to have (isOneOcc occ_info) instead of
	-- not (isLoopBreaker occ_info) && not (isExportedId bndr)
	-- That was because a rather fragile use of rules got confused
	-- if you inlined even a binding f=g  e.g. We used to have
	--	map = mapList
	-- But now a more precise use of phases has eliminated this problem,
	-- so the is_active test will do the job.  I think.
	--
	-- OLD COMMENT: (delete soon)
	-- Indeed, you might suppose that
879
880
881
882
883
884
	-- there is nothing wrong with substituting for a trivial RHS, even
	-- if it occurs many times.  But consider
	--	x = y
	--	h = _inline_me_ (...x...)
	-- Here we do *not* want to have x inlined, even though the RHS is
	-- trivial, becuase the contract for an INLINE pragma is "no inlining".
885
	-- This is important in the rules for the Prelude 
886
887
888
889
890
891
  where
    active = case getMode env of
		   SimplGently  -> isAlwaysActive prag
		   SimplPhase n -> isActive n prag
    prag = idInlinePragma bndr
\end{code}
892

893
894
blackListInline tells if we must not inline at a call site because the
Id's inline pragma says not to do so.
895

896
897
898
However, blackListInline is ignored for things with with Compulsory inlinings,
because they don't have bindings, so we must inline them no matter how
gentle we are being.
899

900
\begin{code}
901
902
activeInline :: SimplEnv -> OutId -> OccInfo -> Bool
activeInline env id occ
903
  = case getMode env of
904
      SimplGently -> isAlwaysActive prag && isOneOcc occ 
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
	-- No inlining at all when doing gentle stuff,
	-- except for things that occur once
	-- The reason is that too little clean-up happens if you 
	-- don't inline use-once things.   Also a bit of inlining is *good* for
	-- full laziness; it can expose constant sub-expressions.
	-- Example in spectral/mandel/Mandel.hs, where the mandelset 
	-- function gets a useful let-float if you inline windowToViewport

	-- NB: we used to have a second exception, for data con wrappers.
	-- On the grounds that we use gentle mode for rule LHSs, and 
	-- they match better when data con wrappers are inlined.
	-- But that only really applies to the trivial wrappers (like (:)),
	-- and they are now constructed as Compulsory unfoldings (in MkId)
	-- so they'll happen anyway.

920
921
922
      SimplPhase n -> isActive n prag
  where
    prag = idInlinePragma id
923
924
925
926
927
928
929
930

activeRule :: SimplEnv -> Maybe (Activation -> Bool)
-- Nothing => No rules at all
activeRule env
  = case getMode env of
	SimplGently  -> Nothing		-- No rules in gentle mode
	SimplPhase n -> Just (isActive n)
\end{code}	
931
932


933
934
935
936
937
%************************************************************************
%*									*
\subsubsection{Command-line switches}
%*									*
%************************************************************************
938

939
940
941
942
\begin{code}
getSimplIntSwitch :: SwitchChecker -> (Int-> SimplifierSwitch) -> Int
getSimplIntSwitch chkr switch
  = expectJust "getSimplIntSwitch" (intSwitchSet chkr switch)
943

944
switchIsOn :: (switch -> SwitchResult) -> switch -> Bool
945

946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
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
1015
1016
1017
switchIsOn lookup_fn switch
  = case (lookup_fn switch) of
      SwBool False -> False
      _	    	   -> True

intSwitchSet :: (switch -> SwitchResult)
	     -> (Int -> switch)
	     -> Maybe Int

intSwitchSet lookup_fn switch
  = case (lookup_fn (switch (panic "intSwitchSet"))) of
      SwInt int -> Just int
      _	    	-> Nothing
\end{code}


\begin{code}
type SwitchChecker = SimplifierSwitch -> SwitchResult

data SwitchResult
  = SwBool	Bool		-- on/off
  | SwString	FAST_STRING	-- nothing or a String
  | SwInt	Int		-- nothing or an Int

isAmongSimpl :: [SimplifierSwitch] -> SimplifierSwitch -> SwitchResult
isAmongSimpl on_switches		-- Switches mentioned later occur *earlier*
					-- in the list; defaults right at the end.
  = let
	tidied_on_switches = foldl rm_dups [] on_switches
		-- The fold*l* ensures that we keep the latest switches;
		-- ie the ones that occur earliest in the list.

	sw_tbl :: Array Int SwitchResult
	sw_tbl = (array	(0, lAST_SIMPL_SWITCH_TAG) -- bounds...
			all_undefined)
		 // defined_elems

	all_undefined = [ (i, SwBool False) | i <- [0 .. lAST_SIMPL_SWITCH_TAG ] ]

	defined_elems = map mk_assoc_elem tidied_on_switches
    in
    -- (avoid some unboxing, bounds checking, and other horrible things:)
#if __GLASGOW_HASKELL__ < 405
    case sw_tbl of { Array bounds_who_needs_'em stuff ->
#else
    case sw_tbl of { Array _ _ stuff ->
#endif
    \ switch ->
	case (indexArray# stuff (tagOf_SimplSwitch switch)) of
#if __GLASGOW_HASKELL__ < 400
	  Lift v -> v
#elif __GLASGOW_HASKELL__ < 403
	  (# _, v #) -> v
#else
	  (# v #) -> v
#endif
    }
  where
    mk_assoc_elem k@(MaxSimplifierIterations lvl)
	= (iBox (tagOf_SimplSwitch k), SwInt lvl)
    mk_assoc_elem k
	= (iBox (tagOf_SimplSwitch k), SwBool True) -- I'm here, Mom!

    -- cannot have duplicates if we are going to use the array thing
    rm_dups switches_so_far switch
      = if switch `is_elem` switches_so_far
    	then switches_so_far
	else switch : switches_so_far
      where
	sw `is_elem` []     = False
	sw `is_elem` (s:ss) = (tagOf_SimplSwitch sw) ==# (tagOf_SimplSwitch s)
			    || sw `is_elem` ss
1018
1019
\end{code}

1020
These things behave just like enumeration types.
1021
1022

\begin{code}
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
instance Eq SimplifierSwitch where
    a == b = tagOf_SimplSwitch a ==# tagOf_SimplSwitch b

instance Ord SimplifierSwitch where
    a <  b  = tagOf_SimplSwitch a <# tagOf_SimplSwitch b
    a <= b  = tagOf_SimplSwitch a <=# tagOf_SimplSwitch b


tagOf_SimplSwitch (MaxSimplifierIterations _)	= _ILIT(1)
tagOf_SimplSwitch NoCaseOfCase			= _ILIT(2)

-- If you add anything here, be sure to change lAST_SIMPL_SWITCH_TAG, too!

lAST_SIMPL_SWITCH_TAG = 2
1037
\end{code}
1038