← 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/CorrelatedValuePropagation.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/CorrelatedValuePropagation.cpp
1
 
//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
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 file implements the Correlated Value Propagation pass.
11
 
//
12
 
//===----------------------------------------------------------------------===//
13
 
 
14
 
#define DEBUG_TYPE "correlated-value-propagation"
15
 
#include "llvm/Transforms/Scalar.h"
16
 
#include "llvm/Function.h"
17
 
#include "llvm/Instructions.h"
18
 
#include "llvm/Pass.h"
19
 
#include "llvm/Analysis/LazyValueInfo.h"
20
 
#include "llvm/Support/CFG.h"
21
 
#include "llvm/Transforms/Utils/Local.h"
22
 
#include "llvm/ADT/Statistic.h"
23
 
using namespace llvm;
24
 
 
25
 
STATISTIC(NumPhis,      "Number of phis propagated");
26
 
STATISTIC(NumSelects,   "Number of selects propagated");
27
 
STATISTIC(NumMemAccess, "Number of memory access targets propagated");
28
 
STATISTIC(NumCmps,      "Number of comparisons propagated");
29
 
 
30
 
namespace {
31
 
  class CorrelatedValuePropagation : public FunctionPass {
32
 
    LazyValueInfo *LVI;
33
 
    
34
 
    bool processSelect(SelectInst *SI);
35
 
    bool processPHI(PHINode *P);
36
 
    bool processMemAccess(Instruction *I);
37
 
    bool processCmp(CmpInst *C);
38
 
    
39
 
  public:
40
 
    static char ID;
41
 
    CorrelatedValuePropagation(): FunctionPass(ID) { }
42
 
    
43
 
    bool runOnFunction(Function &F);
44
 
    
45
 
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
46
 
      AU.addRequired<LazyValueInfo>();
47
 
    }
48
 
  };
49
 
}
50
 
 
51
 
char CorrelatedValuePropagation::ID = 0;
52
 
INITIALIZE_PASS(CorrelatedValuePropagation, "correlated-propagation",
53
 
                "Value Propagation", false, false);
54
 
 
55
 
// Public interface to the Value Propagation pass
56
 
Pass *llvm::createCorrelatedValuePropagationPass() {
57
 
  return new CorrelatedValuePropagation();
58
 
}
59
 
 
60
 
bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
61
 
  if (S->getType()->isVectorTy()) return false;
62
 
  if (isa<Constant>(S->getOperand(0))) return false;
63
 
  
64
 
  Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
65
 
  if (!C) return false;
66
 
  
67
 
  ConstantInt *CI = dyn_cast<ConstantInt>(C);
68
 
  if (!CI) return false;
69
 
  
70
 
  S->replaceAllUsesWith(S->getOperand(CI->isOne() ? 1 : 2));
71
 
  S->eraseFromParent();
72
 
 
73
 
  ++NumSelects;
74
 
  
75
 
  return true;
76
 
}
77
 
 
78
 
bool CorrelatedValuePropagation::processPHI(PHINode *P) {
79
 
  bool Changed = false;
80
 
  
81
 
  BasicBlock *BB = P->getParent();
82
 
  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
83
 
    Value *Incoming = P->getIncomingValue(i);
84
 
    if (isa<Constant>(Incoming)) continue;
85
 
    
86
 
    Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
87
 
                                         P->getIncomingBlock(i),
88
 
                                         BB);
89
 
    if (!C) continue;
90
 
    
91
 
    P->setIncomingValue(i, C);
92
 
    Changed = true;
93
 
  }
94
 
  
95
 
  if (Value *ConstVal = P->hasConstantValue()) {
96
 
    P->replaceAllUsesWith(ConstVal);
97
 
    P->eraseFromParent();
98
 
    Changed = true;
99
 
  }
100
 
  
101
 
  ++NumPhis;
102
 
  
103
 
  return Changed;
104
 
}
105
 
 
106
 
bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
107
 
  Value *Pointer = 0;
108
 
  if (LoadInst *L = dyn_cast<LoadInst>(I))
109
 
    Pointer = L->getPointerOperand();
110
 
  else
111
 
    Pointer = cast<StoreInst>(I)->getPointerOperand();
112
 
  
113
 
  if (isa<Constant>(Pointer)) return false;
114
 
  
115
 
  Constant *C = LVI->getConstant(Pointer, I->getParent());
116
 
  if (!C) return false;
117
 
  
118
 
  ++NumMemAccess;
119
 
  I->replaceUsesOfWith(Pointer, C);
120
 
  return true;
121
 
}
122
 
 
123
 
/// processCmp - If the value of this comparison could be determined locally,
124
 
/// constant propagation would already have figured it out.  Instead, walk
125
 
/// the predecessors and statically evaluate the comparison based on information
126
 
/// available on that edge.  If a given static evaluation is true on ALL
127
 
/// incoming edges, then it's true universally and we can simplify the compare.
128
 
bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
129
 
  Value *Op0 = C->getOperand(0);
130
 
  if (isa<Instruction>(Op0) &&
131
 
      cast<Instruction>(Op0)->getParent() == C->getParent())
132
 
    return false;
133
 
  
134
 
  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
135
 
  if (!Op1) return false;
136
 
  
137
 
  pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
138
 
  if (PI == PE) return false;
139
 
  
140
 
  LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(), 
141
 
                                    C->getOperand(0), Op1, *PI, C->getParent());
142
 
  if (Result == LazyValueInfo::Unknown) return false;
143
 
 
144
 
  ++PI;
145
 
  while (PI != PE) {
146
 
    LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(), 
147
 
                                    C->getOperand(0), Op1, *PI, C->getParent());
148
 
    if (Res != Result) return false;
149
 
    ++PI;
150
 
  }
151
 
  
152
 
  ++NumCmps;
153
 
  
154
 
  if (Result == LazyValueInfo::True)
155
 
    C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
156
 
  else
157
 
    C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
158
 
  
159
 
  C->eraseFromParent();
160
 
 
161
 
  return true;
162
 
}
163
 
 
164
 
bool CorrelatedValuePropagation::runOnFunction(Function &F) {
165
 
  LVI = &getAnalysis<LazyValueInfo>();
166
 
  
167
 
  bool FnChanged = false;
168
 
  
169
 
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
170
 
    bool BBChanged = false;
171
 
    for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
172
 
      Instruction *II = BI++;
173
 
      switch (II->getOpcode()) {
174
 
      case Instruction::Select:
175
 
        BBChanged |= processSelect(cast<SelectInst>(II));
176
 
        break;
177
 
      case Instruction::PHI:
178
 
        BBChanged |= processPHI(cast<PHINode>(II));
179
 
        break;
180
 
      case Instruction::ICmp:
181
 
      case Instruction::FCmp:
182
 
        BBChanged |= processCmp(cast<CmpInst>(II));
183
 
        break;
184
 
      case Instruction::Load:
185
 
      case Instruction::Store:
186
 
        BBChanged |= processMemAccess(II);
187
 
        break;
188
 
      }
189
 
    }
190
 
    
191
 
    // Propagating correlated values might leave cruft around.
192
 
    // Try to clean it up before we continue.
193
 
    if (BBChanged)
194
 
      SimplifyInstructionsInBlock(FI);
195
 
    
196
 
    FnChanged |= BBChanged;
197
 
  }
198
 
  
199
 
  return FnChanged;
200
 
}