Added major new capabilities to scheduler (only BURR for now) to support physical register dependency. The BURR scheduler can now backtrace and duplicate instructions in order to avoid "expensive / impossible to copy" values (e.g. status flag EFLAGS for x86) from being clobbered.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42284 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 1346595..b775122 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -27,6 +27,65 @@
#include "llvm/Support/MathExtras.h"
using namespace llvm;
+
+/// getPhysicalRegisterRegClass - Returns the Register Class of a physical
+/// register.
+static const TargetRegisterClass *getPhysicalRegisterRegClass(
+ const MRegisterInfo *MRI,
+ MVT::ValueType VT,
+ unsigned reg) {
+ assert(MRegisterInfo::isPhysicalRegister(reg) &&
+ "reg must be a physical register");
+ // Pick the register class of the right type that contains this physreg.
+ for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
+ E = MRI->regclass_end(); I != E; ++I)
+ if ((*I)->hasType(VT) && (*I)->contains(reg))
+ return *I;
+ assert(false && "Couldn't find the register class");
+ return 0;
+}
+
+
+/// CheckForPhysRegDependency - Check if the dependency between def and use of
+/// a specified operand is a physical register dependency. If so, returns the
+/// register and the cost of copying the register.
+static void CheckForPhysRegDependency(SDNode *Def, SDNode *Use, unsigned Op,
+ const MRegisterInfo *MRI,
+ const TargetInstrInfo *TII,
+ unsigned &PhysReg, int &Cost) {
+ if (Op != 2 || Use->getOpcode() != ISD::CopyToReg)
+ return;
+
+ unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
+ if (MRegisterInfo::isVirtualRegister(Reg))
+ return;
+
+ unsigned ResNo = Use->getOperand(2).ResNo;
+ if (Def->isTargetOpcode()) {
+ const TargetInstrDescriptor &II = TII->get(Def->getTargetOpcode());
+ if (ResNo >= II.numDefs &&
+ II.ImplicitDefs[ResNo - II.numDefs] == Reg) {
+ PhysReg = Reg;
+ const TargetRegisterClass *RC =
+ getPhysicalRegisterRegClass(MRI, Def->getValueType(ResNo), Reg);
+ Cost = RC->getCopyCost();
+ }
+ }
+}
+
+SUnit *ScheduleDAG::Clone(SUnit *Old) {
+ SUnit *SU = NewSUnit(Old->Node);
+ for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i)
+ SU->FlaggedNodes.push_back(SU->FlaggedNodes[i]);
+ SU->InstanceNo = SUnitMap[Old->Node].size();
+ SU->Latency = Old->Latency;
+ SU->isTwoAddress = Old->isTwoAddress;
+ SU->isCommutable = Old->isCommutable;
+ SU->hasImplicitDefs = Old->hasImplicitDefs;
+ SUnitMap[Old->Node].push_back(SU);
+ return SU;
+}
+
/// BuildSchedUnits - Build SUnits from the selection dag that we are input.
/// This SUnit graph is similar to the SelectionDAG, but represents flagged
/// together nodes with a single SUnit.
@@ -44,7 +103,7 @@
continue;
// If this node has already been processed, stop now.
- if (SUnitMap[NI]) continue;
+ if (SUnitMap[NI].size()) continue;
SUnit *NodeSUnit = NewSUnit(NI);
@@ -59,7 +118,7 @@
do {
N = N->getOperand(N->getNumOperands()-1).Val;
NodeSUnit->FlaggedNodes.push_back(N);
- SUnitMap[N] = NodeSUnit;
+ SUnitMap[N].push_back(NodeSUnit);
} while (N->getNumOperands() &&
N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
std::reverse(NodeSUnit->FlaggedNodes.begin(),
@@ -79,7 +138,7 @@
if (FlagVal.isOperand(*UI)) {
HasFlagUse = true;
NodeSUnit->FlaggedNodes.push_back(N);
- SUnitMap[N] = NodeSUnit;
+ SUnitMap[N].push_back(NodeSUnit);
N = *UI;
break;
}
@@ -89,7 +148,7 @@
// Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
// Update the SUnit
NodeSUnit->Node = N;
- SUnitMap[N] = NodeSUnit;
+ SUnitMap[N].push_back(NodeSUnit);
// Compute the latency for the node. We use the sum of the latencies for
// all nodes flagged together into this SUnit.
@@ -125,13 +184,16 @@
if (MainNode->isTargetOpcode()) {
unsigned Opc = MainNode->getTargetOpcode();
- for (unsigned i = 0, ee = TII->getNumOperands(Opc); i != ee; ++i) {
- if (TII->getOperandConstraint(Opc, i, TOI::TIED_TO) != -1) {
+ const TargetInstrDescriptor &TID = TII->get(Opc);
+ if (TID.ImplicitDefs)
+ SU->hasImplicitDefs = true;
+ for (unsigned i = 0; i != TID.numOperands; ++i) {
+ if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
SU->isTwoAddress = true;
break;
}
}
- if (TII->isCommutableInstr(Opc))
+ if (TID.Flags & M_COMMUTABLE)
SU->isCommutable = true;
}
@@ -141,34 +203,25 @@
for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
SDNode *N = SU->FlaggedNodes[n];
+ if (N->isTargetOpcode() && TII->getImplicitDefs(N->getTargetOpcode()))
+ SU->hasImplicitDefs = true;
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
SDNode *OpN = N->getOperand(i).Val;
if (isPassiveNode(OpN)) continue; // Not scheduled.
- SUnit *OpSU = SUnitMap[OpN];
+ SUnit *OpSU = SUnitMap[OpN].front();
assert(OpSU && "Node has no SUnit!");
if (OpSU == SU) continue; // In the same group.
MVT::ValueType OpVT = N->getOperand(i).getValueType();
assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
bool isChain = OpVT == MVT::Other;
-
- if (SU->addPred(OpSU, isChain)) {
- if (!isChain) {
- SU->NumPreds++;
- SU->NumPredsLeft++;
- } else {
- SU->NumChainPredsLeft++;
- }
- }
- if (OpSU->addSucc(SU, isChain)) {
- if (!isChain) {
- OpSU->NumSuccs++;
- OpSU->NumSuccsLeft++;
- } else {
- OpSU->NumChainSuccsLeft++;
- }
- }
+
+ unsigned PhysReg = 0;
+ int Cost = 1;
+ // Determine if this is a physical register dependency.
+ CheckForPhysRegDependency(OpN, N, i, MRI, TII, PhysReg, Cost);
+ SU->addPred(OpSU, isChain, false, PhysReg, Cost);
}
}
@@ -200,7 +253,7 @@
void ScheduleDAG::CalculateHeights() {
std::vector<std::pair<SUnit*, unsigned> > WorkList;
- SUnit *Root = SUnitMap[DAG.getRoot().Val];
+ SUnit *Root = SUnitMap[DAG.getRoot().Val].front();
WorkList.push_back(std::make_pair(Root, 0U));
while (!WorkList.empty()) {
@@ -254,27 +307,14 @@
? TII->getPointerRegClass() : MRI->getRegClass(toi.RegClass);
}
-// Returns the Register Class of a physical register
-static const TargetRegisterClass *getPhysicalRegisterRegClass(
- const MRegisterInfo *MRI,
- MVT::ValueType VT,
- unsigned reg) {
- assert(MRegisterInfo::isPhysicalRegister(reg) &&
- "reg must be a physical register");
- // Pick the register class of the right type that contains this physreg.
- for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
- E = MRI->regclass_end(); I != E; ++I)
- if ((*I)->hasType(VT) && (*I)->contains(reg))
- return *I;
- assert(false && "Couldn't find the register class");
- return 0;
-}
-
-void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned SrcReg,
+void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
+ unsigned InstanceNo, unsigned SrcReg,
DenseMap<SDOperand, unsigned> &VRBaseMap) {
unsigned VRBase = 0;
if (MRegisterInfo::isVirtualRegister(SrcReg)) {
// Just use the input register directly!
+ if (InstanceNo > 0)
+ VRBaseMap.erase(SDOperand(Node, ResNo));
bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo),SrcReg));
assert(isNew && "Node emitted out of order - early");
return;
@@ -282,32 +322,54 @@
// If the node is only used by a CopyToReg and the dest reg is a vreg, use
// the CopyToReg'd destination register instead of creating a new vreg.
+ bool MatchReg = true;
for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
UI != E; ++UI) {
SDNode *Use = *UI;
+ bool Match = true;
if (Use->getOpcode() == ISD::CopyToReg &&
Use->getOperand(2).Val == Node &&
Use->getOperand(2).ResNo == ResNo) {
unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
if (MRegisterInfo::isVirtualRegister(DestReg)) {
VRBase = DestReg;
- break;
+ Match = false;
+ } else if (DestReg != SrcReg)
+ Match = false;
+ } else {
+ for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
+ SDOperand Op = Use->getOperand(i);
+ if (Op.Val != Node)
+ continue;
+ MVT::ValueType VT = Node->getValueType(Op.ResNo);
+ if (VT != MVT::Other && VT != MVT::Flag)
+ Match = false;
}
}
+ MatchReg &= Match;
+ if (VRBase)
+ break;
}
- // Figure out the register class to create for the destreg.
const TargetRegisterClass *TRC = 0;
- if (VRBase) {
+ // Figure out the register class to create for the destreg.
+ if (VRBase)
TRC = RegMap->getRegClass(VRBase);
- } else {
+ else
TRC = getPhysicalRegisterRegClass(MRI, Node->getValueType(ResNo), SrcReg);
-
+
+ // If all uses are reading from the src physical register and copying the
+ // register is either impossible or very expensive, then don't create a copy.
+ if (MatchReg && TRC->getCopyCost() < 0) {
+ VRBase = SrcReg;
+ } else {
// Create the reg, emit the copy.
VRBase = RegMap->createVirtualRegister(TRC);
+ MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
}
- MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
+ if (InstanceNo > 0)
+ VRBaseMap.erase(SDOperand(Node, ResNo));
bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo), VRBase));
assert(isNew && "Node emitted out of order - early");
}
@@ -611,7 +673,7 @@
/// EmitNode - Generate machine code for an node and needed dependencies.
///
-void ScheduleDAG::EmitNode(SDNode *Node,
+void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
DenseMap<SDOperand, unsigned> &VRBaseMap) {
// If machine instruction
if (Node->isTargetOpcode()) {
@@ -677,7 +739,7 @@
for (unsigned i = II.numDefs; i < NumResults; ++i) {
unsigned Reg = II.ImplicitDefs[i - II.numDefs];
if (Node->hasAnyUseOfValue(i))
- EmitCopyFromReg(Node, i, Reg, VRBaseMap);
+ EmitCopyFromReg(Node, i, InstanceNo, Reg, VRBaseMap);
}
}
} else {
@@ -713,7 +775,7 @@
}
case ISD::CopyFromReg: {
unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
- EmitCopyFromReg(Node, 0, SrcReg, VRBaseMap);
+ EmitCopyFromReg(Node, 0, InstanceNo, SrcReg, VRBaseMap);
break;
}
case ISD::INLINEASM: {
@@ -802,9 +864,9 @@
DenseMap<SDOperand, unsigned> VRBaseMap;
for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
if (SUnit *SU = Sequence[i]) {
- for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++)
- EmitNode(SU->FlaggedNodes[j], VRBaseMap);
- EmitNode(SU->Node, VRBaseMap);
+ for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j)
+ EmitNode(SU->FlaggedNodes[j], SU->InstanceNo, VRBaseMap);
+ EmitNode(SU->Node, SU->InstanceNo, VRBaseMap);
} else {
// Null SUnit* is a noop.
EmitNoop();
@@ -869,7 +931,10 @@
cerr << " ch #";
else
cerr << " val #";
- cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")\n";
+ cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+ if (I->isSpecial)
+ cerr << " *";
+ cerr << "\n";
}
}
if (Succs.size() != 0) {
@@ -880,7 +945,10 @@
cerr << " ch #";
else
cerr << " val #";
- cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")\n";
+ cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+ if (I->isSpecial)
+ cerr << " *";
+ cerr << "\n";
}
}
cerr << "\n";