clang  7.0.0svn
RangedConstraintManager.h
Go to the documentation of this file.
1 //== RangedConstraintManager.h ----------------------------------*- 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 // Ranged constraint manager, built on SimpleConstraintManager.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
15 #define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
16 
20 
21 namespace clang {
22 
23 namespace ento {
24 
25 /// A Range represents the closed range [from, to]. The caller must
26 /// guarantee that from <= to. Note that Range is immutable, so as not
27 /// to subvert RangeSet's immutability.
28 class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
29 public:
30  Range(const llvm::APSInt &from, const llvm::APSInt &to)
31  : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
32  assert(from <= to);
33  }
34  bool Includes(const llvm::APSInt &v) const {
35  return *first <= v && v <= *second;
36  }
37  const llvm::APSInt &From() const { return *first; }
38  const llvm::APSInt &To() const { return *second; }
39  const llvm::APSInt *getConcreteValue() const {
40  return &From() == &To() ? &From() : nullptr;
41  }
42 
43  void Profile(llvm::FoldingSetNodeID &ID) const {
44  ID.AddPointer(&From());
45  ID.AddPointer(&To());
46  }
47 };
48 
49 class RangeTrait : public llvm::ImutContainerInfo<Range> {
50 public:
51  // When comparing if one Range is less than another, we should compare
52  // the actual APSInt values instead of their pointers. This keeps the order
53  // consistent (instead of comparing by pointer values) and can potentially
54  // be used to speed up some of the operations in RangeSet.
55  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
56  return *lhs.first < *rhs.first ||
57  (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
58  }
59 };
60 
61 /// RangeSet contains a set of ranges. If the set is empty, then
62 /// there the value of a symbol is overly constrained and there are no
63 /// possible values for that symbol.
64 class RangeSet {
65  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
66  PrimRangeSet ranges; // no need to make const, since it is an
67  // ImmutableSet - this allows default operator=
68  // to work.
69 public:
70  typedef PrimRangeSet::Factory Factory;
71  typedef PrimRangeSet::iterator iterator;
72 
73  RangeSet(PrimRangeSet RS) : ranges(RS) {}
74 
75  /// Create a new set with all ranges of this set and RS.
76  /// Possible intersections are not checked here.
77  RangeSet addRange(Factory &F, const RangeSet &RS) {
78  PrimRangeSet Ranges(RS.ranges);
79  for (const auto &range : ranges)
80  Ranges = F.add(Ranges, range);
81  return RangeSet(Ranges);
82  }
83 
84  iterator begin() const { return ranges.begin(); }
85  iterator end() const { return ranges.end(); }
86 
87  bool isEmpty() const { return ranges.isEmpty(); }
88 
89  /// Construct a new RangeSet representing '{ [from, to] }'.
90  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
91  : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
92 
93  /// Profile - Generates a hash profile of this RangeSet for use
94  /// by FoldingSet.
95  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
96 
97  /// getConcreteValue - If a symbol is contrained to equal a specific integer
98  /// constant then this method returns that value. Otherwise, it returns
99  /// NULL.
100  const llvm::APSInt *getConcreteValue() const {
101  return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
102  }
103 
104 private:
105  void IntersectInRange(BasicValueFactory &BV, Factory &F,
106  const llvm::APSInt &Lower, const llvm::APSInt &Upper,
107  PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
108  PrimRangeSet::iterator &e) const;
109 
110  const llvm::APSInt &getMinValue() const;
111 
112  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
113 
114 public:
115  RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
116  llvm::APSInt Upper) const;
117 
118  void print(raw_ostream &os) const;
119 
120  bool operator==(const RangeSet &other) const {
121  return ranges == other.ranges;
122  }
123 };
124 
125 
127 using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>;
128 
129 template <>
131  : public ProgramStatePartialTrait<ConstraintRangeTy> {
132  static void *GDMIndex() { static int Index; return &Index; }
133 };
134 
135 
137 public:
139  : SimpleConstraintManager(SE, SB) {}
140 
141  ~RangedConstraintManager() override;
142 
143  //===------------------------------------------------------------------===//
144  // Implementation for interface from SimpleConstraintManager.
145  //===------------------------------------------------------------------===//
146 
148  bool Assumption) override;
149 
150  ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
151  const llvm::APSInt &From,
152  const llvm::APSInt &To,
153  bool InRange) override;
154 
155  ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
156  bool Assumption) override;
157 
158 protected:
159  /// Assume a constraint between a symbolic expression and a concrete integer.
160  virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym,
162  const llvm::APSInt &Int);
163 
164  //===------------------------------------------------------------------===//
165  // Interface that subclasses must implement.
166  //===------------------------------------------------------------------===//
167 
168  // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
169  // operation for the method being invoked.
170 
171  virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
172  const llvm::APSInt &V,
173  const llvm::APSInt &Adjustment) = 0;
174 
175  virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
176  const llvm::APSInt &V,
177  const llvm::APSInt &Adjustment) = 0;
178 
179  virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
180  const llvm::APSInt &V,
181  const llvm::APSInt &Adjustment) = 0;
182 
183  virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
184  const llvm::APSInt &V,
185  const llvm::APSInt &Adjustment) = 0;
186 
187  virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
188  const llvm::APSInt &V,
189  const llvm::APSInt &Adjustment) = 0;
190 
191  virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
192  const llvm::APSInt &V,
193  const llvm::APSInt &Adjustment) = 0;
194 
195  virtual ProgramStateRef assumeSymWithinInclusiveRange(
196  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
197  const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
198 
199  virtual ProgramStateRef assumeSymOutsideInclusiveRange(
200  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
201  const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
202 
203  //===------------------------------------------------------------------===//
204  // Internal implementation.
205  //===------------------------------------------------------------------===//
206 private:
207  static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
208 };
209 
210 } // end GR namespace
211 
212 } // end clang namespace
213 
214 #endif
const llvm::APSInt & From() const
void Profile(llvm::FoldingSetNodeID &ID) const
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:30
A Range represents the closed range [from, to].
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintRangeTy
RangeSet contains a set of ranges.
static bool isLess(key_type_ref lhs, key_type_ref rhs)
Symbolic value.
Definition: SymExpr.h:30
Range(const llvm::APSInt &from, const llvm::APSInt &to)
LineState State
RangeSet addRange(Factory &F, const RangeSet &RS)
Create a new set with all ranges of this set and RS.
Definition: Format.h:2022
BinaryOperatorKind
PrimRangeSet::Factory Factory
RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
Construct a new RangeSet representing &#39;{ [from, to] }&#39;.
const llvm::APSInt * getConcreteValue() const
const llvm::APSInt * getConcreteValue() const
getConcreteValue - If a symbol is contrained to equal a specific integer constant then this method re...
bool Includes(const llvm::APSInt &v) const
do v
Definition: arm_acle.h:78
void Profile(llvm::FoldingSetNodeID &ID) const
Profile - Generates a hash profile of this RangeSet for use by FoldingSet.
bool operator==(const RangeSet &other) const
Dataflow Directional Tag Classes.
const llvm::APSInt & To() const
PrimRangeSet::iterator iterator
RangedConstraintManager(SubEngine *SE, SValBuilder &SB)