lib/Checker/BasicConstraintManager.cpp

   1 //== BasicConstraintManager.cpp - Manage basic constraints.------*- 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 //  This file defines BasicConstraintManager, a class that tracks simple
  11 //  equality and inequality constraints on symbolic values of GRState.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "SimpleConstraintManager.h"
  16 #include "clang/GR/PathSensitive/GRState.h"
  17 #include "clang/GR/PathSensitive/GRStateTrait.h"
  18 #include "clang/GR/PathSensitive/GRTransferFuncs.h"
  19 #include "llvm/Support/raw_ostream.h"
  20
  21 using namespace clang;
  22
  23
  24 namespace { class ConstNotEq {}; }
  25 namespace { class ConstEq {}; }
  26
  27 typedef llvm::ImmutableMap<SymbolRef,GRState::IntSetTy> ConstNotEqTy;
  28 typedef llvm::ImmutableMap<SymbolRef,const llvm::APSInt*> ConstEqTy;
  29
  30 static int ConstEqIndex = 0;
  31 static int ConstNotEqIndex = 0;
  32
  33 namespace clang {
  34 template<>
  35 struct GRStateTrait<ConstNotEq> : public GRStatePartialTrait<ConstNotEqTy> {
  36   static inline void* GDMIndex() { return &ConstNotEqIndex; }
  37 };
  38
  39 template<>
  40 struct GRStateTrait<ConstEq> : public GRStatePartialTrait<ConstEqTy> {
  41   static inline void* GDMIndex() { return &ConstEqIndex; }
  42 };
  43 }
  44
  45 namespace {
  46 // BasicConstraintManager only tracks equality and inequality constraints of
  47 // constants and integer variables.
  48 class BasicConstraintManager
  49   : public SimpleConstraintManager {
  50   GRState::IntSetTy::Factory ISetFactory;
  51 public:
  52   BasicConstraintManager(GRStateManager &statemgr, GRSubEngine &subengine)
  53     : SimpleConstraintManager(subengine),
  54       ISetFactory(statemgr.getAllocator()) {}
  55
  56   const GRState *assumeSymNE(const GRState* state, SymbolRef sym,
  57                              const llvm::APSInt& V,
  58                              const llvm::APSInt& Adjustment);
  59
  60   const GRState *assumeSymEQ(const GRState* state, SymbolRef sym,
  61                              const llvm::APSInt& V,
  62                              const llvm::APSInt& Adjustment);
  63
  64   const GRState *assumeSymLT(const GRState* state, SymbolRef sym,
  65                              const llvm::APSInt& V,
  66                              const llvm::APSInt& Adjustment);
  67
  68   const GRState *assumeSymGT(const GRState* state, SymbolRef sym,
  69                              const llvm::APSInt& V,
  70                              const llvm::APSInt& Adjustment);
  71
  72   const GRState *assumeSymGE(const GRState* state, SymbolRef sym,
  73                              const llvm::APSInt& V,
  74                              const llvm::APSInt& Adjustment);
  75
  76   const GRState *assumeSymLE(const GRState* state, SymbolRef sym,
  77                              const llvm::APSInt& V,
  78                              const llvm::APSInt& Adjustment);
  79
  80   const GRState* AddEQ(const GRState* state, SymbolRef sym, const llvm::APSInt& V);
  81
  82   const GRState* AddNE(const GRState* state, SymbolRef sym, const llvm::APSInt& V);
  83
  84   const llvm::APSInt* getSymVal(const GRState* state, SymbolRef sym) const;
  85   bool isNotEqual(const GRState* state, SymbolRef sym, const llvm::APSInt& V)
  86       const;
  87   bool isEqual(const GRState* state, SymbolRef sym, const llvm::APSInt& V)
  88       const;
  89
  90   const GRState* RemoveDeadBindings(const GRState* state, SymbolReaper& SymReaper);
  91
  92   void print(const GRState* state, llvm::raw_ostream& Out,
  93              const char* nl, const char *sep);
  94 };
  95
  96 } // end anonymous namespace
  97
  98 ConstraintManager* clang::CreateBasicConstraintManager(GRStateManager& statemgr,
  99                                                        GRSubEngine &subengine) {
 100   return new BasicConstraintManager(statemgr, subengine);
 101 }
 102
 103
 104 const GRState*
 105 BasicConstraintManager::assumeSymNE(const GRState *state, SymbolRef sym,
 106                                     const llvm::APSInt &V,
 107                                     const llvm::APSInt &Adjustment) {
 108   // First, determine if sym == X, where X+Adjustment != V.
 109   llvm::APSInt Adjusted = V-Adjustment;
 110   if (const llvm::APSInt* X = getSymVal(state, sym)) {
 111     bool isFeasible = (*X != Adjusted);
 112     return isFeasible ? state : NULL;
 113   }
 114
 115   // Second, determine if sym+Adjustment != V.
 116   if (isNotEqual(state, sym, Adjusted))
 117     return state;
 118
 119   // If we reach here, sym is not a constant and we don't know if it is != V.
 120   // Make that assumption.
 121   return AddNE(state, sym, Adjusted);
 122 }
 123
 124 const GRState*
 125 BasicConstraintManager::assumeSymEQ(const GRState *state, SymbolRef sym,
 126                                     const llvm::APSInt &V,
 127                                     const llvm::APSInt &Adjustment) {
 128   // First, determine if sym == X, where X+Adjustment != V.
 129   llvm::APSInt Adjusted = V-Adjustment;
 130   if (const llvm::APSInt* X = getSymVal(state, sym)) {
 131     bool isFeasible = (*X == Adjusted);
 132     return isFeasible ? state : NULL;
 133   }
 134
 135   // Second, determine if sym+Adjustment != V.
 136   if (isNotEqual(state, sym, Adjusted))
 137     return NULL;
 138
 139   // If we reach here, sym is not a constant and we don't know if it is == V.
 140   // Make that assumption.
 141   return AddEQ(state, sym, Adjusted);
 142 }
 143
 144 // The logic for these will be handled in another ConstraintManager.
 145 const GRState*
 146 BasicConstraintManager::assumeSymLT(const GRState *state, SymbolRef sym,
 147                                     const llvm::APSInt &V,
 148                                     const llvm::APSInt &Adjustment) {
 149   // Is 'V' the smallest possible value?
 150   if (V == llvm::APSInt::getMinValue(V.getBitWidth(), V.isUnsigned())) {
 151     // sym cannot be any value less than 'V'.  This path is infeasible.
 152     return NULL;
 153   }
 154
 155   // FIXME: For now have assuming x < y be the same as assuming sym != V;
 156   return assumeSymNE(state, sym, V, Adjustment);
 157 }
 158
 159 const GRState*
 160 BasicConstraintManager::assumeSymGT(const GRState *state, SymbolRef sym,
 161                                     const llvm::APSInt &V,
 162                                     const llvm::APSInt &Adjustment) {
 163   // Is 'V' the largest possible value?
 164   if (V == llvm::APSInt::getMaxValue(V.getBitWidth(), V.isUnsigned())) {
 165     // sym cannot be any value greater than 'V'.  This path is infeasible.
 166     return NULL;
 167   }
 168
 169   // FIXME: For now have assuming x > y be the same as assuming sym != V;
 170   return assumeSymNE(state, sym, V, Adjustment);
 171 }
 172
 173 const GRState*
 174 BasicConstraintManager::assumeSymGE(const GRState *state, SymbolRef sym,
 175                                     const llvm::APSInt &V,
 176                                     const llvm::APSInt &Adjustment) {
 177   // Reject a path if the value of sym is a constant X and !(X+Adj >= V).
 178   if (const llvm::APSInt *X = getSymVal(state, sym)) {
 179     bool isFeasible = (*X >= V-Adjustment);
 180     return isFeasible ? state : NULL;
 181   }
 182
 183   // Sym is not a constant, but it is worth looking to see if V is the
 184   // maximum integer value.
 185   if (V == llvm::APSInt::getMaxValue(V.getBitWidth(), V.isUnsigned())) {
 186     llvm::APSInt Adjusted = V-Adjustment;
 187
 188     // If we know that sym != V (after adjustment), then this condition
 189     // is infeasible since there is no other value greater than V.
 190     bool isFeasible = !isNotEqual(state, sym, Adjusted);
 191
 192     // If the path is still feasible then as a consequence we know that
 193     // 'sym+Adjustment == V' because there are no larger values.
 194     // Add this constraint.
 195     return isFeasible ? AddEQ(state, sym, Adjusted) : NULL;
 196   }
 197
 198   return state;
 199 }
 200
 201 const GRState*
 202 BasicConstraintManager::assumeSymLE(const GRState *state, SymbolRef sym,
 203                                     const llvm::APSInt &V,
 204                                     const llvm::APSInt &Adjustment) {
 205   // Reject a path if the value of sym is a constant X and !(X+Adj <= V).
 206   if (const llvm::APSInt* X = getSymVal(state, sym)) {
 207     bool isFeasible = (*X <= V-Adjustment);
 208     return isFeasible ? state : NULL;
 209   }
 210
 211   // Sym is not a constant, but it is worth looking to see if V is the
 212   // minimum integer value.
 213   if (V == llvm::APSInt::getMinValue(V.getBitWidth(), V.isUnsigned())) {
 214     llvm::APSInt Adjusted = V-Adjustment;
 215
 216     // If we know that sym != V (after adjustment), then this condition
 217     // is infeasible since there is no other value less than V.
 218     bool isFeasible = !isNotEqual(state, sym, Adjusted);
 219
 220     // If the path is still feasible then as a consequence we know that
 221     // 'sym+Adjustment == V' because there are no smaller values.
 222     // Add this constraint.
 223     return isFeasible ? AddEQ(state, sym, Adjusted) : NULL;
 224   }
 225
 226   return state;
 227 }
 228
 229 const GRState* BasicConstraintManager::AddEQ(const GRState* state, SymbolRef sym,
 230                                              const llvm::APSInt& V) {
 231   // Create a new state with the old binding replaced.
 232   return state->set<ConstEq>(sym, &state->getBasicVals().getValue(V));
 233 }
 234
 235 const GRState* BasicConstraintManager::AddNE(const GRState* state, SymbolRef sym,
 236                                              const llvm::APSInt& V) {
 237
 238   // First, retrieve the NE-set associated with the given symbol.
 239   ConstNotEqTy::data_type* T = state->get<ConstNotEq>(sym);
 240   GRState::IntSetTy S = T ? *T : ISetFactory.getEmptySet();
 241
 242   // Now add V to the NE set.
 243   S = ISetFactory.add(S, &state->getBasicVals().getValue(V));
 244
 245   // Create a new state with the old binding replaced.
 246   return state->set<ConstNotEq>(sym, S);
 247 }
 248
 249 const llvm::APSInt* BasicConstraintManager::getSymVal(const GRState* state,
 250                                                       SymbolRef sym) const {
 251   const ConstEqTy::data_type* T = state->get<ConstEq>(sym);
 252   return T ? *T : NULL;
 253 }
 254
 255 bool BasicConstraintManager::isNotEqual(const GRState* state, SymbolRef sym,
 256                                         const llvm::APSInt& V) const {
 257
 258   // Retrieve the NE-set associated with the given symbol.
 259   const ConstNotEqTy::data_type* T = state->get<ConstNotEq>(sym);
 260
 261   // See if V is present in the NE-set.
 262   return T ? T->contains(&state->getBasicVals().getValue(V)) : false;
 263 }
 264
 265 bool BasicConstraintManager::isEqual(const GRState* state, SymbolRef sym,
 266                                      const llvm::APSInt& V) const {
 267   // Retrieve the EQ-set associated with the given symbol.
 268   const ConstEqTy::data_type* T = state->get<ConstEq>(sym);
 269   // See if V is present in the EQ-set.
 270   return T ? **T == V : false;
 271 }
 272
 273 /// Scan all symbols referenced by the constraints. If the symbol is not alive
 274 /// as marked in LSymbols, mark it as dead in DSymbols.
 275 const GRState*
 276 BasicConstraintManager::RemoveDeadBindings(const GRState* state,
 277                                            SymbolReaper& SymReaper) {
 278
 279   ConstEqTy CE = state->get<ConstEq>();
 280   ConstEqTy::Factory& CEFactory = state->get_context<ConstEq>();
 281
 282   for (ConstEqTy::iterator I = CE.begin(), E = CE.end(); I!=E; ++I) {
 283     SymbolRef sym = I.getKey();
 284     if (SymReaper.maybeDead(sym))
 285       CE = CEFactory.remove(CE, sym);
 286   }
 287   state = state->set<ConstEq>(CE);
 288
 289   ConstNotEqTy CNE = state->get<ConstNotEq>();
 290   ConstNotEqTy::Factory& CNEFactory = state->get_context<ConstNotEq>();
 291
 292   for (ConstNotEqTy::iterator I = CNE.begin(), E = CNE.end(); I != E; ++I) {
 293     SymbolRef sym = I.getKey();
 294     if (SymReaper.maybeDead(sym))
 295       CNE = CNEFactory.remove(CNE, sym);
 296   }
 297
 298   return state->set<ConstNotEq>(CNE);
 299 }
 300
 301 void BasicConstraintManager::print(const GRState* state, llvm::raw_ostream& Out,
 302                                    const char* nl, const char *sep) {
 303   // Print equality constraints.
 304
 305   ConstEqTy CE = state->get<ConstEq>();
 306
 307   if (!CE.isEmpty()) {
 308     Out << nl << sep << "'==' constraints:";
 309     for (ConstEqTy::iterator I = CE.begin(), E = CE.end(); I!=E; ++I)
 310       Out << nl << " $" << I.getKey() << " : " << *I.getData();
 311   }
 312
 313   // Print != constraints.
 314
 315   ConstNotEqTy CNE = state->get<ConstNotEq>();
 316
 317   if (!CNE.isEmpty()) {
 318     Out << nl << sep << "'!=' constraints:";
 319
 320     for (ConstNotEqTy::iterator I = CNE.begin(), EI = CNE.end(); I!=EI; ++I) {
 321       Out << nl << " $" << I.getKey() << " : ";
 322       bool isFirst = true;
 323
 324       GRState::IntSetTy::iterator J = I.getData().begin(),
 325                                   EJ = I.getData().end();
 326
 327       for ( ; J != EJ; ++J) {
 328         if (isFirst) isFirst = false;
 329         else Out << ", ";
 330
 331         Out << (*J)->getSExtValue(); // Hack: should print to raw_ostream.
 332       }
 333     }
 334   }
 335 }