//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Evan Cheng and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#define DEBUG_TYPE "pre-RA-sched"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
-#include "llvm/CodeGen/SSARegMap.h"
-#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
bool isBottomUp;
/// AvailableQueue - The priority queue to use for the available SUnits.
- ///a
SchedulingPriorityQueue *AvailableQueue;
/// LiveRegs / LiveRegDefs - A set of physical registers and their definition
void ScheduleDAGRRList::Schedule() {
DOUT << "********** List Scheduling **********\n";
- LiveRegDefs.resize(MRI->getNumRegs(), NULL);
- LiveRegCycles.resize(MRI->getNumRegs(), 0);
+ LiveRegDefs.resize(TRI->getNumRegs(), NULL);
+ LiveRegCycles.resize(TRI->getNumRegs(), 0);
// Build scheduling units.
BuildSchedUnits();
if (!SU || !SU->Node) continue;
if (SU->isCommutable) {
unsigned Opc = SU->Node->getTargetOpcode();
- unsigned NumRes = TII->getNumDefs(Opc);
- unsigned NumOps = CountOperands(SU->Node);
+ const TargetInstrDesc &TID = TII->get(Opc);
+ unsigned NumRes = TID.getNumDefs();
+ unsigned NumOps = TID.getNumOperands() - NumRes;
for (unsigned j = 0; j != NumOps; ++j) {
- if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) == -1)
+ if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
continue;
SDNode *OpN = SU->Node->getOperand(j).Val;
- SUnit *OpSU = SUnitMap[OpN][SU->InstanceNo];
+ SUnit *OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo];
if (OpSU && OperandSeen.count(OpSU) == 1) {
// Ok, so SU is not the last use of OpSU, but SU is two-address so
// it will clobber OpSU. Try to commute SU if no other source operands
for (unsigned k = 0; k < NumOps; ++k) {
if (k != j) {
OpN = SU->Node->getOperand(k).Val;
- OpSU = SUnitMap[OpN][SU->InstanceNo];
+ OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo];
if (OpSU && OperandSeen.count(OpSU) == 1) {
DoCommute = false;
break;
return NULL;
SUnit *NewSU;
- for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
- if (N->getValueType(i) == MVT::Flag)
- return NULL;
bool TryUnfold = false;
+ for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
+ MVT::ValueType VT = N->getValueType(i);
+ if (VT == MVT::Flag)
+ return NULL;
+ else if (VT == MVT::Other)
+ TryUnfold = true;
+ }
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
const SDOperand &Op = N->getOperand(i);
MVT::ValueType VT = Op.Val->getValueType(Op.ResNo);
if (VT == MVT::Flag)
return NULL;
- else if (VT == MVT::Other)
- TryUnfold = true;
}
if (TryUnfold) {
SmallVector<SDNode*, 4> NewNodes;
- if (!MRI->unfoldMemoryOperand(DAG, N, NewNodes))
+ if (!TII->unfoldMemoryOperand(DAG, N, NewNodes))
return NULL;
DOUT << "Unfolding SU # " << SU->NodeNum << "\n";
N = NewNodes[1];
SDNode *LoadNode = NewNodes[0];
- std::vector<SDNode*> Deleted;
unsigned NumVals = N->getNumValues();
unsigned OldNumVals = SU->Node->getNumValues();
for (unsigned i = 0; i != NumVals; ++i)
- DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, i),
- SDOperand(N, i), Deleted);
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, i), SDOperand(N, i));
DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, OldNumVals-1),
- SDOperand(LoadNode, 1), Deleted);
+ SDOperand(LoadNode, 1));
- SUnit *LoadSU = NewSUnit(LoadNode);
SUnit *NewSU = NewSUnit(N);
- SUnitMap[LoadNode].push_back(LoadSU);
SUnitMap[N].push_back(NewSU);
- const TargetInstrDescriptor *TID = &TII->get(LoadNode->getTargetOpcode());
- for (unsigned i = 0; i != TID->numOperands; ++i) {
- if (TID->getOperandConstraint(i, TOI::TIED_TO) != -1) {
- LoadSU->isTwoAddress = true;
- break;
- }
- }
- if (TID->Flags & M_COMMUTABLE)
- LoadSU->isCommutable = true;
-
- TID = &TII->get(N->getTargetOpcode());
- for (unsigned i = 0; i != TID->numOperands; ++i) {
- if (TID->getOperandConstraint(i, TOI::TIED_TO) != -1) {
+ const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
+ for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
+ if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
NewSU->isTwoAddress = true;
break;
}
}
- if (TID->Flags & M_COMMUTABLE)
+ if (TID.isCommutable())
NewSU->isCommutable = true;
-
// FIXME: Calculate height / depth and propagate the changes?
- LoadSU->Depth = NewSU->Depth = SU->Depth;
- LoadSU->Height = NewSU->Height = SU->Height;
- ComputeLatency(LoadSU);
+ NewSU->Depth = SU->Depth;
+ NewSU->Height = SU->Height;
ComputeLatency(NewSU);
+ // LoadNode may already exist. This can happen when there is another
+ // load from the same location and producing the same type of value
+ // but it has different alignment or volatileness.
+ bool isNewLoad = true;
+ SUnit *LoadSU;
+ DenseMap<SDNode*, std::vector<SUnit*> >::iterator SMI =
+ SUnitMap.find(LoadNode);
+ if (SMI != SUnitMap.end()) {
+ LoadSU = SMI->second.front();
+ isNewLoad = false;
+ } else {
+ LoadSU = NewSUnit(LoadNode);
+ SUnitMap[LoadNode].push_back(LoadSU);
+
+ LoadSU->Depth = SU->Depth;
+ LoadSU->Height = SU->Height;
+ ComputeLatency(LoadSU);
+ }
+
SUnit *ChainPred = NULL;
SmallVector<SDep, 4> ChainSuccs;
SmallVector<SDep, 4> LoadPreds;
}
SU->removePred(ChainPred, true, false);
- LoadSU->addPred(ChainPred, true, false);
+ if (isNewLoad)
+ LoadSU->addPred(ChainPred, true, false);
for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
SDep *Pred = &LoadPreds[i];
SU->removePred(Pred->Dep, Pred->isCtrl, Pred->isSpecial);
- LoadSU->addPred(Pred->Dep, Pred->isCtrl, Pred->isSpecial,
- Pred->Reg, Pred->Cost);
+ if (isNewLoad)
+ LoadSU->addPred(Pred->Dep, Pred->isCtrl, Pred->isSpecial,
+ Pred->Reg, Pred->Cost);
}
for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
SDep *Pred = &NodePreds[i];
for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
SDep *Succ = &ChainSuccs[i];
Succ->Dep->removePred(SU, Succ->isCtrl, Succ->isSpecial);
- Succ->Dep->addPred(LoadSU, Succ->isCtrl, Succ->isSpecial,
- Succ->Reg, Succ->Cost);
+ if (isNewLoad)
+ Succ->Dep->addPred(LoadSU, Succ->isCtrl, Succ->isSpecial,
+ Succ->Reg, Succ->Cost);
}
- NewSU->addPred(LoadSU, false, false);
+ if (isNewLoad)
+ NewSU->addPred(LoadSU, false, false);
- AvailableQueue->addNode(LoadSU);
+ if (isNewLoad)
+ AvailableQueue->addNode(LoadSU);
AvailableQueue->addNode(NewSU);
++NumUnfolds;
if (NewSU->NumSuccsLeft == 0) {
NewSU->isAvailable = true;
return NewSU;
- } else
- SU = NewSU;
+ }
+ SU = NewSU;
}
DOUT << "Duplicating SU # " << SU->NodeNum << "\n";
/// FIXME: Move to SelectionDAG?
static MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg,
const TargetInstrInfo *TII) {
- const TargetInstrDescriptor &TID = TII->get(N->getTargetOpcode());
+ const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
- unsigned NumRes = TID.numDefs;
- for (const unsigned *ImpDef = TID.ImplicitDefs; *ImpDef; ++ImpDef) {
+ unsigned NumRes = TID.getNumDefs();
+ for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
if (Reg == *ImpDef)
break;
++NumRes;
if (RegAdded.insert(Reg))
LRegs.push_back(Reg);
}
- for (const unsigned *Alias = MRI->getAliasSet(Reg);
+ for (const unsigned *Alias = TRI->getAliasSet(Reg);
*Alias; ++Alias)
if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != I->Dep) {
if (RegAdded.insert(*Alias))
SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1];
if (!Node || !Node->isTargetOpcode())
continue;
- const TargetInstrDescriptor &TID = TII->get(Node->getTargetOpcode());
+ const TargetInstrDesc &TID = TII->get(Node->getTargetOpcode());
if (!TID.ImplicitDefs)
continue;
for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) {
if (RegAdded.insert(*Reg))
LRegs.push_back(*Reg);
}
- for (const unsigned *Alias = MRI->getAliasSet(*Reg);
+ for (const unsigned *Alias = TRI->getAliasSet(*Reg);
*Alias; ++Alias)
if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != SU) {
if (RegAdded.insert(*Alias))
// Issue expensive cross register class copies.
MVT::ValueType VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII);
const TargetRegisterClass *RC =
- MRI->getPhysicalRegisterRegClass(VT, Reg);
- const TargetRegisterClass *DestRC = MRI->getCrossCopyRegClass(RC);
+ TRI->getPhysicalRegisterRegClass(VT, Reg);
+ const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
if (!DestRC) {
assert(false && "Don't know how to copy this physical register!");
abort();
// All leaves to Available queue.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
- if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
+ if (SUnits[i].Preds.empty() && &SUnits[i] != Entry) {
AvailableQueue->push(&SUnits[i]);
SUnits[i].isAvailable = true;
}
std::vector<unsigned> SethiUllmanNumbers;
const TargetInstrInfo *TII;
+ const TargetRegisterInfo *TRI;
public:
- explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii)
- : TII(tii) {}
+ explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii,
+ const TargetRegisterInfo *tri)
+ : TII(tii), TRI(tri) {}
void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
std::vector<SUnit> &sunits) {
// CopyToReg should be close to its uses to facilitate coalescing and
// avoid spilling.
return 0;
+ else if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
+ Opc == TargetInstrInfo::INSERT_SUBREG)
+ // EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to
+ // facilitate coalescing.
+ return 0;
else if (SU->NumSuccs == 0)
// If SU does not have a use, i.e. it doesn't produce a value that would
// be consumed (e.g. store), then it terminates a chain of computation.
return MaxCycle;
}
+/// calcMaxScratches - Returns an cost estimate of the worse case requirement
+/// for scratch registers. Live-in operands and live-out results don't count
+/// since they are "fixed".
+static unsigned calcMaxScratches(const SUnit *SU) {
+ unsigned Scratches = 0;
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ if (I->isCtrl) continue; // ignore chain preds
+ if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyFromReg)
+ Scratches++;
+ }
+ for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+ I != E; ++I) {
+ if (I->isCtrl) continue; // ignore chain succs
+ if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyToReg)
+ Scratches += 10;
+ }
+ return Scratches;
+}
+
// Bottom up
bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
// There used to be a special tie breaker here that looked for
if (LDist < RDist)
return true;
else if (LDist == RDist) {
- if (left->Height > right->Height)
+ // Intuitively, it's good to push down instructions whose results are
+ // liveout so their long live ranges won't conflict with other values
+ // which are needed inside the BB. Further prioritize liveout instructions
+ // by the number of operands which are calculated within the BB.
+ unsigned LScratch = calcMaxScratches(left);
+ unsigned RScratch = calcMaxScratches(right);
+ if (LScratch > RScratch)
return true;
- else if (left->Height == right->Height)
- if (left->Depth < right->Depth)
+ else if (LScratch == RScratch)
+ if (left->Height > right->Height)
return true;
- else if (left->Depth == right->Depth)
- if (left->CycleBound > right->CycleBound)
+ else if (left->Height == right->Height)
+ if (left->Depth < right->Depth)
return true;
+ else if (left->Depth == right->Depth)
+ if (left->CycleBound > right->CycleBound)
+ return true;
}
}
return false;
bool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) {
if (SU->isTwoAddress) {
unsigned Opc = SU->Node->getTargetOpcode();
- unsigned NumRes = TII->getNumDefs(Opc);
- unsigned NumOps = ScheduleDAG::CountOperands(SU->Node);
+ const TargetInstrDesc &TID = TII->get(Opc);
+ unsigned NumRes = TID.getNumDefs();
+ unsigned NumOps = TID.getNumOperands() - NumRes;
for (unsigned i = 0; i != NumOps; ++i) {
- if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) != -1) {
+ if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
SDNode *DU = SU->Node->getOperand(i).Val;
- if (Op == (*SUnitMap)[DU][SU->InstanceNo])
+ if ((*SUnitMap).find(DU) != (*SUnitMap).end() &&
+ Op == (*SUnitMap)[DU][SU->InstanceNo])
return true;
}
}
return false;
}
+/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
+/// physical register def.
+static bool canClobberPhysRegDefs(SUnit *SuccSU, SUnit *SU,
+ const TargetInstrInfo *TII,
+ const TargetRegisterInfo *TRI) {
+ SDNode *N = SuccSU->Node;
+ unsigned NumDefs = TII->get(N->getTargetOpcode()).getNumDefs();
+ const unsigned *ImpDefs = TII->get(N->getTargetOpcode()).getImplicitDefs();
+ if (!ImpDefs)
+ return false;
+ const unsigned *SUImpDefs =
+ TII->get(SU->Node->getTargetOpcode()).getImplicitDefs();
+ if (!SUImpDefs)
+ return false;
+ for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
+ MVT::ValueType VT = N->getValueType(i);
+ if (VT == MVT::Flag || VT == MVT::Other)
+ continue;
+ unsigned Reg = ImpDefs[i - NumDefs];
+ for (;*SUImpDefs; ++SUImpDefs) {
+ unsigned SUReg = *SUImpDefs;
+ if (TRI->regsOverlap(Reg, SUReg))
+ return true;
+ }
+ }
+ return false;
+}
+
/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
/// it as a def&use operand. Add a pseudo control edge from it to the other
/// node (if it won't create a cycle) so the two-address one will be scheduled
continue;
unsigned Opc = Node->getTargetOpcode();
- unsigned NumRes = TII->getNumDefs(Opc);
- unsigned NumOps = ScheduleDAG::CountOperands(Node);
+ const TargetInstrDesc &TID = TII->get(Opc);
+ unsigned NumRes = TID.getNumDefs();
+ unsigned NumOps = TID.getNumOperands() - NumRes;
for (unsigned j = 0; j != NumOps; ++j) {
- if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) != -1) {
+ if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) != -1) {
SDNode *DU = SU->Node->getOperand(j).Val;
+ if ((*SUnitMap).find(DU) == (*SUnitMap).end())
+ continue;
SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo];
if (!DUSU) continue;
for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
I != E; ++I) {
if (I->isCtrl) continue;
SUnit *SuccSU = I->Dep;
- // Don't constraint nodes with implicit defs. It can create cycles
- // plus it may increase register pressures.
- if (SuccSU == SU || SuccSU->hasPhysRegDefs)
+ if (SuccSU == SU)
+ continue;
+ // Be conservative. Ignore if nodes aren't at roughly the same
+ // depth and height.
+ if (SuccSU->Height < SU->Height && (SU->Height - SuccSU->Height) > 1)
continue;
- // Be conservative. Ignore if nodes aren't at the same depth.
- if (SuccSU->Depth != SU->Depth)
+ if (!SuccSU->Node || !SuccSU->Node->isTargetOpcode())
+ continue;
+ // Don't constrain nodes with physical register defs if the
+ // predecessor can clobber them.
+ if (SuccSU->hasPhysRegDefs) {
+ if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
+ continue;
+ }
+ // Don't constraint extract_subreg / insert_subreg these may be
+ // coalesced away. We don't them close to their uses.
+ unsigned SuccOpc = SuccSU->Node->getTargetOpcode();
+ if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
+ SuccOpc == TargetInstrInfo::INSERT_SUBREG)
continue;
if ((!canClobber(SuccSU, DUSU) ||
(hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
SelectionDAG *DAG,
MachineBasicBlock *BB) {
const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo();
+ const TargetRegisterInfo *TRI = DAG->getTarget().getRegisterInfo();
return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true,
- new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII));
+ new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII, TRI));
}
llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
projects / oota-llvm.git / blobdiff