X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=compiler%2FsimplCore%2FSimplify.lhs;h=eb2884cef446cd8fbe4ecedac299f94e11aa1e48;hp=f8462be79fccc3dd4f1ab0ac841dfcc4fb712929;hb=6a944ae7fe1e8e2e456c68717188463263f8978f;hpb=e97df85e14fa5b088fcfee0c2acbd961869e05fe diff --git a/compiler/simplCore/Simplify.lhs b/compiler/simplCore/Simplify.lhs index f8462be..eb2884c 100644 --- a/compiler/simplCore/Simplify.lhs +++ b/compiler/simplCore/Simplify.lhs @@ -35,9 +35,8 @@ import BasicTypes ( isMarkedStrict, Arity ) import CostCentre ( currentCCS, pushCCisNop ) import TysPrim ( realWorldStatePrimTy ) import PrelInfo ( realWorldPrimId ) -import BasicTypes ( TopLevelFlag(..), isTopLevel, - RecFlag(..), isNonRuleLoopBreaker ) -import MonadUtils ( foldlM ) +import BasicTypes ( TopLevelFlag(..), isTopLevel, RecFlag(..) ) +import MonadUtils ( foldlM, mapAccumLM ) import Maybes ( orElse ) import Data.List ( mapAccumL ) import Outputable @@ -597,7 +596,7 @@ completeBind env top_lvl old_bndr new_bndr new_rhs ; if postInlineUnconditionally env top_lvl new_bndr occ_info new_rhs new_unfolding -- Inline and discard the binding then do { tick (PostInlineUnconditionally old_bndr) - ; return (extendIdSubst env old_bndr (DoneEx new_rhs)) } + ; return (extendIdSubst env old_bndr (DoneEx new_rhs)) } -- Use the substitution to make quite, quite sure that the -- substitution will happen, since we are going to discard the binding @@ -673,18 +672,21 @@ simplUnfolding env _ _ _ _ (DFunUnfolding con ops) simplUnfolding env top_lvl _ _ _ (CoreUnfolding { uf_tmpl = expr, uf_arity = arity , uf_guidance = guide@(InlineRule {}) }) - = do { expr' <- simplExpr (setMode simplGentlyForInlineRules env) expr + = do { expr' <- simplExpr (updMode updModeForInlineRules env) expr -- See Note [Simplifying gently inside InlineRules] in SimplUtils ; let mb_wkr' = CoreSubst.substInlineRuleInfo (mkCoreSubst env) (ir_info guide) ; return (mkCoreUnfolding (isTopLevel top_lvl) expr' arity (guide { ir_info = mb_wkr' })) } -- See Note [Top-level flag on inline rules] in CoreUnfold -simplUnfolding _ top_lvl _ occ_info new_rhs _ - | omit_unfolding = return NoUnfolding - | otherwise = return (mkUnfolding (isTopLevel top_lvl) new_rhs) - where - omit_unfolding = isNonRuleLoopBreaker occ_info +simplUnfolding _ top_lvl _ _occ_info new_rhs _ + = return (mkUnfolding (isTopLevel top_lvl) new_rhs) + -- We make an unfolding *even for loop-breakers*. + -- Reason: (a) It might be useful to know that they are WHNF + -- (b) In TidyPgm we currently assume that, if we want to + -- expose the unfolding then indeed we *have* an unfolding + -- to expose. (We could instead use the RHS, but currently + -- we don't.) The simple thing is always to have one. \end{code} Note [Arity decrease] @@ -900,7 +902,7 @@ rebuild env expr cont0 Stop {} -> return (env, expr) CoerceIt co cont -> rebuild env (mkCoerce co expr) cont Select _ bndr alts se cont -> rebuildCase (se `setFloats` env) expr bndr alts cont - StrictArg fun _ info cont -> rebuildCall env (fun `App` expr) info cont + StrictArg info _ cont -> rebuildCall env (info `addArgTo` expr) cont StrictBind b bs body se cont -> do { env' <- simplNonRecX (se `setFloats` env) b expr ; simplLam env' bs body cont } ApplyTo _ arg se cont -> do { arg' <- simplExpr (se `setInScope` env) arg @@ -942,14 +944,19 @@ simplCast env body co0 cont0 add_coerce co (s1s2, _t1t2) (ApplyTo dup (Type arg_ty) arg_se cont) -- (f |> g) ty ---> (f ty) |> (g @ ty) - -- This implements the PushT rule from the paper + -- This implements the PushT and PushC rules from the paper | Just (tyvar,_) <- splitForAllTy_maybe s1s2 - , not (isCoVar tyvar) - = ApplyTo dup (Type ty') (zapSubstEnv env) (addCoerce (mkInstCoercion co ty') cont) + = let + (new_arg_ty, new_cast) + | isCoVar tyvar = (new_arg_co, mkCselRCoercion co) -- PushC rule + | otherwise = (ty', mkInstCoercion co ty') -- PushT rule + in + ApplyTo dup (Type new_arg_ty) (zapSubstEnv arg_se) (addCoerce new_cast cont) where ty' = substTy (arg_se `setInScope` env) arg_ty - - -- ToDo: the PushC rule is not implemented at all + new_arg_co = mkCsel1Coercion co `mkTransCoercion` + ty' `mkTransCoercion` + mkSymCoercion (mkCsel2Coercion co) add_coerce co (s1s2, _t1t2) (ApplyTo dup arg arg_se cont) | not (isTypeArg arg) -- This implements the Push rule from the paper @@ -968,7 +975,7 @@ simplCast env body co0 cont0 -- But it isn't a common case. -- -- Example of use: Trac #995 - = ApplyTo dup new_arg (zapSubstEnv env) (addCoerce co2 cont) + = ApplyTo dup new_arg (zapSubstEnv arg_se) (addCoerce co2 cont) where -- we split coercion t1->t2 ~ s1->s2 into t1 ~ s1 and -- t2 ~ s2 with left and right on the curried form: @@ -1087,7 +1094,7 @@ simplVar env var cont = case substId env var of DoneEx e -> simplExprF (zapSubstEnv env) e cont ContEx tvs ids e -> simplExprF (setSubstEnv env tvs ids) e cont - DoneId var1 -> completeCall (zapSubstEnv env) var1 cont + DoneId var1 -> completeCall env var1 cont -- Note [zapSubstEnv] -- The template is already simplified, so don't re-substitute. -- This is VITAL. Consider @@ -1103,41 +1110,21 @@ simplVar env var cont completeCall :: SimplEnv -> Id -> SimplCont -> SimplM (SimplEnv, OutExpr) completeCall env var cont - = do { let (args,call_cont) = contArgs cont + = do { ------------- Try inlining ---------------- + dflags <- getDOptsSmpl + ; let (args,call_cont) = contArgs cont -- The args are OutExprs, obtained by *lazily* substituting -- in the args found in cont. These args are only examined -- to limited depth (unless a rule fires). But we must do -- the substitution; rule matching on un-simplified args would -- be bogus - ------------- First try rules ---------------- - -- Do this before trying inlining. Some functions have - -- rules *and* are strict; in this case, we don't want to - -- inline the wrapper of the non-specialised thing; better - -- to call the specialised thing instead. - -- - -- We used to use the black-listing mechanism to ensure that inlining of - -- the wrapper didn't occur for things that have specialisations till a - -- later phase, so but now we just try RULES first - -- - -- See also Note [Rules for recursive functions] - ; rule_base <- getSimplRules - ; let rules = getRules rule_base var - ; mb_rule <- tryRules env var rules args call_cont - ; case mb_rule of { - Just (n_args, rule_rhs) -> simplExprF env rule_rhs (dropArgs n_args cont) ; - -- The ruleArity says how many args the rule consumed - ; Nothing -> do -- No rules - - - ------------- Next try inlining ---------------- - { dflags <- getDOptsSmpl - ; let arg_infos = [interestingArg arg | arg <- args, isValArg arg] - n_val_args = length arg_infos - interesting_cont = interestingCallContext call_cont - active_inline = activeInline env var - maybe_inline = callSiteInline dflags active_inline var - (null args) arg_infos interesting_cont + arg_infos = [interestingArg arg | arg <- args, isValArg arg] + n_val_args = length arg_infos + interesting_cont = interestingCallContext call_cont + active_inline = activeInline env var + maybe_inline = callSiteInline dflags active_inline var + (null args) arg_infos interesting_cont ; case maybe_inline of { Just unfolding -- There is an inlining! -> do { tick (UnfoldingDone var) @@ -1148,24 +1135,20 @@ completeCall env var cont text "Cont: " <+> ppr call_cont]) else id) - simplExprF env unfolding cont } + simplExprF (zapSubstEnv env) unfolding cont } - ; Nothing -> -- No inlining! + ; Nothing -> do -- No inlining! - ------------- No inlining! ---------------- - -- Next, look for rules or specialisations that match - -- - rebuildCall env (Var var) - (mkArgInfo var rules n_val_args call_cont) - cont - }}}} + { rule_base <- getSimplRules + ; let info = mkArgInfo var (getRules rule_base var) n_val_args call_cont + ; rebuildCall env info cont + }}} rebuildCall :: SimplEnv - -> OutExpr -- Function -> ArgInfo -> SimplCont -> SimplM (SimplEnv, OutExpr) -rebuildCall env fun (ArgInfo { ai_strs = [] }) cont +rebuildCall env (ArgInfo { ai_fun = fun, ai_args = rev_args, ai_strs = [] }) cont -- When we run out of strictness args, it means -- that the call is definitely bottom; see SimplUtils.mkArgInfo -- Then we want to discard the entire strict continuation. E.g. @@ -1177,25 +1160,26 @@ rebuildCall env fun (ArgInfo { ai_strs = [] }) cont -- the continuation, leaving just the bottoming expression. But the -- type might not be right, so we may have to add a coerce. | not (contIsTrivial cont) -- Only do this if there is a non-trivial - = return (env, mk_coerce fun) -- contination to discard, else we do it + = return (env, mk_coerce res) -- contination to discard, else we do it where -- again and again! - fun_ty = exprType fun - cont_ty = contResultType env fun_ty cont - co = mkUnsafeCoercion fun_ty cont_ty - mk_coerce expr | cont_ty `coreEqType` fun_ty = expr + res = mkApps (Var fun) (reverse rev_args) + res_ty = exprType res + cont_ty = contResultType env res_ty cont + co = mkUnsafeCoercion res_ty cont_ty + mk_coerce expr | cont_ty `coreEqType` res_ty = expr | otherwise = mkCoerce co expr -rebuildCall env fun info (ApplyTo _ (Type arg_ty) se cont) +rebuildCall env info (ApplyTo _ (Type arg_ty) se cont) = do { ty' <- simplCoercion (se `setInScope` env) arg_ty - ; rebuildCall env (fun `App` Type ty') info cont } + ; rebuildCall env (info `addArgTo` Type ty') cont } -rebuildCall env fun - (ArgInfo { ai_rules = has_rules, ai_strs = str:strs, ai_discs = disc:discs }) - (ApplyTo _ arg arg_se cont) +rebuildCall env info@(ArgInfo { ai_encl = encl_rules + , ai_strs = str:strs, ai_discs = disc:discs }) + (ApplyTo _ arg arg_se cont) | str -- Strict argument = -- pprTrace "Strict Arg" (ppr arg $$ ppr (seIdSubst env) $$ ppr (seInScope env)) $ simplExprF (arg_se `setFloats` env) arg - (StrictArg fun cci arg_info' cont) + (StrictArg info' cci cont) -- Note [Shadowing] | otherwise -- Lazy argument @@ -1205,16 +1189,40 @@ rebuildCall env fun -- floating a demanded let. = do { arg' <- simplExprC (arg_se `setInScope` env) arg (mkLazyArgStop cci) - ; rebuildCall env (fun `App` arg') arg_info' cont } + ; rebuildCall env (addArgTo info' arg') cont } where - arg_info' = ArgInfo { ai_rules = has_rules, ai_strs = strs, ai_discs = discs } - cci | has_rules || disc > 0 = ArgCtxt has_rules -- Be keener here - | otherwise = BoringCtxt -- Nothing interesting - -rebuildCall env fun _ cont - = rebuild env fun cont + info' = info { ai_strs = strs, ai_discs = discs } + cci | encl_rules || disc > 0 = ArgCtxt encl_rules -- Be keener here + | otherwise = BoringCtxt -- Nothing interesting + +rebuildCall env (ArgInfo { ai_fun = fun, ai_args = rev_args, ai_rules = rules }) cont + = do { -- We've accumulated a simplified call in + -- so try rewrite rules; see Note [RULEs apply to simplified arguments] + -- See also Note [Rules for recursive functions] + ; let args = reverse rev_args + env' = zapSubstEnv env + ; mb_rule <- tryRules env rules fun args cont + ; case mb_rule of { + Just (n_args, rule_rhs) -> simplExprF env' rule_rhs $ + pushArgs env' (drop n_args args) cont ; + -- n_args says how many args the rule consumed + ; Nothing -> rebuild env (mkApps (Var fun) args) cont -- No rules + } } \end{code} +Note [RULES apply to simplified arguments] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +It's very desirable to try RULES once the arguments have been simplified, because +doing so ensures that rule cascades work in one pass. Consider + {-# RULES g (h x) = k x + f (k x) = x #-} + ...f (g (h x))... +Then we want to rewrite (g (h x)) to (k x) and only then try f's rules. If +we match f's rules against the un-simplified RHS, it won't match. This +makes a particularly big difference when superclass selectors are involved: + op ($p1 ($p2 (df d))) +We want all this to unravel in one sweeep. + Note [Shadowing] ~~~~~~~~~~~~~~~~ This part of the simplifier may break the no-shadowing invariant @@ -1247,11 +1255,11 @@ all this at once is TOO HARD! %************************************************************************ \begin{code} -tryRules :: SimplEnv - -> Id -> [CoreRule] -> [OutExpr] -> SimplCont +tryRules :: SimplEnv -> [CoreRule] + -> Id -> [OutExpr] -> SimplCont -> SimplM (Maybe (Arity, CoreExpr)) -- The arity is the number of -- args consumed by the rule -tryRules env fn rules args call_cont +tryRules env rules fn args call_cont | null rules = return Nothing | otherwise @@ -1259,7 +1267,6 @@ tryRules env fn rules args call_cont ; case activeRule dflags env of { Nothing -> return Nothing ; -- No rules apply Just act_fn -> - case lookupRule act_fn (getInScope env) fn args rules of { Nothing -> return Nothing ; -- No rule matches Just (rule, rule_rhs) -> @@ -1467,17 +1474,19 @@ rebuildCase env scrut case_bndr [(_, bndrs, rhs)] cont -- exprOkForSpeculation was intended for. var_demanded_later _ = False +-------------------------------------------------- +-- 3. Try seq rules; see Note [User-defined RULES for seq] in MkId +-------------------------------------------------- + rebuildCase env scrut case_bndr alts@[(_, bndrs, rhs)] cont | all isDeadBinder (case_bndr : bndrs) -- So this is just 'seq' - = -- For this case, see Note [User-defined RULES for seq] in MkId - do { let rhs' = substExpr env rhs + = do { let rhs' = substExpr env rhs out_args = [Type (substTy env (idType case_bndr)), Type (exprType rhs'), scrut, rhs'] -- Lazily evaluated, so we don't do most of this ; rule_base <- getSimplRules - ; let rules = getRules rule_base seqId - ; mb_rule <- tryRules env seqId rules out_args cont + ; mb_rule <- tryRules env (getRules rule_base seqId) seqId out_args cont ; case mb_rule of Just (n_args, res) -> simplExprF (zapSubstEnv env) (mkApps res (drop n_args out_args)) @@ -1502,9 +1511,11 @@ reallyRebuildCase env scrut case_bndr alts cont -- Check for empty alternatives ; if null alts' then missingAlt env case_bndr alts cont else do - { case_expr <- mkCase scrut' case_bndr' alts' + { dflags <- getDOptsSmpl + ; case_expr <- mkCase dflags scrut' case_bndr' alts' - -- Notice that rebuild gets the in-scope set from env, not alt_env + -- Notice that rebuild gets the in-scope set from env', not alt_env + -- (which in any case is only build in simplAlts) -- The case binder *not* scope over the whole returned case-expression ; rebuild env' case_expr nodup_cont } } \end{code} @@ -1595,65 +1606,6 @@ At one point I did transformation in LiberateCase, but it's more robust here. (Otherwise, there's a danger that we'll simply drop the 'seq' altogether, before LiberateCase gets to see it.) - -\begin{code} -improveSeq :: (FamInstEnv, FamInstEnv) -> SimplEnv - -> OutExpr -> InId -> OutId -> [InAlt] - -> SimplM (SimplEnv, OutExpr, OutId) --- Note [Improving seq] -improveSeq fam_envs env scrut case_bndr case_bndr1 [(DEFAULT,_,_)] - | not (isDeadBinder case_bndr) -- Not a pure seq! See the Note! - , Just (co, ty2) <- topNormaliseType fam_envs (idType case_bndr1) - = do { case_bndr2 <- newId (fsLit "nt") ty2 - ; let rhs = DoneEx (Var case_bndr2 `Cast` mkSymCoercion co) - env2 = extendIdSubst env case_bndr rhs - ; return (env2, scrut `Cast` co, case_bndr2) } - -improveSeq _ env scrut _ case_bndr1 _ - = return (env, scrut, case_bndr1) -\end{code} - - -simplAlts does two things: - -1. Eliminate alternatives that cannot match, including the - DEFAULT alternative. - -2. If the DEFAULT alternative can match only one possible constructor, - then make that constructor explicit. - e.g. - case e of x { DEFAULT -> rhs } - ===> - case e of x { (a,b) -> rhs } - where the type is a single constructor type. This gives better code - when rhs also scrutinises x or e. - -Here "cannot match" includes knowledge from GADTs - -It's a good idea do do this stuff before simplifying the alternatives, to -avoid simplifying alternatives we know can't happen, and to come up with -the list of constructors that are handled, to put into the IdInfo of the -case binder, for use when simplifying the alternatives. - -Eliminating the default alternative in (1) isn't so obvious, but it can -happen: - -data Colour = Red | Green | Blue - -f x = case x of - Red -> .. - Green -> .. - DEFAULT -> h x - -h y = case y of - Blue -> .. - DEFAULT -> [ case y of ... ] - -If we inline h into f, the default case of the inlined h can't happen. -If we don't notice this, we may end up filtering out *all* the cases -of the inner case y, which give us nowhere to go! - - \begin{code} simplAlts :: SimplEnv -> OutExpr @@ -1662,7 +1614,7 @@ simplAlts :: SimplEnv -> SimplCont -> SimplM (OutExpr, OutId, [OutAlt]) -- Includes the continuation -- Like simplExpr, this just returns the simplified alternatives; --- it not return an environment +-- it does not return an environment simplAlts env scrut case_bndr alts cont' = -- pprTrace "simplAlts" (ppr alts $$ ppr (seIdSubst env)) $ @@ -1674,11 +1626,29 @@ simplAlts env scrut case_bndr alts cont' ; (alt_env', scrut', case_bndr') <- improveSeq fam_envs env1 scrut case_bndr case_bndr1 alts - ; (imposs_deflt_cons, in_alts) <- prepareAlts alt_env' scrut' case_bndr' alts + ; (imposs_deflt_cons, in_alts) <- prepareAlts scrut' case_bndr' alts ; alts' <- mapM (simplAlt alt_env' imposs_deflt_cons case_bndr' cont') in_alts ; return (scrut', case_bndr', alts') } + +------------------------------------ +improveSeq :: (FamInstEnv, FamInstEnv) -> SimplEnv + -> OutExpr -> InId -> OutId -> [InAlt] + -> SimplM (SimplEnv, OutExpr, OutId) +-- Note [Improving seq] +improveSeq fam_envs env scrut case_bndr case_bndr1 [(DEFAULT,_,_)] + | not (isDeadBinder case_bndr) -- Not a pure seq! See the Note! + , Just (co, ty2) <- topNormaliseType fam_envs (idType case_bndr1) + = do { case_bndr2 <- newId (fsLit "nt") ty2 + ; let rhs = DoneEx (Var case_bndr2 `Cast` mkSymCoercion co) + env2 = extendIdSubst env case_bndr rhs + ; return (env2, scrut `Cast` co, case_bndr2) } + +improveSeq _ env scrut _ case_bndr1 _ + = return (env, scrut, case_bndr1) + + ------------------------------------ simplAlt :: SimplEnv -> [AltCon] -- These constructors can't be present when @@ -1891,18 +1861,11 @@ mkDupableCont env cont@(StrictBind {}) = return (env, mkBoringStop, cont) -- See Note [Duplicating StrictBind] -mkDupableCont env (StrictArg fun cci ai cont) +mkDupableCont env (StrictArg info cci cont) -- See Note [Duplicating StrictArg] = do { (env', dup, nodup) <- mkDupableCont env cont - ; (env'', fun') <- mk_dupable_call env' fun - ; return (env'', StrictArg fun' cci ai dup, nodup) } - where - mk_dupable_call env (Var v) = return (env, Var v) - mk_dupable_call env (App fun arg) = do { (env', fun') <- mk_dupable_call env fun - ; (env'', arg') <- makeTrivial env' arg - ; return (env'', fun' `App` arg') } - mk_dupable_call _ other = pprPanic "mk_dupable_call" (ppr other) - -- The invariant of StrictArg is that the first arg is always an App chain + ; (env'', args') <- mapAccumLM makeTrivial env' (ai_args info) + ; return (env'', StrictArg (info { ai_args = args' }) cci dup, nodup) } mkDupableCont env (ApplyTo _ arg se cont) = -- e.g. [...hole...] (...arg...)