LoopSimplify.cpp revision c30bda7540de573c887e00bb76ac78d85f56acd4
167a9801bc510ff2c28068361fb30ae397fd1e026Chris Lattner//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// 10ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// This pass performs several transformations to transform natural loops into a 11ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// simpler form, which makes subsequent analyses and transformations simpler and 12ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner// more effective. 13dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 14dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop pre-header insertion guarantees that there is a single, non-critical 15dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// entry edge from outside of the loop to the loop header. This simplifies a 16dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// number of analyses and transformations, such as LICM. 17dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// 18dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// Loop exit-block insertion guarantees that all exit blocks from the loop 19dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner// (blocks which are outside of the loop that have predecessors inside of the 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 3538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Transforms/Scalar.h" 362ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Constant.h" 3747b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 382ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Function.h" 392ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner#include "llvm/Type.h" 400f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner#include "llvm/Analysis/Dominators.h" 410f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner#include "llvm/Analysis/LoopInfo.h" 4238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner#include "llvm/Support/CFG.h" 43529b28da455a703d226a31a03400e6662ff569feChris Lattner#include "llvm/Transforms/Utils/Local.h" 44551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 45551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetVector.h" 46551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 47551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 4866ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerusing namespace llvm; 49d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 5038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattnernamespace { 51ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner Statistic<> 5266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted"); 53529b28da455a703d226a31a03400e6662ff569feChris Lattner Statistic<> 54529b28da455a703d226a31a03400e6662ff569feChris Lattner NumNested("loopsimplify", "Number of nested loops split out"); 5538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 56ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner struct LoopSimplify : public FunctionPass { 5738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual bool runOnFunction(Function &F); 5838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 5938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 6038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We need loop information to identify the loops... 6138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addRequired<LoopInfo>(); 62dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addRequired<DominatorSet>(); 63786c5646e9cd15f18a6a7938673f74b02a05adb8Chris Lattner AU.addRequired<DominatorTree>(); 6438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 6538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<LoopInfo>(); 6638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorSet>(); 6738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<ImmediateDominators>(); 6838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreserved<DominatorTree>(); 69dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner AU.addPreserved<DominanceFrontier>(); 7038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added.... 7138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 7238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner private: 7338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool ProcessLoop(Loop *L); 74dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 75dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds); 7659fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 7738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner void InsertPreheaderForLoop(Loop *L); 78529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *SeparateNestedLoop(Loop *L); 792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void InsertUniqueBackedgeBlock(Loop *L); 802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> &PredBlocks); 8338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner }; 8438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 85ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner RegisterOpt<LoopSimplify> 86ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner X("loopsimplify", "Canonicalize natural loops", true); 8738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 8838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 8938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner// Publically exposed interface to pass... 9066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattnerconst PassInfo *llvm::LoopSimplifyID = X.getPassInfo(); 914b5015604908e9296800991a7c538a255356428fChris LattnerFunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 9238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 9338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 9438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// it in any convenient order) inserting preheaders... 9538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 96ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::runOnFunction(Function &F) { 9738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 9838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner LoopInfo &LI = getAnalysis<LoopInfo>(); 9938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 100329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) 101329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner Changed |= ProcessLoop(*I); 10238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 10438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 10538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 10738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 10838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// all loops have preheaders. 10938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 110ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnerbool LoopSimplify::ProcessLoop(Loop *L) { 11138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner bool Changed = false; 11238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 1132ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // Check to see that no blocks (other than the header) in the loop have 1142ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // predecessors that are not in the loop. This is not valid for natural 1152ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // loops, but can occur if the blocks are unreachable. Since they are 1162ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // unreachable we can just shamelessly destroy their terminators to make them 1172ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // not branch into the loop! 1182ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner assert(L->getBlocks()[0] == L->getHeader() && 1192ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner "Header isn't first block in loop?"); 1202ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) { 1212ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner BasicBlock *LoopBB = L->getBlocks()[i]; 1222ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner Retry: 1232ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB); 1242ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner PI != E; ++PI) 1252ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner if (!L->contains(*PI)) { 1262ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // This predecessor is not in the loop. Kill its terminator! 1272ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner BasicBlock *DeadBlock = *PI; 1282ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock); 1292ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner SI != E; ++SI) 1302ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner (*SI)->removePredecessor(DeadBlock); // Remove PHI node entries 1312ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 1322ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner // Delete the dead terminator. 1332ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner DeadBlock->getInstList().pop_back(); 1342ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 1352ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner Value *RetVal = 0; 1362ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner if (LoopBB->getParent()->getReturnType() != Type::VoidTy) 1372ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType()); 1382ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner new ReturnInst(RetVal, DeadBlock); 1392ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner goto Retry; // We just invalidated the pred_iterator. Retry. 1402ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner } 1412ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner } 1422ef703ec429900c5b49d94d82332e7a216a2d7c4Chris Lattner 14338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Does the loop already have a preheader? If so, don't modify the loop... 14438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (L->getLoopPreheader() == 0) { 14538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner InsertPreheaderForLoop(L); 14638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner NumInserted++; 14738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Changed = true; 14838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 14938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 15066ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // Next, check to make sure that all exit nodes of the loop only have 15166ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors that are inside of the loop. This check guarantees that the 15266ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // loop preheader/header will dominate the exit blocks. If the exit block has 15366ea98e85c5f9c03aac139563d7874e93dc345c6Chris Lattner // predecessors from outside of the loop, split the edge now. 154f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner std::vector<BasicBlock*> ExitBlocks; 155f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner L->getExitBlocks(ExitBlocks); 156fed22aac4337c589841c443be70fe05559693f6aChris Lattner 157fed22aac4337c589841c443be70fe05559693f6aChris Lattner SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 158fed22aac4337c589841c443be70fe05559693f6aChris Lattner for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 159fed22aac4337c589841c443be70fe05559693f6aChris Lattner E = ExitBlockSet.end(); I != E; ++I) { 160fed22aac4337c589841c443be70fe05559693f6aChris Lattner BasicBlock *ExitBlock = *I; 161de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 162de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner PI != PE; ++PI) 163de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner if (!L->contains(*PI)) { 164fed22aac4337c589841c443be70fe05559693f6aChris Lattner RewriteLoopExitBlock(L, ExitBlock); 165de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner NumInserted++; 166de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner Changed = true; 167de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner break; 168de7aee760e77d49877ec308bc47dc455b2b754afChris Lattner } 169fed22aac4337c589841c443be70fe05559693f6aChris Lattner } 170dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 171529b28da455a703d226a31a03400e6662ff569feChris Lattner // If the header has more than two predecessors at this point (from the 172529b28da455a703d226a31a03400e6662ff569feChris Lattner // preheader and from multiple backedges), we must adjust the loop. 1732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (L->getNumBackEdges() != 1) { 174529b28da455a703d226a31a03400e6662ff569feChris Lattner // If this is really a nested loop, rip it out into a child loop. 175529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *NL = SeparateNestedLoop(L)) { 176529b28da455a703d226a31a03400e6662ff569feChris Lattner ++NumNested; 177529b28da455a703d226a31a03400e6662ff569feChris Lattner // This is a big restructuring change, reprocess the whole loop. 178529b28da455a703d226a31a03400e6662ff569feChris Lattner ProcessLoop(NL); 179529b28da455a703d226a31a03400e6662ff569feChris Lattner return true; 180529b28da455a703d226a31a03400e6662ff569feChris Lattner } 181529b28da455a703d226a31a03400e6662ff569feChris Lattner 1822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner InsertUniqueBackedgeBlock(L); 1832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NumInserted++; 1842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Changed = true; 1852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 1862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 187329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 188329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner Changed |= ProcessLoop(*I); 18938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner return Changed; 19038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 19138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 192dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// SplitBlockPredecessors - Split the specified block into two blocks. We want 193dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// to move the predecessors specified in the Preds list to point to the new 194dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// block, leaving the remaining predecessors pointing to BB. This method 195dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// updates the SSA PHINode's, but no other analyses. 19638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner/// 197ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris LattnerBasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 198ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattner const char *Suffix, 199dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const std::vector<BasicBlock*> &Preds) { 20038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 201dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Create new basic block, insert right before the original block... 202c24a076c6a22a932e4fc2b745fd748fe7ee3cb15Chris Lattner BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB); 20338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 20438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader first gets an unconditional branch to the loop header... 205108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner BranchInst *BI = new BranchInst(BB, NewBB); 20638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 207dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // For every PHI node in the block, insert a PHI node into NewBB where the 208dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming values from the out of loop edges are moved to NewBB. We have two 209dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // possible cases here. If the loop is dead, we just insert dummy entries 210dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // into the PHI nodes for the new edge. If the loop is not dead, we move the 211dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // incoming edges in BB into new PHI nodes in NewBB. 21238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 213dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!Preds.empty()) { // Is the loop not obviously dead? 2140f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Check to see if the values being merged into the new block need PHI 2150f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // nodes. If so, insert them. 216200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 217200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 218529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; 219529b28da455a703d226a31a03400e6662ff569feChris Lattner 2200f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Check to see if all of the values coming in are the same. If so, we 2210f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // don't need to create a new PHI node. 2220f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 2230f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner for (unsigned i = 1, e = Preds.size(); i != e; ++i) 2240f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 2250f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner InVal = 0; 2260f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner break; 2270f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner } 2280f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner 2290f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // If the values coming into the block are not the same, we need a PHI. 2300f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner if (InVal == 0) { 231010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner // Create the new PHI node, insert it into NewBB at the end of the block 232010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 233010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner 234010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner // Move all of the edges from blocks outside the loop to the new PHI 235010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 236529b28da455a703d226a31a03400e6662ff569feChris Lattner Value *V = PN->removeIncomingValue(Preds[i], false); 237010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner NewPHI->addIncoming(V, Preds[i]); 238010ba10032d7c5f34c209cae1a9445776f49914aChris Lattner } 2390f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner InVal = NewPHI; 2400f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner } else { 2410f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Remove all of the edges coming into the PHI nodes from outside of the 2420f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // block. 2430f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) 2440f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner PN->removeIncomingValue(Preds[i], false); 24538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 2460f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner 2470f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // Add an incoming value to the PHI node in the loop for the preheader 2480f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner // edge. 2490f98e75adff9024dcfe1d2afbfa83625d60ebaa8Chris Lattner PN->addIncoming(InVal, NewBB); 250529b28da455a703d226a31a03400e6662ff569feChris Lattner 251529b28da455a703d226a31a03400e6662ff569feChris Lattner // Can we eliminate this phi node now? 252529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Value *V = hasConstantValue(PN)) { 253c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (!isa<Instruction>(V) || 254c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) { 255c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->replaceAllUsesWith(V); 256c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner BB->getInstList().erase(PN); 257c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner } 258529b28da455a703d226a31a03400e6662ff569feChris Lattner } 25938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 26038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 26138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Now that the PHI nodes are updated, actually move the edges from 262dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Preds to point to NewBB instead of BB. 26338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 264dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 265dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 26638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 267dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (TI->getSuccessor(s) == BB) 26838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner TI->setSuccessor(s, NewBB); 26938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 27038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 27138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } else { // Otherwise the loop is dead... 272200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 273200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 27438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Insert dummy values as the incoming value... 27538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 276200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos } 277dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 278dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner return NewBB; 279dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner} 28038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 281dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 282dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader, this method is called to insert one. This method has two phases: 283dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// preheader insertion and analysis updating. 284dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner/// 285ee2c50cca57272b92cf9e0d1fb238d14d57ea1ddChris Lattnervoid LoopSimplify::InsertPreheaderForLoop(Loop *L) { 286dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *Header = L->getHeader(); 287dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 288dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Compute the set of predecessors of the loop that are not in the loop. 289dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> OutsideBlocks; 290dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 291dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PI != PE; ++PI) 292dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (!L->contains(*PI)) // Coming in from outside the loop? 293dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner OutsideBlocks.push_back(*PI); // Keep track of it... 294dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 295dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Split out the loop pre-header 296dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBB = 297dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 298dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 29938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner //===--------------------------------------------------------------------===// 300cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Update analysis results now that we have performed the transformation 30138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // 30238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 30338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // We know that we have loop information to update... update it now. 30438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (Loop *Parent = L->getParentLoop()) 30538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 3069f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 3079f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner // If the header for the loop used to be an exit node for another loop, then 3089f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner // we need to update this to know that the loop-preheader is now the exit 3099f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner // node. Note that the only loop that could have our header as an exit node 3108f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // is a sibling loop, ie, one with the same parent loop, or one if it's 3118f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // children. 3128f6396e80fa60e4ff79ddf7d81381d726405ac45Chris Lattner // 313329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner LoopInfo::iterator ParentLoops, ParentLoopsE; 314329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner if (Loop *Parent = L->getParentLoop()) { 315329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner ParentLoops = Parent->begin(); 316329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner ParentLoopsE = Parent->end(); 317329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner } else { // Must check top-level loops... 318329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner ParentLoops = getAnalysis<LoopInfo>().begin(); 319329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner ParentLoopsE = getAnalysis<LoopInfo>().end(); 320329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner } 3219f879cfb0a93bf34818fb68e1dc209d47a7d24f3Chris Lattner 322dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 323786c5646e9cd15f18a6a7938673f74b02a05adb8Chris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 32485ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner 32585ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner 32685ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner // Update the dominator tree information. 32785ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner // The immediate dominator of the preheader is the immediate dominator of 32885ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner // the old header. 32985ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner DominatorTree::Node *PHDomTreeNode = 33085ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner DT.createNewNode(NewBB, DT.getNode(Header)->getIDom()); 33185ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner 33285ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner // Change the header node so that PNHode is the new immediate dominator 33385ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner DT.changeImmediateDominator(DT.getNode(Header), PHDomTreeNode); 334786c5646e9cd15f18a6a7938673f74b02a05adb8Chris Lattner 335dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner { 33638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The blocks that dominate NewBB are the blocks that dominate Header, 33738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // minus Header, plus NewBB. 338dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorSet::DomSetType DomSet = DS.getDominators(Header); 33938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner DomSet.erase(Header); // Header does not dominate us... 340dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.addBasicBlock(NewBB, DomSet); 3414d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner 3424d01892e36cc8ea4537b32dd71f11d767edeeef2Chris Lattner // The newly created basic block dominates all nodes dominated by Header. 34385ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner for (df_iterator<DominatorTree::Node*> DFI = df_begin(PHDomTreeNode), 34485ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner E = df_end(PHDomTreeNode); DFI != E; ++DFI) 34585ebd541faf03a00d20ce3bdaf133aa6948c64f8Chris Lattner DS.addDominator((*DFI)->getBlock(), NewBB); 34638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 34738acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 34838acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Update immediate dominator information if we have it... 34938acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 35038acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // Whatever i-dominated the header node now immediately dominates NewBB 35138acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner ID->addNewBlock(NewBB, ID->get(Header)); 35238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 35338acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner // The preheader now is the immediate dominator for the header node... 35438acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner ID->setImmediateDominator(Header, NewBB); 35538acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner } 35638acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner 357dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 358dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 359dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 360dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // everything that Header does, and it strictly dominates Header in 361dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // addition. 362dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 363dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 364dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewDFSet.erase(Header); 365dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 366dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 367dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 368dfa5f83c8ea9fa577c5a42407c3fd8b6c789a6ddMisha Brukman // replacing occurrences of Header with NewBB in some cases. If a block 369dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // dominates a (now) predecessor of NewBB, but did not strictly dominate 370dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Header, it will have Header in it's DF set, but should now have NewBB in 371dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // its set. 372dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 373dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Get all of the dominators of the predecessor... 374dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner const DominatorSet::DomSetType &PredDoms = 375dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DS.getDominators(OutsideBlocks[i]); 376dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 377dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner PDE = PredDoms.end(); PDI != PDE; ++PDI) { 378dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *PredDom = *PDI; 379dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // If the loop header is in DF(PredDom), then PredDom didn't dominate 380dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // the header but did dominate a predecessor outside of the loop. Now 381dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // we change this entry to include the preheader in the DF instead of 382dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // the header. 383dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominanceFrontier::iterator DFI = DF->find(PredDom); 384dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(DFI != DF->end() && "No dominance frontier for node?"); 385dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DFI->second.count(Header)) { 386dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->removeFromFrontier(DFI, Header); 387dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DF->addToFrontier(DFI, NewBB); 388dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 389dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 390dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 391dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 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 DominatorSet &DS = getAnalysis<DominatorSet>(); 399dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 400dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner std::vector<BasicBlock*> LoopBlocks; 401dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 402dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (L->contains(*I)) 403dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner LoopBlocks.push_back(*I); 404dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 4057e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 4067e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 4077e7ad49c23867a5de8e15adfd946fdfa4ba68902Chris Lattner 40869269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner // Update Loop Information - we know that the new block will be in the parent 40969269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner // loop of L. 41069269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner if (Loop *Parent = L->getParentLoop()) 41169269ac203156ae8512c9513b75e5c7217c9ac4eChris Lattner Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 41274cd04ea0154defa837a6d4c12bad29aae44e5b6Chris Lattner 4132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 4142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 41559fb87d469b9b38b0f4c1e31a2f34fa8f09b981dChris Lattner return NewBB; 4162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 4172ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 418529b28da455a703d226a31a03400e6662ff569feChris Lattner/// AddBlockAndPredsToSet - Add the specified block, and all of its 419529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessors, to the specified set, if it's not already in there. Stop 420529b28da455a703d226a31a03400e6662ff569feChris Lattner/// predecessor traversal when we reach StopBlock. 421529b28da455a703d226a31a03400e6662ff569feChris Lattnerstatic void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock, 422529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> &Blocks) { 423529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!Blocks.insert(BB).second) return; // already processed. 424529b28da455a703d226a31a03400e6662ff569feChris Lattner if (BB == StopBlock) return; // Stop here! 425529b28da455a703d226a31a03400e6662ff569feChris Lattner 426529b28da455a703d226a31a03400e6662ff569feChris Lattner for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) 427529b28da455a703d226a31a03400e6662ff569feChris Lattner AddBlockAndPredsToSet(*I, StopBlock, Blocks); 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. 432c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattnerstatic PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS) { 433200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 434200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 4351f62f82b05563df9c83094608de24ea581014d1eChris Lattner ++I; 436c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (Value *V = hasConstantValue(PN)) 437c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) { 438c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // This is a degenerate PHI already, don't modify it! 439c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->replaceAllUsesWith(V); 440c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PN->getParent()->getInstList().erase(PN); 441c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner continue; 442c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner } 443c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner 444c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // Scan this PHI node looking for a use of the PHI node by itself. 445c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 446c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner if (PN->getIncomingValue(i) == PN && 447c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner L->contains(PN->getIncomingBlock(i))) 448c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner // We found something tasty to remove. 449c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner return PN; 4501f62f82b05563df9c83094608de24ea581014d1eChris Lattner } 4511f62f82b05563df9c83094608de24ea581014d1eChris Lattner return 0; 4521f62f82b05563df9c83094608de24ea581014d1eChris Lattner} 4531f62f82b05563df9c83094608de24ea581014d1eChris Lattner 454529b28da455a703d226a31a03400e6662ff569feChris Lattner/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 455529b28da455a703d226a31a03400e6662ff569feChris Lattner/// them out into a nested loop. This is important for code that looks like 456529b28da455a703d226a31a03400e6662ff569feChris Lattner/// this: 457529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 458529b28da455a703d226a31a03400e6662ff569feChris Lattner/// Loop: 459529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 460529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond, Loop, Next 461529b28da455a703d226a31a03400e6662ff569feChris Lattner/// ... 462529b28da455a703d226a31a03400e6662ff569feChris Lattner/// br cond2, Loop, Out 463529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 464529b28da455a703d226a31a03400e6662ff569feChris Lattner/// To identify this common case, we look at the PHI nodes in the header of the 465529b28da455a703d226a31a03400e6662ff569feChris Lattner/// loop. PHI nodes with unchanging values on one backedge correspond to values 466529b28da455a703d226a31a03400e6662ff569feChris Lattner/// that change in the "outer" loop, but not in the "inner" loop. 467529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 468529b28da455a703d226a31a03400e6662ff569feChris Lattner/// If we are able to separate out a loop, return the new outer loop that was 469529b28da455a703d226a31a03400e6662ff569feChris Lattner/// created. 470529b28da455a703d226a31a03400e6662ff569feChris Lattner/// 471529b28da455a703d226a31a03400e6662ff569feChris LattnerLoop *LoopSimplify::SeparateNestedLoop(Loop *L) { 472c30bda7540de573c887e00bb76ac78d85f56acd4Chris Lattner PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>()); 4731f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN == 0) return 0; // No known way to partition. 474529b28da455a703d226a31a03400e6662ff569feChris Lattner 4751f62f82b05563df9c83094608de24ea581014d1eChris Lattner // Pull out all predecessors that have varying values in the loop. This 4761f62f82b05563df9c83094608de24ea581014d1eChris Lattner // handles the case when a PHI node has multiple instances of itself as 4771f62f82b05563df9c83094608de24ea581014d1eChris Lattner // arguments. 478529b28da455a703d226a31a03400e6662ff569feChris Lattner std::vector<BasicBlock*> OuterLoopPreds; 4791f62f82b05563df9c83094608de24ea581014d1eChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 4801f62f82b05563df9c83094608de24ea581014d1eChris Lattner if (PN->getIncomingValue(i) != PN || 4811f62f82b05563df9c83094608de24ea581014d1eChris Lattner !L->contains(PN->getIncomingBlock(i))) 4821f62f82b05563df9c83094608de24ea581014d1eChris Lattner OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 483529b28da455a703d226a31a03400e6662ff569feChris Lattner 4844b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Header = L->getHeader(); 485529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds); 486529b28da455a703d226a31a03400e6662ff569feChris Lattner 487529b28da455a703d226a31a03400e6662ff569feChris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 488529b28da455a703d226a31a03400e6662ff569feChris Lattner UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds); 489529b28da455a703d226a31a03400e6662ff569feChris Lattner 490529b28da455a703d226a31a03400e6662ff569feChris Lattner // Create the new outer loop. 491529b28da455a703d226a31a03400e6662ff569feChris Lattner Loop *NewOuter = new Loop(); 492529b28da455a703d226a31a03400e6662ff569feChris Lattner 493529b28da455a703d226a31a03400e6662ff569feChris Lattner LoopInfo &LI = getAnalysis<LoopInfo>(); 494529b28da455a703d226a31a03400e6662ff569feChris Lattner 495529b28da455a703d226a31a03400e6662ff569feChris Lattner // Change the parent loop to use the outer loop as its child now. 496529b28da455a703d226a31a03400e6662ff569feChris Lattner if (Loop *Parent = L->getParentLoop()) 497529b28da455a703d226a31a03400e6662ff569feChris Lattner Parent->replaceChildLoopWith(L, NewOuter); 498529b28da455a703d226a31a03400e6662ff569feChris Lattner else 499529b28da455a703d226a31a03400e6662ff569feChris Lattner LI.changeTopLevelLoop(L, NewOuter); 500529b28da455a703d226a31a03400e6662ff569feChris Lattner 501529b28da455a703d226a31a03400e6662ff569feChris Lattner // This block is going to be our new header block: add it to this loop and all 502529b28da455a703d226a31a03400e6662ff569feChris Lattner // parent loops. 503529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 504529b28da455a703d226a31a03400e6662ff569feChris Lattner 505529b28da455a703d226a31a03400e6662ff569feChris Lattner // L is now a subloop of our outer loop. 506529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L); 507529b28da455a703d226a31a03400e6662ff569feChris Lattner 508529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 509529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addBlockEntry(L->getBlocks()[i]); 510529b28da455a703d226a31a03400e6662ff569feChris Lattner 511529b28da455a703d226a31a03400e6662ff569feChris Lattner // Determine which blocks should stay in L and which should be moved out to 512529b28da455a703d226a31a03400e6662ff569feChris Lattner // the Outer loop now. 513529b28da455a703d226a31a03400e6662ff569feChris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 514529b28da455a703d226a31a03400e6662ff569feChris Lattner std::set<BasicBlock*> BlocksInL; 515529b28da455a703d226a31a03400e6662ff569feChris Lattner for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 516529b28da455a703d226a31a03400e6662ff569feChris Lattner if (DS.dominates(Header, *PI)) 517529b28da455a703d226a31a03400e6662ff569feChris Lattner AddBlockAndPredsToSet(*PI, Header, BlocksInL); 518529b28da455a703d226a31a03400e6662ff569feChris Lattner 519529b28da455a703d226a31a03400e6662ff569feChris Lattner 520529b28da455a703d226a31a03400e6662ff569feChris Lattner // Scan all of the loop children of L, moving them to OuterLoop if they are 521529b28da455a703d226a31a03400e6662ff569feChris Lattner // not part of the inner loop. 522529b28da455a703d226a31a03400e6662ff569feChris Lattner for (Loop::iterator I = L->begin(); I != L->end(); ) 523529b28da455a703d226a31a03400e6662ff569feChris Lattner if (BlocksInL.count((*I)->getHeader())) 524529b28da455a703d226a31a03400e6662ff569feChris Lattner ++I; // Loop remains in L 525529b28da455a703d226a31a03400e6662ff569feChris Lattner else 526529b28da455a703d226a31a03400e6662ff569feChris Lattner NewOuter->addChildLoop(L->removeChildLoop(I)); 527529b28da455a703d226a31a03400e6662ff569feChris Lattner 528529b28da455a703d226a31a03400e6662ff569feChris Lattner // Now that we know which blocks are in L and which need to be moved to 529529b28da455a703d226a31a03400e6662ff569feChris Lattner // OuterLoop, move any blocks that need it. 530529b28da455a703d226a31a03400e6662ff569feChris Lattner for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 531529b28da455a703d226a31a03400e6662ff569feChris Lattner BasicBlock *BB = L->getBlocks()[i]; 532529b28da455a703d226a31a03400e6662ff569feChris Lattner if (!BlocksInL.count(BB)) { 533529b28da455a703d226a31a03400e6662ff569feChris Lattner // Move this block to the parent, updating the exit blocks sets 534529b28da455a703d226a31a03400e6662ff569feChris Lattner L->removeBlockFromLoop(BB); 535529b28da455a703d226a31a03400e6662ff569feChris Lattner if (LI[BB] == L) 536529b28da455a703d226a31a03400e6662ff569feChris Lattner LI.changeLoopFor(BB, NewOuter); 537529b28da455a703d226a31a03400e6662ff569feChris Lattner --i; 538529b28da455a703d226a31a03400e6662ff569feChris Lattner } 539529b28da455a703d226a31a03400e6662ff569feChris Lattner } 540529b28da455a703d226a31a03400e6662ff569feChris Lattner 541529b28da455a703d226a31a03400e6662ff569feChris Lattner return NewOuter; 542529b28da455a703d226a31a03400e6662ff569feChris Lattner} 543529b28da455a703d226a31a03400e6662ff569feChris Lattner 544529b28da455a703d226a31a03400e6662ff569feChris Lattner 545529b28da455a703d226a31a03400e6662ff569feChris Lattner 5462ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// InsertUniqueBackedgeBlock - This method is called when the specified loop 5472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// has more than one backedge in it. If this occurs, revector all of these 5482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// backedges to target a new basic block and have that block branch to the loop 5492ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// header. This ensures that loops have exactly one backedge. 5502ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 5512ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 5522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 5532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Get information about the loop 5552ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 5562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Header = L->getHeader(); 5572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function *F = Header->getParent(); 5582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5592ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Figure out which basic blocks contain back-edges to the loop header. 5602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> BackedgeBlocks; 5612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 5622ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (*I != Preheader) BackedgeBlocks.push_back(*I); 5632ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5642ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Create and insert the new backedge block... 5652ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 566108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner BranchInst *BETerminator = new BranchInst(Header, BEBlock); 5672ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5682ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Move the new backedge block to right after the last backedge block. 5692ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 5702ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 5712ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5722ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that the block has been inserted into the function, create PHI nodes in 5732ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // the backedge block which correspond to any PHI nodes in the header block. 574200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 575200a360ec66b4d016c17d6f8e3ea559b1fd07205Alkis Evlogimenos PHINode *PN = cast<PHINode>(I); 5762ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 5772ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BETerminator); 5782ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->op_reserve(2*BackedgeBlocks.size()); 5792ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 5802ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Loop over the PHI node, moving all entries except the one for the 5812ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // preheader over to the new PHI node. 5822ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner unsigned PreheaderIdx = ~0U; 5832ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner bool HasUniqueIncomingValue = true; 5842ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *UniqueValue = 0; 5852ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 5862ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *IBB = PN->getIncomingBlock(i); 5872ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner Value *IV = PN->getIncomingValue(i); 5882ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (IBB == Preheader) { 5892ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PreheaderIdx = i; 5902ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } else { 5912ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->addIncoming(IV, IBB); 5922ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 5932ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (UniqueValue == 0) 5942ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UniqueValue = IV; 5952ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner else if (UniqueValue != IV) 5962ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner HasUniqueIncomingValue = false; 5972ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 5982ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 5992ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6002ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6012ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Delete all of the incoming values from the old PN except the preheader's 6022ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 6032ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (PreheaderIdx != 0) { 6042ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 6052ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 6062ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6072ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->op_erase(PN->op_begin()+2, PN->op_end()); 6082ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6092ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Finally, add the newly constructed PHI node as the entry for the BEBlock. 6102ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner PN->addIncoming(NewPN, BEBlock); 6112ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6122ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // As an optimization, if all incoming values in the new PhiNode (which is a 6132ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // subset of the incoming values of the old PHI node) have the same value, 6142ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // eliminate the PHI Node. 6152ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (HasUniqueIncomingValue) { 6162ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewPN->replaceAllUsesWith(UniqueValue); 6172ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BEBlock->getInstList().erase(NewPN); 6182ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6192ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6202ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6212ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Now that all of the PHI nodes have been inserted and adjusted, modify the 6222ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // backedge blocks to just to the BEBlock instead of the header. 6232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 6242ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 6252ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 6262ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner if (TI->getSuccessor(Op) == Header) 6272ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner TI->setSuccessor(Op, BEBlock); 6282ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner } 6292ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6302ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner //===--- Update all analyses which we must preserve now -----------------===// 6312ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6322ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update Loop Information - we know that this block is now in the current 6332ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // loop and all parent loops. 6342ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>()); 6352ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6362ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner // Update dominator information (set, immdom, domtree, and domfrontier) 6372ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 6382ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner} 6392ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6402ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// UpdateDomInfoForRevectoredPreds - This method is used to update the four 6412ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// different kinds of dominator information (dominator sets, immediate 6422ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// dominators, dominator trees, and dominance frontiers) after a new block has 6432ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// been added to the CFG. 6442ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 6454f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// This only supports the case when an existing block (known as "NewBBSucc"), 6464f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// had some of its predecessors factored into a new basic block. This 6472ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// transformation inserts a new basic block ("NewBB"), with a single 6484f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// unconditional branch to NewBBSucc, and moves some predecessors of 6494f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// "NewBBSucc" to now branch to NewBB. These predecessors are listed in 6504f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// PredBlocks, even though they are the same as 6514f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner/// pred_begin(NewBB)/pred_end(NewBB). 6522ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner/// 6532ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattnervoid LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 6542ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner std::vector<BasicBlock*> &PredBlocks) { 6554f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner assert(!PredBlocks.empty() && "No predblocks??"); 6562ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner assert(succ_begin(NewBB) != succ_end(NewBB) && 6572ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner ++succ_begin(NewBB) == succ_end(NewBB) && 6582ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner "NewBB should have a single successor!"); 6594f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner BasicBlock *NewBBSucc = *succ_begin(NewBB); 6602ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner DominatorSet &DS = getAnalysis<DominatorSet>(); 6612ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner 6624f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // Update dominator information... The blocks that dominate NewBB are the 6634f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // intersection of the dominators of predecessors, plus the block itself. 6644f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // 6654f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]); 6664f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 6674f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i])); 6684f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 6694f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner DS.addBasicBlock(NewBB, NewBBDomSet); 6704f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner 6714f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // The newly inserted basic block will dominate existing basic blocks iff the 6724f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate 6734f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // the non-pred blocks, then they all must be the same block! 6744f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // 6754f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner bool NewBBDominatesNewBBSucc = true; 6764f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner { 6774f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner BasicBlock *OnePred = PredBlocks[0]; 6784f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 6794f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (PredBlocks[i] != OnePred) { 6804f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner NewBBDominatesNewBBSucc = false; 6814f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner break; 6824f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 6834f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 6844f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) 6854f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 6864f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner PI != E; ++PI) 68799dcc1da860d5eb4ab05fd27b55fb31f50dd8b4aChris Lattner if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 6884f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner NewBBDominatesNewBBSucc = false; 6894f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner break; 6904f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 6914f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 6924f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 6934f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // The other scenario where the new block can dominate its successors are when 6944f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc 6954f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner // already. 6964f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner if (!NewBBDominatesNewBBSucc) { 6974f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner NewBBDominatesNewBBSucc = true; 6984f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 6994f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner PI != E; ++PI) 7004f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 7014f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner NewBBDominatesNewBBSucc = false; 7024f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner break; 7034f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner } 7044f303bd4a579cc567879fbd1cf6c7a928fae8210Chris Lattner } 705dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 7064f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // If NewBB dominates some blocks, then it will dominate all blocks that 7073e0b870def750929512ebe86e9b589fbab9d538eChris Lattner // NewBBSucc does. 7084f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) { 7094f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner BasicBlock *PredBlock = PredBlocks[0]; 7104f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner Function *F = NewBB->getParent(); 7114f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 7123e0b870def750929512ebe86e9b589fbab9d538eChris Lattner if (DS.dominates(NewBBSucc, I)) 7134f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DS.addDominator(I, NewBB); 7144f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 7154f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 716dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update immediate dominator information if we have it... 717dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner BasicBlock *NewBBIDom = 0; 718dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 7194f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // To find the immediate dominator of the new exit node, we trace up the 7204f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // immediate dominators of a predecessor until we find a basic block that 7214f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // dominates the exit block. 722dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // 7232ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner BasicBlock *Dom = PredBlocks[0]; // Some random predecessor... 724dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 725dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(Dom != 0 && "No shared dominator found???"); 726dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner Dom = ID->get(Dom); 727dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 728dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 729dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Set the immediate dominator now... 730dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner ID->addNewBlock(NewBB, Dom); 731dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 7324f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 7334f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // If NewBB strictly dominates other blocks, we need to update their idom's 7344f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // now. The only block that need adjustment is the NewBBSucc block, whose 7354f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // idom should currently be set to PredBlocks[0]. 7364edf6c043e7a9b9941db7caa3084b99aa18d91adChris Lattner if (NewBBDominatesNewBBSucc) 7374f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner ID->setImmediateDominator(NewBBSucc, NewBB); 738dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 739dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 740dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update DominatorTree information if it is active. 741dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 7424f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // If we don't have ImmediateDominator info around, calculate the idom as 7434f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // above. 744dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner DominatorTree::Node *NewBBIDomNode; 745dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (NewBBIDom) { 746dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = DT->getNode(NewBBIDom); 747dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } else { 7482ab6a7358e7788eae43b73a79e066322ef0a55d5Chris Lattner NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred 749c444a4228f31656f854d15eac671b450df557346Chris Lattner while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) { 750dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner NewBBIDomNode = NewBBIDomNode->getIDom(); 751dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner assert(NewBBIDomNode && "No shared dominator found??"); 752dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 753dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 754dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 7554f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // Create the new dominator tree node... and set the idom of NewBB. 7564f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode); 7574f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 7584f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // If NewBB strictly dominates other blocks, then it is now the immediate 7594f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // dominator of NewBBSucc. Update the dominator tree as appropriate. 7604f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) { 7614f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc); 7624f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DT->changeImmediateDominator(NewBBSuccNode, NewBBNode); 7634f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 764dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 765dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 766dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner // Update dominance frontier information... 767dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 7684b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 7694b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // DF(PredBlocks[0]) without the stuff that the new block does not dominate 7704b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // a predecessor of. 7714f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (NewBBDominatesNewBBSucc) { 7724f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]); 7734f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (DFI != DF->end()) { 7744f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominanceFrontier::DomSetType Set = DFI->second; 7754f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // Filter out stuff in Set that we do not dominate a predecessor of. 7764f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 7774f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner E = Set.end(); SetI != E;) { 7784f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner bool DominatesPred = false; 7794f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 7804f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner PI != E; ++PI) 7814f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (DS.dominates(NewBB, *PI)) 7824f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominatesPred = true; 7834f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner if (!DominatesPred) 7844f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner Set.erase(SetI++); 7854f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner else 7864f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner ++SetI; 7874f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 788dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner 7894f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DF->addBasicBlock(NewBB, Set); 7904f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } 7914f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner 7924f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner } else { 7934f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 7944f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 7954f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner // NewBBSucc)). NewBBSucc is the single successor of NewBB. 7964f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DominanceFrontier::DomSetType NewDFSet; 7974f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner NewDFSet.insert(NewBBSucc); 7984f02fc28eb20f20f41c5ea148ce5058a72b55adeChris Lattner DF->addBasicBlock(NewBB, NewDFSet); 7994b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner } 8004b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner 8014b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // Now we must loop over all of the dominance frontiers in the function, 8024b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // replacing occurrences of NewBBSucc with NewBB in some cases. All 8034b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // blocks that dominate a block in PredBlocks and contained NewBBSucc in 8044b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // their dominance frontier must be updated to contain NewBB instead. 8054b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // 8064b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) { 8074b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *Pred = PredBlocks[i]; 8084b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // Get all of the dominators of the predecessor... 8094b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred); 8104b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 8114b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner PDE = PredDoms.end(); PDI != PDE; ++PDI) { 8124b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner BasicBlock *PredDom = *PDI; 8134b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner 8144b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // If the NewBBSucc node is in DF(PredDom), then PredDom didn't 8154b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // dominate NewBBSucc but did dominate a predecessor of it. Now we 8164b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // change this entry to include NewBB in the DF instead of NewBBSucc. 8174b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner DominanceFrontier::iterator DFI = DF->find(PredDom); 8184b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner assert(DFI != DF->end() && "No dominance frontier for node?"); 8194b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner if (DFI->second.count(NewBBSucc)) { 8204b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // If NewBBSucc should not stay in our dominator frontier, remove it. 8214b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // We remove it unless there is a predecessor of NewBBSucc that we 8224b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // dominate, but we don't strictly dominate NewBBSucc. 8234b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner bool ShouldRemove = true; 8244b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) { 8254b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // Okay, we know that PredDom does not strictly dominate NewBBSucc. 8264b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner // Check to see if it dominates any predecessors of NewBBSucc. 8274b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), 8284b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner E = pred_end(NewBBSucc); PI != E; ++PI) 8294b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner if (DS.dominates(PredDom, *PI)) { 8304b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner ShouldRemove = false; 8314b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner break; 8324b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner } 833dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 8344b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner 8354b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner if (ShouldRemove) 8364b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner DF->removeFromFrontier(DFI, NewBBSucc); 8374b66242c5498a99ed754f698d779243dd1e291e2Chris Lattner DF->addToFrontier(DFI, NewBB); 838dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 839dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 840dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 841dbf3cd7952736b649b4d19badb73ec6c1f9be583Chris Lattner } 84238acf9e85d25f022309372c26d54ecb7c77840f2Chris Lattner} 843d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 844