llvm dev - Oct 2008 - [LLVMdev] Making Sense of ISel DAG Output

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?

                                           -Dave

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.

Dan

Dear all,

I'm trying to run the example of recursive type construction examples  
in LLVM Programmer's Manual, here is the code:

// Create the initial outer struct
PATypeHolder StructTy = OpaqueType::get();
std::vector<const Type*> Elts;
Elts.push_back(PointerType::get(StructTy));
Elts.push_back(Type::Int32Ty);
StructType *NewSTy = StructType::get(Elts);

// At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that
// the struct and the opaque type are actually the same.
cast<OpaqueType>(StructTy.get())->refineAbstractTypeTo(NewSTy);

// NewSTy is potentially invalidated, but StructTy (a PATypeHolder) is
// kept up-to-date
NewSTy = cast<StructType>(StructTy.get());

// Add a name for the type to the module symbol table (optional)
MyModule->addTypeName("mylist", NewSTy);


However, it does not work. The compiler says that the API of  
PointerType::get(PATypeHolder &) does not exist.

It seems that the API has been removed from LLVM trunk.

I'd be very appreciated if you could tell me how to construct  
Recursive Type using the LLVM trunk API.

Thank you very much.

Best,

Haohui
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20081003/3104064a/attachment.html>

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