<html>
<head>
<base href="http://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - LLVM's pivot element selection is bad for sparse switch statements"
href="http://llvm.org/bugs/show_bug.cgi?id=22262">22262</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>LLVM's pivot element selection is bad for sparse switch statements
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Common Code Generator Code
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>djasper@google.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>