1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This implements the ScheduleDAGInstrs class, which implements re-scheduling 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// of MachineInstrs. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "sched-instrs" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "ScheduleDAGInstrs.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Operator.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/AliasAnalysis.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/ValueTracking.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineFunctionPass.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineMemOperand.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/PseudoSourceValue.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/MC/MCInstrItineraries.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetMachine.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetInstrInfo.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetRegisterInfo.h" 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetSubtargetInfo.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallSet.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineLoopInfo &mli, 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineDominatorTree &mdt) 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InstrItins(mf.getTarget().getInstrItineraryData()), 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Defs(TRI->getNumRegs()), Uses(TRI->getNumRegs()), 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRegs(MLI, MDT), FirstDbgValue(0) { 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgValues.clear(); 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Run - perform scheduling. 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGInstrs::Run(MachineBasicBlock *bb, 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator begin, 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator end, 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned endcount) { 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB = bb; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Begin = begin; 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPosIndex = endcount; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScheduleDAG::Run(bb, end); 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// getUnderlyingObjectFromInt - This is the function that does the work of 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic const Value *getUnderlyingObjectFromInt(const Value *V) { 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const Operator *U = dyn_cast<Operator>(V)) { 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we find a ptrtoint, we can transfer control back to the 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // regular getUnderlyingObjectFromInt. 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (U->getOpcode() == Instruction::PtrToInt) 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return U->getOperand(0); 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we find an add of a constant or a multiplied value, it's 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // likely that the other operand will lead us to the base 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // object. We don't have to worry about the case where the 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // object address is somehow being computed by the multiply, 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // because our callers only care when the result is an 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // identifibale object. 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (U->getOpcode() != Instruction::Add || 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (!isa<ConstantInt>(U->getOperand(1)) && 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Operator::getOpcode(U->getOperand(1)) != Instruction::Mul)) 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = U->getOperand(0); 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (1); 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// getUnderlyingObject - This is a wrapper around GetUnderlyingObject 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic const Value *getUnderlyingObject(const Value *V) { 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // First just call Value::getUnderlyingObject to let it do what it does. 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = GetUnderlyingObject(V); 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it found an inttoptr, use special code to continue climing. 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Operator::getOpcode(V) != Instruction::IntToPtr) 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If that succeeded in finding a pointer, continue the search. 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!O->getType()->isPointerTy()) 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = O; 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (1); 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// getUnderlyingObjectForInstr - If this machine instr has memory reference 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// information and it can be tracked to a normal reference to a known 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// object, return the Value for that object. Otherwise return null. 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic const Value *getUnderlyingObjectForInstr(const MachineInstr *MI, 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineFrameInfo *MFI, 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool &MayAlias) { 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MayAlias = true; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MI->hasOneMemOperand() || 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !(*MI->memoperands_begin())->getValue() || 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (*MI->memoperands_begin())->isVolatile()) 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *V = (*MI->memoperands_begin())->getValue(); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!V) 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = getUnderlyingObject(V); 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // For now, ignore PseudoSourceValues which may alias LLVM IR values 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // because the code that uses this function has no way to cope with 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // such aliases. 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PSV->isAliased(MFI)) 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MayAlias = PSV->mayAlias(MFI); 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isIdentifiedObject(V)) 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRegs.Deps.clear(); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MachineLoop *ML = MLI.getLoopFor(BB)) 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BB == ML->getLoopLatch()) { 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *Header = ML->getHeader(); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = Header->livein_end(); I != E; ++I) 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopLiveInRegs.insert(*I); 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopRegs.VisitLoop(ML); 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// AddSchedBarrierDeps - Add dependencies from instructions in the current 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// list of instructions being scheduled to scheduling barrier by adding 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the exit SU to the register defs and use list. This is because we want to 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// make sure instructions which define registers that are either used by 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the terminator or are live-out are properly scheduled. This is 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// especially important when the definition latency of the return value(s) 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// are too high to be hidden by the branch or when the liveout registers 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// used by instructions in the fallthrough block. 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ScheduleDAGInstrs::AddSchedBarrierDeps() { 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *ExitMI = InsertPos != BB->end() ? &*InsertPos : 0; 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExitSU.setInstr(ExitMI); 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool AllDepKnown = ExitMI && 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (ExitMI->getDesc().isCall() || ExitMI->getDesc().isBarrier()); 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ExitMI && AllDepKnown) { 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it's a call or a barrier, add dependencies on the defs and uses of 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // instruction. 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = ExitMI->getNumOperands(); i != e; ++i) { 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineOperand &MO = ExitMI->getOperand(i); 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MO.isReg() || MO.isDef()) continue; 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Reg = MO.getReg(); 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Reg == 0) continue; 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Uses[Reg].push_back(&ExitSU); 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For others, e.g. fallthrough, conditional branch, assume the exit 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // uses all the registers that are livein to the successor blocks. 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallSet<unsigned, 8> Seen; 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE = BB->succ_end(); SI != SE; ++SI) 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = (*SI)->livein_end(); I != E; ++I) { 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Reg = *I; 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Seen.insert(Reg)) 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Uses[Reg].push_back(&ExitSU); 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We'll be allocating one SUnit for each instruction, plus one for 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the region exit node. 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnits.reserve(BB->size()); 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We build scheduling units by walking a block's instruction list from bottom 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to top. 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember where a generic side-effecting instruction is as we procede. 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *BarrierChain = 0, *AliasChain = 0; 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Memory references to specific known memory locations are tracked 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // so that they can be given more precise dependencies. We track 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // separately the known memory locations that may alias and those 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that are known not to alias 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs; 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if the scheduler cares about latencies. 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool UnitLatencies = ForceUnitLatencies(); 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Ask the target if address-backscheduling is desirable, and if so how much. 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned SpecialAddressLatency = ST.getSpecialAddressLatency(); 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove any stale debug info; sometimes BuildSchedGraph is called again 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // without emitting the info from the previous call. 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgValues.clear(); 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman FirstDbgValue = NULL; 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Model data dependencies between instructions being scheduled and the 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ExitSU. 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddSchedBarrierDeps(); 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Defs[i].empty() && "Only BuildGraph should push/pop Defs"); 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Walk the list of instructions, from bottom moving up. 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *PrevMI = NULL; 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MII != MIE; --MII) { 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *MI = prior(MII); 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MI && PrevMI) { 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgValues.push_back(std::make_pair(PrevMI, MI)); 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PrevMI = NULL; 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI->isDebugValue()) { 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PrevMI = MI; 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = MI->getDesc(); 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!MCID.isTerminator() && !MI->isLabel() && 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Cannot schedule terminators or labels!"); 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create the SUnit for this MI. 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *SU = NewSUnit(MI); 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isCall = MCID.isCall(); 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isCommutable = MCID.isCommutable(); 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Assign the Latency field of SU using target-provided information. 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UnitLatencies) 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->Latency = 1; 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ComputeLatency(SU); 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add register-based dependencies (data, anti, and output). 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineOperand &MO = MI->getOperand(j); 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isReg()) continue; 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = MO.getReg(); 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Reg == 0) continue; 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SUnit *> &UseList = Uses[Reg]; 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Defs are push in the order they are visited and never reordered. 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SUnit *> &DefList = Defs[Reg]; 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Optionally add output and anti dependencies. For anti 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dependencies we use a latency of 0 because for a multi-issue 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // target we want to allow the defining instruction to issue 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // in the same cycle as the using instruction. 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: Using a latency of 1 here for output dependencies assumes 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // there's no cost for reusing registers. 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned AOLatency = (Kind == SDep::Anti) ? 0 : 1; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = DefList.size(); i != e; ++i) { 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *DefSU = DefList[i]; 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DefSU == &ExitSU) 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DefSU != SU && 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (Kind != SDep::Output || !MO.isDead() || 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !DefSU->getInstr()->registerDefIsDead(Reg))) 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/Reg)); 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<SUnit *> &MemDefList = Defs[*Alias]; 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = MemDefList.size(); i != e; ++i) { 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SUnit *DefSU = MemDefList[i]; 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DefSU == &ExitSU) 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DefSU != SU && 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (Kind != SDep::Output || !MO.isDead() || 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !DefSU->getInstr()->registerDefIsDead(*Alias))) 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DefSU->addPred(SDep(SU, Kind, AOLatency, /*Reg=*/ *Alias)); 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isDef()) { 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add any data dependencies. 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned DataLatency = SU->Latency; 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *UseSU = UseList[i]; 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UseSU == SU) 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned LDataLatency = DataLatency; 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Optionally add in a special extra latency for nodes that 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // feed addresses. 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: Do this for register aliases too. 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: Perhaps we should get rid of 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // SpecialAddressLatency and just move this into 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // adjustSchedDependency for the targets that care about it. 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SpecialAddressLatency != 0 && !UnitLatencies && 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseSU != &ExitSU) { 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *UseMI = UseSU->getInstr(); 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &UseMCID = UseMI->getDesc(); 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg); 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(RegUseIndex >= 0 && "UseMI doesn's use register!"); 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RegUseIndex >= 0 && 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (UseMCID.mayLoad() || UseMCID.mayStore()) && 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (unsigned)RegUseIndex < UseMCID.getNumOperands() && 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMCID.OpInfo[RegUseIndex].isLookupPtrRegClass()) 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LDataLatency += SpecialAddressLatency; 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Adjust the dependence latency using operand def/use 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // information (if any), and then allow the target to 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // perform its own adjustments. 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SDep& dep = SDep(SU, SDep::Data, LDataLatency, Reg); 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!UnitLatencies) { 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ComputeOperandLatency(SU, UseSU, const_cast<SDep &>(dep)); 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ST.adjustSchedDependency(SU, UseSU, const_cast<SDep &>(dep)); 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UseSU->addPred(dep); 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SUnit *> &UseList = Uses[*Alias]; 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = UseList.size(); i != e; ++i) { 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *UseSU = UseList[i]; 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UseSU == SU) 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SDep& dep = SDep(SU, SDep::Data, DataLatency, *Alias); 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!UnitLatencies) { 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ComputeOperandLatency(SU, UseSU, const_cast<SDep &>(dep)); 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ST.adjustSchedDependency(SU, UseSU, const_cast<SDep &>(dep)); 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UseSU->addPred(dep); 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If a def is going to wrap back around to the top of the loop, 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // backschedule it. 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!UnitLatencies && DefList.empty()) { 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg); 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != LoopRegs.Deps.end()) { 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineOperand *UseMO = I->second.first; 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Count = I->second.second; 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineInstr *UseMI = UseMO->getParent(); 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned UseMOIdx = UseMO - &UseMI->getOperand(0); 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &UseMCID = UseMI->getDesc(); 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: If we knew the total depth of the region here, we could 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // handle the case where the whole loop is inside the region but 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is large enough that the isScheduleHigh trick isn't needed. 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMOIdx < UseMCID.getNumOperands()) { 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Currently, we only support scheduling regions consisting of 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // single basic blocks. Check to see if the instruction is in 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the same region by checking to see if it has the same parent. 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UseMI->getParent() != MI->getParent()) { 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Latency = SU->Latency; 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Latency += SpecialAddressLatency; 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is a wild guess as to the portion of the latency which 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // will be overlapped by work done outside the current 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // scheduling region. 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Latency -= std::min(Latency, Count); 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Add the artificial edge. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExitSU.addPred(SDep(SU, SDep::Order, Latency, 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*Reg=*/0, /*isNormalMemory=*/false, 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*isMustAlias=*/false, 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*isArtificial=*/true)); 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (SpecialAddressLatency > 0 && 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The entire loop body is within the current scheduling region 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and the latency of this operation is assumed to be greater 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // than the latency of the loop. 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: Recursively mark data-edge predecessors as 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isScheduleHigh too. 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->isScheduleHigh = true; 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoopRegs.Deps.erase(I); 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UseList.clear(); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isDead()) 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DefList.clear(); 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Calls will not be reordered because of chain dependencies (see 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // below). Since call operands are dead, calls may continue to be added 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to the DefList making dependence checking quadratic in the size of 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the block. Instead, we leave only one call at the back of the 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DefList. 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SU->isCall) { 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!DefList.empty() && DefList.back()->isCall) 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DefList.pop_back(); 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DefList.push_back(SU); 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UseList.push_back(SU); 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add chain dependencies. 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Chain dependencies used to enforce memory order should have 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // latency of 0 (except for true dependency of Store followed by 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // aliased Load... we estimate that with a single cycle of latency 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // assuming the hardware will bypass) 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // after stack slots are lowered to actual addresses. 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // produce more precise dependence information. 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define STORE_LOAD_LATENCY 1 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned TrueMemOrderLatency = 0; 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MCID.isCall() || MI->hasUnmodeledSideEffects() || 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (MI->hasVolatileMemoryRef() && 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (!MCID.mayLoad() || !MI->isInvariantLoad(AA)))) { 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Be conservative with these and add dependencies on all memory 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // references, even those that are known to not alias. 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::map<const Value *, SUnit *>::iterator I = 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = I->second.size(); i != e; ++i) 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NonAliasMemDefs.clear(); 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NonAliasMemUses.clear(); 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add SU to the barrier chain. 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BarrierChain) 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BarrierChain = SU; 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // fall-through 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new_alias_chain: 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Chain all possibly aliasing memory references though SU. 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AliasChain) 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasChain = SU; 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(), 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = AliasMemDefs.end(); I != E; ++I) { 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (std::map<const Value *, std::vector<SUnit *> >::iterator I = 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = I->second.size(); i != e; ++i) 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PendingLoads.clear(); 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasMemDefs.clear(); 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasMemUses.clear(); 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (MCID.mayStore()) { 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MayAlias = true; 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TrueMemOrderLatency = STORE_LOAD_LATENCY; 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A store to a specific PseudoSourceValue. Add precise dependencies. 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Record the def in MemDefs, first adding a dep if there is 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // an existing def. 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::map<const Value *, SUnit *>::iterator I = 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::map<const Value *, SUnit *>::iterator IE = 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != IE) { 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*isNormalMemory=*/true)); 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second = SU; 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MayAlias) 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasMemDefs[V] = SU; 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NonAliasMemDefs[V] = SU; 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Handle the uses in MemUses, if there are any. 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::map<const Value *, std::vector<SUnit *> >::iterator J = 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::map<const Value *, std::vector<SUnit *> >::iterator JE = 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (J != JE) { 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = J->second.size(); i != e; ++i) 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman J->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency, 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*Reg=*/0, /*isNormalMemory=*/true)); 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman J->second.clear(); 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MayAlias) { 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add dependencies from all the PendingLoads, i.e. loads 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // with no underlying object. 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency)); 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add dependence on alias chain, if needed. 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AliasChain) 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add dependence on barrier chain, if needed. 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BarrierChain) 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Treat all other stores conservatively. 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto new_alias_chain; 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!ExitSU.isPred(SU)) 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Push store's up a bit to avoid them getting in between cmp 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // and branches. 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExitSU.addPred(SDep(SU, SDep::Order, 0, 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /*Reg=*/0, /*isNormalMemory=*/false, 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /*isMustAlias=*/false, 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /*isArtificial=*/true)); 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (MCID.mayLoad()) { 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MayAlias = true; 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TrueMemOrderLatency = 0; 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI->isInvariantLoad(AA)) { 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Invariant load, no chain dependencies needed! 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 52519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const Value *V = 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman getUnderlyingObjectForInstr(MI, MFI, MayAlias)) { 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A load from a specific PseudoSourceValue. Add precise dependencies. 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::map<const Value *, SUnit *>::iterator I = 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::map<const Value *, SUnit *>::iterator IE = 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != IE) 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0, /*Reg=*/0, 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*isNormalMemory=*/true)); 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MayAlias) 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasMemUses[V].push_back(SU); 53719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NonAliasMemUses[V].push_back(SU); 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A load with no underlying object. Depend on all 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // potentially aliasing stores. 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::map<const Value *, SUnit *>::iterator I = 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->second->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PendingLoads.push_back(SU); 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MayAlias = true; 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add dependencies on alias and barrier chains, if needed. 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MayAlias && AliasChain) 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AliasChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BarrierChain) 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BarrierChain->addPred(SDep(SU, SDep::Order, /*Latency=*/0)); 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 55819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PrevMI) 55919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman FirstDbgValue = PrevMI; 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Defs[i].clear(); 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Uses[i].clear(); 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PendingLoads.clear(); 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGInstrs::FinishBlock() { 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Nothing to do. 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute the latency for the node. 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!InstrItins || InstrItins->isEmpty()) { 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->Latency = 1; 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 57719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Simplistic target-independent heuristic: assume that loads take 57819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // extra time. 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SU->getInstr()->getDesc().mayLoad()) 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->Latency += 2; 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->Latency = TII->getInstrLatency(InstrItins, SU->getInstr()); 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ScheduleDAGInstrs::ComputeOperandLatency(SUnit *Def, SUnit *Use, 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDep& dep) const { 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!InstrItins || InstrItins->isEmpty()) 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // For a data dependency with a known register... 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0)) 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const unsigned Reg = dep.getReg(); 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ... find the definition of the register in the defining 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *DefMI = Def->getInstr(); 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int DefIdx = DefMI->findRegisterDefOperandIdx(Reg); 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DefIdx != -1) { 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineOperand &MO = DefMI->getOperand(DefIdx); 60319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isReg() && MO.isImplicit() && 60419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DefIdx >= (int)DefMI->getDesc().getNumOperands()) { 60519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This is an implicit def, getOperandLatency() won't return the correct 60619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // latency. e.g. 60719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // %D6<def>, %D7<def> = VLD1q16 %R2<kill>, 0, ..., %Q3<imp-def> 60819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // %Q1<def> = VMULv8i16 %Q1<kill>, %Q3<kill>, ... 60919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // What we want is to compute latency between def of %D6/%D7 and use of 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // %Q3 instead. 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DefIdx = DefMI->findRegisterDefOperandIdx(Reg, false, true, TRI); 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *UseMI = Use->getInstr(); 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For all uses of the register, calculate the maxmimum latency 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int Latency = -1; 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMI) { 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineOperand &MO = UseMI->getOperand(i); 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isReg() || !MO.isUse()) 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned MOReg = MO.getReg(); 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MOReg != Reg) 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int UseCycle = TII->getOperandLatency(InstrItins, DefMI, DefIdx, 62619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI, i); 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Latency = std::max(Latency, UseCycle); 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 62919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 63019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // UseMI is null, then it must be a scheduling barrier. 63119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!InstrItins || InstrItins->isEmpty()) 63219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DefClass = DefMI->getDesc().getSchedClass(); 63419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Latency = InstrItins->getOperandCycle(DefClass, DefIdx); 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 63619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we found a latency, then replace the existing dependence latency. 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Latency >= 0) 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dep.setLatency(Latency); 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->getInstr()->dump(); 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstd::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string s; 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman raw_string_ostream oss(s); 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SU == &EntrySU) 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman oss << "<entry>"; 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (SU == &ExitSU) 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman oss << "<exit>"; 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->getInstr()->print(oss); 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return oss.str(); 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// EmitSchedule - Emit the machine code in scheduled order. 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanMachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() { 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // For MachineInstr-based scheduling, we're rescheduling the instructions in 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the block, so start by removing them from the block. 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Begin != InsertPos) { 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator I = Begin; 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Begin; 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->remove(I); 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If first instruction was a DBG_VALUE then put it back. 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (FirstDbgValue) 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BB->insert(InsertPos, FirstDbgValue); 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Then re-insert them according to the given schedule. 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SUnit *SU = Sequence[i]) 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BB->insert(InsertPos, SU->getInstr()); 67719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Null SUnit* is a noop. 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EmitNoop(); 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update the Begin iterator, as the first instruction in the block 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // may have been scheduled later. 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Sequence.empty()) 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Begin = Sequence[0]->getInstr(); 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 68719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Reinsert any remaining debug_values. 68819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 68919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 69119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *DbgValue = P.first; 69219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *OrigPrivMI = P.second; 69319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BB->insertAfter(OrigPrivMI, DbgValue); 69419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 69519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgValues.clear(); 69619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman FirstDbgValue = NULL; 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BB; 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 699