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