llvm/clang/include/clang/Analysis/Analyses/IntervalPartition.h

//===- IntervalPartition.h - CFG Partitioning into Intervals -----*- C++-*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  This file defines functionality for partitioning a CFG into intervals and
//  building a weak topological order (WTO) of the nodes, based on the
//  partitioning. The concepts and implementations for the graph partitioning
//  are based on the presentation in "Compilers" by Aho, Sethi and Ullman (the
//  "dragon book"), pages 664-666. The concepts around WTOs is taken from the
//  paper "Efficient chaotic iteration strategies with widenings," by
//  F. Bourdoncle ([Bourdoncle1993]).
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
#define LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H

#include "clang/Analysis/CFG.h"
#include "llvm/ADT/DenseSet.h"
#include <deque>
#include <memory>
#include <vector>

namespace clang {
/// A _weak topological ordering_ (WTO) of CFG nodes provides a total order over
/// the CFG (defined in `WTOCompare`, below), which can guide the order in which
/// to visit nodes in fixpoint computations over the CFG.
///
/// Roughly, a WTO a) groups the blocks so that loop heads are grouped with
/// their bodies and any nodes they dominate after the loop and b) orders the
/// groups topologically. As a result, the blocks in a series of loops are
/// ordered such that all nodes in loop `i` are earlier in the order than nodes
/// in loop `j`. This ordering, when combined with widening, bounds the number
/// of times a node must be visited for a dataflow algorithm to reach a
/// fixpoint. For the precise definition of a WTO and its properties, see
/// [Bourdoncle1993].
///
/// Here, we provide a simplified WTO which drops its nesting structure,
/// maintaining only the ordering itself. The ordering is built from the limit
/// flow graph of `Cfg` (derived from iteratively partitioning it into
/// intervals) if and only if it is reducible (its limit flow graph has one
/// node). Returns `nullopt` when `Cfg` is not reducible.
///
/// This WTO construction is described in Section 4.2 of [Bourdoncle1993].
WeakTopologicalOrdering;
std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg);

struct WTOCompare { … };

namespace internal {
// An interval is a strongly-connected component of the CFG along with a
// trailing acyclic structure. An interval can be constructed directly from CFG
// blocks or from a graph of other intervals. Each interval has one _header_
// block, from which the interval is built. The _header_ of the interval is
// either the graph's entry block or has at least one predecessor outside of the
// interval. All other blocks in the interval have only predecessors also in the
// interval.
struct CFGIntervalNode { … };

// Since graphs are built from pointers to nodes, we use a deque to ensure
// pointer stability.
CFGIntervalGraph;

std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header);

// Partitions `Cfg` into intervals and constructs the graph of the intervals
// based on the edges between nodes in these intervals.
CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg);

// (Further) partitions `Graph` into intervals and constructs the graph of the
// intervals based on the edges between nodes (themselves intervals) in these
// intervals.
CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph);
} // namespace internal
} // namespace clang

#endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H