[LLVMdev] FoldingSetNodeID operations inefficiency

[Dan Gohman]

On Apr 30, 2008, at 11:13 AM, Roman Levenstein wrote:
>> Do we know where the quadradic FoldingSetNodeID operations are  
>> coming from?
>
> Re-computation of the FoldingSetNodeID hashes takes a lot of time  
> for a node with 3200 operands,
> since the Bits array contains 6400 elements. Moreover, it looks like  
> a temporary data structure is
> allocated for this computation, which also takes time and memory. I  
> still do not quite understand where
> the quadratic factor comes from.

Ok.

>
>
>> Is caching of TokenFactor hash id's effective?
>
> I tried to insert some debugging code to see how efficient are the  
> CSE sets. And my understanding is that we have hits
> only for constants, registers and some other "simple" nodes. I have  
> never seen on my tests e.g. any TokenFactor that would
> be found  in the CSE table  and reused.  If it is the case in  
> general, may be  such nodes should not be put into CSE tables
> at all?

One possible explanation for this is SelectionDAG's conservative  
approach
to memory dependencies, wherein it often has tall sequences of chains  
in the
dependency graph and avoids many cases where nodes might have common
chain operands. As LLVM gets more aggressive in this area, we may  
begin to
see TokenFactors getting CSE'd.

I guess even then it won't be very common though.

>> If you're going to be splitting large TokenFactors, then  
>> theoretically
>> you'd want to use the same ordering that the schedulers would use,
>> such as sorting the loads ascending by addresses or whatever. That
>> might not be very simple though :-}.
>
>
> Well, if the addresses are not constants and have different bases,  
> it may be a bit tricky.

> Or do you have something specific in mind?

We don't need the base ordering to match the full runtime addresses'  
order;
we primarily need to group addresses with common bases together so
that a secondary sort based on ascending offset can be effective.

Dan