lib/CodeGen/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/TargetSchedInfo.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*> {
  67   NodeHeap(const NodeHeap&);          // DO NOT IMPLEMENT
  68   void operator=(const NodeHeap&);    // DO NOT IMPLEMENT
  69 public:
  70   typedef std::list<NodeDelayPair*>::iterator iterator;
  71   typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
  72
  73 public:
  74   NodeHeap() : _size(0) {}
  75
  76   inline unsigned       size() const { return _size; }
  77
  78   const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
  79   cycles_t              getDelay(const_iterator i) const { return (*i)->delay;}
  80
  81   inline void           makeHeap() {
  82     // make_heap(begin(), end(), NDPLessThan);
  83   }
  84
  85   inline iterator       findNode(const SchedGraphNode* node) {
  86     for (iterator I=begin(); I != end(); ++I)
  87       if (getNode(I) == node)
  88         return I;
  89     return end();
  90   }
  91
  92   inline void     removeNode    (const SchedGraphNode* node) {
  93     iterator ndpPtr = findNode(node);
  94     if (ndpPtr != end())
  95       {
  96         delete *ndpPtr;
  97         erase(ndpPtr);
  98         --_size;
  99       }
 100   };
 101
 102   void            insert(const SchedGraphNode* node, cycles_t delay) {
 103     NodeDelayPair* ndp = new NodeDelayPair(node, delay);
 104     if (_size == 0 || front()->delay < delay)
 105       push_front(ndp);
 106     else
 107       {
 108         iterator I=begin();
 109         for ( ; I != end() && getDelay(I) >= delay; ++I)
 110           ;
 111         std::list<NodeDelayPair*>::insert(I, ndp);
 112       }
 113     _size++;
 114   }
 115 private:
 116   unsigned int _size;
 117 };
 118
 119
 120 class SchedPriorities {
 121   SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
 122   void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
 123 public:
 124   SchedPriorities(const Function *F, const SchedGraph *G,
 125                   FunctionLiveVarInfo &LVI);
 126
 127
 128   // This must be called before scheduling begins.
 129   void          initialize              ();
 130
 131   cycles_t      getTime                 () const { return curTime; }
 132   cycles_t      getEarliestReadyTime    () const { return earliestReadyTime; }
 133   unsigned      getNumReady             () const { return candsAsHeap.size(); }
 134   bool          nodeIsReady             (const SchedGraphNode* node) const {
 135     return (candsAsSet.find(node) != candsAsSet.end());
 136   }
 137
 138   void          issuedReadyNodeAt       (cycles_t curTime,
 139                                          const SchedGraphNode* node);
 140
 141   void          insertReady             (const SchedGraphNode* node);
 142
 143   void          updateTime              (cycles_t /*unused*/);
 144
 145   const SchedGraphNode* getNextHighest  (const SchedulingManager& S,
 146                                          cycles_t curTime);
 147                                         // choose next highest priority instr
 148
 149 private:
 150   typedef NodeHeap::iterator candIndex;
 151
 152 private:
 153   cycles_t curTime;
 154   const SchedGraph* graph;
 155   FunctionLiveVarInfo &methodLiveVarInfo;
 156   hash_map<const MachineInstr*, bool> lastUseMap;
 157   std::vector<cycles_t> nodeDelayVec;
 158   std::vector<cycles_t> nodeEarliestUseVec;
 159   std::vector<cycles_t> earliestReadyTimeForNode;
 160   cycles_t earliestReadyTime;
 161   NodeHeap candsAsHeap;                         // candidate nodes, ready to go
 162   hash_set<const SchedGraphNode*> candsAsSet;   //same entries as candsAsHeap,
 163                                                 //   but as set for fast lookup
 164   std::vector<candIndex> mcands;                // holds pointers into cands
 165   candIndex nextToTry;                          // next cand after the last
 166                                                 //   one tried in this cycle
 167
 168   int           chooseByRule1           (std::vector<candIndex>& mcands);
 169   int           chooseByRule2           (std::vector<candIndex>& mcands);
 170   int           chooseByRule3           (std::vector<candIndex>& mcands);
 171
 172   void          findSetWithMaxDelay     (std::vector<candIndex>& mcands,
 173                                          const SchedulingManager& S);
 174
 175   void          computeDelays           (const SchedGraph* graph);
 176
 177   void          initializeReadyHeap     (const SchedGraph* graph);
 178
 179   bool          instructionHasLastUse   (FunctionLiveVarInfo& LVI,
 180                                          const SchedGraphNode* graphNode);
 181
 182   // NOTE: The next two return references to the actual vector entries.
 183   //       Use the following two if you don't need to modify the value.
 184   cycles_t&     getNodeDelayRef         (const SchedGraphNode* node) {
 185     assert(node->getNodeId() < nodeDelayVec.size());
 186     return nodeDelayVec[node->getNodeId()];
 187   }
 188   cycles_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
 189     assert(node->getNodeId() < earliestReadyTimeForNode.size());
 190     return earliestReadyTimeForNode[node->getNodeId()];
 191   }
 192
 193   cycles_t      getNodeDelay            (const SchedGraphNode* node) const {
 194     return ((SchedPriorities*) this)->getNodeDelayRef(node);
 195   }
 196   cycles_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
 197     return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
 198   }
 199 };
 200
 201
 202 inline void SchedPriorities::updateTime(cycles_t c) {
 203   curTime = c;
 204   nextToTry = candsAsHeap.begin();
 205   mcands.clear();
 206 }
 207
 208 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);
 209
 210 #endif