lib/Target/SparcV9/InstrSched/SchedPriorities.h

   1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
   2 //
   3 // Strategy:
   4 //    Priority ordering rules:
   5 //    (1) Max delay, which is the order of the heap S.candsAsHeap.
   6 //    (2) Instruction that frees up a register.
   7 //    (3) Instruction that has the maximum number of dependent instructions.
   8 //    Note that rules 2 and 3 are only used if issue conflicts prevent
   9 //    choosing a higher priority instruction by rule 1.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
  14 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
  15
  16 #include "SchedGraph.h"
  17 #include "llvm/CodeGen/InstrScheduling.h"
  18 #include "llvm/Target/MachineSchedInfo.h"
  19 #include "Support/hash_set"
  20 #include <list>
  21
  22 class Function;
  23 class MachineInstr;
  24 class SchedulingManager;
  25 class FunctionLiveVarInfo;
  26
  27 //---------------------------------------------------------------------------
  28 // Debug option levels for instruction scheduling
  29
  30 enum SchedDebugLevel_t {
  31   Sched_NoDebugInfo,
  32   Sched_Disable,
  33   Sched_PrintMachineCode,
  34   Sched_PrintSchedTrace,
  35   Sched_PrintSchedGraphs,
  36 };
  37
  38 extern SchedDebugLevel_t SchedDebugLevel;
  39
  40 //---------------------------------------------------------------------------
  41 // Function: instrIsFeasible
  42 //
  43 // Purpose:
  44 //   Used by the priority analysis to filter out instructions
  45 //   that are not feasible to issue in the current cycle.
  46 //   Should only be used during schedule construction..
  47 //---------------------------------------------------------------------------
  48
  49 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
  50
  51
  52
  53 struct NodeDelayPair {
  54   const SchedGraphNode* node;
  55   cycles_t delay;
  56   NodeDelayPair(const SchedGraphNode* n, cycles_t d) :  node(n), delay(d) {}
  57   inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
  58 };
  59
  60 inline bool
  61 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
  62 {
  63   return np1->delay < np2->delay;
  64 }
  65
  66 class NodeHeap: public std::list<NodeDelayPair*>, public NonCopyable {
  67 public:
  68   typedef std::list<NodeDelayPair*>::iterator iterator;
  69   typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
  70
  71 public:
  72   NodeHeap() : _size(0) {}
  73
  74   inline unsigned       size() const { return _size; }
  75
  76   const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
  77   cycles_t              getDelay(const_iterator i) const { return (*i)->delay;}
  78
  79   inline void           makeHeap() {
  80     // make_heap(begin(), end(), NDPLessThan);
  81   }
  82
  83   inline iterator       findNode(const SchedGraphNode* node) {
  84     for (iterator I=begin(); I != end(); ++I)
  85       if (getNode(I) == node)
  86         return I;
  87     return end();
  88   }
  89
  90   inline void     removeNode    (const SchedGraphNode* node) {
  91     iterator ndpPtr = findNode(node);
  92     if (ndpPtr != end())
  93       {
  94         delete *ndpPtr;
  95         erase(ndpPtr);
  96         --_size;
  97       }
  98   };
  99
 100   void            insert(const SchedGraphNode* node, cycles_t delay) {
 101     NodeDelayPair* ndp = new NodeDelayPair(node, delay);
 102     if (_size == 0 || front()->delay < delay)
 103       push_front(ndp);
 104     else
 105       {
 106         iterator I=begin();
 107         for ( ; I != end() && getDelay(I) >= delay; ++I)
 108           ;
 109         std::list<NodeDelayPair*>::insert(I, ndp);
 110       }
 111     _size++;
 112   }
 113 private:
 114   unsigned int _size;
 115 };
 116
 117
 118 class SchedPriorities: public NonCopyable {
 119 public:
 120   SchedPriorities(const Function *F, const SchedGraph *G,
 121                   FunctionLiveVarInfo &LVI);
 122
 123
 124   // This must be called before scheduling begins.
 125   void          initialize              ();
 126
 127   cycles_t      getTime                 () const { return curTime; }
 128   cycles_t      getEarliestReadyTime    () const { return earliestReadyTime; }
 129   unsigned      getNumReady             () const { return candsAsHeap.size(); }
 130   bool          nodeIsReady             (const SchedGraphNode* node) const {
 131     return (candsAsSet.find(node) != candsAsSet.end());
 132   }
 133
 134   void          issuedReadyNodeAt       (cycles_t curTime,
 135                                          const SchedGraphNode* node);
 136
 137   void          insertReady             (const SchedGraphNode* node);
 138
 139   void          updateTime              (cycles_t /*unused*/);
 140
 141   const SchedGraphNode* getNextHighest  (const SchedulingManager& S,
 142                                          cycles_t curTime);
 143                                         // choose next highest priority instr
 144
 145 private:
 146   typedef NodeHeap::iterator candIndex;
 147
 148 private:
 149   cycles_t curTime;
 150   const SchedGraph* graph;
 151   FunctionLiveVarInfo &methodLiveVarInfo;
 152   hash_map<const MachineInstr*, bool> lastUseMap;
 153   std::vector<cycles_t> nodeDelayVec;
 154   std::vector<cycles_t> nodeEarliestUseVec;
 155   std::vector<cycles_t> earliestReadyTimeForNode;
 156   cycles_t earliestReadyTime;
 157   NodeHeap candsAsHeap;                         // candidate nodes, ready to go
 158   hash_set<const SchedGraphNode*> candsAsSet;   //same entries as candsAsHeap,
 159                                                 //   but as set for fast lookup
 160   std::vector<candIndex> mcands;                // holds pointers into cands
 161   candIndex nextToTry;                          // next cand after the last
 162                                                 //   one tried in this cycle
 163
 164   int           chooseByRule1           (std::vector<candIndex>& mcands);
 165   int           chooseByRule2           (std::vector<candIndex>& mcands);
 166   int           chooseByRule3           (std::vector<candIndex>& mcands);
 167
 168   void          findSetWithMaxDelay     (std::vector<candIndex>& mcands,
 169                                          const SchedulingManager& S);
 170
 171   void          computeDelays           (const SchedGraph* graph);
 172
 173   void          initializeReadyHeap     (const SchedGraph* graph);
 174
 175   bool          instructionHasLastUse   (FunctionLiveVarInfo& LVI,
 176                                          const SchedGraphNode* graphNode);
 177
 178   // NOTE: The next two return references to the actual vector entries.
 179   //       Use the following two if you don't need to modify the value.
 180   cycles_t&     getNodeDelayRef         (const SchedGraphNode* node) {
 181     assert(node->getNodeId() < nodeDelayVec.size());
 182     return nodeDelayVec[node->getNodeId()];
 183   }
 184   cycles_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
 185     assert(node->getNodeId() < earliestReadyTimeForNode.size());
 186     return earliestReadyTimeForNode[node->getNodeId()];
 187   }
 188
 189   cycles_t      getNodeDelay            (const SchedGraphNode* node) const {
 190     return ((SchedPriorities*) this)->getNodeDelayRef(node);
 191   }
 192   cycles_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
 193     return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
 194   }
 195 };
 196
 197
 198 inline void SchedPriorities::updateTime(cycles_t c) {
 199   curTime = c;
 200   nextToTry = candsAsHeap.begin();
 201   mcands.clear();
 202 }
 203
 204 inline std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
 205   return os << "Delay for node " << nd->node->getNodeId()
 206             << " = " << (long)nd->delay << "\n";
 207 }
 208
 209 #endif