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].
using WeakTopologicalOrdering = std::vector<const CFGBlock *>;
std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg);

struct WTOCompare {
  WTOCompare(const WeakTopologicalOrdering &WTO);

  bool operator()(const CFGBlock *B1, const CFGBlock *B2) const {
    auto ID1 = B1->getBlockID();
    auto ID2 = B2->getBlockID();

    unsigned V1 = ID1 >= BlockOrder.size() ? 0 : BlockOrder[ID1];
    unsigned V2 = ID2 >= BlockOrder.size() ? 0 : BlockOrder[ID2];
    return V1 > V2;
  }

  std::vector<unsigned> BlockOrder;
};

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 {
  CFGIntervalNode() = default;
  CFGIntervalNode(unsigned ID) : ID(ID) {}

  CFGIntervalNode(unsigned ID, std::vector<const CFGBlock *> Nodes)
      : ID(ID), Nodes(std::move(Nodes)) {}

  const llvm::SmallDenseSet<const CFGIntervalNode *> &preds() const {
    return Predecessors;
  }
  const llvm::SmallDenseSet<const CFGIntervalNode *> &succs() const {
    return Successors;
  }

  // Unique identifier of this interval relative to other intervals in the same
  // graph.
  unsigned ID;

  std::vector<const CFGBlock *> Nodes;

  // Predessor intervals of this interval: those intervals for which there
  // exists an edge from a node in that other interval to the head of this
  // interval.
  llvm::SmallDenseSet<const CFGIntervalNode *> Predecessors;

  // Successor intervals of this interval: those intervals for which there
  // exists an edge from a node in this interval to the head of that other
  // interval.
  llvm::SmallDenseSet<const CFGIntervalNode *> Successors;
};

// Since graphs are built from pointers to nodes, we use a deque to ensure
// pointer stability.
using CFGIntervalGraph = std::deque<CFGIntervalNode>;

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