First version of SchedGraph common class and refactoring of SchedGraph.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8148 91177308-0d34-0410-b5e6-96231b3b80d8

10 files changed, 706 insertions, 962 deletions

diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp
index ae19a0635e..00a6a557f2 100644
--- a/lib/CodeGen/InstrSched/InstrScheduling.cpp
+++ b/lib/CodeGen/InstrSched/InstrScheduling.cpp
@@ -1047,8 +1047,8 @@ NodeCanFillDelaySlot(const SchedulingManager& S,
   
   for (SchedGraphNode::const_iterator EI = node->beginInEdges();
        EI != node->endInEdges(); ++EI)
-    if (! (*EI)->getSrc()->isDummyNode()
-	&& mii.isLoad((*EI)->getSrc()->getOpCode())
+    if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
+	&& mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpCode())
 	&& (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
       return false;
   
@@ -1065,7 +1065,7 @@ NodeCanFillDelaySlot(const SchedulingManager& S,
     bool onlyCDEdgeToBranch = true;
     for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
          OEI != node->endOutEdges(); ++OEI)
-      if (! (*OEI)->getSink()->isDummyNode()
+      if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
           && ((*OEI)->getSink() != brNode
               || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
       {
diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp
index 899e188dab..b058448566 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.cpp
+++ b/lib/CodeGen/InstrSched/SchedGraph.cpp
@@ -7,16 +7,21 @@
 //===----------------------------------------------------------------------===//
 
 #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/CodeGen/SchedGraphCommon.h"
+#include <iostream>
+
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
+#include "Support/STLExtras.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Target/TargetRegInfo.h"
 #include "llvm/Function.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/InstrSelection.h"
 #include "llvm/iOther.h"
 #include "Support/StringExtras.h"
-#include "Support/STLExtras.h"
+
 
 //*********************** Internal Data Structures *************************/
 
@@ -39,93 +44,6 @@ struct ValueToDefVecMap: public hash_map<const Value*, RefVec> {
   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
@@ -136,11 +54,11 @@ 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)
+  : SchedGraphNodeCommon(NID), origIndexInBB(indexInBB), MBB(mbb), MI(mbb ? (*mbb)[indexInBB] : 0)
+  {
+  if (MI)
     {
-      MachineOpCode mopCode = minstr->getOpCode();
+      MachineOpCode mopCode = MI->getOpCode();
       latency = Target.getInstrInfo().hasResultInterlock(mopCode)
 	? Target.getInstrInfo().minLatency(mopCode)
 	: Target.getInstrInfo().maxLatency(mopCode);
@@ -156,51 +74,6 @@ SchedGraphNode::~SchedGraphNode()
                 deleter<SchedGraphEdge>);
 }
 
-void SchedGraphNode::dump(int indent) const {
-  std::cerr << std::string(indent*2, ' ') << *this; 
-}
-
-
-inline void
-SchedGraphNode::addInEdge(SchedGraphEdge* edge)
-{
-  inEdges.push_back(edge);
-}
-
-
-inline void
-SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
-{
-  outEdges.push_back(edge);
-}
-
-inline void
-SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
-{
-  assert(edge->getSink() == this);
-  
-  for (iterator I = beginInEdges(); I != endInEdges(); ++I)
-    if ((*I) == edge)
-      {
-	inEdges.erase(I);
-	break;
-      }
-}
-
-inline void
-SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
-{
-  assert(edge->getSrc() == this);
-  
-  for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
-    if ((*I) == edge)
-      {
-	outEdges.erase(I);
-	break;
-      }
-}
-
-
 // 
 // class SchedGraph
 // 
@@ -243,62 +116,6 @@ SchedGraph::dump() const
 }
 
 
-void
-SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
-  // Delete and disconnect all in-edges for the node
-  for (SchedGraphNode::iterator I = node->beginInEdges();
-       I != node->endInEdges(); ++I)
-  {
-    SchedGraphNode* srcNode = (*I)->getSrc();
-    srcNode->removeOutEdge(*I);
-    delete *I;
-      
-    if (addDummyEdges &&
-        srcNode != getRoot() &&
-        srcNode->beginOutEdges() == srcNode->endOutEdges())
-    { 
-      // srcNode has no more out edges, so add an edge to dummy EXIT node
-      assert(node != getLeaf() && "Adding edge that was just removed?");
-      (void) new SchedGraphEdge(srcNode, getLeaf(),
-                        SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
-    }
-  }
-  
-  node->inEdges.clear();
-}
-
-void
-SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
-  // Delete and disconnect all out-edges for the node
-  for (SchedGraphNode::iterator I = node->beginOutEdges();
-       I != node->endOutEdges(); ++I)
-  {
-    SchedGraphNode* sinkNode = (*I)->getSink();
-    sinkNode->removeInEdge(*I);
-    delete *I;
-      
-    if (addDummyEdges &&
-        sinkNode != getLeaf() &&
-        sinkNode->beginInEdges() == sinkNode->endInEdges())
-    { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
-      assert(node != getRoot() && "Adding edge that was just removed?");
-      (void) new SchedGraphEdge(getRoot(), sinkNode,
-                        SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
-    }
-  }
-  
-  node->outEdges.clear();
-}
-
-void
-SchedGraph::eraseIncidentEdges(SchedGraphNode* node, bool addDummyEdges)
-{
-  this->eraseIncomingEdges(node, addDummyEdges);	
-  this->eraseOutgoingEdges(node, addDummyEdges);	
-}
-
 
 void
 SchedGraph::addDummyEdges()
@@ -697,10 +514,10 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
   
   // Collect the register references and value defs. for explicit operands
   // 
-  const MachineInstr& minstr = *node->getMachineInstr();
-  for (int i=0, numOps = (int) minstr.getNumOperands(); i < numOps; i++)
+  const MachineInstr& MI = *node->getMachineInstr();
+  for (int i=0, numOps = (int) MI.getNumOperands(); i < numOps; i++)
   {
-    const MachineOperand& mop = minstr.getOperand(i);
+    const MachineOperand& mop = MI.getOperand(i);
       
     // if this references a register other than the hardwired
     // "zero" register, record the reference.
@@ -728,8 +545,8 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
     }
     
     // ignore all other non-def operands
-    if (!minstr.getOperand(i).opIsDefOnly() &&
-        !minstr.getOperand(i).opIsDefAndUse())
+    if (!MI.getOperand(i).opIsDefOnly() &&
+        !MI.getOperand(i).opIsDefAndUse())
       continue;
       
     // We must be defining a value.
@@ -745,21 +562,21 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
   // Collect value defs. for implicit operands.  They may have allocated
   // physical registers also.
   // 
-  for (unsigned i=0, N = minstr.getNumImplicitRefs(); i != N; ++i)
+  for (unsigned i=0, N = MI.getNumImplicitRefs(); i != N; ++i)
   {
-    const MachineOperand& mop = minstr.getImplicitOp(i);
+    const MachineOperand& mop = MI.getImplicitOp(i);
     if (mop.hasAllocatedReg())
     {
       int regNum = mop.getAllocatedRegNum();
       if (regNum != target.getRegInfo().getZeroRegNum())
         regToRefVecMap[mop.getAllocatedRegNum()]
-          .push_back(std::make_pair(node, i + minstr.getNumOperands()));
+          .push_back(std::make_pair(node, i + MI.getNumOperands()));
       continue;                     // nothing more to do
     }
 
     if (mop.opIsDefOnly() || mop.opIsDefAndUse()) {
-      assert(minstr.getImplicitRef(i) != NULL && "Null value being defined?");
-      valueToDefVecMap[minstr.getImplicitRef(i)].push_back(std::make_pair(node,
+      assert(MI.getImplicitRef(i) != NULL && "Null value being defined?");
+      valueToDefVecMap[MI.getImplicitRef(i)].push_back(std::make_pair(node,
                                                                           -i)); 
     }
   }
@@ -885,9 +702,9 @@ SchedGraph::buildGraph(const TargetMachine& target)
 /*ctor*/
 SchedGraphSet::SchedGraphSet(const Function* _function,
 			     const TargetMachine& target) :
-  method(_function)
+  function(_function)
 {
-  buildGraphsForMethod(method, target);
+  buildGraphsForMethod(function, target);
 }
 
 
@@ -903,13 +720,13 @@ SchedGraphSet::~SchedGraphSet()
 void
 SchedGraphSet::dump() const
 {
-  std::cerr << "======== Sched graphs for function `" << method->getName()
+  std::cerr << "======== Sched graphs for function `" << function->getName()
             << "' ========\n\n";
   
   for (const_iterator I=begin(); I != end(); ++I)
     (*I)->dump();
   
-  std::cerr << "\n====== End graphs for function `" << method->getName()
+  std::cerr << "\n====== End graphs for function `" << function->getName()
             << "' ========\n\n";
 }
 
@@ -946,7 +763,7 @@ std::ostream &operator<<(std::ostream &os, const SchedGraphEdge& edge)
 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node)
 {
   os << std::string(8, ' ')
-     << "Node " << node.nodeId << " : "
+     << "Node " << node.ID << " : "
      << "latency = " << node.latency << "\n" << std::string(12, ' ');
   
   if (node.getMachineInstr() == NULL)
diff --git a/lib/CodeGen/InstrSched/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h
index 2b7e44965b..82e5dd619b 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.h
+++ b/lib/CodeGen/InstrSched/SchedGraph.h
@@ -17,264 +17,80 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "Support/GraphTraits.h"
 #include "Support/hash_map"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
 
-class Value;
-class Instruction;
-class TerminatorInst;
-class BasicBlock;
-class Function;
-class TargetMachine;
-class SchedGraphEdge; 
-class SchedGraphNode; 
-class SchedGraph; 
 class RegToRefVecMap;
 class ValueToDefVecMap;
 class RefVec;
-class MachineInstr;
-class MachineBasicBlock;
 
+class SchedGraphNode : public SchedGraphNodeCommon {
 
-/******************** 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 SchedGraphEdge {
-  SchedGraphEdge(const SchedGraphEdge &);  // DO NOT IMPLEMENT
-  void operator=(const SchedGraphEdge &);  // DO NOT IMPLEMENT
-public:
-  enum SchedGraphEdgeDepType {
-    CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
-  };
-  enum DataDepOrderType {
-    TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
-  };
-  
-private:
-  SchedGraphNode*	src;
-  SchedGraphNode*	sink;
-  SchedGraphEdgeDepType depType;
-  unsigned int          depOrderType;
-  int			minDelay; // cached latency (assumes fixed target arch)
-  
-  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
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       SchedGraphEdgeDepType _depType,
-				       unsigned int     _depOrderType,
-				       int _minDelay = -1);
-  
-  // constructor for explicit value dependence (may be true/anti/output)
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       const Value*    _val,
-				       unsigned int     _depOrderType,
-				       int _minDelay = -1);
-  
-  // constructor for machine register dependence
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _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.
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       ResourceId      _resourceId,
-				       int _minDelay = -1);
-  
-  /*dtor*/		~SchedGraphEdge();
-  
-  SchedGraphNode*	getSrc		() const { return src; }
-  SchedGraphNode*	getSink		() const { return sink; }
-  int			getMinDelay	() const { return minDelay; }
-  SchedGraphEdgeDepType getDepType	() const { return depType; }
-  
-  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;
-  }
-  
-public:
-  // 
-  // Debugging support
-  // 
-  friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
-  
-  void		dump	(int indent=0) const;
-    
-private:
-  // disable default ctor
-  /*ctor*/		SchedGraphEdge();	// DO NOT IMPLEMENT
-};
+  int origIndexInBB;            // original position of machine instr in BB
+  MachineBasicBlock *MBB;
+  const MachineInstr *MI;
 
 
+  SchedGraphNode (unsigned nodeId, MachineBasicBlock *mbb,
+		  int   indexInBB, const TargetMachine& Target);
+  ~SchedGraphNode	();
 
-class SchedGraphNode {
-  unsigned nodeId;
-  MachineBasicBlock *MBB;
-  const MachineInstr* minstr;
-  std::vector<SchedGraphEdge*> inEdges;
-  std::vector<SchedGraphEdge*> outEdges;
-  int origIndexInBB;            // original position of machine instr in BB
-  int latency;
+  friend class SchedGraph;		// give access for ctor and dtor
+  friend class SchedGraphEdge;		// give access for adding edges
 
-  SchedGraphNode(const SchedGraphNode &);  // DO NOT IMPLEMENT
-  void operator=(const SchedGraphNode &);  // DO NOT IMPLEMENT
-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;
-  
 public:
-  //
   // Accessor methods
-  // 
-  unsigned              getNodeId	() const { return nodeId; }
-  const MachineInstr*   getMachineInstr	() const { return minstr; }
-  const MachineOpCode   getOpCode	() const { return minstr->getOpCode(); }
-  int                   getLatency	() const { return latency; }
-  unsigned              getNumInEdges	() const { return inEdges.size(); }
-  unsigned              getNumOutEdges	() const { return outEdges.size(); }
-  bool			isDummyNode	() const { return (minstr == NULL); }
+  const MachineInstr*   getMachineInstr	() const { return MI; }
+  const MachineOpCode   getOpCode	() const { return MI->getOpCode(); }
+  bool			isDummyNode	() const { return (MI == NULL); }
   MachineBasicBlock    &getMachineBasicBlock() const { return *MBB; }
-  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(); }
-  
-public:
-  //
-  // Debugging support
-  // 
-  friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
-  
-  void		dump	(int indent=0) const;
-  
-private:
-  friend class SchedGraph;		// give access for ctor and dtor
-  friend class SchedGraphEdge;		// give access for adding edges
-  
-  void			addInEdge	(SchedGraphEdge* edge);
-  void			addOutEdge	(SchedGraphEdge* edge);
-  
-  void			removeInEdge	(const SchedGraphEdge* edge);
-  void			removeOutEdge	(const SchedGraphEdge* edge);
-  
-  // disable default constructor and provide a ctor for single-block graphs
-  /*ctor*/		SchedGraphNode();	// DO NOT IMPLEMENT
-  /*ctor*/		SchedGraphNode	(unsigned nodeId,
-                                         MachineBasicBlock *mbb,
-                                         int   indexInBB,
-					 const TargetMachine& Target);
-  /*dtor*/		~SchedGraphNode	();
-};
-
 
+  int               getOrigIndexInBB() const { return origIndexInBB; }
+};
 
-class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
-  MachineBasicBlock &MBB;               // basic blocks for this graph
-  SchedGraphNode* graphRoot;		// the root and leaf are not inserted
-  SchedGraphNode* graphLeaf;		//  in the hash_map (see getNumNodes())
+class SchedGraph : public SchedGraphCommon {
+  MachineBasicBlock &MBB;
+  hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
   
-  typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
-  SchedGraph(const SchedGraph &);       // DO NOT IMPLEMENT
-  void operator=(const SchedGraph &);   // DO NOT IMPLEMENT
 public:
-  using map_base::iterator;
-  using map_base::const_iterator;
-  
-public:
-  //
-  // Accessor methods
-  //
-  MachineBasicBlock               &getBasicBlock()  const { return MBB; }
-  unsigned                         getNumNodes()    const { return size()+2; }
-  SchedGraphNode*		   getRoot()	    const { return graphRoot; }
-  SchedGraphNode*		   getLeaf()	    const { return graphLeaf; }
-  
-  SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
-    const_iterator onePair = this->find(minstr);
-    return (onePair != this->end())? (*onePair).second : NULL;
+  typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
+  typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
+    
+  MachineBasicBlock&               getBasicBlock() const{return MBB;}
+  const unsigned int		   getNumNodes()    const { return GraphMap.size()+2; }
+  SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
+    const_iterator onePair = find(MI);
+    return (onePair != end())? onePair->second : NULL;
   }
   
-  //
-  // Delete nodes or edges from the graph.
-  // 
-  void		eraseNode		(SchedGraphNode* node);
-  
-  void		eraseIncomingEdges	(SchedGraphNode* node,
-					 bool addDummyEdges = true);
-  
-  void		eraseOutgoingEdges	(SchedGraphNode* node,
-					 bool addDummyEdges = true);
-  
-  void		eraseIncidentEdges	(SchedGraphNode* node,
-					 bool addDummyEdges = true);
+  // Debugging support
+  void		dump	() const;
   
-  //
-  // Unordered iterators.
-  // Return values is pair<const MachineIntr*,SchedGraphNode*>.
-  //
-  using map_base::begin;
-  using map_base::end;
+protected:
+  SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
+  ~SchedGraph();
 
-  //
-  // Ordered iterators.
+  // Unordered iterators.
   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
   //
-  // void			   postord_init();
-  // postorder_iterator	   postord_begin();
-  // postorder_iterator	   postord_end();
-  // const_postorder_iterator postord_begin() const;
-  // const_postorder_iterator postord_end() const;
+  hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
+    return GraphMap.begin();
+  }
+  hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
+    return GraphMap.end();
+  }
+ 
+  unsigned size() { return GraphMap.size(); }
+  iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
   
-  //
-  // Debugging support
-  // 
-  void		dump	() const;
+  SchedGraphNode *&operator[](const MachineInstr *MI) {
+    return GraphMap[MI];
+  }
   
 private:
   friend class SchedGraphSet;		// give access to ctor
   
-  // disable default constructor and provide a ctor for single-block graphs
-  /*ctor*/	SchedGraph		(MachineBasicBlock &bb,
-					 const TargetMachine& target);
-  /*dtor*/	~SchedGraph		();
+ 
   
   inline void	noteGraphNodeForInstr	(const MachineInstr* minstr,
 					 SchedGraphNode* node)
@@ -288,12 +104,13 @@ private:
   //
   void  	buildGraph		(const TargetMachine& target);
   
-  void          buildNodesForBB         (const TargetMachine& target,
+   void          buildNodesForBB         (const TargetMachine& target,
                                          MachineBasicBlock &MBB,
                                          std::vector<SchedGraphNode*>& memNV,
                                          std::vector<SchedGraphNode*>& callNV,
                                          RegToRefVecMap& regToRefVecMap,
                                          ValueToDefVecMap& valueToDefVecMap);
+
   
   void          findDefUseInfoAtInstr   (const TargetMachine& target,
                                          SchedGraphNode* node,
@@ -301,6 +118,7 @@ private:
                                          std::vector<SchedGraphNode*>& callNV,
                                          RegToRefVecMap& regToRefVecMap,
                                          ValueToDefVecMap& valueToDefVecMap);
+
                                          
   void		addEdgesForInstruction(const MachineInstr& minstr,
                                      const ValueToDefVecMap& valueToDefVecMap,
@@ -309,12 +127,15 @@ private:
   void		addCDEdges		(const TerminatorInst* term,
 					 const TargetMachine& target);
   
-  void		addMemEdges         (const std::vector<SchedGraphNode*>& memNV,
+  void		addMemEdges         (const std::vector<SchedGraphNode*>& memNod,
                                      const TargetMachine& target);
   
+  void          addCallCCEdges      (const std::vector<SchedGraphNode*>& memNod,
+                                     MachineBasicBlock& bbMvec,
+                                     const TargetMachine& target);
   void          addCallDepEdges     (const std::vector<SchedGraphNode*>& callNV,
                                      const TargetMachine& target);
-    
+  
   void		addMachineRegEdges	(RegToRefVecMap& regToRefVecMap,
 					 const TargetMachine& target);
   
@@ -324,44 +145,41 @@ private:
                                          bool  refNodeIsDef,
                                          bool  refNodeIsDefAndUse,
 					 const TargetMachine& target);
-  
-  void		addDummyEdges		();
+  void          addDummyEdges();
+
 };
 
 
-class SchedGraphSet : private std::vector<SchedGraph*> {
-private:
-  const Function* method;
 
-  SchedGraphSet(const SchedGraphSet&);    // DO NOT IMPLEMENT
-  void operator=(const SchedGraphSet&);   // DO NOT IMPLEMENT
-public:
-  typedef std::vector<SchedGraph*> baseVector;
-  using baseVector::iterator;
-  using baseVector::const_iterator;
-  
+class SchedGraphSet {
+  const Function* function;
+  std::vector<SchedGraph*> Graphs;
+
+  // Graph builder
+  void buildGraphsForMethod (const Function *F, const TargetMachine& target);
+
+  inline void addGraph(SchedGraph* graph) {
+    assert(graph != NULL);
+    Graphs.push_back(graph);
+  }  
+
 public:
-  SchedGraphSet(const Function *F, const TargetMachine &TM);
+  SchedGraphSet(const Function * function, const TargetMachine& target);
   ~SchedGraphSet();
   
-  // Iterators
-  using baseVector::begin;
-  using baseVector::end;
-  
+  //iterators
+  typedef std::vector<SchedGraph*>::const_iterator iterator;
+  typedef std::vector<SchedGraph*>::const_iterator const_iterator;
+
+  std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
+  std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
+
   // Debugging support
   void dump() const;
-  
-private:
-  inline void	addGraph(SchedGraph* graph) {
-    assert(graph != NULL);
-    this->push_back(graph);
-  }
-  
-  // Graph builder
-  void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
 };
 
 
+
 //********************** Sched Graph Iterators *****************************/
 
 // Ok to make it a template because it shd get instantiated at most twice:
@@ -381,7 +199,7 @@ public:
   inline bool operator!=(const _Self& x) const { return !operator==(x); }
   
   // operator*() differs for pred or succ iterator
-  inline _NodeType* operator*() const { return (*oi)->getSrc(); }
+  inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
   inline	 _NodeType* operator->() const { return operator*(); }
   
   inline _EdgeType* getEdge() const { return *(oi); }
@@ -409,7 +227,7 @@ public:
   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 (*oi)->getSink(); }
+  inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
   inline	 _NodeType* operator->() const { return operator*(); }
   
   inline _EdgeType* getEdge() const { return *(oi); }
@@ -477,7 +295,7 @@ template <> struct GraphTraits<SchedGraph*> {
   typedef SchedGraphNode NodeType;
   typedef sg_succ_iterator ChildIteratorType;
 
-  static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
+  static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
   static inline ChildIteratorType child_begin(NodeType *N) { 
     return succ_begin(N); 
   }
@@ -491,7 +309,7 @@ template <> struct GraphTraits<const SchedGraph*> {
   typedef sg_succ_const_iterator ChildIteratorType;
 
   static inline NodeType *getEntryNode(const SchedGraph *SG) {
-    return SG->getRoot();
+    return (NodeType*)SG->getRoot();
   }
   static inline ChildIteratorType child_begin(NodeType *N) { 
     return succ_begin(N); 
diff --git a/lib/CodeGen/InstrSched/SchedGraphCommon.cpp b/lib/CodeGen/InstrSched/SchedGraphCommon.cpp
new file mode 100644
index 0000000000..287a6796fb
--- /dev/null
+++ b/lib/CodeGen/InstrSched/SchedGraphCommon.cpp
@@ -0,0 +1,237 @@
+#include "llvm/CodeGen/SchedGraphCommon.h"
+#include "Support/STLExtras.h"
+
+class SchedGraphCommon;
+
+// 
+// class SchedGraphEdge
+// 
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+			       SchedGraphNodeCommon* _sink,
+			       SchedGraphEdgeDepType _depType,
+			       unsigned int     _depOrderType,
+			       int _minDelay)
+  : src(_src),
+    sink(_sink),
+    depType(_depType),
+    depOrderType(_depOrderType),
+    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+    val(NULL)
+{
+  iteDiff=0;
+  assert(src != sink && "Self-loop in scheduling graph!");
+  src->addOutEdge(this);
+  sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon*  _src,
+			       SchedGraphNodeCommon*  _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)
+{
+  iteDiff=0;
+  assert(src != sink && "Self-loop in scheduling graph!");
+  src->addOutEdge(this);
+  sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon*  _src,
+			       SchedGraphNodeCommon*  _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)
+{
+  iteDiff=0;
+  assert(src != sink && "Self-loop in scheduling graph!");
+  src->addOutEdge(this);
+  sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+			       SchedGraphNodeCommon* _sink,
+			       ResourceId      _resourceId,
+			       int             _minDelay)
+  : src(_src),
+    sink(_sink),
+    depType(MachineResource),
+    depOrderType(NonDataDep),
+    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+    resourceId(_resourceId)
+{
+  iteDiff=0;
+  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; 
+}
+
+
+
+/*ctor*/           
+
+SchedGraphNodeCommon::SchedGraphNodeCommon(unsigned  _nodeId)
+  :ID(_nodeId),
+   latency(0){
+  
+}
+
+/*dtor*/
+SchedGraphNodeCommon::~SchedGraphNodeCommon()
+{
+  // for each node, delete its out-edges
+  std::for_each(beginOutEdges(), endOutEdges(),
+                deleter<SchedGraphEdge>);
+}
+
+
+void SchedGraphNodeCommon::dump(int indent) const {
+  std::cerr << std::string(indent*2, ' ') << *this; 
+}
+
+
+inline void
+SchedGraphNodeCommon::addInEdge(SchedGraphEdge* edge)
+{
+  inEdges.push_back(edge);
+}
+
+
+inline void
+SchedGraphNodeCommon::addOutEdge(SchedGraphEdge* edge)
+{
+  outEdges.push_back(edge);
+}
+
+inline void
+SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge)
+{
+  assert(edge->getSink() == this);
+  
+  for (iterator I = beginInEdges(); I != endInEdges(); ++I)
+    if ((*I) == edge)
+      {
+	inEdges.erase(I);
+	break;
+      }
+}
+
+inline void
+SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge)
+{
+  assert(edge->getSrc() == this);
+  
+  for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
+    if ((*I) == edge)
+      {
+	outEdges.erase(I);
+	break;
+      }
+}
+
+
+//class SchedGraphCommon
+
+/*ctor*/
+SchedGraphCommon::SchedGraphCommon()
+{ 
+}
+
+
+/*dtor*/
+SchedGraphCommon::~SchedGraphCommon()
+{
+
+  delete graphRoot;
+  delete graphLeaf;
+}
+
+
+void
+SchedGraphCommon::eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+  // Delete and disconnect all in-edges for the node
+  for (SchedGraphNodeCommon::iterator I = node->beginInEdges();
+       I != node->endInEdges(); ++I)
+    {
+      SchedGraphNodeCommon* srcNode = (*I)->getSrc();
+      srcNode->removeOutEdge(*I);
+      delete *I;
+      
+      if (addDummyEdges &&
+	  srcNode != getRoot() &&
+	  srcNode->beginOutEdges() == srcNode->endOutEdges())
+	{ // srcNode has no more out edges, so add an edge to dummy EXIT node
+	  assert(node != getLeaf() && "Adding edge that was just removed?");
+	  (void) new SchedGraphEdge(srcNode, getLeaf(),
+		    SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+	}
+    }
+  
+  node->inEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+  // Delete and disconnect all out-edges for the node
+  for (SchedGraphNodeCommon::iterator I = node->beginOutEdges();
+       I != node->endOutEdges(); ++I)
+    {
+      SchedGraphNodeCommon* sinkNode = (*I)->getSink();
+      sinkNode->removeInEdge(*I);
+      delete *I;
+      
+      if (addDummyEdges &&
+	  sinkNode != getLeaf() &&
+	  sinkNode->beginInEdges() == sinkNode->endInEdges())
+	{ //sinkNode has no more in edges, so add an edge from dummy ENTRY node
+	  assert(node != getRoot() && "Adding edge that was just removed?");
+	  (void) new SchedGraphEdge(getRoot(), sinkNode,
+		    SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+	}
+    }
+  
+  node->outEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+  this->eraseIncomingEdges(node, addDummyEdges);	
+  this->eraseOutgoingEdges(node, addDummyEdges);	
+}
+
+std::ostream &operator<<(std::ostream &os, const SchedGraphNodeCommon& node)
+{
+  
+  return os;
+}
diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp
index b60a33bcfd..20c0f8217a 100644
--- a/lib/CodeGen/InstrSched/SchedPriorities.cpp
+++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp
@@ -59,7 +59,7 @@ SchedPriorities::computeDelays(const SchedGraph* graph)
 	  for (SchedGraphNode::const_iterator E=node->beginOutEdges();
 	       E != node->endOutEdges(); ++E)
 	    {
-	      cycles_t sinkDelay = getNodeDelay((*E)->getSink());
+	      cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
 	      nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
 	    }
 	}
@@ -71,7 +71,7 @@ SchedPriorities::computeDelays(const SchedGraph* graph)
 void
 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
 {
-  const SchedGraphNode* graphRoot = graph->getRoot();
+  const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
   assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
   
   // Insert immediate successors of dummy root, which are the actual roots
@@ -137,7 +137,7 @@ SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
   for (SchedGraphNode::const_iterator E=node->beginOutEdges();
        E != node->endOutEdges(); ++E)
     {
-      cycles_t& etime = getEarliestReadyTimeForNodeRef((*E)->getSink());
+      cycles_t& etime = getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
       etime = std::max(etime, curTime + (*E)->getMinDelay());
     }    
 }
diff --git a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp
index ae19a0635e..00a6a557f2 100644
--- a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp
+++ b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp
@@ -1047,8 +1047,8 @@ NodeCanFillDelaySlot(const SchedulingManager& S,
   
   for (SchedGraphNode::const_iterator EI = node->beginInEdges();
        EI != node->endInEdges(); ++EI)
-    if (! (*EI)->getSrc()->isDummyNode()
-	&& mii.isLoad((*EI)->getSrc()->getOpCode())
+    if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
+	&& mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpCode())
 	&& (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
       return false;
   
@@ -1065,7 +1065,7 @@ NodeCanFillDelaySlot(const SchedulingManager& S,
     bool onlyCDEdgeToBranch = true;
     for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
          OEI != node->endOutEdges(); ++OEI)
-      if (! (*OEI)->getSink()->isDummyNode()
+      if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
           && ((*OEI)->getSink() != brNode
               || (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
       {
diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp
index 899e188dab..b058448566 100644
--- a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp
+++ b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp
@@ -7,16 +7,21 @@
 //===----------------------------------------------------------------------===//
 
 #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/CodeGen/SchedGraphCommon.h"
+#include <iostream>
+
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
+#include "Support/STLExtras.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Target/TargetRegInfo.h"
 #include "llvm/Function.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/InstrSelection.h"
 #include "llvm/iOther.h"
 #include "Support/StringExtras.h"
-#include "Support/STLExtras.h"
+
 
 //*********************** Internal Data Structures *************************/
 
@@ -39,93 +44,6 @@ struct ValueToDefVecMap: public hash_map<const Value*, RefVec> {
   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
@@ -136,11 +54,11 @@ 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)
+  : SchedGraphNodeCommon(NID), origIndexInBB(indexInBB), MBB(mbb), MI(mbb ? (*mbb)[indexInBB] : 0)
+  {
+  if (MI)
     {
-      MachineOpCode mopCode = minstr->getOpCode();
+      MachineOpCode mopCode = MI->getOpCode();
       latency = Target.getInstrInfo().hasResultInterlock(mopCode)
 	? Target.getInstrInfo().minLatency(mopCode)
 	: Target.getInstrInfo().maxLatency(mopCode);
@@ -156,51 +74,6 @@ SchedGraphNode::~SchedGraphNode()
                 deleter<SchedGraphEdge>);
 }
 
-void SchedGraphNode::dump(int indent) const {
-  std::cerr << std::string(indent*2, ' ') << *this; 
-}
-
-
-inline void
-SchedGraphNode::addInEdge(SchedGraphEdge* edge)
-{
-  inEdges.push_back(edge);
-}
-
-
-inline void
-SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
-{
-  outEdges.push_back(edge);
-}
-
-inline void
-SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
-{
-  assert(edge->getSink() == this);
-  
-  for (iterator I = beginInEdges(); I != endInEdges(); ++I)
-    if ((*I) == edge)
-      {
-	inEdges.erase(I);
-	break;
-      }
-}
-
-inline void
-SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
-{
-  assert(edge->getSrc() == this);
-  
-  for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
-    if ((*I) == edge)
-      {
-	outEdges.erase(I);
-	break;
-      }
-}
-
-
 // 
 // class SchedGraph
 // 
@@ -243,62 +116,6 @@ SchedGraph::dump() const
 }
 
 
-void
-SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
-  // Delete and disconnect all in-edges for the node
-  for (SchedGraphNode::iterator I = node->beginInEdges();
-       I != node->endInEdges(); ++I)
-  {
-    SchedGraphNode* srcNode = (*I)->getSrc();
-    srcNode->removeOutEdge(*I);
-    delete *I;
-      
-    if (addDummyEdges &&
-        srcNode != getRoot() &&
-        srcNode->beginOutEdges() == srcNode->endOutEdges())
-    { 
-      // srcNode has no more out edges, so add an edge to dummy EXIT node
-      assert(node != getLeaf() && "Adding edge that was just removed?");
-      (void) new SchedGraphEdge(srcNode, getLeaf(),
-                        SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
-    }
-  }
-  
-  node->inEdges.clear();
-}
-
-void
-SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
-  // Delete and disconnect all out-edges for the node
-  for (SchedGraphNode::iterator I = node->beginOutEdges();
-       I != node->endOutEdges(); ++I)
-  {
-    SchedGraphNode* sinkNode = (*I)->getSink();
-    sinkNode->removeInEdge(*I);
-    delete *I;
-      
-    if (addDummyEdges &&
-        sinkNode != getLeaf() &&
-        sinkNode->beginInEdges() == sinkNode->endInEdges())
-    { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
-      assert(node != getRoot() && "Adding edge that was just removed?");
-      (void) new SchedGraphEdge(getRoot(), sinkNode,
-                        SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
-    }
-  }
-  
-  node->outEdges.clear();
-}
-
-void
-SchedGraph::eraseIncidentEdges(SchedGraphNode* node, bool addDummyEdges)
-{
-  this->eraseIncomingEdges(node, addDummyEdges);	
-  this->eraseOutgoingEdges(node, addDummyEdges);	
-}
-
 
 void
 SchedGraph::addDummyEdges()
@@ -697,10 +514,10 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
   
   // Collect the register references and value defs. for explicit operands
   // 
-  const MachineInstr& minstr = *node->getMachineInstr();
-  for (int i=0, numOps = (int) minstr.getNumOperands(); i < numOps; i++)
+  const MachineInstr& MI = *node->getMachineInstr();
+  for (int i=0, numOps = (int) MI.getNumOperands(); i < numOps; i++)
   {
-    const MachineOperand& mop = minstr.getOperand(i);
+    const MachineOperand& mop = MI.getOperand(i);
       
     // if this references a register other than the hardwired
     // "zero" register, record the reference.
@@ -728,8 +545,8 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
     }
     
     // ignore all other non-def operands
-    if (!minstr.getOperand(i).opIsDefOnly() &&
-        !minstr.getOperand(i).opIsDefAndUse())
+    if (!MI.getOperand(i).opIsDefOnly() &&
+        !MI.getOperand(i).opIsDefAndUse())
       continue;
       
     // We must be defining a value.
@@ -745,21 +562,21 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
   // Collect value defs. for implicit operands.  They may have allocated
   // physical registers also.
   // 
-  for (unsigned i=0, N = minstr.getNumImplicitRefs(); i != N; ++i)
+  for (unsigned i=0, N = MI.getNumImplicitRefs(); i != N; ++i)
   {
-    const MachineOperand& mop = minstr.getImplicitOp(i);
+    const MachineOperand& mop = MI.getImplicitOp(i);
     if (mop.hasAllocatedReg())
     {
       int regNum = mop.getAllocatedRegNum();
       if (regNum != target.getRegInfo().getZeroRegNum())
         regToRefVecMap[mop.getAllocatedRegNum()]
-          .push_back(std::make_pair(node, i + minstr.getNumOperands()));
+          .push_back(std::make_pair(node, i + MI.getNumOperands()));
       continue;                     // nothing more to do
     }
 
     if (mop.opIsDefOnly() || mop.opIsDefAndUse()) {
-      assert(minstr.getImplicitRef(i) != NULL && "Null value being defined?");
-      valueToDefVecMap[minstr.getImplicitRef(i)].push_back(std::make_pair(node,
+      assert(MI.getImplicitRef(i) != NULL && "Null value being defined?");
+      valueToDefVecMap[MI.getImplicitRef(i)].push_back(std::make_pair(node,
                                                                           -i)); 
     }
   }
@@ -885,9 +702,9 @@ SchedGraph::buildGraph(const TargetMachine& target)
 /*ctor*/
 SchedGraphSet::SchedGraphSet(const Function* _function,
 			     const TargetMachine& target) :
-  method(_function)
+  function(_function)
 {
-  buildGraphsForMethod(method, target);
+  buildGraphsForMethod(function, target);
 }
 
 
@@ -903,13 +720,13 @@ SchedGraphSet::~SchedGraphSet()
 void
 SchedGraphSet::dump() const
 {
-  std::cerr << "======== Sched graphs for function `" << method->getName()
+  std::cerr << "======== Sched graphs for function `" << function->getName()
             << "' ========\n\n";
   
   for (const_iterator I=begin(); I != end(); ++I)
     (*I)->dump();
   
-  std::cerr << "\n====== End graphs for function `" << method->getName()
+  std::cerr << "\n====== End graphs for function `" << function->getName()
             << "' ========\n\n";
 }
 
@@ -946,7 +763,7 @@ std::ostream &operator<<(std::ostream &os, const SchedGraphEdge& edge)
 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node)
 {
   os << std::string(8, ' ')
-     << "Node " << node.nodeId << " : "
+     << "Node " << node.ID << " : "
      << "latency = " << node.latency << "\n" << std::string(12, ' ');
   
   if (node.getMachineInstr() == NULL)
diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.h b/lib/Target/SparcV9/InstrSched/SchedGraph.h
index 2b7e44965b..82e5dd619b 100644
--- a/lib/Target/SparcV9/InstrSched/SchedGraph.h
+++ b/lib/Target/SparcV9/InstrSched/SchedGraph.h
@@ -17,264 +17,80 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "Support/GraphTraits.h"
 #include "Support/hash_map"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
 
-class Value;
-class Instruction;
-class TerminatorInst;
-class BasicBlock;
-class Function;
-class TargetMachine;
-class SchedGraphEdge; 
-class SchedGraphNode; 
-class SchedGraph; 
 class RegToRefVecMap;
 class ValueToDefVecMap;
 class RefVec;
-class MachineInstr;
-class MachineBasicBlock;
 
+class SchedGraphNode : public SchedGraphNodeCommon {
 
-/******************** 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 SchedGraphEdge {
-  SchedGraphEdge(const SchedGraphEdge &);  // DO NOT IMPLEMENT
-  void operator=(const SchedGraphEdge &);  // DO NOT IMPLEMENT
-public:
-  enum SchedGraphEdgeDepType {
-    CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
-  };
-  enum DataDepOrderType {
-    TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
-  };
-  
-private:
-  SchedGraphNode*	src;
-  SchedGraphNode*	sink;
-  SchedGraphEdgeDepType depType;
-  unsigned int          depOrderType;
-  int			minDelay; // cached latency (assumes fixed target arch)
-  
-  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
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       SchedGraphEdgeDepType _depType,
-				       unsigned int     _depOrderType,
-				       int _minDelay = -1);
-  
-  // constructor for explicit value dependence (may be true/anti/output)
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       const Value*    _val,
-				       unsigned int     _depOrderType,
-				       int _minDelay = -1);
-  
-  // constructor for machine register dependence
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _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.
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       ResourceId      _resourceId,
-				       int _minDelay = -1);
-  
-  /*dtor*/		~SchedGraphEdge();
-  
-  SchedGraphNode*	getSrc		() const { return src; }
-  SchedGraphNode*	getSink		() const { return sink; }
-  int			getMinDelay	() const { return minDelay; }
-  SchedGraphEdgeDepType getDepType	() const { return depType; }
-  
-  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;
-  }
-  
-public:
-  // 
-  // Debugging support
-  // 
-  friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
-  
-  void		dump	(int indent=0) const;
-    
-private:
-  // disable default ctor
-  /*ctor*/		SchedGraphEdge();	// DO NOT IMPLEMENT
-};
+  int origIndexInBB;            // original position of machine instr in BB
+  MachineBasicBlock *MBB;
+  const MachineInstr *MI;
 
 
+  SchedGraphNode (unsigned nodeId, MachineBasicBlock *mbb,
+		  int   indexInBB, const TargetMachine& Target);
+  ~SchedGraphNode	();
 
-class SchedGraphNode {
-  unsigned nodeId;
-  MachineBasicBlock *MBB;
-  const MachineInstr* minstr;
-  std::vector<SchedGraphEdge*> inEdges;
-  std::vector<SchedGraphEdge*> outEdges;
-  int origIndexInBB;            // original position of machine instr in BB
-  int latency;
+  friend class SchedGraph;		// give access for ctor and dtor
+  friend class SchedGraphEdge;		// give access for adding edges
 
-  SchedGraphNode(const SchedGraphNode &);  // DO NOT IMPLEMENT
-  void operator=(const SchedGraphNode &);  // DO NOT IMPLEMENT
-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;
-  
 public:
-  //
   // Accessor methods
-  // 
-  unsigned              getNodeId	() const { return nodeId; }
-  const MachineInstr*   getMachineInstr	() const { return minstr; }
-  const MachineOpCode   getOpCode	() const { return minstr->getOpCode(); }
-  int                   getLatency	() const { return latency; }
-  unsigned              getNumInEdges	() const { return inEdges.size(); }
-  unsigned              getNumOutEdges	() const { return outEdges.size(); }
-  bool			isDummyNode	() const { return (minstr == NULL); }
+  const MachineInstr*   getMachineInstr	() const { return MI; }
+  const MachineOpCode   getOpCode	() const { return MI->getOpCode(); }
+  bool			isDummyNode	() const { return (MI == NULL); }
   MachineBasicBlock    &getMachineBasicBlock() const { return *MBB; }
-  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(); }
-  
-public:
-  //
-  // Debugging support
-  // 
-  friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
-  
-  void		dump	(int indent=0) const;
-  
-private:
-  friend class SchedGraph;		// give access for ctor and dtor
-  friend class SchedGraphEdge;		// give access for adding edges
-  
-  void			addInEdge	(SchedGraphEdge* edge);
-  void			addOutEdge	(SchedGraphEdge* edge);
-  
-  void			removeInEdge	(const SchedGraphEdge* edge);
-  void			removeOutEdge	(const SchedGraphEdge* edge);
-  
-  // disable default constructor and provide a ctor for single-block graphs
-  /*ctor*/		SchedGraphNode();	// DO NOT IMPLEMENT
-  /*ctor*/		SchedGraphNode	(unsigned nodeId,
-                                         MachineBasicBlock *mbb,
-                                         int   indexInBB,
-					 const TargetMachine& Target);
-  /*dtor*/		~SchedGraphNode	();
-};
-
 
+  int               getOrigIndexInBB() const { return origIndexInBB; }
+};
 
-class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
-  MachineBasicBlock &MBB;               // basic blocks for this graph
-  SchedGraphNode* graphRoot;		// the root and leaf are not inserted
-  SchedGraphNode* graphLeaf;		//  in the hash_map (see getNumNodes())
+class SchedGraph : public SchedGraphCommon {
+  MachineBasicBlock &MBB;
+  hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
   
-  typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
-  SchedGraph(const SchedGraph &);       // DO NOT IMPLEMENT
-  void operator=(const SchedGraph &);   // DO NOT IMPLEMENT
 public:
-  using map_base::iterator;
-  using map_base::const_iterator;
-  
-public:
-  //
-  // Accessor methods
-  //
-  MachineBasicBlock               &getBasicBlock()  const { return MBB; }
-  unsigned                         getNumNodes()    const { return size()+2; }
-  SchedGraphNode*		   getRoot()	    const { return graphRoot; }
-  SchedGraphNode*		   getLeaf()	    const { return graphLeaf; }
-  
-  SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
-    const_iterator onePair = this->find(minstr);
-    return (onePair != this->end())? (*onePair).second : NULL;
+  typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
+  typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
+    
+  MachineBasicBlock&               getBasicBlock() const{return MBB;}
+  const unsigned int		   getNumNodes()    const { return GraphMap.size()+2; }
+  SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
+    const_iterator onePair = find(MI);
+    return (onePair != end())? onePair->second : NULL;
   }
   
-  //
-  // Delete nodes or edges from the graph.
-  // 
-  void		eraseNode		(SchedGraphNode* node);
-  
-  void		eraseIncomingEdges	(SchedGraphNode* node,
-					 bool addDummyEdges = true);
-  
-  void		eraseOutgoingEdges	(SchedGraphNode* node,
-					 bool addDummyEdges = true);
-  
-  void		eraseIncidentEdges	(SchedGraphNode* node,
-					 bool addDummyEdges = true);
+  // Debugging support
+  void		dump	() const;
   
-  //
-  // Unordered iterators.
-  // Return values is pair<const MachineIntr*,SchedGraphNode*>.
-  //
-  using map_base::begin;
-  using map_base::end;
+protected:
+  SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
+  ~SchedGraph();
 
-  //
-  // Ordered iterators.
+  // Unordered iterators.
   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
   //
-  // void			   postord_init();
-  // postorder_iterator	   postord_begin();
-  // postorder_iterator	   postord_end();
-  // const_postorder_iterator postord_begin() const;
-  // const_postorder_iterator postord_end() const;
+  hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
+    return GraphMap.begin();
+  }
+  hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
+    return GraphMap.end();
+  }
+ 
+  unsigned size() { return GraphMap.size(); }
+  iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
   
-  //
-  // Debugging support
-  // 
-  void		dump	() const;
+  SchedGraphNode *&operator[](const MachineInstr *MI) {
+    return GraphMap[MI];
+  }
   
 private:
   friend class SchedGraphSet;		// give access to ctor
   
-  // disable default constructor and provide a ctor for single-block graphs
-  /*ctor*/	SchedGraph		(MachineBasicBlock &bb,
-					 const TargetMachine& target);
-  /*dtor*/	~SchedGraph		();
+ 
   
   inline void	noteGraphNodeForInstr	(const MachineInstr* minstr,
 					 SchedGraphNode* node)
@@ -288,12 +104,13 @@ private:
   //
   void  	buildGraph		(const TargetMachine& target);
   
-  void          buildNodesForBB         (const TargetMachine& target,
+   void          buildNodesForBB         (const TargetMachine& target,
                                          MachineBasicBlock &MBB,
                                          std::vector<SchedGraphNode*>& memNV,
                                          std::vector<SchedGraphNode*>& callNV,
                                          RegToRefVecMap& regToRefVecMap,
                                          ValueToDefVecMap& valueToDefVecMap);
+
   
   void          findDefUseInfoAtInstr   (const TargetMachine& target,
                                          SchedGraphNode* node,
@@ -301,6 +118,7 @@ private:
                                          std::vector<SchedGraphNode*>& callNV,
                                          RegToRefVecMap& regToRefVecMap,
                                          ValueToDefVecMap& valueToDefVecMap);
+
                                          
   void		addEdgesForInstruction(const MachineInstr& minstr,
                                      const ValueToDefVecMap& valueToDefVecMap,
@@ -309,12 +127,15 @@ private:
   void		addCDEdges		(const TerminatorInst* term,
 					 const TargetMachine& target);
   
-  void		addMemEdges         (const std::vector<SchedGraphNode*>& memNV,
+  void		addMemEdges         (const std::vector<SchedGraphNode*>& memNod,
                                      const TargetMachine& target);
   
+  void          addCallCCEdges      (const std::vector<SchedGraphNode*>& memNod,
+                                     MachineBasicBlock& bbMvec,
+                                     const TargetMachine& target);
   void          addCallDepEdges     (const std::vector<SchedGraphNode*>& callNV,
                                      const TargetMachine& target);
-    
+  
   void		addMachineRegEdges	(RegToRefVecMap& regToRefVecMap,
 					 const TargetMachine& target);
   
@@ -324,44 +145,41 @@ private:
                                          bool  refNodeIsDef,
                                          bool  refNodeIsDefAndUse,
 					 const TargetMachine& target);
-  
-  void		addDummyEdges		();
+  void          addDummyEdges();
+
 };
 
 
-class SchedGraphSet : private std::vector<SchedGraph*> {
-private:
-  const Function* method;
 
-  SchedGraphSet(const SchedGraphSet&);    // DO NOT IMPLEMENT
-  void operator=(const SchedGraphSet&);   // DO NOT IMPLEMENT
-public:
-  typedef std::vector<SchedGraph*> baseVector;
-  using baseVector::iterator;
-  using baseVector::const_iterator;
-  
+class SchedGraphSet {
+  const Function* function;
+  std::vector<SchedGraph*> Graphs;
+
+  // Graph builder
+  void buildGraphsForMethod (const Function *F, const TargetMachine& target);
+
+  inline void addGraph(SchedGraph* graph) {
+    assert(graph != NULL);
+    Graphs.push_back(graph);
+  }  
+
 public:
-  SchedGraphSet(const Function *F, const TargetMachine &TM);
+  SchedGraphSet(const Function * function, const TargetMachine& target);
   ~SchedGraphSet();
   
-  // Iterators
-  using baseVector::begin;
-  using baseVector::end;
-  
+  //iterators
+  typedef std::vector<SchedGraph*>::const_iterator iterator;
+  typedef std::vector<SchedGraph*>::const_iterator const_iterator;
+
+  std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
+  std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
+
   // Debugging support
   void dump() const;
-  
-private:
-  inline void	addGraph(SchedGraph* graph) {
-    assert(graph != NULL);
-    this->push_back(graph);
-  }
-  
-  // Graph builder
-  void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
 };
 
 
+
 //********************** Sched Graph Iterators *****************************/
 
 // Ok to make it a template because it shd get instantiated at most twice:
@@ -381,7 +199,7 @@ public:
   inline bool operator!=(const _Self& x) const { return !operator==(x); }
   
   // operator*() differs for pred or succ iterator
-  inline _NodeType* operator*() const { return (*oi)->getSrc(); }
+  inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
   inline	 _NodeType* operator->() const { return operator*(); }
   
   inline _EdgeType* getEdge() const { return *(oi); }
@@ -409,7 +227,7 @@ public:
   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 (*oi)->getSink(); }
+  inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
   inline	 _NodeType* operator->() const { return operator*(); }
   
   inline _EdgeType* getEdge() const { return *(oi); }
@@ -477,7 +295,7 @@ template <> struct GraphTraits<SchedGraph*> {
   typedef SchedGraphNode NodeType;
   typedef sg_succ_iterator ChildIteratorType;
 
-  static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
+  static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
   static inline ChildIteratorType child_begin(NodeType *N) { 
     return succ_begin(N); 
   }
@@ -491,7 +309,7 @@ template <> struct GraphTraits<const SchedGraph*> {
   typedef sg_succ_const_iterator ChildIteratorType;
 
   static inline NodeType *getEntryNode(const SchedGraph *SG) {
-    return SG->getRoot();
+    return (NodeType*)SG->getRoot();
   }
   static inline ChildIteratorType child_begin(NodeType *N) { 
     return succ_begin(N); 
diff --git a/lib/Target/SparcV9/InstrSched/SchedGraphCommon.cpp b/lib/Target/SparcV9/InstrSched/SchedGraphCommon.cpp
new file mode 100644
index 0000000000..287a6796fb
--- /dev/null
+++ b/lib/Target/SparcV9/InstrSched/SchedGraphCommon.cpp
@@ -0,0 +1,237 @@
+#include "llvm/CodeGen/SchedGraphCommon.h"
+#include "Support/STLExtras.h"
+
+class SchedGraphCommon;
+
+// 
+// class SchedGraphEdge
+// 
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+			       SchedGraphNodeCommon* _sink,
+			       SchedGraphEdgeDepType _depType,
+			       unsigned int     _depOrderType,
+			       int _minDelay)
+  : src(_src),
+    sink(_sink),
+    depType(_depType),
+    depOrderType(_depOrderType),
+    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+    val(NULL)
+{
+  iteDiff=0;
+  assert(src != sink && "Self-loop in scheduling graph!");
+  src->addOutEdge(this);
+  sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon*  _src,
+			       SchedGraphNodeCommon*  _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)
+{
+  iteDiff=0;
+  assert(src != sink && "Self-loop in scheduling graph!");
+  src->addOutEdge(this);
+  sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon*  _src,
+			       SchedGraphNodeCommon*  _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)
+{
+  iteDiff=0;
+  assert(src != sink && "Self-loop in scheduling graph!");
+  src->addOutEdge(this);
+  sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+			       SchedGraphNodeCommon* _sink,
+			       ResourceId      _resourceId,
+			       int             _minDelay)
+  : src(_src),
+    sink(_sink),
+    depType(MachineResource),
+    depOrderType(NonDataDep),
+    minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+    resourceId(_resourceId)
+{
+  iteDiff=0;
+  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; 
+}
+
+
+
+/*ctor*/           
+
+SchedGraphNodeCommon::SchedGraphNodeCommon(unsigned  _nodeId)
+  :ID(_nodeId),
+   latency(0){
+  
+}
+
+/*dtor*/
+SchedGraphNodeCommon::~SchedGraphNodeCommon()
+{
+  // for each node, delete its out-edges
+  std::for_each(beginOutEdges(), endOutEdges(),
+                deleter<SchedGraphEdge>);
+}
+
+
+void SchedGraphNodeCommon::dump(int indent) const {
+  std::cerr << std::string(indent*2, ' ') << *this; 
+}
+
+
+inline void
+SchedGraphNodeCommon::addInEdge(SchedGraphEdge* edge)
+{
+  inEdges.push_back(edge);
+}
+
+
+inline void
+SchedGraphNodeCommon::addOutEdge(SchedGraphEdge* edge)
+{
+  outEdges.push_back(edge);
+}
+
+inline void
+SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge)
+{
+  assert(edge->getSink() == this);
+  
+  for (iterator I = beginInEdges(); I != endInEdges(); ++I)
+    if ((*I) == edge)
+      {
+	inEdges.erase(I);
+	break;
+      }
+}
+
+inline void
+SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge)
+{
+  assert(edge->getSrc() == this);
+  
+  for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
+    if ((*I) == edge)
+      {
+	outEdges.erase(I);
+	break;
+      }
+}
+
+
+//class SchedGraphCommon
+
+/*ctor*/
+SchedGraphCommon::SchedGraphCommon()
+{ 
+}
+
+
+/*dtor*/
+SchedGraphCommon::~SchedGraphCommon()
+{
+
+  delete graphRoot;
+  delete graphLeaf;
+}
+
+
+void
+SchedGraphCommon::eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+  // Delete and disconnect all in-edges for the node
+  for (SchedGraphNodeCommon::iterator I = node->beginInEdges();
+       I != node->endInEdges(); ++I)
+    {
+      SchedGraphNodeCommon* srcNode = (*I)->getSrc();
+      srcNode->removeOutEdge(*I);
+      delete *I;
+      
+      if (addDummyEdges &&
+	  srcNode != getRoot() &&
+	  srcNode->beginOutEdges() == srcNode->endOutEdges())
+	{ // srcNode has no more out edges, so add an edge to dummy EXIT node
+	  assert(node != getLeaf() && "Adding edge that was just removed?");
+	  (void) new SchedGraphEdge(srcNode, getLeaf(),
+		    SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+	}
+    }
+  
+  node->inEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+  // Delete and disconnect all out-edges for the node
+  for (SchedGraphNodeCommon::iterator I = node->beginOutEdges();
+       I != node->endOutEdges(); ++I)
+    {
+      SchedGraphNodeCommon* sinkNode = (*I)->getSink();
+      sinkNode->removeInEdge(*I);
+      delete *I;
+      
+      if (addDummyEdges &&
+	  sinkNode != getLeaf() &&
+	  sinkNode->beginInEdges() == sinkNode->endInEdges())
+	{ //sinkNode has no more in edges, so add an edge from dummy ENTRY node
+	  assert(node != getRoot() && "Adding edge that was just removed?");
+	  (void) new SchedGraphEdge(getRoot(), sinkNode,
+		    SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+	}
+    }
+  
+  node->outEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+  this->eraseIncomingEdges(node, addDummyEdges);	
+  this->eraseOutgoingEdges(node, addDummyEdges);	
+}
+
+std::ostream &operator<<(std::ostream &os, const SchedGraphNodeCommon& node)
+{
+  
+  return os;
+}
diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp
index b60a33bcfd..20c0f8217a 100644
--- a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp
+++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp
@@ -59,7 +59,7 @@ SchedPriorities::computeDelays(const SchedGraph* graph)
 	  for (SchedGraphNode::const_iterator E=node->beginOutEdges();
 	       E != node->endOutEdges(); ++E)
 	    {
-	      cycles_t sinkDelay = getNodeDelay((*E)->getSink());
+	      cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
 	      nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
 	    }
 	}
@@ -71,7 +71,7 @@ SchedPriorities::computeDelays(const SchedGraph* graph)
 void
 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
 {
-  const SchedGraphNode* graphRoot = graph->getRoot();
+  const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
   assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
   
   // Insert immediate successors of dummy root, which are the actual roots
@@ -137,7 +137,7 @@ SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
   for (SchedGraphNode::const_iterator E=node->beginOutEdges();
        E != node->endOutEdges(); ++E)
     {
-      cycles_t& etime = getEarliestReadyTimeForNodeRef((*E)->getSink());
+      cycles_t& etime = getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
       etime = std::max(etime, curTime + (*E)->getMinDelay());
     }    
 }