LoopSimplify.cpp revision ecd94c804a563f2a86572dcf1d2e81f397e19daa
167a9801bc510ff2c28068361fb30ae397fd1e026Chris Lattner//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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 2066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// loop) only have predecessors from inside of the loop (and are thus dominated 2166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// by the loop header). This simplifies transformations such as store-sinking 2266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner// that are built into LICM. 23dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// This pass also guarantees that loops will have exactly one backedge. 252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner// 26dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Note that the simplifycfg pass will clean up blocks which are split out but 27ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// end up being unnecessary, so usage of this pass should not pessimize 28ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// generated code. 29ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// 30ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass obviously modifies the CFG, but updates loop information and 31ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// dominator information. 3238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 3338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner//===----------------------------------------------------------------------===// 3438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 35d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "loopsimplify" 3638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h" 372ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Constant.h" 3847b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 392ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Function.h" 402ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Type.h" 41cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 420f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner#include "llvm/Analysis/Dominators.h" 430f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner#include "llvm/Analysis/LoopInfo.h" 4438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 45a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 46551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 47551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetVector.h" 48551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 49551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 5066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerusing namespace llvm; 51d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 52d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 53d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumNested , "Number of nested loops split out"); 5438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 55d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 569525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass { 57ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 58794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel LoopSimplify() : FunctionPass((intptr_t)&ID) {} 59794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 60cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // AA - If we have an alias analysis object to update, this is it, otherwise 61cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner // this is null. 62cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner AliasAnalysis *AA; 63c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LoopInfo *LI; 64cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner 6538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual bool runOnFunction(Function &F); 66fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 6838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 6938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addRequired<LoopInfo>(); 70786c5646e9cd15f18a6a7938673f74b02a05adb8Chris Lattner AU.addRequired<DominatorTree>(); 713b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel AU.addRequired<ETForest>(); 7238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 7338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<LoopInfo>(); 74baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner AU.addPreserved<ETForest>(); 7538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 76dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addPreserved<DominanceFrontier>(); 7794f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 7838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 7938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 8038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool ProcessLoop(Loop *L); 81dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 82dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds); 8359fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 8438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner void InsertPreheaderForLoop(Loop *L); 85529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *SeparateNestedLoop(Loop *L); 862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void InsertUniqueBackedgeBlock(Loop *L); 87120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner void PlaceSplitBlockCarefully(BasicBlock *NewBB, 88120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner std::vector<BasicBlock*> &SplitPreds, 89120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L); 90120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> &PredBlocks); 9338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 9438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 951997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char LoopSimplify::ID = 0; 967f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<LoopSimplify> 97ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner X("loopsimplify", "Canonicalize natural loops", true); 9838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 9938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass... 10166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerconst PassInfo *llvm::LoopSimplifyID = X.getPassInfo(); 1024b5015604908e9296800991a7c538a255356428fChris LattnerFunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 10338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 10538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 10638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 107ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::runOnFunction(Function &F) { 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 109c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI = &getAnalysis<LoopInfo>(); 110cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner AA = getAnalysisToUpdate<AliasAnalysis>(); 11138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 112fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Check to see that no blocks (other than the header) in loops have 113fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // predecessors that are not in loops. This is not valid for natural loops, 114fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // but can occur if the blocks are unreachable. Since they are unreachable we 115fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // can just shamelessly destroy their terminators to make them not branch into 116fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // the loop! 117fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 118fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // This case can only occur for unreachable blocks. Blocks that are 119fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // unreachable can't be in loops, so filter those blocks out. 120fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (LI->getLoopFor(BB)) continue; 121fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 122fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner bool BlockUnreachable = false; 123fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner TerminatorInst *TI = BB->getTerminator(); 124fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 125fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Check to see if any successors of this block are non-loop-header loops 126fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // that are not the header. 127fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 128fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // If this successor is not in a loop, BB is clearly ok. 129fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner Loop *L = LI->getLoopFor(TI->getSuccessor(i)); 130fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (!L) continue; 131fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 132fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // If the succ is the loop header, and if L is a top-level loop, then this 133fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // is an entrance into a loop through the header, which is also ok. 134fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0) 135fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner continue; 136fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 137fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Otherwise, this is an entrance into a loop from some place invalid. 138fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Either the loop structure is invalid and this is not a natural loop (in 139fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // which case the compiler is buggy somewhere else) or BB is unreachable. 140fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner BlockUnreachable = true; 141fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner break; 142fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner } 143fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 144fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // If this block is ok, check the next one. 145fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (!BlockUnreachable) continue; 146fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 147fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Otherwise, this block is dead. To clean up the CFG and to allow later 148fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // loop transformations to ignore this case, we delete the edges into the 149fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // loop by replacing the terminator. 150fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 151fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Remove PHI entries from the successors. 152fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 153fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner TI->getSuccessor(i)->removePredecessor(BB); 154fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 155fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Add a new unreachable instruction. 156fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner new UnreachableInst(TI); 157fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 158fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Delete the dead terminator. 159fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (AA) AA->deleteValue(&BB->back()); 160fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner BB->getInstList().pop_back(); 161fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner Changed |= true; 162fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner } 163fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 164c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 165329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner Changed |= ProcessLoop(*I); 16638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 16738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 16838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 16938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 17038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 17138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 17238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 173ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::ProcessLoop(Loop *L) { 17438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 1753bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop: 1763bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner 1770ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner // Canonicalize inner loops before outer loops. Inner loop canonicalization 1780ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner // can provide work for the outer loop to canonicalize. 1790ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 1800ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner Changed |= ProcessLoop(*I); 1810ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner 1822ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner assert(L->getBlocks()[0] == L->getHeader() && 1832ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner "Header isn't first block in loop?"); 1842ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 185fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Does the loop already have a preheader? If so, don't insert one. 18638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (L->getLoopPreheader() == 0) { 18738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner InsertPreheaderForLoop(L); 18838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NumInserted++; 18938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed = true; 19038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 19138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 19266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 19366ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 19466ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 195ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner // predecessors from outside of the loop, split the edge now. 196ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner std::vector<BasicBlock*> ExitBlocks; 197ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner L->getExitBlocks(ExitBlocks); 198c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner 199ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 200fed22aac4337c589841c443be70fe05559693f6aChris Lattner for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 201fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 202fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 203de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 204de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 2058587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // Must be exactly this loop: no subloops, parent loops, or non-loop preds 2068587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // allowed. 207ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner if (!L->contains(*PI)) { 208fed22aac4337c589841c443be70fe05559693f6aChris Lattner RewriteLoopExitBlock(L, ExitBlock); 209de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner NumInserted++; 210de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner Changed = true; 211de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 212de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 213fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 214dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 215529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 216529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 2173bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner unsigned NumBackedges = L->getNumBackEdges(); 2183bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner if (NumBackedges != 1) { 2193bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If this is really a nested loop, rip it out into a child loop. Don't do 2203bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // this for loops with a giant number of backedges, just factor them into a 2213bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // common backedge instead. 2223bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner if (NumBackedges < 8) { 2233bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner if (Loop *NL = SeparateNestedLoop(L)) { 2243bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ++NumNested; 2253bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // This is a big restructuring change, reprocess the whole loop. 2263bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ProcessLoop(NL); 2273bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner Changed = true; 2283bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // GCC doesn't tail recursion eliminate this. 2293bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner goto ReprocessLoop; 2303bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner } 231529b28da455a703d226a31a03400e6662ff569feChris Lattner } 232529b28da455a703d226a31a03400e6662ff569feChris Lattner 2333bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If we either couldn't, or didn't want to, identify nesting of the loops, 2343bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // insert a new block that all backedges target, then make it jump to the 2353bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // loop header. 2362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner InsertUniqueBackedgeBlock(L); 2372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NumInserted++; 2382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Changed = true; 2392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 2402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 24194f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // Scan over the PHI nodes in the loop header. Since they now have only two 24294f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // incoming values (the loop is canonicalized), we may have simplified the PHI 24394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 24494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PHINode *PN; 24594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner for (BasicBlock::iterator I = L->getHeader()->begin(); 24694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner (PN = dyn_cast<PHINode>(I++)); ) 24798599ba6c6b12a01718b08f57ceb7aa3397c5b2dChris Lattner if (Value *V = PN->hasConstantValue()) { 24894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PN->replaceAllUsesWith(V); 24994f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PN->eraseFromParent(); 25094f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner } 25194f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner 25238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 25338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 25438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 255dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// SplitBlockPredecessors - Split the specified block into two blocks. We want 256dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// to move the predecessors specified in the Preds list to point to the new 257dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// block, leaving the remaining predecessors pointing to BB. This method 258dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// updates the SSA PHINode's, but no other analyses. 25938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 260ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris LattnerBasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 261ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner const char *Suffix, 262dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds) { 263fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 264dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create new basic block, insert right before the original block... 265c24a076c6a22a932e4fc2b745fd748fe7ee3cb15Chris Lattner BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB); 26638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 26738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader first gets an unconditional branch to the loop header... 268108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner BranchInst *BI = new BranchInst(BB, NewBB); 269fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 270dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // For every PHI node in the block, insert a PHI node into NewBB where the 271dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming values from the out of loop edges are moved to NewBB. We have two 272dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // possible cases here. If the loop is dead, we just insert dummy entries 273dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // into the PHI nodes for the new edge. If the loop is not dead, we move the 274dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming edges in BB into new PHI nodes in NewBB. 27538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 276dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!Preds.empty()) { // Is the loop not obviously dead? 2770f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Check to see if the values being merged into the new block need PHI 2780f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // nodes. If so, insert them. 279200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 280200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 281529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; 282529b28da455a703d226a31a03400e6662ff569feChris Lattner 2830f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Check to see if all of the values coming in are the same. If so, we 2840f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // don't need to create a new PHI node. 2850f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 2860f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner for (unsigned i = 1, e = Preds.size(); i != e; ++i) 2870f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 2880f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner InVal = 0; 2890f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner break; 2900f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner } 291fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 2920f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // If the values coming into the block are not the same, we need a PHI. 2930f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner if (InVal == 0) { 294010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner // Create the new PHI node, insert it into NewBB at the end of the block 295010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 296cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPHI); 297fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 298010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner // Move all of the edges from blocks outside the loop to the new PHI 299010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 300529b28da455a703d226a31a03400e6662ff569feChris Lattner Value *V = PN->removeIncomingValue(Preds[i], false); 301010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner NewPHI->addIncoming(V, Preds[i]); 302010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner } 3030f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner InVal = NewPHI; 3040f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner } else { 3050f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Remove all of the edges coming into the PHI nodes from outside of the 3060f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // block. 3070f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) 3080f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner PN->removeIncomingValue(Preds[i], false); 30938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 3100f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner 3110f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Add an incoming value to the PHI node in the loop for the preheader 3120f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // edge. 3130f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner PN->addIncoming(InVal, NewBB); 314529b28da455a703d226a31a03400e6662ff569feChris Lattner 315529b28da455a703d226a31a03400e6662ff569feChris Lattner // Can we eliminate this phi node now? 3165e1b23192184aadbfbd79a31641eb3c0c0ecdc05Chris Lattner if (Value *V = PN->hasConstantValue(true)) { 317a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky Instruction *I = dyn_cast<Instruction>(V); 318558fc740da62bb93ddfc85f353ab0665b566127fOwen Anderson // If I is in NewBB, the ETForest call will fail, because NewBB isn't 319558fc740da62bb93ddfc85f353ab0665b566127fOwen Anderson // registered in ETForest yet. Handle this case explicitly. 320a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (!I || (I->getParent() != NewBB && 321a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky getAnalysis<ETForest>().dominates(I, PN))) { 322c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->replaceAllUsesWith(V); 323cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(PN); 324c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner BB->getInstList().erase(PN); 325c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner } 326529b28da455a703d226a31a03400e6662ff569feChris Lattner } 32738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 328fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 32938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Now that the PHI nodes are updated, actually move the edges from 330dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Preds to point to NewBB instead of BB. 33138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 332dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 333dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 33438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 335dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (TI->getSuccessor(s) == BB) 33638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner TI->setSuccessor(s, NewBB); 33738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 338fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 33938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } else { // Otherwise the loop is dead... 340200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 341200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 34238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Insert dummy values as the incoming value... 34338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 344200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos } 345fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman } 346dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner return NewBB; 347dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 34838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 349dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 350dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 351dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 352dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 353ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnervoid LoopSimplify::InsertPreheaderForLoop(Loop *L) { 354dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 355dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 356dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 357dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> OutsideBlocks; 358dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 359dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PI != PE; ++PI) 3608587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner if (!L->contains(*PI)) // Coming in from outside the loop? 3618587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner OutsideBlocks.push_back(*PI); // Keep track of it... 362fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 363c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner // Split out the loop pre-header. 364dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 365dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 366c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner 367fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 36838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner //===--------------------------------------------------------------------===// 369cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Update analysis results now that we have performed the transformation 37038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 371fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 37238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We know that we have loop information to update... update it now. 37338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (Loop *Parent = L->getParentLoop()) 374c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner Parent->addBasicBlockToLoop(NewBB, *LI); 3759f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 376c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner UpdateDomInfoForRevectoredPreds(NewBB, OutsideBlocks); 377120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 378120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 379120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 380120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 381dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 382dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 383529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 384529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks. This method is used to split exit blocks that have predecessors 385529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop. 38659fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 387dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> LoopBlocks; 388dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 389dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (L->contains(*I)) 390dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner LoopBlocks.push_back(*I); 391dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 3927e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 3937e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 3947e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 395c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // Update Loop Information - we know that the new block will be in whichever 396c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // loop the Exit block is in. Note that it may not be in that immediate loop, 397c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // if the successor is some other loop header. In that case, we continue 398c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // walking up the loop tree to find a loop that contains both the successor 399c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // block and the predecessor block. 400c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner Loop *SuccLoop = LI->getLoopFor(Exit); 401c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner while (SuccLoop && !SuccLoop->contains(L->getHeader())) 402c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner SuccLoop = SuccLoop->getParentLoop(); 403c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if (SuccLoop) 404c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner SuccLoop->addBasicBlockToLoop(NewBB, *LI); 40574cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner 4062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 4072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 40859fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner return NewBB; 4092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 411529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 412529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 413529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 41458d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 415529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 41658d7fbf250659246fcca9417a91170a681b1850aDevang Patel std::vector<BasicBlock *> WorkList; 41758d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(InputBB); 41858d7fbf250659246fcca9417a91170a681b1850aDevang Patel do { 41958d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 42058d7fbf250659246fcca9417a91170a681b1850aDevang Patel if (Blocks.insert(BB).second && BB != StopBlock) 42158d7fbf250659246fcca9417a91170a681b1850aDevang Patel // If BB is not already processed and it is not a stop block then 42258d7fbf250659246fcca9417a91170a681b1850aDevang Patel // insert its predecessor in the work list 42358d7fbf250659246fcca9417a91170a681b1850aDevang Patel for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 42458d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *WBB = *I; 42558d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(WBB); 42658d7fbf250659246fcca9417a91170a681b1850aDevang Patel } 42758d7fbf250659246fcca9417a91170a681b1850aDevang Patel } while(!WorkList.empty()); 428529b28da455a703d226a31a03400e6662ff569feChris Lattner} 429529b28da455a703d226a31a03400e6662ff569feChris Lattner 4301f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 4311f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops. 432ad190145912facc6fbf2fbe58023bb238fbf2365Owen Andersonstatic PHINode *FindPHIToPartitionLoops(Loop *L, ETForest *EF, 433ad190145912facc6fbf2fbe58023bb238fbf2365Owen Anderson AliasAnalysis *AA) { 434200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 435200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 4361f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 437a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman if (Value *V = PN->hasConstantValue()) 4383b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel if (!isa<Instruction>(V) || EF->dominates(cast<Instruction>(V), PN)) { 439c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // This is a degenerate PHI already, don't modify it! 440c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->replaceAllUsesWith(V); 441cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(PN); 442fee341137957b9021b17561bd644aa726aa524e7Chris Lattner PN->eraseFromParent(); 443c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner continue; 444c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner } 445c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 446c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 447c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 448c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 449c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 450c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 451c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4521f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4531f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4541f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4551f62f82b05563df9c83094608de24ea581014d1eChris Lattner 456120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 457120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block. This prevents the preheader from 458120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated. 459120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattnervoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 460120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner std::vector<BasicBlock*>&SplitPreds, 461120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L) { 462120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Check to see if NewBB is already well placed. 463120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = NewBB; --BBI; 464120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 465120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (&*BBI == SplitPreds[i]) 466120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner return; 467120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 468120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 469120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If it isn't already after an outside block, move it after one. This is 470120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // always good as it makes the uncond branch from the outside block into a 471120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // fall-through. 472120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 473120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Figure out *which* outside block to put this after. Prefer an outside 474120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // block that neighbors a BB actually in the loop. 475120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner BasicBlock *FoundBB = 0; 476120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 477120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = SplitPreds[i]; 478120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (++BBI != NewBB->getParent()->end() && 479120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner L->contains(BBI)) { 480120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[i]; 481120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner break; 482120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 483120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 484120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 485120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If our heuristic for a *good* bb to place this after doesn't find 486120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // anything, just pick something. It's likely better than leaving it within 487120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // the loop. 488120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (!FoundBB) 489120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[0]; 490120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner NewBB->moveAfter(FoundBB); 491120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner} 492120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 493120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 494529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 495529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 496529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 497529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 498529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 499529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 500529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 501529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 502529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 503529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 504529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 505529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 506529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 507529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 508529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 509529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 510529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 511529b28da455a703d226a31a03400e6662ff569feChris LattnerLoop *LoopSimplify::SeparateNestedLoop(Loop *L) { 5123b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel ETForest *EF = getAnalysisToUpdate<ETForest>(); 5133b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel PHINode *PN = FindPHIToPartitionLoops(L, EF, AA); 5141f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 515529b28da455a703d226a31a03400e6662ff569feChris Lattner 5161f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 5171f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 5181f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 519529b28da455a703d226a31a03400e6662ff569feChris Lattner std::vector<BasicBlock*> OuterLoopPreds; 5201f62f82b05563df9c83094608de24ea581014d1eChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 5211f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 5221f62f82b05563df9c83094608de24ea581014d1eChris Lattner !L->contains(PN->getIncomingBlock(i))) 5231f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 524529b28da455a703d226a31a03400e6662ff569feChris Lattner 5254b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 526529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds); 527529b28da455a703d226a31a03400e6662ff569feChris Lattner 528529b28da455a703d226a31a03400e6662ff569feChris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 529529b28da455a703d226a31a03400e6662ff569feChris Lattner UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds); 530529b28da455a703d226a31a03400e6662ff569feChris Lattner 531120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 532120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 533120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 534120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 535529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 536529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 537529b28da455a703d226a31a03400e6662ff569feChris Lattner 538529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 539529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 540529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 541529b28da455a703d226a31a03400e6662ff569feChris Lattner else 542c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeTopLevelLoop(L, NewOuter); 543529b28da455a703d226a31a03400e6662ff569feChris Lattner 544529b28da455a703d226a31a03400e6662ff569feChris Lattner // This block is going to be our new header block: add it to this loop and all 545529b28da455a703d226a31a03400e6662ff569feChris Lattner // parent loops. 546c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner NewOuter->addBasicBlockToLoop(NewBB, *LI); 547529b28da455a703d226a31a03400e6662ff569feChris Lattner 548529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 549529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 550529b28da455a703d226a31a03400e6662ff569feChris Lattner 551529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 552529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addBlockEntry(L->getBlocks()[i]); 553529b28da455a703d226a31a03400e6662ff569feChris Lattner 554529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 555529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 556529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 557529b28da455a703d226a31a03400e6662ff569feChris Lattner for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 558a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (EF->dominates(Header, *PI)) 559529b28da455a703d226a31a03400e6662ff569feChris Lattner AddBlockAndPredsToSet(*PI, Header, BlocksInL); 560529b28da455a703d226a31a03400e6662ff569feChris Lattner 561529b28da455a703d226a31a03400e6662ff569feChris Lattner 562529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 563529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 564529b28da455a703d226a31a03400e6662ff569feChris Lattner for (Loop::iterator I = L->begin(); I != L->end(); ) 565529b28da455a703d226a31a03400e6662ff569feChris Lattner if (BlocksInL.count((*I)->getHeader())) 566529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 567529b28da455a703d226a31a03400e6662ff569feChris Lattner else 568529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L->removeChildLoop(I)); 569529b28da455a703d226a31a03400e6662ff569feChris Lattner 570529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 571529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 572529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 573529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 574529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 575529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 576529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 577c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if ((*LI)[BB] == L) 578c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeLoopFor(BB, NewOuter); 579529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 580529b28da455a703d226a31a03400e6662ff569feChris Lattner } 581529b28da455a703d226a31a03400e6662ff569feChris Lattner } 582529b28da455a703d226a31a03400e6662ff569feChris Lattner 583529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 584529b28da455a703d226a31a03400e6662ff569feChris Lattner} 585529b28da455a703d226a31a03400e6662ff569feChris Lattner 586529b28da455a703d226a31a03400e6662ff569feChris Lattner 587529b28da455a703d226a31a03400e6662ff569feChris Lattner 5882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 5892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 5902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 5912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 5922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 5932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 5942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 5952ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5962ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 5972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 5982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 5992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 6002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 6022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 6032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 6042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (*I != Preheader) BackedgeBlocks.push_back(*I); 6052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 6072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 608108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner BranchInst *BETerminator = new BranchInst(Header, BEBlock); 6092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 6112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 6122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 613fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 6152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 616200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 617200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 6182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 6192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BETerminator); 6205551706b0f8e970720deea0bf6aa34116030d6beChris Lattner NewPN->reserveOperandSpace(BackedgeBlocks.size()); 621cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPN); 6222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 6242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 6252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 6262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 6272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 6282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 6292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 6302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 6312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 6322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 6332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 6342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 6352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 6372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 6382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 6392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 6402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 643fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 6452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 6462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 6472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 6482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 6492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6505551706b0f8e970720deea0bf6aa34116030d6beChris Lattner // Nuke all entries except the zero'th. 6515551706b0f8e970720deea0bf6aa34116030d6beChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 6525551706b0f8e970720deea0bf6aa34116030d6beChris Lattner PN->removeIncomingValue(e-i, false); 6532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 6552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 6562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 6582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 6592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 6602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 662cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(NewPN); 6632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 6642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6652ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6662ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 6682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // backedge blocks to just to the BEBlock instead of the header. 6692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 6702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 6712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 6722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 6732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 6742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 6772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 6792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 680c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner L->addBasicBlockToLoop(BEBlock, *LI); 6812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 6832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 6842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 6852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 68617cba6d2326f1f81098334def5f4f99d867e3ce4Owen Anderson// Returns true if BasicBlock A dominates at least one block in vector B 68717cba6d2326f1f81098334def5f4f99d867e3ce4Owen Anderson// Helper function for UpdateDomInfoForRevectoredPreds 688cc221cdf0cf90459bda58969eacac926d0ca6f1cOwen Andersonstatic bool BlockDominatesAny(BasicBlock* A, const std::vector<BasicBlock*>& B, 689cc221cdf0cf90459bda58969eacac926d0ca6f1cOwen Anderson ETForest& ETF) { 690cc221cdf0cf90459bda58969eacac926d0ca6f1cOwen Anderson for (std::vector<BasicBlock*>::const_iterator BI = B.begin(), BE = B.end(); 691cc221cdf0cf90459bda58969eacac926d0ca6f1cOwen Anderson BI != BE; ++BI) { 6920cd04618734590b3328d6db2214ee523d11104edOwen Anderson if (ETF.dominates(A, *BI)) 6930cd04618734590b3328d6db2214ee523d11104edOwen Anderson return true; 6940cd04618734590b3328d6db2214ee523d11104edOwen Anderson } 6950cd04618734590b3328d6db2214ee523d11104edOwen Anderson return false; 69617cba6d2326f1f81098334def5f4f99d867e3ce4Owen Anderson} 69717cba6d2326f1f81098334def5f4f99d867e3ce4Owen Anderson 6982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// UpdateDomInfoForRevectoredPreds - This method is used to update the four 699a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky/// different kinds of dominator information (immediate dominators, 700a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky/// dominator trees, et-forest and dominance frontiers) after a new block has 7012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// been added to the CFG. 7022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 7034f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// This only supports the case when an existing block (known as "NewBBSucc"), 7044f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// had some of its predecessors factored into a new basic block. This 7052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// transformation inserts a new basic block ("NewBB"), with a single 7064f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// unconditional branch to NewBBSucc, and moves some predecessors of 7074f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// "NewBBSucc" to now branch to NewBB. These predecessors are listed in 7084f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// PredBlocks, even though they are the same as 7094f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// pred_begin(NewBB)/pred_end(NewBB). 7102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 7112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 7122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> &PredBlocks) { 7134f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner assert(!PredBlocks.empty() && "No predblocks??"); 7142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(succ_begin(NewBB) != succ_end(NewBB) && 7152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner ++succ_begin(NewBB) == succ_end(NewBB) && 7162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner "NewBB should have a single successor!"); 7174f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner BasicBlock *NewBBSucc = *succ_begin(NewBB); 718a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky ETForest& ETF = getAnalysis<ETForest>(); 719a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky 7204f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // The newly inserted basic block will dominate existing basic blocks iff the 7214f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate 7224f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // the non-pred blocks, then they all must be the same block! 7234f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // 7244f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner bool NewBBDominatesNewBBSucc = true; 7254f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner { 7264f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner BasicBlock *OnePred = PredBlocks[0]; 727a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky unsigned i = 1, e = PredBlocks.size(); 728558fc740da62bb93ddfc85f353ab0665b566127fOwen Anderson for (i = 1; !ETF.isReachableFromEntry(OnePred); ++i) { 729c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner assert(i != e && "Didn't find reachable pred?"); 730c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner OnePred = PredBlocks[i]; 731c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner } 732c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner 733c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner for (; i != e; ++i) 734558fc740da62bb93ddfc85f353ab0665b566127fOwen Anderson if (PredBlocks[i] != OnePred && ETF.isReachableFromEntry(OnePred)){ 7354f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner NewBBDominatesNewBBSucc = false; 7364f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner break; 7374f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 7384f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 7394f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) 7404f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 7414f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner PI != E; ++PI) 742a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (*PI != NewBB && !ETF.dominates(NewBBSucc, *PI)) { 7434f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner NewBBDominatesNewBBSucc = false; 7444f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner break; 7454f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 7464f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 7474f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 7484f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // The other scenario where the new block can dominate its successors are when 7494f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc 7504f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // already. 7514f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner if (!NewBBDominatesNewBBSucc) { 7524f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner NewBBDominatesNewBBSucc = true; 7534f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 7544f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner PI != E; ++PI) 755a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (*PI != NewBB && !ETF.dominates(NewBBSucc, *PI)) { 7564f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner NewBBDominatesNewBBSucc = false; 7574f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner break; 7584f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner } 7594f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner } 760dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 761e9ed4452bce4f5a7f8005d7ebd649a20c22ef268Owen Anderson BasicBlock *NewBBIDom = 0; 762dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 763dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update DominatorTree information if it is active. 764dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 7654f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // If we don't have ImmediateDominator info around, calculate the idom as 7664f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // above. 767a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (!NewBBIDom) { 768a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky unsigned i = 0; 769a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky for (i = 0; i < PredBlocks.size(); ++i) 770a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) { 771a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky NewBBIDom = PredBlocks[i]; 772a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky break; 773a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky } 774a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky assert(i != PredBlocks.size() && "No reachable preds?"); 775a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky for (i = i + 1; i < PredBlocks.size(); ++i) { 776a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) 777a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky NewBBIDom = ETF.nearestCommonDominator(NewBBIDom, PredBlocks[i]); 778e9ed4452bce4f5a7f8005d7ebd649a20c22ef268Owen Anderson } 779a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky assert(NewBBIDom && "No immediate dominator found??"); 780dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 781a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky DominatorTree::Node *NewBBIDomNode = DT->getNode(NewBBIDom); 782dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 7834f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // Create the new dominator tree node... and set the idom of NewBB. 7844f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode); 7854f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 7864f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // If NewBB strictly dominates other blocks, then it is now the immediate 7874f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // dominator of NewBBSucc. Update the dominator tree as appropriate. 7884f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) { 7894f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc); 7904f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DT->changeImmediateDominator(NewBBSuccNode, NewBBNode); 7914f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 792dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 793dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 794baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner // Update ET-Forest information if it is active. 795baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner if (ETForest *EF = getAnalysisToUpdate<ETForest>()) { 796baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner EF->addNewBlock(NewBB, NewBBIDom); 797baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner if (NewBBDominatesNewBBSucc) 798baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner EF->setImmediateDominator(NewBBSucc, NewBB); 799baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner } 800baec98d00bda1cc904405d92716ea9d2f4c1fe9dChris Lattner 801dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 802dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 8034b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 8044b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // DF(PredBlocks[0]) without the stuff that the new block does not dominate 8054b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // a predecessor of. 8064f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) { 8074f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]); 8084f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (DFI != DF->end()) { 8094f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominanceFrontier::DomSetType Set = DFI->second; 8104f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // Filter out stuff in Set that we do not dominate a predecessor of. 8114f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 8124f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner E = Set.end(); SetI != E;) { 8134f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner bool DominatesPred = false; 8144f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 8154f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner PI != E; ++PI) 816a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (ETF.dominates(NewBB, *PI)) 8174f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominatesPred = true; 8184f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (!DominatesPred) 8194f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner Set.erase(SetI++); 8204f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner else 8214f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner ++SetI; 8224f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 823dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 8244f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DF->addBasicBlock(NewBB, Set); 8254f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 8264f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 8274f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } else { 8284f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 8294f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 8304f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // NewBBSucc)). NewBBSucc is the single successor of NewBB. 8314f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominanceFrontier::DomSetType NewDFSet; 8324f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner NewDFSet.insert(NewBBSucc); 8334f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DF->addBasicBlock(NewBB, NewDFSet); 8344b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner } 8354b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner 8364b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 8374b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // replacing occurrences of NewBBSucc with NewBB in some cases. All 8384b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // blocks that dominate a block in PredBlocks and contained NewBBSucc in 8394b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // their dominance frontier must be updated to contain NewBB instead. 8404b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // 84117cba6d2326f1f81098334def5f4f99d867e3ce4Owen Anderson for (Function::iterator FI = NewBB->getParent()->begin(), 8420cd04618734590b3328d6db2214ee523d11104edOwen Anderson FE = NewBB->getParent()->end(); FI != FE; ++FI) { 8430cd04618734590b3328d6db2214ee523d11104edOwen Anderson DominanceFrontier::iterator DFI = DF->find(FI); 8440cd04618734590b3328d6db2214ee523d11104edOwen Anderson if (DFI == DF->end()) continue; // unreachable block. 8450cd04618734590b3328d6db2214ee523d11104edOwen Anderson 8460cd04618734590b3328d6db2214ee523d11104edOwen Anderson // Only consider dominators of NewBBSucc 8470cd04618734590b3328d6db2214ee523d11104edOwen Anderson if (!DFI->second.count(NewBBSucc)) continue; 848ad190145912facc6fbf2fbe58023bb238fbf2365Owen Anderson 8490cd04618734590b3328d6db2214ee523d11104edOwen Anderson if (BlockDominatesAny(FI, PredBlocks, ETF)) { 8500cd04618734590b3328d6db2214ee523d11104edOwen Anderson // If NewBBSucc should not stay in our dominator frontier, remove it. 8510cd04618734590b3328d6db2214ee523d11104edOwen Anderson // We remove it unless there is a predecessor of NewBBSucc that we 8520cd04618734590b3328d6db2214ee523d11104edOwen Anderson // dominate, but we don't strictly dominate NewBBSucc. 8530cd04618734590b3328d6db2214ee523d11104edOwen Anderson bool ShouldRemove = true; 8540cd04618734590b3328d6db2214ee523d11104edOwen Anderson if ((BasicBlock*)FI == NewBBSucc || !ETF.dominates(FI, NewBBSucc)) { 8550cd04618734590b3328d6db2214ee523d11104edOwen Anderson // Okay, we know that PredDom does not strictly dominate NewBBSucc. 8560cd04618734590b3328d6db2214ee523d11104edOwen Anderson // Check to see if it dominates any predecessors of NewBBSucc. 8570cd04618734590b3328d6db2214ee523d11104edOwen Anderson for (pred_iterator PI = pred_begin(NewBBSucc), 8580cd04618734590b3328d6db2214ee523d11104edOwen Anderson E = pred_end(NewBBSucc); PI != E; ++PI) 8590cd04618734590b3328d6db2214ee523d11104edOwen Anderson if (ETF.dominates(FI, *PI)) { 8600cd04618734590b3328d6db2214ee523d11104edOwen Anderson ShouldRemove = false; 8610cd04618734590b3328d6db2214ee523d11104edOwen Anderson break; 8620cd04618734590b3328d6db2214ee523d11104edOwen Anderson } 8630cd04618734590b3328d6db2214ee523d11104edOwen Anderson 8640cd04618734590b3328d6db2214ee523d11104edOwen Anderson if (ShouldRemove) 8650cd04618734590b3328d6db2214ee523d11104edOwen Anderson DF->removeFromFrontier(DFI, NewBBSucc); 8660cd04618734590b3328d6db2214ee523d11104edOwen Anderson DF->addToFrontier(DFI, NewBB); 8670cd04618734590b3328d6db2214ee523d11104edOwen Anderson 8680cd04618734590b3328d6db2214ee523d11104edOwen Anderson break; 8690cd04618734590b3328d6db2214ee523d11104edOwen Anderson } 8700cd04618734590b3328d6db2214ee523d11104edOwen Anderson } 8710cd04618734590b3328d6db2214ee523d11104edOwen Anderson } 8720cd04618734590b3328d6db2214ee523d11104edOwen Anderson } 87338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 874d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 87517cba6d2326f1f81098334def5f4f99d867e3ce4Owen Anderson 876