LLVM API Documentation
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 cycles_t delay; 00065 NodeDelayPair(const SchedGraphNode* n, cycles_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 cycles_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, cycles_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 cycles_t getTime () const { return curTime; } 00141 cycles_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 (cycles_t curTime, 00148 const SchedGraphNode* node); 00149 00150 void insertReady (const SchedGraphNode* node); 00151 00152 void updateTime (cycles_t /*unused*/); 00153 00154 const SchedGraphNode* getNextHighest (const SchedulingManager& S, 00155 cycles_t curTime); 00156 // choose next highest priority instr 00157 00158 private: 00159 typedef NodeHeap::iterator candIndex; 00160 00161 private: 00162 cycles_t curTime; 00163 const SchedGraph* graph; 00164 FunctionLiveVarInfo &methodLiveVarInfo; 00165 hash_map<const MachineInstr*, bool> lastUseMap; 00166 std::vector<cycles_t> nodeDelayVec; 00167 std::vector<cycles_t> nodeEarliestUseVec; 00168 std::vector<cycles_t> earliestReadyTimeForNode; 00169 cycles_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 cycles_t& getNodeDelayRef (const SchedGraphNode* node) { 00194 assert(node->getNodeId() < nodeDelayVec.size()); 00195 return nodeDelayVec[node->getNodeId()]; 00196 } 00197 cycles_t& getEarliestReadyTimeForNodeRef (const SchedGraphNode* node) { 00198 assert(node->getNodeId() < earliestReadyTimeForNode.size()); 00199 return earliestReadyTimeForNode[node->getNodeId()]; 00200 } 00201 00202 cycles_t getNodeDelay (const SchedGraphNode* node) const { 00203 return ((SchedPriorities*) this)->getNodeDelayRef(node); 00204 } 00205 cycles_t getEarliestReadyTimeForNode(const SchedGraphNode* node) const { 00206 return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node); 00207 } 00208 }; 00209 00210 00211 inline void SchedPriorities::updateTime(cycles_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