path: root/include/llvm/CodeGen/SchedGraphCommon.h

//===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// A common graph class that is based on the SSA graph. It includes
// extra dependencies that are caused by machine resources.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
#define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H

#include "llvm/Value.h"
#include "llvm/ADT/iterator"
#include "llvm/Support/Streams.h"
#include <vector>

namespace llvm {

class SchedGraphEdge;
class SchedGraphNode;

/******************** Exported Data Types and Constants ********************/

typedef int ResourceId;
const ResourceId InvalidRID        = -1;
const ResourceId MachineCCRegsRID  = -2; // use +ve numbers for actual regs
const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
const ResourceId MachineFPRegsRID  = -4; // use +ve numbers for actual regs


//*********************** Public Class Declarations ************************/
class SchedGraphNodeCommon {
protected:
  unsigned ID;
  std::vector<SchedGraphEdge*> inEdges;
  std::vector<SchedGraphEdge*> outEdges;
  int latency;
  int origIndexInBB;            // original position of instr in BB

public:
  typedef std::vector<SchedGraphEdge*>::iterator iterator;
  typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
  typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator;
  typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;

  // Accessor methods
  unsigned getNodeId() const { return ID; }
  int getLatency() const { return latency; }
  unsigned getNumInEdges() const { return inEdges.size(); }
  unsigned getNumOutEdges() const { return outEdges.size(); }
  int getOrigIndexInBB() const { return origIndexInBB; }

  // Iterators
  iterator beginInEdges() { return inEdges.begin(); }
  iterator endInEdges() { return inEdges.end(); }
  iterator beginOutEdges() { return outEdges.begin(); }
  iterator endOutEdges() { return outEdges.end(); }

  const_iterator beginInEdges() const { return inEdges.begin(); }
  const_iterator endInEdges() const { return inEdges.end(); }
  const_iterator beginOutEdges() const { return outEdges.begin(); }
  const_iterator endOutEdges() const { return outEdges.end(); }

  void dump(int indent=0) const;

  // Debugging support
  void print(llvm_ostream &os) const {
    if (os.stream()) print(*os.stream());
  }
  virtual void print(std::ostream &os) const = 0;

protected:
  friend class SchedGraphCommon;
  friend class SchedGraphEdge;   // give access for adding edges


  // disable default constructor and provide a ctor for single-block graphs
  SchedGraphNodeCommon();  // DO NOT IMPLEMENT

  inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : ID(Id), latency(late), origIndexInBB(index) {}

  virtual ~SchedGraphNodeCommon();

  //Functions to add and remove edges
  inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
  inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
  void removeInEdge(const SchedGraphEdge* edge);
  void removeOutEdge(const SchedGraphEdge* edge);

};

// ostream << operator for SchedGraphNode class
inline llvm_ostream &operator<<(llvm_ostream &os,
                                const SchedGraphNodeCommon &node) {
  node.print(os);
  return os;
}
inline std::ostream &operator<<(std::ostream &os,
                                const SchedGraphNodeCommon &node) {
  node.print(os);
  return os;
}

//
// SchedGraphEdge - Edge class to represent dependencies
//
class SchedGraphEdge {
public:
  enum SchedGraphEdgeDepType {
    CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
  };
  enum DataDepOrderType {
    TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
  };

protected:
  SchedGraphNodeCommon* src;
  SchedGraphNodeCommon* sink;
  SchedGraphEdgeDepType depType;
  unsigned int depOrderType;
  int minDelay; // cached latency (assumes fixed target arch)
  int iteDiff;

  union {
    const Value* val;
    int          machineRegNum;
    ResourceId   resourceId;
  };

public:
  // For all constructors, if minDelay is unspecified, minDelay is
  // set to _src->getLatency().

  // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
  SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
                 SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
                 int _minDelay = -1);

  // constructor for explicit value dependence (may be true/anti/output)
  SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
                 const Value* _val, unsigned int _depOrderType,
                 int _minDelay = -1);

  // constructor for machine register dependence
  SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
                 unsigned int _regNum, unsigned int _depOrderType,
                 int _minDelay = -1);

  // constructor for any other machine resource dependences.
  // DataDepOrderType is always NonDataDep.  It it not an argument to
  // avoid overloading ambiguity with previous constructor.
  SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
                 ResourceId _resourceId, int _minDelay = -1);

  ~SchedGraphEdge() {}

  SchedGraphNodeCommon* getSrc() const { return src; }
  SchedGraphNodeCommon* getSink() const { return sink; }
  int getMinDelay() const { return minDelay; }
  SchedGraphEdgeDepType getDepType() const { return depType; }
  unsigned int getDepOrderType() const { return depOrderType; }

  const Value* getValue() const {
    assert(depType == ValueDep); return val;
  }

  int getMachineReg() const {
    assert(depType == MachineRegister); return machineRegNum;
  }

  int getResourceId() const {
    assert(depType == MachineResource); return resourceId;
  }

  void setIteDiff(int _iteDiff) {
    iteDiff = _iteDiff;
  }

  int getIteDiff() {
    return iteDiff;
  }

public:
  // Debugging support
  void print(llvm_ostream &os) const {
    if (os.stream()) print(*os.stream());
  }
  void print(std::ostream &os) const;
  void dump(int indent=0) const;

private:
  // disable default ctor
  SchedGraphEdge(); // DO NOT IMPLEMENT
};

// ostream << operator for SchedGraphNode class
inline llvm_ostream &operator<<(llvm_ostream &os, const SchedGraphEdge &edge) {
  edge.print(os);
  return os;
}
inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
  edge.print(os);
  return os;
}

class SchedGraphCommon {

protected:
  SchedGraphNodeCommon* graphRoot;     // the root and leaf are not inserted
  SchedGraphNodeCommon* graphLeaf;     //  in the hash_map (see getNumNodes())

public:
  //
  // Accessor methods
  //
  SchedGraphNodeCommon* getRoot() const { return graphRoot; }
  SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }

  //
  // Delete nodes or edges from the graph.
  //
  void eraseNode(SchedGraphNodeCommon* node);
  void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
  void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
  void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);

  SchedGraphCommon() {}
  ~SchedGraphCommon();
};


//********************** Sched Graph Iterators *****************************/

// Ok to make it a template because it shd get instantiated at most twice:
// for <SchedGraphNode, SchedGraphNode::iterator> and
// for <const SchedGraphNode, SchedGraphNode::const_iterator>.
//
template <class _NodeType, class _EdgeType, class _EdgeIter>
class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
protected:
  _EdgeIter oi;
public:
  typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;

  inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}

  inline bool operator==(const _Self& x) const { return oi == x.oi; }
  inline bool operator!=(const _Self& x) const { return !operator==(x); }

  // operator*() differs for pred or succ iterator
  inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
  inline _NodeType* operator->() const { return operator*(); }

  inline _EdgeType* getEdge() const { return *(oi); }

  inline _Self &operator++() { ++oi; return *this; }    // Preincrement
  inline _Self operator++(int) {                        // Postincrement
    _Self tmp(*this); ++*this; return tmp;
  }

  inline _Self &operator--() { --oi; return *this; }    // Predecrement
  inline _Self operator--(int) {                        // Postdecrement
    _Self tmp = *this; --*this; return tmp;
  }
};

template <class _NodeType, class _EdgeType, class _EdgeIter>
class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
protected:
  _EdgeIter oi;
public:
  typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;

  inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}

  inline bool operator==(const _Self& x) const { return oi == x.oi; }
  inline bool operator!=(const _Self& x) const { return !operator==(x); }

  inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
  inline _NodeType* operator->() const { return operator*(); }

  inline _EdgeType* getEdge() const { return *(oi); }

  inline _Self &operator++() { ++oi; return *this; }    // Preincrement
  inline _Self operator++(int) {                        // Postincrement
    _Self tmp(*this); ++*this; return tmp;
  }

  inline _Self &operator--() { --oi; return *this; }    // Predecrement
  inline _Self operator--(int) {                        // Postdecrement
    _Self tmp = *this; --*this; return tmp;
  }
};
} // End llvm namespace

#endif