← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/Scalar/SCCVN.cpp
 
1
//===- SCCVN.cpp - Eliminate redundant values -----------------------------===//
 
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 performs global value numbering to eliminate fully redundant
 
11
// instructions.  This is based on the paper "SCC-based Value Numbering"
 
12
// by Cooper, et al.
 
13
//
 
14
//===----------------------------------------------------------------------===//
 
15
 
 
16
#define DEBUG_TYPE "sccvn"
 
17
#include "llvm/Transforms/Scalar.h"
 
18
#include "llvm/BasicBlock.h"
 
19
#include "llvm/Constants.h"
 
20
#include "llvm/DerivedTypes.h"
 
21
#include "llvm/Function.h"
 
22
#include "llvm/Operator.h"
 
23
#include "llvm/Value.h"
 
24
#include "llvm/ADT/DenseMap.h"
 
25
#include "llvm/ADT/DepthFirstIterator.h"
 
26
#include "llvm/ADT/PostOrderIterator.h"
 
27
#include "llvm/ADT/SmallPtrSet.h"
 
28
#include "llvm/ADT/SmallVector.h"
 
29
#include "llvm/ADT/SparseBitVector.h"
 
30
#include "llvm/ADT/Statistic.h"
 
31
#include "llvm/Analysis/Dominators.h"
 
32
#include "llvm/Support/CFG.h"
 
33
#include "llvm/Support/CommandLine.h"
 
34
#include "llvm/Support/Debug.h"
 
35
#include "llvm/Support/ErrorHandling.h"
 
36
#include "llvm/Transforms/Utils/SSAUpdater.h"
 
37
using namespace llvm;
 
38
 
 
39
STATISTIC(NumSCCVNInstr,  "Number of instructions deleted by SCCVN");
 
40
STATISTIC(NumSCCVNPhi,  "Number of phis deleted by SCCVN");
 
41
 
 
42
//===----------------------------------------------------------------------===//
 
43
//                         ValueTable Class
 
44
//===----------------------------------------------------------------------===//
 
45
 
 
46
/// This class holds the mapping between values and value numbers.  It is used
 
47
/// as an efficient mechanism to determine the expression-wise equivalence of
 
48
/// two values.
 
49
namespace {
 
50
  struct Expression {
 
51
    enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
 
52
                            UDIV, SDIV, FDIV, UREM, SREM,
 
53
                            FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
 
54
                            ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
 
55
                            ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
 
56
                            FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
 
57
                            FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
 
58
                            FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
 
59
                            SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
 
60
                            FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
 
61
                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
 
62
                            INSERTVALUE, EXTRACTVALUE, EMPTY, TOMBSTONE };
 
63
 
 
64
    ExpressionOpcode opcode;
 
65
    const Type* type;
 
66
    SmallVector<uint32_t, 4> varargs;
 
67
 
 
68
    Expression() { }
 
69
    Expression(ExpressionOpcode o) : opcode(o) { }
 
70
 
 
71
    bool operator==(const Expression &other) const {
 
72
      if (opcode != other.opcode)
 
73
        return false;
 
74
      else if (opcode == EMPTY || opcode == TOMBSTONE)
 
75
        return true;
 
76
      else if (type != other.type)
 
77
        return false;
 
78
      else {
 
79
        if (varargs.size() != other.varargs.size())
 
80
          return false;
 
81
 
 
82
        for (size_t i = 0; i < varargs.size(); ++i)
 
83
          if (varargs[i] != other.varargs[i])
 
84
            return false;
 
85
 
 
86
        return true;
 
87
      }
 
88
    }
 
89
 
 
90
    bool operator!=(const Expression &other) const {
 
91
      return !(*this == other);
 
92
    }
 
93
  };
 
94
 
 
95
  class ValueTable {
 
96
    private:
 
97
      DenseMap<Value*, uint32_t> valueNumbering;
 
98
      DenseMap<Expression, uint32_t> expressionNumbering;
 
99
      DenseMap<Value*, uint32_t> constantsNumbering;
 
100
 
 
101
      uint32_t nextValueNumber;
 
102
 
 
103
      Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
 
104
      Expression::ExpressionOpcode getOpcode(CmpInst* C);
 
105
      Expression::ExpressionOpcode getOpcode(CastInst* C);
 
106
      Expression create_expression(BinaryOperator* BO);
 
107
      Expression create_expression(CmpInst* C);
 
108
      Expression create_expression(ShuffleVectorInst* V);
 
109
      Expression create_expression(ExtractElementInst* C);
 
110
      Expression create_expression(InsertElementInst* V);
 
111
      Expression create_expression(SelectInst* V);
 
112
      Expression create_expression(CastInst* C);
 
113
      Expression create_expression(GetElementPtrInst* G);
 
114
      Expression create_expression(CallInst* C);
 
115
      Expression create_expression(Constant* C);
 
116
      Expression create_expression(ExtractValueInst* C);
 
117
      Expression create_expression(InsertValueInst* C);
 
118
    public:
 
119
      ValueTable() : nextValueNumber(1) { }
 
120
      uint32_t computeNumber(Value *V);
 
121
      uint32_t lookup(Value *V);
 
122
      void add(Value *V, uint32_t num);
 
123
      void clear();
 
124
      void clearExpressions();
 
125
      void erase(Value *v);
 
126
      unsigned size();
 
127
      void verifyRemoved(const Value *) const;
 
128
  };
 
129
}
 
130
 
 
131
namespace llvm {
 
132
template <> struct DenseMapInfo<Expression> {
 
133
  static inline Expression getEmptyKey() {
 
134
    return Expression(Expression::EMPTY);
 
135
  }
 
136
 
 
137
  static inline Expression getTombstoneKey() {
 
138
    return Expression(Expression::TOMBSTONE);
 
139
  }
 
140
 
 
141
  static unsigned getHashValue(const Expression e) {
 
142
    unsigned hash = e.opcode;
 
143
 
 
144
    hash = ((unsigned)((uintptr_t)e.type >> 4) ^
 
145
            (unsigned)((uintptr_t)e.type >> 9));
 
146
 
 
147
    for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
 
148
         E = e.varargs.end(); I != E; ++I)
 
149
      hash = *I + hash * 37;
 
150
 
 
151
    return hash;
 
152
  }
 
153
  static bool isEqual(const Expression &LHS, const Expression &RHS) {
 
154
    return LHS == RHS;
 
155
  }
 
156
};
 
157
template <>
 
158
struct isPodLike<Expression> { static const bool value = true; };
 
159
 
 
160
}
 
161
 
 
162
//===----------------------------------------------------------------------===//
 
163
//                     ValueTable Internal Functions
 
164
//===----------------------------------------------------------------------===//
 
165
Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
 
166
  switch(BO->getOpcode()) {
 
167
  default: // THIS SHOULD NEVER HAPPEN
 
168
    llvm_unreachable("Binary operator with unknown opcode?");
 
169
  case Instruction::Add:  return Expression::ADD;
 
170
  case Instruction::FAdd: return Expression::FADD;
 
171
  case Instruction::Sub:  return Expression::SUB;
 
172
  case Instruction::FSub: return Expression::FSUB;
 
173
  case Instruction::Mul:  return Expression::MUL;
 
174
  case Instruction::FMul: return Expression::FMUL;
 
175
  case Instruction::UDiv: return Expression::UDIV;
 
176
  case Instruction::SDiv: return Expression::SDIV;
 
177
  case Instruction::FDiv: return Expression::FDIV;
 
178
  case Instruction::URem: return Expression::UREM;
 
179
  case Instruction::SRem: return Expression::SREM;
 
180
  case Instruction::FRem: return Expression::FREM;
 
181
  case Instruction::Shl:  return Expression::SHL;
 
182
  case Instruction::LShr: return Expression::LSHR;
 
183
  case Instruction::AShr: return Expression::ASHR;
 
184
  case Instruction::And:  return Expression::AND;
 
185
  case Instruction::Or:   return Expression::OR;
 
186
  case Instruction::Xor:  return Expression::XOR;
 
187
  }
 
188
}
 
189
 
 
190
Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 
191
  if (isa<ICmpInst>(C)) {
 
192
    switch (C->getPredicate()) {
 
193
    default:  // THIS SHOULD NEVER HAPPEN
 
194
      llvm_unreachable("Comparison with unknown predicate?");
 
195
    case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
 
196
    case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
 
197
    case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
 
198
    case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
 
199
    case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
 
200
    case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
 
201
    case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
 
202
    case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
 
203
    case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
 
204
    case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
 
205
    }
 
206
  } else {
 
207
    switch (C->getPredicate()) {
 
208
    default: // THIS SHOULD NEVER HAPPEN
 
209
      llvm_unreachable("Comparison with unknown predicate?");
 
210
    case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
 
211
    case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
 
212
    case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
 
213
    case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
 
214
    case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
 
215
    case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
 
216
    case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
 
217
    case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
 
218
    case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
 
219
    case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
 
220
    case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
 
221
    case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
 
222
    case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
 
223
    case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
 
224
    }
 
225
  }
 
226
}
 
227
 
 
228
Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
 
229
  switch(C->getOpcode()) {
 
230
  default: // THIS SHOULD NEVER HAPPEN
 
231
    llvm_unreachable("Cast operator with unknown opcode?");
 
232
  case Instruction::Trunc:    return Expression::TRUNC;
 
233
  case Instruction::ZExt:     return Expression::ZEXT;
 
234
  case Instruction::SExt:     return Expression::SEXT;
 
235
  case Instruction::FPToUI:   return Expression::FPTOUI;
 
236
  case Instruction::FPToSI:   return Expression::FPTOSI;
 
237
  case Instruction::UIToFP:   return Expression::UITOFP;
 
238
  case Instruction::SIToFP:   return Expression::SITOFP;
 
239
  case Instruction::FPTrunc:  return Expression::FPTRUNC;
 
240
  case Instruction::FPExt:    return Expression::FPEXT;
 
241
  case Instruction::PtrToInt: return Expression::PTRTOINT;
 
242
  case Instruction::IntToPtr: return Expression::INTTOPTR;
 
243
  case Instruction::BitCast:  return Expression::BITCAST;
 
244
  }
 
245
}
 
246
 
 
247
Expression ValueTable::create_expression(CallInst* C) {
 
248
  Expression e;
 
249
 
 
250
  e.type = C->getType();
 
251
  e.opcode = Expression::CALL;
 
252
 
 
253
  e.varargs.push_back(lookup(C->getCalledFunction()));
 
254
  for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
 
255
       I != E; ++I)
 
256
    e.varargs.push_back(lookup(*I));
 
257
 
 
258
  return e;
 
259
}
 
260
 
 
261
Expression ValueTable::create_expression(BinaryOperator* BO) {
 
262
  Expression e;
 
263
  e.varargs.push_back(lookup(BO->getOperand(0)));
 
264
  e.varargs.push_back(lookup(BO->getOperand(1)));
 
265
  e.type = BO->getType();
 
266
  e.opcode = getOpcode(BO);
 
267
 
 
268
  return e;
 
269
}
 
270
 
 
271
Expression ValueTable::create_expression(CmpInst* C) {
 
272
  Expression e;
 
273
 
 
274
  e.varargs.push_back(lookup(C->getOperand(0)));
 
275
  e.varargs.push_back(lookup(C->getOperand(1)));
 
276
  e.type = C->getType();
 
277
  e.opcode = getOpcode(C);
 
278
 
 
279
  return e;
 
280
}
 
281
 
 
282
Expression ValueTable::create_expression(CastInst* C) {
 
283
  Expression e;
 
284
 
 
285
  e.varargs.push_back(lookup(C->getOperand(0)));
 
286
  e.type = C->getType();
 
287
  e.opcode = getOpcode(C);
 
288
 
 
289
  return e;
 
290
}
 
291
 
 
292
Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 
293
  Expression e;
 
294
 
 
295
  e.varargs.push_back(lookup(S->getOperand(0)));
 
296
  e.varargs.push_back(lookup(S->getOperand(1)));
 
297
  e.varargs.push_back(lookup(S->getOperand(2)));
 
298
  e.type = S->getType();
 
299
  e.opcode = Expression::SHUFFLE;
 
300
 
 
301
  return e;
 
302
}
 
303
 
 
304
Expression ValueTable::create_expression(ExtractElementInst* E) {
 
305
  Expression e;
 
306
 
 
307
  e.varargs.push_back(lookup(E->getOperand(0)));
 
308
  e.varargs.push_back(lookup(E->getOperand(1)));
 
309
  e.type = E->getType();
 
310
  e.opcode = Expression::EXTRACT;
 
311
 
 
312
  return e;
 
313
}
 
314
 
 
315
Expression ValueTable::create_expression(InsertElementInst* I) {
 
316
  Expression e;
 
317
 
 
318
  e.varargs.push_back(lookup(I->getOperand(0)));
 
319
  e.varargs.push_back(lookup(I->getOperand(1)));
 
320
  e.varargs.push_back(lookup(I->getOperand(2)));
 
321
  e.type = I->getType();
 
322
  e.opcode = Expression::INSERT;
 
323
 
 
324
  return e;
 
325
}
 
326
 
 
327
Expression ValueTable::create_expression(SelectInst* I) {
 
328
  Expression e;
 
329
 
 
330
  e.varargs.push_back(lookup(I->getCondition()));
 
331
  e.varargs.push_back(lookup(I->getTrueValue()));
 
332
  e.varargs.push_back(lookup(I->getFalseValue()));
 
333
  e.type = I->getType();
 
334
  e.opcode = Expression::SELECT;
 
335
 
 
336
  return e;
 
337
}
 
338
 
 
339
Expression ValueTable::create_expression(GetElementPtrInst* G) {
 
340
  Expression e;
 
341
 
 
342
  e.varargs.push_back(lookup(G->getPointerOperand()));
 
343
  e.type = G->getType();
 
344
  e.opcode = Expression::GEP;
 
345
 
 
346
  for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
 
347
       I != E; ++I)
 
348
    e.varargs.push_back(lookup(*I));
 
349
 
 
350
  return e;
 
351
}
 
352
 
 
353
Expression ValueTable::create_expression(ExtractValueInst* E) {
 
354
  Expression e;
 
355
 
 
356
  e.varargs.push_back(lookup(E->getAggregateOperand()));
 
357
  for (ExtractValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
 
358
       II != IE; ++II)
 
359
    e.varargs.push_back(*II);
 
360
  e.type = E->getType();
 
361
  e.opcode = Expression::EXTRACTVALUE;
 
362
 
 
363
  return e;
 
364
}
 
365
 
 
366
Expression ValueTable::create_expression(InsertValueInst* E) {
 
367
  Expression e;
 
368
 
 
369
  e.varargs.push_back(lookup(E->getAggregateOperand()));
 
370
  e.varargs.push_back(lookup(E->getInsertedValueOperand()));
 
371
  for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
 
372
       II != IE; ++II)
 
373
    e.varargs.push_back(*II);
 
374
  e.type = E->getType();
 
375
  e.opcode = Expression::INSERTVALUE;
 
376
 
 
377
  return e;
 
378
}
 
379
 
 
380
//===----------------------------------------------------------------------===//
 
381
//                     ValueTable External Functions
 
382
//===----------------------------------------------------------------------===//
 
383
 
 
384
/// add - Insert a value into the table with a specified value number.
 
385
void ValueTable::add(Value *V, uint32_t num) {
 
386
  valueNumbering[V] = num;
 
387
}
 
388
 
 
389
/// computeNumber - Returns the value number for the specified value, assigning
 
390
/// it a new number if it did not have one before.
 
391
uint32_t ValueTable::computeNumber(Value *V) {
 
392
  if (uint32_t v = valueNumbering[V])
 
393
    return v;
 
394
  else if (uint32_t v= constantsNumbering[V])
 
395
    return v;
 
396
 
 
397
  if (!isa<Instruction>(V)) {
 
398
    constantsNumbering[V] = nextValueNumber;
 
399
    return nextValueNumber++;
 
400
  }
 
401
  
 
402
  Instruction* I = cast<Instruction>(V);
 
403
  Expression exp;
 
404
  switch (I->getOpcode()) {
 
405
    case Instruction::Add:
 
406
    case Instruction::FAdd:
 
407
    case Instruction::Sub:
 
408
    case Instruction::FSub:
 
409
    case Instruction::Mul:
 
410
    case Instruction::FMul:
 
411
    case Instruction::UDiv:
 
412
    case Instruction::SDiv:
 
413
    case Instruction::FDiv:
 
414
    case Instruction::URem:
 
415
    case Instruction::SRem:
 
416
    case Instruction::FRem:
 
417
    case Instruction::Shl:
 
418
    case Instruction::LShr:
 
419
    case Instruction::AShr:
 
420
    case Instruction::And:
 
421
    case Instruction::Or :
 
422
    case Instruction::Xor:
 
423
      exp = create_expression(cast<BinaryOperator>(I));
 
424
      break;
 
425
    case Instruction::ICmp:
 
426
    case Instruction::FCmp:
 
427
      exp = create_expression(cast<CmpInst>(I));
 
428
      break;
 
429
    case Instruction::Trunc:
 
430
    case Instruction::ZExt:
 
431
    case Instruction::SExt:
 
432
    case Instruction::FPToUI:
 
433
    case Instruction::FPToSI:
 
434
    case Instruction::UIToFP:
 
435
    case Instruction::SIToFP:
 
436
    case Instruction::FPTrunc:
 
437
    case Instruction::FPExt:
 
438
    case Instruction::PtrToInt:
 
439
    case Instruction::IntToPtr:
 
440
    case Instruction::BitCast:
 
441
      exp = create_expression(cast<CastInst>(I));
 
442
      break;
 
443
    case Instruction::Select:
 
444
      exp = create_expression(cast<SelectInst>(I));
 
445
      break;
 
446
    case Instruction::ExtractElement:
 
447
      exp = create_expression(cast<ExtractElementInst>(I));
 
448
      break;
 
449
    case Instruction::InsertElement:
 
450
      exp = create_expression(cast<InsertElementInst>(I));
 
451
      break;
 
452
    case Instruction::ShuffleVector:
 
453
      exp = create_expression(cast<ShuffleVectorInst>(I));
 
454
      break;
 
455
    case Instruction::ExtractValue:
 
456
      exp = create_expression(cast<ExtractValueInst>(I));
 
457
      break;
 
458
    case Instruction::InsertValue:
 
459
      exp = create_expression(cast<InsertValueInst>(I));
 
460
      break;      
 
461
    case Instruction::GetElementPtr:
 
462
      exp = create_expression(cast<GetElementPtrInst>(I));
 
463
      break;
 
464
    default:
 
465
      valueNumbering[V] = nextValueNumber;
 
466
      return nextValueNumber++;
 
467
  }
 
468
 
 
469
  uint32_t& e = expressionNumbering[exp];
 
470
  if (!e) e = nextValueNumber++;
 
471
  valueNumbering[V] = e;
 
472
  
 
473
  return e;
 
474
}
 
475
 
 
476
/// lookup - Returns the value number of the specified value. Returns 0 if
 
477
/// the value has not yet been numbered.
 
478
uint32_t ValueTable::lookup(Value *V) {
 
479
  if (!isa<Instruction>(V)) {
 
480
    if (!constantsNumbering.count(V))
 
481
      constantsNumbering[V] = nextValueNumber++;
 
482
    return constantsNumbering[V];
 
483
  }
 
484
  
 
485
  return valueNumbering[V];
 
486
}
 
487
 
 
488
/// clear - Remove all entries from the ValueTable
 
489
void ValueTable::clear() {
 
490
  valueNumbering.clear();
 
491
  expressionNumbering.clear();
 
492
  constantsNumbering.clear();
 
493
  nextValueNumber = 1;
 
494
}
 
495
 
 
496
void ValueTable::clearExpressions() {
 
497
  expressionNumbering.clear();
 
498
  constantsNumbering.clear();
 
499
  nextValueNumber = 1;
 
500
}
 
501
 
 
502
/// erase - Remove a value from the value numbering
 
503
void ValueTable::erase(Value *V) {
 
504
  valueNumbering.erase(V);
 
505
}
 
506
 
 
507
/// verifyRemoved - Verify that the value is removed from all internal data
 
508
/// structures.
 
509
void ValueTable::verifyRemoved(const Value *V) const {
 
510
  for (DenseMap<Value*, uint32_t>::const_iterator
 
511
         I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
 
512
    assert(I->first != V && "Inst still occurs in value numbering map!");
 
513
  }
 
514
}
 
515
 
 
516
//===----------------------------------------------------------------------===//
 
517
//                              SCCVN Pass
 
518
//===----------------------------------------------------------------------===//
 
519
 
 
520
namespace {
 
521
 
 
522
  struct ValueNumberScope {
 
523
    ValueNumberScope* parent;
 
524
    DenseMap<uint32_t, Value*> table;
 
525
    SparseBitVector<128> availIn;
 
526
    SparseBitVector<128> availOut;
 
527
    
 
528
    ValueNumberScope(ValueNumberScope* p) : parent(p) { }
 
529
  };
 
530
 
 
531
  class SCCVN : public FunctionPass {
 
532
    bool runOnFunction(Function &F);
 
533
  public:
 
534
    static char ID; // Pass identification, replacement for typeid
 
535
    SCCVN() : FunctionPass(&ID) { }
 
536
 
 
537
  private:
 
538
    ValueTable VT;
 
539
    DenseMap<BasicBlock*, ValueNumberScope*> BBMap;
 
540
    
 
541
    // This transformation requires dominator postdominator info
 
542
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
543
      AU.addRequired<DominatorTree>();
 
544
 
 
545
      AU.addPreserved<DominatorTree>();
 
546
      AU.setPreservesCFG();
 
547
    }
 
548
  };
 
549
 
 
550
  char SCCVN::ID = 0;
 
551
}
 
552
 
 
553
// createSCCVNPass - The public interface to this file...
 
554
FunctionPass *llvm::createSCCVNPass() { return new SCCVN(); }
 
555
 
 
556
static RegisterPass<SCCVN> X("sccvn",
 
557
                              "SCC Value Numbering");
 
558
 
 
559
static Value *lookupNumber(ValueNumberScope *Locals, uint32_t num) {
 
560
  while (Locals) {
 
561
    DenseMap<uint32_t, Value*>::iterator I = Locals->table.find(num);
 
562
    if (I != Locals->table.end())
 
563
      return I->second;
 
564
    Locals = Locals->parent;
 
565
  }
 
566
 
 
567
  return 0;
 
568
}
 
569
 
 
570
bool SCCVN::runOnFunction(Function& F) {
 
571
  // Implement the RPO version of the SCCVN algorithm.  Conceptually, 
 
572
  // we optimisitically assume that all instructions with the same opcode have
 
573
  // the same VN.  Then we deepen our comparison by one level, to all 
 
574
  // instructions whose operands have the same opcodes get the same VN.  We
 
575
  // iterate this process until the partitioning stops changing, at which
 
576
  // point we have computed a full numbering.
 
577
  ReversePostOrderTraversal<Function*> RPOT(&F);
 
578
  bool done = false;
 
579
  while (!done) {
 
580
    done = true;
 
581
    VT.clearExpressions();
 
582
    for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
 
583
         E = RPOT.end(); I != E; ++I) {
 
584
      BasicBlock* BB = *I;
 
585
      for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 
586
           BI != BE; ++BI) {
 
587
         uint32_t origVN = VT.lookup(BI);
 
588
         uint32_t newVN = VT.computeNumber(BI);
 
589
         if (origVN != newVN)
 
590
           done = false;
 
591
      }
 
592
    }
 
593
  }
 
594
  
 
595
  // Now, do a dominator walk, eliminating simple, dominated redundancies as we
 
596
  // go.  Also, build the ValueNumberScope structure that will be used for
 
597
  // computing full availability.
 
598
  DominatorTree& DT = getAnalysis<DominatorTree>();
 
599
  bool changed = false;
 
600
  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 
601
       DE = df_end(DT.getRootNode()); DI != DE; ++DI) {
 
602
    BasicBlock* BB = DI->getBlock();
 
603
    if (DI->getIDom())
 
604
      BBMap[BB] = new ValueNumberScope(BBMap[DI->getIDom()->getBlock()]);
 
605
    else
 
606
      BBMap[BB] = new ValueNumberScope(0);
 
607
    
 
608
    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 
609
      uint32_t num = VT.lookup(I);
 
610
      Value* repl = lookupNumber(BBMap[BB], num);
 
611
      
 
612
      if (repl) {
 
613
        if (isa<PHINode>(I))
 
614
          ++NumSCCVNPhi;
 
615
        else
 
616
          ++NumSCCVNInstr;
 
617
        I->replaceAllUsesWith(repl);
 
618
        Instruction* OldInst = I;
 
619
        ++I;
 
620
        BBMap[BB]->table[num] = repl;
 
621
        OldInst->eraseFromParent();
 
622
        changed = true;
 
623
      } else {
 
624
        BBMap[BB]->table[num] = I;
 
625
        BBMap[BB]->availOut.set(num);
 
626
  
 
627
        ++I;
 
628
      }
 
629
    }
 
630
  }
 
631
 
 
632
  // Perform a forward data-flow to compute availability at all points on
 
633
  // the CFG.
 
634
  do {
 
635
    changed = false;
 
636
    for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
 
637
         E = RPOT.end(); I != E; ++I) {
 
638
      BasicBlock* BB = *I;
 
639
      ValueNumberScope *VNS = BBMap[BB];
 
640
      
 
641
      SparseBitVector<128> preds;
 
642
      bool first = true;
 
643
      for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 
644
           PI != PE; ++PI) {
 
645
        if (first) {
 
646
          preds = BBMap[*PI]->availOut;
 
647
          first = false;
 
648
        } else {
 
649
          preds &= BBMap[*PI]->availOut;
 
650
        }
 
651
      }
 
652
      
 
653
      changed |= (VNS->availIn |= preds);
 
654
      changed |= (VNS->availOut |= preds);
 
655
    }
 
656
  } while (changed);
 
657
  
 
658
  // Use full availability information to perform non-dominated replacements.
 
659
  SSAUpdater SSU; 
 
660
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 
661
    if (!BBMap.count(FI)) continue;
 
662
    for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
 
663
         BI != BE; ) {
 
664
      uint32_t num = VT.lookup(BI);
 
665
      if (!BBMap[FI]->availIn.test(num)) {
 
666
        ++BI;
 
667
        continue;
 
668
      }
 
669
      
 
670
      SSU.Initialize(BI);
 
671
      
 
672
      SmallPtrSet<BasicBlock*, 8> visited;
 
673
      SmallVector<BasicBlock*, 8> stack;
 
674
      visited.insert(FI);
 
675
      for (pred_iterator PI = pred_begin(FI), PE = pred_end(FI);
 
676
           PI != PE; ++PI)
 
677
        if (!visited.count(*PI))
 
678
          stack.push_back(*PI);
 
679
      
 
680
      while (!stack.empty()) {
 
681
        BasicBlock* CurrBB = stack.pop_back_val();
 
682
        visited.insert(CurrBB);
 
683
        
 
684
        ValueNumberScope* S = BBMap[CurrBB];
 
685
        if (S->table.count(num)) {
 
686
          SSU.AddAvailableValue(CurrBB, S->table[num]);
 
687
        } else {
 
688
          for (pred_iterator PI = pred_begin(CurrBB), PE = pred_end(CurrBB);
 
689
               PI != PE; ++PI)
 
690
            if (!visited.count(*PI))
 
691
              stack.push_back(*PI);
 
692
        }
 
693
      }
 
694
      
 
695
      Value* repl = SSU.GetValueInMiddleOfBlock(FI);
 
696
      BI->replaceAllUsesWith(repl);
 
697
      Instruction* CurInst = BI;
 
698
      ++BI;
 
699
      BBMap[FI]->table[num] = repl;
 
700
      if (isa<PHINode>(CurInst))
 
701
        ++NumSCCVNPhi;
 
702
      else
 
703
        ++NumSCCVNInstr;
 
704
        
 
705
      CurInst->eraseFromParent();
 
706
    }
 
707
  }
 
708
 
 
709
  VT.clear();
 
710
  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
 
711
       I = BBMap.begin(), E = BBMap.end(); I != E; ++I)
 
712
    delete I->second;
 
713
  BBMap.clear();
 
714
  
 
715
  return changed;
 
716
}