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 50081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LCSSA() : LoopPass(ID) { 51081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLCSSAPass(*PassRegistry::getPassRegistry()); 52081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 53794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 54d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Cached analysis information for the current function. 55cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DominatorTree *DT; 5692deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::vector<BasicBlock*> LoopBlocks; 5768fbd735f1e0761a3ba16aec4dcb1c1f163f9749Owen Anderson PredIteratorCache PredCache; 585c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman Loop *L; 5911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 60b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 61b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel 6211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// This transformation requires natural loop information & requires that 63a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// loop preheaders be inserted into the CFG. It maintains both of these, 64a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// as well as the CFG. It also requires dominator information. 6511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// 6611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 672480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson AU.setPreservesCFG(); 68f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 69052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<DominatorTree>(); 70052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<LoopInfo>(); 7111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreservedID(LoopSimplifyID); 721e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addPreserved<ScalarEvolution>(); 7311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 7411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 758c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner bool ProcessInstruction(Instruction *Inst, 768c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks); 7739b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner 785c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman /// verifyAnalysis() - Verify loop nest. 795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman virtual void verifyAnalysis() const { 805c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // Check the special guarantees that LCSSA makes. 81bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!"); 825c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 835c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 8492deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson /// inLoop - returns true if the given block is within the current loop 8539b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner bool inLoop(BasicBlock *B) const { 86e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 87e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson } 8811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 8911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 90844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 91844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LCSSA::ID = 0; 922ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) 932ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 942ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 952ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) 9611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 97394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLCSSAPass() { return new LCSSA(); } 9890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LCSSAID = LCSSA::ID; 9911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 1008c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1018c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// BlockDominatesAnExit - Return true if the specified block dominates at least 1028c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// one of the blocks in the specified list. 1038c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerstatic bool BlockDominatesAnExit(BasicBlock *BB, 1048c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks, 1058c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner DominatorTree *DT) { 1068c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner DomTreeNode *DomNode = DT->getNode(BB); 1078c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 1088c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (DT->dominates(DomNode, DT->getNode(ExitBlocks[i]))) 1098c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 1108c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1118c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 1128c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 1138c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1148c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 115a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// runOnFunction - Process all loops in the function, inner-most out. 1168c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerbool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) { 1178c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner L = TheLoop; 1187be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 119cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DT = &getAnalysis<DominatorTree>(); 12096bf524b531fd404b118fad7bbe410e9aceeaa5dDevang Patel 1218c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Get the set of exiting blocks. 1228c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SmallVector<BasicBlock*, 8> ExitBlocks; 1238c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner L->getExitBlocks(ExitBlocks); 1248c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1258c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (ExitBlocks.empty()) 1268c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 1278c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 12839b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner // Speed up queries by creating a sorted vector of blocks. 12992deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.clear(); 13092deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 13139b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner array_pod_sort(LoopBlocks.begin(), LoopBlocks.end()); 1327db2789251eba38a5e7be7286570c9c6fbb98e31Owen Anderson 1338c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Look at all the instructions in the loop, checking to see if they have uses 1348c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // outside the loop. If so, rewrite those uses. 1358c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner bool MadeChange = false; 13611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 1378c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (Loop::block_iterator BBI = L->block_begin(), E = L->block_end(); 1388c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BBI != E; ++BBI) { 1398c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *BB = *BBI; 1408c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1418c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // For large loops, avoid use-scanning by using dominance information: In 1428c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // particular, if a block does not dominate any of the loop exits, then none 1438c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // of the values defined in the block could be used outside the loop. 1448c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (!BlockDominatesAnExit(BB, ExitBlocks, DT)) 1458c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner continue; 1468c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1478c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); 1488c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner I != E; ++I) { 1498c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Reject two common cases fast: instructions with no uses (like stores) 1508c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // and instructions with one use that is in the same block as this. 1518c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (I->use_empty() || 1528c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner (I->hasOneUse() && I->use_back()->getParent() == BB && 1538c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner !isa<PHINode>(I->use_back()))) 1548c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner continue; 1558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner MadeChange |= ProcessInstruction(I, ExitBlocks); 1578c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 1588c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 159408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 160bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT)); 1618c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner PredCache.clear(); 162408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 1638c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return MadeChange; 1648c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 165d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1668c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// isExitBlock - Return true if the specified block is in the list. 1678c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerstatic bool isExitBlock(BasicBlock *BB, 1688c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks) { 1698c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 1708c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (ExitBlocks[i] == BB) 1718c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 1728c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 1738c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 174d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1758c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// ProcessInstruction - Given an instruction in the loop, check to see if it 1768c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// has any uses that are outside the current loop. If so, insert LCSSA PHI 1778c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner/// nodes and rewrite the uses. 1788c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattnerbool LCSSA::ProcessInstruction(Instruction *Inst, 1798c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner const SmallVectorImpl<BasicBlock*> &ExitBlocks) { 1808c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SmallVector<Use*, 16> UsesToRewrite; 1818c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1828c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *InstBB = Inst->getParent(); 1838c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1848c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end(); 1858c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UI != E; ++UI) { 186a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif User *U = *UI; 187a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 188a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif if (PHINode *PN = dyn_cast<PHINode>(U)) 1898c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UserBB = PN->getIncomingBlock(UI); 1908c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1918c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (InstBB != UserBB && !inLoop(UserBB)) 1928c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UsesToRewrite.push_back(&UI.getUse()); 1938c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 194a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif 1958c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If there are no uses outside the loop, exit with no change. 1968c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (UsesToRewrite.empty()) return false; 1978c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 1988c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ++NumLCSSA; // We are applying the transformation 1996b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 2006b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // Invoke instructions are special in that their result value is not available 2016b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // along their unwind edge. The code below tests to see whether DomBB dominates 2026b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // the value, so adjust DomBB to the normal destination block, which is 2036b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // effectively where the value is first usable. 2048c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *DomBB = Inst->getParent(); 2058c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (InvokeInst *Inv = dyn_cast<InvokeInst>(Inst)) 2066b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomBB = Inv->getNormalDest(); 2076b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 2086b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomTreeNode *DomNode = DT->getNode(DomBB); 209d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 210838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich SmallVector<PHINode*, 16> AddedPHIs; 211838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 2128c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdater SSAUpdate; 213fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands SSAUpdate.Initialize(Inst->getType(), Inst->getName()); 2148c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2158c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Insert the LCSSA phi's into all of the exit blocks dominated by the 216f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // value, and add them to the Phi's map. 2178c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (SmallVectorImpl<BasicBlock*>::const_iterator BBI = ExitBlocks.begin(), 21839b0c3d6133b702367048cd9ef518ad6747f3351Chris Lattner BBE = ExitBlocks.end(); BBI != BBE; ++BBI) { 2198c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *ExitBB = *BBI; 2208c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (!DT->dominates(DomNode, DT->getNode(ExitBB))) continue; 2218c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2228c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If we already inserted something for this BB, don't reprocess it. 2238c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (SSAUpdate.HasValueForBlock(ExitBB)) continue; 2248c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2253ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *PN = PHINode::Create(Inst->getType(), 2263ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PredCache.GetNumPreds(ExitBB), 2273ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad Inst->getName()+".lcssa", 2288c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ExitBB->begin()); 229d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 2308c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Add inputs from inside the loop for this PHI. 231f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) { 2328c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner PN->addIncoming(Inst, *PI); 233f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 234f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // If the exit block has a predecessor not within the loop, arrange for 235eaa181c83ae7d6295e95753a1d6ae9a684d35fa7Dan Gohman // the incoming value use corresponding to that predecessor to be 236f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // rewritten in terms of a different LCSSA PHI. 237f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman if (!inLoop(*PI)) 238f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman UsesToRewrite.push_back( 239f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman &PN->getOperandUse( 240f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1))); 241f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman } 242838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 243838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs.push_back(PN); 2448c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2458c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Remember that this phi makes the value alive in this block. 2468c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.AddAvailableValue(ExitBB, PN); 24730019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 24830019c88f4b9227460335cbafab0f770eb356083Owen Anderson 2498c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Rewrite all uses outside the loop in terms of the new PHIs we just 2508c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // inserted. 2518c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) { 2528c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If this use is in an exit block, rewrite to use the newly inserted PHI. 2538c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // This is required for correctness because SSAUpdate doesn't handle uses in 2548c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // the same block. It assumes the PHI we inserted is at the end of the 2558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // block. 2568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner Instruction *User = cast<Instruction>(UsesToRewrite[i]->getUser()); 2578c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *UserBB = User->getParent(); 2588c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) 2598c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UserBB = PN->getIncomingBlock(*UsesToRewrite[i]); 2608c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 2618c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (isa<PHINode>(UserBB->begin()) && 2628c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner isExitBlock(UserBB, ExitBlocks)) { 2638c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UsesToRewrite[i]->set(UserBB->begin()); 264d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 2652824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 266d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 2678c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Otherwise, do full PHI insertion. 2688c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.RewriteUse(*UsesToRewrite[i]); 269d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 270838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 271838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich // Remove PHI nodes that did not have any uses rewritten. 272838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) { 2736e51c6ad9d9c3c02c7b7692e21645beb68408281Cameron Zwarich if (AddedPHIs[i]->use_empty()) 274838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs[i]->eraseFromParent(); 275838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich } 276e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson 2778c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 278408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 279d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 280