NoQ created this revision.
NoQ added reviewers: dcoughlin, xazax.hun, a_sidorin, rnkovacs,
mikhail.ramalho, Szelethus, baloghadamsoftware, Charusso.
Herald added subscribers: cfe-commits, dkrupp, donat.nagy, a.sidorin, szepet,
eraman.
Herald added a project: clang.
Currently we always inline functions that have no branches, i.e. have exactly
three CFG blocks: [B2 <https://reviews.llvm.org/B2>] ENTRY, [B1
<https://reviews.llvm.org/B1>] some code, [B0] 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`.
Repository:
rC Clang
https://reviews.llvm.org/D61051
Files:
clang/include/clang/Analysis/CFG.h
clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
clang/lib/Analysis/CFG.cpp
clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
clang/test/Analysis/inline-if-constexpr.cpp
clang/unittests/Analysis/CFGTest.cpp
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> 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)};
}
};
@@ -50,8 +64,8 @@
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
@@ -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
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/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/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/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<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()) {
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/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.
//===--------------------------------------------------------------------===//
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
