lib/CodeGen/SelectionDAG/ScheduleDAG.cpp

   1 //===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the ScheduleDAG class, which is a base class used by
  11 // scheduling implementation classes.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "pre-RA-sched"
  16 #include "llvm/CodeGen/ScheduleDAG.h"
  17 #include "llvm/Target/TargetMachine.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19 #include "llvm/Target/TargetRegisterInfo.h"
  20 #include "llvm/Support/Debug.h"
  21 using namespace llvm;
  22
  23 ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
  24                          const TargetMachine &tm)
  25   : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) {
  26   TII = TM.getInstrInfo();
  27   MF  = BB->getParent();
  28   TRI = TM.getRegisterInfo();
  29   TLI = TM.getTargetLowering();
  30   ConstPool = MF->getConstantPool();
  31 }
  32
  33 /// CheckForPhysRegDependency - Check if the dependency between def and use of
  34 /// a specified operand is a physical register dependency. If so, returns the
  35 /// register and the cost of copying the register.
  36 static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
  37                                       const TargetRegisterInfo *TRI,
  38                                       const TargetInstrInfo *TII,
  39                                       unsigned &PhysReg, int &Cost) {
  40   if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
  41     return;
  42
  43   unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
  44   if (TargetRegisterInfo::isVirtualRegister(Reg))
  45     return;
  46
  47   unsigned ResNo = User->getOperand(2).getResNo();
  48   if (Def->isMachineOpcode()) {
  49     const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
  50     if (ResNo >= II.getNumDefs() &&
  51         II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
  52       PhysReg = Reg;
  53       const TargetRegisterClass *RC =
  54         TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo));
  55       Cost = RC->getCopyCost();
  56     }
  57   }
  58 }
  59
  60 SUnit *ScheduleDAG::Clone(SUnit *Old) {
  61   SUnit *SU = NewSUnit(Old->getNode());
  62   SU->OrigNode = Old->OrigNode;
  63   SU->Latency = Old->Latency;
  64   SU->isTwoAddress = Old->isTwoAddress;
  65   SU->isCommutable = Old->isCommutable;
  66   SU->hasPhysRegDefs = Old->hasPhysRegDefs;
  67   return SU;
  68 }
  69
  70
  71 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
  72 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
  73 /// together nodes with a single SUnit.
  74 void ScheduleDAG::BuildSchedUnits() {
  75   // Reserve entries in the vector for each of the SUnits we are creating.  This
  76   // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
  77   // invalidated.
  78   SUnits.reserve(DAG->allnodes_size());
  79
  80   // During scheduling, the NodeId field of SDNode is used to map SDNodes
  81   // to their associated SUnits by holding SUnits table indices. A value
  82   // of -1 means the SDNode does not yet have an associated SUnit.
  83   for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
  84        E = DAG->allnodes_end(); NI != E; ++NI)
  85     NI->setNodeId(-1);
  86
  87   for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
  88        E = DAG->allnodes_end(); NI != E; ++NI) {
  89     if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
  90       continue;
  91
  92     // If this node has already been processed, stop now.
  93     if (NI->getNodeId() != -1) continue;
  94
  95     SUnit *NodeSUnit = NewSUnit(NI);
  96
  97     // See if anything is flagged to this node, if so, add them to flagged
  98     // nodes.  Nodes can have at most one flag input and one flag output.  Flags
  99     // are required the be the last operand and result of a node.
 100
 101     // Scan up to find flagged preds.
 102     SDNode *N = NI;
 103     if (N->getNumOperands() &&
 104         N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
 105       do {
 106         N = N->getOperand(N->getNumOperands()-1).getNode();
 107         assert(N->getNodeId() == -1 && "Node already inserted!");
 108         N->setNodeId(NodeSUnit->NodeNum);
 109       } while (N->getNumOperands() &&
 110                N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
 111     }
 112
 113     // Scan down to find any flagged succs.
 114     N = NI;
 115     while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
 116       SDValue FlagVal(N, N->getNumValues()-1);
 117
 118       // There are either zero or one users of the Flag result.
 119       bool HasFlagUse = false;
 120       for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
 121            UI != E; ++UI)
 122         if (FlagVal.isOperandOf(*UI)) {
 123           HasFlagUse = true;
 124           assert(N->getNodeId() == -1 && "Node already inserted!");
 125           N->setNodeId(NodeSUnit->NodeNum);
 126           N = *UI;
 127           break;
 128         }
 129       if (!HasFlagUse) break;
 130     }
 131
 132     // If there are flag operands involved, N is now the bottom-most node
 133     // of the sequence of nodes that are flagged together.
 134     // Update the SUnit.
 135     NodeSUnit->setNode(N);
 136     assert(N->getNodeId() == -1 && "Node already inserted!");
 137     N->setNodeId(NodeSUnit->NodeNum);
 138
 139     ComputeLatency(NodeSUnit);
 140   }
 141
 142   // Pass 2: add the preds, succs, etc.
 143   for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
 144     SUnit *SU = &SUnits[su];
 145     SDNode *MainNode = SU->getNode();
 146
 147     if (MainNode->isMachineOpcode()) {
 148       unsigned Opc = MainNode->getMachineOpcode();
 149       const TargetInstrDesc &TID = TII->get(Opc);
 150       for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
 151         if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
 152           SU->isTwoAddress = true;
 153           break;
 154         }
 155       }
 156       if (TID.isCommutable())
 157         SU->isCommutable = true;
 158     }
 159
 160     // Find all predecessors and successors of the group.
 161     for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
 162       if (N->isMachineOpcode() &&
 163           TII->get(N->getMachineOpcode()).getImplicitDefs() &&
 164           CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs())
 165         SU->hasPhysRegDefs = true;
 166
 167       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 168         SDNode *OpN = N->getOperand(i).getNode();
 169         if (isPassiveNode(OpN)) continue;   // Not scheduled.
 170         SUnit *OpSU = &SUnits[OpN->getNodeId()];
 171         assert(OpSU && "Node has no SUnit!");
 172         if (OpSU == SU) continue;           // In the same group.
 173
 174         MVT OpVT = N->getOperand(i).getValueType();
 175         assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
 176         bool isChain = OpVT == MVT::Other;
 177
 178         unsigned PhysReg = 0;
 179         int Cost = 1;
 180         // Determine if this is a physical register dependency.
 181         CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
 182         SU->addPred(OpSU, isChain, false, PhysReg, Cost);
 183       }
 184     }
 185   }
 186 }
 187
 188 void ScheduleDAG::ComputeLatency(SUnit *SU) {
 189   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
 190
 191   // Compute the latency for the node.  We use the sum of the latencies for
 192   // all nodes flagged together into this SUnit.
 193   if (InstrItins.isEmpty()) {
 194     // No latency information.
 195     SU->Latency = 1;
 196     return;
 197   }
 198
 199   SU->Latency = 0;
 200   for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
 201     if (N->isMachineOpcode()) {
 202       unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass();
 203       const InstrStage *S = InstrItins.begin(SchedClass);
 204       const InstrStage *E = InstrItins.end(SchedClass);
 205       for (; S != E; ++S)
 206         SU->Latency += S->Cycles;
 207     }
 208   }
 209 }
 210
 211 /// CalculateDepths - compute depths using algorithms for the longest
 212 /// paths in the DAG
 213 void ScheduleDAG::CalculateDepths() {
 214   unsigned DAGSize = SUnits.size();
 215   std::vector<SUnit*> WorkList;
 216   WorkList.reserve(DAGSize);
 217
 218   // Initialize the data structures
 219   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
 220     SUnit *SU = &SUnits[i];
 221     unsigned Degree = SU->Preds.size();
 222     // Temporarily use the Depth field as scratch space for the degree count.
 223     SU->Depth = Degree;
 224
 225     // Is it a node without dependencies?
 226     if (Degree == 0) {
 227         assert(SU->Preds.empty() && "SUnit should have no predecessors");
 228         // Collect leaf nodes
 229         WorkList.push_back(SU);
 230     }
 231   }
 232
 233   // Process nodes in the topological order
 234   while (!WorkList.empty()) {
 235     SUnit *SU = WorkList.back();
 236     WorkList.pop_back();
 237     unsigned SUDepth = 0;
 238
 239     // Use dynamic programming:
 240     // When current node is being processed, all of its dependencies
 241     // are already processed.
 242     // So, just iterate over all predecessors and take the longest path
 243     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 244          I != E; ++I) {
 245       unsigned PredDepth = I->Dep->Depth;
 246       if (PredDepth+1 > SUDepth) {
 247           SUDepth = PredDepth + 1;
 248       }
 249     }
 250
 251     SU->Depth = SUDepth;
 252
 253     // Update degrees of all nodes depending on current SUnit
 254     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 255          I != E; ++I) {
 256       SUnit *SU = I->Dep;
 257       if (!--SU->Depth)
 258         // If all dependencies of the node are processed already,
 259         // then the longest path for the node can be computed now
 260         WorkList.push_back(SU);
 261     }
 262   }
 263 }
 264
 265 /// CalculateHeights - compute heights using algorithms for the longest
 266 /// paths in the DAG
 267 void ScheduleDAG::CalculateHeights() {
 268   unsigned DAGSize = SUnits.size();
 269   std::vector<SUnit*> WorkList;
 270   WorkList.reserve(DAGSize);
 271
 272   // Initialize the data structures
 273   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
 274     SUnit *SU = &SUnits[i];
 275     unsigned Degree = SU->Succs.size();
 276     // Temporarily use the Height field as scratch space for the degree count.
 277     SU->Height = Degree;
 278
 279     // Is it a node without dependencies?
 280     if (Degree == 0) {
 281         assert(SU->Succs.empty() && "Something wrong");
 282         assert(WorkList.empty() && "Should be empty");
 283         // Collect leaf nodes
 284         WorkList.push_back(SU);
 285     }
 286   }
 287
 288   // Process nodes in the topological order
 289   while (!WorkList.empty()) {
 290     SUnit *SU = WorkList.back();
 291     WorkList.pop_back();
 292     unsigned SUHeight = 0;
 293
 294     // Use dynamic programming:
 295     // When current node is being processed, all of its dependencies
 296     // are already processed.
 297     // So, just iterate over all successors and take the longest path
 298     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 299          I != E; ++I) {
 300       unsigned SuccHeight = I->Dep->Height;
 301       if (SuccHeight+1 > SUHeight) {
 302           SUHeight = SuccHeight + 1;
 303       }
 304     }
 305
 306     SU->Height = SUHeight;
 307
 308     // Update degrees of all nodes depending on current SUnit
 309     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 310          I != E; ++I) {
 311       SUnit *SU = I->Dep;
 312       if (!--SU->Height)
 313         // If all dependencies of the node are processed already,
 314         // then the longest path for the node can be computed now
 315         WorkList.push_back(SU);
 316     }
 317   }
 318 }
 319
 320 /// CountResults - The results of target nodes have register or immediate
 321 /// operands first, then an optional chain, and optional flag operands (which do
 322 /// not go into the resulting MachineInstr).
 323 unsigned ScheduleDAG::CountResults(SDNode *Node) {
 324   unsigned N = Node->getNumValues();
 325   while (N && Node->getValueType(N - 1) == MVT::Flag)
 326     --N;
 327   if (N && Node->getValueType(N - 1) == MVT::Other)
 328     --N;    // Skip over chain result.
 329   return N;
 330 }
 331
 332 /// CountOperands - The inputs to target nodes have any actual inputs first,
 333 /// followed by special operands that describe memory references, then an
 334 /// optional chain operand, then an optional flag operand.  Compute the number
 335 /// of actual operands that will go into the resulting MachineInstr.
 336 unsigned ScheduleDAG::CountOperands(SDNode *Node) {
 337   unsigned N = ComputeMemOperandsEnd(Node);
 338   while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode()))
 339     --N; // Ignore MEMOPERAND nodes
 340   return N;
 341 }
 342
 343 /// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
 344 /// operand
 345 unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) {
 346   unsigned N = Node->getNumOperands();
 347   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
 348     --N;
 349   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
 350     --N; // Ignore chain if it exists.
 351   return N;
 352 }
 353
 354
 355 /// dump - dump the schedule.
 356 void ScheduleDAG::dumpSchedule() const {
 357   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 358     if (SUnit *SU = Sequence[i])
 359       SU->dump(DAG);
 360     else
 361       cerr << "**** NOOP ****\n";
 362   }
 363 }
 364
 365
 366 /// Run - perform scheduling.
 367 ///
 368 void ScheduleDAG::Run() {
 369   Schedule();
 370
 371   DOUT << "*** Final schedule ***\n";
 372   DEBUG(dumpSchedule());
 373   DOUT << "\n";
 374 }
 375
 376 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
 377 /// a group of nodes flagged together.
 378 void SUnit::dump(const SelectionDAG *G) const {
 379   cerr << "SU(" << NodeNum << "): ";
 380   if (getNode())
 381     getNode()->dump(G);
 382   else
 383     cerr << "CROSS RC COPY ";
 384   cerr << "\n";
 385   SmallVector<SDNode *, 4> FlaggedNodes;
 386   for (SDNode *N = getNode()->getFlaggedNode(); N; N = N->getFlaggedNode())
 387     FlaggedNodes.push_back(N);
 388   while (!FlaggedNodes.empty()) {
 389     cerr << "    ";
 390     FlaggedNodes.back()->dump(G);
 391     cerr << "\n";
 392     FlaggedNodes.pop_back();
 393   }
 394 }
 395
 396 void SUnit::dumpAll(const SelectionDAG *G) const {
 397   dump(G);
 398
 399   cerr << "  # preds left       : " << NumPredsLeft << "\n";
 400   cerr << "  # succs left       : " << NumSuccsLeft << "\n";
 401   cerr << "  Latency            : " << Latency << "\n";
 402   cerr << "  Depth              : " << Depth << "\n";
 403   cerr << "  Height             : " << Height << "\n";
 404
 405   if (Preds.size() != 0) {
 406     cerr << "  Predecessors:\n";
 407     for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
 408          I != E; ++I) {
 409       if (I->isCtrl)
 410         cerr << "   ch  #";
 411       else
 412         cerr << "   val #";
 413       cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
 414       if (I->isSpecial)
 415         cerr << " *";
 416       cerr << "\n";
 417     }
 418   }
 419   if (Succs.size() != 0) {
 420     cerr << "  Successors:\n";
 421     for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
 422          I != E; ++I) {
 423       if (I->isCtrl)
 424         cerr << "   ch  #";
 425       else
 426         cerr << "   val #";
 427       cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
 428       if (I->isSpecial)
 429         cerr << " *";
 430       cerr << "\n";
 431     }
 432   }
 433   cerr << "\n";
 434 }