lib/CodeGen/InstrSched/SchedPriorities.h

   1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Strategy:
  11 //    Priority ordering rules:
  12 //    (1) Max delay, which is the order of the heap S.candsAsHeap.
  13 //    (2) Instruction that frees up a register.
  14 //    (3) Instruction that has the maximum number of dependent instructions.
  15 //    Note that rules 2 and 3 are only used if issue conflicts prevent
  16 //    choosing a higher priority instruction by rule 1.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
  21 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
  22
  23 #include "SchedGraph.h"
  24 #include "llvm/CodeGen/InstrScheduling.h"
  25 #include "llvm/Target/TargetSchedInfo.h"
  26 #include "Support/hash_set"
  27 #include <list>
  28
  29 class Function;
  30 class MachineInstr;
  31 class SchedulingManager;
  32 class FunctionLiveVarInfo;
  33
  34 //---------------------------------------------------------------------------
  35 // Debug option levels for instruction scheduling
  36
  37 enum SchedDebugLevel_t {
  38   Sched_NoDebugInfo,
  39   Sched_Disable,
  40   Sched_PrintMachineCode,
  41   Sched_PrintSchedTrace,
  42   Sched_PrintSchedGraphs,
  43 };
  44
  45 extern SchedDebugLevel_t SchedDebugLevel;
  46
  47 //---------------------------------------------------------------------------
  48 // Function: instrIsFeasible
  49 //
  50 // Purpose:
  51 //   Used by the priority analysis to filter out instructions
  52 //   that are not feasible to issue in the current cycle.
  53 //   Should only be used during schedule construction..
  54 //---------------------------------------------------------------------------
  55
  56 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
  57
  58
  59
  60 struct NodeDelayPair {
  61   const SchedGraphNode* node;
  62   cycles_t delay;
  63   NodeDelayPair(const SchedGraphNode* n, cycles_t d) :  node(n), delay(d) {}
  64   inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
  65 };
  66
  67 inline bool
  68 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
  69 {
  70   return np1->delay < np2->delay;
  71 }
  72
  73 class NodeHeap : public std::list<NodeDelayPair*> {
  74   NodeHeap(const NodeHeap&);          // DO NOT IMPLEMENT
  75   void operator=(const NodeHeap&);    // DO NOT IMPLEMENT
  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 {
 128   SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
 129   void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
 130 public:
 131   SchedPriorities(const Function *F, const SchedGraph *G,
 132                   FunctionLiveVarInfo &LVI);
 133
 134
 135   // This must be called before scheduling begins.
 136   void          initialize              ();
 137
 138   cycles_t      getTime                 () const { return curTime; }
 139   cycles_t      getEarliestReadyTime    () const { return earliestReadyTime; }
 140   unsigned      getNumReady             () const { return candsAsHeap.size(); }
 141   bool          nodeIsReady             (const SchedGraphNode* node) const {
 142     return (candsAsSet.find(node) != candsAsSet.end());
 143   }
 144
 145   void          issuedReadyNodeAt       (cycles_t curTime,
 146                                          const SchedGraphNode* node);
 147
 148   void          insertReady             (const SchedGraphNode* node);
 149
 150   void          updateTime              (cycles_t /*unused*/);
 151
 152   const SchedGraphNode* getNextHighest  (const SchedulingManager& S,
 153                                          cycles_t curTime);
 154                                         // choose next highest priority instr
 155
 156 private:
 157   typedef NodeHeap::iterator candIndex;
 158
 159 private:
 160   cycles_t curTime;
 161   const SchedGraph* graph;
 162   FunctionLiveVarInfo &methodLiveVarInfo;
 163   hash_map<const MachineInstr*, bool> lastUseMap;
 164   std::vector<cycles_t> nodeDelayVec;
 165   std::vector<cycles_t> nodeEarliestUseVec;
 166   std::vector<cycles_t> earliestReadyTimeForNode;
 167   cycles_t earliestReadyTime;
 168   NodeHeap candsAsHeap;                         // candidate nodes, ready to go
 169   hash_set<const SchedGraphNode*> candsAsSet;   //same entries as candsAsHeap,
 170                                                 //   but as set for fast lookup
 171   std::vector<candIndex> mcands;                // holds pointers into cands
 172   candIndex nextToTry;                          // next cand after the last
 173                                                 //   one tried in this cycle
 174
 175   int           chooseByRule1           (std::vector<candIndex>& mcands);
 176   int           chooseByRule2           (std::vector<candIndex>& mcands);
 177   int           chooseByRule3           (std::vector<candIndex>& mcands);
 178
 179   void          findSetWithMaxDelay     (std::vector<candIndex>& mcands,
 180                                          const SchedulingManager& S);
 181
 182   void          computeDelays           (const SchedGraph* graph);
 183
 184   void          initializeReadyHeap     (const SchedGraph* graph);
 185
 186   bool          instructionHasLastUse   (FunctionLiveVarInfo& LVI,
 187                                          const SchedGraphNode* graphNode);
 188
 189   // NOTE: The next two return references to the actual vector entries.
 190   //       Use the following two if you don't need to modify the value.
 191   cycles_t&     getNodeDelayRef         (const SchedGraphNode* node) {
 192     assert(node->getNodeId() < nodeDelayVec.size());
 193     return nodeDelayVec[node->getNodeId()];
 194   }
 195   cycles_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
 196     assert(node->getNodeId() < earliestReadyTimeForNode.size());
 197     return earliestReadyTimeForNode[node->getNodeId()];
 198   }
 199
 200   cycles_t      getNodeDelay            (const SchedGraphNode* node) const {
 201     return ((SchedPriorities*) this)->getNodeDelayRef(node);
 202   }
 203   cycles_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
 204     return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
 205   }
 206 };
 207
 208
 209 inline void SchedPriorities::updateTime(cycles_t c) {
 210   curTime = c;
 211   nextToTry = candsAsHeap.begin();
 212   mcands.clear();
 213 }
 214
 215 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);
 216
 217 #endif