X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FBasicBlockUtils.cpp;h=b4f74f97e9786dd1e93843742ecd22cc3cef5d7b;hb=1f35b178858c693261b08ab41022f92e250e08b4;hp=93a8c8e593433809738bbc8b6e737b228ce87a71;hpb=280a6e607d8eb7401749a92db624a82de47da777;p=oota-llvm.git diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index 93a8c8e5934..b4f74f97e97 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -15,14 +15,181 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Function.h" #include "llvm/Instructions.h" +#include "llvm/IntrinsicInst.h" #include "llvm/Constant.h" #include "llvm/Type.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/ValueHandle.h" #include using namespace llvm; +/// DeleteDeadBlock - Delete the specified block, which must have no +/// predecessors. +void llvm::DeleteDeadBlock(BasicBlock *BB) { + assert((pred_begin(BB) == pred_end(BB) || + // Can delete self loop. + BB->getSinglePredecessor() == BB) && "Block is not dead!"); + TerminatorInst *BBTerm = BB->getTerminator(); + + // Loop through all of our successors and make sure they know that one + // of their predecessors is going away. + for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) + BBTerm->getSuccessor(i)->removePredecessor(BB); + + // Zap all the instructions in the block. + while (!BB->empty()) { + Instruction &I = BB->back(); + // If this instruction is used, replace uses with an arbitrary value. + // Because control flow can't get here, we don't care what we replace the + // value with. Note that since this block is unreachable, and all values + // contained within it must dominate their uses, that all uses will + // eventually be removed (they are themselves dead). + if (!I.use_empty()) + I.replaceAllUsesWith(UndefValue::get(I.getType())); + BB->getInstList().pop_back(); + } + + // Zap the block! + 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, Pass *P) { + if (!isa(BB->begin())) return; + + AliasAnalysis *AA = 0; + MemoryDependenceAnalysis *MemDep = 0; + if (P) { + AA = P->getAnalysisIfAvailable(); + MemDep = P->getAnalysisIfAvailable(); + } + + while (PHINode *PN = dyn_cast(BB->begin())) { + if (PN->getIncomingValue(0) != PN) + PN->replaceAllUsesWith(PN->getIncomingValue(0)); + else + PN->replaceAllUsesWith(UndefValue::get(PN->getType())); + + if (MemDep) + MemDep->removeInstruction(PN); // Memdep updates AA itself. + else if (AA && isa(PN->getType())) + AA->deleteValue(PN); + + PN->eraseFromParent(); + } +} + + +/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it +/// is dead. Also recursively delete any operands that become dead as +/// a result. This includes tracing the def-use list from the PHI to see if +/// it is ultimately unused or if it reaches an unused cycle. +bool llvm::DeleteDeadPHIs(BasicBlock *BB) { + // Recursively deleting a PHI may cause multiple PHIs to be deleted + // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete. + SmallVector PHIs; + for (BasicBlock::iterator I = BB->begin(); + PHINode *PN = dyn_cast(I); ++I) + PHIs.push_back(PN); + + bool Changed = false; + for (unsigned i = 0, e = PHIs.size(); i != e; ++i) + if (PHINode *PN = dyn_cast_or_null(PHIs[i].operator Value*())) + Changed |= RecursivelyDeleteDeadPHINode(PN); + + return Changed; +} + +/// 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) { + // Don't merge away blocks who have their address taken. + if (BB->hasAddressTaken()) return false; + + // Can't merge if there are multiple predecessors, or no predecessors. + BasicBlock *PredBB = BB->getUniquePredecessor(); + if (!PredBB) return false; + + // Don't break self-loops. + if (PredBB == BB) return false; + // Don't break invokes. + if (isa(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; + } + + // 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(BI)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + if (PN->getIncomingValue(i) == PN) + return false; + } else + break; + } + + // Begin by getting rid of unneeded PHIs. + if (isa(BB->front())) + FoldSingleEntryPHINodes(BB, P); + + // Delete the unconditional branch from the predecessor... + PredBB->getInstList().pop_back(); + + // Make all PHI nodes that referred to BB now refer to Pred as their + // source... + BB->replaceAllUsesWith(PredBB); + + // Move all definitions in the successor to the predecessor... + PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); + + // Inherit predecessors name if it exists. + if (!PredBB->hasName()) + PredBB->takeName(BB); + + // Finally, erase the old block and update dominator info. + if (P) { + if (DominatorTree *DT = P->getAnalysisIfAvailable()) { + if (DomTreeNode *DTN = DT->getNode(BB)) { + DomTreeNode *PredDTN = DT->getNode(PredBB); + SmallVector Children(DTN->begin(), DTN->end()); + for (SmallVector::iterator DI = Children.begin(), + DE = Children.end(); DI != DE; ++DI) + DT->changeImmediateDominator(*DI, PredDTN); + + DT->eraseNode(BB); + } + + if (LoopInfo *LI = P->getAnalysisIfAvailable()) + LI->removeBlock(BB); + + if (MemoryDependenceAnalysis *MD = + P->getAnalysisIfAvailable()) + MD->invalidateCachedPredecessors(); + } + } + + BB->eraseFromParent(); + return true; +} + /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) /// with a value, then remove and delete the original instruction. /// @@ -68,68 +235,31 @@ void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); } -/// RemoveSuccessor - Change the specified terminator instruction such that its -/// successor SuccNum no longer exists. Because this reduces the outgoing -/// degree of the current basic block, the actual terminator instruction itself -/// may have to be changed. In the case where the last successor of the block -/// is deleted, a return instruction is inserted in its place which can cause a -/// surprising change in program behavior if it is not expected. -/// -void llvm::RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) { - assert(SuccNum < TI->getNumSuccessors() && - "Trying to remove a nonexistant successor!"); - - // If our old successor block contains any PHI nodes, remove the entry in the - // PHI nodes that comes from this branch... - // - BasicBlock *BB = TI->getParent(); - TI->getSuccessor(SuccNum)->removePredecessor(BB); - - TerminatorInst *NewTI = 0; - switch (TI->getOpcode()) { - case Instruction::Br: - // If this is a conditional branch... convert to unconditional branch. - if (TI->getNumSuccessors() == 2) { - cast(TI)->setUnconditionalDest(TI->getSuccessor(1-SuccNum)); - } else { // Otherwise convert to a return instruction... - Value *RetVal = 0; - - // Create a value to return... if the function doesn't return null... - if (BB->getParent()->getReturnType() != Type::VoidTy) - RetVal = Constant::getNullValue(BB->getParent()->getReturnType()); - - // Create the return... - NewTI = ReturnInst::Create(RetVal); - } - break; - - case Instruction::Invoke: // Should convert to call - case Instruction::Switch: // Should remove entry - default: - case Instruction::Ret: // Cannot happen, has no successors! - assert(0 && "Unhandled terminator instruction type in RemoveSuccessor!"); - abort(); +/// GetSuccessorNumber - Search for the specified successor of basic block BB +/// and return its position in the terminator instruction's list of +/// successors. It is an error to call this with a block that is not a +/// successor. +unsigned llvm::GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ) { + TerminatorInst *Term = BB->getTerminator(); +#ifndef NDEBUG + unsigned e = Term->getNumSuccessors(); +#endif + for (unsigned i = 0; ; ++i) { + assert(i != e && "Didn't find edge?"); + if (Term->getSuccessor(i) == Succ) + return i; } - - if (NewTI) // If it's a different instruction, replace. - ReplaceInstWithInst(TI, NewTI); + return 0; } /// SplitEdge - Split the edge connecting specified block. Pass P must /// not be NULL. BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { - TerminatorInst *LatchTerm = BB->getTerminator(); - unsigned SuccNum = 0; - for (unsigned i = 0, e = LatchTerm->getNumSuccessors(); ; ++i) { - assert(i != e && "Didn't find edge?"); - if (LatchTerm->getSuccessor(i) == Succ) { - SuccNum = i; - break; - } - } + unsigned SuccNum = GetSuccessorNumber(BB, Succ); // If this is a critical edge, let SplitCriticalEdge do it. - if (SplitCriticalEdge(BB->getTerminator(), SuccNum, P)) + TerminatorInst *LatchTerm = BB->getTerminator(); + if (SplitCriticalEdge(LatchTerm, SuccNum, P)) return LatchTerm->getSuccessor(SuccNum); // If the edge isn't critical, then BB has a single successor or Succ has a @@ -139,14 +269,15 @@ BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { // If the successor only has a single pred, split the top of the successor // block. assert(SP == BB && "CFG broken"); + SP = NULL; return SplitBlock(Succ, Succ->begin(), P); - } else { - // Otherwise, if BB has a single successor, split it at the bottom of the - // block. - assert(BB->getTerminator()->getNumSuccessors() == 1 && - "Should have a single succ!"); - return SplitBlock(BB, BB->getTerminator(), P); } + + // Otherwise, if BB has a single successor, split it at the bottom of the + // block. + assert(BB->getTerminator()->getNumSuccessors() == 1 && + "Should have a single succ!"); + return SplitBlock(BB, BB->getTerminator(), P); } /// SplitBlock - Split the specified block at the specified instruction - every @@ -155,36 +286,31 @@ BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { /// the loop info is updated. /// BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { - - LoopInfo &LI = P->getAnalysis(); BasicBlock::iterator SplitIt = SplitPt; while (isa(SplitIt)) ++SplitIt; BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); - // The new block lives in whichever loop the old one did. - if (Loop *L = LI.getLoopFor(Old)) - L->addBasicBlockToLoop(New, LI.getBase()); - - if (DominatorTree *DT = P->getAnalysisToUpdate()) - { - // Old dominates New. New node domiantes all other nodes dominated by Old. - DomTreeNode *OldNode = DT->getNode(Old); - std::vector Children; - for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); - I != E; ++I) - Children.push_back(*I); + // The new block lives in whichever loop the old one did. This preserves + // LCSSA as well, because we force the split point to be after any PHI nodes. + if (LoopInfo *LI = P->getAnalysisIfAvailable()) + if (Loop *L = LI->getLoopFor(Old)) + L->addBasicBlockToLoop(New, LI->getBase()); - DomTreeNode *NewNode = DT->addNewBlock(New,Old); + if (DominatorTree *DT = P->getAnalysisIfAvailable()) { + // Old dominates New. New node dominates all other nodes dominated by Old. + DomTreeNode *OldNode = DT->getNode(Old); + std::vector Children; + for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); + I != E; ++I) + Children.push_back(*I); + DomTreeNode *NewNode = DT->addNewBlock(New,Old); for (std::vector::iterator I = Children.begin(), E = Children.end(); I != E; ++I) DT->changeImmediateDominator(*I, NewNode); - } + } - if (DominanceFrontier *DF = P->getAnalysisToUpdate()) - DF->splitBlock(Old); - return New; } @@ -195,32 +321,64 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { /// Preds array, which has NumPreds elements in it. The new block is given a /// suffix of 'Suffix'. /// -/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and -/// DominanceFrontier, but no other analyses. +/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, +/// LoopInfo, and LCCSA but no other analyses. In particular, it does not +/// preserve LoopSimplify (because it's complicated to handle the case where one +/// of the edges being split is an exit of a loop with other exits). +/// BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds, unsigned NumPreds, const char *Suffix, Pass *P) { // Create new basic block, insert right before the original block. - BasicBlock *NewBB = - BasicBlock::Create(BB->getName()+Suffix, BB->getParent(), BB); + BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, + BB->getParent(), BB); // The new block unconditionally branches to the old block. BranchInst *BI = BranchInst::Create(BB, NewBB); + LoopInfo *LI = P ? P->getAnalysisIfAvailable() : 0; + Loop *L = LI ? LI->getLoopFor(BB) : 0; + bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); + // Move the edges from Preds to point to NewBB instead of BB. - for (unsigned i = 0; i != NumPreds; ++i) + // While here, if we need to preserve loop analyses, collect + // some information about how this split will affect loops. + bool HasLoopExit = false; + bool IsLoopEntry = !!L; + bool SplitMakesNewLoopHeader = false; + for (unsigned i = 0; i != NumPreds; ++i) { + // This is slightly more strict than necessary; the minimum requirement + // is that there be no more than one indirectbr branching to BB. And + // all BlockAddress uses would need to be updated. + assert(!isa(Preds[i]->getTerminator()) && + "Cannot split an edge from an IndirectBrInst"); + Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); - - // Update dominator tree and dominator frontier if available. - DominatorTree *DT = P ? P->getAnalysisToUpdate() : 0; + + if (LI) { + // If we need to preserve LCSSA, determine if any of + // the preds is a loop exit. + if (PreserveLCSSA) + if (Loop *PL = LI->getLoopFor(Preds[i])) + if (!PL->contains(BB)) + HasLoopExit = true; + // If we need to preserve LoopInfo, note whether any of the + // preds crosses an interesting loop boundary. + if (L) { + if (L->contains(Preds[i])) + IsLoopEntry = false; + else + SplitMakesNewLoopHeader = true; + } + } + } + + // Update dominator tree if available. + DominatorTree *DT = P ? P->getAnalysisIfAvailable() : 0; if (DT) DT->splitBlock(NewBB); - if (DominanceFrontier *DF = P ? P->getAnalysisToUpdate():0) - DF->splitBlock(NewBB); - AliasAnalysis *AA = P ? P->getAnalysisToUpdate() : 0; - - + // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI // node becomes an incoming value for BB's phi node. However, if the Preds // list is empty, we need to insert dummy entries into the PHI nodes in BB to @@ -231,20 +389,54 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, cast(I)->addIncoming(UndefValue::get(I->getType()), NewBB); return NewBB; } + + AliasAnalysis *AA = P ? P->getAnalysisIfAvailable() : 0; + + if (L) { + if (IsLoopEntry) { + // Add the new block to the nearest enclosing loop (and not an + // adjacent loop). To find this, examine each of the predecessors and + // determine which loops enclose them, and select the most-nested loop + // which contains the loop containing the block being split. + Loop *InnermostPredLoop = 0; + for (unsigned i = 0; i != NumPreds; ++i) + if (Loop *PredLoop = LI->getLoopFor(Preds[i])) { + // Seek a loop which actually contains the block being split (to + // avoid adjacent loops). + while (PredLoop && !PredLoop->contains(BB)) + PredLoop = PredLoop->getParentLoop(); + // Select the most-nested of these loops which contains the block. + if (PredLoop && + PredLoop->contains(BB) && + (!InnermostPredLoop || + InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) + InnermostPredLoop = PredLoop; + } + if (InnermostPredLoop) + InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + } else { + L->addBasicBlockToLoop(NewBB, LI->getBase()); + if (SplitMakesNewLoopHeader) + L->moveToHeader(NewBB); + } + } // Otherwise, create a new PHI node in NewBB for each PHI node in BB. for (BasicBlock::iterator I = BB->begin(); isa(I); ) { PHINode *PN = cast(I++); // Check to see if all of the values coming in are the same. If so, we - // don't need to create a new PHI node. - Value *InVal = PN->getIncomingValueForBlock(Preds[0]); - for (unsigned i = 1; i != NumPreds; ++i) - if (InVal != PN->getIncomingValueForBlock(Preds[i])) { - InVal = 0; - break; - } - + // don't need to create a new PHI node, unless it's needed for LCSSA. + Value *InVal = 0; + if (!HasLoopExit) { + InVal = PN->getIncomingValueForBlock(Preds[0]); + for (unsigned i = 1; i != NumPreds; ++i) + if (InVal != PN->getIncomingValueForBlock(Preds[i])) { + InVal = 0; + break; + } + } + if (InVal) { // If all incoming values for the new PHI would be the same, just don't // make a new PHI. Instead, just remove the incoming values from the old @@ -255,7 +447,7 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // If the values coming into the block are not the same, we need a PHI. // Create the new PHI node, insert it into NewBB at the end of the block PHINode *NewPHI = - PHINode::Create(PN->getType(), PN->getName()+".ph", BI); + PHINode::Create(PN->getType(), NumPreds, PN->getName()+".ph", BI); if (AA) AA->copyValue(PN, NewPHI); // Move all of the PHI values for 'Preds' to the new PHI. @@ -269,17 +461,90 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // Add an incoming value to the PHI node in the loop for the preheader // edge. PN->addIncoming(InVal, NewBB); - - // Check to see if we can eliminate this phi node. - if (Value *V = PN->hasConstantValue(DT != 0)) { - Instruction *I = dyn_cast(V); - if (!I || DT == 0 || DT->dominates(I, PN)) { - PN->replaceAllUsesWith(V); - if (AA) AA->deleteValue(PN); - PN->eraseFromParent(); - } - } } return NewBB; } + +/// FindFunctionBackedges - Analyze the specified function to find all of the +/// loop backedges in the function and return them. This is a relatively cheap +/// (compared to computing dominators and loop info) analysis. +/// +/// The output is added to Result, as pairs of edge info. +void llvm::FindFunctionBackedges(const Function &F, + SmallVectorImpl > &Result) { + const BasicBlock *BB = &F.getEntryBlock(); + if (succ_begin(BB) == succ_end(BB)) + return; + + SmallPtrSet Visited; + SmallVector, 8> VisitStack; + SmallPtrSet InStack; + + Visited.insert(BB); + VisitStack.push_back(std::make_pair(BB, succ_begin(BB))); + InStack.insert(BB); + do { + std::pair &Top = VisitStack.back(); + const BasicBlock *ParentBB = Top.first; + succ_const_iterator &I = Top.second; + + bool FoundNew = false; + while (I != succ_end(ParentBB)) { + BB = *I++; + if (Visited.insert(BB)) { + FoundNew = true; + break; + } + // Successor is in VisitStack, it's a back edge. + if (InStack.count(BB)) + Result.push_back(std::make_pair(ParentBB, BB)); + } + + if (FoundNew) { + // Go down one level if there is a unvisited successor. + InStack.insert(BB); + VisitStack.push_back(std::make_pair(BB, succ_begin(BB))); + } else { + // Go up one level. + InStack.erase(VisitStack.pop_back_val().first); + } + } while (!VisitStack.empty()); +} + +/// FoldReturnIntoUncondBranch - This method duplicates the specified return +/// instruction into a predecessor which ends in an unconditional branch. If +/// the return instruction returns a value defined by a PHI, propagate the +/// right value into the return. It returns the new return instruction in the +/// predecessor. +ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, + BasicBlock *Pred) { + Instruction *UncondBranch = Pred->getTerminator(); + // Clone the return and add it to the end of the predecessor. + Instruction *NewRet = RI->clone(); + Pred->getInstList().push_back(NewRet); + + // If the return instruction returns a value, and if the value was a + // PHI node in "BB", propagate the right value into the return. + for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); + i != e; ++i) + if (PHINode *PN = dyn_cast(*i)) + if (PN->getParent() == BB) + *i = PN->getIncomingValueForBlock(Pred); + + // Update any PHI nodes in the returning block to realize that we no + // longer branch to them. + BB->removePredecessor(Pred); + UncondBranch->eraseFromParent(); + return cast(NewRet); +} + +/// GetFirstDebugLocInBasicBlock - Return first valid DebugLoc entry in a +/// given basic block. +DebugLoc llvm::GetFirstDebugLocInBasicBlock(const BasicBlock *BB) { + if (const Instruction *I = BB->getFirstNonPHI()) + return I->getDebugLoc(); + // Scanning entire block may be too expensive, if the first instruction + // does not have valid location info. + return DebugLoc(); +}