LLVM API Documentation

SchedPriorities.cpp

Go to the documentation of this file.
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     CycleCount_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         CycleCount_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(CycleCount_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     CycleCount_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                                 CycleCount_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       CycleCount_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