{- (c) The AQUA Project, Glasgow University, 1993-1998 \section{Common subexpression} -} {-# LANGUAGE CPP #-} {-# OPTIONS_GHC -Wno-incomplete-record-updates #-} {-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-} module GHC.Core.Opt.CSE (cseProgram, cseOneExpr) where #include "HsVersions.h" import GHC.Prelude import GHC.Core.Subst import GHC.Types.Var ( Var ) import GHC.Types.Var.Env ( mkInScopeSet ) import GHC.Types.Id ( Id, idType, idHasRules, zapStableUnfolding , idInlineActivation, setInlineActivation , zapIdOccInfo, zapIdUsageInfo, idInlinePragma , isJoinId, isJoinId_maybe ) import GHC.Core.Utils ( mkAltExpr, eqExpr , exprIsTickedString , stripTicksE, stripTicksT, mkTicks ) import GHC.Core.FVs ( exprFreeVars ) import GHC.Core.Type ( tyConAppArgs ) import GHC.Core import GHC.Utils.Outputable import GHC.Types.Basic import GHC.Types.Tickish import GHC.Core.Map.Expr import GHC.Utils.Misc ( filterOut, equalLength, debugIsOn ) import GHC.Utils.Panic import Data.List ( mapAccumL ) {- Simple common sub-expression ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When we see x1 = C a b x2 = C x1 b we build up a reverse mapping: C a b -> x1 C x1 b -> x2 and apply that to the rest of the program. When we then see y1 = C a b y2 = C y1 b we replace the C a b with x1. But then we *dont* want to add x1 -> y1 to the mapping. Rather, we want the reverse, y1 -> x1 so that a subsequent binding y2 = C y1 b will get transformed to C x1 b, and then to x2. So we carry an extra var->var substitution which we apply *before* looking up in the reverse mapping. Note [Shadowing] ~~~~~~~~~~~~~~~~ We have to be careful about shadowing. For example, consider f = \x -> let y = x+x in h = \x -> x+x in ... Here we must *not* do CSE on the inner x+x! The simplifier used to guarantee no shadowing, but it doesn't any more (it proved too hard), so we clone as we go. We can simply add clones to the substitution already described. A similar tricky situation is this, with x_123 and y_123 sharing the same unique: let x_123 = e1 in let y_123 = e2 in let foo = e1 Naively applying e1 = x_123 during CSE we would get: let x_123 = e1 in let y_123 = e2 in let foo = x_123 But x_123 is shadowed by y_123 and things would go terribly wrong! One more reason why we have to substitute binders as we go so we will properly get: let x1 = e1 in let x2 = e2 in let foo = x1 Note [CSE for bindings] ~~~~~~~~~~~~~~~~~~~~~~~ Let-bindings have two cases, implemented by extendCSEnvWithBinding. * SUBSTITUTE: applies when the RHS is a variable let x = y in ...(h x).... Here we want to extend the /substitution/ with x -> y, so that the (h x) in the body might CSE with an enclosing (let v = h y in ...). NB: the substitution maps InIds, so we extend the substitution with a binding for the original InId 'x' How can we have a variable on the RHS? Doesn't the simplifier inline them? - First, the original RHS might have been (g z) which has CSE'd with an enclosing (let y = g z in ...). This is super-important. See #5996: x1 = C a b x2 = C x1 b y1 = C a b y2 = C y1 b Here we CSE y1's rhs to 'x1', and then we must add (y1->x1) to the substitution so that we can CSE the binding for y2. - Second, we use extendCSEnvWithBinding for case expression scrutinees too; see Note [CSE for case expressions] * EXTEND THE REVERSE MAPPING: applies in all other cases let x = h y in ...(h y)... Here we want to extend the /reverse mapping (cs_map)/ so that we CSE the (h y) call to x. Note that we use EXTEND even for a trivial expression, provided it is not a variable or literal. In particular this /includes/ type applications. This can be important (#13156); e.g. case f @ Int of { r1 -> case f @ Int of { r2 -> ... Here we want to common-up the two uses of (f @ Int) so we can remove one of the case expressions. See also Note [Corner case for case expressions] for another reason not to use SUBSTITUTE for all trivial expressions. Notice that - The SUBSTITUTE situation extends the substitution (cs_subst) - The EXTEND situation extends the reverse mapping (cs_map) Notice also that in the SUBSTITUTE case we leave behind a binding x = y even though we /also/ carry a substitution x -> y. Can we just drop the binding instead? Well, not at top level! See Note [Top level and postInlineUnconditionally] in GHC.Core.Opt.Simplify.Utils; and in any case CSE applies only to the /bindings/ of the program, and we leave it to the simplifier to propate effects to the RULES. Finally, it doesn't seem worth the effort to discard the nested bindings because the simplifier will do it next. Note [CSE for case expressions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider case scrut_expr of x { ...alts... } This is very like a strict let-binding let !x = scrut_expr in ... So we use (extendCSEnvWithBinding x scrut_expr) to process scrut_expr and x, and as a result all the stuff under Note [CSE for bindings] applies directly. For example: * Trivial scrutinee f = \x -> case x of wild { (a:as) -> case a of wild1 { (p,q) -> ...(wild1:as)... Here, (wild1:as) is morally the same as (a:as) and hence equal to wild. But that's not quite obvious. In the rest of the compiler we want to keep it as (wild1:as), but for CSE purpose that's a bad idea. By using extendCSEnvWithBinding we add the binding (wild1 -> a) to the substitution, which does exactly the right thing. (Notice this is exactly backwards to what the simplifier does, which is to try to replaces uses of 'a' with uses of 'wild1'.) This is the main reason that extendCSEnvWithBinding is called with a trivial rhs. * Non-trivial scrutinee case (f x) of y { pat -> ...let z = f x in ... } By using extendCSEnvWithBinding we'll add (f x :-> y) to the cs_map, and thereby CSE the inner (f x) to y. Note [CSE for INLINE and NOINLINE] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ There are some subtle interactions of CSE with functions that the user has marked as INLINE or NOINLINE. (Examples from Roman Leshchinskiy.) Consider yes :: Int {-# NOINLINE yes #-} yes = undefined no :: Int {-# NOINLINE no #-} no = undefined foo :: Int -> Int -> Int {-# NOINLINE foo #-} foo m n = n {-# RULES "foo/no" foo no = id #-} bar :: Int -> Int bar = foo yes We do not expect the rule to fire. But if we do CSE, then we risk getting yes=no, and the rule does fire. Actually, it won't because NOINLINE means that 'yes' will never be inlined, not even if we have yes=no. So that's fine (now; perhaps in the olden days, yes=no would have substituted even if 'yes' was NOINLINE). But we do need to take care. Consider {-# NOINLINE bar #-} bar = <rhs> -- Same rhs as foo foo = <rhs> If CSE produces foo = bar then foo will never be inlined to <rhs> (when it should be, if <rhs> is small). The conclusion here is this: We should not add <rhs> :-> bar to the CSEnv if 'bar' has any constraints on when it can inline; that is, if its 'activation' not always active. Otherwise we might replace <rhs> by 'bar', and then later be unable to see that it really was <rhs>. An except to the rule is when the INLINE pragma is not from the user, e.g. from WorkWrap (see Note [Wrapper activation]). We can tell because noUserInlineSpec is then true. Note that we do not (currently) do CSE on the unfolding stored inside an Id, even if it is a 'stable' unfolding. That means that when an unfolding happens, it is always faithful to what the stable unfolding originally was. Note [CSE for stable unfoldings] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider {-# Unf = Stable (\pq. build blah) #-} foo = x Here 'foo' has a stable unfolding, but its (optimised) RHS is trivial. (Turns out that this actually happens for the enumFromTo method of the Integer instance of Enum in GHC.Enum.) Suppose moreover that foo's stable unfolding originates from an INLINE or INLINEABLE pragma on foo. Then we obviously do NOT want to extend the substitution with (foo->x), because we promised to inline foo as what the user wrote. See similar Note [Stable unfoldings and postInlineUnconditionally] in GHC.Core.Opt.Simplify.Utils. Nor do we want to change the reverse mapping. Suppose we have foo {-# Unf = Stable (\pq. build blah) #-} = <expr> bar = <expr> There could conceivably be merit in rewriting the RHS of bar: bar = foo but now bar's inlining behaviour will change, and importing modules might see that. So it seems dodgy and we don't do it. Stable unfoldings are also created during worker/wrapper when we decide that a function's definition is so small that it should always inline. In this case we still want to do CSE (#13340). Hence the use of isAnyInlinePragma rather than isStableUnfolding. Now consider foo = <expr> bar {-# Unf = Stable ... #-} = <expr> where the unfolding was added by strictness analysis, say. Then CSE goes ahead, so we get bar = foo and probably use SUBSTITUTE that will make 'bar' dead. But just possibly not -- see Note [Dealing with ticks]. In that case we might be left with bar = tick t1 (tick t2 foo) in which case we would really like to get rid of the stable unfolding (generated by the strictness analyser, say). Hence the zapStableUnfolding in cse_bind. Not a big deal, and only makes a difference when ticks get into the picture. Note [Corner case for case expressions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Here is another reason that we do not use SUBSTITUTE for all trivial expressions. Consider case x |> co of (y::Array# Int) { ... } We do not want to extend the substitution with (y -> x |> co); since y is of unlifted type, this would destroy the let/app invariant if (x |> co) was not ok-for-speculation. But surely (x |> co) is ok-for-speculation, because it's a trivial expression, and x's type is also unlifted, presumably. Well, maybe not if you are using unsafe casts. I actually found a case where we had (x :: HValue) |> (UnsafeCo :: HValue ~ Array# Int) Note [CSE for join points?] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ We must not be naive about join points in CSE: join j = e in if b then jump j else 1 + e The expression (1 + jump j) is not good (see Note [Invariants on join points] in GHC.Core). This seems to come up quite seldom, but it happens (first seen compiling ppHtml in Haddock.Backends.Xhtml). We could try and be careful by tracking which join points are still valid at each subexpression, but since join points aren't allocated or shared, there's less to gain by trying to CSE them. (#13219) Note [Look inside join-point binders] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Another way how CSE for join points is tricky is let join foo x = (x, 42) join bar x = (x, 42) in … jump foo 1 … jump bar 2 … naively, CSE would turn this into let join foo x = (x, 42) join bar = foo in … jump foo 1 … jump bar 2 … but now bar is a join point that claims arity one, but its right-hand side is not a lambda, breaking the join-point invariant (this was #15002). So `cse_bind` must zoom past the lambdas of a join point (using `collectNBinders`) and resume searching for CSE opportunities only in the body of the join point. Note [CSE for recursive bindings] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider f = \x ... f.... g = \y ... g ... where the "..." are identical. Could we CSE them? In full generality with mutual recursion it's quite hard; but for self-recursive bindings (which are very common) it's rather easy: * Maintain a separate cs_rec_map, that maps (\f. (\x. ...f...) ) -> f Note the \f in the domain of the mapping! * When we come across the binding for 'g', look up (\g. (\y. ...g...)) Bingo we get a hit. So we can replace the 'g' binding with g = f We can't use cs_map for this, because the key isn't an expression of the program; it's a kind of synthetic key for recursive bindings. Note [Separate envs for let rhs and body] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Substituting occurances of the binder in the rhs with the renamed binder is wrong for non-recursive bindings. Why? Consider this core. let {x_123 = e} in let {y_123 = \eta0 -> x_123} in ... In the second line the y_123 on the lhs and x_123 on the rhs refer to different binders even if they share the same unique. If we apply the substitution `123 => x2_124}` to both the lhs and rhs we will transform `let y_123 = \eta0 -> x_123` into `let x2_124 = \eta0 -> x2_124`. However x2_124 on the rhs is not in scope and really shouldn't have been renamed at all. Because really this should still be x_123! In fact this exact thing happened in #21685. To fix this we pass two different cse envs to cse_bind. One we use the cse the rhs of the binding. And one we update with the result of cseing the rhs which we then use going forward for the body/rest of the module. ************************************************************************ * * \section{Common subexpression} * * ************************************************************************ -} cseProgram :: CoreProgram -> CoreProgram cseProgram :: CoreProgram -> CoreProgram cseProgram CoreProgram binds = forall a b. (a, b) -> b snd (forall (t :: * -> *) s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) mapAccumL (TopLevelFlag -> CSEnv -> CoreBind -> (CSEnv, CoreBind) cseBind TopLevelFlag TopLevel) CSEnv emptyCSEnv CoreProgram binds) cseBind :: TopLevelFlag -> CSEnv -> CoreBind -> (CSEnv, CoreBind) cseBind :: TopLevelFlag -> CSEnv -> CoreBind -> (CSEnv, CoreBind) cseBind TopLevelFlag toplevel CSEnv env (NonRec Var b Expr Var e) = (CSEnv env2, forall b. b -> Expr b -> Bind b NonRec Var b2 Expr Var e2) where -- See Note [Separate envs for let rhs and body] (CSEnv env1, Var b1) = CSEnv -> Var -> (CSEnv, Var) addBinder CSEnv env Var b (CSEnv env2, (Var b2, Expr Var e2)) = TopLevelFlag -> CSEnv -> CSEnv -> (Var, Expr Var) -> Var -> (CSEnv, (Var, Expr Var)) cse_bind TopLevelFlag toplevel CSEnv env CSEnv env1 (Var b,Expr Var e) Var b1 cseBind TopLevelFlag toplevel CSEnv env (Rec [(Var in_id, Expr Var rhs)]) | Var -> Bool noCSE Var in_id = (CSEnv env1, forall b. [(b, Expr b)] -> Bind b Rec [(Var out_id, Expr Var rhs')]) -- See Note [CSE for recursive bindings] | Just Expr Var previous <- CSEnv -> Var -> Expr Var -> Maybe (Expr Var) lookupCSRecEnv CSEnv env Var out_id Expr Var rhs'' , let previous' :: Expr Var previous' = [CoreTickish] -> Expr Var -> Expr Var mkTicks [CoreTickish] ticks Expr Var previous out_id' :: Var out_id' = TopLevelFlag -> Var -> Var delayInlining TopLevelFlag toplevel Var out_id = -- We have a hit in the recursive-binding cache (CSEnv -> Var -> Expr Var -> CSEnv extendCSSubst CSEnv env1 Var in_id Expr Var previous', forall b. b -> Expr b -> Bind b NonRec Var out_id' Expr Var previous') | Bool otherwise = (CSEnv -> Var -> Expr Var -> Expr Var -> CSEnv extendCSRecEnv CSEnv env1 Var out_id Expr Var rhs'' Expr Var id_expr', forall b. [(b, Expr b)] -> Bind b Rec [(Var zapped_id, Expr Var rhs')]) where (CSEnv env1, [Var out_id]) = CSEnv -> [Var] -> (CSEnv, [Var]) addRecBinders CSEnv env [Var in_id] rhs' :: Expr Var rhs' = CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env1 Expr Var rhs rhs'' :: Expr Var rhs'' = forall b. (CoreTickish -> Bool) -> Expr b -> Expr b stripTicksE forall (pass :: TickishPass). GenTickish pass -> Bool tickishFloatable Expr Var rhs' ticks :: [CoreTickish] ticks = forall b. (CoreTickish -> Bool) -> Expr b -> [CoreTickish] stripTicksT forall (pass :: TickishPass). GenTickish pass -> Bool tickishFloatable Expr Var rhs' id_expr' :: Expr Var id_expr' = forall b. Var -> Expr b varToCoreExpr Var out_id zapped_id :: Var zapped_id = Var -> Var zapIdUsageInfo Var out_id cseBind TopLevelFlag toplevel CSEnv env (Rec [(Var, Expr Var)] pairs) = (CSEnv env2, forall b. [(b, Expr b)] -> Bind b Rec [(Var, Expr Var)] pairs') where (CSEnv env1, [Var] bndrs1) = CSEnv -> [Var] -> (CSEnv, [Var]) addRecBinders CSEnv env (forall a b. (a -> b) -> [a] -> [b] map forall a b. (a, b) -> a fst [(Var, Expr Var)] pairs) (CSEnv env2, [(Var, Expr Var)] pairs') = forall (t :: * -> *) s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) mapAccumL CSEnv -> ((Var, Expr Var), Var) -> (CSEnv, (Var, Expr Var)) do_one CSEnv env1 (forall a b. [a] -> [b] -> [(a, b)] zip [(Var, Expr Var)] pairs [Var] bndrs1) do_one :: CSEnv -> ((Var, Expr Var), Var) -> (CSEnv, (Var, Expr Var)) do_one CSEnv env ((Var, Expr Var) pr, Var b1) = TopLevelFlag -> CSEnv -> CSEnv -> (Var, Expr Var) -> Var -> (CSEnv, (Var, Expr Var)) cse_bind TopLevelFlag toplevel CSEnv env CSEnv env (Var, Expr Var) pr Var b1 -- | Given a binding of @in_id@ to @in_rhs@, and a fresh name to refer -- to @in_id@ (@out_id@, created from addBinder or addRecBinders), -- first try to CSE @in_rhs@, and then add the resulting (possibly CSE'd) -- binding to the 'CSEnv', so that we attempt to CSE any expressions -- which are equal to @out_rhs@. -- We use a different env for cse on the rhs and for extendCSEnvWithBinding -- for reasons explain in See Note [Separate envs for let rhs and body] cse_bind :: TopLevelFlag -> CSEnv -> CSEnv -> (InId, InExpr) -> OutId -> (CSEnv, (OutId, OutExpr)) cse_bind :: TopLevelFlag -> CSEnv -> CSEnv -> (Var, Expr Var) -> Var -> (CSEnv, (Var, Expr Var)) cse_bind TopLevelFlag toplevel CSEnv env_rhs CSEnv env_body (Var in_id, Expr Var in_rhs) Var out_id | TopLevelFlag -> Bool isTopLevel TopLevelFlag toplevel, Expr Var -> Bool exprIsTickedString Expr Var in_rhs -- See Note [Take care with literal strings] = (CSEnv env_body', (Var out_id', Expr Var in_rhs)) | Just JoinArity arity <- Var -> Maybe JoinArity isJoinId_maybe Var out_id -- See Note [Look inside join-point binders] = let ([Var] params, Expr Var in_body) = forall b. JoinArity -> Expr b -> ([b], Expr b) collectNBinders JoinArity arity Expr Var in_rhs (CSEnv env', [Var] params') = CSEnv -> [Var] -> (CSEnv, [Var]) addBinders CSEnv env_rhs [Var] params out_body :: Expr Var out_body = CSEnv -> Expr Var -> Expr Var tryForCSE CSEnv env' Expr Var in_body in (CSEnv env_body , (Var out_id, forall b. [b] -> Expr b -> Expr b mkLams [Var] params' Expr Var out_body)) | Bool otherwise = (CSEnv env_body', (Var out_id'', Expr Var out_rhs)) where (CSEnv env_body', Var out_id') = CSEnv -> Var -> Var -> Expr Var -> Bool -> (CSEnv, Var) extendCSEnvWithBinding CSEnv env_body Var in_id Var out_id Expr Var out_rhs Bool cse_done (Bool cse_done, Expr Var out_rhs) = CSEnv -> Expr Var -> (Bool, Expr Var) try_for_cse CSEnv env_rhs Expr Var in_rhs out_id'' :: Var out_id'' | Bool cse_done = Var -> Var zapStableUnfolding forall a b. (a -> b) -> a -> b $ TopLevelFlag -> Var -> Var delayInlining TopLevelFlag toplevel Var out_id' | Bool otherwise = Var out_id' delayInlining :: TopLevelFlag -> Id -> Id -- Add a NOINLINE[2] if the Id doesn't have an INLNE pragma already -- See Note [Delay inlining after CSE] delayInlining :: TopLevelFlag -> Var -> Var delayInlining TopLevelFlag top_lvl Var bndr | TopLevelFlag -> Bool isTopLevel TopLevelFlag top_lvl , Activation -> Bool isAlwaysActive (Var -> Activation idInlineActivation Var bndr) , Var -> Bool idHasRules Var bndr -- Only if the Id has some RULES, -- which might otherwise get lost -- These rules are probably auto-generated specialisations, -- since Ids with manual rules usually have manually-inserted -- delayed inlining anyway = Var bndr Var -> Activation -> Var `setInlineActivation` Activation activateAfterInitial | Bool otherwise = Var bndr extendCSEnvWithBinding :: CSEnv -- Includes InId->OutId cloning -> InVar -- Could be a let-bound type -> OutId -> OutExpr -- Processed binding -> Bool -- True <=> RHS was CSE'd and is a variable -- or maybe (Tick t variable) -> (CSEnv, OutId) -- Final env, final bndr -- Extend the CSE env with a mapping [rhs -> out-id] -- unless we can instead just substitute [in-id -> rhs] -- -- It's possible for the binder to be a type variable, -- in which case we can just substitute. -- See Note [CSE for bindings] extendCSEnvWithBinding :: CSEnv -> Var -> Var -> Expr Var -> Bool -> (CSEnv, Var) extendCSEnvWithBinding CSEnv env Var in_id Var out_id Expr Var rhs' Bool cse_done | Bool -> Bool not (Var -> Bool isId Var out_id) = (CSEnv -> Var -> Expr Var -> CSEnv extendCSSubst CSEnv env Var in_id Expr Var rhs', Var out_id) | Var -> Bool noCSE Var out_id = (CSEnv env, Var out_id) | Bool use_subst = (CSEnv -> Var -> Expr Var -> CSEnv extendCSSubst CSEnv env Var in_id Expr Var rhs', Var out_id) | Bool cse_done = (CSEnv env, Var out_id) -- See Note [Dealing with ticks] | Bool otherwise = (CSEnv -> Expr Var -> Expr Var -> CSEnv extendCSEnv CSEnv env Expr Var rhs' Expr Var id_expr', Var zapped_id) where id_expr' :: Expr Var id_expr' = forall b. Var -> Expr b varToCoreExpr Var out_id zapped_id :: Var zapped_id = Var -> Var zapIdUsageInfo Var out_id -- Putting the Id into the cs_map makes it possible that -- it'll become shared more than it is now, which would -- invalidate (the usage part of) its demand info. -- This caused #100218. -- Easiest thing is to zap the usage info; subsequently -- performing late demand-analysis will restore it. Don't zap -- the strictness info; it's not necessary to do so, and losing -- it is bad for performance if you don't do late demand -- analysis -- Should we use SUBSTITUTE or EXTEND? -- See Note [CSE for bindings] use_subst :: Bool use_subst | Var {} <- Expr Var rhs' = Bool True | Bool otherwise = Bool False -- | Given a binder `let x = e`, this function -- determines whether we should add `e -> x` to the cs_map noCSE :: InId -> Bool noCSE :: Var -> Bool noCSE Var id = Bool -> Bool not (Activation -> Bool isAlwaysActive (Var -> Activation idInlineActivation Var id)) Bool -> Bool -> Bool && Bool -> Bool not (InlineSpec -> Bool noUserInlineSpec (InlinePragma -> InlineSpec inlinePragmaSpec (Var -> InlinePragma idInlinePragma Var id))) -- See Note [CSE for INLINE and NOINLINE] Bool -> Bool -> Bool || InlinePragma -> Bool isAnyInlinePragma (Var -> InlinePragma idInlinePragma Var id) -- See Note [CSE for stable unfoldings] Bool -> Bool -> Bool || Var -> Bool isJoinId Var id -- See Note [CSE for join points?] {- Note [Take care with literal strings] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider this example: x = "foo"# y = "foo"# ...x...y...x...y.... We would normally turn this into: x = "foo"# y = x ...x...x...x...x.... But this breaks an invariant of Core, namely that the RHS of a top-level binding of type Addr# must be a string literal, not another variable. See Note [Core top-level string literals] in GHC.Core. For this reason, we special case top-level bindings to literal strings and leave the original RHS unmodified. This produces: x = "foo"# y = "foo"# ...x...x...x...x.... Now 'y' will be discarded as dead code, and we are done. The net effect is that for the y-binding we want to - Use SUBSTITUTE, by extending the substitution with y :-> x - but leave the original binding for y undisturbed This is done by cse_bind. I got it wrong the first time (#13367). Note [Dealing with ticks] ~~~~~~~~~~~~~~~~~~~~~~~~~ Ticks complicate CSE a bit, as I discovered in the fallout from fixing #19360. * To get more CSE-ing, we strip all the tickishFloatable ticks from an expression - when inserting into the cs_map (see extendCSEnv) - when looking up in the cs_map (see call to lookupCSEnv in try_for_cse) Quite why only the tickishFloatable ticks, I'm not quite sure. AK: I think we only do this for floatable ticks since generally we don't mind them being less accurate as much. E.g. consider case e of C1 -> f (<tick1> e1) C2 -> f (<tick2> e1) If the ticks are (floatable) source notes nothing too bad happens if the debug info for both branches says the code comes from the same source location. Even if it will be inaccurate for one of the branches. We should probably still consider this worthwhile. However if the ticks are cost centres we really don't want the cost of both branches to be attributed to the same cost centre. Because a user might explicitly have inserted different cost centres in order to distinguish between evaluations resulting from the two different branches. e.g. something like this: case e of C1 -> f ({ SCC "evalAlt1"} e1) C1 -> f ({ SCC "evalAlt2"} e1) But it's still a bit suspicious. * If we get a hit in cs_map, we wrap the result in the ticks from the thing we are looking up (see try_for_cse) Net result: if we get a hit, we might replace let x = tick t1 (tick t2 e) with let x = tick t1 (tick t2 y) where 'y' is the variable that 'e' maps to. Now consider extendCSEnvWithBinding for the binding for 'x': * We can't use SUBSTITUTE because those ticks might not be trivial (we use tickishIsCode in exprIsTrivial) * We should not use EXTEND, because we definitely don't want to add (tick t1 (tick t2 y)) :-> x to the cs_map. Remember we strip off the ticks, so that would amount to adding y :-> x, very silly. TL;DR: we do neither; hence the cse_done case in extendCSEnvWithBinding. Note [Delay inlining after CSE] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose (#15445) we have f,g :: Num a => a -> a f x = ...f (x-1)..... g y = ...g (y-1) .... and we make some specialisations of 'g', either automatically, or via a SPECIALISE pragma. Then CSE kicks in and notices that the RHSs of 'f' and 'g' are identical, so we get f x = ...f (x-1)... g = f {-# RULES g @Int _ = $sg #-} Now there is terrible danger that, in an importing module, we'll inline 'g' before we have a chance to run its specialisation! Solution: during CSE, after a "hit" in the CSE cache * when adding a binding g = f * for a top-level function g * and g has specialisation RULES add a NOINLINE[2] activation to it, to ensure it's not inlined right away. Notes: * Why top level only? Because for nested bindings we are already past phase 2 and will never return there. * Why "only if g has RULES"? Because there is no point in doing this if there are no RULES; and other things being equal it delays optimisation to delay inlining (#17409) ---- Historical note --- This patch is simpler and more direct than an earlier version: commit 2110738b280543698407924a16ac92b6d804dc36 Author: Simon Peyton Jones <simonpj@microsoft.com> Date: Mon Jul 30 13:43:56 2018 +0100 Don't inline functions with RULES too early We had to revert this patch because it made GHC itself slower. Why? It delayed inlining of /all/ functions with RULES, and that was very bad in GHC.Tc.Solver.Flatten.flatten_ty_con_app * It delayed inlining of liftM * That delayed the unravelling of the recursion in some dictionary bindings. * That delayed some eta expansion, leaving flatten_ty_con_app = \x y. let <stuff> in \z. blah * That allowed the float-out pass to put sguff between the \y and \z. * And that permanently stopped eta expansion of the function, even once <stuff> was simplified. -} tryForCSE :: CSEnv -> InExpr -> OutExpr tryForCSE :: CSEnv -> Expr Var -> Expr Var tryForCSE CSEnv env Expr Var expr = forall a b. (a, b) -> b snd (CSEnv -> Expr Var -> (Bool, Expr Var) try_for_cse CSEnv env Expr Var expr) try_for_cse :: CSEnv -> InExpr -> (Bool, OutExpr) -- (False, e') => We did not CSE the entire expression, -- but we might have CSE'd some sub-expressions, -- yielding e' -- -- (True, te') => We CSE'd the entire expression, -- yielding the trivial expression te' try_for_cse :: CSEnv -> Expr Var -> (Bool, Expr Var) try_for_cse CSEnv env Expr Var expr | Just Expr Var e <- CSEnv -> Expr Var -> Maybe (Expr Var) lookupCSEnv CSEnv env Expr Var expr'' = (Bool True, [CoreTickish] -> Expr Var -> Expr Var mkTicks [CoreTickish] ticks Expr Var e) | Bool otherwise = (Bool False, Expr Var expr') -- The varToCoreExpr is needed if we have -- case e of xco { ...case e of yco { ... } ... } -- Then CSE will substitute yco -> xco; -- but these are /coercion/ variables where expr' :: Expr Var expr' = CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env Expr Var expr expr'' :: Expr Var expr'' = forall b. (CoreTickish -> Bool) -> Expr b -> Expr b stripTicksE forall (pass :: TickishPass). GenTickish pass -> Bool tickishFloatable Expr Var expr' ticks :: [CoreTickish] ticks = forall b. (CoreTickish -> Bool) -> Expr b -> [CoreTickish] stripTicksT forall (pass :: TickishPass). GenTickish pass -> Bool tickishFloatable Expr Var expr' -- We don't want to lose the source notes when a common sub -- expression gets eliminated. Hence we push all (!) of them on -- top of the replaced sub-expression. This is probably not too -- useful in practice, but upholds our semantics. -- | Runs CSE on a single expression. -- -- This entry point is not used in the compiler itself, but is provided -- as a convenient entry point for users of the GHC API. cseOneExpr :: InExpr -> OutExpr cseOneExpr :: Expr Var -> Expr Var cseOneExpr Expr Var e = CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env Expr Var e where env :: CSEnv env = CSEnv emptyCSEnv {cs_subst :: Subst cs_subst = InScopeSet -> Subst mkEmptySubst (VarSet -> InScopeSet mkInScopeSet (Expr Var -> VarSet exprFreeVars Expr Var e)) } cseExpr :: CSEnv -> InExpr -> OutExpr cseExpr :: CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env (Type Type t) = forall b. Type -> Expr b Type (Subst -> Type -> Type substTy (CSEnv -> Subst csEnvSubst CSEnv env) Type t) cseExpr CSEnv env (Coercion Coercion c) = forall b. Coercion -> Expr b Coercion (HasCallStack => Subst -> Coercion -> Coercion substCo (CSEnv -> Subst csEnvSubst CSEnv env) Coercion c) cseExpr CSEnv _ (Lit Literal lit) = forall b. Literal -> Expr b Lit Literal lit cseExpr CSEnv env (Var Var v) = CSEnv -> Var -> Expr Var lookupSubst CSEnv env Var v cseExpr CSEnv env (App Expr Var f Expr Var a) = forall b. Expr b -> Expr b -> Expr b App (CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env Expr Var f) (CSEnv -> Expr Var -> Expr Var tryForCSE CSEnv env Expr Var a) cseExpr CSEnv env (Tick CoreTickish t Expr Var e) = forall b. CoreTickish -> Expr b -> Expr b Tick CoreTickish t (CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env Expr Var e) cseExpr CSEnv env (Cast Expr Var e Coercion co) = forall b. Expr b -> Coercion -> Expr b Cast (CSEnv -> Expr Var -> Expr Var tryForCSE CSEnv env Expr Var e) (HasCallStack => Subst -> Coercion -> Coercion substCo (CSEnv -> Subst csEnvSubst CSEnv env) Coercion co) cseExpr CSEnv env (Lam Var b Expr Var e) = let (CSEnv env', Var b') = CSEnv -> Var -> (CSEnv, Var) addBinder CSEnv env Var b in forall b. b -> Expr b -> Expr b Lam Var b' (CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env' Expr Var e) cseExpr CSEnv env (Let CoreBind bind Expr Var e) = let (CSEnv env', CoreBind bind') = TopLevelFlag -> CSEnv -> CoreBind -> (CSEnv, CoreBind) cseBind TopLevelFlag NotTopLevel CSEnv env CoreBind bind in forall b. Bind b -> Expr b -> Expr b Let CoreBind bind' (CSEnv -> Expr Var -> Expr Var cseExpr CSEnv env' Expr Var e) cseExpr CSEnv env (Case Expr Var e Var bndr Type ty [OutAlt] alts) = CSEnv -> Expr Var -> Var -> Type -> [OutAlt] -> Expr Var cseCase CSEnv env Expr Var e Var bndr Type ty [OutAlt] alts cseCase :: CSEnv -> InExpr -> InId -> InType -> [InAlt] -> OutExpr cseCase :: CSEnv -> Expr Var -> Var -> Type -> [OutAlt] -> Expr Var cseCase CSEnv env Expr Var scrut Var bndr Type ty [OutAlt] alts = forall b. Expr b -> b -> Type -> [Alt b] -> Expr b Case Expr Var scrut1 Var bndr3 Type ty' forall a b. (a -> b) -> a -> b $ CSEnv -> [OutAlt] -> [OutAlt] combineAlts CSEnv alt_env (forall a b. (a -> b) -> [a] -> [b] map OutAlt -> OutAlt cse_alt [OutAlt] alts) where ty' :: Type ty' = Subst -> Type -> Type substTy (CSEnv -> Subst csEnvSubst CSEnv env) Type ty (Bool cse_done, Expr Var scrut1) = CSEnv -> Expr Var -> (Bool, Expr Var) try_for_cse CSEnv env Expr Var scrut bndr1 :: Var bndr1 = Var -> Var zapIdOccInfo Var bndr -- Zapping the OccInfo is needed because the extendCSEnv -- in cse_alt may mean that a dead case binder -- becomes alive, and Lint rejects that (CSEnv env1, Var bndr2) = CSEnv -> Var -> (CSEnv, Var) addBinder CSEnv env Var bndr1 (CSEnv alt_env, Var bndr3) = CSEnv -> Var -> Var -> Expr Var -> Bool -> (CSEnv, Var) extendCSEnvWithBinding CSEnv env1 Var bndr Var bndr2 Expr Var scrut1 Bool cse_done -- extendCSEnvWithBinding: see Note [CSE for case expressions] con_target :: OutExpr con_target :: Expr Var con_target = CSEnv -> Var -> Expr Var lookupSubst CSEnv alt_env Var bndr arg_tys :: [OutType] arg_tys :: [Type] arg_tys = Type -> [Type] tyConAppArgs (Var -> Type idType Var bndr3) -- See Note [CSE for case alternatives] cse_alt :: OutAlt -> OutAlt cse_alt (Alt (DataAlt DataCon con) [Var] args Expr Var rhs) = forall b. AltCon -> [b] -> Expr b -> Alt b Alt (DataCon -> AltCon DataAlt DataCon con) [Var] args' (CSEnv -> Expr Var -> Expr Var tryForCSE CSEnv new_env Expr Var rhs) where (CSEnv env', [Var] args') = CSEnv -> [Var] -> (CSEnv, [Var]) addBinders CSEnv alt_env [Var] args new_env :: CSEnv new_env = CSEnv -> Expr Var -> Expr Var -> CSEnv extendCSEnv CSEnv env' Expr Var con_expr Expr Var con_target con_expr :: Expr Var con_expr = AltCon -> [Var] -> [Type] -> Expr Var mkAltExpr (DataCon -> AltCon DataAlt DataCon con) [Var] args' [Type] arg_tys cse_alt (Alt AltCon con [Var] args Expr Var rhs) = forall b. AltCon -> [b] -> Expr b -> Alt b Alt AltCon con [Var] args' (CSEnv -> Expr Var -> Expr Var tryForCSE CSEnv env' Expr Var rhs) where (CSEnv env', [Var] args') = CSEnv -> [Var] -> (CSEnv, [Var]) addBinders CSEnv alt_env [Var] args combineAlts :: CSEnv -> [OutAlt] -> [OutAlt] -- See Note [Combine case alternatives] combineAlts :: CSEnv -> [OutAlt] -> [OutAlt] combineAlts CSEnv env [OutAlt] alts | (Just OutAlt alt1, [OutAlt] rest_alts) <- [OutAlt] -> (Maybe OutAlt, [OutAlt]) find_bndr_free_alt [OutAlt] alts , Alt AltCon _ [Var] bndrs1 Expr Var rhs1 <- OutAlt alt1 , let filtered_alts :: [OutAlt] filtered_alts = forall a. (a -> Bool) -> [a] -> [a] filterOut (Expr Var -> OutAlt -> Bool identical_alt Expr Var rhs1) [OutAlt] rest_alts , Bool -> Bool not (forall a b. [a] -> [b] -> Bool equalLength [OutAlt] rest_alts [OutAlt] filtered_alts) = ASSERT2( null bndrs1, ppr alts ) forall b. AltCon -> [b] -> Expr b -> Alt b Alt AltCon DEFAULT [] Expr Var rhs1 forall a. a -> [a] -> [a] : [OutAlt] filtered_alts | Bool otherwise = [OutAlt] alts where in_scope :: InScopeSet in_scope = Subst -> InScopeSet substInScope (CSEnv -> Subst csEnvSubst CSEnv env) find_bndr_free_alt :: [CoreAlt] -> (Maybe CoreAlt, [CoreAlt]) -- The (Just alt) is a binder-free alt -- See Note [Combine case alts: awkward corner] find_bndr_free_alt :: [OutAlt] -> (Maybe OutAlt, [OutAlt]) find_bndr_free_alt [] = (forall a. Maybe a Nothing, []) find_bndr_free_alt (alt :: OutAlt alt@(Alt AltCon _ [Var] bndrs Expr Var _) : [OutAlt] alts) | forall (t :: * -> *) a. Foldable t => t a -> Bool null [Var] bndrs = (forall a. a -> Maybe a Just OutAlt alt, [OutAlt] alts) | Bool otherwise = case [OutAlt] -> (Maybe OutAlt, [OutAlt]) find_bndr_free_alt [OutAlt] alts of (Maybe OutAlt mb_bf, [OutAlt] alts) -> (Maybe OutAlt mb_bf, OutAlt altforall a. a -> [a] -> [a] :[OutAlt] alts) identical_alt :: Expr Var -> OutAlt -> Bool identical_alt Expr Var rhs1 (Alt AltCon _ [Var] _ Expr Var rhs) = InScopeSet -> Expr Var -> Expr Var -> Bool eqExpr InScopeSet in_scope Expr Var rhs1 Expr Var rhs -- Even if this alt has binders, they will have been cloned -- If any of these binders are mentioned in 'rhs', then -- 'rhs' won't compare equal to 'rhs1' (which is from an -- alt with no binders). {- Note [CSE for case alternatives] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider case e of x K1 y -> ....(K1 y)... K2 -> ....K2.... We definitely want to CSE that (K1 y) into just x. But what about the lone K2? At first you would think "no" because turning K2 into 'x' increases the number of live variables. But * Turning K2 into x increases the chance of combining identical alts. Example case xs of (_:_) -> f xs [] -> f [] See #17901 and simplCore/should_compile/T17901 for more examples of this kind. * The next run of the simplifier will turn 'x' back into K2, so we won't permanently bloat the free-var count. Note [Combine case alternatives] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ combineAlts is just a more heavyweight version of the use of combineIdenticalAlts in GHC.Core.Opt.Simplify.Utils.prepareAlts. The basic idea is to transform DEFAULT -> e1 K x -> e1 W y z -> e2 ===> DEFAULT -> e1 W y z -> e2 In the simplifier we use cheapEqExpr, because it is called a lot. But here in CSE we use the full eqExpr. After all, two alternatives usually differ near the root, so it probably isn't expensive to compare the full alternative. It seems like the same kind of thing that CSE is supposed to be doing, which is why I put it here. I actually saw some examples in the wild, where some inlining made e1 too big for cheapEqExpr to catch it. Note [Combine case alts: awkward corner] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We would really like to check isDeadBinder on the binders in the alternative. But alas, the simplifer zaps occ-info on binders in case alternatives; see Note [Case alternative occ info] in GHC.Core.Opt.Simplify. * One alternative (perhaps a good one) would be to do OccAnal just before CSE. Then perhaps we could get rid of combineIdenticalAlts in the Simplifier, which might save work. * Another would be for CSE to return free vars as it goes. * But the current solution is to find a nullary alternative (including the DEFAULT alt, if any). This will not catch case x of A y -> blah B z p -> blah where no alternative is nullary or DEFAULT. But the current solution is at least cheap. ************************************************************************ * * \section{The CSE envt} * * ************************************************************************ -} data CSEnv = CS { CSEnv -> Subst cs_subst :: Subst -- Maps InBndrs to OutExprs -- The substitution variables to -- /trivial/ OutExprs, not arbitrary expressions , CSEnv -> CoreMap (Expr Var) cs_map :: CoreMap OutExpr -- The "reverse" mapping. -- Maps a OutExpr to a /trivial/ OutExpr -- The key of cs_map is stripped of all Ticks -- It maps arbitrary expressions to trivial expressions -- representing the same value. E.g @C a b@ to @x1@. , CSEnv -> CoreMap (Expr Var) cs_rec_map :: CoreMap OutExpr -- See Note [CSE for recursive bindings] } emptyCSEnv :: CSEnv emptyCSEnv :: CSEnv emptyCSEnv = CS { cs_map :: CoreMap (Expr Var) cs_map = forall a. CoreMap a emptyCoreMap, cs_rec_map :: CoreMap (Expr Var) cs_rec_map = forall a. CoreMap a emptyCoreMap , cs_subst :: Subst cs_subst = Subst emptySubst } lookupCSEnv :: CSEnv -> OutExpr -> Maybe OutExpr lookupCSEnv :: CSEnv -> Expr Var -> Maybe (Expr Var) lookupCSEnv (CS { cs_map :: CSEnv -> CoreMap (Expr Var) cs_map = CoreMap (Expr Var) csmap }) Expr Var expr = forall a. CoreMap a -> Expr Var -> Maybe a lookupCoreMap CoreMap (Expr Var) csmap Expr Var expr -- | @extendCSEnv env e triv_expr@ will replace any occurrence of @e@ with @triv_expr@ going forward. extendCSEnv :: CSEnv -> OutExpr -> OutExpr -> CSEnv extendCSEnv :: CSEnv -> Expr Var -> Expr Var -> CSEnv extendCSEnv CSEnv cse Expr Var expr Expr Var triv_expr = CSEnv cse { cs_map :: CoreMap (Expr Var) cs_map = forall a. CoreMap a -> Expr Var -> a -> CoreMap a extendCoreMap (CSEnv -> CoreMap (Expr Var) cs_map CSEnv cse) Expr Var sexpr Expr Var triv_expr } where sexpr :: Expr Var sexpr = forall b. (CoreTickish -> Bool) -> Expr b -> Expr b stripTicksE forall (pass :: TickishPass). GenTickish pass -> Bool tickishFloatable Expr Var expr extendCSRecEnv :: CSEnv -> OutId -> OutExpr -> OutExpr -> CSEnv -- See Note [CSE for recursive bindings] extendCSRecEnv :: CSEnv -> Var -> Expr Var -> Expr Var -> CSEnv extendCSRecEnv CSEnv cse Var bndr Expr Var expr Expr Var triv_expr = CSEnv cse { cs_rec_map :: CoreMap (Expr Var) cs_rec_map = forall a. CoreMap a -> Expr Var -> a -> CoreMap a extendCoreMap (CSEnv -> CoreMap (Expr Var) cs_rec_map CSEnv cse) (forall b. b -> Expr b -> Expr b Lam Var bndr Expr Var expr) Expr Var triv_expr } lookupCSRecEnv :: CSEnv -> OutId -> OutExpr -> Maybe OutExpr -- See Note [CSE for recursive bindings] lookupCSRecEnv :: CSEnv -> Var -> Expr Var -> Maybe (Expr Var) lookupCSRecEnv (CS { cs_rec_map :: CSEnv -> CoreMap (Expr Var) cs_rec_map = CoreMap (Expr Var) csmap }) Var bndr Expr Var expr = forall a. CoreMap a -> Expr Var -> Maybe a lookupCoreMap CoreMap (Expr Var) csmap (forall b. b -> Expr b -> Expr b Lam Var bndr Expr Var expr) csEnvSubst :: CSEnv -> Subst csEnvSubst :: CSEnv -> Subst csEnvSubst = CSEnv -> Subst cs_subst lookupSubst :: CSEnv -> Id -> OutExpr lookupSubst :: CSEnv -> Var -> Expr Var lookupSubst (CS { cs_subst :: CSEnv -> Subst cs_subst = Subst sub}) Var x = HasDebugCallStack => Subst -> Var -> Expr Var lookupIdSubst Subst sub Var x extendCSSubst :: CSEnv -> Id -> CoreExpr -> CSEnv extendCSSubst :: CSEnv -> Var -> Expr Var -> CSEnv extendCSSubst CSEnv cse Var x Expr Var rhs = CSEnv cse { cs_subst :: Subst cs_subst = Subst -> Var -> Expr Var -> Subst extendSubst (CSEnv -> Subst cs_subst CSEnv cse) Var x Expr Var rhs } -- | Add clones to the substitution to deal with shadowing. See -- Note [Shadowing] for more details. You should call this whenever -- you go under a binder. addBinder :: CSEnv -> Var -> (CSEnv, Var) addBinder :: CSEnv -> Var -> (CSEnv, Var) addBinder CSEnv cse Var v = (CSEnv cse { cs_subst :: Subst cs_subst = Subst sub' }, Var v') where (Subst sub', Var v') = Subst -> Var -> (Subst, Var) substBndr (CSEnv -> Subst cs_subst CSEnv cse) Var v addBinders :: CSEnv -> [Var] -> (CSEnv, [Var]) addBinders :: CSEnv -> [Var] -> (CSEnv, [Var]) addBinders CSEnv cse [Var] vs = (CSEnv cse { cs_subst :: Subst cs_subst = Subst sub' }, [Var] vs') where (Subst sub', [Var] vs') = Subst -> [Var] -> (Subst, [Var]) substBndrs (CSEnv -> Subst cs_subst CSEnv cse) [Var] vs addRecBinders :: CSEnv -> [Id] -> (CSEnv, [Id]) addRecBinders :: CSEnv -> [Var] -> (CSEnv, [Var]) addRecBinders CSEnv cse [Var] vs = (CSEnv cse { cs_subst :: Subst cs_subst = Subst sub' }, [Var] vs') where (Subst sub', [Var] vs') = Subst -> [Var] -> (Subst, [Var]) substRecBndrs (CSEnv -> Subst cs_subst CSEnv cse) [Var] vs