Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -523,8 +523,7 @@ /// (A) Optional isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, - bool InvertAPred = false, - unsigned Depth = 0, + bool LHSIsFalse = false, unsigned Depth = 0, AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -4393,7 +4393,7 @@ } Optional llvm::isImpliedCondition(const Value *LHS, const Value *RHS, - const DataLayout &DL, bool InvertAPred, + const DataLayout &DL, bool LHSIsFalse, unsigned Depth, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { @@ -4405,7 +4405,7 @@ assert(OpTy->getScalarType()->isIntegerTy(1)); // LHS ==> RHS by definition - if (!InvertAPred && LHS == RHS) + if (!LHSIsFalse && LHS == RHS) return true; if (OpTy->isVectorTy()) @@ -4413,15 +4413,40 @@ return None; assert(OpTy->isIntegerTy(1) && "implied by above"); - ICmpInst::Predicate APred, BPred; - Value *ALHS, *ARHS; Value *BLHS, *BRHS; + ICmpInst::Predicate BPred; + // We expect the RHS to be an icmp. + if (!match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS)))) + return None; - if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS))) || - !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS)))) + Value *ALHS, *ARHS; + ICmpInst::Predicate APred; + // The LHS can be an 'or', 'and', or 'icmp'. + if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS)))) { + // The remaining tests are all recursive, so bail out if we hit the limit. + if (Depth == MaxDepth) + return None; + // If the result of an 'or' is false, then we know both legs of the 'or' are + // false. Similarly, if the result of an 'and' is true, then we know both + // legs of the 'and' are true. + if ((LHSIsFalse && match(LHS, m_Or(m_Value(ALHS), m_Value(ARHS)))) || + (!LHSIsFalse && match(LHS, m_And(m_Value(ALHS), m_Value(ARHS))))) { + if (Optional Implication = isImpliedCondition( + ALHS, RHS, DL, LHSIsFalse, Depth + 1, AC, CxtI, DT)) + return Implication; + if (Optional Implication = isImpliedCondition( + ARHS, RHS, DL, LHSIsFalse, Depth + 1, AC, CxtI, DT)) + return Implication; + return None; + } return None; + } + // All of the below logic assumes both LHS and RHS are icmps. + assert(isa(LHS) && isa(RHS) && "Expected icmps."); - if (InvertAPred) + // The rest of the logic assumes the LHS condition is true. If that's not the + // case, invert the predicate to make it so. + if (LHSIsFalse) APred = CmpInst::getInversePredicate(APred); // Can we infer anything when the two compares have matching operands? Index: test/Transforms/InstCombine/select-implied.ll =================================================================== --- test/Transforms/InstCombine/select-implied.ll +++ test/Transforms/InstCombine/select-implied.ll @@ -121,3 +121,44 @@ declare void @foo(i32) declare i32 @bar(i32) + +; CHECK-LABEL: @test_and +; CHECK: tpath: +; CHECK-NOT: select +; CHECK: ret i32 313 +define i32 @test_and(i32 %a, i32 %b) { +entry: + %cmp1 = icmp ne i32 %a, 0 + %cmp2 = icmp ne i32 %b, 0 + %and = and i1 %cmp1, %cmp2 + br i1 %and, label %tpath, label %end + +tpath: + %cmp3 = icmp eq i32 %a, 0 ;; <-- implied false + %c = select i1 %cmp3, i32 0, i32 313 + ret i32 %c + +end: + ret i32 0 +} + +; cmp1 and cmp2 are false on the 'fpath' path and thus cmp3 is true. +; CHECK-LABEL: @test_or1 +; CHECK: fpath: +; CHECK-NOT: select +; CHECK: ret i32 37 +define i32 @test_or1(i32 %a, i32 %b) { +entry: + %cmp1 = icmp eq i32 %a, 0 + %cmp2 = icmp eq i32 %b, 0 + %or = or i1 %cmp1, %cmp2 + br i1 %or, label %end, label %fpath + +fpath: + %cmp3 = icmp ne i32 %a, 0 ;; <-- implied true + %c = select i1 %cmp3, i32 37, i32 0 + ret i32 %c + +end: + ret i32 0 +} Index: test/Transforms/SimplifyCFG/implied-and-or.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/implied-and-or.ll @@ -0,0 +1,183 @@ +; RUN: opt %s -S -simplifycfg | FileCheck %s + +declare void @foo() +declare void @bar() + + +; CHECK-LABEL: @test_and1 +; CHECK: taken: +; CHECK-NOT: cmp3 +; CHECK: call void @bar() +; CHECK-NEXT: call void @foo() +; CHECK: ret +define void @test_and1(i32 %a, i32 %b) { +entry: + %cmp1 = icmp eq i32 %a, 0 + %cmp2 = icmp eq i32 %b, 0 + %and = and i1 %cmp1, %cmp2 + br i1 %and, label %taken, label %end + +taken: + call void @bar() + %cmp3 = icmp eq i32 %a, 0 ;; <-- implied true + br i1 %cmp3, label %if.then, label %end + +if.then: + call void @foo() + br label %end + +end: + ret void +} + +; We can't infer anything if the result of the 'and' is false +; CHECK-LABEL: @test_and2 +; CHECK: taken: +; CHECK: call void @bar() +; CHECK: %cmp3 +; CHECK: br i1 %cmp3 +; CHECK: if.then: +; CHECK: call void @foo() +; CHECK: ret +define void @test_and2(i32 %a, i32 %b) { +entry: + %cmp1 = icmp eq i32 %a, 0 + %cmp2 = icmp eq i32 %b, 0 + %and = and i1 %cmp1, %cmp2 + br i1 %and, label %end, label %taken + +taken: + call void @bar() + %cmp3 = icmp eq i32 %a, 0 + br i1 %cmp3, label %if.then, label %end + +if.then: + call void @foo() + br label %end + +end: + ret void +} + +; CHECK-LABEL: @test_or1 +; CHECK: taken: +; CHECK-NOT: cmp3 +; CHECK: call void @bar() +; CHECK-NEXT: call void @foo() +; CHECK: ret +define void @test_or1(i32 %a, i32 %b) { +entry: + %cmp1 = icmp eq i32 %a, 0 + %cmp2 = icmp eq i32 %b, 0 + %or = or i1 %cmp1, %cmp2 + br i1 %or, label %end, label %taken + +taken: + call void @bar() + %cmp3 = icmp ne i32 %a, 0 ;; <-- implied true + br i1 %cmp3, label %if.then, label %end + +if.then: + call void @foo() + br label %end + +end: + ret void +} + +; We can't infer anything if the result of the 'or' is true +; CHECK-LABEL: @test_or2 +; CHECK: call void @bar() +; CHECK: %cmp3 +; CHECK: br i1 %cmp3 +; CHECK: if.then: +; CHECK: call void @foo() +; CHECK: ret +define void @test_or2(i32 %a, i32 %b) { +entry: + %cmp1 = icmp eq i32 %a, 0 + %cmp2 = icmp eq i32 %b, 0 + %or = or i1 %cmp1, %cmp2 + br i1 %or, label %taken, label %end + +taken: + call void @bar() + %cmp3 = icmp eq i32 %a, 0 + br i1 %cmp3, label %if.then, label %end + +if.then: + call void @foo() + br label %end + +end: + ret void +} + +; We can recurse a tree of 'and' or 'or's. +; CHECK-LABEL: @test_and_recurse1 +; CHECK: taken: +; CHECK-NEXT: call void @bar() +; CHECK-NEXT: call void @foo() +; CHECK-NEXT: br label %end +; CHECK: ret +define void @test_and_recurse1(i32 %a, i32 %b, i32 %c) { +entry: + %cmpa = icmp eq i32 %a, 0 + %cmpb = icmp eq i32 %b, 0 + %cmpc = icmp eq i32 %c, 0 + %and1 = and i1 %cmpa, %cmpb + %and2 = and i1 %and1, %cmpc + br i1 %and2, label %taken, label %end + +taken: + call void @bar() + %cmp3 = icmp eq i32 %a, 0 + br i1 %cmp3, label %if.then, label %end + +if.then: + call void @foo() + br label %end + +end: + ret void +} + +; Check to make sure we don't recurse too deep. +; CHECK-LABEL: @test_and_recurse2 +; CHECK: taken: +; CHECK-NEXT: call void @bar() +; CHECK-NEXT: %cmp3 = icmp eq i32 %a, 0 +; CHECK-NEXT: br i1 %cmp3, label %if.then, label %end +; CHECK: ret +define void @test_and_recurse2(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f, + i32 %g, i32 %h) { +entry: + %cmpa = icmp eq i32 %a, 0 + %cmpb = icmp eq i32 %b, 0 + %cmpc = icmp eq i32 %c, 0 + %cmpd = icmp eq i32 %d, 0 + %cmpe = icmp eq i32 %e, 0 + %cmpf = icmp eq i32 %f, 0 + %cmpg = icmp eq i32 %g, 0 + %cmph = icmp eq i32 %h, 0 + %and1 = and i1 %cmpa, %cmpb + %and2 = and i1 %and1, %cmpc + %and3 = and i1 %and2, %cmpd + %and4 = and i1 %and3, %cmpe + %and5 = and i1 %and4, %cmpf + %and6 = and i1 %and5, %cmpg + %and7 = and i1 %and6, %cmph + br i1 %and7, label %taken, label %end + +taken: + call void @bar() + %cmp3 = icmp eq i32 %a, 0 ; <-- can be implied true + br i1 %cmp3, label %if.then, label %end + +if.then: + call void @foo() + br label %end + +end: + ret void +}