Chris seems fond of #include <vector>. Fix these. Also convert use list in

Value to a vector instead of a list.

Move SchedGraph.h & SchedPriorities.h into lib/CodeGen/InstrScheduling


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

14 files changed, 14 insertions, 716 deletions

diff --git a/include/llvm/CodeGen/InstrSelection.h b/include/llvm/CodeGen/InstrSelection.h
index 0a8a92706d..e07ebd7a33 100644
--- a/include/llvm/CodeGen/InstrSelection.h
+++ b/include/llvm/CodeGen/InstrSelection.h
@@ -13,7 +13,6 @@
 #define LLVM_CODEGEN_INSTR_SELECTION_H
 
 #include "llvm/Instruction.h"
-#include <vector>
 class Method;
 class InstrForest;
 class MachineInstr;
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 9903f09c01..29e832dd58 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -19,7 +19,7 @@
 #include "llvm/CodeGen/InstrForest.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/NonCopyable.h"
-#include "llvm/Target/Machine.h"
+#include "llvm/Target/InstInfo.h"
 
 template<class _MI, class _V> class ValOpIterator;
 
diff --git a/include/llvm/CodeGen/SchedGraph.h b/include/llvm/CodeGen/SchedGraph.h
deleted file mode 100644
index e12d90ffcd..0000000000
--- a/include/llvm/CodeGen/SchedGraph.h
+++ /dev/null
@@ -1,495 +0,0 @@
-/* -*-C++-*-
- ****************************************************************************
- * File:
- *	SchedGraph.h
- * 
- * Purpose:
- *	Scheduling graph based on SSA graph plus extra dependence edges
- *	capturing dependences due to machine resources (machine registers,
- *	CC registers, and any others).
- * 
- * Strategy:
- *	This graph tries to leverage the SSA graph as much as possible,
- *	but captures the extra dependences through a common interface.
- * 
- * History:
- *	7/20/01	 -  Vikram Adve  -  Created
- ***************************************************************************/
-
-#ifndef LLVM_CODEGEN_SCHEDGRAPH_H
-#define LLVM_CODEGEN_SCHEDGRAPH_H
-
-#include "llvm/CFGdecls.h"			// just for graph iterators
-#include "llvm/Support/NonCopyable.h"
-#include "llvm/Support/HashExtras.h"
-#include <hash_map>
-
-class Value;
-class Instruction;
-class BasicBlock;
-class Method;
-class TargetMachine;
-class SchedGraphEdge; 
-class SchedGraphNode; 
-class SchedGraph; 
-class NodeToRegRefMap;
-
-/******************** Exported Data Types and Constants ********************/
-
-typedef int ResourceId;
-const ResourceId InvalidResourceId = -1;
-
-
-//*********************** Public Class Declarations ************************/
-
-class SchedGraphEdge: public NonCopyable {
-public:
-  enum SchedGraphEdgeDepType {
-    CtrlDep, MemoryDep, DefUseDep, MachineRegister, MachineResource
-  };
-  enum DataDepOrderType {
-    TrueDep, AntiDep, OutputDep, NonDataDep
-  };
-  
-protected:
-  SchedGraphNode*	src;
-  SchedGraphNode*	sink;
-  SchedGraphEdgeDepType depType;
-  DataDepOrderType	depOrderType;
-  int			minDelay; // cached latency (assumes fixed target arch)
-  
-  union {
-    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,
-				       DataDepOrderType _depOrderType =TrueDep,
-				       int _minDelay = -1);
-  
-  // constructor for explicit def-use or memory def-use edge
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       Value*          _val,
-				       DataDepOrderType _depOrderType =TrueDep,
-				       int _minDelay = -1);
-  
-  // constructor for machine register dependence
-  /*ctor*/		SchedGraphEdge(SchedGraphNode* _src,
-				       SchedGraphNode* _sink,
-				       unsigned int    _regNum,
-				       DataDepOrderType _depOrderType =TrueDep,
-				       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 == DefUseDep || depType == MemoryDep); return val;
-  }
-  int			getMachineReg	() const {
-    assert(depType == MachineRegister); return machineRegNum;
-  }
-  int			getResourceId	() const {
-    assert(depType == MachineResource); return resourceId;
-  }
-  
-public:
-  // 
-  // Debugging support
-  // 
-  friend ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
-  
-  void		dump	(int indent=0) const;
-    
-private:
-  // disable default ctor
-  /*ctor*/		SchedGraphEdge();	// DO NOT IMPLEMENT
-};
-
-
-
-class SchedGraphNode: public NonCopyable {
-private:
-  unsigned int nodeId;
-  const Instruction* instr;
-  const MachineInstr* minstr;
-  vector<SchedGraphEdge*> inEdges;
-  vector<SchedGraphEdge*> outEdges;
-  int latency;
-  
-public:
-  typedef	vector<SchedGraphEdge*>::iterator	iterator;
-  typedef	vector<SchedGraphEdge*>::const_iterator	const_iterator;
-  
-public:
-  //
-  // Accessor methods
-  // 
-  unsigned int		getNodeId	() const { return nodeId; }
-  const Instruction*	getInstr	() const { return instr; }
-  const MachineInstr*	getMachineInstr	() const { return minstr; }
-  int			getLatency	() const { return latency; }
-  unsigned int		getNumInEdges	() const { return inEdges.size(); }
-  unsigned int		getNumOutEdges	() const { return outEdges.size(); }
-  bool			isDummyNode	() const { return (minstr == NULL); }
-  
-  //
-  // 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(); }
-  
-  //
-  // Limited modifier methods
-  // 
-  void			eraseAllEdges	();
-  
-public:
-  //
-  // Debugging support
-  // 
-  friend ostream& operator<<(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 int _nodeId,
-					 const Instruction* _instr,
-					 const MachineInstr* _minstr,
-					 const TargetMachine& _target);
-  /*dtor*/		~SchedGraphNode	();
-};
-
-
-
-class SchedGraph :
-  public NonCopyable,
-  private hash_map<const MachineInstr*, SchedGraphNode*>
-{
-private:
-  vector<const BasicBlock*> bbVec;	// basic blocks included in the graph
-  SchedGraphNode* graphRoot;		// the root and leaf are not inserted
-  SchedGraphNode* graphLeaf;		//  in the hash_map (see getNumNodes())
-  
-public:
-  typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator;
-  typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
-  
-public:
-  //
-  // Accessor methods
-  //
-  const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
-  const unsigned int		   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;
-  }
-  
-  //
-  // Delete a node from the graph.
-  // 
-  void		  eraseNode(SchedGraphNode* node);
-  
-  //
-  // Unordered iterators.
-  // Return values is pair<const MachineIntr*,SchedGraphNode*>.
-  //
-  iterator	begin()	{
-    return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
-  }
-  iterator	end() {
-    return hash_map<const MachineInstr*, SchedGraphNode*>::end();
-  }
-  const_iterator begin() const {
-    return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
-  }
-  const_iterator end()	const {
-    return hash_map<const MachineInstr*, SchedGraphNode*>::end();
-  }
-  
-  //
-  // Ordered 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;
-  
-  //
-  // Debugging support
-  // 
-  void		dump	() const;
-  
-private:
-  friend class SchedGraphSet;		// give access to ctor
-  
-  // disable default constructor and provide a ctor for single-block graphs
-  /*ctor*/	SchedGraph		();	// DO NOT IMPLEMENT
-  /*ctor*/	SchedGraph		(const BasicBlock* bb,
-					 const TargetMachine& target);
-  /*dtor*/	~SchedGraph		();
-  
-  inline void	noteGraphNodeForInstr	(const MachineInstr* minstr,
-					 SchedGraphNode* node)
-  {
-    assert((*this)[minstr] == NULL);
-    (*this)[minstr] = node;
-  }
-
-  //
-  // Graph builder
-  //
-  void		buildGraph		(const TargetMachine& target);
-  
-  void		addEdgesForInstruction	(SchedGraphNode* node,
-					 NodeToRegRefMap& regToRefVecMap,
-					 const TargetMachine& target);
-  
-  void		addCDEdges		(const TerminatorInst* term,
-					 const TargetMachine& target);
-  
-  void		addMemEdges	     (const vector<const Instruction*>& memVec,
-				      const TargetMachine& target);
-  
-  void		addMachineRegEdges	(NodeToRegRefMap& regToRefVecMap,
-					 const TargetMachine& target);
-  
-  void		addSSAEdge		(SchedGraphNode* node,
-					 Value* val,
-					 const TargetMachine& target);
-  
-  void		addDummyEdges		();
-};
-
-
-class SchedGraphSet :  
-  public NonCopyable,
-  private hash_map<const BasicBlock*, SchedGraph*>
-{
-private:
-  const Method* method;
-  
-public:
-  typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
-  typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
-  
-public:
-  /*ctor*/	SchedGraphSet		(const Method* _method,
-					 const TargetMachine& target);
-  /*dtor*/	~SchedGraphSet		();
-  
-  //
-  // Accessors
-  //
-  SchedGraph*	getGraphForBasicBlock	(const BasicBlock* bb) const {
-    const_iterator onePair = this->find(bb);
-    return (onePair != this->end())? (*onePair).second : NULL;
-  }
-  
-  //
-  // Iterators
-  //
-  iterator	begin()	{
-    return hash_map<const BasicBlock*, SchedGraph*>::begin();
-  }
-  iterator	end() {
-    return hash_map<const BasicBlock*, SchedGraph*>::end();
-  }
-  const_iterator begin() const {
-    return hash_map<const BasicBlock*, SchedGraph*>::begin();
-  }
-  const_iterator end()	const {
-    return hash_map<const BasicBlock*, SchedGraph*>::end();
-  }
-  
-  //
-  // Debugging support
-  // 
-  void		dump	() const;
-  
-private:
-  inline void	noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
-    assert((*this)[bb] == NULL);
-    (*this)[bb] = graph;
-  }
-
-  //
-  // Graph builder
-  //
-  void		buildGraphsForMethod	(const Method *method,
-					 const TargetMachine& target);
-};
-
-
-//********************** 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 PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
-protected:
-  _EdgeIter oi;
-public:
-  typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
-  
-  inline PredIterator(_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 (*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 SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
-protected:
-  _EdgeIter oi;
-public:
-  typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
-  
-  inline SuccIterator(_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 (*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;
-  }
-};
-
-// 
-// sg_pred_iterator
-// sg_pred_const_iterator
-//
-typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
-    sg_pred_iterator;
-typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
-    sg_pred_const_iterator;
-
-inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
-  return sg_pred_iterator(N->beginInEdges());
-}
-inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
-  return sg_pred_iterator(N->endInEdges());
-}
-inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
-  return sg_pred_const_iterator(N->beginInEdges());
-}
-inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
-  return sg_pred_const_iterator(N->endInEdges());
-}
-
-
-// 
-// sg_succ_iterator
-// sg_succ_const_iterator
-//
-typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
-    sg_succ_iterator;
-typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
-    sg_succ_const_iterator;
-
-inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
-  return sg_succ_iterator(N->beginOutEdges());
-}
-inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
-  return sg_succ_iterator(N->endOutEdges());
-}
-inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
-  return sg_succ_const_iterator(N->beginOutEdges());
-}
-inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
-  return sg_succ_const_iterator(N->endOutEdges());
-}
-
-// 
-// po_iterator
-// po_const_iterator
-//
-typedef cfg::POIterator<SchedGraphNode, sg_succ_iterator> sg_po_iterator;
-typedef cfg::POIterator<const SchedGraphNode, 
-		        sg_succ_const_iterator> sg_po_const_iterator;
-
-
-//************************ External Functions *****************************/
-
-
-ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
-
-ostream& operator<<(ostream& os, const SchedGraphNode& node);
-
-
-/***************************************************************************/
-
-#endif
diff --git a/include/llvm/CodeGen/SchedPriorities.h b/include/llvm/CodeGen/SchedPriorities.h
deleted file mode 100644
index 45f19b4654..0000000000
--- a/include/llvm/CodeGen/SchedPriorities.h
+++ /dev/null
@@ -1,203 +0,0 @@
-/* -*-C++-*-
- ****************************************************************************
- * File:
- *	SchedPriorities.h
- * 
- * Purpose:
- *	Encapsulate heuristics for instruction scheduling.
- * 
- * Strategy:
- *    Priority ordering rules:
- *    (1) Max delay, which is the order of the heap S.candsAsHeap.
- *    (2) Instruction that frees up a register.
- *    (3) Instruction that has the maximum number of dependent instructions.
- *    Note that rules 2 and 3 are only used if issue conflicts prevent
- *    choosing a higher priority instruction by rule 1.
- * 
- * History:
- *	7/30/01	 -  Vikram Adve  -  Created
- ***************************************************************************/
-
-#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
-#define LLVM_CODEGEN_SCHEDPRIORITIES_H
-
-#include "llvm/CodeGen/InstrScheduling.h"
-#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
-#include "llvm/CodeGen/SchedGraph.h"
-#include "llvm/Target/SchedInfo.h"
-
-class Method;
-class MachineInstr;
-class SchedulingManager;
-
-
-struct NodeDelayPair {
-  const SchedGraphNode* node;
-  cycles_t delay;
-  NodeDelayPair(const SchedGraphNode* n, cycles_t d) :  node(n), delay(d) {}
-  inline bool operator< (const NodeDelayPair& np) { return delay < np.delay; }
-};
-
-inline bool
-NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
-{
-  return (np1->delay < np2->delay);
-}
-
-class NodeHeap: public list<NodeDelayPair*>, public NonCopyable {
-public:
-  typedef list<NodeDelayPair*>::iterator iterator;
-  typedef list<NodeDelayPair*>::const_iterator const_iterator;
-  
-public:
-  /*ctor*/	  NodeHeap	() : list<NodeDelayPair*>(), _size(0) {}
-  /*dtor*/	  ~NodeHeap	() {}
-  
-  inline unsigned int	size	() const { return _size; }
-  
-  const SchedGraphNode* getNode	(const_iterator i) const { return (*i)->node; }
-  cycles_t		getDelay(const_iterator i) const { return (*i)->delay;}
-  
-  inline void		makeHeap() { 
-    // make_heap(begin(), end(), NDPLessThan);
-  }
-  
-  inline iterator	findNode(const SchedGraphNode* node) {
-    for (iterator I=begin(); I != end(); ++I)
-      if (getNode(I) == node)
-	return I;
-    return end();
-  }
-  
-  inline void	  removeNode	(const SchedGraphNode* node) {
-    iterator ndpPtr = findNode(node);
-    if (ndpPtr != end())
-      {
-	delete *ndpPtr;
-	erase(ndpPtr);
-	--_size;
-      }
-  };
-  
-  void		  insert(const SchedGraphNode* node, cycles_t delay) {
-    NodeDelayPair* ndp = new NodeDelayPair(node, delay);
-    if (_size == 0 || front()->delay < delay)
-      push_front(ndp);
-    else
-      {
-	iterator I=begin();
-	for ( ; I != end() && getDelay(I) >= delay; ++I)
-	  ;
-	list<NodeDelayPair*>::insert(I, ndp);
-      }
-    _size++;
-  }
-private:
-  unsigned int _size;
-};
-
-
-class SchedPriorities: public NonCopyable {
-public:
-  /*ctor*/	SchedPriorities		(const Method* method,
-					 const SchedGraph* _graph);
-  
-  // This must be called before scheduling begins.
-  void		initialize		();
-  
-  cycles_t	getTime			() const { return curTime; }
-  cycles_t	getEarliestReadyTime	() const { return earliestReadyTime; }
-  unsigned	getNumReady		() const { return candsAsHeap.size(); }
-  bool		nodeIsReady		(const SchedGraphNode* node) const {
-    return (candsAsSet.find(node) != candsAsSet.end());
-  }
-  
-  void		issuedReadyNodeAt	(cycles_t curTime,
-					 const SchedGraphNode* node);
-  
-  void		insertReady		(const SchedGraphNode* node);
-  
-  void		updateTime		(cycles_t /*unused*/);
-  
-  const SchedGraphNode* getNextHighest	(const SchedulingManager& S,
-					 cycles_t curTime);
-					// choose next highest priority instr
-  
-private:
-  typedef NodeHeap::iterator candIndex;
-  
-private:
-  cycles_t curTime;
-  const SchedGraph* graph;
-  MethodLiveVarInfo methodLiveVarInfo;
-  hash_map<const MachineInstr*, bool> lastUseMap;
-  vector<cycles_t> nodeDelayVec;
-  vector<cycles_t> earliestForNode;
-  cycles_t earliestReadyTime;
-  NodeHeap candsAsHeap;				// candidate nodes, ready to go
-  hash_set<const SchedGraphNode*> candsAsSet;	// same entries as candsAsHeap,
-						//   but as set for fast lookup
-  vector<candIndex> mcands;			// holds pointers into cands
-  candIndex nextToTry;				// next cand after the last
-						//   one tried in this cycle
-  
-  int		chooseByRule1		(vector<candIndex>& mcands);
-  int		chooseByRule2		(vector<candIndex>& mcands);
-  int		chooseByRule3		(vector<candIndex>& mcands);
-  
-  void		findSetWithMaxDelay	(vector<candIndex>& mcands,
-					 const SchedulingManager& S);
-  
-  void		computeDelays		(const SchedGraph* graph);
-  
-  void		initializeReadyHeap	(const SchedGraph* graph);
-  
-  bool		instructionHasLastUse	(MethodLiveVarInfo& methodLiveVarInfo,
-					 const SchedGraphNode* graphNode);
-  
-  // NOTE: The next two return references to the actual vector entries.
-  //       Use with care.
-  cycles_t&	getNodeDelayRef		(const SchedGraphNode* node) {
-    assert(node->getNodeId() < nodeDelayVec.size());
-    return nodeDelayVec[node->getNodeId()];
-  }
-  cycles_t&	getEarliestForNodeRef	(const SchedGraphNode* node) {
-    assert(node->getNodeId() < earliestForNode.size());
-    return earliestForNode[node->getNodeId()];
-  }
-};
-
-
-inline void
-SchedPriorities::insertReady(const SchedGraphNode* node)
-{
-  candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
-  candsAsSet.insert(node);
-  mcands.clear(); // ensure reset choices is called before any more choices
-  earliestReadyTime = min(earliestReadyTime,
-			  earliestForNode[node->getNodeId()]);
-  
-  if (SchedDebugLevel >= Sched_PrintSchedTrace)
-    {
-      cout << "    Cycle " << this->getTime() << ": "
-	   << " Node " << node->getNodeId() << " is ready; "
-	   << " Delay = " << this->getNodeDelayRef(node) << "; Instruction: "
-	   << endl;
-      cout << "        " << *node->getMachineInstr() << endl;
-    }
-}
-
-inline void SchedPriorities::updateTime(cycles_t c) {
-  curTime = c;
-  nextToTry = candsAsHeap.begin();
-  mcands.clear();
-}
-
-inline ostream& operator<< (ostream& os, const NodeDelayPair* nd) {
-  return os << "Delay for node " << nd->node->getNodeId()
-	    << " = " << nd->delay << endl;
-}
-
-/***************************************************************************/
-
-#endif
diff --git a/include/llvm/ConstPoolVals.h b/include/llvm/ConstPoolVals.h
index 09260b5cea..71ca6a7a96 100644
--- a/include/llvm/ConstPoolVals.h
+++ b/include/llvm/ConstPoolVals.h
@@ -10,7 +10,6 @@
 
 #include "llvm/User.h"
 #include "llvm/Support/DataTypes.h"
-#include <vector>
 
 class ArrayType;
 class StructType;
diff --git a/include/llvm/DerivedTypes.h b/include/llvm/DerivedTypes.h
index e024ed3edc..3f93459b23 100644
--- a/include/llvm/DerivedTypes.h
+++ b/include/llvm/DerivedTypes.h
@@ -12,7 +12,6 @@
 #define LLVM_DERIVED_TYPES_H
 
 #include "llvm/Type.h"
-#include <vector>
 
 class DerivedType : public Type {
   // AbstractTypeUsers - Implement a list of the users that need to be notified
diff --git a/include/llvm/InstrTypes.h b/include/llvm/InstrTypes.h
index 1f771e6350..75c4943e44 100644
--- a/include/llvm/InstrTypes.h
+++ b/include/llvm/InstrTypes.h
@@ -10,8 +10,6 @@
 #define LLVM_INSTRUCTION_TYPES_H
 
 #include "llvm/Instruction.h"
-#include <list>
-#include <vector>
 
 class Method;
 class SymTabValue;
diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h
index 2bb590bc5e..3bbb8e7031 100644
--- a/include/llvm/Instruction.h
+++ b/include/llvm/Instruction.h
@@ -13,7 +13,7 @@
 class Type;
 class BasicBlock;
 class Method;
-class MachineInstr;		// do not include header file MachineInstr.h
+class MachineInstr;
 class MachineCodeForVMInstr;
 
 class Instruction : public User {
diff --git a/include/llvm/SymbolTable.h b/include/llvm/SymbolTable.h
index a53608f1d9..18ccf136c0 100644
--- a/include/llvm/SymbolTable.h
+++ b/include/llvm/SymbolTable.h
@@ -17,7 +17,6 @@
 #define LLVM_SYMBOL_TABLE_H
 
 #include "llvm/Value.h"
-#include <vector>
 #include <map>
 
 class Value;
diff --git a/include/llvm/Target/Data.h b/include/llvm/Target/Data.h
index 55739503e7..aa0afbcb7d 100644
--- a/include/llvm/Target/Data.h
+++ b/include/llvm/Target/Data.h
@@ -14,7 +14,6 @@
 #define LLVM_TARGET_DATA_H
 
 #include "llvm/Type.h"
-#include <vector>
 
 class StructType;
 class StructLayout;
diff --git a/include/llvm/Target/RegInfo.h b/include/llvm/Target/RegInfo.h
index 726baabf24..bb1b029b28 100644
--- a/include/llvm/Target/RegInfo.h
+++ b/include/llvm/Target/RegInfo.h
@@ -8,9 +8,14 @@
 #ifndef LLVM_TARGET_REGINFO_H
 #define LLVM_TARGET_REGINFO_H
 
-class LiveRangeInfo;
-class Method;
+#include "llvm/Support/NonCopyable.h"
+#include <hash_map>
+#include <string>
+
+class Value;
 class Instruction;
+class Method;
+class LiveRangeInfo;
 class LiveRange;
 class AddedInstrns;
 class MachineInstr;
diff --git a/include/llvm/User.h b/include/llvm/User.h
index d914b1fc1d..535dd1e88a 100644
--- a/include/llvm/User.h
+++ b/include/llvm/User.h
@@ -13,7 +13,6 @@
 #define LLVM_USER_H
 
 #include "llvm/Value.h"
-#include <vector>
 
 class User : public Value {
   User(const User &);             // Do not implement
diff --git a/include/llvm/Value.h b/include/llvm/Value.h
index dd97d3577d..d2bf4cd5f1 100644
--- a/include/llvm/Value.h
+++ b/include/llvm/Value.h
@@ -8,7 +8,7 @@
 #ifndef LLVM_VALUE_H
 #define LLVM_VALUE_H
 
-#include <list>
+#include <vector>
 #include "llvm/Annotation.h"
 #include "llvm/AbstractTypeUser.h"
 
@@ -44,7 +44,7 @@ public:
   };
 
 private:
-  list<User *> Uses;
+  vector<User *> Uses;
   string Name;
   PATypeHandle<Type> Ty;
   ValueTy VTy;
@@ -130,10 +130,10 @@ public:
   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
 
   //----------------------------------------------------------------------
-  // Methods for handling the list of uses of this DEF.
+  // Methods for handling the vector of uses of this Value.
   //
-  typedef list<User*>::iterator       use_iterator;
-  typedef list<User*>::const_iterator use_const_iterator;
+  typedef vector<User*>::iterator       use_iterator;
+  typedef vector<User*>::const_iterator use_const_iterator;
 
   inline unsigned           use_size()  const { return Uses.size();  }
   inline bool               use_empty() const { return Uses.empty(); }
diff --git a/include/llvm/iOther.h b/include/llvm/iOther.h
index 97f3262581..e723d4e975 100644
--- a/include/llvm/iOther.h
+++ b/include/llvm/iOther.h
@@ -10,7 +10,6 @@
 
 #include "llvm/InstrTypes.h"
 #include "llvm/Method.h"
-#include <vector>
 
 //===----------------------------------------------------------------------===//
 //                               PHINode Class