[GHC] #14737: Improve performance of Simplify.simplCast

[GHC]

#14737: Improve performance of Simplify.simplCast
-------------------------------------+-------------------------------------
        Reporter:  tdammers          |                Owner:  (none)
            Type:  bug               |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #11735 #14683     |  Differential Rev(s):  Phab:D4385
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 >  Interestingly, the coercion optimizer will not work on InstCo ... (Refl
 ...).

 At first I disagreed.  The first equation for `opt_co4` is this
 {{{
 opt_co4 env sym rep r (InstCo co1 arg)
     -- forall over type...
   | Just (tv, kind_co, co_body) <- splitForAllCo_maybe co1
   = opt_co4_wrap (extendLiftingContext env tv
                     (arg' `mkCoherenceRightCo` mkSymCo kind_co))
                  sym rep r co_body
 }}}
 If `arg` is `Refl` then `kind_co` is also `Refl`, so `mkCoherenceRightCo`
 is a no-op.  So the argument to `extendLiftingContext` is `Refl`; and it
 looks like this
 {{{
 extendLiftingContext (LC subst env) tv (Refl _ ty)
   = LC (extendTvSubst subst tv ty) env
 }}}
 That is, it just extends the `TvSubst`.  And that looks exactly what
 happens in `mkInstCo`.  So I think that `opc_co4` does in fact do exactly
 the same.  But perhaps spotting a `Refl` argument would be a bit more
 direct?

 Meanwhile
 * I agree that `kind_co` should be substituted.  But how?  By calling
 `ope_co4` on it?  Or `opt_co3`?  I don't understand the hierarchy of
 `opt_co` functions.
 * I find that code for `extendLiftingContext` hard to grok.  In the `Refl`
 case we extend the `TvSubst`; otherwise we extend the `LiftCoEnv`.   Very
 mysterious.  I looked at it a bit, but got lost in the deeply cryptic
 `liftEnvSubst`.

 Returning to the main event, however, I agree we won't get an efficient
 substitution, because in the example in comment:13 the
 `splitForAllCo_maybe` will fail -- because `co1` is another `InstCo`!
 What we need, as usual, is to accumulate those arguments in a list; then
 in the middle we should find a stack of `ForAllCo`s; and we can extend the
 substitution as we pair them up.  Would that be right?   Perhaps that's
 why Tobias saw no improvement -- though I'm a bit surprised that it got a
 lot worse.


 >  opt_co4 uses splitForAllCo_maybe, which doesn't look for Refls. Perhaps
 it should.

 You mean that `Refl (forall a. ty)` can be regarded as a form of
 `ForAllCo`?  Especially since `mkForAllCo` goes to some trouble to build a
 `Refl` if it can.  So surely yes, `splitForAllCo_maybe` should split a
 `Refl (forall a.ty)`.

 > The only way InstCos can come into being is in the coercion optimizer.
 There is no call to mkInstCo beyond it. So perhaps we can take that into
 account when designing these functions.

 Not true: `pushCoTyArg` calls `mkInstCo`; that's where this entire
 conversation started!  And I don't know what it means to "take it into
 account"

 Things to do
 * Fix the missing substitution in `opt_co4`
 * Fix `splitForAllCo_maybe`
 * Fix `opt_co4` to behave well on deeply nsted `InstCos`
 Might you do these -- you are more likely to get them right than me.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14737#comment:16>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler