ScheduleDAGSDNodes.cpp revision 84023e0fbefc406a4c611d3d64a10df5d3a97dd7
1//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the ScheduleDAG class, which is a base class used by 11// scheduling implementation classes. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "pre-RA-sched" 16#include "SDNodeDbgValue.h" 17#include "ScheduleDAGSDNodes.h" 18#include "InstrEmitter.h" 19#include "llvm/CodeGen/SelectionDAG.h" 20#include "llvm/Target/TargetMachine.h" 21#include "llvm/Target/TargetInstrInfo.h" 22#include "llvm/Target/TargetLowering.h" 23#include "llvm/Target/TargetRegisterInfo.h" 24#include "llvm/Target/TargetSubtarget.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include "llvm/ADT/SmallSet.h" 28#include "llvm/ADT/SmallVector.h" 29#include "llvm/ADT/Statistic.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/raw_ostream.h" 32using namespace llvm; 33 34STATISTIC(LoadsClustered, "Number of loads clustered together"); 35 36ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 37 : ScheduleDAG(mf) { 38} 39 40/// Run - perform scheduling. 41/// 42void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 43 MachineBasicBlock::iterator insertPos) { 44 DAG = dag; 45 ScheduleDAG::Run(bb, insertPos); 46} 47 48/// NewSUnit - Creates a new SUnit and return a ptr to it. 49/// 50SUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) { 51#ifndef NDEBUG 52 const SUnit *Addr = 0; 53 if (!SUnits.empty()) 54 Addr = &SUnits[0]; 55#endif 56 SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 57 assert((Addr == 0 || Addr == &SUnits[0]) && 58 "SUnits std::vector reallocated on the fly!"); 59 SUnits.back().OrigNode = &SUnits.back(); 60 SUnit *SU = &SUnits.back(); 61 const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 62 if (N->isMachineOpcode() && 63 N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) 64 SU->SchedulingPref = Sched::None; 65 else 66 SU->SchedulingPref = TLI.getSchedulingPreference(N); 67 return SU; 68} 69 70SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 71 SUnit *SU = NewSUnit(Old->getNode()); 72 SU->OrigNode = Old->OrigNode; 73 SU->Latency = Old->Latency; 74 SU->isTwoAddress = Old->isTwoAddress; 75 SU->isCommutable = Old->isCommutable; 76 SU->hasPhysRegDefs = Old->hasPhysRegDefs; 77 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 78 SU->SchedulingPref = Old->SchedulingPref; 79 Old->isCloned = true; 80 return SU; 81} 82 83/// CheckForPhysRegDependency - Check if the dependency between def and use of 84/// a specified operand is a physical register dependency. If so, returns the 85/// register and the cost of copying the register. 86static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 87 const TargetRegisterInfo *TRI, 88 const TargetInstrInfo *TII, 89 unsigned &PhysReg, int &Cost) { 90 if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 91 return; 92 93 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 94 if (TargetRegisterInfo::isVirtualRegister(Reg)) 95 return; 96 97 unsigned ResNo = User->getOperand(2).getResNo(); 98 if (Def->isMachineOpcode()) { 99 const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 100 if (ResNo >= II.getNumDefs() && 101 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 102 PhysReg = Reg; 103 const TargetRegisterClass *RC = 104 TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 105 Cost = RC->getCopyCost(); 106 } 107 } 108} 109 110static void AddFlags(SDNode *N, SDValue Flag, bool AddFlag, 111 SelectionDAG *DAG) { 112 SmallVector<EVT, 4> VTs; 113 SDNode *FlagDestNode = Flag.getNode(); 114 115 // Don't add a flag from a node to itself. 116 if (FlagDestNode == N) return; 117 118 // Don't add a flag to something which already has a flag. 119 if (N->getValueType(N->getNumValues() - 1) == MVT::Flag) return; 120 121 for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 122 VTs.push_back(N->getValueType(I)); 123 124 if (AddFlag) 125 VTs.push_back(MVT::Flag); 126 127 SmallVector<SDValue, 4> Ops; 128 for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 129 Ops.push_back(N->getOperand(I)); 130 131 if (FlagDestNode) 132 Ops.push_back(Flag); 133 134 SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 135 MachineSDNode::mmo_iterator Begin = 0, End = 0; 136 MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 137 138 // Store memory references. 139 if (MN) { 140 Begin = MN->memoperands_begin(); 141 End = MN->memoperands_end(); 142 } 143 144 DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 145 146 // Reset the memory references 147 if (MN) 148 MN->setMemRefs(Begin, End); 149} 150 151/// ClusterNeighboringLoads - Force nearby loads together by "flagging" them. 152/// This function finds loads of the same base and different offsets. If the 153/// offsets are not far apart (target specific), it add MVT::Flag inputs and 154/// outputs to ensure they are scheduled together and in order. This 155/// optimization may benefit some targets by improving cache locality. 156void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 157 SDNode *Chain = 0; 158 unsigned NumOps = Node->getNumOperands(); 159 if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 160 Chain = Node->getOperand(NumOps-1).getNode(); 161 if (!Chain) 162 return; 163 164 // Look for other loads of the same chain. Find loads that are loading from 165 // the same base pointer and different offsets. 166 SmallPtrSet<SDNode*, 16> Visited; 167 SmallVector<int64_t, 4> Offsets; 168 DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 169 bool Cluster = false; 170 SDNode *Base = Node; 171 for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 172 I != E; ++I) { 173 SDNode *User = *I; 174 if (User == Node || !Visited.insert(User)) 175 continue; 176 int64_t Offset1, Offset2; 177 if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 178 Offset1 == Offset2) 179 // FIXME: Should be ok if they addresses are identical. But earlier 180 // optimizations really should have eliminated one of the loads. 181 continue; 182 if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 183 Offsets.push_back(Offset1); 184 O2SMap.insert(std::make_pair(Offset2, User)); 185 Offsets.push_back(Offset2); 186 if (Offset2 < Offset1) 187 Base = User; 188 Cluster = true; 189 } 190 191 if (!Cluster) 192 return; 193 194 // Sort them in increasing order. 195 std::sort(Offsets.begin(), Offsets.end()); 196 197 // Check if the loads are close enough. 198 SmallVector<SDNode*, 4> Loads; 199 unsigned NumLoads = 0; 200 int64_t BaseOff = Offsets[0]; 201 SDNode *BaseLoad = O2SMap[BaseOff]; 202 Loads.push_back(BaseLoad); 203 for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 204 int64_t Offset = Offsets[i]; 205 SDNode *Load = O2SMap[Offset]; 206 if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 207 break; // Stop right here. Ignore loads that are further away. 208 Loads.push_back(Load); 209 ++NumLoads; 210 } 211 212 if (NumLoads == 0) 213 return; 214 215 // Cluster loads by adding MVT::Flag outputs and inputs. This also 216 // ensure they are scheduled in order of increasing addresses. 217 SDNode *Lead = Loads[0]; 218 AddFlags(Lead, SDValue(0, 0), true, DAG); 219 220 SDValue InFlag = SDValue(Lead, Lead->getNumValues() - 1); 221 for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 222 bool OutFlag = I < E - 1; 223 SDNode *Load = Loads[I]; 224 225 AddFlags(Load, InFlag, OutFlag, DAG); 226 227 if (OutFlag) 228 InFlag = SDValue(Load, Load->getNumValues() - 1); 229 230 ++LoadsClustered; 231 } 232} 233 234/// ClusterNodes - Cluster certain nodes which should be scheduled together. 235/// 236void ScheduleDAGSDNodes::ClusterNodes() { 237 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 238 E = DAG->allnodes_end(); NI != E; ++NI) { 239 SDNode *Node = &*NI; 240 if (!Node || !Node->isMachineOpcode()) 241 continue; 242 243 unsigned Opc = Node->getMachineOpcode(); 244 const TargetInstrDesc &TID = TII->get(Opc); 245 if (TID.mayLoad()) 246 // Cluster loads from "near" addresses into combined SUnits. 247 ClusterNeighboringLoads(Node); 248 } 249} 250 251void ScheduleDAGSDNodes::BuildSchedUnits() { 252 // During scheduling, the NodeId field of SDNode is used to map SDNodes 253 // to their associated SUnits by holding SUnits table indices. A value 254 // of -1 means the SDNode does not yet have an associated SUnit. 255 unsigned NumNodes = 0; 256 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 257 E = DAG->allnodes_end(); NI != E; ++NI) { 258 NI->setNodeId(-1); 259 ++NumNodes; 260 } 261 262 // Reserve entries in the vector for each of the SUnits we are creating. This 263 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 264 // invalidated. 265 // FIXME: Multiply by 2 because we may clone nodes during scheduling. 266 // This is a temporary workaround. 267 SUnits.reserve(NumNodes * 2); 268 269 // Add all nodes in depth first order. 270 SmallVector<SDNode*, 64> Worklist; 271 SmallPtrSet<SDNode*, 64> Visited; 272 Worklist.push_back(DAG->getRoot().getNode()); 273 Visited.insert(DAG->getRoot().getNode()); 274 275 while (!Worklist.empty()) { 276 SDNode *NI = Worklist.pop_back_val(); 277 278 // Add all operands to the worklist unless they've already been added. 279 for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 280 if (Visited.insert(NI->getOperand(i).getNode())) 281 Worklist.push_back(NI->getOperand(i).getNode()); 282 283 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 284 continue; 285 286 // If this node has already been processed, stop now. 287 if (NI->getNodeId() != -1) continue; 288 289 SUnit *NodeSUnit = NewSUnit(NI); 290 291 // See if anything is flagged to this node, if so, add them to flagged 292 // nodes. Nodes can have at most one flag input and one flag output. Flags 293 // are required to be the last operand and result of a node. 294 295 // Scan up to find flagged preds. 296 SDNode *N = NI; 297 while (N->getNumOperands() && 298 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 299 N = N->getOperand(N->getNumOperands()-1).getNode(); 300 assert(N->getNodeId() == -1 && "Node already inserted!"); 301 N->setNodeId(NodeSUnit->NodeNum); 302 } 303 304 // Scan down to find any flagged succs. 305 N = NI; 306 while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 307 SDValue FlagVal(N, N->getNumValues()-1); 308 309 // There are either zero or one users of the Flag result. 310 bool HasFlagUse = false; 311 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 312 UI != E; ++UI) 313 if (FlagVal.isOperandOf(*UI)) { 314 HasFlagUse = true; 315 assert(N->getNodeId() == -1 && "Node already inserted!"); 316 N->setNodeId(NodeSUnit->NodeNum); 317 N = *UI; 318 break; 319 } 320 if (!HasFlagUse) break; 321 } 322 323 // If there are flag operands involved, N is now the bottom-most node 324 // of the sequence of nodes that are flagged together. 325 // Update the SUnit. 326 NodeSUnit->setNode(N); 327 assert(N->getNodeId() == -1 && "Node already inserted!"); 328 N->setNodeId(NodeSUnit->NodeNum); 329 330 // Assign the Latency field of NodeSUnit using target-provided information. 331 ComputeLatency(NodeSUnit); 332 } 333} 334 335void ScheduleDAGSDNodes::AddSchedEdges() { 336 const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 337 338 // Check to see if the scheduler cares about latencies. 339 bool UnitLatencies = ForceUnitLatencies(); 340 341 // Pass 2: add the preds, succs, etc. 342 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 343 SUnit *SU = &SUnits[su]; 344 SDNode *MainNode = SU->getNode(); 345 346 if (MainNode->isMachineOpcode()) { 347 unsigned Opc = MainNode->getMachineOpcode(); 348 const TargetInstrDesc &TID = TII->get(Opc); 349 for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 350 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 351 SU->isTwoAddress = true; 352 break; 353 } 354 } 355 if (TID.isCommutable()) 356 SU->isCommutable = true; 357 } 358 359 // Find all predecessors and successors of the group. 360 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 361 if (N->isMachineOpcode() && 362 TII->get(N->getMachineOpcode()).getImplicitDefs()) { 363 SU->hasPhysRegClobbers = true; 364 unsigned NumUsed = InstrEmitter::CountResults(N); 365 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 366 --NumUsed; // Skip over unused values at the end. 367 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 368 SU->hasPhysRegDefs = true; 369 } 370 371 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 372 SDNode *OpN = N->getOperand(i).getNode(); 373 if (isPassiveNode(OpN)) continue; // Not scheduled. 374 SUnit *OpSU = &SUnits[OpN->getNodeId()]; 375 assert(OpSU && "Node has no SUnit!"); 376 if (OpSU == SU) continue; // In the same group. 377 378 EVT OpVT = N->getOperand(i).getValueType(); 379 assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 380 bool isChain = OpVT == MVT::Other; 381 382 unsigned PhysReg = 0; 383 int Cost = 1; 384 // Determine if this is a physical register dependency. 385 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 386 assert((PhysReg == 0 || !isChain) && 387 "Chain dependence via physreg data?"); 388 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 389 // emits a copy from the physical register to a virtual register unless 390 // it requires a cross class copy (cost < 0). That means we are only 391 // treating "expensive to copy" register dependency as physical register 392 // dependency. This may change in the future though. 393 if (Cost >= 0) 394 PhysReg = 0; 395 396 // If this is a ctrl dep, latency is 1. 397 unsigned OpLatency = isChain ? 1 : OpSU->Latency; 398 const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 399 OpLatency, PhysReg); 400 if (!isChain && !UnitLatencies) { 401 ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep)); 402 ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep)); 403 } 404 405 SU->addPred(dep); 406 } 407 } 408 } 409} 410 411/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 412/// are input. This SUnit graph is similar to the SelectionDAG, but 413/// excludes nodes that aren't interesting to scheduling, and represents 414/// flagged together nodes with a single SUnit. 415void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 416 // Cluster certain nodes which should be scheduled together. 417 ClusterNodes(); 418 // Populate the SUnits array. 419 BuildSchedUnits(); 420 // Compute all the scheduling dependencies between nodes. 421 AddSchedEdges(); 422} 423 424void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 425 // Check to see if the scheduler cares about latencies. 426 if (ForceUnitLatencies()) { 427 SU->Latency = 1; 428 return; 429 } 430 431 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 432 if (InstrItins.isEmpty()) { 433 SU->Latency = 1; 434 return; 435 } 436 437 // Compute the latency for the node. We use the sum of the latencies for 438 // all nodes flagged together into this SUnit. 439 SU->Latency = 0; 440 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 441 if (N->isMachineOpcode()) { 442 SU->Latency += InstrItins. 443 getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 444 } 445} 446 447void ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use, 448 unsigned OpIdx, SDep& dep) const{ 449 // Check to see if the scheduler cares about latencies. 450 if (ForceUnitLatencies()) 451 return; 452 453 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 454 if (InstrItins.isEmpty()) 455 return; 456 457 if (dep.getKind() != SDep::Data) 458 return; 459 460 unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 461 if (Def->isMachineOpcode()) { 462 const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 463 if (DefIdx >= II.getNumDefs()) 464 return; 465 int DefCycle = InstrItins.getOperandCycle(II.getSchedClass(), DefIdx); 466 if (DefCycle < 0) 467 return; 468 int UseCycle = 1; 469 if (Use->isMachineOpcode()) { 470 const unsigned UseClass = TII->get(Use->getMachineOpcode()).getSchedClass(); 471 UseCycle = InstrItins.getOperandCycle(UseClass, OpIdx); 472 } 473 if (UseCycle >= 0) { 474 int Latency = DefCycle - UseCycle + 1; 475 if (Latency >= 0) 476 dep.setLatency(Latency); 477 } 478 } 479} 480 481void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 482 if (!SU->getNode()) { 483 dbgs() << "PHYS REG COPY\n"; 484 return; 485 } 486 487 SU->getNode()->dump(DAG); 488 dbgs() << "\n"; 489 SmallVector<SDNode *, 4> FlaggedNodes; 490 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 491 FlaggedNodes.push_back(N); 492 while (!FlaggedNodes.empty()) { 493 dbgs() << " "; 494 FlaggedNodes.back()->dump(DAG); 495 dbgs() << "\n"; 496 FlaggedNodes.pop_back(); 497 } 498} 499 500namespace { 501 struct OrderSorter { 502 bool operator()(const std::pair<unsigned, MachineInstr*> &A, 503 const std::pair<unsigned, MachineInstr*> &B) { 504 return A.first < B.first; 505 } 506 }; 507} 508 509// ProcessSourceNode - Process nodes with source order numbers. These are added 510// to a vector which EmitSchedule uses to determine how to insert dbg_value 511// instructions in the right order. 512static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, 513 InstrEmitter &Emitter, 514 DenseMap<SDValue, unsigned> &VRBaseMap, 515 SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 516 SmallSet<unsigned, 8> &Seen) { 517 unsigned Order = DAG->GetOrdering(N); 518 if (!Order || !Seen.insert(Order)) 519 return; 520 521 MachineBasicBlock *BB = Emitter.getBlock(); 522 if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { 523 // Did not insert any instruction. 524 Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 525 return; 526 } 527 528 Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 529 if (!N->getHasDebugValue()) 530 return; 531 // Opportunistically insert immediate dbg_value uses, i.e. those with source 532 // order number right after the N. 533 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 534 SmallVector<SDDbgValue*,2> &DVs = DAG->GetDbgValues(N); 535 for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 536 if (DVs[i]->isInvalidated()) 537 continue; 538 unsigned DVOrder = DVs[i]->getOrder(); 539 if (DVOrder == ++Order) { 540 MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 541 if (DbgMI) { 542 Orders.push_back(std::make_pair(DVOrder, DbgMI)); 543 BB->insert(InsertPos, DbgMI); 544 } 545 DVs[i]->setIsInvalidated(); 546 } 547 } 548} 549 550 551/// EmitSchedule - Emit the machine code in scheduled order. 552MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { 553 InstrEmitter Emitter(BB, InsertPos); 554 DenseMap<SDValue, unsigned> VRBaseMap; 555 DenseMap<SUnit*, unsigned> CopyVRBaseMap; 556 SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 557 SmallSet<unsigned, 8> Seen; 558 bool HasDbg = DAG->hasDebugValues(); 559 560 // If this is the first BB, emit byval parameter dbg_value's. 561 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 562 SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 563 SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 564 for (; PDI != PDE; ++PDI) { 565 MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 566 if (DbgMI) 567 BB->insert(InsertPos, DbgMI); 568 } 569 } 570 571 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 572 SUnit *SU = Sequence[i]; 573 if (!SU) { 574 // Null SUnit* is a noop. 575 EmitNoop(); 576 continue; 577 } 578 579 // For pre-regalloc scheduling, create instructions corresponding to the 580 // SDNode and any flagged SDNodes and append them to the block. 581 if (!SU->getNode()) { 582 // Emit a copy. 583 EmitPhysRegCopy(SU, CopyVRBaseMap); 584 continue; 585 } 586 587 SmallVector<SDNode *, 4> FlaggedNodes; 588 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; 589 N = N->getFlaggedNode()) 590 FlaggedNodes.push_back(N); 591 while (!FlaggedNodes.empty()) { 592 SDNode *N = FlaggedNodes.back(); 593 Emitter.EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned, 594 VRBaseMap); 595 // Remember the source order of the inserted instruction. 596 if (HasDbg) 597 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 598 FlaggedNodes.pop_back(); 599 } 600 Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 601 VRBaseMap); 602 // Remember the source order of the inserted instruction. 603 if (HasDbg) 604 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 605 Seen); 606 } 607 608 // Insert all the dbg_values which have not already been inserted in source 609 // order sequence. 610 if (HasDbg) { 611 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 612 613 // Sort the source order instructions and use the order to insert debug 614 // values. 615 std::sort(Orders.begin(), Orders.end(), OrderSorter()); 616 617 SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 618 SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 619 // Now emit the rest according to source order. 620 unsigned LastOrder = 0; 621 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 622 unsigned Order = Orders[i].first; 623 MachineInstr *MI = Orders[i].second; 624 // Insert all SDDbgValue's whose order(s) are before "Order". 625 if (!MI) 626 continue; 627#ifndef NDEBUG 628 unsigned LastDIOrder = 0; 629#endif 630 for (; DI != DE && 631 (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 632#ifndef NDEBUG 633 assert((*DI)->getOrder() >= LastDIOrder && 634 "SDDbgValue nodes must be in source order!"); 635 LastDIOrder = (*DI)->getOrder(); 636#endif 637 if ((*DI)->isInvalidated()) 638 continue; 639 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 640 if (DbgMI) { 641 if (!LastOrder) 642 // Insert to start of the BB (after PHIs). 643 BB->insert(BBBegin, DbgMI); 644 else { 645 MachineBasicBlock::iterator Pos = MI; 646 BB->insert(llvm::next(Pos), DbgMI); 647 } 648 } 649 } 650 LastOrder = Order; 651 } 652 // Add trailing DbgValue's before the terminator. FIXME: May want to add 653 // some of them before one or more conditional branches? 654 while (DI != DE) { 655 MachineBasicBlock *InsertBB = Emitter.getBlock(); 656 MachineBasicBlock::iterator Pos= Emitter.getBlock()->getFirstTerminator(); 657 if (!(*DI)->isInvalidated()) { 658 MachineInstr *DbgMI= Emitter.EmitDbgValue(*DI, VRBaseMap); 659 if (DbgMI) 660 InsertBB->insert(Pos, DbgMI); 661 } 662 ++DI; 663 } 664 } 665 666 BB = Emitter.getBlock(); 667 InsertPos = Emitter.getInsertPos(); 668 return BB; 669} 670