llvm.org GIT mirror llvm / release_23 include / llvm / CodeGen / SchedGraphCommon.h
release_23

Tree @release_23 (Download .tar.gz)

SchedGraphCommon.h @release_23

4848689
ea61c35
6fbcc26
 
7ed47a1
 
ea61c35
6fbcc26
0320b14
 
 
 
4848689
0320b14
 
 
 
 
551ccae
b5ebf15
ea2c1dc
0320b14
d0fde30
 
0320b14
 
 
 
 
 
 
 
 
 
 
 
1796cb7
0320b14
 
 
 
 
 
f68b8a2
0320b14
 
1796cb7
 
 
0320b14
ea61c35
0320b14
1796cb7
 
 
 
f68b8a2
0320b14
 
1796cb7
00876a2
1796cb7
 
ea61c35
1796cb7
 
 
 
0320b14
1796cb7
0320b14
 
1796cb7
5c7e326
ea61c35
0320b14
 
00876a2
ea61c35
 
0320b14
00876a2
ea61c35
b4b2e9d
ea61c35
0320b14
ea61c35
1796cb7
 
 
 
 
ea61c35
0320b14
 
1796cb7
ea61c35
00876a2
1796cb7
 
 
 
 
 
 
0320b14
 
 
 
 
 
 
 
ea61c35
0320b14
00876a2
 
0320b14
1796cb7
 
 
ea61c35
0320b14
 
 
 
 
1796cb7
00876a2
0320b14
 
ea61c35
0320b14
1796cb7
00876a2
 
ea61c35
0320b14
1796cb7
00876a2
 
ea61c35
0320b14
1796cb7
00876a2
 
ea61c35
0320b14
 
 
1796cb7
00876a2
ea61c35
d04087c
ea61c35
00876a2
 
1796cb7
 
b4b2e9d
 
1796cb7
0320b14
 
1796cb7
 
0320b14
 
1796cb7
 
0320b14
 
1796cb7
 
0320b14
 
1796cb7
 
0320b14
 
ea61c35
0320b14
 
1796cb7
5c7e326
1796cb7
ea61c35
0320b14
 
00876a2
0320b14
 
1796cb7
 
 
 
 
0320b14
 
ea61c35
0320b14
1796cb7
 
0320b14
 
 
 
 
1796cb7
ea61c35
 
0320b14
 
ea61c35
1796cb7
 
 
 
ea61c35
d04087c
1796cb7
0320b14
 
a105c80
 
 
 
 
 
ea61c35
a105c80
 
 
 
 
 
ea61c35
a105c80
ea61c35
a105c80
 
ea61c35
a105c80
 
 
ea61c35
a105c80
ea61c35
a105c80
00876a2
ea61c35
a105c80
ea61c35
a105c80
00876a2
a105c80
 
 
 
 
 
 
 
 
 
ea61c35
a105c80
ea61c35
a105c80
 
ea61c35
a105c80
 
ea61c35
a105c80
ea61c35
a105c80
00876a2
ea61c35
a105c80
ea61c35
a105c80
00876a2
a105c80
 
 
d0fde30
 
0320b14
//===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file 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
  virtual void print(std::ostream &os) const = 0;
  void print(std::ostream *os) const { if (os) print(*os); }

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 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(std::ostream &os) const;
  void print(std::ostream *os) const { if (os) print(*os); }
  void dump(int indent=0) const;

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

// ostream << operator for SchedGraphNode class
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