LoopSimplify.cpp revision d735ee85dbab8e4f66f9ec157f19956e0d11ec7a
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" 373cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner#include "llvm/Constants.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; 640e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominatorTree *DT; 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>(); 7138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 7238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<LoopInfo>(); 7338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 74dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addPreserved<DominanceFrontier>(); 7594f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 7638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 7758e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 7858e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel /// verifyAnalysis() - Verify loop nest. 7958e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel void verifyAnalysis() const { 8058e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel#ifndef NDEBUG 8158e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel LoopInfo *NLI = &getAnalysis<LoopInfo>(); 8258e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) 8358e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel (*I)->verifyLoop(); 8458e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel#endif 8558e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel } 8658e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 8738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 8838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool ProcessLoop(Loop *L); 89dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 90dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds); 9159fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 9238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner void InsertPreheaderForLoop(Loop *L); 93529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *SeparateNestedLoop(Loop *L); 942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void InsertUniqueBackedgeBlock(Loop *L); 95120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner void PlaceSplitBlockCarefully(BasicBlock *NewBB, 96120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner std::vector<BasicBlock*> &SplitPreds, 97120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L); 9838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 9938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 1001997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char LoopSimplify::ID = 0; 1017f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<LoopSimplify> 102ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner X("loopsimplify", "Canonicalize natural loops", true); 10338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 10438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass... 10666ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerconst PassInfo *llvm::LoopSimplifyID = X.getPassInfo(); 1074b5015604908e9296800991a7c538a255356428fChris LattnerFunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 11038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 11138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 112ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::runOnFunction(Function &F) { 11338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 114c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI = &getAnalysis<LoopInfo>(); 115cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner AA = getAnalysisToUpdate<AliasAnalysis>(); 1160e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT = &getAnalysis<DominatorTree>(); 11738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 118fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Check to see that no blocks (other than the header) in loops have 119fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // predecessors that are not in loops. This is not valid for natural loops, 120fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // but can occur if the blocks are unreachable. Since they are unreachable we 121fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // can just shamelessly destroy their terminators to make them not branch into 122fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // the loop! 123fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 124fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // This case can only occur for unreachable blocks. Blocks that are 125fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // unreachable can't be in loops, so filter those blocks out. 126fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (LI->getLoopFor(BB)) continue; 127fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 128fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner bool BlockUnreachable = false; 129fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner TerminatorInst *TI = BB->getTerminator(); 130fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 131fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Check to see if any successors of this block are non-loop-header loops 132fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // that are not the header. 133fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 134fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // If this successor is not in a loop, BB is clearly ok. 135fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner Loop *L = LI->getLoopFor(TI->getSuccessor(i)); 136fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (!L) continue; 137fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 138fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // If the succ is the loop header, and if L is a top-level loop, then this 139fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // is an entrance into a loop through the header, which is also ok. 140fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0) 141fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner continue; 142fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 143fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Otherwise, this is an entrance into a loop from some place invalid. 144fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Either the loop structure is invalid and this is not a natural loop (in 145fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // which case the compiler is buggy somewhere else) or BB is unreachable. 146fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner BlockUnreachable = true; 147fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner break; 148fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner } 149fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 150fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // If this block is ok, check the next one. 151fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner if (!BlockUnreachable) continue; 152fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 153fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Otherwise, this block is dead. To clean up the CFG and to allow later 154fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // loop transformations to ignore this case, we delete the edges into the 155fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // loop by replacing the terminator. 156fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 157fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Remove PHI entries from the successors. 158fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 159fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner TI->getSuccessor(i)->removePredecessor(BB); 160fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 1613cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner // Add a new unreachable instruction before the old terminator. 162fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner new UnreachableInst(TI); 163fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 164fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Delete the dead terminator. 1653cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner if (AA) AA->deleteValue(TI); 1663cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner if (!TI->use_empty()) 1673cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 1683cb63ddd5183a1469e4557b3e22735ed3ace05b2Chris Lattner TI->eraseFromParent(); 169fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner Changed |= true; 170fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner } 171fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner 172c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 173329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner Changed |= ProcessLoop(*I); 17438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 17538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 17638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 17738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 17838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 17938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 18038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 181ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::ProcessLoop(Loop *L) { 18238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 1833bb4657488f700bbe3376fb547017163b8fbbd8fChris LattnerReprocessLoop: 1843bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner 1850ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner // Canonicalize inner loops before outer loops. Inner loop canonicalization 1860ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner // can provide work for the outer loop to canonicalize. 1870ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 1880ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner Changed |= ProcessLoop(*I); 1890ab9f966de73911930b47ce09f2a691bc687ed32Chris Lattner 1902ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner assert(L->getBlocks()[0] == L->getHeader() && 1912ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner "Header isn't first block in loop?"); 1922ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 193fa78946482a2cc73a1485887dfd12edd12b742a4Chris Lattner // Does the loop already have a preheader? If so, don't insert one. 19438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (L->getLoopPreheader() == 0) { 19538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner InsertPreheaderForLoop(L); 19638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NumInserted++; 19738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed = true; 19838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 19938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 20066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 20166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 20266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 203ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner // predecessors from outside of the loop, split the edge now. 204b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 205ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner L->getExitBlocks(ExitBlocks); 206c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner 207ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 208fed22aac4337c589841c443be70fe05559693f6aChris Lattner for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 209fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 210fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 211de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 212de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 2138587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // Must be exactly this loop: no subloops, parent loops, or non-loop preds 2148587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner // allowed. 215ee628cfefb93e0261ee3e56686d3fffa4e81f371Chris Lattner if (!L->contains(*PI)) { 216fed22aac4337c589841c443be70fe05559693f6aChris Lattner RewriteLoopExitBlock(L, ExitBlock); 217de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner NumInserted++; 218de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner Changed = true; 219de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 220de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 221fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 222dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 223529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 224529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 2253bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner unsigned NumBackedges = L->getNumBackEdges(); 2263bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner if (NumBackedges != 1) { 2273bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If this is really a nested loop, rip it out into a child loop. Don't do 2283bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // this for loops with a giant number of backedges, just factor them into a 2293bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // common backedge instead. 2303bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner if (NumBackedges < 8) { 2313bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner if (Loop *NL = SeparateNestedLoop(L)) { 2323bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ++NumNested; 2333bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // This is a big restructuring change, reprocess the whole loop. 2343bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner ProcessLoop(NL); 2353bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner Changed = true; 2363bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // GCC doesn't tail recursion eliminate this. 2373bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner goto ReprocessLoop; 2383bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner } 239529b28da455a703d226a31a03400e6662ff569feChris Lattner } 240529b28da455a703d226a31a03400e6662ff569feChris Lattner 2413bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // If we either couldn't, or didn't want to, identify nesting of the loops, 2423bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // insert a new block that all backedges target, then make it jump to the 2433bb4657488f700bbe3376fb547017163b8fbbd8fChris Lattner // loop header. 2442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner InsertUniqueBackedgeBlock(L); 2452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NumInserted++; 2462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Changed = true; 2472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 2482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 24994f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // Scan over the PHI nodes in the loop header. Since they now have only two 25094f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // incoming values (the loop is canonicalized), we may have simplified the PHI 25194f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 25294f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PHINode *PN; 25394f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner for (BasicBlock::iterator I = L->getHeader()->begin(); 25494f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner (PN = dyn_cast<PHINode>(I++)); ) 25598599ba6c6b12a01718b08f57ceb7aa3397c5b2dChris Lattner if (Value *V = PN->hasConstantValue()) { 25694f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PN->replaceAllUsesWith(V); 25794f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner PN->eraseFromParent(); 25894f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner } 25994f40324481c04ae8718967b4b5a3d7ca22370e6Chris Lattner 26038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 26138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 26238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 263dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// SplitBlockPredecessors - Split the specified block into two blocks. We want 264dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// to move the predecessors specified in the Preds list to point to the new 265dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// block, leaving the remaining predecessors pointing to BB. This method 266dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// updates the SSA PHINode's, but no other analyses. 26738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 268ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris LattnerBasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 269ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner const char *Suffix, 270dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds) { 271fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 272dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create new basic block, insert right before the original block... 273c24a076c6a22a932e4fc2b745fd748fe7ee3cb15Chris Lattner BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB); 27438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 27538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader first gets an unconditional branch to the loop header... 276108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner BranchInst *BI = new BranchInst(BB, NewBB); 277fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 278dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // For every PHI node in the block, insert a PHI node into NewBB where the 279dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming values from the out of loop edges are moved to NewBB. We have two 280dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // possible cases here. If the loop is dead, we just insert dummy entries 281dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // into the PHI nodes for the new edge. If the loop is not dead, we move the 282dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming edges in BB into new PHI nodes in NewBB. 28338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 284dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!Preds.empty()) { // Is the loop not obviously dead? 2850f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Check to see if the values being merged into the new block need PHI 2860f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // nodes. If so, insert them. 287200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 288200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 289529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; 290529b28da455a703d226a31a03400e6662ff569feChris Lattner 2910f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Check to see if all of the values coming in are the same. If so, we 2920f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // don't need to create a new PHI node. 2930f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 2940f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner for (unsigned i = 1, e = Preds.size(); i != e; ++i) 2950f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 2960f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner InVal = 0; 2970f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner break; 2980f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner } 299fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3000f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // If the values coming into the block are not the same, we need a PHI. 3010f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner if (InVal == 0) { 302010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner // Create the new PHI node, insert it into NewBB at the end of the block 303010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 304cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPHI); 305fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 306010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner // Move all of the edges from blocks outside the loop to the new PHI 307010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 308529b28da455a703d226a31a03400e6662ff569feChris Lattner Value *V = PN->removeIncomingValue(Preds[i], false); 309010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner NewPHI->addIncoming(V, Preds[i]); 310010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner } 3110f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner InVal = NewPHI; 3120f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner } else { 3130f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Remove all of the edges coming into the PHI nodes from outside of the 3140f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // block. 3150f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) 3160f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner PN->removeIncomingValue(Preds[i], false); 31738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 3180f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner 3190f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Add an incoming value to the PHI node in the loop for the preheader 3200f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // edge. 3210f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner PN->addIncoming(InVal, NewBB); 322529b28da455a703d226a31a03400e6662ff569feChris Lattner 323529b28da455a703d226a31a03400e6662ff569feChris Lattner // Can we eliminate this phi node now? 3245e1b23192184aadbfbd79a31641eb3c0c0ecdc05Chris Lattner if (Value *V = PN->hasConstantValue(true)) { 325a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky Instruction *I = dyn_cast<Instruction>(V); 326dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel // If I is in NewBB, the Dominator call will fail, because NewBB isn't 327dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel // registered in DominatorTree yet. Handle this case explicitly. 328a397ce1cc2872b059a128f43b8fd300c61700793Nick Lewycky if (!I || (I->getParent() != NewBB && 329dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel getAnalysis<DominatorTree>().dominates(I, PN))) { 330c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->replaceAllUsesWith(V); 331cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(PN); 332c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner BB->getInstList().erase(PN); 333c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner } 334529b28da455a703d226a31a03400e6662ff569feChris Lattner } 33538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 336fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 33738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Now that the PHI nodes are updated, actually move the edges from 338dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Preds to point to NewBB instead of BB. 33938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 340dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 341dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 34238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 343dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (TI->getSuccessor(s) == BB) 34438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner TI->setSuccessor(s, NewBB); 34538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 346fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 34738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } else { // Otherwise the loop is dead... 348200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 349200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 35038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Insert dummy values as the incoming value... 35138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 352200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos } 353fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman } 3540e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 355dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner return NewBB; 356dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 35738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 358dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 359dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 360dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 361dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 362ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnervoid LoopSimplify::InsertPreheaderForLoop(Loop *L) { 363dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 364dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 365dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 366dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> OutsideBlocks; 367dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 368dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PI != PE; ++PI) 3698587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner if (!L->contains(*PI)) // Coming in from outside the loop? 3708587eb3a51117b630c18236cc53eb865e76faf2dChris Lattner OutsideBlocks.push_back(*PI); // Keep track of it... 371fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 372c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner // Split out the loop pre-header. 373dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 374dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 375c3984578bed8236f35825ca8aa30b3ed6cff60d5Chris Lattner 376fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 37738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner //===--------------------------------------------------------------------===// 378cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Update analysis results now that we have performed the transformation 37938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 380fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 38138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We know that we have loop information to update... update it now. 38238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (Loop *Parent = L->getParentLoop()) 383d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson Parent->addBasicBlockToLoop(NewBB, LI->getBase()); 3849f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 3850e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(NewBB); 3860e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) 3870e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DF->splitBlock(NewBB); 3880e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 389120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 390120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 391120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 392dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 393dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 394529b28da455a703d226a31a03400e6662ff569feChris Lattner/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 395529b28da455a703d226a31a03400e6662ff569feChris Lattner/// blocks. This method is used to split exit blocks that have predecessors 396529b28da455a703d226a31a03400e6662ff569feChris Lattner/// outside of the loop. 39759fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris LattnerBasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 398dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> LoopBlocks; 399dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 400dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (L->contains(*I)) 401dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner LoopBlocks.push_back(*I); 402dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 4037e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 4047e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 4057e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 406c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // Update Loop Information - we know that the new block will be in whichever 407c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // loop the Exit block is in. Note that it may not be in that immediate loop, 408c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // if the successor is some other loop header. In that case, we continue 409c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // walking up the loop tree to find a loop that contains both the successor 410c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner // block and the predecessor block. 411c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner Loop *SuccLoop = LI->getLoopFor(Exit); 412c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner while (SuccLoop && !SuccLoop->contains(L->getHeader())) 413c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner SuccLoop = SuccLoop->getParentLoop(); 414c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if (SuccLoop) 415d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 41674cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner 4170e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update Dominator Information 4180e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(NewBB); 4190e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) 4200e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DF->splitBlock(NewBB); 4210e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 42259fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner return NewBB; 4232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 425529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 426529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 427529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 42858d7fbf250659246fcca9417a91170a681b1850aDevang Patelstatic void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 429529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 43058d7fbf250659246fcca9417a91170a681b1850aDevang Patel std::vector<BasicBlock *> WorkList; 43158d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(InputBB); 43258d7fbf250659246fcca9417a91170a681b1850aDevang Patel do { 43358d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 43458d7fbf250659246fcca9417a91170a681b1850aDevang Patel if (Blocks.insert(BB).second && BB != StopBlock) 43558d7fbf250659246fcca9417a91170a681b1850aDevang Patel // If BB is not already processed and it is not a stop block then 43658d7fbf250659246fcca9417a91170a681b1850aDevang Patel // insert its predecessor in the work list 43758d7fbf250659246fcca9417a91170a681b1850aDevang Patel for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 43858d7fbf250659246fcca9417a91170a681b1850aDevang Patel BasicBlock *WBB = *I; 43958d7fbf250659246fcca9417a91170a681b1850aDevang Patel WorkList.push_back(WBB); 44058d7fbf250659246fcca9417a91170a681b1850aDevang Patel } 44158d7fbf250659246fcca9417a91170a681b1850aDevang Patel } while(!WorkList.empty()); 442529b28da455a703d226a31a03400e6662ff569feChris Lattner} 443529b28da455a703d226a31a03400e6662ff569feChris Lattner 4441f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 4451f62f82b05563df9c83094608de24ea581014d1eChris Lattner/// PHI node that tells us how to partition the loops. 446dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 447ad190145912facc6fbf2fbe58023bb238fbf2365Owen Anderson AliasAnalysis *AA) { 448200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 449200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 4501f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 451a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman if (Value *V = PN->hasConstantValue()) 452dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel if (!isa<Instruction>(V) || DT->dominates(cast<Instruction>(V), PN)) { 453c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // This is a degenerate PHI already, don't modify it! 454c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->replaceAllUsesWith(V); 455cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(PN); 456fee341137957b9021b17561bd644aa726aa524e7Chris Lattner PN->eraseFromParent(); 457c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner continue; 458c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner } 459c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 460c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 461c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 462c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 463c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 464c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 465c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4661f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4671f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4681f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4691f62f82b05563df9c83094608de24ea581014d1eChris Lattner 470120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 471120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// right after some 'outside block' block. This prevents the preheader from 472120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner// being placed inside the loop body, e.g. when the loop hasn't been rotated. 473120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattnervoid LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 474120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner std::vector<BasicBlock*>&SplitPreds, 475120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Loop *L) { 476120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Check to see if NewBB is already well placed. 477120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = NewBB; --BBI; 478120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 479120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (&*BBI == SplitPreds[i]) 480120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner return; 481120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 482120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 483120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If it isn't already after an outside block, move it after one. This is 484120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // always good as it makes the uncond branch from the outside block into a 485120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // fall-through. 486120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 487120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Figure out *which* outside block to put this after. Prefer an outside 488120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // block that neighbors a BB actually in the loop. 489120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner BasicBlock *FoundBB = 0; 490120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 491120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner Function::iterator BBI = SplitPreds[i]; 492120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (++BBI != NewBB->getParent()->end() && 493120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner L->contains(BBI)) { 494120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[i]; 495120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner break; 496120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 497120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner } 498120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 499120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // If our heuristic for a *good* bb to place this after doesn't find 500120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // anything, just pick something. It's likely better than leaving it within 501120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // the loop. 502120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner if (!FoundBB) 503120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner FoundBB = SplitPreds[0]; 504120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner NewBB->moveAfter(FoundBB); 505120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner} 506120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 507120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 508529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 509529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 510529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 511529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 512529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 513529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 514529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 515529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 516529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 517529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 518529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 519529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 520529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 521529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 522529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 523529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 524529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 525529b28da455a703d226a31a03400e6662ff569feChris LattnerLoop *LoopSimplify::SeparateNestedLoop(Loop *L) { 526dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); 5271f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 528529b28da455a703d226a31a03400e6662ff569feChris Lattner 5291f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 5301f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 5311f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 532529b28da455a703d226a31a03400e6662ff569feChris Lattner std::vector<BasicBlock*> OuterLoopPreds; 5331f62f82b05563df9c83094608de24ea581014d1eChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 5341f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 5351f62f82b05563df9c83094608de24ea581014d1eChris Lattner !L->contains(PN->getIncomingBlock(i))) 5361f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 537529b28da455a703d226a31a03400e6662ff569feChris Lattner 5384b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 539529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds); 540529b28da455a703d226a31a03400e6662ff569feChris Lattner 5410e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update dominator information 5420e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(NewBB); 5430e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) 5440e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DF->splitBlock(NewBB); 545529b28da455a703d226a31a03400e6662ff569feChris Lattner 546120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // Make sure that NewBB is put someplace intelligent, which doesn't mess up 547120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner // code layout too horribly. 548120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 549120fce5540b34f81ee5773d30548ce7cc2b5f571Chris Lattner 550529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 551529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 552529b28da455a703d226a31a03400e6662ff569feChris Lattner 553529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 554529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 555529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 556529b28da455a703d226a31a03400e6662ff569feChris Lattner else 557c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeTopLevelLoop(L, NewOuter); 558529b28da455a703d226a31a03400e6662ff569feChris Lattner 559529b28da455a703d226a31a03400e6662ff569feChris Lattner // This block is going to be our new header block: add it to this loop and all 560529b28da455a703d226a31a03400e6662ff569feChris Lattner // parent loops. 561d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson NewOuter->addBasicBlockToLoop(NewBB, LI->getBase()); 562529b28da455a703d226a31a03400e6662ff569feChris Lattner 563529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 564529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 565529b28da455a703d226a31a03400e6662ff569feChris Lattner 566529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 567529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addBlockEntry(L->getBlocks()[i]); 568529b28da455a703d226a31a03400e6662ff569feChris Lattner 569529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 570529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 571529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 572529b28da455a703d226a31a03400e6662ff569feChris Lattner for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 573dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel if (DT->dominates(Header, *PI)) 574529b28da455a703d226a31a03400e6662ff569feChris Lattner AddBlockAndPredsToSet(*PI, Header, BlocksInL); 575529b28da455a703d226a31a03400e6662ff569feChris Lattner 576529b28da455a703d226a31a03400e6662ff569feChris Lattner 577529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 578529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 579c08fa28897356be54fba724056c3aa91da8b3e39David Greene const std::vector<Loop*> &SubLoops = L->getSubLoops(); 580c08fa28897356be54fba724056c3aa91da8b3e39David Greene for (size_t I = 0; I != SubLoops.size(); ) 581c08fa28897356be54fba724056c3aa91da8b3e39David Greene if (BlocksInL.count(SubLoops[I]->getHeader())) 582529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 583529b28da455a703d226a31a03400e6662ff569feChris Lattner else 584c08fa28897356be54fba724056c3aa91da8b3e39David Greene NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 585529b28da455a703d226a31a03400e6662ff569feChris Lattner 586529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 587529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 588529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 589529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 590529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 591529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 592529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 593c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner if ((*LI)[BB] == L) 594c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9Chris Lattner LI->changeLoopFor(BB, NewOuter); 595529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 596529b28da455a703d226a31a03400e6662ff569feChris Lattner } 597529b28da455a703d226a31a03400e6662ff569feChris Lattner } 598529b28da455a703d226a31a03400e6662ff569feChris Lattner 599529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 600529b28da455a703d226a31a03400e6662ff569feChris Lattner} 601529b28da455a703d226a31a03400e6662ff569feChris Lattner 602529b28da455a703d226a31a03400e6662ff569feChris Lattner 603529b28da455a703d226a31a03400e6662ff569feChris Lattner 6042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 6052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 6062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 6072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 6082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 6092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 6102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 6112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 6132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 6142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 6152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 6162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6172ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 6182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 6192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 6202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (*I != Preheader) BackedgeBlocks.push_back(*I); 6212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 6232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 624108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner BranchInst *BETerminator = new BranchInst(Header, BEBlock); 6252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 6272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 6282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 629fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 6312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 632200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 633200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 6342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 6352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BETerminator); 6365551706b0f8e970720deea0bf6aa34116030d6beChris Lattner NewPN->reserveOperandSpace(BackedgeBlocks.size()); 637cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->copyValue(PN, NewPN); 6382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 6402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 6412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 6422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 6432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 6442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 6452ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 6462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 6472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 6482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 6492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 6502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 6512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 6532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 6542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 6552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 6562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 659fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 6612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 6622ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 6632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 6642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 6652ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6665551706b0f8e970720deea0bf6aa34116030d6beChris Lattner // Nuke all entries except the zero'th. 6675551706b0f8e970720deea0bf6aa34116030d6beChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 6685551706b0f8e970720deea0bf6aa34116030d6beChris Lattner PN->removeIncomingValue(e-i, false); 6692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 6712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 6722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 6742ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 6752ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 6762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 678cec5b8831d4ee3d81990bf1af41ce1d4f4cf9704Chris Lattner if (AA) AA->deleteValue(NewPN); 6792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 6802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 6842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // backedge blocks to just to the BEBlock instead of the header. 6852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 6862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 6872ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 6882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 6892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 6902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 6932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 6952ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 696d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson L->addBasicBlockToLoop(BEBlock, LI->getBase()); 6972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6980e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Update dominator information 6990e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(BEBlock); 7000e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) 7010e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DF->splitBlock(BEBlock); 70238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 703