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 
operatorWTOCompare55   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;
CFGIntervalNodeCFGIntervalNode77   CFGIntervalNode(unsigned ID) : ID(ID) {}
78 
CFGIntervalNodeCFGIntervalNode79   CFGIntervalNode(unsigned ID, std::vector<const CFGBlock *> Nodes)
80       : ID(ID), Nodes(std::move(Nodes)) {}
81 
predsCFGIntervalNode82   const llvm::SmallDenseSet<const CFGIntervalNode *> &preds() const {
83     return Predecessors;
84   }
succsCFGIntervalNode85   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 *Header);
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