[analyzer] Add checker callback for beginning of function.

[dcoughlin]

Summary

Add a checker callback that is called when the analyzer starts analyzing a
function either at the top level or when inlined. This will be used by a
follow-on patch making the DeallocChecker path sensitive.

[zaks.anna]

LGTM with a request for a tiny other improvement in the documentation.
Thanks!

include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h

111

Is this called for non-inlined functions? It would be worth updating the comments for this one as well.

include/clang/Analysis/ProgramPoint.h

public:
   const Stmt *getCallExpr() const {
     return static_cast<const Stmt *>(getData1());
   }
 
   const StackFrameContext *getCalleeContext() const {
     return static_cast<const StackFrameContext *>(getData2());
   }
 
+  /// Returns the entry block in the CFG for the entered function.
+  const CFGBlock *getEntry() const {
+    const StackFrameContext *CalleeCtx = getCalleeContext();
+    const CFG *CalleeCFG = CalleeCtx->getCFG();
+    return &(CalleeCFG->getEntry());
+  }
+
 private:
   friend class ProgramPoint;
   CallEnter() {}
   static bool isKind(const ProgramPoint &Location) {
     return Location.getKind() == CallEnterKind;
   }
 };
 

include/clang/StaticAnalyzer/Core/Checker.h

 public:
   template <typename CHECKER>
   static void _register(CHECKER *checker, CheckerManager &mgr) {
     mgr._registerForEndAnalysis(
      CheckerManager::CheckEndAnalysisFunc(checker, _checkEndAnalysis<CHECKER>));
   }
 };
 
+class BeginFunction {
+  template <typename CHECKER>
+  static void _checkBeginFunction(void *checker, CheckerContext &C) {
+    ((const CHECKER *)checker)->checkBeginFunction(C);
+  }
+
+public:
+  template <typename CHECKER>
+  static void _register(CHECKER *checker, CheckerManager &mgr) {
+    mgr._registerForBeginFunction(CheckerManager::CheckBeginFunctionFunc(
+        checker, _checkBeginFunction<CHECKER>));
+  }
+};
+
 class EndFunction {
   template <typename CHECKER>
   static void _checkEndFunction(void *checker,
                                 CheckerContext &C) {
     ((const CHECKER *)checker)->checkEndFunction(C);
   }
 
 public:

include/clang/StaticAnalyzer/Core/CheckerManager.h

void runCheckersForBind(ExplodedNodeSet &Dst,
                           SVal location, SVal val,
                           const Stmt *S, ExprEngine &Eng,
                           const ProgramPoint &PP);
 
   /// \brief Run checkers for end of analysis.
   void runCheckersForEndAnalysis(ExplodedGraph &G, BugReporter &BR,
                                  ExprEngine &Eng);
 
+  /// \brief Run checkers on begining of function.
+  void runCheckersForBeginFunction(ExplodedNodeSet &Dst,
+                                   const BlockEdge &L,
+                                   ExplodedNode *Pred,
+                                   ExprEngine &Eng);
+
   /// \brief Run checkers on end of function.
   void runCheckersForEndFunction(NodeBuilderContext &BC,
                                  ExplodedNodeSet &Dst,
                                  ExplodedNode *Pred,
                                  ExprEngine &Eng);
 
   /// \brief Run checkers for branch condition.
   void runCheckersForBranchCondition(const Stmt *condition,
typedef CheckerFn<void (const SVal &location, bool isLoad,
       CheckLocationFunc;
   
   typedef CheckerFn<void (const SVal &location, const SVal &val, 
                           const Stmt *S, CheckerContext &)> 
       CheckBindFunc;
   
   typedef CheckerFn<void (ExplodedGraph &, BugReporter &, ExprEngine &)>
       CheckEndAnalysisFunc;
-  
   typedef CheckerFn<void (CheckerContext &)>
+      CheckBeginFunctionFunc;
+
+  typedef CheckerFn<void (CheckerContext &)>
       CheckEndFunctionFunc;
   
   typedef CheckerFn<void (const Stmt *, CheckerContext &)>
       CheckBranchConditionFunc;
   
   typedef CheckerFn<void (SymbolReaper &, CheckerContext &)>
       CheckDeadSymbolsFunc;
   
//===----------------------------------------------------------------------===//
   void _registerForPostCall(CheckCallFunc checkfn);
 
   void _registerForLocation(CheckLocationFunc checkfn);
 
   void _registerForBind(CheckBindFunc checkfn);
 
   void _registerForEndAnalysis(CheckEndAnalysisFunc checkfn);
 
+  void _registerForBeginFunction(CheckEndFunctionFunc checkfn);
   void _registerForEndFunction(CheckEndFunctionFunc checkfn);
 
   void _registerForBranchCondition(CheckBranchConditionFunc checkfn);
 
   void _registerForLiveSymbols(CheckLiveSymbolsFunc checkfn);
 
   void _registerForDeadSymbols(CheckDeadSymbolsFunc checkfn);
 
private:
   std::vector<CheckCallFunc> PostCallCheckers;
 
   std::vector<CheckLocationFunc> LocationCheckers;
 
   std::vector<CheckBindFunc> BindCheckers;
 
   std::vector<CheckEndAnalysisFunc> EndAnalysisCheckers;
 
+  std::vector<CheckBeginFunctionFunc> BeginFunctionCheckers;
   std::vector<CheckEndFunctionFunc> EndFunctionCheckers;
 
   std::vector<CheckBranchConditionFunc> BranchConditionCheckers;
 
   std::vector<CheckLiveSymbolsFunc> LiveSymbolsCheckers;
 
   std::vector<CheckDeadSymbolsFunc> DeadSymbolsCheckers;
 

include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h

private:
 
   void generateNode(const ProgramPoint &Loc,
                     ProgramStateRef State,
                     ExplodedNode *Pred);
 
   void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
   void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
   void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
+
+  void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred);
+
   void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
 
   void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
                     ExplodedNode *Pred);
   void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
                                     const CFGBlock *B, ExplodedNode *Pred);
 
   /// Handle conditional logic for running static initializers.

include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

public:
   /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
   ///  nodes by processing the 'effects' of a computed goto jump.
   void processIndirectGoto(IndirectGotoNodeBuilder& builder) override;
 
   /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
   ///  nodes by processing the 'effects' of a switch statement.
   void processSwitch(SwitchNodeBuilder& builder) override;
 
+  /// Called by CoreEngine.  Used to notify checkers that processing a
+  /// function has begun. Called for both inlined and and top-level functions.
+  void processBeginOfFunction(NodeBuilderContext &BC,
+                              ExplodedNode *Pred, ExplodedNodeSet &Dst,
+                              const BlockEdge &L) override;
+
   /// Called by CoreEngine.  Used to generate end-of-path
   /// nodes when the control reaches the end of a function.
   void processEndOfFunction(NodeBuilderContext& BC,
                             ExplodedNode *Pred) override;
 
   /// Remove dead bindings/symbols before exiting a function.
   void removeDeadOnEndOfFunction(NodeBuilderContext& BC,
                                  ExplodedNode *Pred,
                                  ExplodedNodeSet &Dst);
 
   /// Generate the entry node of the callee.
-  void processCallEnter(CallEnter CE, ExplodedNode *Pred) override;
+  void processCallEnter(NodeBuilderContext& BC, CallEnter CE,
+                        ExplodedNode *Pred) override;
 
   /// Generate the sequence of nodes that simulate the call exit and the post
   /// visit for CallExpr.
   void processCallExit(ExplodedNode *Pred) override;
 
   /// Called by CoreEngine when the analysis worklist has terminated.
   void processEndWorklist(bool hasWorkRemaining) override;
 

include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h

public:
   /// Called by CoreEngine.  Used to generate successor
   /// nodes by processing the 'effects' of a computed goto jump.
   virtual void processIndirectGoto(IndirectGotoNodeBuilder& builder) = 0;
 
   /// Called by CoreEngine.  Used to generate successor
   /// nodes by processing the 'effects' of a switch statement.
   virtual void processSwitch(SwitchNodeBuilder& builder) = 0;
 
+  /// Called by CoreEngine.  Used to notify checkers that processing a
+  /// function has begun. Called for both inlined and and top-level functions.
+  virtual void processBeginOfFunction(NodeBuilderContext &BC,
+                                      ExplodedNode *Pred,
+                                      ExplodedNodeSet &Dst,
+                                      const BlockEdge &L) = 0;
+
   /// Called by CoreEngine.  Used to generate end-of-path
   /// nodes when the control reaches the end of a function.
   virtual void processEndOfFunction(NodeBuilderContext& BC,
                                     ExplodedNode *Pred) = 0;
 
   // Generate the entry node of the callee.
-  virtual void processCallEnter(CallEnter CE, ExplodedNode *Pred) = 0;
+  virtual void processCallEnter(NodeBuilderContext& BC, CallEnter CE,
+                                ExplodedNode *Pred) = 0;
 
   // Generate the first post callsite node.
   virtual void processCallExit(ExplodedNode *Pred) = 0;
 
   /// Called by ConstraintManager. Used to call checker-specific
   /// logic for handling assumptions on symbolic values.
   virtual ProgramStateRef processAssume(ProgramStateRef state,
                                        SVal cond, bool assumption) = 0;

lib/StaticAnalyzer/Checkers/CheckerDocumentation.cpp

public:
   /// variable is not freed right after it goes out of scope.)
   ///
   /// \param SR The SymbolReaper object can be queried to determine which
   ///           symbols are dead.
   ///
   /// check::DeadSymbols
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const {}
 
+
+  /// \brief Called when the analyzer core starts analyzing a function,
+  /// regardless of whether it is analyzed at the top level or is inlined.
+  ///
+  /// check::BeginFunction
+  void checkBeginFunction(CheckerContext &Ctx) const {}
+
   /// \brief Called when the analyzer core reaches the end of a
   /// function being analyzed.
   ///
   /// check::EndFunction
   void checkEndFunction(CheckerContext &Ctx) const {}
 
   /// \brief Called after all the paths in the ExplodedGraph reach end of path
   /// - the symbolic execution graph is fully explored.

lib/StaticAnalyzer/Checkers/TraversalChecker.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class TraversalDumper : public Checker< check::BranchCondition,
+                                        check::BeginFunction,
                                         check::EndFunction > {
 public:
   void checkBranchCondition(const Stmt *Condition, CheckerContext &C) const;
+  void checkBeginFunction(CheckerContext &C) const;
   void checkEndFunction(CheckerContext &C) const;
 };
 }
 
 void TraversalDumper::checkBranchCondition(const Stmt *Condition,
                                            CheckerContext &C) const {
   // Special-case Objective-C's for-in loop, which uses the entire loop as its
   // condition. We just print the collection expression.
   const Stmt *Parent = dyn_cast<ObjCForCollectionStmt>(Condition);
   if (!Parent) {
     const ParentMap &Parents = C.getLocationContext()->getParentMap();
     Parent = Parents.getParent(Condition);
   }
 
   // It is mildly evil to print directly to llvm::outs() rather than emitting
   // warnings, but this ensures things do not get filtered out by the rest of
   // the static analyzer machinery.
   SourceLocation Loc = Parent->getLocStart();
   llvm::outs() << C.getSourceManager().getSpellingLineNumber(Loc) << " "
                << Parent->getStmtClassName() << "\n";
 }
 
+void TraversalDumper::checkBeginFunction(CheckerContext &C) const {
+  llvm::outs() << "--BEGIN FUNCTION--\n";
+}
+
 void TraversalDumper::checkEndFunction(CheckerContext &C) const {
   llvm::outs() << "--END FUNCTION--\n";
 }
 
 void ento::registerTraversalDumper(CheckerManager &mgr) {
   mgr.registerChecker<TraversalDumper>();
 }
 

lib/StaticAnalyzer/Core/CheckerManager.cpp

 
 void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
                                                BugReporter &BR,
                                                ExprEngine &Eng) {
   for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
     EndAnalysisCheckers[i](G, BR, Eng);
 }
 
+namespace {
+struct CheckBeginFunctionContext {
+  typedef std::vector<CheckerManager::CheckBeginFunctionFunc> CheckersTy;
+  const CheckersTy &Checkers;
+  ExprEngine &Eng;
+  const ProgramPoint &PP;
+
+  CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
+  CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
+
+  CheckBeginFunctionContext(const CheckersTy &Checkers, ExprEngine &Eng,
+                            const ProgramPoint &PP)
+      : Checkers(Checkers), Eng(Eng), PP(PP) {}
+
+  void runChecker(CheckerManager::CheckBeginFunctionFunc checkFn,
+                  NodeBuilder &Bldr, ExplodedNode *Pred) {
+    const ProgramPoint &L = PP.withTag(checkFn.Checker);
+    CheckerContext C(Bldr, Eng, Pred, L);
+
+    checkFn(C);
+  }
+};
+}
+
+void CheckerManager::runCheckersForBeginFunction(ExplodedNodeSet &Dst,
+                                                 const BlockEdge &L,
+                                                 ExplodedNode *Pred,
+                                                 ExprEngine &Eng) {
+  ExplodedNodeSet Src;
+  Src.insert(Pred);
+  CheckBeginFunctionContext C(BeginFunctionCheckers, Eng, L);
+  expandGraphWithCheckers(C, Dst, Src);
+}
+
 /// \brief Run checkers for end of path.
 // Note, We do not chain the checker output (like in expandGraphWithCheckers)
 // for this callback since end of path nodes are expected to be final.
 void CheckerManager::runCheckersForEndFunction(NodeBuilderContext &BC,
                                                ExplodedNodeSet &Dst,
                                                ExplodedNode *Pred,
                                                ExprEngine &Eng) {
 

 void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
   BindCheckers.push_back(checkfn);
 }
 
 void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
   EndAnalysisCheckers.push_back(checkfn);
 }
 
+void CheckerManager::_registerForBeginFunction(CheckBeginFunctionFunc checkfn) {
+  BeginFunctionCheckers.push_back(checkfn);
+}
+
 void CheckerManager::_registerForEndFunction(CheckEndFunctionFunc checkfn) {
   EndFunctionCheckers.push_back(checkfn);
 }
 
 void CheckerManager::_registerForBranchCondition(
                                              CheckBranchConditionFunc checkfn) {
   BranchConditionCheckers.push_back(checkfn);
 }

lib/StaticAnalyzer/Core/CoreEngine.cpp

if (G.num_roots() == 0) { // Initialize the analysis by constructing
     // Construct an edge representing the
     // starting location in the function.
     BlockEdge StartLoc(Entry, Succ, L);
 
     // Set the current block counter to being empty.
     WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
 
     if (!InitState)
-      // Generate the root.
-      generateNode(StartLoc, SubEng.getInitialState(L), nullptr);
-    else
-      generateNode(StartLoc, InitState, nullptr);
+      InitState = SubEng.getInitialState(L);
+
+    bool IsNew;
+    ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
+    assert (IsNew);
+    G.addRoot(Node);
+
+    NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
+    ExplodedNodeSet DstBegin;
+    SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
+
+    enqueue(DstBegin);
   }
 
   // Check if we have a steps limit
   bool UnlimitedSteps = Steps == 0;
 
   while (WList->hasWork()) {
     if (!UnlimitedSteps) {
       if (Steps == 0) {
case ProgramPoint::BlockEntranceKind:
       HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
       break;
 
     case ProgramPoint::BlockExitKind:
       assert (false && "BlockExit location never occur in forward analysis.");
       break;
 
     case ProgramPoint::CallEnterKind: {
-      CallEnter CEnter = Loc.castAs<CallEnter>();
-      SubEng.processCallEnter(CEnter, Pred);
+      HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
       break;
     }
 
     case ProgramPoint::CallExitBeginKind:
       SubEng.processCallExit(Pred);
       break;
 
     case ProgramPoint::EpsilonKind: {
void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
 
   assert (B->succ_size() == 1 &&
           "Blocks with no terminator should have at most 1 successor.");
 
   generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
                Pred->State, Pred);
 }
 
+void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
+  NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
+  SubEng.processCallEnter(BuilderCtx, CE, Pred);
+}
+
 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
                                 const CFGBlock * B, ExplodedNode *Pred) {
   assert(B->succ_size() == 2);
   NodeBuilderContext Ctx(*this, B, Pred);
   ExplodedNodeSet Dst;
   SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
                        *(B->succ_begin()), *(B->succ_begin()+1));
   // Enqueue the new frontier onto the worklist.

lib/StaticAnalyzer/Core/ExprEngine.cpp

 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
 #include "llvm/ADT/ImmutableList.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/SaveAndRestore.h"
 
 #ifndef NDEBUG
 #include "llvm/Support/GraphWriter.h"
 #endif
 
 using namespace clang;
 using namespace ento;
 using llvm::APSInt;
return std::find_if(Set.begin(), Set.end(),
                           Ctx.first->dump();
                           llvm::errs() << "\n";
                         }
            return Ctx.second == Frame;
          }) == Set.end();
 }
 #endif
 
+void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
+                                        ExplodedNode *Pred,
+                                        ExplodedNodeSet &Dst,
+                                        const BlockEdge &L) {
+  SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
+  getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
+}
+
 /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
 ///  nodes when the control reaches the end of a function.
 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
                                       ExplodedNode *Pred) {
   // FIXME: Assert that stackFrameDoesNotContainInitializedTemporaries(*Pred)).
   // We currently cannot enable this assert, as lifetime extended temporaries
   // are not modelled correctly.
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());

lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

STATISTIC(NumOfDynamicDispatchPathSplits,
   "The # of times we split the path due to imprecise dynamic dispatch info");
 
 STATISTIC(NumInlinedCalls,
   "The # of times we inlined a call");
 
 STATISTIC(NumReachedInlineCountMax,
   "The # of times we reached inline count maximum");
 
-void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
+void ExprEngine::processCallEnter(NodeBuilderContext& BC, CallEnter CE,
+                                  ExplodedNode *Pred) {
   // Get the entry block in the CFG of the callee.
   const StackFrameContext *calleeCtx = CE.getCalleeContext();
   PrettyStackTraceLocationContext CrashInfo(calleeCtx);
-
-  const CFG *CalleeCFG = calleeCtx->getCFG();
-  const CFGBlock *Entry = &(CalleeCFG->getEntry());
+  const CFGBlock *Entry = CE.getEntry();
 
   // Validate the CFG.
   assert(Entry->empty());
   assert(Entry->succ_size() == 1);
 
   // Get the solitary successor.
   const CFGBlock *Succ = *(Entry->succ_begin());
 
   // Construct an edge representing the starting location in the callee.
   BlockEdge Loc(Entry, Succ, calleeCtx);
 
   ProgramStateRef state = Pred->getState();
 
   // Construct a new node and add it to the worklist.
   bool isNew;
   ExplodedNode *Node = G.getNode(Loc, state, false, &isNew);
   Node->addPredecessor(Pred, G);
-  if (isNew)
-    Engine.getWorkList()->enqueue(Node);
+  if (isNew) {
+    ExplodedNodeSet DstBegin;
+    processBeginOfFunction(BC, Node, DstBegin, Loc);
+    Engine.enqueue(DstBegin);
+  }
 }
 
 // Find the last statement on the path to the exploded node and the
 // corresponding Block.
 static std::pair<const Stmt*,
                  const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
   const Stmt *S = nullptr;
   const CFGBlock *Blk = nullptr;

test/Analysis/traversal-begin-end-function.c

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,debug.DumpTraversal %s | FileCheck %s
+
+void inline_callee(int i);
+
+// CHECK: --BEGIN FUNCTION--
+void inline_caller() {
+  // CHECK: --BEGIN FUNCTION--
+  // CHECK: --BEGIN FUNCTION--
+  // CHECK: --BEGIN FUNCTION--
+  inline_callee(3);
+  // CHECK: --END FUNCTION--
+  // CHECK: --END FUNCTION--
+  // CHECK: --END FUNCTION--
+}
+// CHECK: --END FUNCTION--
+
+void inline_callee(int i) {
+  if (i <= 1)
+    return;
+
+  inline_callee(i - 1);
+}

test/Analysis/traversal-path-unification.c

 // RUN: %clang_cc1 -analyze -analyzer-checker=core,debug.DumpTraversal %s | FileCheck %s
 // RUN: %clang_cc1 -analyze -analyzer-checker=core,debug.DumpTraversal -DUSE_EXPR %s | FileCheck %s
 
 int a();
 int b();
 int c();
 
 #ifdef USE_EXPR
 #define CHECK(x) ((x) & 1)
 #else
 #define CHECK(x) (x)
 #endif
 
+// CHECK: --BEGIN FUNCTION--
 void testRemoveDeadBindings() {
   int i = a();
   if (CHECK(i))
     a();
   else
     b();
 
   // At this point the symbol bound to 'i' is dead.
   // The effects of a() and b() are identical (they both invalidate globals).
   // We should unify the two paths here and only get one end-of-path node.
   c();
 }
 
 // CHECK: --END FUNCTION--
 // CHECK-NOT: --END FUNCTION--