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