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