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