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