Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 1 | //== AnalysisContext.cpp - Analysis context for Path Sens analysis -*- 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 AnalysisContext, a class that manages the analysis context |
| 11 | // data for path sensitive analysis. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "clang/Analysis/PathSensitive/AnalysisContext.h" |
Ted Kremenek | d02e83a | 2009-12-04 02:03:51 +0000 | [diff] [blame] | 16 | #include "clang/Analysis/PathSensitive/MemRegion.h" |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 17 | #include "clang/Analysis/Analyses/LiveVariables.h" |
| 18 | #include "clang/Analysis/CFG.h" |
| 19 | #include "clang/AST/Decl.h" |
| 20 | #include "clang/AST/DeclObjC.h" |
| 21 | #include "clang/AST/ParentMap.h" |
Ted Kremenek | b1a7b65 | 2009-11-26 02:31:33 +0000 | [diff] [blame] | 22 | #include "clang/AST/StmtVisitor.h" |
| 23 | #include "clang/Analysis/Support/BumpVector.h" |
Mike Stump | 87a05f1 | 2009-07-31 01:10:29 +0000 | [diff] [blame] | 24 | #include "llvm/Support/ErrorHandling.h" |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 25 | |
| 26 | using namespace clang; |
| 27 | |
Ted Kremenek | 58f5ec7 | 2009-10-20 21:39:41 +0000 | [diff] [blame] | 28 | void AnalysisContextManager::clear() { |
| 29 | for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) |
| 30 | delete I->second; |
| 31 | Contexts.clear(); |
| 32 | } |
| 33 | |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 34 | Stmt *AnalysisContext::getBody() { |
Ted Kremenek | 2376002 | 2009-08-21 23:58:43 +0000 | [diff] [blame] | 35 | if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 36 | return FD->getBody(); |
Ted Kremenek | 2376002 | 2009-08-21 23:58:43 +0000 | [diff] [blame] | 37 | else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 38 | return MD->getBody(); |
Ted Kremenek | 30a4534 | 2009-12-04 20:34:55 +0000 | [diff] [blame] | 39 | else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) |
| 40 | return BD->getBody(); |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 41 | |
Mike Stump | 87a05f1 | 2009-07-31 01:10:29 +0000 | [diff] [blame] | 42 | llvm::llvm_unreachable("unknown code decl"); |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 43 | } |
| 44 | |
Ted Kremenek | 82cd37c | 2009-08-21 23:25:54 +0000 | [diff] [blame] | 45 | const ImplicitParamDecl *AnalysisContext::getSelfDecl() const { |
| 46 | if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) |
| 47 | return MD->getSelfDecl(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 48 | |
Ted Kremenek | 82cd37c | 2009-08-21 23:25:54 +0000 | [diff] [blame] | 49 | return NULL; |
| 50 | } |
| 51 | |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 52 | CFG *AnalysisContext::getCFG() { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 53 | if (!cfg) |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 54 | cfg = CFG::buildCFG(getBody(), &D->getASTContext()); |
| 55 | return cfg; |
| 56 | } |
| 57 | |
| 58 | ParentMap &AnalysisContext::getParentMap() { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 59 | if (!PM) |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 60 | PM = new ParentMap(getBody()); |
| 61 | return *PM; |
| 62 | } |
| 63 | |
| 64 | LiveVariables *AnalysisContext::getLiveVariables() { |
| 65 | if (!liveness) { |
| 66 | CFG *c = getCFG(); |
| 67 | if (!c) |
| 68 | return 0; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 69 | |
Ted Kremenek | b1a7b65 | 2009-11-26 02:31:33 +0000 | [diff] [blame] | 70 | liveness = new LiveVariables(*this); |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 71 | liveness->runOnCFG(*c); |
| 72 | liveness->runOnAllBlocks(*c, 0, true); |
| 73 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 74 | |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 75 | return liveness; |
| 76 | } |
| 77 | |
Ted Kremenek | 2376002 | 2009-08-21 23:58:43 +0000 | [diff] [blame] | 78 | AnalysisContext *AnalysisContextManager::getContext(const Decl *D) { |
| 79 | AnalysisContext *&AC = Contexts[D]; |
| 80 | if (!AC) |
| 81 | AC = new AnalysisContext(D); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 82 | |
Ted Kremenek | 2376002 | 2009-08-21 23:58:43 +0000 | [diff] [blame] | 83 | return AC; |
Zhongxing Xu | 97ab394 | 2009-07-30 01:17:21 +0000 | [diff] [blame] | 84 | } |
Zhongxing Xu | 18c7c06 | 2009-08-03 07:23:22 +0000 | [diff] [blame] | 85 | |
Ted Kremenek | d02e83a | 2009-12-04 02:03:51 +0000 | [diff] [blame] | 86 | const BlockDecl *BlockInvocationContext::getBlockDecl() const { |
| 87 | return Data.is<const BlockDataRegion*>() ? |
| 88 | Data.get<const BlockDataRegion*>()->getDecl() |
| 89 | : Data.get<const BlockDecl*>(); |
| 90 | } |
| 91 | |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 92 | //===----------------------------------------------------------------------===// |
| 93 | // FoldingSet profiling. |
| 94 | //===----------------------------------------------------------------------===// |
| 95 | |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 96 | void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, |
| 97 | ContextKind ck, |
| 98 | AnalysisContext *ctx, |
| 99 | const LocationContext *parent, |
| 100 | const void* data) { |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 101 | ID.AddInteger(ck); |
| 102 | ID.AddPointer(ctx); |
| 103 | ID.AddPointer(parent); |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 104 | ID.AddPointer(data); |
Zhongxing Xu | 18c7c06 | 2009-08-03 07:23:22 +0000 | [diff] [blame] | 105 | } |
| 106 | |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 107 | void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { |
| 108 | Profile(ID, getAnalysisContext(), getParent(), CallSite); |
Zhongxing Xu | 18c7c06 | 2009-08-03 07:23:22 +0000 | [diff] [blame] | 109 | } |
| 110 | |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 111 | void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { |
| 112 | Profile(ID, getAnalysisContext(), getParent(), Enter); |
| 113 | } |
| 114 | |
| 115 | void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { |
Ted Kremenek | d02e83a | 2009-12-04 02:03:51 +0000 | [diff] [blame] | 116 | if (const BlockDataRegion *BR = getBlockRegion()) |
| 117 | Profile(ID, getAnalysisContext(), getParent(), BR); |
| 118 | else |
| 119 | Profile(ID, getAnalysisContext(), getParent(), |
| 120 | Data.get<const BlockDecl*>()); |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 121 | } |
| 122 | |
| 123 | //===----------------------------------------------------------------------===// |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 124 | // LocationContext creation. |
Ted Kremenek | dc0d909 | 2009-12-04 00:50:10 +0000 | [diff] [blame] | 125 | //===----------------------------------------------------------------------===// |
| 126 | |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 127 | template <typename LOC, typename DATA> |
| 128 | const LOC* |
| 129 | LocationContextManager::getLocationContext(AnalysisContext *ctx, |
| 130 | const LocationContext *parent, |
| 131 | const DATA *d) { |
| 132 | llvm::FoldingSetNodeID ID; |
| 133 | LOC::Profile(ID, ctx, parent, d); |
| 134 | void *InsertPos; |
Ted Kremenek | 58f5ec7 | 2009-10-20 21:39:41 +0000 | [diff] [blame] | 135 | |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 136 | LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); |
| 137 | |
| 138 | if (!L) { |
| 139 | L = new LOC(ctx, parent, d); |
| 140 | Contexts.InsertNode(L, InsertPos); |
| 141 | } |
| 142 | return L; |
Ted Kremenek | 58f5ec7 | 2009-10-20 21:39:41 +0000 | [diff] [blame] | 143 | } |
| 144 | |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 145 | const StackFrameContext* |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 146 | LocationContextManager::getStackFrame(AnalysisContext *ctx, |
Ted Kremenek | 54c809b | 2009-08-21 23:39:58 +0000 | [diff] [blame] | 147 | const LocationContext *parent, |
| 148 | const Stmt *s) { |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 149 | return getLocationContext<StackFrameContext, Stmt>(ctx, parent, s); |
Zhongxing Xu | 18c7c06 | 2009-08-03 07:23:22 +0000 | [diff] [blame] | 150 | } |
| 151 | |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 152 | const ScopeContext * |
| 153 | LocationContextManager::getScope(AnalysisContext *ctx, |
| 154 | const LocationContext *parent, |
| 155 | const Stmt *s) { |
| 156 | return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); |
| 157 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 158 | |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 159 | const BlockInvocationContext * |
| 160 | LocationContextManager::getBlockInvocation(AnalysisContext *ctx, |
| 161 | const LocationContext *parent, |
Ted Kremenek | d02e83a | 2009-12-04 02:03:51 +0000 | [diff] [blame] | 162 | const BlockDataRegion *BR) { |
| 163 | return getLocationContext<BlockInvocationContext, BlockDataRegion>(ctx, |
| 164 | parent, |
| 165 | BR); |
Zhongxing Xu | 18c7c06 | 2009-08-03 07:23:22 +0000 | [diff] [blame] | 166 | } |
Ted Kremenek | b1a7b65 | 2009-11-26 02:31:33 +0000 | [diff] [blame] | 167 | |
| 168 | //===----------------------------------------------------------------------===// |
Ted Kremenek | 67d1287 | 2009-12-07 22:05:27 +0000 | [diff] [blame] | 169 | // LocationContext methods. |
| 170 | //===----------------------------------------------------------------------===// |
| 171 | |
| 172 | const StackFrameContext *LocationContext::getCurrentStackFrame() const { |
| 173 | const LocationContext *LC = this; |
| 174 | while (LC) { |
| 175 | if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) |
| 176 | return SFC; |
| 177 | LC = LC->getParent(); |
| 178 | } |
| 179 | return NULL; |
| 180 | } |
| 181 | |
| 182 | //===----------------------------------------------------------------------===// |
Ted Kremenek | b1a7b65 | 2009-11-26 02:31:33 +0000 | [diff] [blame] | 183 | // Lazily generated map to query the external variables referenced by a Block. |
| 184 | //===----------------------------------------------------------------------===// |
| 185 | |
| 186 | namespace { |
| 187 | class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ |
| 188 | BumpVector<const VarDecl*> &BEVals; |
| 189 | BumpVectorContext &BC; |
| 190 | public: |
| 191 | FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals, |
| 192 | BumpVectorContext &bc) |
| 193 | : BEVals(bevals), BC(bc) {} |
| 194 | |
| 195 | void VisitStmt(Stmt *S) { |
| 196 | for (Stmt::child_iterator I = S->child_begin(), E = S->child_end();I!=E;++I) |
| 197 | if (Stmt *child = *I) |
| 198 | Visit(child); |
| 199 | } |
| 200 | |
| 201 | void VisitBlockDeclRefExpr(BlockDeclRefExpr *DR) { |
| 202 | if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) |
| 203 | BEVals.push_back(VD, BC); |
| 204 | } |
| 205 | }; |
| 206 | } // end anonymous namespace |
| 207 | |
| 208 | typedef BumpVector<const VarDecl*> DeclVec; |
| 209 | |
| 210 | static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, |
| 211 | void *&Vec, |
| 212 | llvm::BumpPtrAllocator &A) { |
| 213 | if (Vec) |
| 214 | return (DeclVec*) Vec; |
| 215 | |
| 216 | BumpVectorContext BC(A); |
| 217 | DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>(); |
| 218 | new (BV) DeclVec(BC, 10); |
| 219 | |
| 220 | // Find the referenced variables. |
| 221 | FindBlockDeclRefExprsVals F(*BV, BC); |
| 222 | F.Visit(BD->getBody()); |
| 223 | |
| 224 | Vec = BV; |
| 225 | return BV; |
| 226 | } |
| 227 | |
| 228 | std::pair<AnalysisContext::referenced_decls_iterator, |
| 229 | AnalysisContext::referenced_decls_iterator> |
| 230 | AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) { |
| 231 | if (!ReferencedBlockVars) |
| 232 | ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); |
| 233 | |
| 234 | DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); |
| 235 | return std::make_pair(V->begin(), V->end()); |
| 236 | } |
| 237 | |
| 238 | //===----------------------------------------------------------------------===// |
| 239 | // Cleanup. |
| 240 | //===----------------------------------------------------------------------===// |
| 241 | |
| 242 | AnalysisContext::~AnalysisContext() { |
| 243 | delete cfg; |
| 244 | delete liveness; |
| 245 | delete PM; |
| 246 | delete ReferencedBlockVars; |
| 247 | } |
| 248 | |
| 249 | AnalysisContextManager::~AnalysisContextManager() { |
| 250 | for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) |
| 251 | delete I->second; |
| 252 | } |
Ted Kremenek | 0ee4124 | 2009-12-04 01:28:56 +0000 | [diff] [blame] | 253 | |
| 254 | LocationContext::~LocationContext() {} |
| 255 | |
| 256 | LocationContextManager::~LocationContextManager() { |
| 257 | clear(); |
| 258 | } |
| 259 | |
| 260 | void LocationContextManager::clear() { |
| 261 | for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(), |
| 262 | E = Contexts.end(); I != E; ) { |
| 263 | LocationContext *LC = &*I; |
| 264 | ++I; |
| 265 | delete LC; |
| 266 | } |
| 267 | |
| 268 | Contexts.clear(); |
| 269 | } |
| 270 | |