llvm/clang/lib/Analysis/IntervalPartition.cpp

//===- IntervalPartition.cpp - 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.
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/Analyses/IntervalPartition.h"
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/STLExtras.h"
#include <optional>
#include <queue>
#include <vector>

namespace clang {

// Intermediate data used in constructing a CFGIntervalNode.
template <typename Node> struct BuildResult { … };

namespace internal {
static unsigned getID(const CFGBlock &B) { … }
static unsigned getID(const CFGIntervalNode &I) { … }

// `Node` must be one of `CFGBlock` or `CFGIntervalNode`.
template <typename Node>
BuildResult<Node> buildInterval(llvm::BitVector &Partitioned,
                                const Node *Header) { … }

template <typename Node>
void fillIntervalNode(CFGIntervalGraph &Graph,
                      std::vector<CFGIntervalNode *> &Index,
                      std::queue<const Node *> &Successors,
                      llvm::BitVector &Partitioned, const Node *Header) { … }

template <typename Node>
CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs,
                                            const Node *EntryBlock) { … }

std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header) { … }

CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg) { … }

CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph) { … }
} // namespace internal

std::optional<std::vector<const CFGBlock *>> getIntervalWTO(const CFG &Cfg) { … }

WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) { … }
} // namespace clang