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