LCSSA.cpp revision 7be3f1e0788163775cd7c9e4dc6bc82578f28f9e
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 (...) 1511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 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 302480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Transforms/Scalar.h" 3111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Pass.h" 3211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Function.h" 3311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Instructions.h" 349e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson#include "llvm/ADT/SetVector.h" 35a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson#include "llvm/ADT/Statistic.h" 362480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Analysis/Dominators.h" 3711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Analysis/LoopInfo.h" 3811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Support/CFG.h" 392480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include <algorithm> 402f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson#include <map> 4111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4211f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4411f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonnamespace { 45bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson static Statistic<> NumLCSSA("lcssa", 46bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson "Number of live out of a loop variables"); 47a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson 4811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson class LCSSA : public FunctionPass { 4911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson public: 50a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson 51a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson 5211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopInfo *LI; // Loop information 53c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson DominatorTree *DT; // Dominator Tree for the current Function... 542480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson DominanceFrontier *DF; // Current Dominance Frontier 5592deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::vector<BasicBlock*> LoopBlocks; 5611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 5711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual bool runOnFunction(Function &F); 58fc3a3bc64b2781ab63f87312d953e3fa22888899Owen Anderson bool visitSubloop(Loop* L); 59408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson void processInstruction(Instruction* Instr, 60408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson const std::vector<BasicBlock*>& exitBlocks); 6111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 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(); 6811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequiredID(LoopSimplifyID); 6911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreservedID(LoopSimplifyID); 7011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequired<LoopInfo>(); 712f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson AU.addRequired<DominatorTree>(); 722480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson AU.addRequired<DominanceFrontier>(); 7311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 7411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 759e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson SetVector<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L); 76408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Instruction *getValueDominatingBlock(BasicBlock *BB, 779e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson std::map<BasicBlock*, Instruction*>& PotDoms); 789e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson 7992deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson /// inLoop - returns true if the given block is within the current loop 8092deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson const bool inLoop(BasicBlock* B) { 81e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 82e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson } 8311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 8411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 8511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 8611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 8711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 8811f510b577878e61e62a3a9c5c8d86483961d20cOwen AndersonFunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 89a4529321713313545f53ee759800705bdb3f2a29Owen Andersonconst PassInfo *llvm::LCSSAID = X.getPassInfo(); 9011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 91a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// runOnFunction - Process all loops in the function, inner-most out. 9211f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonbool LCSSA::runOnFunction(Function &F) { 9311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson bool changed = false; 947be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 9511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LI = &getAnalysis<LoopInfo>(); 962480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson DF = &getAnalysis<DominanceFrontier>(); 972480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson DT = &getAnalysis<DominatorTree>(); 9811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 9911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 1002480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson changed |= visitSubloop(*I); 10111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 102b9b2b309d3195d9e2ed1e72da8566a470783e8d7Evan Cheng 10311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return changed; 10411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 10511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 106a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// visitSubloop - Recursively process all subloops, and then process the given 107a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// loop if it has live-out values. 1082480737211fcb466f4f8d2c6c5a7303fd832984bOwen Andersonbool LCSSA::visitSubloop(Loop* L) { 1092480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 1102480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson visitSubloop(*I); 1117be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 1122480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson // Speed up queries by creating a sorted list of blocks 11392deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.clear(); 11492deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 11592deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::sort(LoopBlocks.begin(), LoopBlocks.end()); 1162480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson 1179e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson SetVector<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L); 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 12411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::vector<BasicBlock*> exitBlocks; 12511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson L->getExitBlocks(exitBlocks); 12611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 1272f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 1282f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // Iterate over all affected values for this loop and insert Phi nodes 1292f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // for them in the appropriate exit blocks 130408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 1319e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 1322480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson E = AffectedValues.end(); I != E; ++I) { 1339e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson processInstruction(*I, exitBlocks); 134408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 135408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 136c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson assert(L->isLCSSAForm()); 137c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson 13892deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson return true; 139408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 140408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 141a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 142a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// eliminate all out-of-loop uses. 143408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Andersonvoid LCSSA::processInstruction(Instruction* Instr, 144408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson const std::vector<BasicBlock*>& exitBlocks) 145408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson{ 146408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson ++NumLCSSA; // We are applying the transformation 147408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 148408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson std::map<BasicBlock*, Instruction*> Phis; 14930019c88f4b9227460335cbafab0f770eb356083Owen Anderson 15030019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Add the base instruction to the Phis list. This makes tracking down 15130019c88f4b9227460335cbafab0f770eb356083Owen Anderson // the dominating values easier when we're filling in Phi nodes. This will 15230019c88f4b9227460335cbafab0f770eb356083Owen Anderson // be removed later, before we perform use replacement. 153408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Phis[Instr->getParent()] = Instr; 154408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 155408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Phi nodes that need to be IDF-processed 156408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson std::vector<PHINode*> workList; 157408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 158408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (std::vector<BasicBlock*>::const_iterator BBI = exitBlocks.begin(), 1593d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 1603d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson Instruction*& phi = Phis[*BBI]; 1613d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson if (phi == 0 && 1623d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson DT->getNode(Instr->getParent())->dominates(DT->getNode(*BBI))) { 1633d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 164c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson (*BBI)->begin()); 1653d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson workList.push_back(cast<PHINode>(phi)); 1662824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 1673d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson } 16811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 16930019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Phi nodes that need to have their incoming values filled. 17030019c88f4b9227460335cbafab0f770eb356083Owen Anderson std::vector<PHINode*> needIncomingValues; 17130019c88f4b9227460335cbafab0f770eb356083Owen Anderson 172408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where 1739e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson // necessary. Keep track of these new Phi's in the "Phis" map. 174408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson while (!workList.empty()) { 175408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson PHINode *CurPHI = workList.back(); 176408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson workList.pop_back(); 1772f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 17830019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Even though we've removed this Phi from the work list, we still need 17930019c88f4b9227460335cbafab0f770eb356083Owen Anderson // to fill in its incoming values. 18030019c88f4b9227460335cbafab0f770eb356083Owen Anderson needIncomingValues.push_back(CurPHI); 18130019c88f4b9227460335cbafab0f770eb356083Owen Anderson 182408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Get the current Phi's DF, and insert Phi nodes. Add these new 183408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // nodes to our worklist. 184408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson DominanceFrontier::const_iterator it = DF->find(CurPHI->getParent()); 185408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson if (it != DF->end()) { 186408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson const DominanceFrontier::DomSetType &S = it->second; 187408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 188408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson PE = S.end(); P != PE; ++P) { 189c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson if (DT->getNode(Instr->getParent())->dominates(DT->getNode(*P))) { 190c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson Instruction *&Phi = Phis[*P]; 191c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson if (Phi == 0) { 192c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson // Still doesn't have operands... 193c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson Phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 194c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson (*P)->begin()); 1952f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 196c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson workList.push_back(cast<PHINode>(Phi)); 197c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson } 1982f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson } 1992f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson } 200bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson } 20130019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 20230019c88f4b9227460335cbafab0f770eb356083Owen Anderson 20330019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Fill in all Phis we've inserted that need their incoming values filled in. 20430019c88f4b9227460335cbafab0f770eb356083Owen Anderson for (std::vector<PHINode*>::iterator IVI = needIncomingValues.begin(), 20530019c88f4b9227460335cbafab0f770eb356083Owen Anderson IVE = needIncomingValues.end(); IVI != IVE; ++IVI) { 20630019c88f4b9227460335cbafab0f770eb356083Owen Anderson for (pred_iterator PI = pred_begin((*IVI)->getParent()), 20730019c88f4b9227460335cbafab0f770eb356083Owen Anderson E = pred_end((*IVI)->getParent()); PI != E; ++PI) 20830019c88f4b9227460335cbafab0f770eb356083Owen Anderson (*IVI)->addIncoming(getValueDominatingBlock(*PI, Phis), 209408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson *PI); 210bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson } 21100ea74c27e8fbd78f5564d4efd185431c13a92e7Owen Anderson 212408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Find all uses of the affected value, and replace them with the 213408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // appropriate Phi. 214408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson std::vector<Instruction*> Uses; 215408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (Instruction::use_iterator UI = Instr->use_begin(), UE = Instr->use_end(); 216408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson UI != UE; ++UI) { 217408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Instruction* use = cast<Instruction>(*UI); 218c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson // Don't need to update uses within the loop body. 21992deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson if (!inLoop(use->getParent())) 220408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Uses.push_back(use); 221408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 222408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 223408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (std::vector<Instruction*>::iterator II = Uses.begin(), IE = Uses.end(); 224408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson II != IE; ++II) { 2252824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson if (PHINode* phi = dyn_cast<PHINode>(*II)) { 2262824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson for (unsigned int i = 0; i < phi->getNumIncomingValues(); ++i) { 2279e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson if (phi->getIncomingValue(i) == Instr) { 2289e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson Instruction* dominator = 2292824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson getValueDominatingBlock(phi->getIncomingBlock(i), Phis); 2302824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson phi->setIncomingValue(i, dominator); 2319e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson } 2322824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 2332824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } else { 2349e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis); 2359e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson (*II)->replaceUsesOfWith(Instr, NewVal); 2362824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 237408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 23811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 23911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 2402480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 2412480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// are used by instructions outside of it. 2429e1c1ddd4b514731236c0c24184ae194fb4d3706Owen AndersonSetVector<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L) { 243408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 244408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // FIXME: For large loops, we may be able to avoid a lot of use-scanning 245408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // by using dominance information. In particular, if a block does not 246408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // dominate any of the loop exits, then none of the values defined in the 247408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // block could be used outside the loop. 248408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 2499e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson SetVector<Instruction*> AffectedValues; 25011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 25111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) { 25211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 25311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 25411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++UI) { 25511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 2567be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson if (PHINode* p = dyn_cast<PHINode>(*UI)) { 2577be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson unsigned OperandNo = UI.getOperandNo(); 2587be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson UserBB = p->getIncomingBlock(OperandNo/2); 2597be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson } 2607be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 261e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson if (!inLoop(UserBB)) { 26211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AffectedValues.insert(I); 263408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson break; 264408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 26511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 26611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 26711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return AffectedValues; 2682480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson} 269408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 270a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// getValueDominatingBlock - Return the value within the potential dominators 271a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// map that dominates the given block. 272408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen AndersonInstruction *LCSSA::getValueDominatingBlock(BasicBlock *BB, 2739e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson std::map<BasicBlock*, Instruction*>& PotDoms) { 2742824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson DominatorTree::Node* bbNode = DT->getNode(BB); 2752824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson while (bbNode != 0) { 2762824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson std::map<BasicBlock*, Instruction*>::iterator I = 2772824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson PotDoms.find(bbNode->getBlock()); 2782824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson if (I != PotDoms.end()) { 2792824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson return (*I).second; 2802824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 2812824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson bbNode = bbNode->getIDom(); 2822824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 283408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 2842824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson assert(0 && "No dominating value found."); 285408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 286408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson return 0; 287408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 288