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