Home | History | Annotate | Download | only in Analysis 
      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 
    437