LoopSimplify.cpp revision d0fde30ce850b78371fd1386338350591f9ff494
167a9801bc510ff2c28068361fb30ae397fd1e026Chris Lattner//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 10ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass performs several transformations to transform natural loops into a 11ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// simpler form, which makes subsequent analyses and transformations simpler and 12ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// more effective. 13dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 14dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop pre-header insertion guarantees that there is a single, non-critical 15dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// entry edge from outside of the loop to the loop header. This simplifies a 16dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// number of analyses and transformations, such as LICM. 17dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 18dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop exit-block insertion guarantees that all exit blocks from the loop 19dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// (blocks which are outside of the loop that have predecessors inside of the 20dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// loop) are dominated by the loop header. This simplifies transformations such 21e6f7f61cda02e9aa8f87f84f0c91668e8a6de569Chris Lattner// as store-sinking that are built into LICM. 22dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// This pass also guarantees that loops will have exactly one backedge. 242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// 25dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Note that the simplifycfg pass will clean up blocks which are split out but 26ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// end up being unnecessary, so usage of this pass should not pessimize 27ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// generated code. 28ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// 29ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass obviously modifies the CFG, but updates loop information and 30ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// dominator information. 3138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 3238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//===----------------------------------------------------------------------===// 3338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 3438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h" 3538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Analysis/Dominators.h" 3638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Analysis/LoopInfo.h" 3738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Function.h" 3838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/iTerminators.h" 3938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/iPHINode.h" 4038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Constant.h" 4138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 42dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner#include "Support/SetOperations.h" 43a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner#include "Support/Statistic.h" 4474cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner#include "Support/DepthFirstIterator.h" 4538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 46d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 47d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 4838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattnernamespace { 49ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner Statistic<> 50ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner NumInserted("loopsimplify", "Number of pre-header blocks inserted"); 5138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 52ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner struct LoopSimplify : public FunctionPass { 5338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual bool runOnFunction(Function &F); 5438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 5538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 5638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 5738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addRequired<LoopInfo>(); 58dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addRequired<DominatorSet>(); 5938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 6038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<LoopInfo>(); 6138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorSet>(); 6238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<ImmediateDominators>(); 6338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 64dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addPreserved<DominanceFrontier>(); 6538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added.... 6638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 6738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 6838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool ProcessLoop(Loop *L); 69dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 70dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds); 71dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner void RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 7238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner void InsertPreheaderForLoop(Loop *L); 732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void InsertUniqueBackedgeBlock(Loop *L); 742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> &PredBlocks); 7738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 7838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 79ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner RegisterOpt<LoopSimplify> 80ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner X("loopsimplify", "Canonicalize natural loops", true); 8138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 8238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 8338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass... 8498bf436e2e2ab463d79c54a42a46b12028905330Chris Lattnerconst PassInfo *LoopSimplifyID = X.getPassInfo(); 8598bf436e2e2ab463d79c54a42a46b12028905330Chris LattnerPass *createLoopSimplifyPass() { return new LoopSimplify(); } 8638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 8738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 8838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 8938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 90ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::runOnFunction(Function &F) { 9138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 9238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner LoopInfo &LI = getAnalysis<LoopInfo>(); 9338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 9438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned i = 0, e = LI.getTopLevelLoops().size(); i != e; ++i) 9538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed |= ProcessLoop(LI.getTopLevelLoops()[i]); 9638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 9738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 9838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 9938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 10238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 10338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 104ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::ProcessLoop(Loop *L) { 10538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 10638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Does the loop already have a preheader? If so, don't modify the loop... 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (L->getLoopPreheader() == 0) { 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner InsertPreheaderForLoop(L); 11038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NumInserted++; 11138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed = true; 11238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 11338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 114e6f7f61cda02e9aa8f87f84f0c91668e8a6de569Chris Lattner // Regardless of whether or not we added a preheader to the loop we must 115e6f7f61cda02e9aa8f87f84f0c91668e8a6de569Chris Lattner // guarantee that the preheader dominates all exit nodes. If there are any 116e6f7f61cda02e9aa8f87f84f0c91668e8a6de569Chris Lattner // exit nodes not dominated, split them now. 117dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 118dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 119dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) 120dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!DS.dominates(Header, L->getExitBlocks()[i])) { 121dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner RewriteLoopExitBlock(L, L->getExitBlocks()[i]); 1227e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(DS.dominates(Header, L->getExitBlocks()[i]) && 1237e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner "RewriteLoopExitBlock failed?"); 124dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NumInserted++; 125dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Changed = true; 126dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 127dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 1282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // The preheader may have more than two predecessors at this point (from the 1292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader and from the backedges). To simplify the loop more, insert an 1302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // extra back-edge block in the loop so that there is exactly one backedge. 1312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (L->getNumBackEdges() != 1) { 1322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner InsertUniqueBackedgeBlock(L); 1332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NumInserted++; 1342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Changed = true; 1352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 1362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 13738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner const std::vector<Loop*> &SubLoops = L->getSubLoops(); 13838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 13938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed |= ProcessLoop(SubLoops[i]); 14038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 14138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 14238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 143dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// SplitBlockPredecessors - Split the specified block into two blocks. We want 144dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// to move the predecessors specified in the Preds list to point to the new 145dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// block, leaving the remaining predecessors pointing to BB. This method 146dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// updates the SSA PHINode's, but no other analyses. 14738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 148ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris LattnerBasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 149ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner const char *Suffix, 150dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds) { 15138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 152dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create new basic block, insert right before the original block... 153dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB); 15438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 15538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader first gets an unconditional branch to the loop header... 156dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BranchInst *BI = new BranchInst(BB); 15738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NewBB->getInstList().push_back(BI); 15838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 159dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // For every PHI node in the block, insert a PHI node into NewBB where the 160dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming values from the out of loop edges are moved to NewBB. We have two 161dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // possible cases here. If the loop is dead, we just insert dummy entries 162dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // into the PHI nodes for the new edge. If the loop is not dead, we move the 163dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming edges in BB into new PHI nodes in NewBB. 16438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 165dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!Preds.empty()) { // Is the loop not obviously dead? 166dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (BasicBlock::iterator I = BB->begin(); 167e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 16838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 16938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Create the new PHI node, insert it into NewBB at the end of the block 17038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 17138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 17238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Move all of the edges from blocks outside the loop to the new PHI 173dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 174dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Value *V = PN->removeIncomingValue(Preds[i]); 175dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewPHI->addIncoming(V, Preds[i]); 17638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 17738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 17838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Add an incoming value to the PHI node in the loop for the preheader 17938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // edge 18038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(NewPHI, NewBB); 18138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 18238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 18338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Now that the PHI nodes are updated, actually move the edges from 184dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Preds to point to NewBB instead of BB. 18538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 186dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 187dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 18838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 189dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (TI->getSuccessor(s) == BB) 19038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner TI->setSuccessor(s, NewBB); 19138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 19238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 19338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } else { // Otherwise the loop is dead... 194dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (BasicBlock::iterator I = BB->begin(); 195e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) 19638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Insert dummy values as the incoming value... 19738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 198dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 199dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner return NewBB; 200dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 20138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 2028f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner// ChangeExitBlock - This recursive function is used to change any exit blocks 2038f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner// that use OldExit to use NewExit instead. This is recursive because children 2048f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner// may need to be processed as well. 2058f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner// 2068f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattnerstatic void ChangeExitBlock(Loop *L, BasicBlock *OldExit, BasicBlock *NewExit) { 2078f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner if (L->hasExitBlock(OldExit)) { 2088f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner L->changeExitBlock(OldExit, NewExit); 2098f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner const std::vector<Loop*> &SubLoops = L->getSubLoops(); 2108f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 2118f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner ChangeExitBlock(SubLoops[i], OldExit, NewExit); 2128f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner } 2138f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner} 2148f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner 21538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 216dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 217dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 218dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 219dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 220ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnervoid LoopSimplify::InsertPreheaderForLoop(Loop *L) { 221dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 222dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 223dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 224dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> OutsideBlocks; 225dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 226dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PI != PE; ++PI) 227dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!L->contains(*PI)) // Coming in from outside the loop? 228dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner OutsideBlocks.push_back(*PI); // Keep track of it... 229dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 230dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Split out the loop pre-header 231dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 232dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 233dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 23438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner //===--------------------------------------------------------------------===// 235cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Update analysis results now that we have performed the transformation 23638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 23738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 23838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We know that we have loop information to update... update it now. 23938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (Loop *Parent = L->getParentLoop()) 24038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 2419f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 2429f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner // If the header for the loop used to be an exit node for another loop, then 2439f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner // we need to update this to know that the loop-preheader is now the exit 2449f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner // node. Note that the only loop that could have our header as an exit node 2458f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // is a sibling loop, ie, one with the same parent loop, or one if it's 2468f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // children. 2478f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // 2489f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner const std::vector<Loop*> *ParentSubLoops; 2499f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner if (Loop *Parent = L->getParentLoop()) 2509f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner ParentSubLoops = &Parent->getSubLoops(); 2519f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner else // Must check top-level loops... 2529f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner ParentSubLoops = &getAnalysis<LoopInfo>().getTopLevelLoops(); 2539f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 2548f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // Loop over all sibling loops, performing the substitution (recursively to 2558f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // include child loops)... 2569f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner for (unsigned i = 0, e = ParentSubLoops->size(); i != e; ++i) 2578f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner ChangeExitBlock((*ParentSubLoops)[i], Header, NewBB); 25838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 259dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 260dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner { 26138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The blocks that dominate NewBB are the blocks that dominate Header, 26238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // minus Header, plus NewBB. 263dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet::DomSetType DomSet = DS.getDominators(Header); 2644d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner DomSet.insert(NewBB); // We dominate ourself 26538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DomSet.erase(Header); // Header does not dominate us... 266dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addBasicBlock(NewBB, DomSet); 2674d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner 2684d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner // The newly created basic block dominates all nodes dominated by Header. 2694d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner for (Function::iterator I = Header->getParent()->begin(), 2704d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner E = Header->getParent()->end(); I != E; ++I) 271dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DS.dominates(Header, I)) 272dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addDominator(I, NewBB); 27338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 27438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 27538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Update immediate dominator information if we have it... 27638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 27738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Whatever i-dominated the header node now immediately dominates NewBB 27838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner ID->addNewBlock(NewBB, ID->get(Header)); 27938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 28038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader now is the immediate dominator for the header node... 28138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner ID->setImmediateDominator(Header, NewBB); 28238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 28338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 28438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Update DominatorTree information if it is active. 28538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 28638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The immediate dominator of the preheader is the immediate dominator of 28738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // the old header. 28838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 28938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DominatorTree::Node *HeaderNode = DT->getNode(Header); 2904d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner DominatorTree::Node *PHNode = DT->createNewNode(NewBB, 2914d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner HeaderNode->getIDom()); 29238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 29338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Change the header node so that PNHode is the new immediate dominator 29438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DT->changeImmediateDominator(HeaderNode, PHNode); 29538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 296dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 297dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 298dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 299dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 300dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // everything that Header does, and it strictly dominates Header in 301dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // addition. 302dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 303dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 304dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewDFSet.erase(Header); 305dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 306dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 307dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 308dfa5f83c8ea9fa577c5a42407c3fd8b6c789a6ddMisha Brukman // replacing occurrences of Header with NewBB in some cases. If a block 309dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // dominates a (now) predecessor of NewBB, but did not strictly dominate 310dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Header, it will have Header in it's DF set, but should now have NewBB in 311dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // its set. 312dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 313dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Get all of the dominators of the predecessor... 314dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const DominatorSet::DomSetType &PredDoms = 315dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.getDominators(OutsideBlocks[i]); 316dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 317dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PDE = PredDoms.end(); PDI != PDE; ++PDI) { 318dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *PredDom = *PDI; 319dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // If the loop header is in DF(PredDom), then PredDom didn't dominate 320dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // the header but did dominate a predecessor outside of the loop. Now 321dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // we change this entry to include the preheader in the DF instead of 322dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // the header. 323dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::iterator DFI = DF->find(PredDom); 324dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DFI != DF->end() && "No dominance frontier for node?"); 325dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DFI->second.count(Header)) { 326dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->removeFromFrontier(DFI, Header); 327dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addToFrontier(DFI, NewBB); 328dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 329dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 330dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 331dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 332dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 333dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 334ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnervoid LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 335dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 336dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(!DS.dominates(L->getHeader(), Exit) && 337dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner "Loop already dominates exit block??"); 3387e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit) 3397e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner != L->getExitBlocks().end() && "Not a current exit block!"); 340dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 341dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> LoopBlocks; 342dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 343dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (L->contains(*I)) 344dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner LoopBlocks.push_back(*I); 345dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 3467e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 3477e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 3487e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 34969269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner // Update Loop Information - we know that the new block will be in the parent 35069269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner // loop of L. 35169269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner if (Loop *Parent = L->getParentLoop()) 35269269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 35374cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner 35474cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner // Replace any instances of Exit with NewBB in this and any nested loops... 35574cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I) 3566315938d68df89ea1f5c8f9424d9f3584b74bc8cChris Lattner if (I->hasExitBlock(Exit)) 3576315938d68df89ea1f5c8f9424d9f3584b74bc8cChris Lattner I->changeExitBlock(Exit, NewBB); // Update exit block information 35869269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner 3592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 3602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 3612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 3622ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 3642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 3652ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 3662ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 3672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 3682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 3692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 3702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 3722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 3732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 3742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 3752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 3772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 3782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 3792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (*I != Preheader) BackedgeBlocks.push_back(*I); 3802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 3822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 3832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Instruction *BETerminator = new BranchInst(Header); 3842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().push_back(BETerminator); 3852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 3872ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 3882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 3892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 3912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 3922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (BasicBlock::iterator I = Header->begin(); 3932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 3942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 3952ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BETerminator); 3962ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->op_reserve(2*BackedgeBlocks.size()); 3972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 3982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 3992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 4002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 4012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 4022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 4032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 4042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 4052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 4062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 4072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 4082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 4092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 4102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 4112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 4122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 4132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 4142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 4152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4172ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 4202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 4212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 4222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 4232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 4242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->op_erase(PN->op_begin()+2, PN->op_end()); 4262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 4282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 4292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 4312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 4322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 4332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 4342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 4352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 4362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 4402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // backedge blocks to just to the BEBlock instead of the header. 4412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 4422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 4432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 4442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 4452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 4462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 4472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 4492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 4512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 4522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>()); 4532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Replace any instances of Exit with NewBB in this and any nested loops... 4552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I) 4562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (I->hasExitBlock(Header)) 4572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner I->changeExitBlock(Header, BEBlock); // Update exit block information 4582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 4602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 4612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4622ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 4632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// UpdateDomInfoForRevectoredPreds - This method is used to update the four 4642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// different kinds of dominator information (dominator sets, immediate 4652ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// dominators, dominator trees, and dominance frontiers) after a new block has 4662ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// been added to the CFG. 4672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 4682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// This only supports the case when an existing block (known as "Exit"), had 4692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// some of its predecessors factored into a new basic block. This 4702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// transformation inserts a new basic block ("NewBB"), with a single 4712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// unconditional branch to Exit, and moves some predecessors of "Exit" to now 4722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// branch to NewBB. These predecessors are listed in PredBlocks, even though 4732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// they are the same as pred_begin(NewBB)/pred_end(NewBB). 4742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 4752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 4762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> &PredBlocks) { 4772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(succ_begin(NewBB) != succ_end(NewBB) && 4782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner ++succ_begin(NewBB) == succ_end(NewBB) && 4792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner "NewBB should have a single successor!"); 4802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 4812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 482dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominator information... The blocks that dominate NewBB are the 483dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // intersection of the dominators of predecessors, plus the block itself. 484dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // The newly created basic block does not dominate anything except itself. 485dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // 4862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]); 4872ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 4882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i])); 489dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 490dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addBasicBlock(NewBB, NewBBDomSet); 491dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 492dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update immediate dominator information if we have it... 493dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBBIDom = 0; 494dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 495dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // This block does not strictly dominate anything, so it is not an immediate 496dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // dominator. To find the immediate dominator of the new exit node, we 497dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // trace up the immediate dominators of a predecessor until we find a basic 498dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // block that dominates the exit block. 499dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // 5002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Dom = PredBlocks[0]; // Some random predecessor... 501dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 502dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(Dom != 0 && "No shared dominator found???"); 503dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Dom = ID->get(Dom); 504dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 505dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 506dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Set the immediate dominator now... 507dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner ID->addNewBlock(NewBB, Dom); 508dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 509dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 510dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 511dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update DominatorTree information if it is active. 512dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 513dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // NewBB doesn't dominate anything, so just create a node and link it into 514dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // its immediate dominator. If we don't have ImmediateDominator info 515dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // around, calculate the idom as above. 516dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorTree::Node *NewBBIDomNode; 517dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (NewBBIDom) { 518dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = DT->getNode(NewBBIDom); 519dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } else { 5202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred 521c444a4228f31656f854d15eac671b450df557346Chris Lattner while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) { 522dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = NewBBIDomNode->getIDom(); 523dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(NewBBIDomNode && "No shared dominator found??"); 524dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 525dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 526dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 527dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create the new dominator tree node... 528dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DT->createNewNode(NewBB, NewBBIDomNode); 529dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 530dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 531dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 532dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 533dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // DF(NewBB) is {Exit} because NewBB does not strictly dominate Exit, but it 5342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // does dominate itself (and there is an edge (NewBB -> Exit)). Exit is the 5352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // single successor of NewBB. 536dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::DomSetType NewDFSet; 5372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Exit = *succ_begin(NewBB); 538dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewDFSet.insert(Exit); 539dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 540dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 541dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 5422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // replacing occurrences of Exit with NewBB in some cases. All blocks that 5432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // dominate a block in PredBlocks and contained Exit in their dominance 5442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // frontier must be updated to contain NewBB instead. This only occurs if 5452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // there is more than one block in PredBlocks. 5462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // 5472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PredBlocks.size() > 1) { 5482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) { 5492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Pred = PredBlocks[i]; 5502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get all of the dominators of the predecessor... 5512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred); 5522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 5532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PDE = PredDoms.end(); PDI != PDE; ++PDI) { 5542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *PredDom = *PDI; 5552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // If the Exit node is in DF(PredDom), then PredDom didn't dominate 5572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Exit but did dominate a predecessor of it. Now we change this 5582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // entry to include NewBB in the DF instead of Exit. 559dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::iterator DFI = DF->find(PredDom); 560dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DFI != DF->end() && "No dominance frontier for node?"); 561dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DFI->second.count(Exit)) { 562dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->removeFromFrontier(DFI, Exit); 563dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addToFrontier(DFI, NewBB); 564dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 565dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 566dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 567dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 568dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 56938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 570d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 571d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 572