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