RangedConstraintManager.h revision 336979
133965Sjdp//== RangedConstraintManager.h ----------------------------------*- C++ -*--==// 233965Sjdp// 333965Sjdp// The LLVM Compiler Infrastructure 433965Sjdp// 533965Sjdp// This file is distributed under the University of Illinois Open Source 633965Sjdp// License. See LICENSE.TXT for details. 733965Sjdp// 833965Sjdp//===----------------------------------------------------------------------===// 933965Sjdp// 1033965Sjdp// Ranged constraint manager, built on SimpleConstraintManager. 1133965Sjdp// 1233965Sjdp//===----------------------------------------------------------------------===// 1333965Sjdp 1433965Sjdp#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 1533965Sjdp#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 1633965Sjdp 1733965Sjdp#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 1838889Sjdp#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 1933965Sjdp#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" 2033965Sjdp 2133965Sjdpnamespace clang { 2238889Sjdp 2333965Sjdpnamespace ento { 2433965Sjdp 2533965Sjdp/// A Range represents the closed range [from, to]. The caller must 2660484Sobrien/// guarantee that from <= to. Note that Range is immutable, so as not 2733965Sjdp/// to subvert RangeSet's immutability. 2833965Sjdpclass Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { 2933965Sjdppublic: 3077298Sobrien Range(const llvm::APSInt &from, const llvm::APSInt &to) 3177298Sobrien : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { 3233965Sjdp assert(from <= to); 3333965Sjdp } 3433965Sjdp bool Includes(const llvm::APSInt &v) const { 3533965Sjdp return *first <= v && v <= *second; 3633965Sjdp } 3733965Sjdp const llvm::APSInt &From() const { return *first; } 3833965Sjdp const llvm::APSInt &To() const { return *second; } 3933965Sjdp const llvm::APSInt *getConcreteValue() const { 4033965Sjdp return &From() == &To() ? &From() : nullptr; 4133965Sjdp } 4233965Sjdp 4333965Sjdp void Profile(llvm::FoldingSetNodeID &ID) const { 4433965Sjdp ID.AddPointer(&From()); 4533965Sjdp ID.AddPointer(&To()); 4633965Sjdp } 4733965Sjdp}; 4833965Sjdp 4933965Sjdpclass RangeTrait : public llvm::ImutContainerInfo<Range> { 5033965Sjdppublic: 5177298Sobrien // When comparing if one Range is less than another, we should compare 5277298Sobrien // the actual APSInt values instead of their pointers. This keeps the order 5377298Sobrien // consistent (instead of comparing by pointer values) and can potentially 5477298Sobrien // be used to speed up some of the operations in RangeSet. 5533965Sjdp static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 5633965Sjdp return *lhs.first < *rhs.first || 5733965Sjdp (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); 5833965Sjdp } 5933965Sjdp}; 6033965Sjdp 6133965Sjdp/// RangeSet contains a set of ranges. If the set is empty, then 6233965Sjdp/// there the value of a symbol is overly constrained and there are no 6333965Sjdp/// possible values for that symbol. 6433965Sjdpclass RangeSet { 6533965Sjdp typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; 6633965Sjdp PrimRangeSet ranges; // no need to make const, since it is an 6733965Sjdp // ImmutableSet - this allows default operator= 6833965Sjdp // to work. 6933965Sjdppublic: 7033965Sjdp typedef PrimRangeSet::Factory Factory; 7133965Sjdp typedef PrimRangeSet::iterator iterator; 7260484Sobrien 7360484Sobrien RangeSet(PrimRangeSet RS) : ranges(RS) {} 7433965Sjdp 7533965Sjdp /// Create a new set with all ranges of this set and RS. 7633965Sjdp /// Possible intersections are not checked here. 7733965Sjdp RangeSet addRange(Factory &F, const RangeSet &RS) { 7833965Sjdp 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() { static int Index; return &Index; } 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