path: root/lib/CodeGen/InstrSched/SchedGraph.cpp

//===- SchedGraph.cpp - Scheduling Graph Implementation -------------------===//
//
// Scheduling graph based on SSA graph plus extra dependence edges capturing
// dependences due to machine resources (machine registers, CC registers, and
// any others).
//
//===----------------------------------------------------------------------===//

#include "SchedGraph.h"
#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/Target/TargetRegInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Function.h"
#include "llvm/iOther.h"
#include "Support/StringExtras.h"
#include "Support/STLExtras.h"

//*********************** Internal Data Structures *************************/

// The following two types need to be classes, not typedefs, so we can use
// opaque declarations in SchedGraph.h
// 
struct RefVec: public std::vector<std::pair<SchedGraphNode*, int> > {
  typedef std::vector<std::pair<SchedGraphNode*,int> >::iterator iterator;
  typedef
  std::vector<std::pair<SchedGraphNode*,int> >::const_iterator const_iterator;
};

struct RegToRefVecMap: public hash_map<int, RefVec> {
  typedef hash_map<int, RefVec>::      iterator       iterator;
  typedef hash_map<int, RefVec>::const_iterator const_iterator;
};

struct ValueToDefVecMap: public hash_map<const Value*, RefVec> {
  typedef hash_map<const Value*, RefVec>::      iterator       iterator;
  typedef hash_map<const Value*, RefVec>::const_iterator const_iterator;
};

// 
// class SchedGraphEdge
// 

/*ctor*/
SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
			       SchedGraphNode* _sink,
			       SchedGraphEdgeDepType _depType,
			       unsigned int     _depOrderType,
			       int _minDelay)
  : src(_src),
    sink(_sink),
    depType(_depType),
    depOrderType(_depOrderType),
    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
    val(NULL)
{
  assert(src != sink && "Self-loop in scheduling graph!");
  src->addOutEdge(this);
  sink->addInEdge(this);
}


/*ctor*/
SchedGraphEdge::SchedGraphEdge(SchedGraphNode*  _src,
			       SchedGraphNode*  _sink,
			       const Value*     _val,
			       unsigned int     _depOrderType,
			       int              _minDelay)
  : src(_src),
    sink(_sink),
    depType(ValueDep),
    depOrderType(_depOrderType),
    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
    val(_val)
{
  assert(src != sink && "Self-loop in scheduling graph!");
  src->addOutEdge(this);
  sink->addInEdge(this);
}


/*ctor*/
SchedGraphEdge::SchedGraphEdge(SchedGraphNode*  _src,
			       SchedGraphNode*  _sink,
			       unsigned int     _regNum,
			       unsigned int     _depOrderType,
			       int             _minDelay)
  : src(_src),
    sink(_sink),
    depType(MachineRegister),
    depOrderType(_depOrderType),
    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
    machineRegNum(_regNum)
{
  assert(src != sink && "Self-loop in scheduling graph!");
  src->addOutEdge(this);
  sink->addInEdge(this);
}


/*ctor*/
SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
			       SchedGraphNode* _sink,
			       ResourceId      _resourceId,
			       int             _minDelay)
  : src(_src),
    sink(_sink),
    depType(MachineResource),
    depOrderType(NonDataDep),
    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
    resourceId(_resourceId)
{
  assert(src != sink && "Self-loop in scheduling graph!");
  src->addOutEdge(this);
  sink->addInEdge(this);
}

/*dtor*/
SchedGraphEdge::~SchedGraphEdge()
{
}

void SchedGraphEdge::dump(int indent) const {
  std::cerr << std::string(indent*2, ' ') << *this; 
}


// 
// class SchedGraphNode
// 

/*ctor*/
SchedGraphNode::SchedGraphNode(unsigned NID,
                               MachineBasicBlock *mbb,
                               int   indexInBB,
			       const TargetMachine& Target)
  : nodeId(NID), MBB(mbb), minstr(mbb ? (*mbb)[indexInBB] : 0),
    origIndexInBB(indexInBB), latency(0) {
  if (minstr)
    {
      MachineOpCode mopCode =