Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -436,16 +436,18 @@ /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20). ConstantRange getConstantRangeFromMetadata(MDNode &RangeMD); - /// Return true if RHS is known to be implied by LHS. A & B must be i1 - /// (boolean) values or a vector of such values. Note that the truth table for - /// implication is the same as <=u on i1 values (but not <=s!). The truth - /// table for both is: + /// Return true if RHS is known to be implied by LHS. The implication may be + /// either true or false depending on what is returned in ImpliedTrue. + /// A & B must be i1 (boolean) values or a vector of such values. Note that + /// the truth table for implication is the same as <=u on i1 values (but not + /// <=s!). The truth table for both is: /// | T | F (B) /// T | T | F /// F | T | T /// (A) - bool isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL, - unsigned Depth = 0, AssumptionCache *AC = nullptr, + bool isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue, + const DataLayout &DL, unsigned Depth = 0, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); } // end namespace llvm Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ lib/Analysis/InstructionSimplify.cpp @@ -2131,14 +2131,16 @@ if (match(RHS, m_Zero())) return LHS; break; - case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_UGE: { // X >=u 1 -> X if (match(RHS, m_One())) return LHS; - if (isImpliedCondition(RHS, LHS, Q.DL)) + bool ImpliedTrue; + if (isImpliedCondition(RHS, LHS, ImpliedTrue, Q.DL) && ImpliedTrue) return getTrue(ITy); break; - case ICmpInst::ICMP_SGE: + } + case ICmpInst::ICMP_SGE: { /// For signed comparison, the values for an i1 are 0 and -1 /// respectively. This maps into a truth table of: /// LHS | RHS | LHS >=s RHS | LHS implies RHS @@ -2146,9 +2148,11 @@ /// 0 | 1 | 1 (0 >= -1) | 1 /// 1 | 0 | 0 (-1 >= 0) | 0 /// 1 | 1 | 1 (-1 >= -1) | 1 - if (isImpliedCondition(LHS, RHS, Q.DL)) + bool ImpliedTrue; + if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue) return getTrue(ITy); break; + } case ICmpInst::ICMP_SLT: // X X if (match(RHS, m_Zero())) @@ -2159,11 +2163,13 @@ if (match(RHS, m_One())) return LHS; break; - case ICmpInst::ICMP_ULE: - if (isImpliedCondition(LHS, RHS, Q.DL)) + case ICmpInst::ICMP_ULE: { + bool ImpliedTrue; + if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue) return getTrue(ITy); break; } + } } // If we are comparing with zero then try hard since this is a common case. Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -3788,9 +3788,112 @@ } } -bool llvm::isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL, - unsigned Depth, AssumptionCache *AC, - const Instruction *CxtI, +/// Return true if "icmp2 Pred op1 op2" is known to be implied by "icmp1 Pred +/// op1 op2". The implication may be either true or false depending on the +/// return value of ImpliedTrue. +static bool isImpliedCondMatchingOperands(CmpInst::Predicate APred, Value *ALHS, + Value *ARHS, CmpInst::Predicate BPred, + Value *BLHS, Value *BRHS, + bool &ImpliedTrue) { + // The operands of the two compares must match. + bool IsMatchingOps = (ALHS == BLHS && ARHS == BRHS); + bool IsSwappedOps = (ALHS == BRHS && ARHS == BLHS); + if (!IsMatchingOps && !IsSwappedOps) + return false; + + // If the operands are swapped and the predicates match we can infer the + // second condition is false because if, for example, A > B is true, then B > + // A must be false. + if (IsSwappedOps && APred == BPred) { + switch (APred) { + default: + break; + case CmpInst::ICMP_UGT: + case CmpInst::ICMP_ULT: + case CmpInst::ICMP_SGT: + case CmpInst::ICMP_SLT: + ImpliedTrue = false; + return true; + } + } + + // If the operands are swapped and the swapped predicates match, then we know + // the first condition implies the second is true. + if (IsSwappedOps && APred == ICmpInst::getSwappedPredicate(BPred)) { + ImpliedTrue = true; + return true; + } + + // The next bit of logic is the same for unsigned and signed comparison. + // Therefore, unconditionally convert the predicates to their unsigned + // equivalent to reduce the amount of logic needed. This is safe because + // we've already verified that the sign of the predicates match. + CmpInst::Predicate UnsignedAPred = ICmpInst::getUnsignedPredicate(APred); + CmpInst::Predicate UnsignedBPred = ICmpInst::getUnsignedPredicate(BPred); + + // The next bit of logic assumes the operands matched, so swap the predicate + // if necessary. + if (IsSwappedOps) + UnsignedBPred = ICmpInst::getSwappedPredicate(UnsignedBPred); + + switch (UnsignedAPred) { + default: + break; + case CmpInst::ICMP_EQ: + if (UnsignedBPred == CmpInst::ICMP_UGT || // A == B implies A > B is false + UnsignedBPred == CmpInst::ICMP_ULT || // A == B implies A < B is false + UnsignedBPred == CmpInst::ICMP_NE) { // A == B implies A != B is false + ImpliedTrue = false; + return true; + } + break; + case CmpInst::ICMP_NE: + if (UnsignedBPred == CmpInst::ICMP_EQ) { // A != B implies A == B is false + ImpliedTrue = false; + return true; + } + break; + case CmpInst::ICMP_UGT: + if (UnsignedBPred == CmpInst::ICMP_EQ || // A > B implies A == B is false. + UnsignedBPred == CmpInst::ICMP_ULE) { // A > B implies A <= B is false. + ImpliedTrue = false; + return true; + } + if (UnsignedBPred == CmpInst::ICMP_NE) { // A > B implies A != B is true. + ImpliedTrue = true; + return true; + } + break; + case CmpInst::ICMP_ULT: + if (UnsignedBPred == CmpInst::ICMP_EQ || // A < B implies A == B is false. + UnsignedBPred == CmpInst::ICMP_UGE) { // A < B implies A >= B is false. + ImpliedTrue = false; + return true; + } + if (UnsignedBPred == CmpInst::ICMP_NE) { // A < B implies A != B is true. + ImpliedTrue = true; + return true; + } + break; + case CmpInst::ICMP_UGE: + if (UnsignedBPred == CmpInst::ICMP_ULT) { // A >= B implies A < B is false. + ImpliedTrue = false; + return true; + } + break; + case CmpInst::ICMP_ULE: + if (UnsignedBPred == CmpInst::ICMP_UGT) { // A <= B implies A > B is false. + ImpliedTrue = false; + return true; + } + break; + } + return false; +} + +bool llvm::isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue, + const DataLayout &DL, unsigned Depth, + AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { assert(LHS->getType() == RHS->getType() && "mismatched type"); Type *OpTy = LHS->getType(); @@ -3812,9 +3915,21 @@ !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS)))) return false; - if (APred == BPred) + /// The predicates must match sign or at least one of them must be an equality + /// comparison (which is signless). + if (ICmpInst::isSigned(APred) != ICmpInst::isSigned(BPred) && + !ICmpInst::isEquality(APred) && !ICmpInst::isEquality(BPred)) + return false; + + if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS, + ImpliedTrue)) + return true; + + if (APred == BPred) { + ImpliedTrue = true; return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC, CxtI, DT); + } return false; } Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -928,12 +928,16 @@ if (!PBI || !PBI->isConditional() || PBI->getSuccessor(0) != CurrentBB) return false; - if (isImpliedCondition(PBI->getCondition(), Cond, DL)) { + bool ImpliedTrue; + if (isImpliedCondition(PBI->getCondition(), Cond, ImpliedTrue, DL) && + ImpliedTrue) { BI->getSuccessor(1)->removePredecessor(BB); BranchInst::Create(BI->getSuccessor(0), BI); BI->eraseFromParent(); return true; } + // FIXME: If ImpliedTrue == false we should unconditionally branch to the + // false edge. CurrentBB = CurrentPred; CurrentPred = CurrentBB->getSinglePredecessor(); } Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -2722,13 +2722,17 @@ // If BI is reached from the true path of PBI and PBI's condition implies // BI's condition, we know the direction of the BI branch. + bool ImpliedTrue; if (PBI->getSuccessor(0) == BI->getParent() && - isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL) && + isImpliedCondition(PBI->getCondition(), BI->getCondition(), ImpliedTrue, + DL) && PBI->getSuccessor(0) != PBI->getSuccessor(1) && BB->getSinglePredecessor()) { // Turn this into a branch on constant. auto *OldCond = BI->getCondition(); - BI->setCondition(ConstantInt::getTrue(BB->getContext())); + ConstantInt *CI = ImpliedTrue ? ConstantInt::getTrue(BB->getContext()) + : ConstantInt::getFalse(BB->getContext()); + BI->setCondition(CI); RecursivelyDeleteTriviallyDeadInstructions(OldCond); return true; // Nuke the branch on constant. } Index: test/Transforms/SimplifyCFG/implied-cond-matching.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/implied-cond-matching.ll @@ -0,0 +1,310 @@ +; RUN: opt %s -S -simplifycfg | FileCheck %s + +; Test same condition with swapped operands. +; void test_swapped_ops(unsigned a, unsigned b) { +; if (a > b) { +; if (b > a) <- always false +; dead(); +; alive(); +; } +; } +; +; CHECK-LABEL: @test_swapped_ops +; CHECK-NOT: call void @dead() +; CHECK: call void @alive() +; CHECK: ret +define void @test_swapped_ops(i32 %a, i32 %b) { +entry: + %cmp = icmp ugt i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + %cmp1 = icmp ugt i32 %b, %a + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @dead() + br label %if.end + +if.end: + call void @alive() + br label %if.end3 + +if.end3: + ret void +} + +; void test_swapped_pred(unsigned a, unsigned b) { +; if (a > b) { +; alive(); +; if (b < a) <- always true; remove branch +; alive(); +; } +; } +; +; CHECK-LABEL: @test_swapped_pred +; CHECK: call void @alive() +; CHECK-NEXT: call void @alive() +; CHECK: ret +define void @test_swapped_pred(i32 %a, i32 %b) { +entry: + %cmp = icmp ugt i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + call void @alive() + %cmp1 = icmp ult i32 %b, %a + br i1 %cmp1, label %if.then2, label %if.end3 + +if.then2: + call void @alive() + br label %if.end3 + +if.end3: + ret void +} + +; A == B implies A > B is false +; A == B implies A < B is false +; A == B implies A != B is false +; CHECK-LABEL: @test_eq +; CHECK-NOT: dead +; CHECK: ret void +define void @test_eq(i32 %a, i32 %b) { +entry: + %cmp = icmp eq i32 %a, %b + br i1 %cmp, label %if.end, label %if.end9 + +if.end: + %cmp3 = icmp ugt i32 %a, %b + br i1 %cmp3, label %if.then4, label %if.end5 + +if.then4: + call void @dead() + br label %if.end5 + +if.end5: + %cmp6 = icmp ult i32 %a, %b + br i1 %cmp6, label %if.then7, label %if.end8 + +if.then7: + call void @dead() + br label %if.end8 + +if.end8: + br label %if.end9 + +if.end9: + ret void +} + +; A != B implies A == B is false +; CHECK-LABEL: @test_ne +; CHECK-NOT: dead +; CHECK: ret void +define void @test_ne(i32 %a, i32 %b) { +entry: + %cmp = icmp ne i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + %cmp1 = icmp eq i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @dead() + br label %if.end + +if.end: + br label %if.end3 + +if.end3: + ret void +} + +; A > B implies A == B is false. +; A > B implies A <= B is false. +; A > B implies A != B is true. +; CHECK-LABEL: @test_gt +; CHECK-NOT: dead +; CHECK: alive +; CHECK-NOT: dead +; CHECK: ret void +define void @test_gt(i32 %a, i32 %b) { +entry: + %cmp = icmp ugt i32 %a, %b + br i1 %cmp, label %if.then, label %if.end9 + +if.then: + %cmp1 = icmp eq i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @dead() + br label %if.end + +if.end: + %cmp3 = icmp ule i32 %a, %b + br i1 %cmp3, label %if.then4, label %if.end5 + +if.then4: + call void @dead() + br label %if.end5 + +if.end5: + %cmp6 = icmp ne i32 %a, %b + br i1 %cmp6, label %if.then7, label %if.end8 + +if.then7: + call void @alive() + br label %if.end8 + +if.end8: + br label %if.end9 + +if.end9: + ret void +} + +; A < B implies A == B is false. +; A < B implies A >= B is false. +; A < B implies A != B is true. +; CHECK-LABEL: @test_lt +; CHECK-NOT: dead +; CHECK: alive +; CHECK-NOT: dead +; CHECK: ret void +define void @test_lt(i32 %a, i32 %b) { +entry: + %cmp = icmp ult i32 %a, %b + br i1 %cmp, label %if.then, label %if.end9 + +if.then: + %cmp1 = icmp eq i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @dead() + br label %if.end + +if.end: + %cmp3 = icmp ult i32 %a, %b + br i1 %cmp3, label %if.end5, label %if.then4 + +if.then4: + call void @dead() + br label %if.end5 + +if.end5: + %cmp6 = icmp eq i32 %a, %b + br i1 %cmp6, label %if.end8, label %if.then7 + +if.then7: + call void @alive() + br label %if.end8 + +if.end8: + br label %if.end9 + +if.end9: + ret void +} + +; A >= B implies A < B is false. +; CHECK-LABEL: @test_ge +; CHECK-NOT: dead +; CHECK: ret void +define void @test_ge(i32 %a, i32 %b) { +entry: + %cmp = icmp uge i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + %cmp1 = icmp ult i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @dead() + br label %if.end + +if.end: + br label %if.end3 + +if.end3: + ret void +} + +; A <= B implies A > B is false. +; CHECK-LABEL: @test_le +; CHECK-NOT: dead +; CHECK: ret void +define void @test_le(i32 %a, i32 %b) { +entry: + %cmp = icmp ule i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + %cmp1 = icmp ugt i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @dead() + br label %if.end + +if.end: + br label %if.end3 + +if.end3: + ret void +} + +; A u<= B does not imply A s> B is false. +; CHECK-LABEL: @test_ule_sgt_unsafe +; CHECK: alive +; CHECK: ret void +define void @test_ule_sgt_unsafe(i32 %a, i32 %b) { +entry: + %cmp = icmp ule i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + %cmp1 = icmp sgt i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @alive() + br label %if.end + +if.end: + br label %if.end3 + +if.end3: + ret void +} + +; A u> B does not imply B s> A is false. +; CHECK-LABEL: @test_ugt_sgt_unsafe +; CHECK: alive +; CHECK: ret void +define void @test_ugt_sgt_unsafe(i32 %a, i32 %b) { +entry: + %cmp = icmp ugt i32 %a, %b + br i1 %cmp, label %if.then, label %if.end3 + +if.then: + %cmp1 = icmp sgt i32 %b, %a + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: + call void @alive() + br label %if.end + +if.end: + br label %if.end3 + +if.end3: + ret void +} + +declare void @dead() +declare void @alive()