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. The 10 // concepts and implementations are based on the presentation in "Compilers" by 11 // Aho, Sethi and Ullman (the "dragon book"), pages 664-666. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H 16 #define LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H 17 18 #include "clang/Analysis/CFG.h" 19 #include "llvm/ADT/DenseSet.h" 20 #include <vector> 21 22 namespace clang { 23 24 // An interval is a strongly-connected component of the CFG along with a 25 // trailing acyclic structure. The _header_ of the interval is either the CFG 26 // entry block or has at least one predecessor outside of the interval. All 27 // other blocks in the interval have only predecessors also in the interval. 28 struct CFGInterval { 29 CFGInterval(const CFGBlock *Header) : Header(Header), Blocks({Header}) {} 30 31 // The block from which the interval was constructed. Is either the CFG entry 32 // block or has at least one predecessor outside the interval. 33 const CFGBlock *Header; 34 35 llvm::SmallDenseSet<const CFGBlock *> Blocks; 36 37 // Successor blocks of the *interval*: blocks outside the interval for 38 // reachable (in one edge) from within the interval. 39 llvm::SmallDenseSet<const CFGBlock *> Successors; 40 }; 41 42 CFGInterval buildInterval(const CFG &Cfg, const CFGBlock &Header); 43 44 // Partitions `Cfg` into intervals and constructs a graph of the intervals, 45 // based on the edges between nodes in these intervals. 46 std::vector<CFGInterval> partitionIntoIntervals(const CFG &Cfg); 47 48 } // namespace clang 49 50 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H 51