ScheduleDAGInstrs.cpp revision 296417
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#include "llvm/CodeGen/ScheduleDAGInstrs.h" 16#include "llvm/ADT/IntEqClasses.h" 17#include "llvm/ADT/MapVector.h" 18#include "llvm/ADT/SmallPtrSet.h" 19#include "llvm/ADT/SmallSet.h" 20#include "llvm/Analysis/AliasAnalysis.h" 21#include "llvm/Analysis/ValueTracking.h" 22#include "llvm/CodeGen/MachineFunctionPass.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineMemOperand.h" 26#include "llvm/CodeGen/MachineRegisterInfo.h" 27#include "llvm/CodeGen/PseudoSourceValue.h" 28#include "llvm/CodeGen/RegisterPressure.h" 29#include "llvm/CodeGen/ScheduleDFS.h" 30#include "llvm/IR/Operator.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/Support/Format.h" 34#include "llvm/Support/raw_ostream.h" 35#include "llvm/Target/TargetInstrInfo.h" 36#include "llvm/Target/TargetMachine.h" 37#include "llvm/Target/TargetRegisterInfo.h" 38#include "llvm/Target/TargetSubtargetInfo.h" 39#include <queue> 40 41using namespace llvm; 42 43#define DEBUG_TYPE "misched" 44 45static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, 46 cl::ZeroOrMore, cl::init(false), 47 cl::desc("Enable use of AA during MI DAG construction")); 48 49static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, 50 cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction")); 51 52ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 53 const MachineLoopInfo *mli, 54 bool RemoveKillFlags) 55 : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), 56 RemoveKillFlags(RemoveKillFlags), CanHandleTerminators(false), 57 TrackLaneMasks(false), FirstDbgValue(nullptr) { 58 DbgValues.clear(); 59 60 const TargetSubtargetInfo &ST = mf.getSubtarget(); 61 SchedModel.init(ST.getSchedModel(), &ST, TII); 62} 63 64/// getUnderlyingObjectFromInt - This is the function that does the work of 65/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 66static const Value *getUnderlyingObjectFromInt(const Value *V) { 67 do { 68 if (const Operator *U = dyn_cast<Operator>(V)) { 69 // If we find a ptrtoint, we can transfer control back to the 70 // regular getUnderlyingObjectFromInt. 71 if (U->getOpcode() == Instruction::PtrToInt) 72 return U->getOperand(0); 73 // If we find an add of a constant, a multiplied value, or a phi, it's 74 // likely that the other operand will lead us to the base 75 // object. We don't have to worry about the case where the 76 // object address is somehow being computed by the multiply, 77 // because our callers only care when the result is an 78 // identifiable object. 79 if (U->getOpcode() != Instruction::Add || 80 (!isa<ConstantInt>(U->getOperand(1)) && 81 Operator::getOpcode(U->getOperand(1)) != Instruction::Mul && 82 !isa<PHINode>(U->getOperand(1)))) 83 return V; 84 V = U->getOperand(0); 85 } else { 86 return V; 87 } 88 assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 89 } while (1); 90} 91 92/// getUnderlyingObjects - This is a wrapper around GetUnderlyingObjects 93/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 94static void getUnderlyingObjects(const Value *V, 95 SmallVectorImpl<Value *> &Objects, 96 const DataLayout &DL) { 97 SmallPtrSet<const Value *, 16> Visited; 98 SmallVector<const Value *, 4> Working(1, V); 99 do { 100 V = Working.pop_back_val(); 101 102 SmallVector<Value *, 4> Objs; 103 GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL); 104 105 for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), IE = Objs.end(); 106 I != IE; ++I) { 107 V = *I; 108 if (!Visited.insert(V).second) 109 continue; 110 if (Operator::getOpcode(V) == Instruction::IntToPtr) { 111 const Value *O = 112 getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 113 if (O->getType()->isPointerTy()) { 114 Working.push_back(O); 115 continue; 116 } 117 } 118 Objects.push_back(const_cast<Value *>(V)); 119 } 120 } while (!Working.empty()); 121} 122 123typedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType; 124typedef SmallVector<PointerIntPair<ValueType, 1, bool>, 4> 125UnderlyingObjectsVector; 126 127/// getUnderlyingObjectsForInstr - If this machine instr has memory reference 128/// information and it can be tracked to a normal reference to a known 129/// object, return the Value for that object. 130static void getUnderlyingObjectsForInstr(const MachineInstr *MI, 131 const MachineFrameInfo *MFI, 132 UnderlyingObjectsVector &Objects, 133 const DataLayout &DL) { 134 if (!MI->hasOneMemOperand() || 135 (!(*MI->memoperands_begin())->getValue() && 136 !(*MI->memoperands_begin())->getPseudoValue()) || 137 (*MI->memoperands_begin())->isVolatile()) 138 return; 139 140 if (const PseudoSourceValue *PSV = 141 (*MI->memoperands_begin())->getPseudoValue()) { 142 // Function that contain tail calls don't have unique PseudoSourceValue 143 // objects. Two PseudoSourceValues might refer to the same or overlapping 144 // locations. The client code calling this function assumes this is not the 145 // case. So return a conservative answer of no known object. 146 if (MFI->hasTailCall()) 147 return; 148 149 // For now, ignore PseudoSourceValues which may alias LLVM IR values 150 // because the code that uses this function has no way to cope with 151 // such aliases. 152 if (!PSV->isAliased(MFI)) { 153 bool MayAlias = PSV->mayAlias(MFI); 154 Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias)); 155 } 156 return; 157 } 158 159 const Value *V = (*MI->memoperands_begin())->getValue(); 160 if (!V) 161 return; 162 163 SmallVector<Value *, 4> Objs; 164 getUnderlyingObjects(V, Objs, DL); 165 166 for (Value *V : Objs) { 167 if (!isIdentifiedObject(V)) { 168 Objects.clear(); 169 return; 170 } 171 172 Objects.push_back(UnderlyingObjectsVector::value_type(V, true)); 173 } 174} 175 176void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { 177 BB = bb; 178} 179 180void ScheduleDAGInstrs::finishBlock() { 181 // Subclasses should no longer refer to the old block. 182 BB = nullptr; 183} 184 185/// Initialize the DAG and common scheduler state for the current scheduling 186/// region. This does not actually create the DAG, only clears it. The 187/// scheduling driver may call BuildSchedGraph multiple times per scheduling 188/// region. 189void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, 190 MachineBasicBlock::iterator begin, 191 MachineBasicBlock::iterator end, 192 unsigned regioninstrs) { 193 assert(bb == BB && "startBlock should set BB"); 194 RegionBegin = begin; 195 RegionEnd = end; 196 NumRegionInstrs = regioninstrs; 197} 198 199/// Close the current scheduling region. Don't clear any state in case the 200/// driver wants to refer to the previous scheduling region. 201void ScheduleDAGInstrs::exitRegion() { 202 // Nothing to do. 203} 204 205/// addSchedBarrierDeps - Add dependencies from instructions in the current 206/// list of instructions being scheduled to scheduling barrier by adding 207/// the exit SU to the register defs and use list. This is because we want to 208/// make sure instructions which define registers that are either used by 209/// the terminator or are live-out are properly scheduled. This is 210/// especially important when the definition latency of the return value(s) 211/// are too high to be hidden by the branch or when the liveout registers 212/// used by instructions in the fallthrough block. 213void ScheduleDAGInstrs::addSchedBarrierDeps() { 214 MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : nullptr; 215 ExitSU.setInstr(ExitMI); 216 bool AllDepKnown = ExitMI && 217 (ExitMI->isCall() || ExitMI->isBarrier()); 218 if (ExitMI && AllDepKnown) { 219 // If it's a call or a barrier, add dependencies on the defs and uses of 220 // instruction. 221 for (unsigned i = 0, e = ExitMI->getNumOperands(); i != e; ++i) { 222 const MachineOperand &MO = ExitMI->getOperand(i); 223 if (!MO.isReg() || MO.isDef()) continue; 224 unsigned Reg = MO.getReg(); 225 if (Reg == 0) continue; 226 227 if (TRI->isPhysicalRegister(Reg)) 228 Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg)); 229 else if (MO.readsReg()) // ignore undef operands 230 addVRegUseDeps(&ExitSU, i); 231 } 232 } else { 233 // For others, e.g. fallthrough, conditional branch, assume the exit 234 // uses all the registers that are livein to the successor blocks. 235 assert(Uses.empty() && "Uses in set before adding deps?"); 236 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 237 SE = BB->succ_end(); SI != SE; ++SI) 238 for (const auto &LI : (*SI)->liveins()) { 239 if (!Uses.contains(LI.PhysReg)) 240 Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg)); 241 } 242 } 243} 244 245/// MO is an operand of SU's instruction that defines a physical register. Add 246/// data dependencies from SU to any uses of the physical register. 247void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { 248 const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx); 249 assert(MO.isDef() && "expect physreg def"); 250 251 // Ask the target if address-backscheduling is desirable, and if so how much. 252 const TargetSubtargetInfo &ST = MF.getSubtarget(); 253 254 for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 255 Alias.isValid(); ++Alias) { 256 if (!Uses.contains(*Alias)) 257 continue; 258 for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) { 259 SUnit *UseSU = I->SU; 260 if (UseSU == SU) 261 continue; 262 263 // Adjust the dependence latency using operand def/use information, 264 // then allow the target to perform its own adjustments. 265 int UseOp = I->OpIdx; 266 MachineInstr *RegUse = nullptr; 267 SDep Dep; 268 if (UseOp < 0) 269 Dep = SDep(SU, SDep::Artificial); 270 else { 271 // Set the hasPhysRegDefs only for physreg defs that have a use within 272 // the scheduling region. 273 SU->hasPhysRegDefs = true; 274 Dep = SDep(SU, SDep::Data, *Alias); 275 RegUse = UseSU->getInstr(); 276 } 277 Dep.setLatency( 278 SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, RegUse, 279 UseOp)); 280 281 ST.adjustSchedDependency(SU, UseSU, Dep); 282 UseSU->addPred(Dep); 283 } 284 } 285} 286 287/// addPhysRegDeps - Add register dependencies (data, anti, and output) from 288/// this SUnit to following instructions in the same scheduling region that 289/// depend the physical register referenced at OperIdx. 290void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { 291 MachineInstr *MI = SU->getInstr(); 292 MachineOperand &MO = MI->getOperand(OperIdx); 293 294 // Optionally add output and anti dependencies. For anti 295 // dependencies we use a latency of 0 because for a multi-issue 296 // target we want to allow the defining instruction to issue 297 // in the same cycle as the using instruction. 298 // TODO: Using a latency of 1 here for output dependencies assumes 299 // there's no cost for reusing registers. 300 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 301 for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 302 Alias.isValid(); ++Alias) { 303 if (!Defs.contains(*Alias)) 304 continue; 305 for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) { 306 SUnit *DefSU = I->SU; 307 if (DefSU == &ExitSU) 308 continue; 309 if (DefSU != SU && 310 (Kind != SDep::Output || !MO.isDead() || 311 !DefSU->getInstr()->registerDefIsDead(*Alias))) { 312 if (Kind == SDep::Anti) 313 DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias)); 314 else { 315 SDep Dep(SU, Kind, /*Reg=*/*Alias); 316 Dep.setLatency( 317 SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); 318 DefSU->addPred(Dep); 319 } 320 } 321 } 322 } 323 324 if (!MO.isDef()) { 325 SU->hasPhysRegUses = true; 326 // Either insert a new Reg2SUnits entry with an empty SUnits list, or 327 // retrieve the existing SUnits list for this register's uses. 328 // Push this SUnit on the use list. 329 Uses.insert(PhysRegSUOper(SU, OperIdx, MO.getReg())); 330 if (RemoveKillFlags) 331 MO.setIsKill(false); 332 } 333 else { 334 addPhysRegDataDeps(SU, OperIdx); 335 unsigned Reg = MO.getReg(); 336 337 // clear this register's use list 338 if (Uses.contains(Reg)) 339 Uses.eraseAll(Reg); 340 341 if (!MO.isDead()) { 342 Defs.eraseAll(Reg); 343 } else if (SU->isCall) { 344 // Calls will not be reordered because of chain dependencies (see 345 // below). Since call operands are dead, calls may continue to be added 346 // to the DefList making dependence checking quadratic in the size of 347 // the block. Instead, we leave only one call at the back of the 348 // DefList. 349 Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg); 350 Reg2SUnitsMap::iterator B = P.first; 351 Reg2SUnitsMap::iterator I = P.second; 352 for (bool isBegin = I == B; !isBegin; /* empty */) { 353 isBegin = (--I) == B; 354 if (!I->SU->isCall) 355 break; 356 I = Defs.erase(I); 357 } 358 } 359 360 // Defs are pushed in the order they are visited and never reordered. 361 Defs.insert(PhysRegSUOper(SU, OperIdx, Reg)); 362 } 363} 364 365LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const 366{ 367 unsigned Reg = MO.getReg(); 368 // No point in tracking lanemasks if we don't have interesting subregisters. 369 const TargetRegisterClass &RC = *MRI.getRegClass(Reg); 370 if (!RC.HasDisjunctSubRegs) 371 return ~0u; 372 373 unsigned SubReg = MO.getSubReg(); 374 if (SubReg == 0) 375 return RC.getLaneMask(); 376 return TRI->getSubRegIndexLaneMask(SubReg); 377} 378 379/// addVRegDefDeps - Add register output and data dependencies from this SUnit 380/// to instructions that occur later in the same scheduling region if they read 381/// from or write to the virtual register defined at OperIdx. 382/// 383/// TODO: Hoist loop induction variable increments. This has to be 384/// reevaluated. Generally, IV scheduling should be done before coalescing. 385void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { 386 MachineInstr *MI = SU->getInstr(); 387 MachineOperand &MO = MI->getOperand(OperIdx); 388 unsigned Reg = MO.getReg(); 389 390 LaneBitmask DefLaneMask; 391 LaneBitmask KillLaneMask; 392 if (TrackLaneMasks) { 393 bool IsKill = MO.getSubReg() == 0 || MO.isUndef(); 394 DefLaneMask = getLaneMaskForMO(MO); 395 // If we have a <read-undef> flag, none of the lane values comes from an 396 // earlier instruction. 397 KillLaneMask = IsKill ? ~0u : DefLaneMask; 398 399 // Clear undef flag, we'll re-add it later once we know which subregister 400 // Def is first. 401 MO.setIsUndef(false); 402 } else { 403 DefLaneMask = ~0u; 404 KillLaneMask = ~0u; 405 } 406 407 if (MO.isDead()) { 408 assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() && 409 "Dead defs should have no uses"); 410 } else { 411 // Add data dependence to all uses we found so far. 412 const TargetSubtargetInfo &ST = MF.getSubtarget(); 413 for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg), 414 E = CurrentVRegUses.end(); I != E; /*empty*/) { 415 LaneBitmask LaneMask = I->LaneMask; 416 // Ignore uses of other lanes. 417 if ((LaneMask & KillLaneMask) == 0) { 418 ++I; 419 continue; 420 } 421 422 if ((LaneMask & DefLaneMask) != 0) { 423 SUnit *UseSU = I->SU; 424 MachineInstr *Use = UseSU->getInstr(); 425 SDep Dep(SU, SDep::Data, Reg); 426 Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use, 427 I->OperandIndex)); 428 ST.adjustSchedDependency(SU, UseSU, Dep); 429 UseSU->addPred(Dep); 430 } 431 432 LaneMask &= ~KillLaneMask; 433 // If we found a Def for all lanes of this use, remove it from the list. 434 if (LaneMask != 0) { 435 I->LaneMask = LaneMask; 436 ++I; 437 } else 438 I = CurrentVRegUses.erase(I); 439 } 440 } 441 442 // Shortcut: Singly defined vregs do not have output/anti dependencies. 443 if (MRI.hasOneDef(Reg)) 444 return; 445 446 // Add output dependence to the next nearest defs of this vreg. 447 // 448 // Unless this definition is dead, the output dependence should be 449 // transitively redundant with antidependencies from this definition's 450 // uses. We're conservative for now until we have a way to guarantee the uses 451 // are not eliminated sometime during scheduling. The output dependence edge 452 // is also useful if output latency exceeds def-use latency. 453 LaneBitmask LaneMask = DefLaneMask; 454 for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), 455 CurrentVRegDefs.end())) { 456 // Ignore defs for other lanes. 457 if ((V2SU.LaneMask & LaneMask) == 0) 458 continue; 459 // Add an output dependence. 460 SUnit *DefSU = V2SU.SU; 461 // Ignore additional defs of the same lanes in one instruction. This can 462 // happen because lanemasks are shared for targets with too many 463 // subregisters. We also use some representration tricks/hacks where we 464 // add super-register defs/uses, to imply that although we only access parts 465 // of the reg we care about the full one. 466 if (DefSU == SU) 467 continue; 468 SDep Dep(SU, SDep::Output, Reg); 469 Dep.setLatency( 470 SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); 471 DefSU->addPred(Dep); 472 473 // Update current definition. This can get tricky if the def was about a 474 // bigger lanemask before. We then have to shrink it and create a new 475 // VReg2SUnit for the non-overlapping part. 476 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask; 477 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask; 478 if (NonOverlapMask != 0) 479 CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, V2SU.SU)); 480 V2SU.SU = SU; 481 V2SU.LaneMask = OverlapMask; 482 } 483 // If there was no CurrentVRegDefs entry for some lanes yet, create one. 484 if (LaneMask != 0) 485 CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU)); 486} 487 488/// addVRegUseDeps - Add a register data dependency if the instruction that 489/// defines the virtual register used at OperIdx is mapped to an SUnit. Add a 490/// register antidependency from this SUnit to instructions that occur later in 491/// the same scheduling region if they write the virtual register. 492/// 493/// TODO: Handle ExitSU "uses" properly. 494void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { 495 const MachineInstr *MI = SU->getInstr(); 496 const MachineOperand &MO = MI->getOperand(OperIdx); 497 unsigned Reg = MO.getReg(); 498 499 // Remember the use. Data dependencies will be added when we find the def. 500 LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO) : ~0u; 501 CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU)); 502 503 // Add antidependences to the following defs of the vreg. 504 for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), 505 CurrentVRegDefs.end())) { 506 // Ignore defs for unrelated lanes. 507 LaneBitmask PrevDefLaneMask = V2SU.LaneMask; 508 if ((PrevDefLaneMask & LaneMask) == 0) 509 continue; 510 if (V2SU.SU == SU) 511 continue; 512 513 V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg)); 514 } 515} 516 517/// Return true if MI is an instruction we are unable to reason about 518/// (like a call or something with unmodeled side effects). 519static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { 520 return MI->isCall() || MI->hasUnmodeledSideEffects() || 521 (MI->hasOrderedMemoryRef() && 522 (!MI->mayLoad() || !MI->isInvariantLoad(AA))); 523} 524 525// This MI might have either incomplete info, or known to be unsafe 526// to deal with (i.e. volatile object). 527static inline bool isUnsafeMemoryObject(MachineInstr *MI, 528 const MachineFrameInfo *MFI, 529 const DataLayout &DL) { 530 if (!MI || MI->memoperands_empty()) 531 return true; 532 // We purposefully do no check for hasOneMemOperand() here 533 // in hope to trigger an assert downstream in order to 534 // finish implementation. 535 if ((*MI->memoperands_begin())->isVolatile() || 536 MI->hasUnmodeledSideEffects()) 537 return true; 538 539 if ((*MI->memoperands_begin())->getPseudoValue()) { 540 // Similarly to getUnderlyingObjectForInstr: 541 // For now, ignore PseudoSourceValues which may alias LLVM IR values 542 // because the code that uses this function has no way to cope with 543 // such aliases. 544 return true; 545 } 546 547 const Value *V = (*MI->memoperands_begin())->getValue(); 548 if (!V) 549 return true; 550 551 SmallVector<Value *, 4> Objs; 552 getUnderlyingObjects(V, Objs, DL); 553 for (Value *V : Objs) { 554 // Does this pointer refer to a distinct and identifiable object? 555 if (!isIdentifiedObject(V)) 556 return true; 557 } 558 559 return false; 560} 561 562/// This returns true if the two MIs need a chain edge between them. 563/// If these are not even memory operations, we still may need 564/// chain deps between them. The question really is - could 565/// these two MIs be reordered during scheduling from memory dependency 566/// point of view. 567static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, 568 const DataLayout &DL, MachineInstr *MIa, 569 MachineInstr *MIb) { 570 const MachineFunction *MF = MIa->getParent()->getParent(); 571 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 572 573 // Cover a trivial case - no edge is need to itself. 574 if (MIa == MIb) 575 return false; 576 577 // Let the target decide if memory accesses cannot possibly overlap. 578 if ((MIa->mayLoad() || MIa->mayStore()) && 579 (MIb->mayLoad() || MIb->mayStore())) 580 if (TII->areMemAccessesTriviallyDisjoint(MIa, MIb, AA)) 581 return false; 582 583 // FIXME: Need to handle multiple memory operands to support all targets. 584 if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand()) 585 return true; 586 587 if (isUnsafeMemoryObject(MIa, MFI, DL) || isUnsafeMemoryObject(MIb, MFI, DL)) 588 return true; 589 590 // If we are dealing with two "normal" loads, we do not need an edge 591 // between them - they could be reordered. 592 if (!MIa->mayStore() && !MIb->mayStore()) 593 return false; 594 595 // To this point analysis is generic. From here on we do need AA. 596 if (!AA) 597 return true; 598 599 MachineMemOperand *MMOa = *MIa->memoperands_begin(); 600 MachineMemOperand *MMOb = *MIb->memoperands_begin(); 601 602 if (!MMOa->getValue() || !MMOb->getValue()) 603 return true; 604 605 // The following interface to AA is fashioned after DAGCombiner::isAlias 606 // and operates with MachineMemOperand offset with some important 607 // assumptions: 608 // - LLVM fundamentally assumes flat address spaces. 609 // - MachineOperand offset can *only* result from legalization and 610 // cannot affect queries other than the trivial case of overlap 611 // checking. 612 // - These offsets never wrap and never step outside 613 // of allocated objects. 614 // - There should never be any negative offsets here. 615 // 616 // FIXME: Modify API to hide this math from "user" 617 // FIXME: Even before we go to AA we can reason locally about some 618 // memory objects. It can save compile time, and possibly catch some 619 // corner cases not currently covered. 620 621 assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset"); 622 assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset"); 623 624 int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset()); 625 int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset; 626 int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset; 627 628 AliasResult AAResult = 629 AA->alias(MemoryLocation(MMOa->getValue(), Overlapa, 630 UseTBAA ? MMOa->getAAInfo() : AAMDNodes()), 631 MemoryLocation(MMOb->getValue(), Overlapb, 632 UseTBAA ? MMOb->getAAInfo() : AAMDNodes())); 633 634 return (AAResult != NoAlias); 635} 636 637/// This recursive function iterates over chain deps of SUb looking for 638/// "latest" node that needs a chain edge to SUa. 639static unsigned iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, 640 const DataLayout &DL, SUnit *SUa, SUnit *SUb, 641 SUnit *ExitSU, unsigned *Depth, 642 SmallPtrSetImpl<const SUnit *> &Visited) { 643 if (!SUa || !SUb || SUb == ExitSU) 644 return *Depth; 645 646 // Remember visited nodes. 647 if (!Visited.insert(SUb).second) 648 return *Depth; 649 // If there is _some_ dependency already in place, do not 650 // descend any further. 651 // TODO: Need to make sure that if that dependency got eliminated or ignored 652 // for any reason in the future, we would not violate DAG topology. 653 // Currently it does not happen, but makes an implicit assumption about 654 // future implementation. 655 // 656 // Independently, if we encounter node that is some sort of global 657 // object (like a call) we already have full set of dependencies to it 658 // and we can stop descending. 659 if (SUa->isSucc(SUb) || 660 isGlobalMemoryObject(AA, SUb->getInstr())) 661 return *Depth; 662 663 // If we do need an edge, or we have exceeded depth budget, 664 // add that edge to the predecessors chain of SUb, 665 // and stop descending. 666 if (*Depth > 200 || 667 MIsNeedChainEdge(AA, MFI, DL, SUa->getInstr(), SUb->getInstr())) { 668 SUb->addPred(SDep(SUa, SDep::MayAliasMem)); 669 return *Depth; 670 } 671 // Track current depth. 672 (*Depth)++; 673 // Iterate over memory dependencies only. 674 for (SUnit::const_succ_iterator I = SUb->Succs.begin(), E = SUb->Succs.end(); 675 I != E; ++I) 676 if (I->isNormalMemoryOrBarrier()) 677 iterateChainSucc(AA, MFI, DL, SUa, I->getSUnit(), ExitSU, Depth, Visited); 678 return *Depth; 679} 680 681/// This function assumes that "downward" from SU there exist 682/// tail/leaf of already constructed DAG. It iterates downward and 683/// checks whether SU can be aliasing any node dominated 684/// by it. 685static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, 686 const DataLayout &DL, SUnit *SU, SUnit *ExitSU, 687 std::set<SUnit *> &CheckList, 688 unsigned LatencyToLoad) { 689 if (!SU) 690 return; 691 692 SmallPtrSet<const SUnit*, 16> Visited; 693 unsigned Depth = 0; 694 695 for (std::set<SUnit *>::iterator I = CheckList.begin(), IE = CheckList.end(); 696 I != IE; ++I) { 697 if (SU == *I) 698 continue; 699 if (MIsNeedChainEdge(AA, MFI, DL, SU->getInstr(), (*I)->getInstr())) { 700 SDep Dep(SU, SDep::MayAliasMem); 701 Dep.setLatency(((*I)->getInstr()->mayLoad()) ? LatencyToLoad : 0); 702 (*I)->addPred(Dep); 703 } 704 705 // Iterate recursively over all previously added memory chain 706 // successors. Keep track of visited nodes. 707 for (SUnit::const_succ_iterator J = (*I)->Succs.begin(), 708 JE = (*I)->Succs.end(); J != JE; ++J) 709 if (J->isNormalMemoryOrBarrier()) 710 iterateChainSucc(AA, MFI, DL, SU, J->getSUnit(), ExitSU, &Depth, 711 Visited); 712 } 713} 714 715/// Check whether two objects need a chain edge, if so, add it 716/// otherwise remember the rejected SU. 717static inline void addChainDependency(AliasAnalysis *AA, 718 const MachineFrameInfo *MFI, 719 const DataLayout &DL, SUnit *SUa, 720 SUnit *SUb, std::set<SUnit *> &RejectList, 721 unsigned TrueMemOrderLatency = 0, 722 bool isNormalMemory = false) { 723 // If this is a false dependency, 724 // do not add the edge, but remember the rejected node. 725 if (MIsNeedChainEdge(AA, MFI, DL, SUa->getInstr(), SUb->getInstr())) { 726 SDep Dep(SUa, isNormalMemory ? SDep::MayAliasMem : SDep::Barrier); 727 Dep.setLatency(TrueMemOrderLatency); 728 SUb->addPred(Dep); 729 } 730 else { 731 // Duplicate entries should be ignored. 732 RejectList.insert(SUb); 733 DEBUG(dbgs() << "\tReject chain dep between SU(" 734 << SUa->NodeNum << ") and SU(" 735 << SUb->NodeNum << ")\n"); 736 } 737} 738 739/// Create an SUnit for each real instruction, numbered in top-down topological 740/// order. The instruction order A < B, implies that no edge exists from B to A. 741/// 742/// Map each real instruction to its SUnit. 743/// 744/// After initSUnits, the SUnits vector cannot be resized and the scheduler may 745/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs 746/// instead of pointers. 747/// 748/// MachineScheduler relies on initSUnits numbering the nodes by their order in 749/// the original instruction list. 750void ScheduleDAGInstrs::initSUnits() { 751 // We'll be allocating one SUnit for each real instruction in the region, 752 // which is contained within a basic block. 753 SUnits.reserve(NumRegionInstrs); 754 755 for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) { 756 MachineInstr *MI = I; 757 if (MI->isDebugValue()) 758 continue; 759 760 SUnit *SU = newSUnit(MI); 761 MISUnitMap[MI] = SU; 762 763 SU->isCall = MI->isCall(); 764 SU->isCommutable = MI->isCommutable(); 765 766 // Assign the Latency field of SU using target-provided information. 767 SU->Latency = SchedModel.computeInstrLatency(SU->getInstr()); 768 769 // If this SUnit uses a reserved or unbuffered resource, mark it as such. 770 // 771 // Reserved resources block an instruction from issuing and stall the 772 // entire pipeline. These are identified by BufferSize=0. 773 // 774 // Unbuffered resources prevent execution of subsequent instructions that 775 // require the same resources. This is used for in-order execution pipelines 776 // within an out-of-order core. These are identified by BufferSize=1. 777 if (SchedModel.hasInstrSchedModel()) { 778 const MCSchedClassDesc *SC = getSchedClass(SU); 779 for (TargetSchedModel::ProcResIter 780 PI = SchedModel.getWriteProcResBegin(SC), 781 PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { 782 switch (SchedModel.getProcResource(PI->ProcResourceIdx)->BufferSize) { 783 case 0: 784 SU->hasReservedResource = true; 785 break; 786 case 1: 787 SU->isUnbuffered = true; 788 break; 789 default: 790 break; 791 } 792 } 793 } 794 } 795} 796 797void ScheduleDAGInstrs::collectVRegUses(SUnit *SU) { 798 const MachineInstr *MI = SU->getInstr(); 799 for (const MachineOperand &MO : MI->operands()) { 800 if (!MO.isReg()) 801 continue; 802 if (!MO.readsReg()) 803 continue; 804 if (TrackLaneMasks && !MO.isUse()) 805 continue; 806 807 unsigned Reg = MO.getReg(); 808 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 809 continue; 810 811 // Record this local VReg use. 812 VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg); 813 for (; UI != VRegUses.end(); ++UI) { 814 if (UI->SU == SU) 815 break; 816 } 817 if (UI == VRegUses.end()) 818 VRegUses.insert(VReg2SUnit(Reg, 0, SU)); 819 } 820} 821 822/// If RegPressure is non-null, compute register pressure as a side effect. The 823/// DAG builder is an efficient place to do it because it already visits 824/// operands. 825void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 826 RegPressureTracker *RPTracker, 827 PressureDiffs *PDiffs, 828 bool TrackLaneMasks) { 829 const TargetSubtargetInfo &ST = MF.getSubtarget(); 830 bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI 831 : ST.useAA(); 832 AliasAnalysis *AAForDep = UseAA ? AA : nullptr; 833 834 this->TrackLaneMasks = TrackLaneMasks; 835 MISUnitMap.clear(); 836 ScheduleDAG::clearDAG(); 837 838 // Create an SUnit for each real instruction. 839 initSUnits(); 840 841 if (PDiffs) 842 PDiffs->init(SUnits.size()); 843 844 // We build scheduling units by walking a block's instruction list from bottom 845 // to top. 846 847 // Remember where a generic side-effecting instruction is as we proceed. 848 SUnit *BarrierChain = nullptr, *AliasChain = nullptr; 849 850 // Memory references to specific known memory locations are tracked 851 // so that they can be given more precise dependencies. We track 852 // separately the known memory locations that may alias and those 853 // that are known not to alias 854 MapVector<ValueType, std::vector<SUnit *> > AliasMemDefs, NonAliasMemDefs; 855 MapVector<ValueType, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 856 std::set<SUnit*> RejectMemNodes; 857 858 // Remove any stale debug info; sometimes BuildSchedGraph is called again 859 // without emitting the info from the previous call. 860 DbgValues.clear(); 861 FirstDbgValue = nullptr; 862 863 assert(Defs.empty() && Uses.empty() && 864 "Only BuildGraph should update Defs/Uses"); 865 Defs.setUniverse(TRI->getNumRegs()); 866 Uses.setUniverse(TRI->getNumRegs()); 867 868 assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs"); 869 assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses"); 870 unsigned NumVirtRegs = MRI.getNumVirtRegs(); 871 CurrentVRegDefs.setUniverse(NumVirtRegs); 872 CurrentVRegUses.setUniverse(NumVirtRegs); 873 874 VRegUses.clear(); 875 VRegUses.setUniverse(NumVirtRegs); 876 877 // Model data dependencies between instructions being scheduled and the 878 // ExitSU. 879 addSchedBarrierDeps(); 880 881 // Walk the list of instructions, from bottom moving up. 882 MachineInstr *DbgMI = nullptr; 883 for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; 884 MII != MIE; --MII) { 885 MachineInstr *MI = std::prev(MII); 886 if (MI && DbgMI) { 887 DbgValues.push_back(std::make_pair(DbgMI, MI)); 888 DbgMI = nullptr; 889 } 890 891 if (MI->isDebugValue()) { 892 DbgMI = MI; 893 continue; 894 } 895 SUnit *SU = MISUnitMap[MI]; 896 assert(SU && "No SUnit mapped to this MI"); 897 898 if (RPTracker) { 899 collectVRegUses(SU); 900 901 RegisterOperands RegOpers; 902 RegOpers.collect(*MI, *TRI, MRI); 903 if (PDiffs != nullptr) 904 PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI); 905 906 RPTracker->recedeSkipDebugValues(); 907 assert(&*RPTracker->getPos() == MI && "RPTracker in sync"); 908 RPTracker->recede(RegOpers); 909 } 910 911 assert( 912 (CanHandleTerminators || (!MI->isTerminator() && !MI->isPosition())) && 913 "Cannot schedule terminators or labels!"); 914 915 // Add register-based dependencies (data, anti, and output). 916 bool HasVRegDef = false; 917 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 918 const MachineOperand &MO = MI->getOperand(j); 919 if (!MO.isReg()) continue; 920 unsigned Reg = MO.getReg(); 921 if (Reg == 0) continue; 922 923 if (TRI->isPhysicalRegister(Reg)) 924 addPhysRegDeps(SU, j); 925 else { 926 if (MO.isDef()) { 927 HasVRegDef = true; 928 addVRegDefDeps(SU, j); 929 } 930 else if (MO.readsReg()) // ignore undef operands 931 addVRegUseDeps(SU, j); 932 } 933 } 934 // If we haven't seen any uses in this scheduling region, create a 935 // dependence edge to ExitSU to model the live-out latency. This is required 936 // for vreg defs with no in-region use, and prefetches with no vreg def. 937 // 938 // FIXME: NumDataSuccs would be more precise than NumSuccs here. This 939 // check currently relies on being called before adding chain deps. 940 if (SU->NumSuccs == 0 && SU->Latency > 1 941 && (HasVRegDef || MI->mayLoad())) { 942 SDep Dep(SU, SDep::Artificial); 943 Dep.setLatency(SU->Latency - 1); 944 ExitSU.addPred(Dep); 945 } 946 947 // Add chain dependencies. 948 // Chain dependencies used to enforce memory order should have 949 // latency of 0 (except for true dependency of Store followed by 950 // aliased Load... we estimate that with a single cycle of latency 951 // assuming the hardware will bypass) 952 // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 953 // after stack slots are lowered to actual addresses. 954 // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 955 // produce more precise dependence information. 956 unsigned TrueMemOrderLatency = MI->mayStore() ? 1 : 0; 957 if (isGlobalMemoryObject(AA, MI)) { 958 // Be conservative with these and add dependencies on all memory 959 // references, even those that are known to not alias. 960 for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 961 NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 962 for (unsigned i = 0, e = I->second.size(); i != e; ++i) { 963 I->second[i]->addPred(SDep(SU, SDep::Barrier)); 964 } 965 } 966 for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 967 NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 968 for (unsigned i = 0, e = I->second.size(); i != e; ++i) { 969 SDep Dep(SU, SDep::Barrier); 970 Dep.setLatency(TrueMemOrderLatency); 971 I->second[i]->addPred(Dep); 972 } 973 } 974 // Add SU to the barrier chain. 975 if (BarrierChain) 976 BarrierChain->addPred(SDep(SU, SDep::Barrier)); 977 BarrierChain = SU; 978 // This is a barrier event that acts as a pivotal node in the DAG, 979 // so it is safe to clear list of exposed nodes. 980 adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, 981 TrueMemOrderLatency); 982 RejectMemNodes.clear(); 983 NonAliasMemDefs.clear(); 984 NonAliasMemUses.clear(); 985 986 // fall-through 987 new_alias_chain: 988 // Chain all possibly aliasing memory references through SU. 989 if (AliasChain) { 990 unsigned ChainLatency = 0; 991 if (AliasChain->getInstr()->mayLoad()) 992 ChainLatency = TrueMemOrderLatency; 993 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, 994 RejectMemNodes, ChainLatency); 995 } 996 AliasChain = SU; 997 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 998 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 999 PendingLoads[k], RejectMemNodes, 1000 TrueMemOrderLatency); 1001 for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1002 AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) { 1003 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1004 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1005 I->second[i], RejectMemNodes); 1006 } 1007 for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1008 AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 1009 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1010 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1011 I->second[i], RejectMemNodes, TrueMemOrderLatency); 1012 } 1013 // This call must come after calls to addChainDependency() since it 1014 // consumes the 'RejectMemNodes' list that addChainDependency() possibly 1015 // adds to. 1016 adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, 1017 TrueMemOrderLatency); 1018 PendingLoads.clear(); 1019 AliasMemDefs.clear(); 1020 AliasMemUses.clear(); 1021 } else if (MI->mayStore()) { 1022 // Add dependence on barrier chain, if needed. 1023 // There is no point to check aliasing on barrier event. Even if 1024 // SU and barrier _could_ be reordered, they should not. In addition, 1025 // we have lost all RejectMemNodes below barrier. 1026 if (BarrierChain) 1027 BarrierChain->addPred(SDep(SU, SDep::Barrier)); 1028 1029 UnderlyingObjectsVector Objs; 1030 getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout()); 1031 1032 if (Objs.empty()) { 1033 // Treat all other stores conservatively. 1034 goto new_alias_chain; 1035 } 1036 1037 bool MayAlias = false; 1038 for (UnderlyingObjectsVector::iterator K = Objs.begin(), KE = Objs.end(); 1039 K != KE; ++K) { 1040 ValueType V = K->getPointer(); 1041 bool ThisMayAlias = K->getInt(); 1042 if (ThisMayAlias) 1043 MayAlias = true; 1044 1045 // A store to a specific PseudoSourceValue. Add precise dependencies. 1046 // Record the def in MemDefs, first adding a dep if there is 1047 // an existing def. 1048 MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1049 ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 1050 MapVector<ValueType, std::vector<SUnit *> >::iterator IE = 1051 ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 1052 if (I != IE) { 1053 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1054 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1055 I->second[i], RejectMemNodes, 0, true); 1056 1057 // If we're not using AA, then we only need one store per object. 1058 if (!AAForDep) 1059 I->second.clear(); 1060 I->second.push_back(SU); 1061 } else { 1062 if (ThisMayAlias) { 1063 if (!AAForDep) 1064 AliasMemDefs[V].clear(); 1065 AliasMemDefs[V].push_back(SU); 1066 } else { 1067 if (!AAForDep) 1068 NonAliasMemDefs[V].clear(); 1069 NonAliasMemDefs[V].push_back(SU); 1070 } 1071 } 1072 // Handle the uses in MemUses, if there are any. 1073 MapVector<ValueType, std::vector<SUnit *> >::iterator J = 1074 ((ThisMayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 1075 MapVector<ValueType, std::vector<SUnit *> >::iterator JE = 1076 ((ThisMayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 1077 if (J != JE) { 1078 for (unsigned i = 0, e = J->second.size(); i != e; ++i) 1079 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1080 J->second[i], RejectMemNodes, 1081 TrueMemOrderLatency, true); 1082 J->second.clear(); 1083 } 1084 } 1085 if (MayAlias) { 1086 // Add dependencies from all the PendingLoads, i.e. loads 1087 // with no underlying object. 1088 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 1089 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1090 PendingLoads[k], RejectMemNodes, 1091 TrueMemOrderLatency); 1092 // Add dependence on alias chain, if needed. 1093 if (AliasChain) 1094 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, 1095 RejectMemNodes); 1096 } 1097 // This call must come after calls to addChainDependency() since it 1098 // consumes the 'RejectMemNodes' list that addChainDependency() possibly 1099 // adds to. 1100 adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, 1101 TrueMemOrderLatency); 1102 } else if (MI->mayLoad()) { 1103 bool MayAlias = true; 1104 if (MI->isInvariantLoad(AA)) { 1105 // Invariant load, no chain dependencies needed! 1106 } else { 1107 UnderlyingObjectsVector Objs; 1108 getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout()); 1109 1110 if (Objs.empty()) { 1111 // A load with no underlying object. Depend on all 1112 // potentially aliasing stores. 1113 for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1114 AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 1115 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1116 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1117 I->second[i], RejectMemNodes); 1118 1119 PendingLoads.push_back(SU); 1120 MayAlias = true; 1121 } else { 1122 MayAlias = false; 1123 } 1124 1125 for (UnderlyingObjectsVector::iterator 1126 J = Objs.begin(), JE = Objs.end(); J != JE; ++J) { 1127 ValueType V = J->getPointer(); 1128 bool ThisMayAlias = J->getInt(); 1129 1130 if (ThisMayAlias) 1131 MayAlias = true; 1132 1133 // A load from a specific PseudoSourceValue. Add precise dependencies. 1134 MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1135 ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 1136 MapVector<ValueType, std::vector<SUnit *> >::iterator IE = 1137 ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 1138 if (I != IE) 1139 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1140 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1141 I->second[i], RejectMemNodes, 0, true); 1142 if (ThisMayAlias) 1143 AliasMemUses[V].push_back(SU); 1144 else 1145 NonAliasMemUses[V].push_back(SU); 1146 } 1147 // Add dependencies on alias and barrier chains, if needed. 1148 if (MayAlias && AliasChain) 1149 addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, 1150 RejectMemNodes); 1151 if (MayAlias) 1152 // This call must come after calls to addChainDependency() since it 1153 // consumes the 'RejectMemNodes' list that addChainDependency() 1154 // possibly adds to. 1155 adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, 1156 RejectMemNodes, /*Latency=*/0); 1157 if (BarrierChain) 1158 BarrierChain->addPred(SDep(SU, SDep::Barrier)); 1159 } 1160 } 1161 } 1162 if (DbgMI) 1163 FirstDbgValue = DbgMI; 1164 1165 Defs.clear(); 1166 Uses.clear(); 1167 CurrentVRegDefs.clear(); 1168 CurrentVRegUses.clear(); 1169 PendingLoads.clear(); 1170} 1171 1172/// \brief Initialize register live-range state for updating kills. 1173void ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) { 1174 // Start with no live registers. 1175 LiveRegs.reset(); 1176 1177 // Examine the live-in regs of all successors. 1178 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 1179 SE = BB->succ_end(); SI != SE; ++SI) { 1180 for (const auto &LI : (*SI)->liveins()) { 1181 // Repeat, for reg and all subregs. 1182 for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true); 1183 SubRegs.isValid(); ++SubRegs) 1184 LiveRegs.set(*SubRegs); 1185 } 1186 } 1187} 1188 1189/// \brief If we change a kill flag on the bundle instruction implicit register 1190/// operands, then we also need to propagate that to any instructions inside 1191/// the bundle which had the same kill state. 1192static void toggleBundleKillFlag(MachineInstr *MI, unsigned Reg, 1193 bool NewKillState) { 1194 if (MI->getOpcode() != TargetOpcode::BUNDLE) 1195 return; 1196 1197 // Walk backwards from the last instruction in the bundle to the first. 1198 // Once we set a kill flag on an instruction, we bail out, as otherwise we 1199 // might set it on too many operands. We will clear as many flags as we 1200 // can though. 1201 MachineBasicBlock::instr_iterator Begin = MI->getIterator(); 1202 MachineBasicBlock::instr_iterator End = getBundleEnd(MI); 1203 while (Begin != End) { 1204 for (MachineOperand &MO : (--End)->operands()) { 1205 if (!MO.isReg() || MO.isDef() || Reg != MO.getReg()) 1206 continue; 1207 1208 // DEBUG_VALUE nodes do not contribute to code generation and should 1209 // always be ignored. Failure to do so may result in trying to modify 1210 // KILL flags on DEBUG_VALUE nodes, which is distressing. 1211 if (MO.isDebug()) 1212 continue; 1213 1214 // If the register has the internal flag then it could be killing an 1215 // internal def of the register. In this case, just skip. We only want 1216 // to toggle the flag on operands visible outside the bundle. 1217 if (MO.isInternalRead()) 1218 continue; 1219 1220 if (MO.isKill() == NewKillState) 1221 continue; 1222 MO.setIsKill(NewKillState); 1223 if (NewKillState) 1224 return; 1225 } 1226 } 1227} 1228 1229bool ScheduleDAGInstrs::toggleKillFlag(MachineInstr *MI, MachineOperand &MO) { 1230 // Setting kill flag... 1231 if (!MO.isKill()) { 1232 MO.setIsKill(true); 1233 toggleBundleKillFlag(MI, MO.getReg(), true); 1234 return false; 1235 } 1236 1237 // If MO itself is live, clear the kill flag... 1238 if (LiveRegs.test(MO.getReg())) { 1239 MO.setIsKill(false); 1240 toggleBundleKillFlag(MI, MO.getReg(), false); 1241 return false; 1242 } 1243 1244 // If any subreg of MO is live, then create an imp-def for that 1245 // subreg and keep MO marked as killed. 1246 MO.setIsKill(false); 1247 toggleBundleKillFlag(MI, MO.getReg(), false); 1248 bool AllDead = true; 1249 const unsigned SuperReg = MO.getReg(); 1250 MachineInstrBuilder MIB(MF, MI); 1251 for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { 1252 if (LiveRegs.test(*SubRegs)) { 1253 MIB.addReg(*SubRegs, RegState::ImplicitDefine); 1254 AllDead = false; 1255 } 1256 } 1257 1258 if(AllDead) { 1259 MO.setIsKill(true); 1260 toggleBundleKillFlag(MI, MO.getReg(), true); 1261 } 1262 return false; 1263} 1264 1265// FIXME: Reuse the LivePhysRegs utility for this. 1266void ScheduleDAGInstrs::fixupKills(MachineBasicBlock *MBB) { 1267 DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 1268 1269 LiveRegs.resize(TRI->getNumRegs()); 1270 BitVector killedRegs(TRI->getNumRegs()); 1271 1272 startBlockForKills(MBB); 1273 1274 // Examine block from end to start... 1275 unsigned Count = MBB->size(); 1276 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 1277 I != E; --Count) { 1278 MachineInstr *MI = --I; 1279 if (MI->isDebugValue()) 1280 continue; 1281 1282 // Update liveness. Registers that are defed but not used in this 1283 // instruction are now dead. Mark register and all subregs as they 1284 // are completely defined. 1285 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1286 MachineOperand &MO = MI->getOperand(i); 1287 if (MO.isRegMask()) 1288 LiveRegs.clearBitsNotInMask(MO.getRegMask()); 1289 if (!MO.isReg()) continue; 1290 unsigned Reg = MO.getReg(); 1291 if (Reg == 0) continue; 1292 if (!MO.isDef()) continue; 1293 // Ignore two-addr defs. 1294 if (MI->isRegTiedToUseOperand(i)) continue; 1295 1296 // Repeat for reg and all subregs. 1297 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 1298 SubRegs.isValid(); ++SubRegs) 1299 LiveRegs.reset(*SubRegs); 1300 } 1301 1302 // Examine all used registers and set/clear kill flag. When a 1303 // register is used multiple times we only set the kill flag on 1304 // the first use. Don't set kill flags on undef operands. 1305 killedRegs.reset(); 1306 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1307 MachineOperand &MO = MI->getOperand(i); 1308 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 1309 unsigned Reg = MO.getReg(); 1310 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 1311 1312 bool kill = false; 1313 if (!killedRegs.test(Reg)) { 1314 kill = true; 1315 // A register is not killed if any subregs are live... 1316 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 1317 if (LiveRegs.test(*SubRegs)) { 1318 kill = false; 1319 break; 1320 } 1321 } 1322 1323 // If subreg is not live, then register is killed if it became 1324 // live in this instruction 1325 if (kill) 1326 kill = !LiveRegs.test(Reg); 1327 } 1328 1329 if (MO.isKill() != kill) { 1330 DEBUG(dbgs() << "Fixing " << MO << " in "); 1331 // Warning: toggleKillFlag may invalidate MO. 1332 toggleKillFlag(MI, MO); 1333 DEBUG(MI->dump()); 1334 DEBUG(if (MI->getOpcode() == TargetOpcode::BUNDLE) { 1335 MachineBasicBlock::instr_iterator Begin = MI->getIterator(); 1336 MachineBasicBlock::instr_iterator End = getBundleEnd(MI); 1337 while (++Begin != End) 1338 DEBUG(Begin->dump()); 1339 }); 1340 } 1341 1342 killedRegs.set(Reg); 1343 } 1344 1345 // Mark any used register (that is not using undef) and subregs as 1346 // now live... 1347 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1348 MachineOperand &MO = MI->getOperand(i); 1349 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 1350 unsigned Reg = MO.getReg(); 1351 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 1352 1353 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 1354 SubRegs.isValid(); ++SubRegs) 1355 LiveRegs.set(*SubRegs); 1356 } 1357 } 1358} 1359 1360void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 1361#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1362 SU->getInstr()->dump(); 1363#endif 1364} 1365 1366std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 1367 std::string s; 1368 raw_string_ostream oss(s); 1369 if (SU == &EntrySU) 1370 oss << "<entry>"; 1371 else if (SU == &ExitSU) 1372 oss << "<exit>"; 1373 else 1374 SU->getInstr()->print(oss, /*SkipOpers=*/true); 1375 return oss.str(); 1376} 1377 1378/// Return the basic block label. It is not necessarilly unique because a block 1379/// contains multiple scheduling regions. But it is fine for visualization. 1380std::string ScheduleDAGInstrs::getDAGName() const { 1381 return "dag." + BB->getFullName(); 1382} 1383 1384//===----------------------------------------------------------------------===// 1385// SchedDFSResult Implementation 1386//===----------------------------------------------------------------------===// 1387 1388namespace llvm { 1389/// \brief Internal state used to compute SchedDFSResult. 1390class SchedDFSImpl { 1391 SchedDFSResult &R; 1392 1393 /// Join DAG nodes into equivalence classes by their subtree. 1394 IntEqClasses SubtreeClasses; 1395 /// List PredSU, SuccSU pairs that represent data edges between subtrees. 1396 std::vector<std::pair<const SUnit*, const SUnit*> > ConnectionPairs; 1397 1398 struct RootData { 1399 unsigned NodeID; 1400 unsigned ParentNodeID; // Parent node (member of the parent subtree). 1401 unsigned SubInstrCount; // Instr count in this tree only, not children. 1402 1403 RootData(unsigned id): NodeID(id), 1404 ParentNodeID(SchedDFSResult::InvalidSubtreeID), 1405 SubInstrCount(0) {} 1406 1407 unsigned getSparseSetIndex() const { return NodeID; } 1408 }; 1409 1410 SparseSet<RootData> RootSet; 1411 1412public: 1413 SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) { 1414 RootSet.setUniverse(R.DFSNodeData.size()); 1415 } 1416 1417 /// Return true if this node been visited by the DFS traversal. 1418 /// 1419 /// During visitPostorderNode the Node's SubtreeID is assigned to the Node 1420 /// ID. Later, SubtreeID is updated but remains valid. 1421 bool isVisited(const SUnit *SU) const { 1422 return R.DFSNodeData[SU->NodeNum].SubtreeID 1423 != SchedDFSResult::InvalidSubtreeID; 1424 } 1425 1426 /// Initialize this node's instruction count. We don't need to flag the node 1427 /// visited until visitPostorder because the DAG cannot have cycles. 1428 void visitPreorder(const SUnit *SU) { 1429 R.DFSNodeData[SU->NodeNum].InstrCount = 1430 SU->getInstr()->isTransient() ? 0 : 1; 1431 } 1432 1433 /// Called once for each node after all predecessors are visited. Revisit this 1434 /// node's predecessors and potentially join them now that we know the ILP of 1435 /// the other predecessors. 1436 void visitPostorderNode(const SUnit *SU) { 1437 // Mark this node as the root of a subtree. It may be joined with its 1438 // successors later. 1439 R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum; 1440 RootData RData(SU->NodeNum); 1441 RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1; 1442 1443 // If any predecessors are still in their own subtree, they either cannot be 1444 // joined or are large enough to remain separate. If this parent node's 1445 // total instruction count is not greater than a child subtree by at least 1446 // the subtree limit, then try to join it now since splitting subtrees is 1447 // only useful if multiple high-pressure paths are possible. 1448 unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount; 1449 for (SUnit::const_pred_iterator 1450 PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) { 1451 if (PI->getKind() != SDep::Data) 1452 continue; 1453 unsigned PredNum = PI->getSUnit()->NodeNum; 1454 if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit) 1455 joinPredSubtree(*PI, SU, /*CheckLimit=*/false); 1456 1457 // Either link or merge the TreeData entry from the child to the parent. 1458 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) { 1459 // If the predecessor's parent is invalid, this is a tree edge and the 1460 // current node is the parent. 1461 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID) 1462 RootSet[PredNum].ParentNodeID = SU->NodeNum; 1463 } 1464 else if (RootSet.count(PredNum)) { 1465 // The predecessor is not a root, but is still in the root set. This 1466 // must be the new parent that it was just joined to. Note that 1467 // RootSet[PredNum].ParentNodeID may either be invalid or may still be 1468 // set to the original parent. 1469 RData.SubInstrCount += RootSet[PredNum].SubInstrCount; 1470 RootSet.erase(PredNum); 1471 } 1472 } 1473 RootSet[SU->NodeNum] = RData; 1474 } 1475 1476 /// Called once for each tree edge after calling visitPostOrderNode on the 1477 /// predecessor. Increment the parent node's instruction count and 1478 /// preemptively join this subtree to its parent's if it is small enough. 1479 void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) { 1480 R.DFSNodeData[Succ->NodeNum].InstrCount 1481 += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount; 1482 joinPredSubtree(PredDep, Succ); 1483 } 1484 1485 /// Add a connection for cross edges. 1486 void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) { 1487 ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ)); 1488 } 1489 1490 /// Set each node's subtree ID to the representative ID and record connections 1491 /// between trees. 1492 void finalize() { 1493 SubtreeClasses.compress(); 1494 R.DFSTreeData.resize(SubtreeClasses.getNumClasses()); 1495 assert(SubtreeClasses.getNumClasses() == RootSet.size() 1496 && "number of roots should match trees"); 1497 for (SparseSet<RootData>::const_iterator 1498 RI = RootSet.begin(), RE = RootSet.end(); RI != RE; ++RI) { 1499 unsigned TreeID = SubtreeClasses[RI->NodeID]; 1500 if (RI->ParentNodeID != SchedDFSResult::InvalidSubtreeID) 1501 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[RI->ParentNodeID]; 1502 R.DFSTreeData[TreeID].SubInstrCount = RI->SubInstrCount; 1503 // Note that SubInstrCount may be greater than InstrCount if we joined 1504 // subtrees across a cross edge. InstrCount will be attributed to the 1505 // original parent, while SubInstrCount will be attributed to the joined 1506 // parent. 1507 } 1508 R.SubtreeConnections.resize(SubtreeClasses.getNumClasses()); 1509 R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses()); 1510 DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n"); 1511 for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) { 1512 R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx]; 1513 DEBUG(dbgs() << " SU(" << Idx << ") in tree " 1514 << R.DFSNodeData[Idx].SubtreeID << '\n'); 1515 } 1516 for (std::vector<std::pair<const SUnit*, const SUnit*> >::const_iterator 1517 I = ConnectionPairs.begin(), E = ConnectionPairs.end(); 1518 I != E; ++I) { 1519 unsigned PredTree = SubtreeClasses[I->first->NodeNum]; 1520 unsigned SuccTree = SubtreeClasses[I->second->NodeNum]; 1521 if (PredTree == SuccTree) 1522 continue; 1523 unsigned Depth = I->first->getDepth(); 1524 addConnection(PredTree, SuccTree, Depth); 1525 addConnection(SuccTree, PredTree, Depth); 1526 } 1527 } 1528 1529protected: 1530 /// Join the predecessor subtree with the successor that is its DFS 1531 /// parent. Apply some heuristics before joining. 1532 bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, 1533 bool CheckLimit = true) { 1534 assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges"); 1535 1536 // Check if the predecessor is already joined. 1537 const SUnit *PredSU = PredDep.getSUnit(); 1538 unsigned PredNum = PredSU->NodeNum; 1539 if (R.DFSNodeData[PredNum].SubtreeID != PredNum) 1540 return false; 1541 1542 // Four is the magic number of successors before a node is considered a 1543 // pinch point. 1544 unsigned NumDataSucs = 0; 1545 for (SUnit::const_succ_iterator SI = PredSU->Succs.begin(), 1546 SE = PredSU->Succs.end(); SI != SE; ++SI) { 1547 if (SI->getKind() == SDep::Data) { 1548 if (++NumDataSucs >= 4) 1549 return false; 1550 } 1551 } 1552 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit) 1553 return false; 1554 R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum; 1555 SubtreeClasses.join(Succ->NodeNum, PredNum); 1556 return true; 1557 } 1558 1559 /// Called by finalize() to record a connection between trees. 1560 void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) { 1561 if (!Depth) 1562 return; 1563 1564 do { 1565 SmallVectorImpl<SchedDFSResult::Connection> &Connections = 1566 R.SubtreeConnections[FromTree]; 1567 for (SmallVectorImpl<SchedDFSResult::Connection>::iterator 1568 I = Connections.begin(), E = Connections.end(); I != E; ++I) { 1569 if (I->TreeID == ToTree) { 1570 I->Level = std::max(I->Level, Depth); 1571 return; 1572 } 1573 } 1574 Connections.push_back(SchedDFSResult::Connection(ToTree, Depth)); 1575 FromTree = R.DFSTreeData[FromTree].ParentTreeID; 1576 } while (FromTree != SchedDFSResult::InvalidSubtreeID); 1577 } 1578}; 1579} // namespace llvm 1580 1581namespace { 1582/// \brief Manage the stack used by a reverse depth-first search over the DAG. 1583class SchedDAGReverseDFS { 1584 std::vector<std::pair<const SUnit*, SUnit::const_pred_iterator> > DFSStack; 1585public: 1586 bool isComplete() const { return DFSStack.empty(); } 1587 1588 void follow(const SUnit *SU) { 1589 DFSStack.push_back(std::make_pair(SU, SU->Preds.begin())); 1590 } 1591 void advance() { ++DFSStack.back().second; } 1592 1593 const SDep *backtrack() { 1594 DFSStack.pop_back(); 1595 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second); 1596 } 1597 1598 const SUnit *getCurr() const { return DFSStack.back().first; } 1599 1600 SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; } 1601 1602 SUnit::const_pred_iterator getPredEnd() const { 1603 return getCurr()->Preds.end(); 1604 } 1605}; 1606} // anonymous 1607 1608static bool hasDataSucc(const SUnit *SU) { 1609 for (SUnit::const_succ_iterator 1610 SI = SU->Succs.begin(), SE = SU->Succs.end(); SI != SE; ++SI) { 1611 if (SI->getKind() == SDep::Data && !SI->getSUnit()->isBoundaryNode()) 1612 return true; 1613 } 1614 return false; 1615} 1616 1617/// Compute an ILP metric for all nodes in the subDAG reachable via depth-first 1618/// search from this root. 1619void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) { 1620 if (!IsBottomUp) 1621 llvm_unreachable("Top-down ILP metric is unimplemnted"); 1622 1623 SchedDFSImpl Impl(*this); 1624 for (ArrayRef<SUnit>::const_iterator 1625 SI = SUnits.begin(), SE = SUnits.end(); SI != SE; ++SI) { 1626 const SUnit *SU = &*SI; 1627 if (Impl.isVisited(SU) || hasDataSucc(SU)) 1628 continue; 1629 1630 SchedDAGReverseDFS DFS; 1631 Impl.visitPreorder(SU); 1632 DFS.follow(SU); 1633 for (;;) { 1634 // Traverse the leftmost path as far as possible. 1635 while (DFS.getPred() != DFS.getPredEnd()) { 1636 const SDep &PredDep = *DFS.getPred(); 1637 DFS.advance(); 1638 // Ignore non-data edges. 1639 if (PredDep.getKind() != SDep::Data 1640 || PredDep.getSUnit()->isBoundaryNode()) { 1641 continue; 1642 } 1643 // An already visited edge is a cross edge, assuming an acyclic DAG. 1644 if (Impl.isVisited(PredDep.getSUnit())) { 1645 Impl.visitCrossEdge(PredDep, DFS.getCurr()); 1646 continue; 1647 } 1648 Impl.visitPreorder(PredDep.getSUnit()); 1649 DFS.follow(PredDep.getSUnit()); 1650 } 1651 // Visit the top of the stack in postorder and backtrack. 1652 const SUnit *Child = DFS.getCurr(); 1653 const SDep *PredDep = DFS.backtrack(); 1654 Impl.visitPostorderNode(Child); 1655 if (PredDep) 1656 Impl.visitPostorderEdge(*PredDep, DFS.getCurr()); 1657 if (DFS.isComplete()) 1658 break; 1659 } 1660 } 1661 Impl.finalize(); 1662} 1663 1664/// The root of the given SubtreeID was just scheduled. For all subtrees 1665/// connected to this tree, record the depth of the connection so that the 1666/// nearest connected subtrees can be prioritized. 1667void SchedDFSResult::scheduleTree(unsigned SubtreeID) { 1668 for (SmallVectorImpl<Connection>::const_iterator 1669 I = SubtreeConnections[SubtreeID].begin(), 1670 E = SubtreeConnections[SubtreeID].end(); I != E; ++I) { 1671 SubtreeConnectLevels[I->TreeID] = 1672 std::max(SubtreeConnectLevels[I->TreeID], I->Level); 1673 DEBUG(dbgs() << " Tree: " << I->TreeID 1674 << " @" << SubtreeConnectLevels[I->TreeID] << '\n'); 1675 } 1676} 1677 1678LLVM_DUMP_METHOD 1679void ILPValue::print(raw_ostream &OS) const { 1680 OS << InstrCount << " / " << Length << " = "; 1681 if (!Length) 1682 OS << "BADILP"; 1683 else 1684 OS << format("%g", ((double)InstrCount / Length)); 1685} 1686 1687LLVM_DUMP_METHOD 1688void ILPValue::dump() const { 1689 dbgs() << *this << '\n'; 1690} 1691 1692namespace llvm { 1693 1694LLVM_DUMP_METHOD 1695raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) { 1696 Val.print(OS); 1697 return OS; 1698} 1699 1700} // namespace llvm 1701