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