[llvm-bugs] [Bug 48529] New: Reassociate reorders evaluation of short-circuited comparisons

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=48529

            Bug ID: 48529
           Summary: Reassociate reorders evaluation of short-circuited
                    comparisons
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: mhillen at linux.ibm.com
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

Created attachment 24291
  --> https://bugs.llvm.org/attachment.cgi?id=24291&action=edit
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 ...
https://github.com/llvm/llvm-project/blob/9f80ab1213e9f28b1b86f133fa7edf9a61c6f8fd/llvm/lib/Transforms/Scalar/Reassociate.cpp#L2204

  // 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
https://github.com/llvm/llvm-project/blob/9f80ab1213e9f28b1b86f133fa7edf9a61c6f8fd/llvm/lib/Transforms/Scalar/Reassociate.cpp#L2193

  // 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).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20201216/a6c1651b/attachment.html>