Simple case analyses generate too many branches
Take the following example,
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),
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.
Trac metadata
Trac field | Value |
---|---|
Version | 7.8.4 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |