LCSSA.cpp revision a90b2c7240ef4b2db134cc3ae55210652508f073 
1//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Owen Anderson and is distributed under the
6// University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass transforms loops by placing phi nodes at the end of the loops for
11// all values that are live across the loop boundary.  For example, it turns
12// the left into the right code:
13//
14// for (...)                for (...)
15//   if (c)                   if(c)
16//     X1 = ...                 X1 = ...
17//   else                     else
18//     X2 = ...                 X2 = ...
19//   X3 = phi(X1, X2)         X3 = phi(X1, X2)
20// ... = X3 + 4              X4 = phi(X3)
21//                           ... = X4 + 4
22//
23// This is still valid LLVM; the extra phi nodes are purely redundant, and will
24// be trivially eliminated by InstCombine.  The major benefit of this
25// transformation is that it makes many other loop optimizations, such as
26// LoopUnswitching, simpler.
27//
28//===----------------------------------------------------------------------===//
29
30#include "llvm/Transforms/Scalar.h"
31#include "llvm/Pass.h"
32#include "llvm/Function.h"
33#include "llvm/Instructions.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/Analysis/Dominators.h"
36#include "llvm/Analysis/LoopInfo.h"
37#include "llvm/Support/CFG.h"
38#include <algorithm>
39#include <vector>
40
41using namespace llvm;
42
43namespace {
44  static Statistic<> NumLCSSA("lcssa", "Number of times LCSSA was applied");
45
46  class LCSSA : public FunctionPass {
47  public:
48
49
50    LoopInfo *LI;  // Loop information
51    DominatorTree *DT;       // Dominator Tree for the current Loop...
52    DominanceFrontier *DF;   // Current Dominance Frontier
53
54    virtual bool runOnFunction(Function &F);
55    bool visitSubloop(Loop* L);
56
57    /// This transformation requires natural loop information & requires that
58    /// loop preheaders be inserted into the CFG.  It maintains both of these,
59    /// as well as the CFG.  It also requires dominator information.
60    ///
61    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
62      AU.setPreservesCFG();
63      AU.addRequiredID(LoopSimplifyID);
64      AU.addPreservedID(LoopSimplifyID);
65      AU.addRequired<LoopInfo>();
66      AU.addPreserved<LoopInfo>();
67      AU.addRequired<DominatorTree>(); // Not sure if this one will actually
68                                       // be needed.
69      AU.addRequired<DominanceFrontier>();
70    }
71  private:
72    std::set<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L,
73                                           std::vector<BasicBlock*> LoopBlocks);
74  };
75
76  RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
77}
78
79FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); }
80
81bool LCSSA::runOnFunction(Function &F) {
82  bool changed = false;
83  LI = &getAnalysis<LoopInfo>();
84  DF = &getAnalysis<DominanceFrontier>();
85  DT = &getAnalysis<DominatorTree>();
86
87  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
88    changed |= visitSubloop(*I);
89  }
90
91  return changed;
92}
93
94bool LCSSA::visitSubloop(Loop* L) {
95  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
96    visitSubloop(*I);
97
98  // Speed up queries by creating a sorted list of blocks
99  std::vector<BasicBlock*> LoopBlocks(L->block_begin(), L->block_end());
100  std::sort(LoopBlocks.begin(), LoopBlocks.end());
101
102  std::set<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L,
103                                           LoopBlocks);
104
105  std::vector<BasicBlock*> exitBlocks;
106  L->getExitBlocks(exitBlocks);
107
108  for (std::set<Instruction*>::iterator I = AffectedValues.begin(),
109       E = AffectedValues.end(); I != E; ++I) {
110    ++NumLCSSA; // We are applying the transformation
111    for (std::vector<BasicBlock*>::iterator BBI = exitBlocks.begin(),
112         BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
113      PHINode *phi = new PHINode((*I)->getType(), "lcssa");
114      (*BBI)->getInstList().insert((*BBI)->front(), phi);
115
116      for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE;
117           ++PI)
118        phi->addIncoming(*I, *PI);
119    }
120
121    for (Value::use_iterator UI = (*I)->use_begin(), UE = (*I)->use_end();
122         UI != UE; ++UI) {
123      BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
124      if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
125        ; // FIXME: This should update the SSA form.
126    }
127  }
128
129  return true; // FIXME: Should be more intelligent in our return value.
130}
131
132/// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that
133/// are used by instructions outside of it.
134std::set<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L,
135                                         std::vector<BasicBlock*> LoopBlocks) {
136
137  std::set<Instruction*> AffectedValues;
138  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
139       BB != E; ++BB) {
140    for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I)
141      for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
142           ++UI) {
143        BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
144        if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
145          AffectedValues.insert(I);
146      }
147  }
148  return AffectedValues;
149}
150