lib/CodeGen/SelectionDAG/ScheduleDAG.cpp

   1 //===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by James M. Laskey and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements a simple two pass scheduler.  The first pass attempts to push
  11 // backward any lengthy instructions and critical paths.  The second pass packs
  12 // instructions into semi-optimal time slots.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "sched"
  17 #include "llvm/CodeGen/MachineConstantPool.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/ScheduleDAG.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetInstrItineraries.h"
  24 #include "llvm/Target/TargetLowering.h"
  25 #include "llvm/Support/Debug.h"
  26 #include <iostream>
  27 using namespace llvm;
  28
  29
  30 /// CountResults - The results of target nodes have register or immediate
  31 /// operands first, then an optional chain, and optional flag operands (which do
  32 /// not go into the machine instrs.)
  33 static unsigned CountResults(SDNode *Node) {
  34   unsigned N = Node->getNumValues();
  35   while (N && Node->getValueType(N - 1) == MVT::Flag)
  36     --N;
  37   if (N && Node->getValueType(N - 1) == MVT::Other)
  38     --N;    // Skip over chain result.
  39   return N;
  40 }
  41
  42 /// CountOperands  The inputs to target nodes have any actual inputs first,
  43 /// followed by an optional chain operand, then flag operands.  Compute the
  44 /// number of actual operands that  will go into the machine instr.
  45 static unsigned CountOperands(SDNode *Node) {
  46   unsigned N = Node->getNumOperands();
  47   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
  48     --N;
  49   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
  50     --N; // Ignore chain if it exists.
  51   return N;
  52 }
  53
  54 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
  55 ///
  56 void ScheduleDAG::PrepareNodeInfo() {
  57   // Allocate node information
  58   Info = new NodeInfo[NodeCount];
  59
  60   unsigned i = 0;
  61   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
  62        E = DAG.allnodes_end(); I != E; ++I, ++i) {
  63     // Fast reference to node schedule info
  64     NodeInfo* NI = &Info[i];
  65     // Set up map
  66     Map[I] = NI;
  67     // Set node
  68     NI->Node = I;
  69     // Set pending visit count
  70     NI->setPending(I->use_size());
  71   }
  72 }
  73
  74 /// IdentifyGroups - Put flagged nodes into groups.
  75 ///
  76 void ScheduleDAG::IdentifyGroups() {
  77   for (unsigned i = 0, N = NodeCount; i < N; i++) {
  78     NodeInfo* NI = &Info[i];
  79     SDNode *Node = NI->Node;
  80
  81     // For each operand (in reverse to only look at flags)
  82     for (unsigned N = Node->getNumOperands(); 0 < N--;) {
  83       // Get operand
  84       SDOperand Op = Node->getOperand(N);
  85       // No more flags to walk
  86       if (Op.getValueType() != MVT::Flag) break;
  87       // Add to node group
  88       NodeGroup::Add(getNI(Op.Val), NI);
  89       // Let everyone else know
  90       HasGroups = true;
  91     }
  92   }
  93 }
  94
  95 static unsigned CreateVirtualRegisters(MachineInstr *MI,
  96                                        unsigned NumResults,
  97                                        SSARegMap *RegMap,
  98                                        const TargetInstrDescriptor &II) {
  99   // Create the result registers for this node and add the result regs to
 100   // the machine instruction.
 101   const TargetOperandInfo *OpInfo = II.OpInfo;
 102   unsigned ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
 103   MI->addRegOperand(ResultReg, MachineOperand::Def);
 104   for (unsigned i = 1; i != NumResults; ++i) {
 105     assert(OpInfo[i].RegClass && "Isn't a register operand!");
 106     MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[i].RegClass),
 107                       MachineOperand::Def);
 108   }
 109   return ResultReg;
 110 }
 111
 112 /// EmitNode - Generate machine code for an node and needed dependencies.
 113 ///
 114 void ScheduleDAG::EmitNode(NodeInfo *NI) {
 115   unsigned VRBase = 0;                 // First virtual register for node
 116   SDNode *Node = NI->Node;
 117
 118   // If machine instruction
 119   if (Node->isTargetOpcode()) {
 120     unsigned Opc = Node->getTargetOpcode();
 121     const TargetInstrDescriptor &II = TII->get(Opc);
 122
 123     unsigned NumResults = CountResults(Node);
 124     unsigned NodeOperands = CountOperands(Node);
 125     unsigned NumMIOperands = NodeOperands + NumResults;
 126 #ifndef NDEBUG
 127     assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
 128            "#operands for dag node doesn't match .td file!");
 129 #endif
 130
 131     // Create the new machine instruction.
 132     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
 133
 134     // Add result register values for things that are defined by this
 135     // instruction.
 136
 137     // If the node is only used by a CopyToReg and the dest reg is a vreg, use
 138     // the CopyToReg'd destination register instead of creating a new vreg.
 139     if (NumResults == 1) {
 140       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 141            UI != E; ++UI) {
 142         SDNode *Use = *UI;
 143         if (Use->getOpcode() == ISD::CopyToReg &&
 144             Use->getOperand(2).Val == Node) {
 145           unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
 146           if (MRegisterInfo::isVirtualRegister(Reg)) {
 147             VRBase = Reg;
 148             MI->addRegOperand(Reg, MachineOperand::Def);
 149             break;
 150           }
 151         }
 152       }
 153     }
 154
 155     // Otherwise, create new virtual registers.
 156     if (NumResults && VRBase == 0)
 157       VRBase = CreateVirtualRegisters(MI, NumResults, RegMap, II);
 158
 159     // Emit all of the actual operands of this instruction, adding them to the
 160     // instruction as appropriate.
 161     for (unsigned i = 0; i != NodeOperands; ++i) {
 162       if (Node->getOperand(i).isTargetOpcode()) {
 163         // Note that this case is redundant with the final else block, but we
 164         // include it because it is the most common and it makes the logic
 165         // simpler here.
 166         assert(Node->getOperand(i).getValueType() != MVT::Other &&
 167                Node->getOperand(i).getValueType() != MVT::Flag &&
 168                "Chain and flag operands should occur at end of operand list!");
 169
 170         // Get/emit the operand.
 171         unsigned VReg = getVR(Node->getOperand(i));
 172         MI->addRegOperand(VReg, MachineOperand::Use);
 173
 174         // Verify that it is right.
 175         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
 176         assert(II.OpInfo[i+NumResults].RegClass &&
 177                "Don't have operand info for this instruction!");
 178         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
 179                "Register class of operand and regclass of use don't agree!");
 180       } else if (ConstantSDNode *C =
 181                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
 182         MI->addZeroExtImm64Operand(C->getValue());
 183       } else if (RegisterSDNode*R =
 184                  dyn_cast<RegisterSDNode>(Node->getOperand(i))) {
 185         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 186       } else if (GlobalAddressSDNode *TGA =
 187                        dyn_cast<GlobalAddressSDNode>(Node->getOperand(i))) {
 188         MI->addGlobalAddressOperand(TGA->getGlobal(), false, TGA->getOffset());
 189       } else if (BasicBlockSDNode *BB =
 190                        dyn_cast<BasicBlockSDNode>(Node->getOperand(i))) {
 191         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
 192       } else if (FrameIndexSDNode *FI =
 193                        dyn_cast<FrameIndexSDNode>(Node->getOperand(i))) {
 194         MI->addFrameIndexOperand(FI->getIndex());
 195       } else if (ConstantPoolSDNode *CP =
 196                     dyn_cast<ConstantPoolSDNode>(Node->getOperand(i))) {
 197         unsigned Idx = ConstPool->getConstantPoolIndex(CP->get(),
 198                                                        CP->getAlignment());
 199         MI->addConstantPoolIndexOperand(Idx);
 200       } else if (ExternalSymbolSDNode *ES =
 201                  dyn_cast<ExternalSymbolSDNode>(Node->getOperand(i))) {
 202         MI->addExternalSymbolOperand(ES->getSymbol(), false);
 203       } else {
 204         assert(Node->getOperand(i).getValueType() != MVT::Other &&
 205                Node->getOperand(i).getValueType() != MVT::Flag &&
 206                "Chain and flag operands should occur at end of operand list!");
 207         unsigned VReg = getVR(Node->getOperand(i));
 208         MI->addRegOperand(VReg, MachineOperand::Use);
 209
 210         // Verify that it is right.
 211         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
 212         assert(II.OpInfo[i+NumResults].RegClass &&
 213                "Don't have operand info for this instruction!");
 214         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
 215                "Register class of operand and regclass of use don't agree!");
 216       }
 217     }
 218
 219     // Now that we have emitted all operands, emit this instruction itself.
 220     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
 221       BB->insert(BB->end(), MI);
 222     } else {
 223       // Insert this instruction into the end of the basic block, potentially
 224       // taking some custom action.
 225       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
 226     }
 227   } else {
 228     switch (Node->getOpcode()) {
 229     default:
 230       Node->dump();
 231       assert(0 && "This target-independent node should have been selected!");
 232     case ISD::EntryToken: // fall thru
 233     case ISD::TokenFactor:
 234       break;
 235     case ISD::CopyToReg: {
 236       unsigned InReg = getVR(Node->getOperand(2));
 237       unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 238       if (InReg != DestReg)   // Coallesced away the copy?
 239         MRI->copyRegToReg(*BB, BB->end(), DestReg, InReg,
 240                           RegMap->getRegClass(InReg));
 241       break;
 242     }
 243     case ISD::CopyFromReg: {
 244       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 245       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
 246         VRBase = SrcReg;  // Just use the input register directly!
 247         break;
 248       }
 249
 250       // If the node is only used by a CopyToReg and the dest reg is a vreg, use
 251       // the CopyToReg'd destination register instead of creating a new vreg.
 252       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 253            UI != E; ++UI) {
 254         SDNode *Use = *UI;
 255         if (Use->getOpcode() == ISD::CopyToReg &&
 256             Use->getOperand(2).Val == Node) {
 257           unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
 258           if (MRegisterInfo::isVirtualRegister(DestReg)) {
 259             VRBase = DestReg;
 260             break;
 261           }
 262         }
 263       }
 264
 265       // Figure out the register class to create for the destreg.
 266       const TargetRegisterClass *TRC = 0;
 267       if (VRBase) {
 268         TRC = RegMap->getRegClass(VRBase);
 269       } else {
 270
 271         // Pick the register class of the right type that contains this physreg.
 272         for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
 273              E = MRI->regclass_end(); I != E; ++I)
 274           if ((*I)->hasType(Node->getValueType(0)) &&
 275               (*I)->contains(SrcReg)) {
 276             TRC = *I;
 277             break;
 278           }
 279         assert(TRC && "Couldn't find register class for reg copy!");
 280
 281         // Create the reg, emit the copy.
 282         VRBase = RegMap->createVirtualRegister(TRC);
 283       }
 284       MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
 285       break;
 286     }
 287     case ISD::INLINEASM: {
 288       unsigned NumOps = Node->getNumOperands();
 289       if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
 290         --NumOps;  // Ignore the flag operand.
 291
 292       // Create the inline asm machine instruction.
 293       MachineInstr *MI =
 294         new MachineInstr(BB, TargetInstrInfo::INLINEASM, (NumOps-2)/2+1);
 295
 296       // Add the asm string as an external symbol operand.
 297       const char *AsmStr =
 298         cast<ExternalSymbolSDNode>(Node->getOperand(1))->getSymbol();
 299       MI->addExternalSymbolOperand(AsmStr, false);
 300
 301       // Add all of the operand registers to the instruction.
 302       for (unsigned i = 2; i != NumOps; i += 2) {
 303         unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
 304         unsigned Flags =cast<ConstantSDNode>(Node->getOperand(i+1))->getValue();
 305         MachineOperand::UseType UseTy;
 306         switch (Flags) {
 307         default: assert(0 && "Bad flags!");
 308         case 1: UseTy = MachineOperand::Use; break;
 309         case 2: UseTy = MachineOperand::Def; break;
 310         case 3: UseTy = MachineOperand::UseAndDef; break;
 311         }
 312         MI->addMachineRegOperand(Reg, UseTy);
 313       }
 314       break;
 315     }
 316     }
 317   }
 318
 319   assert(NI->VRBase == 0 && "Node emitted out of order - early");
 320   NI->VRBase = VRBase;
 321 }
 322
 323 /// EmitAll - Emit all nodes in schedule sorted order.
 324 ///
 325 void ScheduleDAG::EmitAll() {
 326   // For each node in the ordering
 327   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 328     // Get the scheduling info
 329     NodeInfo *NI = Ordering[i];
 330     if (NI->isInGroup()) {
 331       NodeGroupIterator NGI(Ordering[i]);
 332       while (NodeInfo *NI = NGI.next()) EmitNode(NI);
 333     } else {
 334       EmitNode(NI);
 335     }
 336   }
 337 }
 338
 339 /// isFlagDefiner - Returns true if the node defines a flag result.
 340 static bool isFlagDefiner(SDNode *A) {
 341   unsigned N = A->getNumValues();
 342   return N && A->getValueType(N - 1) == MVT::Flag;
 343 }
 344
 345 /// isFlagUser - Returns true if the node uses a flag result.
 346 ///
 347 static bool isFlagUser(SDNode *A) {
 348   unsigned N = A->getNumOperands();
 349   return N && A->getOperand(N - 1).getValueType() == MVT::Flag;
 350 }
 351
 352 /// printNI - Print node info.
 353 ///
 354 void ScheduleDAG::printNI(std::ostream &O, NodeInfo *NI) const {
 355 #ifndef NDEBUG
 356   SDNode *Node = NI->Node;
 357   O << " "
 358     << std::hex << Node << std::dec
 359     << ", Lat=" << NI->Latency
 360     << ", Slot=" << NI->Slot
 361     << ", ARITY=(" << Node->getNumOperands() << ","
 362                    << Node->getNumValues() << ")"
 363     << " " << Node->getOperationName(&DAG);
 364   if (isFlagDefiner(Node)) O << "<#";
 365   if (isFlagUser(Node)) O << ">#";
 366 #endif
 367 }
 368
 369 /// printChanges - Hilight changes in order caused by scheduling.
 370 ///
 371 void ScheduleDAG::printChanges(unsigned Index) const {
 372 #ifndef NDEBUG
 373   // Get the ordered node count
 374   unsigned N = Ordering.size();
 375   // Determine if any changes
 376   unsigned i = 0;
 377   for (; i < N; i++) {
 378     NodeInfo *NI = Ordering[i];
 379     if (NI->Preorder != i) break;
 380   }
 381
 382   if (i < N) {
 383     std::cerr << Index << ". New Ordering\n";
 384
 385     for (i = 0; i < N; i++) {
 386       NodeInfo *NI = Ordering[i];
 387       std::cerr << "  " << NI->Preorder << ". ";
 388       printNI(std::cerr, NI);
 389       std::cerr << "\n";
 390       if (NI->isGroupDominator()) {
 391         NodeGroup *Group = NI->Group;
 392         for (NIIterator NII = Group->group_begin(), E = Group->group_end();
 393              NII != E; NII++) {
 394           std::cerr << "          ";
 395           printNI(std::cerr, *NII);
 396           std::cerr << "\n";
 397         }
 398       }
 399     }
 400   } else {
 401     std::cerr << Index << ". No Changes\n";
 402   }
 403 #endif
 404 }
 405
 406 /// print - Print ordering to specified output stream.
 407 ///
 408 void ScheduleDAG::print(std::ostream &O) const {
 409 #ifndef NDEBUG
 410   using namespace std;
 411   O << "Ordering\n";
 412   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 413     NodeInfo *NI = Ordering[i];
 414     printNI(O, NI);
 415     O << "\n";
 416     if (NI->isGroupDominator()) {
 417       NodeGroup *Group = NI->Group;
 418       for (NIIterator NII = Group->group_begin(), E = Group->group_end();
 419            NII != E; NII++) {
 420         O << "    ";
 421         printNI(O, *NII);
 422         O << "\n";
 423       }
 424     }
 425   }
 426 #endif
 427 }
 428
 429 void ScheduleDAG::dump(const char *tag) const {
 430   std::cerr << tag; dump();
 431 }
 432
 433 void ScheduleDAG::dump() const {
 434   print(std::cerr);
 435 }
 436
 437 /// Run - perform scheduling.
 438 ///
 439 MachineBasicBlock *ScheduleDAG::Run() {
 440   TII = TM.getInstrInfo();
 441   MRI = TM.getRegisterInfo();
 442   RegMap = BB->getParent()->getSSARegMap();
 443   ConstPool = BB->getParent()->getConstantPool();
 444
 445   // Number the nodes
 446   NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end());
 447   // Set up minimum info for scheduling
 448   PrepareNodeInfo();
 449   // Construct node groups for flagged nodes
 450   IdentifyGroups();
 451
 452   Schedule();
 453   return BB;
 454 }
 455
 456
 457 /// CountInternalUses - Returns the number of edges between the two nodes.
 458 ///
 459 static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U) {
 460   unsigned N = 0;
 461   for (unsigned M = U->Node->getNumOperands(); 0 < M--;) {
 462     SDOperand Op = U->Node->getOperand(M);
 463     if (Op.Val == D->Node) N++;
 464   }
 465
 466   return N;
 467 }
 468
 469 //===----------------------------------------------------------------------===//
 470 /// Add - Adds a definer and user pair to a node group.
 471 ///
 472 void NodeGroup::Add(NodeInfo *D, NodeInfo *U) {
 473   // Get current groups
 474   NodeGroup *DGroup = D->Group;
 475   NodeGroup *UGroup = U->Group;
 476   // If both are members of groups
 477   if (DGroup && UGroup) {
 478     // There may have been another edge connecting
 479     if (DGroup == UGroup) return;
 480     // Add the pending users count
 481     DGroup->addPending(UGroup->getPending());
 482     // For each member of the users group
 483     NodeGroupIterator UNGI(U);
 484     while (NodeInfo *UNI = UNGI.next() ) {
 485       // Change the group
 486       UNI->Group = DGroup;
 487       // For each member of the definers group
 488       NodeGroupIterator DNGI(D);
 489       while (NodeInfo *DNI = DNGI.next() ) {
 490         // Remove internal edges
 491         DGroup->addPending(-CountInternalUses(DNI, UNI));
 492       }
 493     }
 494     // Merge the two lists
 495     DGroup->group_insert(DGroup->group_end(),
 496                          UGroup->group_begin(), UGroup->group_end());
 497   } else if (DGroup) {
 498     // Make user member of definers group
 499     U->Group = DGroup;
 500     // Add users uses to definers group pending
 501     DGroup->addPending(U->Node->use_size());
 502     // For each member of the definers group
 503     NodeGroupIterator DNGI(D);
 504     while (NodeInfo *DNI = DNGI.next() ) {
 505       // Remove internal edges
 506       DGroup->addPending(-CountInternalUses(DNI, U));
 507     }
 508     DGroup->group_push_back(U);
 509   } else if (UGroup) {
 510     // Make definer member of users group
 511     D->Group = UGroup;
 512     // Add definers uses to users group pending
 513     UGroup->addPending(D->Node->use_size());
 514     // For each member of the users group
 515     NodeGroupIterator UNGI(U);
 516     while (NodeInfo *UNI = UNGI.next() ) {
 517       // Remove internal edges
 518       UGroup->addPending(-CountInternalUses(D, UNI));
 519     }
 520     UGroup->group_insert(UGroup->group_begin(), D);
 521   } else {
 522     D->Group = U->Group = DGroup = new NodeGroup();
 523     DGroup->addPending(D->Node->use_size() + U->Node->use_size() -
 524                        CountInternalUses(D, U));
 525     DGroup->group_push_back(D);
 526     DGroup->group_push_back(U);
 527   }
 528 }