Ted Kremenek | 53ba0b6 | 2009-06-24 23:06:47 +0000 | [diff] [blame] | 1 | //= GRState.cpp - Path-Sensitive "State" for tracking values -----*- C++ -*--=// |
Ted Kremenek | 9153f73 | 2008-02-05 07:17:49 +0000 | [diff] [blame] | 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 | // |
Ted Kremenek | 53ba0b6 | 2009-06-24 23:06:47 +0000 | [diff] [blame] | 10 | // This file implements GRState and GRStateManager. |
Ted Kremenek | 9153f73 | 2008-02-05 07:17:49 +0000 | [diff] [blame] | 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Benjamin Kramer | 5e2d2c2 | 2010-03-27 21:19:47 +0000 | [diff] [blame] | 14 | #include "clang/Analysis/CFG.h" |
Ted Kremenek | 1309f9a | 2010-01-25 04:41:41 +0000 | [diff] [blame] | 15 | #include "clang/Checker/PathSensitive/GRStateTrait.h" |
| 16 | #include "clang/Checker/PathSensitive/GRState.h" |
| 17 | #include "clang/Checker/PathSensitive/GRTransferFuncs.h" |
Chris Lattner | 405674c | 2008-08-23 22:23:37 +0000 | [diff] [blame] | 18 | #include "llvm/Support/raw_ostream.h" |
Ted Kremenek | 05125f1 | 2008-08-27 23:13:01 +0000 | [diff] [blame] | 19 | |
Ted Kremenek | f66ea2cd | 2008-02-04 21:59:22 +0000 | [diff] [blame] | 20 | using namespace clang; |
| 21 | |
Ted Kremenek | 05125f1 | 2008-08-27 23:13:01 +0000 | [diff] [blame] | 22 | // Give the vtable for ConstraintManager somewhere to live. |
Ted Kremenek | 53ba0b6 | 2009-06-24 23:06:47 +0000 | [diff] [blame] | 23 | // FIXME: Move this elsewhere. |
Ted Kremenek | 05125f1 | 2008-08-27 23:13:01 +0000 | [diff] [blame] | 24 | ConstraintManager::~ConstraintManager() {} |
| 25 | |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 26 | GRStateManager::~GRStateManager() { |
| 27 | for (std::vector<GRState::Printer*>::iterator I=Printers.begin(), |
| 28 | E=Printers.end(); I!=E; ++I) |
| 29 | delete *I; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 30 | |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 31 | for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); |
| 32 | I!=E; ++I) |
| 33 | I->second.second(I->second.first); |
| 34 | } |
| 35 | |
Ted Kremenek | 4adc81e | 2008-08-13 04:27:00 +0000 | [diff] [blame] | 36 | const GRState* |
Jordy Rose | 7dadf79 | 2010-07-01 20:09:55 +0000 | [diff] [blame] | 37 | GRStateManager::RemoveDeadBindings(const GRState* state, |
Zhongxing Xu | 17ddf1c | 2010-03-17 03:35:08 +0000 | [diff] [blame] | 38 | const StackFrameContext *LCtx, |
Ted Kremenek | 241677a | 2009-01-21 22:26:05 +0000 | [diff] [blame] | 39 | SymbolReaper& SymReaper) { |
| 40 | |
Ted Kremenek | b87d909 | 2008-02-08 19:17:19 +0000 | [diff] [blame] | 41 | // This code essentially performs a "mark-and-sweep" of the VariableBindings. |
| 42 | // The roots are any Block-level exprs and Decls that our liveness algorithm |
| 43 | // tells us are live. We then see what Decls they may reference, and keep |
| 44 | // those around. This code more than likely can be made faster, and the |
| 45 | // frequency of which this method is called should be experimented with |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 46 | // for optimum performance. |
| 47 | llvm::SmallVector<const MemRegion*, 10> RegionRoots; |
Ted Kremenek | 2ed14be | 2008-12-05 00:47:52 +0000 | [diff] [blame] | 48 | GRState NewState = *state; |
Ted Kremenek | f59bf48 | 2008-07-17 18:38:48 +0000 | [diff] [blame] | 49 | |
Jordy Rose | 7dadf79 | 2010-07-01 20:09:55 +0000 | [diff] [blame] | 50 | NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, SymReaper, |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 51 | state, RegionRoots); |
Ted Kremenek | 016f52f | 2008-02-08 21:10:02 +0000 | [diff] [blame] | 52 | |
Ted Kremenek | f59bf48 | 2008-07-17 18:38:48 +0000 | [diff] [blame] | 53 | // Clean up the store. |
Zhongxing Xu | 5e4cb34 | 2010-08-15 12:45:09 +0000 | [diff] [blame^] | 54 | NewState.St = StoreMgr->RemoveDeadBindings(NewState.St, LCtx, |
| 55 | SymReaper, RegionRoots); |
| 56 | state = getPersistentState(NewState); |
| 57 | return ConstraintMgr->RemoveDeadBindings(state, SymReaper); |
Ted Kremenek | b87d909 | 2008-02-08 19:17:19 +0000 | [diff] [blame] | 58 | } |
Ted Kremenek | 862d5bb | 2008-02-06 00:54:14 +0000 | [diff] [blame] | 59 | |
Zhongxing Xu | 2ce43c8 | 2010-07-22 13:52:13 +0000 | [diff] [blame] | 60 | const GRState *GRStateManager::MarshalState(const GRState *state, |
Zhongxing Xu | d5ef7b2 | 2010-07-23 05:55:01 +0000 | [diff] [blame] | 61 | const StackFrameContext *InitLoc) { |
Zhongxing Xu | 2ce43c8 | 2010-07-22 13:52:13 +0000 | [diff] [blame] | 62 | // make up an empty state for now. |
| 63 | GRState State(this, |
| 64 | EnvMgr.getInitialEnvironment(), |
| 65 | StoreMgr->getInitialStore(InitLoc), |
| 66 | GDMFactory.GetEmptyMap()); |
| 67 | |
| 68 | return getPersistentState(State); |
| 69 | } |
| 70 | |
Ted Kremenek | 76500d0 | 2009-06-23 20:38:51 +0000 | [diff] [blame] | 71 | const GRState *GRState::unbindLoc(Loc LV) const { |
Jordy Rose | a9c7621 | 2010-08-05 03:33:56 +0000 | [diff] [blame] | 72 | assert(!isa<loc::MemRegionVal>(LV) && "Use InvalidateRegion instead."); |
| 73 | |
Ted Kremenek | 76500d0 | 2009-06-23 20:38:51 +0000 | [diff] [blame] | 74 | Store OldStore = getStore(); |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 75 | Store NewStore = getStateManager().StoreMgr->Remove(OldStore, LV); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 76 | |
Ted Kremenek | 4323a57 | 2008-07-10 22:03:41 +0000 | [diff] [blame] | 77 | if (NewStore == OldStore) |
Ted Kremenek | 76500d0 | 2009-06-23 20:38:51 +0000 | [diff] [blame] | 78 | return this; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 79 | |
Jordy Rose | a9c7621 | 2010-08-05 03:33:56 +0000 | [diff] [blame] | 80 | return makeWithStore(NewStore); |
Ted Kremenek | 4323a57 | 2008-07-10 22:03:41 +0000 | [diff] [blame] | 81 | } |
| 82 | |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 83 | SVal GRState::getSValAsScalarOrLoc(const MemRegion *R) const { |
Ted Kremenek | 233e913 | 2009-06-24 22:15:30 +0000 | [diff] [blame] | 84 | // We only want to do fetches from regions that we can actually bind |
| 85 | // values. For example, SymbolicRegions of type 'id<...>' cannot |
| 86 | // have direct bindings (but their can be bindings on their subregions). |
| 87 | if (!R->isBoundable()) |
| 88 | return UnknownVal(); |
| 89 | |
| 90 | if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) { |
Zhongxing Xu | 018220c | 2010-08-11 06:10:55 +0000 | [diff] [blame] | 91 | QualType T = TR->getValueType(); |
Ted Kremenek | 233e913 | 2009-06-24 22:15:30 +0000 | [diff] [blame] | 92 | if (Loc::IsLocType(T) || T->isIntegerType()) |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 93 | return getSVal(R); |
Ted Kremenek | 233e913 | 2009-06-24 22:15:30 +0000 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | return UnknownVal(); |
| 97 | } |
| 98 | |
Ted Kremenek | 4f596c2 | 2009-06-27 00:24:54 +0000 | [diff] [blame] | 99 | |
Ted Kremenek | 8e02934 | 2009-08-27 22:17:37 +0000 | [diff] [blame] | 100 | const GRState *GRState::BindExpr(const Stmt* Ex, SVal V, bool Invalidate) const{ |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 101 | Environment NewEnv = getStateManager().EnvMgr.BindExpr(Env, Ex, V, |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 102 | Invalidate); |
Ted Kremenek | 4f596c2 | 2009-06-27 00:24:54 +0000 | [diff] [blame] | 103 | if (NewEnv == Env) |
| 104 | return this; |
Ted Kremenek | 6d2c657 | 2009-08-27 22:15:20 +0000 | [diff] [blame] | 105 | |
Ted Kremenek | 4f596c2 | 2009-06-27 00:24:54 +0000 | [diff] [blame] | 106 | GRState NewSt = *this; |
| 107 | NewSt.Env = NewEnv; |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 108 | return getStateManager().getPersistentState(NewSt); |
Ted Kremenek | 4f596c2 | 2009-06-27 00:24:54 +0000 | [diff] [blame] | 109 | } |
| 110 | |
Zhongxing Xu | 17fd863 | 2009-08-17 06:19:58 +0000 | [diff] [blame] | 111 | const GRState* GRStateManager::getInitialState(const LocationContext *InitLoc) { |
Ted Kremenek | 6d2c657 | 2009-08-27 22:15:20 +0000 | [diff] [blame] | 112 | GRState State(this, |
Zhongxing Xu | c179a7f | 2010-03-05 04:45:36 +0000 | [diff] [blame] | 113 | EnvMgr.getInitialEnvironment(), |
Zhongxing Xu | 17fd863 | 2009-08-17 06:19:58 +0000 | [diff] [blame] | 114 | StoreMgr->getInitialStore(InitLoc), |
| 115 | GDMFactory.GetEmptyMap()); |
Ted Kremenek | caa3724 | 2008-08-19 16:51:45 +0000 | [diff] [blame] | 116 | |
Zhongxing Xu | 17fd863 | 2009-08-17 06:19:58 +0000 | [diff] [blame] | 117 | return getPersistentState(State); |
Ted Kremenek | 9153f73 | 2008-02-05 07:17:49 +0000 | [diff] [blame] | 118 | } |
| 119 | |
Ted Kremenek | 4adc81e | 2008-08-13 04:27:00 +0000 | [diff] [blame] | 120 | const GRState* GRStateManager::getPersistentState(GRState& State) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 121 | |
Ted Kremenek | 9153f73 | 2008-02-05 07:17:49 +0000 | [diff] [blame] | 122 | llvm::FoldingSetNodeID ID; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 123 | State.Profile(ID); |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 124 | void* InsertPos; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 125 | |
Ted Kremenek | 4adc81e | 2008-08-13 04:27:00 +0000 | [diff] [blame] | 126 | if (GRState* I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) |
Ted Kremenek | 9153f73 | 2008-02-05 07:17:49 +0000 | [diff] [blame] | 127 | return I; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 128 | |
Ted Kremenek | 4adc81e | 2008-08-13 04:27:00 +0000 | [diff] [blame] | 129 | GRState* I = (GRState*) Alloc.Allocate<GRState>(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 130 | new (I) GRState(State); |
Ted Kremenek | 9153f73 | 2008-02-05 07:17:49 +0000 | [diff] [blame] | 131 | StateSet.InsertNode(I, InsertPos); |
| 132 | return I; |
| 133 | } |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 134 | |
Ted Kremenek | 67f2853 | 2009-06-17 22:02:04 +0000 | [diff] [blame] | 135 | const GRState* GRState::makeWithStore(Store store) const { |
| 136 | GRState NewSt = *this; |
Zhongxing Xu | 4193eca | 2008-12-20 06:32:12 +0000 | [diff] [blame] | 137 | NewSt.St = store; |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 138 | return getStateManager().getPersistentState(NewSt); |
Zhongxing Xu | 4193eca | 2008-12-20 06:32:12 +0000 | [diff] [blame] | 139 | } |
| 140 | |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 141 | //===----------------------------------------------------------------------===// |
| 142 | // State pretty-printing. |
| 143 | //===----------------------------------------------------------------------===// |
Ted Kremenek | 461f977 | 2008-03-11 18:57:24 +0000 | [diff] [blame] | 144 | |
Zhongxing Xu | c179a7f | 2010-03-05 04:45:36 +0000 | [diff] [blame] | 145 | void GRState::print(llvm::raw_ostream& Out, CFG &C, const char* nl, |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 146 | const char* sep) const { |
Ted Kremenek | a622d8c | 2008-08-19 22:24:03 +0000 | [diff] [blame] | 147 | // Print the store. |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 148 | GRStateManager &Mgr = getStateManager(); |
| 149 | Mgr.getStoreManager().print(getStore(), Out, nl, sep); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 150 | |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 151 | // Print Subexpression bindings. |
Ted Kremenek | a622d8c | 2008-08-19 22:24:03 +0000 | [diff] [blame] | 152 | bool isFirst = true; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 153 | |
| 154 | for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 155 | if (C.isBlkExpr(I.getKey())) |
| 156 | continue; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 157 | |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 158 | if (isFirst) { |
Ted Kremenek | 59894f9 | 2008-03-04 18:30:35 +0000 | [diff] [blame] | 159 | Out << nl << nl << "Sub-Expressions:" << nl; |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 160 | isFirst = false; |
| 161 | } |
Ted Kremenek | 59894f9 | 2008-03-04 18:30:35 +0000 | [diff] [blame] | 162 | else { Out << nl; } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 163 | |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 164 | Out << " (" << (void*) I.getKey() << ") "; |
Chris Lattner | e4f2142 | 2009-06-30 01:26:17 +0000 | [diff] [blame] | 165 | LangOptions LO; // FIXME. |
| 166 | I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); |
Ted Kremenek | 6f9b3a4 | 2009-07-13 23:53:06 +0000 | [diff] [blame] | 167 | Out << " : " << I.getData(); |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 168 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 169 | |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 170 | // Print block-expression bindings. |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 171 | isFirst = true; |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 172 | |
| 173 | for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { |
| 174 | if (!C.isBlkExpr(I.getKey())) |
| 175 | continue; |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 176 | |
| 177 | if (isFirst) { |
Ted Kremenek | 59894f9 | 2008-03-04 18:30:35 +0000 | [diff] [blame] | 178 | Out << nl << nl << "Block-level Expressions:" << nl; |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 179 | isFirst = false; |
| 180 | } |
Ted Kremenek | 59894f9 | 2008-03-04 18:30:35 +0000 | [diff] [blame] | 181 | else { Out << nl; } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 182 | |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 183 | Out << " (" << (void*) I.getKey() << ") "; |
Chris Lattner | e4f2142 | 2009-06-30 01:26:17 +0000 | [diff] [blame] | 184 | LangOptions LO; // FIXME. |
| 185 | I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); |
Ted Kremenek | 6f9b3a4 | 2009-07-13 23:53:06 +0000 | [diff] [blame] | 186 | Out << " : " << I.getData(); |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 187 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 188 | |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 189 | Mgr.getConstraintManager().print(this, Out, nl, sep); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 190 | |
Ted Kremenek | b65be70 | 2009-06-18 01:23:53 +0000 | [diff] [blame] | 191 | // Print checker-specific data. |
Ted Kremenek | 0fb0bc4 | 2009-08-27 01:39:13 +0000 | [diff] [blame] | 192 | for (std::vector<Printer*>::iterator I = Mgr.Printers.begin(), |
| 193 | E = Mgr.Printers.end(); I != E; ++I) { |
Ted Kremenek | b65be70 | 2009-06-18 01:23:53 +0000 | [diff] [blame] | 194 | (*I)->Print(Out, this, nl, sep); |
| 195 | } |
Ted Kremenek | e7d2211 | 2008-02-11 19:21:59 +0000 | [diff] [blame] | 196 | } |
Ted Kremenek | 729a9a2 | 2008-07-17 23:15:45 +0000 | [diff] [blame] | 197 | |
Zhongxing Xu | c179a7f | 2010-03-05 04:45:36 +0000 | [diff] [blame] | 198 | void GRState::printDOT(llvm::raw_ostream& Out, CFG &C) const { |
| 199 | print(Out, C, "\\l", "\\|"); |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 200 | } |
| 201 | |
Zhongxing Xu | c179a7f | 2010-03-05 04:45:36 +0000 | [diff] [blame] | 202 | void GRState::printStdErr(CFG &C) const { |
| 203 | print(llvm::errs(), C); |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 204 | } |
| 205 | |
Ted Kremenek | 72cd17f | 2008-08-14 21:16:54 +0000 | [diff] [blame] | 206 | //===----------------------------------------------------------------------===// |
| 207 | // Generic Data Map. |
| 208 | //===----------------------------------------------------------------------===// |
| 209 | |
| 210 | void* const* GRState::FindGDM(void* K) const { |
| 211 | return GDM.lookup(K); |
| 212 | } |
| 213 | |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 214 | void* |
| 215 | GRStateManager::FindGDMContext(void* K, |
| 216 | void* (*CreateContext)(llvm::BumpPtrAllocator&), |
| 217 | void (*DeleteContext)(void*)) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 218 | |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 219 | std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; |
| 220 | if (!p.first) { |
| 221 | p.first = CreateContext(Alloc); |
| 222 | p.second = DeleteContext; |
| 223 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 224 | |
Ted Kremenek | 1c72ef0 | 2008-08-16 00:49:49 +0000 | [diff] [blame] | 225 | return p.first; |
| 226 | } |
| 227 | |
Zhongxing Xu | 4230da6 | 2008-11-03 05:18:34 +0000 | [diff] [blame] | 228 | const GRState* GRStateManager::addGDM(const GRState* St, void* Key, void* Data){ |
Ted Kremenek | 72cd17f | 2008-08-14 21:16:54 +0000 | [diff] [blame] | 229 | GRState::GenericDataMap M1 = St->getGDM(); |
| 230 | GRState::GenericDataMap M2 = GDMFactory.Add(M1, Key, Data); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 231 | |
Ted Kremenek | 72cd17f | 2008-08-14 21:16:54 +0000 | [diff] [blame] | 232 | if (M1 == M2) |
| 233 | return St; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 234 | |
Ted Kremenek | 72cd17f | 2008-08-14 21:16:54 +0000 | [diff] [blame] | 235 | GRState NewSt = *St; |
| 236 | NewSt.GDM = M2; |
| 237 | return getPersistentState(NewSt); |
| 238 | } |
Ted Kremenek | 584def7 | 2008-07-22 00:46:16 +0000 | [diff] [blame] | 239 | |
Zhongxing Xu | 0541d10 | 2010-03-25 01:39:39 +0000 | [diff] [blame] | 240 | const GRState *GRStateManager::removeGDM(const GRState *state, void *Key) { |
| 241 | GRState::GenericDataMap OldM = state->getGDM(); |
| 242 | GRState::GenericDataMap NewM = GDMFactory.Remove(OldM, Key); |
| 243 | |
| 244 | if (NewM == OldM) |
| 245 | return state; |
| 246 | |
| 247 | GRState NewState = *state; |
| 248 | NewState.GDM = NewM; |
| 249 | return getPersistentState(NewState); |
| 250 | } |
| 251 | |
Ted Kremenek | 584def7 | 2008-07-22 00:46:16 +0000 | [diff] [blame] | 252 | //===----------------------------------------------------------------------===// |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 253 | // Utility. |
| 254 | //===----------------------------------------------------------------------===// |
| 255 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 256 | namespace { |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 257 | class ScanReachableSymbols : public SubRegionMap::Visitor { |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 258 | typedef llvm::DenseSet<const MemRegion*> VisitedRegionsTy; |
| 259 | |
| 260 | VisitedRegionsTy visited; |
Ted Kremenek | 47fed90 | 2009-06-18 01:33:24 +0000 | [diff] [blame] | 261 | const GRState *state; |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 262 | SymbolVisitor &visitor; |
| 263 | llvm::OwningPtr<SubRegionMap> SRM; |
| 264 | public: |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 265 | |
Ted Kremenek | 47fed90 | 2009-06-18 01:33:24 +0000 | [diff] [blame] | 266 | ScanReachableSymbols(const GRState *st, SymbolVisitor& v) |
| 267 | : state(st), visitor(v) {} |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 268 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 269 | bool scan(nonloc::CompoundVal val); |
| 270 | bool scan(SVal val); |
| 271 | bool scan(const MemRegion *R); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 272 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 273 | // From SubRegionMap::Visitor. |
| 274 | bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) { |
| 275 | return scan(SubRegion); |
| 276 | } |
| 277 | }; |
| 278 | } |
| 279 | |
| 280 | bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 281 | for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 282 | if (!scan(*I)) |
| 283 | return false; |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 284 | |
| 285 | return true; |
| 286 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 287 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 288 | bool ScanReachableSymbols::scan(SVal val) { |
| 289 | if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) |
| 290 | return scan(X->getRegion()); |
Ted Kremenek | 380022d | 2009-03-30 18:45:36 +0000 | [diff] [blame] | 291 | |
Zhongxing Xu | 951b334 | 2010-01-11 07:40:00 +0000 | [diff] [blame] | 292 | if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) |
| 293 | return scan(X->getLoc()); |
| 294 | |
Ted Kremenek | 380022d | 2009-03-30 18:45:36 +0000 | [diff] [blame] | 295 | if (SymbolRef Sym = val.getAsSymbol()) |
| 296 | return visitor.VisitSymbol(Sym); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 297 | |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 298 | if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 299 | return scan(*X); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 300 | |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 301 | return true; |
| 302 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 303 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 304 | bool ScanReachableSymbols::scan(const MemRegion *R) { |
Ted Kremenek | 1cb151e | 2009-03-04 00:13:10 +0000 | [diff] [blame] | 305 | if (isa<MemSpaceRegion>(R) || visited.count(R)) |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 306 | return true; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 307 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 308 | visited.insert(R); |
| 309 | |
| 310 | // If this is a symbolic region, visit the symbol for the region. |
| 311 | if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) |
| 312 | if (!visitor.VisitSymbol(SR->getSymbol())) |
| 313 | return false; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 314 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 315 | // If this is a subregion, also visit the parent regions. |
| 316 | if (const SubRegion *SR = dyn_cast<SubRegion>(R)) |
Ted Kremenek | 6076e0a | 2009-03-03 18:15:30 +0000 | [diff] [blame] | 317 | if (!scan(SR->getSuperRegion())) |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 318 | return false; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 319 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 320 | // Now look at the binding to this region (if any). |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 321 | if (!scan(state->getSValAsScalarOrLoc(R))) |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 322 | return false; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 323 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 324 | // Now look at the subregions. |
| 325 | if (!SRM.get()) |
Zhongxing Xu | f5416bd | 2010-02-05 05:18:47 +0000 | [diff] [blame] | 326 | SRM.reset(state->getStateManager().getStoreManager(). |
| 327 | getSubRegionMap(state->getStore())); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 328 | |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 329 | return SRM->iterSubRegions(R, *this); |
| 330 | } |
| 331 | |
Ted Kremenek | 47fed90 | 2009-06-18 01:33:24 +0000 | [diff] [blame] | 332 | bool GRState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { |
| 333 | ScanReachableSymbols S(this, visitor); |
Ted Kremenek | 5dc2746 | 2009-03-03 02:51:43 +0000 | [diff] [blame] | 334 | return S.scan(val); |
| 335 | } |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 336 | |
Ted Kremenek | 9dce71f | 2009-11-26 02:32:19 +0000 | [diff] [blame] | 337 | bool GRState::scanReachableSymbols(const SVal *I, const SVal *E, |
| 338 | SymbolVisitor &visitor) const { |
| 339 | ScanReachableSymbols S(this, visitor); |
| 340 | for ( ; I != E; ++I) { |
Ted Kremenek | 43f19f7 | 2009-12-01 17:50:25 +0000 | [diff] [blame] | 341 | if (!S.scan(*I)) |
| 342 | return false; |
Ted Kremenek | 9dce71f | 2009-11-26 02:32:19 +0000 | [diff] [blame] | 343 | } |
Ted Kremenek | 43f19f7 | 2009-12-01 17:50:25 +0000 | [diff] [blame] | 344 | return true; |
Ted Kremenek | 9dce71f | 2009-11-26 02:32:19 +0000 | [diff] [blame] | 345 | } |
| 346 | |
| 347 | bool GRState::scanReachableSymbols(const MemRegion * const *I, |
| 348 | const MemRegion * const *E, |
| 349 | SymbolVisitor &visitor) const { |
| 350 | ScanReachableSymbols S(this, visitor); |
| 351 | for ( ; I != E; ++I) { |
Ted Kremenek | 43f19f7 | 2009-12-01 17:50:25 +0000 | [diff] [blame] | 352 | if (!S.scan(*I)) |
| 353 | return false; |
Ted Kremenek | 9dce71f | 2009-11-26 02:32:19 +0000 | [diff] [blame] | 354 | } |
Ted Kremenek | 43f19f7 | 2009-12-01 17:50:25 +0000 | [diff] [blame] | 355 | return true; |
Ted Kremenek | 9dce71f | 2009-11-26 02:32:19 +0000 | [diff] [blame] | 356 | } |