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