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

    \section{Common subexpression}
    -}

    module GHC.Core.Opt.CSE (cseProgram, cseOneExpr) where

    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, idJoinPointHood, idUnfolding )
    import GHC.Core.Utils   ( mkAltExpr
                            , 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 )
    import GHC.Utils.Panic
    import Data.Functor.Identity ( Identity (..) )
    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 *don't* 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 in CSE]
    ~~~~~~~~~~~~~~~~~~~~~~~
    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 propagate 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 exception 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.

    Wrinkles

    * Stable unfoldings are also created during worker/wrapper when we
      decide that a function's definition is so small that it should
      always inline, or indeed for the wrapper function itself.  In this
      case we still want to do CSE (#13340). Hence the use of
      isStableUserUnfolding/isStableSystemUnfolding rather than
      isStableUnfolding.

    * 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-can-float 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 occurrences 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 = (CSEnv, CoreProgram) -> CoreProgram
    forall a b. (a, b) -> b
    snd ((CSEnv -> CoreBind -> (CSEnv, CoreBind))
    -> CSEnv -> CoreProgram -> (CSEnv, CoreProgram)
    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, Var -> Expr Var -> CoreBind
    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, [(Var, Expr Var)] -> CoreBind
    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', Var -> Expr Var -> CoreBind
    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', [(Var, Expr Var)] -> CoreBind
    forall b. [(b, Expr b)] -> Bind b
    Rec [(Var
    zapped_id, Expr Var
    rhs')])

      where
        (CSEnv
    env1, Identity Var
    out_id) = CSEnv -> Identity Var -> (CSEnv, Identity Var)
    forall (f :: * -> *).
    Traversable f =>
    CSEnv -> f Var -> (CSEnv, f Var)
    addRecBinders CSEnv
    env (Var -> Identity Var
    forall a. a -> Identity a
    Identity Var
    in_id)
        rhs' :: Expr Var
    rhs'  = CSEnv -> Expr Var -> Expr Var
    cseExpr CSEnv
    env1 Expr Var
    rhs
        rhs'' :: Expr Var
    rhs'' = (CoreTickish -> Bool) -> Expr Var -> Expr Var
    forall b. (CoreTickish -> Bool) -> Expr b -> Expr b
    stripTicksE CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable Expr Var
    rhs'
        ticks :: [CoreTickish]
    ticks = (CoreTickish -> Bool) -> Expr Var -> [CoreTickish]
    forall b. (CoreTickish -> Bool) -> Expr b -> [CoreTickish]
    stripTicksT CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable Expr Var
    rhs'
        id_expr' :: Expr Var
    id_expr'  = Var -> Expr Var
    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, [(Var, Expr Var)] -> CoreBind
    forall b. [(b, Expr b)] -> Bind b
    Rec [(Var, Expr Var)]
    pairs')
      where
        (CSEnv
    env1, [Var]
    bndrs1) = CSEnv -> [Var] -> (CSEnv, [Var])
    forall (f :: * -> *).
    Traversable f =>
    CSEnv -> f Var -> (CSEnv, f Var)
    addRecBinders CSEnv
    env (((Var, Expr Var) -> Var) -> [(Var, Expr Var)] -> [Var]
    forall a b. (a -> b) -> [a] -> [b]
    map (Var, Expr Var) -> Var
    forall a b. (a, b) -> a
    fst [(Var, Expr Var)]
    pairs)
        (CSEnv
    env2, [(Var, Expr Var)]
    pairs') = (CSEnv -> ((Var, Expr Var), Var) -> (CSEnv, (Var, Expr Var)))
    -> CSEnv -> [((Var, Expr Var), Var)] -> (CSEnv, [(Var, Expr Var)])
    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 ([(Var, Expr Var)] -> [Var] -> [((Var, Expr Var), Var)]
    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))

      | JoinPoint Int
    arity <- Var -> JoinPointHood
    idJoinPointHood Var
    out_id
          -- See Note [Look inside join-point binders]
      = let ([Var]
    params, Expr Var
    in_body) = Int -> Expr Var -> ([Var], Expr Var)
    forall b. Int -> Expr b -> ([b], Expr b)
    collectNBinders Int
    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, [Var] -> Expr Var -> Expr Var
    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 (Var -> Var) -> Var -> Var
    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'  = Var -> Expr Var
    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
      | Var -> Bool
    isJoinId Var
    id                = Bool
    no_cse  -- See Note [CSE for join points?]
      | Unfolding -> Bool
    isStableUserUnfolding  Unfolding
    unf = Bool
    no_cse  -- See Note [CSE for stable unfoldings]
      | Bool
    user_activation_control    = Bool
    no_cse  -- See Note [CSE for INLINE and NOINLINE]
      | Bool
    otherwise = Bool
    yes_cse
       where
         unf :: Unfolding
    unf = IdUnfoldingFun
    idUnfolding Var
    id
         user_activation_control :: Bool
    user_activation_control = 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)))
         yes_cse :: Bool
    yes_cse = Bool
    False
         no_cse :: Bool
    no_cse  = Bool
    True

    {- 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 = (Bool, Expr Var) -> Expr Var
    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'' = (CoreTickish -> Bool) -> Expr Var -> Expr Var
    forall b. (CoreTickish -> Bool) -> Expr b -> Expr b
    stripTicksE CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable Expr Var
    expr'
        ticks :: [CoreTickish]
    ticks  = (CoreTickish -> Bool) -> Expr Var -> [CoreTickish]
    forall b. (CoreTickish -> Bool) -> Expr b -> [CoreTickish]
    stripTicksT CoreTickish -> Bool
    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 = mkEmptySubst (mkInScopeSet (exprFreeVars e)) }

    cseExpr :: CSEnv -> InExpr -> OutExpr
    cseExpr :: CSEnv -> Expr Var -> Expr Var
    cseExpr CSEnv
    env (Type Type
    t)              = Type -> Expr Var
    forall b. Type -> Expr b
    Type (Subst -> Type -> Type
    substTyUnchecked (CSEnv -> Subst
    csEnvSubst CSEnv
    env) Type
    t)
    cseExpr CSEnv
    env (Coercion Coercion
    c)          = Coercion -> Expr Var
    forall b. Coercion -> Expr b
    Coercion (HasDebugCallStack => Subst -> Coercion -> Coercion
    Subst -> Coercion -> Coercion
    substCo (CSEnv -> Subst
    csEnvSubst CSEnv
    env) Coercion
    c)
    cseExpr CSEnv
    _   (Lit Literal
    lit)             = Literal -> Expr Var
    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)             = Expr Var -> Expr Var -> Expr Var
    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)            = CoreTickish -> Expr Var -> Expr Var
    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)           = Expr Var -> Coercion -> Expr Var
    forall b. Expr b -> Coercion -> Expr b
    Cast (CSEnv -> Expr Var -> Expr Var
    tryForCSE CSEnv
    env Expr Var
    e) (HasDebugCallStack => Subst -> Coercion -> Coercion
    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 Var -> Expr Var -> Expr Var
    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 CoreBind -> Expr Var -> Expr Var
    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
      = Expr Var -> Var -> Type -> [OutAlt] -> Expr Var
    forall b. Expr b -> b -> Type -> [Alt b] -> Expr b
    Case Expr Var
    scrut1 Var
    bndr3 Type
    ty' ([OutAlt] -> Expr Var) -> [OutAlt] -> Expr Var
    forall a b. (a -> b) -> a -> b
    $
        [OutAlt] -> [OutAlt]
    combineAlts ((OutAlt -> OutAlt) -> [OutAlt] -> [OutAlt]
    forall a b. (a -> b) -> [a] -> [b]
    map OutAlt -> OutAlt
    cse_alt [OutAlt]
    alts)
      where
        ty' :: Type
    ty' = Subst -> Type -> Type
    substTyUnchecked (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 = HasCallStack => Type -> [Type]
    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)
            = AltCon -> [Var] -> Expr Var -> OutAlt
    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)
            = AltCon -> [Var] -> Expr Var -> OutAlt
    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 :: [OutAlt] -> [OutAlt]
    -- See Note [Combine case alternatives]
    combineAlts :: [OutAlt] -> [OutAlt]
    combineAlts [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 = (OutAlt -> Bool) -> [OutAlt] -> [OutAlt]
    forall a. (a -> Bool) -> [a] -> [a]
    filterOut (Expr Var -> OutAlt -> Bool
    identical_alt Expr Var
    rhs1) [OutAlt]
    rest_alts
      , Bool -> Bool
    not ([OutAlt] -> [OutAlt] -> Bool
    forall a b. [a] -> [b] -> Bool
    equalLength [OutAlt]
    rest_alts [OutAlt]
    filtered_alts)
      = Bool -> SDoc -> [OutAlt] -> [OutAlt]
    forall a. HasCallStack => Bool -> SDoc -> a -> a
    assertPpr ([Var] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [Var]
    bndrs1) ([OutAlt] -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr [OutAlt]
    alts) ([OutAlt] -> [OutAlt]) -> [OutAlt] -> [OutAlt]
    forall a b. (a -> b) -> a -> b
    $
        AltCon -> [Var] -> Expr Var -> OutAlt
    forall b. AltCon -> [b] -> Expr b -> Alt b
    Alt AltCon
    DEFAULT [] Expr Var
    rhs1 OutAlt -> [OutAlt] -> [OutAlt]
    forall a. a -> [a] -> [a]
    : [OutAlt]
    filtered_alts

      | Bool
    otherwise
      = [OutAlt]
    alts
      where

        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 []
          = (Maybe OutAlt
    forall a. Maybe a
    Nothing, [])
        find_bndr_free_alt (alt :: OutAlt
    alt@(Alt AltCon
    _ [Var]
    bndrs Expr Var
    _) : [OutAlt]
    alts)
          | [Var] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [Var]
    bndrs = (OutAlt -> Maybe OutAlt
    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
    altOutAlt -> [OutAlt] -> [OutAlt]
    forall a. a -> [a] -> [a]
    :[OutAlt]
    alts)

        identical_alt :: Expr Var -> OutAlt -> Bool
    identical_alt Expr Var
    rhs1 (Alt AltCon
    _ [Var]
    _ Expr Var
    rhs) = Expr Var -> Expr Var -> Bool
    eqCoreExpr 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 eqCoreExpr.  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 = CoreMap (Expr Var)
    forall a. CoreMap a
    emptyCoreMap, cs_rec_map :: CoreMap (Expr Var)
    cs_rec_map = CoreMap (Expr Var)
    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
      = CoreMap (Expr Var) -> Expr Var -> Maybe (Expr Var)
    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 = extendCoreMap (cs_map cse) sexpr triv_expr }
      where
        sexpr :: Expr Var
    sexpr = (CoreTickish -> Bool) -> Expr Var -> Expr Var
    forall b. (CoreTickish -> Bool) -> Expr b -> Expr b
    stripTicksE CoreTickish -> Bool
    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 = extendCoreMap (cs_rec_map cse) (Lam bndr expr) 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
      = CoreMap (Expr Var) -> Expr Var -> Maybe (Expr Var)
    forall a. CoreMap a -> Expr Var -> Maybe a
    lookupCoreMap CoreMap (Expr Var)
    csmap (Var -> Expr Var -> Expr Var
    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
    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 = extendSubst (cs_subst cse) x rhs }

    -- | Add clones to the substitution to deal with shadowing.  See
    -- Note [Shadowing in CSE] 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 = 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 = sub' }, [Var]
    vs')
                    where
                      (Subst
    sub', [Var]
    vs') = Subst -> [Var] -> (Subst, [Var])
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Var -> (Subst, f Var)
    substBndrs (CSEnv -> Subst
    cs_subst CSEnv
    cse) [Var]
    vs

    addRecBinders :: Traversable f => CSEnv -> f Id -> (CSEnv, f Id)
    addRecBinders :: forall (f :: * -> *).
    Traversable f =>
    CSEnv -> f Var -> (CSEnv, f Var)
    addRecBinders = \ CSEnv
    cse f Var
    vs ->
        let (Subst
    sub', f Var
    vs') = Subst -> f Var -> (Subst, f Var)
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Var -> (Subst, f Var)
    substRecBndrs (CSEnv -> Subst
    cs_subst CSEnv
    cse) f Var
    vs
        in (CSEnv
    cse { cs_subst = sub' }, f Var
    vs')
    {-# INLINE addRecBinders #-}