RangedConstraintManager.h revision 344779
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 17#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" 20 21namespace clang { 22 23namespace 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. 28class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { 29public: 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 49class RangeTrait : public llvm::ImutContainerInfo<Range> { 50public: 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. 64class 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. 69public: 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 104private: 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 114public: 115 RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, 116 llvm::APSInt Upper) const; 117 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 128class ConstraintRange {}; 129using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>; 130 131template <> 132struct ProgramStateTrait<ConstraintRange> 133 : public ProgramStatePartialTrait<ConstraintRangeTy> { 134 static void *GDMIndex(); 135}; 136 137 138class RangedConstraintManager : public SimpleConstraintManager { 139public: 140 RangedConstraintManager(SubEngine *SE, SValBuilder &SB) 141 : SimpleConstraintManager(SE, SB) {} 142 143 ~RangedConstraintManager() override; 144 145 //===------------------------------------------------------------------===// 146 // Implementation for interface from SimpleConstraintManager. 147 //===------------------------------------------------------------------===// 148 149 ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, 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 160protected: 161 /// Assume a constraint between a symbolic expression and a concrete integer. 162 virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, 163 BinaryOperator::Opcode op, 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 //===------------------------------------------------------------------===// 208private: 209 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); 210}; 211 212} // end GR namespace 213 214} // end clang namespace 215 216#endif 217