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