lib/Target/SparcV9/InstrSched/SchedPriorities.h

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