← Back to branch summary

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

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Analysis/PHITransAddr.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/Analysis/PHITransAddr.cpp
1
 
//===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===//
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 PHITransAddr class.
11
 
//
12
 
//===----------------------------------------------------------------------===//
13
 
 
14
 
#include "llvm/Analysis/PHITransAddr.h"
15
 
#include "llvm/Analysis/Dominators.h"
16
 
#include "llvm/Analysis/InstructionSimplify.h"
17
 
#include "llvm/Support/Debug.h"
18
 
#include "llvm/Support/raw_ostream.h"
19
 
using namespace llvm;
20
 
 
21
 
static bool CanPHITrans(Instruction *Inst) {
22
 
  if (isa<PHINode>(Inst) ||
23
 
      isa<BitCastInst>(Inst) ||
24
 
      isa<GetElementPtrInst>(Inst))
25
 
    return true;
26
 
  
27
 
  if (Inst->getOpcode() == Instruction::Add &&
28
 
      isa<ConstantInt>(Inst->getOperand(1)))
29
 
    return true;
30
 
  
31
 
  //   cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
32
 
  //   if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
33
 
  //     cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
34
 
  return false;
35
 
}
36
 
 
37
 
void PHITransAddr::dump() const {
38
 
  if (Addr == 0) {
39
 
    dbgs() << "PHITransAddr: null\n";
40
 
    return;
41
 
  }
42
 
  dbgs() << "PHITransAddr: " << *Addr << "\n";
43
 
  for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
44
 
    dbgs() << "  Input #" << i << " is " << *InstInputs[i] << "\n";
45
 
}
46
 
 
47
 
 
48
 
static bool VerifySubExpr(Value *Expr,
49
 
                          SmallVectorImpl<Instruction*> &InstInputs) {
50
 
  // If this is a non-instruction value, there is nothing to do.
51
 
  Instruction *I = dyn_cast<Instruction>(Expr);
52
 
  if (I == 0) return true;
53
 
  
54
 
  // If it's an instruction, it is either in Tmp or its operands recursively
55
 
  // are.
56
 
  SmallVectorImpl<Instruction*>::iterator Entry =
57
 
    std::find(InstInputs.begin(), InstInputs.end(), I);
58
 
  if (Entry != InstInputs.end()) {
59
 
    InstInputs.erase(Entry);
60
 
    return true;
61
 
  }
62
 
  
63
 
  // If it isn't in the InstInputs list it is a subexpr incorporated into the
64
 
  // address.  Sanity check that it is phi translatable.
65
 
  if (!CanPHITrans(I)) {
66
 
    errs() << "Non phi translatable instruction found in PHITransAddr, either "
67
 
              "something is missing from InstInputs or CanPHITrans is wrong:\n";
68
 
    errs() << *I << '\n';
69
 
    return false;
70
 
  }
71
 
  
72
 
  // Validate the operands of the instruction.
73
 
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
74
 
    if (!VerifySubExpr(I->getOperand(i), InstInputs))
75
 
      return false;
76
 
 
77
 
  return true;
78
 
}
79
 
 
80
 
/// Verify - Check internal consistency of this data structure.  If the
81
 
/// structure is valid, it returns true.  If invalid, it prints errors and
82
 
/// returns false.
83
 
bool PHITransAddr::Verify() const {
84
 
  if (Addr == 0) return true;
85
 
  
86
 
  SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end());  
87
 
  
88
 
  if (!VerifySubExpr(Addr, Tmp))
89
 
    return false;
90
 
  
91
 
  if (!Tmp.empty()) {
92
 
    errs() << "PHITransAddr inconsistent, contains extra instructions:\n";
93
 
    for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
94
 
      errs() << "  InstInput #" << i << " is " << *InstInputs[i] << "\n";
95
 
    return false;
96
 
  }
97
 
  
98
 
  // a-ok.
99
 
  return true;
100
 
}
101
 
 
102
 
 
103
 
/// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
104
 
/// if we have some hope of doing it.  This should be used as a filter to
105
 
/// avoid calling PHITranslateValue in hopeless situations.
106
 
bool PHITransAddr::IsPotentiallyPHITranslatable() const {
107
 
  // If the input value is not an instruction, or if it is not defined in CurBB,
108
 
  // then we don't need to phi translate it.
109
 
  Instruction *Inst = dyn_cast<Instruction>(Addr);
110
 
  return Inst == 0 || CanPHITrans(Inst);
111
 
}
112
 
 
113
 
 
114
 
static void RemoveInstInputs(Value *V, 
115
 
                             SmallVectorImpl<Instruction*> &InstInputs) {
116
 
  Instruction *I = dyn_cast<Instruction>(V);
117
 
  if (I == 0) return;
118
 
  
119
 
  // If the instruction is in the InstInputs list, remove it.
120
 
  SmallVectorImpl<Instruction*>::iterator Entry =
121
 
    std::find(InstInputs.begin(), InstInputs.end(), I);
122
 
  if (Entry != InstInputs.end()) {
123
 
    InstInputs.erase(Entry);
124
 
    return;
125
 
  }
126
 
  
127
 
  assert(!isa<PHINode>(I) && "Error, removing something that isn't an input");
128
 
  
129
 
  // Otherwise, it must have instruction inputs itself.  Zap them recursively.
130
 
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
131
 
    if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
132
 
      RemoveInstInputs(Op, InstInputs);
133
 
  }
134
 
}
135
 
 
136
 
Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
137
 
                                         BasicBlock *PredBB,
138
 
                                         const DominatorTree *DT) {
139
 
  // If this is a non-instruction value, it can't require PHI translation.
140
 
  Instruction *Inst = dyn_cast<Instruction>(V);
141
 
  if (Inst == 0) return V;
142
 
  
143
 
  // Determine whether 'Inst' is an input to our PHI translatable expression.
144
 
  bool isInput = std::count(InstInputs.begin(), InstInputs.end(), Inst);
145
 
 
146
 
  // Handle inputs instructions if needed.
147
 
  if (isInput) {
148
 
    if (Inst->getParent() != CurBB) {
149
 
      // If it is an input defined in a different block, then it remains an
150
 
      // input.
151
 
      return Inst;
152
 
    }
153
 
 
154
 
    // If 'Inst' is defined in this block and is an input that needs to be phi
155
 
    // translated, we need to incorporate the value into the expression or fail.
156
 
 
157
 
    // In either case, the instruction itself isn't an input any longer.
158
 
    InstInputs.erase(std::find(InstInputs.begin(), InstInputs.end(), Inst));
159
 
    
160
 
    // If this is a PHI, go ahead and translate it.
161
 
    if (PHINode *PN = dyn_cast<PHINode>(Inst))
162
 
      return AddAsInput(PN->getIncomingValueForBlock(PredBB));
163
 
    
164
 
    // If this is a non-phi value, and it is analyzable, we can incorporate it
165
 
    // into the expression by making all instruction operands be inputs.
166
 
    if (!CanPHITrans(Inst))
167
 
      return 0;
168
 
   
169
 
    // All instruction operands are now inputs (and of course, they may also be
170
 
    // defined in this block, so they may need to be phi translated themselves.
171
 
    for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
172
 
      if (Instruction *Op = dyn_cast<Instruction>(Inst->getOperand(i)))
173
 
        InstInputs.push_back(Op);
174
 
  }
175
 
 
176
 
  // Ok, it must be an intermediate result (either because it started that way
177
 
  // or because we just incorporated it into the expression).  See if its
178
 
  // operands need to be phi translated, and if so, reconstruct it.
179
 
  
180
 
  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
181
 
    Value *PHIIn = PHITranslateSubExpr(BC->getOperand(0), CurBB, PredBB, DT);
182
 
    if (PHIIn == 0) return 0;
183
 
    if (PHIIn == BC->getOperand(0))
184
 
      return BC;
185
 
    
186
 
    // Find an available version of this cast.
187
 
    
188
 
    // Constants are trivial to find.
189
 
    if (Constant *C = dyn_cast<Constant>(PHIIn))
190
 
      return AddAsInput(ConstantExpr::getBitCast(C, BC->getType()));
191
 
    
192
 
    // Otherwise we have to see if a bitcasted version of the incoming pointer
193
 
    // is available.  If so, we can use it, otherwise we have to fail.
194
 
    for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end();
195
 
         UI != E; ++UI) {
196
 
      if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI))
197
 
        if (BCI->getType() == BC->getType() &&
198
 
            (!DT || DT->dominates(BCI->getParent(), PredBB)))
199
 
          return BCI;
200
 
    }
201
 
    return 0;
202
 
  }
203
 
  
204
 
  // Handle getelementptr with at least one PHI translatable operand.
205
 
  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
206
 
    SmallVector<Value*, 8> GEPOps;
207
 
    bool AnyChanged = false;
208
 
    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
209
 
      Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB, DT);
210
 
      if (GEPOp == 0) return 0;
211
 
      
212
 
      AnyChanged |= GEPOp != GEP->getOperand(i);
213
 
      GEPOps.push_back(GEPOp);
214
 
    }
215
 
    
216
 
    if (!AnyChanged)
217
 
      return GEP;
218
 
    
219
 
    // Simplify the GEP to handle 'gep x, 0' -> x etc.
220
 
    if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD)) {
221
 
      for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
222
 
        RemoveInstInputs(GEPOps[i], InstInputs);
223
 
      
224
 
      return AddAsInput(V);
225
 
    }
226
 
    
227
 
    // Scan to see if we have this GEP available.
228
 
    Value *APHIOp = GEPOps[0];
229
 
    for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end();
230
 
         UI != E; ++UI) {
231
 
      if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
232
 
        if (GEPI->getType() == GEP->getType() &&
233
 
            GEPI->getNumOperands() == GEPOps.size() &&
234
 
            GEPI->getParent()->getParent() == CurBB->getParent() &&
235
 
            (!DT || DT->dominates(GEPI->getParent(), PredBB))) {
236
 
          bool Mismatch = false;
237
 
          for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
238
 
            if (GEPI->getOperand(i) != GEPOps[i]) {
239
 
              Mismatch = true;
240
 
              break;
241
 
            }
242
 
          if (!Mismatch)
243
 
            return GEPI;
244
 
        }
245
 
    }
246
 
    return 0;
247
 
  }
248
 
  
249
 
  // Handle add with a constant RHS.
250
 
  if (Inst->getOpcode() == Instruction::Add &&
251
 
      isa<ConstantInt>(Inst->getOperand(1))) {
252
 
    // PHI translate the LHS.
253
 
    Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
254
 
    bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
255
 
    bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
256
 
    
257
 
    Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);
258
 
    if (LHS == 0) return 0;
259
 
    
260
 
    // If the PHI translated LHS is an add of a constant, fold the immediates.
261
 
    if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
262
 
      if (BOp->getOpcode() == Instruction::Add)
263
 
        if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
264
 
          LHS = BOp->getOperand(0);
265
 
          RHS = ConstantExpr::getAdd(RHS, CI);
266
 
          isNSW = isNUW = false;
267
 
          
268
 
          // If the old 'LHS' was an input, add the new 'LHS' as an input.
269
 
          if (std::count(InstInputs.begin(), InstInputs.end(), BOp)) {
270
 
            RemoveInstInputs(BOp, InstInputs);
271
 
            AddAsInput(LHS);
272
 
          }
273
 
        }
274
 
    
275
 
    // See if the add simplifies away.
276
 
    if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD)) {
277
 
      // If we simplified the operands, the LHS is no longer an input, but Res
278
 
      // is.
279
 
      RemoveInstInputs(LHS, InstInputs);
280
 
      return AddAsInput(Res);
281
 
    }
282
 
 
283
 
    // If we didn't modify the add, just return it.
284
 
    if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))
285
 
      return Inst;
286
 
    
287
 
    // Otherwise, see if we have this add available somewhere.
288
 
    for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end();
289
 
         UI != E; ++UI) {
290
 
      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*UI))
291
 
        if (BO->getOpcode() == Instruction::Add &&
292
 
            BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
293
 
            BO->getParent()->getParent() == CurBB->getParent() &&
294
 
            (!DT || DT->dominates(BO->getParent(), PredBB)))
295
 
          return BO;
296
 
    }
297
 
    
298
 
    return 0;
299
 
  }
300
 
  
301
 
  // Otherwise, we failed.
302
 
  return 0;
303
 
}
304
 
 
305
 
 
306
 
/// PHITranslateValue - PHI translate the current address up the CFG from
307
 
/// CurBB to Pred, updating our state to reflect any needed changes.  If the
308
 
/// dominator tree DT is non-null, the translated value must dominate
309
 
/// PredBB.  This returns true on failure and sets Addr to null.
310
 
bool PHITransAddr::PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB,
311
 
                                     const DominatorTree *DT) {
312
 
  assert(Verify() && "Invalid PHITransAddr!");
313
 
  Addr = PHITranslateSubExpr(Addr, CurBB, PredBB, DT);
314
 
  assert(Verify() && "Invalid PHITransAddr!");
315
 
 
316
 
  if (DT) {
317
 
    // Make sure the value is live in the predecessor.
318
 
    if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
319
 
      if (!DT->dominates(Inst->getParent(), PredBB))
320
 
        Addr = 0;
321
 
  }
322
 
 
323
 
  return Addr == 0;
324
 
}
325
 
 
326
 
/// PHITranslateWithInsertion - PHI translate this value into the specified
327
 
/// predecessor block, inserting a computation of the value if it is
328
 
/// unavailable.
329
 
///
330
 
/// All newly created instructions are added to the NewInsts list.  This
331
 
/// returns null on failure.
332
 
///
333
 
Value *PHITransAddr::
334
 
PHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
335
 
                          const DominatorTree &DT,
336
 
                          SmallVectorImpl<Instruction*> &NewInsts) {
337
 
  unsigned NISize = NewInsts.size();
338
 
  
339
 
  // Attempt to PHI translate with insertion.
340
 
  Addr = InsertPHITranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
341
 
  
342
 
  // If successful, return the new value.
343
 
  if (Addr) return Addr;
344
 
  
345
 
  // If not, destroy any intermediate instructions inserted.
346
 
  while (NewInsts.size() != NISize)
347
 
    NewInsts.pop_back_val()->eraseFromParent();
348
 
  return 0;
349
 
}
350
 
 
351
 
 
352
 
/// InsertPHITranslatedPointer - Insert a computation of the PHI translated
353
 
/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
354
 
/// block.  All newly created instructions are added to the NewInsts list.
355
 
/// This returns null on failure.
356
 
///
357
 
Value *PHITransAddr::
358
 
InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB,
359
 
                           BasicBlock *PredBB, const DominatorTree &DT,
360
 
                           SmallVectorImpl<Instruction*> &NewInsts) {
361
 
  // See if we have a version of this value already available and dominating
362
 
  // PredBB.  If so, there is no need to insert a new instance of it.
363
 
  PHITransAddr Tmp(InVal, TD);
364
 
  if (!Tmp.PHITranslateValue(CurBB, PredBB, &DT))
365
 
    return Tmp.getAddr();
366
 
 
367
 
  // If we don't have an available version of this value, it must be an
368
 
  // instruction.
369
 
  Instruction *Inst = cast<Instruction>(InVal);
370
 
  
371
 
  // Handle bitcast of PHI translatable value.
372
 
  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
373
 
    Value *OpVal = InsertPHITranslatedSubExpr(BC->getOperand(0),
374
 
                                              CurBB, PredBB, DT, NewInsts);
375
 
    if (OpVal == 0) return 0;
376
 
    
377
 
    // Otherwise insert a bitcast at the end of PredBB.
378
 
    BitCastInst *New = new BitCastInst(OpVal, InVal->getType(),
379
 
                                       InVal->getName()+".phi.trans.insert",
380
 
                                       PredBB->getTerminator());
381
 
    NewInsts.push_back(New);
382
 
    return New;
383
 
  }
384
 
  
385
 
  // Handle getelementptr with at least one PHI operand.
386
 
  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
387
 
    SmallVector<Value*, 8> GEPOps;
388
 
    BasicBlock *CurBB = GEP->getParent();
389
 
    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
390
 
      Value *OpVal = InsertPHITranslatedSubExpr(GEP->getOperand(i),
391
 
                                                CurBB, PredBB, DT, NewInsts);
392
 
      if (OpVal == 0) return 0;
393
 
      GEPOps.push_back(OpVal);
394
 
    }
395
 
    
396
 
    GetElementPtrInst *Result = 
397
 
    GetElementPtrInst::Create(GEPOps[0], GEPOps.begin()+1, GEPOps.end(),
398
 
                              InVal->getName()+".phi.trans.insert",
399
 
                              PredBB->getTerminator());
400
 
    Result->setIsInBounds(GEP->isInBounds());
401
 
    NewInsts.push_back(Result);
402
 
    return Result;
403
 
  }
404
 
  
405
 
#if 0
406
 
  // FIXME: This code works, but it is unclear that we actually want to insert
407
 
  // a big chain of computation in order to make a value available in a block.
408
 
  // This needs to be evaluated carefully to consider its cost trade offs.
409
 
  
410
 
  // Handle add with a constant RHS.
411
 
  if (Inst->getOpcode() == Instruction::Add &&
412
 
      isa<ConstantInt>(Inst->getOperand(1))) {
413
 
    // PHI translate the LHS.
414
 
    Value *OpVal = InsertPHITranslatedSubExpr(Inst->getOperand(0),
415
 
                                              CurBB, PredBB, DT, NewInsts);
416
 
    if (OpVal == 0) return 0;
417
 
    
418
 
    BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1),
419
 
                                           InVal->getName()+".phi.trans.insert",
420
 
                                                    PredBB->getTerminator());
421
 
    Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
422
 
    Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
423
 
    NewInsts.push_back(Res);
424
 
    return Res;
425
 
  }
426
 
#endif
427
 
  
428
 
  return 0;
429
 
}