lib/CodeGen/InstrSched/SchedPriorities.cpp

   1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics -------------===//
   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 #include "SchedPriorities.h"
  21 #include "llvm/CodeGen/FunctionLiveVarInfo.h"
  22 #include "llvm/CodeGen/MachineBasicBlock.h"
  23 #include "llvm/Support/CFG.h"
  24 #include "Support/PostOrderIterator.h"
  25
  26 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
  27   return os << "Delay for node " << nd->node->getNodeId()
  28             << " = " << (long)nd->delay << "\n";
  29 }
  30
  31
  32 SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G,
  33                                  FunctionLiveVarInfo &LVI)
  34   : curTime(0), graph(G), methodLiveVarInfo(LVI),
  35     nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious
  36     earliestReadyTimeForNode(G->getNumNodes(), 0),
  37     earliestReadyTime(0),
  38     nextToTry(candsAsHeap.begin())
  39 {
  40   computeDelays(graph);
  41 }
  42
  43
  44 void
  45 SchedPriorities::initialize() {
  46   initializeReadyHeap(graph);
  47 }
  48
  49
  50 void
  51 SchedPriorities::computeDelays(const SchedGraph* graph) {
  52   po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
  53   for ( ; poIter != poEnd; ++poIter) {
  54     const SchedGraphNode* node = *poIter;
  55     cycles_t nodeDelay;
  56     if (node->beginOutEdges() == node->endOutEdges())
  57       nodeDelay = node->getLatency();
  58     else {
  59       // Iterate over the out-edges of the node to compute delay
  60       nodeDelay = 0;
  61       for (SchedGraphNode::const_iterator E=node->beginOutEdges();
  62            E != node->endOutEdges(); ++E) {
  63         cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
  64         nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
  65       }
  66     }
  67     getNodeDelayRef(node) = nodeDelay;
  68   }
  69 }
  70
  71
  72 void
  73 SchedPriorities::initializeReadyHeap(const SchedGraph* graph) {
  74   const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
  75   assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
  76
  77   // Insert immediate successors of dummy root, which are the actual roots
  78   sg_succ_const_iterator SEnd = succ_end(graphRoot);
  79   for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
  80     this->insertReady(*S);
  81
  82 #undef TEST_HEAP_CONVERSION
  83 #ifdef TEST_HEAP_CONVERSION
  84   std::cerr << "Before heap conversion:\n";
  85   copy(candsAsHeap.begin(), candsAsHeap.end(),
  86        ostream_iterator<NodeDelayPair*>(std::cerr,"\n"));
  87 #endif
  88
  89   candsAsHeap.makeHeap();
  90
  91   nextToTry = candsAsHeap.begin();
  92
  93 #ifdef TEST_HEAP_CONVERSION
  94   std::cerr << "After heap conversion:\n";
  95   copy(candsAsHeap.begin(), candsAsHeap.end(),
  96        ostream_iterator<NodeDelayPair*>(std::cerr,"\n"));
  97 #endif
  98 }
  99
 100 void
 101 SchedPriorities::insertReady(const SchedGraphNode* node) {
 102   candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
 103   candsAsSet.insert(node);
 104   mcands.clear(); // ensure reset choices is called before any more choices
 105   earliestReadyTime = std::min(earliestReadyTime,
 106                        getEarliestReadyTimeForNode(node));
 107
 108   if (SchedDebugLevel >= Sched_PrintSchedTrace) {
 109     std::cerr << " Node " << node->getNodeId() << " will be ready in Cycle "
 110               << getEarliestReadyTimeForNode(node) << "; "
 111               << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n"
 112               << "        " << *node->getMachineInstr() << "\n";
 113   }
 114 }
 115
 116 void
 117 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
 118                                    const SchedGraphNode* node) {
 119   candsAsHeap.removeNode(node);
 120   candsAsSet.erase(node);
 121   mcands.clear(); // ensure reset choices is called before any more choices
 122
 123   if (earliestReadyTime == getEarliestReadyTimeForNode(node)) {
 124     // earliestReadyTime may have been due to this node, so recompute it
 125     earliestReadyTime = HUGE_LATENCY;
 126     for (NodeHeap::const_iterator I=candsAsHeap.begin();
 127          I != candsAsHeap.end(); ++I)
 128       if (candsAsHeap.getNode(I)) {
 129         earliestReadyTime =
 130           std::min(earliestReadyTime,
 131                    getEarliestReadyTimeForNode(candsAsHeap.getNode(I)));
 132       }
 133   }
 134
 135   // Now update ready times for successors
 136   for (SchedGraphNode::const_iterator E=node->beginOutEdges();
 137        E != node->endOutEdges(); ++E) {
 138     cycles_t& etime =
 139       getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
 140     etime = std::max(etime, curTime + (*E)->getMinDelay());
 141   }
 142 }
 143
 144
 145 //----------------------------------------------------------------------
 146 // Priority ordering rules:
 147 // (1) Max delay, which is the order of the heap S.candsAsHeap.
 148 // (2) Instruction that frees up a register.
 149 // (3) Instruction that has the maximum number of dependent instructions.
 150 // Note that rules 2 and 3 are only used if issue conflicts prevent
 151 // choosing a higher priority instruction by rule 1.
 152 //----------------------------------------------------------------------
 153
 154 inline int
 155 SchedPriorities::chooseByRule1(std::vector<candIndex>& mcands) {
 156   return (mcands.size() == 1)? 0        // only one choice exists so take it
 157                              : -1;      // -1 indicates multiple choices
 158 }
 159
 160 inline int
 161 SchedPriorities::chooseByRule2(std::vector<candIndex>& mcands) {
 162   assert(mcands.size() >= 1 && "Should have at least one candidate here.");
 163   for (unsigned i=0, N = mcands.size(); i < N; i++)
 164     if (instructionHasLastUse(methodLiveVarInfo,
 165                               candsAsHeap.getNode(mcands[i])))
 166       return i;
 167   return -1;
 168 }
 169
 170 inline int
 171 SchedPriorities::chooseByRule3(std::vector<candIndex>& mcands) {
 172   assert(mcands.size() >= 1 && "Should have at least one candidate here.");
 173   int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
 174   int indexWithMaxUses = 0;
 175   for (unsigned i=1, N = mcands.size(); i < N; i++) {
 176     int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
 177     if (numUses > maxUses) {
 178       maxUses = numUses;
 179       indexWithMaxUses = i;
 180     }
 181   }
 182   return indexWithMaxUses;
 183 }
 184
 185 const SchedGraphNode*
 186 SchedPriorities::getNextHighest(const SchedulingManager& S,
 187                                 cycles_t curTime) {
 188   int nextIdx = -1;
 189   const SchedGraphNode* nextChoice = NULL;
 190
 191   if (mcands.size() == 0)
 192     findSetWithMaxDelay(mcands, S);
 193
 194   while (nextIdx < 0 && mcands.size() > 0) {
 195     nextIdx = chooseByRule1(mcands);     // rule 1
 196
 197     if (nextIdx == -1)
 198       nextIdx = chooseByRule2(mcands); // rule 2
 199
 200     if (nextIdx == -1)
 201       nextIdx = chooseByRule3(mcands); // rule 3
 202
 203     if (nextIdx == -1)
 204       nextIdx = 0;                       // default to first choice by delays
 205
 206     // We have found the next best candidate.  Check if it ready in
 207     // the current cycle, and if it is feasible.
 208     // If not, remove it from mcands and continue.  Refill mcands if
 209     // it becomes empty.
 210     nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
 211     if (getEarliestReadyTimeForNode(nextChoice) > curTime
 212         || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
 213     {
 214       mcands.erase(mcands.begin() + nextIdx);
 215       nextIdx = -1;
 216       if (mcands.size() == 0)
 217         findSetWithMaxDelay(mcands, S);
 218     }
 219   }
 220
 221   if (nextIdx >= 0) {
 222     mcands.erase(mcands.begin() + nextIdx);
 223     return nextChoice;
 224   } else
 225     return NULL;
 226 }
 227
 228
 229 void
 230 SchedPriorities::findSetWithMaxDelay(std::vector<candIndex>& mcands,
 231                                      const SchedulingManager& S)
 232 {
 233   if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
 234     { // out of choices at current maximum delay;
 235       // put nodes with next highest delay in mcands
 236       candIndex next = nextToTry;
 237       cycles_t maxDelay = candsAsHeap.getDelay(next);
 238       for (; next != candsAsHeap.end()
 239              && candsAsHeap.getDelay(next) == maxDelay; ++next)
 240         mcands.push_back(next);
 241
 242       nextToTry = next;
 243
 244       if (SchedDebugLevel >= Sched_PrintSchedTrace) {
 245         std::cerr << "    Cycle " << (long)getTime() << ": "
 246                   << "Next highest delay = " << (long)maxDelay << " : "
 247                   << mcands.size() << " Nodes with this delay: ";
 248         for (unsigned i=0; i < mcands.size(); i++)
 249           std::cerr << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
 250         std::cerr << "\n";
 251       }
 252     }
 253 }
 254
 255
 256 bool
 257 SchedPriorities::instructionHasLastUse(FunctionLiveVarInfo &LVI,
 258                                        const SchedGraphNode* graphNode) {
 259   const MachineInstr *MI = graphNode->getMachineInstr();
 260
 261   hash_map<const MachineInstr*, bool>::const_iterator
 262     ui = lastUseMap.find(MI);
 263   if (ui != lastUseMap.end())
 264     return ui->second;
 265
 266   // else check if instruction is a last use and save it in the hash_map
 267   bool hasLastUse = false;
 268   const BasicBlock* bb = graphNode->getMachineBasicBlock().getBasicBlock();
 269   const ValueSet &LVs = LVI.getLiveVarSetBeforeMInst(MI, bb);
 270
 271   for (MachineInstr::const_val_op_iterator OI = MI->begin(), OE = MI->end();
 272        OI != OE; ++OI)
 273     if (!LVs.count(*OI)) {
 274       hasLastUse = true;
 275       break;
 276     }
 277
 278   return lastUseMap[MI] = hasLastUse;
 279 }
 280