[ConstraintElimination] Decompose or instruction if the constant operand < 2^known_zero_bits of the first operand.

[zjaffal]

Summary

The or operation can be represented as an add instruction.

[nikic]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

357

You're looking for haveNoCommonBitsSet().

[zjaffal]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

357

I tried the following snippet

if (match(V, m_Or(m_Value(Op0), m_ConstantInt(CI)))) {
  if (haveNoCommonBitsSet(Op0, CI, DL))
    return MergeResults(Op0, CI, IsSigned);
}

it works for most of the cases but for the following test define void @test.not.uge.ule

%start.4 = or i8 %start, 4
%t.4 = icmp ule i8 %start.4, %high
call void @use(i1 %t.4)

%t.4 is not replaced with true

[nikic]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

357

Isn't that the expected behavior? It's the same with your current patch.

[goldstein.w.n]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

359

Is it more useful to have an add than an or?

[nikic]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

359

For this pass, yes, as it only handles adds. If this was a more generic question: We currently canonicalize add -> or if no common bits, and then undo that in various places. It's hard to say whether switching to the reverse direction or -> add would be more beneficial. We have both many or folds and many add folds. I've never tried it, though I did wonder about it in the past.

[fhahn]

Looks like the patch needs updating.

[zjaffal]

The new change uses haveNoCommonBitsSet instead

[zjaffal]

llvm/test/Transforms/ConstraintElimination/or.ll

534–535

This transformation should be true
https://alive2.llvm.org/ce/z/xvrMtA

hasNoCommonBits doesn't optimise it while the original implementation did

610–611

this check should be false
https://alive2.llvm.org/ce/z/9-7sJR

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

373

Could you add a comment indicating what this code does, i.e. treat or as an Add if no common bits are set?

374

nit: merge with previous if

llvm/test/Transforms/ConstraintElimination/or.ll

534–535

It's fine if the current version doesn't catch all possible cases we could optimize. Further improvements can be landed as follow-ups

[fhahn]

LGTM with the suggestions addressed before landing.

[zjaffal]

• Add comment to explain that the operation is being treated as an add
• Address nit comments

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
+#include "llvm/Support/KnownBits.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 
 #include <cmath>
 #include <string>
 
 using namespace llvm;
static Decomposition decompose(Value *V,
   Value *Op1;
   ConstantInt *CI;
   if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
     return MergeResults(Op0, Op1, IsSigned);
   }
   if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
     if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
       Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
                                  ConstantInt::get(Op0->getType(), 0));
     if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
       Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
                                  ConstantInt::get(Op1->getType(), 0));
 
     return MergeResults(Op0, Op1, IsSigned);
   }
 
   if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
       canUseSExt(CI)) {
     Preconditions.emplace_back(
         CmpInst::ICMP_UGE, Op0,
         ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
     return MergeResults(Op0, CI, true);
   }
 
+  // Decompose or as an add if there are no common bits between the operands.
+  if (match(V, m_Or(m_Value(Op0), m_ConstantInt(CI))) &&
+      haveNoCommonBitsSet(Op0, CI, DL)) {
+    return MergeResults(Op0, CI, IsSigned);
+  }
+
   if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
     int64_t Mult = int64_t(std::pow(int64_t(2), CI->getSExtValue()));
     auto Result = decompose(Op1, Preconditions, IsSigned, DL);
     Result.mul(Mult);
     return Result;
   }
 
   if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&

llvm/test/Transforms/ConstraintElimination/or.ll

 ; CHECK-NEXT:    [[F_2:%.*]] = icmp ult i8 [[I_2]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[F_2]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       end:
 ; CHECK-NEXT:    [[T_0:%.*]] = icmp ult i8 [[START]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_1:%.*]] = or i8 [[START]], 1
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ult i8 [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_2:%.*]] = or i8 [[START]], 2
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ult i8 [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_3:%.*]] = or i8 [[START]], 3
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp ult i8 [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_4:%.*]] = or i8 [[START]], 4
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ult i8 [[START_4]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %start = shl nuw nsw i8 %init_val, 2
   %start.plus.3 = add nuw i8 %start, 3

 ; CHECK-NEXT:    [[F_2:%.*]] = icmp ule i8 [[I_2]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[F_2]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       end:
 ; CHECK-NEXT:    [[T_0:%.*]] = icmp ule i8 [[START]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_1:%.*]] = or i8 [[START]], 1
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i8 [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_2:%.*]] = or i8 [[START]], 2
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_3:%.*]] = or i8 [[START]], 3
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp ule i8 [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_4:%.*]] = or i8 [[START]], 4
 ; CHECK-NEXT:    [[T_4:%.*]] = icmp ule i8 [[START_4]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[T_4]])
 ; CHECK-NEXT:    [[START_5:%.*]] = or i8 [[START]], 5
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ule i8 [[START_5]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %start = shl nuw nsw i8 %init_val, 2
   %start.plus.3 = add nuw i8 %start, 3

 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ugt i8 [[I_2]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[T_2]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       end:
 ; CHECK-NEXT:    [[F_0:%.*]] = icmp ugt i8 [[START]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_1:%.*]] = or i8 [[START]], 1
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp ugt i8 [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_2:%.*]] = or i8 [[START]], 2
 ; CHECK-NEXT:    [[F_2:%.*]] = icmp ugt i8 [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_3:%.*]] = or i8 [[START]], 3
 ; CHECK-NEXT:    [[F_3:%.*]] = icmp ugt i8 [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_4:%.*]] = or i8 [[START]], 4
 ; CHECK-NEXT:    [[F_4:%.*]] = icmp ugt i8 [[START_4]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[F_4]])
 ; CHECK-NEXT:    [[START_5:%.*]] = or i8 [[START]], 5
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ugt i8 [[START_5]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %start = shl nuw nsw i8 %init_val, 2
   %start.plus.3 = add nuw i8 %start, 3

 ; CHECK-NEXT:    [[T_2:%.*]] = icmp uge i8 [[I_2]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[T_2]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       end:
 ; CHECK-NEXT:    [[F_0:%.*]] = icmp ugt i8 [[START]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_1:%.*]] = or i8 [[START]], 1
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp uge i8 [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_2:%.*]] = or i8 [[START]], 2
 ; CHECK-NEXT:    [[F_2:%.*]] = icmp uge i8 [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_3:%.*]] = or i8 [[START]], 3
 ; CHECK-NEXT:    [[F_3:%.*]] = icmp uge i8 [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_4:%.*]] = or i8 [[START]], 4
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp uge i8 [[START_4]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    [[START_5:%.*]] = or i8 [[START]], 5
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp uge i8 [[START_5]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;