LLVM API Documentation
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 }