<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 - Reassociate reorders evaluation of short-circuited comparisons"
href="https://bugs.llvm.org/show_bug.cgi?id=48529">48529</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Reassociate reorders evaluation of short-circuited comparisons
</td>
</tr>
<tr>
<th>Product</th>
<td>new-bugs
</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>new bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>mhillen@linux.ibm.com
</td>
</tr>
<tr>
<th>CC</th>
<td>htmldeveloper@gmail.com, llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=24291" name="attach_24291" title="Example that demonstrates the reordering; clang++ -g -S -O2 -o- shortcircuit.cpp">attachment 24291</a> <a href="attachment.cgi?id=24291&action=edit" title="Example that demonstrates the reordering; clang++ -g -S -O2 -o- shortcircuit.cpp">[details]</a></span>
Example that demonstrates the reordering; clang++ -g -S -O2 -o-
shortcircuit.cpp
The Reassociate pass can end up reordering the evaluation of short-circuited
comparisons, when SimplifyCFG folded them to to OR expressions and CodeGen
later unfolds the OR expressions into short-circuited form. There is a check in
Reassociate that attempts to prevent reordering in these cases, yet that check
happens a few lines of code too late (see below). I have attached an example
that reproduces on targets X86-64 and SystemZ.
In my reduced example (attached), the expression
if (ab > de || ac > df || bc > cd)
return 0;
is first emitted as short-circuited by clang, then SimplifyCFG folds the latter
two comparisons into an OR
...
%cmp6 = fcmp contract ogt float %mul1, %mul4 (i.e., ac and df)
%cmp8 = fcmp contract ogt float %mul2, %mul5 (i.e., bc and cd)
%or.cond26 = or i1 %cmp6, %cmp8,
br i1 %or.cond26, label %cleanup, label %if.end,
...
and Reassociate flips the operands of the OR (ranks just happen to turn out
that way)
...
%or.cond26 = or i1 %cmp8, %cmp6
...
When CodeGen turns that back into short-circuited form, honoring that new
order, the emitted code checks bc > cd before ac > df, potentially ignoring the
intent behind the order in the code.
A code comment explicitly states that behavior as undesired, with a guard to
return early. However, that check ...
<a href="https://github.com/llvm/llvm-project/blob/9f80ab1213e9f28b1b86f133fa7edf9a61c6f8fd/llvm/lib/Transforms/Scalar/Reassociate.cpp#L2204">https://github.com/llvm/llvm-project/blob/9f80ab1213e9f28b1b86f133fa7edf9a61c6f8fd/llvm/lib/Transforms/Scalar/Reassociate.cpp#L2204</a>
// Do not reassociate boolean (i1) expressions. We want to preserve the
// original order of evaluation for short-circuited comparisons that
// SimplifyCFG has folded to AND/OR expressions. If the expression
// is not further optimized, it is likely to be transformed back to a
// short-circuited form for code gen, and the source order may have been
// optimized for the most likely conditions.
if (I->getType()->isIntegerTy(1))
return;
... is too late, since the reordering already happens before in
canonicalizeOperands
<a href="https://github.com/llvm/llvm-project/blob/9f80ab1213e9f28b1b86f133fa7edf9a61c6f8fd/llvm/lib/Transforms/Scalar/Reassociate.cpp#L2193">https://github.com/llvm/llvm-project/blob/9f80ab1213e9f28b1b86f133fa7edf9a61c6f8fd/llvm/lib/Transforms/Scalar/Reassociate.cpp#L2193</a>
// Commute binary operators, to canonicalize the order of their operands.
// This can potentially expose more CSE opportunities, and makes writing
other
// transformations simpler.
if (I->isCommutative())
canonicalizeOperands(I);
Moving the check for a boolean expression up above the call to
canonicalizeOperands would prevent the reordering. (fwiw, that change passes
the testsuite).</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>