RegionInfo.h | Explore in Territory

//===- RegionInfo.h - SESE region analysis ----------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// Calculate a program structure tree built out of single entry single exit
// regions.
// The basic ideas are taken from "The Program Structure Tree - Richard Johnson,
// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The
// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana
// Koehler - 2009".
// The algorithm to calculate these data structures however is completely
// different, as it takes advantage of existing information already available
// in (Post)dominace tree and dominance frontier passes. This leads to a simpler
// and in practice hopefully better performing algorithm. The runtime of the
// algorithms described in the papers above are both linear in graph size,
// O(V+E), whereas this algorithm is not, as the dominance frontier information
// itself is not, but in practice runtime seems to be in the order of magnitude
// of dominance tree calculation.
//
// WARNING: LLVM is generally very concerned about compile time such that
//          the use of additional analysis passes in the default
//          optimization sequence is avoided as much as possible.
//          Specifically, if you do not need the RegionInfo, but dominance
//          information could be sufficient please base your work only on
//          the dominator tree. Most passes maintain it, such that using
//          it has often near zero cost. In contrast RegionInfo is by
//          default not available, is not maintained by existing
//          transformations and there is no intention to do so.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_REGIONINFO_H
#define LLVM_ANALYSIS_REGIONINFO_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Pass.h"
#include <algorithm>
#include <cassert>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <type_traits>
#include <vector>

namespace llvm {

class DominanceFrontier;
class Loop;
class LoopInfo;
class PostDominatorTree;
class Region;
template <class RegionTr> class RegionBase;
class RegionInfo;
template <class RegionTr> class RegionInfoBase;
class RegionNode;
class raw_ostream;

// Class to be specialized for different users of RegionInfo
// (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to
// pass around an unreasonable number of template parameters.
template <class FuncT_>
struct RegionTraits { … };

template <>
struct RegionTraits<Function> { … };

/// Marker class to iterate over the elements of a Region in flat mode.
///
/// The class is used to either iterate in Flat mode or by not using it to not
/// iterate in Flat mode.  During a Flat mode iteration all Regions are entered
/// and the iteration returns every BasicBlock.  If the Flat mode is not
/// selected for SubRegions just one RegionNode containing the subregion is
/// returned.
template <class GraphType>
class FlatIt { … };

/// A RegionNode represents a subregion or a BasicBlock that is part of a
/// Region.
template <class Tr>
class RegionNodeBase { … };

//===----------------------------------------------------------------------===//
/// A single entry single exit Region.
///
/// A Region is a connected subgraph of a control flow graph that has exactly
/// two connections to the remaining graph. It can be used to analyze or
/// optimize parts of the control flow graph.
///
/// A <em> simple Region </em> is connected to the remaining graph by just two
/// edges. One edge entering the Region and another one leaving the Region.
///
/// An <em> extended Region </em> (or just Region) is a subgraph that can be
/// transform into a simple Region. The transformation is done by adding
/// BasicBlocks that merge several entry or exit edges so that after the merge
/// just one entry and one exit edge exists.
///
/// The \e Entry of a Region is the first BasicBlock that is passed after
/// entering the Region. It is an element of the Region. The entry BasicBlock
/// dominates all BasicBlocks in the Region.
///
/// The \e Exit of a Region is the first BasicBlock that is passed after
/// leaving the Region. It is not an element of the Region. The exit BasicBlock,
/// postdominates all BasicBlocks in the Region.
///
/// A <em> canonical Region </em> cannot be constructed by combining smaller
/// Regions.
///
/// Region A is the \e parent of Region B, if B is completely contained in A.
///
/// Two canonical Regions either do not intersect at all or one is
/// the parent of the other.
///
/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
/// Regions in the control flow graph and E is the \e parent relation of these
/// Regions.
///
/// Example:
///
/// \verbatim
/// A simple control flow graph, that contains two regions.
///
///        1
///       / |
///      2   |
///     / \   3
///    4   5  |
///    |   |  |
///    6   7  8
///     \  | /
///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
///        9        Region B: 2 -> 9 {2,4,5,6,7}
/// \endverbatim
///
/// You can obtain more examples by either calling
///
/// <tt> "opt -passes='print<regions>' anyprogram.ll" </tt>
/// or
/// <tt> "opt -view-regions-only anyprogram.ll" </tt>
///
/// on any LLVM file you are interested in.
///
/// The first call returns a textual representation of the program structure
/// tree, the second one creates a graphical representation using graphviz.
template <class Tr>
class RegionBase : public RegionNodeBase<Tr> { … };

/// Print a RegionNode.
template <class Tr>
inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node);

//===----------------------------------------------------------------------===//
/// Analysis that detects all canonical Regions.
///
/// The RegionInfo pass detects all canonical regions in a function. The Regions
/// are connected using the parent relation. This builds a Program Structure
/// Tree.
template <class Tr>
class RegionInfoBase { … };

class RegionNode : public RegionNodeBase<RegionTraits<Function>> { … };

class Region : public RegionBase<RegionTraits<Function>> { … };

class RegionInfo : public RegionInfoBase<RegionTraits<Function>> { … };

class RegionInfoPass : public FunctionPass { … };

/// Analysis pass that exposes the \c RegionInfo for a function.
class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> { … };

/// Printer pass for the \c RegionInfo.
class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> { … };

/// Verifier pass for the \c RegionInfo.
struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> { … };

template <>
template <>
inline BasicBlock *
RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const { … }

template <>
template <>
inline Region *
RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const { … }

template <class Tr>
inline raw_ostream &operator<<(raw_ostream &OS,
                               const RegionNodeBase<Tr> &Node) { … }

extern template class RegionBase<RegionTraits<Function>>;
extern template class RegionNodeBase<RegionTraits<Function>>;
extern template class RegionInfoBase<RegionTraits<Function>>;

} // end namespace llvm

#endif // LLVM_ANALYSIS_REGIONINFO_H
llvm/llvm/include/llvm/Analysis/RegionInfo.h
