LCSSA.cpp revision 90c579de5a383cee278acc3f7e7b9d0a656e6a35
12480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// The LLVM Compiler Infrastructure 411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson//===----------------------------------------------------------------------===// 911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 1011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// This pass transforms loops by placing phi nodes at the end of the loops for 1111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// all values that are live across the loop boundary. For example, it turns 1211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// the left into the right code: 1311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 1411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// for (...) for (...) 1523d9d27c265753da55a8ee7879820acb4d1e3a6dDan Gohman// if (c) if (c) 1611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// X1 = ... X1 = ... 1711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// else else 1811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// X2 = ... X2 = ... 1911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// X3 = phi(X1, X2) X3 = phi(X1, X2) 20c702a9ed1c99fc520fa8e003f88949a74e0c269fDan Gohman// ... = X3 + 4 X4 = phi(X3) 21c702a9ed1c99fc520fa8e003f88949a74e0c269fDan Gohman// ... = X4 + 4 2211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 2311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// This is still valid LLVM; the extra phi nodes are purely redundant, and will 2411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// be trivially eliminated by InstCombine. The major benefit of this 2511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// transformation is that it makes many other loop optimizations, such as 2611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// LoopUnswitching, simpler. 2711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 2811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson//===----------------------------------------------------------------------===// 2911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 30d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "lcssa" 312480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Transforms/Scalar.h" 32e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson#include "llvm/Constants.h" 3311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Pass.h" 3411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Function.h" 3511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Instructions.h" 362480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Analysis/Dominators.h" 37b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/LoopPass.h" 38b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 398c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner#include "llvm/Transforms/Utils/SSAUpdater.h" 408c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner#include "llvm/ADT/Statistic.h" 418c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner#include "llvm/ADT/STLExtras.h" 4268fbd735f1e0761a3ba16aec4dcb1c1f163f9749Owen Anderson#include "llvm/Support/PredIteratorCache.h" 4311f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 45d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumLCSSA, "Number of live out of a loop variables"); 46d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner 4711f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonnamespace { 488c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner struct LCSSA : public LoopPass { 49ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 5090c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson LCSSA() : LoopPass(ID) {} 51794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 52d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Cached analysis information for the current function. 53cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DominatorTree *DT; 5492deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::vector<BasicBlock*> LoopBlocks; 5568fbd735f1e0761a3ba16aec4dcb1c1f163f9749Owen Anderson PredIteratorCache PredCache; 565c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman Loop *L; 5711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 58b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 59b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel 6011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// This transformation requires natural loop information & requires that 61a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// loop preheaders be inserted into the CFG. It maintains both of these, 62a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// as well as the CFG. It also requires dominator information. 6311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// 6411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 652480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson AU.setPreservesCFG(); 66f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 67052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<DominatorTree>(); 681e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<DominatorTree>(); 691e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<DominanceFrontier>(); 70052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<LoopInfo>(); 711e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<LoopInfo>(); 7211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreservedID(LoopSimplifyID); 731e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<ScalarEvolution>(); 7411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 7511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 768c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner bool ProcessInstruction(Instruction *Inst, 778c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks); 7839b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner 795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman /// verifyAnalysis() - Verify loop nest. 805c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman virtual void verifyAnalysis() const { 815c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Check the special guarantees that LCSSA makes. 82bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!"); 835c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 845c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 8592deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson /// inLoop - returns true if the given block is within the current loop 8639b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner bool inLoop(BasicBlock *B) const { 87e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 88e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson } 8911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 9011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 91844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 92844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LCSSA::ID = 0; 93844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 9411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 95394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLCSSAPass() { return new LCSSA(); } 9690c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LCSSAID = LCSSA::ID; 9711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 988c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 998c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// BlockDominatesAnExit - Return true if the specified block dominates at least 1008c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// one of the blocks in the specified list. 1018c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerstatic bool BlockDominatesAnExit(BasicBlock *BB, 1028c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks, 1038c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner DominatorTree *DT) { 1048c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner DomTreeNode *DomNode = DT->getNode(BB); 1058c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 1068c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (DT->dominates(DomNode, DT->getNode(ExitBlocks[i]))) 1078c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 1088c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1098c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 1108c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 1118c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1128c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 113a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// runOnFunction - Process all loops in the function, inner-most out. 1148c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerbool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) { 1158c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner L = TheLoop; 1167be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 117cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DT = &getAnalysis<DominatorTree>(); 11896bf524b531fd404b118fad7bbe410e9aceeaa5dDevang Patel 1198c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Get the set of exiting blocks. 1208c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SmallVector<BasicBlock*, 8> ExitBlocks; 1218c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner L->getExitBlocks(ExitBlocks); 1228c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1238c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (ExitBlocks.empty()) 1248c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 1258c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 12639b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner // Speed up queries by creating a sorted vector of blocks. 12792deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.clear(); 12892deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 12939b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner array_pod_sort(LoopBlocks.begin(), LoopBlocks.end()); 1307db2789251eba38a5e7be7286570c9c6fbb98e31Owen Anderson 1318c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Look at all the instructions in the loop, checking to see if they have uses 1328c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // outside the loop. If so, rewrite those uses. 1338c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner bool MadeChange = false; 13411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 1358c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (Loop::block_iterator BBI = L->block_begin(), E = L->block_end(); 1368c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BBI != E; ++BBI) { 1378c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *BB = *BBI; 1388c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1398c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // For large loops, avoid use-scanning by using dominance information: In 1408c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // particular, if a block does not dominate any of the loop exits, then none 1418c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // of the values defined in the block could be used outside the loop. 1428c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (!BlockDominatesAnExit(BB, ExitBlocks, DT)) 1438c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner continue; 1448c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1458c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); 1468c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner I != E; ++I) { 1478c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Reject two common cases fast: instructions with no uses (like stores) 1488c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // and instructions with one use that is in the same block as this. 1498c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (I->use_empty() || 1508c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner (I->hasOneUse() && I->use_back()->getParent() == BB && 1518c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner !isa<PHINode>(I->use_back()))) 1528c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner continue; 1538c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1548c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner MadeChange |= ProcessInstruction(I, ExitBlocks); 1558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 1568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 157408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 158bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT)); 1598c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner PredCache.clear(); 160408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 1618c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return MadeChange; 1628c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 163d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1648c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// isExitBlock - Return true if the specified block is in the list. 1658c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerstatic bool isExitBlock(BasicBlock *BB, 1668c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks) { 1678c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 1688c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (ExitBlocks[i] == BB) 1698c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 1708c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 1718c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 172d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1738c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// ProcessInstruction - Given an instruction in the loop, check to see if it 1748c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// has any uses that are outside the current loop. If so, insert LCSSA PHI 1758c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// nodes and rewrite the uses. 1768c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerbool LCSSA::ProcessInstruction(Instruction *Inst, 1778c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks) { 1788c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SmallVector<Use*, 16> UsesToRewrite; 1798c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1808c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *InstBB = Inst->getParent(); 1818c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1828c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end(); 1838c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UI != E; ++UI) { 184a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif User *U = *UI; 185a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 186a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif if (PHINode *PN = dyn_cast<PHINode>(U)) 1878c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UserBB = PN->getIncomingBlock(UI); 1888c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1898c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (InstBB != UserBB && !inLoop(UserBB)) 1908c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UsesToRewrite.push_back(&UI.getUse()); 1918c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 192a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif 1938c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If there are no uses outside the loop, exit with no change. 1948c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (UsesToRewrite.empty()) return false; 1958c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1968c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ++NumLCSSA; // We are applying the transformation 1976b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 1986b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // Invoke instructions are special in that their result value is not available 1996b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // along their unwind edge. The code below tests to see whether DomBB dominates 2006b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // the value, so adjust DomBB to the normal destination block, which is 2016b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // effectively where the value is first usable. 2028c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *DomBB = Inst->getParent(); 2038c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (InvokeInst *Inv = dyn_cast<InvokeInst>(Inst)) 2046b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomBB = Inv->getNormalDest(); 2056b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 2066b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomTreeNode *DomNode = DT->getNode(DomBB); 207d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 2088c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdater SSAUpdate; 2098c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.Initialize(Inst); 2108c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2118c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Insert the LCSSA phi's into all of the exit blocks dominated by the 212f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // value, and add them to the Phi's map. 2138c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (SmallVectorImpl<BasicBlock*>::const_iterator BBI = ExitBlocks.begin(), 21439b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner BBE = ExitBlocks.end(); BBI != BBE; ++BBI) { 2158c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *ExitBB = *BBI; 2168c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (!DT->dominates(DomNode, DT->getNode(ExitBB))) continue; 2178c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2188c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If we already inserted something for this BB, don't reprocess it. 2198c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (SSAUpdate.HasValueForBlock(ExitBB)) continue; 2208c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2218c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner PHINode *PN = PHINode::Create(Inst->getType(), Inst->getName()+".lcssa", 2228c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ExitBB->begin()); 2238c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner PN->reserveOperandSpace(PredCache.GetNumPreds(ExitBB)); 224d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 2258c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Add inputs from inside the loop for this PHI. 226f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) { 2278c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner PN->addIncoming(Inst, *PI); 228f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 229f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // If the exit block has a predecessor not within the loop, arrange for 230eaa181c83ae7d6295e95753a1d6ae9a684d35fa7Dan Gohman // the incoming value use corresponding to that predecessor to be 231f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // rewritten in terms of a different LCSSA PHI. 232f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman if (!inLoop(*PI)) 233f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman UsesToRewrite.push_back( 234f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman &PN->getOperandUse( 235f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1))); 236f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman } 2378c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2388c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Remember that this phi makes the value alive in this block. 2398c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.AddAvailableValue(ExitBB, PN); 24030019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 24130019c88f4b9227460335cbafab0f770eb356083Owen Anderson 2428c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Rewrite all uses outside the loop in terms of the new PHIs we just 2438c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // inserted. 2448c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) { 2458c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If this use is in an exit block, rewrite to use the newly inserted PHI. 2468c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // This is required for correctness because SSAUpdate doesn't handle uses in 2478c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // the same block. It assumes the PHI we inserted is at the end of the 2488c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // block. 2498c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner Instruction *User = cast<Instruction>(UsesToRewrite[i]->getUser()); 2508c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *UserBB = User->getParent(); 2518c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) 2528c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UserBB = PN->getIncomingBlock(*UsesToRewrite[i]); 2538c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2548c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (isa<PHINode>(UserBB->begin()) && 2558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner isExitBlock(UserBB, ExitBlocks)) { 2568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UsesToRewrite[i]->set(UserBB->begin()); 257d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 2582824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 259d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 2608c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Otherwise, do full PHI insertion. 2618c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.RewriteUse(*UsesToRewrite[i]); 262d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 263e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson 2648c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 265408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 266d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 267