LCSSA.cpp revision e4e1ecd37c42abb307666950bade4b2e462334bb
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" 31e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson#include "llvm/Constants.h" 3211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Pass.h" 3311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Function.h" 3411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Instructions.h" 359e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson#include "llvm/ADT/SetVector.h" 36a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson#include "llvm/ADT/Statistic.h" 372480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Analysis/Dominators.h" 3811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Analysis/LoopInfo.h" 3911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Support/CFG.h" 402480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include <algorithm> 412f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson#include <map> 4211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4311f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4511f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonnamespace { 46bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson static Statistic<> NumLCSSA("lcssa", 47bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson "Number of live out of a loop variables"); 48a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson 4911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson class LCSSA : public FunctionPass { 5011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson public: 51a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson 52a90b2c7240ef4b2db134cc3ae55210652508f073Owen Anderson 5311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopInfo *LI; // Loop information 54c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson DominatorTree *DT; // Dominator Tree for the current Function... 552480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson DominanceFrontier *DF; // Current Dominance Frontier 5692deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::vector<BasicBlock*> LoopBlocks; 5711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 5811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual bool runOnFunction(Function &F); 59fc3a3bc64b2781ab63f87312d953e3fa22888899Owen Anderson bool visitSubloop(Loop* L); 60408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 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>(); 722f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson AU.addRequired<DominatorTree>(); 732480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson AU.addRequired<DominanceFrontier>(); 7411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 7511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 769e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson SetVector<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L); 77e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson Value *getValueDominatingBlock(BasicBlock *BB, 78e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson std::map<BasicBlock*, Value*>& PotDoms) { 7913a68e425767b164802e62269633ae71f60692d2Chris Lattner return getValueDominatingDTNode(DT->getNode(BB), PotDoms); 8013a68e425767b164802e62269633ae71f60692d2Chris Lattner } 81e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson Value *getValueDominatingDTNode(DominatorTree::Node *Node, 82e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson std::map<BasicBlock*, Value*>& PotDoms); 8313a68e425767b164802e62269633ae71f60692d2Chris Lattner 8492deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson /// inLoop - returns true if the given block is within the current loop 8592deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson const bool inLoop(BasicBlock* B) { 86e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 87e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson } 8811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 8911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 9011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 9111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 9211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 9311f510b577878e61e62a3a9c5c8d86483961d20cOwen AndersonFunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 94a4529321713313545f53ee759800705bdb3f2a29Owen Andersonconst PassInfo *llvm::LCSSAID = X.getPassInfo(); 9511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 96a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// runOnFunction - Process all loops in the function, inner-most out. 9711f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonbool LCSSA::runOnFunction(Function &F) { 9811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson bool changed = false; 997be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 10011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LI = &getAnalysis<LoopInfo>(); 1012480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson DF = &getAnalysis<DominanceFrontier>(); 1022480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson DT = &getAnalysis<DominatorTree>(); 10311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 10411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 1052480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson changed |= visitSubloop(*I); 10611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 107b9b2b309d3195d9e2ed1e72da8566a470783e8d7Evan Cheng 10811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return changed; 10911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 11011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 111a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// visitSubloop - Recursively process all subloops, and then process the given 112a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// loop if it has live-out values. 1132480737211fcb466f4f8d2c6c5a7303fd832984bOwen Andersonbool LCSSA::visitSubloop(Loop* L) { 1142480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 1152480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson visitSubloop(*I); 1167be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 1172480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson // Speed up queries by creating a sorted list of blocks 11892deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.clear(); 11992deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 12092deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson std::sort(LoopBlocks.begin(), LoopBlocks.end()); 1212480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson 1229e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson SetVector<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L); 12311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 124408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // If no values are affected, we can save a lot of work, since we know that 125408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // nothing will be changed. 126408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson if (AffectedValues.empty()) 127408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson return false; 128408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 12911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::vector<BasicBlock*> exitBlocks; 13011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson L->getExitBlocks(exitBlocks); 13111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 1322f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 1332f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // Iterate over all affected values for this loop and insert Phi nodes 1342f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson // for them in the appropriate exit blocks 135408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 1369e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 1372480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson E = AffectedValues.end(); I != E; ++I) { 1389e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson processInstruction(*I, exitBlocks); 139408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 140408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 141c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson assert(L->isLCSSAForm()); 142c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson 14392deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson return true; 144408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 145408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 146a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 147a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// eliminate all out-of-loop uses. 148408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Andersonvoid LCSSA::processInstruction(Instruction* Instr, 149408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson const std::vector<BasicBlock*>& exitBlocks) 150408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson{ 151408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson ++NumLCSSA; // We are applying the transformation 152408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 153e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson std::map<BasicBlock*, Value*> Phis; 15430019c88f4b9227460335cbafab0f770eb356083Owen Anderson 15530019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Add the base instruction to the Phis list. This makes tracking down 15630019c88f4b9227460335cbafab0f770eb356083Owen Anderson // the dominating values easier when we're filling in Phi nodes. This will 15730019c88f4b9227460335cbafab0f770eb356083Owen Anderson // be removed later, before we perform use replacement. 158408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Phis[Instr->getParent()] = Instr; 159408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 160408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Phi nodes that need to be IDF-processed 161408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson std::vector<PHINode*> workList; 162408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 163408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (std::vector<BasicBlock*>::const_iterator BBI = exitBlocks.begin(), 1643d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 165e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson Value*& phi = Phis[*BBI]; 1663d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson if (phi == 0 && 1673d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson DT->getNode(Instr->getParent())->dominates(DT->getNode(*BBI))) { 1683d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 169c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson (*BBI)->begin()); 1703d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson workList.push_back(cast<PHINode>(phi)); 1712824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 1723d2aa47bd3a9e2ea5fdcf1690fa280a5199f4d81Owen Anderson } 17311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 17430019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Phi nodes that need to have their incoming values filled. 17530019c88f4b9227460335cbafab0f770eb356083Owen Anderson std::vector<PHINode*> needIncomingValues; 17630019c88f4b9227460335cbafab0f770eb356083Owen Anderson 177408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where 1789e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson // necessary. Keep track of these new Phi's in the "Phis" map. 179408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson while (!workList.empty()) { 180408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson PHINode *CurPHI = workList.back(); 181408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson workList.pop_back(); 1822f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 18330019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Even though we've removed this Phi from the work list, we still need 18430019c88f4b9227460335cbafab0f770eb356083Owen Anderson // to fill in its incoming values. 18530019c88f4b9227460335cbafab0f770eb356083Owen Anderson needIncomingValues.push_back(CurPHI); 18630019c88f4b9227460335cbafab0f770eb356083Owen Anderson 187408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Get the current Phi's DF, and insert Phi nodes. Add these new 188408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // nodes to our worklist. 189408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson DominanceFrontier::const_iterator it = DF->find(CurPHI->getParent()); 190408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson if (it != DF->end()) { 191408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson const DominanceFrontier::DomSetType &S = it->second; 192408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 193408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson PE = S.end(); P != PE; ++P) { 194c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson if (DT->getNode(Instr->getParent())->dominates(DT->getNode(*P))) { 195e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson Value *&Phi = Phis[*P]; 196c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson if (Phi == 0) { 197c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson // Still doesn't have operands... 198c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson Phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 199c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson (*P)->begin()); 2002f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson 201c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson workList.push_back(cast<PHINode>(Phi)); 202c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson } 2032f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson } 2042f21e07915c1e09245d51b64b55f0f25d5f8a7f5Owen Anderson } 205bd82277cbbd93f8704a6bf52c4842c5e71fb675fOwen Anderson } 20630019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 20730019c88f4b9227460335cbafab0f770eb356083Owen Anderson 20830019c88f4b9227460335cbafab0f770eb356083Owen Anderson // Fill in all Phis we've inserted that need their incoming values filled in. 20930019c88f4b9227460335cbafab0f770eb356083Owen Anderson for (std::vector<PHINode*>::iterator IVI = needIncomingValues.begin(), 210e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson IVE = needIncomingValues.end(); IVI != IVE; ++IVI) 21130019c88f4b9227460335cbafab0f770eb356083Owen Anderson for (pred_iterator PI = pred_begin((*IVI)->getParent()), 21230019c88f4b9227460335cbafab0f770eb356083Owen Anderson E = pred_end((*IVI)->getParent()); PI != E; ++PI) 21330019c88f4b9227460335cbafab0f770eb356083Owen Anderson (*IVI)->addIncoming(getValueDominatingBlock(*PI, Phis), 214408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson *PI); 21500ea74c27e8fbd78f5564d4efd185431c13a92e7Owen Anderson 216408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // Find all uses of the affected value, and replace them with the 217408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // appropriate Phi. 218408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson std::vector<Instruction*> Uses; 219408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (Instruction::use_iterator UI = Instr->use_begin(), UE = Instr->use_end(); 220408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson UI != UE; ++UI) { 221408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Instruction* use = cast<Instruction>(*UI); 2228b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson BasicBlock* UserBB = use->getParent(); 2238b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson if (PHINode* p = dyn_cast<PHINode>(use)) { 2248b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson unsigned OperandNo = UI.getOperandNo(); 2258b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson UserBB = p->getIncomingBlock(OperandNo/2); 2268b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson } 2278b92d0cae10b1abf660788e7d8e493d71ac1e477Owen Anderson 228c14c1d472a0bc2a184e4ea1221bd01b1f86e7f26Owen Anderson // Don't need to update uses within the loop body. 22992deacf2f703b1882a30eee1e73b1c99a4b5eec5Owen Anderson if (!inLoop(use->getParent())) 230408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson Uses.push_back(use); 231408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 232408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 233408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson for (std::vector<Instruction*>::iterator II = Uses.begin(), IE = Uses.end(); 234408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson II != IE; ++II) { 2352824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson if (PHINode* phi = dyn_cast<PHINode>(*II)) { 2362824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson for (unsigned int i = 0; i < phi->getNumIncomingValues(); ++i) { 2379e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson if (phi->getIncomingValue(i) == Instr) { 238e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson Value* dominator = 2392824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson getValueDominatingBlock(phi->getIncomingBlock(i), Phis); 2402824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson phi->setIncomingValue(i, dominator); 2419e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson } 2422824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 2432824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } else { 24413a68e425767b164802e62269633ae71f60692d2Chris Lattner Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis); 24513a68e425767b164802e62269633ae71f60692d2Chris Lattner (*II)->replaceUsesOfWith(Instr, NewVal); 2462824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 247408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 24811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 24911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 2502480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 2512480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson/// are used by instructions outside of it. 2529e1c1ddd4b514731236c0c24184ae194fb4d3706Owen AndersonSetVector<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L) { 253408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 254408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // FIXME: For large loops, we may be able to avoid a lot of use-scanning 255408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // by using dominance information. In particular, if a block does not 256408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // dominate any of the loop exits, then none of the values defined in the 257408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson // block could be used outside the loop. 258408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 2599e1c1ddd4b514731236c0c24184ae194fb4d3706Owen Anderson SetVector<Instruction*> AffectedValues; 26011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 26111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) { 26211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 26311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 26411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++UI) { 26511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 2667be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson if (PHINode* p = dyn_cast<PHINode>(*UI)) { 2677be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson unsigned OperandNo = UI.getOperandNo(); 2687be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson UserBB = p->getIncomingBlock(OperandNo/2); 2697be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson } 2707be3f1e0788163775cd7c9e4dc6bc82578f28f9eOwen Anderson 271e9d93d5d70a59f78f4ec726711e9363cfc6b1f4dOwen Anderson if (!inLoop(UserBB)) { 27211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AffectedValues.insert(I); 273408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson break; 274408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson } 27511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 27611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 27711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return AffectedValues; 2782480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson} 279408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 280a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// getValueDominatingBlock - Return the value within the potential dominators 281a4529321713313545f53ee759800705bdb3f2a29Owen Anderson/// map that dominates the given block. 282e4e1ecd37c42abb307666950bade4b2e462334bbOwen AndersonValue *LCSSA::getValueDominatingDTNode(DominatorTree::Node *Node, 283e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson std::map<BasicBlock*, Value*>& PotDoms) { 284e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson // FIXME: The following insertion should be in place rather than the if 285e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson // statement. Currently, this is due to the fact that LCSSA isn't smart 286e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson // enough to avoid inserting IDF Phis that don't dominate any uses. In some 287e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson // of those cases, it could ask us to provide a dominating value for a block 288e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson // that has none, so we need to return undef. 289e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson //assert(Node != 0 && "Didn't find dom value?"); 290e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson if (Node == 0) return UndefValue::get(PotDoms.begin()->second->getType()); 291e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson 292e4e1ecd37c42abb307666950bade4b2e462334bbOwen Anderson Value *&CacheSlot = PotDoms[Node->getBlock()]; 29313a68e425767b164802e62269633ae71f60692d2Chris Lattner if (CacheSlot) return CacheSlot; 294408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson 29513a68e425767b164802e62269633ae71f60692d2Chris Lattner // Otherwise, return the value of the idom and remember this for next time. 29613a68e425767b164802e62269633ae71f60692d2Chris Lattner return CacheSlot = getValueDominatingDTNode(Node->getIDom(), PotDoms); 297408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 298