<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>