diff options
| -rw-r--r-- | include/llvm/Transforms/Utils/BasicBlockUtils.h | 8 | ||||
| -rw-r--r-- | lib/Transforms/Utils/BasicBlockUtils.cpp | 70 | ||||
| -rw-r--r-- | lib/Transforms/Utils/LoopUnroll.cpp | 48 | ||||
| -rw-r--r-- | test/Transforms/SimplifyCFG/PhiBlockMerge.ll | 2 |
4 files changed, 31 insertions, 97 deletions
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index e766d72..47d6895 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -43,9 +43,11 @@ void FoldSingleEntryPHINodes(BasicBlock *BB); /// it is ultimately unused or if it reaches an unused cycle. void DeleteDeadPHIs(BasicBlock *BB); -/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, -/// if possible. The return value indicates success or failure. -bool MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P = 0); +/// MergeBlockIntoPredecessor - Folds a basic block into its predecessor if it +/// only has one predecessor, and that predecessor only has one successor. +/// If a Pass is given, the LoopInfo and DominatorTree analyses will be kept +/// current. Returns the combined block, or null if no merging was performed. +BasicBlock *MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P = 0); // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) // with a value, then remove and delete the original instruction. diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index c2c662f..b6f00e2 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -95,54 +95,28 @@ void llvm::DeleteDeadPHIs(BasicBlock *BB) { RecursivelyDeleteDeadPHINode(PN); } -/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, -/// if possible. The return value indicates success or failure. -bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) { - pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); - // Can't merge the entry block. - if (pred_begin(BB) == pred_end(BB)) return false; - - BasicBlock *PredBB = *PI++; - for (; PI != PE; ++PI) // Search all predecessors, see if they are all same - if (*PI != PredBB) { - PredBB = 0; // There are multiple different predecessors... - break; - } - - // Can't merge if there are multiple predecessors. - if (!PredBB) return false; +/// MergeBlockIntoPredecessor - Folds a basic block into its predecessor if it +/// only has one predecessor, and that predecessor only has one successor. +/// If a Pass is given, the LoopInfo and DominatorTree analyses will be kept +/// current. Returns the combined block, or null if no merging was performed. +BasicBlock *llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) { + // Don't merge if the block has multiple predecessors. + BasicBlock *PredBB = BB->getSinglePredecessor(); + if (!PredBB) return 0; + // Don't merge if the predecessor has multiple successors. + if (PredBB->getTerminator()->getNumSuccessors() != 1) return 0; // Don't break self-loops. - if (PredBB == BB) return false; + if (PredBB == BB) return 0; // Don't break invokes. - if (isa<InvokeInst>(PredBB->getTerminator())) return false; - - succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB)); - BasicBlock* OnlySucc = BB; - for (; SI != SE; ++SI) - if (*SI != OnlySucc) { - OnlySucc = 0; // There are multiple distinct successors! - break; - } + if (isa<InvokeInst>(PredBB->getTerminator())) return 0; - // Can't merge if there are multiple successors. - if (!OnlySucc) return false; - - // Can't merge if there is PHI loop. - for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) { - if (PHINode *PN = dyn_cast<PHINode>(BI)) { - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingValue(i) == PN) - return false; - } else - break; - } + // Resolve any PHI nodes at the start of the block. They are all + // guaranteed to have exactly one entry if they exist, unless there are + // multiple duplicate (but guaranteed to be equal) entries for the + // incoming edges. This occurs when there are multiple edges from + // PredBB to BB. + FoldSingleEntryPHINodes(BB); - // Begin by getting rid of unneeded PHIs. - while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - BB->getInstList().pop_front(); // Delete the phi node... - } - // Delete the unconditional branch from the predecessor... PredBB->getInstList().pop_back(); @@ -153,7 +127,7 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) { // source... BB->replaceAllUsesWith(PredBB); - // Inherit predecessors name if it exists. + // If the predecessor doesn't have a name, take the successor's name. if (!PredBB->hasName()) PredBB->takeName(BB); @@ -172,12 +146,14 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) { DT->eraseNode(BB); } } + // Notify LoopInfo that the block is removed. + if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) + LI->removeBlock(BB); } BB->eraseFromParent(); - - return true; + return PredBB; } /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp index d68427a..9b68df0 100644 --- a/lib/Transforms/Utils/LoopUnroll.cpp +++ b/lib/Transforms/Utils/LoopUnroll.cpp @@ -49,52 +49,6 @@ static inline void RemapInstruction(Instruction *I, } } -/// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it -/// only has one predecessor, and that predecessor only has one successor. -/// The LoopInfo Analysis that is passed will be kept consistent. -/// Returns the new combined block. -static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { - // Merge basic blocks into their predecessor if there is only one distinct - // pred, and if there is only one distinct successor of the predecessor, and - // if there are no PHI nodes. - BasicBlock *OnlyPred = BB->getSinglePredecessor(); - if (!OnlyPred) return 0; - - if (OnlyPred->getTerminator()->getNumSuccessors() != 1) - return 0; - - DEBUG(errs() << "Merging: " << *BB << "into: " << *OnlyPred); - - // Resolve any PHI nodes at the start of the block. They are all - // guaranteed to have exactly one entry if they exist, unless there are - // multiple duplicate (but guaranteed to be equal) entries for the - // incoming edges. This occurs when there are multiple edges from - // OnlyPred to OnlySucc. - FoldSingleEntryPHINodes(BB); - - // Delete the unconditional branch from the predecessor... - OnlyPred->getInstList().pop_back(); - - // Move all definitions in the successor to the predecessor... - OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); - - // Make all PHI nodes that referred to BB now refer to Pred as their - // source... - BB->replaceAllUsesWith(OnlyPred); - - std::string OldName = BB->getName(); - - // Erase basic block from the function... - LI->removeBlock(BB); - BB->eraseFromParent(); - - // Inherit predecessor's name if it exists... - if (!OldName.empty() && !OnlyPred->hasName()) - OnlyPred->setName(OldName); - - return OnlyPred; -} - /// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true /// if unrolling was succesful, or false if the loop was unmodified. Unrolling /// can only fail when the loop's latch block is not terminated by a conditional @@ -333,7 +287,7 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM) } else { Term->setUnconditionalDest(Dest); // Merge adjacent basic blocks, if possible. - if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) { + if (BasicBlock *Fold = MergeBlockIntoPredecessor(Dest, LI)) { std::replace(Latches.begin(), Latches.end(), Dest, Fold); std::replace(Headers.begin(), Headers.end(), Dest, Fold); } diff --git a/test/Transforms/SimplifyCFG/PhiBlockMerge.ll b/test/Transforms/SimplifyCFG/PhiBlockMerge.ll index a648efd..1219dfe 100644 --- a/test/Transforms/SimplifyCFG/PhiBlockMerge.ll +++ b/test/Transforms/SimplifyCFG/PhiBlockMerge.ll @@ -9,6 +9,7 @@ define i32 @test(i1 %a, i1 %b) { O: ; preds = %0 br i1 %b, label %N, label %Q Q: ; preds = %O + call void @foo() br label %N N: ; preds = %Q, %O ; This block should be foldable into M @@ -20,3 +21,4 @@ M: ; preds = %N, %0 ret i32 %R } +declare void @foo() |