242 lines · cpp
1//===- IntervalPartition.cpp - CFG Partitioning into Intervals --*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines functionality for partitioning a CFG into intervals.10//11//===----------------------------------------------------------------------===//12 13#include "clang/Analysis/Analyses/IntervalPartition.h"14#include "clang/Analysis/CFG.h"15#include "llvm/ADT/BitVector.h"16#include "llvm/ADT/STLExtras.h"17#include <optional>18#include <queue>19#include <vector>20 21namespace clang {22 23// Intermediate data used in constructing a CFGIntervalNode.24template <typename Node> struct BuildResult {25 // Use a vector to maintain the insertion order. Given the expected small26 // number of nodes, vector should be sufficiently efficient. Elements must not27 // be null.28 std::vector<const Node *> Nodes;29 // Elements must not be null.30 llvm::SmallDenseSet<const Node *> Successors;31};32 33namespace internal {34static unsigned getID(const CFGBlock &B) { return B.getBlockID(); }35static unsigned getID(const CFGIntervalNode &I) { return I.ID; }36 37// `Node` must be one of `CFGBlock` or `CFGIntervalNode`.38template <typename Node>39static BuildResult<Node> buildInterval(llvm::BitVector &Partitioned,40 const Node *Header) {41 assert(Header != nullptr);42 BuildResult<Node> Interval;43 Interval.Nodes.push_back(Header);44 Partitioned.set(getID(*Header));45 46 // FIXME: Compare performance against using RPO to consider nodes, rather than47 // following successors.48 //49 // Elements must not be null. Duplicates are prevented using `Workset`, below.50 std::queue<const Node *> Worklist;51 llvm::BitVector Workset(Partitioned.size(), false);52 for (const Node *S : Header->succs())53 if (S != nullptr)54 if (auto SID = getID(*S); !Partitioned.test(SID)) {55 // Successors are unique, so we don't test against `Workset` before56 // adding to `Worklist`.57 Worklist.push(S);58 Workset.set(SID);59 }60 61 // Contains successors of blocks in the interval that couldn't be added to the62 // interval on their first encounter. This occurs when they have a predecessor63 // that is either definitively outside the interval or hasn't been considered64 // yet. In the latter case, we'll revisit the block through some other path65 // from the interval. At the end of processing the worklist, we filter out any66 // that ended up in the interval to produce the output set of interval67 // successors. Elements are never null.68 std::vector<const Node *> MaybeSuccessors;69 70 while (!Worklist.empty()) {71 const auto *B = Worklist.front();72 auto ID = getID(*B);73 Worklist.pop();74 Workset.reset(ID);75 76 // Check whether all predecessors are in the interval, in which case `B`77 // is included as well.78 bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) {79 return llvm::is_contained(Interval.Nodes, P);80 });81 if (AllInInterval) {82 Interval.Nodes.push_back(B);83 Partitioned.set(ID);84 for (const Node *S : B->succs())85 if (S != nullptr)86 if (auto SID = getID(*S);87 !Partitioned.test(SID) && !Workset.test(SID)) {88 Worklist.push(S);89 Workset.set(SID);90 }91 } else {92 MaybeSuccessors.push_back(B);93 }94 }95 96 // Any block successors not in the current interval are interval successors.97 for (const Node *B : MaybeSuccessors)98 if (!llvm::is_contained(Interval.Nodes, B))99 Interval.Successors.insert(B);100 101 return Interval;102}103 104template <typename Node>105static void fillIntervalNode(CFGIntervalGraph &Graph,106 std::vector<CFGIntervalNode *> &Index,107 std::queue<const Node *> &Successors,108 llvm::BitVector &Partitioned, const Node *Header) {109 BuildResult<Node> Result = buildInterval(Partitioned, Header);110 for (const auto *S : Result.Successors)111 Successors.push(S);112 113 CFGIntervalNode &Interval = Graph.emplace_back(Graph.size());114 115 // Index the nodes of the new interval. The index maps nodes from the input116 // graph (specifically, `Result.Nodes`) to identifiers of nodes in the output117 // graph. In this case, the new interval has identifier `ID` so all of its118 // nodes (`Result.Nodes`) map to `ID`.119 for (const auto *N : Result.Nodes) {120 assert(N != nullptr);121 assert(getID(*N) < Index.size());122 Index[getID(*N)] = &Interval;123 }124 125 if constexpr (std::is_same_v<std::decay_t<Node>, CFGBlock>)126 Interval.Nodes = std::move(Result.Nodes);127 else {128 std::vector<const CFGBlock *> Nodes;129 // Flatten the sub vectors into a single list.130 size_t Count = 0;131 for (auto &N : Result.Nodes)132 Count += N->Nodes.size();133 Nodes.reserve(Count);134 for (auto &N : Result.Nodes)135 llvm::append_range(Nodes, N->Nodes);136 Interval.Nodes = std::move(Nodes);137 }138}139 140template <typename Node>141static CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs,142 const Node *EntryBlock) {143 assert(EntryBlock != nullptr);144 CFGIntervalGraph Graph;145 // `Index` maps all of the nodes of the input graph to the interval to which146 // they are assigned in the output graph. The values (interval pointers) are147 // never null.148 std::vector<CFGIntervalNode *> Index(NumBlockIDs, nullptr);149 150 // Lists header nodes (from the input graph) and their associated151 // interval. Since header nodes can vary in type and are only needed within152 // this function, we record them separately from `CFGIntervalNode`. This153 // choice enables to express `CFGIntervalNode` without using a variant.154 std::vector<std::pair<const Node *, CFGIntervalNode *>> Intervals;155 llvm::BitVector Partitioned(NumBlockIDs, false);156 std::queue<const Node *> Successors;157 158 fillIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock);159 Intervals.emplace_back(EntryBlock, &Graph.back());160 161 while (!Successors.empty()) {162 const auto *B = Successors.front();163 Successors.pop();164 assert(B != nullptr);165 if (Partitioned.test(getID(*B)))166 continue;167 168 // B has not been partitioned, but it has a predecessor that has. Create a169 // new interval from `B`.170 fillIntervalNode(Graph, Index, Successors, Partitioned, B);171 Intervals.emplace_back(B, &Graph.back());172 }173 174 // Go back and patch up all the Intervals -- the successors and predecessors.175 for (auto [H, N] : Intervals) {176 // Map input-graph predecessors to output-graph nodes and mark those as177 // predecessors of `N`. Then, mark `N` as a successor of said predecessor.178 for (const Node *P : H->preds()) {179 if (P == nullptr)180 continue;181 182 assert(getID(*P) < NumBlockIDs);183 CFGIntervalNode *Pred = Index[getID(*P)];184 if (Pred == nullptr)185 // Unreachable node.186 continue;187 if (Pred != N // Not a backedge.188 && N->Predecessors.insert(Pred).second)189 // Note: given the guard above, which guarantees we only ever insert190 // unique elements, we could use a simple list (like `vector`) for191 // `Successors`, rather than a set.192 Pred->Successors.insert(N);193 }194 }195 196 return Graph;197}198 199std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header) {200 llvm::BitVector Partitioned(Header->getParent()->getNumBlockIDs(), false);201 return buildInterval(Partitioned, Header).Nodes;202}203 204CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg) {205 return partitionIntoIntervalsImpl(Cfg.getNumBlockIDs(), &Cfg.getEntry());206}207 208CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph) {209 return partitionIntoIntervalsImpl(Graph.size(), &Graph[0]);210}211} // namespace internal212 213std::optional<std::vector<const CFGBlock *>> getIntervalWTO(const CFG &Cfg) {214 // Backing storage for the allocated nodes in each graph.215 unsigned PrevSize = Cfg.size();216 if (PrevSize == 0)217 return {};218 internal::CFGIntervalGraph Graph = internal::partitionIntoIntervals(Cfg);219 unsigned Size = Graph.size();220 while (Size > 1 && Size < PrevSize) {221 PrevSize = Graph.size();222 Graph = internal::partitionIntoIntervals(Graph);223 Size = Graph.size();224 }225 if (Size > 1)226 // Not reducible.227 return std::nullopt;228 229 assert(Size != 0);230 return std::move(Graph[0].Nodes);231}232 233WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) {234 if (WTO.empty())235 return;236 auto N = WTO[0]->getParent()->getNumBlockIDs();237 BlockOrder.resize(N, 0);238 for (unsigned I = 0, S = WTO.size(); I < S; ++I)239 BlockOrder[WTO[I]->getBlockID()] = I + 1;240}241} // namespace clang242