<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 --- - Optimization: Failure to recognize right shift will result in either 0 or 1."
href="http://llvm.org/bugs/show_bug.cgi?id=15809">15809</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Optimization: Failure to recognize right shift will result in either 0 or 1.
</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>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>Scalar Optimizations
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>silvas@purdue.edu
</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>Created <span class=""><a href="attachment.cgi?id=10397" name="attach_10397" title="test_bitmap.c">attachment 10397</a> <a href="attachment.cgi?id=10397&action=edit" title="test_bitmap.c">[details]</a></span>
test_bitmap.c
(all of this is with clang -O2 at r179948)
The code for `test_bitmap_ternary` is 5 bytes smaller than `test_bitmap_shift`,
2 instructions shorter, and avoids 2 non-immediate shifts (possibly just 1 on
architectures that don't have something like x86 BT). I think the issue is a
failure to recognize that there is only one set bit, so shifting back by the
same amount gives exactly either 0 or 1.
int test_bitmap_ternary(int shift, int bitmap)
{
return ((1 << shift) & bitmap) ? 1 : 0;
}
int test_bitmap_shift(int shift, int bitmap)
{
return ((1 << shift) & bitmap) >> shift;
}
The problem is exacerbated with some more decoration (adding !! doesn't affect
the codegen for `test_bitmap_ternary`):
int test_bitmap_shift_notnot(int shift, int bitmap)
{
return !!(((1 << shift) & bitmap) >> shift);
}
define i32 @test_bitmap_ternary(i32 %shift, i32 %bitmap) #0 {
%1 = shl i32 1, %shift
%2 = and i32 %1, %bitmap
%3 = icmp ne i32 %2, 0
%4 = zext i1 %3 to i32
ret i32 %4
}
define i32 @test_bitmap_shift(i32 %shift, i32 %bitmap) #0 {
%1 = shl i32 1, %shift
%2 = and i32 %1, %bitmap
%3 = ashr i32 %2, %shift
ret i32 %3
}
define i32 @test_bitmap_shift_notnot(i32 %shift, i32 %bitmap) #0 {
%1 = shl i32 1, %shift
%2 = and i32 %1, %bitmap
%3 = ashr i32 %2, %shift
%4 = icmp ne i32 %3, 0
%5 = zext i1 %4 to i32
ret i32 %5
}
0000000000000050 <test_bitmap_ternary>:
50: 0f a3 fe bt %edi,%esi
53: 19 c0 sbb %eax,%eax
55: 83 e0 01 and $0x1,%eax
58: c3 retq
0000000000000060 <test_bitmap_shift>:
60: 89 f9 mov %edi,%ecx
62: b8 01 00 00 00 mov $0x1,%eax
67: d3 e0 shl %cl,%eax
69: 21 f0 and %esi,%eax
6b: d3 f8 sar %cl,%eax
6d: c3 retq
0000000000000060 <test_bitmap_shift_notnot>:
60: 89 f9 mov %edi,%ecx
62: b8 01 00 00 00 mov $0x1,%eax
67: d3 e0 shl %cl,%eax
69: 21 f0 and %esi,%eax
6b: d3 f8 sar %cl,%eax
6d: 85 c0 test %eax,%eax
6f: 0f 95 c0 setne %al
72: 0f b6 c0 movzbl %al,%eax
75: c3 retq</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>