<html>
<head>
<base href="https://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 --- - Loop unswtich and GVN interact badly and miscompile"
href="https://llvm.org/bugs/show_bug.cgi?id=31652">31652</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Loop unswtich and GVN interact badly and miscompile
</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>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>nunoplopes@sapo.pt
</td>
</tr>
<tr>
<th>CC</th>
<td>david.majnemer@gmail.com, davide@freebsd.org, dberlin@dberlin.org, gil.hur@sf.snu.ac.kr, juneyoung.lee@sf.snu.ac.kr, llvm-bugs@lists.llvm.org, regehr@cs.utah.edu, sanjoy@playingwithpointers.com
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=17845" name="attach_17845" title="Reduced IR test case">attachment 17845</a> <a href="attachment.cgi?id=17845&action=edit" title="Reduced IR test case">[details]</a></span>
Reduced IR test case
Loop unswitch and GVN when taken together can miscompile code due to
disagreeing semantics of branch on undef.
In our opinion it's loop unswitch that is incorrect.
Test case in C:
static volatile int always_false = 0;
void maybe_init(int *p) {}
int f(int limit0) {
int maybe_undef_loc;
maybe_init(&maybe_undef_loc);
int limit = limit0;
int total = 0;
for (int i = 0; i < limit; i++) {
total++;
if (always_false) {
if (maybe_undef_loc != (limit0 + 10)) {
total++;
}
}
limit = limit0 + 10;
}
return total;
}
int printf(const char *, ...);
int main(int argc, char **argv) {
printf("f(10) = %d\n", f(10));
return 0;
}
I believe this test case has no UB even at C level. It should print "f(10) =
20".
I've attached a reduced IR test case.
Running LICM, the comparison of maybe_undef_loc gets hoisted:
$ opt -S bug.ll -loop-rotate -licm
...
loop.body.lr.ph:
%undef_loc = load i32, i32* %maybe_undef_loc, align 4
%add = add nsw i32 %limit0, 10
%cmp3 = icmp ne i32 %undef_loc, %add
%limit2 = add nsw i32 %limit0, 10
br label %loop.body
...
This is still ok. But then adding loop unswitch:
$ opt -S bug.ll -loop-rotate -licm -loop-unswitch
...
loop.body.lr.ph:
%undef_loc = load i32, i32* %maybe_undef_loc, align 4
%add = add nsw i32 %limit0, 10
%cmp3 = icmp ne i32 %undef_loc, %add
%limit2 = add nsw i32 %limit0, 10
br i1 %cmp3, label %loop.body.lr.ph.split.us, label
%loop.body.lr.ph.loop.body.lr.ph.split_crit_edge
...
Loop unswitch introduce a branch on %cmp3, which will be undef once we inline
maybe_init(). Hence loop unswitch assumes branch on undef is a
non-deterministic jump (so not UB).
By running GVN after loop unswitch, we clearly see that GVN has a different
perspective on the semantics of branch on undef. It produces this diff:
- %limit2 = add nsw i32 %limit0, 10
...
- %cmp = icmp slt i32 %i2, %limit2
+ %cmp = icmp slt i32 %i2, %undef_loc
I'm not including the context here, but to be able to justify this
transformation, branch on undef has to be UB, not a non-deterministic jump as
assumed by loop unswitch above.
Putting all things together:
$ opt -S bug.ll -loop-rotate -licm -loop-unswitch -gvn | opt -S -O2 | llc -o
x.S && clang x.S -o x && ./x
f(10) = 1
This is wrong. Should be 20, not 1.
This example shows how Loop unswitch and GVN can produce a miscompilation
end-to-end. The bug can be fixed by using the proposed freeze instruction in
loop unswitch.
(Example by Sanjoy)</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>