Opened 5 years ago

Closed 5 years ago

Last modified 4 years ago

#10129 closed task (fixed)

emitCmmLitSwitch could be better

Reported by: nomeata Owned by:
Priority: normal Milestone: 8.0.1
Component: Compiler (CodeGen) Version: 7.8.4
Keywords: Cc: simonmar, bgamari
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D693
Wiki Page:

Description

This is a spin off #10124. While looking at the code generated for

f :: Int -> Bool
f a = case a of
        1  -> True
        2  -> True
        3  -> True
        4  -> True
        8  -> True
        9  -> True
        11 -> True
        19 -> True
        _  -> False

I noticed this Cmm:

       c2tI:
           if (%MO_S_Lt_W64(_s2sJ::I64, 3)) goto c2tw; else goto c2tx;
       c2tw:
           if (%MO_S_Lt_W64(_s2sJ::I64, 2)) goto c2tq; else goto c2tr;
       c2tq:
           if (_s2sJ::I64 != 1) goto c2tg; else goto c2th;
       c2tr:
           if (_s2sJ::I64 != 2) goto c2tg; else goto c2th;

Note that when c2tr is reached, we know 2 ≤ _s2sJ < 3, so _s2sJ already is 2, and this check is redundant.

emitCmmLitSwitch does not take that into account, probably because it also needs to work for floats.

I wonder if it isn’t a bit shady to use an if-then-else tree for floats. Maybe for float types, a sequence of equality tests is more suitable. For all other cases, the code generator could make use of "2 ≤ x < 3 ⇒ x = 2" and skip one check.

Change History (7)

comment:1 Changed 5 years ago by nomeata

Differential Rev(s): Phab:D693
Status: newpatch

comment:2 Changed 5 years ago by bgamari

Cc: bgamari added
Type of failure: None/UnknownRuntime performance bug

comment:3 Changed 5 years ago by Joachim Breitner <mail@…>

In c3eee14d31585445d4a7eff5b6c69a815b911059/ghc:

Improve if-then-else tree for cases on literal values

Previously, in the branch of the if-then-else tree, it would emit a
final check if the scrut matches the alternative, even if earlier
comparisons alread imply this equality. By keeping track of the bounds
we can skip this check. Of course this is only sound for integer types.
This closes #10129.
Differential Revision: https://phabricator.haskell.org/D693

comment:4 Changed 5 years ago by nomeata

Resolution: fixed
Status: patchclosed

This bit is done. It would still be nice to unify emitCmmLitSwitch with emitSwitch, but maybe some other day.

comment:5 Changed 5 years ago by simonpj

Regression test? Maybe too awkward...

comment:6 Changed 5 years ago by nomeata

I thought about this, but I’m really not sure how to do it. The best thing I could think of would be to grep on the output of -ddump-cmm, but that seems too fragile.

comment:7 Changed 4 years ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.