diff options
| -rw-r--r-- | lib/Transforms/Utils/SimplifyCFG.cpp | 74 | ||||
| -rw-r--r-- | test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll | 36 | ||||
| -rw-r--r-- | test/Transforms/SimplifyCFG/switch_switch_fold_dbginfo.ll | 2 |
3 files changed, 111 insertions, 1 deletions
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 6df846cbd1..7b93b4a8e2 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -2450,6 +2450,77 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI) { return !DeadCases.empty(); } +/// FindPHIForConditionForwarding - If BB would be eligible for simplification +/// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated +/// by an unconditional branch), look at the phi node for BB in the successor +/// block and see if the incoming value is equal to CaseValue. If so, return +/// the phi node, and set PhiIndex to BB's index in the phi node. +static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, + BasicBlock *BB, + int *PhiIndex) { + if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) + return NULL; // BB must be empty to be a candidate for simplification. + if (!BB->getSinglePredecessor()) + return NULL; // BB must be dominated by the switch. + + BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); + if (!Branch || !Branch->isUnconditional()) + return NULL; // Terminator must be unconditional branch. + + BasicBlock *Succ = Branch->getSuccessor(0); + + BasicBlock::iterator I = Succ->begin(); + while (PHINode *PHI = dyn_cast<PHINode>(I++)) { + int Idx = PHI->getBasicBlockIndex(BB); + assert(Idx >= 0 && "PHI has no entry for predecessor?"); + + Value *InValue = PHI->getIncomingValue(Idx); + if (InValue != CaseValue) continue; + + *PhiIndex = Idx; + return PHI; + } + + return NULL; +} + +/// ForwardSwitchConditionToPHI - Try to forward the condition of a switch +/// instruction to a phi node dominated by the switch, if that would mean that +/// some of the destination blocks of the switch can be folded away. +/// Returns true if a change is made. +static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { + typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap; + ForwardingNodesMap ForwardingNodes; + + for (unsigned I = 1; I < SI->getNumCases(); ++I) { // 0 is the default case. + ConstantInt *CaseValue = SI->getCaseValue(I); + BasicBlock *CaseDest = SI->getSuccessor(I); + + int PhiIndex; + PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest, + &PhiIndex); + if (!PHI) continue; + + ForwardingNodes[PHI].push_back(PhiIndex); + } + + bool Changed = false; + + for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), + E = ForwardingNodes.end(); I != E; ++I) { + PHINode *Phi = I->first; + SmallVector<int,4> &Indexes = I->second; + + if (Indexes.size() < 2) continue; + + for (size_t I = 0, E = Indexes.size(); I != E; ++I) + Phi->setIncomingValue(Indexes[I], SI->getCondition()); + Changed = true; + } + + return Changed; +} + bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { // If this switch is too complex to want to look at, ignore it. if (!isValueEqualityComparison(SI)) @@ -2486,6 +2557,9 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { if (EliminateDeadSwitchCases(SI)) return SimplifyCFG(BB) | true; + if (ForwardSwitchConditionToPHI(SI)) + return SimplifyCFG(BB) | true; + return false; } diff --git a/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll b/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll new file mode 100644 index 0000000000..1b70c065ba --- /dev/null +++ b/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll @@ -0,0 +1,36 @@ +; RUN: opt < %s -simplifycfg -S | \ +; RUN: not grep " switch" +; PR10131 + +; ModuleID = '<stdin>' +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32" +target triple = "i386-pc-linux-gnu" + +define i32 @t(i32 %m) nounwind readnone { +entry: + switch i32 %m, label %sw.bb4 [ + i32 0, label %sw.bb0 + i32 1, label %sw.bb1 + i32 2, label %sw.bb2 + i32 3, label %sw.bb3 + ] + +sw.bb0: ; preds = %entry + br label %return + +sw.bb1: ; preds = %entry + br label %return + +sw.bb2: ; preds = %entry + br label %return + +sw.bb3: ; preds = %entry + br label %return + +sw.bb4: ; preds = %entry + br label %return + +return: ; preds = %entry, %sw.bb4, %sw.bb3, %sw.bb2, %sw.bb1 + %retval.0 = phi i32 [ 4, %sw.bb4 ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %sw.bb0 ] + ret i32 %retval.0 +} diff --git a/test/Transforms/SimplifyCFG/switch_switch_fold_dbginfo.ll b/test/Transforms/SimplifyCFG/switch_switch_fold_dbginfo.ll index 7d7391af1b..343e169edc 100644 --- a/test/Transforms/SimplifyCFG/switch_switch_fold_dbginfo.ll +++ b/test/Transforms/SimplifyCFG/switch_switch_fold_dbginfo.ll @@ -1,5 +1,5 @@ ; RUN: opt < %s -simplifycfg -S | \ -; RUN: grep switch | count 1 +; RUN: not grep " switch" ; ModuleID = '<stdin>' target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32" |