llvm/llvm/include/llvm/Analysis/LoopIterator.h

//===--------- LoopIterator.h - Iterate over loop blocks --------*- 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 iterators to visit the basic blocks within a loop.
//
// These iterators currently visit blocks within subloops as well.
// Unfortunately we have no efficient way of summarizing loop exits which would
// allow skipping subloops during traversal.
//
// If you want to visit all blocks in a loop and don't need an ordered traveral,
// use Loop::block_begin() instead.
//
// This is intentionally designed to work with ill-formed loops in which the
// backedge has been deleted. The only prerequisite is that all blocks
// contained within the loop according to the most recent LoopInfo analysis are
// reachable from the loop header.
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LOOPITERATOR_H
#define LLVM_ANALYSIS_LOOPITERATOR_H

#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/LoopInfo.h"

namespace llvm {

class LoopBlocksTraversal;

// A traits type that is intended to be used in graph algorithms. The graph
// traits starts at the loop header, and traverses the BasicBlocks that are in
// the loop body, but not the loop header. Since the loop header is skipped,
// the back edges are excluded.
//
// TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
//       LoopBodyTraits, so that insertEdge doesn't have to be specialized.
struct LoopBodyTraits { … };

/// Store the result of a depth first search within basic blocks contained by a
/// single loop.
///
/// TODO: This could be generalized for any CFG region, or the entire CFG.
class LoopBlocksDFS { … };

/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
/// interface for the DFS reverse post-order traversal of blocks in a loop body.
class LoopBlocksRPO { … };

/// Specialize po_iterator_storage to record postorder numbers.
template<> class po_iterator_storage<LoopBlocksTraversal, true> { … };

/// Traverse the blocks in a loop using a depth-first search.
class LoopBlocksTraversal { … };

inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
    std::optional<BasicBlock *> From, BasicBlock *To) { … }

inline void po_iterator_storage<LoopBlocksTraversal, true>::
finishPostorder(BasicBlock *BB) { … }

} // End namespace llvm

#endif