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