diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -997,10 +997,9 @@ assert(!verifyFunction(*F, &dbgs())); } -static bool checkAndReplaceCondition( - CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, - Instruction *User, Module *ReproducerModule, - ArrayRef ReproducerCondStack, DominatorTree &DT) { +static std::optional checkCondition(CmpInst *Cmp, ConstraintInfo &Info, + unsigned NumIn, unsigned NumOut, + Instruction *User) { LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n"); CmpInst::Predicate Pred = Cmp->getPredicate(); @@ -1010,7 +1009,7 @@ auto R = Info.getConstraintForSolving(Pred, A, B); if (R.empty() || !R.isValid(Info)){ LLVM_DEBUG(dbgs() << " failed to decompose condition\n"); - return false; + return std::nullopt; } auto &CSToUse = Info.getCS(R.IsSigned); @@ -1025,12 +1024,12 @@ CSToUse.popLastConstraint(); }); - auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) { + if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) { if (!DebugCounter::shouldExecute(EliminatedCounter)) - return false; + return std::nullopt; LLVM_DEBUG({ - if (IsTrue) { + if (*ImpliedCondition) { dbgs() << "Condition " << *Cmp; } else { auto InversePred = Cmp->getInversePredicate(); @@ -1040,7 +1039,17 @@ dbgs() << " implied by dominating constraints\n"; CSToUse.dump(); }); + return ImpliedCondition; + } + + return std::nullopt; +} +static bool checkAndReplaceCondition( + CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, + Instruction *User, Module *ReproducerModule, + ArrayRef ReproducerCondStack, DominatorTree &DT) { + auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) { generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT); Constant *ConstantC = ConstantInt::getBool( CmpInst::makeCmpResultType(Cmp->getType()), IsTrue); @@ -1062,9 +1071,8 @@ return true; }; - if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) + if (auto ImpliedCondition = checkCondition(Cmp, Info, NumIn, NumOut, User)) return ReplaceCmpWithConstant(Cmp, *ImpliedCondition); - return false; } @@ -1084,6 +1092,44 @@ ReproducerCondStack.pop_back(); } +/// Check if the first condition for an AND implies the second. +static bool checkAndSecondOpImpliedByFirst( + FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, + SmallVectorImpl &ReproducerCondStack, + SmallVectorImpl &DFSInStack) { + CmpInst::Predicate Pred; + Value *A, *B; + Instruction *And = CB.getContextInst(); + if (!match(And->getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B)))) + return false; + unsigned OldSize = DFSInStack.size(); + + // Optimistically add fact from first condition. + Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); + if (OldSize == DFSInStack.size()) + return false; + + bool Changed = false; + // Check if the second condition can be simplified now. + if (auto ImpliedCondition = + checkCondition(cast(And->getOperand(1)), Info, CB.NumIn, + CB.NumOut, CB.getContextInst())) { + if (*ImpliedCondition) + And->setOperand(1, ConstantInt::getTrue(And->getType())); + else + And->setOperand(1, ConstantInt::getFalse(And->getType())); + Changed = true; + } + + // Remove entries again. + while (OldSize < DFSInStack.size()) { + StackEntry E = DFSInStack.back(); + removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack, + DFSInStack); + } + return Changed; +} + void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, unsigned NumOut, SmallVectorImpl &DFSInStack) { @@ -1285,15 +1331,21 @@ if (auto *II = dyn_cast(Inst)) { Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); } else if (auto *Cmp = dyn_cast(Inst)) { - Changed |= checkAndReplaceCondition( + bool Simplified = checkAndReplaceCondition( Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(), ReproducerModule.get(), ReproducerCondStack, S.DT); + if (!Simplified && match(CB.getContextInst(), + m_LogicalAnd(m_Value(), m_Specific(Inst)))) { + Simplified = + checkAndSecondOpImpliedByFirst(CB, Info, ReproducerModule.get(), + ReproducerCondStack, DFSInStack); + } + Changed |= Simplified; } continue; } LLVM_DEBUG(dbgs() << "fact to add to the system: " << *CB.Inst << "\n"); - ; ICmpInst::Predicate Pred; Value *A, *B; Value *Cmp = CB.Inst; diff --git a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll --- a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll +++ b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll @@ -6,7 +6,7 @@ ; 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: [[AND:%.*]] = and i1 [[C_1]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: ret i1 false @@ -31,7 +31,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10 ; CHECK-NEXT: [[T_1:%.*]] = icmp ugt i8 [[X]], 5 -; CHECK-NEXT: [[AND:%.*]] = select i1 [[C_1]], i1 [[T_1]], i1 false +; CHECK-NEXT: [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: ret i1 false @@ -55,7 +55,7 @@ ; CHECK-LABEL: @test_same_cond_for_and( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10 -; CHECK-NEXT: [[AND:%.*]] = and i1 [[C_1]], [[C_1]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[C_1]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: ret i1 false @@ -78,7 +78,7 @@ ; CHECK-LABEL: @test_same_cond_for_and_select_form( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10 -; CHECK-NEXT: [[AND:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false +; CHECK-NEXT: [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: ret i1 false @@ -325,7 +325,7 @@ ; 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: [[AND:%.*]] = and i1 [[C_1]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: ret i1 true diff --git a/llvm/test/Transforms/ConstraintElimination/and.ll b/llvm/test/Transforms/ConstraintElimination/and.ll --- a/llvm/test/Transforms/ConstraintElimination/and.ll +++ b/llvm/test/Transforms/ConstraintElimination/and.ll @@ -459,7 +459,7 @@ ; CHECK-NEXT: [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]] ; CHECK-NEXT: [[C_3:%.*]] = icmp ule i4 3, [[X]] ; CHECK-NEXT: [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]] -; CHECK-NEXT: [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false +; CHECK-NEXT: [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false ; CHECK-NEXT: [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false ; CHECK-NEXT: [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false ; CHECK-NEXT: br i1 [[AND_3]], label [[BB1:%.*]], label [[EXIT:%.*]] @@ -546,7 +546,7 @@ ; CHECK-NEXT: [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]] ; CHECK-NEXT: [[C_3:%.*]] = icmp ule i4 3, [[X]] ; CHECK-NEXT: [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]] -; CHECK-NEXT: [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false +; CHECK-NEXT: [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false ; CHECK-NEXT: [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false ; CHECK-NEXT: [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false ; CHECK-NEXT: [[AND_4:%.*]] = select i1 [[AND_3]], i1 true, i1 false diff --git a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll --- a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll +++ b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll @@ -616,7 +616,7 @@ ; CHECK: step.check: ; CHECK-NEXT: [[STEP_POS:%.*]] = icmp sge i16 [[STEP:%.*]], 0 ; CHECK-NEXT: [[STEP_SLT_N:%.*]] = icmp slt i16 [[STEP]], [[N]] -; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_SLT_N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], false ; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] ; CHECK: ptr.check: ; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i16 [[STEP]] diff --git a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll --- a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll +++ b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll @@ -36,7 +36,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5 ; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_UGE]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4 @@ -65,7 +65,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5 ; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_UGE]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4 @@ -98,7 +98,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5 ; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_UGE]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: ; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4