2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 \section[SimplCore]{Driver for simplifying @Core@ programs}
7 module SimplCore ( core2core, simplifyExpr ) where
9 #include "HsVersions.h"
11 import DynFlags ( CoreToDo(..), SimplifierSwitch(..),
12 SimplifierMode(..), DynFlags, DynFlag(..), dopt,
15 import HscTypes ( HscEnv(..), ModGuts(..), ExternalPackageState(..),
16 Dependencies( dep_mods ),
18 import CSE ( cseProgram )
19 import Rules ( RuleBase, emptyRuleBase, mkRuleBase, unionRuleBase,
20 extendRuleBaseList, pprRuleBase, ruleCheckProgram,
21 mkSpecInfo, addSpecInfo )
22 import PprCore ( pprCoreBindings, pprCoreExpr, pprRules )
23 import OccurAnal ( occurAnalysePgm, occurAnalyseGlobalExpr )
24 import IdInfo ( setNewStrictnessInfo, newStrictnessInfo,
25 setWorkerInfo, workerInfo,
26 setSpecInfo, specInfo, specInfoRules )
27 import CoreUtils ( coreBindsSize )
28 import Simplify ( simplTopBinds, simplExpr )
29 import SimplEnv ( SimplEnv, simplBinders, mkSimplEnv, setInScopeSet )
31 import ErrUtils ( dumpIfSet, dumpIfSet_dyn, showPass )
32 import CoreLint ( endPass )
33 import VarEnv ( mkInScopeSet )
34 import FloatIn ( floatInwards )
35 import FloatOut ( floatOutwards )
36 import Id ( Id, modifyIdInfo, idInfo, isExportedId, isLocalId,
37 idSpecialisation, setIdSpecialisation, idName )
40 import NameEnv ( lookupNameEnv )
41 import LiberateCase ( liberateCase )
42 import SAT ( doStaticArgs )
43 import Specialise ( specProgram)
44 import SpecConstr ( specConstrProgram)
45 import DmdAnal ( dmdAnalPgm )
46 import WorkWrap ( wwTopBinds )
48 import StrictAnal ( saBinds )
49 import CprAnalyse ( cprAnalyse )
52 import UniqSupply ( UniqSupply, mkSplitUniqSupply, splitUniqSupply )
53 import IO ( hPutStr, stderr )
55 import List ( partition )
56 import Maybes ( orElse )
59 %************************************************************************
61 \subsection{The driver for the simplifier}
63 %************************************************************************
70 core2core hsc_env guts
72 let dflags = hsc_dflags hsc_env
73 core_todos = getCoreToDo dflags
75 us <- mkSplitUniqSupply 's'
76 let (cp_us, ru_us) = splitUniqSupply us
78 -- COMPUTE THE RULE BASE TO USE
79 (imp_rule_base, guts') <- prepareRules hsc_env guts ru_us
82 (stats, guts'') <- doCorePasses hsc_env imp_rule_base cp_us
83 (zeroSimplCount dflags)
86 dumpIfSet_dyn dflags Opt_D_dump_simpl_stats
87 "Grand total simplifier statistics"
93 simplifyExpr :: DynFlags -- includes spec of what core-to-core passes to do
96 -- simplifyExpr is called by the driver to simplify an
97 -- expression typed in at the interactive prompt
98 simplifyExpr dflags expr
100 ; showPass dflags "Simplify"
102 ; us <- mkSplitUniqSupply 's'
104 ; let (expr', _counts) = initSmpl dflags us $
105 simplExprGently gentleSimplEnv expr
107 ; dumpIfSet_dyn dflags Opt_D_dump_simpl "Simplified expression"
113 gentleSimplEnv :: SimplEnv
114 gentleSimplEnv = mkSimplEnv SimplGently
118 doCorePasses :: HscEnv
119 -> RuleBase -- the imported main rule base
120 -> UniqSupply -- uniques
121 -> SimplCount -- simplifier stats
122 -> ModGuts -- local binds in (with rules attached)
123 -> [CoreToDo] -- which passes to do
124 -> IO (SimplCount, ModGuts)
126 doCorePasses hsc_env rb us stats guts []
127 = return (stats, guts)
129 doCorePasses hsc_env rb us stats guts (to_do : to_dos)
131 let (us1, us2) = splitUniqSupply us
132 (stats1, guts1) <- doCorePass to_do hsc_env us1 rb guts
133 doCorePasses hsc_env rb us2 (stats `plusSimplCount` stats1) guts1 to_dos
135 doCorePass (CoreDoSimplify mode sws) = _scc_ "Simplify" simplifyPgm mode sws
136 doCorePass CoreCSE = _scc_ "CommonSubExpr" trBinds cseProgram
137 doCorePass CoreLiberateCase = _scc_ "LiberateCase" trBinds liberateCase
138 doCorePass CoreDoFloatInwards = _scc_ "FloatInwards" trBinds floatInwards
139 doCorePass (CoreDoFloatOutwards f) = _scc_ "FloatOutwards" trBindsU (floatOutwards f)
140 doCorePass CoreDoStaticArgs = _scc_ "StaticArgs" trBinds doStaticArgs
141 doCorePass CoreDoStrictness = _scc_ "Stranal" trBinds dmdAnalPgm
142 doCorePass CoreDoWorkerWrapper = _scc_ "WorkWrap" trBindsU wwTopBinds
143 doCorePass CoreDoSpecialising = _scc_ "Specialise" trBindsU specProgram
144 doCorePass CoreDoSpecConstr = _scc_ "SpecConstr" trBindsU specConstrProgram
145 doCorePass CoreDoGlomBinds = trBinds glomBinds
146 doCorePass CoreDoPrintCore = observe printCore
147 doCorePass (CoreDoRuleCheck phase pat) = observe (ruleCheck phase pat)
148 doCorePass CoreDoNothing = observe (\ _ _ -> return ())
149 #ifdef OLD_STRICTNESS
150 doCorePass CoreDoOldStrictness = _scc_ "OldStrictness" trBinds doOldStrictness
153 #ifdef OLD_STRICTNESS
154 doOldStrictness dfs binds
155 = do binds1 <- saBinds dfs binds
156 binds2 <- cprAnalyse dfs binds1
160 printCore _ binds = dumpIfSet True "Print Core" (pprCoreBindings binds)
162 ruleCheck phase pat dflags binds = do showPass dflags "RuleCheck"
163 printDump (ruleCheckProgram phase pat binds)
165 -- Most passes return no stats and don't change rules
166 trBinds :: (DynFlags -> [CoreBind] -> IO [CoreBind])
167 -> HscEnv -> UniqSupply -> RuleBase -> ModGuts
168 -> IO (SimplCount, ModGuts)
169 trBinds do_pass hsc_env us rb guts
170 = do { binds' <- do_pass dflags (mg_binds guts)
171 ; return (zeroSimplCount dflags, guts { mg_binds = binds' }) }
173 dflags = hsc_dflags hsc_env
175 trBindsU :: (DynFlags -> UniqSupply -> [CoreBind] -> IO [CoreBind])
176 -> HscEnv -> UniqSupply -> RuleBase -> ModGuts
177 -> IO (SimplCount, ModGuts)
178 trBindsU do_pass hsc_env us rb guts
179 = do { binds' <- do_pass dflags us (mg_binds guts)
180 ; return (zeroSimplCount dflags, guts { mg_binds = binds' }) }
182 dflags = hsc_dflags hsc_env
184 -- Observer passes just peek; don't modify the bindings at all
185 observe :: (DynFlags -> [CoreBind] -> IO a)
186 -> HscEnv -> UniqSupply -> RuleBase -> ModGuts
187 -> IO (SimplCount, ModGuts)
188 observe do_pass hsc_env us rb guts
189 = do { binds <- do_pass dflags (mg_binds guts)
190 ; return (zeroSimplCount dflags, guts) }
192 dflags = hsc_dflags hsc_env
197 %************************************************************************
199 \subsection{Dealing with rules}
201 %************************************************************************
203 -- prepareLocalRuleBase takes the CoreBinds and rules defined in this module.
204 -- It attaches those rules that are for local Ids to their binders, and
205 -- returns the remainder attached to Ids in an IdSet.
208 prepareRules :: HscEnv
211 -> IO (RuleBase, -- Rule base for imported things, incl
212 -- (a) rules defined in this module (orphans)
213 -- (b) rules from other modules in home package
214 -- but not things from other packages
216 ModGuts) -- Modified fields are
217 -- (a) Bindings have rules attached,
218 -- (b) Rules are now just orphan rules
220 prepareRules hsc_env@(HscEnv { hsc_dflags = dflags, hsc_HPT = hpt })
221 guts@(ModGuts { mg_binds = binds, mg_deps = deps, mg_rules = local_rules })
223 = do { let -- Simplify the local rules; boringly, we need to make an in-scope set
224 -- from the local binders, to avoid warnings from Simplify.simplVar
225 local_ids = mkInScopeSet (mkVarSet (bindersOfBinds binds))
226 env = setInScopeSet gentleSimplEnv local_ids
227 (better_rules,_) = initSmpl dflags us (mapSmpl (simplRule env) local_rules)
228 home_pkg_rules = hptRules hsc_env (dep_mods deps)
230 -- Find the rules for locally-defined Ids; then we can attach them
231 -- to the binders in the top-level bindings
234 -- - It makes the rules easier to look up
235 -- - It means that transformation rules and specialisations for
236 -- locally defined Ids are handled uniformly
237 -- - It keeps alive things that are referred to only from a rule
238 -- (the occurrence analyser knows about rules attached to Ids)
239 -- - It makes sure that, when we apply a rule, the free vars
240 -- of the RHS are more likely to be in scope
241 -- - The imported rules are carried in the in-scope set
242 -- which is extended on each iteration by the new wave of
243 -- local binders; any rules which aren't on the binding will
244 -- thereby get dropped
245 (rules_for_locals, rules_for_imps) = partition isLocalRule better_rules
246 local_rule_base = extendRuleBaseList emptyRuleBase rules_for_locals
247 binds_w_rules = updateBinders local_rule_base binds
249 hpt_rule_base = mkRuleBase home_pkg_rules
250 imp_rule_base = extendRuleBaseList hpt_rule_base rules_for_imps
252 ; dumpIfSet_dyn dflags Opt_D_dump_rules "Transformation rules"
253 (vcat [text "Local rules", pprRules better_rules,
255 text "Imported rules", pprRuleBase imp_rule_base])
257 ; return (imp_rule_base, guts { mg_binds = binds_w_rules,
258 mg_rules = rules_for_imps })
261 updateBinders :: RuleBase -> [CoreBind] -> [CoreBind]
262 updateBinders local_rules binds
263 = map update_bndrs binds
265 update_bndrs (NonRec b r) = NonRec (update_bndr b) r
266 update_bndrs (Rec prs) = Rec [(update_bndr b, r) | (b,r) <- prs]
268 update_bndr bndr = case lookupNameEnv local_rules (idName bndr) of
270 Just rules -> bndr `setIdSpecialisation` mkSpecInfo rules
274 We must do some gentle simplification on the template (but not the RHS)
275 of each rule. The case that forced me to add this was the fold/build rule,
276 which without simplification looked like:
277 fold k z (build (/\a. g a)) ==> ...
278 This doesn't match unless you do eta reduction on the build argument.
281 simplRule env rule@(BuiltinRule {})
283 simplRule env rule@(Rule { ru_bndrs = bndrs, ru_args = args, ru_rhs = rhs })
284 = simplBinders env bndrs `thenSmpl` \ (env, bndrs') ->
285 mapSmpl (simplExprGently env) args `thenSmpl` \ args' ->
286 simplExprGently env rhs `thenSmpl` \ rhs' ->
287 returnSmpl (rule { ru_bndrs = bndrs', ru_args = args', ru_rhs = rhs' })
289 -- It's important that simplExprGently does eta reduction.
290 -- For example, in a rule like:
291 -- augment g (build h)
292 -- we do not want to get
293 -- augment (\a. g a) (build h)
294 -- otherwise we don't match when given an argument like
297 -- The simplifier does indeed do eta reduction (it's in
298 -- Simplify.completeLam) but only if -O is on.
302 simplExprGently :: SimplEnv -> CoreExpr -> SimplM CoreExpr
303 -- Simplifies an expression
304 -- does occurrence analysis, then simplification
305 -- and repeats (twice currently) because one pass
306 -- alone leaves tons of crud.
307 -- Used (a) for user expressions typed in at the interactive prompt
308 -- (b) the LHS and RHS of a RULE
310 -- The name 'Gently' suggests that the SimplifierMode is SimplGently,
311 -- and in fact that is so.... but the 'Gently' in simplExprGently doesn't
312 -- enforce that; it just simplifies the expression twice
314 simplExprGently env expr
315 = simplExpr env (occurAnalyseGlobalExpr expr) `thenSmpl` \ expr1 ->
316 simplExpr env (occurAnalyseGlobalExpr expr1)
320 %************************************************************************
322 \subsection{Glomming}
324 %************************************************************************
327 glomBinds :: DynFlags -> [CoreBind] -> IO [CoreBind]
328 -- Glom all binds together in one Rec, in case any
329 -- transformations have introduced any new dependencies
331 -- NB: the global invariant is this:
332 -- *** the top level bindings are never cloned, and are always unique ***
334 -- We sort them into dependency order, but applying transformation rules may
335 -- make something at the top refer to something at the bottom:
339 -- RULE: p (q x) = h x
341 -- Applying this rule makes f refer to h,
342 -- although it doesn't appear to in the source program.
343 -- This pass lets us control where it happens.
345 -- NOTICE that this cannot happen for rules whose head is a locally-defined
346 -- function. It only happens for rules whose head is an imported function
347 -- (p in the example above). So, for example, the rule had been
348 -- RULE: f (p x) = h x
349 -- then the rule for f would be attached to f itself (in its IdInfo)
350 -- by prepareLocalRuleBase and h would be regarded by the occurrency
351 -- analyser as free in f.
353 glomBinds dflags binds
354 = do { showPass dflags "GlomBinds" ;
355 let { recd_binds = [Rec (flattenBinds binds)] } ;
357 -- Not much point in printing the result...
358 -- just consumes output bandwidth
362 %************************************************************************
364 \subsection{The driver for the simplifier}
366 %************************************************************************
369 simplifyPgm :: SimplifierMode
370 -> [SimplifierSwitch]
375 -> IO (SimplCount, ModGuts) -- New bindings
377 simplifyPgm mode switches hsc_env us imp_rule_base guts
379 showPass dflags "Simplify";
381 (termination_msg, it_count, counts_out, binds')
382 <- do_iteration us 1 (zeroSimplCount dflags) (mg_binds guts) ;
384 dumpIfSet (dopt Opt_D_verbose_core2core dflags
385 && dopt Opt_D_dump_simpl_stats dflags)
386 "Simplifier statistics"
387 (vcat [text termination_msg <+> text "after" <+> ppr it_count <+> text "iterations",
389 pprSimplCount counts_out]);
391 endPass dflags "Simplify" Opt_D_verbose_core2core binds';
393 return (counts_out, guts { mg_binds = binds' })
396 dflags = hsc_dflags hsc_env
397 phase_info = case mode of
398 SimplGently -> "gentle"
399 SimplPhase n -> show n
401 sw_chkr = isAmongSimpl switches
402 max_iterations = intSwitchSet sw_chkr MaxSimplifierIterations `orElse` 2
404 do_iteration us iteration_no counts binds
405 -- iteration_no is the number of the iteration we are
406 -- about to begin, with '1' for the first
407 | iteration_no > max_iterations -- Stop if we've run out of iterations
410 if max_iterations > 2 then
411 hPutStr stderr ("NOTE: Simplifier still going after " ++
412 show max_iterations ++
413 " iterations; bailing out.\n")
417 -- Subtract 1 from iteration_no to get the
418 -- number of iterations we actually completed
419 return ("Simplifier baled out", iteration_no - 1, counts, binds)
422 -- Try and force thunks off the binds; significantly reduces
423 -- space usage, especially with -O. JRS, 000620.
424 | let sz = coreBindsSize binds in sz == sz
426 -- Occurrence analysis
427 let { tagged_binds = _scc_ "OccAnal" occurAnalysePgm binds } ;
428 dumpIfSet_dyn dflags Opt_D_dump_occur_anal "Occurrence analysis"
429 (pprCoreBindings tagged_binds);
431 -- Get any new rules, and extend the rule base
432 -- We need to do this regularly, because simplification can
433 -- poke on IdInfo thunks, which in turn brings in new rules
434 -- behind the scenes. Otherwise there's a danger we'll simply
435 -- miss the rules for Ids hidden inside imported inlinings
436 eps <- hscEPS hsc_env ;
437 let { rule_base' = unionRuleBase imp_rule_base (eps_rule_base eps)
438 ; simpl_env = mkSimplEnv mode sw_chkr rule_base' } ;
440 -- Simplify the program
441 -- We do this with a *case* not a *let* because lazy pattern
442 -- matching bit us with bad space leak!
443 -- With a let, we ended up with
448 -- case t of {(_,counts') -> if counts'=0 then ... }
449 -- So the conditional didn't force counts', because the
450 -- selection got duplicated. Sigh!
451 case initSmpl dflags us1 (_scc_ "SimplTopBinds" simplTopBinds simpl_env tagged_binds) of {
452 (binds', counts') -> do {
454 let { all_counts = counts `plusSimplCount` counts'
455 ; herald = "Simplifier phase " ++ phase_info ++
456 ", iteration " ++ show iteration_no ++
457 " out of " ++ show max_iterations
460 -- Stop if nothing happened; don't dump output
461 if isZeroSimplCount counts' then
462 return ("Simplifier reached fixed point", iteration_no,
465 -- Short out indirections
466 -- We do this *after* at least one run of the simplifier
467 -- because indirection-shorting uses the export flag on *occurrences*
468 -- and that isn't guaranteed to be ok until after the first run propagates
469 -- stuff from the binding site to its occurrences
470 let { binds'' = _scc_ "ZapInd" shortOutIndirections binds' } ;
472 -- Dump the result of this iteration
473 dumpIfSet_dyn dflags Opt_D_dump_simpl_iterations herald
474 (pprSimplCount counts') ;
475 endPass dflags herald Opt_D_dump_simpl_iterations binds'' ;
478 do_iteration us2 (iteration_no + 1) all_counts binds''
481 (us1, us2) = splitUniqSupply us
485 %************************************************************************
487 Shorting out indirections
489 %************************************************************************
493 x_local = <expression>
497 where x_exported is exported, and x_local is not, then we replace it with this:
499 x_exported = <expression>
503 Without this we never get rid of the x_exported = x_local thing. This
504 save a gratuitous jump (from \tr{x_exported} to \tr{x_local}), and
505 makes strictness information propagate better. This used to happen in
506 the final phase, but it's tidier to do it here.
508 STRICTNESS: if we have done strictness analysis, we want the strictness info on
509 x_local to transfer to x_exported. Hence the copyIdInfo call.
511 RULES: we want to *add* any RULES for x_local to x_exported.
513 Note [Rules and indirection-zapping]
514 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
515 Problem: what if x_exported has a RULE that mentions something in ...bindings...?
516 Then the things mentioned can be out of scope! Solution
517 a) Make sure that in this pass the usage-info from x_exported is
518 available for ...bindings...
519 b) If there are any such RULES, rec-ify the entire top-level.
520 It'll get sorted out next time round
524 The example that went bad on me at one stage was this one:
526 iterate :: (a -> a) -> a -> [a]
528 iterate = iterateList
530 iterateFB c f x = x `c` iterateFB c f (f x)
531 iterateList f x = x : iterateList f (f x)
535 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
536 "iterateFB" iterateFB (:) = iterateList
539 This got shorted out to:
541 iterateList :: (a -> a) -> a -> [a]
542 iterateList = iterate
544 iterateFB c f x = x `c` iterateFB c f (f x)
545 iterate f x = x : iterate f (f x)
548 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
549 "iterateFB" iterateFB (:) = iterate
552 And now we get an infinite loop in the rule system
553 iterate f x -> build (\cn -> iterateFB c f x)
557 Tiresome old solution:
558 don't do shorting out if f has rewrite rules (see shortableIdInfo)
560 New solution (I think):
561 use rule switching-off pragmas to get rid
562 of iterateList in the first place
567 If more than one exported thing is equal to a local thing (i.e., the
568 local thing really is shared), then we do one only:
571 x_exported1 = x_local
572 x_exported2 = x_local
576 x_exported2 = x_exported1
579 We rely on prior eta reduction to simplify things like
581 x_exported = /\ tyvars -> x_local tyvars
585 Hence,there's a possibility of leaving unchanged something like this:
588 x_exported1 = x_local Int
590 By the time we've thrown away the types in STG land this
591 could be eliminated. But I don't think it's very common
592 and it's dangerous to do this fiddling in STG land
593 because we might elminate a binding that's mentioned in the
594 unfolding for something.
597 type IndEnv = IdEnv Id -- Maps local_id -> exported_id
599 shortOutIndirections :: [CoreBind] -> [CoreBind]
600 shortOutIndirections binds
601 | isEmptyVarEnv ind_env = binds
602 | no_need_to_flatten = binds'
603 | otherwise = [Rec (flattenBinds binds')] -- See Note [Rules and indirect-zapping]
605 ind_env = makeIndEnv binds
606 exp_ids = varSetElems ind_env -- These exported Ids are the subjects
607 exp_id_set = mkVarSet exp_ids -- of the indirection-elimination
608 no_need_to_flatten = all (null . specInfoRules . idSpecialisation) exp_ids
609 binds' = concatMap zap binds
611 zap (NonRec bndr rhs) = [NonRec b r | (b,r) <- zapPair (bndr,rhs)]
612 zap (Rec pairs) = [Rec (concatMap zapPair pairs)]
615 | bndr `elemVarSet` exp_id_set = []
616 | Just exp_id <- lookupVarEnv ind_env bndr = [(transferIdInfo exp_id bndr, rhs),
618 | otherwise = [(bndr,rhs)]
620 makeIndEnv :: [CoreBind] -> IndEnv
622 = foldr add_bind emptyVarEnv binds
624 add_bind :: CoreBind -> IndEnv -> IndEnv
625 add_bind (NonRec exported_id rhs) env = add_pair (exported_id, rhs) env
626 add_bind (Rec pairs) env = foldr add_pair env pairs
628 add_pair :: (Id,CoreExpr) -> IndEnv -> IndEnv
629 add_pair (exported_id, Var local_id) env
630 | shortMeOut env exported_id local_id = extendVarEnv env local_id exported_id
631 add_pair (exported_id, rhs) env
634 shortMeOut ind_env exported_id local_id
635 -- The if-then-else stuff is just so I can get a pprTrace to see
636 -- how often I don't get shorting out becuase of IdInfo stuff
637 = if isExportedId exported_id && -- Only if this is exported
639 isLocalId local_id && -- Only if this one is defined in this
640 -- module, so that we *can* change its
641 -- binding to be the exported thing!
643 not (isExportedId local_id) && -- Only if this one is not itself exported,
644 -- since the transformation will nuke it
646 not (local_id `elemVarEnv` ind_env) -- Only if not already substituted for
651 if isEmptySpecInfo (specInfo (idInfo exported_id)) -- Only if no rules
652 then True -- See note on "Messing up rules"
655 pprTrace "shortMeOut:" (ppr exported_id)
664 transferIdInfo :: Id -> Id -> Id
665 transferIdInfo exported_id local_id
666 = modifyIdInfo transfer exported_id
668 local_info = idInfo local_id
669 transfer exp_info = exp_info `setNewStrictnessInfo` newStrictnessInfo local_info
670 `setWorkerInfo` workerInfo local_info
671 `setSpecInfo` addSpecInfo (specInfo exp_info)
672 (specInfo local_info)