aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Scalar/GCSE.cpp
blob: fa9867a585356d3f3ae5d0987f83f12e93d1b4b2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
//===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass is designed to be a very quick global transformation that
// eliminates global common subexpressions from a function.  It does this by
// using an existing value numbering implementation to identify the common
// subexpressions, eliminating them when possible.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "gcse"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Type.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ValueNumbering.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
using namespace llvm;

STATISTIC(NumInstRemoved, "Number of instructions removed");
STATISTIC(NumLoadRemoved, "Number of loads removed");
STATISTIC(NumCallRemoved, "Number of calls removed");
STATISTIC(NumNonInsts   , "Number of instructions removed due "
                          "to non-instruction values");
STATISTIC(NumArgsRepl   , "Number of function arguments replaced "
                          "with constant values");
namespace {
  struct VISIBILITY_HIDDEN GCSE : public FunctionPass {
    static char ID; // Pass identifcation, replacement for typeid
    GCSE() : FunctionPass((intptr_t)&ID) {}

    virtual bool runOnFunction(Function &F);

  private:
    void ReplaceInstructionWith(Instruction *I, Value *V);

    // This transformation requires dominator and immediate dominator info
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      AU.addRequired<ETForest>();
      AU.addRequired<DominatorTree>();
      AU.addRequired<ValueNumbering>();
    }
  };

  char GCSE::ID = 0;
  RegisterPass<GCSE> X("gcse", "Global Common Subexpression Elimination");
}

// createGCSEPass - The public interface to this file...
FunctionPass *llvm::createGCSEPass() { return new GCSE(); }

// GCSE::runOnFunction - This is the main transformation entry point for a
// function.
//
bool GCSE::runOnFunction(Function &F) {
  bool Changed = false;

  // Get pointers to the analysis results that we will be using...
  ETForest &EF = getAnalysis<ETForest>();
  ValueNumbering &VN = getAnalysis<ValueNumbering>();
  DominatorTree &DT = getAnalysis<DominatorTree>();

  std::vector<Value*> EqualValues;

  // Check for value numbers of arguments.  If the value numbering
  // implementation can prove that an incoming argument is a constant or global
  // value address, substitute it, making the argument dead.
  for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI)
    if (!AI->use_empty()) {
      VN.getEqualNumberNodes(AI, EqualValues);
      if (!EqualValues.empty()) {
        for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
          if (isa<Constant>(EqualValues[i])) {
            AI->replaceAllUsesWith(EqualValues[i]);
            ++NumArgsRepl;
            Changed = true;
            break;
          }
        EqualValues.clear();
      }
    }

  // Traverse the CFG of the function in dominator order, so that we see each
  // instruction after we see its operands.
  for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
         E = df_end(DT.getRootNode()); DI != E; ++DI) {
    BasicBlock *BB = DI->getBlock();

    // Remember which instructions we've seen in this basic block as we scan.
    std::set<Instruction*> BlockInsts;

    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
      Instruction *Inst = I++;

      if (Constant *C = ConstantFoldInstruction(Inst)) {
        ReplaceInstructionWith(Inst, C);
      } else if (Inst->getType() != Type::VoidTy) {
        // If this instruction computes a value, try to fold together common
        // instructions that compute it.
        //
        VN.getEqualNumberNodes(Inst, EqualValues);

        // If this instruction computes a value that is already computed
        // elsewhere, try to recycle the old value.
        if (!EqualValues.empty()) {
          if (Inst == &*BB->begin())
            I = BB->end();
          else {
            I = Inst; --I;
          }

          // First check to see if we were able to value number this instruction
          // to a non-instruction value.  If so, prefer that value over other
          // instructions which may compute the same thing.
          for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
            if (!isa<Instruction>(EqualValues[i])) {
              ++NumNonInsts;      // Keep track of # of insts repl with values

              // Change all users of Inst to use the replacement and remove it
              // from the program.
              ReplaceInstructionWith(Inst, EqualValues[i]);
              Inst = 0;
              EqualValues.clear();  // don't enter the next loop
              break;
            }

          // If there were no non-instruction values that this instruction
          // produces, find a dominating instruction that produces the same
          // value.  If we find one, use it's value instead of ours.
          for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) {
            Instruction *OtherI = cast<Instruction>(EqualValues[i]);
            bool Dominates = false;
            if (OtherI->getParent() == BB)
              Dominates = BlockInsts.count(OtherI);
            else
              Dominates = EF.dominates(OtherI->getParent(), BB);

            if (Dominates) {
              // Okay, we found an instruction with the same value as this one
              // and that dominates this one.  Replace this instruction with the
              // specified one.
              ReplaceInstructionWith(Inst, OtherI);
              Inst = 0;
              break;
            }
          }

          EqualValues.clear();

          if (Inst) {
            I = Inst; ++I;             // Deleted no instructions
          } else if (I == BB->end()) { // Deleted first instruction
            I = BB->begin();
          } else {                     // Deleted inst in middle of block.
            ++I;
          }
        }

        if (Inst)
          BlockInsts.insert(Inst);
      }
    }
  }

  // When the worklist is empty, return whether or not we changed anything...
  return Changed;
}


void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) {
  if (isa<LoadInst>(I))
    ++NumLoadRemoved; // Keep track of loads eliminated
  if (isa<CallInst>(I))
    ++NumCallRemoved; // Keep track of calls eliminated
  ++NumInstRemoved;   // Keep track of number of insts eliminated

  // Update value numbering
  getAnalysis<ValueNumbering>().deleteValue(I);

  I->replaceAllUsesWith(V);

  if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
    // Removing an invoke instruction requires adding a branch to the normal
    // destination and removing PHI node entries in the exception destination.
    new BranchInst(II->getNormalDest(), II);
    II->getUnwindDest()->removePredecessor(II->getParent());
  }

  // Erase the instruction from the program.
  I->getParent()->getInstList().erase(I);
}