[LLVMdev] Testcases where GVN uses too much memory?

[Owen Anderson]

Hi Duncan,

> Each element in `LeaderTable` was an intrusively linked list of
> `LeaderTableEntry`, with each element of the list costing 24B (assuming
> 64-bit pointers).
> 
>   - Remove the link from `LeaderTableEntry`, slimming it down to 16B.
> 
>   - Replace the linked list with a hand-rolled vector, with size and
>     capacity each represented using `uint32_t`.
> 
> If the list has a single entry, it still costs 24B and does not require
> a dereference.  If it has more than one element, it mallocs an array and
> costs 24B plus 16B per entry.
> 
> Since the entries will be next to each other in memory, we get a
> locality savings here.

I don’t follow the logic here.  My recollection is that the common case is a single element in the list, for which the data structure is already optimized: the head element (not a pointer, but the actual element) is stored in-line with the LeaderTable itself, requiring no additional allocation at all.

—Owen

On May 2, 2014, at 5:56 PM, Duncan P. N. Exon Smith <dexonsmith at apple.com> wrote:

> I've heard a few times, "GVN uses too much memory."  The real fix
> is probably a rewrite of some sort, but that's not what this email
> is about.
> 
> I have a few patches that should *incrementally* reduce its memory
> usage.  Keyword being "should", because I haven't observed an
> improvement... in fact, I haven't seen it using much memory at all.
> 
> Does anyone have a specific testcase where GVN uses gobs of memory?
> 
> I heard a rumour that gambitc can repro this, but I don't have time
> right now to look for and isolate a testcase.  If someone else has
> one handy, I'd appreciate if you could send it across.
> 
> <0001-GVN-Avoid-BumpPtrAllocator-leak-in-performPRE.patch><0002-GVN-Don-t-shuffle-entries-in-replaceInLeaderTable.patch><0003-GVN-Optimize-Expression-for-size.patch><0004-GVN-Change-from-a-linked-list-to-a-vector.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev