diff --git a/clang/unittests/Analysis/Analyses/CMakeLists.txt b/clang/unittests/Analysis/Analyses/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/Analyses/CMakeLists.txt @@ -0,0 +1,23 @@ +set(LLVM_LINK_COMPONENTS + Support + ) + +add_clang_unittest(ClangAnalysisAnalysesTests + PostOrderCFGViewTest.cpp + ) + +clang_target_link_libraries(ClangAnalysisAnalysesTests + PRIVATE + clangAnalysis + clangAST + clangASTMatchers + clangBasic + clangFrontend + clangTesting + clangTooling + ) + +target_link_libraries(ClangAnalysisAnalysesTests + PRIVATE + LLVMTestingSupport + ) diff --git a/clang/unittests/Analysis/Analyses/PostOrderCFGViewTest.cpp b/clang/unittests/Analysis/Analyses/PostOrderCFGViewTest.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/Analyses/PostOrderCFGViewTest.cpp @@ -0,0 +1,384 @@ +//===- unittests/Analysis/Analyses/PostOrderCFGViewTest.cpp ---------------===// +// +// 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/Analyses/PostOrderCFGView.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/CFG.h" +#include "clang/Tooling/Tooling.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include +#include +#include +#include +#include +#include + +namespace clang { +namespace analysis { +namespace analyses { +namespace { + +using ::testing::ElementsAre; +using ::testing::NotNull; + +class PostOrderBlockIDMatchCallback + : public ast_matchers::MatchFinder::MatchCallback { +public: + const std::vector &getPostOrderBlockIDs() const { + return PostOrderBlockIDs; + } + + void run(const ast_matchers::MatchFinder::MatchResult &Result) override { + const auto *Func = Result.Nodes.getNodeAs("func"); + ASSERT_THAT(Func, NotNull()); + + Stmt *Body = Func->getBody(); + ASSERT_THAT(Body, NotNull()); + + CFG::BuildOptions Options; + Options.AddImplicitDtors = true; + Options.AddTemporaryDtors = true; + Options.setAllAlwaysAdd(); + + std::unique_ptr Cfg = + CFG::buildCFG(nullptr, Body, Result.Context, Options); + ASSERT_THAT(Cfg, NotNull()); + + PostOrderCFGView POV(Cfg.get()); + std::priority_queue, + PostOrderCFGView::BlockOrderCompare> + BlocksQueue(POV.getComparator()); + for (const CFGBlock *Block : *Cfg) + BlocksQueue.push(Block); + + while (!BlocksQueue.empty()) { + PostOrderBlockIDs.push_back(BlocksQueue.top()->getBlockID()); + BlocksQueue.pop(); + } + } + +private: + std::vector PostOrderBlockIDs; +}; + +template +void expectPostOrderBlockIDs(const char *Code, T MatchesPostOrderBlockIDs) { + std::unique_ptr AST = + tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"}); + ASSERT_THAT(AST, NotNull()); + + PostOrderBlockIDMatchCallback Callback; + ast_matchers::MatchFinder Finder; + Finder.addMatcher( + ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"), + &Callback); + Finder.matchAST(AST->getASTContext()); + + EXPECT_THAT(Callback.getPostOrderBlockIDs(), MatchesPostOrderBlockIDs); +} + +TEST(PostOrderCFGViewTest, EmptyFunc) { + expectPostOrderBlockIDs(R"( + // B1 (succs: B0) + void target() { + } + // B0 + )", + ElementsAre(0, 1)); +} + +TEST(PostOrderCFGViewTest, IfStmt) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B5 (succs: B4) + void target() { + // B4 (succs: B3, B2) + foo(); + if (foo()) { + // B3 (succs: B1) + foo(); + } else { + // B2 (succs: B1) + foo(); + } + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 1, 3, 2, 4, 5)); +} + +TEST(PostOrderCFGViewTest, IfStmtLogicalAnd) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B4, B2) + foo(); + if (foo() && /*B4 (succs: B3, B2)*/ foo()) { + // B3 (succs: B1) + foo(); + } else { + // B2 (succs: B1) + foo(); + } + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 1, 3, 2, 4, 5, 6)); +} + +TEST(PostOrderCFGViewTest, IfStmtLogicalOr) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B3, B4) + foo(); + if (foo() || /*B4 (succs: B3, B2)*/ foo()) { + // B2 (succs: B1) + foo(); + } else { + // B3 (succs: B1) + foo(); + } + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 1, 3, 2, 4, 5, 6)); +} + +TEST(PostOrderCFGViewTest, ForStmt) { + expectPostOrderBlockIDs(R"( + void foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B4) + foo(); + for (int i = 0; /*B4 (succs: B3, B1)*/ i < 10; /*B2 (succs: B4)*/ i++) { + // B3 (succs: B2) + foo(); + } + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(2, 3, 0, 1, 4, 5, 6)); +} + +TEST(PostOrderCFGViewTest, WhileStmt) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B4) + foo(); + while (/*B4 (succs: B3, B1)*/ foo()) { + // B3 (succs: B2) + foo(); + } // B2 (succs: B4 - back edge) + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(2, 3, 0, 1, 4, 5, 6)); +} + +TEST(PostOrderCFGViewTest, DoWhileStmt) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B3) + foo(); + do { + // B3 (succs: B2) + foo(); + } while (/*B2 (succs: B4, B1)*/ foo()); // B4 (succs: B3 - back edge) + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(4, 0, 1, 2, 3, 5, 6)); +} + +TEST(PostOrderCFGViewTest, TernaryCondStmt) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B5 (succs: B4) + void target() { + // B4 (succs: B2, B3) + foo(); + int bar = foo() ? /*B2 (succs: B1)*/ 21 : /*B3 (succs: B1)*/ 42; + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 1, 2, 3, 4, 5)); +} + +TEST(PostOrderCFGViewTest, TernaryCondStmtTempDtor) { + expectPostOrderBlockIDs(R"( + class Fatal { + public: + ~Fatal() __attribute__((noreturn)); + int value(); + }; + + bool foo(); + + // B7 (succs: B6) + void target() { + // B6 (succs: B4, B5) + foo(); + int bar = foo() ? /*B4 (succs: B3)*/ 21 : + /*B5 (succs: B3)*/ Fatal().value(); + // B3 (succs: B2, B1) + // B2 (succs: B0 - temp dtor, noreturn) + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 2, 1, 3, 4, 5, 6, 7)); +} + +TEST(PostOrderCFGViewTest, GoToStmtForward) { + expectPostOrderBlockIDs(R"( + void foo(); + + // B4 (succs: B3) + void target() { + // B3 (succs: B1) + foo(); + goto bar; + // B2 (succs: B1) + foo(); + bar: + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(2, 0, 1, 3, 4)); + expectPostOrderBlockIDs(R"( + bool foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B4, B3) + foo(); + if (foo()) { + // B4 (succs: B1) + foo(); + goto bar; + } else { + // B3 (succs: B2) + foo(); + } + // B2 (succs: B1) + foo(); + bar: + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 1, 4, 2, 3, 5, 6)); +} + +TEST(PostOrderCFGViewTest, GoToStmtBackward) { + expectPostOrderBlockIDs(R"( + void foo(); + + // B3 (succs: B2) + void target() { + // B2 (succs: B2) + bar: + foo(); + foo(); + goto bar; + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(0, 1, 2, 3)); + expectPostOrderBlockIDs(R"( + bool foo(); + + // B6 (succs: B5) + void target() { + // B5 (succs: B4) + foo(); + bar: + // B4 (succs: B3, B2) + if (foo()) { + // B3 (succs: B4) + foo(); + goto bar; + } else { + // B2 (succs: B1) + foo(); + } + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(3, 0, 1, 2, 4, 5, 6)); +} + +TEST(PostOrderCFGViewTest, ComplexFlow) { + expectPostOrderBlockIDs(R"( + bool foo(); + + // B10 (succs: B9) + void target() { + // B9 (succs: B8) + foo(); + for (int i = 0; /*B8 (succs: B7, B1)*/ i < 10; /*B2 (succs: B8)*/ i++) { + if ((/*B7 (succs: B6, B5)*/ foo() && /*B6 (succs: B4, B5)*/ foo()) || + /*B5 (succs: B4, B3)*/ foo()) { + // B4 (succs: B2) + foo(); + } else { + // B3 (succs: B2) + foo(); + } + } + // B1 (succs: B0) + foo(); + } + // B0 + )", + ElementsAre(2, 4, 3, 5, 6, 7, 0, 1, 8, 9, 10)); +} + +} // namespace +} // namespace analyses +} // namespace analysis +} // namespace clang diff --git a/clang/unittests/Analysis/CMakeLists.txt b/clang/unittests/Analysis/CMakeLists.txt --- a/clang/unittests/Analysis/CMakeLists.txt +++ b/clang/unittests/Analysis/CMakeLists.txt @@ -28,3 +28,5 @@ PRIVATE LLVMTestingSupport ) + +add_subdirectory(Analyses)