diff options
author | Benjamin Kramer <benny.kra@googlemail.com> | 2013-08-07 10:29:38 +0000 |
---|---|---|
committer | Benjamin Kramer <benny.kra@googlemail.com> | 2013-08-07 10:29:38 +0000 |
commit | c11b107f21f8f1baf1021999fc7d01b93e00922b (patch) | |
tree | 30b40715cea776c60986056d6fbf36269c6557ff | |
parent | e4a4aecffb25df25736fec328d9147ee43335c2b (diff) | |
download | llvm-c11b107f21f8f1baf1021999fc7d01b93e00922b.tar.gz llvm-c11b107f21f8f1baf1021999fc7d01b93e00922b.tar.bz2 llvm-c11b107f21f8f1baf1021999fc7d01b93e00922b.tar.xz |
JumpThreading: Turn a select instruction into branching if it allows to thread one half of the select.
This is a common pattern coming out of simplifycfg generating gross code.
a: ; preds = %entry
%sel = select i1 %cmp1, double %add, double 0.000000e+00
br label %b
b:
%cond5 = phi double [ %sel, %a ], [ %sub, %entry ]
%cmp6 = fcmp oeq double %cond5, 0.000000e+00
br i1 %cmp6, label %if.then, label %if.end
becomes
a:
br i1 %cmp1, label %b, label %if.then
b:
%cond5 = phi double [ %sub, %entry ], [ %add, %a ]
%cmp6 = fcmp oeq double %cond5, 0.000000e+00
br i1 %cmp6, label %if.then, label %if.end
Skipping block b completely if possible.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187880 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/Transforms/Scalar/JumpThreading.cpp | 83 | ||||
-rw-r--r-- | test/Transforms/JumpThreading/select.ll | 63 |
2 files changed, 146 insertions, 0 deletions
diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index 2d961ee630..0b8906d43f 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -130,6 +130,7 @@ namespace { bool ProcessBranchOnXOR(BinaryOperator *BO); bool SimplifyPartiallyRedundantLoad(LoadInst *LI); + bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); }; } @@ -776,7 +777,11 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { return true; } } + } + + if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB)) + return true; } // Check for some cases that are worth simplifying. Right now we want to look @@ -1615,3 +1620,81 @@ bool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, ++NumDupes; return true; } + +/// TryToUnfoldSelect - Look for blocks of the form +/// bb1: +/// %a = select +/// br bb +/// +/// bb2: +/// %p = phi [%a, %bb] ... +/// %c = icmp %p +/// br i1 %c +/// +/// And expand the select into a branch structure if one of its arms allows %c +/// to be folded. This later enables threading from bb1 over bb2. +bool JumpThreading::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { + BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); + PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0)); + Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1)); + + if (!CondBr || !CondBr->isConditional() || !CondLHS || + CondLHS->getParent() != BB) + return false; + + for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) { + BasicBlock *Pred = CondLHS->getIncomingBlock(I); + SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I)); + + // Look if one of the incoming values is a select in the corresponding + // predecessor. + if (!SI || SI->getParent() != Pred || !SI->hasOneUse()) + continue; + + BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator()); + if (!PredTerm || !PredTerm->isUnconditional()) + continue; + + // Now check if one of the select values would allow us to constant fold the + // terminator in BB. We don't do the transform if both sides fold, those + // cases will be threaded in any case. + LazyValueInfo::Tristate LHSFolds = + LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1), + CondRHS, Pred, BB); + LazyValueInfo::Tristate RHSFolds = + LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2), + CondRHS, Pred, BB); + if ((LHSFolds != LazyValueInfo::Unknown || + RHSFolds != LazyValueInfo::Unknown) && + LHSFolds != RHSFolds) { + // Expand the select. + // + // Pred -- + // | v + // | NewBB + // | | + // |----- + // v + // BB + BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", + BB->getParent(), BB); + // Move the unconditional branch to NewBB. + PredTerm->removeFromParent(); + NewBB->getInstList().insert(NewBB->end(), PredTerm); + // Create a conditional branch and update PHI nodes. + BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); + CondLHS->setIncomingValue(I, SI->getFalseValue()); + CondLHS->addIncoming(SI->getTrueValue(), NewBB); + // The select is now dead. + SI->eraseFromParent(); + + // Update any other PHI nodes in BB. + for (BasicBlock::iterator BI = BB->begin(); + PHINode *Phi = dyn_cast<PHINode>(BI); ++BI) + if (Phi != CondLHS) + Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB); + return true; + } + } + return false; +} diff --git a/test/Transforms/JumpThreading/select.ll b/test/Transforms/JumpThreading/select.ll index 18f5e23fac..201e604e0c 100644 --- a/test/Transforms/JumpThreading/select.ll +++ b/test/Transforms/JumpThreading/select.ll @@ -157,3 +157,66 @@ L3: L4: ret void } + +define void @unfold1(double %x, double %y) nounwind { +entry: + %sub = fsub double %x, %y + %cmp = fcmp ogt double %sub, 1.000000e+01 + br i1 %cmp, label %cond.end4, label %cond.false + +cond.false: ; preds = %entry + %add = fadd double %x, %y + %cmp1 = fcmp ogt double %add, 1.000000e+01 + %add. = select i1 %cmp1, double %add, double 0.000000e+00 + br label %cond.end4 + +cond.end4: ; preds = %entry, %cond.false + %cond5 = phi double [ %add., %cond.false ], [ %sub, %entry ] + %cmp6 = fcmp oeq double %cond5, 0.000000e+00 + br i1 %cmp6, label %if.then, label %if.end + +if.then: ; preds = %cond.end4 + call void @foo() + br label %if.end + +if.end: ; preds = %if.then, %cond.end4 + ret void + +; CHECK-LABEL: @unfold1 +; CHECK: br i1 %cmp, label %cond.end4, label %cond.false +; CHECK: br i1 %cmp1, label %cond.end4, label %if.then +; CHECK: br i1 %cmp6, label %if.then, label %if.end +; CHECK: br label %if.end +} + + +define void @unfold2(i32 %x, i32 %y) nounwind { +entry: + %sub = sub nsw i32 %x, %y + %cmp = icmp sgt i32 %sub, 10 + br i1 %cmp, label %cond.end4, label %cond.false + +cond.false: ; preds = %entry + %add = add nsw i32 %x, %y + %cmp1 = icmp sgt i32 %add, 10 + %add. = select i1 %cmp1, i32 0, i32 %add + br label %cond.end4 + +cond.end4: ; preds = %entry, %cond.false + %cond5 = phi i32 [ %add., %cond.false ], [ %sub, %entry ] + %cmp6 = icmp eq i32 %cond5, 0 + br i1 %cmp6, label %if.then, label %if.end + +if.then: ; preds = %cond.end4 + call void @foo() + br label %if.end + +if.end: ; preds = %if.then, %cond.end4 + ret void + +; CHECK-LABEL: @unfold2 +; CHECK: br i1 %cmp, label %if.end, label %cond.false +; CHECK: br i1 %cmp1, label %if.then, label %cond.end4 +; CHECK: br i1 %cmp6, label %if.then, label %if.end +; CHECK: br label %if.end +} |