diff options
| -rw-r--r-- | lib/Transforms/Utils/Local.cpp | 170 | ||||
| -rw-r--r-- | test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll | 240 |
2 files changed, 386 insertions, 24 deletions
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index e470e14..ca9f2b1 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -525,6 +525,13 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { PredBB->eraseFromParent(); } +/// CanMergeValues - Return true if we can choose one of these values to use +/// in place of the other. Note that we will always choose the non-undef +/// value to keep. +static bool CanMergeValues(Value *First, Value *Second) { + return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); +} + /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an /// almost-empty BB ending in an unconditional branch to Succ, into succ. /// @@ -555,7 +562,8 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { BasicBlock *IBB = PN->getIncomingBlock(PI); if (BBPreds.count(IBB) && - BBPN->getIncomingValueForBlock(IBB) != PN->getIncomingValue(PI)) { + !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), + PN->getIncomingValue(PI))) { DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " @@ -570,7 +578,8 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { // one for BB, in which case this phi node will not prevent the merging // of the block. BasicBlock *IBB = PN->getIncomingBlock(PI); - if (BBPreds.count(IBB) && Val != PN->getIncomingValue(PI)) { + if (BBPreds.count(IBB) && + !CanMergeValues(Val, PN->getIncomingValue(PI))) { DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with regard to common " << "predecessor " << IBB->getName() << "\n"); @@ -583,6 +592,139 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { return true; } +typedef SmallVector<BasicBlock *, 16> PredBlockVector; +typedef DenseMap<BasicBlock *, Value *> IncomingValueMap; + +/// \brief Determines the value to use as the phi node input for a block. +/// +/// Select between \p OldVal any value that we know flows from \p BB +/// to a particular phi on the basis of which one (if either) is not +/// undef. Update IncomingValues based on the selected value. +/// +/// \param OldVal The value we are considering selecting. +/// \param BB The block that the value flows in from. +/// \param IncomingValues A map from block-to-value for other phi inputs +/// that we have examined. +/// +/// \returns the selected value. +static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, + IncomingValueMap &IncomingValues) { + if (!isa<UndefValue>(OldVal)) { + assert((!IncomingValues.count(BB) || + IncomingValues.find(BB)->second == OldVal) && + "Expected OldVal to match incoming value from BB!"); + + IncomingValues.insert(std::make_pair(BB, OldVal)); + return OldVal; + } + + IncomingValueMap::const_iterator It = IncomingValues.find(BB); + if (It != IncomingValues.end()) return It->second; + + return OldVal; +} + +/// \brief Create a map from block to value for the operands of a +/// given phi. +/// +/// Create a map from block to value for each non-undef value flowing +/// into \p PN. +/// +/// \param PN The phi we are collecting the map for. +/// \param IncomingValues [out] The map from block to value for this phi. +static void gatherIncomingValuesToPhi(PHINode *PN, + IncomingValueMap &IncomingValues) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + BasicBlock *BB = PN->getIncomingBlock(i); + Value *V = PN->getIncomingValue(i); + + if (!isa<UndefValue>(V)) + IncomingValues.insert(std::make_pair(BB, V)); + } +} + +/// \brief Replace the incoming undef values to a phi with the values +/// from a block-to-value map. +/// +/// \param PN The phi we are replacing the undefs in. +/// \param IncomingValues A map from block to value. +static void replaceUndefValuesInPhi(PHINode *PN, + const IncomingValueMap &IncomingValues) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *V = PN->getIncomingValue(i); + + if (!isa<UndefValue>(V)) continue; + + BasicBlock *BB = PN->getIncomingBlock(i); + IncomingValueMap::const_iterator It = IncomingValues.find(BB); + if (It == IncomingValues.end()) continue; + + PN->setIncomingValue(i, It->second); + } +} + +/// \brief Replace a value flowing from a block to a phi with +/// potentially multiple instances of that value flowing from the +/// block's predecessors to the phi. +/// +/// \param BB The block with the value flowing into the phi. +/// \param BBPreds The predecessors of BB. +/// \param PN The phi that we are updating. +static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, + const PredBlockVector &BBPreds, + PHINode *PN) { + Value *OldVal = PN->removeIncomingValue(BB, false); + assert(OldVal && "No entry in PHI for Pred BB!"); + + IncomingValueMap IncomingValues; + + // We are merging two blocks - BB, and the block containing PN - and + // as a result we need to redirect edges from the predecessors of BB + // to go to the block containing PN, and update PN + // accordingly. Since we allow merging blocks in the case where the + // predecessor and successor blocks both share some predecessors, + // and where some of those common predecessors might have undef + // values flowing into PN, we want to rewrite those values to be + // consistent with the non-undef values. + + gatherIncomingValuesToPhi(PN, IncomingValues); + + // If this incoming value is one of the PHI nodes in BB, the new entries + // in the PHI node are the entries from the old PHI. + if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { + PHINode *OldValPN = cast<PHINode>(OldVal); + for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { + // Note that, since we are merging phi nodes and BB and Succ might + // have common predecessors, we could end up with a phi node with + // identical incoming branches. This will be cleaned up later (and + // will trigger asserts if we try to clean it up now, without also + // simplifying the corresponding conditional branch). + BasicBlock *PredBB = OldValPN->getIncomingBlock(i); + Value *PredVal = OldValPN->getIncomingValue(i); + Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, + IncomingValues); + + // And add a new incoming value for this predecessor for the + // newly retargeted branch. + PN->addIncoming(Selected, PredBB); + } + } else { + for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { + // Update existing incoming values in PN for this + // predecessor of BB. + BasicBlock *PredBB = BBPreds[i]; + Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, + IncomingValues); + + // And add a new incoming value for this predecessor for the + // newly retargeted branch. + PN->addIncoming(Selected, PredBB); + } + } + + replaceUndefValuesInPhi(PN, IncomingValues); +} + /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an /// unconditional branch, and contains no instructions other than PHI nodes, /// potential side-effect free intrinsics and the branch. If possible, @@ -634,31 +776,13 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { // If there is more than one pred of succ, and there are PHI nodes in // the successor, then we need to add incoming edges for the PHI nodes // - const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); + const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); // Loop over all of the PHI nodes in the successor of BB. for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { PHINode *PN = cast<PHINode>(I); - Value *OldVal = PN->removeIncomingValue(BB, false); - assert(OldVal && "No entry in PHI for Pred BB!"); - - // If this incoming value is one of the PHI nodes in BB, the new entries - // in the PHI node are the entries from the old PHI. - if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { - PHINode *OldValPN = cast<PHINode>(OldVal); - for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) - // Note that, since we are merging phi nodes and BB and Succ might - // have common predecessors, we could end up with a phi node with - // identical incoming branches. This will be cleaned up later (and - // will trigger asserts if we try to clean it up now, without also - // simplifying the corresponding conditional branch). - PN->addIncoming(OldValPN->getIncomingValue(i), - OldValPN->getIncomingBlock(i)); - } else { - // Add an incoming value for each of the new incoming values. - for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) - PN->addIncoming(OldVal, BBPreds[i]); - } + + redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); } } diff --git a/test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll b/test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll index 912c755..b07ef97 100644 --- a/test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll +++ b/test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll @@ -1,8 +1,18 @@ ; Test merging of blocks with phi nodes. ; -; RUN: opt < %s -simplifycfg -S | not grep N: +; RUN: opt < %s -simplifycfg -S > %t +; RUN: not grep N: %t +; RUN: not grep X: %t +; RUN: not grep 'switch i32[^U]+%U' %t +; RUN: not grep "^BB.tomerge" %t +; RUN: grep "^BB.nomerge" %t | count 2 ; +; ModuleID = '<stdin>' +declare i1 @foo() + +declare i1 @bar(i32) + define i32 @test(i1 %a) { Q: br i1 %a, label %N, label %M @@ -16,3 +26,231 @@ M: ; preds = %N, %Q ret i32 %R } +; Test merging of blocks with phi nodes where at least one incoming value +; in the successor is undef. +define i8 @testundef(i32 %u) { +R: + switch i32 %u, label %U [ + i32 0, label %S + i32 1, label %T + i32 2, label %T + ] + +S: ; preds = %R + br label %U + +T: ; preds = %R, %R + br label %U + +U: ; preds = %T, %S, %R + ; We should be able to merge either the S or T block into U by rewriting + ; R's incoming value with the incoming value of that predecessor since + ; R's incoming value is undef and both of those predecessors are simple + ; unconditional branches. + %val.0 = phi i8 [ undef, %R ], [ 1, %T ], [ 0, %S ] + ret i8 %val.0 +} + +; Test merging of blocks with phi nodes where at least one incoming value +; in the successor is undef. +define i8 @testundef2(i32 %u, i32* %A) { +V: + switch i32 %u, label %U [ + i32 0, label %W + i32 1, label %X + i32 2, label %X + i32 3, label %Z + ] + +W: ; preds = %V + br label %U + +Z: + store i32 0, i32* %A, align 4 + br label %X + +X: ; preds = %V, %V, %Z + br label %U + +U: ; preds = %X, %W, %V + ; We should be able to merge either the W or X block into U by rewriting + ; V's incoming value with the incoming value of that predecessor since + ; V's incoming value is undef and both of those predecessors are simple + ; unconditional branches. Note that X has predecessors beyond + ; the direct predecessors of U. + %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 1, %W ] + ret i8 %val.0 +} + +define i8 @testmergesome(i32 %u, i32* %A) { +V: + switch i32 %u, label %Y [ + i32 0, label %W + i32 1, label %X + i32 2, label %X + i32 3, label %Z + ] + +W: ; preds = %V + store i32 1, i32* %A, align 4 + br label %Y + +Z: + store i32 0, i32* %A, align 4 + br label %X + +X: ; preds = %V, %Z + br label %Y + +Y: ; preds = %X, %W, %V + ; After merging X into Y, we should have 5 predecessors + ; and thus 5 incoming values to the phi. + %val.0 = phi i8 [ 1, %V ], [ 1, %X ], [ 2, %W ] + ret i8 %val.0 +} + + +define i8 @testmergesome2(i32 %u, i32* %A) { +V: + switch i32 %u, label %W [ + i32 0, label %W + i32 1, label %Y + i32 2, label %X + i32 4, label %Y + ] + +W: ; preds = %V + store i32 1, i32* %A, align 4 + br label %Y + +X: ; preds = %V, %Z + br label %Y + +Y: ; preds = %X, %W, %V + ; Ensure that we deal with both undef inputs for V when we merge in X. + %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 2, %W ], [ undef, %V ] + ret i8 %val.0 +} + +; This function can't be merged +define void @a() { +entry: + br label %BB.nomerge + +BB.nomerge: ; preds = %Common, %entry + ; This phi has a conflicting value (0) with below phi (2), so blocks + ; can't be merged. + %a = phi i32 [ 1, %entry ], [ 0, %Common ] ; <i32> [#uses=1] + br label %Succ + +Succ: ; preds = %Common, %BB.nomerge + %b = phi i32 [ %a, %BB.nomerge ], [ 2, %Common ] ; <i32> [#uses=0] + %conde = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %conde, label %Common, label %Exit + +Common: ; preds = %Succ + %cond = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %cond, label %BB.nomerge, label %Succ + +Exit: ; preds = %Succ + ret void +} + +; This function can't be merged +define void @b() { +entry: + br label %BB.nomerge + +BB.nomerge: ; preds = %Common, %entry + br label %Succ + +Succ: ; preds = %Common, %BB.nomerge + ; This phi has confliction values for Common and (through BB) Common, + ; blocks can't be merged + %b = phi i32 [ 1, %BB.nomerge ], [ 2, %Common ] ; <i32> [#uses=0] + %conde = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %conde, label %Common, label %Exit + +Common: ; preds = %Succ + %cond = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %cond, label %BB.nomerge, label %Succ + +Exit: ; preds = %Succ + ret void +} + +; This function can be merged +define void @c() { +entry: + br label %BB.tomerge + +BB.tomerge: ; preds = %Common, %entry + br label %Succ + +Succ: ; preds = %Common, %BB.tomerge, %Pre-Exit + ; This phi has identical values for Common and (through BB) Common, + ; blocks can't be merged + %b = phi i32 [ 1, %BB.tomerge ], [ 1, %Common ], [ 2, %Pre-Exit ] + %conde = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %conde, label %Common, label %Pre-Exit + +Common: ; preds = %Succ + %cond = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %cond, label %BB.tomerge, label %Succ + +Pre-Exit: ; preds = %Succ + ; This adds a backedge, so the %b phi node gets a third branch and is + ; not completely trivial + %cond2 = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %cond2, label %Succ, label %Exit + +Exit: ; preds = %Pre-Exit + ret void +} + +; This function can be merged +define void @d() { +entry: + br label %BB.tomerge + +BB.tomerge: ; preds = %Common, %entry + ; This phi has a matching value (0) with below phi (0), so blocks + ; can be merged. + %a = phi i32 [ 1, %entry ], [ 0, %Common ] ; <i32> [#uses=1] + br label %Succ + +Succ: ; preds = %Common, %BB.tomerge + %b = phi i32 [ %a, %BB.tomerge ], [ 0, %Common ] ; <i32> [#uses=0] + %conde = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %conde, label %Common, label %Exit + +Common: ; preds = %Succ + %cond = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %cond, label %BB.tomerge, label %Succ + +Exit: ; preds = %Succ + ret void +} + +; This function can be merged +define void @e() { +entry: + br label %BB.tomerge + +BB.tomerge: ; preds = %Use, %entry + ; This phi is used somewhere else than Succ, but this should not prevent + ; merging this block + %a = phi i32 [ 1, %entry ], [ 0, %Use ] ; <i32> [#uses=1] + br label %Succ + +Succ: ; preds = %BB.tomerge + %conde = call i1 @foo( ) ; <i1> [#uses=1] + br i1 %conde, label %Use, label %Exit + +Use: ; preds = %Succ + %cond = call i1 @bar( i32 %a ) ; <i1> [#uses=1] + br i1 %cond, label %BB.tomerge, label %Exit + +Exit: ; preds = %Use, %Succ + ret void +} |