| //===- 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 "llvm/ADT/BitVector.h" | |
| #include "llvm/ADT/STLExtras.h" | |
| #include <optional> | |
| #include <queue> | |
| #include <vector> | |
| namespace clang { | |
| // Intermediate data used in constructing a CFGIntervalNode. | |
| template <typename Node> struct BuildResult { | |
| // Use a vector to maintain the insertion order. Given the expected small | |
| // number of nodes, vector should be sufficiently efficient. Elements must not | |
| // be null. | |
| std::vector<const Node *> Nodes; | |
| // Elements must not be null. | |
| llvm::SmallDenseSet<const Node *> Successors; | |
| }; | |
| namespace internal { | |
| static unsigned getID(const CFGBlock &B) { return B.getBlockID(); } | |
| static unsigned getID(const CFGIntervalNode &I) { return I.ID; } | |
| // `Node` must be one of `CFGBlock` or `CFGIntervalNode`. | |
| template <typename Node> | |
| static BuildResult<Node> buildInterval(llvm::BitVector &Partitioned, | |
| const Node *Header) { | |
| assert(Header != nullptr); | |
| BuildResult<Node> Interval; | |
| Interval.Nodes.push_back(Header); | |
| Partitioned.set(getID(*Header)); | |
| // FIXME: Compare performance against using RPO to consider nodes, rather than | |
| // following successors. | |
| // | |
| // Elements must not be null. Duplicates are prevented using `Workset`, below. | |
| std::queue<const Node *> Worklist; | |
| llvm::BitVector Workset(Partitioned.size(), false); | |
| for (const Node *S : Header->succs()) | |
| if (S != nullptr) | |
| if (auto SID = getID(*S); !Partitioned.test(SID)) { | |
| // Successors are unique, so we don't test against `Workset` before | |
| // adding to `Worklist`. | |
| Worklist.push(S); | |
| Workset.set(SID); | |
| } | |
| // 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. Elements are never null. | |
| std::vector<const Node *> MaybeSuccessors; | |
| while (!Worklist.empty()) { | |
| const auto *B = Worklist.front(); | |
| auto ID = getID(*B); | |
| Worklist.pop(); | |
| Workset.reset(ID); | |
| // Check whether all predecessors are in the interval, in which case `B` | |
| // is included as well. | |
| bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) { | |
| return llvm::is_contained(Interval.Nodes, P); | |
| }); | |
| if (AllInInterval) { | |
| Interval.Nodes.push_back(B); | |
| Partitioned.set(ID); | |
| for (const Node *S : B->succs()) | |
| if (S != nullptr) | |
| if (auto SID = getID(*S); | |
| !Partitioned.test(SID) && !Workset.test(SID)) { | |
| Worklist.push(S); | |
| Workset.set(SID); | |
| } | |
| } else { | |
| MaybeSuccessors.push_back(B); | |
| } | |
| } | |
| // Any block successors not in the current interval are interval successors. | |
| for (const Node *B : MaybeSuccessors) | |
| if (!llvm::is_contained(Interval.Nodes, B)) | |
| Interval.Successors.insert(B); | |
| return Interval; | |
| } | |
| template <typename Node> | |
| static void fillIntervalNode(CFGIntervalGraph &Graph, | |
| std::vector<CFGIntervalNode *> &Index, | |
| std::queue<const Node *> &Successors, | |
| llvm::BitVector &Partitioned, const Node *Header) { | |
| BuildResult<Node> Result = buildInterval(Partitioned, Header); | |
| for (const auto *S : Result.Successors) | |
| Successors.push(S); | |
| CFGIntervalNode &Interval = Graph.emplace_back(Graph.size()); | |
| // Index the nodes of the new interval. The index maps nodes from the input | |
| // graph (specifically, `Result.Nodes`) to identifiers of nodes in the output | |
| // graph. In this case, the new interval has identifier `ID` so all of its | |
| // nodes (`Result.Nodes`) map to `ID`. | |
| for (const auto *N : Result.Nodes) { | |
| assert(N != nullptr); | |
| assert(getID(*N) < Index.size()); | |
| Index[getID(*N)] = &Interval; | |
| } | |
| if constexpr (std::is_same_v<std::decay_t<Node>, CFGBlock>) | |
| Interval.Nodes = std::move(Result.Nodes); | |
| else { | |
| std::vector<const CFGBlock *> Nodes; | |
| // Flatten the sub vectors into a single list. | |
| size_t Count = 0; | |
| for (auto &N : Result.Nodes) | |
| Count += N->Nodes.size(); | |
| Nodes.reserve(Count); | |
| for (auto &N : Result.Nodes) | |
| llvm::append_range(Nodes, N->Nodes); | |
| Interval.Nodes = std::move(Nodes); | |
| } | |
| } | |
| template <typename Node> | |
| static CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs, | |
| const Node *EntryBlock) { | |
| assert(EntryBlock != nullptr); | |
| CFGIntervalGraph Graph; | |
| // `Index` maps all of the nodes of the input graph to the interval to which | |
| // they are assigned in the output graph. The values (interval pointers) are | |
| // never null. | |
| std::vector<CFGIntervalNode *> Index(NumBlockIDs, nullptr); | |
| // Lists header nodes (from the input graph) and their associated | |
| // interval. Since header nodes can vary in type and are only needed within | |
| // this function, we record them separately from `CFGIntervalNode`. This | |
| // choice enables to express `CFGIntervalNode` without using a variant. | |
| std::vector<std::pair<const Node *, CFGIntervalNode *>> Intervals; | |
| llvm::BitVector Partitioned(NumBlockIDs, false); | |
| std::queue<const Node *> Successors; | |
| fillIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock); | |
| Intervals.emplace_back(EntryBlock, &Graph.back()); | |
| while (!Successors.empty()) { | |
| const auto *B = Successors.front(); | |
| Successors.pop(); | |
| assert(B != nullptr); | |
| if (Partitioned.test(getID(*B))) | |
| continue; | |
| // B has not been partitioned, but it has a predecessor that has. Create a | |
| // new interval from `B`. | |
| fillIntervalNode(Graph, Index, Successors, Partitioned, B); | |
| Intervals.emplace_back(B, &Graph.back()); | |
| } | |
| // Go back and patch up all the Intervals -- the successors and predecessors. | |
| for (auto [H, N] : Intervals) { | |
| // Map input-graph predecessors to output-graph nodes and mark those as | |
| // predecessors of `N`. Then, mark `N` as a successor of said predecessor. | |
| for (const Node *P : H->preds()) { | |
| if (P == nullptr) | |
| continue; | |
| assert(getID(*P) < NumBlockIDs); | |
| CFGIntervalNode *Pred = Index[getID(*P)]; | |
| if (Pred == nullptr) | |
| // Unreachable node. | |
| continue; | |
| if (Pred != N // Not a backedge. | |
| && N->Predecessors.insert(Pred).second) | |
| // Note: given the guard above, which guarantees we only ever insert | |
| // unique elements, we could use a simple list (like `vector`) for | |
| // `Successors`, rather than a set. | |
| Pred->Successors.insert(N); | |
| } | |
| } | |
| return Graph; | |
| } | |
| std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header) { | |
| llvm::BitVector Partitioned(Header->getParent()->getNumBlockIDs(), false); | |
| return buildInterval(Partitioned, Header).Nodes; | |
| } | |
| CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg) { | |
| return partitionIntoIntervalsImpl(Cfg.getNumBlockIDs(), &Cfg.getEntry()); | |
| } | |
| CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph) { | |
| return partitionIntoIntervalsImpl(Graph.size(), &Graph[0]); | |
| } | |
| } // namespace internal | |
| std::optional<std::vector<const CFGBlock *>> getIntervalWTO(const CFG &Cfg) { | |
| // Backing storage for the allocated nodes in each graph. | |
| unsigned PrevSize = Cfg.size(); | |
| if (PrevSize == 0) | |
| return {}; | |
| internal::CFGIntervalGraph Graph = internal::partitionIntoIntervals(Cfg); | |
| unsigned Size = Graph.size(); | |
| while (Size > 1 && Size < PrevSize) { | |
| PrevSize = Graph.size(); | |
| Graph = internal::partitionIntoIntervals(Graph); | |
| Size = Graph.size(); | |
| } | |
| if (Size > 1) | |
| // Not reducible. | |
| return std::nullopt; | |
| assert(Size != 0); | |
| return std::move(Graph[0].Nodes); | |
| } | |
| WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) { | |
| if (WTO.empty()) | |
| return; | |
| auto N = WTO[0]->getParent()->getNumBlockIDs(); | |
| BlockOrder.resize(N, 0); | |
| for (unsigned I = 0, S = WTO.size(); I < S; ++I) | |
| BlockOrder[WTO[I]->getBlockID()] = I + 1; | |
| } | |
| } // namespace clang |