Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- 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 contains the declaration of the Interval class, which

// represents a set of CFG nodes and is a portion of an interval partition.

//

// Intervals have some interesting and useful properties, including the

// following:

//    1. The header node of an interval dominates all of the elements of the

//       interval

//

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

#ifndef LLVM_ANALYSIS_INTERVAL_H

#define LLVM_ANALYSIS_INTERVAL_H

#include "llvm/ADT/GraphTraits.h"

#include <vector>

namespace llvm {

class BasicBlock;

class raw_ostream;

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

//

/// Interval Class - An Interval is a set of nodes defined such that every node

/// in the interval has all of its predecessors in the interval (except for the

/// header)

///

class Interval {

  /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this

  /// interval.  Also, any loops in this interval must go through the HeaderNode.

  ///

  BasicBlock *HeaderNode;

public:

  using succ_iterator = std::vector<BasicBlock*>::iterator;

  using pred_iterator = std::vector<BasicBlock*>::iterator;

  using node_iterator = std::vector<BasicBlock*>::iterator;

  inline Interval(BasicBlock *Header) : HeaderNode(Header) {

    Nodes.push_back(Header);

  }

  inline BasicBlock *getHeaderNode() const { return HeaderNode; }

  /// Nodes - The basic blocks in this interval.

  std::vector<BasicBlock*> Nodes;

  /// Successors - List of BasicBlocks that are reachable directly from nodes in

  /// this interval, but are not in the interval themselves.

  /// These nodes necessarily must be header nodes for other intervals.

  std::vector<BasicBlock*> Successors;

  /// Predecessors - List of BasicBlocks that have this Interval's header block

  /// as one of their successors.

  std::vector<BasicBlock*> Predecessors;

  /// contains - Find out if a basic block is in this interval

  inline bool contains(BasicBlock *BB) const {

    for (BasicBlock *Node : Nodes)

      if (Node == BB)

        return true;

    return false;

    // I don't want the dependency on <algorithm>

    //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();

  }

  /// isSuccessor - find out if a basic block is a successor of this Interval

  inline bool isSuccessor(BasicBlock *BB) const {

    for (BasicBlock *Successor : Successors)

      if (Successor == BB)

        return true;

    return false;

    // I don't want the dependency on <algorithm>

    //return find(Successors.begin(), Successors.end(), BB) != Successors.end();

  }

  /// Equality operator.  It is only valid to compare two intervals from the

  /// same partition, because of this, all we have to check is the header node

  /// for equality.

  inline bool operator==(const Interval &I) const {

    return HeaderNode == I.HeaderNode;

  }

  /// print - Show contents in human readable format...

  void print(raw_ostream &O) const;

};

/// succ_begin/succ_end - define methods so that Intervals may be used

/// just like BasicBlocks can with the succ_* functions, and *::succ_iterator.

///

inline Interval::succ_iterator succ_begin(Interval *I) {

  return I->Successors.begin();

}

inline Interval::succ_iterator succ_end(Interval *I)   {

  return I->Successors.end();

}

/// pred_begin/pred_end - define methods so that Intervals may be used

/// just like BasicBlocks can with the pred_* functions, and *::pred_iterator.

///

inline Interval::pred_iterator pred_begin(Interval *I) {

  return I->Predecessors.begin();

}

inline Interval::pred_iterator pred_end(Interval *I)   {

  return I->Predecessors.end();

}

template <> struct GraphTraits<Interval*> {

  using NodeRef = Interval *;

  using ChildIteratorType = Interval::succ_iterator;

  static NodeRef getEntryNode(Interval *I) { return I; }

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

  static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }

  static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }

};

template <> struct GraphTraits<Inverse<Interval*>> {

  using NodeRef = Interval *;

  using ChildIteratorType = Interval::pred_iterator;

  static NodeRef getEntryNode(Inverse<Interval *> G) { return G.Graph; }

  static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }

  static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }

};

} // end namespace llvm

#endif // LLVM_ANALYSIS_INTERVAL_H