Index: clang/unittests/Analysis/CFGBuilder.h =================================================================== --- /dev/null +++ clang/unittests/Analysis/CFGBuilder.h @@ -0,0 +1,69 @@ +//===- unittests/Analysis/CFGTest.cpp - CFG tests -------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/CFG.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Tooling/Tooling.h" + +namespace clang { +namespace analysis { + +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 = 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 = BuildResult::SawFunctionBody; + CFG::BuildOptions Options; + Options.AddImplicitDtors = true; + if (std::unique_ptr Cfg = + CFG::buildCFG(nullptr, Body, Result.Context, Options)) + TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)}; + } +}; + +inline BuildResult BuildCFG(const char *Code) { + CFGCallback Callback; + + ast_matchers::MatchFinder Finder; + Finder.addMatcher(ast_matchers::functionDecl().bind("func"), &Callback); + std::unique_ptr Factory( + tooling::newFrontendActionFactory(&Finder)); + std::vector Args = {"-std=c++11", + "-fno-delayed-template-parsing"}; + if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args)) + return BuildResult::ToolFailed; + return std::move(Callback.TheBuildResult); +} + +} // namespace analysis +} // namespace clang Index: clang/unittests/Analysis/CFGDominatorTree.cpp =================================================================== --- /dev/null +++ clang/unittests/Analysis/CFGDominatorTree.cpp @@ -0,0 +1,118 @@ +//===- unittests/Analysis/CFGTest.cpp - CFG tests -------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "CFGBuilder.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/Analyses/Dominators.h" +#include "clang/Analysis/CFG.h" +#include "clang/Tooling/Tooling.h" +#include "gtest/gtest.h" +#include +#include + +namespace clang { +namespace analysis { +namespace { + +template +struct FindStmt { + bool operator()(const CFGElement &E) { + if (auto S = E.getAs()) + return isa(S->getStmt()); + return false; + } +}; + +template +bool hasStmtType(CFGBlock *Block) { + return llvm::find_if(*Block, FindStmt()) == Block->end(); +} + +TEST(CFGDominatorTree, DomTree) { + const char *Code = "enum Kind {\n" + " A\n" + "};\n" + "\n" + "void f() {\n" + " switch(Kind{}) {\n" + " case A:\n" + " break;\n" + " }\n" + "}\n"; + BuildResult Result = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + // [B3 (ENTRY)] -> [B1] -> [B2] -> [B0 (EXIT)] + // switch case A + + CFG *cfg = Result.getCFG(); + + // Sanity checks. + EXPECT_EQ(cfg->size(), 4u); + + CFGBlock *ExitBlock = *cfg->begin(); + EXPECT_EQ(ExitBlock, &cfg->getExit()); + + CFGBlock *SwitchBlock = *(cfg->begin() + 1); + EXPECT_TRUE(hasStmtType(SwitchBlock)); + + CFGBlock *CaseABlock = *(cfg->begin() + 2); + EXPECT_TRUE(hasStmtType(CaseABlock)); + + CFGBlock *EntryBlock = *(cfg->begin() + 3); + EXPECT_EQ(EntryBlock, &cfg->getEntry()); + + // Test the dominator tree. + CFGDomTree Dom; + Dom.buildDominatorTree(cfg); + + EXPECT_TRUE(Dom.dominates(ExitBlock, ExitBlock)); + EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock)); + EXPECT_TRUE(Dom.dominates(CaseABlock, ExitBlock)); + EXPECT_TRUE(Dom.dominates(SwitchBlock, ExitBlock)); + EXPECT_TRUE(Dom.dominates(EntryBlock, ExitBlock)); + + EXPECT_TRUE(Dom.dominates(CaseABlock, CaseABlock)); + EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock)); + EXPECT_TRUE(Dom.dominates(SwitchBlock, CaseABlock)); + EXPECT_TRUE(Dom.dominates(EntryBlock, CaseABlock)); + + EXPECT_TRUE(Dom.dominates(SwitchBlock, SwitchBlock)); + EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock)); + EXPECT_TRUE(Dom.dominates(EntryBlock, SwitchBlock)); + + EXPECT_TRUE(Dom.dominates(EntryBlock, EntryBlock)); + EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock)); + + // Test the post dominator tree. + + CFGPostDomTree PostDom; + PostDom.buildDominatorTree(cfg); + + EXPECT_TRUE(PostDom.dominates(ExitBlock, EntryBlock)); + EXPECT_TRUE(PostDom.dominates(CaseABlock, EntryBlock)); + EXPECT_TRUE(PostDom.dominates(SwitchBlock, EntryBlock)); + EXPECT_TRUE(PostDom.dominates(EntryBlock, EntryBlock)); + EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock)); + + EXPECT_TRUE(PostDom.dominates(ExitBlock, SwitchBlock)); + EXPECT_TRUE(PostDom.dominates(CaseABlock, SwitchBlock)); + EXPECT_TRUE(PostDom.dominates(SwitchBlock, SwitchBlock)); + EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock)); + + EXPECT_TRUE(PostDom.dominates(ExitBlock, CaseABlock)); + EXPECT_TRUE(PostDom.dominates(CaseABlock, CaseABlock)); + EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock)); + + EXPECT_TRUE(PostDom.dominates(ExitBlock, ExitBlock)); + EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock)); +} + +} // namespace +} // namespace analysis +} // namespace clang Index: clang/unittests/Analysis/CFGTest.cpp =================================================================== --- clang/unittests/Analysis/CFGTest.cpp +++ clang/unittests/Analysis/CFGTest.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "CFGBuilder.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/Analysis/CFG.h" #include "clang/Tooling/Tooling.h" @@ -17,57 +18,6 @@ namespace analysis { namespace { -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 = 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 = BuildResult::SawFunctionBody; - CFG::BuildOptions Options; - Options.AddImplicitDtors = true; - if (std::unique_ptr 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 Factory( - tooling::newFrontendActionFactory(&Finder)); - std::vector Args = {"-std=c++11", "-fno-delayed-template-parsing"}; - if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args)) - 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) { Index: clang/unittests/Analysis/CMakeLists.txt =================================================================== --- clang/unittests/Analysis/CMakeLists.txt +++ clang/unittests/Analysis/CMakeLists.txt @@ -3,6 +3,7 @@ ) add_clang_unittest(ClangAnalysisTests + CFGDominatorTree.cpp CFGTest.cpp CloneDetectionTest.cpp ExprMutationAnalyzerTest.cpp