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/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index ed564b2..b01b525 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -10,7 +10,6 @@
// This implements the SelectionDAG class.
//
//===----------------------------------------------------------------------===//
-
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Constants.h"
#include "llvm/GlobalAlias.h"
@@ -465,14 +464,15 @@
// no cycles in the graph.
for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
SDNode *Operand = I->Val;
- Operand->removeUser(N);
+ Operand->removeUser(std::distance(N->op_begin(), I), N);
// Now that we removed this operand, see if there are no uses of it left.
if (Operand->use_empty())
DeadNodes.push_back(Operand);
}
- if (N->OperandsNeedDelete)
+ if (N->OperandsNeedDelete) {
delete[] N->OperandList;
+ }
N->OperandList = 0;
N->NumOperands = 0;
@@ -504,14 +504,15 @@
// no cycles in the graph.
for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
SDNode *Operand = I->Val;
- Operand->removeUser(N);
+ Operand->removeUser(std::distance(N->op_begin(), I), N);
// Now that we removed this operand, see if there are no uses of it left.
if (Operand->use_empty())
DeadNodes.push_back(Operand);
}
- if (N->OperandsNeedDelete)
+ if (N->OperandsNeedDelete) {
delete[] N->OperandList;
+ }
N->OperandList = 0;
N->NumOperands = 0;
@@ -538,9 +539,10 @@
// Drop all of the operands and decrement used nodes use counts.
for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
- I->Val->removeUser(N);
- if (N->OperandsNeedDelete)
+ I->Val->removeUser(std::distance(N->op_begin(), I), N);
+ if (N->OperandsNeedDelete) {
delete[] N->OperandList;
+ }
N->OperandList = 0;
N->NumOperands = 0;
@@ -701,8 +703,9 @@
while (!AllNodes.empty()) {
SDNode *N = AllNodes.begin();
N->SetNextInBucket(0);
- if (N->OperandsNeedDelete)
+ if (N->OperandsNeedDelete) {
delete [] N->OperandList;
+ }
N->OperandList = 0;
N->NumOperands = 0;
AllNodes.pop_front();
@@ -2920,9 +2923,10 @@
RemoveNodeFromCSEMaps(N);
// Now we update the operands.
- N->OperandList[0].Val->removeUser(N);
- Op.Val->addUser(N);
+ N->OperandList[0].Val->removeUser(0, N);
N->OperandList[0] = Op;
+ N->OperandList[0].setUser(N);
+ Op.Val->addUser(0, N);
// If this gets put into a CSE map, add it.
if (InsertPos) CSEMap.InsertNode(N, InsertPos);
@@ -2949,14 +2953,16 @@
// Now we update the operands.
if (N->OperandList[0] != Op1) {
- N->OperandList[0].Val->removeUser(N);
- Op1.Val->addUser(N);
+ N->OperandList[0].Val->removeUser(0, N);
N->OperandList[0] = Op1;
+ N->OperandList[0].setUser(N);
+ Op1.Val->addUser(0, N);
}
if (N->OperandList[1] != Op2) {
- N->OperandList[1].Val->removeUser(N);
- Op2.Val->addUser(N);
+ N->OperandList[1].Val->removeUser(1, N);
N->OperandList[1] = Op2;
+ N->OperandList[1].setUser(N);
+ Op2.Val->addUser(1, N);
}
// If this gets put into a CSE map, add it.
@@ -2984,7 +2990,6 @@
return UpdateNodeOperands(N, Ops, 5);
}
-
SDOperand SelectionDAG::
UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
SDNode *N = InN.Val;
@@ -3015,9 +3020,10 @@
// Now we update the operands.
for (unsigned i = 0; i != NumOps; ++i) {
if (N->OperandList[i] != Ops[i]) {
- N->OperandList[i].Val->removeUser(N);
- Ops[i].Val->addUser(N);
+ N->OperandList[i].Val->removeUser(i, N);
N->OperandList[i] = Ops[i];
+ N->OperandList[i].setUser(N);
+ Ops[i].Val->addUser(i, N);
}
}
@@ -3026,7 +3032,6 @@
return InN;
}
-
/// MorphNodeTo - This frees the operands of the current node, resets the
/// opcode, types, and operands to the specified value. This should only be
/// used by the SelectionDAG class.
@@ -3039,13 +3044,14 @@
// Clear the operands list, updating used nodes to remove this from their
// use list.
for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
- I->Val->removeUser(this);
+ I->Val->removeUser(std::distance(op_begin(), I), this);
// If NumOps is larger than the # of operands we currently have, reallocate
// the operand list.
if (NumOps > NumOperands) {
- if (OperandsNeedDelete)
+ if (OperandsNeedDelete) {
delete [] OperandList;
+ }
OperandList = new SDOperand[NumOps];
OperandsNeedDelete = true;
}
@@ -3055,8 +3061,10 @@
for (unsigned i = 0, e = NumOps; i != e; ++i) {
OperandList[i] = Ops[i];
+ OperandList[i].setUser(this);
SDNode *N = OperandList[i].Val;
- N->Uses.push_back(this);
+ N->addUser(i, this);
+ ++N->UsesSize;
}
}
@@ -3324,21 +3332,27 @@
assert(From->getNumValues() == 1 && FromN.ResNo == 0 &&
"Cannot replace with this method!");
assert(From != To.Val && "Cannot replace uses of with self");
-
+
+ SmallSetVector<SDNode*, 16> Users;
while (!From->use_empty()) {
- // Process users until they are all gone.
- SDNode *U = *From->use_begin();
-
+ SDNode::use_iterator UI = From->use_begin();
+ SDNode *U = UI->getUser();
+
+ // Remember that this node is about to morph.
+ if (Users.count(U))
+ continue;
+ Users.insert(U);
// This node is about to morph, remove its old self from the CSE maps.
RemoveNodeFromCSEMaps(U);
-
- for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
- I != E; ++I)
+ int operandNum = 0;
+ for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
+ I != E; ++I, ++operandNum)
if (I->Val == From) {
- From->removeUser(U);
+ From->removeUser(operandNum, U);
*I = To;
- To.Val->addUser(U);
- }
+ I->setUser(U);
+ To.Val->addUser(operandNum, U);
+ }
// Now that we have modified U, add it back to the CSE maps. If it already
// exists there, recursively merge the results together.
@@ -3372,21 +3386,26 @@
return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
UpdateListener);
+ SmallSetVector<SDNode*, 16> Users;
while (!From->use_empty()) {
- // Process users until they are all gone.
- SDNode *U = *From->use_begin();
-
+ SDNode::use_iterator UI = From->use_begin();
+ SDNode *U = UI->getUser();
+
+ // Remember that this node is about to morph.
+ if (Users.count(U))
+ continue;
+ Users.insert(U);
// This node is about to morph, remove its old self from the CSE maps.
RemoveNodeFromCSEMaps(U);
-
- for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
- I != E; ++I)
+ int operandNum = 0;
+ for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
+ I != E; ++I, ++operandNum)
if (I->Val == From) {
- From->removeUser(U);
+ From->removeUser(operandNum, U);
I->Val = To;
- To->addUser(U);
+ To->addUser(operandNum, U);
}
-
+
// Now that we have modified U, add it back to the CSE maps. If it already
// exists there, recursively merge the results together.
if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
@@ -3415,22 +3434,28 @@
if (From->getNumValues() == 1) // Handle the simple case efficiently.
return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
+ SmallSetVector<SDNode*, 16> Users;
while (!From->use_empty()) {
- // Process users until they are all gone.
- SDNode *U = *From->use_begin();
-
+ SDNode::use_iterator UI = From->use_begin();
+ SDNode *U = UI->getUser();
+
+ // Remember that this node is about to morph.
+ if (Users.count(U))
+ continue;
+ Users.insert(U);
// This node is about to morph, remove its old self from the CSE maps.
RemoveNodeFromCSEMaps(U);
-
- for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
- I != E; ++I)
+ int operandNum = 0;
+ for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
+ I != E; ++I, ++operandNum)
if (I->Val == From) {
const SDOperand &ToOp = To[I->ResNo];
- From->removeUser(U);
+ From->removeUser(operandNum, U);
*I = ToOp;
- ToOp.Val->addUser(U);
+ I->setUser(U);
+ ToOp.Val->addUser(operandNum, U);
}
-
+
// Now that we have modified U, add it back to the CSE maps. If it already
// exists there, recursively merge the results together.
if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
@@ -3460,7 +3485,7 @@
ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
SelectionDAG::DAGUpdateListener *chain)
: Set(set), Chain(chain) {}
-
+
virtual void NodeDeleted(SDNode *N) {
Set.remove(N);
if (Chain) Chain->NodeDeleted(N);
@@ -3488,7 +3513,13 @@
// Get all of the users of From.Val. We want these in a nice,
// deterministically ordered and uniqued set, so we use a SmallSetVector.
- SmallSetVector<SDNode*, 16> Users(From.Val->use_begin(), From.Val->use_end());
+ SmallSetVector<SDNode*, 16> Users;
+ for (SDNode::use_iterator UI = From.Val->use_begin(),
+ E = From.Val->use_end(); UI != E; ++UI) {
+ SDNode *User = UI->getUser();
+ if (!Users.count(User))
+ Users.insert(User);
+ }
// When one of the recursive merges deletes nodes from the graph, we need to
// make sure that UpdateListener is notified *and* that the node is removed
@@ -3502,7 +3533,7 @@
Users.pop_back();
// Scan for an operand that matches From.
- SDOperand *Op = User->OperandList, *E = User->OperandList+User->NumOperands;
+ SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
for (; Op != E; ++Op)
if (*Op == From) break;
@@ -3516,9 +3547,10 @@
// Update all operands that match "From" in case there are multiple uses.
for (; Op != E; ++Op) {
if (*Op == From) {
- From.Val->removeUser(User);
- *Op = To;
- To.Val->addUser(User);
+ From.Val->removeUser(Op-User->op_begin(), User);
+ *Op = To;
+ Op->setUser(User);
+ To.Val->addUser(Op-User->op_begin(), User);
}
}
@@ -3698,16 +3730,13 @@
SmallPtrSet<SDNode*, 32> UsersHandled;
- for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) {
- SDNode *User = *UI;
- if (User->getNumOperands() == 1 ||
- UsersHandled.insert(User)) // First time we've seen this?
- for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
- if (User->getOperand(i) == TheValue) {
- if (NUses == 0)
- return false; // too many uses
- --NUses;
- }
+ // TODO: Only iterate over uses of a given value of the node
+ for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
+ if (*UI == TheValue) {
+ if (NUses == 0)
+ return false;
+ --NUses;
+ }
}
// Found exactly the right number of uses?
@@ -3726,8 +3755,8 @@
SmallPtrSet<SDNode*, 32> UsersHandled;
- for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) {
- SDNode *User = *UI;
+ for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
+ SDNode *User = UI->getUser();
if (User->getNumOperands() == 1 ||
UsersHandled.insert(User)) // First time we've seen this?
for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
@@ -3745,7 +3774,7 @@
bool SDNode::isOnlyUseOf(SDNode *N) const {
bool Seen = false;
for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
- SDNode *User = *I;
+ SDNode *User = I->getUser();
if (User == this)
Seen = true;
else
@@ -3757,7 +3786,7 @@
/// isOperand - Return true if this node is an operand of N.
///
-bool SDOperand::isOperandOf(SDNode *N) const {
+bool SDOperandImpl::isOperandOf(SDNode *N) const {
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
if (*this == N->getOperand(i))
return true;
@@ -3776,7 +3805,7 @@
/// side-effecting instructions. In practice, this looks through token
/// factors and non-volatile loads. In order to remain efficient, this only
/// looks a couple of nodes in, it does not do an exhaustive search.
-bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest,
+bool SDOperandImpl::reachesChainWithoutSideEffects(SDOperandImpl Dest,
unsigned Depth) const {
if (*this == Dest) return true;