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