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 "llvm/Operator.h" 17#include "llvm/Analysis/AliasAnalysis.h" 18#include "llvm/Analysis/ValueTracking.h" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "llvm/CodeGen/MachineFunctionPass.h" 21#include "llvm/CodeGen/MachineMemOperand.h" 22#include "llvm/CodeGen/MachineRegisterInfo.h" 23#include "llvm/CodeGen/PseudoSourceValue.h" 24#include "llvm/CodeGen/RegisterPressure.h" 25#include "llvm/CodeGen/ScheduleDAGInstrs.h" 26#include "llvm/MC/MCInstrItineraries.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetRegisterInfo.h" 30#include "llvm/Target/TargetSubtargetInfo.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/Support/raw_ostream.h" 34#include "llvm/ADT/SmallSet.h" 35#include "llvm/ADT/SmallPtrSet.h" 36using namespace llvm; 37 38static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, 39 cl::ZeroOrMore, cl::init(false), 40 cl::desc("Enable use of AA during MI GAD construction")); 41 42ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 43 const MachineLoopInfo &mli, 44 const MachineDominatorTree &mdt, 45 bool IsPostRAFlag, 46 LiveIntervals *lis) 47 : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), 48 InstrItins(mf.getTarget().getInstrItineraryData()), LIS(lis), 49 IsPostRA(IsPostRAFlag), UnitLatencies(false), CanHandleTerminators(false), 50 LoopRegs(MDT), FirstDbgValue(0) { 51 assert((IsPostRA || LIS) && "PreRA scheduling requires LiveIntervals"); 52 DbgValues.clear(); 53 assert(!(IsPostRA && MRI.getNumVirtRegs()) && 54 "Virtual registers must be removed prior to PostRA scheduling"); 55} 56 57/// getUnderlyingObjectFromInt - This is the function that does the work of 58/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 59static const Value *getUnderlyingObjectFromInt(const Value *V) { 60 do { 61 if (const Operator *U = dyn_cast<Operator>(V)) { 62 // If we find a ptrtoint, we can transfer control back to the 63 // regular getUnderlyingObjectFromInt. 64 if (U->getOpcode() == Instruction::PtrToInt) 65 return U->getOperand(0); 66 // If we find an add of a constant or a multiplied value, it's 67 // likely that the other operand will lead us to the base 68 // object. We don't have to worry about the case where the 69 // object address is somehow being computed by the multiply, 70 // because our callers only care when the result is an 71 // identifibale object. 72 if (U->getOpcode() != Instruction::Add || 73 (!isa<ConstantInt>(U->getOperand(1)) && 74 Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) 75 return V; 76 V = U->getOperand(0); 77 } else { 78 return V; 79 } 80 assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 81 } while (1); 82} 83 84/// getUnderlyingObject - This is a wrapper around GetUnderlyingObject 85/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 86static const Value *getUnderlyingObject(const Value *V) { 87 // First just call Value::getUnderlyingObject to let it do what it does. 88 do { 89 V = GetUnderlyingObject(V); 90 // If it found an inttoptr, use special code to continue climing. 91 if (Operator::getOpcode(V) != Instruction::IntToPtr) 92 break; 93 const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 94 // If that succeeded in finding a pointer, continue the search. 95 if (!O->getType()->isPointerTy()) 96 break; 97 V = O; 98 } while (1); 99 return V; 100} 101 102/// getUnderlyingObjectForInstr - If this machine instr has memory reference 103/// information and it can be tracked to a normal reference to a known 104/// object, return the Value for that object. Otherwise return null. 105static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, 106 const MachineFrameInfo *MFI, 107 bool &MayAlias) { 108 MayAlias = true; 109 if (!MI->hasOneMemOperand() || 110 !(*MI->memoperands_begin())->getValue() || 111 (*MI->memoperands_begin())->isVolatile()) 112 return 0; 113 114 const Value *V = (*MI->memoperands_begin())->getValue(); 115 if (!V) 116 return 0; 117 118 V = getUnderlyingObject(V); 119 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 120 // For now, ignore PseudoSourceValues which may alias LLVM IR values 121 // because the code that uses this function has no way to cope with 122 // such aliases. 123 if (PSV->isAliased(MFI)) 124 return 0; 125 126 MayAlias = PSV->mayAlias(MFI); 127 return V; 128 } 129 130 if (isIdentifiedObject(V)) 131 return V; 132 133 return 0; 134} 135 136void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { 137 BB = bb; 138 LoopRegs.Deps.clear(); 139 if (MachineLoop *ML = MLI.getLoopFor(BB)) 140 if (BB == ML->getLoopLatch()) 141 LoopRegs.VisitLoop(ML); 142} 143 144void ScheduleDAGInstrs::finishBlock() { 145 // Subclasses should no longer refer to the old block. 146 BB = 0; 147} 148 149/// Initialize the map with the number of registers. 150void Reg2SUnitsMap::setRegLimit(unsigned Limit) { 151 PhysRegSet.setUniverse(Limit); 152 SUnits.resize(Limit); 153} 154 155/// Clear the map without deallocating storage. 156void Reg2SUnitsMap::clear() { 157 for (const_iterator I = reg_begin(), E = reg_end(); I != E; ++I) { 158 SUnits[*I].clear(); 159 } 160 PhysRegSet.clear(); 161} 162 163/// Initialize the DAG and common scheduler state for the current scheduling 164/// region. This does not actually create the DAG, only clears it. The 165/// scheduling driver may call BuildSchedGraph multiple times per scheduling 166/// region. 167void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, 168 MachineBasicBlock::iterator begin, 169 MachineBasicBlock::iterator end, 170 unsigned endcount) { 171 assert(bb == BB && "startBlock should set BB"); 172 RegionBegin = begin; 173 RegionEnd = end; 174 EndIndex = endcount; 175 MISUnitMap.clear(); 176 177 // Check to see if the scheduler cares about latencies. 178 UnitLatencies = forceUnitLatencies(); 179 180 ScheduleDAG::clearDAG(); 181} 182 183/// Close the current scheduling region. Don't clear any state in case the 184/// driver wants to refer to the previous scheduling region. 185void ScheduleDAGInstrs::exitRegion() { 186 // Nothing to do. 187} 188 189/// addSchedBarrierDeps - Add dependencies from instructions in the current 190/// list of instructions being scheduled to scheduling barrier by adding 191/// the exit SU to the register defs and use list. This is because we want to 192/// make sure instructions which define registers that are either used by 193/// the terminator or are live-out are properly scheduled. This is 194/// especially important when the definition latency of the return value(s) 195/// are too high to be hidden by the branch or when the liveout registers 196/// used by instructions in the fallthrough block. 197void ScheduleDAGInstrs::addSchedBarrierDeps() { 198 MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : 0; 199 ExitSU.setInstr(ExitMI); 200 bool AllDepKnown = ExitMI && 201 (ExitMI->isCall() || ExitMI->isBarrier()); 202 if (ExitMI && AllDepKnown) { 203 // If it's a call or a barrier, add dependencies on the defs and uses of 204 // instruction. 205 for (unsigned i = 0, e = ExitMI->getNumOperands(); i != e; ++i) { 206 const MachineOperand &MO = ExitMI->getOperand(i); 207 if (!MO.isReg() || MO.isDef()) continue; 208 unsigned Reg = MO.getReg(); 209 if (Reg == 0) continue; 210 211 if (TRI->isPhysicalRegister(Reg)) 212 Uses[Reg].push_back(PhysRegSUOper(&ExitSU, -1)); 213 else { 214 assert(!IsPostRA && "Virtual register encountered after regalloc."); 215 addVRegUseDeps(&ExitSU, i); 216 } 217 } 218 } else { 219 // For others, e.g. fallthrough, conditional branch, assume the exit 220 // uses all the registers that are livein to the successor blocks. 221 assert(Uses.empty() && "Uses in set before adding deps?"); 222 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 223 SE = BB->succ_end(); SI != SE; ++SI) 224 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 225 E = (*SI)->livein_end(); I != E; ++I) { 226 unsigned Reg = *I; 227 if (!Uses.contains(Reg)) 228 Uses[Reg].push_back(PhysRegSUOper(&ExitSU, -1)); 229 } 230 } 231} 232 233/// MO is an operand of SU's instruction that defines a physical register. Add 234/// data dependencies from SU to any uses of the physical register. 235void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { 236 const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx); 237 assert(MO.isDef() && "expect physreg def"); 238 239 // Ask the target if address-backscheduling is desirable, and if so how much. 240 const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 241 unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 242 unsigned DataLatency = SU->Latency; 243 244 for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 245 Alias.isValid(); ++Alias) { 246 if (!Uses.contains(*Alias)) 247 continue; 248 std::vector<PhysRegSUOper> &UseList = Uses[*Alias]; 249 for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 250 SUnit *UseSU = UseList[i].SU; 251 if (UseSU == SU) 252 continue; 253 MachineInstr *UseMI = UseSU->getInstr(); 254 int UseOp = UseList[i].OpIdx; 255 unsigned LDataLatency = DataLatency; 256 // Optionally add in a special extra latency for nodes that 257 // feed addresses. 258 // TODO: Perhaps we should get rid of 259 // SpecialAddressLatency and just move this into 260 // adjustSchedDependency for the targets that care about it. 261 if (SpecialAddressLatency != 0 && !UnitLatencies && 262 UseSU != &ExitSU) { 263 const MCInstrDesc &UseMCID = UseMI->getDesc(); 264 int RegUseIndex = UseMI->findRegisterUseOperandIdx(*Alias); 265 assert(RegUseIndex >= 0 && "UseMI doesn't use register!"); 266 if (RegUseIndex >= 0 && 267 (UseMI->mayLoad() || UseMI->mayStore()) && 268 (unsigned)RegUseIndex < UseMCID.getNumOperands() && 269 UseMCID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 270 LDataLatency += SpecialAddressLatency; 271 } 272 // Adjust the dependence latency using operand def/use 273 // information (if any), and then allow the target to 274 // perform its own adjustments. 275 SDep dep(SU, SDep::Data, LDataLatency, *Alias); 276 if (!UnitLatencies) { 277 unsigned Latency = 278 TII->computeOperandLatency(InstrItins, SU->getInstr(), OperIdx, 279 (UseOp < 0 ? 0 : UseMI), UseOp); 280 dep.setLatency(Latency); 281 unsigned MinLatency = 282 TII->computeOperandLatency(InstrItins, SU->getInstr(), OperIdx, 283 (UseOp < 0 ? 0 : UseMI), UseOp, 284 /*FindMin=*/true); 285 dep.setMinLatency(MinLatency); 286 287 ST.adjustSchedDependency(SU, UseSU, dep); 288 } 289 UseSU->addPred(dep); 290 } 291 } 292} 293 294/// addPhysRegDeps - Add register dependencies (data, anti, and output) from 295/// this SUnit to following instructions in the same scheduling region that 296/// depend the physical register referenced at OperIdx. 297void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { 298 const MachineInstr *MI = SU->getInstr(); 299 const MachineOperand &MO = MI->getOperand(OperIdx); 300 301 // Optionally add output and anti dependencies. For anti 302 // dependencies we use a latency of 0 because for a multi-issue 303 // target we want to allow the defining instruction to issue 304 // in the same cycle as the using instruction. 305 // TODO: Using a latency of 1 here for output dependencies assumes 306 // there's no cost for reusing registers. 307 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 308 for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 309 Alias.isValid(); ++Alias) { 310 if (!Defs.contains(*Alias)) 311 continue; 312 std::vector<PhysRegSUOper> &DefList = Defs[*Alias]; 313 for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 314 SUnit *DefSU = DefList[i].SU; 315 if (DefSU == &ExitSU) 316 continue; 317 if (DefSU != SU && 318 (Kind != SDep::Output || !MO.isDead() || 319 !DefSU->getInstr()->registerDefIsDead(*Alias))) { 320 if (Kind == SDep::Anti) 321 DefSU->addPred(SDep(SU, Kind, 0, /*Reg=*/*Alias)); 322 else { 323 unsigned AOLat = TII->getOutputLatency(InstrItins, MI, OperIdx, 324 DefSU->getInstr()); 325 DefSU->addPred(SDep(SU, Kind, AOLat, /*Reg=*/*Alias)); 326 } 327 } 328 } 329 } 330 331 if (!MO.isDef()) { 332 // Either insert a new Reg2SUnits entry with an empty SUnits list, or 333 // retrieve the existing SUnits list for this register's uses. 334 // Push this SUnit on the use list. 335 Uses[MO.getReg()].push_back(PhysRegSUOper(SU, OperIdx)); 336 } 337 else { 338 addPhysRegDataDeps(SU, OperIdx); 339 340 // Either insert a new Reg2SUnits entry with an empty SUnits list, or 341 // retrieve the existing SUnits list for this register's defs. 342 std::vector<PhysRegSUOper> &DefList = Defs[MO.getReg()]; 343 344 // If a def is going to wrap back around to the top of the loop, 345 // backschedule it. 346 if (!UnitLatencies && DefList.empty()) { 347 LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(MO.getReg()); 348 if (I != LoopRegs.Deps.end()) { 349 const MachineOperand *UseMO = I->second.first; 350 unsigned Count = I->second.second; 351 const MachineInstr *UseMI = UseMO->getParent(); 352 unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 353 const MCInstrDesc &UseMCID = UseMI->getDesc(); 354 const TargetSubtargetInfo &ST = 355 TM.getSubtarget<TargetSubtargetInfo>(); 356 unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 357 // TODO: If we knew the total depth of the region here, we could 358 // handle the case where the whole loop is inside the region but 359 // is large enough that the isScheduleHigh trick isn't needed. 360 if (UseMOIdx < UseMCID.getNumOperands()) { 361 // Currently, we only support scheduling regions consisting of 362 // single basic blocks. Check to see if the instruction is in 363 // the same region by checking to see if it has the same parent. 364 if (UseMI->getParent() != MI->getParent()) { 365 unsigned Latency = SU->Latency; 366 if (UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 367 Latency += SpecialAddressLatency; 368 // This is a wild guess as to the portion of the latency which 369 // will be overlapped by work done outside the current 370 // scheduling region. 371 Latency -= std::min(Latency, Count); 372 // Add the artificial edge. 373 ExitSU.addPred(SDep(SU, SDep::Order, Latency, 374 /*Reg=*/0, /*isNormalMemory=*/false, 375 /*isMustAlias=*/false, 376 /*isArtificial=*/true)); 377 } else if (SpecialAddressLatency > 0 && 378 UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 379 // The entire loop body is within the current scheduling region 380 // and the latency of this operation is assumed to be greater 381 // than the latency of the loop. 382 // TODO: Recursively mark data-edge predecessors as 383 // isScheduleHigh too. 384 SU->isScheduleHigh = true; 385 } 386 } 387 LoopRegs.Deps.erase(I); 388 } 389 } 390 391 // clear this register's use list 392 if (Uses.contains(MO.getReg())) 393 Uses[MO.getReg()].clear(); 394 395 if (!MO.isDead()) 396 DefList.clear(); 397 398 // Calls will not be reordered because of chain dependencies (see 399 // below). Since call operands are dead, calls may continue to be added 400 // to the DefList making dependence checking quadratic in the size of 401 // the block. Instead, we leave only one call at the back of the 402 // DefList. 403 if (SU->isCall) { 404 while (!DefList.empty() && DefList.back().SU->isCall) 405 DefList.pop_back(); 406 } 407 // Defs are pushed in the order they are visited and never reordered. 408 DefList.push_back(PhysRegSUOper(SU, OperIdx)); 409 } 410} 411 412/// addVRegDefDeps - Add register output and data dependencies from this SUnit 413/// to instructions that occur later in the same scheduling region if they read 414/// from or write to the virtual register defined at OperIdx. 415/// 416/// TODO: Hoist loop induction variable increments. This has to be 417/// reevaluated. Generally, IV scheduling should be done before coalescing. 418void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { 419 const MachineInstr *MI = SU->getInstr(); 420 unsigned Reg = MI->getOperand(OperIdx).getReg(); 421 422 // Singly defined vregs do not have output/anti dependencies. 423 // The current operand is a def, so we have at least one. 424 // Check here if there are any others... 425 if (MRI.hasOneDef(Reg)) 426 return; 427 428 // Add output dependence to the next nearest def of this vreg. 429 // 430 // Unless this definition is dead, the output dependence should be 431 // transitively redundant with antidependencies from this definition's 432 // uses. We're conservative for now until we have a way to guarantee the uses 433 // are not eliminated sometime during scheduling. The output dependence edge 434 // is also useful if output latency exceeds def-use latency. 435 VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); 436 if (DefI == VRegDefs.end()) 437 VRegDefs.insert(VReg2SUnit(Reg, SU)); 438 else { 439 SUnit *DefSU = DefI->SU; 440 if (DefSU != SU && DefSU != &ExitSU) { 441 unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx, 442 DefSU->getInstr()); 443 DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg)); 444 } 445 DefI->SU = SU; 446 } 447} 448 449/// addVRegUseDeps - Add a register data dependency if the instruction that 450/// defines the virtual register used at OperIdx is mapped to an SUnit. Add a 451/// register antidependency from this SUnit to instructions that occur later in 452/// the same scheduling region if they write the virtual register. 453/// 454/// TODO: Handle ExitSU "uses" properly. 455void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { 456 MachineInstr *MI = SU->getInstr(); 457 unsigned Reg = MI->getOperand(OperIdx).getReg(); 458 459 // Lookup this operand's reaching definition. 460 assert(LIS && "vreg dependencies requires LiveIntervals"); 461 LiveRangeQuery LRQ(LIS->getInterval(Reg), LIS->getInstructionIndex(MI)); 462 VNInfo *VNI = LRQ.valueIn(); 463 464 // VNI will be valid because MachineOperand::readsReg() is checked by caller. 465 assert(VNI && "No value to read by operand"); 466 MachineInstr *Def = LIS->getInstructionFromIndex(VNI->def); 467 // Phis and other noninstructions (after coalescing) have a NULL Def. 468 if (Def) { 469 SUnit *DefSU = getSUnit(Def); 470 if (DefSU) { 471 // The reaching Def lives within this scheduling region. 472 // Create a data dependence. 473 // 474 // TODO: Handle "special" address latencies cleanly. 475 SDep dep(DefSU, SDep::Data, DefSU->Latency, Reg); 476 if (!UnitLatencies) { 477 // Adjust the dependence latency using operand def/use information, then 478 // allow the target to perform its own adjustments. 479 int DefOp = Def->findRegisterDefOperandIdx(Reg); 480 unsigned Latency = 481 TII->computeOperandLatency(InstrItins, Def, DefOp, MI, OperIdx); 482 dep.setLatency(Latency); 483 unsigned MinLatency = 484 TII->computeOperandLatency(InstrItins, Def, DefOp, MI, OperIdx, 485 /*FindMin=*/true); 486 dep.setMinLatency(MinLatency); 487 488 const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 489 ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep)); 490 } 491 SU->addPred(dep); 492 } 493 } 494 495 // Add antidependence to the following def of the vreg it uses. 496 VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); 497 if (DefI != VRegDefs.end() && DefI->SU != SU) 498 DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg)); 499} 500 501/// Return true if MI is an instruction we are unable to reason about 502/// (like a call or something with unmodeled side effects). 503static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { 504 if (MI->isCall() || MI->hasUnmodeledSideEffects() || 505 (MI->hasOrderedMemoryRef() && 506 (!MI->mayLoad() || !MI->isInvariantLoad(AA)))) 507 return true; 508 return false; 509} 510 511// This MI might have either incomplete info, or known to be unsafe 512// to deal with (i.e. volatile object). 513static inline bool isUnsafeMemoryObject(MachineInstr *MI, 514 const MachineFrameInfo *MFI) { 515 if (!MI || MI->memoperands_empty()) 516 return true; 517 // We purposefully do no check for hasOneMemOperand() here 518 // in hope to trigger an assert downstream in order to 519 // finish implementation. 520 if ((*MI->memoperands_begin())->isVolatile() || 521 MI->hasUnmodeledSideEffects()) 522 return true; 523 524 const Value *V = (*MI->memoperands_begin())->getValue(); 525 if (!V) 526 return true; 527 528 V = getUnderlyingObject(V); 529 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 530 // Similarly to getUnderlyingObjectForInstr: 531 // For now, ignore PseudoSourceValues which may alias LLVM IR values 532 // because the code that uses this function has no way to cope with 533 // such aliases. 534 if (PSV->isAliased(MFI)) 535 return true; 536 } 537 // Does this pointer refer to a distinct and identifiable object? 538 if (!isIdentifiedObject(V)) 539 return true; 540 541 return false; 542} 543 544/// This returns true if the two MIs need a chain edge betwee them. 545/// If these are not even memory operations, we still may need 546/// chain deps between them. The question really is - could 547/// these two MIs be reordered during scheduling from memory dependency 548/// point of view. 549static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, 550 MachineInstr *MIa, 551 MachineInstr *MIb) { 552 // Cover a trivial case - no edge is need to itself. 553 if (MIa == MIb) 554 return false; 555 556 if (isUnsafeMemoryObject(MIa, MFI) || isUnsafeMemoryObject(MIb, MFI)) 557 return true; 558 559 // If we are dealing with two "normal" loads, we do not need an edge 560 // between them - they could be reordered. 561 if (!MIa->mayStore() && !MIb->mayStore()) 562 return false; 563 564 // To this point analysis is generic. From here on we do need AA. 565 if (!AA) 566 return true; 567 568 MachineMemOperand *MMOa = *MIa->memoperands_begin(); 569 MachineMemOperand *MMOb = *MIb->memoperands_begin(); 570 571 // FIXME: Need to handle multiple memory operands to support all targets. 572 if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand()) 573 llvm_unreachable("Multiple memory operands."); 574 575 // The following interface to AA is fashioned after DAGCombiner::isAlias 576 // and operates with MachineMemOperand offset with some important 577 // assumptions: 578 // - LLVM fundamentally assumes flat address spaces. 579 // - MachineOperand offset can *only* result from legalization and 580 // cannot affect queries other than the trivial case of overlap 581 // checking. 582 // - These offsets never wrap and never step outside 583 // of allocated objects. 584 // - There should never be any negative offsets here. 585 // 586 // FIXME: Modify API to hide this math from "user" 587 // FIXME: Even before we go to AA we can reason locally about some 588 // memory objects. It can save compile time, and possibly catch some 589 // corner cases not currently covered. 590 591 assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset"); 592 assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset"); 593 594 int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset()); 595 int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset; 596 int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset; 597 598 AliasAnalysis::AliasResult AAResult = AA->alias( 599 AliasAnalysis::Location(MMOa->getValue(), Overlapa, 600 MMOa->getTBAAInfo()), 601 AliasAnalysis::Location(MMOb->getValue(), Overlapb, 602 MMOb->getTBAAInfo())); 603 604 return (AAResult != AliasAnalysis::NoAlias); 605} 606 607/// This recursive function iterates over chain deps of SUb looking for 608/// "latest" node that needs a chain edge to SUa. 609static unsigned 610iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, 611 SUnit *SUa, SUnit *SUb, SUnit *ExitSU, unsigned *Depth, 612 SmallPtrSet<const SUnit*, 16> &Visited) { 613 if (!SUa || !SUb || SUb == ExitSU) 614 return *Depth; 615 616 // Remember visited nodes. 617 if (!Visited.insert(SUb)) 618 return *Depth; 619 // If there is _some_ dependency already in place, do not 620 // descend any further. 621 // TODO: Need to make sure that if that dependency got eliminated or ignored 622 // for any reason in the future, we would not violate DAG topology. 623 // Currently it does not happen, but makes an implicit assumption about 624 // future implementation. 625 // 626 // Independently, if we encounter node that is some sort of global 627 // object (like a call) we already have full set of dependencies to it 628 // and we can stop descending. 629 if (SUa->isSucc(SUb) || 630 isGlobalMemoryObject(AA, SUb->getInstr())) 631 return *Depth; 632 633 // If we do need an edge, or we have exceeded depth budget, 634 // add that edge to the predecessors chain of SUb, 635 // and stop descending. 636 if (*Depth > 200 || 637 MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) { 638 SUb->addPred(SDep(SUa, SDep::Order, /*Latency=*/0, /*Reg=*/0, 639 /*isNormalMemory=*/true)); 640 return *Depth; 641 } 642 // Track current depth. 643 (*Depth)++; 644 // Iterate over chain dependencies only. 645 for (SUnit::const_succ_iterator I = SUb->Succs.begin(), E = SUb->Succs.end(); 646 I != E; ++I) 647 if (I->isCtrl()) 648 iterateChainSucc (AA, MFI, SUa, I->getSUnit(), ExitSU, Depth, Visited); 649 return *Depth; 650} 651 652/// This function assumes that "downward" from SU there exist 653/// tail/leaf of already constructed DAG. It iterates downward and 654/// checks whether SU can be aliasing any node dominated 655/// by it. 656static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, 657 SUnit *SU, SUnit *ExitSU, std::set<SUnit *> &CheckList, 658 unsigned LatencyToLoad) { 659 if (!SU) 660 return; 661 662 SmallPtrSet<const SUnit*, 16> Visited; 663 unsigned Depth = 0; 664 665 for (std::set<SUnit *>::iterator I = CheckList.begin(), IE = CheckList.end(); 666 I != IE; ++I) { 667 if (SU == *I) 668 continue; 669 if (MIsNeedChainEdge(AA, MFI, SU->getInstr(), (*I)->getInstr())) { 670 unsigned Latency = ((*I)->getInstr()->mayLoad()) ? LatencyToLoad : 0; 671 (*I)->addPred(SDep(SU, SDep::Order, Latency, /*Reg=*/0, 672 /*isNormalMemory=*/true)); 673 } 674 // Now go through all the chain successors and iterate from them. 675 // Keep track of visited nodes. 676 for (SUnit::const_succ_iterator J = (*I)->Succs.begin(), 677 JE = (*I)->Succs.end(); J != JE; ++J) 678 if (J->isCtrl()) 679 iterateChainSucc (AA, MFI, SU, J->getSUnit(), 680 ExitSU, &Depth, Visited); 681 } 682} 683 684/// Check whether two objects need a chain edge, if so, add it 685/// otherwise remember the rejected SU. 686static inline 687void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, 688 SUnit *SUa, SUnit *SUb, 689 std::set<SUnit *> &RejectList, 690 unsigned TrueMemOrderLatency = 0, 691 bool isNormalMemory = false) { 692 // If this is a false dependency, 693 // do not add the edge, but rememeber the rejected node. 694 if (!EnableAASchedMI || 695 MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) 696 SUb->addPred(SDep(SUa, SDep::Order, TrueMemOrderLatency, /*Reg=*/0, 697 isNormalMemory)); 698 else { 699 // Duplicate entries should be ignored. 700 RejectList.insert(SUb); 701 DEBUG(dbgs() << "\tReject chain dep between SU(" 702 << SUa->NodeNum << ") and SU(" 703 << SUb->NodeNum << ")\n"); 704 } 705} 706 707/// Create an SUnit for each real instruction, numbered in top-down toplological 708/// order. The instruction order A < B, implies that no edge exists from B to A. 709/// 710/// Map each real instruction to its SUnit. 711/// 712/// After initSUnits, the SUnits vector cannot be resized and the scheduler may 713/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs 714/// instead of pointers. 715/// 716/// MachineScheduler relies on initSUnits numbering the nodes by their order in 717/// the original instruction list. 718void ScheduleDAGInstrs::initSUnits() { 719 // We'll be allocating one SUnit for each real instruction in the region, 720 // which is contained within a basic block. 721 SUnits.reserve(BB->size()); 722 723 for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) { 724 MachineInstr *MI = I; 725 if (MI->isDebugValue()) 726 continue; 727 728 SUnit *SU = newSUnit(MI); 729 MISUnitMap[MI] = SU; 730 731 SU->isCall = MI->isCall(); 732 SU->isCommutable = MI->isCommutable(); 733 734 // Assign the Latency field of SU using target-provided information. 735 if (UnitLatencies) 736 SU->Latency = 1; 737 else 738 computeLatency(SU); 739 } 740} 741 742/// If RegPressure is non null, compute register pressure as a side effect. The 743/// DAG builder is an efficient place to do it because it already visits 744/// operands. 745void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 746 RegPressureTracker *RPTracker) { 747 // Create an SUnit for each real instruction. 748 initSUnits(); 749 750 // We build scheduling units by walking a block's instruction list from bottom 751 // to top. 752 753 // Remember where a generic side-effecting instruction is as we procede. 754 SUnit *BarrierChain = 0, *AliasChain = 0; 755 756 // Memory references to specific known memory locations are tracked 757 // so that they can be given more precise dependencies. We track 758 // separately the known memory locations that may alias and those 759 // that are known not to alias 760 std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; 761 std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 762 std::set<SUnit*> RejectMemNodes; 763 764 // Remove any stale debug info; sometimes BuildSchedGraph is called again 765 // without emitting the info from the previous call. 766 DbgValues.clear(); 767 FirstDbgValue = NULL; 768 769 assert(Defs.empty() && Uses.empty() && 770 "Only BuildGraph should update Defs/Uses"); 771 Defs.setRegLimit(TRI->getNumRegs()); 772 Uses.setRegLimit(TRI->getNumRegs()); 773 774 assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs"); 775 // FIXME: Allow SparseSet to reserve space for the creation of virtual 776 // registers during scheduling. Don't artificially inflate the Universe 777 // because we want to assert that vregs are not created during DAG building. 778 VRegDefs.setUniverse(MRI.getNumVirtRegs()); 779 780 // Model data dependencies between instructions being scheduled and the 781 // ExitSU. 782 addSchedBarrierDeps(); 783 784 // Walk the list of instructions, from bottom moving up. 785 MachineInstr *PrevMI = NULL; 786 for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; 787 MII != MIE; --MII) { 788 MachineInstr *MI = prior(MII); 789 if (MI && PrevMI) { 790 DbgValues.push_back(std::make_pair(PrevMI, MI)); 791 PrevMI = NULL; 792 } 793 794 if (MI->isDebugValue()) { 795 PrevMI = MI; 796 continue; 797 } 798 if (RPTracker) { 799 RPTracker->recede(); 800 assert(RPTracker->getPos() == prior(MII) && "RPTracker can't find MI"); 801 } 802 803 assert((!MI->isTerminator() || CanHandleTerminators) && !MI->isLabel() && 804 "Cannot schedule terminators or labels!"); 805 806 SUnit *SU = MISUnitMap[MI]; 807 assert(SU && "No SUnit mapped to this MI"); 808 809 // Add register-based dependencies (data, anti, and output). 810 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 811 const MachineOperand &MO = MI->getOperand(j); 812 if (!MO.isReg()) continue; 813 unsigned Reg = MO.getReg(); 814 if (Reg == 0) continue; 815 816 if (TRI->isPhysicalRegister(Reg)) 817 addPhysRegDeps(SU, j); 818 else { 819 assert(!IsPostRA && "Virtual register encountered!"); 820 if (MO.isDef()) 821 addVRegDefDeps(SU, j); 822 else if (MO.readsReg()) // ignore undef operands 823 addVRegUseDeps(SU, j); 824 } 825 } 826 827 // Add chain dependencies. 828 // Chain dependencies used to enforce memory order should have 829 // latency of 0 (except for true dependency of Store followed by 830 // aliased Load... we estimate that with a single cycle of latency 831 // assuming the hardware will bypass) 832 // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 833 // after stack slots are lowered to actual addresses. 834 // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 835 // produce more precise dependence information. 836 unsigned TrueMemOrderLatency = MI->mayStore() ? 1 : 0; 837 if (isGlobalMemoryObject(AA, MI)) { 838 // Be conservative with these and add dependencies on all memory 839 // references, even those that are known to not alias. 840 for (std::map<const Value *, SUnit *>::iterator I = 841 NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 842 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 843 } 844 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 845 NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 846 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 847 I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 848 } 849 // Add SU to the barrier chain. 850 if (BarrierChain) 851 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 852 BarrierChain = SU; 853 // This is a barrier event that acts as a pivotal node in the DAG, 854 // so it is safe to clear list of exposed nodes. 855 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, 856 TrueMemOrderLatency); 857 RejectMemNodes.clear(); 858 NonAliasMemDefs.clear(); 859 NonAliasMemUses.clear(); 860 861 // fall-through 862 new_alias_chain: 863 // Chain all possibly aliasing memory references though SU. 864 if (AliasChain) { 865 unsigned ChainLatency = 0; 866 if (AliasChain->getInstr()->mayLoad()) 867 ChainLatency = TrueMemOrderLatency; 868 addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes, 869 ChainLatency); 870 } 871 AliasChain = SU; 872 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 873 addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, 874 TrueMemOrderLatency); 875 for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), 876 E = AliasMemDefs.end(); I != E; ++I) 877 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); 878 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 879 AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 880 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 881 addChainDependency(AA, MFI, SU, I->second[i], RejectMemNodes, 882 TrueMemOrderLatency); 883 } 884 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, 885 TrueMemOrderLatency); 886 PendingLoads.clear(); 887 AliasMemDefs.clear(); 888 AliasMemUses.clear(); 889 } else if (MI->mayStore()) { 890 bool MayAlias = true; 891 if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 892 // A store to a specific PseudoSourceValue. Add precise dependencies. 893 // Record the def in MemDefs, first adding a dep if there is 894 // an existing def. 895 std::map<const Value *, SUnit *>::iterator I = 896 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 897 std::map<const Value *, SUnit *>::iterator IE = 898 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 899 if (I != IE) { 900 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 901 0, true); 902 I->second = SU; 903 } else { 904 if (MayAlias) 905 AliasMemDefs[V] = SU; 906 else 907 NonAliasMemDefs[V] = SU; 908 } 909 // Handle the uses in MemUses, if there are any. 910 std::map<const Value *, std::vector<SUnit *> >::iterator J = 911 ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 912 std::map<const Value *, std::vector<SUnit *> >::iterator JE = 913 ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 914 if (J != JE) { 915 for (unsigned i = 0, e = J->second.size(); i != e; ++i) 916 addChainDependency(AA, MFI, SU, J->second[i], RejectMemNodes, 917 TrueMemOrderLatency, true); 918 J->second.clear(); 919 } 920 if (MayAlias) { 921 // Add dependencies from all the PendingLoads, i.e. loads 922 // with no underlying object. 923 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 924 addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, 925 TrueMemOrderLatency); 926 // Add dependence on alias chain, if needed. 927 if (AliasChain) 928 addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); 929 // But we also should check dependent instructions for the 930 // SU in question. 931 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, 932 TrueMemOrderLatency); 933 } 934 // Add dependence on barrier chain, if needed. 935 // There is no point to check aliasing on barrier event. Even if 936 // SU and barrier _could_ be reordered, they should not. In addition, 937 // we have lost all RejectMemNodes below barrier. 938 if (BarrierChain) 939 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 940 } else { 941 // Treat all other stores conservatively. 942 goto new_alias_chain; 943 } 944 945 if (!ExitSU.isPred(SU)) 946 // Push store's up a bit to avoid them getting in between cmp 947 // and branches. 948 ExitSU.addPred(SDep(SU, SDep::Order, 0, 949 /*Reg=*/0, /*isNormalMemory=*/false, 950 /*isMustAlias=*/false, 951 /*isArtificial=*/true)); 952 } else if (MI->mayLoad()) { 953 bool MayAlias = true; 954 if (MI->isInvariantLoad(AA)) { 955 // Invariant load, no chain dependencies needed! 956 } else { 957 if (const Value *V = 958 getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 959 // A load from a specific PseudoSourceValue. Add precise dependencies. 960 std::map<const Value *, SUnit *>::iterator I = 961 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 962 std::map<const Value *, SUnit *>::iterator IE = 963 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 964 if (I != IE) 965 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); 966 if (MayAlias) 967 AliasMemUses[V].push_back(SU); 968 else 969 NonAliasMemUses[V].push_back(SU); 970 } else { 971 // A load with no underlying object. Depend on all 972 // potentially aliasing stores. 973 for (std::map<const Value *, SUnit *>::iterator I = 974 AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 975 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); 976 977 PendingLoads.push_back(SU); 978 MayAlias = true; 979 } 980 if (MayAlias) 981 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, /*Latency=*/0); 982 // Add dependencies on alias and barrier chains, if needed. 983 if (MayAlias && AliasChain) 984 addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); 985 if (BarrierChain) 986 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 987 } 988 } 989 } 990 if (PrevMI) 991 FirstDbgValue = PrevMI; 992 993 Defs.clear(); 994 Uses.clear(); 995 VRegDefs.clear(); 996 PendingLoads.clear(); 997} 998 999void ScheduleDAGInstrs::computeLatency(SUnit *SU) { 1000 // Compute the latency for the node. We only provide a default for missing 1001 // itineraries. Empty itineraries still have latency properties. 1002 if (!InstrItins) { 1003 SU->Latency = 1; 1004 1005 // Simplistic target-independent heuristic: assume that loads take 1006 // extra time. 1007 if (SU->getInstr()->mayLoad()) 1008 SU->Latency += 2; 1009 } else { 1010 SU->Latency = TII->getInstrLatency(InstrItins, SU->getInstr()); 1011 } 1012} 1013 1014void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 1015#ifndef NDEBUG 1016 SU->getInstr()->dump(); 1017#endif 1018} 1019 1020std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 1021 std::string s; 1022 raw_string_ostream oss(s); 1023 if (SU == &EntrySU) 1024 oss << "<entry>"; 1025 else if (SU == &ExitSU) 1026 oss << "<exit>"; 1027 else 1028 SU->getInstr()->print(oss); 1029 return oss.str(); 1030} 1031 1032/// Return the basic block label. It is not necessarilly unique because a block 1033/// contains multiple scheduling regions. But it is fine for visualization. 1034std::string ScheduleDAGInstrs::getDAGName() const { 1035 return "dag." + BB->getFullName(); 1036} 1037