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 "pre-RA-sched"
  17 #include "llvm/Type.h"
  18 #include "llvm/CodeGen/ScheduleDAG.h"
  19 #include "llvm/CodeGen/MachineConstantPool.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/Target/TargetData.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetLowering.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/MathExtras.h"
  28 using namespace llvm;
  29
  30
  31 /// CheckForPhysRegDependency - Check if the dependency between def and use of
  32 /// a specified operand is a physical register dependency. If so, returns the
  33 /// register and the cost of copying the register.
  34 static void CheckForPhysRegDependency(SDNode *Def, SDNode *Use, unsigned Op,
  35                                       const MRegisterInfo *MRI,
  36                                       const TargetInstrInfo *TII,
  37                                       unsigned &PhysReg, int &Cost) {
  38   if (Op != 2 || Use->getOpcode() != ISD::CopyToReg)
  39     return;
  40
  41   unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
  42   if (MRegisterInfo::isVirtualRegister(Reg))
  43     return;
  44
  45   unsigned ResNo = Use->getOperand(2).ResNo;
  46   if (Def->isTargetOpcode()) {
  47     const TargetInstrDescriptor &II = TII->get(Def->getTargetOpcode());
  48     if (ResNo >= II.numDefs &&
  49         II.ImplicitDefs[ResNo - II.numDefs] == Reg) {
  50       PhysReg = Reg;
  51       const TargetRegisterClass *RC =
  52         MRI->getPhysicalRegisterRegClass(Def->getValueType(ResNo), Reg);
  53       Cost = RC->getCopyCost();
  54     }
  55   }
  56 }
  57
  58 SUnit *ScheduleDAG::Clone(SUnit *Old) {
  59   SUnit *SU = NewSUnit(Old->Node);
  60   for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i)
  61     SU->FlaggedNodes.push_back(SU->FlaggedNodes[i]);
  62   SU->InstanceNo = SUnitMap[Old->Node].size();
  63   SU->Latency = Old->Latency;
  64   SU->isTwoAddress = Old->isTwoAddress;
  65   SU->isCommutable = Old->isCommutable;
  66   SU->hasImplicitDefs = Old->hasImplicitDefs;
  67   SUnitMap[Old->Node].push_back(SU);
  68   return SU;
  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   // Reserve entries in the vector for each of the SUnits we are creating.  This
  76   // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
  77   // invalidated.
  78   SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end()));
  79
  80   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
  81
  82   for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(),
  83        E = DAG.allnodes_end(); NI != E; ++NI) {
  84     if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
  85       continue;
  86
  87     // If this node has already been processed, stop now.
  88     if (SUnitMap[NI].size()) continue;
  89
  90     SUnit *NodeSUnit = NewSUnit(NI);
  91
  92     // See if anything is flagged to this node, if so, add them to flagged
  93     // nodes.  Nodes can have at most one flag input and one flag output.  Flags
  94     // are required the be the last operand and result of a node.
  95
  96     // Scan up, adding flagged preds to FlaggedNodes.
  97     SDNode *N = NI;
  98     if (N->getNumOperands() &&
  99         N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
 100       do {
 101         N = N->getOperand(N->getNumOperands()-1).Val;
 102         NodeSUnit->FlaggedNodes.push_back(N);
 103         SUnitMap[N].push_back(NodeSUnit);
 104       } while (N->getNumOperands() &&
 105                N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
 106       std::reverse(NodeSUnit->FlaggedNodes.begin(),
 107                    NodeSUnit->FlaggedNodes.end());
 108     }
 109
 110     // Scan down, adding this node and any flagged succs to FlaggedNodes if they
 111     // have a user of the flag operand.
 112     N = NI;
 113     while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
 114       SDOperand FlagVal(N, N->getNumValues()-1);
 115
 116       // There are either zero or one users of the Flag result.
 117       bool HasFlagUse = false;
 118       for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
 119            UI != E; ++UI)
 120         if (FlagVal.isOperand(*UI)) {
 121           HasFlagUse = true;
 122           NodeSUnit->FlaggedNodes.push_back(N);
 123           SUnitMap[N].push_back(NodeSUnit);
 124           N = *UI;
 125           break;
 126         }
 127       if (!HasFlagUse) break;
 128     }
 129
 130     // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
 131     // Update the SUnit
 132     NodeSUnit->Node = N;
 133     SUnitMap[N].push_back(NodeSUnit);
 134
 135     // Compute the latency for the node.  We use the sum of the latencies for
 136     // all nodes flagged together into this SUnit.
 137     if (InstrItins.isEmpty()) {
 138       // No latency information.
 139       NodeSUnit->Latency = 1;
 140     } else {
 141       NodeSUnit->Latency = 0;
 142       if (N->isTargetOpcode()) {
 143         unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode());
 144         InstrStage *S = InstrItins.begin(SchedClass);
 145         InstrStage *E = InstrItins.end(SchedClass);
 146         for (; S != E; ++S)
 147           NodeSUnit->Latency += S->Cycles;
 148       }
 149       for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) {
 150         SDNode *FNode = NodeSUnit->FlaggedNodes[i];
 151         if (FNode->isTargetOpcode()) {
 152           unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode());
 153           InstrStage *S = InstrItins.begin(SchedClass);
 154           InstrStage *E = InstrItins.end(SchedClass);
 155           for (; S != E; ++S)
 156             NodeSUnit->Latency += S->Cycles;
 157         }
 158       }
 159     }
 160   }
 161
 162   // Pass 2: add the preds, succs, etc.
 163   for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
 164     SUnit *SU = &SUnits[su];
 165     SDNode *MainNode = SU->Node;
 166
 167     if (MainNode->isTargetOpcode()) {
 168       unsigned Opc = MainNode->getTargetOpcode();
 169       const TargetInstrDescriptor &TID = TII->get(Opc);
 170       if (TID.ImplicitDefs)
 171         SU->hasImplicitDefs = true;
 172       for (unsigned i = 0; i != TID.numOperands; ++i) {
 173         if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
 174           SU->isTwoAddress = true;
 175           break;
 176         }
 177       }
 178       if (TID.Flags & M_COMMUTABLE)
 179         SU->isCommutable = true;
 180     }
 181
 182     // Find all predecessors and successors of the group.
 183     // Temporarily add N to make code simpler.
 184     SU->FlaggedNodes.push_back(MainNode);
 185
 186     for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
 187       SDNode *N = SU->FlaggedNodes[n];
 188       if (N->isTargetOpcode() && TII->getImplicitDefs(N->getTargetOpcode()))
 189         SU->hasImplicitDefs = true;
 190
 191       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 192         SDNode *OpN = N->getOperand(i).Val;
 193         if (isPassiveNode(OpN)) continue;   // Not scheduled.
 194         SUnit *OpSU = SUnitMap[OpN].front();
 195         assert(OpSU && "Node has no SUnit!");
 196         if (OpSU == SU) continue;           // In the same group.
 197
 198         MVT::ValueType OpVT = N->getOperand(i).getValueType();
 199         assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
 200         bool isChain = OpVT == MVT::Other;
 201
 202         unsigned PhysReg = 0;
 203         int Cost = 1;
 204         // Determine if this is a physical register dependency.
 205         CheckForPhysRegDependency(OpN, N, i, MRI, TII, PhysReg, Cost);
 206         SU->addPred(OpSU, isChain, false, PhysReg, Cost);
 207       }
 208     }
 209
 210     // Remove MainNode from FlaggedNodes again.
 211     SU->FlaggedNodes.pop_back();
 212   }
 213
 214   return;
 215 }
 216
 217 void ScheduleDAG::CalculateDepths() {
 218   std::vector<std::pair<SUnit*, unsigned> > WorkList;
 219   for (unsigned i = 0, e = SUnits.size(); i != e; ++i)
 220     if (SUnits[i].Preds.size() == 0)
 221       WorkList.push_back(std::make_pair(&SUnits[i], 0U));
 222
 223   while (!WorkList.empty()) {
 224     SUnit *SU = WorkList.back().first;
 225     unsigned Depth = WorkList.back().second;
 226     WorkList.pop_back();
 227     if (SU->Depth == 0 || Depth > SU->Depth) {
 228       SU->Depth = Depth;
 229       for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 230            I != E; ++I)
 231         WorkList.push_back(std::make_pair(I->Dep, Depth+1));
 232     }
 233   }
 234 }
 235
 236 void ScheduleDAG::CalculateHeights() {
 237   std::vector<std::pair<SUnit*, unsigned> > WorkList;
 238   SUnit *Root = SUnitMap[DAG.getRoot().Val].front();
 239   WorkList.push_back(std::make_pair(Root, 0U));
 240
 241   while (!WorkList.empty()) {
 242     SUnit *SU = WorkList.back().first;
 243     unsigned Height = WorkList.back().second;
 244     WorkList.pop_back();
 245     if (SU->Height == 0 || Height > SU->Height) {
 246       SU->Height = Height;
 247       for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 248            I != E; ++I)
 249         WorkList.push_back(std::make_pair(I->Dep, Height+1));
 250     }
 251   }
 252 }
 253
 254 /// CountResults - The results of target nodes have register or immediate
 255 /// operands first, then an optional chain, and optional flag operands (which do
 256 /// not go into the machine instrs.)
 257 unsigned ScheduleDAG::CountResults(SDNode *Node) {
 258   unsigned N = Node->getNumValues();
 259   while (N && Node->getValueType(N - 1) == MVT::Flag)
 260     --N;
 261   if (N && Node->getValueType(N - 1) == MVT::Other)
 262     --N;    // Skip over chain result.
 263   return N;
 264 }
 265
 266 /// CountOperands  The inputs to target nodes have any actual inputs first,
 267 /// followed by an optional chain operand, then flag operands.  Compute the
 268 /// number of actual operands that  will go into the machine instr.
 269 unsigned ScheduleDAG::CountOperands(SDNode *Node) {
 270   unsigned N = Node->getNumOperands();
 271   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
 272     --N;
 273   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
 274     --N; // Ignore chain if it exists.
 275   return N;
 276 }
 277
 278 static const TargetRegisterClass *getInstrOperandRegClass(
 279         const MRegisterInfo *MRI,
 280         const TargetInstrInfo *TII,
 281         const TargetInstrDescriptor *II,
 282         unsigned Op) {
 283   if (Op >= II->numOperands) {
 284     assert((II->Flags & M_VARIABLE_OPS)&& "Invalid operand # of instruction");
 285     return NULL;
 286   }
 287   const TargetOperandInfo &toi = II->OpInfo[Op];
 288   return (toi.Flags & M_LOOK_UP_PTR_REG_CLASS)
 289          ? TII->getPointerRegClass() : MRI->getRegClass(toi.RegClass);
 290 }
 291
 292 void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
 293                                   unsigned InstanceNo, unsigned SrcReg,
 294                                   DenseMap<SDOperand, unsigned> &VRBaseMap) {
 295   unsigned VRBase = 0;
 296   if (MRegisterInfo::isVirtualRegister(SrcReg)) {
 297     // Just use the input register directly!
 298     if (InstanceNo > 0)
 299       VRBaseMap.erase(SDOperand(Node, ResNo));
 300     bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo),SrcReg));
 301     assert(isNew && "Node emitted out of order - early");
 302     return;
 303   }
 304
 305   // If the node is only used by a CopyToReg and the dest reg is a vreg, use
 306   // the CopyToReg'd destination register instead of creating a new vreg.
 307   bool MatchReg = true;
 308   for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 309        UI != E; ++UI) {
 310     SDNode *Use = *UI;
 311     bool Match = true;
 312     if (Use->getOpcode() == ISD::CopyToReg &&
 313         Use->getOperand(2).Val == Node &&
 314         Use->getOperand(2).ResNo == ResNo) {
 315       unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
 316       if (MRegisterInfo::isVirtualRegister(DestReg)) {
 317         VRBase = DestReg;
 318         Match = false;
 319       } else if (DestReg != SrcReg)
 320         Match = false;
 321     } else {
 322       for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
 323         SDOperand Op = Use->getOperand(i);
 324         if (Op.Val != Node)
 325           continue;
 326         MVT::ValueType VT = Node->getValueType(Op.ResNo);
 327         if (VT != MVT::Other && VT != MVT::Flag)
 328           Match = false;
 329       }
 330     }
 331     MatchReg &= Match;
 332     if (VRBase)
 333       break;
 334   }
 335
 336   const TargetRegisterClass *TRC = 0;
 337   // Figure out the register class to create for the destreg.
 338   if (VRBase)
 339     TRC = RegMap->getRegClass(VRBase);
 340   else
 341     TRC = MRI->getPhysicalRegisterRegClass(Node->getValueType(ResNo), SrcReg);
 342
 343   // If all uses are reading from the src physical register and copying the
 344   // register is either impossible or very expensive, then don't create a copy.
 345   if (MatchReg && TRC->getCopyCost() < 0) {
 346     VRBase = SrcReg;
 347   } else {
 348     // Create the reg, emit the copy.
 349     VRBase = RegMap->createVirtualRegister(TRC);
 350     MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC, TRC);
 351   }
 352
 353   if (InstanceNo > 0)
 354     VRBaseMap.erase(SDOperand(Node, ResNo));
 355   bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo), VRBase));
 356   assert(isNew && "Node emitted out of order - early");
 357 }
 358
 359 void ScheduleDAG::CreateVirtualRegisters(SDNode *Node,
 360                                          MachineInstr *MI,
 361                                          const TargetInstrDescriptor &II,
 362                                      DenseMap<SDOperand, unsigned> &VRBaseMap) {
 363   for (unsigned i = 0; i < II.numDefs; ++i) {
 364     // If the specific node value is only used by a CopyToReg and the dest reg
 365     // is a vreg, use the CopyToReg'd destination register instead of creating
 366     // a new vreg.
 367     unsigned VRBase = 0;
 368     for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 369          UI != E; ++UI) {
 370       SDNode *Use = *UI;
 371       if (Use->getOpcode() == ISD::CopyToReg &&
 372           Use->getOperand(2).Val == Node &&
 373           Use->getOperand(2).ResNo == i) {
 374         unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
 375         if (MRegisterInfo::isVirtualRegister(Reg)) {
 376           VRBase = Reg;
 377           MI->addRegOperand(Reg, true);
 378           break;
 379         }
 380       }
 381     }
 382
 383     // Create the result registers for this node and add the result regs to
 384     // the machine instruction.
 385     if (VRBase == 0) {
 386       const TargetRegisterClass *RC = getInstrOperandRegClass(MRI, TII, &II, i);
 387       assert(RC && "Isn't a register operand!");
 388       VRBase = RegMap->createVirtualRegister(RC);
 389       MI->addRegOperand(VRBase, true);
 390     }
 391
 392     bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,i), VRBase));
 393     assert(isNew && "Node emitted out of order - early");
 394   }
 395 }
 396
 397 /// getVR - Return the virtual register corresponding to the specified result
 398 /// of the specified node.
 399 static unsigned getVR(SDOperand Op, DenseMap<SDOperand, unsigned> &VRBaseMap) {
 400   DenseMap<SDOperand, unsigned>::iterator I = VRBaseMap.find(Op);
 401   assert(I != VRBaseMap.end() && "Node emitted out of order - late");
 402   return I->second;
 403 }
 404
 405
 406 /// AddOperand - Add the specified operand to the specified machine instr.  II
 407 /// specifies the instruction information for the node, and IIOpNum is the
 408 /// operand number (in the II) that we are adding. IIOpNum and II are used for
 409 /// assertions only.
 410 void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op,
 411                              unsigned IIOpNum,
 412                              const TargetInstrDescriptor *II,
 413                              DenseMap<SDOperand, unsigned> &VRBaseMap) {
 414   if (Op.isTargetOpcode()) {
 415     // Note that this case is redundant with the final else block, but we
 416     // include it because it is the most common and it makes the logic
 417     // simpler here.
 418     assert(Op.getValueType() != MVT::Other &&
 419            Op.getValueType() != MVT::Flag &&
 420            "Chain and flag operands should occur at end of operand list!");
 421
 422     // Get/emit the operand.
 423     unsigned VReg = getVR(Op, VRBaseMap);
 424     const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 425     bool isOptDef = (IIOpNum < TID->numOperands)
 426       ? (TID->OpInfo[IIOpNum].Flags & M_OPTIONAL_DEF_OPERAND) : false;
 427     MI->addRegOperand(VReg, isOptDef);
 428
 429     // Verify that it is right.
 430     assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
 431     if (II) {
 432       const TargetRegisterClass *RC =
 433                           getInstrOperandRegClass(MRI, TII, II, IIOpNum);
 434       assert(RC && "Don't have operand info for this instruction!");
 435       const TargetRegisterClass *VRC = RegMap->getRegClass(VReg);
 436       if (VRC != RC) {
 437         cerr << "Register class of operand and regclass of use don't agree!\n";
 438 #ifndef NDEBUG
 439         cerr << "Operand = " << IIOpNum << "\n";
 440         cerr << "Op->Val = "; Op.Val->dump(&DAG); cerr << "\n";
 441         cerr << "MI = "; MI->print(cerr);
 442         cerr << "VReg = " << VReg << "\n";
 443         cerr << "VReg RegClass     size = " << VRC->getSize()
 444              << ", align = " << VRC->getAlignment() << "\n";
 445         cerr << "Expected RegClass size = " << RC->getSize()
 446              << ", align = " << RC->getAlignment() << "\n";
 447 #endif
 448         cerr << "Fatal error, aborting.\n";
 449         abort();
 450       }
 451     }
 452   } else if (ConstantSDNode *C =
 453              dyn_cast<ConstantSDNode>(Op)) {
 454     MI->addImmOperand(C->getValue());
 455   } else if (RegisterSDNode *R =
 456              dyn_cast<RegisterSDNode>(Op)) {
 457     MI->addRegOperand(R->getReg(), false);
 458   } else if (GlobalAddressSDNode *TGA =
 459              dyn_cast<GlobalAddressSDNode>(Op)) {
 460     MI->addGlobalAddressOperand(TGA->getGlobal(), TGA->getOffset());
 461   } else if (BasicBlockSDNode *BB =
 462              dyn_cast<BasicBlockSDNode>(Op)) {
 463     MI->addMachineBasicBlockOperand(BB->getBasicBlock());
 464   } else if (FrameIndexSDNode *FI =
 465              dyn_cast<FrameIndexSDNode>(Op)) {
 466     MI->addFrameIndexOperand(FI->getIndex());
 467   } else if (JumpTableSDNode *JT =
 468              dyn_cast<JumpTableSDNode>(Op)) {
 469     MI->addJumpTableIndexOperand(JT->getIndex());
 470   } else if (ConstantPoolSDNode *CP =
 471              dyn_cast<ConstantPoolSDNode>(Op)) {
 472     int Offset = CP->getOffset();
 473     unsigned Align = CP->getAlignment();
 474     const Type *Type = CP->getType();
 475     // MachineConstantPool wants an explicit alignment.
 476     if (Align == 0) {
 477       Align = TM.getTargetData()->getPreferredTypeAlignmentShift(Type);
 478       if (Align == 0) {
 479         // Alignment of vector types.  FIXME!
 480         Align = TM.getTargetData()->getTypeSize(Type);
 481         Align = Log2_64(Align);
 482       }
 483     }
 484
 485     unsigned Idx;
 486     if (CP->isMachineConstantPoolEntry())
 487       Idx = ConstPool->getConstantPoolIndex(CP->getMachineCPVal(), Align);
 488     else
 489       Idx = ConstPool->getConstantPoolIndex(CP->getConstVal(), Align);
 490     MI->addConstantPoolIndexOperand(Idx, Offset);
 491   } else if (ExternalSymbolSDNode *ES =
 492              dyn_cast<ExternalSymbolSDNode>(Op)) {
 493     MI->addExternalSymbolOperand(ES->getSymbol());
 494   } else {
 495     assert(Op.getValueType() != MVT::Other &&
 496            Op.getValueType() != MVT::Flag &&
 497            "Chain and flag operands should occur at end of operand list!");
 498     unsigned VReg = getVR(Op, VRBaseMap);
 499     MI->addRegOperand(VReg, false);
 500
 501     // Verify that it is right.
 502     assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
 503     if (II) {
 504       const TargetRegisterClass *RC =
 505                             getInstrOperandRegClass(MRI, TII, II, IIOpNum);
 506       assert(RC && "Don't have operand info for this instruction!");
 507       assert(RegMap->getRegClass(VReg) == RC &&
 508              "Register class of operand and regclass of use don't agree!");
 509     }
 510   }
 511
 512 }
 513
 514 // Returns the Register Class of a subregister
 515 static const TargetRegisterClass *getSubRegisterRegClass(
 516         const TargetRegisterClass *TRC,
 517         unsigned SubIdx) {
 518   // Pick the register class of the subregister
 519   MRegisterInfo::regclass_iterator I = TRC->subregclasses_begin() + SubIdx-1;
 520   assert(I < TRC->subregclasses_end() &&
 521          "Invalid subregister index for register class");
 522   return *I;
 523 }
 524
 525 static const TargetRegisterClass *getSuperregRegisterClass(
 526         const TargetRegisterClass *TRC,
 527         unsigned SubIdx,
 528         MVT::ValueType VT) {
 529   // Pick the register class of the superegister for this type
 530   for (MRegisterInfo::regclass_iterator I = TRC->superregclasses_begin(),
 531          E = TRC->superregclasses_end(); I != E; ++I)
 532     if ((*I)->hasType(VT) && getSubRegisterRegClass(*I, SubIdx) == TRC)
 533       return *I;
 534   assert(false && "Couldn't find the register class");
 535   return 0;
 536 }
 537
 538 /// EmitSubregNode - Generate machine code for subreg nodes.
 539 ///
 540 void ScheduleDAG::EmitSubregNode(SDNode *Node,
 541                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
 542   unsigned VRBase = 0;
 543   unsigned Opc = Node->getTargetOpcode();
 544   if (Opc == TargetInstrInfo::EXTRACT_SUBREG) {
 545     // If the node is only used by a CopyToReg and the dest reg is a vreg, use
 546     // the CopyToReg'd destination register instead of creating a new vreg.
 547     for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 548          UI != E; ++UI) {
 549       SDNode *Use = *UI;
 550       if (Use->getOpcode() == ISD::CopyToReg &&
 551           Use->getOperand(2).Val == Node) {
 552         unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
 553         if (MRegisterInfo::isVirtualRegister(DestReg)) {
 554           VRBase = DestReg;
 555           break;
 556         }
 557       }
 558     }
 559
 560     unsigned SubIdx = cast<ConstantSDNode>(Node->getOperand(1))->getValue();
 561
 562     // TODO: If the node is a use of a CopyFromReg from a physical register
 563     // fold the extract into the copy now
 564
 565     // TODO: Add tracking info to SSARegMap of which vregs are subregs
 566     // to allow coalescing in the allocator
 567
 568     // Create the extract_subreg machine instruction.
 569     MachineInstr *MI =
 570       new MachineInstr(BB, TII->get(TargetInstrInfo::EXTRACT_SUBREG));
 571
 572     // Figure out the register class to create for the destreg.
 573     unsigned VReg = getVR(Node->getOperand(0), VRBaseMap);
 574     const TargetRegisterClass *TRC = RegMap->getRegClass(VReg);
 575     const TargetRegisterClass *SRC = getSubRegisterRegClass(TRC, SubIdx);
 576
 577     if (VRBase) {
 578       // Grab the destination register
 579       const TargetRegisterClass *DRC = 0;
 580       DRC = RegMap->getRegClass(VRBase);
 581       assert(SRC == DRC &&
 582              "Source subregister and destination must have the same class");
 583     } else {
 584       // Create the reg
 585       VRBase = RegMap->createVirtualRegister(SRC);
 586     }
 587
 588     // Add def, source, and subreg index
 589     MI->addRegOperand(VRBase, true);
 590     AddOperand(MI, Node->getOperand(0), 0, 0, VRBaseMap);
 591     MI->addImmOperand(SubIdx);
 592
 593   } else if (Opc == TargetInstrInfo::INSERT_SUBREG) {
 594     assert((Node->getNumOperands() == 2 || Node->getNumOperands() == 3) &&
 595             "Malformed insert_subreg node");
 596     bool isUndefInput = (Node->getNumOperands() == 2);
 597     unsigned SubReg = 0;
 598     unsigned SubIdx = 0;
 599
 600     if (isUndefInput) {
 601       SubReg = getVR(Node->getOperand(0), VRBaseMap);
 602       SubIdx = cast<ConstantSDNode>(Node->getOperand(1))->getValue();
 603     } else {
 604       SubReg = getVR(Node->getOperand(1), VRBaseMap);
 605       SubIdx = cast<ConstantSDNode>(Node->getOperand(2))->getValue();
 606     }
 607
 608     // TODO: Add tracking info to SSARegMap of which vregs are subregs
 609     // to allow coalescing in the allocator
 610
 611     // If the node is only used by a CopyToReg and the dest reg is a vreg, use
 612     // the CopyToReg'd destination register instead of creating a new vreg.
 613     // If the CopyToReg'd destination register is physical, then fold the
 614     // insert into the copy
 615     for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
 616          UI != E; ++UI) {
 617       SDNode *Use = *UI;
 618       if (Use->getOpcode() == ISD::CopyToReg &&
 619           Use->getOperand(2).Val == Node) {
 620         unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
 621         if (MRegisterInfo::isVirtualRegister(DestReg)) {
 622           VRBase = DestReg;
 623           break;
 624         }
 625       }
 626     }
 627
 628     // Create the insert_subreg machine instruction.
 629     MachineInstr *MI =
 630       new MachineInstr(BB, TII->get(TargetInstrInfo::INSERT_SUBREG));
 631
 632     // Figure out the register class to create for the destreg.
 633     const TargetRegisterClass *TRC = 0;
 634     if (VRBase) {
 635       TRC = RegMap->getRegClass(VRBase);
 636     } else {
 637       TRC = getSuperregRegisterClass(RegMap->getRegClass(SubReg),
 638                                      SubIdx,
 639                                      Node->getValueType(0));
 640       assert(TRC && "Couldn't determine register class for insert_subreg");
 641       VRBase = RegMap->createVirtualRegister(TRC); // Create the reg
 642     }
 643
 644     MI->addRegOperand(VRBase, true);
 645     AddOperand(MI, Node->getOperand(0), 0, 0, VRBaseMap);
 646     if (!isUndefInput)
 647       AddOperand(MI, Node->getOperand(1), 0, 0, VRBaseMap);
 648     MI->addImmOperand(SubIdx);
 649   } else
 650     assert(0 && "Node is not a subreg insert or extract");
 651
 652   bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,0), VRBase));
 653   assert(isNew && "Node emitted out of order - early");
 654 }
 655
 656 /// EmitNode - Generate machine code for an node and needed dependencies.
 657 ///
 658 void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
 659                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
 660   // If machine instruction
 661   if (Node->isTargetOpcode()) {
 662     unsigned Opc = Node->getTargetOpcode();
 663
 664     // Handle subreg insert/extract specially
 665     if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
 666         Opc == TargetInstrInfo::INSERT_SUBREG) {
 667       EmitSubregNode(Node, VRBaseMap);
 668       return;
 669     }
 670
 671     const TargetInstrDescriptor &II = TII->get(Opc);
 672
 673     unsigned NumResults = CountResults(Node);
 674     unsigned NodeOperands = CountOperands(Node);
 675     unsigned NumMIOperands = NodeOperands + NumResults;
 676     bool     HasPhysRegOuts = (NumResults > II.numDefs) && II.ImplicitDefs;
 677 #ifndef NDEBUG
 678     assert((unsigned(II.numOperands) == NumMIOperands ||
 679             HasPhysRegOuts || (II.Flags & M_VARIABLE_OPS)) &&
 680            "#operands for dag node doesn't match .td file!");
 681 #endif
 682
 683     // Create the new machine instruction.
 684     MachineInstr *MI = new MachineInstr(II);
 685
 686     // Add result register values for things that are defined by this
 687     // instruction.
 688     if (NumResults)
 689       CreateVirtualRegisters(Node, MI, II, VRBaseMap);
 690
 691     // Emit all of the actual operands of this instruction, adding them to the
 692     // instruction as appropriate.
 693     for (unsigned i = 0; i != NodeOperands; ++i)
 694       AddOperand(MI, Node->getOperand(i), i+II.numDefs, &II, VRBaseMap);
 695
 696     // Commute node if it has been determined to be profitable.
 697     if (CommuteSet.count(Node)) {
 698       MachineInstr *NewMI = TII->commuteInstruction(MI);
 699       if (NewMI == 0)
 700         DOUT << "Sched: COMMUTING FAILED!\n";
 701       else {
 702         DOUT << "Sched: COMMUTED TO: " << *NewMI;
 703         if (MI != NewMI) {
 704           delete MI;
 705           MI = NewMI;
 706         }
 707       }
 708     }
 709
 710     // Now that we have emitted all operands, emit this instruction itself.
 711     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
 712       BB->insert(BB->end(), MI);
 713     } else {
 714       // Insert this instruction into the end of the basic block, potentially
 715       // taking some custom action.
 716       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
 717     }
 718
 719     // Additional results must be an physical register def.
 720     if (HasPhysRegOuts) {
 721       for (unsigned i = II.numDefs; i < NumResults; ++i) {
 722         unsigned Reg = II.ImplicitDefs[i - II.numDefs];
 723         if (Node->hasAnyUseOfValue(i))
 724           EmitCopyFromReg(Node, i, InstanceNo, Reg, VRBaseMap);
 725       }
 726     }
 727   } else {
 728     switch (Node->getOpcode()) {
 729     default:
 730 #ifndef NDEBUG
 731       Node->dump(&DAG);
 732 #endif
 733       assert(0 && "This target-independent node should have been selected!");
 734     case ISD::EntryToken: // fall thru
 735     case ISD::TokenFactor:
 736     case ISD::LABEL:
 737       break;
 738     case ISD::CopyToReg: {
 739       unsigned InReg;
 740       if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Node->getOperand(2)))
 741         InReg = R->getReg();
 742       else
 743         InReg = getVR(Node->getOperand(2), VRBaseMap);
 744       unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 745       if (InReg != DestReg)  {// Coalesced away the copy?
 746         const TargetRegisterClass *TRC = 0;
 747         // Get the target register class
 748         if (MRegisterInfo::isVirtualRegister(InReg))
 749           TRC = RegMap->getRegClass(InReg);
 750         else
 751           TRC =
 752             MRI->getPhysicalRegisterRegClass(Node->getOperand(2).getValueType(),
 753                                             InReg);
 754         MRI->copyRegToReg(*BB, BB->end(), DestReg, InReg, TRC, TRC);
 755       }
 756       break;
 757     }
 758     case ISD::CopyFromReg: {
 759       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 760       EmitCopyFromReg(Node, 0, InstanceNo, SrcReg, VRBaseMap);
 761       break;
 762     }
 763     case ISD::INLINEASM: {
 764       unsigned NumOps = Node->getNumOperands();
 765       if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
 766         --NumOps;  // Ignore the flag operand.
 767
 768       // Create the inline asm machine instruction.
 769       MachineInstr *MI =
 770         new MachineInstr(BB, TII->get(TargetInstrInfo::INLINEASM));
 771
 772       // Add the asm string as an external symbol operand.
 773       const char *AsmStr =
 774         cast<ExternalSymbolSDNode>(Node->getOperand(1))->getSymbol();
 775       MI->addExternalSymbolOperand(AsmStr);
 776
 777       // Add all of the operand registers to the instruction.
 778       for (unsigned i = 2; i != NumOps;) {
 779         unsigned Flags = cast<ConstantSDNode>(Node->getOperand(i))->getValue();
 780         unsigned NumVals = Flags >> 3;
 781
 782         MI->addImmOperand(Flags);
 783         ++i;  // Skip the ID value.
 784
 785         switch (Flags & 7) {
 786         default: assert(0 && "Bad flags!");
 787         case 1:  // Use of register.
 788           for (; NumVals; --NumVals, ++i) {
 789             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
 790             MI->addRegOperand(Reg, false);
 791           }
 792           break;
 793         case 2:   // Def of register.
 794           for (; NumVals; --NumVals, ++i) {
 795             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
 796             MI->addRegOperand(Reg, true);
 797           }
 798           break;
 799         case 3: { // Immediate.
 800           for (; NumVals; --NumVals, ++i) {
 801             if (ConstantSDNode *CS =
 802                    dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
 803               MI->addImmOperand(CS->getValue());
 804             } else {
 805               GlobalAddressSDNode *GA =
 806                   cast<GlobalAddressSDNode>(Node->getOperand(i));
 807               MI->addGlobalAddressOperand(GA->getGlobal(), GA->getOffset());
 808             }
 809           }
 810           break;
 811         }
 812         case 4:  // Addressing mode.
 813           // The addressing mode has been selected, just add all of the
 814           // operands to the machine instruction.
 815           for (; NumVals; --NumVals, ++i)
 816             AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap);
 817           break;
 818         }
 819       }
 820       break;
 821     }
 822     }
 823   }
 824 }
 825
 826 void ScheduleDAG::EmitNoop() {
 827   TII->insertNoop(*BB, BB->end());
 828 }
 829
 830 void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap) {
 831   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 832        I != E; ++I) {
 833     if (I->isCtrl) continue;  // ignore chain preds
 834     if (!I->Dep->Node) {
 835       // Copy to physical register.
 836       DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep);
 837       assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
 838       // Find the destination physical register.
 839       unsigned Reg = 0;
 840       for (SUnit::const_succ_iterator II = SU->Succs.begin(),
 841              EE = SU->Succs.end(); II != EE; ++II) {
 842         if (I->Reg) {
 843           Reg = I->Reg;
 844           break;
 845         }
 846       }
 847       assert(I->Reg && "Unknown physical register!");
 848       MRI->copyRegToReg(*BB, BB->end(), Reg, VRI->second,
 849                         SU->CopyDstRC, SU->CopySrcRC);
 850     } else {
 851       // Copy from physical register.
 852       assert(I->Reg && "Unknown physical register!");
 853       unsigned VRBase = RegMap->createVirtualRegister(SU->CopyDstRC);
 854       bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase));
 855       assert(isNew && "Node emitted out of order - early");
 856       MRI->copyRegToReg(*BB, BB->end(), VRBase, I->Reg,
 857                         SU->CopyDstRC, SU->CopySrcRC);
 858     }
 859     break;
 860   }
 861 }
 862
 863 /// EmitSchedule - Emit the machine code in scheduled order.
 864 void ScheduleDAG::EmitSchedule() {
 865   // If this is the first basic block in the function, and if it has live ins
 866   // that need to be copied into vregs, emit the copies into the top of the
 867   // block before emitting the code for the block.
 868   MachineFunction &MF = DAG.getMachineFunction();
 869   if (&MF.front() == BB && MF.livein_begin() != MF.livein_end()) {
 870     for (MachineFunction::livein_iterator LI = MF.livein_begin(),
 871          E = MF.livein_end(); LI != E; ++LI)
 872       if (LI->second) {
 873         const TargetRegisterClass *RC = RegMap->getRegClass(LI->second);
 874         MRI->copyRegToReg(*MF.begin(), MF.begin()->end(), LI->second,
 875                           LI->first, RC, RC);
 876       }
 877   }
 878
 879
 880   // Finally, emit the code for all of the scheduled instructions.
 881   DenseMap<SDOperand, unsigned> VRBaseMap;
 882   DenseMap<SUnit*, unsigned> CopyVRBaseMap;
 883   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 884     if (SUnit *SU = Sequence[i]) {
 885       for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j)
 886         EmitNode(SU->FlaggedNodes[j], SU->InstanceNo, VRBaseMap);
 887       if (SU->Node)
 888         EmitNode(SU->Node, SU->InstanceNo, VRBaseMap);
 889       else
 890         EmitCrossRCCopy(SU, CopyVRBaseMap);
 891     } else {
 892       // Null SUnit* is a noop.
 893       EmitNoop();
 894     }
 895   }
 896 }
 897
 898 /// dump - dump the schedule.
 899 void ScheduleDAG::dumpSchedule() const {
 900   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 901     if (SUnit *SU = Sequence[i])
 902       SU->dump(&DAG);
 903     else
 904       cerr << "**** NOOP ****\n";
 905   }
 906 }
 907
 908
 909 /// Run - perform scheduling.
 910 ///
 911 MachineBasicBlock *ScheduleDAG::Run() {
 912   TII = TM.getInstrInfo();
 913   MRI = TM.getRegisterInfo();
 914   RegMap = BB->getParent()->getSSARegMap();
 915   ConstPool = BB->getParent()->getConstantPool();
 916
 917   Schedule();
 918   return BB;
 919 }
 920
 921 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
 922 /// a group of nodes flagged together.
 923 void SUnit::dump(const SelectionDAG *G) const {
 924   cerr << "SU(" << NodeNum << "): ";
 925   if (Node)
 926     Node->dump(G);
 927   else
 928     cerr << "CROSS RC COPY ";
 929   cerr << "\n";
 930   if (FlaggedNodes.size() != 0) {
 931     for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
 932       cerr << "    ";
 933       FlaggedNodes[i]->dump(G);
 934       cerr << "\n";
 935     }
 936   }
 937 }
 938
 939 void SUnit::dumpAll(const SelectionDAG *G) const {
 940   dump(G);
 941
 942   cerr << "  # preds left       : " << NumPredsLeft << "\n";
 943   cerr << "  # succs left       : " << NumSuccsLeft << "\n";
 944   cerr << "  # chain preds left : " << NumChainPredsLeft << "\n";
 945   cerr << "  # chain succs left : " << NumChainSuccsLeft << "\n";
 946   cerr << "  Latency            : " << Latency << "\n";
 947   cerr << "  Depth              : " << Depth << "\n";
 948   cerr << "  Height             : " << Height << "\n";
 949
 950   if (Preds.size() != 0) {
 951     cerr << "  Predecessors:\n";
 952     for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
 953          I != E; ++I) {
 954       if (I->isCtrl)
 955         cerr << "   ch  #";
 956       else
 957         cerr << "   val #";
 958       cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
 959       if (I->isSpecial)
 960         cerr << " *";
 961       cerr << "\n";
 962     }
 963   }
 964   if (Succs.size() != 0) {
 965     cerr << "  Successors:\n";
 966     for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
 967          I != E; ++I) {
 968       if (I->isCtrl)
 969         cerr << "   ch  #";
 970       else
 971         cerr << "   val #";
 972       cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
 973       if (I->isSpecial)
 974         cerr << " *";
 975       cerr << "\n";
 976     }
 977   }
 978   cerr << "\n";
 979 }