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