LCSSA.cpp revision 11f510b577878e61e62a3a9c5c8d86483961d20c 
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/Pass.h"
31#include "llvm/Function.h"
32#include "llvm/Instructions.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/Support/CFG.h"
35#include "llvm/Transforms/Scalar.h"
36#include "llvm/Transforms/Utils/BasicBlockUtils.h"
37#include <iostream>
38#include <set>
39#include <vector>
40
41using namespace llvm;
42
43namespace {
44  class LCSSA : public FunctionPass {
45  public:
46    LoopInfo *LI;  // Loop information
47
48    // LoopProcessWorklist - List of loops we need to process.
49    std::vector<Loop*> LoopProcessWorklist;
50
51    virtual bool runOnFunction(Function &F);
52
53    bool visitLoop(Loop *L, Value *V);
54
55    /// This transformation requires natural loop information & requires that
56    /// loop preheaders be inserted into the CFG...
57    ///
58    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
59      AU.addRequiredID(LoopSimplifyID);
60      AU.addPreservedID(LoopSimplifyID);
61      AU.addRequired<LoopInfo>();
62      AU.addPreserved<LoopInfo>();
63    }
64  private:
65    void addSubloopsToWorklist(Loop* L);
66    std::set<Value*> loopValuesUsedOutsideLoop(Loop *L);
67  };
68
69  RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
70}
71
72FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); }
73
74bool LCSSA::runOnFunction(Function &F) {
75  bool changed = false;
76  LI = &getAnalysis<LoopInfo>();
77
78  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
79    addSubloopsToWorklist(*I);
80    LoopProcessWorklist.push_back(*I);
81  }
82
83  for (std::vector<Loop*>::iterator I = LoopProcessWorklist.begin(),
84       E = LoopProcessWorklist.end(); I != E; ++I) {
85    std::set<Value*> AffectedValues = loopValuesUsedOutsideLoop(*I);
86    if (!AffectedValues.empty()) {
87      for (std::set<Value*>::iterator VI = AffectedValues.begin(),
88           VE = AffectedValues.end(); VI != VE; ++VI)
89        changed |= visitLoop(*I, *VI);
90    }
91  }
92
93  return changed;
94}
95
96bool LCSSA::visitLoop(Loop *L, Value* V) {
97  // We will be doing lots of "loop contains block" queries.  Loop::contains is
98  // linear time, use a set to speed this up.
99  std::set<BasicBlock*> LoopBlocks;
100
101  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
102       BB != E; ++BB)
103    LoopBlocks.insert(*BB);
104
105  std::vector<BasicBlock*> exitBlocks;
106  L->getExitBlocks(exitBlocks);
107
108  for (std::vector<BasicBlock*>::iterator BBI = exitBlocks.begin(),
109       BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
110    PHINode *phi = new PHINode(V->getType(), "lcssa");
111    (*BBI)->getInstList().insert((*BBI)->front(), phi);
112
113    for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE;
114         ++PI)
115      phi->addIncoming(V, *PI);
116  }
117
118  for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;
119       ++UI) {
120    BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
121    if (!LoopBlocks.count(UserBB))
122      ; // FIXME: This should update the SSA form through the rest of the graph.
123  }
124
125  return false;
126}
127
128void LCSSA::addSubloopsToWorklist(Loop* L) {
129  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
130    addSubloopsToWorklist(*I);
131    LoopProcessWorklist.push_back(*I);
132  }
133}
134
135/// loopValuesUsedOutsideLoop - Return true if there are any values defined in
136/// the loop that are used by instructions outside of it.
137std::set<Value*> LCSSA::loopValuesUsedOutsideLoop(Loop *L) {
138  std::set<Value*> AffectedValues;
139
140  // We will be doing lots of "loop contains block" queries.  Loop::contains is
141  // linear time, use a set to speed this up.
142  std::set<BasicBlock*> LoopBlocks;
143
144  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
145       BB != E; ++BB)
146    LoopBlocks.insert(*BB);
147
148  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
149       BB != E; ++BB) {
150    for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I)
151      for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
152           ++UI) {
153        BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
154        if (!LoopBlocks.count(UserBB))
155          AffectedValues.insert(I);
156      }
157  }
158  return AffectedValues;
159}