Dead node removal in DAGCombiner

Is this piece of code in DAGCombiner::visitLOAD removing a dead node?

06155 if (N->use_empty()) {
06156 removeFromWorkList(N);
06157 DAG.DeleteNode(N);
06158 }

If it is, is there a reason it doesn't push its operands to the work
list as done in line 974-975?

00970 // If N has no uses, it is dead. Make sure to revisit all
N's operands once
00971 // N is deleted from the DAG, since they too may now be dead
or may have a
00972 // reduced number of uses, allowing other xforms.
00973 if (N->use_empty() && N != &Dummy) {
00974 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00975 AddToWorkList(N->getOperand(i).getNode());
00976
00977 DAG.DeleteNode(N);
00978 continue;
00979 }

Or is it one of the corner cases mentioned in SelectionDAGISel.cpp:644?

00644 // Skip dead nodes. DAGCombiner is expected to eliminate
all dead nodes,
00645 // but there are currently some corner cases that it
misses. Also, this
00646 // makes it theoretically possible to disable the DAGCombiner.

I am seeing an error message "LLVM ERROR: Cannot select:" because
operands of a dead node do not get removed.

Hi Akira,

Is this piece of code in DAGCombiner::visitLOAD removing a dead node?

06155 if (N->use_empty()) {
06156 removeFromWorkList(N);
06157 DAG.DeleteNode(N);
06158 }

yes.

If it is, is there a reason it doesn't push its operands to the work
list as done in line 974-975?

00970 // If N has no uses, it is dead. Make sure to revisit all
N's operands once
00971 // N is deleted from the DAG, since they too may now be dead
or may have a
00972 // reduced number of uses, allowing other xforms.
00973 if (N->use_empty()&& N !=&Dummy) {
00974 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00975 AddToWorkList(N->getOperand(i).getNode());
00976
00977 DAG.DeleteNode(N);
00978 continue;
00979 }

I suspect they could be removed. Probably a helper function should be added
for this and used all over the place. Also, the RAUW earlier can cause nodes
to be unified (due to CSE). Probably the WorkListRemover class should add nodes
to the worklist in the NodeUpdated method.

Or is it one of the corner cases mentioned in SelectionDAGISel.cpp:644?

00644 // Skip dead nodes. DAGCombiner is expected to eliminate
all dead nodes,
00645 // but there are currently some corner cases that it
misses. Also, this
00646 // makes it theoretically possible to disable the DAGCombiner.

I am seeing an error message "LLVM ERROR: Cannot select:" because
operands of a dead node do not get removed.

What is it that cannot be selected?

Ciao, Duncan.

Hi Akira,

Is this piece of code in DAGCombiner::visitLOAD removing a dead node?

06155 if (N->use_empty()) {
06156 removeFromWorkList(N);
06157 DAG.DeleteNode(N);
06158 }

yes.

If it is, is there a reason it doesn't push its operands to the work
list as done in line 974-975?

00970 // If N has no uses, it is dead. Make sure to revisit all
N's operands once
00971 // N is deleted from the DAG, since they too may now be dead
or may have a
00972 // reduced number of uses, allowing other xforms.
00973 if (N->use_empty()&& N !=&Dummy) {
00974 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00975 AddToWorkList(N->getOperand(i).getNode());
00976
00977 DAG.DeleteNode(N);
00978 continue;
00979 }

I suspect they could be removed. Probably a helper function should be added
for this and used all over the place. Also, the RAUW earlier can cause nodes
to be unified (due to CSE). Probably the WorkListRemover class should add nodes
to the worklist in the NodeUpdated method.

Or is it one of the corner cases mentioned in SelectionDAGISel.cpp:644?

00644 // Skip dead nodes. DAGCombiner is expected to eliminate
all dead nodes,
00645 // but there are currently some corner cases that it
misses. Also, this
00646 // makes it theoretically possible to disable the DAGCombiner.

I am seeing an error message "LLVM ERROR: Cannot select:" because
operands of a dead node do not get removed.

What is it that cannot be selected?

This seems to be what is happening,

There is a subgraph in the DAG.
(Load (Add (MipsHi tglobaladdr), (MipsLo tglobaladdr)))

The Load node is removed in DAGCombiner.cpp:6155, but its operand are
not removed, leaving this subgraph:
(Add (MipsHi tglobaladdr), (MipsLo tglobaladdr))

Since Add is a dead node without any users, the selector skips this
node in SelectionDAGISel.cpp:644-.

Then, the selector tries to match this fragment:
(MipsLo tglobaladdr)

MipsLo does not have a pattern defined, since it is not meant to be
the root node of a pattern, therefore instruction selection fails.

I was thinking this problem should go away if DAGCombiner cleans up
all dead nodes, but it looks like I should just define a pattern for
MIpsLo for now.