[GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

7 Jan 2018

      #14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
           Reporter:  AndreasK       |             Owner:  (none)
               Type:  task           |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.2.2
  (CodeGen)                          |
           Keywords:  Codegen, CMM,  |  Operating System:  Unknown/Multiple
  Patterns, Pattern Matching         |
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 For a pattern like:
 {{{
 f_test :: Int#->Int#
 f_test a = case a of
     1# -> 33#
     7# -> 34#
      _ -> -1#
 }}}

 GHC currently generates code that works best if the default branch is
 taken most often.

 Pseudo-Code
 {{{
 if (a >= 8)
     return -1;
 else {
     if (a < 7) {
         if(a != 1)
             return -1;
         else
             return 33;
     }
     else
         return 34;
 }
 }}}

 CMM:
 {{{
        c1cr: // global
            if (%MO_S_Ge_W64(R2, 8)) goto c1co; else goto u1cu;
        u1cu: // global
            if (%MO_S_Lt_W64(R2, 7)) goto u1cv; else goto c1cq;
        u1cv: // global
            if (R2 != 1) goto c1co; else goto c1cp;
        c1co: // global
            R1 = (-1);
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
        c1cp: // global
            R1 = 33;
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
        c1cq: // global
            R1 = 34;
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
      }

 }}}

 Wouldn't the following be better?
 {{{
 if(a == 1)
     return 33
 else if(a == 7)
     return 34
 else
     return -1
 }}}

 I would expect that to
 * Improve the cases:
   * a = 1
   * a < 7
 * Be the same for:
   * a = 7
 * Be worse for
   * a > 8

 This would be especially nice for the cases where the default branch is
 raising a pattern match exception.
 Which is a code path I wouldn't expect to be taken often nor be very
 performance sensitive.

 Even if we keep the current logic there is room for improvement.
 GHC currently creates the following assembly:

 {{{
 _c1cr:
         cmpq $8,%r14
         jge _c1co
 _u1cu:
         cmpq $7,%r14
         jl _u1cv
 _c1cq:
         movl $34,%ebx
         jmp *(%rbp)
 _u1cv:
         cmpq $1,%r14
         jne _c1co
 _c1cp:
         movl $33,%ebx
         jmp *(%rbp)
 _c1co:
         movq $-1,%rbx
         jmp *(%rbp)
 }}}

 It would be nice if we could remove one comparison at least.
 {{{
 _c1cr:
         cmpq $7,%r14
         jg _c1co
 _u1cu:
         ;No longer neccesary cmpq $7,%r14
         jl _u1cv
 _c1cq:
         movl $34,%ebx
         jmp *(%rbp)
 _u1cv:
         cmpq $1,%r14
         jne _c1co
 _c1cp:
         movl $33,%ebx
         jmp *(%rbp)
 _c1co:
         movq $-1,%rbx
         jmp *(%rbp)
 }}}

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