LLVM API Documentation

SchedPriorities.h

Go to the documentation of this file.
00001 //===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Strategy:
00011 //    Priority ordering rules:
00012 //    (1) Max delay, which is the order of the heap S.candsAsHeap.
00013 //    (2) Instruction that frees up a register.
00014 //    (3) Instruction that has the maximum number of dependent instructions.
00015 //    Note that rules 2 and 3 are only used if issue conflicts prevent
00016 //    choosing a higher priority instruction by rule 1.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
00021 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
00022 
00023 #include "SchedGraph.h"
00024 #include "llvm/CodeGen/InstrScheduling.h"
00025 #include "llvm/Target/TargetSchedInfo.h"
00026 #include "llvm/ADT/hash_set"
00027 #include <list>
00028 
00029 namespace llvm {
00030 
00031 class Function;
00032 class MachineInstr;
00033 class SchedulingManager;
00034 class FunctionLiveVarInfo;
00035 
00036 //---------------------------------------------------------------------------
00037 // Debug option levels for instruction scheduling
00038 
00039 enum SchedDebugLevel_t {
00040   Sched_NoDebugInfo,
00041   Sched_Disable,
00042   Sched_PrintMachineCode,
00043   Sched_PrintSchedTrace,
00044   Sched_PrintSchedGraphs,
00045 };
00046 
00047 extern SchedDebugLevel_t SchedDebugLevel;
00048 
00049 //---------------------------------------------------------------------------
00050 // Function: instrIsFeasible
00051 //
00052 // Purpose:
00053 //   Used by the priority analysis to filter out instructions
00054 //   that are not feasible to issue in the current cycle.
00055 //   Should only be used during schedule construction..
00056 //---------------------------------------------------------------------------
00057 
00058 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
00059 
00060 
00061 
00062 struct NodeDelayPair {
00063   const SchedGraphNode* node;
00064   CycleCount_t delay;
00065   NodeDelayPair(const SchedGraphNode* n, CycleCount_t d) :  node(n), delay(d) {}
00066   inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
00067 };
00068 
00069 inline bool
00070 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
00071 {
00072   return np1->delay < np2->delay;
00073 }
00074 
00075 class NodeHeap : public std::list<NodeDelayPair*> {
00076   NodeHeap(const NodeHeap&);          // DO NOT IMPLEMENT
00077   void operator=(const NodeHeap&);    // DO NOT IMPLEMENT
00078 public:
00079   typedef std::list<NodeDelayPair*>::iterator iterator;
00080   typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
00081 
00082 public:
00083   NodeHeap() : _size(0) {}
00084 
00085   inline unsigned       size() const { return _size; }
00086 
00087   const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
00088   CycleCount_t          getDelay(const_iterator i) const { return (*i)->delay;}
00089 
00090   inline void           makeHeap() {
00091     // make_heap(begin(), end(), NDPLessThan);
00092   }
00093 
00094   inline iterator       findNode(const SchedGraphNode* node) {
00095     for (iterator I=begin(); I != end(); ++I)
00096       if (getNode(I) == node)
00097         return I;
00098     return end();
00099   }
00100 
00101   inline void     removeNode    (const SchedGraphNode* node) {
00102     iterator ndpPtr = findNode(node);
00103     if (ndpPtr != end())
00104       {
00105         delete *ndpPtr;
00106         erase(ndpPtr);
00107         --_size;
00108       }
00109   };
00110 
00111   void            insert(const SchedGraphNode* node, CycleCount_t delay) {
00112     NodeDelayPair* ndp = new NodeDelayPair(node, delay);
00113     if (_size == 0 || front()->delay < delay)
00114       push_front(ndp);
00115     else
00116       {
00117         iterator I=begin();
00118         for ( ; I != end() && getDelay(I) >= delay; ++I)
00119           ;
00120         std::list<NodeDelayPair*>::insert(I, ndp);
00121       }
00122     _size++;
00123   }
00124 private:
00125   unsigned int _size;
00126 };
00127 
00128 
00129 class SchedPriorities {
00130   SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
00131   void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
00132 public:
00133   SchedPriorities(const Function *F, const SchedGraph *G,
00134                   FunctionLiveVarInfo &LVI);
00135 
00136 
00137   // This must be called before scheduling begins.
00138   void          initialize              ();
00139 
00140   CycleCount_t  getTime                 () const { return curTime; }
00141   CycleCount_t  getEarliestReadyTime    () const { return earliestReadyTime; }
00142   unsigned      getNumReady             () const { return candsAsHeap.size(); }
00143   bool          nodeIsReady             (const SchedGraphNode* node) const {
00144     return (candsAsSet.find(node) != candsAsSet.end());
00145   }
00146 
00147   void          issuedReadyNodeAt       (CycleCount_t curTime,
00148                                          const SchedGraphNode* node);
00149 
00150   void          insertReady             (const SchedGraphNode* node);
00151 
00152   void          updateTime              (CycleCount_t /*unused*/);
00153 
00154   const SchedGraphNode* getNextHighest  (const SchedulingManager& S,
00155                                          CycleCount_t curTime);
00156                                         // choose next highest priority instr
00157 
00158 private:
00159   typedef NodeHeap::iterator candIndex;
00160 
00161 private:
00162   CycleCount_t curTime;
00163   const SchedGraph* graph;
00164   FunctionLiveVarInfo &methodLiveVarInfo;
00165   hash_map<const MachineInstr*, bool> lastUseMap;
00166   std::vector<CycleCount_t> nodeDelayVec;
00167   std::vector<CycleCount_t> nodeEarliestUseVec;
00168   std::vector<CycleCount_t> earliestReadyTimeForNode;
00169   CycleCount_t earliestReadyTime;
00170   NodeHeap candsAsHeap;                         // candidate nodes, ready to go
00171   hash_set<const SchedGraphNode*> candsAsSet;   //same entries as candsAsHeap,
00172                                                 //   but as set for fast lookup
00173   std::vector<candIndex> mcands;                // holds pointers into cands
00174   candIndex nextToTry;                          // next cand after the last
00175                                                 //   one tried in this cycle
00176 
00177   int           chooseByRule1           (std::vector<candIndex>& mcands);
00178   int           chooseByRule2           (std::vector<candIndex>& mcands);
00179   int           chooseByRule3           (std::vector<candIndex>& mcands);
00180 
00181   void          findSetWithMaxDelay     (std::vector<candIndex>& mcands,
00182                                          const SchedulingManager& S);
00183 
00184   void          computeDelays           (const SchedGraph* graph);
00185 
00186   void          initializeReadyHeap     (const SchedGraph* graph);
00187 
00188   bool          instructionHasLastUse   (FunctionLiveVarInfo& LVI,
00189                                          const SchedGraphNode* graphNode);
00190 
00191   // NOTE: The next two return references to the actual vector entries.
00192   //       Use the following two if you don't need to modify the value.
00193   CycleCount_t& getNodeDelayRef         (const SchedGraphNode* node) {
00194     assert(node->getNodeId() < nodeDelayVec.size());
00195     return nodeDelayVec[node->getNodeId()];
00196   }
00197   CycleCount_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
00198     assert(node->getNodeId() < earliestReadyTimeForNode.size());
00199     return earliestReadyTimeForNode[node->getNodeId()];
00200   }
00201 
00202   CycleCount_t      getNodeDelay            (const SchedGraphNode* node) const {
00203     return ((SchedPriorities*) this)->getNodeDelayRef(node);
00204   }
00205   CycleCount_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
00206     return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
00207   }
00208 };
00209 
00210 
00211 inline void SchedPriorities::updateTime(CycleCount_t c) {
00212   curTime = c;
00213   nextToTry = candsAsHeap.begin();
00214   mcands.clear();
00215 }
00216 
00217 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);
00218 
00219 } // End llvm namespace
00220 
00221 #endif