← 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/InstructionSimplify.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/InstructionSimplify.cpp
1
 
//===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
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 routines for folding instructions into simpler forms
11
 
// that do not require creating new instructions.  For example, this does
12
 
// constant folding, and can handle identities like (X&0)->0.
13
 
//
14
 
//===----------------------------------------------------------------------===//
15
 
 
16
 
#include "llvm/Analysis/InstructionSimplify.h"
17
 
#include "llvm/Analysis/ConstantFolding.h"
18
 
#include "llvm/Support/ValueHandle.h"
19
 
#include "llvm/Instructions.h"
20
 
#include "llvm/Support/PatternMatch.h"
21
 
using namespace llvm;
22
 
using namespace llvm::PatternMatch;
23
 
 
24
 
/// SimplifyAddInst - Given operands for an Add, see if we can
25
 
/// fold the result.  If not, this returns null.
26
 
Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
27
 
                             const TargetData *TD) {
28
 
  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
29
 
    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
30
 
      Constant *Ops[] = { CLHS, CRHS };
31
 
      return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
32
 
                                      Ops, 2, TD);
33
 
    }
34
 
    
35
 
    // Canonicalize the constant to the RHS.
36
 
    std::swap(Op0, Op1);
37
 
  }
38
 
  
39
 
  if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
40
 
    // X + undef -> undef
41
 
    if (isa<UndefValue>(Op1C))
42
 
      return Op1C;
43
 
    
44
 
    // X + 0 --> X
45
 
    if (Op1C->isNullValue())
46
 
      return Op0;
47
 
  }
48
 
  
49
 
  // FIXME: Could pull several more out of instcombine.
50
 
  return 0;
51
 
}
52
 
 
53
 
/// SimplifyAndInst - Given operands for an And, see if we can
54
 
/// fold the result.  If not, this returns null.
55
 
Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) {
56
 
  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
57
 
    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
58
 
      Constant *Ops[] = { CLHS, CRHS };
59
 
      return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
60
 
                                      Ops, 2, TD);
61
 
    }
62
 
  
63
 
    // Canonicalize the constant to the RHS.
64
 
    std::swap(Op0, Op1);
65
 
  }
66
 
  
67
 
  // X & undef -> 0
68
 
  if (isa<UndefValue>(Op1))
69
 
    return Constant::getNullValue(Op0->getType());
70
 
  
71
 
  // X & X = X
72
 
  if (Op0 == Op1)
73
 
    return Op0;
74
 
  
75
 
  // X & <0,0> = <0,0>
76
 
  if (isa<ConstantAggregateZero>(Op1))
77
 
    return Op1;
78
 
  
79
 
  // X & <-1,-1> = X
80
 
  if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
81
 
    if (CP->isAllOnesValue())
82
 
      return Op0;
83
 
  
84
 
  if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
85
 
    // X & 0 = 0
86
 
    if (Op1CI->isZero())
87
 
      return Op1CI;
88
 
    // X & -1 = X
89
 
    if (Op1CI->isAllOnesValue())
90
 
      return Op0;
91
 
  }
92
 
  
93
 
  // A & ~A  =  ~A & A  =  0
94
 
  Value *A, *B;
95
 
  if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
96
 
      (match(Op1, m_Not(m_Value(A))) && A == Op0))
97
 
    return Constant::getNullValue(Op0->getType());
98
 
  
99
 
  // (A | ?) & A = A
100
 
  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
101
 
      (A == Op1 || B == Op1))
102
 
    return Op1;
103
 
  
104
 
  // A & (A | ?) = A
105
 
  if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
106
 
      (A == Op0 || B == Op0))
107
 
    return Op0;
108
 
  
109
 
  return 0;
110
 
}
111
 
 
112
 
/// SimplifyOrInst - Given operands for an Or, see if we can
113
 
/// fold the result.  If not, this returns null.
114
 
Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
115
 
  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
116
 
    if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
117
 
      Constant *Ops[] = { CLHS, CRHS };
118
 
      return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
119
 
                                      Ops, 2, TD);
120
 
    }
121
 
    
122
 
    // Canonicalize the constant to the RHS.
123
 
    std::swap(Op0, Op1);
124
 
  }
125
 
  
126
 
  // X | undef -> -1
127
 
  if (isa<UndefValue>(Op1))
128
 
    return Constant::getAllOnesValue(Op0->getType());
129
 
  
130
 
  // X | X = X
131
 
  if (Op0 == Op1)
132
 
    return Op0;
133
 
 
134
 
  // X | <0,0> = X
135
 
  if (isa<ConstantAggregateZero>(Op1))
136
 
    return Op0;
137
 
  
138
 
  // X | <-1,-1> = <-1,-1>
139
 
  if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
140
 
    if (CP->isAllOnesValue())            
141
 
      return Op1;
142
 
  
143
 
  if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
144
 
    // X | 0 = X
145
 
    if (Op1CI->isZero())
146
 
      return Op0;
147
 
    // X | -1 = -1
148
 
    if (Op1CI->isAllOnesValue())
149
 
      return Op1CI;
150
 
  }
151
 
  
152
 
  // A | ~A  =  ~A | A  =  -1
153
 
  Value *A, *B;
154
 
  if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
155
 
      (match(Op1, m_Not(m_Value(A))) && A == Op0))
156
 
    return Constant::getAllOnesValue(Op0->getType());
157
 
  
158
 
  // (A & ?) | A = A
159
 
  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
160
 
      (A == Op1 || B == Op1))
161
 
    return Op1;
162
 
  
163
 
  // A | (A & ?) = A
164
 
  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
165
 
      (A == Op0 || B == Op0))
166
 
    return Op0;
167
 
  
168
 
  return 0;
169
 
}
170
 
 
171
 
 
172
 
static const Type *GetCompareTy(Value *Op) {
173
 
  return CmpInst::makeCmpResultType(Op->getType());
174
 
}
175
 
 
176
 
 
177
 
/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
178
 
/// fold the result.  If not, this returns null.
179
 
Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
180
 
                              const TargetData *TD) {
181
 
  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
182
 
  assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
183
 
  
184
 
  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
185
 
    if (Constant *CRHS = dyn_cast<Constant>(RHS))
186
 
      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
187
 
 
188
 
    // If we have a constant, make sure it is on the RHS.
189
 
    std::swap(LHS, RHS);
190
 
    Pred = CmpInst::getSwappedPredicate(Pred);
191
 
  }
192
 
  
193
 
  // ITy - This is the return type of the compare we're considering.
194
 
  const Type *ITy = GetCompareTy(LHS);
195
 
  
196
 
  // icmp X, X -> true/false
197
 
  // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
198
 
  // because X could be 0.
199
 
  if (LHS == RHS || isa<UndefValue>(RHS))
200
 
    return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
201
 
  
202
 
  // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
203
 
  // addresses never equal each other!  We already know that Op0 != Op1.
204
 
  if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 
205
 
       isa<ConstantPointerNull>(LHS)) &&
206
 
      (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 
207
 
       isa<ConstantPointerNull>(RHS)))
208
 
    return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
209
 
  
210
 
  // See if we are doing a comparison with a constant.
211
 
  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
212
 
    // If we have an icmp le or icmp ge instruction, turn it into the
213
 
    // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
214
 
    // them being folded in the code below.
215
 
    switch (Pred) {
216
 
    default: break;
217
 
    case ICmpInst::ICMP_ULE:
218
 
      if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
219
 
        return ConstantInt::getTrue(CI->getContext());
220
 
      break;
221
 
    case ICmpInst::ICMP_SLE:
222
 
      if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
223
 
        return ConstantInt::getTrue(CI->getContext());
224
 
      break;
225
 
    case ICmpInst::ICMP_UGE:
226
 
      if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
227
 
        return ConstantInt::getTrue(CI->getContext());
228
 
      break;
229
 
    case ICmpInst::ICMP_SGE:
230
 
      if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
231
 
        return ConstantInt::getTrue(CI->getContext());
232
 
      break;
233
 
    }
234
 
  }
235
 
  
236
 
  
237
 
  return 0;
238
 
}
239
 
 
240
 
/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
241
 
/// fold the result.  If not, this returns null.
242
 
Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
243
 
                              const TargetData *TD) {
244
 
  CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
245
 
  assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
246
 
 
247
 
  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
248
 
    if (Constant *CRHS = dyn_cast<Constant>(RHS))
249
 
      return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
250
 
   
251
 
    // If we have a constant, make sure it is on the RHS.
252
 
    std::swap(LHS, RHS);
253
 
    Pred = CmpInst::getSwappedPredicate(Pred);
254
 
  }
255
 
  
256
 
  // Fold trivial predicates.
257
 
  if (Pred == FCmpInst::FCMP_FALSE)
258
 
    return ConstantInt::get(GetCompareTy(LHS), 0);
259
 
  if (Pred == FCmpInst::FCMP_TRUE)
260
 
    return ConstantInt::get(GetCompareTy(LHS), 1);
261
 
 
262
 
  if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
263
 
    return UndefValue::get(GetCompareTy(LHS));
264
 
 
265
 
  // fcmp x,x -> true/false.  Not all compares are foldable.
266
 
  if (LHS == RHS) {
267
 
    if (CmpInst::isTrueWhenEqual(Pred))
268
 
      return ConstantInt::get(GetCompareTy(LHS), 1);
269
 
    if (CmpInst::isFalseWhenEqual(Pred))
270
 
      return ConstantInt::get(GetCompareTy(LHS), 0);
271
 
  }
272
 
  
273
 
  // Handle fcmp with constant RHS
274
 
  if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
275
 
    // If the constant is a nan, see if we can fold the comparison based on it.
276
 
    if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
277
 
      if (CFP->getValueAPF().isNaN()) {
278
 
        if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
279
 
          return ConstantInt::getFalse(CFP->getContext());
280
 
        assert(FCmpInst::isUnordered(Pred) &&
281
 
               "Comparison must be either ordered or unordered!");
282
 
        // True if unordered.
283
 
        return ConstantInt::getTrue(CFP->getContext());
284
 
      }
285
 
      // Check whether the constant is an infinity.
286
 
      if (CFP->getValueAPF().isInfinity()) {
287
 
        if (CFP->getValueAPF().isNegative()) {
288
 
          switch (Pred) {
289
 
          case FCmpInst::FCMP_OLT:
290
 
            // No value is ordered and less than negative infinity.
291
 
            return ConstantInt::getFalse(CFP->getContext());
292
 
          case FCmpInst::FCMP_UGE:
293
 
            // All values are unordered with or at least negative infinity.
294
 
            return ConstantInt::getTrue(CFP->getContext());
295
 
          default:
296
 
            break;
297
 
          }
298
 
        } else {
299
 
          switch (Pred) {
300
 
          case FCmpInst::FCMP_OGT:
301
 
            // No value is ordered and greater than infinity.
302
 
            return ConstantInt::getFalse(CFP->getContext());
303
 
          case FCmpInst::FCMP_ULE:
304
 
            // All values are unordered with and at most infinity.
305
 
            return ConstantInt::getTrue(CFP->getContext());
306
 
          default:
307
 
            break;
308
 
          }
309
 
        }
310
 
      }
311
 
    }
312
 
  }
313
 
  
314
 
  return 0;
315
 
}
316
 
 
317
 
/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
318
 
/// the result.  If not, this returns null.
319
 
Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
320
 
                                const TargetData *TD) {
321
 
  // select true, X, Y  -> X
322
 
  // select false, X, Y -> Y
323
 
  if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
324
 
    return CB->getZExtValue() ? TrueVal : FalseVal;
325
 
  
326
 
  // select C, X, X -> X
327
 
  if (TrueVal == FalseVal)
328
 
    return TrueVal;
329
 
  
330
 
  if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
331
 
    return FalseVal;
332
 
  if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
333
 
    return TrueVal;
334
 
  if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
335
 
    if (isa<Constant>(TrueVal))
336
 
      return TrueVal;
337
 
    return FalseVal;
338
 
  }
339
 
  
340
 
  
341
 
  
342
 
  return 0;
343
 
}
344
 
 
345
 
 
346
 
/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
347
 
/// fold the result.  If not, this returns null.
348
 
Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
349
 
                             const TargetData *TD) {
350
 
  // getelementptr P -> P.
351
 
  if (NumOps == 1)
352
 
    return Ops[0];
353
 
 
354
 
  // TODO.
355
 
  //if (isa<UndefValue>(Ops[0]))
356
 
  //  return UndefValue::get(GEP.getType());
357
 
 
358
 
  // getelementptr P, 0 -> P.
359
 
  if (NumOps == 2)
360
 
    if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
361
 
      if (C->isZero())
362
 
        return Ops[0];
363
 
  
364
 
  // Check to see if this is constant foldable.
365
 
  for (unsigned i = 0; i != NumOps; ++i)
366
 
    if (!isa<Constant>(Ops[i]))
367
 
      return 0;
368
 
  
369
 
  return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
370
 
                                        (Constant *const*)Ops+1, NumOps-1);
371
 
}
372
 
 
373
 
 
374
 
//=== Helper functions for higher up the class hierarchy.
375
 
 
376
 
/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
377
 
/// fold the result.  If not, this returns null.
378
 
Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 
379
 
                           const TargetData *TD) {
380
 
  switch (Opcode) {
381
 
  case Instruction::And: return SimplifyAndInst(LHS, RHS, TD);
382
 
  case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD);
383
 
  default:
384
 
    if (Constant *CLHS = dyn_cast<Constant>(LHS))
385
 
      if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
386
 
        Constant *COps[] = {CLHS, CRHS};
387
 
        return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
388
 
      }
389
 
    return 0;
390
 
  }
391
 
}
392
 
 
393
 
/// SimplifyCmpInst - Given operands for a CmpInst, see if we can
394
 
/// fold the result.
395
 
Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
396
 
                             const TargetData *TD) {
397
 
  if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
398
 
    return SimplifyICmpInst(Predicate, LHS, RHS, TD);
399
 
  return SimplifyFCmpInst(Predicate, LHS, RHS, TD);
400
 
}
401
 
 
402
 
 
403
 
/// SimplifyInstruction - See if we can compute a simplified version of this
404
 
/// instruction.  If not, this returns null.
405
 
Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
406
 
  switch (I->getOpcode()) {
407
 
  default:
408
 
    return ConstantFoldInstruction(I, TD);
409
 
  case Instruction::Add:
410
 
    return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
411
 
                           cast<BinaryOperator>(I)->hasNoSignedWrap(),
412
 
                           cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
413
 
  case Instruction::And:
414
 
    return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
415
 
  case Instruction::Or:
416
 
    return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
417
 
  case Instruction::ICmp:
418
 
    return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
419
 
                            I->getOperand(0), I->getOperand(1), TD);
420
 
  case Instruction::FCmp:
421
 
    return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
422
 
                            I->getOperand(0), I->getOperand(1), TD);
423
 
  case Instruction::Select:
424
 
    return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
425
 
                              I->getOperand(2), TD);
426
 
  case Instruction::GetElementPtr: {
427
 
    SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
428
 
    return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
429
 
  }
430
 
  }
431
 
}
432
 
 
433
 
/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
434
 
/// delete the From instruction.  In addition to a basic RAUW, this does a
435
 
/// recursive simplification of the newly formed instructions.  This catches
436
 
/// things where one simplification exposes other opportunities.  This only
437
 
/// simplifies and deletes scalar operations, it does not change the CFG.
438
 
///
439
 
void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
440
 
                                     const TargetData *TD) {
441
 
  assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
442
 
  
443
 
  // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
444
 
  // we can know if it gets deleted out from under us or replaced in a
445
 
  // recursive simplification.
446
 
  WeakVH FromHandle(From);
447
 
  WeakVH ToHandle(To);
448
 
  
449
 
  while (!From->use_empty()) {
450
 
    // Update the instruction to use the new value.
451
 
    Use &TheUse = From->use_begin().getUse();
452
 
    Instruction *User = cast<Instruction>(TheUse.getUser());
453
 
    TheUse = To;
454
 
 
455
 
    // Check to see if the instruction can be folded due to the operand
456
 
    // replacement.  For example changing (or X, Y) into (or X, -1) can replace
457
 
    // the 'or' with -1.
458
 
    Value *SimplifiedVal;
459
 
    {
460
 
      // Sanity check to make sure 'User' doesn't dangle across
461
 
      // SimplifyInstruction.
462
 
      AssertingVH<> UserHandle(User);
463
 
    
464
 
      SimplifiedVal = SimplifyInstruction(User, TD);
465
 
      if (SimplifiedVal == 0) continue;
466
 
    }
467
 
    
468
 
    // Recursively simplify this user to the new value.
469
 
    ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD);
470
 
    From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
471
 
    To = ToHandle;
472
 
      
473
 
    assert(ToHandle && "To value deleted by recursive simplification?");
474
 
      
475
 
    // If the recursive simplification ended up revisiting and deleting
476
 
    // 'From' then we're done.
477
 
    if (From == 0)
478
 
      return;
479
 
  }
480
 
  
481
 
  // If 'From' has value handles referring to it, do a real RAUW to update them.
482
 
  From->replaceAllUsesWith(To);
483
 
  
484
 
  From->eraseFromParent();
485
 
}
486