ScheduleDAGInstrs.cpp revision 205218
192108Sphk//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// 292108Sphk// 392108Sphk// The LLVM Compiler Infrastructure 492108Sphk// 592108Sphk// This file is distributed under the University of Illinois Open Source 692108Sphk// License. See LICENSE.TXT for details. 792108Sphk// 892108Sphk//===----------------------------------------------------------------------===// 992108Sphk// 1092108Sphk// This implements the ScheduleDAGInstrs class, which implements re-scheduling 1192108Sphk// of MachineInstrs. 1292108Sphk// 1392108Sphk//===----------------------------------------------------------------------===// 1492108Sphk 1592108Sphk#define DEBUG_TYPE "sched-instrs" 1692108Sphk#include "ScheduleDAGInstrs.h" 1792108Sphk#include "llvm/Operator.h" 1892108Sphk#include "llvm/Analysis/AliasAnalysis.h" 1992108Sphk#include "llvm/CodeGen/MachineFunctionPass.h" 2092108Sphk#include "llvm/CodeGen/MachineMemOperand.h" 2192108Sphk#include "llvm/CodeGen/MachineRegisterInfo.h" 2292108Sphk#include "llvm/CodeGen/PseudoSourceValue.h" 2392108Sphk#include "llvm/Target/TargetMachine.h" 2492108Sphk#include "llvm/Target/TargetInstrInfo.h" 2592108Sphk#include "llvm/Target/TargetRegisterInfo.h" 2692108Sphk#include "llvm/Target/TargetSubtarget.h" 2792108Sphk#include "llvm/Support/Debug.h" 2892108Sphk#include "llvm/Support/raw_ostream.h" 2992108Sphk#include "llvm/ADT/SmallSet.h" 3092108Sphkusing namespace llvm; 3192108Sphk 3292108SphkScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 3392108Sphk const MachineLoopInfo &mli, 3492108Sphk const MachineDominatorTree &mdt) 3592108Sphk : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) { 3692108Sphk MFI = mf.getFrameInfo(); 3792108Sphk DbgValueVec.clear(); 3892108Sphk} 3992108Sphk 4092108Sphk/// Run - perform scheduling. 4192108Sphk/// 4292108Sphkvoid ScheduleDAGInstrs::Run(MachineBasicBlock *bb, 4392108Sphk MachineBasicBlock::iterator begin, 4492108Sphk MachineBasicBlock::iterator end, 4592108Sphk unsigned endcount) { 4692108Sphk BB = bb; 4792108Sphk Begin = begin; 4892108Sphk InsertPosIndex = endcount; 4992108Sphk 5092108Sphk ScheduleDAG::Run(bb, end); 5192108Sphk} 5292108Sphk 5392108Sphk/// getUnderlyingObjectFromInt - This is the function that does the work of 5492108Sphk/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 5592108Sphkstatic const Value *getUnderlyingObjectFromInt(const Value *V) { 5692108Sphk do { 5792108Sphk if (const Operator *U = dyn_cast<Operator>(V)) { 5892108Sphk // If we find a ptrtoint, we can transfer control back to the 5993248Sphk // regular getUnderlyingObjectFromInt. 6097075Sphk if (U->getOpcode() == Instruction::PtrToInt) 6192108Sphk return U->getOperand(0); 6292108Sphk // If we find an add of a constant or a multiplied value, it's 6393776Sphk // likely that the other operand will lead us to the base 6492108Sphk // object. We don't have to worry about the case where the 6592108Sphk // object address is somehow being computed by the multiply, 6692108Sphk // because our callers only care when the result is an 6792108Sphk // identifibale object. 6892108Sphk if (U->getOpcode() != Instruction::Add || 6992108Sphk (!isa<ConstantInt>(U->getOperand(1)) && 7092108Sphk Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) 7192108Sphk return V; 7292108Sphk V = U->getOperand(0); 7392108Sphk } else { 7492108Sphk return V; 7592108Sphk } 7692108Sphk assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 7792108Sphk } while (1); 7892108Sphk} 7992108Sphk 8092108Sphk/// getUnderlyingObject - This is a wrapper around Value::getUnderlyingObject 8192108Sphk/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 8292108Sphkstatic const Value *getUnderlyingObject(const Value *V) { 8392108Sphk // First just call Value::getUnderlyingObject to let it do what it does. 8492108Sphk do { 8592108Sphk V = V->getUnderlyingObject(); 8692108Sphk // If it found an inttoptr, use special code to continue climing. 8792108Sphk if (Operator::getOpcode(V) != Instruction::IntToPtr) 8892108Sphk break; 8992108Sphk const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 9092108Sphk // If that succeeded in finding a pointer, continue the search. 9192108Sphk if (!O->getType()->isPointerTy()) 9292108Sphk break; 9392108Sphk V = O; 9492108Sphk } while (1); 9592108Sphk return V; 9693778Sphk} 9793778Sphk 9892108Sphk/// getUnderlyingObjectForInstr - If this machine instr has memory reference 9992108Sphk/// information and it can be tracked to a normal reference to a known 10092108Sphk/// object, return the Value for that object. Otherwise return null. 10192108Sphkstatic const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, 10295038Sphk const MachineFrameInfo *MFI, 10395038Sphk bool &MayAlias) { 10495038Sphk MayAlias = true; 10595038Sphk if (!MI->hasOneMemOperand() || 10695038Sphk !(*MI->memoperands_begin())->getValue() || 10795038Sphk (*MI->memoperands_begin())->isVolatile()) 10895038Sphk return 0; 10995038Sphk 11095038Sphk const Value *V = (*MI->memoperands_begin())->getValue(); 11195038Sphk if (!V) 11295038Sphk return 0; 11395038Sphk 11495038Sphk V = getUnderlyingObject(V); 11595038Sphk if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 11695038Sphk // For now, ignore PseudoSourceValues which may alias LLVM IR values 11795038Sphk // because the code that uses this function has no way to cope with 11895038Sphk // such aliases. 11995038Sphk if (PSV->isAliased(MFI)) 12092108Sphk return 0; 12192108Sphk 12292108Sphk MayAlias = PSV->mayAlias(MFI); 12392108Sphk return V; 12492108Sphk } 12592108Sphk 12692108Sphk if (isIdentifiedObject(V)) 12792108Sphk return V; 12892108Sphk 12992108Sphk return 0; 13092108Sphk} 13192108Sphk 13292108Sphkvoid ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { 13392108Sphk if (MachineLoop *ML = MLI.getLoopFor(BB)) 13492108Sphk if (BB == ML->getLoopLatch()) { 13592403Sphk MachineBasicBlock *Header = ML->getHeader(); 13692403Sphk for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), 13792108Sphk E = Header->livein_end(); I != E; ++I) 13892108Sphk LoopLiveInRegs.insert(*I); 13992108Sphk LoopRegs.VisitLoop(ML); 14092403Sphk } 14192108Sphk} 14292108Sphk 14392108Sphkvoid ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { 14492108Sphk // We'll be allocating one SUnit for each instruction, plus one for 14592108Sphk // the region exit node. 14692108Sphk SUnits.reserve(BB->size()); 14792108Sphk 14892108Sphk // We build scheduling units by walking a block's instruction list from bottom 14992108Sphk // to top. 15092108Sphk 15192108Sphk // Remember where a generic side-effecting instruction is as we procede. 15292108Sphk SUnit *BarrierChain = 0, *AliasChain = 0; 15392108Sphk 15492108Sphk // Memory references to specific known memory locations are tracked 15592108Sphk // so that they can be given more precise dependencies. We track 15692108Sphk // separately the known memory locations that may alias and those 15792403Sphk // that are known not to alias 15892403Sphk std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; 15992108Sphk std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 16092403Sphk 16192403Sphk // Keep track of dangling debug references to registers. 16292108Sphk std::pair<MachineInstr*, unsigned> 16392403Sphk DanglingDebugValue[TargetRegisterInfo::FirstVirtualRegister]; 16492403Sphk 16592108Sphk // Check to see if the scheduler cares about latencies. 16692403Sphk bool UnitLatencies = ForceUnitLatencies(); 16794287Sphk 16894287Sphk // Ask the target if address-backscheduling is desirable, and if so how much. 16995038Sphk const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 17095038Sphk unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 17192403Sphk 17292403Sphk // Remove any stale debug info; sometimes BuildSchedGraph is called again 17392403Sphk // without emitting the info from the previous call. 17492403Sphk DbgValueVec.clear(); 17592403Sphk std::memset(DanglingDebugValue, 0, sizeof(DanglingDebugValue)); 17692403Sphk 17792403Sphk // Walk the list of instructions, from bottom moving up. 17892403Sphk for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; 17992403Sphk MII != MIE; --MII) { 18092403Sphk MachineInstr *MI = prior(MII); 18192108Sphk // DBG_VALUE does not have SUnit's built, so just remember these for later 18292403Sphk // reinsertion. 18392403Sphk if (MI->isDebugValue()) { 18492403Sphk if (MI->getNumOperands()==3 && MI->getOperand(0).isReg() && 18592403Sphk MI->getOperand(0).getReg()) 18692403Sphk DanglingDebugValue[MI->getOperand(0).getReg()] = 18792108Sphk std::make_pair(MI, DbgValueVec.size()); 18892108Sphk DbgValueVec.push_back(MI); 18992403Sphk continue; 19092108Sphk } 19192108Sphk const TargetInstrDesc &TID = MI->getDesc(); 19292108Sphk assert(!TID.isTerminator() && !MI->isLabel() && 19392108Sphk "Cannot schedule terminators or labels!"); 19492108Sphk // Create the SUnit for this MI. 19592108Sphk SUnit *SU = NewSUnit(MI); 19692108Sphk 19792108Sphk // Assign the Latency field of SU using target-provided information. 19892108Sphk if (UnitLatencies) 19992108Sphk SU->Latency = 1; 20092108Sphk else 20192108Sphk ComputeLatency(SU); 20293248Sphk 20392108Sphk // Add register-based dependencies (data, anti, and output). 20492108Sphk for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 20592108Sphk const MachineOperand &MO = MI->getOperand(j); 20692108Sphk if (!MO.isReg()) continue; 20793642Sphk unsigned Reg = MO.getReg(); 20892108Sphk if (Reg == 0) continue; 20992108Sphk 21092108Sphk assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); 21192108Sphk 21293248Sphk if (MO.isDef() && DanglingDebugValue[Reg].first!=0) { 21392108Sphk SU->setDbgInstr(DanglingDebugValue[Reg].first); 21493776Sphk DbgValueVec[DanglingDebugValue[Reg].second] = 0; 21592108Sphk DanglingDebugValue[Reg] = std::make_pair((MachineInstr*)0, 0); 21692108Sphk } 21792108Sphk 21892108Sphk std::vector<SUnit *> &UseList = Uses[Reg]; 21992108Sphk std::vector<SUnit *> &DefList = Defs[Reg]; 22092108Sphk // Optionally add output and anti dependencies. For anti 22192108Sphk // dependencies we use a latency of 0 because for a multi-issue 22292108Sphk // target we want to allow the defining instruction to issue 22392108Sphk // in the same cycle as the using instruction. 22492108Sphk // TODO: Using a latency of 1 here for output dependencies assumes 22592108Sphk // there's no cost for reusing registers. 22692108Sphk SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 22792108Sphk unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1; 22892108Sphk for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 22992108Sphk SUnit *DefSU = DefList[i]; 23092108Sphk if (DefSU != SU && 23192108Sphk (Kind != SDep::Output || !MO.isDead() || 23292108Sphk !DefSU->getInstr()->registerDefIsDead(Reg))) 23392108Sphk DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg)); 23492108Sphk } 23592108Sphk for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 23692108Sphk std::vector<SUnit *> &DefList = Defs[*Alias]; 23792108Sphk for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 23892108Sphk SUnit *DefSU = DefList[i]; 23992108Sphk if (DefSU != SU && 24092108Sphk (Kind != SDep::Output || !MO.isDead() || 24192108Sphk !DefSU->getInstr()->registerDefIsDead(*Alias))) 24292108Sphk DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias)); 24392108Sphk } 24492108Sphk } 24592108Sphk 24692108Sphk if (MO.isDef()) { 24792108Sphk // Add any data dependencies. 24892108Sphk unsigned DataLatency = SU->Latency; 24992108Sphk for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 25092108Sphk SUnit *UseSU = UseList[i]; 25192108Sphk if (UseSU != SU) { 25292108Sphk unsigned LDataLatency = DataLatency; 25392108Sphk // Optionally add in a special extra latency for nodes that 25492108Sphk // feed addresses. 25592108Sphk // TODO: Do this for register aliases too. 25692108Sphk // TODO: Perhaps we should get rid of 25792108Sphk // SpecialAddressLatency and just move this into 25892108Sphk // adjustSchedDependency for the targets that care about 25992108Sphk // it. 260 if (SpecialAddressLatency != 0 && !UnitLatencies) { 261 MachineInstr *UseMI = UseSU->getInstr(); 262 const TargetInstrDesc &UseTID = UseMI->getDesc(); 263 int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg); 264 assert(RegUseIndex >= 0 && "UseMI doesn's use register!"); 265 if ((UseTID.mayLoad() || UseTID.mayStore()) && 266 (unsigned)RegUseIndex < UseTID.getNumOperands() && 267 UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 268 LDataLatency += SpecialAddressLatency; 269 } 270 // Adjust the dependence latency using operand def/use 271 // information (if any), and then allow the target to 272 // perform its own adjustments. 273 const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg); 274 if (!UnitLatencies) { 275 ComputeOperandLatency(SU, UseSU, (SDep &)dep); 276 ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 277 } 278 UseSU->addPred(dep); 279 } 280 } 281 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 282 std::vector<SUnit *> &UseList = Uses[*Alias]; 283 for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 284 SUnit *UseSU = UseList[i]; 285 if (UseSU != SU) { 286 const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias); 287 if (!UnitLatencies) { 288 ComputeOperandLatency(SU, UseSU, (SDep &)dep); 289 ST.adjustSchedDependency(SU, UseSU, (SDep &)dep); 290 } 291 UseSU->addPred(dep); 292 } 293 } 294 } 295 296 // If a def is going to wrap back around to the top of the loop, 297 // backschedule it. 298 if (!UnitLatencies && DefList.empty()) { 299 LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg); 300 if (I != LoopRegs.Deps.end()) { 301 const MachineOperand *UseMO = I->second.first; 302 unsigned Count = I->second.second; 303 const MachineInstr *UseMI = UseMO->getParent(); 304 unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 305 const TargetInstrDesc &UseTID = UseMI->getDesc(); 306 // TODO: If we knew the total depth of the region here, we could 307 // handle the case where the whole loop is inside the region but 308 // is large enough that the isScheduleHigh trick isn't needed. 309 if (UseMOIdx < UseTID.getNumOperands()) { 310 // Currently, we only support scheduling regions consisting of 311 // single basic blocks. Check to see if the instruction is in 312 // the same region by checking to see if it has the same parent. 313 if (UseMI->getParent() != MI->getParent()) { 314 unsigned Latency = SU->Latency; 315 if (UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 316 Latency += SpecialAddressLatency; 317 // This is a wild guess as to the portion of the latency which 318 // will be overlapped by work done outside the current 319 // scheduling region. 320 Latency -= std::min(Latency, Count); 321 // Add the artifical edge. 322 ExitSU.addPred(SDep(SU, SDep::Order, Latency, 323 /*Reg=*/0, /*isNormalMemory=*/false, 324 /*isMustAlias=*/false, 325 /*isArtificial=*/true)); 326 } else if (SpecialAddressLatency > 0 && 327 UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 328 // The entire loop body is within the current scheduling region 329 // and the latency of this operation is assumed to be greater 330 // than the latency of the loop. 331 // TODO: Recursively mark data-edge predecessors as 332 // isScheduleHigh too. 333 SU->isScheduleHigh = true; 334 } 335 } 336 LoopRegs.Deps.erase(I); 337 } 338 } 339 340 UseList.clear(); 341 if (!MO.isDead()) 342 DefList.clear(); 343 DefList.push_back(SU); 344 } else { 345 UseList.push_back(SU); 346 } 347 } 348 349 // Add chain dependencies. 350 // Chain dependencies used to enforce memory order should have 351 // latency of 0 (except for true dependency of Store followed by 352 // aliased Load... we estimate that with a single cycle of latency 353 // assuming the hardware will bypass) 354 // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 355 // after stack slots are lowered to actual addresses. 356 // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 357 // produce more precise dependence information. 358#define STORE_LOAD_LATENCY 1 359 unsigned TrueMemOrderLatency = 0; 360 if (TID.isCall() || TID.hasUnmodeledSideEffects() || 361 (MI->hasVolatileMemoryRef() && 362 (!TID.mayLoad() || !MI->isInvariantLoad(AA)))) { 363 // Be conservative with these and add dependencies on all memory 364 // references, even those that are known to not alias. 365 for (std::map<const Value *, SUnit *>::iterator I = 366 NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 367 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 368 } 369 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 370 NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 371 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 372 I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 373 } 374 NonAliasMemDefs.clear(); 375 NonAliasMemUses.clear(); 376 // Add SU to the barrier chain. 377 if (BarrierChain) 378 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 379 BarrierChain = SU; 380 381 // fall-through 382 new_alias_chain: 383 // Chain all possibly aliasing memory references though SU. 384 if (AliasChain) 385 AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 386 AliasChain = SU; 387 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 388 PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 389 for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), 390 E = AliasMemDefs.end(); I != E; ++I) { 391 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 392 } 393 for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 394 AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 395 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 396 I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 397 } 398 PendingLoads.clear(); 399 AliasMemDefs.clear(); 400 AliasMemUses.clear(); 401 } else if (TID.mayStore()) { 402 bool MayAlias = true; 403 TrueMemOrderLatency = STORE_LOAD_LATENCY; 404 if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 405 // A store to a specific PseudoSourceValue. Add precise dependencies. 406 // Record the def in MemDefs, first adding a dep if there is 407 // an existing def. 408 std::map<const Value *, SUnit *>::iterator I = 409 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 410 std::map<const Value *, SUnit *>::iterator IE = 411 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 412 if (I != IE) { 413 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 414 /*isNormalMemory=*/true)); 415 I->second = SU; 416 } else { 417 if (MayAlias) 418 AliasMemDefs[V] = SU; 419 else 420 NonAliasMemDefs[V] = SU; 421 } 422 // Handle the uses in MemUses, if there are any. 423 std::map<const Value *, std::vector<SUnit *> >::iterator J = 424 ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 425 std::map<const Value *, std::vector<SUnit *> >::iterator JE = 426 ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 427 if (J != JE) { 428 for (unsigned i = 0, e = J->second.size(); i != e; ++i) 429 J->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency, 430 /*Reg=*/0, /*isNormalMemory=*/true)); 431 J->second.clear(); 432 } 433 if (MayAlias) { 434 // Add dependencies from all the PendingLoads, i.e. loads 435 // with no underlying object. 436 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 437 PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 438 // Add dependence on alias chain, if needed. 439 if (AliasChain) 440 AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 441 } 442 // Add dependence on barrier chain, if needed. 443 if (BarrierChain) 444 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 445 } else { 446 // Treat all other stores conservatively. 447 goto new_alias_chain; 448 } 449 } else if (TID.mayLoad()) { 450 bool MayAlias = true; 451 TrueMemOrderLatency = 0; 452 if (MI->isInvariantLoad(AA)) { 453 // Invariant load, no chain dependencies needed! 454 } else { 455 if (const Value *V = 456 getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 457 // A load from a specific PseudoSourceValue. Add precise dependencies. 458 std::map<const Value *, SUnit *>::iterator I = 459 ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 460 std::map<const Value *, SUnit *>::iterator IE = 461 ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 462 if (I != IE) 463 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 464 /*isNormalMemory=*/true)); 465 if (MayAlias) 466 AliasMemUses[V].push_back(SU); 467 else 468 NonAliasMemUses[V].push_back(SU); 469 } else { 470 // A load with no underlying object. Depend on all 471 // potentially aliasing stores. 472 for (std::map<const Value *, SUnit *>::iterator I = 473 AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 474 I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 475 476 PendingLoads.push_back(SU); 477 MayAlias = true; 478 } 479 480 // Add dependencies on alias and barrier chains, if needed. 481 if (MayAlias && AliasChain) 482 AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 483 if (BarrierChain) 484 BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 485 } 486 } 487 } 488 489 for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { 490 Defs[i].clear(); 491 Uses[i].clear(); 492 } 493 PendingLoads.clear(); 494} 495 496void ScheduleDAGInstrs::FinishBlock() { 497 // Nothing to do. 498} 499 500void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { 501 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 502 503 // Compute the latency for the node. 504 SU->Latency = 505 InstrItins.getStageLatency(SU->getInstr()->getDesc().getSchedClass()); 506 507 // Simplistic target-independent heuristic: assume that loads take 508 // extra time. 509 if (InstrItins.isEmpty()) 510 if (SU->getInstr()->getDesc().mayLoad()) 511 SU->Latency += 2; 512} 513 514void ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use, 515 SDep& dep) const { 516 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 517 if (InstrItins.isEmpty()) 518 return; 519 520 // For a data dependency with a known register... 521 if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0)) 522 return; 523 524 const unsigned Reg = dep.getReg(); 525 526 // ... find the definition of the register in the defining 527 // instruction 528 MachineInstr *DefMI = Def->getInstr(); 529 int DefIdx = DefMI->findRegisterDefOperandIdx(Reg); 530 if (DefIdx != -1) { 531 int DefCycle = InstrItins.getOperandCycle(DefMI->getDesc().getSchedClass(), DefIdx); 532 if (DefCycle >= 0) { 533 MachineInstr *UseMI = Use->getInstr(); 534 const unsigned UseClass = UseMI->getDesc().getSchedClass(); 535 536 // For all uses of the register, calculate the maxmimum latency 537 int Latency = -1; 538 for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 539 const MachineOperand &MO = UseMI->getOperand(i); 540 if (!MO.isReg() || !MO.isUse()) 541 continue; 542 unsigned MOReg = MO.getReg(); 543 if (MOReg != Reg) 544 continue; 545 546 int UseCycle = InstrItins.getOperandCycle(UseClass, i); 547 if (UseCycle >= 0) 548 Latency = std::max(Latency, DefCycle - UseCycle + 1); 549 } 550 551 // If we found a latency, then replace the existing dependence latency. 552 if (Latency >= 0) 553 dep.setLatency(Latency); 554 } 555 } 556} 557 558void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 559 SU->getInstr()->dump(); 560} 561 562std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 563 std::string s; 564 raw_string_ostream oss(s); 565 if (SU == &EntrySU) 566 oss << "<entry>"; 567 else if (SU == &ExitSU) 568 oss << "<exit>"; 569 else 570 SU->getInstr()->print(oss); 571 return oss.str(); 572} 573 574// EmitSchedule - Emit the machine code in scheduled order. 575MachineBasicBlock *ScheduleDAGInstrs:: 576EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) { 577 // For MachineInstr-based scheduling, we're rescheduling the instructions in 578 // the block, so start by removing them from the block. 579 while (Begin != InsertPos) { 580 MachineBasicBlock::iterator I = Begin; 581 ++Begin; 582 BB->remove(I); 583 } 584 585 // First reinsert any remaining debug_values; these are either constants, 586 // or refer to live-in registers. The beginning of the block is the right 587 // place for the latter. The former might reasonably be placed elsewhere 588 // using some kind of ordering algorithm, but right now it doesn't matter. 589 for (int i = DbgValueVec.size()-1; i>=0; --i) 590 if (DbgValueVec[i]) 591 BB->insert(InsertPos, DbgValueVec[i]); 592 593 // Then re-insert them according to the given schedule. 594 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 595 SUnit *SU = Sequence[i]; 596 if (!SU) { 597 // Null SUnit* is a noop. 598 EmitNoop(); 599 continue; 600 } 601 602 BB->insert(InsertPos, SU->getInstr()); 603 if (SU->getDbgInstr()) 604 BB->insert(InsertPos, SU->getDbgInstr()); 605 } 606 607 // Update the Begin iterator, as the first instruction in the block 608 // may have been scheduled later. 609 if (!DbgValueVec.empty()) { 610 for (int i = DbgValueVec.size()-1; i>=0; --i) 611 if (DbgValueVec[i]!=0) { 612 Begin = DbgValueVec[DbgValueVec.size()-1]; 613 break; 614 } 615 } else if (!Sequence.empty()) 616 Begin = Sequence[0]->getInstr(); 617 618 DbgValueVec.clear(); 619 return BB; 620} 621