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/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAGILP.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/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallPtrSet.h"
using namespace llvm;
static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
cl::ZeroOrMore, cl::init(false),
cl::desc("Enable use of AA during MI GAD construction"));
ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
const MachineLoopInfo &mli,
const MachineDominatorTree &mdt,
bool IsPostRAFlag,
LiveIntervals *lis)
: ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), LIS(lis),
IsPostRA(IsPostRAFlag), CanHandleTerminators(false), FirstDbgValue(0) {
assert((IsPostRA || LIS) && "PreRA scheduling requires LiveIntervals");
DbgValues.clear();
assert(!(IsPostRA && MRI.getNumVirtRegs()) &&
"Virtual registers must be removed prior to PostRA scheduling");
const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
SchedModel.init(*ST.getSchedModel(), &ST, TII);
}
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) {
BB = bb;
}
void ScheduleDAGInstrs::finishBlock() {
BB = 0;
}
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) {
assert(bb == BB && "startBlock should set BB");
RegionBegin = begin;
RegionEnd = end;
EndIndex = endcount;
MISUnitMap.clear();
ScheduleDAG::clearDAG();
}
void ScheduleDAGInstrs::exitRegion() {
}
void ScheduleDAGInstrs::addSchedBarrierDeps() {
MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : 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(PhysRegSUOper(&ExitSU, -1));
else {
assert(!IsPostRA && "Virtual register encountered after regalloc.");
addVRegUseDeps(&ExitSU, i);
}
}
} else {
assert(Uses.empty() && "Uses in set before adding deps?");
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 (!Uses.contains(Reg))
Uses[Reg].push_back(PhysRegSUOper(&ExitSU, -1));
}
}
}
void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) {
const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx);
assert(MO.isDef() && "expect physreg def");
const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
Alias.isValid(); ++Alias) {
if (!Uses.contains(*Alias))
continue;
std::vector<PhysRegSUOper> &UseList = Uses[*Alias];
for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
SUnit *UseSU = UseList[i].SU;
if (UseSU == SU)
continue;
SDep dep(SU, SDep::Data, 1, *Alias);
int UseOp = UseList[i].OpIdx;
MachineInstr *RegUse = UseOp < 0 ? 0 : UseSU->getInstr();
dep.setLatency(
SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
RegUse, UseOp, false));
dep.setMinLatency(
SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
RegUse, UseOp, true));
ST.adjustSchedDependency(SU, UseSU, 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 (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
Alias.isValid(); ++Alias) {
if (!Defs.contains(*Alias))
continue;
std::vector<PhysRegSUOper> &DefList = Defs[*Alias];
for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
SUnit *DefSU = DefList[i].SU;
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 =
SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr());
DefSU->addPred(SDep(SU, Kind, AOLat, *Alias));
}
}
}
}
if (!MO.isDef()) {
Uses[MO.getReg()].push_back(PhysRegSUOper(SU, OperIdx));
}
else {
addPhysRegDataDeps(SU, OperIdx);
std::vector<PhysRegSUOper> &DefList = Defs[MO.getReg()];
if (Uses.contains(MO.getReg()))
Uses[MO.getReg()].clear();
if (!MO.isDead())
DefList.clear();
if (SU->isCall) {
while (!DefList.empty() && DefList.back().SU->isCall)
DefList.pop_back();
}
DefList.push_back(PhysRegSUOper(SU, OperIdx));
}
}
void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
const MachineInstr *MI = SU->getInstr();
unsigned Reg = MI->getOperand(OperIdx).getReg();
if (MRI.hasOneDef(Reg))
return;
VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
if (DefI == VRegDefs.end())
VRegDefs.insert(VReg2SUnit(Reg, SU));
else {
SUnit *DefSU = DefI->SU;
if (DefSU != SU && DefSU != &ExitSU) {
unsigned OutLatency =
SchedModel.computeOutputLatency(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");
LiveRangeQuery LRQ(LIS->getInterval(Reg), LIS->getInstructionIndex(MI));
VNInfo *VNI = LRQ.valueIn();
assert(VNI && "No value to read by operand");
MachineInstr *Def = LIS->getInstructionFromIndex(VNI->def);
if (Def) {
SUnit *DefSU = getSUnit(Def);
if (DefSU) {
SDep dep(DefSU, SDep::Data, 1, Reg);
int DefOp = Def->findRegisterDefOperandIdx(Reg);
dep.setLatency(
SchedModel.computeOperandLatency(Def, DefOp, MI, OperIdx, false));
dep.setMinLatency(
SchedModel.computeOperandLatency(Def, DefOp, MI, OperIdx, true));
const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep));
SU->addPred(dep);
}
}
VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
if (DefI != VRegDefs.end() && DefI->SU != SU)
DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));
}
static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) {
if (MI->isCall() || MI->hasUnmodeledSideEffects() ||
(MI->hasOrderedMemoryRef() &&
(!MI->mayLoad() || !MI->isInvariantLoad(AA))))
return true;
return false;
}
static inline bool isUnsafeMemoryObject(MachineInstr *MI,
const MachineFrameInfo *MFI) {
if (!MI || MI->memoperands_empty())
return true;
if ((*MI->memoperands_begin())->isVolatile() ||
MI->hasUnmodeledSideEffects())
return true;
const Value *V = (*MI->memoperands_begin())->getValue();
if (!V)
return true;
V = getUnderlyingObject(V);
if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
if (PSV->isAliased(MFI))
return true;
}
if (!isIdentifiedObject(V))
return true;
return false;
}
static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
MachineInstr *MIa,
MachineInstr *MIb) {
if (MIa == MIb)
return false;
if (isUnsafeMemoryObject(MIa, MFI) || isUnsafeMemoryObject(MIb, MFI))
return true;
if (!MIa->mayStore() && !MIb->mayStore())
return false;
if (!AA)
return true;
MachineMemOperand *MMOa = *MIa->memoperands_begin();
MachineMemOperand *MMOb = *MIb->memoperands_begin();
if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand())
llvm_unreachable("Multiple memory operands.");
assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset");
assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset");
int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset;
int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset;
AliasAnalysis::AliasResult AAResult = AA->alias(
AliasAnalysis::Location(MMOa->getValue(), Overlapa,
MMOa->getTBAAInfo()),
AliasAnalysis::Location(MMOb->getValue(), Overlapb,
MMOb->getTBAAInfo()));
return (AAResult != AliasAnalysis::NoAlias);
}
static unsigned
iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI,
SUnit *SUa, SUnit *SUb, SUnit *ExitSU, unsigned *Depth,
SmallPtrSet<const SUnit*, 16> &Visited) {
if (!SUa || !SUb || SUb == ExitSU)
return *Depth;
if (!Visited.insert(SUb))
return *Depth;
if (SUa->isSucc(SUb) ||
isGlobalMemoryObject(AA, SUb->getInstr()))
return *Depth;
if (*Depth > 200 ||
MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr())) {
SUb->addPred(SDep(SUa, SDep::Order, 0, 0,
true));
return *Depth;
}
(*Depth)++;
for (SUnit::const_succ_iterator I = SUb->Succs.begin(), E = SUb->Succs.end();
I != E; ++I)
if (I->isCtrl())
iterateChainSucc (AA, MFI, SUa, I->getSUnit(), ExitSU, Depth, Visited);
return *Depth;
}
static void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI,
SUnit *SU, SUnit *ExitSU, std::set<SUnit *> &CheckList,
unsigned LatencyToLoad) {
if (!SU)
return;
SmallPtrSet<const SUnit*, 16> Visited;
unsigned Depth = 0;
for (std::set<SUnit *>::iterator I = CheckList.begin(), IE = CheckList.end();
I != IE; ++I) {
if (SU == *I)
continue;
if (MIsNeedChainEdge(AA, MFI, SU->getInstr(), (*I)->getInstr())) {
unsigned Latency = ((*I)->getInstr()->mayLoad()) ? LatencyToLoad : 0;
(*I)->addPred(SDep(SU, SDep::Order, Latency, 0,
true));
}
for (SUnit::const_succ_iterator J = (*I)->Succs.begin(),
JE = (*I)->Succs.end(); J != JE; ++J)
if (J->isCtrl())
iterateChainSucc (AA, MFI, SU, J->getSUnit(),
ExitSU, &Depth, Visited);
}
}
static inline
void addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI,
SUnit *SUa, SUnit *SUb,
std::set<SUnit *> &RejectList,
unsigned TrueMemOrderLatency = 0,
bool isNormalMemory = false) {
if (!EnableAASchedMI ||
MIsNeedChainEdge(AA, MFI, SUa->getInstr(), SUb->getInstr()))
SUb->addPred(SDep(SUa, SDep::Order, TrueMemOrderLatency, 0,
isNormalMemory));
else {
RejectList.insert(SUb);
DEBUG(dbgs() << "\tReject chain dep between SU("
<< SUa->NodeNum << ") and SU("
<< SUb->NodeNum << ")\n");
}
}
void ScheduleDAGInstrs::initSUnits() {
SUnits.reserve(BB->size());
for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) {
MachineInstr *MI = I;
if (MI->isDebugValue())
continue;
SUnit *SU = newSUnit(MI);
MISUnitMap[MI] = SU;
SU->isCall = MI->isCall();
SU->isCommutable = MI->isCommutable();
SU->Latency = SchedModel.computeInstrLatency(SU->getInstr());
}
}
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
RegPressureTracker *RPTracker) {
initSUnits();
SUnit *BarrierChain = 0, *AliasChain = 0;
std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs;
std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses;
std::set<SUnit*> RejectMemNodes;
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 = RegionEnd, MIE = RegionBegin;
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;
}
if (RPTracker) {
RPTracker->recede();
assert(RPTracker->getPos() == prior(MII) && "RPTracker can't find MI");
}
assert((!MI->isTerminator() || CanHandleTerminators) && !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);
}
}
unsigned TrueMemOrderLatency = MI->mayStore() ? 1 : 0;
if (isGlobalMemoryObject(AA, MI)) {
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));
}
if (BarrierChain)
BarrierChain->addPred(SDep(SU, SDep::Order, 0));
BarrierChain = SU;
adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes,
TrueMemOrderLatency);
RejectMemNodes.clear();
NonAliasMemDefs.clear();
NonAliasMemUses.clear();
new_alias_chain:
if (AliasChain) {
unsigned ChainLatency = 0;
if (AliasChain->getInstr()->mayLoad())
ChainLatency = TrueMemOrderLatency;
addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes,
ChainLatency);
}
AliasChain = SU;
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes,
TrueMemOrderLatency);
for (std::map<const Value *, SUnit *>::iterator I = AliasMemDefs.begin(),
E = AliasMemDefs.end(); I != E; ++I)
addChainDependency(AA, MFI, SU, I->second, RejectMemNodes);
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)
addChainDependency(AA, MFI, SU, I->second[i], RejectMemNodes,
TrueMemOrderLatency);
}
adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes,
TrueMemOrderLatency);
PendingLoads.clear();
AliasMemDefs.clear();
AliasMemUses.clear();
} else if (MI->mayStore()) {
bool MayAlias = true;
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) {
addChainDependency(AA, MFI, SU, I->second, RejectMemNodes,
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)
addChainDependency(AA, MFI, SU, J->second[i], RejectMemNodes,
TrueMemOrderLatency, true);
J->second.clear();
}
if (MayAlias) {
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
addChainDependency(AA, MFI, SU, PendingLoads[k], RejectMemNodes,
TrueMemOrderLatency);
if (AliasChain)
addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes);
adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes,
TrueMemOrderLatency);
}
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;
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)
addChainDependency(AA, MFI, SU, I->second, RejectMemNodes, 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)
addChainDependency(AA, MFI, SU, I->second, RejectMemNodes);
PendingLoads.push_back(SU);
MayAlias = true;
}
if (MayAlias)
adjustChainDeps(AA, MFI, SU, &ExitSU, RejectMemNodes, 0);
if (MayAlias && AliasChain)
addChainDependency(AA, MFI, SU, AliasChain, RejectMemNodes);
if (BarrierChain)
BarrierChain->addPred(SDep(SU, SDep::Order, 0));
}
}
}
if (PrevMI)
FirstDbgValue = PrevMI;
Defs.clear();
Uses.clear();
VRegDefs.clear();
PendingLoads.clear();
}
void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
SU->getInstr()->dump();
#endif
}
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();
}
namespace {
class SchedDAGReverseDFS {
std::vector<std::pair<const SUnit*, SUnit::const_pred_iterator> > DFSStack;
public:
bool isComplete() const { return DFSStack.empty(); }
void follow(const SUnit *SU) {
DFSStack.push_back(std::make_pair(SU, SU->Preds.begin()));
}
void advance() { ++DFSStack.back().second; }
void backtrack() { DFSStack.pop_back(); }
const SUnit *getCurr() const { return DFSStack.back().first; }
SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
SUnit::const_pred_iterator getPredEnd() const {
return getCurr()->Preds.end();
}
};
}
void ScheduleDAGILP::resize(unsigned NumSUnits) {
ILPValues.resize(NumSUnits);
}
ILPValue ScheduleDAGILP::getILP(const SUnit *SU) {
return ILPValues[SU->NodeNum];
}
static ILPValue initILP(const SUnit *SU) {
unsigned Cnt = SU->getInstr()->isTransient() ? 0 : 1;
return ILPValue(Cnt, 1 + SU->getDepth());
}
void ScheduleDAGILP::computeILP(const SUnit *Root) {
if (!IsBottomUp)
llvm_unreachable("Top-down ILP metric is unimplemnted");
SchedDAGReverseDFS DFS;
ILPValues[Root->NodeNum] = initILP(Root);
DFS.follow(Root);
for (;;) {
while (DFS.getPred() != DFS.getPredEnd()) {
const SUnit *PredSU = DFS.getPred()->getSUnit();
DFS.advance();
if (ILPValues[PredSU->NodeNum].isValid())
continue;
ILPValues[PredSU->NodeNum] = initILP(PredSU);
DFS.follow(PredSU);
}
unsigned PredCount = ILPValues[DFS.getCurr()->NodeNum].InstrCount;
DFS.backtrack();
if (DFS.isComplete())
break;
ILPValues[DFS.getCurr()->NodeNum].InstrCount += PredCount;
}
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void ILPValue::print(raw_ostream &OS) const {
if (!isValid())
OS << "BADILP";
OS << InstrCount << " / " << Cycles << " = "
<< format("%g", ((double)InstrCount / Cycles));
}
void ILPValue::dump() const {
dbgs() << *this << '\n';
}
namespace llvm {
raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) {
Val.print(OS);
return OS;
}
} #endif // !NDEBUG || LLVM_ENABLE_DUMP