1//===- IntervalPartition.h - 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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines functionality for partitioning a CFG into intervals and
10// building a weak topological order (WTO) of the nodes, based on the
11// partitioning. The concepts and implementations for the graph partitioning
12// are based on the presentation in "Compilers" by Aho, Sethi and Ullman (the
13// "dragon book"), pages 664-666. The concepts around WTOs is taken from the
14// paper "Efficient chaotic iteration strategies with widenings," by
15// F. Bourdoncle ([Bourdoncle1993]).
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
20#define LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
21
22#include "clang/Analysis/CFG.h"
23#include "llvm/ADT/DenseSet.h"
24#include <deque>
25#include <memory>
26#include <vector>
27
28namespace clang {
29/// A _weak topological ordering_ (WTO) of CFG nodes provides a total order over
30/// the CFG (defined in `WTOCompare`, below), which can guide the order in which
31/// to visit nodes in fixpoint computations over the CFG.
32///
33/// Roughly, a WTO a) groups the blocks so that loop heads are grouped with
34/// their bodies and any nodes they dominate after the loop and b) orders the
35/// groups topologically. As a result, the blocks in a series of loops are
36/// ordered such that all nodes in loop `i` are earlier in the order than nodes
37/// in loop `j`. This ordering, when combined with widening, bounds the number
38/// of times a node must be visited for a dataflow algorithm to reach a
39/// fixpoint. For the precise definition of a WTO and its properties, see
40/// [Bourdoncle1993].
41///
42/// Here, we provide a simplified WTO which drops its nesting structure,
43/// maintaining only the ordering itself. The ordering is built from the limit
44/// flow graph of `Cfg` (derived from iteratively partitioning it into
45/// intervals) if and only if it is reducible (its limit flow graph has one
46/// node). Returns `nullopt` when `Cfg` is not reducible.
47///
48/// This WTO construction is described in Section 4.2 of [Bourdoncle1993].
49using WeakTopologicalOrdering = std::vector<const CFGBlock *>;
50std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg);
51
52struct WTOCompare {
53 WTOCompare(const WeakTopologicalOrdering &WTO);
54
55 bool operator()(const CFGBlock *B1, const CFGBlock *B2) const {
56 auto ID1 = B1->getBlockID();
57 auto ID2 = B2->getBlockID();
58
59 unsigned V1 = ID1 >= BlockOrder.size() ? 0 : BlockOrder[ID1];
60 unsigned V2 = ID2 >= BlockOrder.size() ? 0 : BlockOrder[ID2];
61 return V1 > V2;
62 }
63
64 std::vector<unsigned> BlockOrder;
65};
66
67namespace internal {
68// An interval is a strongly-connected component of the CFG along with a
69// trailing acyclic structure. An interval can be constructed directly from CFG
70// blocks or from a graph of other intervals. Each interval has one _header_
71// block, from which the interval is built. The _header_ of the interval is
72// either the graph's entry block or has at least one predecessor outside of the
73// interval. All other blocks in the interval have only predecessors also in the
74// interval.
75struct CFGIntervalNode {
76 CFGIntervalNode() = default;
77 CFGIntervalNode(unsigned ID) : ID(ID) {}
78
79 CFGIntervalNode(unsigned ID, std::vector<const CFGBlock *> Nodes)
80 : ID(ID), Nodes(std::move(Nodes)) {}
81
82 const llvm::SmallDenseSet<const CFGIntervalNode *> &preds() const {
83 return Predecessors;
84 }
85 const llvm::SmallDenseSet<const CFGIntervalNode *> &succs() const {
86 return Successors;
87 }
88
89 // Unique identifier of this interval relative to other intervals in the same
90 // graph.
91 unsigned ID;
92
93 std::vector<const CFGBlock *> Nodes;
94
95 // Predessor intervals of this interval: those intervals for which there
96 // exists an edge from a node in that other interval to the head of this
97 // interval.
98 llvm::SmallDenseSet<const CFGIntervalNode *> Predecessors;
99
100 // Successor intervals of this interval: those intervals for which there
101 // exists an edge from a node in this interval to the head of that other
102 // interval.
103 llvm::SmallDenseSet<const CFGIntervalNode *> Successors;
104};
105
106// Since graphs are built from pointers to nodes, we use a deque to ensure
107// pointer stability.
108using CFGIntervalGraph = std::deque<CFGIntervalNode>;
109
110std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header);
111
112// Partitions `Cfg` into intervals and constructs the graph of the intervals
113// based on the edges between nodes in these intervals.
114CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg);
115
116// (Further) partitions `Graph` into intervals and constructs the graph of the
117// intervals based on the edges between nodes (themselves intervals) in these
118// intervals.
119CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph);
120} // namespace internal
121} // namespace clang
122
123#endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
124