[GHC] #10124: Simple case analyses generate too many branches

28 Feb 2015

      #10124: Simple case analyses generate too many branches
-------------------------------------+-------------------------------------
              Reporter:  bgamari     |             Owner:
                  Type:  bug         |            Status:  new
              Priority:  normal      |         Milestone:
             Component:  Compiler    |           Version:  7.8.4
              Keywords:              |  Operating System:  Unknown/Multiple
          Architecture:              |   Type of failure:  None/Unknown
  Unknown/Multiple                   |        Blocked By:
             Test Case:              |   Related Tickets:
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
 Take the following example,
 {{{#!hs
 f :: Int -> Bool
 f a = case a of
         1  -> True
         5  -> True
         8  -> True
         9  -> True
         11 -> True
         19 -> True
         _  -> False
 {-# NOINLINE f #-}

 main = print $ f 8
 }}}

 This gets lowered to the following Core (by GHC 7.8),

 {{{#!hs
 f
 f =
   \ a_s3EH ->
     case a_s3EH of _ { I# ds_s3EJ ->
     case ds_s3EJ of _ {
       __DEFAULT -> False;
       1 -> True;
       5 -> True;
       8 -> True;
       9 -> True;
       11 -> True;
       19 -> True
     }
     }
 }}}

 I have expected GHC to lower this into a nice string of logical
 operations, with perhaps a couple of branches at the end to determine the
 result.

 Unfortunately, this is not what happens. Instead the C-- is a sea of
 branches,

 {{{
        c3F7:
            _s3EK::I64 = I64[R1 + 7];
            if (%MO_S_Lt_W64(_s3EK::I64, 9)) goto c3Fz; else goto c3FA;
        c3Fz:
            if (%MO_S_Lt_W64(_s3EK::I64, 5)) goto c3Fq; else goto c3Fr;
        c3Fq:
            if (_s3EK::I64 != 1) goto c3Ff; else goto c3Fg;
        c3Fr:
            if (%MO_S_Lt_W64(_s3EK::I64, 8)) goto c3Fn; else goto c3Fo;
        c3Fn:
            if (_s3EK::I64 != 5) goto c3Ff; else goto c3Fg;
        c3Fo:
            if (_s3EK::I64 != 8) goto c3Ff; else goto c3Fg;
        c3FA:
            if (%MO_S_Lt_W64(_s3EK::I64, 11)) goto c3Fw; else goto c3Fx;
        c3Fw:
            if (_s3EK::I64 != 9) goto c3Ff; else goto c3Fg;
        c3Fx:
            if (%MO_S_Lt_W64(_s3EK::I64, 19)) goto c3Ft; else goto c3Fu;
        c3Ft:
            if (_s3EK::I64 != 11) goto c3Ff; else goto c3Fg;
        c3Fu:
            if (_s3EK::I64 != 19) goto c3Ff; else goto c3Fg;
        c3Ff:
            R1 = False_closure+1;
            Sp = Sp + 8;
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
        c3Fg:
            R1 = True_closure+2;
            Sp = Sp + 8;
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
 ...
 }}}

 Which gets turned into the branchy assembler that you would expect. To my
 surprise even the LLVM backend isn't able to bring this back into a
 branchless form.

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