[LLVMbugs] [Bug 18348] New: Switch with large ranges may generate huge jump tables

[bugzilla-daemon at llvm.org]

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

            Bug ID: 18348
           Summary: Switch with large ranges may generate huge jump tables
           Product: libraries
           Version: 3.3
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: jn at sirrida.de
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

When compiling with clang -O3 -S the following program is implemented with a
huge jump table where a decision tree would have been much more appropriate:

int main(int argc, char **argv) {
  switch (argc) {
    case 5000 ... 5063: return 100;
    case 5100 ... 5163: return 200;
    case 5200 ... 5263: return 300;
    case 5300 ... 5364: return 400;
    case 5400 ... 5463: return 500;
    case 5500 ... 5563: return 600;
    default: return -1;
    }
  }

As far as I can see the jump table covers the whole range 5000 ... 5563.
All jump table covers only ranges with up to 64 elements; all larger ranges are
tested afterwards, i.e. the range 5300 ... 5364 (containing 65 elements) is
tested later.

I consider the resulting jump table as being inadequately large (564 entries
for 5 ranges, this amounts to 4512 bytes on a 64 bit system). The special case
for ranges with more than 64 elements seems to artificial as also discussed in
bug #1255.

Instead of testing the density of the jump table it probably would be better to
compare the switch label range with the number of conditional statements of the
competing decision tree - this can easily be changed in
SelectionDAGBuilder::handleJTSwitchCase
(lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp).

As far as I can see this quirk is also present in trunk.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20131231/26c5e60a/attachment.html>