[LLVMdev] Making Sense of ISel DAG Output

[Dan Gohman]

On Oct 7, 2008, at 12:04 PM, David Greene wrote:

> On Friday 03 October 2008 12:06, Dan Gohman wrote:
>> On Fri, October 3, 2008 9:10 am, David Greene wrote:
>>> On Thursday 02 October 2008 19:32, Dan Gohman wrote:
>>>> Looking at your dump() output above, it looks like the pre- 
>>>> selection
>>>> loads have multiple uses, so even though you've managed to match a
>>>> larger pattern that incorporates them, they still need to exist to
>>>> satisfy some other users.
>>>
>>> Yes, I looked at that too.  It looks like these other uses end up  
>>> being
>>> chains to TokenFactor nodes that don't go anywhere.  They're really,
>>> truly,
>>> dead.  Who is supposed to clean those up?
>>
>> DAGCombine will zap dead nodes, but nodes can also become dead
>> during selection. Some parts of selection know how to clean up
>> nodes that become dead during selection, but my guess is that
>> it's missing some cases.
>
> Ok, as far as I can tell, here's what's happening.
>
> I have the following pattern:
>
> let AddedComplexity = 40 in {
>  def : Pat<(v2f64 (vector_shuffle (v2f64 (scalar_to_vector (loadf64  
> addr:
> $src1))),
>                                   (v2f64 (scalar_to_vector (loadf64  
> addr:
> $src2))),
>                                   SHUFP_shuffle_mask:$sm)),
>            (SHUFPDrri (v2f64 (MOVSD2PDrm addr:$src1)),
>                       (v2f64 (MOVSD2PDrm addr:$src2)),
>                       SHUFP_shuffle_mask:$sm)>, Requires<[HasSSE2]>;
> } // AddedComplexity
>
> After much hacking of tblgen, I finally convinced it to generate some
> somewhat-seemingly-reasonably-correct matching and generation code.
>
> What's happening is that that generation code constructs two MOVSD2PD
> instructions.  These are all brand-new SDNodes.  The very last step  
> of the
> generation code calls
>
>  SDNode *RetVal = CurDAG->SelectNodeTo(N.Val, Opc2, VT2, Tmp1, Tmp3,  
> Tmp5);
>
> where N is the vector_shuffle node.  and the Tmp variables are the two
> MOVSD2PD instructions and the shuffle mask.  SelectNodeTo does an in- 
> place
> replacement of the machine-independent SDNode (vector_shuffle)with a
> machine-dependent one (the SHUFPD).
>
> When we pop back out to SelectRoot we run into this code:
>
>      if (ResNode != Node) {
>        if (ResNode) {
>          ReplaceUses(Node, ResNode);
>        }
>        if (Node->use_empty()) { // Don't delete EntryToken, etc.
>          ISelQueueUpdater ISQU(ISelQueue);
>          CurDAG->RemoveDeadNode(Node, &ISQU);
>          UpdateQueue(ISQU);
>        }
>      }
>
> Since we did an in-placement replacement the first test fails and we  
> don't
> call ReplaceUses.  I think this is correct EXCEPT that now we have  
> orphaned
> machine-independent loadf64 and scalar_to_vector nodes that got  
> disconnected
> from the vector_shuffle by SelectNodeTo.  We go ahead and  select  
> those
> (correctly) to MOVSD instructions which are then dead.  But no one  
> cleans them
> up.
>
> The root of the problem seems to be the orphand operands of the
> vector_shuffle.  Given that I had to hack tblgen quite a bit to get  
> it to even
> accept and generate mostly-correct code for the pattern, I'm going  
> to need a
> little help from the tblgen experts to get this final cleanup  
> accomplished.
> How should that happen?  Does SelectNodeTo need to take care of it?

It should. SelectNodeTo is a wrapper around MorphNodeTo, and MorphNodeTo
has code to check for and remove nodes that become dead, specifically to
address this case. If that's not working, it's a bug.

What version of LLVM are you using here? This is code that has changed
substantially over the last few months. And we've fixed a number of
similar-sounding bugs along the way.

>
> I plan to contribute these enhancements to tblgen back upstrream as  
> they are
> quite useful for doing cool isel stuff.  But I gotta get this case  
> to work
> first.  :)

:-)

Dan