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 | |
28 | namespace 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]. |
49 | using WeakTopologicalOrdering = std::vector<const CFGBlock *>; |
50 | std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg); |
51 | |
52 | struct 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 | |
67 | namespace 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. |
75 | struct 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. |
108 | using CFGIntervalGraph = std::deque<CFGIntervalNode>; |
109 | |
110 | std::vector<const CFGBlock *> buildInterval(const CFGBlock *); |
111 | |
112 | // Partitions `Cfg` into intervals and constructs the graph of the intervals |
113 | // based on the edges between nodes in these intervals. |
114 | CFGIntervalGraph 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. |
119 | CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph); |
120 | } // namespace internal |
121 | } // namespace clang |
122 | |
123 | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H |
124 | |