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