ScheduleDAGInstrs.cpp [plain text]
#define DEBUG_TYPE "sched-instrs"
#include "llvm/Operator.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/SmallSet.h"
using namespace llvm;
ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
const MachineLoopInfo &mli,
const MachineDominatorTree &mdt,
bool IsPostRAFlag,
LiveIntervals *lis)
: ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()),
InstrItins(mf.getTarget().getInstrItineraryData()), LIS(lis),
IsPostRA(IsPostRAFlag), UnitLatencies(false), LoopRegs(MLI, MDT),
FirstDbgValue(0) {
assert((IsPostRA || LIS) && "PreRA scheduling requires LiveIntervals");
DbgValues.clear();
assert(!(IsPostRA && MRI.getNumVirtRegs()) &&
"Virtual registers must be removed prior to PostRA scheduling");
}
static const Value *getUnderlyingObjectFromInt(const Value *V) {
do {
if (const Operator *U = dyn_cast<Operator>(V)) {
if (U->getOpcode() == Instruction::PtrToInt)
return U->getOperand(0);
if (U->getOpcode() != Instruction::Add ||
(!isa<ConstantInt>(U->getOperand(1)) &&
Operator::getOpcode(U->getOperand(1)) != Instruction::Mul))
return V;
V = U->getOperand(0);
} else {
return V;
}
assert(V->getType()->isIntegerTy() && "Unexpected operand type!");
} while (1);
}
static const Value *getUnderlyingObject(const Value *V) {
do {
V = GetUnderlyingObject(V);
if (Operator::getOpcode(V) != Instruction::IntToPtr)
break;
const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
if (!O->getType()->isPointerTy())
break;
V = O;
} while (1);
return V;
}
static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI,
const MachineFrameInfo *MFI,
bool &MayAlias) {
MayAlias = true;
if (!MI->hasOneMemOperand() ||
!(*MI->memoperands_begin())->getValue() ||
(*MI->memoperands_begin())->isVolatile())
return 0;
const Value *V = (*MI->memoperands_begin())->getValue();
if (!V)
return 0;
V = getUnderlyingObject(V);
if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
if (PSV->isAliased(MFI))
return 0;
MayAlias = PSV->mayAlias(MFI);
return V;
}
if (isIdentifiedObject(V))
return V;
return 0;
}
void ScheduleDAGInstrs::startBlock(MachineBasicBlock *BB) {
LoopRegs.Deps.clear();
if (MachineLoop *ML = MLI.getLoopFor(BB))
if (BB == ML->getLoopLatch())
LoopRegs.VisitLoop(ML);
}
void ScheduleDAGInstrs::finishBlock() {
}
void Reg2SUnitsMap::setRegLimit(unsigned Limit) {
PhysRegSet.setUniverse(Limit);
SUnits.resize(Limit);
}
void Reg2SUnitsMap::clear() {
for (const_iterator I = reg_begin(), E = reg_end(); I != E; ++I) {
SUnits[*I].clear();
}
PhysRegSet.clear();
}
void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
unsigned endcount) {
BB = bb;
Begin = begin;
End = end;
EndIndex = endcount;
UnitLatencies = forceUnitLatencies();
ScheduleDAG::clearDAG();
}
void ScheduleDAGInstrs::exitRegion() {
}
void ScheduleDAGInstrs::addSchedBarrierDeps() {
MachineInstr *ExitMI = End != BB->end() ? &*End : 0;
ExitSU.setInstr(ExitMI);
bool AllDepKnown = ExitMI &&
(ExitMI->isCall() || ExitMI->isBarrier());
if (ExitMI && AllDepKnown) {
for (unsigned i = 0, e = ExitMI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = ExitMI->getOperand(i);
if (!MO.isReg() || MO.isDef()) continue;
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
if (TRI->isPhysicalRegister(Reg))
Uses[Reg].push_back(&ExitSU);
else
assert(!IsPostRA && "Virtual register encountered after regalloc.");
}
} else {
SmallSet<unsigned, 8> Seen;
for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
SE = BB->succ_end(); SI != SE; ++SI)
for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
E = (*SI)->livein_end(); I != E; ++I) {
unsigned Reg = *I;
if (Seen.insert(Reg))
Uses[Reg].push_back(&ExitSU);
}
}
}
void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU,
const MachineOperand &MO) {
assert(MO.isDef() && "expect physreg def");
const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
unsigned SpecialAddressLatency = ST.getSpecialAddressLatency();
unsigned DataLatency = SU->Latency;
for (const uint16_t *Alias = TRI->getOverlaps(MO.getReg()); *Alias; ++Alias) {
if (!Uses.contains(*Alias))
continue;
std::vector<SUnit*> &UseList = Uses[*Alias];
for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
SUnit *UseSU = UseList[i];
if (UseSU == SU)
continue;
unsigned LDataLatency = DataLatency;
if (SpecialAddressLatency != 0 && !UnitLatencies &&
UseSU != &ExitSU) {
MachineInstr *UseMI = UseSU->getInstr();
const MCInstrDesc &UseMCID = UseMI->getDesc();
int RegUseIndex = UseMI->findRegisterUseOperandIdx(*Alias);
assert(RegUseIndex >= 0 && "UseMI doesn't use register!");
if (RegUseIndex >= 0 &&
(UseMI->mayLoad() || UseMI->mayStore()) &&
(unsigned)RegUseIndex < UseMCID.getNumOperands() &&
UseMCID.OpInfo[RegUseIndex].isLookupPtrRegClass())
LDataLatency += SpecialAddressLatency;
}
const SDep& dep = SDep(SU, SDep::Data, LDataLatency, *Alias);
if (!UnitLatencies) {
computeOperandLatency(SU, UseSU, const_cast<SDep &>(dep));
ST.adjustSchedDependency(SU, UseSU, const_cast<SDep &>(dep));
}
UseSU->addPred(dep);
}
}
}
void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
const MachineInstr *MI = SU->getInstr();
const MachineOperand &MO = MI->getOperand(OperIdx);
SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
for (const uint16_t *Alias = TRI->getOverlaps(MO.getReg()); *Alias; ++Alias) {
if (!Defs.contains(*Alias))
continue;
std::vector<SUnit *> &DefList = Defs[*Alias];
for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
SUnit *DefSU = DefList[i];
if (DefSU == &ExitSU)
continue;
if (DefSU != SU &&
(Kind != SDep::Output || !MO.isDead() ||
!DefSU->getInstr()->registerDefIsDead(*Alias))) {
if (Kind == SDep::Anti)
DefSU->addPred(SDep(SU, Kind, 0, *Alias));
else {
unsigned AOLat = TII->getOutputLatency(InstrItins, MI, OperIdx,
DefSU->getInstr());
DefSU->addPred(SDep(SU, Kind, AOLat, *Alias));
}
}
}
}
if (!MO.isDef()) {
Uses[MO.getReg()].push_back(SU);
}
else {
addPhysRegDataDeps(SU, MO);
std::vector<SUnit *> &DefList = Defs[MO.getReg()];
if (!UnitLatencies && DefList.empty()) {
LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(MO.getReg());
if (I != LoopRegs.Deps.end()) {
const MachineOperand *UseMO = I->second.first;
unsigned Count = I->second.second;
const MachineInstr *UseMI = UseMO->getParent();
unsigned UseMOIdx = UseMO - &UseMI->getOperand(0);
const MCInstrDesc &UseMCID = UseMI->getDesc();
const TargetSubtargetInfo &ST =
TM.getSubtarget<TargetSubtargetInfo>();
unsigned SpecialAddressLatency = ST.getSpecialAddressLatency();
if (UseMOIdx < UseMCID.getNumOperands()) {
if (UseMI->getParent() != MI->getParent()) {
unsigned Latency = SU->Latency;
if (UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass())
Latency += SpecialAddressLatency;
Latency -= std::min(Latency, Count);
ExitSU.addPred(SDep(SU, SDep::Order, Latency,
0, false,
false,
true));
} else if (SpecialAddressLatency > 0 &&
UseMCID.OpInfo[UseMOIdx].isLookupPtrRegClass()) {
SU->isScheduleHigh = true;
}
}
LoopRegs.Deps.erase(I);
}
}
if (Uses.contains(MO.getReg()))
Uses[MO.getReg()].clear();
if (!MO.isDead())
DefList.clear();
if (SU->isCall) {
while (!DefList.empty() && DefList.back()->isCall)
DefList.pop_back();
}
DefList.push_back(SU);
}
}
void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
const MachineInstr *MI = SU->getInstr();
unsigned Reg = MI->getOperand(OperIdx).getReg();
if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())
return;
VReg2SUnitMap::iterator DefI = findVRegDef(Reg);
if (DefI == VRegDefs.end())
VRegDefs.insert(VReg2SUnit(Reg, SU));
else {
SUnit *DefSU = DefI->SU;
if (DefSU != SU && DefSU != &ExitSU) {
unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx,
DefSU->getInstr());
DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg));
}
DefI->SU = SU;
}
}
void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
MachineInstr *MI = SU->getInstr();
unsigned Reg = MI->getOperand(OperIdx).getReg();
assert(LIS && "vreg dependencies requires LiveIntervals");
SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot();
LiveInterval *LI = &LIS->getInterval(Reg);
VNInfo *VNI = LI->getVNInfoBefore(UseIdx);
MachineInstr *Def = LIS->getInstructionFromIndex(VNI->def);
if (Def) {
SUnit *DefSU = getSUnit(Def);
if (DefSU) {
const SDep &dep = SDep(DefSU, SDep::Data, DefSU->Latency, Reg);
if (!UnitLatencies) {
computeOperandLatency(DefSU, SU, const_cast<SDep &>(dep));
const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep));
}
SU->addPred(dep);
}
}
VReg2SUnitMap::iterator DefI = findVRegDef(Reg);
if (DefI != VRegDefs.end() && DefI->SU != SU)
DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));
}
void ScheduleDAGInstrs::initSUnits() {
SUnits.reserve(BB->size());
for (MachineBasicBlock::iterator I = Begin; I != End; ++I) {
MachineInstr *MI = I;
if (MI->isDebugValue())
continue;
SUnit *SU = newSUnit(MI);
MISUnitMap[MI] = SU;
SU->isCall = MI->isCall();
SU->isCommutable = MI->isCommutable();
if (UnitLatencies)
SU->Latency = 1;
else
computeLatency(SU);
}
}
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA) {
initSUnits();
SUnit *BarrierChain = 0, *AliasChain = 0;
std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs;
std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses;
DbgValues.clear();
FirstDbgValue = NULL;
assert(Defs.empty() && Uses.empty() &&
"Only BuildGraph should update Defs/Uses");
Defs.setRegLimit(TRI->getNumRegs());
Uses.setRegLimit(TRI->getNumRegs());
assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs");
VRegDefs.setUniverse(MRI.getNumVirtRegs());
addSchedBarrierDeps();
MachineInstr *PrevMI = NULL;
for (MachineBasicBlock::iterator MII = End, MIE = Begin;
MII != MIE; --MII) {
MachineInstr *MI = prior(MII);
if (MI && PrevMI) {
DbgValues.push_back(std::make_pair(PrevMI, MI));
PrevMI = NULL;
}
if (MI->isDebugValue()) {
PrevMI = MI;
continue;
}
assert(!MI->isTerminator() && !MI->isLabel() &&
"Cannot schedule terminators or labels!");
SUnit *SU = MISUnitMap[MI];
assert(SU && "No SUnit mapped to this MI");
for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
const MachineOperand &MO = MI->getOperand(j);
if (!MO.isReg()) continue;
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
if (TRI->isPhysicalRegister(Reg))
addPhysRegDeps(SU, j);
else {
assert(!IsPostRA && "Virtual register encountered!");
if (MO.isDef())
addVRegDefDeps(SU, j);
else if (MO.readsReg()) addVRegUseDeps(SU, j);
}
}
#define STORE_LOAD_LATENCY 1
unsigned TrueMemOrderLatency = 0;
if (MI->isCall() || MI->hasUnmodeledSideEffects() ||
(MI->hasVolatileMemoryRef() &&
(!MI->mayLoad() || !MI->isInvariantLoad(AA)))) {
for (std::map<const Value *, SUnit *>::iterator I =
NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) {
I->second->addPred(SDep(SU, SDep::Order, 0));
}
for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) {
for (unsigned i = 0, e = I->second.size(); i != e; ++i)
I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency));
}
NonAliasMemDefs.clear();
NonAliasMemUses.clear();
if (BarrierChain)
BarrierChain->addPred(SDep(SU, SDep::Order, 0));
BarrierChain = SU;
new_alias_chain:
if (AliasChain)
AliasChain->addPred(SDep(SU, SDep::Order, 0));
AliasChain = SU;
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency));
for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(),
E = AliasMemDefs.end(); I != E; ++I) {
I->second->addPred(SDep(SU, SDep::Order, 0));
}
for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) {
for (unsigned i = 0, e = I->second.size(); i != e; ++i)
I->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency));
}
PendingLoads.clear();
AliasMemDefs.clear();
AliasMemUses.clear();
} else if (MI->mayStore()) {
bool MayAlias = true;
TrueMemOrderLatency = STORE_LOAD_LATENCY;
if (const Value *V = getUnderlyingObjectForInstr(MI, MFI, MayAlias)) {
std::map<const Value *, SUnit *>::iterator I =
((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V));
std::map<const Value *, SUnit *>::iterator IE =
((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end());
if (I != IE) {
I->second->addPred(SDep(SU, SDep::Order, 0, 0,
true));
I->second = SU;
} else {
if (MayAlias)
AliasMemDefs[V] = SU;
else
NonAliasMemDefs[V] = SU;
}
std::map<const Value *, std::vector<SUnit *> >::iterator J =
((MayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V));
std::map<const Value *, std::vector<SUnit *> >::iterator JE =
((MayAlias) ? AliasMemUses.end() : NonAliasMemUses.end());
if (J != JE) {
for (unsigned i = 0, e = J->second.size(); i != e; ++i)
J->second[i]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency,
0, true));
J->second.clear();
}
if (MayAlias) {
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
PendingLoads[k]->addPred(SDep(SU, SDep::Order, TrueMemOrderLatency));
if (AliasChain)
AliasChain->addPred(SDep(SU, SDep::Order, 0));
}
if (BarrierChain)
BarrierChain->addPred(SDep(SU, SDep::Order, 0));
} else {
goto new_alias_chain;
}
if (!ExitSU.isPred(SU))
ExitSU.addPred(SDep(SU, SDep::Order, 0,
0, false,
false,
true));
} else if (MI->mayLoad()) {
bool MayAlias = true;
TrueMemOrderLatency = 0;
if (MI->isInvariantLoad(AA)) {
} else {
if (const Value *V =
getUnderlyingObjectForInstr(MI, MFI, MayAlias)) {
std::map<const Value *, SUnit *>::iterator I =
((MayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V));
std::map<const Value *, SUnit *>::iterator IE =
((MayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end());
if (I != IE)
I->second->addPred(SDep(SU, SDep::Order, 0, 0,
true));
if (MayAlias)
AliasMemUses[V].push_back(SU);
else
NonAliasMemUses[V].push_back(SU);
} else {
for (std::map<const Value *, SUnit *>::iterator I =
AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I)
I->second->addPred(SDep(SU, SDep::Order, 0));
PendingLoads.push_back(SU);
MayAlias = true;
}
if (MayAlias && AliasChain)
AliasChain->addPred(SDep(SU, SDep::Order, 0));
if (BarrierChain)
BarrierChain->addPred(SDep(SU, SDep::Order, 0));
}
}
}
if (PrevMI)
FirstDbgValue = PrevMI;
Defs.clear();
Uses.clear();
VRegDefs.clear();
PendingLoads.clear();
MISUnitMap.clear();
}
void ScheduleDAGInstrs::computeLatency(SUnit *SU) {
if (!InstrItins || InstrItins->isEmpty()) {
SU->Latency = 1;
if (SU->getInstr()->mayLoad())
SU->Latency += 2;
} else {
SU->Latency = TII->getInstrLatency(InstrItins, SU->getInstr());
}
}
void ScheduleDAGInstrs::computeOperandLatency(SUnit *Def, SUnit *Use,
SDep& dep) const {
if (!InstrItins || InstrItins->isEmpty())
return;
if ((dep.getKind() != SDep::Data) || (dep.getReg() == 0))
return;
const unsigned Reg = dep.getReg();
MachineInstr *DefMI = Def->getInstr();
int DefIdx = DefMI->findRegisterDefOperandIdx(Reg);
if (DefIdx != -1) {
const MachineOperand &MO = DefMI->getOperand(DefIdx);
if (MO.isReg() && MO.isImplicit() &&
DefIdx >= (int)DefMI->getDesc().getNumOperands()) {
unsigned Op2 = DefMI->findRegisterDefOperandIdx(Reg, false, true, TRI);
if (DefMI->getOperand(Op2).isReg())
DefIdx = Op2;
}
MachineInstr *UseMI = Use->getInstr();
int Latency = -1;
if (UseMI) {
for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = UseMI->getOperand(i);
if (!MO.isReg() || !MO.isUse())
continue;
unsigned MOReg = MO.getReg();
if (MOReg != Reg)
continue;
int UseCycle = TII->getOperandLatency(InstrItins, DefMI, DefIdx,
UseMI, i);
Latency = std::max(Latency, UseCycle);
}
} else {
if (!InstrItins || InstrItins->isEmpty())
return;
unsigned DefClass = DefMI->getDesc().getSchedClass();
Latency = InstrItins->getOperandCycle(DefClass, DefIdx);
}
if (Latency >= 0)
dep.setLatency(Latency);
}
}
void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
SU->getInstr()->dump();
}
std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
std::string s;
raw_string_ostream oss(s);
if (SU == &EntrySU)
oss << "<entry>";
else if (SU == &ExitSU)
oss << "<exit>";
else
SU->getInstr()->print(oss);
return oss.str();
}
std::string ScheduleDAGInstrs::getDAGName() const {
return "dag." + BB->getFullName();
}