ymandel updated this revision to Diff 531702. ymandel added a comment. Expand comments
Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D152263/new/ https://reviews.llvm.org/D152263 Files: clang/include/clang/Analysis/Analyses/IntervalPartition.h clang/lib/Analysis/CMakeLists.txt clang/lib/Analysis/IntervalPartition.cpp clang/unittests/Analysis/CMakeLists.txt clang/unittests/Analysis/IntervalPartitionTest.cpp
Index: clang/unittests/Analysis/IntervalPartitionTest.cpp =================================================================== --- /dev/null +++ clang/unittests/Analysis/IntervalPartitionTest.cpp @@ -0,0 +1,164 @@ +//===- unittests/Analysis/IntervalPartitionTest.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/IntervalPartition.h" +#include "CFGBuildResult.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace clang { +namespace analysis { +namespace { + +TEST(BuildInterval, PartitionSimpleOneInterval) { + + const char *Code = R"(void f() { + int x = 3; + int y = 7; + x = y + x; + })"; + BuildResult Result = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + + // Basic correctness checks. + ASSERT_EQ(cfg->size(), 3u); + + auto &EntryBlock = cfg->getEntry(); + + CFGInterval I = buildInterval(EntryBlock); + EXPECT_EQ(I.Blocks.size(), 3u); +} + +TEST(BuildInterval, PartitionIfThenOneInterval) { + + const char *Code = R"(void f() { + int x = 3; + if (x > 3) + x = 2; + else + x = 7; + x = x + x; + })"; + BuildResult Result = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + + // Basic correctness checks. + ASSERT_EQ(cfg->size(), 6u); + + auto &EntryBlock = cfg->getEntry(); + + CFGInterval I = buildInterval(EntryBlock); + EXPECT_EQ(I.Blocks.size(), 6u); +} + +using ::testing::UnorderedElementsAre; + +TEST(BuildInterval, PartitionWhileMultipleIntervals) { + + const char *Code = R"(void f() { + int x = 3; + while (x >= 3) + --x; + x = x + x; + })"; + BuildResult Result = BuildCFG(Code); + ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + ASSERT_EQ(cfg->size(), 7u); + + auto *EntryBlock = &cfg->getEntry(); + CFGBlock *InitXBlock = *EntryBlock->succ_begin(); + CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin(); + + CFGInterval I1 = buildInterval(*EntryBlock); + EXPECT_THAT(I1.Blocks, UnorderedElementsAre(EntryBlock, InitXBlock)); + + CFGInterval I2 = buildInterval(*LoopHeadBlock); + EXPECT_EQ(I2.Blocks.size(), 5u); +} + +TEST(PartitionIntoIntervals, PartitionIfThenOneInterval) { + const char *Code = R"(void f() { + int x = 3; + if (x > 3) + x = 2; + else + x = 7; + x = x + x; + })"; + BuildResult Result = BuildCFG(Code); + ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + ASSERT_EQ(cfg->size(), 6u); + + auto Intervals = partitionIntoIntervals(*cfg); + EXPECT_EQ(Intervals.size(), 1u); +} + +TEST(PartitionIntoIntervals, PartitionWhileTwoIntervals) { + const char *Code = R"(void f() { + int x = 3; + while (x >= 3) + --x; + x = x + x; + })"; + BuildResult Result = BuildCFG(Code); + ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + ASSERT_EQ(cfg->size(), 7u); + + auto Intervals = partitionIntoIntervals(*cfg); + EXPECT_EQ(Intervals.size(), 2u); +} + +TEST(PartitionIntoIntervals, PartitionNestedWhileThreeIntervals) { + const char *Code = R"(void f() { + int x = 3; + while (x >= 3) { + --x; + int y = x; + while (y > 0) --y; + } + x = x + x; + })"; + BuildResult Result = BuildCFG(Code); + ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + auto Intervals = partitionIntoIntervals(*cfg); + EXPECT_EQ(Intervals.size(), 3u); +} + +TEST(PartitionIntoIntervals, PartitionSequentialWhileThreeIntervals) { + const char *Code = R"(void f() { + int x = 3; + while (x >= 3) { + --x; + } + x = x + x; + int y = x; + while (y > 0) --y; + })"; + BuildResult Result = BuildCFG(Code); + ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus()); + + CFG *cfg = Result.getCFG(); + auto Intervals = partitionIntoIntervals(*cfg); + EXPECT_EQ(Intervals.size(), 3u); +} + +} // namespace +} // namespace analysis +} // namespace clang Index: clang/unittests/Analysis/CMakeLists.txt =================================================================== --- clang/unittests/Analysis/CMakeLists.txt +++ clang/unittests/Analysis/CMakeLists.txt @@ -8,6 +8,7 @@ CFGTest.cpp CloneDetectionTest.cpp ExprMutationAnalyzerTest.cpp + IntervalPartitionTest.cpp MacroExpansionContextTest.cpp UnsafeBufferUsageTest.cpp ) Index: clang/lib/Analysis/IntervalPartition.cpp =================================================================== --- /dev/null +++ clang/lib/Analysis/IntervalPartition.cpp @@ -0,0 +1,102 @@ +//===- IntervalPartition.cpp - CFG Partitioning into Intervals --*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines functionality for partitioning a CFG into intervals. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/IntervalPartition.h" +#include "clang/Analysis/CFG.h" +#include <queue> +#include <set> +#include <vector> + +namespace clang { + +static CFGInterval buildInterval(std::set<const CFGBlock *> &Partitioned, + const CFGBlock &Header) { + CFGInterval Interval(&Header); + Partitioned.insert(&Header); + + std::queue<const CFGBlock *> Worklist; + for (const CFGBlock *S : Header.succs()) + Worklist.push(S); + + // Contains successors of blocks in the interval that couldn't be added to the + // interval on their first encounter. This occurs when they have a predecessor + // that is either definitively outside the interval or hasn't been considered + // yet. In the latter case, we'll revisit the block through some other path + // from the interval. At the end of processing the worklist, we filter out any + // that ended up in the interval to produce the output set of interval + // successors. + std::vector<const CFGBlock *> MaybeSuccessors; + + while (!Worklist.empty()) { + const auto *B = Worklist.front(); + Worklist.pop(); + assert(B != nullptr); + if (Partitioned.find(B) != Partitioned.end()) + continue; + + // Check whether all predecessors are in the interval, in which case `B` + // is included as well. + bool AllInInterval = true; + for (const CFGBlock *P : B->preds()) + if (Interval.Blocks.find(P) == Interval.Blocks.end()) { + MaybeSuccessors.push_back(B); + AllInInterval = false; + break; + } + if (AllInInterval) { + Interval.Blocks.insert(B); + Partitioned.insert(B); + for (const CFGBlock *S : B->succs()) + Worklist.push(S); + } + } + + // Any block successors not in the current interval are interval successors. + for (const CFGBlock *B : MaybeSuccessors) + if (Interval.Blocks.find(B) == Interval.Blocks.end()) + Interval.Successors.insert(B); + + return Interval; +} + +CFGInterval buildInterval(const CFGBlock &Header) { + std::set<const CFGBlock *> Partitioned; + return buildInterval(Partitioned, Header); +} + +std::vector<CFGInterval> partitionIntoIntervals(const CFG &Cfg) { + std::vector<CFGInterval> Intervals; + std::set<const CFGBlock *> Partitioned; + auto &EntryBlock = Cfg.getEntry(); + Intervals.push_back(buildInterval(Partitioned, EntryBlock)); + + std::queue<const CFGBlock *> Successors; + for (const auto *S : Intervals[0].Successors) + Successors.push(S); + + while (!Successors.empty()) { + const auto *B = Successors.front(); + Successors.pop(); + if (Partitioned.find(B) != Partitioned.end()) + continue; + + // B has not been partitioned, but it has a predecessor that has. + CFGInterval I = buildInterval(Partitioned, *B); + for (const auto *S : I.Successors) + Successors.push(S); + Intervals.push_back(std::move(I)); + } + + return Intervals; +} + +} // namespace clang Index: clang/lib/Analysis/CMakeLists.txt =================================================================== --- clang/lib/Analysis/CMakeLists.txt +++ clang/lib/Analysis/CMakeLists.txt @@ -18,6 +18,7 @@ CodeInjector.cpp Dominators.cpp ExprMutationAnalyzer.cpp + IntervalPartition.cpp IssueHash.cpp LiveVariables.cpp MacroExpansionContext.cpp Index: clang/include/clang/Analysis/Analyses/IntervalPartition.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/Analyses/IntervalPartition.h @@ -0,0 +1,50 @@ +//===- IntervalPartition.h - CFG Partitioning into Intervals -----*- C++-*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines functionality for partitioning a CFG into intervals. The +// concepts and implementations are based on the presentation in "Compilers" by +// Aho, Sethi and Ullman (the "dragon book"), pages 664-666. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H + +#include "clang/Analysis/CFG.h" +#include <set> +#include <vector> + +namespace clang { + +// An interval is a strongly-connected component of the CFG along with a +// trailing acyclic structure. The _header_ of the interval is either the CFG +// entry block or has at least one predecessor outside of the interval. All +// other blocks in the interval have only predecessors also in the interval. +struct CFGInterval { + CFGInterval(const CFGBlock *Header) : Header(Header), Blocks({Header}) {} + + // The block from which the interval was constructed. Is either the CFG entry + // block or has at least one predecessor outside the interval. + const CFGBlock *Header; + + std::set<const CFGBlock *> Blocks; + + // Successor blocks of the *interval*: blocks outside the interval for + // reachable (in one edge) from within the interval. + std::set<const CFGBlock *> Successors; +}; + +CFGInterval buildInterval(const CFGBlock &Header); + +// Partitions `Cfg` into intervals and constructs a graph of the intervals, +// based on the edges between nodes in these intervals. +std::vector<CFGInterval> partitionIntoIntervals(const CFG &Cfg); + +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
