[LLVMbugs] [Bug 926] NEW: sdisel switch lowering can be improved

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=926

           Summary: sdisel switch lowering can be improved
           Product: libraries
           Version: 1.8
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Common Code Generator Code
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: sabre at nondot.org


First, the trivial thing: a switch lowered to a series of conditional branches always results in an explicit 
"fallthrough" uncond branch to the next block from the initial block.  This is probably a minor book-
keeping bug:

        cmpl $6, %eax
        jl LBB1_20      #entry
***   jmp LBB1_15     #entry
LBB1_15:        #entry


More significantly, we should change the heuristic of the switch lowering a bit.  Specifically, right now, 
at the top level, we decide whether to lower the switch to a series of branches or to a table jump.  I 
think we should always go through the "branch sequence" code path, but make it a bit more 
sophisticated.

In particular, the worklist should start out with a single record with all the case ranges on it.  Each time 
through the loop, a range is popped off.  If the range satisfies the conditions for a tbljmp, emit one.  
Otherwise, split in half and emit a branch to choose between the two.

This would allow us to handle switches with dense portions that are spread out (e.g. 0...100  + 
2000...2100) as two separate tbljump pieces.

This would also make it more natural to plug in other heuristics.  For example, perlbmk has a switch 
that looks like this:
        switch uint %tmp158, label %bb336 [
                 uint 0, label %bb338
                 uint 1, label %bb338
                 uint 2, label %bb338
                 uint 3, label %bb338
                 uint 4, label %bb338
                 uint 5, label %bb338
                 uint 6, label %bb338
                 uint 7, label %bb
                 uint 8, label %bb338
                 uint 9, label %bb322
                 uint 10, label %bb324
                 uint 11, label %bb326
                 uint 12, label %bb328
                 uint 13, label %bb330
                 uint 14, label %bb332
                 uint 15, label %bb334
...

When emitted as a branch tree, the leaves end up doing lots of work to discriminate between the 0->6 
cases, when they all go to the same place.

Another nice xform is to do the "shift/and" technique for switches.

-Chris



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.