lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp

   1 //===---- ScheduleDAGEmit.cpp - Emit routines for 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 Emit routines for the ScheduleDAG class, which creates
  11 // MachineInstrs according to the computed schedule.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "pre-RA-sched"
  16 #include "ScheduleDAGSDNodes.h"
  17 #include "llvm/CodeGen/MachineConstantPool.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/MachineInstrBuilder.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/Target/TargetData.h"
  22 #include "llvm/Target/TargetMachine.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetLowering.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/MathExtras.h"
  30 using namespace llvm;
  31
  32 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
  33 /// implicit physical register output.
  34 void ScheduleDAGSDNodes::
  35 EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, bool IsCloned,
  36                 unsigned SrcReg, DenseMap<SDValue, unsigned> &VRBaseMap) {
  37   unsigned VRBase = 0;
  38   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
  39     // Just use the input register directly!
  40     SDValue Op(Node, ResNo);
  41     if (IsClone)
  42       VRBaseMap.erase(Op);
  43     bool isNew = VRBaseMap.insert(std::make_pair(Op, SrcReg)).second;
  44     isNew = isNew; // Silence compiler warning.
  45     assert(isNew && "Node emitted out of order - early");
  46     return;
  47   }
  48
  49   // If the node is only used by a CopyToReg and the dest reg is a vreg, use
  50   // the CopyToReg'd destination register instead of creating a new vreg.
  51   bool MatchReg = true;
  52   const TargetRegisterClass *UseRC = NULL;
  53   if (!IsClone && !IsCloned)
  54     for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
  55          UI != E; ++UI) {
  56       SDNode *User = *UI;
  57       bool Match = true;
  58       if (User->getOpcode() == ISD::CopyToReg &&
  59           User->getOperand(2).getNode() == Node &&
  60           User->getOperand(2).getResNo() == ResNo) {
  61         unsigned DestReg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
  62         if (TargetRegisterInfo::isVirtualRegister(DestReg)) {
  63           VRBase = DestReg;
  64           Match = false;
  65         } else if (DestReg != SrcReg)
  66           Match = false;
  67       } else {
  68         for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
  69           SDValue Op = User->getOperand(i);
  70           if (Op.getNode() != Node || Op.getResNo() != ResNo)
  71             continue;
  72           MVT VT = Node->getValueType(Op.getResNo());
  73           if (VT == MVT::Other || VT == MVT::Flag)
  74             continue;
  75           Match = false;
  76           if (User->isMachineOpcode()) {
  77             const TargetInstrDesc &II = TII->get(User->getMachineOpcode());
  78             const TargetRegisterClass *RC =
  79               getInstrOperandRegClass(TRI, II, i+II.getNumDefs());
  80             if (!UseRC)
  81               UseRC = RC;
  82             else if (RC) {
  83               if (UseRC->hasSuperClass(RC))
  84                 UseRC = RC;
  85               else
  86                 assert((UseRC == RC || RC->hasSuperClass(UseRC)) &&
  87                        "Multiple uses expecting different register classes!");
  88             }
  89           }
  90         }
  91       }
  92       MatchReg &= Match;
  93       if (VRBase)
  94         break;
  95     }
  96
  97   MVT VT = Node->getValueType(ResNo);
  98   const TargetRegisterClass *SrcRC = 0, *DstRC = 0;
  99   SrcRC = TRI->getPhysicalRegisterRegClass(SrcReg, VT);
 100
 101   // Figure out the register class to create for the destreg.
 102   if (VRBase) {
 103     DstRC = MRI.getRegClass(VRBase);
 104   } else if (UseRC) {
 105     assert(UseRC->hasType(VT) && "Incompatible phys register def and uses!");
 106     DstRC = UseRC;
 107   } else {
 108     DstRC = TLI->getRegClassFor(VT);
 109   }
 110
 111   // If all uses are reading from the src physical register and copying the
 112   // register is either impossible or very expensive, then don't create a copy.
 113   if (MatchReg && SrcRC->getCopyCost() < 0) {
 114     VRBase = SrcReg;
 115   } else {
 116     // Create the reg, emit the copy.
 117     VRBase = MRI.createVirtualRegister(DstRC);
 118     bool Emitted = TII->copyRegToReg(*BB, InsertPos, VRBase, SrcReg,
 119                                      DstRC, SrcRC);
 120
 121     assert(Emitted && "Unable to issue a copy instruction!\n");
 122     (void) Emitted;
 123   }
 124
 125   SDValue Op(Node, ResNo);
 126   if (IsClone)
 127     VRBaseMap.erase(Op);
 128   bool isNew = VRBaseMap.insert(std::make_pair(Op, VRBase)).second;
 129   isNew = isNew; // Silence compiler warning.
 130   assert(isNew && "Node emitted out of order - early");
 131 }
 132
 133 /// getDstOfCopyToRegUse - If the only use of the specified result number of
 134 /// node is a CopyToReg, return its destination register. Return 0 otherwise.
 135 unsigned ScheduleDAGSDNodes::getDstOfOnlyCopyToRegUse(SDNode *Node,
 136                                                       unsigned ResNo) const {
 137   if (!Node->hasOneUse())
 138     return 0;
 139
 140   SDNode *User = *Node->use_begin();
 141   if (User->getOpcode() == ISD::CopyToReg &&
 142       User->getOperand(2).getNode() == Node &&
 143       User->getOperand(2).getResNo() == ResNo) {
 144     unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
 145     if (TargetRegisterInfo::isVirtualRegister(Reg))
 146       return Reg;
 147   }
 148   return 0;
 149 }
 150
 151 void ScheduleDAGSDNodes::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 152                                        const TargetInstrDesc &II,
 153                                        bool IsClone, bool IsCloned,
 154                                        DenseMap<SDValue, unsigned> &VRBaseMap) {
 155   assert(Node->getMachineOpcode() != TargetInstrInfo::IMPLICIT_DEF &&
 156          "IMPLICIT_DEF should have been handled as a special case elsewhere!");
 157
 158   for (unsigned i = 0; i < II.getNumDefs(); ++i) {
 159     // If the specific node value is only used by a CopyToReg and the dest reg
 160     // is a vreg in the same register class, use the CopyToReg'd destination
 161     // register instead of creating a new vreg.
 162     unsigned VRBase = 0;
 163     const TargetRegisterClass *RC = getInstrOperandRegClass(TRI, II, i);
 164     if (II.OpInfo[i].isOptionalDef()) {
 165       // Optional def must be a physical register.
 166       unsigned NumResults = CountResults(Node);
 167       VRBase = cast<RegisterSDNode>(Node->getOperand(i-NumResults))->getReg();
 168       assert(TargetRegisterInfo::isPhysicalRegister(VRBase));
 169       MI->addOperand(MachineOperand::CreateReg(VRBase, true));
 170     }
 171
 172     if (!VRBase && !IsClone && !IsCloned)
 173       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 174            UI != E; ++UI) {
 175         SDNode *User = *UI;
 176         if (User->getOpcode() == ISD::CopyToReg &&
 177             User->getOperand(2).getNode() == Node &&
 178             User->getOperand(2).getResNo() == i) {
 179           unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
 180           if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 181             const TargetRegisterClass *RegRC = MRI.getRegClass(Reg);
 182             if (RegRC == RC) {
 183               VRBase = Reg;
 184               MI->addOperand(MachineOperand::CreateReg(Reg, true));
 185               break;
 186             }
 187           }
 188         }
 189       }
 190
 191     // Create the result registers for this node and add the result regs to
 192     // the machine instruction.
 193     if (VRBase == 0) {
 194       assert(RC && "Isn't a register operand!");
 195       VRBase = MRI.createVirtualRegister(RC);
 196       MI->addOperand(MachineOperand::CreateReg(VRBase, true));
 197     }
 198
 199     SDValue Op(Node, i);
 200     if (IsClone)
 201       VRBaseMap.erase(Op);
 202     bool isNew = VRBaseMap.insert(std::make_pair(Op, VRBase)).second;
 203     isNew = isNew; // Silence compiler warning.
 204     assert(isNew && "Node emitted out of order - early");
 205   }
 206 }
 207
 208 /// getVR - Return the virtual register corresponding to the specified result
 209 /// of the specified node.
 210 unsigned ScheduleDAGSDNodes::getVR(SDValue Op,
 211                                    DenseMap<SDValue, unsigned> &VRBaseMap) {
 212   if (Op.isMachineOpcode() &&
 213       Op.getMachineOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
 214     // Add an IMPLICIT_DEF instruction before every use.
 215     unsigned VReg = getDstOfOnlyCopyToRegUse(Op.getNode(), Op.getResNo());
 216     // IMPLICIT_DEF can produce any type of result so its TargetInstrDesc
 217     // does not include operand register class info.
 218     if (!VReg) {
 219       const TargetRegisterClass *RC = TLI->getRegClassFor(Op.getValueType());
 220       VReg = MRI.createVirtualRegister(RC);
 221     }
 222     BuildMI(BB, Op.getDebugLoc(), TII->get(TargetInstrInfo::IMPLICIT_DEF),VReg);
 223     return VReg;
 224   }
 225
 226   DenseMap<SDValue, unsigned>::iterator I = VRBaseMap.find(Op);
 227   assert(I != VRBaseMap.end() && "Node emitted out of order - late");
 228   return I->second;
 229 }
 230
 231
 232 /// AddRegisterOperand - Add the specified register as an operand to the
 233 /// specified machine instr. Insert register copies if the register is
 234 /// not in the required register class.
 235 void
 236 ScheduleDAGSDNodes::AddRegisterOperand(MachineInstr *MI, SDValue Op,
 237                                        unsigned IIOpNum,
 238                                        const TargetInstrDesc *II,
 239                                        DenseMap<SDValue, unsigned> &VRBaseMap) {
 240   assert(Op.getValueType() != MVT::Other &&
 241          Op.getValueType() != MVT::Flag &&
 242          "Chain and flag operands should occur at end of operand list!");
 243   // Get/emit the operand.
 244   unsigned VReg = getVR(Op, VRBaseMap);
 245   assert(TargetRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
 246
 247   const TargetInstrDesc &TID = MI->getDesc();
 248   bool isOptDef = IIOpNum < TID.getNumOperands() &&
 249     TID.OpInfo[IIOpNum].isOptionalDef();
 250
 251   // If the instruction requires a register in a different class, create
 252   // a new virtual register and copy the value into it.
 253   if (II) {
 254     const TargetRegisterClass *SrcRC =
 255       MRI.getRegClass(VReg);
 256     const TargetRegisterClass *DstRC =
 257       getInstrOperandRegClass(TRI, *II, IIOpNum);
 258     assert((DstRC || (TID.isVariadic() && IIOpNum >= TID.getNumOperands())) &&
 259            "Don't have operand info for this instruction!");
 260     if (DstRC && SrcRC != DstRC && !SrcRC->hasSuperClass(DstRC)) {
 261       unsigned NewVReg = MRI.createVirtualRegister(DstRC);
 262       bool Emitted = TII->copyRegToReg(*BB, InsertPos, NewVReg, VReg,
 263                                        DstRC, SrcRC);
 264       assert(Emitted && "Unable to issue a copy instruction!\n");
 265       (void) Emitted;
 266       VReg = NewVReg;
 267     }
 268   }
 269
 270   MI->addOperand(MachineOperand::CreateReg(VReg, isOptDef));
 271 }
 272
 273 /// AddOperand - Add the specified operand to the specified machine instr.  II
 274 /// specifies the instruction information for the node, and IIOpNum is the
 275 /// operand number (in the II) that we are adding. IIOpNum and II are used for
 276 /// assertions only.
 277 void ScheduleDAGSDNodes::AddOperand(MachineInstr *MI, SDValue Op,
 278                                     unsigned IIOpNum,
 279                                     const TargetInstrDesc *II,
 280                                     DenseMap<SDValue, unsigned> &VRBaseMap) {
 281   if (Op.isMachineOpcode()) {
 282     AddRegisterOperand(MI, Op, IIOpNum, II, VRBaseMap);
 283   } else if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
 284     MI->addOperand(MachineOperand::CreateImm(C->getZExtValue()));
 285   } else if (ConstantFPSDNode *F = dyn_cast<ConstantFPSDNode>(Op)) {
 286     const ConstantFP *CFP = F->getConstantFPValue();
 287     MI->addOperand(MachineOperand::CreateFPImm(CFP));
 288   } else if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op)) {
 289     MI->addOperand(MachineOperand::CreateReg(R->getReg(), false));
 290   } else if (GlobalAddressSDNode *TGA = dyn_cast<GlobalAddressSDNode>(Op)) {
 291     MI->addOperand(MachineOperand::CreateGA(TGA->getGlobal(), TGA->getOffset(),
 292                                             TGA->getTargetFlags()));
 293   } else if (BasicBlockSDNode *BBNode = dyn_cast<BasicBlockSDNode>(Op)) {
 294     MI->addOperand(MachineOperand::CreateMBB(BBNode->getBasicBlock()));
 295   } else if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Op)) {
 296     MI->addOperand(MachineOperand::CreateFI(FI->getIndex()));
 297   } else if (JumpTableSDNode *JT = dyn_cast<JumpTableSDNode>(Op)) {
 298     MI->addOperand(MachineOperand::CreateJTI(JT->getIndex(),
 299                                              JT->getTargetFlags()));
 300   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Op)) {
 301     int Offset = CP->getOffset();
 302     unsigned Align = CP->getAlignment();
 303     const Type *Type = CP->getType();
 304     // MachineConstantPool wants an explicit alignment.
 305     if (Align == 0) {
 306       Align = TM.getTargetData()->getPrefTypeAlignment(Type);
 307       if (Align == 0) {
 308         // Alignment of vector types.  FIXME!
 309         Align = TM.getTargetData()->getTypeAllocSize(Type);
 310       }
 311     }
 312
 313     unsigned Idx;
 314     if (CP->isMachineConstantPoolEntry())
 315       Idx = ConstPool->getConstantPoolIndex(CP->getMachineCPVal(), Align);
 316     else
 317       Idx = ConstPool->getConstantPoolIndex(CP->getConstVal(), Align);
 318     MI->addOperand(MachineOperand::CreateCPI(Idx, Offset,
 319                                              CP->getTargetFlags()));
 320   } else if (ExternalSymbolSDNode *ES = dyn_cast<ExternalSymbolSDNode>(Op)) {
 321     MI->addOperand(MachineOperand::CreateES(ES->getSymbol(), 0,
 322                                             ES->getTargetFlags()));
 323   } else {
 324     assert(Op.getValueType() != MVT::Other &&
 325            Op.getValueType() != MVT::Flag &&
 326            "Chain and flag operands should occur at end of operand list!");
 327     AddRegisterOperand(MI, Op, IIOpNum, II, VRBaseMap);
 328   }
 329 }
 330
 331 /// getSuperRegisterRegClass - Returns the register class of a superreg A whose
 332 /// "SubIdx"'th sub-register class is the specified register class and whose
 333 /// type matches the specified type.
 334 static const TargetRegisterClass*
 335 getSuperRegisterRegClass(const TargetRegisterClass *TRC,
 336                          unsigned SubIdx, MVT VT) {
 337   // Pick the register class of the superegister for this type
 338   for (TargetRegisterInfo::regclass_iterator I = TRC->superregclasses_begin(),
 339          E = TRC->superregclasses_end(); I != E; ++I)
 340     if ((*I)->hasType(VT) && (*I)->getSubRegisterRegClass(SubIdx) == TRC)
 341       return *I;
 342   assert(false && "Couldn't find the register class");
 343   return 0;
 344 }
 345
 346 /// EmitSubregNode - Generate machine code for subreg nodes.
 347 ///
 348 void ScheduleDAGSDNodes::EmitSubregNode(SDNode *Node,
 349                                         DenseMap<SDValue, unsigned> &VRBaseMap){
 350   unsigned VRBase = 0;
 351   unsigned Opc = Node->getMachineOpcode();
 352
 353   // If the node is only used by a CopyToReg and the dest reg is a vreg, use
 354   // the CopyToReg'd destination register instead of creating a new vreg.
 355   for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 356        UI != E; ++UI) {
 357     SDNode *User = *UI;
 358     if (User->getOpcode() == ISD::CopyToReg &&
 359         User->getOperand(2).getNode() == Node) {
 360       unsigned DestReg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
 361       if (TargetRegisterInfo::isVirtualRegister(DestReg)) {
 362         VRBase = DestReg;
 363         break;
 364       }
 365     }
 366   }
 367
 368   if (Opc == TargetInstrInfo::EXTRACT_SUBREG) {
 369     unsigned SubIdx = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
 370
 371     // Create the extract_subreg machine instruction.
 372     MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(),
 373                                TII->get(TargetInstrInfo::EXTRACT_SUBREG));
 374
 375     // Figure out the register class to create for the destreg.
 376     unsigned VReg = getVR(Node->getOperand(0), VRBaseMap);
 377     const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
 378     const TargetRegisterClass *SRC = TRC->getSubRegisterRegClass(SubIdx);
 379     assert(SRC && "Invalid subregister index in EXTRACT_SUBREG");
 380
 381     // Figure out the register class to create for the destreg.
 382     // Note that if we're going to directly use an existing register,
 383     // it must be precisely the required class, and not a subclass
 384     // thereof.
 385     if (VRBase == 0 || SRC != MRI.getRegClass(VRBase)) {
 386       // Create the reg
 387       assert(SRC && "Couldn't find source register class");
 388       VRBase = MRI.createVirtualRegister(SRC);
 389     }
 390
 391     // Add def, source, and subreg index
 392     MI->addOperand(MachineOperand::CreateReg(VRBase, true));
 393     AddOperand(MI, Node->getOperand(0), 0, 0, VRBaseMap);
 394     MI->addOperand(MachineOperand::CreateImm(SubIdx));
 395     BB->insert(InsertPos, MI);
 396   } else if (Opc == TargetInstrInfo::INSERT_SUBREG ||
 397              Opc == TargetInstrInfo::SUBREG_TO_REG) {
 398     SDValue N0 = Node->getOperand(0);
 399     SDValue N1 = Node->getOperand(1);
 400     SDValue N2 = Node->getOperand(2);
 401     unsigned SubReg = getVR(N1, VRBaseMap);
 402     unsigned SubIdx = cast<ConstantSDNode>(N2)->getZExtValue();
 403     const TargetRegisterClass *TRC = MRI.getRegClass(SubReg);
 404     const TargetRegisterClass *SRC =
 405       getSuperRegisterRegClass(TRC, SubIdx,
 406                                Node->getValueType(0));
 407
 408     // Figure out the register class to create for the destreg.
 409     // Note that if we're going to directly use an existing register,
 410     // it must be precisely the required class, and not a subclass
 411     // thereof.
 412     if (VRBase == 0 || SRC != MRI.getRegClass(VRBase)) {
 413       // Create the reg
 414       assert(SRC && "Couldn't find source register class");
 415       VRBase = MRI.createVirtualRegister(SRC);
 416     }
 417
 418     // Create the insert_subreg or subreg_to_reg machine instruction.
 419     MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(), TII->get(Opc));
 420     MI->addOperand(MachineOperand::CreateReg(VRBase, true));
 421
 422     // If creating a subreg_to_reg, then the first input operand
 423     // is an implicit value immediate, otherwise it's a register
 424     if (Opc == TargetInstrInfo::SUBREG_TO_REG) {
 425       const ConstantSDNode *SD = cast<ConstantSDNode>(N0);
 426       MI->addOperand(MachineOperand::CreateImm(SD->getZExtValue()));
 427     } else
 428       AddOperand(MI, N0, 0, 0, VRBaseMap);
 429     // Add the subregster being inserted
 430     AddOperand(MI, N1, 0, 0, VRBaseMap);
 431     MI->addOperand(MachineOperand::CreateImm(SubIdx));
 432     BB->insert(InsertPos, MI);
 433   } else
 434     LLVM_UNREACHABLE("Node is not insert_subreg, extract_subreg, or subreg_to_reg");
 435
 436   SDValue Op(Node, 0);
 437   bool isNew = VRBaseMap.insert(std::make_pair(Op, VRBase)).second;
 438   isNew = isNew; // Silence compiler warning.
 439   assert(isNew && "Node emitted out of order - early");
 440 }
 441
 442 /// EmitCopyToRegClassNode - Generate machine code for COPY_TO_REGCLASS nodes.
 443 /// COPY_TO_REGCLASS is just a normal copy, except that the destination
 444 /// register is constrained to be in a particular register class.
 445 ///
 446 void
 447 ScheduleDAGSDNodes::EmitCopyToRegClassNode(SDNode *Node,
 448                                        DenseMap<SDValue, unsigned> &VRBaseMap) {
 449   unsigned VReg = getVR(Node->getOperand(0), VRBaseMap);
 450   const TargetRegisterClass *SrcRC = MRI.getRegClass(VReg);
 451
 452   unsigned DstRCIdx = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
 453   const TargetRegisterClass *DstRC = TRI->getRegClass(DstRCIdx);
 454
 455   // Create the new VReg in the destination class and emit a copy.
 456   unsigned NewVReg = MRI.createVirtualRegister(DstRC);
 457   bool Emitted = TII->copyRegToReg(*BB, InsertPos, NewVReg, VReg,
 458                                    DstRC, SrcRC);
 459   assert(Emitted &&
 460          "Unable to issue a copy instruction for a COPY_TO_REGCLASS node!\n");
 461   (void) Emitted;
 462
 463   SDValue Op(Node, 0);
 464   bool isNew = VRBaseMap.insert(std::make_pair(Op, NewVReg)).second;
 465   isNew = isNew; // Silence compiler warning.
 466   assert(isNew && "Node emitted out of order - early");
 467 }
 468
 469 /// EmitNode - Generate machine code for an node and needed dependencies.
 470 ///
 471 void ScheduleDAGSDNodes::EmitNode(SDNode *Node, bool IsClone, bool IsCloned,
 472                                   DenseMap<SDValue, unsigned> &VRBaseMap) {
 473   // If machine instruction
 474   if (Node->isMachineOpcode()) {
 475     unsigned Opc = Node->getMachineOpcode();
 476
 477     // Handle subreg insert/extract specially
 478     if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
 479         Opc == TargetInstrInfo::INSERT_SUBREG ||
 480         Opc == TargetInstrInfo::SUBREG_TO_REG) {
 481       EmitSubregNode(Node, VRBaseMap);
 482       return;
 483     }
 484
 485     // Handle COPY_TO_REGCLASS specially.
 486     if (Opc == TargetInstrInfo::COPY_TO_REGCLASS) {
 487       EmitCopyToRegClassNode(Node, VRBaseMap);
 488       return;
 489     }
 490
 491     if (Opc == TargetInstrInfo::IMPLICIT_DEF)
 492       // We want a unique VR for each IMPLICIT_DEF use.
 493       return;
 494
 495     const TargetInstrDesc &II = TII->get(Opc);
 496     unsigned NumResults = CountResults(Node);
 497     unsigned NodeOperands = CountOperands(Node);
 498     unsigned MemOperandsEnd = ComputeMemOperandsEnd(Node);
 499     bool HasPhysRegOuts = (NumResults > II.getNumDefs()) &&
 500                           II.getImplicitDefs() != 0;
 501 #ifndef NDEBUG
 502     unsigned NumMIOperands = NodeOperands + NumResults;
 503     assert((II.getNumOperands() == NumMIOperands ||
 504             HasPhysRegOuts || II.isVariadic()) &&
 505            "#operands for dag node doesn't match .td file!");
 506 #endif
 507
 508     // Create the new machine instruction.
 509     MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(), II);
 510
 511     // Add result register values for things that are defined by this
 512     // instruction.
 513     if (NumResults)
 514       CreateVirtualRegisters(Node, MI, II, IsClone, IsCloned, VRBaseMap);
 515
 516     // Emit all of the actual operands of this instruction, adding them to the
 517     // instruction as appropriate.
 518     bool HasOptPRefs = II.getNumDefs() > NumResults;
 519     assert((!HasOptPRefs || !HasPhysRegOuts) &&
 520            "Unable to cope with optional defs and phys regs defs!");
 521     unsigned NumSkip = HasOptPRefs ? II.getNumDefs() - NumResults : 0;
 522     for (unsigned i = NumSkip; i != NodeOperands; ++i)
 523       AddOperand(MI, Node->getOperand(i), i-NumSkip+II.getNumDefs(), &II,
 524                  VRBaseMap);
 525
 526     // Emit all of the memory operands of this instruction
 527     for (unsigned i = NodeOperands; i != MemOperandsEnd; ++i)
 528       AddMemOperand(MI,cast<MemOperandSDNode>(Node->getOperand(i+NumSkip))->MO);
 529
 530     if (II.usesCustomDAGSchedInsertionHook()) {
 531       // Insert this instruction into the basic block using a target
 532       // specific inserter which may returns a new basic block.
 533       BB = TLI->EmitInstrWithCustomInserter(MI, BB);
 534       InsertPos = BB->end();
 535     } else {
 536       BB->insert(InsertPos, MI);
 537     }
 538
 539     // Additional results must be an physical register def.
 540     if (HasPhysRegOuts) {
 541       for (unsigned i = II.getNumDefs(); i < NumResults; ++i) {
 542         unsigned Reg = II.getImplicitDefs()[i - II.getNumDefs()];
 543         if (Node->hasAnyUseOfValue(i))
 544           EmitCopyFromReg(Node, i, IsClone, IsCloned, Reg, VRBaseMap);
 545       }
 546     }
 547     return;
 548   }
 549
 550   switch (Node->getOpcode()) {
 551   default:
 552 #ifndef NDEBUG
 553     Node->dump(DAG);
 554 #endif
 555     LLVM_UNREACHABLE("This target-independent node should have been selected!");
 556     break;
 557   case ISD::EntryToken:
 558     LLVM_UNREACHABLE("EntryToken should have been excluded from the schedule!");
 559     break;
 560   case ISD::TokenFactor: // fall thru
 561     break;
 562   case ISD::CopyToReg: {
 563     unsigned SrcReg;
 564     SDValue SrcVal = Node->getOperand(2);
 565     if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(SrcVal))
 566       SrcReg = R->getReg();
 567     else
 568       SrcReg = getVR(SrcVal, VRBaseMap);
 569
 570     unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 571     if (SrcReg == DestReg) // Coalesced away the copy? Ignore.
 572       break;
 573
 574     const TargetRegisterClass *SrcTRC = 0, *DstTRC = 0;
 575     // Get the register classes of the src/dst.
 576     if (TargetRegisterInfo::isVirtualRegister(SrcReg))
 577       SrcTRC = MRI.getRegClass(SrcReg);
 578     else
 579       SrcTRC = TRI->getPhysicalRegisterRegClass(SrcReg,SrcVal.getValueType());
 580
 581     if (TargetRegisterInfo::isVirtualRegister(DestReg))
 582       DstTRC = MRI.getRegClass(DestReg);
 583     else
 584       DstTRC = TRI->getPhysicalRegisterRegClass(DestReg,
 585                                             Node->getOperand(1).getValueType());
 586
 587     bool Emitted = TII->copyRegToReg(*BB, InsertPos, DestReg, SrcReg,
 588                                      DstTRC, SrcTRC);
 589     assert(Emitted && "Unable to issue a copy instruction!\n");
 590     (void) Emitted;
 591     break;
 592   }
 593   case ISD::CopyFromReg: {
 594     unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 595     EmitCopyFromReg(Node, 0, IsClone, IsCloned, SrcReg, VRBaseMap);
 596     break;
 597   }
 598   case ISD::INLINEASM: {
 599     unsigned NumOps = Node->getNumOperands();
 600     if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
 601       --NumOps;  // Ignore the flag operand.
 602
 603     // Create the inline asm machine instruction.
 604     MachineInstr *MI = BuildMI(MF, Node->getDebugLoc(),
 605                                TII->get(TargetInstrInfo::INLINEASM));
 606
 607     // Add the asm string as an external symbol operand.
 608     const char *AsmStr =
 609       cast<ExternalSymbolSDNode>(Node->getOperand(1))->getSymbol();
 610     MI->addOperand(MachineOperand::CreateES(AsmStr));
 611
 612     // Add all of the operand registers to the instruction.
 613     for (unsigned i = 2; i != NumOps;) {
 614       unsigned Flags =
 615         cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
 616       unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
 617
 618       MI->addOperand(MachineOperand::CreateImm(Flags));
 619       ++i;  // Skip the ID value.
 620
 621       switch (Flags & 7) {
 622       default: LLVM_UNREACHABLE("Bad flags!");
 623       case 2:   // Def of register.
 624         for (; NumVals; --NumVals, ++i) {
 625           unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
 626           MI->addOperand(MachineOperand::CreateReg(Reg, true));
 627         }
 628         break;
 629       case 6:   // Def of earlyclobber register.
 630         for (; NumVals; --NumVals, ++i) {
 631           unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
 632           MI->addOperand(MachineOperand::CreateReg(Reg, true, false, false,
 633                                                    false, false, true));
 634         }
 635         break;
 636       case 1:  // Use of register.
 637       case 3:  // Immediate.
 638       case 4:  // Addressing mode.
 639         // The addressing mode has been selected, just add all of the
 640         // operands to the machine instruction.
 641         for (; NumVals; --NumVals, ++i)
 642           AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap);
 643         break;
 644       }
 645     }
 646     BB->insert(InsertPos, MI);
 647     break;
 648   }
 649   }
 650 }
 651
 652 /// EmitSchedule - Emit the machine code in scheduled order.
 653 MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() {
 654   DenseMap<SDValue, unsigned> VRBaseMap;
 655   DenseMap<SUnit*, unsigned> CopyVRBaseMap;
 656   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 657     SUnit *SU = Sequence[i];
 658     if (!SU) {
 659       // Null SUnit* is a noop.
 660       EmitNoop();
 661       continue;
 662     }
 663
 664     // For pre-regalloc scheduling, create instructions corresponding to the
 665     // SDNode and any flagged SDNodes and append them to the block.
 666     if (!SU->getNode()) {
 667       // Emit a copy.
 668       EmitPhysRegCopy(SU, CopyVRBaseMap);
 669       continue;
 670     }
 671
 672     SmallVector<SDNode *, 4> FlaggedNodes;
 673     for (SDNode *N = SU->getNode()->getFlaggedNode(); N;
 674          N = N->getFlaggedNode())
 675       FlaggedNodes.push_back(N);
 676     while (!FlaggedNodes.empty()) {
 677       EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned,VRBaseMap);
 678       FlaggedNodes.pop_back();
 679     }
 680     EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
 681   }
 682
 683   return BB;
 684 }