[Reassociate] move check to ignore boolean expressions before canonicalizing binary operands

[mhillenbrand]

Summary

The Reassociate pass intends to leave alone boolean (i1) expressions
to preserve the order of short-circuited comparisons, which SimplifyCFG
has folded into AND/OR expressions. The check to achieve that behavior
currently is ineffective since it only happens after
canonicalizeOperands() may already have flipped the order of operands
(and, consequentially, the order of short-circuited comparisons after
CodeGen). Move that check up to happen before the call to
canonicalizeOperands().

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

[fhahn]

Can you add a test for the change?

[lebedev.ri]

I do not understand the example in https://bugs.llvm.org/show_bug.cgi?id=48529
By "intent", are you saying that the canonicalization of commutative ops
is causing the code to be miscompiled, leading to different observable side-effects?

[mhillenbrand]

@lebedev.ri No, I do not see differences in observable side-effects. Though, runtime differs significantly depending on the order of evaluation. Thus, "intent" would be out-of-band information that the programmer has about the likelihood of each of the terms being true, and placing the most-likely term first, while that cannot be derived from the source by the compiler.

In the example

if (ab > de || ac > df || bc > cd)
      return 0;

the programmer may know that (ab > de) is more commonly true than (ac >df) and thus place the former check first. With short-circuited evaluation strictly in the order of the source code, the resulting code would execute fewer comparisons and run faster, and vice versa.

@fhahn I will add a test (seeking feedback whether this actually makes sense with this initial submission).

[mhillenbrand]

Add regression test

[spatel]

llvm/lib/Transforms/Scalar/Reassociate.cpp

2190–2195

For reference, this was added in 2010:
27dfb1e

I'm sympathetic to the motivation, but that was a hack: one goal of IR is to overcome side-channel source-level optimization like this.

For example, we added several IR transforms to reduce compiled-code differences in source-level diffs like "if (bool1 && bool2)" vs. "if (bool1 & bool2)" (logical vs. bitwise ops).

If the expression order matters, then we want the programmer to indicate that explicitly with something like "__builtin_expect" or profile metadata.

So this patch is really taking us away from the end goal (assuming we can get there). It might help solve the motivating problem in the short-term, but there's no guarantee that the fix will last.

[mhillenbrand]

Sanjay, thanks for providing context. In that light, I'm dropping this patch.

llvm/lib/Transforms/Scalar/Reassociate.cpp

if (isReassociableOp(I->getOperand(0), Instruction::Mul) ||
          (isReassociableOp(I->user_back(), Instruction::Mul) ||
           isReassociableOp(I->user_back(), Instruction::Add)))) {
       Instruction *NI = ConvertShiftToMul(I);
       RedoInsts.insert(I);
       MadeChange = true;
       I = NI;
     }
 
+  // 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;
+
   // 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);
 
   // Canonicalize negative constants out of expressions.
   if (Instruction *Res = canonicalizeNegFPConstants(I))
     I = Res;
 
   // Don't optimize floating-point instructions unless they are 'fast'.
   if (I->getType()->isFPOrFPVectorTy() && !I->isFast())
     return;
 
-  // 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;
 
   // If this is a bitwise or instruction of operands
   // with no common bits set, convert it to X+Y.
   if (I->getOpcode() == Instruction::Or &&
       ShouldConvertOrWithNoCommonBitsToAdd(I) && !isLoadCombineCandidate(I) &&
       haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1),
                           I->getModule()->getDataLayout(), /*AC=*/nullptr, I,
                           /*DT=*/nullptr)) {

llvm/test/Transforms/Reassociate/pr48529.ll

+; RUN: opt < %s -reassociate -S | FileCheck %s
+; PR48529
+
+; reduced from code with the structure
+;
+; float ab = a * b;
+; float ac = a * c;
+; float bc = b * c;
+; ...
+;
+; if (ab > de || ac > df || bc > cd)
+;     return 0;
+; ...
+; return 1;
+;
+; clang first produces short-circuiting control flow
+; which simplify-cfg contracts to "or i1"
+
+define i32 @simple_reduced() {
+lor.lhs.false:
+  %mul4 = fmul contract float undef, undef
+  %cmp6 = fcmp contract ogt float undef, %mul4
+  %cmp8 = fcmp contract ogt float undef, undef
+  %or.cond2 = or i1 %cmp6, %cmp8
+; CHECK: simple_reduced
+; CHECK: %or.cond2 = or i1 %cmp6, %cmp8
+  br i1 %or.cond2, label %return, label %if.end
+
+if.end:
+  ret i32 1
+
+return:
+  ret i32 0
+}