LCSSA.cpp revision 844731a7f1909f55935e3514c9e713a62d67662e
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) 2011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// ... = X3 + 4 X4 = phi(X3) 2111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// ... = 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" 369e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson#include "llvm/ADT/SetVector.h" 37a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson#include "llvm/ADT/Statistic.h" 382480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Analysis/Dominators.h" 39b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/LoopPass.h" 40b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 4111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Support/CFG.h" 429133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/Compiler.h" 432480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include <algorithm> 440974ea0911f5099997078861a605357d1e572dddReid Spencer#include <map> 4511f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 47d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumLCSSA, "Number of live out of a loop variables"); 48d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner 4911f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonnamespace { 50b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel struct VISIBILITY_HIDDEN LCSSA : public LoopPass { 51ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 52b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel LCSSA() : LoopPass((intptr_t)&ID) {} 53794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 54d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Cached analysis information for the current function. 55d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner LoopInfo *LI; 56cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DominatorTree *DT; 5792deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::vector<BasicBlock*> LoopBlocks; 5811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 59b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 60b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel 61d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner void ProcessInstruction(Instruction* Instr, 62b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel const SmallVector<BasicBlock*, 8>& exitBlocks); 6311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 6411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// This transformation requires natural loop information & requires that 65a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// loop preheaders be inserted into the CFG. It maintains both of these, 66a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// as well as the CFG. It also requires dominator information. 6711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// 6811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 692480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson AU.setPreservesCFG(); 7011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequiredID(LoopSimplifyID); 7111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreservedID(LoopSimplifyID); 7211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequired<LoopInfo>(); 73b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel AU.addPreserved<LoopInfo>(); 74cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng AU.addRequired<DominatorTree>(); 75b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel AU.addPreserved<ScalarEvolution>(); 7681a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel AU.addPreserved<DominatorTree>(); 7781a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel 7881a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel // Request DominanceFrontier now, even though LCSSA does 7981a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel // not use it. This allows Pass Manager to schedule Dominance 8081a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel // Frontier early enough such that one LPPassManager can handle 8181a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel // multiple loop transformation passes. 8281a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel AU.addRequired<DominanceFrontier>(); 8381a129c0fb6cc3022bb0b5e48ab06d8ab7dc03d5Devang Patel AU.addPreserved<DominanceFrontier>(); 8411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 8511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 86d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner void getLoopValuesUsedOutsideLoop(Loop *L, 87d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner SetVector<Instruction*> &AffectedValues); 88d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 8926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 9026042420d642e810f5cdfb2da6156b74aaf80945Devang Patel std::map<DomTreeNode*, Value*> &Phis); 91d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 9292deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson /// inLoop - returns true if the given block is within the current loop 934aefd6b7d4dadf8109221a89742725c116d8f8e0Anton Korobeynikov bool inLoop(BasicBlock* B) { 94e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 95e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson } 9611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 9711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 98844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 99844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LCSSA::ID = 0; 100844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 10111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 102b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang PatelLoopPass *llvm::createLCSSAPass() { return new LCSSA(); } 103a4529321713313545f53ee759800705bdb3f2a29Owen Andersonconst PassInfo *llvm::LCSSAID = X.getPassInfo(); 10411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 105a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// runOnFunction - Process all loops in the function, inner-most out. 106b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patelbool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) { 1077be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 108b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel LI = &LPM.getAnalysis<LoopInfo>(); 109cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DT = &getAnalysis<DominatorTree>(); 11096bf524b531fd404b118fad7bbe410e9aceeaa5dDevang Patel 1112480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson // Speed up queries by creating a sorted list of blocks 11292deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.clear(); 11392deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 11492deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::sort(LoopBlocks.begin(), LoopBlocks.end()); 1152480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson 116d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner SetVector<Instruction*> AffectedValues; 117d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner getLoopValuesUsedOutsideLoop(L, AffectedValues); 11811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 119408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // If no values are affected, we can save a lot of work, since we know that 120408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // nothing will be changed. 121408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson if (AffectedValues.empty()) 122408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson return false; 123408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 124b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> exitBlocks; 125b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel L->getExitBlocks(exitBlocks); 1262f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 1272f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // Iterate over all affected values for this loop and insert Phi nodes 1282f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // for them in the appropriate exit blocks 129408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 1309e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 131d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner E = AffectedValues.end(); I != E; ++I) 132d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner ProcessInstruction(*I, exitBlocks); 133408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 134c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson assert(L->isLCSSAForm()); 135c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson 13692deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson return true; 137408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 138408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 139a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 140a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// eliminate all out-of-loop uses. 141d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattnervoid LCSSA::ProcessInstruction(Instruction *Instr, 142b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel const SmallVector<BasicBlock*, 8>& exitBlocks) { 143408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson ++NumLCSSA; // We are applying the transformation 144d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 145d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Keep track of the blocks that have the value available already. 14626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel std::map<DomTreeNode*, Value*> Phis; 147d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 14826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *InstrNode = DT->getNode(Instr->getParent()); 149d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 150d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Insert the LCSSA phi's into the exit blocks (dominated by the value), and 151d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // add them to the Phi's map. 152b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel for (SmallVector<BasicBlock*, 8>::const_iterator BBI = exitBlocks.begin(), 1533d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 154d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner BasicBlock *BB = *BBI; 15526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *ExitBBNode = DT->getNode(BB); 156cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng Value *&Phi = Phis[ExitBBNode]; 1579a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (!Phi && DT->dominates(InstrNode, ExitBBNode)) { 158051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Instr->getType(), Instr->getName()+".lcssa", 159051a950000e21935165db56695e35bade668193bGabor Greif BB->begin()); 160cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 161cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner 162cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner // Remember that this phi makes the value alive in this block. 163cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner Phi = PN; 164d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 165d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Add inputs from inside the loop for this PHI. 166d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 167cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner PN->addIncoming(Instr, *PI); 168bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson } 16930019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 17030019c88f4b9227460335cbafab0f770eb356083Owen Anderson 17100ea74c27e8fbd78f5564d4efd185431c13a92e7Owen Anderson 172d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Record all uses of Instr outside the loop. We need to rewrite these. The 173d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // LCSSA phis won't be included because they use the value in the loop. 174d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end(); 175d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner UI != E;) { 176d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 177d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner if (PHINode *P = dyn_cast<PHINode>(*UI)) { 1788b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson unsigned OperandNo = UI.getOperandNo(); 179d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner UserBB = P->getIncomingBlock(OperandNo/2); 1808b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson } 1818b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson 182d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // If the user is in the loop, don't rewrite it! 183f9ba401bf5eddc5ca6282766682116e922f092d7Chris Lattner if (UserBB == Instr->getParent() || inLoop(UserBB)) { 184d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner ++UI; 185d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 1862824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 187d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 188d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Otherwise, patch up uses of the value with the appropriate LCSSA Phi, 189d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // inserting PHI nodes into join points where needed. 190cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis); 191d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 192d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Preincrement the iterator to avoid invalidating it when we change the 193d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // value. 194d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner Use &U = UI.getUse(); 195d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner ++UI; 196d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner U.set(Val); 197408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 19811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 19911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 2002480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 2012480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// are used by instructions outside of it. 202d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattnervoid LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, 203d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner SetVector<Instruction*> &AffectedValues) { 204408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // FIXME: For large loops, we may be able to avoid a lot of use-scanning 205408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // by using dominance information. In particular, if a block does not 206408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // dominate any of the loop exits, then none of the values defined in the 207408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // block could be used outside the loop. 20811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 20911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) { 21011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 21111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 21211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++UI) { 21311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 2147be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson if (PHINode* p = dyn_cast<PHINode>(*UI)) { 2157be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson unsigned OperandNo = UI.getOperandNo(); 2167be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson UserBB = p->getIncomingBlock(OperandNo/2); 2177be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson } 2187be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 219f9ba401bf5eddc5ca6282766682116e922f092d7Chris Lattner if (*BB != UserBB && !inLoop(UserBB)) { 2207b399695289793c57196b66d71d5e965639e920cDevang Patel const StructType *STy = dyn_cast<StructType>(I->getType()); 2217b399695289793c57196b66d71d5e965639e920cDevang Patel if (STy) { 2227b399695289793c57196b66d71d5e965639e920cDevang Patel // I is a call or an invoke that returns multiple values. 2237b399695289793c57196b66d71d5e965639e920cDevang Patel // These values are accessible through getresult only. 2247b399695289793c57196b66d71d5e965639e920cDevang Patel // If the getresult value is not in the BB then move it 2257b399695289793c57196b66d71d5e965639e920cDevang Patel // immediately here. It will be processed in next iteration. 2267b399695289793c57196b66d71d5e965639e920cDevang Patel BasicBlock::iterator InsertPoint; 2277b399695289793c57196b66d71d5e965639e920cDevang Patel if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { 2287b399695289793c57196b66d71d5e965639e920cDevang Patel InsertPoint = II->getNormalDest()->begin(); 2297b399695289793c57196b66d71d5e965639e920cDevang Patel while (isa<PHINode>(InsertPoint)) 2307b399695289793c57196b66d71d5e965639e920cDevang Patel ++InsertPoint; 2317b399695289793c57196b66d71d5e965639e920cDevang Patel } else { 2327b399695289793c57196b66d71d5e965639e920cDevang Patel InsertPoint = I; 2337b399695289793c57196b66d71d5e965639e920cDevang Patel InsertPoint++; 2347b399695289793c57196b66d71d5e965639e920cDevang Patel } 2357b399695289793c57196b66d71d5e965639e920cDevang Patel for (Value::use_iterator TmpI = I->use_begin(), 2367b399695289793c57196b66d71d5e965639e920cDevang Patel TmpE = I->use_end(); TmpI != TmpE; ++TmpI) { 2377b399695289793c57196b66d71d5e965639e920cDevang Patel GetResultInst *GR = cast<GetResultInst>(TmpI); 2387b399695289793c57196b66d71d5e965639e920cDevang Patel if (GR->getParent() != *BB) 2397b399695289793c57196b66d71d5e965639e920cDevang Patel GR->moveBefore(InsertPoint); 2407b399695289793c57196b66d71d5e965639e920cDevang Patel } 2417b399695289793c57196b66d71d5e965639e920cDevang Patel } else 2427b399695289793c57196b66d71d5e965639e920cDevang Patel AffectedValues.insert(I); 243408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson break; 244408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 24511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 24611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 2472480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson} 248408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 249d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner/// GetValueForBlock - Get the value to use within the specified basic block. 250d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner/// available values are in Phis. 25126042420d642e810f5cdfb2da6156b74aaf80945Devang PatelValue *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 25226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel std::map<DomTreeNode*, Value*> &Phis) { 253cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner // If there is no dominator info for this BB, it is unreachable. 254cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner if (BB == 0) 255cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner return UndefValue::get(OrigInst->getType()); 256cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner 257d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // If we have already computed this value, return the previously computed val. 258cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner Value *&V = Phis[BB]; 259d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner if (V) return V; 260d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 26126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDom = BB->getIDom(); 262d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 263d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Otherwise, there are two cases: we either have to insert a PHI node or we 264d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // don't. We need to insert a PHI node if this block is not dominated by one 265d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // of the exit nodes from the loop (the loop could have multiple exits, and 266d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // though the value defined *inside* the loop dominated all its uses, each 267d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // exit by itself may not dominate all the uses). 268d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // 269d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // The simplest way to check for this condition is by checking to see if the 270d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // idom is in the loop. If so, we *know* that none of the exit blocks 271d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // dominate this block. Note that we *know* that the block defining the 272d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // original instruction is in the idom chain, because if it weren't, then the 273d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // original value didn't dominate this use. 274cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng if (!inLoop(IDom->getBlock())) { 275d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Idom is not in the loop, we must still be "below" the exit block and must 276d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // be fully dominated by the value live in the idom. 277d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner return V = GetValueForBlock(IDom, OrigInst, Phis); 278d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 279e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson 280cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng BasicBlock *BBN = BB->getBlock(); 281cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng 282d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 283d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // now, then get values to fill in the incoming values for the PHI. 284051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(OrigInst->getType(), OrigInst->getName()+".lcssa", 285051a950000e21935165db56695e35bade668193bGabor Greif BBN->begin()); 286cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng PN->reserveOperandSpace(std::distance(pred_begin(BBN), pred_end(BBN))); 287cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner V = PN; 288cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner 289d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Fill in the incoming values for the block. 290cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng for (pred_iterator PI = pred_begin(BBN), E = pred_end(BBN); PI != E; ++PI) 291cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI); 292cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner return PN; 293408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 294d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 295