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