[ConstraintElim] Track and simplify conditions at use.

[fhahn]

Summary

This patch updates ConstraintElimination to track uses of conditions in
the worklist. This allows simplifying conditions using the context that
holds directly at the condition, instead of where the condition is
defined.

This allows us to catch more cases in practice: there are multiple
code-size changes for CTMark while compile-time remains unchanged:
https://llvm-compile-time-tracker.com/compare.php?from=55d04119687ac4a9509717a4c310332921047375&to=6c8e15609386078cb34df7c3891fdb1c47c8f830&stat=size-total

This should help to simplify D151799.

[nikic]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1064

Aren't we always working on a single Use now and could replace just that use?

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1064

We could still replace multiple uses if there are other uses dominated by the current one. This way, we don't need to query the constraint system repeatedly if we already were able to prove it at a dominating use.

[nikic]

Can you please add some tests with uses in phi nodes? I don't think the handling for those is correct. (Though more in the direction of missing some replacements that were previously done rather than doing invalid replacements.)

[fhahn]

In D153660#4446248, @nikic wrote:

Can you please add some tests with uses in phi nodes? I don't think the handling for those is correct. (Though more in the direction of missing some replacements that were previously done rather than doing invalid replacements.)

I added some tests in 0ddfb802e4ca. Is that what you had in mind? I think we shouldn't miss any of those, because the code should ensure that the uses in the context instruction (the user of the use we queued) is always replaced.

[fhahn]

Rebase on top of current main.

[nikic]

The case I had in mind is something like this:

define i1 @test(i32 %x) {
entry:
  %cmp1 = icmp sgt i32 %x, 1
  br i1 %cmp1, label %if, label %join

if:
  %cmp2 = icmp sgt i32 %x, 0
  br label %join

join:
  %phi = phi i1 [ %cmp2, %if ], [ false, %entry ]
  ret i1 %phi
}

Where the %cmp1 fact dominates the %cmp2 use, but not if we consider the %cmp2 use to be in %join.

[bcl5980]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1306

Typo?

[fhahn]

In D153660#4447236, @nikic wrote:

The case I had in mind is something like this:

define i1 @test(i32 %x) {
entry:
  %cmp1 = icmp sgt i32 %x, 1
  br i1 %cmp1, label %if, label %join

if:
  %cmp2 = icmp sgt i32 %x, 0
  br label %join

join:
  %phi = phi i1 [ %cmp2, %if ], [ false, %entry ]
  ret i1 %phi
}

Where the %cmp1 fact dominates the %cmp2 use, but not if we consider the %cmp2 use to be in %join.

Ah yes, not an issue during the replacement but where we queue. Added tests in 81e3779a131f and updated the code to use the branch instruction of the incoming block as context.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1306

Thanks, removed!

[nikic]

Can you please also add a test along these lines?

define i1 @test(i1 %c, i32 %x) {
entry:
  br i1 %c, label %if, label %join

if: 
  %cmp1 = icmp sgt i32 %x, 1
  %cmp2 = icmp sgt i32 %x, 0
  br i1 %cmp1, label %join, label %exit

join:
  %phi = phi i1 [ %cmp2, %if ], [ false, %entry ]
  ret i1 %phi

exit:
  ret i1 false
}

Here the fact is known only along the edge, but in neither of the blocks. I don't expect this to actually get folded...

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

666

No need for getOperandNo, there's an overload for Uses.

721

The dyn_cast is needed because it may have been replaced by a constant already?

1286

Stray semicolon

[fhahn]

Address latest comments, thanks!

In D153660#4452297, @nikic wrote:

Can you please also add a test along these lines?

define i1 @test(i1 %c, i32 %x) {
entry:
  br i1 %c, label %if, label %join

if: 
  %cmp1 = icmp sgt i32 %x, 1
  %cmp2 = icmp sgt i32 %x, 0
  br i1 %cmp1, label %join, label %exit

join:
  %phi = phi i1 [ %cmp2, %if ], [ false, %entry ]
  ret i1 %phi

exit:
  ret i1 false
}

Here the fact is known only along the edge, but in neither of the blocks. I don't expect this to actually get folded...

Yep, if the fact is only known on the edge then we don't simplify it at the moment. This could probably be handled by making the fact handling more fine-grained.

I *think* this should already be covered by the following test. It's a 3 entry phi, not sure if it is worth adding a dedicated simpler case? https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll#L221

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

666

Done, thanks!

721

Yes, I added a comment here.

1286

removed, thanks!

[nikic]

In D153660#4452408, @fhahn wrote:

Yep, if the fact is only known on the edge then we don't simplify it at the moment. This could probably be handled by making the fact handling more fine-grained.

I *think* this should already be covered by the following test. It's a 3 entry phi, not sure if it is worth adding a dedicated simpler case? https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll#L221

Ah yes, that does cover the case. Nevermind then.

LGTM with the nits addressed.

[fhahn]

In D153660#4452713, @nikic wrote:

In D153660#4452408, @fhahn wrote:

Yep, if the fact is only known on the edge then we don't simplify it at the moment. This could probably be handled by making the fact handling more fine-grained.

I *think* this should already be covered by the following test. It's a 3 entry phi, not sure if it is worth adding a dedicated simpler case? https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll#L221

Ah yes, that does cover the case. Nevermind then.

LGTM with the nits addressed.

Thanks! Just to double check, the previous nits should already be addressed, where there any additional nits that may not got submitted?

[nikic]

In D153660#4452721, @fhahn wrote:

Thanks! Just to double check, the previous nits should already be addressed, where there any additional nits that may not got submitted?

Nope, just a case of too many tabs...

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

void ConstraintInfo::transferToOtherSystem(
   case CmpInst::ICMP_SGE:
     if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
       addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
     }
     break;
   }
 }
 
+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 {
 /// Represents either
 ///  * a condition that holds on entry to a block (=conditional fact)
 ///  * an assume (=assume fact)
-///  * an instruction to simplify.
+///  * a use of a compare instruction to simplify.
 /// It also tracks the Dominator DFS in and out numbers for each entry.
 struct FactOrCheck {
+  union {
     Instruction *Inst;
+    Use *U;
+  };
   unsigned NumIn;
   unsigned NumOut;
-  bool IsCheck;
+  bool HasInst;
   bool Not;
 
-  FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool IsCheck, bool Not)
+  FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool Not)
       : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
-        IsCheck(IsCheck), Not(Not) {}
+        HasInst(true), Not(Not) {}
+
+  FactOrCheck(DomTreeNode *DTN, Use *U)
+      : U(U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
+        HasInst(false), Not(false) {}
 
   static FactOrCheck getFact(DomTreeNode *DTN, Instruction *Inst,
                              bool Not = false) {
-    return FactOrCheck(DTN, Inst, false, Not);
+    return FactOrCheck(DTN, Inst, Not);
   }
 
-  static FactOrCheck getCheck(DomTreeNode *DTN, Instruction *Inst) {
-    return FactOrCheck(DTN, Inst, true, false);
+  static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) {
+    return FactOrCheck(DTN, U);
   }
 
-  bool isAssumeFact() const {
-    if (!IsCheck && isa<IntrinsicInst>(Inst)) {
-      assert(match(Inst, m_Intrinsic<Intrinsic::assume>()));
-      return true;
-    }
-    return false;
+  static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) {
+    return FactOrCheck(DTN, CI, false);
+
+  bool isCheck() const {
+    return !HasInst ||
+           match(Inst, m_Intrinsic<Intrinsic::ssub_with_overflow>());
   }
 
-  bool isConditionFact() const { return !IsCheck && isa<CmpInst>(Inst); }
+  Instruction *getContextInst() const {
+    if (HasInst)
+      return Inst;
+    return getContextInstForUse(*U);
+  }
+  Instruction *getInstructionToSimplify() const {
+    assert(isCheck());
+    if (HasInst)
+      return Inst;
+    // The use may have been simplified to a constant already.
+    return dyn_cast<Instruction>(*U);
+  }
+  bool isConditionFact() const { return !isCheck() && isa<CmpInst>(Inst); }
 };
 
 /// Keep state required to build worklist.
 struct State {
   DominatorTree &DT;
   SmallVector<FactOrCheck, 64> WorkList;
 
   State(DominatorTree &DT) : DT(DT) {}

 #endif
 
 void State::addInfoFor(BasicBlock &BB) {
   // True as long as long as the current instruction is guaranteed to execute.
   bool GuaranteedToExecute = true;
   // Queue conditions and assumes.
   for (Instruction &I : BB) {
     if (auto Cmp = dyn_cast<ICmpInst>(&I)) {
-      WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), Cmp));
+      for (Use &U : Cmp->uses()) {
+        auto *UserI = getContextInstForUse(U);
+        auto *DTN = DT.getNode(UserI->getParent());
+        if (!DTN)
+          continue;
+        WorkList.push_back(FactOrCheck::getCheck(DTN, &U));
+      }
       continue;
     }
 
     if (match(&I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
-      WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), &I));
+      WorkList.push_back(
+          FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));
       continue;
     }
 
     Value *Cond;
     // 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 (GuaranteedToExecute) {
static void generateReproducer(CmpInst *Cond, Module *M,
   CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));
   Entry->getTerminator()->setOperand(0, Cond);
   remapInstructionsInBlocks({Entry}, Old2New);
 
   assert(!verifyFunction(*F, &dbgs()));
 }
 
 static bool checkAndReplaceCondition(
-    CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule,
+    CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
+    Instruction *ContextInst, Module *ReproducerModule,
     ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT) {
   LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
 
   CmpInst::Predicate Pred = Cmp->getPredicate();
   Value *A = Cmp->getOperand(0);
   Value *B = Cmp->getOperand(1);
 
   auto R = Info.getConstraintForSolving(Pred, A, B);
LLVM_DEBUG({
       }
       dbgs() << " implied by dominating constraints\n";
       CSToUse.dump();
     });
 
     generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
     Constant *ConstantC = ConstantInt::getBool(
         CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);
-    Cmp->replaceUsesWithIf(ConstantC, [](Use &U) {
+    Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
+                                       ContextInst](Use &U) {
+      auto *UserI = getContextInstForUse(U);
+      auto *DTN = DT.getNode(UserI->getParent());
+      if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
+        return false;
+      if (UserI->getParent() == ContextInst->getParent() &&
+          UserI->comesBefore(ContextInst))
+        return false;
+
       // Conditions in an assume trivially simplify to true. Skip uses
       // in assume calls to not destroy the available information.
       auto *II = dyn_cast<IntrinsicInst>(U.getUser());
       return !II || II->getIntrinsicID() != Intrinsic::assume;
     });
     NumCondsRemoved++;
     return true;
   };
if (A.NumIn == B.NumIn) {
         bool NoConstOpA = HasNoConstOp(A);
         bool NoConstOpB = HasNoConstOp(B);
         return NoConstOpA < NoConstOpB;
       }
       if (A.isConditionFact())
         return true;
       if (B.isConditionFact())
         return false;
-      return A.Inst->comesBefore(B.Inst);
+      auto *InstA = A.getContextInst();
+      auto *InstB = B.getContextInst();
+      return InstA->comesBefore(InstB);
     }
     return A.NumIn < B.NumIn;
   });
 
   SmallVector<Instruction *> ToRemove;
 
   // Finally, process ordered worklist and eliminate implied conditions.
   SmallVector<StackEntry, 16> DFSInStack;
while (!DFSInStack.empty()) {
         dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),
                        Info.getValue2Index(E.IsSigned));
         dbgs() << "\n";
       });
       removeEntryFromStack(E, Info, ReproducerModule.get(), ReproducerCondStack,
                            DFSInStack);
     }
 
-    LLVM_DEBUG({
-      dbgs() << "Processing ";
-      if (CB.IsCheck)
-        dbgs() << "condition to simplify: " << *CB.Inst;
-      else
-        dbgs() << "fact to add to the system: " << *CB.Inst;
-      dbgs() << "\n";
-    });
+    LLVM_DEBUG(dbgs() << "Processing ");
 
     // For a block, check if any CmpInsts become known based on the current set
     // of constraints.
-    if (CB.IsCheck) {
-      if (auto *II = dyn_cast<WithOverflowInst>(CB.Inst)) {
+    if (CB.isCheck()) {
+      Instruction *Inst = CB.getInstructionToSimplify();
+      if (!Inst)
+        continue;
+      LLVM_DEBUG(dbgs() << "condition to simplify: " << *Inst << "\n");
+      if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {
         Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
-      } else if (auto *Cmp = dyn_cast<ICmpInst>(CB.Inst)) {
-        Changed |= checkAndReplaceCondition(Cmp, Info, ReproducerModule.get(),
-                                            ReproducerCondStack, S.DT);
+      } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
+        Changed |= checkAndReplaceCondition(
+            Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
+            ReproducerModule.get(), ReproducerCondStack, S.DT);
       }
       continue;
     }
 
+    LLVM_DEBUG(dbgs() << "fact to add to the system: " << *CB.Inst << "\n");
     ICmpInst::Predicate Pred;
     Value *A, *B;
     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)))) {
       if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
         LLVM_DEBUG(
             dbgs()
             << "Skip adding constraint because system has too many rows.\n");

llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ne i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i32 [[X]], 16
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_3]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[Z:%.*]], 0
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C_4]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C_4]], i1 true, i1 false
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i1 [ [[C_1]], [[ENTRY:%.*]] ], [ [[SEL]], [[THEN]] ]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
 entry:
   %c.1 = icmp ne i32 %x, 0
   %c.2 = icmp ne i32 %y, 0

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ne i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i32 [[X]], 16
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_3]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[Z:%.*]], 0
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C_4]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C_4]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[SEL]], label [[T_1:%.*]], label [[EXIT]]
 ; CHECK:       t.1:
-; CHECK-NEXT:    ret i1 [[C_1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i1 [ [[C_1]], [[ENTRY:%.*]] ], [ [[SEL]], [[THEN]] ]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
 entry:
   %c.1 = icmp ne i32 %x, 0
   %c.2 = icmp ne i32 %y, 0
   %c.3 = icmp eq i32 %x, 16

 define i1 @test_and_used_in_false_branch(i8 %x) {
 ; CHECK-LABEL: @test_and_used_in_false_branch(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[T_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    ret i1 [[T_1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 [[T_1]]
 ;
 
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %t.1 = icmp ugt i8 %x, 5
   %and = and i1 %c.1, %t.1

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i8 [[X]], 5
 ; CHECK-NEXT:    [[AND:%.*]] = or i1 [[C_1]], [[T_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 [[T_1]]
 ; CHECK:       else:
-; CHECK-NEXT:    ret i1 [[T_1]]
+; CHECK-NEXT:    ret i1 false
 ;
 
 entry:
   %c.1 = icmp ule i8 %x, 10
   %t.1 = icmp ule i8 %x, 5
   %and = or i1 %c.1, %t.1
   br i1 %and, label %then, label %else
 

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
 ; CHECK-NEXT:    [[AND:%.*]] = or i1 [[C_1]], [[T_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 [[T_1]]
 ; CHECK:       else:
-; CHECK-NEXT:    ret i1 [[T_1]]
+; CHECK-NEXT:    ret i1 false
 ;
 
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %t.1 = icmp ugt i8 %x, 5
   %and = or i1 %c.1, %t.1
   br i1 %and, label %then, label %else
 
 then:
   ret i1 %t.1
 
 else:
   ret i1 %t.1
 }

llvm/test/Transforms/ConstraintElimination/assumes.ll

;
   call void @llvm.assume(i1 %cmp.1)
   br label %exit
 
 exit:
   ret i1 %res.2
 }
 
 ; The information of from the assume can be used to simplify %t.2.
-; TODO
 define i1 @assume_single_bb_conditions_after_assume(i8 %a, i8 %b, i1 %c) {
 ; CHECK-LABEL: @assume_single_bb_conditions_after_assume(
 ; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw nsw i8 [[A:%.*]], 1
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i8 [[ADD_1]], [[B:%.*]]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i8 [[ADD_1]], [[B]]
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    call void @may_unwind()
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP_1]])
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[A]], [[B]]
-; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], true
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw nsw i8 [[A]], 2
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i8 [[ADD_2]], [[B]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[C_2]]
 ; CHECK-NEXT:    ret i1 [[RES_2]]
 ;
   %add.1 = add nsw nuw i8 %a, 1
   %cmp.1 = icmp ule i8 %add.1, %b
   %c.1 = icmp ule i8 %add.1, %b

 ; CHECK-LABEL: @all_uses_after_assume(
 ; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw nsw i8 [[A:%.*]], 1
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i8 [[ADD_1]], [[B:%.*]]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i8 [[ADD_1]], [[B]]
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[A]], [[B]]
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    call void @may_unwind()
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP_1]])
-; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], [[T_2]]
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw nsw i8 [[A]], 2
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i8 [[ADD_2]], [[B]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[C_2]]
 ; CHECK-NEXT:    ret i1 [[RES_2]]
 ;
   %add.1 = add nsw nuw i8 %a, 1
   %cmp.1 = icmp ule i8 %add.1, %b
   %c.1 = icmp ule i8 %add.1, %b

 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i16 [[A:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    store volatile float 0.000000e+00, ptr [[DST:%.*]], align 4
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i16 [[A]], 20
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[C_2]])
-; CHECK-NEXT:    ret i1 [[C_2]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %c.1 = icmp ult i16 %a, 10
   br i1 %c.1, label %then, label %else
 
 then:
   ret i1 0
 
 else:
   store volatile float 0.000000e+00, ptr %dst
   %c.2 = icmp eq i16 %a, 20
   tail call void @llvm.assume(i1 %c.2)
   ret i1 %c.2
 }

llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 [[X]], 1
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP1]])
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ [[CMP2]], [[IF]] ], [ false, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ true, [[IF]] ], [ false, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i1 [[PHI]]
 ;
 entry:
   %cmp2 = icmp sgt i8 %x, 0
   br i1 %c, label %if, label %join
 
 if:
   %cmp1 = icmp sgt i8 %x, 1

 ; CHECK-NEXT:    br i1 [[C_0:%.*]], label [[IF:%.*]], label [[JOIN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[X]], 1
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[THEN_1:%.*]], label [[JOIN]]
 ; CHECK:       then.1:
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ [[CMP2]], [[IF]] ], [ [[CMP2]], [[THEN_1]] ], [ false, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ [[CMP2]], [[IF]] ], [ true, [[THEN_1]] ], [ false, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i1 [[PHI]]
 ;
 entry:
   br i1 %c.0, label %if, label %join
 
 if:
   %cmp1 = icmp sgt i8 %x, 1
   %cmp2 = icmp sgt i8 %x, 1

 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[X]], 1
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[THEN_1:%.*]], label [[ELSE_1:%.*]]
 ; CHECK:       then.1:
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       else.1:
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ [[CMP2]], [[ELSE_1]] ], [ [[CMP2]], [[THEN_1]] ], [ false, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ false, [[ELSE_1]] ], [ true, [[THEN_1]] ], [ false, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i1 [[PHI]]
 ;
 entry:
   br i1 %c.0, label %if, label %join
 
 if:
   %cmp1 = icmp sgt i8 %x, 1
   %cmp2 = icmp sgt i8 %x, 1

llvm/test/Transforms/ConstraintElimination/monotonic-pointer-phis-crashes.ll

 ; CHECK-NEXT:    [[NODE_1:%.*]] = phi ptr [ [[START]], [[ENTRY:%.*]] ], [ null, [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp ne ptr [[NODE_1]], null
 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C_1]], label [[IF:%.*]], label [[LOOP_HEADER]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ne ptr [[B]], null
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_0]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[EXIT]]
 ; CHECK:       then:
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/ConstraintElimination/uses-in-different-blocks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
 
 define i1 @test_conds_single_use_in_different_blocks(i8 %x) {
 ; CHECK-LABEL: @test_conds_single_use_in_different_blocks(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i8 [[X]], 5
 ; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    ret i1 [[T_1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 [[C_2]]
 ;
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %t.1 = icmp ugt i8 %x, 5
   %c.2 = icmp ugt i8 %x, 5
   br i1 %c.1, label %then, label %else

 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[Y:%.*]], 5
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i8 [[Y]], [[X]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i8 [[Y]], 5
 ; CHECK-NEXT:    br i1 [[C_1]], label [[THEN_1:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then.1:
 ; CHECK-NEXT:    br i1 [[C_2]], label [[THEN_2:%.*]], label [[ELSE]]
 ; CHECK:       then.2:
-; CHECK-NEXT:    ret i1 [[T_1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 [[C_3]]
 ;
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %t.1 = icmp ugt i8 %y, 5
   %c.2 = icmp ugt i8 %y, %x
   %c.3 = icmp ugt i8 %y, 5