From 29874e0dc6c4e55bc384611273343bb358982cc3 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 3 Dec 2008 19:44:02 +0000 Subject: [PATCH] Factor some code into a new FoldSingleEntryPHINodes method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60501 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/BasicBlockUtils.h | 8 ++++++++ include/llvm/Transforms/Utils/Local.h | 2 +- lib/Transforms/Scalar/CondPropagate.cpp | 19 ++++++------------- lib/Transforms/Utils/BasicBlockUtils.cpp | 18 ++++++++++++++++++ lib/Transforms/Utils/SimplifyCFG.cpp | 5 +---- lib/Transforms/Utils/UnrollLoop.cpp | 9 +++------ 6 files changed, 37 insertions(+), 24 deletions(-) diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 6dd92dd71ff..429d3b6edcf 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -30,6 +30,14 @@ class AliasAnalysis; /// predecessors. void DeleteDeadBlock(BasicBlock *BB); + +/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are +/// any single-entry PHI nodes in it, fold them away. This handles the case +/// when all entries to the PHI nodes in a block are guaranteed equal, such as +/// when the block has exactly one predecessor. +void FoldSingleEntryPHINodes(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); diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 3fb05357233..3ccc61280f7 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -56,7 +56,7 @@ void RecursivelyDeleteTriviallyDeadInstructions(Value *V, SmallVectorImpl *DeadInst = 0); //===----------------------------------------------------------------------===// -// Control Flow Graph Restructuring... +// Control Flow Graph Restructuring. // /// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its diff --git a/lib/Transforms/Scalar/CondPropagate.cpp b/lib/Transforms/Scalar/CondPropagate.cpp index 126e13e453a..2e899432909 100644 --- a/lib/Transforms/Scalar/CondPropagate.cpp +++ b/lib/Transforms/Scalar/CondPropagate.cpp @@ -14,12 +14,13 @@ #define DEBUG_TYPE "condprop" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Constants.h" #include "llvm/Function.h" #include "llvm/Instructions.h" #include "llvm/Pass.h" #include "llvm/Type.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Compiler.h" @@ -95,13 +96,9 @@ void CondProp::SimplifyBlock(BasicBlock *BB) { BB != BI->getSuccessor(0)) { BasicBlock *Succ = BI->getSuccessor(0); - // If Succ has any PHI nodes, they are all single-entry PHI's. - while (PHINode *PN = dyn_cast(Succ->begin())) { - assert(PN->getNumIncomingValues() == 1 && - "PHI doesn't match parent block"); - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - PN->eraseFromParent(); - } + // If Succ has any PHI nodes, they are all single-entry PHI's. Eliminate + // them. + FoldSingleEntryPHINodes(Succ); // Remove BI. BI->eraseFromParent(); @@ -205,11 +202,7 @@ void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) { // OldSucc had multiple successors. If ToBB has multiple predecessors, then // the edge between them would be critical, which we already took care of. // If ToBB has single operand PHI node then take care of it here. - while (PHINode *PN = dyn_cast(ToBB->begin())) { - assert(PN->getNumIncomingValues() == 1 && "Critical Edge Found!"); - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - PN->eraseFromParent(); - } + FoldSingleEntryPHINodes(ToBB); // Update PHI nodes in OldSucc to know that FromBB no longer branches to it. OldSucc->removePredecessor(FromBB); diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index 45cfe8f181f..431424ee9f3 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -54,6 +54,24 @@ void llvm::DeleteDeadBlock(BasicBlock *BB) { BB->eraseFromParent(); } +/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are +/// any single-entry PHI nodes in it, fold them away. This handles the case +/// when all entries to the PHI nodes in a block are guaranteed equal, such as +/// when the block has exactly one predecessor. +void llvm::FoldSingleEntryPHINodes(BasicBlock *BB) { + if (!isa(BB->begin())) + return; + + while (PHINode *PN = dyn_cast(BB->begin())) { + if (PN->getIncomingValue(0) != PN) + PN->replaceAllUsesWith(PN->getIncomingValue(0)); + else + PN->replaceAllUsesWith(UndefValue::get(PN->getType())); + PN->eraseFromParent(); + } +} + + /// 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) { diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index f4faeb3deb5..d6465f599cf 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -1101,10 +1101,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { // Degenerate case of a single entry PHI. if (PN->getNumIncomingValues() == 1) { - if (PN->getIncomingValue(0) != PN) - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - else - PN->replaceAllUsesWith(UndefValue::get(PN->getType())); + FoldSingleEntryPHINodes(PN->getParent()); PN->eraseFromParent(); return true; } diff --git a/lib/Transforms/Utils/UnrollLoop.cpp b/lib/Transforms/Utils/UnrollLoop.cpp index 63493dc66a3..caef7ec5c45 100644 --- a/lib/Transforms/Utils/UnrollLoop.cpp +++ b/lib/Transforms/Utils/UnrollLoop.cpp @@ -25,13 +25,14 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Support/Debug.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" #include using namespace llvm; -/* TODO: Should these be here or in LoopUnroll? */ +// TODO: Should these be here or in LoopUnroll? STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled"); STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)"); @@ -68,11 +69,7 @@ static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { // multiple duplicate (but guaranteed to be equal) entries for the // incoming edges. This occurs when there are multiple edges from // OnlyPred to OnlySucc. - // - while (PHINode *PN = dyn_cast(&BB->front())) { - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - BB->getInstList().pop_front(); // Delete the phi node... - } + FoldSingleEntryPHINodes(BB); // Delete the unconditional branch from the predecessor... OnlyPred->getInstList().pop_back(); -- 2.11.0