Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -517,6 +517,13 @@ return Result; } + /// Find all of the conditions that dominate BB up to a max search depth of \p + /// Limit. + bool + findDominatingConditions(const BasicBlock *BB, + SmallVectorImpl> &DomConds, + unsigned Limit = 1); + /// Return true if RHS is known to be implied true by LHS. Return false if /// RHS is known to be implied false by LHS. Otherwise, return None if no /// implication can be made. Index: include/llvm/IR/BasicBlock.h =================================================================== --- include/llvm/IR/BasicBlock.h +++ include/llvm/IR/BasicBlock.h @@ -226,6 +226,15 @@ static_cast(this)->getUniquePredecessor()); } + /// \brief Return the immediate dominator of this block. Otherwise return a + /// null pointer. Unlike getSinglePredecessor this function is able to walk + /// past if-then (hammocks) and if-then-else (diamond) statements. + const BasicBlock *getIDom() const; + BasicBlock *getIDom() { + return const_cast( + static_cast(this)->getIDom()); + } + /// \brief Return the successor of this block if it has a single successor. /// Otherwise return a null pointer. /// Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -4306,6 +4306,32 @@ LHS, RHS); } +bool llvm::findDominatingConditions( + const BasicBlock *BB, SmallVectorImpl> &DomConds, + unsigned Limit) { + assert(DomConds.empty() && "Expected an empty vector!"); + + unsigned Iter = 0; + const BasicBlock *CurrentBB = BB; + const BasicBlock *CurrentIDom = BB->getIDom(); + while (CurrentIDom && Iter++ < Limit) { + if (CurrentIDom == CurrentBB->getSinglePredecessor()) { + auto *DomBI = dyn_cast(CurrentIDom->getTerminator()); + if (DomBI && DomBI->isConditional()) { + assert((DomBI->getSuccessor(0) == CurrentBB || + DomBI->getSuccessor(1) == CurrentBB) && + "Unexpected CFG!"); + Value *Condition = DomBI->getCondition(); + bool TrueDest = DomBI->getSuccessor(0) == CurrentBB; + DomConds.push_back(std::make_pair(Condition, TrueDest)); + } + } + CurrentBB = CurrentIDom; + CurrentIDom = CurrentBB->getIDom(); + } + return !DomConds.empty(); +} + /// Return true if "icmp Pred LHS RHS" is always true. static bool isTruePredicate(CmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const DataLayout &DL, Index: lib/IR/BasicBlock.cpp =================================================================== --- lib/IR/BasicBlock.cpp +++ lib/IR/BasicBlock.cpp @@ -241,6 +241,36 @@ return PredBB; } +const BasicBlock *BasicBlock::getIDom() const { + const BasicBlock *CurrentPred = this->getSinglePredecessor(); + if (CurrentPred) + return CurrentPred; + + const_pred_iterator PII = pred_begin(this); + const_pred_iterator E = pred_end(this); + // No predecessors. + if (PII == E) + return nullptr; + + unsigned NumPreds = std::distance(PII, E); + if (NumPreds != 2) + return nullptr; + + const BasicBlock *PredA = *PII++; + const BasicBlock *PredB = *PII; + const BasicBlock *PredADom = PredA->getSinglePredecessor(); + const BasicBlock *PredBDom = PredB->getSinglePredecessor(); + // Look through hammocks. + if (PredADom && PredADom == PredB) + return PredB; + if (PredBDom && PredBDom == PredA) + return PredA; + // Look through diamonds. + if (PredADom && PredADom == PredBDom) + return PredADom; + return nullptr; +} + const BasicBlock *BasicBlock::getSingleSuccessor() const { succ_const_iterator SI = succ_begin(this), E = succ_end(this); if (SI == E) return nullptr; // no successors Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -123,6 +123,12 @@ cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions")); +static cl::opt ImplicationSearchThreshold( + "simplifycfg-implication-search-threshold", + cl::desc("The number of predecessors to search for a stronger condition " + "used to simplify a weaker condition"), + cl::init(3), cl::Hidden); + STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping"); @@ -5753,25 +5759,23 @@ if (SimplifyBranchOnICmpChain(BI, Builder, DL)) return true; - // If this basic block has a single dominating predecessor block and the - // dominating block's condition implies BI's condition, we know the direction - // of the BI branch. - if (BasicBlock *Dom = BB->getSinglePredecessor()) { - auto *PBI = dyn_cast_or_null(Dom->getTerminator()); - if (PBI && PBI->isConditional() && - PBI->getSuccessor(0) != PBI->getSuccessor(1)) { - assert(PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB); - bool CondIsTrue = PBI->getSuccessor(0) == BB; - Optional Implication = isImpliedCondition( - PBI->getCondition(), BI->getCondition(), DL, CondIsTrue); + // If this basic block has a dominating condition that implies BI's condition, + // we know the direction of the BI branch. + unsigned Limit = ImplicationSearchThreshold; + SmallVector, 3> DomConds; + if (findDominatingConditions(BB, DomConds, Limit)) { + Value *Cond = BI->getCondition(); + auto &DL = BB->getModule()->getDataLayout(); + for (unsigned i = 0, e = DomConds.size(); i != e; ++i) { + Optional Implication = + isImpliedCondition(DomConds[i].first, Cond, DL, DomConds[i].second); if (Implication) { // Turn this into a branch on constant. - auto *OldCond = BI->getCondition(); ConstantInt *CI = *Implication - ? ConstantInt::getTrue(BB->getContext()) - : ConstantInt::getFalse(BB->getContext()); + ? ConstantInt::getTrue(BB->getContext()) + : ConstantInt::getFalse(BB->getContext()); BI->setCondition(CI); - RecursivelyDeleteTriviallyDeadInstructions(OldCond); + RecursivelyDeleteTriviallyDeadInstructions(Cond); return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; } } Index: test/CodeGen/AArch64/addsub.ll =================================================================== --- test/CodeGen/AArch64/addsub.ll +++ test/CodeGen/AArch64/addsub.ll @@ -110,8 +110,8 @@ %val2 = load i32, i32* @var2_i32 ; CHECK: cmp {{w[0-9]+}}, #4095 -; CHECK: b.ne [[RET:.?LBB[0-9]+_[0-9]+]] - %cmp_pos_small = icmp ne i32 %val, 4095 +; CHECK: b.eq [[RET:.?LBB[0-9]+_[0-9]+]] + %cmp_pos_small = icmp eq i32 %val, 4095 br i1 %cmp_pos_small, label %ret, label %test2 test2: Index: test/CodeGen/AArch64/arm64-andCmpBrToTBZ.ll =================================================================== --- test/CodeGen/AArch64/arm64-andCmpBrToTBZ.ll +++ test/CodeGen/AArch64/arm64-andCmpBrToTBZ.ll @@ -34,10 +34,12 @@ br label %return if.end5: ; preds = %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit, %lor.rhs.i.i.i -; CHECK: %if.end5 -; CHECK: tbz br i1 %tobool.i.i.i, label %if.end12, label %land.rhs.i19, !prof !1 +; The above conditional branch gets simplified based on the dominating condition in if.end +; CHECK-NOT: tbz +; CHECK: %land.rhs.i19 + land.rhs.i19: ; preds = %if.end5 %cmp.i.i.i18 = icmp eq i8* %str6, %str7 br i1 %cmp.i.i.i18, label %if.then7, label %lor.rhs.i.i.i23 Index: test/Transforms/SimplifyCFG/implied-cond-hammock-diamond.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/implied-cond-hammock-diamond.ll @@ -0,0 +1,120 @@ +; RUN: opt %s -S -simplifycfg | FileCheck %s + +; Check that we can simplify a condition in if.then3 based on the branch +; condition of entry. This check to make sure we can traverse past the if.then +; block. +; CHECK-LABEL: @test1( +define void @test1(i32 %a, i32 %b, i32 %c, i32* %arr) { +entry: + %tobool = icmp ne i32 %a, 0 + %tobool1 = icmp ne i32 %b, 0 + %cond = and i1 %tobool, %tobool1 + br i1 %cond, label %if.then, label %if.end9 + +if.then: + store i32 %a, i32* %arr, align 4 + %tobool2 = icmp eq i32 %c, 0 + br i1 %tobool2, label %if.end9, label %if.then3 + +if.then3: + %arrayidx2 = getelementptr inbounds i32, i32* %arr, i64 2 + store i32 %c, i32* %arrayidx2, align 4 + br i1 %tobool1, label %if.then6, label %if.end9 ; <-- Simplifies to br label %if.then6 + +; CHECK: if.then3: +; CHECK: br label %if.end9 +; CHECK-NOT: if.then6: + +if.then6: + %arrayidx1 = getelementptr inbounds i32, i32* %arr, i64 1 + store i32 %b, i32* %arrayidx1, align 4 + br label %if.end9 + +if.end9: + ret void +} + +; Check to make sure we can look through an if-then (hammock). +; CHECK-LABEL: @test2( +define void @test2(i32 %a, i32 %b, i32 %c, i32* %arr) { +entry: + %tobool = icmp ne i32 %a, 0 + %tobool1 = icmp ne i32 %b, 0 + %or.cond = and i1 %tobool, %tobool1 + br i1 %or.cond, label %if.then, label %if.end9 + +if.then: + store i32 %a, i32* %arr, align 4 + %tobool2 = icmp eq i32 %c, 0 + br i1 %tobool2, label %if.end, label %if.then3 + +; CHECK: if.then: +; CHECK: br i1 %tobool2, label %if.then6, label %if.then3 + +if.then3: + %arrayidx4 = getelementptr inbounds i32, i32* %arr, i64 2 + store i32 %c, i32* %arrayidx4, align 4 + br label %if.end + +; CHECK: if.then3: +; CHECK: br label %if.then6 + +if.end: + br i1 %tobool1, label %if.then6, label %if.end9 ; <- Simplifies to br label %if.then6 + +; CHECK-NOT: if.end: +; CHECK-NOT: br i1 %tobool1, label %if.then6, label %if.end9 + +if.then6: + %arrayidx7 = getelementptr inbounds i32, i32* %arr, i64 1 + store i32 %b, i32* %arrayidx7, align 4 + br label %if.end9 + +if.end9: ; preds = %if.end, %if.then6, %entry + ret void +} + +; Check to make sure we can look through an if-then-else (diamond). +; CHECK-LABEL: @test3( +define void @test3(i32 %a, i32 %b, i32 %c, i32* %arr) local_unnamed_addr #0 { +entry: + %tobool = icmp ne i32 %a, 0 + %tobool1 = icmp ne i32 %b, 0 + %or.cond = and i1 %tobool, %tobool1 + br i1 %or.cond, label %if.then, label %if.end7 + +if.then: + %tobool2 = icmp eq i32 %c, 0 + br i1 %tobool2, label %if.else, label %if.then3 + +if.then3: + call void @foo() #2 + br label %if.end + +; CHECK: if.then3: +; CHECK: br label %if.then5 + +if.else: + call void @bar() #2 + br label %if.end + +; CHECK: if.else: +; CHECK: br label %if.then5 + +if.end: + br i1 %tobool1, label %if.then5, label %if.end7 + +; CHECK-NOT: if.end: +; CHECK-NOT: br i1 %tobool1, label %if.then5, label %if.end7 + +if.then5: + %arrayidx = getelementptr inbounds i32, i32* %arr, i64 1 + store i32 %b, i32* %arrayidx, align 4 + br label %if.end7 + +if.end7: + ret void +} + +declare void @foo() +declare void @bar()