← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/Scalar/Sink.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/Scalar/Sink.cpp
1
 
//===-- Sink.cpp - Code Sinking -------------------------------------------===//
2
 
//
3
 
//                     The LLVM Compiler Infrastructure
4
 
//
5
 
// This file is distributed under the University of Illinois Open Source
6
 
// License. See LICENSE.TXT for details.
7
 
//
8
 
//===----------------------------------------------------------------------===//
9
 
//
10
 
// This pass moves instructions into successor blocks, when possible, so that
11
 
// they aren't executed on paths where their results aren't needed.
12
 
//
13
 
//===----------------------------------------------------------------------===//
14
 
 
15
 
#define DEBUG_TYPE "sink"
16
 
#include "llvm/Transforms/Scalar.h"
17
 
#include "llvm/IntrinsicInst.h"
18
 
#include "llvm/Analysis/Dominators.h"
19
 
#include "llvm/Analysis/LoopInfo.h"
20
 
#include "llvm/Analysis/AliasAnalysis.h"
21
 
#include "llvm/Assembly/Writer.h"
22
 
#include "llvm/ADT/Statistic.h"
23
 
#include "llvm/Support/CFG.h"
24
 
#include "llvm/Support/Debug.h"
25
 
#include "llvm/Support/raw_ostream.h"
26
 
using namespace llvm;
27
 
 
28
 
STATISTIC(NumSunk, "Number of instructions sunk");
29
 
 
30
 
namespace {
31
 
  class Sinking : public FunctionPass {
32
 
    DominatorTree *DT;
33
 
    LoopInfo *LI;
34
 
    AliasAnalysis *AA;
35
 
 
36
 
  public:
37
 
    static char ID; // Pass identification
38
 
    Sinking() : FunctionPass(ID) {}
39
 
    
40
 
    virtual bool runOnFunction(Function &F);
41
 
    
42
 
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
43
 
      AU.setPreservesCFG();
44
 
      FunctionPass::getAnalysisUsage(AU);
45
 
      AU.addRequired<AliasAnalysis>();
46
 
      AU.addRequired<DominatorTree>();
47
 
      AU.addRequired<LoopInfo>();
48
 
      AU.addPreserved<DominatorTree>();
49
 
      AU.addPreserved<LoopInfo>();
50
 
    }
51
 
  private:
52
 
    bool ProcessBlock(BasicBlock &BB);
53
 
    bool SinkInstruction(Instruction *I, SmallPtrSet<Instruction *, 8> &Stores);
54
 
    bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB) const;
55
 
  };
56
 
} // end anonymous namespace
57
 
  
58
 
char Sinking::ID = 0;
59
 
INITIALIZE_PASS(Sinking, "sink", "Code sinking", false, false);
60
 
 
61
 
FunctionPass *llvm::createSinkingPass() { return new Sinking(); }
62
 
 
63
 
/// AllUsesDominatedByBlock - Return true if all uses of the specified value
64
 
/// occur in blocks dominated by the specified block.
65
 
bool Sinking::AllUsesDominatedByBlock(Instruction *Inst, 
66
 
                                      BasicBlock *BB) const {
67
 
  // Ignoring debug uses is necessary so debug info doesn't affect the code.
68
 
  // This may leave a referencing dbg_value in the original block, before
69
 
  // the definition of the vreg.  Dwarf generator handles this although the
70
 
  // user might not get the right info at runtime.
71
 
  for (Value::use_iterator I = Inst->use_begin(),
72
 
       E = Inst->use_end(); I != E; ++I) {
73
 
    // Determine the block of the use.
74
 
    Instruction *UseInst = cast<Instruction>(*I);
75
 
    BasicBlock *UseBlock = UseInst->getParent();
76
 
    if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
77
 
      // PHI nodes use the operand in the predecessor block, not the block with
78
 
      // the PHI.
79
 
      unsigned Num = PHINode::getIncomingValueNumForOperand(I.getOperandNo());
80
 
      UseBlock = PN->getIncomingBlock(Num);
81
 
    }
82
 
    // Check that it dominates.
83
 
    if (!DT->dominates(BB, UseBlock))
84
 
      return false;
85
 
  }
86
 
  return true;
87
 
}
88
 
 
89
 
bool Sinking::runOnFunction(Function &F) {
90
 
  DT = &getAnalysis<DominatorTree>();
91
 
  LI = &getAnalysis<LoopInfo>();
92
 
  AA = &getAnalysis<AliasAnalysis>();
93
 
 
94
 
  bool EverMadeChange = false;
95
 
  
96
 
  while (1) {
97
 
    bool MadeChange = false;
98
 
 
99
 
    // Process all basic blocks.
100
 
    for (Function::iterator I = F.begin(), E = F.end(); 
101
 
         I != E; ++I)
102
 
      MadeChange |= ProcessBlock(*I);
103
 
    
104
 
    // If this iteration over the code changed anything, keep iterating.
105
 
    if (!MadeChange) break;
106
 
    EverMadeChange = true;
107
 
  } 
108
 
  return EverMadeChange;
109
 
}
110
 
 
111
 
bool Sinking::ProcessBlock(BasicBlock &BB) {
112
 
  // Can't sink anything out of a block that has less than two successors.
113
 
  if (BB.getTerminator()->getNumSuccessors() <= 1 || BB.empty()) return false;
114
 
 
115
 
  // Don't bother sinking code out of unreachable blocks. In addition to being
116
 
  // unprofitable, it can also lead to infinite looping, because in an unreachable
117
 
  // loop there may be nowhere to stop.
118
 
  if (!DT->isReachableFromEntry(&BB)) return false;
119
 
 
120
 
  bool MadeChange = false;
121
 
 
122
 
  // Walk the basic block bottom-up.  Remember if we saw a store.
123
 
  BasicBlock::iterator I = BB.end();
124
 
  --I;
125
 
  bool ProcessedBegin = false;
126
 
  SmallPtrSet<Instruction *, 8> Stores;
127
 
  do {
128
 
    Instruction *Inst = I;  // The instruction to sink.
129
 
    
130
 
    // Predecrement I (if it's not begin) so that it isn't invalidated by
131
 
    // sinking.
132
 
    ProcessedBegin = I == BB.begin();
133
 
    if (!ProcessedBegin)
134
 
      --I;
135
 
 
136
 
    if (isa<DbgInfoIntrinsic>(Inst))
137
 
      continue;
138
 
 
139
 
    if (SinkInstruction(Inst, Stores))
140
 
      ++NumSunk, MadeChange = true;
141
 
    
142
 
    // If we just processed the first instruction in the block, we're done.
143
 
  } while (!ProcessedBegin);
144
 
  
145
 
  return MadeChange;
146
 
}
147
 
 
148
 
static bool isSafeToMove(Instruction *Inst, AliasAnalysis *AA,
149
 
                         SmallPtrSet<Instruction *, 8> &Stores) {
150
 
  if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
151
 
    if (L->isVolatile()) return false;
152
 
 
153
 
    Value *Ptr = L->getPointerOperand();
154
 
    unsigned Size = AA->getTypeStoreSize(L->getType());
155
 
    for (SmallPtrSet<Instruction *, 8>::iterator I = Stores.begin(),
156
 
         E = Stores.end(); I != E; ++I)
157
 
      if (AA->getModRefInfo(*I, Ptr, Size) & AliasAnalysis::Mod)
158
 
        return false;
159
 
  }
160
 
 
161
 
  if (Inst->mayWriteToMemory()) {
162
 
    Stores.insert(Inst);
163
 
    return false;
164
 
  }
165
 
 
166
 
  return Inst->isSafeToSpeculativelyExecute();
167
 
}
168
 
 
169
 
/// SinkInstruction - Determine whether it is safe to sink the specified machine
170
 
/// instruction out of its current block into a successor.
171
 
bool Sinking::SinkInstruction(Instruction *Inst,
172
 
                              SmallPtrSet<Instruction *, 8> &Stores) {
173
 
  // Check if it's safe to move the instruction.
174
 
  if (!isSafeToMove(Inst, AA, Stores))
175
 
    return false;
176
 
  
177
 
  // FIXME: This should include support for sinking instructions within the
178
 
  // block they are currently in to shorten the live ranges.  We often get
179
 
  // instructions sunk into the top of a large block, but it would be better to
180
 
  // also sink them down before their first use in the block.  This xform has to
181
 
  // be careful not to *increase* register pressure though, e.g. sinking
182
 
  // "x = y + z" down if it kills y and z would increase the live ranges of y
183
 
  // and z and only shrink the live range of x.
184
 
  
185
 
  // Loop over all the operands of the specified instruction.  If there is
186
 
  // anything we can't handle, bail out.
187
 
  BasicBlock *ParentBlock = Inst->getParent();
188
 
  
189
 
  // SuccToSinkTo - This is the successor to sink this instruction to, once we
190
 
  // decide.
191
 
  BasicBlock *SuccToSinkTo = 0;
192
 
  
193
 
  // FIXME: This picks a successor to sink into based on having one
194
 
  // successor that dominates all the uses.  However, there are cases where
195
 
  // sinking can happen but where the sink point isn't a successor.  For
196
 
  // example:
197
 
  //   x = computation
198
 
  //   if () {} else {}
199
 
  //   use x
200
 
  // the instruction could be sunk over the whole diamond for the 
201
 
  // if/then/else (or loop, etc), allowing it to be sunk into other blocks
202
 
  // after that.
203
 
  
204
 
  // Instructions can only be sunk if all their uses are in blocks
205
 
  // dominated by one of the successors.
206
 
  // Look at all the successors and decide which one
207
 
  // we should sink to.
208
 
  for (succ_iterator SI = succ_begin(ParentBlock),
209
 
       E = succ_end(ParentBlock); SI != E; ++SI) {
210
 
    if (AllUsesDominatedByBlock(Inst, *SI)) {
211
 
      SuccToSinkTo = *SI;
212
 
      break;
213
 
    }
214
 
  }
215
 
      
216
 
  // If we couldn't find a block to sink to, ignore this instruction.
217
 
  if (SuccToSinkTo == 0)
218
 
    return false;
219
 
  
220
 
  // It is not possible to sink an instruction into its own block.  This can
221
 
  // happen with loops.
222
 
  if (Inst->getParent() == SuccToSinkTo)
223
 
    return false;
224
 
  
225
 
  DEBUG(dbgs() << "Sink instr " << *Inst);
226
 
  DEBUG(dbgs() << "to block ";
227
 
        WriteAsOperand(dbgs(), SuccToSinkTo, false));
228
 
  
229
 
  // If the block has multiple predecessors, this would introduce computation on
230
 
  // a path that it doesn't already exist.  We could split the critical edge,
231
 
  // but for now we just punt.
232
 
  // FIXME: Split critical edges if not backedges.
233
 
  if (SuccToSinkTo->getUniquePredecessor() != ParentBlock) {
234
 
    // We cannot sink a load across a critical edge - there may be stores in
235
 
    // other code paths.
236
 
    if (!Inst->isSafeToSpeculativelyExecute()) {
237
 
      DEBUG(dbgs() << " *** PUNTING: Wont sink load along critical edge.\n");
238
 
      return false;
239
 
    }
240
 
 
241
 
    // We don't want to sink across a critical edge if we don't dominate the
242
 
    // successor. We could be introducing calculations to new code paths.
243
 
    if (!DT->dominates(ParentBlock, SuccToSinkTo)) {
244
 
      DEBUG(dbgs() << " *** PUNTING: Critical edge found\n");
245
 
      return false;
246
 
    }
247
 
 
248
 
    // Don't sink instructions into a loop.
249
 
    if (LI->isLoopHeader(SuccToSinkTo)) {
250
 
      DEBUG(dbgs() << " *** PUNTING: Loop header found\n");
251
 
      return false;
252
 
    }
253
 
 
254
 
    // Otherwise we are OK with sinking along a critical edge.
255
 
    DEBUG(dbgs() << "Sinking along critical edge.\n");
256
 
  }
257
 
  
258
 
  // Determine where to insert into.  Skip phi nodes.
259
 
  BasicBlock::iterator InsertPos = SuccToSinkTo->begin();
260
 
  while (InsertPos != SuccToSinkTo->end() && isa<PHINode>(InsertPos))
261
 
    ++InsertPos;
262
 
  
263
 
  // Move the instruction.
264
 
  Inst->moveBefore(InsertPos);
265
 
  return true;
266
 
}