Index: clang/include/clang/Analysis/CFG.h =================================================================== --- clang/include/clang/Analysis/CFG.h +++ clang/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: clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -718,6 +718,14 @@ 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. + 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; + /// Checks our policies and decides weither the given call should be inlined. bool shouldInlineCall(const CallEvent &Call, const Decl *D, const ExplodedNode *Pred, Index: clang/lib/Analysis/CFG.cpp =================================================================== --- clang/lib/Analysis/CFG.cpp +++ clang/lib/Analysis/CFG.cpp @@ -4677,6 +4677,50 @@ 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: clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ clang/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: clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -364,6 +364,16 @@ } } +bool ExprEngine::isSmall(AnalysisDeclContext *ADC) const { + 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; +} + void ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx, bool &IsRecursive, unsigned &StackDepth) { IsRecursive = false; @@ -384,8 +394,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(); @@ -878,7 +887,7 @@ return false; // Do not inline large functions. - if (CalleeCFG->getNumBlockIDs() > Opts.MaxInlinableSize) + if (CalleeCFG->getNumBlockIDs() >= Opts.MaxInlinableSize) return false; // It is possible that the live variables analysis cannot be @@ -939,29 +948,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: clang/test/Analysis/inline-if-constexpr.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/inline-if-constexpr.cpp @@ -0,0 +1,18 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection \ +// RUN: -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: clang/unittests/Analysis/CFGTest.cpp =================================================================== --- clang/unittests/Analysis/CFGTest.cpp +++ clang/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(); }"); // Not our problem. } } // namespace