LoopSimplify.cpp revision 7e7ad49c23867a5de8e15adfd946fdfa4ba68902
138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//===- LoopPreheaders.cpp - Loop Preheader Insertion Pass -----------------===// 238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 3dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Insert Loop pre-headers and exit blocks into the CFG for each function in the 4dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// module. This pass updates loop information and dominator information. 5dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 6dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop pre-header insertion guarantees that there is a single, non-critical 7dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// entry edge from outside of the loop to the loop header. This simplifies a 8dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// number of analyses and transformations, such as LICM. 9dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 10dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop exit-block insertion guarantees that all exit blocks from the loop 11dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// (blocks which are outside of the loop that have predecessors inside of the 12dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// loop) are dominated by the loop header. This simplifies transformations such 13dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// as store-sinking that is built into LICM. 14dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 15dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Note that the simplifycfg pass will clean up blocks which are split out but 16dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// end up being unneccesary, so usage of this pass does not neccesarily 17dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// pessimize generated code. 1838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 1938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//===----------------------------------------------------------------------===// 2038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 2138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h" 2238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Analysis/Dominators.h" 2338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Analysis/LoopInfo.h" 2438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Function.h" 2538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/iTerminators.h" 2638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/iPHINode.h" 2738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Constant.h" 2838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 29dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner#include "Support/SetOperations.h" 30a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner#include "Support/Statistic.h" 3138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 3238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattnernamespace { 33a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumInserted("preheaders", "Number of pre-header nodes inserted"); 3438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 3538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner struct Preheaders : public FunctionPass { 3638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual bool runOnFunction(Function &F); 3738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 3838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 3938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 4038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addRequired<LoopInfo>(); 41dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addRequired<DominatorSet>(); 4238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 4338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<LoopInfo>(); 4438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorSet>(); 4538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<ImmediateDominators>(); 4638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 47dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addPreserved<DominanceFrontier>(); 4838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added.... 4938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 5038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 5138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool ProcessLoop(Loop *L); 52dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 53dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds); 54dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner void RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 5538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner void InsertPreheaderForLoop(Loop *L); 5638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 5738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 580bd3616b0b118b6616fabc9a16d291601b16b870Chris Lattner RegisterOpt<Preheaders> X("preheaders", "Natural loop pre-header insertion"); 5938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 6038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 6138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass... 6238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattnerconst PassInfo *LoopPreheadersID = X.getPassInfo(); 6338acf9e85d25f022309372c26d54ecb7c77840f2Chris LattnerPass *createLoopPreheaderInsertionPass() { return new Preheaders(); } 6438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 6538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 6638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 6738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 6838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 6938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattnerbool Preheaders::runOnFunction(Function &F) { 7038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 7138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner LoopInfo &LI = getAnalysis<LoopInfo>(); 7238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 7338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned i = 0, e = LI.getTopLevelLoops().size(); i != e; ++i) 7438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed |= ProcessLoop(LI.getTopLevelLoops()[i]); 7538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 7638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 7738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 7838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 7938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 8038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 8138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 8238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 8338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattnerbool Preheaders::ProcessLoop(Loop *L) { 8438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 8538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 8638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Does the loop already have a preheader? If so, don't modify the loop... 8738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (L->getLoopPreheader() == 0) { 8838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner InsertPreheaderForLoop(L); 8938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NumInserted++; 9038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed = true; 9138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 9238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 93dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 94dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 95dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) 96dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!DS.dominates(Header, L->getExitBlocks()[i])) { 97dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner RewriteLoopExitBlock(L, L->getExitBlocks()[i]); 987e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(DS.dominates(Header, L->getExitBlocks()[i]) && 997e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner "RewriteLoopExitBlock failed?"); 100dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NumInserted++; 101dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Changed = true; 102dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 103dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 10438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner const std::vector<Loop*> &SubLoops = L->getSubLoops(); 10538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 10638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed |= ProcessLoop(SubLoops[i]); 10738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 110dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// SplitBlockPredecessors - Split the specified block into two blocks. We want 111dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// to move the predecessors specified in the Preds list to point to the new 112dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// block, leaving the remaining predecessors pointing to BB. This method 113dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// updates the SSA PHINode's, but no other analyses. 11438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 115dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris LattnerBasicBlock *Preheaders::SplitBlockPredecessors(BasicBlock *BB, 116dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const char *Suffix, 117dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds) { 11838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 119dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create new basic block, insert right before the original block... 120dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB); 12138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 12238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader first gets an unconditional branch to the loop header... 123dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BranchInst *BI = new BranchInst(BB); 12438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NewBB->getInstList().push_back(BI); 12538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 126dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // For every PHI node in the block, insert a PHI node into NewBB where the 127dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming values from the out of loop edges are moved to NewBB. We have two 128dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // possible cases here. If the loop is dead, we just insert dummy entries 129dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // into the PHI nodes for the new edge. If the loop is not dead, we move the 130dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming edges in BB into new PHI nodes in NewBB. 13138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 132dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!Preds.empty()) { // Is the loop not obviously dead? 133dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (BasicBlock::iterator I = BB->begin(); 13438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { 13538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Create the new PHI node, insert it into NewBB at the end of the block 13738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 13838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 13938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Move all of the edges from blocks outside the loop to the new PHI 140dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 141dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Value *V = PN->removeIncomingValue(Preds[i]); 142dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewPHI->addIncoming(V, Preds[i]); 14338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 14438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 14538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Add an incoming value to the PHI node in the loop for the preheader 14638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // edge 14738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(NewPHI, NewBB); 14838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 14938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 15038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Now that the PHI nodes are updated, actually move the edges from 151dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Preds to point to NewBB instead of BB. 15238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 153dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 154dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 15538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 156dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (TI->getSuccessor(s) == BB) 15738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner TI->setSuccessor(s, NewBB); 15838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 15938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 16038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } else { // Otherwise the loop is dead... 161dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (BasicBlock::iterator I = BB->begin(); 16238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PHINode *PN = dyn_cast<PHINode>(&*I); ++I) 16338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Insert dummy values as the incoming value... 16438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 165dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 166dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner return NewBB; 167dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 16838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 16938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 170dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 171dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 172dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 173dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 174dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattnervoid Preheaders::InsertPreheaderForLoop(Loop *L) { 175dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 176dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 177dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 178dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> OutsideBlocks; 179dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 180dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PI != PE; ++PI) 181dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!L->contains(*PI)) // Coming in from outside the loop? 182dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner OutsideBlocks.push_back(*PI); // Keep track of it... 183dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 184dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Split out the loop pre-header 185dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 186dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 187dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 18838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner //===--------------------------------------------------------------------===// 18938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Update analysis results now that we have preformed the transformation 19038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 19138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 19238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We know that we have loop information to update... update it now. 19338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (Loop *Parent = L->getParentLoop()) 19438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 19538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 196dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 197dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner { 19838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The blocks that dominate NewBB are the blocks that dominate Header, 19938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // minus Header, plus NewBB. 200dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet::DomSetType DomSet = DS.getDominators(Header); 2014d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner DomSet.insert(NewBB); // We dominate ourself 20238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DomSet.erase(Header); // Header does not dominate us... 203dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addBasicBlock(NewBB, DomSet); 2044d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner 2054d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner // The newly created basic block dominates all nodes dominated by Header. 2064d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner for (Function::iterator I = Header->getParent()->begin(), 2074d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner E = Header->getParent()->end(); I != E; ++I) 208dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DS.dominates(Header, I)) 209dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addDominator(I, NewBB); 21038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 21138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 21238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Update immediate dominator information if we have it... 21338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 21438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Whatever i-dominated the header node now immediately dominates NewBB 21538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner ID->addNewBlock(NewBB, ID->get(Header)); 21638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 21738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader now is the immediate dominator for the header node... 21838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner ID->setImmediateDominator(Header, NewBB); 21938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 22038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 22138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Update DominatorTree information if it is active. 22238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 22338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The immediate dominator of the preheader is the immediate dominator of 22438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // the old header. 22538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 22638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DominatorTree::Node *HeaderNode = DT->getNode(Header); 2274d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner DominatorTree::Node *PHNode = DT->createNewNode(NewBB, 2284d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner HeaderNode->getIDom()); 22938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 23038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Change the header node so that PNHode is the new immediate dominator 23138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DT->changeImmediateDominator(HeaderNode, PHNode); 23238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 233dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 234dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 235dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 236dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 237dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // everything that Header does, and it strictly dominates Header in 238dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // addition. 239dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 240dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 241dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewDFSet.erase(Header); 242dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 243dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 244dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 245dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // replacing occurances of Header with NewBB in some cases. If a block 246dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // dominates a (now) predecessor of NewBB, but did not strictly dominate 247dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Header, it will have Header in it's DF set, but should now have NewBB in 248dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // its set. 249dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 250dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Get all of the dominators of the predecessor... 251dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const DominatorSet::DomSetType &PredDoms = 252dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.getDominators(OutsideBlocks[i]); 253dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 254dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PDE = PredDoms.end(); PDI != PDE; ++PDI) { 255dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *PredDom = *PDI; 256dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // If the loop header is in DF(PredDom), then PredDom didn't dominate 257dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // the header but did dominate a predecessor outside of the loop. Now 258dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // we change this entry to include the preheader in the DF instead of 259dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // the header. 260dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::iterator DFI = DF->find(PredDom); 261dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DFI != DF->end() && "No dominance frontier for node?"); 262dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DFI->second.count(Header)) { 263dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->removeFromFrontier(DFI, Header); 264dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addToFrontier(DFI, NewBB); 265dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 266dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 267dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 268dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 269dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 270dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 271dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattnervoid Preheaders::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 272dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 273dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(!DS.dominates(L->getHeader(), Exit) && 274dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner "Loop already dominates exit block??"); 2757e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit) 2767e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner != L->getExitBlocks().end() && "Not a current exit block!"); 277dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 278dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> LoopBlocks; 279dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 280dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (L->contains(*I)) 281dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner LoopBlocks.push_back(*I); 282dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 2837e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 2847e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 2857e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 28669269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner // Update Loop Information - we know that the new block will be in the parent 28769269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner // loop of L. 28869269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner if (Loop *Parent = L->getParentLoop()) 28969269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 2907e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner L->changeExitBlock(Exit, NewBB); // Update exit block information 29169269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner 292dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominator information... The blocks that dominate NewBB are the 293dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // intersection of the dominators of predecessors, plus the block itself. 294dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // The newly created basic block does not dominate anything except itself. 295dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // 296dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet::DomSetType NewBBDomSet = DS.getDominators(LoopBlocks[0]); 297dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 1, e = LoopBlocks.size(); i != e; ++i) 298dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner set_intersect(NewBBDomSet, DS.getDominators(LoopBlocks[i])); 299dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 300dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addBasicBlock(NewBB, NewBBDomSet); 301dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 302dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update immediate dominator information if we have it... 303dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBBIDom = 0; 304dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 305dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // This block does not strictly dominate anything, so it is not an immediate 306dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // dominator. To find the immediate dominator of the new exit node, we 307dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // trace up the immediate dominators of a predecessor until we find a basic 308dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // block that dominates the exit block. 309dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // 310dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Dom = LoopBlocks[0]; // Some random predecessor... 311dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 312dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(Dom != 0 && "No shared dominator found???"); 313dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Dom = ID->get(Dom); 314dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 315dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 316dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Set the immediate dominator now... 317dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner ID->addNewBlock(NewBB, Dom); 318dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 319dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 320dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 321dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update DominatorTree information if it is active. 322dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 323dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // NewBB doesn't dominate anything, so just create a node and link it into 324dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // its immediate dominator. If we don't have ImmediateDominator info 325dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // around, calculate the idom as above. 326dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorTree::Node *NewBBIDomNode; 327dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (NewBBIDom) { 328dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = DT->getNode(NewBBIDom); 329dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } else { 330dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = DT->getNode(LoopBlocks[0]); // Random pred 331dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner while (!NewBBDomSet.count(NewBBIDomNode->getNode())) { 332dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = NewBBIDomNode->getIDom(); 333dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(NewBBIDomNode && "No shared dominator found??"); 334dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 335dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 336dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 337dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create the new dominator tree node... 338dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DT->createNewNode(NewBB, NewBBIDomNode); 339dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 340dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 341dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 342dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 343dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // DF(NewBB) is {Exit} because NewBB does not strictly dominate Exit, but it 344dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // does dominate itself (and there is an edge (NewBB -> Exit)). 345dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::DomSetType NewDFSet; 346dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewDFSet.insert(Exit); 347dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 348dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 349dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 350dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // replacing occurances of Exit with NewBB in some cases. If a block 351dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // dominates a (now) predecessor of NewBB, but did not strictly dominate 352dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Exit, it will have Exit in it's DF set, but should now have NewBB in its 353dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // set. 354dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { 355dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Get all of the dominators of the predecessor... 356dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const DominatorSet::DomSetType &PredDoms =DS.getDominators(LoopBlocks[i]); 357dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 358dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PDE = PredDoms.end(); PDI != PDE; ++PDI) { 359dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *PredDom = *PDI; 360dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Make sure to only rewrite blocks that are part of the loop... 361dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (L->contains(PredDom)) { 362dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // If the exit node is in DF(PredDom), then PredDom didn't dominate 363dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Exit but did dominate a predecessor inside of the loop. Now we 364dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // change this entry to include NewBB in the DF instead of Exit. 365dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::iterator DFI = DF->find(PredDom); 366dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DFI != DF->end() && "No dominance frontier for node?"); 367dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DFI->second.count(Exit)) { 368dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->removeFromFrontier(DFI, Exit); 369dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addToFrontier(DFI, NewBB); 370dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 371dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 372dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 373dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 374dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 37538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 376