contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp

   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/AST/Decl.h"
  16 #include "clang/AST/DeclObjC.h"
  17 #include "clang/AST/DeclTemplate.h"
  18 #include "clang/AST/ParentMap.h"
  19 #include "clang/AST/StmtVisitor.h"
  20 #include "clang/Analysis/Analyses/LiveVariables.h"
  21 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
  22 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
  23 #include "clang/Analysis/AnalysisContext.h"
  24 #include "clang/Analysis/CFG.h"
  25 #include "clang/Analysis/CFGStmtMap.h"
  26 #include "clang/Analysis/Support/BumpVector.h"
  27 #include "clang/Analysis/Support/SaveAndRestore.h"
  28 #include "llvm/ADT/SmallSet.h"
  29 #include "llvm/Support/ErrorHandling.h"
  30
  31 using namespace clang;
  32
  33 typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap;
  34
  35 AnalysisContext::AnalysisContext(const Decl *d,
  36                                  idx::TranslationUnit *tu,
  37                                  const CFG::BuildOptions &buildOptions)
  38   : D(d), TU(tu),
  39     cfgBuildOptions(buildOptions),
  40     forcedBlkExprs(0),
  41     builtCFG(false),
  42     builtCompleteCFG(false),
  43     ReferencedBlockVars(0),
  44     ManagedAnalyses(0)
  45 {
  46   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
  47 }
  48
  49 AnalysisContext::AnalysisContext(const Decl *d,
  50                                  idx::TranslationUnit *tu)
  51 : D(d), TU(tu),
  52   forcedBlkExprs(0),
  53   builtCFG(false),
  54   builtCompleteCFG(false),
  55   ReferencedBlockVars(0),
  56   ManagedAnalyses(0)
  57 {
  58   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
  59 }
  60
  61 AnalysisContextManager::AnalysisContextManager(bool useUnoptimizedCFG,
  62                                                bool addImplicitDtors,
  63                                                bool addInitializers) {
  64   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
  65   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
  66   cfgBuildOptions.AddInitializers = addInitializers;
  67 }
  68
  69 void AnalysisContextManager::clear() {
  70   for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I)
  71     delete I->second;
  72   Contexts.clear();
  73 }
  74
  75 Stmt *AnalysisContext::getBody() const {
  76   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
  77     return FD->getBody();
  78   else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
  79     return MD->getBody();
  80   else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D))
  81     return BD->getBody();
  82   else if (const FunctionTemplateDecl *FunTmpl
  83            = dyn_cast_or_null<FunctionTemplateDecl>(D))
  84     return FunTmpl->getTemplatedDecl()->getBody();
  85
  86   llvm_unreachable("unknown code decl");
  87 }
  88
  89 const ImplicitParamDecl *AnalysisContext::getSelfDecl() const {
  90   if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
  91     return MD->getSelfDecl();
  92
  93   return NULL;
  94 }
  95
  96 void AnalysisContext::registerForcedBlockExpression(const Stmt *stmt) {
  97   if (!forcedBlkExprs)
  98     forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
  99   // Default construct an entry for 'stmt'.
 100   if (const Expr *e = dyn_cast<Expr>(stmt))
 101     stmt = e->IgnoreParens();
 102   (void) (*forcedBlkExprs)[stmt];
 103 }
 104
 105 const CFGBlock *
 106 AnalysisContext::getBlockForRegisteredExpression(const Stmt *stmt) {
 107   assert(forcedBlkExprs);
 108   if (const Expr *e = dyn_cast<Expr>(stmt))
 109     stmt = e->IgnoreParens();
 110   CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
 111     forcedBlkExprs->find(stmt);
 112   assert(itr != forcedBlkExprs->end());
 113   return itr->second;
 114 }
 115
 116 CFG *AnalysisContext::getCFG() {
 117   if (!cfgBuildOptions.PruneTriviallyFalseEdges)
 118     return getUnoptimizedCFG();
 119
 120   if (!builtCFG) {
 121     cfg.reset(CFG::buildCFG(D, getBody(),
 122                             &D->getASTContext(), cfgBuildOptions));
 123     // Even when the cfg is not successfully built, we don't
 124     // want to try building it again.
 125     builtCFG = true;
 126   }
 127   return cfg.get();
 128 }
 129
 130 CFG *AnalysisContext::getUnoptimizedCFG() {
 131   if (!builtCompleteCFG) {
 132     SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
 133                                   false);
 134     completeCFG.reset(CFG::buildCFG(D, getBody(), &D->getASTContext(),
 135                                     cfgBuildOptions));
 136     // Even when the cfg is not successfully built, we don't
 137     // want to try building it again.
 138     builtCompleteCFG = true;
 139   }
 140   return completeCFG.get();
 141 }
 142
 143 CFGStmtMap *AnalysisContext::getCFGStmtMap() {
 144   if (cfgStmtMap)
 145     return cfgStmtMap.get();
 146
 147   if (CFG *c = getCFG()) {
 148     cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
 149     return cfgStmtMap.get();
 150   }
 151
 152   return 0;
 153 }
 154
 155 CFGReverseBlockReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() {
 156   if (CFA)
 157     return CFA.get();
 158
 159   if (CFG *c = getCFG()) {
 160     CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
 161     return CFA.get();
 162   }
 163
 164   return 0;
 165 }
 166
 167 void AnalysisContext::dumpCFG() {
 168     getCFG()->dump(getASTContext().getLangOptions());
 169 }
 170
 171 ParentMap &AnalysisContext::getParentMap() {
 172   if (!PM)
 173     PM.reset(new ParentMap(getBody()));
 174   return *PM;
 175 }
 176
 177 PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() {
 178   if (!PCA)
 179     PCA.reset(new PseudoConstantAnalysis(getBody()));
 180   return PCA.get();
 181 }
 182
 183 AnalysisContext *AnalysisContextManager::getContext(const Decl *D,
 184                                                     idx::TranslationUnit *TU) {
 185   AnalysisContext *&AC = Contexts[D];
 186   if (!AC)
 187     AC = new AnalysisContext(D, TU, cfgBuildOptions);
 188   return AC;
 189 }
 190
 191 //===----------------------------------------------------------------------===//
 192 // FoldingSet profiling.
 193 //===----------------------------------------------------------------------===//
 194
 195 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
 196                                     ContextKind ck,
 197                                     AnalysisContext *ctx,
 198                                     const LocationContext *parent,
 199                                     const void *data) {
 200   ID.AddInteger(ck);
 201   ID.AddPointer(ctx);
 202   ID.AddPointer(parent);
 203   ID.AddPointer(data);
 204 }
 205
 206 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
 207   Profile(ID, getAnalysisContext(), getParent(), CallSite, Block, Index);
 208 }
 209
 210 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
 211   Profile(ID, getAnalysisContext(), getParent(), Enter);
 212 }
 213
 214 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
 215   Profile(ID, getAnalysisContext(), getParent(), BD);
 216 }
 217
 218 //===----------------------------------------------------------------------===//
 219 // LocationContext creation.
 220 //===----------------------------------------------------------------------===//
 221
 222 template <typename LOC, typename DATA>
 223 const LOC*
 224 LocationContextManager::getLocationContext(AnalysisContext *ctx,
 225                                            const LocationContext *parent,
 226                                            const DATA *d) {
 227   llvm::FoldingSetNodeID ID;
 228   LOC::Profile(ID, ctx, parent, d);
 229   void *InsertPos;
 230
 231   LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
 232
 233   if (!L) {
 234     L = new LOC(ctx, parent, d);
 235     Contexts.InsertNode(L, InsertPos);
 236   }
 237   return L;
 238 }
 239
 240 const StackFrameContext*
 241 LocationContextManager::getStackFrame(AnalysisContext *ctx,
 242                                       const LocationContext *parent,
 243                                       const Stmt *s,
 244                                       const CFGBlock *blk, unsigned idx) {
 245   llvm::FoldingSetNodeID ID;
 246   StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
 247   void *InsertPos;
 248   StackFrameContext *L =
 249    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
 250   if (!L) {
 251     L = new StackFrameContext(ctx, parent, s, blk, idx);
 252     Contexts.InsertNode(L, InsertPos);
 253   }
 254   return L;
 255 }
 256
 257 const ScopeContext *
 258 LocationContextManager::getScope(AnalysisContext *ctx,
 259                                  const LocationContext *parent,
 260                                  const Stmt *s) {
 261   return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
 262 }
 263
 264 //===----------------------------------------------------------------------===//
 265 // LocationContext methods.
 266 //===----------------------------------------------------------------------===//
 267
 268 const StackFrameContext *LocationContext::getCurrentStackFrame() const {
 269   const LocationContext *LC = this;
 270   while (LC) {
 271     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC))
 272       return SFC;
 273     LC = LC->getParent();
 274   }
 275   return NULL;
 276 }
 277
 278 const StackFrameContext *
 279 LocationContext::getStackFrameForDeclContext(const DeclContext *DC) const {
 280   const LocationContext *LC = this;
 281   while (LC) {
 282     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
 283       if (cast<DeclContext>(SFC->getDecl()) == DC)
 284         return SFC;
 285     }
 286     LC = LC->getParent();
 287   }
 288   return NULL;
 289 }
 290
 291 bool LocationContext::isParentOf(const LocationContext *LC) const {
 292   do {
 293     const LocationContext *Parent = LC->getParent();
 294     if (Parent == this)
 295       return true;
 296     else
 297       LC = Parent;
 298   } while (LC);
 299
 300   return false;
 301 }
 302
 303 //===----------------------------------------------------------------------===//
 304 // Lazily generated map to query the external variables referenced by a Block.
 305 //===----------------------------------------------------------------------===//
 306
 307 namespace {
 308 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
 309   BumpVector<const VarDecl*> &BEVals;
 310   BumpVectorContext &BC;
 311   llvm::DenseMap<const VarDecl*, unsigned> Visited;
 312   llvm::SmallSet<const DeclContext*, 4> IgnoredContexts;
 313 public:
 314   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
 315                             BumpVectorContext &bc)
 316   : BEVals(bevals), BC(bc) {}
 317
 318   bool IsTrackedDecl(const VarDecl *VD) {
 319     const DeclContext *DC = VD->getDeclContext();
 320     return IgnoredContexts.count(DC) == 0;
 321   }
 322
 323   void VisitStmt(Stmt *S) {
 324     for (Stmt::child_range I = S->children(); I; ++I)
 325       if (Stmt *child = *I)
 326         Visit(child);
 327   }
 328
 329   void VisitDeclRefExpr(const DeclRefExpr *DR) {
 330     // Non-local variables are also directly modified.
 331     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
 332       if (!VD->hasLocalStorage()) {
 333         unsigned &flag = Visited[VD];
 334         if (!flag) {
 335           flag = 1;
 336           BEVals.push_back(VD, BC);
 337         }
 338       }
 339   }
 340
 341   void VisitBlockDeclRefExpr(BlockDeclRefExpr *DR) {
 342     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 343       unsigned &flag = Visited[VD];
 344       if (!flag) {
 345         flag = 1;
 346         if (IsTrackedDecl(VD))
 347           BEVals.push_back(VD, BC);
 348       }
 349     }
 350   }
 351
 352   void VisitBlockExpr(BlockExpr *BR) {
 353     // Blocks containing blocks can transitively capture more variables.
 354     IgnoredContexts.insert(BR->getBlockDecl());
 355     Visit(BR->getBlockDecl()->getBody());
 356   }
 357 };
 358 } // end anonymous namespace
 359
 360 typedef BumpVector<const VarDecl*> DeclVec;
 361
 362 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
 363                                               void *&Vec,
 364                                               llvm::BumpPtrAllocator &A) {
 365   if (Vec)
 366     return (DeclVec*) Vec;
 367
 368   BumpVectorContext BC(A);
 369   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
 370   new (BV) DeclVec(BC, 10);
 371
 372   // Find the referenced variables.
 373   FindBlockDeclRefExprsVals F(*BV, BC);
 374   F.Visit(BD->getBody());
 375
 376   Vec = BV;
 377   return BV;
 378 }
 379
 380 std::pair<AnalysisContext::referenced_decls_iterator,
 381           AnalysisContext::referenced_decls_iterator>
 382 AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) {
 383   if (!ReferencedBlockVars)
 384     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
 385
 386   DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
 387   return std::make_pair(V->begin(), V->end());
 388 }
 389
 390 ManagedAnalysis *&AnalysisContext::getAnalysisImpl(const void *tag) {
 391   if (!ManagedAnalyses)
 392     ManagedAnalyses = new ManagedAnalysisMap();
 393   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
 394   return (*M)[tag];
 395 }
 396
 397 //===----------------------------------------------------------------------===//
 398 // Cleanup.
 399 //===----------------------------------------------------------------------===//
 400
 401 ManagedAnalysis::~ManagedAnalysis() {}
 402
 403 AnalysisContext::~AnalysisContext() {
 404   delete forcedBlkExprs;
 405   delete ReferencedBlockVars;
 406   // Release the managed analyses.
 407   if (ManagedAnalyses) {
 408     ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
 409     for (ManagedAnalysisMap::iterator I = M->begin(), E = M->end(); I!=E; ++I)
 410       delete I->second;
 411     delete M;
 412   }
 413 }
 414
 415 AnalysisContextManager::~AnalysisContextManager() {
 416   for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I)
 417     delete I->second;
 418 }
 419
 420 LocationContext::~LocationContext() {}
 421
 422 LocationContextManager::~LocationContextManager() {
 423   clear();
 424 }
 425
 426 void LocationContextManager::clear() {
 427   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
 428        E = Contexts.end(); I != E; ) {
 429     LocationContext *LC = &*I;
 430     ++I;
 431     delete LC;
 432   }
 433
 434   Contexts.clear();
 435 }
 436