<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 - LoopIdiomRecognize: Overflow in ctlz shifting loop"
href="https://bugs.llvm.org/show_bug.cgi?id=51669">51669</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>LoopIdiomRecognize: Overflow in ctlz shifting loop
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>All
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Keywords</th>
<td>miscompilation
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Loop Optimizer
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>nunoplopes@sapo.pt
</td>
</tr>
<tr>
<th>CC</th>
<td>lebedev.ri@gmail.com, llvm-bugs@lists.llvm.org, zhuhan7737@gmail.com
</td>
</tr></table>
<p>
<div>
<pre>Test: Transforms/LoopIdiom/X86/arithmetic-right-shift-until-zero.ll
LoopIdiom creates expressions that overflow and produce incorrect result.
e.g. this instruction:
add nsw i8 %val.numactivebits, %0
overflows and yields poison. Even removing nsw doesn't fix the issue; see
counterexample below.
----------------------------------------
define i8 @p0(i8 %val, i8 %start, i8 %extraoffset) {
%entry:
br label %loop
%loop:
%iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
%nbits = add nsw i8 %iv, %extraoffset
%val.shifted = ashr i8 %val, %nbits
%val.shifted.iszero = icmp eq i8 %val.shifted, 0
%iv.next = add i8 %iv, 1
call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1
%val.shifted.iszero, i8 %iv.next)
br i1 %val.shifted.iszero, label %end, label %loop
%end:
%iv.res = phi i8 [ %iv, %loop ]
%nbits.res = phi i8 [ %nbits, %loop ]
%val.shifted.res = phi i8 [ %val.shifted, %loop ]
%val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
%iv.next.res = phi i8 [ %iv.next, %loop ]
call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1
%val.shifted.iszero.res, i8 %iv.next.res)
ret i8 %iv.res
}
=>
define i8 @p0(i8 %val, i8 %start, i8 %extraoffset) {
%entry:
%val.numleadingzeros = ctlz i8 %val, 0
%val.numactivebits = sub nsw nuw i8 8, %val.numleadingzeros
%0 = sub i8 0, %extraoffset
%val.numactivebits.offset = add i8 %val.numactivebits, %0
%iv.final = smax i8 %val.numactivebits.offset, %start
%loop.backedgetakencount = sub nsw i8 %iv.final, %start
%loop.tripcount = add nsw nuw i8 %loop.backedgetakencount, 1
br label %loop
%loop:
%loop.iv = phi i8 [ 0, %entry ], [ %loop.iv.next, %loop ]
%loop.iv.next = add nsw nuw i8 %loop.iv, 1
%loop.ivcheck = icmp eq i8 %loop.iv.next, %loop.tripcount
%iv = add nsw i8 %loop.iv, %start
%nbits = add nsw i8 %iv, %extraoffset
%val.shifted = ashr i8 %val, %nbits
%iv.next = add i8 %iv, 1
call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %loop.ivcheck,
i8 %iv.next)
br i1 %loop.ivcheck, label %end, label %loop
%end:
%iv.res = phi i8 [ %iv.final, %loop ]
%nbits.res = phi i8 [ %nbits, %loop ]
%val.shifted.res = phi i8 [ %val.shifted, %loop ]
%val.shifted.iszero.res = phi i1 [ %loop.ivcheck, %loop ]
%iv.next.res = phi i8 [ %iv.next, %loop ]
call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1
%val.shifted.iszero.res, i8 %iv.next.res)
ret i8 %iv.res
}
Transformation doesn't verify!
ERROR: Source is more defined than target
Example:
i8 %val = #x80 (128, -128)
i8 %start = #x78 (120)
i8 %extraoffset = #x88 (136, -120)
Source:
i8 %iv = #x78 (120)
i8 %nbits = #x00 (0)
i8 %val.shifted = #x80 (128, -128)
i1 %val.shifted.iszero = #x0 (0)
i8 %iv.next = #x79 (121)
SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 > size: 0 align: 1 alloc type: 0
Block 1 > size: 0 align: 1
Target:
i8 %val.numleadingzeros = #x00 (0)
i8 %val.numactivebits = #x08 (8)
i8 %0 = #x78 (120)
i8 %val.numactivebits.offset = #x80 (128, -128)
i8 %iv.final = #x78 (120)
i8 %loop.backedgetakencount = #x00 (0)
i8 %loop.tripcount = #x01 (1)
i8 %loop.iv = #x00 (0)
i8 %loop.iv.next = #x01 (1)
i1 %loop.ivcheck = #x1 (1)
i8 %iv = #x78 (120)
i8 %nbits = #x00 (0)
i8 %val.shifted = #x80 (128, -128)
i8 %iv.next = #x79 (121)
i8 %iv.res = #x78 (120)
i8 %nbits.res = #x00 (0)
i8 %val.shifted.res = #x80 (128, -128)
i1 %val.shifted.iszero.res = #x1 (1)
i8 %iv.next.res = #x79 (121)</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>