← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

  • 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/include/llvm/Analysis/ScalarEvolutionExpressions.h
 
1
//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
 
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 defines the classes used to represent and build scalar expressions.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
 
15
#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
 
16
 
 
17
#include "llvm/Analysis/ScalarEvolution.h"
 
18
#include "llvm/Support/ErrorHandling.h"
 
19
 
 
20
namespace llvm {
 
21
  class ConstantInt;
 
22
  class ConstantRange;
 
23
  class DominatorTree;
 
24
 
 
25
  enum SCEVTypes {
 
26
    // These should be ordered in terms of increasing complexity to make the
 
27
    // folders simpler.
 
28
    scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
 
29
    scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
 
30
    scUnknown, scCouldNotCompute
 
31
  };
 
32
 
 
33
  //===--------------------------------------------------------------------===//
 
34
  /// SCEVConstant - This class represents a constant integer value.
 
35
  ///
 
36
  class SCEVConstant : public SCEV {
 
37
    friend class ScalarEvolution;
 
38
 
 
39
    ConstantInt *V;
 
40
    SCEVConstant(const FoldingSetNodeID &ID, ConstantInt *v) :
 
41
      SCEV(ID, scConstant), V(v) {}
 
42
  public:
 
43
    ConstantInt *getValue() const { return V; }
 
44
 
 
45
    virtual bool isLoopInvariant(const Loop *L) const {
 
46
      return true;
 
47
    }
 
48
 
 
49
    virtual bool hasComputableLoopEvolution(const Loop *L) const {
 
50
      return false;  // Not loop variant
 
51
    }
 
52
 
 
53
    virtual const Type *getType() const;
 
54
 
 
55
    virtual bool hasOperand(const SCEV *) const {
 
56
      return false;
 
57
    }
 
58
 
 
59
    bool dominates(BasicBlock *BB, DominatorTree *DT) const {
 
60
      return true;
 
61
    }
 
62
 
 
63
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 
64
      return true;
 
65
    }
 
66
 
 
67
    virtual void print(raw_ostream &OS) const;
 
68
 
 
69
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
70
    static inline bool classof(const SCEVConstant *S) { return true; }
 
71
    static inline bool classof(const SCEV *S) {
 
72
      return S->getSCEVType() == scConstant;
 
73
    }
 
74
  };
 
75
 
 
76
  //===--------------------------------------------------------------------===//
 
77
  /// SCEVCastExpr - This is the base class for unary cast operator classes.
 
78
  ///
 
79
  class SCEVCastExpr : public SCEV {
 
80
  protected:
 
81
    const SCEV *Op;
 
82
    const Type *Ty;
 
83
 
 
84
    SCEVCastExpr(const FoldingSetNodeID &ID,
 
85
                 unsigned SCEVTy, const SCEV *op, const Type *ty);
 
86
 
 
87
  public:
 
88
    const SCEV *getOperand() const { return Op; }
 
89
    virtual const Type *getType() const { return Ty; }
 
90
 
 
91
    virtual bool isLoopInvariant(const Loop *L) const {
 
92
      return Op->isLoopInvariant(L);
 
93
    }
 
94
 
 
95
    virtual bool hasComputableLoopEvolution(const Loop *L) const {
 
96
      return Op->hasComputableLoopEvolution(L);
 
97
    }
 
98
 
 
99
    virtual bool hasOperand(const SCEV *O) const {
 
100
      return Op == O || Op->hasOperand(O);
 
101
    }
 
102
 
 
103
    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
104
 
 
105
    virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
106
 
 
107
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
108
    static inline bool classof(const SCEVCastExpr *S) { return true; }
 
109
    static inline bool classof(const SCEV *S) {
 
110
      return S->getSCEVType() == scTruncate ||
 
111
             S->getSCEVType() == scZeroExtend ||
 
112
             S->getSCEVType() == scSignExtend;
 
113
    }
 
114
  };
 
115
 
 
116
  //===--------------------------------------------------------------------===//
 
117
  /// SCEVTruncateExpr - This class represents a truncation of an integer value
 
118
  /// to a smaller integer value.
 
119
  ///
 
120
  class SCEVTruncateExpr : public SCEVCastExpr {
 
121
    friend class ScalarEvolution;
 
122
 
 
123
    SCEVTruncateExpr(const FoldingSetNodeID &ID,
 
124
                     const SCEV *op, const Type *ty);
 
125
 
 
126
  public:
 
127
    virtual void print(raw_ostream &OS) const;
 
128
 
 
129
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
130
    static inline bool classof(const SCEVTruncateExpr *S) { return true; }
 
131
    static inline bool classof(const SCEV *S) {
 
132
      return S->getSCEVType() == scTruncate;
 
133
    }
 
134
  };
 
135
 
 
136
  //===--------------------------------------------------------------------===//
 
137
  /// SCEVZeroExtendExpr - This class represents a zero extension of a small
 
138
  /// integer value to a larger integer value.
 
139
  ///
 
140
  class SCEVZeroExtendExpr : public SCEVCastExpr {
 
141
    friend class ScalarEvolution;
 
142
 
 
143
    SCEVZeroExtendExpr(const FoldingSetNodeID &ID,
 
144
                       const SCEV *op, const Type *ty);
 
145
 
 
146
  public:
 
147
    virtual void print(raw_ostream &OS) const;
 
148
 
 
149
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
150
    static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
 
151
    static inline bool classof(const SCEV *S) {
 
152
      return S->getSCEVType() == scZeroExtend;
 
153
    }
 
154
  };
 
155
 
 
156
  //===--------------------------------------------------------------------===//
 
157
  /// SCEVSignExtendExpr - This class represents a sign extension of a small
 
158
  /// integer value to a larger integer value.
 
159
  ///
 
160
  class SCEVSignExtendExpr : public SCEVCastExpr {
 
161
    friend class ScalarEvolution;
 
162
 
 
163
    SCEVSignExtendExpr(const FoldingSetNodeID &ID,
 
164
                       const SCEV *op, const Type *ty);
 
165
 
 
166
  public:
 
167
    virtual void print(raw_ostream &OS) const;
 
168
 
 
169
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
170
    static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
 
171
    static inline bool classof(const SCEV *S) {
 
172
      return S->getSCEVType() == scSignExtend;
 
173
    }
 
174
  };
 
175
 
 
176
 
 
177
  //===--------------------------------------------------------------------===//
 
178
  /// SCEVNAryExpr - This node is a base class providing common
 
179
  /// functionality for n'ary operators.
 
180
  ///
 
181
  class SCEVNAryExpr : public SCEV {
 
182
  protected:
 
183
    SmallVector<const SCEV *, 8> Operands;
 
184
 
 
185
    SCEVNAryExpr(const FoldingSetNodeID &ID,
 
186
                 enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops)
 
187
      : SCEV(ID, T), Operands(ops.begin(), ops.end()) {}
 
188
 
 
189
  public:
 
190
    unsigned getNumOperands() const { return (unsigned)Operands.size(); }
 
191
    const SCEV *getOperand(unsigned i) const {
 
192
      assert(i < Operands.size() && "Operand index out of range!");
 
193
      return Operands[i];
 
194
    }
 
195
 
 
196
    const SmallVectorImpl<const SCEV *> &getOperands() const {
 
197
      return Operands;
 
198
    }
 
199
    typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator;
 
200
    op_iterator op_begin() const { return Operands.begin(); }
 
201
    op_iterator op_end() const { return Operands.end(); }
 
202
 
 
203
    virtual bool isLoopInvariant(const Loop *L) const {
 
204
      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 
205
        if (!getOperand(i)->isLoopInvariant(L)) return false;
 
206
      return true;
 
207
    }
 
208
 
 
209
    // hasComputableLoopEvolution - N-ary expressions have computable loop
 
210
    // evolutions iff they have at least one operand that varies with the loop,
 
211
    // but that all varying operands are computable.
 
212
    virtual bool hasComputableLoopEvolution(const Loop *L) const {
 
213
      bool HasVarying = false;
 
214
      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 
215
        if (!getOperand(i)->isLoopInvariant(L)) {
 
216
          if (getOperand(i)->hasComputableLoopEvolution(L))
 
217
            HasVarying = true;
 
218
          else
 
219
            return false;
 
220
        }
 
221
      return HasVarying;
 
222
    }
 
223
 
 
224
    virtual bool hasOperand(const SCEV *O) const {
 
225
      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 
226
        if (O == getOperand(i) || getOperand(i)->hasOperand(O))
 
227
          return true;
 
228
      return false;
 
229
    }
 
230
 
 
231
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
232
 
 
233
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
234
 
 
235
    virtual const Type *getType() const { return getOperand(0)->getType(); }
 
236
 
 
237
    bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); }
 
238
    void setHasNoUnsignedWrap(bool B) {
 
239
      SubclassData = (SubclassData & ~(1 << 0)) | (B << 0);
 
240
    }
 
241
    bool hasNoSignedWrap() const { return SubclassData & (1 << 1); }
 
242
    void setHasNoSignedWrap(bool B) {
 
243
      SubclassData = (SubclassData & ~(1 << 1)) | (B << 1);
 
244
    }
 
245
 
 
246
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
247
    static inline bool classof(const SCEVNAryExpr *S) { return true; }
 
248
    static inline bool classof(const SCEV *S) {
 
249
      return S->getSCEVType() == scAddExpr ||
 
250
             S->getSCEVType() == scMulExpr ||
 
251
             S->getSCEVType() == scSMaxExpr ||
 
252
             S->getSCEVType() == scUMaxExpr ||
 
253
             S->getSCEVType() == scAddRecExpr;
 
254
    }
 
255
  };
 
256
 
 
257
  //===--------------------------------------------------------------------===//
 
258
  /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
 
259
  /// operators.
 
260
  ///
 
261
  class SCEVCommutativeExpr : public SCEVNAryExpr {
 
262
  protected:
 
263
    SCEVCommutativeExpr(const FoldingSetNodeID &ID,
 
264
                        enum SCEVTypes T,
 
265
                        const SmallVectorImpl<const SCEV *> &ops)
 
266
      : SCEVNAryExpr(ID, T, ops) {}
 
267
 
 
268
  public:
 
269
    virtual const char *getOperationStr() const = 0;
 
270
 
 
271
    virtual void print(raw_ostream &OS) const;
 
272
 
 
273
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
274
    static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
 
275
    static inline bool classof(const SCEV *S) {
 
276
      return S->getSCEVType() == scAddExpr ||
 
277
             S->getSCEVType() == scMulExpr ||
 
278
             S->getSCEVType() == scSMaxExpr ||
 
279
             S->getSCEVType() == scUMaxExpr;
 
280
    }
 
281
  };
 
282
 
 
283
 
 
284
  //===--------------------------------------------------------------------===//
 
285
  /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
 
286
  ///
 
287
  class SCEVAddExpr : public SCEVCommutativeExpr {
 
288
    friend class ScalarEvolution;
 
289
 
 
290
    SCEVAddExpr(const FoldingSetNodeID &ID,
 
291
                const SmallVectorImpl<const SCEV *> &ops)
 
292
      : SCEVCommutativeExpr(ID, scAddExpr, ops) {
 
293
    }
 
294
 
 
295
  public:
 
296
    virtual const char *getOperationStr() const { return " + "; }
 
297
 
 
298
    virtual const Type *getType() const {
 
299
      // Use the type of the last operand, which is likely to be a pointer
 
300
      // type, if there is one. This doesn't usually matter, but it can help
 
301
      // reduce casts when the expressions are expanded.
 
302
      return getOperand(getNumOperands() - 1)->getType();
 
303
    }
 
304
 
 
305
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
306
    static inline bool classof(const SCEVAddExpr *S) { return true; }
 
307
    static inline bool classof(const SCEV *S) {
 
308
      return S->getSCEVType() == scAddExpr;
 
309
    }
 
310
  };
 
311
 
 
312
  //===--------------------------------------------------------------------===//
 
313
  /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
 
314
  ///
 
315
  class SCEVMulExpr : public SCEVCommutativeExpr {
 
316
    friend class ScalarEvolution;
 
317
 
 
318
    SCEVMulExpr(const FoldingSetNodeID &ID,
 
319
                const SmallVectorImpl<const SCEV *> &ops)
 
320
      : SCEVCommutativeExpr(ID, scMulExpr, ops) {
 
321
    }
 
322
 
 
323
  public:
 
324
    virtual const char *getOperationStr() const { return " * "; }
 
325
 
 
326
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
327
    static inline bool classof(const SCEVMulExpr *S) { return true; }
 
328
    static inline bool classof(const SCEV *S) {
 
329
      return S->getSCEVType() == scMulExpr;
 
330
    }
 
331
  };
 
332
 
 
333
 
 
334
  //===--------------------------------------------------------------------===//
 
335
  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
 
336
  ///
 
337
  class SCEVUDivExpr : public SCEV {
 
338
    friend class ScalarEvolution;
 
339
 
 
340
    const SCEV *LHS;
 
341
    const SCEV *RHS;
 
342
    SCEVUDivExpr(const FoldingSetNodeID &ID, const SCEV *lhs, const SCEV *rhs)
 
343
      : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
 
344
 
 
345
  public:
 
346
    const SCEV *getLHS() const { return LHS; }
 
347
    const SCEV *getRHS() const { return RHS; }
 
348
 
 
349
    virtual bool isLoopInvariant(const Loop *L) const {
 
350
      return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
 
351
    }
 
352
 
 
353
    virtual bool hasComputableLoopEvolution(const Loop *L) const {
 
354
      return LHS->hasComputableLoopEvolution(L) &&
 
355
             RHS->hasComputableLoopEvolution(L);
 
356
    }
 
357
 
 
358
    virtual bool hasOperand(const SCEV *O) const {
 
359
      return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O);
 
360
    }
 
361
 
 
362
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
363
 
 
364
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
365
 
 
366
    virtual const Type *getType() const;
 
367
 
 
368
    void print(raw_ostream &OS) const;
 
369
 
 
370
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
371
    static inline bool classof(const SCEVUDivExpr *S) { return true; }
 
372
    static inline bool classof(const SCEV *S) {
 
373
      return S->getSCEVType() == scUDivExpr;
 
374
    }
 
375
  };
 
376
 
 
377
 
 
378
  //===--------------------------------------------------------------------===//
 
379
  /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
 
380
  /// count of the specified loop.  This is the primary focus of the
 
381
  /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
 
382
  /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
 
383
  /// created and analyzed.
 
384
  ///
 
385
  /// All operands of an AddRec are required to be loop invariant.
 
386
  ///
 
387
  class SCEVAddRecExpr : public SCEVNAryExpr {
 
388
    friend class ScalarEvolution;
 
389
 
 
390
    const Loop *L;
 
391
 
 
392
    SCEVAddRecExpr(const FoldingSetNodeID &ID,
 
393
                   const SmallVectorImpl<const SCEV *> &ops, const Loop *l)
 
394
      : SCEVNAryExpr(ID, scAddRecExpr, ops), L(l) {
 
395
      for (size_t i = 0, e = Operands.size(); i != e; ++i)
 
396
        assert(Operands[i]->isLoopInvariant(l) &&
 
397
               "Operands of AddRec must be loop-invariant!");
 
398
    }
 
399
 
 
400
  public:
 
401
    const SCEV *getStart() const { return Operands[0]; }
 
402
    const Loop *getLoop() const { return L; }
 
403
 
 
404
    /// getStepRecurrence - This method constructs and returns the recurrence
 
405
    /// indicating how much this expression steps by.  If this is a polynomial
 
406
    /// of degree N, it returns a chrec of degree N-1.
 
407
    const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
 
408
      if (isAffine()) return getOperand(1);
 
409
      return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
 
410
                                                           op_end()),
 
411
                              getLoop());
 
412
    }
 
413
 
 
414
    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
 
415
      return L == QL;
 
416
    }
 
417
 
 
418
    virtual bool isLoopInvariant(const Loop *QueryLoop) const;
 
419
 
 
420
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
421
 
 
422
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
423
 
 
424
    /// isAffine - Return true if this is an affine AddRec (i.e., it represents
 
425
    /// an expressions A+B*x where A and B are loop invariant values.
 
426
    bool isAffine() const {
 
427
      // We know that the start value is invariant.  This expression is thus
 
428
      // affine iff the step is also invariant.
 
429
      return getNumOperands() == 2;
 
430
    }
 
431
 
 
432
    /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
 
433
    /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
 
434
    /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
 
435
    bool isQuadratic() const {
 
436
      return getNumOperands() == 3;
 
437
    }
 
438
 
 
439
    /// evaluateAtIteration - Return the value of this chain of recurrences at
 
440
    /// the specified iteration number.
 
441
    const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
 
442
 
 
443
    /// getNumIterationsInRange - Return the number of iterations of this loop
 
444
    /// that produce values in the specified constant range.  Another way of
 
445
    /// looking at this is that it returns the first iteration number where the
 
446
    /// value is not in the condition, thus computing the exit count.  If the
 
447
    /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
 
448
    /// returned.
 
449
    const SCEV *getNumIterationsInRange(ConstantRange Range,
 
450
                                       ScalarEvolution &SE) const;
 
451
 
 
452
    /// getPostIncExpr - Return an expression representing the value of
 
453
    /// this expression one iteration of the loop ahead.
 
454
    const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
 
455
      return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
 
456
    }
 
457
 
 
458
    virtual void print(raw_ostream &OS) const;
 
459
 
 
460
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
461
    static inline bool classof(const SCEVAddRecExpr *S) { return true; }
 
462
    static inline bool classof(const SCEV *S) {
 
463
      return S->getSCEVType() == scAddRecExpr;
 
464
    }
 
465
  };
 
466
 
 
467
 
 
468
  //===--------------------------------------------------------------------===//
 
469
  /// SCEVSMaxExpr - This class represents a signed maximum selection.
 
470
  ///
 
471
  class SCEVSMaxExpr : public SCEVCommutativeExpr {
 
472
    friend class ScalarEvolution;
 
473
 
 
474
    SCEVSMaxExpr(const FoldingSetNodeID &ID,
 
475
                 const SmallVectorImpl<const SCEV *> &ops)
 
476
      : SCEVCommutativeExpr(ID, scSMaxExpr, ops) {
 
477
      // Max never overflows.
 
478
      setHasNoUnsignedWrap(true);
 
479
      setHasNoSignedWrap(true);
 
480
    }
 
481
 
 
482
  public:
 
483
    virtual const char *getOperationStr() const { return " smax "; }
 
484
 
 
485
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
486
    static inline bool classof(const SCEVSMaxExpr *S) { return true; }
 
487
    static inline bool classof(const SCEV *S) {
 
488
      return S->getSCEVType() == scSMaxExpr;
 
489
    }
 
490
  };
 
491
 
 
492
 
 
493
  //===--------------------------------------------------------------------===//
 
494
  /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
 
495
  ///
 
496
  class SCEVUMaxExpr : public SCEVCommutativeExpr {
 
497
    friend class ScalarEvolution;
 
498
 
 
499
    SCEVUMaxExpr(const FoldingSetNodeID &ID,
 
500
                 const SmallVectorImpl<const SCEV *> &ops)
 
501
      : SCEVCommutativeExpr(ID, scUMaxExpr, ops) {
 
502
      // Max never overflows.
 
503
      setHasNoUnsignedWrap(true);
 
504
      setHasNoSignedWrap(true);
 
505
    }
 
506
 
 
507
  public:
 
508
    virtual const char *getOperationStr() const { return " umax "; }
 
509
 
 
510
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
511
    static inline bool classof(const SCEVUMaxExpr *S) { return true; }
 
512
    static inline bool classof(const SCEV *S) {
 
513
      return S->getSCEVType() == scUMaxExpr;
 
514
    }
 
515
  };
 
516
 
 
517
  //===--------------------------------------------------------------------===//
 
518
  /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
 
519
  /// value, and only represent it as its LLVM Value.  This is the "bottom"
 
520
  /// value for the analysis.
 
521
  ///
 
522
  class SCEVUnknown : public SCEV {
 
523
    friend class ScalarEvolution;
 
524
 
 
525
    Value *V;
 
526
    SCEVUnknown(const FoldingSetNodeID &ID, Value *v) :
 
527
      SCEV(ID, scUnknown), V(v) {}
 
528
 
 
529
  public:
 
530
    Value *getValue() const { return V; }
 
531
 
 
532
    /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
 
533
    /// constant representing a type size, alignment, or field offset in
 
534
    /// a target-independent manner, and hasn't happened to have been
 
535
    /// folded with other operations into something unrecognizable. This
 
536
    /// is mainly only useful for pretty-printing and other situations
 
537
    /// where it isn't absolutely required for these to succeed.
 
538
    bool isSizeOf(const Type *&AllocTy) const;
 
539
    bool isAlignOf(const Type *&AllocTy) const;
 
540
    bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const;
 
541
 
 
542
    virtual bool isLoopInvariant(const Loop *L) const;
 
543
    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
 
544
      return false; // not computable
 
545
    }
 
546
 
 
547
    virtual bool hasOperand(const SCEV *) const {
 
548
      return false;
 
549
    }
 
550
 
 
551
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
552
 
 
553
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
554
 
 
555
    virtual const Type *getType() const;
 
556
 
 
557
    virtual void print(raw_ostream &OS) const;
 
558
 
 
559
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
560
    static inline bool classof(const SCEVUnknown *S) { return true; }
 
561
    static inline bool classof(const SCEV *S) {
 
562
      return S->getSCEVType() == scUnknown;
 
563
    }
 
564
  };
 
565
 
 
566
  /// SCEVVisitor - This class defines a simple visitor class that may be used
 
567
  /// for various SCEV analysis purposes.
 
568
  template<typename SC, typename RetVal=void>
 
569
  struct SCEVVisitor {
 
570
    RetVal visit(const SCEV *S) {
 
571
      switch (S->getSCEVType()) {
 
572
      case scConstant:
 
573
        return ((SC*)this)->visitConstant((const SCEVConstant*)S);
 
574
      case scTruncate:
 
575
        return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
 
576
      case scZeroExtend:
 
577
        return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
 
578
      case scSignExtend:
 
579
        return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
 
580
      case scAddExpr:
 
581
        return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
 
582
      case scMulExpr:
 
583
        return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
 
584
      case scUDivExpr:
 
585
        return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
 
586
      case scAddRecExpr:
 
587
        return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
 
588
      case scSMaxExpr:
 
589
        return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
 
590
      case scUMaxExpr:
 
591
        return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
 
592
      case scUnknown:
 
593
        return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
 
594
      case scCouldNotCompute:
 
595
        return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
 
596
      default:
 
597
        llvm_unreachable("Unknown SCEV type!");
 
598
      }
 
599
    }
 
600
 
 
601
    RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
 
602
      llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
 
603
      return RetVal();
 
604
    }
 
605
  };
 
606
}
 
607
 
 
608
#endif