← 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/ScalarEvolution.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/ScalarEvolution.h
 
1
//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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
// The ScalarEvolution class is an LLVM pass which can be used to analyze and
 
11
// categorize scalar expressions in loops.  It specializes in recognizing
 
12
// general induction variables, representing them with the abstract and opaque
 
13
// SCEV class.  Given this analysis, trip counts of loops and other important
 
14
// properties can be obtained.
 
15
//
 
16
// This analysis is primarily useful for induction variable substitution and
 
17
// strength reduction.
 
18
//
 
19
//===----------------------------------------------------------------------===//
 
20
 
 
21
#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
 
22
#define LLVM_ANALYSIS_SCALAREVOLUTION_H
 
23
 
 
24
#include "llvm/Pass.h"
 
25
#include "llvm/Instructions.h"
 
26
#include "llvm/Function.h"
 
27
#include "llvm/System/DataTypes.h"
 
28
#include "llvm/Support/ValueHandle.h"
 
29
#include "llvm/Support/Allocator.h"
 
30
#include "llvm/Support/ConstantRange.h"
 
31
#include "llvm/ADT/FoldingSet.h"
 
32
#include "llvm/ADT/DenseMap.h"
 
33
#include <map>
 
34
 
 
35
namespace llvm {
 
36
  class APInt;
 
37
  class Constant;
 
38
  class ConstantInt;
 
39
  class DominatorTree;
 
40
  class Type;
 
41
  class ScalarEvolution;
 
42
  class TargetData;
 
43
  class LLVMContext;
 
44
  class Loop;
 
45
  class LoopInfo;
 
46
  class Operator;
 
47
  class SCEVUnknown;
 
48
  class SCEV;
 
49
  template<> struct FoldingSetTrait<SCEV>;
 
50
 
 
51
  /// SCEV - This class represents an analyzed expression in the program.  These
 
52
  /// are opaque objects that the client is not allowed to do much with
 
53
  /// directly.
 
54
  ///
 
55
  class SCEV : public FoldingSetNode {
 
56
    friend struct FoldingSetTrait<SCEV>;
 
57
 
 
58
    /// FastID - A reference to an Interned FoldingSetNodeID for this node.
 
59
    /// The ScalarEvolution's BumpPtrAllocator holds the data.
 
60
    FoldingSetNodeIDRef FastID;
 
61
 
 
62
    // The SCEV baseclass this node corresponds to
 
63
    const unsigned short SCEVType;
 
64
 
 
65
  protected:
 
66
    /// SubclassData - This field is initialized to zero and may be used in
 
67
    /// subclasses to store miscellaneous information.
 
68
    unsigned short SubclassData;
 
69
 
 
70
  private:
 
71
    SCEV(const SCEV &);            // DO NOT IMPLEMENT
 
72
    void operator=(const SCEV &);  // DO NOT IMPLEMENT
 
73
  protected:
 
74
    virtual ~SCEV();
 
75
  public:
 
76
    explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) :
 
77
      FastID(ID), SCEVType(SCEVTy), SubclassData(0) {}
 
78
 
 
79
    unsigned getSCEVType() const { return SCEVType; }
 
80
 
 
81
    /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
 
82
    /// the specified loop.
 
83
    virtual bool isLoopInvariant(const Loop *L) const = 0;
 
84
 
 
85
    /// hasComputableLoopEvolution - Return true if this SCEV changes value in a
 
86
    /// known way in the specified loop.  This property being true implies that
 
87
    /// the value is variant in the loop AND that we can emit an expression to
 
88
    /// compute the value of the expression at any particular loop iteration.
 
89
    virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;
 
90
 
 
91
    /// getType - Return the LLVM type of this SCEV expression.
 
92
    ///
 
93
    virtual const Type *getType() const = 0;
 
94
 
 
95
    /// isZero - Return true if the expression is a constant zero.
 
96
    ///
 
97
    bool isZero() const;
 
98
 
 
99
    /// isOne - Return true if the expression is a constant one.
 
100
    ///
 
101
    bool isOne() const;
 
102
 
 
103
    /// isAllOnesValue - Return true if the expression is a constant
 
104
    /// all-ones value.
 
105
    ///
 
106
    bool isAllOnesValue() const;
 
107
 
 
108
    /// hasOperand - Test whether this SCEV has Op as a direct or
 
109
    /// indirect operand.
 
110
    virtual bool hasOperand(const SCEV *Op) const = 0;
 
111
 
 
112
    /// dominates - Return true if elements that makes up this SCEV dominates
 
113
    /// the specified basic block.
 
114
    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0;
 
115
 
 
116
    /// properlyDominates - Return true if elements that makes up this SCEV
 
117
    /// properly dominate the specified basic block.
 
118
    virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const = 0;
 
119
 
 
120
    /// print - Print out the internal representation of this scalar to the
 
121
    /// specified stream.  This should really only be used for debugging
 
122
    /// purposes.
 
123
    virtual void print(raw_ostream &OS) const = 0;
 
124
 
 
125
    /// dump - This method is used for debugging.
 
126
    ///
 
127
    void dump() const;
 
128
  };
 
129
 
 
130
  // Specialize FoldingSetTrait for SCEV to avoid needing to compute
 
131
  // temporary FoldingSetNodeID values.
 
132
  template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
 
133
    static void Profile(const SCEV &X, FoldingSetNodeID& ID) {
 
134
      ID = X.FastID;
 
135
    }
 
136
    static bool Equals(const SCEV &X, const FoldingSetNodeID &ID,
 
137
                       FoldingSetNodeID &TempID) {
 
138
      return ID == X.FastID;
 
139
    }
 
140
    static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
 
141
      return X.FastID.ComputeHash();
 
142
    }
 
143
  };
 
144
 
 
145
  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
 
146
    S.print(OS);
 
147
    return OS;
 
148
  }
 
149
 
 
150
  /// SCEVCouldNotCompute - An object of this class is returned by queries that
 
151
  /// could not be answered.  For example, if you ask for the number of
 
152
  /// iterations of a linked-list traversal loop, you will get one of these.
 
153
  /// None of the standard SCEV operations are valid on this class, it is just a
 
154
  /// marker.
 
155
  struct SCEVCouldNotCompute : public SCEV {
 
156
    SCEVCouldNotCompute();
 
157
 
 
158
    // None of these methods are valid for this object.
 
159
    virtual bool isLoopInvariant(const Loop *L) const;
 
160
    virtual const Type *getType() const;
 
161
    virtual bool hasComputableLoopEvolution(const Loop *L) const;
 
162
    virtual void print(raw_ostream &OS) const;
 
163
    virtual bool hasOperand(const SCEV *Op) const;
 
164
 
 
165
    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const {
 
166
      return true;
 
167
    }
 
168
 
 
169
    virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 
170
      return true;
 
171
    }
 
172
 
 
173
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
 
174
    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
 
175
    static bool classof(const SCEV *S);
 
176
  };
 
177
 
 
178
  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
 
179
  /// client code (intentionally) can't do much with the SCEV objects directly,
 
180
  /// they must ask this class for services.
 
181
  ///
 
182
  class ScalarEvolution : public FunctionPass {
 
183
    /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
 
184
    /// notified whenever a Value is deleted.
 
185
    class SCEVCallbackVH : public CallbackVH {
 
186
      ScalarEvolution *SE;
 
187
      virtual void deleted();
 
188
      virtual void allUsesReplacedWith(Value *New);
 
189
    public:
 
190
      SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
 
191
    };
 
192
 
 
193
    friend class SCEVCallbackVH;
 
194
    friend class SCEVExpander;
 
195
    friend class SCEVUnknown;
 
196
 
 
197
    /// F - The function we are analyzing.
 
198
    ///
 
199
    Function *F;
 
200
 
 
201
    /// LI - The loop information for the function we are currently analyzing.
 
202
    ///
 
203
    LoopInfo *LI;
 
204
 
 
205
    /// TD - The target data information for the target we are targeting.
 
206
    ///
 
207
    TargetData *TD;
 
208
 
 
209
    /// DT - The dominator tree.
 
210
    ///
 
211
    DominatorTree *DT;
 
212
 
 
213
    /// CouldNotCompute - This SCEV is used to represent unknown trip
 
214
    /// counts and things.
 
215
    SCEVCouldNotCompute CouldNotCompute;
 
216
 
 
217
    /// ValueExprMapType - The typedef for ValueExprMap.
 
218
    ///
 
219
    typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
 
220
      ValueExprMapType;
 
221
 
 
222
    /// ValueExprMap - This is a cache of the values we have analyzed so far.
 
223
    ///
 
224
    ValueExprMapType ValueExprMap;
 
225
 
 
226
    /// BackedgeTakenInfo - Information about the backedge-taken count
 
227
    /// of a loop. This currently includes an exact count and a maximum count.
 
228
    ///
 
229
    struct BackedgeTakenInfo {
 
230
      /// Exact - An expression indicating the exact backedge-taken count of
 
231
      /// the loop if it is known, or a SCEVCouldNotCompute otherwise.
 
232
      const SCEV *Exact;
 
233
 
 
234
      /// Max - An expression indicating the least maximum backedge-taken
 
235
      /// count of the loop that is known, or a SCEVCouldNotCompute.
 
236
      const SCEV *Max;
 
237
 
 
238
      /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
 
239
        Exact(exact), Max(exact) {}
 
240
 
 
241
      BackedgeTakenInfo(const SCEV *exact, const SCEV *max) :
 
242
        Exact(exact), Max(max) {}
 
243
 
 
244
      /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
 
245
      /// computed information, or whether it's all SCEVCouldNotCompute
 
246
      /// values.
 
247
      bool hasAnyInfo() const {
 
248
        return !isa<SCEVCouldNotCompute>(Exact) ||
 
249
               !isa<SCEVCouldNotCompute>(Max);
 
250
      }
 
251
    };
 
252
 
 
253
    /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
 
254
    /// this function as they are computed.
 
255
    std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
 
256
 
 
257
    /// ConstantEvolutionLoopExitValue - This map contains entries for all of
 
258
    /// the PHI instructions that we attempt to compute constant evolutions for.
 
259
    /// This allows us to avoid potentially expensive recomputation of these
 
260
    /// properties.  An instruction maps to null if we are unable to compute its
 
261
    /// exit value.
 
262
    std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
 
263
 
 
264
    /// ValuesAtScopes - This map contains entries for all the expressions
 
265
    /// that we attempt to compute getSCEVAtScope information for, which can
 
266
    /// be expensive in extreme cases.
 
267
    std::map<const SCEV *,
 
268
             std::map<const Loop *, const SCEV *> > ValuesAtScopes;
 
269
 
 
270
    /// createSCEV - We know that there is no SCEV for the specified value.
 
271
    /// Analyze the expression.
 
272
    const SCEV *createSCEV(Value *V);
 
273
 
 
274
    /// createNodeForPHI - Provide the special handling we need to analyze PHI
 
275
    /// SCEVs.
 
276
    const SCEV *createNodeForPHI(PHINode *PN);
 
277
 
 
278
    /// createNodeForGEP - Provide the special handling we need to analyze GEP
 
279
    /// SCEVs.
 
280
    const SCEV *createNodeForGEP(GEPOperator *GEP);
 
281
 
 
282
    /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called
 
283
    /// at most once for each SCEV+Loop pair.
 
284
    ///
 
285
    const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
 
286
 
 
287
    /// ForgetSymbolicValue - This looks up computed SCEV values for all
 
288
    /// instructions that depend on the given instruction and removes them from
 
289
    /// the ValueExprMap map if they reference SymName. This is used during PHI
 
290
    /// resolution.
 
291
    void ForgetSymbolicName(Instruction *I, const SCEV *SymName);
 
292
 
 
293
    /// getBECount - Subtract the end and start values and divide by the step,
 
294
    /// rounding up, to get the number of times the backedge is executed. Return
 
295
    /// CouldNotCompute if an intermediate computation overflows.
 
296
    const SCEV *getBECount(const SCEV *Start,
 
297
                           const SCEV *End,
 
298
                           const SCEV *Step,
 
299
                           bool NoWrap);
 
300
 
 
301
    /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
 
302
    /// loop, lazily computing new values if the loop hasn't been analyzed
 
303
    /// yet.
 
304
    const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
 
305
 
 
306
    /// ComputeBackedgeTakenCount - Compute the number of times the specified
 
307
    /// loop will iterate.
 
308
    BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);
 
309
 
 
310
    /// ComputeBackedgeTakenCountFromExit - Compute the number of times the
 
311
    /// backedge of the specified loop will execute if it exits via the
 
312
    /// specified block.
 
313
    BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
 
314
                                                      BasicBlock *ExitingBlock);
 
315
 
 
316
    /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
 
317
    /// backedge of the specified loop will execute if its exit condition
 
318
    /// were a conditional branch of ExitCond, TBB, and FBB.
 
319
    BackedgeTakenInfo
 
320
      ComputeBackedgeTakenCountFromExitCond(const Loop *L,
 
321
                                            Value *ExitCond,
 
322
                                            BasicBlock *TBB,
 
323
                                            BasicBlock *FBB);
 
324
 
 
325
    /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of
 
326
    /// times the backedge of the specified loop will execute if its exit
 
327
    /// condition were a conditional branch of the ICmpInst ExitCond, TBB,
 
328
    /// and FBB.
 
329
    BackedgeTakenInfo
 
330
      ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
 
331
                                                ICmpInst *ExitCond,
 
332
                                                BasicBlock *TBB,
 
333
                                                BasicBlock *FBB);
 
334
 
 
335
    /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
 
336
    /// of 'icmp op load X, cst', try to see if we can compute the
 
337
    /// backedge-taken count.
 
338
    BackedgeTakenInfo
 
339
      ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
 
340
                                                   Constant *RHS,
 
341
                                                   const Loop *L,
 
342
                                                   ICmpInst::Predicate p);
 
343
 
 
344
    /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute
 
345
    /// a constant number of times (the condition evolves only from constants),
 
346
    /// try to evaluate a few iterations of the loop until we get the exit
 
347
    /// condition gets a value of ExitWhen (true or false).  If we cannot
 
348
    /// evaluate the backedge-taken count of the loop, return CouldNotCompute.
 
349
    const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L,
 
350
                                                      Value *Cond,
 
351
                                                      bool ExitWhen);
 
352
 
 
353
    /// HowFarToZero - Return the number of times a backedge comparing the
 
354
    /// specified value to zero will execute.  If not computable, return
 
355
    /// CouldNotCompute.
 
356
    BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L);
 
357
 
 
358
    /// HowFarToNonZero - Return the number of times a backedge checking the
 
359
    /// specified value for nonzero will execute.  If not computable, return
 
360
    /// CouldNotCompute.
 
361
    BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L);
 
362
 
 
363
    /// HowManyLessThans - Return the number of times a backedge containing the
 
364
    /// specified less-than comparison will execute.  If not computable, return
 
365
    /// CouldNotCompute. isSigned specifies whether the less-than is signed.
 
366
    BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
 
367
                                       const Loop *L, bool isSigned);
 
368
 
 
369
    /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
 
370
    /// (which may not be an immediate predecessor) which has exactly one
 
371
    /// successor from which BB is reachable, or null if no such block is
 
372
    /// found.
 
373
    std::pair<BasicBlock *, BasicBlock *>
 
374
    getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
 
375
 
 
376
    /// isImpliedCond - Test whether the condition described by Pred, LHS, and
 
377
    /// RHS is true whenever the given FoundCondValue value evaluates to true.
 
378
    bool isImpliedCond(ICmpInst::Predicate Pred,
 
379
                       const SCEV *LHS, const SCEV *RHS,
 
380
                       Value *FoundCondValue,
 
381
                       bool Inverse);
 
382
 
 
383
    /// isImpliedCondOperands - Test whether the condition described by Pred,
 
384
    /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
 
385
    /// and FoundRHS is true.
 
386
    bool isImpliedCondOperands(ICmpInst::Predicate Pred,
 
387
                               const SCEV *LHS, const SCEV *RHS,
 
388
                               const SCEV *FoundLHS, const SCEV *FoundRHS);
 
389
 
 
390
    /// isImpliedCondOperandsHelper - Test whether the condition described by
 
391
    /// Pred, LHS, and RHS is true whenever the condition described by Pred,
 
392
    /// FoundLHS, and FoundRHS is true.
 
393
    bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
 
394
                                     const SCEV *LHS, const SCEV *RHS,
 
395
                                     const SCEV *FoundLHS, const SCEV *FoundRHS);
 
396
 
 
397
    /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
 
398
    /// in the header of its containing loop, we know the loop executes a
 
399
    /// constant number of times, and the PHI node is just a recurrence
 
400
    /// involving constants, fold it.
 
401
    Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
 
402
                                                const Loop *L);
 
403
 
 
404
    /// isKnownPredicateWithRanges - Test if the given expression is known to
 
405
    /// satisfy the condition described by Pred and the known constant ranges
 
406
    /// of LHS and RHS.
 
407
    ///
 
408
    bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
 
409
                                    const SCEV *LHS, const SCEV *RHS);
 
410
 
 
411
  public:
 
412
    static char ID; // Pass identification, replacement for typeid
 
413
    ScalarEvolution();
 
414
 
 
415
    LLVMContext &getContext() const { return F->getContext(); }
 
416
 
 
417
    /// isSCEVable - Test if values of the given type are analyzable within
 
418
    /// the SCEV framework. This primarily includes integer types, and it
 
419
    /// can optionally include pointer types if the ScalarEvolution class
 
420
    /// has access to target-specific information.
 
421
    bool isSCEVable(const Type *Ty) const;
 
422
 
 
423
    /// getTypeSizeInBits - Return the size in bits of the specified type,
 
424
    /// for which isSCEVable must return true.
 
425
    uint64_t getTypeSizeInBits(const Type *Ty) const;
 
426
 
 
427
    /// getEffectiveSCEVType - Return a type with the same bitwidth as
 
428
    /// the given type and which represents how SCEV will treat the given
 
429
    /// type, for which isSCEVable must return true. For pointer types,
 
430
    /// this is the pointer-sized integer type.
 
431
    const Type *getEffectiveSCEVType(const Type *Ty) const;
 
432
 
 
433
    /// getSCEV - Return a SCEV expression for the full generality of the
 
434
    /// specified expression.
 
435
    const SCEV *getSCEV(Value *V);
 
436
 
 
437
    const SCEV *getConstant(ConstantInt *V);
 
438
    const SCEV *getConstant(const APInt& Val);
 
439
    const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false);
 
440
    const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty);
 
441
    const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty);
 
442
    const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty);
 
443
    const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty);
 
444
    const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
 
445
                           bool HasNUW = false, bool HasNSW = false);
 
446
    const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
 
447
                           bool HasNUW = false, bool HasNSW = false) {
 
448
      SmallVector<const SCEV *, 2> Ops;
 
449
      Ops.push_back(LHS);
 
450
      Ops.push_back(RHS);
 
451
      return getAddExpr(Ops, HasNUW, HasNSW);
 
452
    }
 
453
    const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1,
 
454
                           const SCEV *Op2,
 
455
                           bool HasNUW = false, bool HasNSW = false) {
 
456
      SmallVector<const SCEV *, 3> Ops;
 
457
      Ops.push_back(Op0);
 
458
      Ops.push_back(Op1);
 
459
      Ops.push_back(Op2);
 
460
      return getAddExpr(Ops, HasNUW, HasNSW);
 
461
    }
 
462
    const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
 
463
                           bool HasNUW = false, bool HasNSW = false);
 
464
    const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
 
465
                           bool HasNUW = false, bool HasNSW = false) {
 
466
      SmallVector<const SCEV *, 2> Ops;
 
467
      Ops.push_back(LHS);
 
468
      Ops.push_back(RHS);
 
469
      return getMulExpr(Ops, HasNUW, HasNSW);
 
470
    }
 
471
    const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
 
472
    const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
 
473
                              const Loop *L,
 
474
                              bool HasNUW = false, bool HasNSW = false);
 
475
    const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
 
476
                              const Loop *L,
 
477
                              bool HasNUW = false, bool HasNSW = false);
 
478
    const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
 
479
                              const Loop *L,
 
480
                              bool HasNUW = false, bool HasNSW = false) {
 
481
      SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
 
482
      return getAddRecExpr(NewOp, L, HasNUW, HasNSW);
 
483
    }
 
484
    const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
 
485
    const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
 
486
    const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
 
487
    const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
 
488
    const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
 
489
    const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
 
490
    const SCEV *getUnknown(Value *V);
 
491
    const SCEV *getCouldNotCompute();
 
492
 
 
493
    /// getSizeOfExpr - Return an expression for sizeof on the given type.
 
494
    ///
 
495
    const SCEV *getSizeOfExpr(const Type *AllocTy);
 
496
 
 
497
    /// getAlignOfExpr - Return an expression for alignof on the given type.
 
498
    ///
 
499
    const SCEV *getAlignOfExpr(const Type *AllocTy);
 
500
 
 
501
    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
 
502
    ///
 
503
    const SCEV *getOffsetOfExpr(const StructType *STy, unsigned FieldNo);
 
504
 
 
505
    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
 
506
    ///
 
507
    const SCEV *getOffsetOfExpr(const Type *CTy, Constant *FieldNo);
 
508
 
 
509
    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
 
510
    ///
 
511
    const SCEV *getNegativeSCEV(const SCEV *V);
 
512
 
 
513
    /// getNotSCEV - Return the SCEV object corresponding to ~V.
 
514
    ///
 
515
    const SCEV *getNotSCEV(const SCEV *V);
 
516
 
 
517
    /// getMinusSCEV - Return LHS-RHS.
 
518
    ///
 
519
    const SCEV *getMinusSCEV(const SCEV *LHS,
 
520
                             const SCEV *RHS);
 
521
 
 
522
    /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
 
523
    /// of the input value to the specified type.  If the type must be
 
524
    /// extended, it is zero extended.
 
525
    const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty);
 
526
 
 
527
    /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
 
528
    /// of the input value to the specified type.  If the type must be
 
529
    /// extended, it is sign extended.
 
530
    const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty);
 
531
 
 
532
    /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of
 
533
    /// the input value to the specified type.  If the type must be extended,
 
534
    /// it is zero extended.  The conversion must not be narrowing.
 
535
    const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty);
 
536
 
 
537
    /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of
 
538
    /// the input value to the specified type.  If the type must be extended,
 
539
    /// it is sign extended.  The conversion must not be narrowing.
 
540
    const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty);
 
541
 
 
542
    /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
 
543
    /// the input value to the specified type. If the type must be extended,
 
544
    /// it is extended with unspecified bits. The conversion must not be
 
545
    /// narrowing.
 
546
    const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty);
 
547
 
 
548
    /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
 
549
    /// input value to the specified type.  The conversion must not be
 
550
    /// widening.
 
551
    const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty);
 
552
 
 
553
    /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
 
554
    /// the types using zero-extension, and then perform a umax operation
 
555
    /// with them.
 
556
    const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS,
 
557
                                           const SCEV *RHS);
 
558
 
 
559
    /// getUMinFromMismatchedTypes - Promote the operands to the wider of
 
560
    /// the types using zero-extension, and then perform a umin operation
 
561
    /// with them.
 
562
    const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS,
 
563
                                           const SCEV *RHS);
 
564
 
 
565
    /// getSCEVAtScope - Return a SCEV expression for the specified value
 
566
    /// at the specified scope in the program.  The L value specifies a loop
 
567
    /// nest to evaluate the expression at, where null is the top-level or a
 
568
    /// specified loop is immediately inside of the loop.
 
569
    ///
 
570
    /// This method can be used to compute the exit value for a variable defined
 
571
    /// in a loop by querying what the value will hold in the parent loop.
 
572
    ///
 
573
    /// In the case that a relevant loop exit value cannot be computed, the
 
574
    /// original value V is returned.
 
575
    const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
 
576
 
 
577
    /// getSCEVAtScope - This is a convenience function which does
 
578
    /// getSCEVAtScope(getSCEV(V), L).
 
579
    const SCEV *getSCEVAtScope(Value *V, const Loop *L);
 
580
 
 
581
    /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
 
582
    /// by a conditional between LHS and RHS.  This is used to help avoid max
 
583
    /// expressions in loop trip counts, and to eliminate casts.
 
584
    bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
 
585
                                  const SCEV *LHS, const SCEV *RHS);
 
586
 
 
587
    /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
 
588
    /// protected by a conditional between LHS and RHS.  This is used to
 
589
    /// to eliminate casts.
 
590
    bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
 
591
                                     const SCEV *LHS, const SCEV *RHS);
 
592
 
 
593
    /// getBackedgeTakenCount - If the specified loop has a predictable
 
594
    /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
 
595
    /// object. The backedge-taken count is the number of times the loop header
 
596
    /// will be branched to from within the loop. This is one less than the
 
597
    /// trip count of the loop, since it doesn't count the first iteration,
 
598
    /// when the header is branched to from outside the loop.
 
599
    ///
 
600
    /// Note that it is not valid to call this method on a loop without a
 
601
    /// loop-invariant backedge-taken count (see
 
602
    /// hasLoopInvariantBackedgeTakenCount).
 
603
    ///
 
604
    const SCEV *getBackedgeTakenCount(const Loop *L);
 
605
 
 
606
    /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
 
607
    /// return the least SCEV value that is known never to be less than the
 
608
    /// actual backedge taken count.
 
609
    const SCEV *getMaxBackedgeTakenCount(const Loop *L);
 
610
 
 
611
    /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
 
612
    /// has an analyzable loop-invariant backedge-taken count.
 
613
    bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
 
614
 
 
615
    /// forgetLoop - This method should be called by the client when it has
 
616
    /// changed a loop in a way that may effect ScalarEvolution's ability to
 
617
    /// compute a trip count, or if the loop is deleted.
 
618
    void forgetLoop(const Loop *L);
 
619
 
 
620
    /// forgetValue - This method should be called by the client when it has
 
621
    /// changed a value in a way that may effect its value, or which may
 
622
    /// disconnect it from a def-use chain linking it to a loop.
 
623
    void forgetValue(Value *V);
 
624
 
 
625
    /// GetMinTrailingZeros - Determine the minimum number of zero bits that S
 
626
    /// is guaranteed to end in (at every loop iteration).  It is, at the same
 
627
    /// time, the minimum number of times S is divisible by 2.  For example,
 
628
    /// given {4,+,8} it returns 2.  If S is guaranteed to be 0, it returns the
 
629
    /// bitwidth of S.
 
630
    uint32_t GetMinTrailingZeros(const SCEV *S);
 
631
 
 
632
    /// getUnsignedRange - Determine the unsigned range for a particular SCEV.
 
633
    ///
 
634
    ConstantRange getUnsignedRange(const SCEV *S);
 
635
 
 
636
    /// getSignedRange - Determine the signed range for a particular SCEV.
 
637
    ///
 
638
    ConstantRange getSignedRange(const SCEV *S);
 
639
 
 
640
    /// isKnownNegative - Test if the given expression is known to be negative.
 
641
    ///
 
642
    bool isKnownNegative(const SCEV *S);
 
643
 
 
644
    /// isKnownPositive - Test if the given expression is known to be positive.
 
645
    ///
 
646
    bool isKnownPositive(const SCEV *S);
 
647
 
 
648
    /// isKnownNonNegative - Test if the given expression is known to be
 
649
    /// non-negative.
 
650
    ///
 
651
    bool isKnownNonNegative(const SCEV *S);
 
652
 
 
653
    /// isKnownNonPositive - Test if the given expression is known to be
 
654
    /// non-positive.
 
655
    ///
 
656
    bool isKnownNonPositive(const SCEV *S);
 
657
 
 
658
    /// isKnownNonZero - Test if the given expression is known to be
 
659
    /// non-zero.
 
660
    ///
 
661
    bool isKnownNonZero(const SCEV *S);
 
662
 
 
663
    /// isKnownPredicate - Test if the given expression is known to satisfy
 
664
    /// the condition described by Pred, LHS, and RHS.
 
665
    ///
 
666
    bool isKnownPredicate(ICmpInst::Predicate Pred,
 
667
                          const SCEV *LHS, const SCEV *RHS);
 
668
 
 
669
    /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
 
670
    /// predicate Pred. Return true iff any changes were made. If the
 
671
    /// operands are provably equal or inequal, LHS and RHS are set to
 
672
    /// the same value and Pred is set to either ICMP_EQ or ICMP_NE.
 
673
    ///
 
674
    bool SimplifyICmpOperands(ICmpInst::Predicate &Pred,
 
675
                              const SCEV *&LHS,
 
676
                              const SCEV *&RHS);
 
677
 
 
678
    virtual bool runOnFunction(Function &F);
 
679
    virtual void releaseMemory();
 
680
    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 
681
    virtual void print(raw_ostream &OS, const Module* = 0) const;
 
682
 
 
683
  private:
 
684
    FoldingSet<SCEV> UniqueSCEVs;
 
685
    BumpPtrAllocator SCEVAllocator;
 
686
 
 
687
    /// FirstUnknown - The head of a linked list of all SCEVUnknown
 
688
    /// values that have been allocated. This is used by releaseMemory
 
689
    /// to locate them all and call their destructors.
 
690
    SCEVUnknown *FirstUnknown;
 
691
  };
 
692
}
 
693
 
 
694
#endif