2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
4 \section[SimplCore]{Driver for simplifying @Core@ programs}
7 #include "HsVersions.h"
9 module SimplCore ( core2core ) where
13 import AnalFBWW ( analFBWW )
14 import Bag ( isEmptyBag, foldBag )
15 import BinderInfo ( BinderInfo{-instance Outputable-} )
16 import CgCompInfo ( uNFOLDING_CREATION_THRESHOLD,
17 uNFOLDING_USE_THRESHOLD,
18 uNFOLDING_OVERRIDE_THRESHOLD,
19 uNFOLDING_CON_DISCOUNT_WEIGHT
21 import CmdLineOpts ( CoreToDo(..), SimplifierSwitch(..), switchIsOn,
23 opt_D_simplifier_stats,
24 opt_D_verbose_core2core,
27 opt_ReportWhyUnfoldingsDisallowed,
29 opt_UnfoldingCreationThreshold,
30 opt_UnfoldingOverrideThreshold,
31 opt_UnfoldingUseThreshold
33 import CoreLint ( lintCoreBindings )
36 import CoreUtils ( substCoreBindings, manifestlyWHNF )
37 import ErrUtils ( ghcExit )
38 import FloatIn ( floatInwards )
39 import FloatOut ( floatOutwards )
40 import FoldrBuildWW ( mkFoldrBuildWW )
41 import Id ( idType, toplevelishId, idWantsToBeINLINEd,
42 unfoldingUnfriendlyId,
43 nullIdEnv, addOneToIdEnv, delOneFromIdEnv,
44 lookupIdEnv, IdEnv(..),
45 GenId{-instance Outputable-}
47 import IdInfo ( mkUnfolding )
48 import LiberateCase ( liberateCase )
49 import MagicUFs ( MagicUnfoldingFun )
50 import Maybes ( maybeToBool )
51 import Outputable ( Outputable(..){-instance * (,) -} )
52 import PprCore ( pprCoreBinding, GenCoreExpr{-instance Outputable-} )
53 import PprStyle ( PprStyle(..) )
54 import PprType ( GenType{-instance Outputable-}, GenTyVar{-ditto-} )
55 import Pretty ( ppShow, ppAboves, ppAbove, ppCat, ppStr )
56 import SAT ( doStaticArgs )
57 import SCCauto ( addAutoCostCentres )
58 import SimplMonad ( zeroSimplCount, showSimplCount, SimplCount )
59 import SimplPgm ( simplifyPgm )
60 import SimplVar ( leastItCouldCost )
62 import SpecUtils ( pprSpecErrs )
63 import StrictAnal ( saWwTopBinds )
64 import TyVar ( nullTyVarEnv, GenTyVar{-instance Eq-} )
65 import Unique ( Unique{-instance Eq-} )
66 import UniqSupply ( splitUniqSupply )
67 import Util ( panic{-ToDo:rm-} )
70 import Deforest ( deforestProgram )
71 import DefUtils ( deforestable )
74 isWrapperFor = panic "SimplCore.isWrapperFor (ToDo)"
75 isWrapperId = panic "SimplCore.isWrapperId (ToDo)"
79 core2core :: [CoreToDo] -- spec of what core-to-core passes to do
80 -> FAST_STRING -- module name (profiling only)
81 -> PprStyle -- printing style (for debugging only)
82 -> UniqSupply -- a name supply
83 -> [TyCon] -- local data tycons and tycon specialisations
84 -> FiniteMap TyCon [(Bool, [Maybe Type])]
85 -> [CoreBinding] -- input...
87 ([CoreBinding], -- results: program, plus...
88 IdEnv UnfoldingDetails, -- unfoldings to be exported from here
89 SpecialiseData) -- specialisation data
91 core2core core_todos module_name ppr_style us local_tycons tycon_specs binds
93 if null core_todos then -- very rare, I suspect...
94 -- well, we still must do some renumbering
96 (substCoreBindings nullIdEnv nullTyVarEnv binds us,
101 (if do_verbose_core2core then
102 hPutStr stderr "VERBOSE CORE-TO-CORE:\n"
105 -- better do the main business
106 foldl_mn do_core_pass
107 (binds, us, nullIdEnv, init_specdata, zeroSimplCount)
109 >>= \ (processed_binds, _, inline_env, spec_data, simpl_stats) ->
111 (if opt_D_simplifier_stats
112 then hPutStr stderr ("\nSimplifier Stats:\n")
114 hPutStr stderr (showSimplCount simpl_stats)
120 return (processed_binds, inline_env, spec_data)
123 init_specdata = initSpecData local_tycons tycon_specs
125 do_verbose_core2core = opt_D_verbose_core2core
127 lib_case_threshold -- ToDo: HACK HACK HACK : FIX ME FIX ME FIX ME
128 -- Use 4x a known threshold
129 = case opt_UnfoldingOverrideThreshold of
130 Nothing -> 4 * uNFOLDING_USE_THRESHOLD
134 core_linter = if opt_DoCoreLinting
135 then lintCoreBindings ppr_style
136 else ( \ whodunnit spec_done binds -> binds )
139 do_core_pass info@(binds, us, inline_env, spec_data, simpl_stats) to_do
141 (us1, us2) = splitUniqSupply us
144 CoreDoSimplify simpl_sw_chkr
145 -> BSCC("CoreSimplify")
146 begin_pass ("Simplify" ++ if switchIsOn simpl_sw_chkr SimplDoFoldrBuild
147 then " (foldr/build)" else "") >>
148 case (simplifyPgm binds simpl_sw_chkr simpl_stats us1) of
149 (p, it_cnt, simpl_stats2)
150 -> end_pass False us2 p inline_env spec_data simpl_stats2
151 ("Simplify (" ++ show it_cnt ++ ")"
152 ++ if switchIsOn simpl_sw_chkr SimplDoFoldrBuild
153 then " foldr/build" else "")
156 CoreDoFoldrBuildWorkerWrapper
157 -> BSCC("CoreDoFoldrBuildWorkerWrapper")
159 case (mkFoldrBuildWW us1 binds) of { binds2 ->
160 end_pass False us2 binds2 inline_env spec_data simpl_stats "FBWW"
163 CoreDoFoldrBuildWWAnal
164 -> BSCC("CoreDoFoldrBuildWWAnal")
165 begin_pass "AnalFBWW" >>
166 case (analFBWW binds) of { binds2 ->
167 end_pass False us2 binds2 inline_env spec_data simpl_stats "AnalFBWW"
171 -> BSCC("LiberateCase")
172 begin_pass "LiberateCase" >>
173 case (liberateCase lib_case_threshold binds) of { binds2 ->
174 end_pass False us2 binds2 inline_env spec_data simpl_stats "LiberateCase"
177 CoreDoCalcInlinings1 -- avoid inlinings w/ cost-centres
178 -> BSCC("CoreInlinings1")
179 begin_pass "CalcInlinings" >>
180 case (calcInlinings False inline_env binds) of { inline_env2 ->
181 end_pass False us2 binds inline_env2 spec_data simpl_stats "CalcInlinings"
184 CoreDoCalcInlinings2 -- allow inlinings w/ cost-centres
185 -> BSCC("CoreInlinings2")
186 begin_pass "CalcInlinings" >>
187 case (calcInlinings True inline_env binds) of { inline_env2 ->
188 end_pass False us2 binds inline_env2 spec_data simpl_stats "CalcInlinings"
192 -> BSCC("FloatInwards")
193 begin_pass "FloatIn" >>
194 case (floatInwards binds) of { binds2 ->
195 end_pass False us2 binds2 inline_env spec_data simpl_stats "FloatIn"
199 -> BSCC("CoreFloating")
200 begin_pass "FloatOut" >>
201 case (floatOutwards us1 binds) of { binds2 ->
202 end_pass False us2 binds2 inline_env spec_data simpl_stats "FloatOut"
206 -> BSCC("CoreStaticArgs")
207 begin_pass "StaticArgs" >>
208 case (doStaticArgs binds us1) of { binds2 ->
209 end_pass False us2 binds2 inline_env spec_data simpl_stats "StaticArgs"
210 -- Binds really should be dependency-analysed for static-
211 -- arg transformation... Not to worry, they probably are.
212 -- (I don't think it *dies* if they aren't [WDP 94/04/15])
216 -> BSCC("CoreStranal")
217 begin_pass "StrAnal" >>
218 case (saWwTopBinds us1 binds) of { binds2 ->
219 end_pass False us2 binds2 inline_env spec_data simpl_stats "StrAnal"
223 -> BSCC("Specialise")
224 begin_pass "Specialise" >>
225 case (specProgram us1 binds spec_data) of {
226 (p, spec_data2@(SpecData _ spec_noerrs _ _ _
227 spec_errs spec_warn spec_tyerrs)) ->
229 -- if we got errors, we die straight away
230 (if not spec_noerrs ||
231 (opt_ShowImportSpecs && not (isEmptyBag spec_warn)) then
232 hPutStr stderr (ppShow 1000 {-pprCols-}
233 (pprSpecErrs module_name spec_errs spec_warn spec_tyerrs))
234 >> hPutStr stderr "\n"
238 (if not spec_noerrs then -- Stop here if specialisation errors occured
243 end_pass False us2 p inline_env spec_data2 simpl_stats "Specialise"
249 -> error "ERROR: CoreDoDeforest: not built into compiler\n"
251 -> BSCC("Deforestation")
252 begin_pass "Deforestation" >>
253 case (deforestProgram binds us1) of { binds2 ->
254 end_pass False us2 binds2 inline_env spec_data simpl_stats "Deforestation"
259 CoreDoAutoCostCentres
261 begin_pass "AutoSCCs" >>
262 case (addAutoCostCentres module_name binds) of { binds2 ->
263 end_pass False us2 binds2 inline_env spec_data simpl_stats "AutoSCCs"
267 CoreDoPrintCore -- print result of last pass
268 -> end_pass True us2 binds inline_env spec_data simpl_stats "Print"
271 -------------------------------------------------
274 = if opt_D_show_passes
275 then \ what -> hPutStr stderr ("*** Core2Core: "++what++"\n")
276 else \ what -> return ()
278 end_pass print us2 binds2 inline_env2
279 spec_data2@(SpecData spec_done _ _ _ _ _ _ _)
281 = -- report verbosely, if required
282 (if (do_verbose_core2core && not print) ||
283 (print && not do_verbose_core2core)
285 hPutStr stderr ("\n*** "++what++":\n")
287 hPutStr stderr (ppShow 1000
288 (ppAboves (map (pprCoreBinding ppr_style) binds2)))
294 linted_binds = core_linter what spec_done binds2
297 (linted_binds, -- processed binds, possibly run thru CoreLint
298 us2, -- UniqueSupply for the next guy
299 inline_env2, -- possibly-updated inline env
300 spec_data2, -- possibly-updated specialisation info
301 simpl_stats2 -- accumulated simplifier stats
304 -- here so it can be inlined...
305 foldl_mn f z [] = return z
306 foldl_mn f z (x:xs) = f z x >>= \ zz ->
310 --- ToDo: maybe move elsewhere ---
312 For top-level, exported binders that either (a)~have been INLINEd by
313 the programmer or (b)~are sufficiently ``simple'' that they should be
314 inlined, we want to record this info in a suitable IdEnv.
316 But: if something has a ``wrapper unfolding,'' we do NOT automatically
317 give it a regular unfolding (exception below). We usually assume its
318 worker will get a ``regular'' unfolding. We can then treat these two
319 levels of unfolding separately (we tend to be very friendly towards
320 wrapper unfoldings, for example), giving more fine-tuned control.
322 The exception is: If the ``regular unfolding'' mentions no other
323 global Ids (i.e., it's all PrimOps and cases and local Ids) then we
324 assume it must be really good and we take it anyway.
326 We also need to check that everything in the RHS (values and types)
327 will be visible on the other side of an interface, too.
330 calcInlinings :: Bool -- True => inlinings with _scc_s are OK
331 -> IdEnv UnfoldingDetails
333 -> IdEnv UnfoldingDetails
335 calcInlinings scc_s_OK inline_env_so_far top_binds
337 result = foldl calci inline_env_so_far top_binds
339 --pprTrace "inline env:\n" (ppAboves (map pp_item (getIdEnvMapping result)))
342 pp_item (binder, details)
343 = ppCat [ppr PprDebug binder, ppStr "=>", pp_det details]
345 pp_det NoUnfoldingDetails = ppStr "_N_"
346 --LATER: pp_det (IWantToBeINLINEd _) = ppStr "INLINE"
347 pp_det (GenForm _ _ expr guide)
348 = ppAbove (ppr PprDebug guide) (ppr PprDebug expr)
349 pp_det other = ppStr "???"
352 my_trace = if opt_ReportWhyUnfoldingsDisallowed
354 else \ msg stuff -> stuff
356 (unfolding_creation_threshold, explicit_creation_threshold)
357 = case opt_UnfoldingCreationThreshold of
358 Nothing -> (uNFOLDING_CREATION_THRESHOLD, False)
359 Just xx -> (xx, True)
362 = case opt_UnfoldingUseThreshold of
363 Nothing -> uNFOLDING_USE_THRESHOLD
366 unfold_override_threshold
367 = case opt_UnfoldingOverrideThreshold of
368 Nothing -> uNFOLDING_OVERRIDE_THRESHOLD
371 con_discount_weight = uNFOLDING_CON_DISCOUNT_WEIGHT
373 calci inline_env (Rec pairs)
374 = foldl (calc True{-recursive-}) inline_env pairs
376 calci inline_env bind@(NonRec binder rhs)
377 = calc False{-not recursive-} inline_env (binder, rhs)
379 ---------------------------------------
381 calc is_recursive inline_env (binder, rhs)
382 | not (toplevelishId binder)
383 = --pprTrace "giving up on not top-level:" (ppr PprDebug binder)
386 | rhs_mentions_an_unmentionable
387 || (not explicit_INLINE_requested
388 && (rhs_looks_like_a_caf || guidance_says_don't || guidance_size_too_big))
391 = if explicit_INLINE_requested
392 && not (isWrapperId binder) -- these always claim to be INLINEd
393 && not have_inlining_already
394 then trace -- we'd better have a look...
397 which = if scc_s_OK then " (late):" else " (early):"
399 my_my_trace ("unfolding disallowed for"++which++(ppShow 80 (ppr PprDebug binder))) (
403 | rhs `isWrapperFor` binder
404 -- Don't add an explicit "unfolding"; let the worker/wrapper
405 -- stuff do its thing. INLINE things don't get w/w'd, so
409 #if ! OMIT_DEFORESTER
410 -- For the deforester: bypass the barbed wire for recursive
411 -- functions that want to be inlined and are tagged deforestable
412 -- by the user, allowing these things to be communicated
413 -- across module boundaries.
416 explicit_INLINE_requested &&
417 deforestable binder &&
418 scc_s_OK -- hack, only get them in
420 = glorious_success UnfoldAlways
423 | is_recursive && not rhs_looks_like_a_data_val
424 -- The only recursive defns we are prepared to tolerate at the
425 -- moment is top-level very-obviously-a-data-value ones.
426 -- We *need* these for dictionaries to be exported!
427 = --pprTrace "giving up on rec:" (ppr PprDebug binder)
430 -- Not really interested unless it's exported, but doing it
431 -- this way (not worrying about export-ness) gets us all the
432 -- workers/specs, etc., too; which we will need for generating
433 -- interfaces. We are also not interested if this binder is
434 -- in the environment we already have (perhaps from a previous
435 -- run of calcInlinings -- "earlier" is presumed to mean
438 | explicit_INLINE_requested
439 = glorious_success UnfoldAlways
442 = glorious_success guidance
446 = calcUnfoldingGuidance scc_s_OK max_out_threshold rhs
448 max_out_threshold = if explicit_INLINE_requested
449 then 100000 -- you asked for it, you got it
450 else unfolding_creation_threshold
454 UnfoldAlways -> 0 -- *extremely* small
455 EssentialUnfolding -> 0 -- ditto
456 UnfoldIfGoodArgs _ _ _ size -> size
458 guidance_says_don't = case guidance of { UnfoldNever -> True; _ -> False }
460 guidance_size_too_big
461 -- Does the guidance suggest that this unfolding will
462 -- be of no use *no matter* the arguments given to it?
463 -- Could be more sophisticated...
465 UnfoldAlways -> False
466 EssentialUnfolding -> False
467 UnfoldIfGoodArgs _ no_val_args arg_info_vec size
469 -> if explicit_creation_threshold then
470 False -- user set threshold; don't second-guess...
472 else if no_val_args == 0 && rhs_looks_like_a_data_val then
473 False -- we'd like a top-level data constr to be
474 -- visible even if it is never unfolded
478 = leastItCouldCost con_discount_weight size no_val_args
479 arg_info_vec rhs_arg_tys
481 -- (if (unfold_use_threshold < cost) then (pprTrace "cost:" (ppInt cost)) else \x->x ) (
482 unfold_use_threshold < cost
486 rhs_looks_like_a_caf = not (manifestlyWHNF rhs)
488 rhs_looks_like_a_data_val
489 = case (collectBinders rhs) of
490 (_, _, [], Con _ _) -> True
494 = case (collectBinders rhs) of
495 (_, _, val_binders, _) -> map idType val_binders
497 (mentioned_ids, _, _, mentions_litlit)
498 = mentionedInUnfolding (\x -> x) rhs
500 rhs_mentions_an_unmentionable
501 = foldBag (||) unfoldingUnfriendlyId False mentioned_ids
503 -- ToDo: probably need to chk tycons/classes...
505 mentions_no_other_ids = isEmptyBag mentioned_ids
507 explicit_INLINE_requested
508 -- did it come from a user {-# INLINE ... #-}?
509 -- (Warning: must avoid including wrappers.)
510 = idWantsToBeINLINEd binder
511 && not (rhs `isWrapperFor` binder)
513 have_inlining_already = maybeToBool (lookupIdEnv inline_env binder)
515 ignominious_defeat = inline_env -- just give back what we got
518 "glorious_success" is ours if we've found a suitable unfolding.
520 But we check for a couple of fine points.
522 (1) If this Id already has an inlining in the inline_env,
523 we don't automatically take it -- the earlier one is
524 "likely" to be better.
526 But if the new one doesn't mention any other global
527 Ids, and it's pretty small (< UnfoldingOverrideThreshold),
528 then we take the chance that the new one *is* better.
530 (2) If we have an Id w/ a worker/wrapper split (with
531 an unfolding for the wrapper), we tend to want to keep
532 it -- and *nuke* any inlining that we conjured up
535 But, again, if this unfolding doesn't mention any
536 other global Ids (and small enough), then it is
537 probably better than the worker/wrappery, so we take
540 glorious_success guidance
542 new_env = addOneToIdEnv inline_env binder (mkUnfolding guidance rhs)
544 foldr_building = opt_FoldrBuildOn
546 if (not have_inlining_already) then
547 -- Not in env: we take it no matter what
548 -- NB: we could check for worker/wrapper-ness,
549 -- but the truth is we probably haven't run
550 -- the strictness analyser yet.
553 else if explicit_INLINE_requested then
554 -- If it was a user INLINE, then we know it's already
555 -- in the inline_env; we stick with what we already
557 --pprTrace "giving up on INLINE:" (ppr PprDebug binder)
560 else if isWrapperId binder then
561 -- It's in the env, but we have since worker-wrapperised;
562 -- we either take this new one (because it's so good),
563 -- or we *undo* the one in the inline_env, so the
564 -- wrapper-inlining will take over.
566 if mentions_no_other_ids {- *** && size <= unfold_override_threshold -} then
569 delOneFromIdEnv inline_env binder
572 -- It's in the env, nothing to do w/ worker wrapper;
573 -- we'll take it if it is better.
575 if not foldr_building -- ANDY hates us... (see below)
576 && mentions_no_other_ids
577 && guidance_size <= unfold_override_threshold then
580 --pprTrace "giving up on final hurdle:" (ppCat [ppr PprDebug binder, ppInt guidance_size, ppInt unfold_override_threshold])
581 ignominious_defeat -- and at the last hurdle, too!
584 ANDY, on the hatred of the check above; why obliterate it? Consider
586 head xs = foldr (\ x _ -> x) (_|_) xs
588 This then is exported via a pragma. However,
589 *if* you include the extra code above, you will
590 export the non-foldr/build version.