Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- GenericCycleInfo.h - Info for Cycles in any IR ------*- 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

//

//===----------------------------------------------------------------------===//

///

/// \file

/// \brief Find all cycles in a control-flow graph, including irreducible loops.

///

/// See docs/CycleTerminology.rst for a formal definition of cycles.

///

/// Briefly:

/// - A cycle is a generalization of a loop which can represent

///   irreducible control flow.

/// - Cycles identified in a program are implementation defined,

///   depending on the DFS traversal chosen.

/// - Cycles are well-nested, and form a forest with a parent-child

///   relationship.

/// - In any choice of DFS, every natural loop L is represented by a

///   unique cycle C which is a superset of L.

/// - In the absence of irreducible control flow, the cycles are

///   exactly the natural loops in the program.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_GENERICCYCLEINFO_H

#define LLVM_ADT_GENERICCYCLEINFO_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/GenericSSAContext.h"

#include "llvm/ADT/GraphTraits.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/iterator.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/Printable.h"

#include "llvm/Support/raw_ostream.h"

#include <vector>

namespace llvm {

template <typename ContextT> class GenericCycleInfo;

template <typename ContextT> class GenericCycleInfoCompute;

/// A possibly irreducible generalization of a \ref Loop.

template <typename ContextT> class GenericCycle {

public:

  using BlockT = typename ContextT::BlockT;

  using FunctionT = typename ContextT::FunctionT;

  template <typename> friend class GenericCycleInfo;

  template <typename> friend class GenericCycleInfoCompute;

private:

  /// The parent cycle. Is null for the root "cycle". Top-level cycles point

  /// at the root.

  GenericCycle *ParentCycle = nullptr;

  /// The entry block(s) of the cycle. The header is the only entry if

  /// this is a loop. Is empty for the root "cycle", to avoid

  /// unnecessary memory use.

  SmallVector<BlockT *, 1> Entries;

  /// Child cycles, if any.

  std::vector<std::unique_ptr<GenericCycle>> Children;

  /// Basic blocks that are contained in the cycle, including entry blocks,

  /// and including blocks that are part of a child cycle.

  std::vector<BlockT *> Blocks;

  /// Depth of the cycle in the tree. The root "cycle" is at depth 0.

  ///

  /// \note Depths are not necessarily contiguous. However, child loops always

  ///       have strictly greater depth than their parents, and sibling loops

  ///       always have the same depth.

  unsigned Depth = 0;

  void clear() {

    Entries.clear();

    Children.clear();

    Blocks.clear();

    Depth = 0;

    ParentCycle = nullptr;

  }

  void appendEntry(BlockT *Block) { Entries.push_back(Block); }

  void appendBlock(BlockT *Block) { Blocks.push_back(Block); }

  GenericCycle(const GenericCycle &) = delete;

  GenericCycle &operator=(const GenericCycle &) = delete;

  GenericCycle(GenericCycle &&Rhs) = delete;

  GenericCycle &operator=(GenericCycle &&Rhs) = delete;

public:

  GenericCycle() = default;

  /// \brief Whether the cycle is a natural loop.

  bool isReducible() const { return Entries.size() == 1; }

  BlockT *getHeader() const { return Entries[0]; }

  const SmallVectorImpl<BlockT *> & getEntries() const {

    return Entries;

  }

  /// \brief Return whether \p Block is an entry block of the cycle.

  bool isEntry(const BlockT *Block) const {

    return is_contained(Entries, Block);

  }

  /// \brief Return whether \p Block is contained in the cycle.

  bool contains(const BlockT *Block) const {

    return is_contained(Blocks, Block);

  }

  /// \brief Returns true iff this cycle contains \p C.

  ///

  /// Note: Non-strict containment check, i.e. returns true if C is the

  /// same cycle.

  bool contains(const GenericCycle *C) const;

  const GenericCycle *getParentCycle() const { return ParentCycle; }

  GenericCycle *getParentCycle() { return ParentCycle; }

  unsigned getDepth() const { return Depth; }

  /// Return all of the successor blocks of this cycle.

  ///

  /// These are the blocks _outside of the current cycle_ which are

  /// branched to.

  void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;

  /// Return the preheader block for this cycle. Pre-header is well-defined for

  /// reducible cycle in docs/LoopTerminology.rst as: the only one entering

  /// block and its only edge is to the entry block. Return null for irreducible

  /// cycles.

  BlockT *getCyclePreheader() const;

  /// If the cycle has exactly one entry with exactly one predecessor, return

  /// it, otherwise return nullptr.

  BlockT *getCyclePredecessor() const;

  /// Iteration over child cycles.

  //@{

  using const_child_iterator_base =

      typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;

  struct const_child_iterator

      : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {

    using Base =

        iterator_adaptor_base<const_child_iterator, const_child_iterator_base>;

    const_child_iterator() = default;

    explicit const_child_iterator(const_child_iterator_base I) : Base(I) {}

    const const_child_iterator_base &wrapped() { return Base::wrapped(); }

    GenericCycle *operator*() const { return Base::I->get(); }

  };

  const_child_iterator child_begin() const {

    return const_child_iterator{Children.begin()};

  }

  const_child_iterator child_end() const {

    return const_child_iterator{Children.end()};

  }

  size_t getNumChildren() const { return Children.size(); }

  iterator_range<const_child_iterator> children() const {

    return llvm::make_range(const_child_iterator{Children.begin()},

                            const_child_iterator{Children.end()});

  }

  //@}

  /// Iteration over blocks in the cycle (including entry blocks).

  //@{

  using const_block_iterator = typename std::vector<BlockT *>::const_iterator;

  const_block_iterator block_begin() const {

    return const_block_iterator{Blocks.begin()};

  }

  const_block_iterator block_end() const {

    return const_block_iterator{Blocks.end()};

  }

  size_t getNumBlocks() const { return Blocks.size(); }

  iterator_range<const_block_iterator> blocks() const {

    return llvm::make_range(block_begin(), block_end());

  }

  //@}

  /// Iteration over entry blocks.

  //@{

  using const_entry_iterator =

      typename SmallVectorImpl<BlockT *>::const_iterator;

  size_t getNumEntries() const { return Entries.size(); }

  iterator_range<const_entry_iterator> entries() const {

    return llvm::make_range(Entries.begin(), Entries.end());

  }

  //@}

  Printable printEntries(const ContextT &Ctx) const {

    return Printable([this, &Ctx](raw_ostream &Out) {

      bool First = true;

      for (auto *Entry : Entries) {

        if (!First)

          Out << ' ';

        First = false;

        Out << Ctx.print(Entry);

      }

    });

  }

  Printable print(const ContextT &Ctx) const {

    return Printable([this, &Ctx](raw_ostream &Out) {

      Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')';

      for (auto *Block : Blocks) {

        if (isEntry(Block))

          continue;

        Out << ' ' << Ctx.print(Block);

      }

    });

  }

};

/// \brief Cycle information for a function.

template <typename ContextT> class GenericCycleInfo {

public:

  using BlockT = typename ContextT::BlockT;

  using CycleT = GenericCycle<ContextT>;

  using FunctionT = typename ContextT::FunctionT;

  template <typename> friend class GenericCycle;

  template <typename> friend class GenericCycleInfoCompute;

private:

  ContextT Context;

  /// Map basic blocks to their inner-most containing cycle.

  DenseMap<BlockT *, CycleT *> BlockMap;

  /// Map basic blocks to their top level containing cycle.

  DenseMap<BlockT *, CycleT *> BlockMapTopLevel;

  /// Top-level cycles discovered by any DFS.

  ///

  /// Note: The implementation treats the nullptr as the parent of

  /// every top-level cycle. See \ref contains for an example.

  std::vector<std::unique_ptr<CycleT>> TopLevelCycles;

  /// Move \p Child to \p NewParent by manipulating Children vectors.

  ///

  /// Note: This is an incomplete operation that does not update the depth of

  /// the subtree.

  void moveTopLevelCycleToNewParent(CycleT *NewParent, CycleT *Child);

public:

  GenericCycleInfo() = default;

  GenericCycleInfo(GenericCycleInfo &&) = default;

  GenericCycleInfo &operator=(GenericCycleInfo &&) = default;

  void clear();

  void compute(FunctionT &F);

  FunctionT *getFunction() const { return Context.getFunction(); }

  const ContextT &getSSAContext() const { return Context; }

  CycleT *getCycle(const BlockT *Block) const;

  unsigned getCycleDepth(const BlockT *Block) const;

  CycleT *getTopLevelParentCycle(BlockT *Block);

  /// Methods for debug and self-test.

  //@{

#ifndef NDEBUG

  bool validateTree() const;

#endif

  void print(raw_ostream &Out) const;

  void dump() const { print(dbgs()); }

  //@}

  /// Iteration over top-level cycles.

  //@{

  using const_toplevel_iterator_base =

      typename std::vector<std::unique_ptr<CycleT>>::const_iterator;

  struct const_toplevel_iterator

      : iterator_adaptor_base<const_toplevel_iterator,

                              const_toplevel_iterator_base> {

    using Base = iterator_adaptor_base<const_toplevel_iterator,

                                       const_toplevel_iterator_base>;

    const_toplevel_iterator() = default;

    explicit const_toplevel_iterator(const_toplevel_iterator_base I)

        : Base(I) {}

    const const_toplevel_iterator_base &wrapped() { return Base::wrapped(); }

    CycleT *operator*() const { return Base::I->get(); }

  };

  const_toplevel_iterator toplevel_begin() const {

    return const_toplevel_iterator{TopLevelCycles.begin()};

  }

  const_toplevel_iterator toplevel_end() const {

    return const_toplevel_iterator{TopLevelCycles.end()};

  }

  iterator_range<const_toplevel_iterator> toplevel_cycles() const {

    return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()},

                            const_toplevel_iterator{TopLevelCycles.end()});

  }

  //@}

};

/// \brief GraphTraits for iterating over a sub-tree of the CycleT tree.

template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {

  using NodeRef = CycleRefT;

  using nodes_iterator = ChildIteratorT;

  using ChildIteratorType = nodes_iterator;

  static NodeRef getEntryNode(NodeRef Graph) { return Graph; }

  static ChildIteratorType child_begin(NodeRef Ref) {

    return Ref->child_begin();

  }

  static ChildIteratorType child_end(NodeRef Ref) { return Ref->child_end(); }

  // Not implemented:

  // static nodes_iterator nodes_begin(GraphType *G)

  // static nodes_iterator nodes_end  (GraphType *G)

  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph

  // typedef EdgeRef           - Type of Edge token in the graph, which should

  //                             be cheap to copy.

  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in

  //                             graph, dereference to a EdgeRef.

  // static ChildEdgeIteratorType child_edge_begin(NodeRef)

  // static ChildEdgeIteratorType child_edge_end(NodeRef)

  //     Return iterators that point to the beginning and ending of the

  //     edge list for the given callgraph node.

  //

  // static NodeRef edge_dest(EdgeRef)

  //     Return the destination node of an edge.

  // static unsigned       size       (GraphType *G)

  //    Return total number of nodes in the graph

};

template <typename BlockT>

struct GraphTraits<const GenericCycle<BlockT> *>

    : CycleGraphTraits<const GenericCycle<BlockT> *,

                       typename GenericCycle<BlockT>::const_child_iterator> {};

template <typename BlockT>

struct GraphTraits<GenericCycle<BlockT> *>

    : CycleGraphTraits<GenericCycle<BlockT> *,

                       typename GenericCycle<BlockT>::const_child_iterator> {};

} // namespace llvm

#endif // LLVM_ADT_GENERICCYCLEINFO_H