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