LLVM API Documentation

ScheduleDAG.cpp

Go to the documentation of this file.
00001 //===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by James M. Laskey and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements a simple two pass scheduler.  The first pass attempts to push
00011 // backward any lengthy instructions and critical paths.  The second pass packs
00012 // instructions into semi-optimal time slots.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #define DEBUG_TYPE "sched"
00017 #include "llvm/CodeGen/ScheduleDAG.h"
00018 #include "llvm/CodeGen/MachineConstantPool.h"
00019 #include "llvm/CodeGen/MachineFunction.h"
00020 #include "llvm/CodeGen/SSARegMap.h"
00021 #include "llvm/Target/TargetData.h"
00022 #include "llvm/Target/TargetMachine.h"
00023 #include "llvm/Target/TargetInstrInfo.h"
00024 #include "llvm/Target/TargetLowering.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/Support/MathExtras.h"
00027 #include <iostream>
00028 using namespace llvm;
00029 
00030 
00031 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
00032 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
00033 /// together nodes with a single SUnit.
00034 void ScheduleDAG::BuildSchedUnits() {
00035   // Reserve entries in the vector for each of the SUnits we are creating.  This
00036   // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
00037   // invalidated.
00038   SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end()));
00039   
00040   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
00041   
00042   for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(),
00043        E = DAG.allnodes_end(); NI != E; ++NI) {
00044     if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
00045       continue;
00046     
00047     // If this node has already been processed, stop now.
00048     if (SUnitMap[NI]) continue;
00049     
00050     SUnit *NodeSUnit = NewSUnit(NI);
00051     
00052     // See if anything is flagged to this node, if so, add them to flagged
00053     // nodes.  Nodes can have at most one flag input and one flag output.  Flags
00054     // are required the be the last operand and result of a node.
00055     
00056     // Scan up, adding flagged preds to FlaggedNodes.
00057     SDNode *N = NI;
00058     while (N->getNumOperands() &&
00059            N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
00060       N = N->getOperand(N->getNumOperands()-1).Val;
00061       NodeSUnit->FlaggedNodes.push_back(N);
00062       SUnitMap[N] = NodeSUnit;
00063     }
00064     
00065     // Scan down, adding this node and any flagged succs to FlaggedNodes if they
00066     // have a user of the flag operand.
00067     N = NI;
00068     while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
00069       SDOperand FlagVal(N, N->getNumValues()-1);
00070       
00071       // There are either zero or one users of the Flag result.
00072       bool HasFlagUse = false;
00073       for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 
00074            UI != E; ++UI)
00075         if (FlagVal.isOperand(*UI)) {
00076           HasFlagUse = true;
00077           NodeSUnit->FlaggedNodes.push_back(N);
00078           SUnitMap[N] = NodeSUnit;
00079           N = *UI;
00080           break;
00081         }
00082           if (!HasFlagUse) break;
00083     }
00084     
00085     // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
00086     // Update the SUnit
00087     NodeSUnit->Node = N;
00088     SUnitMap[N] = NodeSUnit;
00089     
00090     // Compute the latency for the node.  We use the sum of the latencies for
00091     // all nodes flagged together into this SUnit.
00092     if (InstrItins.isEmpty()) {
00093       // No latency information.
00094       NodeSUnit->Latency = 1;
00095     } else {
00096       NodeSUnit->Latency = 0;
00097       if (N->isTargetOpcode()) {
00098         unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode());
00099         InstrStage *S = InstrItins.begin(SchedClass);
00100         InstrStage *E = InstrItins.end(SchedClass);
00101         for (; S != E; ++S)
00102           NodeSUnit->Latency += S->Cycles;
00103       }
00104       for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) {
00105         SDNode *FNode = NodeSUnit->FlaggedNodes[i];
00106         if (FNode->isTargetOpcode()) {
00107           unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode());
00108           InstrStage *S = InstrItins.begin(SchedClass);
00109           InstrStage *E = InstrItins.end(SchedClass);
00110           for (; S != E; ++S)
00111             NodeSUnit->Latency += S->Cycles;
00112         }
00113       }
00114     }
00115   }
00116   
00117   // Pass 2: add the preds, succs, etc.
00118   for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
00119     SUnit *SU = &SUnits[su];
00120     SDNode *MainNode = SU->Node;
00121     
00122     if (MainNode->isTargetOpcode()) {
00123       unsigned Opc = MainNode->getTargetOpcode();
00124       if (TII->isTwoAddrInstr(Opc))
00125         SU->isTwoAddress = true;
00126       if (TII->isCommutableInstr(Opc))
00127         SU->isCommutable = true;
00128     }
00129     
00130     // Find all predecessors and successors of the group.
00131     // Temporarily add N to make code simpler.
00132     SU->FlaggedNodes.push_back(MainNode);
00133     
00134     for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
00135       SDNode *N = SU->FlaggedNodes[n];
00136       
00137       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00138         SDNode *OpN = N->getOperand(i).Val;
00139         if (isPassiveNode(OpN)) continue;   // Not scheduled.
00140         SUnit *OpSU = SUnitMap[OpN];
00141         assert(OpSU && "Node has no SUnit!");
00142         if (OpSU == SU) continue;           // In the same group.
00143 
00144         MVT::ValueType OpVT = N->getOperand(i).getValueType();
00145         assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
00146         bool isChain = OpVT == MVT::Other;
00147         
00148         if (SU->Preds.insert(std::make_pair(OpSU, isChain)).second) {
00149           if (!isChain) {
00150             SU->NumPreds++;
00151             SU->NumPredsLeft++;
00152           } else {
00153             SU->NumChainPredsLeft++;
00154           }
00155         }
00156         if (OpSU->Succs.insert(std::make_pair(SU, isChain)).second) {
00157           if (!isChain) {
00158             OpSU->NumSuccs++;
00159             OpSU->NumSuccsLeft++;
00160           } else {
00161             OpSU->NumChainSuccsLeft++;
00162           }
00163         }
00164       }
00165     }
00166     
00167     // Remove MainNode from FlaggedNodes again.
00168     SU->FlaggedNodes.pop_back();
00169   }
00170   
00171   return;
00172 }
00173 
00174 static void CalculateDepths(SUnit *SU, unsigned Depth) {
00175   if (SU->Depth == 0 || Depth > SU->Depth) {
00176     SU->Depth = Depth;
00177     for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(),
00178            E = SU->Succs.end(); I != E; ++I)
00179       CalculateDepths(I->first, Depth+1);
00180   }
00181 }
00182 
00183 void ScheduleDAG::CalculateDepths() {
00184   SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
00185   ::CalculateDepths(Entry, 0U);
00186   for (unsigned i = 0, e = SUnits.size(); i != e; ++i)
00187     if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
00188       ::CalculateDepths(&SUnits[i], 0U);
00189     }
00190 }
00191 
00192 static void CalculateHeights(SUnit *SU, unsigned Height) {
00193   if (SU->Height == 0 || Height > SU->Height) {
00194     SU->Height = Height;
00195     for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
00196            E = SU->Preds.end(); I != E; ++I)
00197       CalculateHeights(I->first, Height+1);
00198   }
00199 }
00200 void ScheduleDAG::CalculateHeights() {
00201   SUnit *Root = SUnitMap[DAG.getRoot().Val];
00202   ::CalculateHeights(Root, 0U);
00203 }
00204 
00205 /// CountResults - The results of target nodes have register or immediate
00206 /// operands first, then an optional chain, and optional flag operands (which do
00207 /// not go into the machine instrs.)
00208 static unsigned CountResults(SDNode *Node) {
00209   unsigned N = Node->getNumValues();
00210   while (N && Node->getValueType(N - 1) == MVT::Flag)
00211     --N;
00212   if (N && Node->getValueType(N - 1) == MVT::Other)
00213     --N;    // Skip over chain result.
00214   return N;
00215 }
00216 
00217 /// CountOperands  The inputs to target nodes have any actual inputs first,
00218 /// followed by an optional chain operand, then flag operands.  Compute the
00219 /// number of actual operands that  will go into the machine instr.
00220 static unsigned CountOperands(SDNode *Node) {
00221   unsigned N = Node->getNumOperands();
00222   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
00223     --N;
00224   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
00225     --N; // Ignore chain if it exists.
00226   return N;
00227 }
00228 
00229 static const TargetRegisterClass *getInstrOperandRegClass(
00230         const MRegisterInfo *MRI, 
00231         const TargetInstrInfo *TII,
00232         const TargetInstrDescriptor *II,
00233         unsigned Op) {
00234   if (Op >= II->numOperands) {
00235     assert((II->Flags & M_VARIABLE_OPS)&& "Invalid operand # of instruction");
00236     return NULL;
00237   }
00238   const TargetOperandInfo &toi = II->OpInfo[Op];
00239   return (toi.Flags & M_LOOK_UP_PTR_REG_CLASS)
00240          ? TII->getPointerRegClass() : MRI->getRegClass(toi.RegClass);
00241 }
00242 
00243 static unsigned CreateVirtualRegisters(const MRegisterInfo *MRI,
00244                                        MachineInstr *MI,
00245                                        unsigned NumResults,
00246                                        SSARegMap *RegMap,
00247                                        const TargetInstrInfo *TII,
00248                                        const TargetInstrDescriptor &II) {
00249   // Create the result registers for this node and add the result regs to
00250   // the machine instruction.
00251   unsigned ResultReg =
00252     RegMap->createVirtualRegister(getInstrOperandRegClass(MRI, TII, &II, 0));
00253   MI->addRegOperand(ResultReg, MachineOperand::Def);
00254   for (unsigned i = 1; i != NumResults; ++i) {
00255     const TargetRegisterClass *RC = getInstrOperandRegClass(MRI, TII, &II, i);
00256     assert(RC && "Isn't a register operand!");
00257     MI->addRegOperand(RegMap->createVirtualRegister(RC), MachineOperand::Def);
00258   }
00259   return ResultReg;
00260 }
00261 
00262 /// getVR - Return the virtual register corresponding to the specified result
00263 /// of the specified node.
00264 static unsigned getVR(SDOperand Op, std::map<SDNode*, unsigned> &VRBaseMap) {
00265   std::map<SDNode*, unsigned>::iterator I = VRBaseMap.find(Op.Val);
00266   assert(I != VRBaseMap.end() && "Node emitted out of order - late");
00267   return I->second + Op.ResNo;
00268 }
00269 
00270 
00271 /// AddOperand - Add the specified operand to the specified machine instr.  II
00272 /// specifies the instruction information for the node, and IIOpNum is the
00273 /// operand number (in the II) that we are adding. IIOpNum and II are used for 
00274 /// assertions only.
00275 void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op,
00276                              unsigned IIOpNum,
00277                              const TargetInstrDescriptor *II,
00278                              std::map<SDNode*, unsigned> &VRBaseMap) {
00279   if (Op.isTargetOpcode()) {
00280     // Note that this case is redundant with the final else block, but we
00281     // include it because it is the most common and it makes the logic
00282     // simpler here.
00283     assert(Op.getValueType() != MVT::Other &&
00284            Op.getValueType() != MVT::Flag &&
00285            "Chain and flag operands should occur at end of operand list!");
00286     
00287     // Get/emit the operand.
00288     unsigned VReg = getVR(Op, VRBaseMap);
00289     MI->addRegOperand(VReg, MachineOperand::Use);
00290     
00291     // Verify that it is right.
00292     assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
00293     if (II) {
00294       const TargetRegisterClass *RC =
00295                           getInstrOperandRegClass(MRI, TII, II, IIOpNum);
00296       assert(RC && "Don't have operand info for this instruction!");
00297       assert(RegMap->getRegClass(VReg) == RC &&
00298              "Register class of operand and regclass of use don't agree!");
00299     }
00300   } else if (ConstantSDNode *C =
00301              dyn_cast<ConstantSDNode>(Op)) {
00302     MI->addImmOperand(C->getValue());
00303   } else if (RegisterSDNode*R =
00304              dyn_cast<RegisterSDNode>(Op)) {
00305     MI->addRegOperand(R->getReg(), MachineOperand::Use);
00306   } else if (GlobalAddressSDNode *TGA =
00307              dyn_cast<GlobalAddressSDNode>(Op)) {
00308     MI->addGlobalAddressOperand(TGA->getGlobal(), TGA->getOffset());
00309   } else if (BasicBlockSDNode *BB =
00310              dyn_cast<BasicBlockSDNode>(Op)) {
00311     MI->addMachineBasicBlockOperand(BB->getBasicBlock());
00312   } else if (FrameIndexSDNode *FI =
00313              dyn_cast<FrameIndexSDNode>(Op)) {
00314     MI->addFrameIndexOperand(FI->getIndex());
00315   } else if (JumpTableSDNode *JT =
00316              dyn_cast<JumpTableSDNode>(Op)) {
00317     MI->addJumpTableIndexOperand(JT->getIndex());
00318   } else if (ConstantPoolSDNode *CP = 
00319              dyn_cast<ConstantPoolSDNode>(Op)) {
00320     int Offset = CP->getOffset();
00321     unsigned Align = CP->getAlignment();
00322     // MachineConstantPool wants an explicit alignment.
00323     if (Align == 0) {
00324       if (CP->get()->getType() == Type::DoubleTy)
00325         Align = 3;  // always 8-byte align doubles.
00326       else {
00327         Align = TM.getTargetData()
00328           ->getTypeAlignmentShift(CP->get()->getType());
00329         if (Align == 0) {
00330           // Alignment of packed types.  FIXME!
00331           Align = TM.getTargetData()->getTypeSize(CP->get()->getType());
00332           Align = Log2_64(Align);
00333         }
00334       }
00335     }
00336     
00337     unsigned Idx = ConstPool->getConstantPoolIndex(CP->get(), Align);
00338     MI->addConstantPoolIndexOperand(Idx, Offset);
00339   } else if (ExternalSymbolSDNode *ES = 
00340              dyn_cast<ExternalSymbolSDNode>(Op)) {
00341     MI->addExternalSymbolOperand(ES->getSymbol());
00342   } else {
00343     assert(Op.getValueType() != MVT::Other &&
00344            Op.getValueType() != MVT::Flag &&
00345            "Chain and flag operands should occur at end of operand list!");
00346     unsigned VReg = getVR(Op, VRBaseMap);
00347     MI->addRegOperand(VReg, MachineOperand::Use);
00348     
00349     // Verify that it is right.
00350     assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
00351     if (II) {
00352       const TargetRegisterClass *RC =
00353                             getInstrOperandRegClass(MRI, TII, II, IIOpNum);
00354       assert(RC && "Don't have operand info for this instruction!");
00355       assert(RegMap->getRegClass(VReg) == RC &&
00356              "Register class of operand and regclass of use don't agree!");
00357     }
00358   }
00359   
00360 }
00361 
00362 
00363 /// EmitNode - Generate machine code for an node and needed dependencies.
00364 ///
00365 void ScheduleDAG::EmitNode(SDNode *Node, 
00366                            std::map<SDNode*, unsigned> &VRBaseMap) {
00367   unsigned VRBase = 0;                 // First virtual register for node
00368   
00369   // If machine instruction
00370   if (Node->isTargetOpcode()) {
00371     unsigned Opc = Node->getTargetOpcode();
00372     const TargetInstrDescriptor &II = TII->get(Opc);
00373 
00374     unsigned NumResults = CountResults(Node);
00375     unsigned NodeOperands = CountOperands(Node);
00376     unsigned NumMIOperands = NodeOperands + NumResults;
00377 #ifndef NDEBUG
00378     assert((unsigned(II.numOperands) == NumMIOperands ||
00379             (II.Flags & M_VARIABLE_OPS)) &&
00380            "#operands for dag node doesn't match .td file!"); 
00381 #endif
00382 
00383     // Create the new machine instruction.
00384     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands);
00385     
00386     // Add result register values for things that are defined by this
00387     // instruction.
00388     
00389     // If the node is only used by a CopyToReg and the dest reg is a vreg, use
00390     // the CopyToReg'd destination register instead of creating a new vreg.
00391     if (NumResults == 1) {
00392       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
00393            UI != E; ++UI) {
00394         SDNode *Use = *UI;
00395         if (Use->getOpcode() == ISD::CopyToReg && 
00396             Use->getOperand(2).Val == Node) {
00397           unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
00398           if (MRegisterInfo::isVirtualRegister(Reg)) {
00399             VRBase = Reg;
00400             MI->addRegOperand(Reg, MachineOperand::Def);
00401             break;
00402           }
00403         }
00404       }
00405     }
00406     
00407     // Otherwise, create new virtual registers.
00408     if (NumResults && VRBase == 0)
00409       VRBase = CreateVirtualRegisters(MRI, MI, NumResults, RegMap, TII, II);
00410     
00411     // Emit all of the actual operands of this instruction, adding them to the
00412     // instruction as appropriate.
00413     for (unsigned i = 0; i != NodeOperands; ++i)
00414       AddOperand(MI, Node->getOperand(i), i+NumResults, &II, VRBaseMap);
00415 
00416     // Commute node if it has been determined to be profitable.
00417     if (CommuteSet.count(Node)) {
00418       MachineInstr *NewMI = TII->commuteInstruction(MI);
00419       if (NewMI == 0)
00420         DEBUG(std::cerr << "Sched: COMMUTING FAILED!\n");
00421       else {
00422         DEBUG(std::cerr << "Sched: COMMUTED TO: " << *NewMI);
00423         if (MI != NewMI) {
00424           delete MI;
00425           MI = NewMI;
00426         }
00427       }
00428     }
00429 
00430     // Now that we have emitted all operands, emit this instruction itself.
00431     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
00432       BB->insert(BB->end(), MI);
00433     } else {
00434       // Insert this instruction into the end of the basic block, potentially
00435       // taking some custom action.
00436       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
00437     }
00438   } else {
00439     switch (Node->getOpcode()) {
00440     default:
00441 #ifndef NDEBUG
00442       Node->dump();
00443 #endif
00444       assert(0 && "This target-independent node should have been selected!");
00445     case ISD::EntryToken: // fall thru
00446     case ISD::TokenFactor:
00447       break;
00448     case ISD::CopyToReg: {
00449       unsigned InReg = getVR(Node->getOperand(2), VRBaseMap);
00450       unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
00451       if (InReg != DestReg)   // Coalesced away the copy?
00452         MRI->copyRegToReg(*BB, BB->end(), DestReg, InReg,
00453                           RegMap->getRegClass(InReg));
00454       break;
00455     }
00456     case ISD::CopyFromReg: {
00457       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
00458       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
00459         VRBase = SrcReg;  // Just use the input register directly!
00460         break;
00461       }
00462 
00463       // If the node is only used by a CopyToReg and the dest reg is a vreg, use
00464       // the CopyToReg'd destination register instead of creating a new vreg.
00465       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
00466            UI != E; ++UI) {
00467         SDNode *Use = *UI;
00468         if (Use->getOpcode() == ISD::CopyToReg && 
00469             Use->getOperand(2).Val == Node) {
00470           unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
00471           if (MRegisterInfo::isVirtualRegister(DestReg)) {
00472             VRBase = DestReg;
00473             break;
00474           }
00475         }
00476       }
00477 
00478       // Figure out the register class to create for the destreg.
00479       const TargetRegisterClass *TRC = 0;
00480       if (VRBase) {
00481         TRC = RegMap->getRegClass(VRBase);
00482       } else {
00483 
00484         // Pick the register class of the right type that contains this physreg.
00485         for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
00486              E = MRI->regclass_end(); I != E; ++I)
00487           if ((*I)->hasType(Node->getValueType(0)) &&
00488               (*I)->contains(SrcReg)) {
00489             TRC = *I;
00490             break;
00491           }
00492         assert(TRC && "Couldn't find register class for reg copy!");
00493       
00494         // Create the reg, emit the copy.
00495         VRBase = RegMap->createVirtualRegister(TRC);
00496       }
00497       MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
00498       break;
00499     }
00500     case ISD::INLINEASM: {
00501       unsigned NumOps = Node->getNumOperands();
00502       if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
00503         --NumOps;  // Ignore the flag operand.
00504       
00505       // Create the inline asm machine instruction.
00506       MachineInstr *MI =
00507         new MachineInstr(BB, TargetInstrInfo::INLINEASM, (NumOps-2)/2+1);
00508 
00509       // Add the asm string as an external symbol operand.
00510       const char *AsmStr =
00511         cast<ExternalSymbolSDNode>(Node->getOperand(1))->getSymbol();
00512       MI->addExternalSymbolOperand(AsmStr);
00513       
00514       // Add all of the operand registers to the instruction.
00515       for (unsigned i = 2; i != NumOps;) {
00516         unsigned Flags = cast<ConstantSDNode>(Node->getOperand(i))->getValue();
00517         unsigned NumVals = Flags >> 3;
00518         
00519         MI->addImmOperand(Flags);
00520         ++i;  // Skip the ID value.
00521         
00522         switch (Flags & 7) {
00523         default: assert(0 && "Bad flags!");
00524         case 1:  // Use of register.
00525           for (; NumVals; --NumVals, ++i) {
00526             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
00527             MI->addRegOperand(Reg, MachineOperand::Use);
00528           }
00529           break;
00530         case 2:   // Def of register.
00531           for (; NumVals; --NumVals, ++i) {
00532             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
00533             MI->addRegOperand(Reg, MachineOperand::Def);
00534           }
00535           break;
00536         case 3: { // Immediate.
00537           assert(NumVals == 1 && "Unknown immediate value!");
00538           uint64_t Val = cast<ConstantSDNode>(Node->getOperand(i))->getValue();
00539           MI->addImmOperand(Val);
00540           ++i;
00541           break;
00542         }
00543         case 4:  // Addressing mode.
00544           // The addressing mode has been selected, just add all of the
00545           // operands to the machine instruction.
00546           for (; NumVals; --NumVals, ++i)
00547             AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap);
00548           break;
00549         }
00550       }
00551       break;
00552     }
00553     }
00554   }
00555 
00556   assert(!VRBaseMap.count(Node) && "Node emitted out of order - early");
00557   VRBaseMap[Node] = VRBase;
00558 }
00559 
00560 void ScheduleDAG::EmitNoop() {
00561   TII->insertNoop(*BB, BB->end());
00562 }
00563 
00564 /// EmitSchedule - Emit the machine code in scheduled order.
00565 void ScheduleDAG::EmitSchedule() {
00566   // If this is the first basic block in the function, and if it has live ins
00567   // that need to be copied into vregs, emit the copies into the top of the
00568   // block before emitting the code for the block.
00569   MachineFunction &MF = DAG.getMachineFunction();
00570   if (&MF.front() == BB && MF.livein_begin() != MF.livein_end()) {
00571     for (MachineFunction::livein_iterator LI = MF.livein_begin(),
00572          E = MF.livein_end(); LI != E; ++LI)
00573       if (LI->second)
00574         MRI->copyRegToReg(*MF.begin(), MF.begin()->end(), LI->second,
00575                           LI->first, RegMap->getRegClass(LI->second));
00576   }
00577   
00578   
00579   // Finally, emit the code for all of the scheduled instructions.
00580   std::map<SDNode*, unsigned> VRBaseMap;
00581   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
00582     if (SUnit *SU = Sequence[i]) {
00583       for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++)
00584         EmitNode(SU->FlaggedNodes[j], VRBaseMap);
00585       EmitNode(SU->Node, VRBaseMap);
00586     } else {
00587       // Null SUnit* is a noop.
00588       EmitNoop();
00589     }
00590   }
00591 }
00592 
00593 /// dump - dump the schedule.
00594 void ScheduleDAG::dumpSchedule() const {
00595   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
00596     if (SUnit *SU = Sequence[i])
00597       SU->dump(&DAG);
00598     else
00599       std::cerr << "**** NOOP ****\n";
00600   }
00601 }
00602 
00603 
00604 /// Run - perform scheduling.
00605 ///
00606 MachineBasicBlock *ScheduleDAG::Run() {
00607   TII = TM.getInstrInfo();
00608   MRI = TM.getRegisterInfo();
00609   RegMap = BB->getParent()->getSSARegMap();
00610   ConstPool = BB->getParent()->getConstantPool();
00611 
00612   Schedule();
00613   return BB;
00614 }
00615 
00616 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
00617 /// a group of nodes flagged together.
00618 void SUnit::dump(const SelectionDAG *G) const {
00619   std::cerr << "SU(" << NodeNum << "): ";
00620   Node->dump(G);
00621   std::cerr << "\n";
00622   if (FlaggedNodes.size() != 0) {
00623     for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
00624       std::cerr << "    ";
00625       FlaggedNodes[i]->dump(G);
00626       std::cerr << "\n";
00627     }
00628   }
00629 }
00630 
00631 void SUnit::dumpAll(const SelectionDAG *G) const {
00632   dump(G);
00633 
00634   std::cerr << "  # preds left       : " << NumPredsLeft << "\n";
00635   std::cerr << "  # succs left       : " << NumSuccsLeft << "\n";
00636   std::cerr << "  # chain preds left : " << NumChainPredsLeft << "\n";
00637   std::cerr << "  # chain succs left : " << NumChainSuccsLeft << "\n";
00638   std::cerr << "  Latency            : " << Latency << "\n";
00639   std::cerr << "  Depth              : " << Depth << "\n";
00640   std::cerr << "  Height             : " << Height << "\n";
00641 
00642   if (Preds.size() != 0) {
00643     std::cerr << "  Predecessors:\n";
00644     for (std::set<std::pair<SUnit*,bool> >::const_iterator I = Preds.begin(),
00645            E = Preds.end(); I != E; ++I) {
00646       if (I->second)
00647         std::cerr << "   ch  ";
00648       else
00649         std::cerr << "   val ";
00650       I->first->dump(G);
00651     }
00652   }
00653   if (Succs.size() != 0) {
00654     std::cerr << "  Successors:\n";
00655     for (std::set<std::pair<SUnit*, bool> >::const_iterator I = Succs.begin(),
00656            E = Succs.end(); I != E; ++I) {
00657       if (I->second)
00658         std::cerr << "   ch  ";
00659       else
00660         std::cerr << "   val ";
00661       I->first->dump(G);
00662     }
00663   }
00664   std::cerr << "\n";
00665 }