ScheduleDAGInstrs.cpp revision 205218
1//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// 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 ScheduleDAGInstrs class, which implements re-scheduling 11// of MachineInstrs. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "sched-instrs" 16#include "ScheduleDAGInstrs.h" 17#include "llvm/Operator.h" 18#include "llvm/Analysis/AliasAnalysis.h" 19#include "llvm/CodeGen/MachineFunctionPass.h" 20#include "llvm/CodeGen/MachineMemOperand.h" 21#include "llvm/CodeGen/MachineRegisterInfo.h" 22#include "llvm/CodeGen/PseudoSourceValue.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/Target/TargetInstrInfo.h" 25#include "llvm/Target/TargetRegisterInfo.h" 26#include "llvm/Target/TargetSubtarget.h" 27#include "llvm/Support/Debug.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/ADT/SmallSet.h" 30using namespace llvm; 31 32ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 33 const MachineLoopInfo &mli, 34 const MachineDominatorTree &mdt) 35 : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) { 36 MFI = mf.getFrameInfo(); 37 DbgValueVec.clear(); 38} 39 40/// Run - perform scheduling. 41/// 42void ScheduleDAGInstrs::Run(MachineBasicBlock *bb, 43 MachineBasicBlock::iterator begin, 44 MachineBasicBlock::iterator end, 45 unsigned endcount) { 46 BB = bb; 47 Begin = begin; 48 InsertPosIndex = endcount; 49 50 ScheduleDAG::Run(bb, end); 51} 52 53/// getUnderlyingObjectFromInt - This is the function that does the work of 54/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 55static const Value *getUnderlyingObjectFromInt(const Value *V) { 56 do { 57 if (const Operator *U = dyn_cast<Operator>(V)) { 58 // If we find a ptrtoint, we can transfer control back to the 59 // regular getUnderlyingObjectFromInt. 60 if (U->getOpcode() == Instruction::PtrToInt) 61 return U->getOperand(0); 62 // If we find an add of a constant or a multiplied value, it's 63 // likely that the other operand will lead us to the base 64 // object. We don't have to worry about the case where the 65 // object address is somehow being computed by the multiply, 66 // because our callers only care when the result is an 67 // identifibale object. 68 if (U->getOpcode() != Instruction::Add || 69 (!isa<ConstantInt>(U->getOperand(1)) && 70 Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) 71 return V; 72 V = U->getOperand(0); 73 } else { 74 return V; 75 } 76 assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 77 } while (1); 78} 79 80/// getUnderlyingObject - This is a wrapper around Value::getUnderlyingObject 81/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 82static const Value *getUnderlyingObject(const Value *V) { 83 // First just call Value::getUnderlyingObject to let it do what it does. 84 do { 85 V = V->getUnderlyingObject(); 86 // If it found an inttoptr, use special code to continue climing. 87 if (Operator::getOpcode(V) != Instruction::IntToPtr) 88 break; 89 const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 90 // If that succeeded in finding a pointer, continue the search. 91 if (!O->getType()->isPointerTy()) 92 break; 93 V = O; 94 } while (1); 95 return V; 96} 97 98/// getUnderlyingObjectForInstr - If this machine instr has memory reference 99/// information and it can be tracked to a normal reference to a known 100/// object, return the Value for that object. Otherwise return null. 101static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, 102 const MachineFrameInfo *MFI, 103 bool &MayAlias) { 104 MayAlias = true; 105 if (!MI->hasOneMemOperand() || 106 !(*MI->memoperands_begin())->getValue() || 107 (*MI->memoperands_begin())->isVolatile()) 108 return 0; 109 110 const Value *V = (*MI->memoperands_begin())->getValue(); 111 if (!V) 112 return 0; 113 114 V = getUnderlyingObject(V); 115 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 116 // For now, ignore PseudoSourceValues which may alias LLVM IR values 117 // because the code that uses this function has no way to cope with 118 // such aliases. 119 if (PSV->isAliased(MFI)) 120 return 0; 121 122 MayAlias = PSV->mayAlias(MFI); 123 return V; 124 } 125 126 if (isIdentifiedObject(V)) 127 return V; 128 129 return 0; 130} 131 132void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { 133 if (MachineLoop *ML = MLI.getLoopFor(BB)) 134 if (BB == ML->getLoopLatch()) { 135 MachineBasicBlock *Header = ML->getHeader(); 136 for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), 137 E = Header->livein_end(); I != E; ++I) 138 LoopLiveInRegs.insert(*I); 139 LoopRegs.VisitLoop(ML); 140 } 141} 142 143void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { 144 // We'll be allocating one SUnit for each instruction, plus one for 145 // the region exit node. 146 SUnits.reserve(BB->size()); 147 148 // We build scheduling units by walking a block's instruction list from bottom 149 // to top. 150 151 // Remember where a generic side-effecting instruction is as we procede. 152 SUnit *BarrierChain = 0, *AliasChain = 0; 153 154 // Memory references to specific known memory locations are tracked 155 // so that they can be given more precise dependencies. We track 156 // separately the known memory locations that may alias and those 157 // that are known not to alias 158 std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; 159 std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 160 161 // Keep track of dangling debug references to registers. 162 std::pair<MachineInstr*, unsigned> 163 DanglingDebugValue[TargetRegisterInfo::FirstVirtualRegister]; 164 165 // Check to see if the scheduler cares about latencies. 166 bool UnitLatencies = ForceUnitLatencies(); 167 168 // Ask the target if address-backscheduling is desirable, and if so how much. 169 const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 170 unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 171 172 // Remove any stale debug info; sometimes BuildSchedGraph is called again 173 // without emitting the info from the previous call. 174 DbgValueVec.clear(); 175 std::memset(DanglingDebugValue, 0, sizeof(DanglingDebugValue)); 176 177 // Walk the list of instructions, from bottom moving up. 178 for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; 179 MII != MIE; --MII) { 180 MachineInstr *MI = prior(MII); 181 // DBG_VALUE does not have SUnit's built, so just remember these for later 182 // reinsertion. 183 if (MI->isDebugValue()) { 184 if (MI->getNumOperands()==3 && MI->getOperand(0).isReg() && 185 MI->getOperand(0).getReg()) 186 DanglingDebugValue[MI->getOperand(0).getReg()] = 187 std::make_pair(MI, DbgValueVec.size()); 188 DbgValueVec.push_back(MI); 189 continue; 190 } 191 const TargetInstrDesc &TID = MI->getDesc(); 192 assert(!TID.isTerminator() && !MI->isLabel() && 193 "Cannot schedule terminators or labels!"); 194 // Create the SUnit for this MI. 195 SUnit *SU = NewSUnit(MI); 196 197 // Assign the Latency field of SU using target-provided information. 198 if (UnitLatencies) 199 SU->Latency = 1; 200 else 201 ComputeLatency(SU); 202 203 // Add register-based dependencies (data, anti, and output). 204 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 205 const MachineOperand &MO = MI->getOperand(j); 206 if (!MO.isReg()) continue; 207 unsigned Reg = MO.getReg(); 208 if (Reg == 0) continue; 209 210 assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); 211 212 if (MO.isDef() && DanglingDebugValue[Reg].first!=0) { 213 SU->setDbgInstr(DanglingDebugValue[Reg].first); 214 DbgValueVec[DanglingDebugValue[Reg].second] = 0; 215 DanglingDebugValue[Reg] = std::make_pair((MachineInstr*)0, 0); 216 } 217 218 std::vector<SUnit *> &UseList = Uses[Reg]; 219 std::vector<SUnit *> &DefList = Defs[Reg]; 220 // Optionally add output and anti dependencies. For anti 221 // dependencies we use a latency of 0 because for a multi-issue 222 // target we want to allow the defining instruction to issue 223 // in the same cycle as the using instruction. 224 // TODO: Using a latency of 1 here for output dependencies assumes 225 // there's no cost for reusing registers. 226 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 227 unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1; 228 for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 229 SUnit *DefSU = DefList[i]; 230 if (DefSU != SU && 231 (Kind != SDep::Output || !MO.isDead() || 232 !DefSU->getInstr()->registerDefIsDead(Reg))) 233 DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg)); 234 } 235 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 236 std::vector<SUnit *> &DefList = Defs[*Alias]; 237 for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 238 SUnit *DefSU = DefList[i]; 239 if (DefSU != SU && 240 (Kind != SDep::Output || !MO.isDead() || 241 !DefSU->getInstr()->registerDefIsDead(*Alias))) 242 DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias)); 243 } 244 } 245 246 if (MO.isDef()) { 247 // Add any data dependencies. 248 unsigned DataLatency = SU->Latency; 249 for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 250 SUnit *UseSU = UseList[i]; 251 if (UseSU != SU) { 252 unsigned LDataLatency = DataLatency; 253 // Optionally add in a special extra latency for nodes that 254 // feed addresses. 255 // TODO: Do this for register aliases too. 256 // TODO: Perhaps we should get rid of 257 // SpecialAddressLatency and just move this into 258 // adjustSchedDependency for the targets that care about 259 // it. 260 if (SpecialAddressLatency != 0 && !UnitLatencies) { 261 MachineInstr *UseMI = UseSU->getInstr(); 262 const TargetInstrDesc &UseTID = UseMI->getDesc(); 263 int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg); 264 assert(RegUseIndex >= 0 && "UseMI doesn's use register!"); 265 if ((UseTID.mayLoad() || UseTID.mayStore()) && 266 (unsigned)RegUseIndex < UseTID.getNumOperands() && 267 UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 268 LDataLatency += SpecialAddressLatency; 269 } 270 // Adjust the dependence latency using operand def/use 271 // information (if any), and then allow the target to 272 // perform its own adjustments. 273 const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg); 274 if (!UnitLatencies) { 275 ComputeOperandLatency(SU, UseSU, (SDep &)dep); 276 ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 277 } 278 UseSU->addPred(dep); 279 } 280 } 281 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 282 std::vector<SUnit *> &UseList = Uses[*Alias]; 283 for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 284 SUnit *UseSU = UseList[i]; 285 if (UseSU != SU) { 286 const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias); 287 if (!UnitLatencies) { 288 ComputeOperandLatency(SU, UseSU, (SDep &)dep); 289 ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 290 } 291 UseSU->addPred(dep); 292 } 293 } 294 } 295 296 // If a def is going to wrap back around to the top of the loop, 297 // backschedule it. 298 if (!UnitLatencies && DefList.empty()) { 299 LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg); 300 if (I != LoopRegs.Deps.end()) { 301 const MachineOperand *UseMO = I->second.first; 302 unsigned Count = I->second.second; 303 const MachineInstr *UseMI = UseMO->getParent(); 304 unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 305 const TargetInstrDesc &UseTID = UseMI->getDesc(); 306 // TODO: If we knew the total depth of the region here, we could 307 // handle the case where the whole loop is inside the region but 308 // is large enough that the isScheduleHigh trick isn't needed. 309 if (UseMOIdx < UseTID.getNumOperands()) { 310 // Currently, we only support scheduling regions consisting of 311 // single basic blocks. Check to see if the instruction is in 312 // the same region by checking to see if it has the same parent. 313 if (UseMI->getParent() != MI->getParent()) { 314 unsigned Latency = SU->Latency; 315 if (UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 316 Latency += SpecialAddressLatency; 317 // This is a wild guess as to the portion of the latency which 318 // will be overlapped by work done outside the current 319 // scheduling region. 320 Latency -= std::min(Latency, Count); 321 // Add the artifical edge. 322 ExitSU.addPred(SDep(SU, SDep::Order, Latency, 323 /*Reg=*/0, /*isNormalMemory=*/false, 324 /*isMustAlias=*/false, 325 /*isArtificial=*/true)); 326 } else if (SpecialAddressLatency > 0 && 327 UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 328 // The entire loop body is within the current scheduling region 329 // and the latency of this operation is assumed to be greater 330 // than the latency of the loop. 331 // TODO: Recursively mark data-edge predecessors as 332 // isScheduleHigh too. 333 SU->isScheduleHigh = true; 334 } 335 } 336 LoopRegs.Deps.erase(I); 337 } 338 } 339 340 UseList.clear(); 341 if (!MO.isDead()) 342 DefList.clear(); 343 DefList.push_back(SU); 344 } else { 345 UseList.push_back(SU); 346 } 347 } 348 349 // Add chain dependencies. 350 // Chain dependencies used to enforce memory order should have 351 // latency of 0 (except for true dependency of Store followed by 352 // aliased Load... we estimate that with a single cycle of latency 353 // assuming the hardware will bypass) 354 // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 355 // after stack slots are lowered to actual addresses. 356 // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 357 // produce more precise dependence information. 358#define STORE_LOAD_LATENCY 1 359 unsigned TrueMemOrderLatency = 0; 360 if (TID.isCall() || TID.hasUnmodeledSideEffects() || 361 (MI->hasVolatileMemoryRef() && 362 (!TID.mayLoad() || !MI->isInvariantLoad(AA)))) { 363 // Be conservative with these and add dependencies on all memory 364 // references, even those that are known to not alias. 365 for (std::map<const Value *, SUnit *>::iterator I = 366 NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 367 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 368 } 369 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 370 NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 371 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 372 I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 373 } 374 NonAliasMemDefs.clear(); 375 NonAliasMemUses.clear(); 376 // Add SU to the barrier chain. 377 if (BarrierChain) 378 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 379 BarrierChain = SU; 380 381 // fall-through 382 new_alias_chain: 383 // Chain all possibly aliasing memory references though SU. 384 if (AliasChain) 385 AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 386 AliasChain = SU; 387 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 388 PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 389 for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), 390 E = AliasMemDefs.end(); I != E; ++I) { 391 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 392 } 393 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 394 AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 395 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 396 I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 397 } 398 PendingLoads.clear(); 399 AliasMemDefs.clear(); 400 AliasMemUses.clear(); 401 } else if (TID.mayStore()) { 402 bool MayAlias = true; 403 TrueMemOrderLatency = STORE_LOAD_LATENCY; 404 if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 405 // A store to a specific PseudoSourceValue. Add precise dependencies. 406 // Record the def in MemDefs, first adding a dep if there is 407 // an existing def. 408 std::map<const Value *, SUnit *>::iterator I = 409 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 410 std::map<const Value *, SUnit *>::iterator IE = 411 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 412 if (I != IE) { 413 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 414 /*isNormalMemory=*/true)); 415 I->second = SU; 416 } else { 417 if (MayAlias) 418 AliasMemDefs[V] = SU; 419 else 420 NonAliasMemDefs[V] = SU; 421 } 422 // Handle the uses in MemUses, if there are any. 423 std::map<const Value *, std::vector<SUnit *> >::iterator J = 424 ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 425 std::map<const Value *, std::vector<SUnit *> >::iterator JE = 426 ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 427 if (J != JE) { 428 for (unsigned i = 0, e = J->second.size(); i != e; ++i) 429 J->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency, 430 /*Reg=*/0, /*isNormalMemory=*/true)); 431 J->second.clear(); 432 } 433 if (MayAlias) { 434 // Add dependencies from all the PendingLoads, i.e. loads 435 // with no underlying object. 436 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 437 PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 438 // Add dependence on alias chain, if needed. 439 if (AliasChain) 440 AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 441 } 442 // Add dependence on barrier chain, if needed. 443 if (BarrierChain) 444 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 445 } else { 446 // Treat all other stores conservatively. 447 goto new_alias_chain; 448 } 449 } else if (TID.mayLoad()) { 450 bool MayAlias = true; 451 TrueMemOrderLatency = 0; 452 if (MI->isInvariantLoad(AA)) { 453 // Invariant load, no chain dependencies needed! 454 } else { 455 if (const Value *V = 456 getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 457 // A load from a specific PseudoSourceValue. Add precise dependencies. 458 std::map<const Value *, SUnit *>::iterator I = 459 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 460 std::map<const Value *, SUnit *>::iterator IE = 461 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 462 if (I != IE) 463 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 464 /*isNormalMemory=*/true)); 465 if (MayAlias) 466 AliasMemUses[V].push_back(SU); 467 else 468 NonAliasMemUses[V].push_back(SU); 469 } else { 470 // A load with no underlying object. Depend on all 471 // potentially aliasing stores. 472 for (std::map<const Value *, SUnit *>::iterator I = 473 AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 474 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 475 476 PendingLoads.push_back(SU); 477 MayAlias = true; 478 } 479 480 // Add dependencies on alias and barrier chains, if needed. 481 if (MayAlias && AliasChain) 482 AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 483 if (BarrierChain) 484 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 485 } 486 } 487 } 488 489 for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { 490 Defs[i].clear(); 491 Uses[i].clear(); 492 } 493 PendingLoads.clear(); 494} 495 496void ScheduleDAGInstrs::FinishBlock() { 497 // Nothing to do. 498} 499 500void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { 501 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 502 503 // Compute the latency for the node. 504 SU->Latency = 505 InstrItins.getStageLatency(SU->getInstr()->getDesc().getSchedClass()); 506 507 // Simplistic target-independent heuristic: assume that loads take 508 // extra time. 509 if (InstrItins.isEmpty()) 510 if (SU->getInstr()->getDesc().mayLoad()) 511 SU->Latency += 2; 512} 513 514void ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use, 515 SDep& dep) const { 516 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 517 if (InstrItins.isEmpty()) 518 return; 519 520 // For a data dependency with a known register... 521 if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0)) 522 return; 523 524 const unsigned Reg = dep.getReg(); 525 526 // ... find the definition of the register in the defining 527 // instruction 528 MachineInstr *DefMI = Def->getInstr(); 529 int DefIdx = DefMI->findRegisterDefOperandIdx(Reg); 530 if (DefIdx != -1) { 531 int DefCycle = InstrItins.getOperandCycle(DefMI->getDesc().getSchedClass(), DefIdx); 532 if (DefCycle >= 0) { 533 MachineInstr *UseMI = Use->getInstr(); 534 const unsigned UseClass = UseMI->getDesc().getSchedClass(); 535 536 // For all uses of the register, calculate the maxmimum latency 537 int Latency = -1; 538 for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 539 const MachineOperand &MO = UseMI->getOperand(i); 540 if (!MO.isReg() || !MO.isUse()) 541 continue; 542 unsigned MOReg = MO.getReg(); 543 if (MOReg != Reg) 544 continue; 545 546 int UseCycle = InstrItins.getOperandCycle(UseClass, i); 547 if (UseCycle >= 0) 548 Latency = std::max(Latency, DefCycle - UseCycle + 1); 549 } 550 551 // If we found a latency, then replace the existing dependence latency. 552 if (Latency >= 0) 553 dep.setLatency(Latency); 554 } 555 } 556} 557 558void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 559 SU->getInstr()->dump(); 560} 561 562std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 563 std::string s; 564 raw_string_ostream oss(s); 565 if (SU == &EntrySU) 566 oss << "<entry>"; 567 else if (SU == &ExitSU) 568 oss << "<exit>"; 569 else 570 SU->getInstr()->print(oss); 571 return oss.str(); 572} 573 574// EmitSchedule - Emit the machine code in scheduled order. 575MachineBasicBlock *ScheduleDAGInstrs:: 576EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) { 577 // For MachineInstr-based scheduling, we're rescheduling the instructions in 578 // the block, so start by removing them from the block. 579 while (Begin != InsertPos) { 580 MachineBasicBlock::iterator I = Begin; 581 ++Begin; 582 BB->remove(I); 583 } 584 585 // First reinsert any remaining debug_values; these are either constants, 586 // or refer to live-in registers. The beginning of the block is the right 587 // place for the latter. The former might reasonably be placed elsewhere 588 // using some kind of ordering algorithm, but right now it doesn't matter. 589 for (int i = DbgValueVec.size()-1; i>=0; --i) 590 if (DbgValueVec[i]) 591 BB->insert(InsertPos, DbgValueVec[i]); 592 593 // Then re-insert them according to the given schedule. 594 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 595 SUnit *SU = Sequence[i]; 596 if (!SU) { 597 // Null SUnit* is a noop. 598 EmitNoop(); 599 continue; 600 } 601 602 BB->insert(InsertPos, SU->getInstr()); 603 if (SU->getDbgInstr()) 604 BB->insert(InsertPos, SU->getDbgInstr()); 605 } 606 607 // Update the Begin iterator, as the first instruction in the block 608 // may have been scheduled later. 609 if (!DbgValueVec.empty()) { 610 for (int i = DbgValueVec.size()-1; i>=0; --i) 611 if (DbgValueVec[i]!=0) { 612 Begin = DbgValueVec[DbgValueVec.size()-1]; 613 break; 614 } 615 } else if (!Sequence.empty()) 616 Begin = Sequence[0]->getInstr(); 617 618 DbgValueVec.clear(); 619 return BB; 620} 621