{-
(c) The AQUA Project, Glasgow University, 1993-1998

\section{Common subexpression}
-}

{-# LANGUAGE CPP #-}

module CSE (cseProgram, cseOneExpr) where

#include "HsVersions.h"

import GhcPrelude

import CoreSubst
import Var              ( Var )
import VarEnv           ( elemInScopeSet, mkInScopeSet )
import Id               ( Id, idType, isDeadBinder
                        , idInlineActivation, setInlineActivation
                        , zapIdOccInfo, zapIdUsageInfo, idInlinePragma
                        , isJoinId, isJoinId_maybe )
import CoreUtils        ( mkAltExpr, eqExpr
                        , exprIsTickedString
                        , stripTicksE, stripTicksT, mkTicks )
import CoreFVs          ( exprFreeVars )
import Type             ( tyConAppArgs )
import CoreSyn
import Outputable
import BasicTypes
import CoreMap
import Util             ( filterOut )
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.


Note [CSE for bindings]
~~~~~~~~~~~~~~~~~~~~~~~
Let-bindings have two cases, implemented by addBinding.

* 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 Trac #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 addBinding 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 (Trac #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 SimplUtils
Note [Top level and postInlineUnconditionally]; 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 (addBinding 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 addBinding 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 addBinding is called with a trivial rhs.

* Non-trivial scrutinee
     case (f x) of y { pat -> ...let z = f x in ... }

  By using addBinding 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
SimplUtils Note [Stable unfoldings and postInlineUnconditionally].

Nor do we want to change the reverse mapping. Suppose we have

   {-# Unf = Stable (\pq. build blah) #-}
   foo = <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.

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, becasue 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
CoreSyn). 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 joint 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.


************************************************************************
*                                                                      *
\section{Common subexpression}
*                                                                      *
************************************************************************
-}

cseProgram :: CoreProgram -> CoreProgram
cseProgram :: CoreProgram -> CoreProgram
cseProgram binds :: CoreProgram
binds = (CSEnv, CoreProgram) -> CoreProgram
forall a b. (a, b) -> b
snd ((CSEnv -> CoreBind -> (CSEnv, CoreBind))
-> CSEnv -> CoreProgram -> (CSEnv, CoreProgram)
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
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 toplevel :: TopLevelFlag
toplevel env :: CSEnv
env (NonRec b :: CoreBndr
b e :: Expr CoreBndr
e)
  = (CSEnv
env2, CoreBndr -> Expr CoreBndr -> CoreBind
forall b. b -> Expr b -> Bind b
NonRec CoreBndr
b2 Expr CoreBndr
e2)
  where
    (env1 :: CSEnv
env1, b1 :: CoreBndr
b1)       = CSEnv -> CoreBndr -> (CSEnv, CoreBndr)
addBinder CSEnv
env CoreBndr
b
    (env2 :: CSEnv
env2, (b2 :: CoreBndr
b2, e2 :: Expr CoreBndr
e2)) = TopLevelFlag
-> CSEnv
-> (CoreBndr, Expr CoreBndr)
-> CoreBndr
-> (CSEnv, (CoreBndr, Expr CoreBndr))
cse_bind TopLevelFlag
toplevel CSEnv
env1 (CoreBndr
b,Expr CoreBndr
e) CoreBndr
b1

cseBind toplevel :: TopLevelFlag
toplevel env :: CSEnv
env (Rec [(in_id :: CoreBndr
in_id, rhs :: Expr CoreBndr
rhs)])
  | CoreBndr -> Bool
noCSE CoreBndr
in_id
  = (CSEnv
env1, [(CoreBndr, Expr CoreBndr)] -> CoreBind
forall b. [(b, Expr b)] -> Bind b
Rec [(CoreBndr
out_id, Expr CoreBndr
rhs')])

  -- See Note [CSE for recursive bindings]
  | Just previous :: Expr CoreBndr
previous <- CSEnv -> CoreBndr -> Expr CoreBndr -> Maybe (Expr CoreBndr)
lookupCSRecEnv CSEnv
env CoreBndr
out_id Expr CoreBndr
rhs''
  , let previous' :: Expr CoreBndr
previous' = [Tickish CoreBndr] -> Expr CoreBndr -> Expr CoreBndr
mkTicks [Tickish CoreBndr]
ticks Expr CoreBndr
previous
        out_id' :: CoreBndr
out_id'   = TopLevelFlag -> CoreBndr -> CoreBndr
delayInlining TopLevelFlag
toplevel CoreBndr
out_id
  = -- We have a hit in the recursive-binding cache
    (CSEnv -> CoreBndr -> Expr CoreBndr -> CSEnv
extendCSSubst CSEnv
env1 CoreBndr
in_id Expr CoreBndr
previous', CoreBndr -> Expr CoreBndr -> CoreBind
forall b. b -> Expr b -> Bind b
NonRec CoreBndr
out_id' Expr CoreBndr
previous')

  | Bool
otherwise
  = (CSEnv -> CoreBndr -> Expr CoreBndr -> Expr CoreBndr -> CSEnv
extendCSRecEnv CSEnv
env1 CoreBndr
out_id Expr CoreBndr
rhs'' Expr CoreBndr
forall b. Expr b
id_expr', [(CoreBndr, Expr CoreBndr)] -> CoreBind
forall b. [(b, Expr b)] -> Bind b
Rec [(CoreBndr
zapped_id, Expr CoreBndr
rhs')])

  where
    (env1 :: CSEnv
env1, [out_id :: CoreBndr
out_id]) = CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addRecBinders CSEnv
env [CoreBndr
in_id]
    rhs' :: Expr CoreBndr
rhs'  = CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env1 Expr CoreBndr
rhs
    rhs'' :: Expr CoreBndr
rhs'' = (Tickish CoreBndr -> Bool) -> Expr CoreBndr -> Expr CoreBndr
forall b. (Tickish CoreBndr -> Bool) -> Expr b -> Expr b
stripTicksE Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Expr CoreBndr
rhs'
    ticks :: [Tickish CoreBndr]
ticks = (Tickish CoreBndr -> Bool) -> Expr CoreBndr -> [Tickish CoreBndr]
forall b.
(Tickish CoreBndr -> Bool) -> Expr b -> [Tickish CoreBndr]
stripTicksT Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Expr CoreBndr
rhs'
    id_expr' :: Expr b
id_expr'  = CoreBndr -> Expr b
forall b. CoreBndr -> Expr b
varToCoreExpr CoreBndr
out_id
    zapped_id :: CoreBndr
zapped_id = CoreBndr -> CoreBndr
zapIdUsageInfo CoreBndr
out_id

cseBind toplevel :: TopLevelFlag
toplevel env :: CSEnv
env (Rec pairs :: [(CoreBndr, Expr CoreBndr)]
pairs)
  = (CSEnv
env2, [(CoreBndr, Expr CoreBndr)] -> CoreBind
forall b. [(b, Expr b)] -> Bind b
Rec [(CoreBndr, Expr CoreBndr)]
pairs')
  where
    (env1 :: CSEnv
env1, bndrs1 :: [CoreBndr]
bndrs1) = CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addRecBinders CSEnv
env (((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> [(CoreBndr, Expr CoreBndr)] -> [CoreBndr]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst [(CoreBndr, Expr CoreBndr)]
pairs)
    (env2 :: CSEnv
env2, pairs' :: [(CoreBndr, Expr CoreBndr)]
pairs') = (CSEnv
 -> ((CoreBndr, Expr CoreBndr), CoreBndr)
 -> (CSEnv, (CoreBndr, Expr CoreBndr)))
-> CSEnv
-> [((CoreBndr, Expr CoreBndr), CoreBndr)]
-> (CSEnv, [(CoreBndr, Expr CoreBndr)])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL CSEnv
-> ((CoreBndr, Expr CoreBndr), CoreBndr)
-> (CSEnv, (CoreBndr, Expr CoreBndr))
do_one CSEnv
env1 ([(CoreBndr, Expr CoreBndr)]
-> [CoreBndr] -> [((CoreBndr, Expr CoreBndr), CoreBndr)]
forall a b. [a] -> [b] -> [(a, b)]
zip [(CoreBndr, Expr CoreBndr)]
pairs [CoreBndr]
bndrs1)

    do_one :: CSEnv
-> ((CoreBndr, Expr CoreBndr), CoreBndr)
-> (CSEnv, (CoreBndr, Expr CoreBndr))
do_one env :: CSEnv
env (pr :: (CoreBndr, Expr CoreBndr)
pr, b1 :: CoreBndr
b1) = TopLevelFlag
-> CSEnv
-> (CoreBndr, Expr CoreBndr)
-> CoreBndr
-> (CSEnv, (CoreBndr, Expr CoreBndr))
cse_bind TopLevelFlag
toplevel CSEnv
env (CoreBndr, Expr CoreBndr)
pr CoreBndr
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@.
cse_bind :: TopLevelFlag -> CSEnv -> (InId, InExpr) -> OutId -> (CSEnv, (OutId, OutExpr))
cse_bind :: TopLevelFlag
-> CSEnv
-> (CoreBndr, Expr CoreBndr)
-> CoreBndr
-> (CSEnv, (CoreBndr, Expr CoreBndr))
cse_bind toplevel :: TopLevelFlag
toplevel env :: CSEnv
env (in_id :: CoreBndr
in_id, in_rhs :: Expr CoreBndr
in_rhs) out_id :: CoreBndr
out_id
  | TopLevelFlag -> Bool
isTopLevel TopLevelFlag
toplevel, Expr CoreBndr -> Bool
exprIsTickedString Expr CoreBndr
in_rhs
      -- See Note [Take care with literal strings]
  = (CSEnv
env', (CoreBndr
out_id', Expr CoreBndr
in_rhs))

  | Just arity :: JoinArity
arity <- CoreBndr -> Maybe JoinArity
isJoinId_maybe CoreBndr
in_id
      -- See Note [Look inside join-point binders]
  = let (params :: [CoreBndr]
params, in_body :: Expr CoreBndr
in_body) = JoinArity -> Expr CoreBndr -> ([CoreBndr], Expr CoreBndr)
forall b. JoinArity -> Expr b -> ([b], Expr b)
collectNBinders JoinArity
arity Expr CoreBndr
in_rhs
        (env' :: CSEnv
env', params' :: [CoreBndr]
params') = CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addBinders CSEnv
env [CoreBndr]
params
        out_body :: Expr CoreBndr
out_body = CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE CSEnv
env' Expr CoreBndr
in_body
    in (CSEnv
env, (CoreBndr
out_id, [CoreBndr] -> Expr CoreBndr -> Expr CoreBndr
forall b. [b] -> Expr b -> Expr b
mkLams [CoreBndr]
params' Expr CoreBndr
out_body))

  | Bool
otherwise
  = (CSEnv
env', (CoreBndr
out_id'', Expr CoreBndr
out_rhs))
  where
    (env' :: CSEnv
env', out_id' :: CoreBndr
out_id') = CSEnv -> CoreBndr -> CoreBndr -> Expr CoreBndr -> (CSEnv, CoreBndr)
addBinding CSEnv
env CoreBndr
in_id CoreBndr
out_id Expr CoreBndr
out_rhs
    (cse_done :: Bool
cse_done, out_rhs :: Expr CoreBndr
out_rhs) = CSEnv -> Expr CoreBndr -> (Bool, Expr CoreBndr)
try_for_cse CSEnv
env Expr CoreBndr
in_rhs
    out_id'' :: CoreBndr
out_id'' | Bool
cse_done  = TopLevelFlag -> CoreBndr -> CoreBndr
delayInlining TopLevelFlag
toplevel CoreBndr
out_id'
             | Bool
otherwise = CoreBndr
out_id'

delayInlining :: TopLevelFlag -> Id -> Id
-- Add a NOINLINE[2] if the Id doesn't have an INLNE pragma already
delayInlining :: TopLevelFlag -> CoreBndr -> CoreBndr
delayInlining top_lvl :: TopLevelFlag
top_lvl bndr :: CoreBndr
bndr
  | TopLevelFlag -> Bool
isTopLevel TopLevelFlag
top_lvl
  , Activation -> Bool
isAlwaysActive (CoreBndr -> Activation
idInlineActivation CoreBndr
bndr)
  = CoreBndr
bndr CoreBndr -> Activation -> CoreBndr
`setInlineActivation` Activation
activeAfterInitial
  | Bool
otherwise
  = CoreBndr
bndr

addBinding :: CSEnv                      -- Includes InId->OutId cloning
           -> InVar                      -- Could be a let-bound type
           -> OutId -> OutExpr           -- Processed binding
           -> (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 (see
-- Note [Type-let] in CoreSyn), in which case we can just substitute.
addBinding :: CSEnv -> CoreBndr -> CoreBndr -> Expr CoreBndr -> (CSEnv, CoreBndr)
addBinding env :: CSEnv
env in_id :: CoreBndr
in_id out_id :: CoreBndr
out_id rhs' :: Expr CoreBndr
rhs'
  | Bool -> Bool
not (CoreBndr -> Bool
isId CoreBndr
in_id) = (CSEnv -> CoreBndr -> Expr CoreBndr -> CSEnv
extendCSSubst CSEnv
env CoreBndr
in_id Expr CoreBndr
rhs',     CoreBndr
out_id)
  | CoreBndr -> Bool
noCSE CoreBndr
in_id      = (CSEnv
env,                              CoreBndr
out_id)
  | Bool
use_subst        = (CSEnv -> CoreBndr -> Expr CoreBndr -> CSEnv
extendCSSubst CSEnv
env CoreBndr
in_id Expr CoreBndr
rhs',     CoreBndr
out_id)
  | Bool
otherwise        = (CSEnv -> Expr CoreBndr -> Expr CoreBndr -> CSEnv
extendCSEnv CSEnv
env Expr CoreBndr
rhs' Expr CoreBndr
forall b. Expr b
id_expr', CoreBndr
zapped_id)
  where
    id_expr' :: Expr b
id_expr'  = CoreBndr -> Expr b
forall b. CoreBndr -> Expr b
varToCoreExpr CoreBndr
out_id
    zapped_id :: CoreBndr
zapped_id = CoreBndr -> CoreBndr
zapIdUsageInfo CoreBndr
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 Trac #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 = case Expr CoreBndr
rhs' of
                   Var {} -> Bool
True
                   _      -> 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 :: CoreBndr -> Bool
noCSE id :: CoreBndr
id =  Bool -> Bool
not (Activation -> Bool
isAlwaysActive (CoreBndr -> Activation
idInlineActivation CoreBndr
id)) Bool -> Bool -> Bool
&&
            Bool -> Bool
not (InlineSpec -> Bool
noUserInlineSpec (InlinePragma -> InlineSpec
inlinePragmaSpec (CoreBndr -> InlinePragma
idInlinePragma CoreBndr
id)))
             -- See Note [CSE for INLINE and NOINLINE]
         Bool -> Bool -> Bool
|| InlinePragma -> Bool
isAnyInlinePragma (CoreBndr -> InlinePragma
idInlinePragma CoreBndr
id)
             -- See Note [CSE for stable unfoldings]
         Bool -> Bool -> Bool
|| CoreBndr -> Bool
isJoinId CoreBndr
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
[CoreSyn top-level string literals] in CoreSyn.

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 (Trac #13367).

Note [Delay inlining after CSE]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Suppose (Trac #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, when adding a top-level
  g = f
binding after a "hit" in the CSE cache, add a NOINLINE[2] activation
to it, to ensure it's not inlined right away.

Why top level only?  Because for nested bindings we are already past
phase 2 and will never return there.
-}

tryForCSE :: CSEnv -> InExpr -> OutExpr
tryForCSE :: CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE env :: CSEnv
env expr :: Expr CoreBndr
expr = (Bool, Expr CoreBndr) -> Expr CoreBndr
forall a b. (a, b) -> b
snd (CSEnv -> Expr CoreBndr -> (Bool, Expr CoreBndr)
try_for_cse CSEnv
env Expr CoreBndr
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 CoreBndr -> (Bool, Expr CoreBndr)
try_for_cse env :: CSEnv
env expr :: Expr CoreBndr
expr
  | Just e :: Expr CoreBndr
e <- CSEnv -> Expr CoreBndr -> Maybe (Expr CoreBndr)
lookupCSEnv CSEnv
env Expr CoreBndr
expr'' = (Bool
True,  [Tickish CoreBndr] -> Expr CoreBndr -> Expr CoreBndr
mkTicks [Tickish CoreBndr]
ticks Expr CoreBndr
e)
  | Bool
otherwise                        = (Bool
False, Expr CoreBndr
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 CoreBndr
expr'  = CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env Expr CoreBndr
expr
    expr'' :: Expr CoreBndr
expr'' = (Tickish CoreBndr -> Bool) -> Expr CoreBndr -> Expr CoreBndr
forall b. (Tickish CoreBndr -> Bool) -> Expr b -> Expr b
stripTicksE Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Expr CoreBndr
expr'
    ticks :: [Tickish CoreBndr]
ticks  = (Tickish CoreBndr -> Bool) -> Expr CoreBndr -> [Tickish CoreBndr]
forall b.
(Tickish CoreBndr -> Bool) -> Expr b -> [Tickish CoreBndr]
stripTicksT Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Expr CoreBndr
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 CoreBndr -> Expr CoreBndr
cseOneExpr e :: Expr CoreBndr
e = CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env Expr CoreBndr
e
  where env :: CSEnv
env = CSEnv
emptyCSEnv {cs_subst :: Subst
cs_subst = InScopeSet -> Subst
mkEmptySubst (VarSet -> InScopeSet
mkInScopeSet (Expr CoreBndr -> VarSet
exprFreeVars Expr CoreBndr
e)) }

cseExpr :: CSEnv -> InExpr -> OutExpr
cseExpr :: CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr env :: CSEnv
env (Type t :: Type
t)              = Type -> Expr CoreBndr
forall b. Type -> Expr b
Type (Subst -> Type -> Type
substTy (CSEnv -> Subst
csEnvSubst CSEnv
env) Type
t)
cseExpr env :: CSEnv
env (Coercion c :: Coercion
c)          = Coercion -> Expr CoreBndr
forall b. Coercion -> Expr b
Coercion (Subst -> Coercion -> Coercion
substCo (CSEnv -> Subst
csEnvSubst CSEnv
env) Coercion
c)
cseExpr _   (Lit lit :: Literal
lit)             = Literal -> Expr CoreBndr
forall b. Literal -> Expr b
Lit Literal
lit
cseExpr env :: CSEnv
env (Var v :: CoreBndr
v)               = CSEnv -> CoreBndr -> Expr CoreBndr
lookupSubst CSEnv
env CoreBndr
v
cseExpr env :: CSEnv
env (App f :: Expr CoreBndr
f a :: Expr CoreBndr
a)             = Expr CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. Expr b -> Expr b -> Expr b
App (CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env Expr CoreBndr
f) (CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE CSEnv
env Expr CoreBndr
a)
cseExpr env :: CSEnv
env (Tick t :: Tickish CoreBndr
t e :: Expr CoreBndr
e)            = Tickish CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. Tickish CoreBndr -> Expr b -> Expr b
Tick Tickish CoreBndr
t (CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env Expr CoreBndr
e)
cseExpr env :: CSEnv
env (Cast e :: Expr CoreBndr
e co :: Coercion
co)           = Expr CoreBndr -> Coercion -> Expr CoreBndr
forall b. Expr b -> Coercion -> Expr b
Cast (CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE CSEnv
env Expr CoreBndr
e) (Subst -> Coercion -> Coercion
substCo (CSEnv -> Subst
csEnvSubst CSEnv
env) Coercion
co)
cseExpr env :: CSEnv
env (Lam b :: CoreBndr
b e :: Expr CoreBndr
e)             = let (env' :: CSEnv
env', b' :: CoreBndr
b') = CSEnv -> CoreBndr -> (CSEnv, CoreBndr)
addBinder CSEnv
env CoreBndr
b
                                    in CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. b -> Expr b -> Expr b
Lam CoreBndr
b' (CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env' Expr CoreBndr
e)
cseExpr env :: CSEnv
env (Let bind :: CoreBind
bind e :: Expr CoreBndr
e)          = let (env' :: CSEnv
env', bind' :: CoreBind
bind') = TopLevelFlag -> CSEnv -> CoreBind -> (CSEnv, CoreBind)
cseBind TopLevelFlag
NotTopLevel CSEnv
env CoreBind
bind
                                    in CoreBind -> Expr CoreBndr -> Expr CoreBndr
forall b. Bind b -> Expr b -> Expr b
Let CoreBind
bind' (CSEnv -> Expr CoreBndr -> Expr CoreBndr
cseExpr CSEnv
env' Expr CoreBndr
e)
cseExpr env :: CSEnv
env (Case e :: Expr CoreBndr
e bndr :: CoreBndr
bndr ty :: Type
ty alts :: [Alt CoreBndr]
alts) = CSEnv
-> Expr CoreBndr
-> CoreBndr
-> Type
-> [Alt CoreBndr]
-> Expr CoreBndr
cseCase CSEnv
env Expr CoreBndr
e CoreBndr
bndr Type
ty [Alt CoreBndr]
alts

cseCase :: CSEnv -> InExpr -> InId -> InType -> [InAlt] -> OutExpr
cseCase :: CSEnv
-> Expr CoreBndr
-> CoreBndr
-> Type
-> [Alt CoreBndr]
-> Expr CoreBndr
cseCase env :: CSEnv
env scrut :: Expr CoreBndr
scrut bndr :: CoreBndr
bndr ty :: Type
ty alts :: [Alt CoreBndr]
alts
  = Expr CoreBndr
-> CoreBndr -> Type -> [Alt CoreBndr] -> Expr CoreBndr
forall b. Expr b -> b -> Type -> [Alt b] -> Expr b
Case Expr CoreBndr
scrut1 CoreBndr
bndr3 Type
ty' ([Alt CoreBndr] -> Expr CoreBndr)
-> [Alt CoreBndr] -> Expr CoreBndr
forall a b. (a -> b) -> a -> b
$
    CSEnv -> [Alt CoreBndr] -> [Alt CoreBndr]
combineAlts CSEnv
alt_env ((Alt CoreBndr -> Alt CoreBndr) -> [Alt CoreBndr] -> [Alt CoreBndr]
forall a b. (a -> b) -> [a] -> [b]
map Alt CoreBndr -> Alt CoreBndr
cse_alt [Alt CoreBndr]
alts)
  where
    ty' :: Type
ty' = Subst -> Type -> Type
substTy (CSEnv -> Subst
csEnvSubst CSEnv
env) Type
ty
    scrut1 :: Expr CoreBndr
scrut1 = CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE CSEnv
env Expr CoreBndr
scrut

    bndr1 :: CoreBndr
bndr1 = CoreBndr -> CoreBndr
zapIdOccInfo CoreBndr
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
    (env1 :: CSEnv
env1, bndr2 :: CoreBndr
bndr2)    = CSEnv -> CoreBndr -> (CSEnv, CoreBndr)
addBinder CSEnv
env CoreBndr
bndr1
    (alt_env :: CSEnv
alt_env, bndr3 :: CoreBndr
bndr3) = CSEnv -> CoreBndr -> CoreBndr -> Expr CoreBndr -> (CSEnv, CoreBndr)
addBinding CSEnv
env1 CoreBndr
bndr CoreBndr
bndr2 Expr CoreBndr
scrut1
         -- addBinding: see Note [CSE for case expressions]

    con_target :: OutExpr
    con_target :: Expr CoreBndr
con_target = CSEnv -> CoreBndr -> Expr CoreBndr
lookupSubst CSEnv
alt_env CoreBndr
bndr

    arg_tys :: [OutType]
    arg_tys :: [Type]
arg_tys = Type -> [Type]
tyConAppArgs (CoreBndr -> Type
idType CoreBndr
bndr3)

    -- Given case x of { K y z -> ...K y z... }
    -- CSE K y z into x...
    cse_alt :: Alt CoreBndr -> Alt CoreBndr
cse_alt (DataAlt con :: DataCon
con, args :: [CoreBndr]
args, rhs :: Expr CoreBndr
rhs)
        | Bool -> Bool
not ([CoreBndr] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [CoreBndr]
args)
                -- ... but don't try CSE if there are no args; it just increases the number
                -- of live vars.  E.g.
                --      case x of { True -> ....True.... }
                -- Don't replace True by x!
                -- Hence the 'null args', which also deal with literals and DEFAULT
        = (DataCon -> AltCon
DataAlt DataCon
con, [CoreBndr]
args', CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE CSEnv
new_env Expr CoreBndr
rhs)
        where
          (env' :: CSEnv
env', args' :: [CoreBndr]
args') = CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addBinders CSEnv
alt_env [CoreBndr]
args
          new_env :: CSEnv
new_env       = CSEnv -> Expr CoreBndr -> Expr CoreBndr -> CSEnv
extendCSEnv CSEnv
env' Expr CoreBndr
con_expr Expr CoreBndr
con_target
          con_expr :: Expr CoreBndr
con_expr      = AltCon -> [CoreBndr] -> [Type] -> Expr CoreBndr
mkAltExpr (DataCon -> AltCon
DataAlt DataCon
con) [CoreBndr]
args' [Type]
arg_tys

    cse_alt (con :: AltCon
con, args :: [CoreBndr]
args, rhs :: Expr CoreBndr
rhs)
        = (AltCon
con, [CoreBndr]
args', CSEnv -> Expr CoreBndr -> Expr CoreBndr
tryForCSE CSEnv
env' Expr CoreBndr
rhs)
        where
          (env' :: CSEnv
env', args' :: [CoreBndr]
args') = CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addBinders CSEnv
alt_env [CoreBndr]
args

combineAlts :: CSEnv -> [InAlt] -> [InAlt]
-- See Note [Combine case alternatives]
combineAlts :: CSEnv -> [Alt CoreBndr] -> [Alt CoreBndr]
combineAlts env :: CSEnv
env ((_,bndrs1 :: [CoreBndr]
bndrs1,rhs1 :: Expr CoreBndr
rhs1) : rest_alts :: [Alt CoreBndr]
rest_alts)
  | (CoreBndr -> Bool) -> [CoreBndr] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all CoreBndr -> Bool
isDeadBinder [CoreBndr]
bndrs1
  = (AltCon
DEFAULT, [], Expr CoreBndr
rhs1) Alt CoreBndr -> [Alt CoreBndr] -> [Alt CoreBndr]
forall a. a -> [a] -> [a]
: [Alt CoreBndr]
filtered_alts
  where
    in_scope :: InScopeSet
in_scope = Subst -> InScopeSet
substInScope (CSEnv -> Subst
csEnvSubst CSEnv
env)
    filtered_alts :: [Alt CoreBndr]
filtered_alts = (Alt CoreBndr -> Bool) -> [Alt CoreBndr] -> [Alt CoreBndr]
forall a. (a -> Bool) -> [a] -> [a]
filterOut Alt CoreBndr -> Bool
forall (t :: * -> *) a.
Foldable t =>
(a, t CoreBndr, Expr CoreBndr) -> Bool
identical [Alt CoreBndr]
rest_alts
    identical :: (a, t CoreBndr, Expr CoreBndr) -> Bool
identical (_con :: a
_con, bndrs :: t CoreBndr
bndrs, rhs :: Expr CoreBndr
rhs) = (CoreBndr -> Bool) -> t CoreBndr -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all CoreBndr -> Bool
ok t CoreBndr
bndrs Bool -> Bool -> Bool
&& InScopeSet -> Expr CoreBndr -> Expr CoreBndr -> Bool
eqExpr InScopeSet
in_scope Expr CoreBndr
rhs1 Expr CoreBndr
rhs
    ok :: CoreBndr -> Bool
ok bndr :: CoreBndr
bndr = CoreBndr -> Bool
isDeadBinder CoreBndr
bndr Bool -> Bool -> Bool
|| Bool -> Bool
not (CoreBndr
bndr CoreBndr -> InScopeSet -> Bool
`elemInScopeSet` InScopeSet
in_scope)

combineAlts _ alts :: [Alt CoreBndr]
alts = [Alt CoreBndr]
alts  -- Default case

{- Note [Combine case alternatives]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combineAlts is just a more heavyweight version of the use of
combineIdenticalAlts in SimplUtils.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 acutally saw some examples in the wild, where some inlining made e1 too
big for cheapEqExpr to catch it.


************************************************************************
*                                                                      *
\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 CoreBndr)
cs_map   :: CoreMap OutExpr   -- The reverse mapping
            -- Maps a OutExpr to a /trivial/ OutExpr
            -- The key of cs_map is stripped of all Ticks

       , CSEnv -> CoreMap (Expr CoreBndr)
cs_rec_map :: CoreMap OutExpr
            -- See Note [CSE for recursive bindings]
       }

emptyCSEnv :: CSEnv
emptyCSEnv :: CSEnv
emptyCSEnv = CS :: Subst
-> CoreMap (Expr CoreBndr) -> CoreMap (Expr CoreBndr) -> CSEnv
CS { cs_map :: CoreMap (Expr CoreBndr)
cs_map = CoreMap (Expr CoreBndr)
forall a. CoreMap a
emptyCoreMap, cs_rec_map :: CoreMap (Expr CoreBndr)
cs_rec_map = CoreMap (Expr CoreBndr)
forall a. CoreMap a
emptyCoreMap
                , cs_subst :: Subst
cs_subst = Subst
emptySubst }

lookupCSEnv :: CSEnv -> OutExpr -> Maybe OutExpr
lookupCSEnv :: CSEnv -> Expr CoreBndr -> Maybe (Expr CoreBndr)
lookupCSEnv (CS { cs_map :: CSEnv -> CoreMap (Expr CoreBndr)
cs_map = CoreMap (Expr CoreBndr)
csmap }) expr :: Expr CoreBndr
expr
  = CoreMap (Expr CoreBndr) -> Expr CoreBndr -> Maybe (Expr CoreBndr)
forall a. CoreMap a -> Expr CoreBndr -> Maybe a
lookupCoreMap CoreMap (Expr CoreBndr)
csmap Expr CoreBndr
expr

extendCSEnv :: CSEnv -> OutExpr -> OutExpr -> CSEnv
extendCSEnv :: CSEnv -> Expr CoreBndr -> Expr CoreBndr -> CSEnv
extendCSEnv cse :: CSEnv
cse expr :: Expr CoreBndr
expr triv_expr :: Expr CoreBndr
triv_expr
  = CSEnv
cse { cs_map :: CoreMap (Expr CoreBndr)
cs_map = CoreMap (Expr CoreBndr)
-> Expr CoreBndr -> Expr CoreBndr -> CoreMap (Expr CoreBndr)
forall a. CoreMap a -> Expr CoreBndr -> a -> CoreMap a
extendCoreMap (CSEnv -> CoreMap (Expr CoreBndr)
cs_map CSEnv
cse) Expr CoreBndr
sexpr Expr CoreBndr
triv_expr }
  where
    sexpr :: Expr CoreBndr
sexpr = (Tickish CoreBndr -> Bool) -> Expr CoreBndr -> Expr CoreBndr
forall b. (Tickish CoreBndr -> Bool) -> Expr b -> Expr b
stripTicksE Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Expr CoreBndr
expr

extendCSRecEnv :: CSEnv -> OutId -> OutExpr -> OutExpr -> CSEnv
-- See Note [CSE for recursive bindings]
extendCSRecEnv :: CSEnv -> CoreBndr -> Expr CoreBndr -> Expr CoreBndr -> CSEnv
extendCSRecEnv cse :: CSEnv
cse bndr :: CoreBndr
bndr expr :: Expr CoreBndr
expr triv_expr :: Expr CoreBndr
triv_expr
  = CSEnv
cse { cs_rec_map :: CoreMap (Expr CoreBndr)
cs_rec_map = CoreMap (Expr CoreBndr)
-> Expr CoreBndr -> Expr CoreBndr -> CoreMap (Expr CoreBndr)
forall a. CoreMap a -> Expr CoreBndr -> a -> CoreMap a
extendCoreMap (CSEnv -> CoreMap (Expr CoreBndr)
cs_rec_map CSEnv
cse) (CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. b -> Expr b -> Expr b
Lam CoreBndr
bndr Expr CoreBndr
expr) Expr CoreBndr
triv_expr }

lookupCSRecEnv :: CSEnv -> OutId -> OutExpr -> Maybe OutExpr
-- See Note [CSE for recursive bindings]
lookupCSRecEnv :: CSEnv -> CoreBndr -> Expr CoreBndr -> Maybe (Expr CoreBndr)
lookupCSRecEnv (CS { cs_rec_map :: CSEnv -> CoreMap (Expr CoreBndr)
cs_rec_map = CoreMap (Expr CoreBndr)
csmap }) bndr :: CoreBndr
bndr expr :: Expr CoreBndr
expr
  = CoreMap (Expr CoreBndr) -> Expr CoreBndr -> Maybe (Expr CoreBndr)
forall a. CoreMap a -> Expr CoreBndr -> Maybe a
lookupCoreMap CoreMap (Expr CoreBndr)
csmap (CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. b -> Expr b -> Expr b
Lam CoreBndr
bndr Expr CoreBndr
expr)

csEnvSubst :: CSEnv -> Subst
csEnvSubst :: CSEnv -> Subst
csEnvSubst = CSEnv -> Subst
cs_subst

lookupSubst :: CSEnv -> Id -> OutExpr
lookupSubst :: CSEnv -> CoreBndr -> Expr CoreBndr
lookupSubst (CS { cs_subst :: CSEnv -> Subst
cs_subst = Subst
sub}) x :: CoreBndr
x = SDoc -> Subst -> CoreBndr -> Expr CoreBndr
lookupIdSubst (String -> SDoc
text "CSE.lookupSubst") Subst
sub CoreBndr
x

extendCSSubst :: CSEnv -> Id  -> CoreExpr -> CSEnv
extendCSSubst :: CSEnv -> CoreBndr -> Expr CoreBndr -> CSEnv
extendCSSubst cse :: CSEnv
cse x :: CoreBndr
x rhs :: Expr CoreBndr
rhs = CSEnv
cse { cs_subst :: Subst
cs_subst = Subst -> CoreBndr -> Expr CoreBndr -> Subst
extendSubst (CSEnv -> Subst
cs_subst CSEnv
cse) CoreBndr
x Expr CoreBndr
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 -> CoreBndr -> (CSEnv, CoreBndr)
addBinder cse :: CSEnv
cse v :: CoreBndr
v = (CSEnv
cse { cs_subst :: Subst
cs_subst = Subst
sub' }, CoreBndr
v')
                where
                  (sub' :: Subst
sub', v' :: CoreBndr
v') = Subst -> CoreBndr -> (Subst, CoreBndr)
substBndr (CSEnv -> Subst
cs_subst CSEnv
cse) CoreBndr
v

addBinders :: CSEnv -> [Var] -> (CSEnv, [Var])
addBinders :: CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addBinders cse :: CSEnv
cse vs :: [CoreBndr]
vs = (CSEnv
cse { cs_subst :: Subst
cs_subst = Subst
sub' }, [CoreBndr]
vs')
                where
                  (sub' :: Subst
sub', vs' :: [CoreBndr]
vs') = Subst -> [CoreBndr] -> (Subst, [CoreBndr])
substBndrs (CSEnv -> Subst
cs_subst CSEnv
cse) [CoreBndr]
vs

addRecBinders :: CSEnv -> [Id] -> (CSEnv, [Id])
addRecBinders :: CSEnv -> [CoreBndr] -> (CSEnv, [CoreBndr])
addRecBinders cse :: CSEnv
cse vs :: [CoreBndr]
vs = (CSEnv
cse { cs_subst :: Subst
cs_subst = Subst
sub' }, [CoreBndr]
vs')
                where
                  (sub' :: Subst
sub', vs' :: [CoreBndr]
vs') = Subst -> [CoreBndr] -> (Subst, [CoreBndr])
substRecBndrs (CSEnv -> Subst
cs_subst CSEnv
cse) [CoreBndr]
vs