Index: include/clang/Analysis/CFG.h =================================================================== --- include/clang/Analysis/CFG.h +++ include/clang/Analysis/CFG.h @@ -1172,6 +1172,12 @@ /// 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. //===--------------------------------------------------------------------===// Index: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -718,6 +718,25 @@ 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, Index: lib/Analysis/CFG.cpp =================================================================== --- lib/Analysis/CFG.cpp +++ lib/Analysis/CFG.cpp @@ -4677,6 +4677,51 @@ 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 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()) { Index: lib/StaticAnalyzer/Core/BugReporterVisitors.cpp =================================================================== --- lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -563,15 +563,14 @@ // 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; } Index: lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -364,6 +364,26 @@ } } +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; @@ -384,8 +404,7 @@ // 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(); @@ -832,8 +851,7 @@ /// 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())) @@ -878,7 +896,7 @@ 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 @@ -918,7 +936,7 @@ } 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); @@ -939,29 +957,23 @@ 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; Index: test/Analysis/inline-if-constexpr.cpp =================================================================== --- test/Analysis/inline-if-constexpr.cpp +++ test/Analysis/inline-if-constexpr.cpp @@ -0,0 +1,18 @@ +// 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 Index: unittests/Analysis/CFGTest.cpp =================================================================== --- unittests/Analysis/CFGTest.cpp +++ unittests/Analysis/CFGTest.cpp @@ -17,27 +17,41 @@ namespace analysis { namespace { -enum BuildResult { - ToolFailed, - ToolRan, - SawFunctionBody, - BuiltCFG, +class BuildResult { +public: + enum Status { + ToolFailed, + ToolRan, + SawFunctionBody, + BuiltCFG, + }; + + BuildResult(Status S, std::unique_ptr 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; }; 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("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::buildCFG(nullptr, Body, Result.Context, Options)) + TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)}; } }; @@ -50,8 +64,8 @@ tooling::newFrontendActionFactory(&Finder)); std::vector 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 @@ -63,7 +77,7 @@ " 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 @@ -73,7 +87,7 @@ "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 @@ -83,7 +97,24 @@ " 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