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