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