[ConstraintElim] Store conditional facts as (Predicate, Op0, Op1).

[fhahn]

Summary

This allows to add facts even if no corresponding ICmp instruction
exists in the IR.

[nikic]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

120

The flags here have become something of a mess. Can we represent these as an enum instead? Something like...

enum {
  /// Fact implied by Inst, holds from the definition point of Inst.
  InstFact,
  /// Fact implied by Condition, holds from the start of the block.
  CondFact,
  /// Check at a specific use-site of an instruction.
  UseCheck,
  /// Check for all uses of an instruction.
  InstCheck,
}

...assuming those are the possible cases, of which I'm not really sure.

[fhahn]

Rebase on top of e6260ec49c5d16dc93ebe8b.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

120

Thanks, added an enum here: e6260ec49c5d

[nikic]

LGTM

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1415

I think you can directly << Pred nowadays.

1418

You can pass false to avoid printing the type again.

1461

I feel like this code would be simpler/cleaner if you didn't share this AddFact call and just did it in both branches above.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1415

Nice, updated in the committed version, thanks!

1418

Nice, updated in the committed version, thanks!

1461

Add fact can be used unconditionally here. Also simplified the matching for the assume condition and added an assert that it gets matched.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 static Instruction *getContextInstForUse(Use &U) {
   Instruction *UserI = cast<Instruction>(U.getUser());
   if (auto *Phi = dyn_cast<PHINode>(UserI))
     UserI = Phi->getIncomingBlock(U)->getTerminator();
   return UserI;
 }
 
 namespace {
+/// Struct to express a condition of the form %Op0 Pred %Op1.
+struct ConditionTy {
+  CmpInst::Predicate Pred;
+  Value *Op0;
+  Value *Op1;
+
+  ConditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
+      : Pred(Pred), Op0(Op0), Op1(Op1) {}
+};
+
 /// Represents either
 ///  * a condition that holds on entry to a block (=condition fact)
 ///  * an assume (=assume fact)
 ///  * a use of a compare instruction to simplify.
 /// It also tracks the Dominator DFS in and out numbers for each entry.
 struct FactOrCheck {
   enum class EntryTy {
     ConditionFact, /// A condition that holds on entry to a block.
     InstFact,      /// A fact that holds after Inst executed (e.g. an assume or
                    /// min/mix intrinsic.
     InstCheck,     /// An instruction to simplify (e.g. an overflow math
                    /// intrinsics).
     UseCheck       /// An use of a compare instruction to simplify.
   };
 
   union {
     Instruction *Inst;
     Use *U;
+    ConditionTy Cond;
   };
 
   unsigned NumIn;
   unsigned NumOut;
   EntryTy Ty;
-  bool Not;
 
-  FactOrCheck(EntryTy Ty, DomTreeNode *DTN, Instruction *Inst, bool Not)
+  FactOrCheck(EntryTy Ty, DomTreeNode *DTN, Instruction *Inst)
       : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
-        Ty(Ty), Not(Not) {}
+        Ty(Ty) {}
 
   FactOrCheck(DomTreeNode *DTN, Use *U)
       : U(U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
-        Ty(EntryTy::UseCheck), Not(false) {}
+        Ty(EntryTy::UseCheck) {}
 
-  static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpInst *Inst,
-                                      bool Not = false) {
-    return FactOrCheck(EntryTy::ConditionFact, DTN, Inst, Not);
+  FactOrCheck(DomTreeNode *DTN, CmpInst::Predicate Pred, Value *Op0, Value *Op1)
+      : Cond(Pred, Op0, Op1), NumIn(DTN->getDFSNumIn()),
+        NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
+
+  static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpInst::Predicate Pred,
+                                      Value *Op0, Value *Op1) {
+    return FactOrCheck(DTN, Pred, Op0, Op1);
   }
 
-  static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst,
-                                 bool Not = false) {
-    return FactOrCheck(EntryTy::InstFact, DTN, Inst, Not);
+  static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst) {
+    return FactOrCheck(EntryTy::InstFact, DTN, Inst);
+  }
+
+  static FactOrCheck getFact(DomTreeNode *DTN, CmpInst::Predicate Pred,
+                             Value *Op0, Value *Op1) {
+    return FactOrCheck(DTN, Pred, Op0, Op1);
   }
 
   static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) {
     return FactOrCheck(DTN, U);
   }
 
   static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) {
-    return FactOrCheck(EntryTy::InstCheck, DTN, CI, false);
+    return FactOrCheck(EntryTy::InstCheck, DTN, CI);
   }
 
   bool isCheck() const {
     return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
   }
 
   Instruction *getContextInst() const {
     if (Ty == EntryTy::UseCheck)
struct StackEntry {
   SmallVector<Value *, 2> ValuesToRelease;
 
   StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,
              SmallVector<Value *, 2> ValuesToRelease)
       : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
         ValuesToRelease(ValuesToRelease) {}
 };
 
-/// Struct to express a pre-condition of the form %Op0 Pred %Op1.
-struct PreconditionTy {
-  CmpInst::Predicate Pred;
-  Value *Op0;
-  Value *Op1;
-
-  PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
-      : Pred(Pred), Op0(Op0), Op1(Op1) {}
-};
-
 struct ConstraintTy {
   SmallVector<int64_t, 8> Coefficients;
-  SmallVector<PreconditionTy, 2> Preconditions;
+  SmallVector<ConditionTy, 2> Preconditions;
 
   SmallVector<SmallVector<int64_t, 8>> ExtraInfo;
 
   bool IsSigned = false;
 
   ConstraintTy() = default;
 
   ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned, bool IsEq,
void mul(int64_t Factor) {
     for (auto &Var : Vars)
       Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor);
   }
 };
 
 } // namespace
 
 static Decomposition decompose(Value *V,
-                               SmallVectorImpl<PreconditionTy> &Preconditions,
+                               SmallVectorImpl<ConditionTy> &Preconditions,
                                bool IsSigned, const DataLayout &DL);
 
 static bool canUseSExt(ConstantInt *CI) {
   const APInt &Val = CI->getValue();
   return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue);
 }
 
-static Decomposition
-decomposeGEP(GEPOperator &GEP, SmallVectorImpl<PreconditionTy> &Preconditions,
+static Decomposition decomposeGEP(GEPOperator &GEP,
+                                  SmallVectorImpl<ConditionTy> &Preconditions,
                                   bool IsSigned, const DataLayout &DL) {
   // Do not reason about pointers where the index size is larger than 64 bits,
   // as the coefficients used to encode constraints are 64 bit integers.
   if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
     return &GEP;
 
   if (!GEP.isInBounds())
     return &GEP;
 
static Decomposition decomposeGEP(GEPOperator &GEP,
   }
   return Result;
 }
 
 // Decomposes \p V into a constant offset + list of pairs { Coefficient,
 // Variable } where Coefficient * Variable. The sum of the constant offset and
 // pairs equals \p V.
 static Decomposition decompose(Value *V,
-                               SmallVectorImpl<PreconditionTy> &Preconditions,
+                               SmallVectorImpl<ConditionTy> &Preconditions,
                                bool IsSigned, const DataLayout &DL) {
 
   auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B,
                                                       bool IsSignedB) {
     auto ResA = decompose(A, Preconditions, IsSigned, DL);
     auto ResB = decompose(B, Preconditions, IsSignedB, DL);
     ResA.add(ResB);
     return ResA;
ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
   default:
     break;
   }
 
   if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
       Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
     return {};
 
-  SmallVector<PreconditionTy, 4> Preconditions;
+  SmallVector<ConditionTy, 4> Preconditions;
   bool IsSigned = CmpInst::isSigned(Pred);
   auto &Value2Index = getValue2Index(IsSigned);
   auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),
                         Preconditions, IsSigned, DL);
   auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),
                         Preconditions, IsSigned, DL);
   int64_t Offset1 = ADec.Offset;
   int64_t Offset2 = BDec.Offset;
ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
   ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
   if (!NewVariables.empty())
     return {};
   return R;
 }
 
 bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
   return Coefficients.size() > 0 &&
-         all_of(Preconditions, [&Info](const PreconditionTy &C) {
+         all_of(Preconditions, [&Info](const ConditionTy &C) {
            return Info.doesHold(C.Pred, C.Op0, C.Op1);
          });
 }
 
 std::optional<bool>
 ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {
   bool IsConditionImplied = CS.isConditionImplied(Coefficients);
 
if (match(&I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
       continue;
     }
 
     if (isa<MinMaxIntrinsic>(&I)) {
       WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));
       continue;
     }
 
-    Value *Cond;
+    Value *A, *B;
+    CmpInst::Predicate Pred;
     // For now, just handle assumes with a single compare as condition.
-    if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
-        isa<ICmpInst>(Cond)) {
+    if (match(&I, m_Intrinsic<Intrinsic::assume>(
+                      m_ICmp(Pred, m_Value(A), m_Value(B))))) {
       if (GuaranteedToExecute) {
         // The assume is guaranteed to execute when BB is entered, hence Cond
         // holds on entry to BB.
         WorkList.emplace_back(FactOrCheck::getConditionFact(
-            DT.getNode(I.getParent()), cast<CmpInst>(Cond)));
+            DT.getNode(I.getParent()), Pred, A, B));
       } else {
         WorkList.emplace_back(
             FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));
       }
     }
     GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
   }
 
if (canAddSuccessor(BB, Successor)) {
         if (SeenCond.insert(V).second)
           CondWorkList.push_back(V);
       };
       QueueValue(Op1);
       QueueValue(Op0);
       while (!CondWorkList.empty()) {
         Value *Cur = CondWorkList.pop_back_val();
         if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
-          WorkList.emplace_back(
-              FactOrCheck::getConditionFact(DT.getNode(Successor), Cmp, IsOr));
+          WorkList.emplace_back(FactOrCheck::getConditionFact(
+              DT.getNode(Successor),
+              IsOr ? CmpInst::getInversePredicate(Cmp->getPredicate())
+                   : Cmp->getPredicate(),
+              Cmp->getOperand(0), Cmp->getOperand(1)));
           continue;
         }
         if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
           QueueValue(Op1);
           QueueValue(Op0);
           continue;
         }
         if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
           QueueValue(Op1);
           QueueValue(Op0);
           continue;
         }
       }
     }
     return;
   }
 
   auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
   if (!CmpI)
     return;
   if (canAddSuccessor(BB, Br->getSuccessor(0)))
-    WorkList.emplace_back(
-        FactOrCheck::getConditionFact(DT.getNode(Br->getSuccessor(0)), CmpI));
+    WorkList.emplace_back(FactOrCheck::getConditionFact(
+        DT.getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
+        CmpI->getOperand(0), CmpI->getOperand(1)));
   if (canAddSuccessor(BB, Br->getSuccessor(1)))
     WorkList.emplace_back(FactOrCheck::getConditionFact(
-        DT.getNode(Br->getSuccessor(1)), CmpI, true));
+        DT.getNode(Br->getSuccessor(1)),
+        CmpInst::getInversePredicate(CmpI->getPredicate()), CmpI->getOperand(0),
+        CmpI->getOperand(1)));
 }
 
 namespace {
 /// Helper to keep track of a condition and if it should be treated as negated
 /// for reproducer construction.
 /// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a
 /// placeholder to keep the ReproducerCondStack in sync with DFSInStack.
 struct ReproducerEntry {
static bool eliminateConstraints(Function &F, DominatorTree &DT,
   // condition to check and a fact have the same numbers, conditional facts come
   // first. Assume facts and checks are ordered according to their relative
   // order in the containing basic block. Also make sure conditions with
   // constant operands come before conditions without constant operands. This
   // increases the effectiveness of the current signed <-> unsigned fact
   // transfer logic.
   stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
     auto HasNoConstOp = [](const FactOrCheck &B) {
-      return !isa<ConstantInt>(B.Inst->getOperand(0)) &&
-             !isa<ConstantInt>(B.Inst->getOperand(1));
+      Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
+      Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
+      return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
     };
     // If both entries have the same In numbers, conditional facts come first.
     // Otherwise use the relative order in the basic block.
     if (A.NumIn == B.NumIn) {
       if (A.isConditionFact() && B.isConditionFact()) {
         bool NoConstOpA = HasNoConstOp(A);
         bool NoConstOpB = HasNoConstOp(B);
         return NoConstOpA < NoConstOpB;
if (CB.isCheck()) {
               checkAndSecondOpImpliedByFirst(CB, Info, ReproducerModule.get(),
                                              ReproducerCondStack, DFSInStack);
         }
         Changed |= Simplified;
       }
       continue;
     }
 
-    LLVM_DEBUG(dbgs() << "fact to add to the system: " << *CB.Inst << "\n");
     auto AddFact = [&](CmpInst::Predicate Pred, Value *A, Value *B) {
       if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
         LLVM_DEBUG(
             dbgs()
             << "Skip adding constraint because system has too many rows.\n");
         return;
       }
 
+      LLVM_DEBUG({
+        dbgs() << "Processing fact to add to the system: "
+               << CmpInst::getPredicateName(Pred) << " ";
+        A->printAsOperand(dbgs());
+        dbgs() << ", ";
+        B->printAsOperand(dbgs());
+        dbgs() << "\n";
+      });
+
       Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
       if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
         ReproducerCondStack.emplace_back(Pred, A, B);
 
       Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
       if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
         // Add dummy entries to ReproducerCondStack to keep it in sync with
         // DFSInStack.
         for (unsigned I = 0,
                       E = (DFSInStack.size() - ReproducerCondStack.size());
              I < E; ++I) {
           ReproducerCondStack.emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
                                            nullptr, nullptr);
         }
       }
     };
 
     ICmpInst::Predicate Pred;
+    if (!CB.isConditionFact()) {
       if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
         Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
         AddFact(Pred, MinMax, MinMax->getLHS());
         AddFact(Pred, MinMax, MinMax->getRHS());
         continue;
       }
+    }
 
-    Value *A, *B;
+    Value *A = nullptr, *B = nullptr;
+    if (CB.isConditionFact()) {
+      Pred = CB.Cond.Pred;
+      A = CB.Cond.Op0;
+      B = CB.Cond.Op1;
+    } else {
       Value *Cmp = CB.Inst;
       match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
       if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
-      // Use the inverse predicate if required.
-      if (CB.Not)
-        Pred = CmpInst::getInversePredicate(Pred);
-
-      AddFact(Pred, A, B);
       }
     }
+    if (A)
+      AddFact(Pred, A, B);
+  }
 
   if (ReproducerModule && !ReproducerModule->functions().empty()) {
     std::string S;
     raw_string_ostream StringS(S);
     ReproducerModule->print(StringS, nullptr);
     StringS.flush();
     OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
     Rem << ore::NV("module") << S;

llvm/test/Transforms/ConstraintElimination/debug.ll

 ; RUN: opt -passes=constraint-elimination -S -debug %s 2>&1 | FileCheck %s
 
 ; REQUIRES: asserts
 
 define i1 @test_and_ule(i4 %x, i4 %y, i4 %z) {
-; CHECK:      Processing fact to add to the system:  %c.1 = icmp ule i4 %x, %y
+; CHECK:      Processing fact to add to the system:  ule i4 %x, i4 %y
 ; CHECK-NEXT: Adding 'ule %x, %y'
 ; CHECK-NEXT:  constraint: %x + -1 * %y <= 0
 
-; CHECK:      Processing fact to add to the system:  %c.2 = icmp ule i4 %y, %z
+; CHECK:      Processing fact to add to the system:  ule i4 %y, i4 %z
 ; CHECK-NEXT: Adding 'ule %y, %z'
 ; CHECK-NEXT:  constraint: %y + -1 * %z <= 0
 
 ; CHECK: Checking   %t.1 = icmp ule i4 %x, %z
 ; CHECK: Condition   %t.1 = icmp ule i4 %x, %z implied by dominating constraints
 
 ; CHECK: Removing %y + -1 * %z <= 0
 ; CHECK: Removing %x + -1 * %y <= 0
bb1:
   ret i1 %t.1
 
 exit:
   %c.3 = icmp ule i4 %x, %z
   ret i1 %c.3
 }
 
 define i1 @test_and_ugt(i4 %x, i4 %y, i4 %z) {
-; CHECK:      Processing fact to add to the system:   %c.1 = icmp ugt i4 %x, %y
+; CHECK:      Processing fact to add to the system:   ugt i4 %x, i4 %y
 ; CHECK-NEXT: Adding 'ugt %x, %y'
 ; CHECK-NEXT:  constraint: -1 * %x + %y <= -1
 
-; CHECK:      Processing fact to add to the system:   %c.2 = icmp ugt i4 %y, %z
+; CHECK:      Processing fact to add to the system:   ugt i4 %y, i4 %z
 ; CHECK-NEXT: Adding 'ugt %y, %z'
 ; CHECK-NEXT:  constraint: -1 * %y + %z <= -1
 
 ; CHECK: Checking   %f.1 = icmp ule i4 %x, %z
 ; CHECK: Condition ugt i4 %x, i4 %z implied by dominating constraints
 
 ; CHECK: Removing -1 * %y + %z <= -1
 ; CHECK: Removing -1 * %x + %y <= -1