lib/CodeGen/InstrSched/SchedPriorities.h

//===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
// 
// 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.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
#define LLVM_CODEGEN_SCHEDPRIORITIES_H

#include "SchedGraph.h"
#include "llvm/CodeGen/InstrScheduling.h"
#include "llvm/Target/TargetSchedInfo.h"
#include "Support/hash_set"
#include <list>

namespace llvm {

class Function;
class MachineInstr;
class SchedulingManager;
class FunctionLiveVarInfo;

//---------------------------------------------------------------------------
// Debug option levels for instruction scheduling

enum SchedDebugLevel_t {
  Sched_NoDebugInfo,
  Sched_Disable,
  Sched_PrintMachineCode, 
  Sched_PrintSchedTrace,
  Sched_PrintSchedGraphs,
};

extern SchedDebugLevel_t SchedDebugLevel;

//---------------------------------------------------------------------------
// Function: instrIsFeasible
// 
// Purpose:
//   Used by the priority analysis to filter out instructions
//   that are not feasible to issue in the current cycle.
//   Should only be used during schedule construction..
//---------------------------------------------------------------------------

bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);



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 std::list<NodeDelayPair*> {
  NodeHeap(const NodeHeap&);          // DO NOT IMPLEMENT
  void operator=(const NodeHeap&);    // DO NOT IMPLEMENT
public:
  typedef std::list<NodeDelayPair*>::iterator iterator;
  typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
  
public:
  NodeHeap() : _size(0) {}
  
  inline unsigned       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)
	  ;
	std::list<NodeDelayPair*>::insert(I, ndp);
      }
    _size++;
  }
private:
  unsigned int _size;
};


class SchedPriorities {
  SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
  void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
public:
  SchedPriorities(const Function *F, const SchedGraph *G,
                  FunctionLiveVarInfo &LVI);
                  
  
  // 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;
  FunctionLiveVarInfo &methodLiveVarInfo;
  hash_map<const MachineInstr*, bool> lastUseMap;
  std::vector<cycles_t> nodeDelayVec;
  std::vector<cycles_t> nodeEarliestUseVec;
  std::vector<cycles_t> earliestReadyTimeForNode;
  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
  std::vector<candIndex> mcands;                // holds pointers into cands
  candIndex nextToTry;				// next cand after the last
						//   one tried in this cycle
  
  int		chooseByRule1		(std::vector<candIndex>& mcands);
  int		chooseByRule2		(std::vector<candIndex>& mcands);
  int		chooseByRule3		(std::vector<candIndex>& mcands);
  
  void		findSetWithMaxDelay	(std::vector<candIndex>& mcands,
					 const SchedulingManager& S);
  
  void		computeDelays		(const SchedGraph* graph);
  
  void		initializeReadyHeap	(const SchedGraph* graph);
  
  bool		instructionHasLastUse	(FunctionLiveVarInfo& LVI,
					 const SchedGraphNode* graphNode);
  
  // NOTE: The next two return references to the actual vector entries.
  //       Use the following two if you don't need to modify the value.
  cycles_t&	getNodeDelayRef		(const SchedGraphNode* node) {
    assert(node->getNodeId() < nodeDelayVec.size());
    return nodeDelayVec[node->getNodeId()];
  }
  cycles_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
    assert(node->getNodeId() < earliestReadyTimeForNode.size());
    return earliestReadyTimeForNode[node->getNodeId()];
  }
  
  cycles_t      getNodeDelay            (const SchedGraphNode* node) const {
    return ((SchedPriorities*) this)->getNodeDelayRef(node); 
  }
  cycles_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
    return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
  }
};


inline void SchedPriorities::updateTime(cycles_t c) {
  curTime = c;
  nextToTry = candsAsHeap.begin();
  mcands.clear();
}

std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);

} // End llvm namespace

#endif