← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

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 FoldingSetNodeIDRef 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 FoldingSetNodeIDRef 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 FoldingSetNodeIDRef 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 FoldingSetNodeIDRef 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 FoldingSetNodeIDRef 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
    // Since SCEVs are immutable, ScalarEvolution allocates operand
 
184
    // arrays with its SCEVAllocator, so this class just needs a simple
 
185
    // pointer rather than a more elaborate vector-like data structure.
 
186
    // This also avoids the need for a non-trivial destructor.
 
187
    const SCEV *const *Operands;
 
188
    size_t NumOperands;
 
189
 
 
190
    SCEVNAryExpr(const FoldingSetNodeIDRef ID,
 
191
                 enum SCEVTypes T, const SCEV *const *O, size_t N)
 
192
      : SCEV(ID, T), Operands(O), NumOperands(N) {}
 
193
 
 
194
  public:
 
195
    size_t getNumOperands() const { return NumOperands; }
 
196
    const SCEV *getOperand(unsigned i) const {
 
197
      assert(i < NumOperands && "Operand index out of range!");
 
198
      return Operands[i];
 
199
    }
 
200
 
 
201
    typedef const SCEV *const *op_iterator;
 
202
    op_iterator op_begin() const { return Operands; }
 
203
    op_iterator op_end() const { return Operands + NumOperands; }
 
204
 
 
205
    virtual bool isLoopInvariant(const Loop *L) const;
 
206
 
 
207
    // hasComputableLoopEvolution - N-ary expressions have computable loop
 
208
    // evolutions iff they have at least one operand that varies with the loop,
 
209
    // but that all varying operands are computable.
 
210
    virtual bool hasComputableLoopEvolution(const Loop *L) const;
 
211
 
 
212
    virtual bool hasOperand(const SCEV *O) const;
 
213
 
 
214
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
215
 
 
216
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
217
 
 
218
    virtual const Type *getType() const { return getOperand(0)->getType(); }
 
219
 
 
220
    bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); }
 
221
    void setHasNoUnsignedWrap(bool B) {
 
222
      SubclassData = (SubclassData & ~(1 << 0)) | (B << 0);
 
223
    }
 
224
    bool hasNoSignedWrap() const { return SubclassData & (1 << 1); }
 
225
    void setHasNoSignedWrap(bool B) {
 
226
      SubclassData = (SubclassData & ~(1 << 1)) | (B << 1);
 
227
    }
 
228
 
 
229
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
230
    static inline bool classof(const SCEVNAryExpr *S) { return true; }
 
231
    static inline bool classof(const SCEV *S) {
 
232
      return S->getSCEVType() == scAddExpr ||
 
233
             S->getSCEVType() == scMulExpr ||
 
234
             S->getSCEVType() == scSMaxExpr ||
 
235
             S->getSCEVType() == scUMaxExpr ||
 
236
             S->getSCEVType() == scAddRecExpr;
 
237
    }
 
238
  };
 
239
 
 
240
  //===--------------------------------------------------------------------===//
 
241
  /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
 
242
  /// operators.
 
243
  ///
 
244
  class SCEVCommutativeExpr : public SCEVNAryExpr {
 
245
  protected:
 
246
    SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
 
247
                        enum SCEVTypes T, const SCEV *const *O, size_t N)
 
248
      : SCEVNAryExpr(ID, T, O, N) {}
 
249
 
 
250
  public:
 
251
    virtual const char *getOperationStr() const = 0;
 
252
 
 
253
    virtual void print(raw_ostream &OS) const;
 
254
 
 
255
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
256
    static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
 
257
    static inline bool classof(const SCEV *S) {
 
258
      return S->getSCEVType() == scAddExpr ||
 
259
             S->getSCEVType() == scMulExpr ||
 
260
             S->getSCEVType() == scSMaxExpr ||
 
261
             S->getSCEVType() == scUMaxExpr;
 
262
    }
 
263
  };
 
264
 
 
265
 
 
266
  //===--------------------------------------------------------------------===//
 
267
  /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
 
268
  ///
 
269
  class SCEVAddExpr : public SCEVCommutativeExpr {
 
270
    friend class ScalarEvolution;
 
271
 
 
272
    SCEVAddExpr(const FoldingSetNodeIDRef ID,
 
273
                const SCEV *const *O, size_t N)
 
274
      : SCEVCommutativeExpr(ID, scAddExpr, O, N) {
 
275
    }
 
276
 
 
277
  public:
 
278
    virtual const char *getOperationStr() const { return " + "; }
 
279
 
 
280
    virtual const Type *getType() const {
 
281
      // Use the type of the last operand, which is likely to be a pointer
 
282
      // type, if there is one. This doesn't usually matter, but it can help
 
283
      // reduce casts when the expressions are expanded.
 
284
      return getOperand(getNumOperands() - 1)->getType();
 
285
    }
 
286
 
 
287
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
288
    static inline bool classof(const SCEVAddExpr *S) { return true; }
 
289
    static inline bool classof(const SCEV *S) {
 
290
      return S->getSCEVType() == scAddExpr;
 
291
    }
 
292
  };
 
293
 
 
294
  //===--------------------------------------------------------------------===//
 
295
  /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
 
296
  ///
 
297
  class SCEVMulExpr : public SCEVCommutativeExpr {
 
298
    friend class ScalarEvolution;
 
299
 
 
300
    SCEVMulExpr(const FoldingSetNodeIDRef ID,
 
301
                const SCEV *const *O, size_t N)
 
302
      : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
 
303
    }
 
304
 
 
305
  public:
 
306
    virtual const char *getOperationStr() const { return " * "; }
 
307
 
 
308
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
309
    static inline bool classof(const SCEVMulExpr *S) { return true; }
 
310
    static inline bool classof(const SCEV *S) {
 
311
      return S->getSCEVType() == scMulExpr;
 
312
    }
 
313
  };
 
314
 
 
315
 
 
316
  //===--------------------------------------------------------------------===//
 
317
  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
 
318
  ///
 
319
  class SCEVUDivExpr : public SCEV {
 
320
    friend class ScalarEvolution;
 
321
 
 
322
    const SCEV *LHS;
 
323
    const SCEV *RHS;
 
324
    SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
 
325
      : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
 
326
 
 
327
  public:
 
328
    const SCEV *getLHS() const { return LHS; }
 
329
    const SCEV *getRHS() const { return RHS; }
 
330
 
 
331
    virtual bool isLoopInvariant(const Loop *L) const {
 
332
      return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
 
333
    }
 
334
 
 
335
    virtual bool hasComputableLoopEvolution(const Loop *L) const {
 
336
      return LHS->hasComputableLoopEvolution(L) &&
 
337
             RHS->hasComputableLoopEvolution(L);
 
338
    }
 
339
 
 
340
    virtual bool hasOperand(const SCEV *O) const {
 
341
      return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O);
 
342
    }
 
343
 
 
344
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
345
 
 
346
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
347
 
 
348
    virtual const Type *getType() const;
 
349
 
 
350
    void print(raw_ostream &OS) const;
 
351
 
 
352
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
353
    static inline bool classof(const SCEVUDivExpr *S) { return true; }
 
354
    static inline bool classof(const SCEV *S) {
 
355
      return S->getSCEVType() == scUDivExpr;
 
356
    }
 
357
  };
 
358
 
 
359
 
 
360
  //===--------------------------------------------------------------------===//
 
361
  /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
 
362
  /// count of the specified loop.  This is the primary focus of the
 
363
  /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
 
364
  /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
 
365
  /// created and analyzed.
 
366
  ///
 
367
  /// All operands of an AddRec are required to be loop invariant.
 
368
  ///
 
369
  class SCEVAddRecExpr : public SCEVNAryExpr {
 
370
    friend class ScalarEvolution;
 
371
 
 
372
    const Loop *L;
 
373
 
 
374
    SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
 
375
                   const SCEV *const *O, size_t N, const Loop *l)
 
376
      : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {
 
377
      for (size_t i = 0, e = NumOperands; i != e; ++i)
 
378
        assert(Operands[i]->isLoopInvariant(l) &&
 
379
               "Operands of AddRec must be loop-invariant!");
 
380
    }
 
381
 
 
382
  public:
 
383
    const SCEV *getStart() const { return Operands[0]; }
 
384
    const Loop *getLoop() const { return L; }
 
385
 
 
386
    /// getStepRecurrence - This method constructs and returns the recurrence
 
387
    /// indicating how much this expression steps by.  If this is a polynomial
 
388
    /// of degree N, it returns a chrec of degree N-1.
 
389
    const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
 
390
      if (isAffine()) return getOperand(1);
 
391
      return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
 
392
                                                           op_end()),
 
393
                              getLoop());
 
394
    }
 
395
 
 
396
    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
 
397
      return L == QL;
 
398
    }
 
399
 
 
400
    virtual bool isLoopInvariant(const Loop *QueryLoop) const;
 
401
 
 
402
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
403
 
 
404
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
405
 
 
406
    /// isAffine - Return true if this is an affine AddRec (i.e., it represents
 
407
    /// an expressions A+B*x where A and B are loop invariant values.
 
408
    bool isAffine() const {
 
409
      // We know that the start value is invariant.  This expression is thus
 
410
      // affine iff the step is also invariant.
 
411
      return getNumOperands() == 2;
 
412
    }
 
413
 
 
414
    /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
 
415
    /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
 
416
    /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
 
417
    bool isQuadratic() const {
 
418
      return getNumOperands() == 3;
 
419
    }
 
420
 
 
421
    /// evaluateAtIteration - Return the value of this chain of recurrences at
 
422
    /// the specified iteration number.
 
423
    const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
 
424
 
 
425
    /// getNumIterationsInRange - Return the number of iterations of this loop
 
426
    /// that produce values in the specified constant range.  Another way of
 
427
    /// looking at this is that it returns the first iteration number where the
 
428
    /// value is not in the condition, thus computing the exit count.  If the
 
429
    /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
 
430
    /// returned.
 
431
    const SCEV *getNumIterationsInRange(ConstantRange Range,
 
432
                                       ScalarEvolution &SE) const;
 
433
 
 
434
    /// getPostIncExpr - Return an expression representing the value of
 
435
    /// this expression one iteration of the loop ahead.
 
436
    const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
 
437
      return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
 
438
    }
 
439
 
 
440
    virtual void print(raw_ostream &OS) const;
 
441
 
 
442
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
443
    static inline bool classof(const SCEVAddRecExpr *S) { return true; }
 
444
    static inline bool classof(const SCEV *S) {
 
445
      return S->getSCEVType() == scAddRecExpr;
 
446
    }
 
447
  };
 
448
 
 
449
 
 
450
  //===--------------------------------------------------------------------===//
 
451
  /// SCEVSMaxExpr - This class represents a signed maximum selection.
 
452
  ///
 
453
  class SCEVSMaxExpr : public SCEVCommutativeExpr {
 
454
    friend class ScalarEvolution;
 
455
 
 
456
    SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
 
457
                 const SCEV *const *O, size_t N)
 
458
      : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
 
459
      // Max never overflows.
 
460
      setHasNoUnsignedWrap(true);
 
461
      setHasNoSignedWrap(true);
 
462
    }
 
463
 
 
464
  public:
 
465
    virtual const char *getOperationStr() const { return " smax "; }
 
466
 
 
467
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
468
    static inline bool classof(const SCEVSMaxExpr *S) { return true; }
 
469
    static inline bool classof(const SCEV *S) {
 
470
      return S->getSCEVType() == scSMaxExpr;
 
471
    }
 
472
  };
 
473
 
 
474
 
 
475
  //===--------------------------------------------------------------------===//
 
476
  /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
 
477
  ///
 
478
  class SCEVUMaxExpr : public SCEVCommutativeExpr {
 
479
    friend class ScalarEvolution;
 
480
 
 
481
    SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
 
482
                 const SCEV *const *O, size_t N)
 
483
      : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
 
484
      // Max never overflows.
 
485
      setHasNoUnsignedWrap(true);
 
486
      setHasNoSignedWrap(true);
 
487
    }
 
488
 
 
489
  public:
 
490
    virtual const char *getOperationStr() const { return " umax "; }
 
491
 
 
492
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
493
    static inline bool classof(const SCEVUMaxExpr *S) { return true; }
 
494
    static inline bool classof(const SCEV *S) {
 
495
      return S->getSCEVType() == scUMaxExpr;
 
496
    }
 
497
  };
 
498
 
 
499
  //===--------------------------------------------------------------------===//
 
500
  /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
 
501
  /// value, and only represent it as its LLVM Value.  This is the "bottom"
 
502
  /// value for the analysis.
 
503
  ///
 
504
  class SCEVUnknown : public SCEV, private CallbackVH {
 
505
    friend class ScalarEvolution;
 
506
 
 
507
    // Implement CallbackVH.
 
508
    virtual void deleted();
 
509
    virtual void allUsesReplacedWith(Value *New);
 
510
 
 
511
    /// SE - The parent ScalarEvolution value. This is used to update
 
512
    /// the parent's maps when the value associated with a SCEVUnknown
 
513
    /// is deleted or RAUW'd.
 
514
    ScalarEvolution *SE;
 
515
 
 
516
    /// Next - The next pointer in the linked list of all
 
517
    /// SCEVUnknown instances owned by a ScalarEvolution.
 
518
    SCEVUnknown *Next;
 
519
 
 
520
    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
 
521
                ScalarEvolution *se, SCEVUnknown *next) :
 
522
      SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
 
523
 
 
524
  public:
 
525
    Value *getValue() const { return getValPtr(); }
 
526
 
 
527
    /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
 
528
    /// constant representing a type size, alignment, or field offset in
 
529
    /// a target-independent manner, and hasn't happened to have been
 
530
    /// folded with other operations into something unrecognizable. This
 
531
    /// is mainly only useful for pretty-printing and other situations
 
532
    /// where it isn't absolutely required for these to succeed.
 
533
    bool isSizeOf(const Type *&AllocTy) const;
 
534
    bool isAlignOf(const Type *&AllocTy) const;
 
535
    bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const;
 
536
 
 
537
    virtual bool isLoopInvariant(const Loop *L) const;
 
538
    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
 
539
      return false; // not computable
 
540
    }
 
541
 
 
542
    virtual bool hasOperand(const SCEV *) const {
 
543
      return false;
 
544
    }
 
545
 
 
546
    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
547
 
 
548
    bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
 
549
 
 
550
    virtual const Type *getType() const;
 
551
 
 
552
    virtual void print(raw_ostream &OS) const;
 
553
 
 
554
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
555
    static inline bool classof(const SCEVUnknown *S) { return true; }
 
556
    static inline bool classof(const SCEV *S) {
 
557
      return S->getSCEVType() == scUnknown;
 
558
    }
 
559
  };
 
560
 
 
561
  /// SCEVVisitor - This class defines a simple visitor class that may be used
 
562
  /// for various SCEV analysis purposes.
 
563
  template<typename SC, typename RetVal=void>
 
564
  struct SCEVVisitor {
 
565
    RetVal visit(const SCEV *S) {
 
566
      switch (S->getSCEVType()) {
 
567
      case scConstant:
 
568
        return ((SC*)this)->visitConstant((const SCEVConstant*)S);
 
569
      case scTruncate:
 
570
        return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
 
571
      case scZeroExtend:
 
572
        return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
 
573
      case scSignExtend:
 
574
        return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
 
575
      case scAddExpr:
 
576
        return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
 
577
      case scMulExpr:
 
578
        return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
 
579
      case scUDivExpr:
 
580
        return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
 
581
      case scAddRecExpr:
 
582
        return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
 
583
      case scSMaxExpr:
 
584
        return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
 
585
      case scUMaxExpr:
 
586
        return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
 
587
      case scUnknown:
 
588
        return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
 
589
      case scCouldNotCompute:
 
590
        return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
 
591
      default:
 
592
        llvm_unreachable("Unknown SCEV type!");
 
593
      }
 
594
    }
 
595
 
 
596
    RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
 
597
      llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
 
598
      return RetVal();
 
599
    }
 
600
  };
 
601
}
 
602
 
 
603
#endif