<html>
<head>
<base href="https://bugs.llvm.org/">
</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 - Codegen creates an extra bench in a binary search"
href="https://bugs.llvm.org/show_bug.cgi?id=37144">37144</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Codegen creates an extra bench in a binary search
</td>
</tr>
<tr>
<th>Product</th>
<td>new-bugs
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</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>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>new bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>rafael@espindo.la
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org, ruiu@google.com
</td>
</tr></table>
<p>
<div>
<pre>lld has a binary search function written as:
--------------------------------------------------
while (Size != 1) {
size_t H = Size / 2;
const It MI = First + H;
Size -= H;
First = Comp(Value, *MI) ? First : First + H;
}
return Comp(Value, *First) ? First : First + 1;
--------------------------------------------------
The objective is to avoid branch misprediction. The body has no branches and
the loop has no early exits, so it is very predictable.
Everything is fine in the IR. The loop is a single BB and a select is used:
%12 = phi i32* [ %0, %8 ], [ %19, %10 ]
...
%14 = getelementptr inbounds i32, i32* %12, i64 %13
...
%18 = icmp ugt i64 %17, %2
%19 = select i1 %18, i32* %12, i32* %14
But codegen decides to use branches:
cmpq %rdx, %rcx
ja .LBB81_4
# %bb.3: # in Loop: Header=BB81_2 Depth=1
leaq (%rdi,%rax,4), %rdi
.LBB81_4: # in Loop: Header=BB81_2 Depth=1
cmpq $1, %rsi
jne .LBB81_2
Which causes massive amounts of branch misprediction. LLD's largest allocation
is a hash table that exists just to avoid using the binary search as often
since it is so expensive.
GCC gets this right. In a lld version without the extra hash table it looks
like fixing this bug would result in a 12% speedup of the entire link is some
testcases.</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>