<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 --- - Switch with large ranges may generate huge jump tables"
href="http://llvm.org/bugs/show_bug.cgi?id=18348">18348</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Switch with large ranges may generate huge jump tables
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>3.3
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</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>jn@sirrida.de
</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>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
<a class="bz_bug_link
bz_status_NEW "
title="NEW --- - Should enhance LLVM switch instruction to take case ranges"
href="show_bug.cgi?id=1255">bug #1255</a>.
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.</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>