[LLVMdev] Making Sense of ISel DAG Output

[David Greene]

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?

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.  :)

                                                       -Dave