ScheduleDAGInstrs.cpp revision a7542d5f870c5d98960d1676e23ac1d1d975d7e5
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 "RegisterPressure.h" 17#include "llvm/Operator.h" 18#include "llvm/Analysis/AliasAnalysis.h" 19#include "llvm/Analysis/ValueTracking.h" 20#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21#include "llvm/CodeGen/MachineFunctionPass.h" 22#include "llvm/CodeGen/MachineMemOperand.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/CodeGen/PseudoSourceValue.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(&ExitSU); 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(&ExitSU); 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, 236 const MachineOperand &MO) { 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<SUnit*> &UseList = Uses[*Alias]; 249 for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 250 SUnit *UseSU = UseList[i]; 251 if (UseSU == SU) 252 continue; 253 unsigned LDataLatency = DataLatency; 254 // Optionally add in a special extra latency for nodes that 255 // feed addresses. 256 // TODO: Perhaps we should get rid of 257 // SpecialAddressLatency and just move this into 258 // adjustSchedDependency for the targets that care about it. 259 if (SpecialAddressLatency != 0 && !UnitLatencies && 260 UseSU != &ExitSU) { 261 MachineInstr *UseMI = UseSU->getInstr(); 262 const MCInstrDesc &UseMCID = UseMI->getDesc(); 263 int RegUseIndex = UseMI->findRegisterUseOperandIdx(*Alias); 264 assert(RegUseIndex >= 0 && "UseMI doesn't use register!"); 265 if (RegUseIndex >= 0 && 266 (UseMI->mayLoad() || UseMI->mayStore()) && 267 (unsigned)RegUseIndex < UseMCID.getNumOperands() && 268 UseMCID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 269 LDataLatency += SpecialAddressLatency; 270 } 271 // Adjust the dependence latency using operand def/use 272 // information (if any), and then allow the target to 273 // perform its own adjustments. 274 SDep dep(SU, SDep::Data, LDataLatency, *Alias); 275 if (!UnitLatencies) { 276 unsigned Latency = computeOperandLatency(SU, UseSU, dep); 277 dep.setLatency(Latency); 278 279 ST.adjustSchedDependency(SU, UseSU, dep); 280 } 281 UseSU->addPred(dep); 282 } 283 } 284} 285 286/// addPhysRegDeps - Add register dependencies (data, anti, and output) from 287/// this SUnit to following instructions in the same scheduling region that 288/// depend the physical register referenced at OperIdx. 289void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { 290 const MachineInstr *MI = SU->getInstr(); 291 const MachineOperand &MO = MI->getOperand(OperIdx); 292 293 // Optionally add output and anti dependencies. For anti 294 // dependencies we use a latency of 0 because for a multi-issue 295 // target we want to allow the defining instruction to issue 296 // in the same cycle as the using instruction. 297 // TODO: Using a latency of 1 here for output dependencies assumes 298 // there's no cost for reusing registers. 299 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 300 for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 301 Alias.isValid(); ++Alias) { 302 if (!Defs.contains(*Alias)) 303 continue; 304 std::vector<SUnit *> &DefList = Defs[*Alias]; 305 for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 306 SUnit *DefSU = DefList[i]; 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, 0, /*Reg=*/*Alias)); 314 else { 315 unsigned AOLat = TII->getOutputLatency(InstrItins, MI, OperIdx, 316 DefSU->getInstr()); 317 DefSU->addPred(SDep(SU, Kind, AOLat, /*Reg=*/*Alias)); 318 } 319 } 320 } 321 } 322 323 if (!MO.isDef()) { 324 // Either insert a new Reg2SUnits entry with an empty SUnits list, or 325 // retrieve the existing SUnits list for this register's uses. 326 // Push this SUnit on the use list. 327 Uses[MO.getReg()].push_back(SU); 328 } 329 else { 330 addPhysRegDataDeps(SU, MO); 331 332 // Either insert a new Reg2SUnits entry with an empty SUnits list, or 333 // retrieve the existing SUnits list for this register's defs. 334 std::vector<SUnit *> &DefList = Defs[MO.getReg()]; 335 336 // If a def is going to wrap back around to the top of the loop, 337 // backschedule it. 338 if (!UnitLatencies && DefList.empty()) { 339 LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(MO.getReg()); 340 if (I != LoopRegs.Deps.end()) { 341 const MachineOperand *UseMO = I->second.first; 342 unsigned Count = I->second.second; 343 const MachineInstr *UseMI = UseMO->getParent(); 344 unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 345 const MCInstrDesc &UseMCID = UseMI->getDesc(); 346 const TargetSubtargetInfo &ST = 347 TM.getSubtarget<TargetSubtargetInfo>(); 348 unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 349 // TODO: If we knew the total depth of the region here, we could 350 // handle the case where the whole loop is inside the region but 351 // is large enough that the isScheduleHigh trick isn't needed. 352 if (UseMOIdx < UseMCID.getNumOperands()) { 353 // Currently, we only support scheduling regions consisting of 354 // single basic blocks. Check to see if the instruction is in 355 // the same region by checking to see if it has the same parent. 356 if (UseMI->getParent() != MI->getParent()) { 357 unsigned Latency = SU->Latency; 358 if (UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 359 Latency += SpecialAddressLatency; 360 // This is a wild guess as to the portion of the latency which 361 // will be overlapped by work done outside the current 362 // scheduling region. 363 Latency -= std::min(Latency, Count); 364 // Add the artificial edge. 365 ExitSU.addPred(SDep(SU, SDep::Order, Latency, 366 /*Reg=*/0, /*isNormalMemory=*/false, 367 /*isMustAlias=*/false, 368 /*isArtificial=*/true)); 369 } else if (SpecialAddressLatency > 0 && 370 UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 371 // The entire loop body is within the current scheduling region 372 // and the latency of this operation is assumed to be greater 373 // than the latency of the loop. 374 // TODO: Recursively mark data-edge predecessors as 375 // isScheduleHigh too. 376 SU->isScheduleHigh = true; 377 } 378 } 379 LoopRegs.Deps.erase(I); 380 } 381 } 382 383 // clear this register's use list 384 if (Uses.contains(MO.getReg())) 385 Uses[MO.getReg()].clear(); 386 387 if (!MO.isDead()) 388 DefList.clear(); 389 390 // Calls will not be reordered because of chain dependencies (see 391 // below). Since call operands are dead, calls may continue to be added 392 // to the DefList making dependence checking quadratic in the size of 393 // the block. Instead, we leave only one call at the back of the 394 // DefList. 395 if (SU->isCall) { 396 while (!DefList.empty() && DefList.back()->isCall) 397 DefList.pop_back(); 398 } 399 // Defs are pushed in the order they are visited and never reordered. 400 DefList.push_back(SU); 401 } 402} 403 404/// addVRegDefDeps - Add register output and data dependencies from this SUnit 405/// to instructions that occur later in the same scheduling region if they read 406/// from or write to the virtual register defined at OperIdx. 407/// 408/// TODO: Hoist loop induction variable increments. This has to be 409/// reevaluated. Generally, IV scheduling should be done before coalescing. 410void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { 411 const MachineInstr *MI = SU->getInstr(); 412 unsigned Reg = MI->getOperand(OperIdx).getReg(); 413 414 // SSA defs do not have output/anti dependencies. 415 // The current operand is a def, so we have at least one. 416 if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) 417 return; 418 419 // Add output dependence to the next nearest def of this vreg. 420 // 421 // Unless this definition is dead, the output dependence should be 422 // transitively redundant with antidependencies from this definition's 423 // uses. We're conservative for now until we have a way to guarantee the uses 424 // are not eliminated sometime during scheduling. The output dependence edge 425 // is also useful if output latency exceeds def-use latency. 426 VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); 427 if (DefI == VRegDefs.end()) 428 VRegDefs.insert(VReg2SUnit(Reg, SU)); 429 else { 430 SUnit *DefSU = DefI->SU; 431 if (DefSU != SU && DefSU != &ExitSU) { 432 unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx, 433 DefSU->getInstr()); 434 DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg)); 435 } 436 DefI->SU = SU; 437 } 438} 439 440/// addVRegUseDeps - Add a register data dependency if the instruction that 441/// defines the virtual register used at OperIdx is mapped to an SUnit. Add a 442/// register antidependency from this SUnit to instructions that occur later in 443/// the same scheduling region if they write the virtual register. 444/// 445/// TODO: Handle ExitSU "uses" properly. 446void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { 447 MachineInstr *MI = SU->getInstr(); 448 unsigned Reg = MI->getOperand(OperIdx).getReg(); 449 450 // Lookup this operand's reaching definition. 451 assert(LIS && "vreg dependencies requires LiveIntervals"); 452 LiveRangeQuery LRQ(LIS->getInterval(Reg), LIS->getInstructionIndex(MI)); 453 VNInfo *VNI = LRQ.valueIn(); 454 455 // VNI will be valid because MachineOperand::readsReg() is checked by caller. 456 assert(VNI && "No value to read by operand"); 457 MachineInstr *Def = LIS->getInstructionFromIndex(VNI->def); 458 // Phis and other noninstructions (after coalescing) have a NULL Def. 459 if (Def) { 460 SUnit *DefSU = getSUnit(Def); 461 if (DefSU) { 462 // The reaching Def lives within this scheduling region. 463 // Create a data dependence. 464 // 465 // TODO: Handle "special" address latencies cleanly. 466 SDep dep(DefSU, SDep::Data, DefSU->Latency, Reg); 467 if (!UnitLatencies) { 468 // Adjust the dependence latency using operand def/use information, then 469 // allow the target to perform its own adjustments. 470 unsigned Latency = computeOperandLatency(DefSU, SU, const_cast<SDep &>(dep)); 471 dep.setLatency(Latency); 472 473 const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 474 ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep)); 475 } 476 SU->addPred(dep); 477 } 478 } 479 480 // Add antidependence to the following def of the vreg it uses. 481 VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg); 482 if (DefI != VRegDefs.end() && DefI->SU != SU) 483 DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg)); 484} 485 486/// Return true if MI is an instruction we are unable to reason about 487/// (like a call or something with unmodeled side effects). 488static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { 489 if (MI->isCall() || MI->hasUnmodeledSideEffects() || 490 (MI->hasVolatileMemoryRef() && 491 (!MI->mayLoad() || !MI->isInvariantLoad(AA)))) 492 return true; 493 return false; 494} 495 496// This MI might have either incomplete info, or known to be unsafe 497// to deal with (i.e. volatile object). 498static inline bool isUnsafeMemoryObject(MachineInstr *MI, 499 const MachineFrameInfo *MFI) { 500 if (!MI || MI->memoperands_empty()) 501 return true; 502 // We purposefully do no check for hasOneMemOperand() here 503 // in hope to trigger an assert downstream in order to 504 // finish implementation. 505 if ((*MI->memoperands_begin())->isVolatile() || 506 MI->hasUnmodeledSideEffects()) 507 return true; 508 509 const Value *V = (*MI->memoperands_begin())->getValue(); 510 if (!V) 511 return true; 512 513 V = getUnderlyingObject(V); 514 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 515 // Similarly to getUnderlyingObjectForInstr: 516 // For now, ignore PseudoSourceValues which may alias LLVM IR values 517 // because the code that uses this function has no way to cope with 518 // such aliases. 519 if (PSV->isAliased(MFI)) 520 return true; 521 } 522 // Does this pointer refer to a distinct and identifiable object? 523 if (!isIdentifiedObject(V)) 524 return true; 525 526 return false; 527} 528 529/// This returns true if the two MIs need a chain edge betwee them. 530/// If these are not even memory operations, we still may need 531/// chain deps between them. The question really is - could 532/// these two MIs be reordered during scheduling from memory dependency 533/// point of view. 534static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, 535 MachineInstr *MIa, 536 MachineInstr *MIb) { 537 // Cover a trivial case - no edge is need to itself. 538 if (MIa == MIb) 539 return false; 540 541 if (isUnsafeMemoryObject(MIa, MFI) || isUnsafeMemoryObject(MIb, MFI)) 542 return true; 543 544 // If we are dealing with two "normal" loads, we do not need an edge 545 // between them - they could be reordered. 546 if (!MIa->mayStore() && !MIb->mayStore()) 547 return false; 548 549 // To this point analysis is generic. From here on we do need AA. 550 if (!AA) 551 return true; 552 553 MachineMemOperand *MMOa = *MIa->memoperands_begin(); 554 MachineMemOperand *MMOb = *MIb->memoperands_begin(); 555 556 // FIXME: Need to handle multiple memory operands to support all targets. 557 if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand()) 558 llvm_unreachable("Multiple memory operands."); 559 560 // The following interface to AA is fashioned after DAGCombiner::isAlias 561 // and operates with MachineMemOperand offset with some important 562 // assumptions: 563 // - LLVM fundamentally assumes flat address spaces. 564 // - MachineOperand offset can *only* result from legalization and 565 // cannot affect queries other than the trivial case of overlap 566 // checking. 567 // - These offsets never wrap and never step outside 568 // of allocated objects. 569 // - There should never be any negative offsets here. 570 // 571 // FIXME: Modify API to hide this math from "user" 572 // FIXME: Even before we go to AA we can reason locally about some 573 // memory objects. It can save compile time, and possibly catch some 574 // corner cases not currently covered. 575 576 assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset"); 577 assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset"); 578 579 int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset()); 580 int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset; 581 int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset; 582 583 AliasAnalysis::AliasResult AAResult = AA->alias( 584 AliasAnalysis::Location(MMOa->getValue(), Overlapa, 585 MMOa->getTBAAInfo()), 586 AliasAnalysis::Location(MMOb->getValue(), Overlapb, 587 MMOb->getTBAAInfo())); 588 589 return (AAResult != AliasAnalysis::NoAlias); 590} 591 592/// This recursive function iterates over chain deps of SUb looking for 593/// "latest" node that needs a chain edge to SUa. 594static unsigned 595iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, 596 SUnit *SUa, SUnit *SUb, SUnit *ExitSU, unsigned *Depth, 597 SmallPtrSet<const SUnit*, 16> &Visited) { 598 if (!SUa || !SUb || SUb == ExitSU) 599 return *Depth; 600 601 // Remember visited nodes. 602 if (!Visited.insert(SUb)) 603 return *Depth; 604 // If there is _some_ dependency already in place, do not 605 // descend any further. 606 // TODO: Need to make sure that if that dependency got eliminated or ignored 607 // for any reason in the future, we would not violate DAG topology. 608 // Currently it does not happen, but makes an implicit assumption about 609 // future implementation. 610 // 611 // Independently, if we encounter node that is some sort of global 612 // object (like a call) we already have full set of dependencies to it 613 // and we can stop descending. 614 if (SUa->isSucc(SUb) || 615 isGlobalMemoryObject(AA, SUb->getInstr())) 616 return *Depth; 617 618 // If we do need an edge, or we have exceeded depth budget, 619 // add that edge to the predecessors chain of SUb, 620 // and stop descending. 621 if (*Depth > 200 || 622 MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) { 623 SUb->addPred(SDep(SUa, SDep::Order, /*Latency=*/0, /*Reg=*/0, 624 /*isNormalMemory=*/true)); 625 return *Depth; 626 } 627 // Track current depth. 628 (*Depth)++; 629 // Iterate over chain dependencies only. 630 for (SUnit::const_succ_iterator I = SUb->Succs.begin(), E = SUb->Succs.end(); 631 I != E; ++I) 632 if (I->isCtrl()) 633 iterateChainSucc (AA, MFI, SUa, I->getSUnit(), ExitSU, Depth, Visited); 634 return *Depth; 635} 636 637/// This function assumes that "downward" from SU there exist 638/// tail/leaf of already constructed DAG. It iterates downward and 639/// checks whether SU can be aliasing any node dominated 640/// by it. 641static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, 642 SUnit *SU, SUnit *ExitSU, std::set<SUnit *> &CheckList) { 643 if (!SU) 644 return; 645 646 SmallPtrSet<const SUnit*, 16> Visited; 647 unsigned Depth = 0; 648 649 for (std::set<SUnit *>::iterator I = CheckList.begin(), IE = CheckList.end(); 650 I != IE; ++I) { 651 if (SU == *I) 652 continue; 653 if (MIsNeedChainEdge(AA, MFI, SU->getInstr(), (*I)->getInstr())) 654 (*I)->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 655 /*isNormalMemory=*/true)); 656 // Now go through all the chain successors and iterate from them. 657 // Keep track of visited nodes. 658 for (SUnit::const_succ_iterator J = (*I)->Succs.begin(), 659 JE = (*I)->Succs.end(); J != JE; ++J) 660 if (J->isCtrl()) 661 iterateChainSucc (AA, MFI, SU, J->getSUnit(), 662 ExitSU, &Depth, Visited); 663 } 664} 665 666/// Check whether two objects need a chain edge, if so, add it 667/// otherwise remember the rejected SU. 668static inline 669void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, 670 SUnit *SUa, SUnit *SUb, 671 std::set<SUnit *> &RejectList, 672 unsigned TrueMemOrderLatency = 0, 673 bool isNormalMemory = false) { 674 // If this is a false dependency, 675 // do not add the edge, but rememeber the rejected node. 676 if (!EnableAASchedMI || 677 MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) 678 SUb->addPred(SDep(SUa, SDep::Order, TrueMemOrderLatency, /*Reg=*/0, 679 isNormalMemory)); 680 else { 681 // Duplicate entries should be ignored. 682 RejectList.insert(SUb); 683 DEBUG(dbgs() << "\tReject chain dep between SU(" 684 << SUa->NodeNum << ") and SU(" 685 << SUb->NodeNum << ")\n"); 686 } 687} 688 689/// Create an SUnit for each real instruction, numbered in top-down toplological 690/// order. The instruction order A < B, implies that no edge exists from B to A. 691/// 692/// Map each real instruction to its SUnit. 693/// 694/// After initSUnits, the SUnits vector cannot be resized and the scheduler may 695/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs 696/// instead of pointers. 697/// 698/// MachineScheduler relies on initSUnits numbering the nodes by their order in 699/// the original instruction list. 700void ScheduleDAGInstrs::initSUnits() { 701 // We'll be allocating one SUnit for each real instruction in the region, 702 // which is contained within a basic block. 703 SUnits.reserve(BB->size()); 704 705 for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) { 706 MachineInstr *MI = I; 707 if (MI->isDebugValue()) 708 continue; 709 710 SUnit *SU = newSUnit(MI); 711 MISUnitMap[MI] = SU; 712 713 SU->isCall = MI->isCall(); 714 SU->isCommutable = MI->isCommutable(); 715 716 // Assign the Latency field of SU using target-provided information. 717 if (UnitLatencies) 718 SU->Latency = 1; 719 else 720 computeLatency(SU); 721 } 722} 723 724/// If RegPressure is non null, compute register pressure as a side effect. The 725/// DAG builder is an efficient place to do it because it already visits 726/// operands. 727void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 728 RegPressureTracker *RPTracker) { 729 // Create an SUnit for each real instruction. 730 initSUnits(); 731 732 // We build scheduling units by walking a block's instruction list from bottom 733 // to top. 734 735 // Remember where a generic side-effecting instruction is as we procede. 736 SUnit *BarrierChain = 0, *AliasChain = 0; 737 738 // Memory references to specific known memory locations are tracked 739 // so that they can be given more precise dependencies. We track 740 // separately the known memory locations that may alias and those 741 // that are known not to alias 742 std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; 743 std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 744 std::set<SUnit*> RejectMemNodes; 745 746 // Remove any stale debug info; sometimes BuildSchedGraph is called again 747 // without emitting the info from the previous call. 748 DbgValues.clear(); 749 FirstDbgValue = NULL; 750 751 assert(Defs.empty() && Uses.empty() && 752 "Only BuildGraph should update Defs/Uses"); 753 Defs.setRegLimit(TRI->getNumRegs()); 754 Uses.setRegLimit(TRI->getNumRegs()); 755 756 assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs"); 757 // FIXME: Allow SparseSet to reserve space for the creation of virtual 758 // registers during scheduling. Don't artificially inflate the Universe 759 // because we want to assert that vregs are not created during DAG building. 760 VRegDefs.setUniverse(MRI.getNumVirtRegs()); 761 762 // Model data dependencies between instructions being scheduled and the 763 // ExitSU. 764 addSchedBarrierDeps(); 765 766 // Walk the list of instructions, from bottom moving up. 767 MachineInstr *PrevMI = NULL; 768 for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; 769 MII != MIE; --MII) { 770 MachineInstr *MI = prior(MII); 771 if (MI && PrevMI) { 772 DbgValues.push_back(std::make_pair(PrevMI, MI)); 773 PrevMI = NULL; 774 } 775 776 if (MI->isDebugValue()) { 777 PrevMI = MI; 778 continue; 779 } 780 if (RPTracker) { 781 RPTracker->recede(); 782 assert(RPTracker->getPos() == prior(MII) && "RPTracker can't find MI"); 783 } 784 785 assert((!MI->isTerminator() || CanHandleTerminators) && !MI->isLabel() && 786 "Cannot schedule terminators or labels!"); 787 788 SUnit *SU = MISUnitMap[MI]; 789 assert(SU && "No SUnit mapped to this MI"); 790 791 // Add register-based dependencies (data, anti, and output). 792 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 793 const MachineOperand &MO = MI->getOperand(j); 794 if (!MO.isReg()) continue; 795 unsigned Reg = MO.getReg(); 796 if (Reg == 0) continue; 797 798 if (TRI->isPhysicalRegister(Reg)) 799 addPhysRegDeps(SU, j); 800 else { 801 assert(!IsPostRA && "Virtual register encountered!"); 802 if (MO.isDef()) 803 addVRegDefDeps(SU, j); 804 else if (MO.readsReg()) // ignore undef operands 805 addVRegUseDeps(SU, j); 806 } 807 } 808 809 // Add chain dependencies. 810 // Chain dependencies used to enforce memory order should have 811 // latency of 0 (except for true dependency of Store followed by 812 // aliased Load... we estimate that with a single cycle of latency 813 // assuming the hardware will bypass) 814 // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 815 // after stack slots are lowered to actual addresses. 816 // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 817 // produce more precise dependence information. 818#define STORE_LOAD_LATENCY 1 819 unsigned TrueMemOrderLatency = 0; 820 if (isGlobalMemoryObject(AA, MI)) { 821 // Be conservative with these and add dependencies on all memory 822 // references, even those that are known to not alias. 823 for (std::map<const Value *, SUnit *>::iterator I = 824 NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 825 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 826 } 827 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 828 NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 829 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 830 I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 831 } 832 // Add SU to the barrier chain. 833 if (BarrierChain) 834 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 835 BarrierChain = SU; 836 // This is a barrier event that acts as a pivotal node in the DAG, 837 // so it is safe to clear list of exposed nodes. 838 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes); 839 RejectMemNodes.clear(); 840 NonAliasMemDefs.clear(); 841 NonAliasMemUses.clear(); 842 843 // fall-through 844 new_alias_chain: 845 // Chain all possibly aliasing memory references though SU. 846 if (AliasChain) 847 addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); 848 AliasChain = SU; 849 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 850 addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, 851 TrueMemOrderLatency); 852 for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), 853 E = AliasMemDefs.end(); I != E; ++I) 854 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); 855 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 856 AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 857 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 858 addChainDependency(AA, MFI, SU, I->second[i], RejectMemNodes, 859 TrueMemOrderLatency); 860 } 861 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes); 862 PendingLoads.clear(); 863 AliasMemDefs.clear(); 864 AliasMemUses.clear(); 865 } else if (MI->mayStore()) { 866 bool MayAlias = true; 867 TrueMemOrderLatency = STORE_LOAD_LATENCY; 868 if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 869 // A store to a specific PseudoSourceValue. Add precise dependencies. 870 // Record the def in MemDefs, first adding a dep if there is 871 // an existing def. 872 std::map<const Value *, SUnit *>::iterator I = 873 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 874 std::map<const Value *, SUnit *>::iterator IE = 875 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 876 if (I != IE) { 877 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 878 0, true); 879 I->second = SU; 880 } else { 881 if (MayAlias) 882 AliasMemDefs[V] = SU; 883 else 884 NonAliasMemDefs[V] = SU; 885 } 886 // Handle the uses in MemUses, if there are any. 887 std::map<const Value *, std::vector<SUnit *> >::iterator J = 888 ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 889 std::map<const Value *, std::vector<SUnit *> >::iterator JE = 890 ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 891 if (J != JE) { 892 for (unsigned i = 0, e = J->second.size(); i != e; ++i) 893 addChainDependency(AA, MFI, SU, J->second[i], RejectMemNodes, 894 TrueMemOrderLatency, true); 895 J->second.clear(); 896 } 897 if (MayAlias) { 898 // Add dependencies from all the PendingLoads, i.e. loads 899 // with no underlying object. 900 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 901 addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes, 902 TrueMemOrderLatency); 903 // Add dependence on alias chain, if needed. 904 if (AliasChain) 905 addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); 906 // But we also should check dependent instructions for the 907 // SU in question. 908 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes); 909 } 910 // Add dependence on barrier chain, if needed. 911 // There is no point to check aliasing on barrier event. Even if 912 // SU and barrier _could_ be reordered, they should not. In addition, 913 // we have lost all RejectMemNodes below barrier. 914 if (BarrierChain) 915 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 916 } else { 917 // Treat all other stores conservatively. 918 goto new_alias_chain; 919 } 920 921 if (!ExitSU.isPred(SU)) 922 // Push store's up a bit to avoid them getting in between cmp 923 // and branches. 924 ExitSU.addPred(SDep(SU, SDep::Order, 0, 925 /*Reg=*/0, /*isNormalMemory=*/false, 926 /*isMustAlias=*/false, 927 /*isArtificial=*/true)); 928 } else if (MI->mayLoad()) { 929 bool MayAlias = true; 930 TrueMemOrderLatency = 0; 931 if (MI->isInvariantLoad(AA)) { 932 // Invariant load, no chain dependencies needed! 933 } else { 934 if (const Value *V = 935 getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 936 // A load from a specific PseudoSourceValue. Add precise dependencies. 937 std::map<const Value *, SUnit *>::iterator I = 938 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 939 std::map<const Value *, SUnit *>::iterator IE = 940 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 941 if (I != IE) 942 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 0, true); 943 if (MayAlias) 944 AliasMemUses[V].push_back(SU); 945 else 946 NonAliasMemUses[V].push_back(SU); 947 } else { 948 // A load with no underlying object. Depend on all 949 // potentially aliasing stores. 950 for (std::map<const Value *, SUnit *>::iterator I = 951 AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 952 addChainDependency(AA, MFI, SU, I->second, RejectMemNodes); 953 954 PendingLoads.push_back(SU); 955 MayAlias = true; 956 } 957 if (MayAlias) 958 adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes); 959 // Add dependencies on alias and barrier chains, if needed. 960 if (MayAlias && AliasChain) 961 addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes); 962 if (BarrierChain) 963 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 964 } 965 } 966 } 967 if (PrevMI) 968 FirstDbgValue = PrevMI; 969 970 Defs.clear(); 971 Uses.clear(); 972 VRegDefs.clear(); 973 PendingLoads.clear(); 974} 975 976void ScheduleDAGInstrs::computeLatency(SUnit *SU) { 977 // Compute the latency for the node. We only provide a default for missing 978 // itineraries. Empty itineraries still have latency properties. 979 if (!InstrItins) { 980 SU->Latency = 1; 981 982 // Simplistic target-independent heuristic: assume that loads take 983 // extra time. 984 if (SU->getInstr()->mayLoad()) 985 SU->Latency += 2; 986 } else { 987 SU->Latency = TII->getInstrLatency(InstrItins, SU->getInstr()); 988 } 989} 990 991unsigned ScheduleDAGInstrs::computeOperandLatency(SUnit *Def, SUnit *Use, 992 const SDep& dep, 993 bool FindMin) const { 994 // For a data dependency with a known register... 995 if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0)) 996 return 1; 997 998 return TII->computeOperandLatency(InstrItins, TRI, Def->getInstr(), 999 Use->getInstr(), dep.getReg(), FindMin); 1000} 1001 1002void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 1003 SU->getInstr()->dump(); 1004} 1005 1006std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 1007 std::string s; 1008 raw_string_ostream oss(s); 1009 if (SU == &EntrySU) 1010 oss << "<entry>"; 1011 else if (SU == &ExitSU) 1012 oss << "<exit>"; 1013 else 1014 SU->getInstr()->print(oss); 1015 return oss.str(); 1016} 1017 1018/// Return the basic block label. It is not necessarilly unique because a block 1019/// contains multiple scheduling regions. But it is fine for visualization. 1020std::string ScheduleDAGInstrs::getDAGName() const { 1021 return "dag." + BB->getFullName(); 1022} 1023