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