LCSSA.cpp revision 26042420d642e810f5cdfb2da6156b74aaf80945
12480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// The LLVM Compiler Infrastructure 411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// This file was developed by Owen Anderson and is distributed under the 611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// University of Illinois Open Source 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" 3911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Analysis/LoopInfo.h" 4011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Support/CFG.h" 419133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/Compiler.h" 422480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include <algorithm> 430974ea0911f5099997078861a605357d1e572dddReid Spencer#include <map> 4411f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 46d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumLCSSA, "Number of live out of a loop variables"); 47d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner 4811f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonnamespace { 499133fe28954d498fc4de13064c7d65bd811de02cReid Spencer struct VISIBILITY_HIDDEN LCSSA : public FunctionPass { 50ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 51794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel LCSSA() : FunctionPass((intptr_t)&ID) {} 52794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 53d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Cached analysis information for the current function. 54d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner LoopInfo *LI; 55cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DominatorTree *DT; 5692deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::vector<BasicBlock*> LoopBlocks; 5711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 5811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual bool runOnFunction(Function &F); 59fc3a3bc64b2781ab63f87312d953e3fa22888899Owen Anderson bool visitSubloop(Loop* L); 60d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner void ProcessInstruction(Instruction* Instr, 61408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson const std::vector<BasicBlock*>& exitBlocks); 6211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 6311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// This transformation requires natural loop information & requires that 64a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// loop preheaders be inserted into the CFG. It maintains both of these, 65a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson /// as well as the CFG. It also requires dominator information. 6611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// 6711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 682480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson AU.setPreservesCFG(); 6911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequiredID(LoopSimplifyID); 7011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreservedID(LoopSimplifyID); 7111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequired<LoopInfo>(); 72cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng AU.addRequired<DominatorTree>(); 7311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 7411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 75d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner void getLoopValuesUsedOutsideLoop(Loop *L, 76d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner SetVector<Instruction*> &AffectedValues); 77d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 7826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 7926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel std::map<DomTreeNode*, Value*> &Phis); 80d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 8192deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson /// inLoop - returns true if the given block is within the current loop 8292deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson const bool inLoop(BasicBlock* B) { 83e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 84e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson } 8511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 8611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 871997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char LCSSA::ID = 0; 887f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 8911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 9011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 9111f510b577878e61e62a3a9c5c8d86483961d20cOwen AndersonFunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 92a4529321713313545f53ee759800705bdb3f2a29Owen Andersonconst PassInfo *llvm::LCSSAID = X.getPassInfo(); 9311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 94a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// runOnFunction - Process all loops in the function, inner-most out. 9511f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonbool LCSSA::runOnFunction(Function &F) { 9611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson bool changed = false; 977be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 9811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LI = &getAnalysis<LoopInfo>(); 99cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng DT = &getAnalysis<DominatorTree>(); 10011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 101d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 1022480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson changed |= visitSubloop(*I); 103b9b2b309d3195d9e2ed1e72da8566a470783e8d7Evan Cheng 10411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return changed; 10511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 10611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 107a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// visitSubloop - Recursively process all subloops, and then process the given 108a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// loop if it has live-out values. 1092480737211fcb466f4f8d2c6c5a7303fd832984bOwen Andersonbool LCSSA::visitSubloop(Loop* L) { 1102480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 1112480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson visitSubloop(*I); 1127be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 1132480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson // Speed up queries by creating a sorted list of blocks 11492deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.clear(); 11592deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 11692deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::sort(LoopBlocks.begin(), LoopBlocks.end()); 1172480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson 118d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner SetVector<Instruction*> AffectedValues; 119d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner getLoopValuesUsedOutsideLoop(L, AffectedValues); 12011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 121408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // If no values are affected, we can save a lot of work, since we know that 122408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // nothing will be changed. 123408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson if (AffectedValues.empty()) 124408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson return false; 125408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 12611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::vector<BasicBlock*> exitBlocks; 12711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson L->getExitBlocks(exitBlocks); 12811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 1292f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 1302f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // Iterate over all affected values for this loop and insert Phi nodes 1312f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // for them in the appropriate exit blocks 132408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 1339e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 134d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner E = AffectedValues.end(); I != E; ++I) 135d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner ProcessInstruction(*I, exitBlocks); 136408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 137c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson assert(L->isLCSSAForm()); 138c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson 13992deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson return true; 140408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 141408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 142a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 143a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// eliminate all out-of-loop uses. 144d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattnervoid LCSSA::ProcessInstruction(Instruction *Instr, 145d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner const std::vector<BasicBlock*>& exitBlocks) { 146408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson ++NumLCSSA; // We are applying the transformation 147d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 148d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Keep track of the blocks that have the value available already. 14926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel std::map<DomTreeNode*, Value*> Phis; 150d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 15126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *InstrNode = DT->getNode(Instr->getParent()); 152d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 153d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Insert the LCSSA phi's into the exit blocks (dominated by the value), and 154d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // add them to the Phi's map. 155408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (std::vector<BasicBlock*>::const_iterator BBI = exitBlocks.begin(), 1563d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 157d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner BasicBlock *BB = *BBI; 15826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *ExitBBNode = DT->getNode(BB); 159cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng Value *&Phi = Phis[ExitBBNode]; 160cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng if (!Phi && InstrNode->dominates(ExitBBNode)) { 161cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner PHINode *PN = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 162cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner BB->begin()); 163cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 164cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner 165cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner // Remember that this phi makes the value alive in this block. 166cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner Phi = PN; 167d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 168d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Add inputs from inside the loop for this PHI. 169d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 170cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner PN->addIncoming(Instr, *PI); 171bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson } 17230019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 17330019c88f4b9227460335cbafab0f770eb356083Owen Anderson 17400ea74c27e8fbd78f5564d4efd185431c13a92e7Owen Anderson 175d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Record all uses of Instr outside the loop. We need to rewrite these. The 176d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // LCSSA phis won't be included because they use the value in the loop. 177d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end(); 178d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner UI != E;) { 179d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 180d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner if (PHINode *P = dyn_cast<PHINode>(*UI)) { 1818b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson unsigned OperandNo = UI.getOperandNo(); 182d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner UserBB = P->getIncomingBlock(OperandNo/2); 1838b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson } 1848b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson 185d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // If the user is in the loop, don't rewrite it! 186f9ba401bf5eddc5ca6282766682116e922f092d7Chris Lattner if (UserBB == Instr->getParent() || inLoop(UserBB)) { 187d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner ++UI; 188d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 1892824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 190d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 191d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Otherwise, patch up uses of the value with the appropriate LCSSA Phi, 192d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // inserting PHI nodes into join points where needed. 193cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis); 194d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 195d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Preincrement the iterator to avoid invalidating it when we change the 196d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // value. 197d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner Use &U = UI.getUse(); 198d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner ++UI; 199d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner U.set(Val); 200408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 20111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 20211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 2032480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 2042480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// are used by instructions outside of it. 205d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattnervoid LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, 206d6b7a1648c12250c4001f2bffd2a2f61d16e59a7Chris Lattner SetVector<Instruction*> &AffectedValues) { 207408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // FIXME: For large loops, we may be able to avoid a lot of use-scanning 208408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // by using dominance information. In particular, if a block does not 209408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // dominate any of the loop exits, then none of the values defined in the 210408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // block could be used outside the loop. 21111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 21211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) { 21311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 21411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 21511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++UI) { 21611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 2177be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson if (PHINode* p = dyn_cast<PHINode>(*UI)) { 2187be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson unsigned OperandNo = UI.getOperandNo(); 2197be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson UserBB = p->getIncomingBlock(OperandNo/2); 2207be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson } 2217be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 222f9ba401bf5eddc5ca6282766682116e922f092d7Chris Lattner if (*BB != UserBB && !inLoop(UserBB)) { 22311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AffectedValues.insert(I); 224408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson break; 225408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 22611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 22711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 2282480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson} 229408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 230d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner/// GetValueForBlock - Get the value to use within the specified basic block. 231d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner/// available values are in Phis. 23226042420d642e810f5cdfb2da6156b74aaf80945Devang PatelValue *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 23326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel std::map<DomTreeNode*, Value*> &Phis) { 234cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner // If there is no dominator info for this BB, it is unreachable. 235cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner if (BB == 0) 236cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner return UndefValue::get(OrigInst->getType()); 237cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner 238d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // If we have already computed this value, return the previously computed val. 239cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner Value *&V = Phis[BB]; 240d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner if (V) return V; 241d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 24226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDom = BB->getIDom(); 243d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 244d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Otherwise, there are two cases: we either have to insert a PHI node or we 245d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // don't. We need to insert a PHI node if this block is not dominated by one 246d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // of the exit nodes from the loop (the loop could have multiple exits, and 247d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // though the value defined *inside* the loop dominated all its uses, each 248d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // exit by itself may not dominate all the uses). 249d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // 250d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // The simplest way to check for this condition is by checking to see if the 251d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // idom is in the loop. If so, we *know* that none of the exit blocks 252d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // dominate this block. Note that we *know* that the block defining the 253d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // original instruction is in the idom chain, because if it weren't, then the 254d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // original value didn't dominate this use. 255cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng if (!inLoop(IDom->getBlock())) { 256d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Idom is not in the loop, we must still be "below" the exit block and must 257d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // be fully dominated by the value live in the idom. 258d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner return V = GetValueForBlock(IDom, OrigInst, Phis); 259d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 260e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson 261cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng BasicBlock *BBN = BB->getBlock(); 262cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng 263d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 264d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // now, then get values to fill in the incoming values for the PHI. 265cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner PHINode *PN = new PHINode(OrigInst->getType(), OrigInst->getName()+".lcssa", 266cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng BBN->begin()); 267cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng PN->reserveOperandSpace(std::distance(pred_begin(BBN), pred_end(BBN))); 268cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner V = PN; 269cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner 270d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner // Fill in the incoming values for the block. 271cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng for (pred_iterator PI = pred_begin(BBN), E = pred_end(BBN); PI != E; ++PI) 272cc045d5df8ad029363f2d0c58db87b15748ce67fEvan Cheng PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI); 273cbea67f55b2211192da23cde8c968b3659b83116Chris Lattner return PN; 274408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 275d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 276