Use a linked data structure for the uses lists of an SDNode, just like
LLVM Value/Use does and MachineRegisterInfo/MachineOperand does.
This allows constant time for all uses list maintenance operations.
The idea was suggested by Chris. Reviewed by Evan and Dan.
Patch is tested and approved by Dan.
On normal use-cases compilation speed is not affected. On very big basic
blocks there are compilation speedups in the range of 15-20% or even better.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48822 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 048ee2c..da83132 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -135,11 +135,11 @@
bool HasFlagUse = false;
for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
UI != E; ++UI)
- if (FlagVal.isOperandOf(*UI)) {
+ if (FlagVal.isOperandOf(UI->getUser())) {
HasFlagUse = true;
NodeSUnit->FlaggedNodes.push_back(N);
SUnitMap[N].push_back(NodeSUnit);
- N = *UI;
+ N = UI->getUser();
break;
}
if (!HasFlagUse) break;
@@ -398,7 +398,7 @@
void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
unsigned InstanceNo, unsigned SrcReg,
- DenseMap<SDOperand, unsigned> &VRBaseMap) {
+ DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
unsigned VRBase = 0;
if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
// Just use the input register directly!
@@ -414,7 +414,7 @@
bool MatchReg = true;
for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
UI != E; ++UI) {
- SDNode *Use = *UI;
+ SDNode *Use = UI->getUser();
bool Match = true;
if (Use->getOpcode() == ISD::CopyToReg &&
Use->getOperand(2).Val == Node &&
@@ -469,7 +469,7 @@
void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
const TargetInstrDesc &II,
- DenseMap<SDOperand, unsigned> &VRBaseMap) {
+ DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
for (unsigned i = 0; i < II.getNumDefs(); ++i) {
// If the specific node value is only used by a CopyToReg and the dest reg
// is a vreg, use the CopyToReg'd destination register instead of creating
@@ -477,7 +477,7 @@
unsigned VRBase = 0;
for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
UI != E; ++UI) {
- SDNode *Use = *UI;
+ SDNode *Use = UI->getUser();
if (Use->getOpcode() == ISD::CopyToReg &&
Use->getOperand(2).Val == Node &&
Use->getOperand(2).ResNo == i) {
@@ -512,8 +512,8 @@
/// getVR - Return the virtual register corresponding to the specified result
/// of the specified node.
-static unsigned getVR(SDOperand Op, DenseMap<SDOperand, unsigned> &VRBaseMap) {
- DenseMap<SDOperand, unsigned>::iterator I = VRBaseMap.find(Op);
+static unsigned getVR(SDOperand Op, DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
+ DenseMap<SDOperandImpl, unsigned>::iterator I = VRBaseMap.find(Op);
assert(I != VRBaseMap.end() && "Node emitted out of order - late");
return I->second;
}
@@ -526,7 +526,7 @@
void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op,
unsigned IIOpNum,
const TargetInstrDesc *II,
- DenseMap<SDOperand, unsigned> &VRBaseMap) {
+ DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
if (Op.isTargetOpcode()) {
// Note that this case is redundant with the final else block, but we
// include it because it is the most common and it makes the logic
@@ -658,7 +658,7 @@
/// EmitSubregNode - Generate machine code for subreg nodes.
///
void ScheduleDAG::EmitSubregNode(SDNode *Node,
- DenseMap<SDOperand, unsigned> &VRBaseMap) {
+ DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
unsigned VRBase = 0;
unsigned Opc = Node->getTargetOpcode();
@@ -666,7 +666,7 @@
// the CopyToReg'd destination register instead of creating a new vreg.
for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
UI != E; ++UI) {
- SDNode *Use = *UI;
+ SDNode *Use = UI->getUser();
if (Use->getOpcode() == ISD::CopyToReg &&
Use->getOperand(2).Val == Node) {
unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
@@ -750,7 +750,7 @@
/// EmitNode - Generate machine code for an node and needed dependencies.
///
void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
- DenseMap<SDOperand, unsigned> &VRBaseMap) {
+ DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
// If machine instruction
if (Node->isTargetOpcode()) {
unsigned Opc = Node->getTargetOpcode();
@@ -1067,7 +1067,7 @@
}
// Finally, emit the code for all of the scheduled instructions.
- DenseMap<SDOperand, unsigned> VRBaseMap;
+ DenseMap<SDOperandImpl, unsigned> VRBaseMap;
DenseMap<SUnit*, unsigned> CopyVRBaseMap;
for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
if (SUnit *SU = Sequence[i]) {