ScheduleDAGInstrs.cpp [plain text]
#define DEBUG_TYPE "sched-instrs"
#include "ScheduleDAGInstrs.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtarget.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)
: ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) {}
void ScheduleDAGInstrs::Run(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
unsigned endcount) {
BB = bb;
Begin = begin;
InsertPosIndex = endcount;
ScheduleDAG::Run(bb, end);
}
static unsigned getOpcode(const Value *V) {
if (const Instruction *I = dyn_cast<Instruction>(V))
return I->getOpcode();
if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
return CE->getOpcode();
return Instruction::UserOp1;
}
static const Value *getUnderlyingObjectFromInt(const Value *V) {
do {
if (const User *U = dyn_cast<User>(V)) {
if (getOpcode(U) == Instruction::PtrToInt)
return U->getOperand(0);
if (getOpcode(U) != Instruction::Add ||
(!isa<ConstantInt>(U->getOperand(1)) &&
getOpcode(U->getOperand(1)) != Instruction::Mul))
return V;
V = U->getOperand(0);
} else {
return V;
}
assert(isa<IntegerType>(V->getType()) && "Unexpected operand type!");
} while (1);
}
static const Value *getUnderlyingObject(const Value *V) {
do {
V = V->getUnderlyingObject();
if (getOpcode(V) != Instruction::IntToPtr)
break;
const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
if (!isa<PointerType>(O->getType()))
break;
V = O;
} while (1);
return V;
}
static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI) {
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 (!isa<PseudoSourceValue>(V) && !isIdentifiedObject(V))
return 0;
return V;
}
void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) {
if (MachineLoop *ML = MLI.getLoopFor(BB))
if (BB == ML->getLoopLatch()) {
MachineBasicBlock *Header = ML->getHeader();
for (MachineBasicBlock::livein_iterator I = Header->livein_begin(),
E = Header->livein_end(); I != E; ++I)
LoopLiveInRegs.insert(*I);
LoopRegs.VisitLoop(ML);
}
}
void ScheduleDAGInstrs::BuildSchedGraph() {
SUnits.reserve(BB->size());
SUnit *Chain = 0;
MachineMemOperand *ChainMMO = 0;
std::map<const Value *, SUnit *> MemDefs;
std::map<const Value *, std::vector<SUnit *> > MemUses;
bool UnitLatencies = ForceUnitLatencies();
unsigned SpecialAddressLatency =
TM.getSubtarget<TargetSubtarget>().getSpecialAddressLatency();
for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin;
MII != MIE; --MII) {
MachineInstr *MI = prior(MII);
const TargetInstrDesc &TID = MI->getDesc();
assert(!TID.isTerminator() && !MI->isLabel() &&
"Cannot schedule terminators or labels!");
SUnit *SU = NewSUnit(MI);
if (UnitLatencies)
SU->Latency = 1;
else
ComputeLatency(SU);
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;
assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
std::vector<SUnit *> &UseList = Uses[Reg];
std::vector<SUnit *> &DefList = Defs[Reg];
SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
SUnit *DefSU = DefList[i];
if (DefSU != SU &&
(Kind != SDep::Output || !MO.isDead() ||
!DefSU->getInstr()->registerDefIsDead(Reg)))
DefSU->addPred(SDep(SU, Kind, 1, Reg));
}
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
std::vector<SUnit *> &DefList = Defs[*Alias];
for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
SUnit *DefSU = DefList[i];
if (DefSU != SU &&
(Kind != SDep::Output || !MO.isDead() ||
!DefSU->getInstr()->registerDefIsDead(Reg)))
DefSU->addPred(SDep(SU, Kind, 1, *Alias));
}
}
if (MO.isDef()) {
unsigned DataLatency = SU->Latency;
for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
SUnit *UseSU = UseList[i];
if (UseSU != SU) {
unsigned LDataLatency = DataLatency;
if (SpecialAddressLatency != 0 && !UnitLatencies) {
MachineInstr *UseMI = UseSU->getInstr();
const TargetInstrDesc &UseTID = UseMI->getDesc();
int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg);
assert(RegUseIndex >= 0 && "UseMI doesn's use register!");
if ((UseTID.mayLoad() || UseTID.mayStore()) &&
(unsigned)RegUseIndex < UseTID.getNumOperands() &&
UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass())
LDataLatency += SpecialAddressLatency;
}
UseSU->addPred(SDep(SU, SDep::Data, LDataLatency, Reg));
}
}
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
std::vector<SUnit *> &UseList = Uses[*Alias];
for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
SUnit *UseSU = UseList[i];
if (UseSU != SU)
UseSU->addPred(SDep(SU, SDep::Data, DataLatency, *Alias));
}
}
if (!UnitLatencies && DefList.empty()) {
LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg);
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 TargetInstrDesc &UseTID = UseMI->getDesc();
if (UseMOIdx < UseTID.getNumOperands()) {
if (UseMI->getParent() != MI->getParent()) {
unsigned Latency = SU->Latency;
if (UseTID.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 &&
UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) {
SU->isScheduleHigh = true;
}
}
LoopRegs.Deps.erase(I);
}
}
UseList.clear();
if (!MO.isDead())
DefList.clear();
DefList.push_back(SU);
} else {
UseList.push_back(SU);
}
}
if (TID.isCall() || TID.hasUnmodeledSideEffects()) {
new_chain:
if (Chain)
Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
Chain = SU;
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
PendingLoads.clear();
for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
E = MemDefs.end(); I != E; ++I) {
I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
I->second = SU;
}
for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
MemUses.begin(), E = MemUses.end(); I != E; ++I) {
for (unsigned i = 0, e = I->second.size(); i != e; ++i)
I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency));
I->second.clear();
}
MachineInstr *ChainMI = Chain->getInstr();
const TargetInstrDesc &ChainTID = ChainMI->getDesc();
if (!ChainTID.isCall() &&
!ChainTID.hasUnmodeledSideEffects() &&
ChainMI->hasOneMemOperand() &&
!ChainMI->memoperands_begin()->isVolatile() &&
ChainMI->memoperands_begin()->getValue())
ChainMMO = &*ChainMI->memoperands_begin();
else
ChainMMO = 0;
} else if (TID.mayStore()) {
if (const Value *V = getUnderlyingObjectForInstr(MI)) {
std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
if (I != MemDefs.end()) {
I->second->addPred(SDep(SU, SDep::Order, SU->Latency, 0,
true));
I->second = SU;
} else {
MemDefs[V] = SU;
}
std::map<const Value *, std::vector<SUnit *> >::iterator J =
MemUses.find(V);
if (J != MemUses.end()) {
for (unsigned i = 0, e = J->second.size(); i != e; ++i)
J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, 0,
true));
J->second.clear();
}
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
if (Chain)
Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
} else
goto new_chain;
} else if (TID.mayLoad()) {
if (TII->isInvariantLoad(MI)) {
} else if (const Value *V = getUnderlyingObjectForInstr(MI)) {
std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
if (I != MemDefs.end())
I->second->addPred(SDep(SU, SDep::Order, SU->Latency, 0,
true));
MemUses[V].push_back(SU);
if (Chain && (!ChainMMO ||
(ChainMMO->isStore() || ChainMMO->isVolatile())))
Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
} else if (MI->hasVolatileMemoryRef()) {
goto new_chain;
} else {
if (Chain)
Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
E = MemDefs.end(); I != E; ++I)
I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
PendingLoads.push_back(SU);
}
}
}
for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) {
Defs[i].clear();
Uses[i].clear();
}
PendingLoads.clear();
}
void ScheduleDAGInstrs::FinishBlock() {
}
void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
SU->Latency =
InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
if (InstrItins.isEmpty())
if (SU->getInstr()->getDesc().mayLoad())
SU->Latency += 2;
}
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();
}
MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
while (Begin != InsertPos) {
MachineBasicBlock::iterator I = Begin;
++Begin;
BB->remove(I);
}
for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
SUnit *SU = Sequence[i];
if (!SU) {
EmitNoop();
continue;
}
BB->insert(InsertPos, SU->getInstr());
}
if (!Sequence.empty())
Begin = Sequence[0]->getInstr();
return BB;
}