[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

 //===- Reassociate.cpp - Reassociate binary expressions -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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)) {