LLVM API Documentation
00001 //===-- SchedPriorities.h - Encapsulate scheduling heuristics -------------===// 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 #include "SchedPriorities.h" 00021 #include "../LiveVar/FunctionLiveVarInfo.h" 00022 #include "llvm/CodeGen/MachineBasicBlock.h" 00023 #include "llvm/Support/CFG.h" 00024 #include "llvm/ADT/PostOrderIterator.h" 00025 #include <iostream> 00026 00027 namespace llvm { 00028 00029 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) { 00030 return os << "Delay for node " << nd->node->getNodeId() 00031 << " = " << (long)nd->delay << "\n"; 00032 } 00033 00034 00035 SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G, 00036 FunctionLiveVarInfo &LVI) 00037 : curTime(0), graph(G), methodLiveVarInfo(LVI), 00038 nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious 00039 earliestReadyTimeForNode(G->getNumNodes(), 0), 00040 earliestReadyTime(0), 00041 nextToTry(candsAsHeap.begin()) 00042 { 00043 computeDelays(graph); 00044 } 00045 00046 00047 void 00048 SchedPriorities::initialize() { 00049 initializeReadyHeap(graph); 00050 } 00051 00052 00053 void 00054 SchedPriorities::computeDelays(const SchedGraph* graph) { 00055 po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph); 00056 for ( ; poIter != poEnd; ++poIter) { 00057 const SchedGraphNode* node = *poIter; 00058 cycles_t nodeDelay; 00059 if (node->beginOutEdges() == node->endOutEdges()) 00060 nodeDelay = node->getLatency(); 00061 else { 00062 // Iterate over the out-edges of the node to compute delay 00063 nodeDelay = 0; 00064 for (SchedGraphNode::const_iterator E=node->beginOutEdges(); 00065 E != node->endOutEdges(); ++E) { 00066 cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink()); 00067 nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay()); 00068 } 00069 } 00070 getNodeDelayRef(node) = nodeDelay; 00071 } 00072 } 00073 00074 00075 void 00076 SchedPriorities::initializeReadyHeap(const SchedGraph* graph) { 00077 const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot(); 00078 assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root"); 00079 00080 // Insert immediate successors of dummy root, which are the actual roots 00081 sg_succ_const_iterator SEnd = succ_end(graphRoot); 00082 for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S) 00083 this->insertReady(*S); 00084 00085 #undef TEST_HEAP_CONVERSION 00086 #ifdef TEST_HEAP_CONVERSION 00087 std::cerr << "Before heap conversion:\n"; 00088 copy(candsAsHeap.begin(), candsAsHeap.end(), 00089 ostream_iterator<NodeDelayPair*>(std::cerr,"\n")); 00090 #endif 00091 00092 candsAsHeap.makeHeap(); 00093 00094 nextToTry = candsAsHeap.begin(); 00095 00096 #ifdef TEST_HEAP_CONVERSION 00097 std::cerr << "After heap conversion:\n"; 00098 copy(candsAsHeap.begin(), candsAsHeap.end(), 00099 ostream_iterator<NodeDelayPair*>(std::cerr,"\n")); 00100 #endif 00101 } 00102 00103 void 00104 SchedPriorities::insertReady(const SchedGraphNode* node) { 00105 candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]); 00106 candsAsSet.insert(node); 00107 mcands.clear(); // ensure reset choices is called before any more choices 00108 earliestReadyTime = std::min(earliestReadyTime, 00109 getEarliestReadyTimeForNode(node)); 00110 00111 if (SchedDebugLevel >= Sched_PrintSchedTrace) { 00112 std::cerr << " Node " << node->getNodeId() << " will be ready in Cycle " 00113 << getEarliestReadyTimeForNode(node) << "; " 00114 << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n" 00115 << " " << *node->getMachineInstr() << "\n"; 00116 } 00117 } 00118 00119 void 00120 SchedPriorities::issuedReadyNodeAt(cycles_t curTime, 00121 const SchedGraphNode* node) { 00122 candsAsHeap.removeNode(node); 00123 candsAsSet.erase(node); 00124 mcands.clear(); // ensure reset choices is called before any more choices 00125 00126 if (earliestReadyTime == getEarliestReadyTimeForNode(node)) { 00127 // earliestReadyTime may have been due to this node, so recompute it 00128 earliestReadyTime = HUGE_LATENCY; 00129 for (NodeHeap::const_iterator I=candsAsHeap.begin(); 00130 I != candsAsHeap.end(); ++I) 00131 if (candsAsHeap.getNode(I)) { 00132 earliestReadyTime = 00133 std::min(earliestReadyTime, 00134 getEarliestReadyTimeForNode(candsAsHeap.getNode(I))); 00135 } 00136 } 00137 00138 // Now update ready times for successors 00139 for (SchedGraphNode::const_iterator E=node->beginOutEdges(); 00140 E != node->endOutEdges(); ++E) { 00141 cycles_t& etime = 00142 getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink()); 00143 etime = std::max(etime, curTime + (*E)->getMinDelay()); 00144 } 00145 } 00146 00147 00148 //---------------------------------------------------------------------- 00149 // Priority ordering rules: 00150 // (1) Max delay, which is the order of the heap S.candsAsHeap. 00151 // (2) Instruction that frees up a register. 00152 // (3) Instruction that has the maximum number of dependent instructions. 00153 // Note that rules 2 and 3 are only used if issue conflicts prevent 00154 // choosing a higher priority instruction by rule 1. 00155 //---------------------------------------------------------------------- 00156 00157 inline int 00158 SchedPriorities::chooseByRule1(std::vector<candIndex>& mcands) { 00159 return (mcands.size() == 1)? 0 // only one choice exists so take it 00160 : -1; // -1 indicates multiple choices 00161 } 00162 00163 inline int 00164 SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands) { 00165 assert(mcands.size() >= 1 && "Should have at least one candidate here."); 00166 for (unsigned i=0, N = mcands.size(); i < N; i++) 00167 if (instructionHasLastUse(methodLiveVarInfo, 00168 candsAsHeap.getNode(mcands[i]))) 00169 return i; 00170 return -1; 00171 } 00172 00173 inline int 00174 SchedPriorities::chooseByRule3(std::vector<candIndex>& mcands) { 00175 assert(mcands.size() >= 1 && "Should have at least one candidate here."); 00176 int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges(); 00177 int indexWithMaxUses = 0; 00178 for (unsigned i=1, N = mcands.size(); i < N; i++) { 00179 int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges(); 00180 if (numUses > maxUses) { 00181 maxUses = numUses; 00182 indexWithMaxUses = i; 00183 } 00184 } 00185 return indexWithMaxUses; 00186 } 00187 00188 const SchedGraphNode* 00189 SchedPriorities::getNextHighest(const SchedulingManager& S, 00190 cycles_t curTime) { 00191 int nextIdx = -1; 00192 const SchedGraphNode* nextChoice = NULL; 00193 00194 if (mcands.size() == 0) 00195 findSetWithMaxDelay(mcands, S); 00196 00197 while (nextIdx < 0 && mcands.size() > 0) { 00198 nextIdx = chooseByRule1(mcands); // rule 1 00199 00200 if (nextIdx == -1) 00201 nextIdx = chooseByRule2(mcands); // rule 2 00202 00203 if (nextIdx == -1) 00204 nextIdx = chooseByRule3(mcands); // rule 3 00205 00206 if (nextIdx == -1) 00207 nextIdx = 0; // default to first choice by delays 00208 00209 // We have found the next best candidate. Check if it ready in 00210 // the current cycle, and if it is feasible. 00211 // If not, remove it from mcands and continue. Refill mcands if 00212 // it becomes empty. 00213 nextChoice = candsAsHeap.getNode(mcands[nextIdx]); 00214 if (getEarliestReadyTimeForNode(nextChoice) > curTime 00215 || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpcode())) 00216 { 00217 mcands.erase(mcands.begin() + nextIdx); 00218 nextIdx = -1; 00219 if (mcands.size() == 0) 00220 findSetWithMaxDelay(mcands, S); 00221 } 00222 } 00223 00224 if (nextIdx >= 0) { 00225 mcands.erase(mcands.begin() + nextIdx); 00226 return nextChoice; 00227 } else 00228 return NULL; 00229 } 00230 00231 00232 void 00233 SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands, 00234 const SchedulingManager& S) 00235 { 00236 if (mcands.size() == 0 && nextToTry != candsAsHeap.end()) 00237 { // out of choices at current maximum delay; 00238 // put nodes with next highest delay in mcands 00239 candIndex next = nextToTry; 00240 cycles_t maxDelay = candsAsHeap.getDelay(next); 00241 for (; next != candsAsHeap.end() 00242 && candsAsHeap.getDelay(next) == maxDelay; ++next) 00243 mcands.push_back(next); 00244 00245 nextToTry = next; 00246 00247 if (SchedDebugLevel >= Sched_PrintSchedTrace) { 00248 std::cerr << " Cycle " << (long)getTime() << ": " 00249 << "Next highest delay = " << (long)maxDelay << " : " 00250 << mcands.size() << " Nodes with this delay: "; 00251 for (unsigned i=0; i < mcands.size(); i++) 00252 std::cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", "; 00253 std::cerr << "\n"; 00254 } 00255 } 00256 } 00257 00258 00259 bool 00260 SchedPriorities::instructionHasLastUse(FunctionLiveVarInfo &LVI, 00261 const SchedGraphNode* graphNode) { 00262 const MachineInstr *MI = graphNode->getMachineInstr(); 00263 00264 hash_map<const MachineInstr*, bool>::const_iterator 00265 ui = lastUseMap.find(MI); 00266 if (ui != lastUseMap.end()) 00267 return ui->second; 00268 00269 // else check if instruction is a last use and save it in the hash_map 00270 bool hasLastUse = false; 00271 const BasicBlock* bb = graphNode->getMachineBasicBlock().getBasicBlock(); 00272 const ValueSet &LVs = LVI.getLiveVarSetBeforeMInst(MI, bb); 00273 00274 for (MachineInstr::const_val_op_iterator OI = MI->begin(), OE = MI->end(); 00275 OI != OE; ++OI) 00276 if (!LVs.count(*OI)) { 00277 hasLastUse = true; 00278 break; 00279 } 00280 00281 return lastUseMap[MI] = hasLastUse; 00282 } 00283 00284 } // End llvm namespace