[GHC] #10606: avoid redundant stores to the stack when examining already-tagged data

[GHC]

#10606: avoid redundant stores to the stack when examining already-tagged data
-------------------------------------+-------------------------------------
              Reporter:  rwbarton    |             Owner:
                  Type:  feature     |            Status:  new
  request                            |         Milestone:
              Priority:  normal      |           Version:  7.11
             Component:  Compiler    |  Operating System:  Unknown/Multiple
  (CodeGen)                          |   Type of failure:  None/Unknown
              Keywords:              |        Blocked By:
          Architecture:              |   Related Tickets:
  Unknown/Multiple                   |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
 GHC compiles a function that performs case analysis on a value of an ADT
 like
 {{{
 bool :: a -> a -> Bool -> a
 bool f t b = case b of
   False -> f
   True  -> t
 }}}
 to Cmm of the form
 {{{
      {offset
        cwV:
            if ((Sp + -24) < SpLim) goto cwW; else goto cwX;
        cwW:
            R4 = R4;
            R3 = R3;
            R2 = R2;
            R1 = Bool.bool_closure;
            call (stg_gc_fun)(R4, R3, R2, R1) args: 8, res: 0, upd: 8;
        cwX:
            I64[Sp - 24] = cwL;     -- (*)
            R1 = R4;
            P64[Sp - 16] = R2;      -- (†1)
            P64[Sp - 8] = R3;       -- (†2)
            Sp = Sp - 24;           -- (‡)
            if (R1 & 7 != 0) goto cwL; else goto cwM;
        cwM:
            call (I64[R1])(R1) returns to cwL, args: 8, res: 8, upd: 8;
        cwL:
            if (R1 & 7 >= 2) goto cwT; else goto cwU;
        cwT:
            R1 = P64[Sp + 16];
            Sp = Sp + 24;
            call stg_ap_0_fast(R1) args: 8, res: 0, upd: 8;
        cwU:
            R1 = P64[Sp + 8];
            Sp = Sp + 24;
            call stg_ap_0_fast(R1) args: 8, res: 0, upd: 8;
      }
 }}}
 Statement (*) stores a return address for the evaluation of `b` to return
 to, and statements (†1), (†2) save local variables that are live in case
 alternatives, since they cannot be held in registers across the evaluation
 of `b`. But in the event that `b` is already evaluated and represented by
 a tagged pointer, all these stores are unnecessary: the return address
 written by (*) is simply dead, and the values saved in (†1), (†2) are
 still available in whatever locations they were copied to the stack from.

 In many cases the data we examine is mostly tagged, and while the active
 part of the stack is likely to be in L1 cache, the cost of these stores
 and reads is probably still positive (barring secondary effects from
 changes to pipelining, branch prediction, and so on).

 In this case we could certainly move the return address store (*) into
 block `cwM`, and possibly move the local variable stores (†1), (†2) into
 `cwM` as well, though it's then not clear to me how to recover the values
 in the alternatives (does Cmm have something like phi nodes?) I don't
 propose to move the statement (‡), as arithmetic on registers is
 essentially free anyways.

 I tried implementing the part of this pertaining to the return address (*)
 and ran into two complications.

 * For some reason, when I moved the return address store (*) into the
 "data is not tagged" branch in the Stg->Cmm translation, this also
 resulted in both the local variable stores (†1), (†2) and the update to Sp
 (‡) being sunk into both branches of the "is the data tagged" conditional
 at some point in the Cmm optimization pipeline. This was useless since
 they couldn't be pushed further past the branch on the returned tag value,
 so the result was enlarged code size that outweighed the savings of
 avoiding a single store. I didn't investigate exactly why this sinking was
 dependent on the location of the store (*), but this should be fixable.

 * There may be heap checks in the alternatives. In that case, the code
 generator currently cleverly reuses the stack frame and info table set up
 for the evaluation of `b` in the heap failure branches. If we move some of
 the stores (*), (†1), (†2) into the evaluation branch `cwM`, then we
 either have to duplicate them in heap failure branches, or set up a new
 stack frame and info table, or do some other clever thing. Or in the worst
 case, only do this optimization when performing the heap check before the
 case (which may then become slightly more attractive).

 I'm attaching the current version of my patch mainly for my own future
 reference; it seems to produce correct, but larger and marginally slower
 code, I believe for the reasons described above.

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