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 @@ -642,6 +642,11 @@ return false; } + bool isAndImpliedCheck() const { + return IsCheck && (Inst->getOpcode() == Instruction::And || + Inst->getOpcode() == Instruction::Select); + } + bool isConditionFact() const { return !IsCheck && isa(Inst); } }; @@ -674,6 +679,13 @@ } #endif +static Instruction *isLogicalAndOfICmps(Value *V) { + CmpInst::Predicate Pred; + if (match(V, m_LogicalAnd(m_ICmp(Pred, m_Value(), m_Value()), + m_ICmp(Pred, m_Value(), m_Value())))) + return cast(V); + return nullptr; +} void State::addInfoFor(BasicBlock &BB) { // True as long as long as the current instruction is guaranteed to execute. bool GuaranteedToExecute = true; @@ -711,6 +723,13 @@ return; Value *Cond = Br->getCondition(); + auto *And = isLogicalAndOfICmps(Cond); + if (And && And->getOperand(0) != And->getOperand(1)) { + + BasicBlock *Successor = Br->getSuccessor(0); + if (canAddSuccessor(BB, Successor)) + WorkList.push_back(FactOrCheck::getCheck(DT.getNode(Successor), And)); + } // If the condition is a chain of ORs/AND and the successor only has the // current block as predecessor, queue conditions for the successor. @@ -922,7 +941,8 @@ static bool checkAndReplaceCondition( CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule, - ArrayRef ReproducerCondStack, DominatorTree &DT) { + ArrayRef ReproducerCondStack, DominatorTree &DT, + std::optional> ShouldReplace = std::nullopt) { LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n"); CmpInst::Predicate Pred = Cmp->getPredicate(); @@ -959,7 +979,9 @@ generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT); Constant *TrueC = ConstantInt::getTrue(CmpInst::makeCmpResultType(Cmp->getType())); - Cmp->replaceUsesWithIf(TrueC, [](Use &U) { + Cmp->replaceUsesWithIf(TrueC, [&ShouldReplace](Use &U) { + if (ShouldReplace && !(*ShouldReplace)(U)) + 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(U.getUser()); @@ -1003,6 +1025,43 @@ 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, DominatorTree &DT, + SmallVectorImpl &DFSInStack) { + CmpInst::Predicate Pred; + Value *A, *B; + if (!match(CB.Inst->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; + + // Check if the second condition can be simplified now. + bool Changed = checkAndReplaceCondition( + cast(CB.Inst->getOperand(1)), Info, ReproducerModule, + ReproducerCondStack, DT, [&CB, &DT](Use &U) { + Instruction *User = cast(U.getUser()); + if (User == CB.Inst) + return true; + auto *DTN = DT.getNode(User->getParent()); + return DTN->getDFSNumIn() >= CB.NumIn && + DTN->getDFSNumOut() <= CB.NumOut; + }); + + // 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) { @@ -1155,6 +1214,13 @@ bool NoConstOpB = HasNoConstOp(B); return NoConstOpA < NoConstOpB; } + + // AndImpliedChecks appear first in the block. + if (A.isAndImpliedCheck()) + return true; + if (B.isAndImpliedCheck()) + return false; + if (A.isConditionFact()) return true; if (B.isConditionFact()) @@ -1207,6 +1273,10 @@ } else if (auto *Cmp = dyn_cast(CB.Inst)) { Changed |= checkAndReplaceCondition(Cmp, Info, ReproducerModule.get(), ReproducerCondStack, S.DT); + } else if (isLogicalAndOfICmps(CB.Inst)) { + Changed |= checkAndSecondOpImpliedByFirst( + CB, Info, ReproducerModule.get(), ReproducerCondStack, S.DT, + DFSInStack); } continue; } 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 @@ -236,10 +236,10 @@ ; 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]] 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]]