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