[LLVMbugs] [Bug 22262] New: LLVM's pivot element selection is bad for sparse switch statements

[bugzilla-daemon at llvm.org]

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

            Bug ID: 22262
           Summary: LLVM's pivot element selection is bad for sparse
                    switch statements
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: djasper at google.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Example:

void f(int v) {
  switch (v) {
    case 10: a(); break;
    case 20: b(); break;
    case 30: c(); break;
    case 40: d(); break;
    case 50: e(); break;
    case 60: f(); break;
    default: h();
  }
}

in lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp, this correctly calls
handleBTSplitSwitchCase in order to create a binary decision tree for the
switch statement. However, the heuristic for selecting the pivot element tries
to maximize the sum of the density of the left and the right half. This makes
sense in order to split at "holes" leading to increased usage of jump tables
later. However, if the density is uniformly distribute such as in the example,
this will always pick a single element on the left or on the right as the
density of the single element is 1 and far greater than any other density.
Thus, the "binary tree" falls back to a linear check of all values.

In order to solve this, we can
a) Compute beforehand that we won't find any subrange to use a jump table for.
b) Precompute the ideal ranges for jump tables. This might actually turn out to
find jump tables in cases where the current heuristic doesn't find them.

-- 
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/20150119/2d4640fb/attachment.html>