ScheduleDAGInstrs.cpp revision 198396
1193323Sed//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This implements the ScheduleDAGInstrs class, which implements re-scheduling 11193323Sed// of MachineInstrs. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#define DEBUG_TYPE "sched-instrs" 16193323Sed#include "ScheduleDAGInstrs.h" 17198090Srdivacky#include "llvm/Operator.h" 18193323Sed#include "llvm/Analysis/AliasAnalysis.h" 19193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 20198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 21193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 22193323Sed#include "llvm/CodeGen/PseudoSourceValue.h" 23193323Sed#include "llvm/Target/TargetMachine.h" 24193323Sed#include "llvm/Target/TargetInstrInfo.h" 25193323Sed#include "llvm/Target/TargetRegisterInfo.h" 26193323Sed#include "llvm/Target/TargetSubtarget.h" 27193323Sed#include "llvm/Support/Debug.h" 28193323Sed#include "llvm/Support/raw_ostream.h" 29193323Sed#include "llvm/ADT/SmallSet.h" 30193323Sedusing namespace llvm; 31193323Sed 32193323SedScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 33193323Sed const MachineLoopInfo &mli, 34193323Sed const MachineDominatorTree &mdt) 35198396Srdivacky : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) { 36198396Srdivacky MFI = mf.getFrameInfo(); 37198396Srdivacky} 38193323Sed 39193323Sed/// Run - perform scheduling. 40193323Sed/// 41193323Sedvoid ScheduleDAGInstrs::Run(MachineBasicBlock *bb, 42193323Sed MachineBasicBlock::iterator begin, 43193323Sed MachineBasicBlock::iterator end, 44193323Sed unsigned endcount) { 45193323Sed BB = bb; 46193323Sed Begin = begin; 47193323Sed InsertPosIndex = endcount; 48193323Sed 49193323Sed ScheduleDAG::Run(bb, end); 50193323Sed} 51193323Sed 52193323Sed/// getUnderlyingObjectFromInt - This is the function that does the work of 53193323Sed/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 54193323Sedstatic const Value *getUnderlyingObjectFromInt(const Value *V) { 55193323Sed do { 56198090Srdivacky if (const Operator *U = dyn_cast<Operator>(V)) { 57193323Sed // If we find a ptrtoint, we can transfer control back to the 58193323Sed // regular getUnderlyingObjectFromInt. 59198090Srdivacky if (U->getOpcode() == Instruction::PtrToInt) 60193323Sed return U->getOperand(0); 61193323Sed // If we find an add of a constant or a multiplied value, it's 62193323Sed // likely that the other operand will lead us to the base 63193323Sed // object. We don't have to worry about the case where the 64198090Srdivacky // object address is somehow being computed by the multiply, 65193323Sed // because our callers only care when the result is an 66193323Sed // identifibale object. 67198090Srdivacky if (U->getOpcode() != Instruction::Add || 68193323Sed (!isa<ConstantInt>(U->getOperand(1)) && 69198090Srdivacky Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) 70193323Sed return V; 71193323Sed V = U->getOperand(0); 72193323Sed } else { 73193323Sed return V; 74193323Sed } 75193323Sed assert(isa<IntegerType>(V->getType()) && "Unexpected operand type!"); 76193323Sed } while (1); 77193323Sed} 78193323Sed 79193323Sed/// getUnderlyingObject - This is a wrapper around Value::getUnderlyingObject 80193323Sed/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 81193323Sedstatic const Value *getUnderlyingObject(const Value *V) { 82193323Sed // First just call Value::getUnderlyingObject to let it do what it does. 83193323Sed do { 84193323Sed V = V->getUnderlyingObject(); 85193323Sed // If it found an inttoptr, use special code to continue climing. 86198090Srdivacky if (Operator::getOpcode(V) != Instruction::IntToPtr) 87193323Sed break; 88193323Sed const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 89193323Sed // If that succeeded in finding a pointer, continue the search. 90193323Sed if (!isa<PointerType>(O->getType())) 91193323Sed break; 92193323Sed V = O; 93193323Sed } while (1); 94193323Sed return V; 95193323Sed} 96193323Sed 97193323Sed/// getUnderlyingObjectForInstr - If this machine instr has memory reference 98193323Sed/// information and it can be tracked to a normal reference to a known 99193323Sed/// object, return the Value for that object. Otherwise return null. 100198396Srdivackystatic const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, 101198396Srdivacky const MachineFrameInfo *MFI) { 102193323Sed if (!MI->hasOneMemOperand() || 103198090Srdivacky !(*MI->memoperands_begin())->getValue() || 104198090Srdivacky (*MI->memoperands_begin())->isVolatile()) 105193323Sed return 0; 106193323Sed 107198090Srdivacky const Value *V = (*MI->memoperands_begin())->getValue(); 108193323Sed if (!V) 109193323Sed return 0; 110193323Sed 111193323Sed V = getUnderlyingObject(V); 112198396Srdivacky if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 113198396Srdivacky // For now, ignore PseudoSourceValues which may alias LLVM IR values 114198396Srdivacky // because the code that uses this function has no way to cope with 115198396Srdivacky // such aliases. 116198396Srdivacky if (PSV->isAliased(MFI)) 117198396Srdivacky return 0; 118198396Srdivacky return V; 119198396Srdivacky } 120193323Sed 121198396Srdivacky if (isIdentifiedObject(V)) 122198396Srdivacky return V; 123198396Srdivacky 124198396Srdivacky return 0; 125193323Sed} 126193323Sed 127193323Sedvoid ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { 128193323Sed if (MachineLoop *ML = MLI.getLoopFor(BB)) 129193323Sed if (BB == ML->getLoopLatch()) { 130193323Sed MachineBasicBlock *Header = ML->getHeader(); 131193323Sed for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), 132193323Sed E = Header->livein_end(); I != E; ++I) 133193323Sed LoopLiveInRegs.insert(*I); 134193323Sed LoopRegs.VisitLoop(ML); 135193323Sed } 136193323Sed} 137193323Sed 138198090Srdivackyvoid ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { 139193323Sed // We'll be allocating one SUnit for each instruction, plus one for 140193323Sed // the region exit node. 141193323Sed SUnits.reserve(BB->size()); 142193323Sed 143193323Sed // We build scheduling units by walking a block's instruction list from bottom 144193323Sed // to top. 145193323Sed 146193323Sed // Remember where a generic side-effecting instruction is as we procede. If 147193323Sed // ChainMMO is null, this is assumed to have arbitrary side-effects. If 148193323Sed // ChainMMO is non-null, then Chain makes only a single memory reference. 149193323Sed SUnit *Chain = 0; 150193323Sed MachineMemOperand *ChainMMO = 0; 151193323Sed 152193323Sed // Memory references to specific known memory locations are tracked so that 153193323Sed // they can be given more precise dependencies. 154193323Sed std::map<const Value *, SUnit *> MemDefs; 155193323Sed std::map<const Value *, std::vector<SUnit *> > MemUses; 156193323Sed 157193323Sed // Check to see if the scheduler cares about latencies. 158193323Sed bool UnitLatencies = ForceUnitLatencies(); 159193323Sed 160193323Sed // Ask the target if address-backscheduling is desirable, and if so how much. 161198090Srdivacky const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 162198090Srdivacky unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 163193323Sed 164193323Sed // Walk the list of instructions, from bottom moving up. 165193323Sed for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; 166193323Sed MII != MIE; --MII) { 167193323Sed MachineInstr *MI = prior(MII); 168193323Sed const TargetInstrDesc &TID = MI->getDesc(); 169193323Sed assert(!TID.isTerminator() && !MI->isLabel() && 170193323Sed "Cannot schedule terminators or labels!"); 171193323Sed // Create the SUnit for this MI. 172193323Sed SUnit *SU = NewSUnit(MI); 173193323Sed 174193323Sed // Assign the Latency field of SU using target-provided information. 175193323Sed if (UnitLatencies) 176193323Sed SU->Latency = 1; 177193323Sed else 178193323Sed ComputeLatency(SU); 179193323Sed 180193323Sed // Add register-based dependencies (data, anti, and output). 181193323Sed for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 182193323Sed const MachineOperand &MO = MI->getOperand(j); 183193323Sed if (!MO.isReg()) continue; 184193323Sed unsigned Reg = MO.getReg(); 185193323Sed if (Reg == 0) continue; 186193323Sed 187193323Sed assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); 188193323Sed std::vector<SUnit *> &UseList = Uses[Reg]; 189193323Sed std::vector<SUnit *> &DefList = Defs[Reg]; 190198090Srdivacky // Optionally add output and anti dependencies. For anti 191198090Srdivacky // dependencies we use a latency of 0 because for a multi-issue 192198090Srdivacky // target we want to allow the defining instruction to issue 193198090Srdivacky // in the same cycle as the using instruction. 194198090Srdivacky // TODO: Using a latency of 1 here for output dependencies assumes 195198090Srdivacky // there's no cost for reusing registers. 196193323Sed SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 197198090Srdivacky unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1; 198193323Sed for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 199193323Sed SUnit *DefSU = DefList[i]; 200193323Sed if (DefSU != SU && 201193323Sed (Kind != SDep::Output || !MO.isDead() || 202193323Sed !DefSU->getInstr()->registerDefIsDead(Reg))) 203198090Srdivacky DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg)); 204193323Sed } 205193323Sed for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 206193323Sed std::vector<SUnit *> &DefList = Defs[*Alias]; 207193323Sed for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 208193323Sed SUnit *DefSU = DefList[i]; 209193323Sed if (DefSU != SU && 210193323Sed (Kind != SDep::Output || !MO.isDead() || 211193323Sed !DefSU->getInstr()->registerDefIsDead(Reg))) 212198090Srdivacky DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias)); 213193323Sed } 214193323Sed } 215193323Sed 216193323Sed if (MO.isDef()) { 217193323Sed // Add any data dependencies. 218193323Sed unsigned DataLatency = SU->Latency; 219193323Sed for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 220193323Sed SUnit *UseSU = UseList[i]; 221193323Sed if (UseSU != SU) { 222193323Sed unsigned LDataLatency = DataLatency; 223193323Sed // Optionally add in a special extra latency for nodes that 224193323Sed // feed addresses. 225193323Sed // TODO: Do this for register aliases too. 226198090Srdivacky // TODO: Perhaps we should get rid of 227198090Srdivacky // SpecialAddressLatency and just move this into 228198090Srdivacky // adjustSchedDependency for the targets that care about 229198090Srdivacky // it. 230193323Sed if (SpecialAddressLatency != 0 && !UnitLatencies) { 231193323Sed MachineInstr *UseMI = UseSU->getInstr(); 232193323Sed const TargetInstrDesc &UseTID = UseMI->getDesc(); 233193323Sed int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg); 234193323Sed assert(RegUseIndex >= 0 && "UseMI doesn's use register!"); 235193323Sed if ((UseTID.mayLoad() || UseTID.mayStore()) && 236193323Sed (unsigned)RegUseIndex < UseTID.getNumOperands() && 237193323Sed UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 238193323Sed LDataLatency += SpecialAddressLatency; 239193323Sed } 240198090Srdivacky // Adjust the dependence latency using operand def/use 241198090Srdivacky // information (if any), and then allow the target to 242198090Srdivacky // perform its own adjustments. 243198090Srdivacky const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg); 244198090Srdivacky if (!UnitLatencies) { 245198090Srdivacky ComputeOperandLatency(SU, UseSU, (SDep &)dep); 246198090Srdivacky ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 247198090Srdivacky } 248198090Srdivacky UseSU->addPred(dep); 249193323Sed } 250193323Sed } 251193323Sed for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 252193323Sed std::vector<SUnit *> &UseList = Uses[*Alias]; 253193323Sed for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 254193323Sed SUnit *UseSU = UseList[i]; 255198090Srdivacky if (UseSU != SU) { 256198090Srdivacky const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias); 257198090Srdivacky if (!UnitLatencies) { 258198090Srdivacky ComputeOperandLatency(SU, UseSU, (SDep &)dep); 259198090Srdivacky ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 260198090Srdivacky } 261198090Srdivacky UseSU->addPred(dep); 262198090Srdivacky } 263193323Sed } 264193323Sed } 265193323Sed 266193323Sed // If a def is going to wrap back around to the top of the loop, 267193323Sed // backschedule it. 268193323Sed if (!UnitLatencies && DefList.empty()) { 269193323Sed LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg); 270193323Sed if (I != LoopRegs.Deps.end()) { 271193323Sed const MachineOperand *UseMO = I->second.first; 272193323Sed unsigned Count = I->second.second; 273193323Sed const MachineInstr *UseMI = UseMO->getParent(); 274193323Sed unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 275193323Sed const TargetInstrDesc &UseTID = UseMI->getDesc(); 276193323Sed // TODO: If we knew the total depth of the region here, we could 277193323Sed // handle the case where the whole loop is inside the region but 278193323Sed // is large enough that the isScheduleHigh trick isn't needed. 279193323Sed if (UseMOIdx < UseTID.getNumOperands()) { 280193323Sed // Currently, we only support scheduling regions consisting of 281193323Sed // single basic blocks. Check to see if the instruction is in 282193323Sed // the same region by checking to see if it has the same parent. 283193323Sed if (UseMI->getParent() != MI->getParent()) { 284193323Sed unsigned Latency = SU->Latency; 285193323Sed if (UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 286193323Sed Latency += SpecialAddressLatency; 287193323Sed // This is a wild guess as to the portion of the latency which 288193323Sed // will be overlapped by work done outside the current 289193323Sed // scheduling region. 290193323Sed Latency -= std::min(Latency, Count); 291193323Sed // Add the artifical edge. 292193323Sed ExitSU.addPred(SDep(SU, SDep::Order, Latency, 293193323Sed /*Reg=*/0, /*isNormalMemory=*/false, 294193323Sed /*isMustAlias=*/false, 295193323Sed /*isArtificial=*/true)); 296193323Sed } else if (SpecialAddressLatency > 0 && 297193323Sed UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 298193323Sed // The entire loop body is within the current scheduling region 299193323Sed // and the latency of this operation is assumed to be greater 300193323Sed // than the latency of the loop. 301193323Sed // TODO: Recursively mark data-edge predecessors as 302193323Sed // isScheduleHigh too. 303193323Sed SU->isScheduleHigh = true; 304193323Sed } 305193323Sed } 306193323Sed LoopRegs.Deps.erase(I); 307193323Sed } 308193323Sed } 309193323Sed 310193323Sed UseList.clear(); 311193323Sed if (!MO.isDead()) 312193323Sed DefList.clear(); 313193323Sed DefList.push_back(SU); 314193323Sed } else { 315193323Sed UseList.push_back(SU); 316193323Sed } 317193323Sed } 318193323Sed 319193323Sed // Add chain dependencies. 320193323Sed // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 321193323Sed // after stack slots are lowered to actual addresses. 322193323Sed // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 323193323Sed // produce more precise dependence information. 324193323Sed if (TID.isCall() || TID.hasUnmodeledSideEffects()) { 325193323Sed new_chain: 326193323Sed // This is the conservative case. Add dependencies on all memory 327193323Sed // references. 328193323Sed if (Chain) 329193323Sed Chain->addPred(SDep(SU, SDep::Order, SU->Latency)); 330193323Sed Chain = SU; 331193323Sed for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 332193323Sed PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency)); 333193323Sed PendingLoads.clear(); 334193323Sed for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(), 335193323Sed E = MemDefs.end(); I != E; ++I) { 336193323Sed I->second->addPred(SDep(SU, SDep::Order, SU->Latency)); 337193323Sed I->second = SU; 338193323Sed } 339193323Sed for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 340193323Sed MemUses.begin(), E = MemUses.end(); I != E; ++I) { 341193323Sed for (unsigned i = 0, e = I->second.size(); i != e; ++i) 342193323Sed I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency)); 343193323Sed I->second.clear(); 344193323Sed } 345193323Sed // See if it is known to just have a single memory reference. 346193323Sed MachineInstr *ChainMI = Chain->getInstr(); 347193323Sed const TargetInstrDesc &ChainTID = ChainMI->getDesc(); 348193323Sed if (!ChainTID.isCall() && 349193323Sed !ChainTID.hasUnmodeledSideEffects() && 350193323Sed ChainMI->hasOneMemOperand() && 351198090Srdivacky !(*ChainMI->memoperands_begin())->isVolatile() && 352198090Srdivacky (*ChainMI->memoperands_begin())->getValue()) 353193323Sed // We know that the Chain accesses one specific memory location. 354198090Srdivacky ChainMMO = *ChainMI->memoperands_begin(); 355193323Sed else 356193323Sed // Unknown memory accesses. Assume the worst. 357193323Sed ChainMMO = 0; 358193323Sed } else if (TID.mayStore()) { 359198396Srdivacky if (const Value *V = getUnderlyingObjectForInstr(MI, MFI)) { 360193323Sed // A store to a specific PseudoSourceValue. Add precise dependencies. 361193323Sed // Handle the def in MemDefs, if there is one. 362193323Sed std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V); 363193323Sed if (I != MemDefs.end()) { 364193323Sed I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0, 365193323Sed /*isNormalMemory=*/true)); 366193323Sed I->second = SU; 367193323Sed } else { 368193323Sed MemDefs[V] = SU; 369193323Sed } 370193323Sed // Handle the uses in MemUses, if there are any. 371193323Sed std::map<const Value *, std::vector<SUnit *> >::iterator J = 372193323Sed MemUses.find(V); 373193323Sed if (J != MemUses.end()) { 374193323Sed for (unsigned i = 0, e = J->second.size(); i != e; ++i) 375193323Sed J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0, 376193323Sed /*isNormalMemory=*/true)); 377193323Sed J->second.clear(); 378193323Sed } 379193323Sed // Add dependencies from all the PendingLoads, since without 380193323Sed // memoperands we must assume they alias anything. 381193323Sed for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 382193323Sed PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency)); 383193323Sed // Add a general dependence too, if needed. 384193323Sed if (Chain) 385193323Sed Chain->addPred(SDep(SU, SDep::Order, SU->Latency)); 386193323Sed } else 387193323Sed // Treat all other stores conservatively. 388193323Sed goto new_chain; 389193323Sed } else if (TID.mayLoad()) { 390198090Srdivacky if (MI->isInvariantLoad(AA)) { 391193323Sed // Invariant load, no chain dependencies needed! 392198396Srdivacky } else if (const Value *V = getUnderlyingObjectForInstr(MI, MFI)) { 393193323Sed // A load from a specific PseudoSourceValue. Add precise dependencies. 394193323Sed std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V); 395193323Sed if (I != MemDefs.end()) 396193323Sed I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0, 397193323Sed /*isNormalMemory=*/true)); 398193323Sed MemUses[V].push_back(SU); 399193323Sed 400193323Sed // Add a general dependence too, if needed. 401193323Sed if (Chain && (!ChainMMO || 402193323Sed (ChainMMO->isStore() || ChainMMO->isVolatile()))) 403193323Sed Chain->addPred(SDep(SU, SDep::Order, SU->Latency)); 404193323Sed } else if (MI->hasVolatileMemoryRef()) { 405193323Sed // Treat volatile loads conservatively. Note that this includes 406193323Sed // cases where memoperand information is unavailable. 407193323Sed goto new_chain; 408193323Sed } else { 409193323Sed // A normal load. Depend on the general chain, as well as on 410193323Sed // all stores. In the absense of MachineMemOperand information, 411193323Sed // we can't even assume that the load doesn't alias well-behaved 412193323Sed // memory locations. 413193323Sed if (Chain) 414193323Sed Chain->addPred(SDep(SU, SDep::Order, SU->Latency)); 415193323Sed for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(), 416193323Sed E = MemDefs.end(); I != E; ++I) 417193323Sed I->second->addPred(SDep(SU, SDep::Order, SU->Latency)); 418193323Sed PendingLoads.push_back(SU); 419193323Sed } 420193323Sed } 421193323Sed } 422193323Sed 423193323Sed for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { 424193323Sed Defs[i].clear(); 425193323Sed Uses[i].clear(); 426193323Sed } 427193323Sed PendingLoads.clear(); 428193323Sed} 429193323Sed 430193323Sedvoid ScheduleDAGInstrs::FinishBlock() { 431193323Sed // Nothing to do. 432193323Sed} 433193323Sed 434193323Sedvoid ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { 435193323Sed const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 436193323Sed 437198090Srdivacky // Compute the latency for the node. 438193323Sed SU->Latency = 439198090Srdivacky InstrItins.getStageLatency(SU->getInstr()->getDesc().getSchedClass()); 440193323Sed 441193323Sed // Simplistic target-independent heuristic: assume that loads take 442193323Sed // extra time. 443193323Sed if (InstrItins.isEmpty()) 444193323Sed if (SU->getInstr()->getDesc().mayLoad()) 445193323Sed SU->Latency += 2; 446193323Sed} 447193323Sed 448198090Srdivackyvoid ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use, 449198090Srdivacky SDep& dep) const { 450198090Srdivacky const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 451198090Srdivacky if (InstrItins.isEmpty()) 452198090Srdivacky return; 453198090Srdivacky 454198090Srdivacky // For a data dependency with a known register... 455198090Srdivacky if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0)) 456198090Srdivacky return; 457198090Srdivacky 458198090Srdivacky const unsigned Reg = dep.getReg(); 459198090Srdivacky 460198090Srdivacky // ... find the definition of the register in the defining 461198090Srdivacky // instruction 462198090Srdivacky MachineInstr *DefMI = Def->getInstr(); 463198090Srdivacky int DefIdx = DefMI->findRegisterDefOperandIdx(Reg); 464198090Srdivacky if (DefIdx != -1) { 465198090Srdivacky int DefCycle = InstrItins.getOperandCycle(DefMI->getDesc().getSchedClass(), DefIdx); 466198090Srdivacky if (DefCycle >= 0) { 467198090Srdivacky MachineInstr *UseMI = Use->getInstr(); 468198090Srdivacky const unsigned UseClass = UseMI->getDesc().getSchedClass(); 469198090Srdivacky 470198090Srdivacky // For all uses of the register, calculate the maxmimum latency 471198090Srdivacky int Latency = -1; 472198090Srdivacky for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 473198090Srdivacky const MachineOperand &MO = UseMI->getOperand(i); 474198090Srdivacky if (!MO.isReg() || !MO.isUse()) 475198090Srdivacky continue; 476198090Srdivacky unsigned MOReg = MO.getReg(); 477198090Srdivacky if (MOReg != Reg) 478198090Srdivacky continue; 479198090Srdivacky 480198090Srdivacky int UseCycle = InstrItins.getOperandCycle(UseClass, i); 481198090Srdivacky if (UseCycle >= 0) 482198090Srdivacky Latency = std::max(Latency, DefCycle - UseCycle + 1); 483198090Srdivacky } 484198090Srdivacky 485198090Srdivacky // If we found a latency, then replace the existing dependence latency. 486198090Srdivacky if (Latency >= 0) 487198090Srdivacky dep.setLatency(Latency); 488198090Srdivacky } 489198090Srdivacky } 490198090Srdivacky} 491198090Srdivacky 492193323Sedvoid ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 493193323Sed SU->getInstr()->dump(); 494193323Sed} 495193323Sed 496193323Sedstd::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 497193323Sed std::string s; 498193323Sed raw_string_ostream oss(s); 499193323Sed if (SU == &EntrySU) 500193323Sed oss << "<entry>"; 501193323Sed else if (SU == &ExitSU) 502193323Sed oss << "<exit>"; 503193323Sed else 504193323Sed SU->getInstr()->print(oss); 505193323Sed return oss.str(); 506193323Sed} 507193323Sed 508193323Sed// EmitSchedule - Emit the machine code in scheduled order. 509198090SrdivackyMachineBasicBlock *ScheduleDAGInstrs:: 510198090SrdivackyEmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) { 511193323Sed // For MachineInstr-based scheduling, we're rescheduling the instructions in 512193323Sed // the block, so start by removing them from the block. 513193323Sed while (Begin != InsertPos) { 514193323Sed MachineBasicBlock::iterator I = Begin; 515193323Sed ++Begin; 516193323Sed BB->remove(I); 517193323Sed } 518193323Sed 519193323Sed // Then re-insert them according to the given schedule. 520193323Sed for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 521193323Sed SUnit *SU = Sequence[i]; 522193323Sed if (!SU) { 523193323Sed // Null SUnit* is a noop. 524193323Sed EmitNoop(); 525193323Sed continue; 526193323Sed } 527193323Sed 528193323Sed BB->insert(InsertPos, SU->getInstr()); 529193323Sed } 530193323Sed 531193323Sed // Update the Begin iterator, as the first instruction in the block 532193323Sed // may have been scheduled later. 533193323Sed if (!Sequence.empty()) 534193323Sed Begin = Sequence[0]->getInstr(); 535193323Sed 536193323Sed return BB; 537193323Sed} 538