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, occurAnalyseExpr )
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 FloatIn ( floatInwards )
34 import FloatOut ( floatOutwards )
35 import Id ( Id, modifyIdInfo, idInfo, isExportedId, isLocalId,
36 idSpecialisation, setIdSpecialisation, idName )
39 import NameEnv ( lookupNameEnv )
40 import LiberateCase ( liberateCase )
41 import SAT ( doStaticArgs )
42 import Specialise ( specProgram)
43 import SpecConstr ( specConstrProgram)
44 import DmdAnal ( dmdAnalPgm )
45 import WorkWrap ( wwTopBinds )
47 import StrictAnal ( saBinds )
48 import CprAnalyse ( cprAnalyse )
51 import UniqSupply ( UniqSupply, mkSplitUniqSupply, splitUniqSupply )
52 import IO ( hPutStr, stderr )
54 import List ( partition )
55 import Maybes ( orElse )
58 %************************************************************************
60 \subsection{The driver for the simplifier}
62 %************************************************************************
69 core2core hsc_env guts
71 let dflags = hsc_dflags hsc_env
72 core_todos = getCoreToDo dflags
74 us <- mkSplitUniqSupply 's'
75 let (cp_us, ru_us) = splitUniqSupply us
77 -- COMPUTE THE RULE BASE TO USE
78 (imp_rule_base, guts') <- prepareRules hsc_env guts ru_us
81 (stats, guts'') <- doCorePasses hsc_env imp_rule_base cp_us
82 (zeroSimplCount dflags)
85 dumpIfSet_dyn dflags Opt_D_dump_simpl_stats
86 "Grand total simplifier statistics"
92 simplifyExpr :: DynFlags -- includes spec of what core-to-core passes to do
95 -- simplifyExpr is called by the driver to simplify an
96 -- expression typed in at the interactive prompt
97 simplifyExpr dflags expr
99 ; showPass dflags "Simplify"
101 ; us <- mkSplitUniqSupply 's'
103 ; let (expr', _counts) = initSmpl dflags us $
104 simplExprGently gentleSimplEnv expr
106 ; dumpIfSet_dyn dflags Opt_D_dump_simpl "Simplified expression"
112 gentleSimplEnv :: SimplEnv
113 gentleSimplEnv = mkSimplEnv SimplGently
117 doCorePasses :: HscEnv
118 -> RuleBase -- the imported main rule base
119 -> UniqSupply -- uniques
120 -> SimplCount -- simplifier stats
121 -> ModGuts -- local binds in (with rules attached)
122 -> [CoreToDo] -- which passes to do
123 -> IO (SimplCount, ModGuts)
125 doCorePasses hsc_env rb us stats guts []
126 = return (stats, guts)
128 doCorePasses hsc_env rb us stats guts (to_do : to_dos)
130 let (us1, us2) = splitUniqSupply us
131 (stats1, guts1) <- doCorePass to_do hsc_env us1 rb guts
132 doCorePasses hsc_env rb us2 (stats `plusSimplCount` stats1) guts1 to_dos
134 doCorePass (CoreDoSimplify mode sws) = _scc_ "Simplify" simplifyPgm mode sws
135 doCorePass CoreCSE = _scc_ "CommonSubExpr" trBinds cseProgram
136 doCorePass CoreLiberateCase = _scc_ "LiberateCase" trBinds liberateCase
137 doCorePass CoreDoFloatInwards = _scc_ "FloatInwards" trBinds floatInwards
138 doCorePass (CoreDoFloatOutwards f) = _scc_ "FloatOutwards" trBindsU (floatOutwards f)
139 doCorePass CoreDoStaticArgs = _scc_ "StaticArgs" trBinds doStaticArgs
140 doCorePass CoreDoStrictness = _scc_ "Stranal" trBinds dmdAnalPgm
141 doCorePass CoreDoWorkerWrapper = _scc_ "WorkWrap" trBindsU wwTopBinds
142 doCorePass CoreDoSpecialising = _scc_ "Specialise" trBindsU specProgram
143 doCorePass CoreDoSpecConstr = _scc_ "SpecConstr" trBindsU specConstrProgram
144 doCorePass CoreDoGlomBinds = trBinds glomBinds
145 doCorePass CoreDoPrintCore = observe printCore
146 doCorePass (CoreDoRuleCheck phase pat) = observe (ruleCheck phase pat)
147 doCorePass CoreDoNothing = observe (\ _ _ -> return ())
148 #ifdef OLD_STRICTNESS
149 doCorePass CoreDoOldStrictness = _scc_ "OldStrictness" trBinds doOldStrictness
152 #ifdef OLD_STRICTNESS
153 doOldStrictness dfs binds
154 = do binds1 <- saBinds dfs binds
155 binds2 <- cprAnalyse dfs binds1
159 printCore _ binds = dumpIfSet True "Print Core" (pprCoreBindings binds)
161 ruleCheck phase pat dflags binds = do showPass dflags "RuleCheck"
162 printDump (ruleCheckProgram phase pat binds)
164 -- Most passes return no stats and don't change rules
165 trBinds :: (DynFlags -> [CoreBind] -> IO [CoreBind])
166 -> HscEnv -> UniqSupply -> RuleBase -> ModGuts
167 -> IO (SimplCount, ModGuts)
168 trBinds do_pass hsc_env us rb guts
169 = do { binds' <- do_pass dflags (mg_binds guts)
170 ; return (zeroSimplCount dflags, guts { mg_binds = binds' }) }
172 dflags = hsc_dflags hsc_env
174 trBindsU :: (DynFlags -> UniqSupply -> [CoreBind] -> IO [CoreBind])
175 -> HscEnv -> UniqSupply -> RuleBase -> ModGuts
176 -> IO (SimplCount, ModGuts)
177 trBindsU do_pass hsc_env us rb guts
178 = do { binds' <- do_pass dflags us (mg_binds guts)
179 ; return (zeroSimplCount dflags, guts { mg_binds = binds' }) }
181 dflags = hsc_dflags hsc_env
183 -- Observer passes just peek; don't modify the bindings at all
184 observe :: (DynFlags -> [CoreBind] -> IO a)
185 -> HscEnv -> UniqSupply -> RuleBase -> ModGuts
186 -> IO (SimplCount, ModGuts)
187 observe do_pass hsc_env us rb guts
188 = do { binds <- do_pass dflags (mg_binds guts)
189 ; return (zeroSimplCount dflags, guts) }
191 dflags = hsc_dflags hsc_env
196 %************************************************************************
198 \subsection{Dealing with rules}
200 %************************************************************************
202 -- prepareLocalRuleBase takes the CoreBinds and rules defined in this module.
203 -- It attaches those rules that are for local Ids to their binders, and
204 -- returns the remainder attached to Ids in an IdSet.
207 prepareRules :: HscEnv
210 -> IO (RuleBase, -- Rule base for imported things, incl
211 -- (a) rules defined in this module (orphans)
212 -- (b) rules from other modules in home package
213 -- but not things from other packages
215 ModGuts) -- Modified fields are
216 -- (a) Bindings have rules attached,
217 -- (b) Rules are now just orphan rules
219 prepareRules hsc_env@(HscEnv { hsc_dflags = dflags, hsc_HPT = hpt })
220 guts@(ModGuts { mg_binds = binds, mg_deps = deps, mg_rules = local_rules })
222 = do { let -- Simplify the local rules; boringly, we need to make an in-scope set
223 -- from the local binders, to avoid warnings from Simplify.simplVar
224 local_ids = mkInScopeSet (mkVarSet (bindersOfBinds binds))
225 env = setInScopeSet gentleSimplEnv local_ids
226 (better_rules,_) = initSmpl dflags us (mapSmpl (simplRule env) local_rules)
227 home_pkg_rules = hptRules hsc_env (dep_mods deps)
229 -- Find the rules for locally-defined Ids; then we can attach them
230 -- to the binders in the top-level bindings
233 -- - It makes the rules easier to look up
234 -- - It means that transformation rules and specialisations for
235 -- locally defined Ids are handled uniformly
236 -- - It keeps alive things that are referred to only from a rule
237 -- (the occurrence analyser knows about rules attached to Ids)
238 -- - It makes sure that, when we apply a rule, the free vars
239 -- of the RHS are more likely to be in scope
240 -- - The imported rules are carried in the in-scope set
241 -- which is extended on each iteration by the new wave of
242 -- local binders; any rules which aren't on the binding will
243 -- thereby get dropped
244 (rules_for_locals, rules_for_imps) = partition isLocalRule better_rules
245 local_rule_base = extendRuleBaseList emptyRuleBase rules_for_locals
246 binds_w_rules = updateBinders local_rule_base binds
248 hpt_rule_base = mkRuleBase home_pkg_rules
249 imp_rule_base = extendRuleBaseList hpt_rule_base rules_for_imps
251 ; dumpIfSet_dyn dflags Opt_D_dump_rules "Transformation rules"
252 (vcat [text "Local rules", pprRules better_rules,
254 text "Imported rules", pprRuleBase imp_rule_base])
256 ; return (imp_rule_base, guts { mg_binds = binds_w_rules,
257 mg_rules = rules_for_imps })
260 updateBinders :: RuleBase -> [CoreBind] -> [CoreBind]
261 updateBinders local_rules binds
262 = map update_bndrs binds
264 update_bndrs (NonRec b r) = NonRec (update_bndr b) r
265 update_bndrs (Rec prs) = Rec [(update_bndr b, r) | (b,r) <- prs]
267 update_bndr bndr = case lookupNameEnv local_rules (idName bndr) of
269 Just rules -> bndr `setIdSpecialisation` mkSpecInfo rules
273 We must do some gentle simplification on the template (but not the RHS)
274 of each rule. The case that forced me to add this was the fold/build rule,
275 which without simplification looked like:
276 fold k z (build (/\a. g a)) ==> ...
277 This doesn't match unless you do eta reduction on the build argument.
280 simplRule env rule@(BuiltinRule {})
282 simplRule env rule@(Rule { ru_bndrs = bndrs, ru_args = args, ru_rhs = rhs })
283 = simplBinders env bndrs `thenSmpl` \ (env, bndrs') ->
284 mapSmpl (simplExprGently env) args `thenSmpl` \ args' ->
285 simplExprGently env rhs `thenSmpl` \ rhs' ->
286 returnSmpl (rule { ru_bndrs = bndrs', ru_args = args', ru_rhs = rhs' })
288 -- It's important that simplExprGently does eta reduction.
289 -- For example, in a rule like:
290 -- augment g (build h)
291 -- we do not want to get
292 -- augment (\a. g a) (build h)
293 -- otherwise we don't match when given an argument like
296 -- The simplifier does indeed do eta reduction (it's in
297 -- Simplify.completeLam) but only if -O is on.
301 simplExprGently :: SimplEnv -> CoreExpr -> SimplM CoreExpr
302 -- Simplifies an expression
303 -- does occurrence analysis, then simplification
304 -- and repeats (twice currently) because one pass
305 -- alone leaves tons of crud.
306 -- Used (a) for user expressions typed in at the interactive prompt
307 -- (b) the LHS and RHS of a RULE
309 -- The name 'Gently' suggests that the SimplifierMode is SimplGently,
310 -- and in fact that is so.... but the 'Gently' in simplExprGently doesn't
311 -- enforce that; it just simplifies the expression twice
313 simplExprGently env expr
314 = simplExpr env (occurAnalyseExpr expr) `thenSmpl` \ expr1 ->
315 simplExpr env (occurAnalyseExpr expr1)
319 %************************************************************************
321 \subsection{Glomming}
323 %************************************************************************
326 glomBinds :: DynFlags -> [CoreBind] -> IO [CoreBind]
327 -- Glom all binds together in one Rec, in case any
328 -- transformations have introduced any new dependencies
330 -- NB: the global invariant is this:
331 -- *** the top level bindings are never cloned, and are always unique ***
333 -- We sort them into dependency order, but applying transformation rules may
334 -- make something at the top refer to something at the bottom:
338 -- RULE: p (q x) = h x
340 -- Applying this rule makes f refer to h,
341 -- although it doesn't appear to in the source program.
342 -- This pass lets us control where it happens.
344 -- NOTICE that this cannot happen for rules whose head is a locally-defined
345 -- function. It only happens for rules whose head is an imported function
346 -- (p in the example above). So, for example, the rule had been
347 -- RULE: f (p x) = h x
348 -- then the rule for f would be attached to f itself (in its IdInfo)
349 -- by prepareLocalRuleBase and h would be regarded by the occurrency
350 -- analyser as free in f.
352 glomBinds dflags binds
353 = do { showPass dflags "GlomBinds" ;
354 let { recd_binds = [Rec (flattenBinds binds)] } ;
356 -- Not much point in printing the result...
357 -- just consumes output bandwidth
361 %************************************************************************
363 \subsection{The driver for the simplifier}
365 %************************************************************************
368 simplifyPgm :: SimplifierMode
369 -> [SimplifierSwitch]
374 -> IO (SimplCount, ModGuts) -- New bindings
376 simplifyPgm mode switches hsc_env us imp_rule_base guts
378 showPass dflags "Simplify";
380 (termination_msg, it_count, counts_out, binds')
381 <- do_iteration us 1 (zeroSimplCount dflags) (mg_binds guts) ;
383 dumpIfSet (dopt Opt_D_verbose_core2core dflags
384 && dopt Opt_D_dump_simpl_stats dflags)
385 "Simplifier statistics"
386 (vcat [text termination_msg <+> text "after" <+> ppr it_count <+> text "iterations",
388 pprSimplCount counts_out]);
390 endPass dflags "Simplify" Opt_D_verbose_core2core binds';
392 return (counts_out, guts { mg_binds = binds' })
395 dflags = hsc_dflags hsc_env
396 phase_info = case mode of
397 SimplGently -> "gentle"
398 SimplPhase n -> show n
400 sw_chkr = isAmongSimpl switches
401 max_iterations = intSwitchSet sw_chkr MaxSimplifierIterations `orElse` 2
403 do_iteration us iteration_no counts binds
404 -- iteration_no is the number of the iteration we are
405 -- about to begin, with '1' for the first
406 | iteration_no > max_iterations -- Stop if we've run out of iterations
409 if max_iterations > 2 then
410 hPutStr stderr ("NOTE: Simplifier still going after " ++
411 show max_iterations ++
412 " iterations; bailing out.\n")
416 -- Subtract 1 from iteration_no to get the
417 -- number of iterations we actually completed
418 return ("Simplifier baled out", iteration_no - 1, counts, binds)
421 -- Try and force thunks off the binds; significantly reduces
422 -- space usage, especially with -O. JRS, 000620.
423 | let sz = coreBindsSize binds in sz == sz
425 -- Occurrence analysis
426 let { tagged_binds = _scc_ "OccAnal" occurAnalysePgm binds } ;
427 dumpIfSet_dyn dflags Opt_D_dump_occur_anal "Occurrence analysis"
428 (pprCoreBindings tagged_binds);
430 -- Get any new rules, and extend the rule base
431 -- We need to do this regularly, because simplification can
432 -- poke on IdInfo thunks, which in turn brings in new rules
433 -- behind the scenes. Otherwise there's a danger we'll simply
434 -- miss the rules for Ids hidden inside imported inlinings
435 eps <- hscEPS hsc_env ;
436 let { rule_base' = unionRuleBase imp_rule_base (eps_rule_base eps)
437 ; simpl_env = mkSimplEnv mode sw_chkr rule_base' } ;
439 -- Simplify the program
440 -- We do this with a *case* not a *let* because lazy pattern
441 -- matching bit us with bad space leak!
442 -- With a let, we ended up with
447 -- case t of {(_,counts') -> if counts'=0 then ... }
448 -- So the conditional didn't force counts', because the
449 -- selection got duplicated. Sigh!
450 case initSmpl dflags us1 (_scc_ "SimplTopBinds" simplTopBinds simpl_env tagged_binds) of {
451 (binds', counts') -> do {
453 let { all_counts = counts `plusSimplCount` counts'
454 ; herald = "Simplifier phase " ++ phase_info ++
455 ", iteration " ++ show iteration_no ++
456 " out of " ++ show max_iterations
459 -- Stop if nothing happened; don't dump output
460 if isZeroSimplCount counts' then
461 return ("Simplifier reached fixed point", iteration_no,
464 -- Short out indirections
465 -- We do this *after* at least one run of the simplifier
466 -- because indirection-shorting uses the export flag on *occurrences*
467 -- and that isn't guaranteed to be ok until after the first run propagates
468 -- stuff from the binding site to its occurrences
469 let { binds'' = _scc_ "ZapInd" shortOutIndirections binds' } ;
471 -- Dump the result of this iteration
472 dumpIfSet_dyn dflags Opt_D_dump_simpl_iterations herald
473 (pprSimplCount counts') ;
474 endPass dflags herald Opt_D_dump_simpl_iterations binds'' ;
477 do_iteration us2 (iteration_no + 1) all_counts binds''
480 (us1, us2) = splitUniqSupply us
484 %************************************************************************
486 Shorting out indirections
488 %************************************************************************
492 x_local = <expression>
496 where x_exported is exported, and x_local is not, then we replace it with this:
498 x_exported = <expression>
502 Without this we never get rid of the x_exported = x_local thing. This
503 save a gratuitous jump (from \tr{x_exported} to \tr{x_local}), and
504 makes strictness information propagate better. This used to happen in
505 the final phase, but it's tidier to do it here.
507 STRICTNESS: if we have done strictness analysis, we want the strictness info on
508 x_local to transfer to x_exported. Hence the copyIdInfo call.
510 RULES: we want to *add* any RULES for x_local to x_exported.
512 Note [Rules and indirection-zapping]
513 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
514 Problem: what if x_exported has a RULE that mentions something in ...bindings...?
515 Then the things mentioned can be out of scope! Solution
516 a) Make sure that in this pass the usage-info from x_exported is
517 available for ...bindings...
518 b) If there are any such RULES, rec-ify the entire top-level.
519 It'll get sorted out next time round
523 The example that went bad on me at one stage was this one:
525 iterate :: (a -> a) -> a -> [a]
527 iterate = iterateList
529 iterateFB c f x = x `c` iterateFB c f (f x)
530 iterateList f x = x : iterateList f (f x)
534 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
535 "iterateFB" iterateFB (:) = iterateList
538 This got shorted out to:
540 iterateList :: (a -> a) -> a -> [a]
541 iterateList = iterate
543 iterateFB c f x = x `c` iterateFB c f (f x)
544 iterate f x = x : iterate f (f x)
547 "iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
548 "iterateFB" iterateFB (:) = iterate
551 And now we get an infinite loop in the rule system
552 iterate f x -> build (\cn -> iterateFB c f x)
556 Tiresome old solution:
557 don't do shorting out if f has rewrite rules (see shortableIdInfo)
559 New solution (I think):
560 use rule switching-off pragmas to get rid
561 of iterateList in the first place
566 If more than one exported thing is equal to a local thing (i.e., the
567 local thing really is shared), then we do one only:
570 x_exported1 = x_local
571 x_exported2 = x_local
575 x_exported2 = x_exported1
578 We rely on prior eta reduction to simplify things like
580 x_exported = /\ tyvars -> x_local tyvars
584 Hence,there's a possibility of leaving unchanged something like this:
587 x_exported1 = x_local Int
589 By the time we've thrown away the types in STG land this
590 could be eliminated. But I don't think it's very common
591 and it's dangerous to do this fiddling in STG land
592 because we might elminate a binding that's mentioned in the
593 unfolding for something.
596 type IndEnv = IdEnv Id -- Maps local_id -> exported_id
598 shortOutIndirections :: [CoreBind] -> [CoreBind]
599 shortOutIndirections binds
600 | isEmptyVarEnv ind_env = binds
601 | no_need_to_flatten = binds'
602 | otherwise = [Rec (flattenBinds binds')] -- See Note [Rules and indirect-zapping]
604 ind_env = makeIndEnv binds
605 exp_ids = varSetElems ind_env -- These exported Ids are the subjects
606 exp_id_set = mkVarSet exp_ids -- of the indirection-elimination
607 no_need_to_flatten = all (null . specInfoRules . idSpecialisation) exp_ids
608 binds' = concatMap zap binds
610 zap (NonRec bndr rhs) = [NonRec b r | (b,r) <- zapPair (bndr,rhs)]
611 zap (Rec pairs) = [Rec (concatMap zapPair pairs)]
614 | bndr `elemVarSet` exp_id_set = []
615 | Just exp_id <- lookupVarEnv ind_env bndr = [(transferIdInfo exp_id bndr, rhs),
617 | otherwise = [(bndr,rhs)]
619 makeIndEnv :: [CoreBind] -> IndEnv
621 = foldr add_bind emptyVarEnv binds
623 add_bind :: CoreBind -> IndEnv -> IndEnv
624 add_bind (NonRec exported_id rhs) env = add_pair (exported_id, rhs) env
625 add_bind (Rec pairs) env = foldr add_pair env pairs
627 add_pair :: (Id,CoreExpr) -> IndEnv -> IndEnv
628 add_pair (exported_id, Var local_id) env
629 | shortMeOut env exported_id local_id = extendVarEnv env local_id exported_id
630 add_pair (exported_id, rhs) env
633 shortMeOut ind_env exported_id local_id
634 -- The if-then-else stuff is just so I can get a pprTrace to see
635 -- how often I don't get shorting out becuase of IdInfo stuff
636 = if isExportedId exported_id && -- Only if this is exported
638 isLocalId local_id && -- Only if this one is defined in this
639 -- module, so that we *can* change its
640 -- binding to be the exported thing!
642 not (isExportedId local_id) && -- Only if this one is not itself exported,
643 -- since the transformation will nuke it
645 not (local_id `elemVarEnv` ind_env) -- Only if not already substituted for
650 if isEmptySpecInfo (specInfo (idInfo exported_id)) -- Only if no rules
651 then True -- See note on "Messing up rules"
654 pprTrace "shortMeOut:" (ppr exported_id)
663 transferIdInfo :: Id -> Id -> Id
664 transferIdInfo exported_id local_id
665 = modifyIdInfo transfer exported_id
667 local_info = idInfo local_id
668 transfer exp_info = exp_info `setNewStrictnessInfo` newStrictnessInfo local_info
669 `setWorkerInfo` workerInfo local_info
670 `setSpecInfo` addSpecInfo (specInfo exp_info)
671 (specInfo local_info)