Change ScheduleDAG's SUnitMap from DenseMap<SDNode*, vector<SUnit*> >
to DenseMap<SDNode*, SUnit*>, and adjust the way cloned SUnit nodes are
handled so that only the original node needs to be in the map.
This speeds up llc on 447.dealII.llvm.bc by about 2%.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52576 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index d3cc116..d61a098 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -79,13 +79,12 @@
SUnit *ScheduleDAG::Clone(SUnit *Old) {
SUnit *SU = NewSUnit(Old->Node);
+ SU->OrigNode = Old->OrigNode;
SU->FlaggedNodes = Old->FlaggedNodes;
- SU->InstanceNo = SUnitMap[Old->Node].size();
SU->Latency = Old->Latency;
SU->isTwoAddress = Old->isTwoAddress;
SU->isCommutable = Old->isCommutable;
SU->hasPhysRegDefs = Old->hasPhysRegDefs;
- SUnitMap[Old->Node].push_back(SU);
return SU;
}
@@ -105,7 +104,7 @@
continue;
// If this node has already been processed, stop now.
- if (!SUnitMap[NI].empty()) continue;
+ if (SUnitMap.count(NI)) continue;
SUnit *NodeSUnit = NewSUnit(NI);
@@ -120,7 +119,9 @@
do {
N = N->getOperand(N->getNumOperands()-1).Val;
NodeSUnit->FlaggedNodes.push_back(N);
- SUnitMap[N].push_back(NodeSUnit);
+ bool isNew = SUnitMap.insert(std::make_pair(N, NodeSUnit));
+ isNew = isNew;
+ assert(isNew && "Node already inserted!");
} while (N->getNumOperands() &&
N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
std::reverse(NodeSUnit->FlaggedNodes.begin(),
@@ -140,7 +141,9 @@
if (FlagVal.isOperandOf(UI->getUser())) {
HasFlagUse = true;
NodeSUnit->FlaggedNodes.push_back(N);
- SUnitMap[N].push_back(NodeSUnit);
+ bool isNew = SUnitMap.insert(std::make_pair(N, NodeSUnit));
+ isNew = isNew;
+ assert(isNew && "Node already inserted!");
N = UI->getUser();
break;
}
@@ -150,7 +153,9 @@
// Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
// Update the SUnit
NodeSUnit->Node = N;
- SUnitMap[N].push_back(NodeSUnit);
+ bool isNew = SUnitMap.insert(std::make_pair(N, NodeSUnit));
+ isNew = isNew;
+ assert(isNew && "Node already inserted!");
ComputeLatency(NodeSUnit);
}
@@ -187,7 +192,7 @@
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].front();
+ SUnit *OpSU = SUnitMap[OpN];
assert(OpSU && "Node has no SUnit!");
if (OpSU == SU) continue; // In the same group.
@@ -399,12 +404,12 @@
}
void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
- unsigned InstanceNo, unsigned SrcReg,
+ bool IsClone, unsigned SrcReg,
DenseMap<SDOperand, unsigned> &VRBaseMap) {
unsigned VRBase = 0;
if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
// Just use the input register directly!
- if (InstanceNo > 0)
+ if (IsClone)
VRBaseMap.erase(SDOperand(Node, ResNo));
bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo),SrcReg));
isNew = isNew; // Silence compiler warning.
@@ -463,7 +468,7 @@
TII->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, DstRC, SrcRC);
}
- if (InstanceNo > 0)
+ if (IsClone)
VRBaseMap.erase(SDOperand(Node, ResNo));
bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo), VRBase));
isNew = isNew; // Silence compiler warning.
@@ -783,7 +788,7 @@
/// EmitNode - Generate machine code for an node and needed dependencies.
///
-void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
+void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone,
DenseMap<SDOperand, unsigned> &VRBaseMap) {
// If machine instruction
if (Node->isTargetOpcode()) {
@@ -858,7 +863,7 @@
for (unsigned i = II.getNumDefs(); i < NumResults; ++i) {
unsigned Reg = II.getImplicitDefs()[i - II.getNumDefs()];
if (Node->hasAnyUseOfValue(i))
- EmitCopyFromReg(Node, i, InstanceNo, Reg, VRBaseMap);
+ EmitCopyFromReg(Node, i, IsClone, Reg, VRBaseMap);
}
}
} else {
@@ -906,7 +911,7 @@
}
case ISD::CopyFromReg: {
unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
- EmitCopyFromReg(Node, 0, InstanceNo, SrcReg, VRBaseMap);
+ EmitCopyFromReg(Node, 0, IsClone, SrcReg, VRBaseMap);
break;
}
case ISD::INLINEASM: {
@@ -1118,11 +1123,11 @@
continue;
}
for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j)
- EmitNode(SU->FlaggedNodes[j], SU->InstanceNo, VRBaseMap);
+ EmitNode(SU->FlaggedNodes[j], SU->OrigNode != SU, VRBaseMap);
if (!SU->Node)
EmitCrossRCCopy(SU, CopyVRBaseMap);
else
- EmitNode(SU->Node, SU->InstanceNo, VRBaseMap);
+ EmitNode(SU->Node, SU->OrigNode != SU, VRBaseMap);
}
if (isEntryBB && SchedLiveInCopies)
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index c2fae25..909588c 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -177,6 +177,7 @@
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
std::vector<SUnit*> NotReady;
+ Sequence.reserve(SUnits.size());
while (!AvailableQueue->empty() || !PendingQueue.empty()) {
// Check to see if any of the pending instructions are ready to issue. If
// so, add them to the available queue.
@@ -319,7 +320,7 @@
LatencyPriorityQueue() : Queue(latency_sort(this)) {
}
- void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
+ void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
std::vector<SUnit> &sunits) {
SUnits = &sunits;
// Calculate node priorities.
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index fc20170..f07bcd5 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -254,7 +254,7 @@
continue;
SDNode *OpN = SU->Node->getOperand(j).Val;
- SUnit *OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo];
+ SUnit *OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN];
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
@@ -263,7 +263,7 @@
for (unsigned k = 0; k < NumOps; ++k) {
if (k != j) {
OpN = SU->Node->getOperand(k).Val;
- OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo];
+ OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN];
if (OpSU && OperandSeen.count(OpSU) == 1) {
DoCommute = false;
break;
@@ -282,7 +282,7 @@
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
if (!I->isCtrl)
- OperandSeen.insert(I->Dep);
+ OperandSeen.insert(I->Dep->OrigNode);
}
}
}
@@ -660,7 +660,7 @@
}
if (TryUnfold) {
- SmallVector<SDNode*, 4> NewNodes;
+ SmallVector<SDNode*, 2> NewNodes;
if (!TII->unfoldMemoryOperand(DAG, N, NewNodes))
return NULL;
@@ -677,7 +677,10 @@
SDOperand(LoadNode, 1));
SUnit *NewSU = CreateNewSUnit(N);
- SUnitMap[N].push_back(NewSU);
+ bool isNew = SUnitMap.insert(std::make_pair(N, NewSU));
+ isNew = isNew;
+ assert(isNew && "Node already inserted!");
+
const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
@@ -697,14 +700,15 @@
// but it has different alignment or volatileness.
bool isNewLoad = true;
SUnit *LoadSU;
- DenseMap<SDNode*, std::vector<SUnit*> >::iterator SMI =
- SUnitMap.find(LoadNode);
+ DenseMap<SDNode*, SUnit*>::iterator SMI = SUnitMap.find(LoadNode);
if (SMI != SUnitMap.end()) {
- LoadSU = SMI->second.front();
+ LoadSU = SMI->second;
isNewLoad = false;
} else {
LoadSU = CreateNewSUnit(LoadNode);
- SUnitMap[LoadNode].push_back(LoadSU);
+ bool isNew = SUnitMap.insert(std::make_pair(LoadNode, LoadSU));
+ isNew = isNew;
+ assert(isNew && "Node already inserted!");
LoadSU->Depth = SU->Depth;
LoadSU->Height = SU->Height;
@@ -943,7 +947,7 @@
unsigned CurCycle = 0;
// Add root to Available queue.
if (!SUnits.empty()) {
- SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front();
+ SUnit *RootSU = SUnitMap[DAG.getRoot().Val];
assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
RootSU->isAvailable = true;
AvailableQueue->push(RootSU);
@@ -952,6 +956,7 @@
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
SmallVector<SUnit*, 4> NotReady;
+ Sequence.reserve(SUnits.size());
while (!AvailableQueue->empty()) {
bool Delayed = false;
DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
@@ -1174,6 +1179,7 @@
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
std::vector<SUnit*> NotReady;
+ Sequence.reserve(SUnits.size());
while (!AvailableQueue->empty()) {
SUnit *CurSU = AvailableQueue->pop();
while (CurSU && CurSU->CycleBound > CurCycle) {
@@ -1277,7 +1283,7 @@
RegReductionPriorityQueue() :
Queue(SF(this)), currentQueueId(0) {}
- virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
+ virtual void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
std::vector<SUnit> &sunits) {}
virtual void addNode(const SUnit *SU) {}
@@ -1327,7 +1333,7 @@
class VISIBILITY_HIDDEN BURegReductionPriorityQueue
: public RegReductionPriorityQueue<bu_ls_rr_sort> {
// SUnitMap SDNode to SUnit mapping (n -> n).
- DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
+ DenseMap<SDNode*, SUnit*> *SUnitMap;
// SUnits - The SUnits for the current graph.
const std::vector<SUnit> *SUnits;
@@ -1343,7 +1349,7 @@
const TargetRegisterInfo *tri)
: TII(tii), TRI(tri), scheduleDAG(NULL) {}
- void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
+ void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
std::vector<SUnit> &sunits) {
SUnitMap = &sumap;
SUnits = &sunits;
@@ -1414,7 +1420,7 @@
class VISIBILITY_HIDDEN TDRegReductionPriorityQueue
: public RegReductionPriorityQueue<td_ls_rr_sort> {
// SUnitMap SDNode to SUnit mapping (n -> n).
- DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
+ DenseMap<SDNode*, SUnit*> *SUnitMap;
// SUnits - The SUnits for the current graph.
const std::vector<SUnit> *SUnits;
@@ -1425,7 +1431,7 @@
public:
TDRegReductionPriorityQueue() {}
- void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
+ void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
std::vector<SUnit> &sunits) {
SUnitMap = &sumap;
SUnits = &sunits;
@@ -1560,7 +1566,7 @@
if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
SDNode *DU = SU->Node->getOperand(i).Val;
if ((*SUnitMap).find(DU) != (*SUnitMap).end() &&
- Op == (*SUnitMap)[DU][SU->InstanceNo])
+ Op->OrigNode == (*SUnitMap)[DU])
return true;
}
}
@@ -1636,7 +1642,7 @@
SDNode *DU = SU->Node->getOperand(j).Val;
if ((*SUnitMap).find(DU) == (*SUnitMap).end())
continue;
- SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo];
+ SUnit *DUSU = (*SUnitMap)[DU];
if (!DUSU) continue;
for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
I != E; ++I) {
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
index f922168..995d877 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
@@ -303,7 +303,7 @@
GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot");
if (G->DAG.getRoot().Val &&
G->SUnitMap.find(G->DAG.getRoot().Val) != G->SUnitMap.end())
- GW.emitEdge(0, -1, G->SUnitMap[G->DAG.getRoot().Val].front(), -1, "");
+ GW.emitEdge(0, -1, G->SUnitMap[G->DAG.getRoot().Val], -1, "");
}
};
}