Home | History | Annotate | Download | only in Analysis 
      1 //== AnalysisDeclContext.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 AnalysisDeclContext, a class that manages the analysis context
     11 // data for path sensitive analysis.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "clang/Analysis/AnalysisContext.h"
     16 #include "BodyFarm.h"
     17 #include "clang/AST/ASTContext.h"
     18 #include "clang/AST/Decl.h"
     19 #include "clang/AST/DeclObjC.h"
     20 #include "clang/AST/DeclTemplate.h"
     21 #include "clang/AST/ParentMap.h"
     22 #include "clang/AST/StmtVisitor.h"
     23 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
     24 #include "clang/Analysis/Analyses/LiveVariables.h"
     25 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
     26 #include "clang/Analysis/CFG.h"
     27 #include "clang/Analysis/CFGStmtMap.h"
     28 #include "clang/Analysis/Support/BumpVector.h"
     29 #include "llvm/ADT/SmallPtrSet.h"
     30 #include "llvm/Support/ErrorHandling.h"
     31 #include "llvm/Support/SaveAndRestore.h"
     32 #include "llvm/Support/raw_ostream.h"
     33 
     34 using namespace clang;
     35 
     36 typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap;
     37 
     38 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
     39                                          const Decl *d,
     40                                          const CFG::BuildOptions &buildOptions)
     41   : Manager(Mgr),
     42     D(d),
     43     cfgBuildOptions(buildOptions),
     44     forcedBlkExprs(nullptr),
     45     builtCFG(false),
     46     builtCompleteCFG(false),
     47     ReferencedBlockVars(nullptr),
     48     ManagedAnalyses(nullptr)
     49 {
     50   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
     51 }
     52 
     53 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
     54                                          const Decl *d)
     55 : Manager(Mgr),
     56   D(d),
     57   forcedBlkExprs(nullptr),
     58   builtCFG(false),
     59   builtCompleteCFG(false),
     60   ReferencedBlockVars(nullptr),
     61   ManagedAnalyses(nullptr)
     62 {
     63   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
     64 }
     65 
     66 AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
     67                                                        bool addImplicitDtors,
     68                                                        bool addInitializers,
     69                                                        bool addTemporaryDtors,
     70                                                        bool synthesizeBodies,
     71                                                        bool addStaticInitBranch,
     72                                                        bool addCXXNewAllocator,
     73                                                        CodeInjector *injector)
     74   : Injector(injector), SynthesizeBodies(synthesizeBodies)
     75 {
     76   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
     77   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
     78   cfgBuildOptions.AddInitializers = addInitializers;
     79   cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
     80   cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
     81   cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
     82 }
     83 
     84 void AnalysisDeclContextManager::clear() {
     85   llvm::DeleteContainerSeconds(Contexts);
     86 }
     87 
     88 static BodyFarm &getBodyFarm(ASTContext &C, CodeInjector *injector = nullptr) {
     89   static BodyFarm *BF = new BodyFarm(C, injector);
     90   return *BF;
     91 }
     92 
     93 Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const {
     94   IsAutosynthesized = false;
     95   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
     96     Stmt *Body = FD->getBody();
     97     if (!Body && Manager && Manager->synthesizeBodies()) {
     98       Body = getBodyFarm(getASTContext(), Manager->Injector.get()).getBody(FD);
     99       if (Body)
    100         IsAutosynthesized = true;
    101     }
    102     return Body;
    103   }
    104   else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
    105     Stmt *Body = MD->getBody();
    106     if (!Body && Manager && Manager->synthesizeBodies()) {
    107       Body = getBodyFarm(getASTContext(), Manager->Injector.get()).getBody(MD);
    108       if (Body)
    109         IsAutosynthesized = true;
    110     }
    111     return Body;
    112   } else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D))
    113     return BD->getBody();
    114   else if (const FunctionTemplateDecl *FunTmpl
    115            = dyn_cast_or_null<FunctionTemplateDecl>(D))
    116     return FunTmpl->getTemplatedDecl()->getBody();
    117 
    118   llvm_unreachable("unknown code decl");
    119 }
    120 
    121 Stmt *AnalysisDeclContext::getBody() const {
    122   bool Tmp;
    123   return getBody(Tmp);
    124 }
    125 
    126 bool AnalysisDeclContext::isBodyAutosynthesized() const {
    127   bool Tmp;
    128   getBody(Tmp);
    129   return Tmp;
    130 }
    131 
    132 bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
    133   bool Tmp;
    134   Stmt *Body = getBody(Tmp);
    135   return Tmp && Body->getLocStart().isValid();
    136 }
    137 
    138 
    139 const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
    140   if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
    141     return MD->getSelfDecl();
    142   if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
    143     // See if 'self' was captured by the block.
    144     for (const auto &I : BD->captures()) {
    145       const VarDecl *VD = I.getVariable();
    146       if (VD->getName() == "self")
    147         return dyn_cast<ImplicitParamDecl>(VD);
    148     }
    149   }
    150 
    151   return nullptr;
    152 }
    153 
    154 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
    155   if (!forcedBlkExprs)
    156     forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
    157   // Default construct an entry for 'stmt'.
    158   if (const Expr *e = dyn_cast<Expr>(stmt))
    159     stmt = e->IgnoreParens();
    160   (void) (*forcedBlkExprs)[stmt];
    161 }
    162 
    163 const CFGBlock *
    164 AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
    165   assert(forcedBlkExprs);
    166   if (const Expr *e = dyn_cast<Expr>(stmt))
    167     stmt = e->IgnoreParens();
    168   CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
    169     forcedBlkExprs->find(stmt);
    170   assert(itr != forcedBlkExprs->end());
    171   return itr->second;
    172 }
    173 
    174 /// Add each synthetic statement in the CFG to the parent map, using the
    175 /// source statement's parent.
    176 static void addParentsForSyntheticStmts(const CFG *TheCFG, ParentMap &PM) {
    177   if (!TheCFG)
    178     return;
    179 
    180   for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
    181                                     E = TheCFG->synthetic_stmt_end();
    182        I != E; ++I) {
    183     PM.setParent(I->first, PM.getParent(I->second));
    184   }
    185 }
    186 
    187 CFG *AnalysisDeclContext::getCFG() {
    188   if (!cfgBuildOptions.PruneTriviallyFalseEdges)
    189     return getUnoptimizedCFG();
    190 
    191   if (!builtCFG) {
    192     cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
    193     // Even when the cfg is not successfully built, we don't
    194     // want to try building it again.
    195     builtCFG = true;
    196 
    197     if (PM)
    198       addParentsForSyntheticStmts(cfg.get(), *PM);
    199 
    200     // The Observer should only observe one build of the CFG.
    201     getCFGBuildOptions().Observer = nullptr;
    202   }
    203   return cfg.get();
    204 }
    205 
    206 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
    207   if (!builtCompleteCFG) {
    208     SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
    209                                   false);
    210     completeCFG =
    211         CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
    212     // Even when the cfg is not successfully built, we don't
    213     // want to try building it again.
    214     builtCompleteCFG = true;
    215 
    216     if (PM)
    217       addParentsForSyntheticStmts(completeCFG.get(), *PM);
    218 
    219     // The Observer should only observe one build of the CFG.
    220     getCFGBuildOptions().Observer = nullptr;
    221   }
    222   return completeCFG.get();
    223 }
    224 
    225 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
    226   if (cfgStmtMap)
    227     return cfgStmtMap.get();
    228 
    229   if (CFG *c = getCFG()) {
    230     cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
    231     return cfgStmtMap.get();
    232   }
    233 
    234   return nullptr;
    235 }
    236 
    237 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
    238   if (CFA)
    239     return CFA.get();
    240 
    241   if (CFG *c = getCFG()) {
    242     CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
    243     return CFA.get();
    244   }
    245 
    246   return nullptr;
    247 }
    248 
    249 void AnalysisDeclContext::dumpCFG(bool ShowColors) {
    250     getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
    251 }
    252 
    253 ParentMap &AnalysisDeclContext::getParentMap() {
    254   if (!PM) {
    255     PM.reset(new ParentMap(getBody()));
    256     if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
    257       for (const auto *I : C->inits()) {
    258         PM->addStmt(I->getInit());
    259       }
    260     }
    261     if (builtCFG)
    262       addParentsForSyntheticStmts(getCFG(), *PM);
    263     if (builtCompleteCFG)
    264       addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
    265   }
    266   return *PM;
    267 }
    268 
    269 PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() {
    270   if (!PCA)
    271     PCA.reset(new PseudoConstantAnalysis(getBody()));
    272   return PCA.get();
    273 }
    274 
    275 AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
    276   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
    277     // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
    278     // that has the body.
    279     FD->hasBody(FD);
    280     D = FD;
    281   }
    282 
    283   AnalysisDeclContext *&AC = Contexts[D];
    284   if (!AC)
    285     AC = new AnalysisDeclContext(this, D, cfgBuildOptions);
    286   return AC;
    287 }
    288 
    289 const StackFrameContext *
    290 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
    291                                const CFGBlock *Blk, unsigned Idx) {
    292   return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
    293 }
    294 
    295 const BlockInvocationContext *
    296 AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
    297                                                const clang::BlockDecl *BD,
    298                                                const void *ContextData) {
    299   return getLocationContextManager().getBlockInvocationContext(this, parent,
    300                                                                BD, ContextData);
    301 }
    302 
    303 LocationContextManager & AnalysisDeclContext::getLocationContextManager() {
    304   assert(Manager &&
    305          "Cannot create LocationContexts without an AnalysisDeclContextManager!");
    306   return Manager->getLocationContextManager();
    307 }
    308 
    309 //===----------------------------------------------------------------------===//
    310 // FoldingSet profiling.
    311 //===----------------------------------------------------------------------===//
    312 
    313 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
    314                                     ContextKind ck,
    315                                     AnalysisDeclContext *ctx,
    316                                     const LocationContext *parent,
    317                                     const void *data) {
    318   ID.AddInteger(ck);
    319   ID.AddPointer(ctx);
    320   ID.AddPointer(parent);
    321   ID.AddPointer(data);
    322 }
    323 
    324 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
    325   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
    326 }
    327 
    328 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
    329   Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
    330 }
    331 
    332 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
    333   Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
    334 }
    335 
    336 //===----------------------------------------------------------------------===//
    337 // LocationContext creation.
    338 //===----------------------------------------------------------------------===//
    339 
    340 template <typename LOC, typename DATA>
    341 const LOC*
    342 LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
    343                                            const LocationContext *parent,
    344                                            const DATA *d) {
    345   llvm::FoldingSetNodeID ID;
    346   LOC::Profile(ID, ctx, parent, d);
    347   void *InsertPos;
    348 
    349   LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
    350 
    351   if (!L) {
    352     L = new LOC(ctx, parent, d);
    353     Contexts.InsertNode(L, InsertPos);
    354   }
    355   return L;
    356 }
    357 
    358 const StackFrameContext*
    359 LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
    360                                       const LocationContext *parent,
    361                                       const Stmt *s,
    362                                       const CFGBlock *blk, unsigned idx) {
    363   llvm::FoldingSetNodeID ID;
    364   StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
    365   void *InsertPos;
    366   StackFrameContext *L =
    367    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
    368   if (!L) {
    369     L = new StackFrameContext(ctx, parent, s, blk, idx);
    370     Contexts.InsertNode(L, InsertPos);
    371   }
    372   return L;
    373 }
    374 
    375 const ScopeContext *
    376 LocationContextManager::getScope(AnalysisDeclContext *ctx,
    377                                  const LocationContext *parent,
    378                                  const Stmt *s) {
    379   return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
    380 }
    381 
    382 const BlockInvocationContext *
    383 LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
    384                                                   const LocationContext *parent,
    385                                                   const BlockDecl *BD,
    386                                                   const void *ContextData) {
    387   llvm::FoldingSetNodeID ID;
    388   BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
    389   void *InsertPos;
    390   BlockInvocationContext *L =
    391     cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
    392                                                                     InsertPos));
    393   if (!L) {
    394     L = new BlockInvocationContext(ctx, parent, BD, ContextData);
    395     Contexts.InsertNode(L, InsertPos);
    396   }
    397   return L;
    398 }
    399 
    400 //===----------------------------------------------------------------------===//
    401 // LocationContext methods.
    402 //===----------------------------------------------------------------------===//
    403 
    404 const StackFrameContext *LocationContext::getCurrentStackFrame() const {
    405   const LocationContext *LC = this;
    406   while (LC) {
    407     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC))
    408       return SFC;
    409     LC = LC->getParent();
    410   }
    411   return nullptr;
    412 }
    413 
    414 bool LocationContext::inTopFrame() const {
    415   return getCurrentStackFrame()->inTopFrame();
    416 }
    417 
    418 bool LocationContext::isParentOf(const LocationContext *LC) const {
    419   do {
    420     const LocationContext *Parent = LC->getParent();
    421     if (Parent == this)
    422       return true;
    423     else
    424       LC = Parent;
    425   } while (LC);
    426 
    427   return false;
    428 }
    429 
    430 void LocationContext::dumpStack(raw_ostream &OS, StringRef Indent) const {
    431   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
    432   PrintingPolicy PP(Ctx.getLangOpts());
    433   PP.TerseOutput = 1;
    434 
    435   unsigned Frame = 0;
    436   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
    437     switch (LCtx->getKind()) {
    438     case StackFrame:
    439       OS << Indent << '#' << Frame++ << ' ';
    440       cast<StackFrameContext>(LCtx)->getDecl()->print(OS, PP);
    441       OS << '\n';
    442       break;
    443     case Scope:
    444       OS << Indent << "    (scope)\n";
    445       break;
    446     case Block:
    447       OS << Indent << "    (block context: "
    448                    << cast<BlockInvocationContext>(LCtx)->getContextData()
    449                    << ")\n";
    450       break;
    451     }
    452   }
    453 }
    454 
    455 LLVM_DUMP_METHOD void LocationContext::dumpStack() const {
    456   dumpStack(llvm::errs());
    457 }
    458 
    459 //===----------------------------------------------------------------------===//
    460 // Lazily generated map to query the external variables referenced by a Block.
    461 //===----------------------------------------------------------------------===//
    462 
    463 namespace {
    464 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
    465   BumpVector<const VarDecl*> &BEVals;
    466   BumpVectorContext &BC;
    467   llvm::SmallPtrSet<const VarDecl*, 4> Visited;
    468   llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts;
    469 public:
    470   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
    471                             BumpVectorContext &bc)
    472   : BEVals(bevals), BC(bc) {}
    473 
    474   void VisitStmt(Stmt *S) {
    475     for (Stmt::child_range I = S->children(); I; ++I)
    476       if (Stmt *child = *I)
    477         Visit(child);
    478   }
    479 
    480   void VisitDeclRefExpr(DeclRefExpr *DR) {
    481     // Non-local variables are also directly modified.
    482     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
    483       if (!VD->hasLocalStorage()) {
    484         if (Visited.insert(VD).second)
    485           BEVals.push_back(VD, BC);
    486       }
    487     }
    488   }
    489 
    490   void VisitBlockExpr(BlockExpr *BR) {
    491     // Blocks containing blocks can transitively capture more variables.
    492     IgnoredContexts.insert(BR->getBlockDecl());
    493     Visit(BR->getBlockDecl()->getBody());
    494   }
    495 
    496   void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
    497     for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
    498          et = PE->semantics_end(); it != et; ++it) {
    499       Expr *Semantic = *it;
    500       if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
    501         Semantic = OVE->getSourceExpr();
    502       Visit(Semantic);
    503     }
    504   }
    505 };
    506 } // end anonymous namespace
    507 
    508 typedef BumpVector<const VarDecl*> DeclVec;
    509 
    510 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
    511                                               void *&Vec,
    512                                               llvm::BumpPtrAllocator &A) {
    513   if (Vec)
    514     return (DeclVec*) Vec;
    515 
    516   BumpVectorContext BC(A);
    517   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
    518   new (BV) DeclVec(BC, 10);
    519 
    520   // Go through the capture list.
    521   for (const auto &CI : BD->captures()) {
    522     BV->push_back(CI.getVariable(), BC);
    523   }
    524 
    525   // Find the referenced global/static variables.
    526   FindBlockDeclRefExprsVals F(*BV, BC);
    527   F.Visit(BD->getBody());
    528 
    529   Vec = BV;
    530   return BV;
    531 }
    532 
    533 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
    534 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
    535   if (!ReferencedBlockVars)
    536     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
    537 
    538   const DeclVec *V =
    539       LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
    540   return llvm::make_range(V->begin(), V->end());
    541 }
    542 
    543 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
    544   if (!ManagedAnalyses)
    545     ManagedAnalyses = new ManagedAnalysisMap();
    546   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
    547   return (*M)[tag];
    548 }
    549 
    550 //===----------------------------------------------------------------------===//
    551 // Cleanup.
    552 //===----------------------------------------------------------------------===//
    553 
    554 ManagedAnalysis::~ManagedAnalysis() {}
    555 
    556 AnalysisDeclContext::~AnalysisDeclContext() {
    557   delete forcedBlkExprs;
    558   delete ReferencedBlockVars;
    559   // Release the managed analyses.
    560   if (ManagedAnalyses) {
    561     ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
    562     llvm::DeleteContainerSeconds(*M);
    563     delete M;
    564   }
    565 }
    566 
    567 AnalysisDeclContextManager::~AnalysisDeclContextManager() {
    568   llvm::DeleteContainerSeconds(Contexts);
    569 }
    570 
    571 LocationContext::~LocationContext() {}
    572 
    573 LocationContextManager::~LocationContextManager() {
    574   clear();
    575 }
    576 
    577 void LocationContextManager::clear() {
    578   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
    579        E = Contexts.end(); I != E; ) {
    580     LocationContext *LC = &*I;
    581     ++I;
    582     delete LC;
    583   }
    584 
    585   Contexts.clear();
    586 }
    587 
    588