[LLVMdev] Dead node removal in DAGCombiner

[Akira Hatanaka]

On Fri, Aug 26, 2011 at 9:52 AM, Duncan Sands <baldrick at free.fr> wrote:
> 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.

> Ciao, Duncan.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>