[analyzer] Treat functions without runtime branches as "small".

[NoQ]

Summary

Currently we always inline functions that have no branches, i.e. have exactly three CFG blocks: ENTRY, some code, EXIT. This makes sense because when there are no branches, it means that there's no exponential complexity introduced by inlining such function. Such functions also don't trigger various fundamental problems with our inlining mechanism, such as the problem of inlined defensive checks.

Sometimes the CFG may contain more blocks, but in practice it still has linear structure because all directions (except, at most, one) of all branches turned out to be unreachable. When this happens, still treat the function as "small".

This is useful, in particular, for dealing with C++17 if constexpr.

[Szelethus]

Nice! I have no objections (other than the nits) to this! Ill take a second look later, because I really need to play around with CFG a bit to give a definitive LGTM.

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

723 ↗

(On Diff #196366)

Your explanation of state splitting, and early returns and the like could be added here as well :)

clang/lib/Analysis/CFG.cpp

4684 ↗

(On Diff #196366)

What are the cases for the size being 2 or 1? Empty function? Is a size of 1 even possible? Can we enforce something here with asserts?

4686 ↗

(On Diff #196366)

Break TODO to new line.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

890 ↗

(On Diff #196366)

Nice.

clang/test/Analysis/inline-if-constexpr.cpp

16 ↗

(On Diff #196366)

Aha, we wouldve seen UNKNOWN because the analyzer wouldn't inline these many functions, right? Neat!

clang/unittests/Analysis/CFGTest.cpp

117 ↗

(On Diff #196366)

What do you mean?

[NoQ]

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

723 ↗

(On Diff #196366)

This function can be controlled through -analyzer-config, which breaks the explanation. I guess i'll put it inside the body.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

890 ↗

(On Diff #196366)

Whoops, that was actually accidental.

clang/test/Analysis/inline-if-constexpr.cpp

16 ↗

(On Diff #196366)

Aha, yup.

[NoQ]

Fxd.

clang/lib/Analysis/CFG.cpp

4684 ↗

(On Diff #196366)

An empty function, i.e. void foo() {}, has two CFG blocks. Every CFG has (by construction) at least an ENTRY and an EXIT, but i don't think this is the right place to introduce such sanity check.

clang/test/Analysis/inline-if-constexpr.cpp

16 ↗

(On Diff #196366)

Hardcoded the max stack depth count to make this more apparent and prevent the test from not testing anything if it's bumped.

[Charusso]

Great patch! There is only a design problem:
You have negated every isSmall() condition looks like you could write isLarge() instead but there is no connection between these functions.
Could you rename or redesign them? The following would be cool: isLarge() iff !isSmalll and isSmall() iff !isLarge().

[NoQ]

In D61051#1481976, @Charusso wrote:

Great patch! There is only a design problem:
You have negated every isSmall() condition looks like you could write isLarge() instead but there is no connection between these functions.
Could you rename or redesign them? The following would be cool: isLarge() iff !isSmalll and isSmall() iff !isLarge().

We essentially classify functions into small/medium/large/huge. In this sense !isSmall() may mean medium or large or huge, while isLarge() may mean large or huge.
I guess i'll comment this up.

[NoQ]

Crystallize the isHuge() function and document more stuff.

[Szelethus]

I mean, better late then never, but LGTM :^)

include/clang/Analysis/CFG.h

public:
   /// Returns the total number of BlockIDs allocated (which start at 0).
   unsigned getNumBlockIDs() const { return NumBlockIDs; }
 
   /// Return the total number of CFGBlocks within the CFG This is simply a
   /// renaming of the getNumBlockIDs(). This is necessary because the dominator
   /// implementation needs such an interface.
   unsigned size() const { return NumBlockIDs; }
 
+  /// Returns true if the CFG has no branches. Usually it boils down to the CFG
+  /// having exactly three blocks (entry, the actual code, exit), but sometimes
+  /// more blocks appear due to having control flow that can be fully
+  /// resolved in compile time.
+  bool isLinear() const;
+
   //===--------------------------------------------------------------------===//
   // CFG Debugging: Pretty-Printing and Visualization.
   //===--------------------------------------------------------------------===//
 
   void viewCFG(const LangOptions &LO) const;
   void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
   void dump(const LangOptions &LO, bool ShowColors) const;
 

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

private:
 
   /// See if a particular call should be inlined, by only looking
   /// at the call event and the current state of analysis.
   CallInlinePolicy mayInlineCallKind(const CallEvent &Call,
                                      const ExplodedNode *Pred,
                                      AnalyzerOptions &Opts,
                                      const EvalCallOptions &CallOpts);
 
+  /// See if the given AnalysisDeclContext is built for a function that we
+  /// should always inline simply because it's small enough.
+  /// Apart from "small" functions, we also have "large" functions
+  /// (cf. isLarge()), some of which are huge (cf. isHuge()), and we classify
+  /// the remaining functions as "medium".
+  bool isSmall(AnalysisDeclContext *ADC) const;
+
+  /// See if the given AnalysisDeclContext is built for a function that we
+  /// should inline carefully because it looks pretty large.
+  bool isLarge(AnalysisDeclContext *ADC) const;
+
+  /// See if the given AnalysisDeclContext is built for a function that we
+  /// should never inline because it's legit gigantic.
+  bool isHuge(AnalysisDeclContext *ADC) const;
+
+  /// See if the given AnalysisDeclContext is built for a function that we
+  /// should inline, just by looking at the declaration of the function.
+  bool mayInlineDecl(AnalysisDeclContext *ADC) const;
+
   /// Checks our policies and decides weither the given call should be inlined.
   bool shouldInlineCall(const CallEvent &Call, const Decl *D,
                         const ExplodedNode *Pred,
                         const EvalCallOptions &CallOpts = {});
 
   bool inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
                   ExplodedNode *Pred, ProgramStateRef State);
 

lib/Analysis/CFG.cpp

 
 /// buildCFG - Constructs a CFG from an AST.
 std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
                                    ASTContext *C, const BuildOptions &BO) {
   CFGBuilder Builder(C, BO);
   return Builder.buildCFG(D, Statement);
 }
 
+bool CFG::isLinear() const {
+  // Quick path: if we only have the ENTRY block, the EXIT block, and some code
+  // in between, then we have no room for control flow.
+  if (size() <= 3)
+    return true;
+
+  // Traverse the CFG until we find a branch.
+  // TODO: While this should still be very fast,
+  // maybe we should cache the answer.
+  llvm::SmallPtrSet<const CFGBlock *, 4> Visited;
+  const CFGBlock *B = Entry;
+  while (B != Exit) {
+    auto IteratorAndFlag = Visited.insert(B);
+    if (!IteratorAndFlag.second) {
+      // We looped back to a block that we've already visited. Not linear.
+      return false;
+    }
+
+    // Iterate over reachable successors.
+    const CFGBlock *FirstReachableB = nullptr;
+    for (const CFGBlock::AdjacentBlock &AB : B->succs()) {
+      if (!AB.isReachable())
+        continue;
+
+      if (FirstReachableB == nullptr) {
+        FirstReachableB = &*AB;
+      } else {
+        // We've encountered a branch. It's not a linear CFG.
+        return false;
+      }
+    }
+
+    if (!FirstReachableB) {
+      // We reached a dead end. EXIT is unreachable. This is linear enough.
+      return true;
+    }
+
+    // There's only one way to move forward. Proceed.
+    B = FirstReachableB;
+  }
+
+  // We reached EXIT and found no branches.
+  return true;
+}
+
 const CXXDestructorDecl *
 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
   switch (getKind()) {
     case CFGElement::Initializer:
     case CFGElement::NewAllocator:
     case CFGElement::LoopExit:
     case CFGElement::LifetimeEnds:
     case CFGElement::Statement:

lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

maybeEmitNote(BugReport &R, const CallEvent &Call, const ExplodedNode *N,
     // but failing to do so. It's too unlikely a system header's fault.
     // It's much more likely a situation in which the function has a failure
     // mode that the user decided not to check. If we want to hunt such
     // omitted checks, we should provide an explicit function-specific note
     // describing the precondition under which the function isn't supposed to
     // initialize its out-parameter, and additionally check that such
     // precondition can actually be fulfilled on the current path.
     if (Call.isInSystemHeader()) {
-      // We make an exception for system header functions that have no branches,
-      // i.e. have exactly 3 CFG blocks: begin, all its code, end. Such
-      // functions unconditionally fail to initialize the variable.
+      // We make an exception for system header functions that have no branches.
+      // Such functions unconditionally fail to initialize the variable.
       // If they call other functions that have more paths within them,
       // this suppression would still apply when we visit these inner functions.
       // One common example of a standard function that doesn't ever initialize
       // its out parameter is operator placement new; it's up to the follow-up
       // constructor (if any) to initialize the memory.
-      if (N->getStackFrame()->getCFG()->size() > 3)
+      if (!N->getStackFrame()->getCFG()->isLinear())
         R.markInvalid(getTag(), nullptr);
       return nullptr;
     }
 
     PathDiagnosticLocation L =
         PathDiagnosticLocation::create(N->getLocation(), SM);
 
     // For now this shouldn't trigger, but once it does (as we add more

lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
     for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
                                    PSI != PSE; ++PSI) {
       Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
                                     calleeCtx->getIndex()+1);
     }
   }
 }
 
+bool ExprEngine::isSmall(AnalysisDeclContext *ADC) const {
+  // When there are no branches in the function, it means that there's no
+  // exponential complexity introduced by inlining such function.
+  // Such functions also don't trigger various fundamental problems
+  // with our inlining mechanism, such as the problem of
+  // inlined defensive checks. Hence isLinear().
+  const CFG *Cfg = ADC->getCFG();
+  return Cfg->isLinear() || Cfg->size() <= AMgr.options.AlwaysInlineSize;
+}
+
+bool ExprEngine::isLarge(AnalysisDeclContext *ADC) const {
+  const CFG *Cfg = ADC->getCFG();
+  return Cfg->size() >= AMgr.options.MinCFGSizeTreatFunctionsAsLarge;
+}
+
+bool ExprEngine::isHuge(AnalysisDeclContext *ADC) const {
+  const CFG *Cfg = ADC->getCFG();
+  return Cfg->getNumBlockIDs() > AMgr.options.MaxInlinableSize;
+}
+
 void ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx,
                                bool &IsRecursive, unsigned &StackDepth) {
   IsRecursive = false;
   StackDepth = 0;
 
   while (LCtx) {
     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LCtx)) {
       const Decl *DI = SFC->getDecl();
 
       // Mark recursive (and mutually recursive) functions and always count
       // them when measuring the stack depth.
       if (DI == D) {
         IsRecursive = true;
         ++StackDepth;
         LCtx = LCtx->getParent();
         continue;
       }
 
       // Do not count the small functions when determining the stack depth.
       AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(DI);
-      const CFG *CalleeCFG = CalleeADC->getCFG();
-      if (CalleeCFG->getNumBlockIDs() > AMgr.options.AlwaysInlineSize)
+      if (!isSmall(CalleeADC))
         ++StackDepth;
     }
     LCtx = LCtx->getParent();
   }
 }
 
 // The GDM component containing the dynamic dispatch bifurcation info. When
 // the exact type of the receiver is not known, we want to explore both paths -
static bool isCXXSharedPtrDtor(const FunctionDecl *FD) {
   return false;
 }
 
 /// Returns true if the function in \p CalleeADC may be inlined in general.
 ///
 /// This checks static properties of the function, such as its signature and
 /// CFG, to determine whether the analyzer should ever consider inlining it,
 /// in any context.
-static bool mayInlineDecl(AnalysisManager &AMgr,
-                          AnalysisDeclContext *CalleeADC) {
+bool ExprEngine::mayInlineDecl(AnalysisDeclContext *CalleeADC) const {
   AnalyzerOptions &Opts = AMgr.getAnalyzerOptions();
   // FIXME: Do not inline variadic calls.
   if (CallEvent::isVariadic(CalleeADC->getDecl()))
     return false;
 
   // Check certain C++-related inlining policies.
   ASTContext &Ctx = CalleeADC->getASTContext();
   if (Ctx.getLangOpts().CPlusPlus) {
bool ExprEngine::mayInlineDecl(AnalysisDeclContext *CalleeADC) const {
 
   // It is possible that the CFG cannot be constructed.
   // Be safe, and check if the CalleeCFG is valid.
   const CFG *CalleeCFG = CalleeADC->getCFG();
   if (!CalleeCFG)
     return false;
 
   // Do not inline large functions.
-  if (CalleeCFG->getNumBlockIDs() > Opts.MaxInlinableSize)
+  if (isHuge(CalleeADC))
     return false;
 
   // It is possible that the live variables analysis cannot be
   // run.  If so, bail out.
   if (!CalleeADC->getAnalysis<RelaxedLiveVariables>())
     return false;
 
   return true;
bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D,
   Optional<bool> MayInline = Engine.FunctionSummaries->mayInline(D);
   if (MayInline.hasValue()) {
     if (!MayInline.getValue())
       return false;
 
   } else {
     // We haven't actually checked the static properties of this function yet.
     // Do that now, and record our decision in the function summaries.
-    if (mayInlineDecl(getAnalysisManager(), CalleeADC)) {
+    if (mayInlineDecl(CalleeADC)) {
       Engine.FunctionSummaries->markMayInline(D);
     } else {
       Engine.FunctionSummaries->markShouldNotInline(D);
       return false;
     }
   }
 
   // Check if we should inline a call based on its kind.
   // FIXME: this checks both static and dynamic properties of the call, which
   // means we're redoing a bit of work that could be cached in the function
   // summary.
   CallInlinePolicy CIP = mayInlineCallKind(Call, Pred, Opts, CallOpts);
   if (CIP != CIP_Allowed) {
     if (CIP == CIP_DisallowedAlways) {
       assert(!MayInline.hasValue() || MayInline.getValue());
       Engine.FunctionSummaries->markShouldNotInline(D);
     }
     return false;
   }
 
-  const CFG *CalleeCFG = CalleeADC->getCFG();
-
   // Do not inline if recursive or we've reached max stack frame count.
   bool IsRecursive = false;
   unsigned StackDepth = 0;
   examineStackFrames(D, Pred->getLocationContext(), IsRecursive, StackDepth);
   if ((StackDepth >= Opts.InlineMaxStackDepth) &&
-      ((CalleeCFG->getNumBlockIDs() > Opts.AlwaysInlineSize)
-       || IsRecursive))
+      (!isSmall(CalleeADC) || IsRecursive))
     return false;
 
   // Do not inline large functions too many times.
   if ((Engine.FunctionSummaries->getNumTimesInlined(D) >
        Opts.MaxTimesInlineLarge) &&
-       CalleeCFG->getNumBlockIDs() >=
-       Opts.MinCFGSizeTreatFunctionsAsLarge) {
+      isLarge(CalleeADC)) {
     NumReachedInlineCountMax++;
     return false;
   }
 
-  if (HowToInline == Inline_Minimal &&
-      (CalleeCFG->getNumBlockIDs() > Opts.AlwaysInlineSize
-      || IsRecursive))
+  if (HowToInline == Inline_Minimal && (!isSmall(CalleeADC) || IsRecursive))
     return false;
 
   return true;
 }
 
 static bool isTrivialObjectAssignment(const CallEvent &Call) {
   const CXXInstanceCall *ICall = dyn_cast<CXXInstanceCall>(&Call);
   if (!ICall)

test/Analysis/inline-if-constexpr.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-inline-max-stack-depth=5 -w -std=c++17 -verify %s
+
+void clang_analyzer_eval(bool);
+
+namespace inline_large_functions_with_if_constexpr {
+bool f0() { if constexpr (true); return true; }
+bool f1() { if constexpr (true); return f0(); }
+bool f2() { if constexpr (true); return f1(); }
+bool f3() { if constexpr (true); return f2(); }
+bool f4() { if constexpr (true); return f3(); }
+bool f5() { if constexpr (true); return f4(); }
+bool f6() { if constexpr (true); return f5(); }
+bool f7() { if constexpr (true); return f6(); }
+void bar() {
+  clang_analyzer_eval(f7()); // expected-warning{{TRUE}}
+}
+} // namespace inline_large_functions_with_if_constexpr

unittests/Analysis/CFGTest.cpp

 #include "gtest/gtest.h"
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace analysis {
 namespace {
 
-enum BuildResult {
+class BuildResult {
+public:
+  enum Status {
     ToolFailed,
     ToolRan,
     SawFunctionBody,
     BuiltCFG,
   };
 
+  BuildResult(Status S, std::unique_ptr<CFG> Cfg = nullptr)
+      : S(S), Cfg(std::move(Cfg)) {}
+
+  Status getStatus() const { return S; }
+  CFG *getCFG() const { return Cfg.get(); }
+
+private:
+  Status S;
+  std::unique_ptr<CFG> Cfg;
+};
+
 class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
 public:
-  BuildResult TheBuildResult = ToolRan;
+  BuildResult TheBuildResult = BuildResult::ToolRan;
 
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
     const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
     Stmt *Body = Func->getBody();
     if (!Body)
       return;
-    TheBuildResult = SawFunctionBody;
+    TheBuildResult = BuildResult::SawFunctionBody;
     CFG::BuildOptions Options;
     Options.AddImplicitDtors = true;
-    if (CFG::buildCFG(nullptr, Body, Result.Context, Options))
-        TheBuildResult = BuiltCFG;
+    if (std::unique_ptr<CFG> Cfg =
+            CFG::buildCFG(nullptr, Body, Result.Context, Options))
+      TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)};
   }
 };
 
 BuildResult BuildCFG(const char *Code) {
   CFGCallback Callback;
 
   ast_matchers::MatchFinder Finder;
   Finder.addMatcher(ast_matchers::functionDecl().bind("func"), &Callback);
   std::unique_ptr<tooling::FrontendActionFactory> Factory(
       tooling::newFrontendActionFactory(&Finder));
   std::vector<std::string> Args = {"-std=c++11", "-fno-delayed-template-parsing"};
   if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args))
-    return ToolFailed;
-  return Callback.TheBuildResult;
+    return BuildResult::ToolFailed;
+  return std::move(Callback.TheBuildResult);
 }
 
 // Constructing a CFG for a range-based for over a dependent type fails (but
 // should not crash).
 TEST(CFG, RangeBasedForOverDependentType) {
   const char *Code = "class Foo;\n"
                      "template <typename T>\n"
                      "void f(const T &Range) {\n"
                      "  for (const Foo *TheFoo : Range) {\n"
                      "  }\n"
                      "}\n";
-  EXPECT_EQ(SawFunctionBody, BuildCFG(Code));
+  EXPECT_EQ(BuildResult::SawFunctionBody, BuildCFG(Code).getStatus());
 }
 
 // Constructing a CFG containing a delete expression on a dependent type should
 // not crash.
 TEST(CFG, DeleteExpressionOnDependentType) {
   const char *Code = "template<class T>\n"
                      "void f(T t) {\n"
                      "  delete t;\n"
                      "}\n";
-  EXPECT_EQ(BuiltCFG, BuildCFG(Code));
+  EXPECT_EQ(BuildResult::BuiltCFG, BuildCFG(Code).getStatus());
 }
 
 // Constructing a CFG on a function template with a variable of incomplete type
 // should not crash.
 TEST(CFG, VariableOfIncompleteType) {
   const char *Code = "template<class T> void f() {\n"
                      "  class Undefined;\n"
                      "  Undefined u;\n"
                      "}\n";
-  EXPECT_EQ(BuiltCFG, BuildCFG(Code));
+  EXPECT_EQ(BuildResult::BuiltCFG, BuildCFG(Code).getStatus());
+}
+
+TEST(CFG, IsLinear) {
+  auto expectLinear = [](bool IsLinear, const char *Code) {
+    BuildResult B = BuildCFG(Code);
+    EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
+    EXPECT_EQ(IsLinear, B.getCFG()->isLinear());
+  };
+
+  expectLinear(true,  "void foo() {}");
+  expectLinear(true,  "void foo() { if (true) return; }");
+  expectLinear(true,  "void foo() { if constexpr (false); }");
+  expectLinear(false, "void foo(bool coin) { if (coin) return; }");
+  expectLinear(false, "void foo() { for(;;); }");
+  expectLinear(false, "void foo() { do {} while (true); }");
+  expectLinear(true,  "void foo() { do {} while (false); }");
+  expectLinear(true,  "void foo() { foo(); }"); // Recursion is not our problem.
 }
 
 } // namespace
 } // namespace analysis
 } // namespace clang