llvm dev - May 2014 - [LLVMdev] Testcases where GVN uses too much memory?

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-GVN-Avoid-BumpPtrAllocator-leak-in-performPRE.patch
Type: application/octet-stream
Size: 4546 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140502/72eb1a26/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-GVN-Don-t-shuffle-entries-in-replaceInLeaderTable.patch
Type: application/octet-stream
Size: 1994 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140502/72eb1a26/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-GVN-Optimize-Expression-for-size.patch
Type: application/octet-stream
Size: 8228 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140502/72eb1a26/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-GVN-Change-from-a-linked-list-to-a-vector.patch
Type: application/octet-stream
Size: 8346 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140502/72eb1a26/attachment-0003.obj>

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

On 2014 May 2, at 21:22, Owen Anderson <resistor at mac.com> wrote:
>> 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.
Right, it's already optimized for the common case.  My goal was to leave
the common case about the same, but improve the rare case.  When GVN
"blows up", is it just a really big common case, or are entries in
`LeaderTable` with 3+ elements dominating the memory footprint?

After this patch:

  - The memory footprint of the common case is unchanged: if there's
    only one element, then it's still 24B stored in-line with no
    additional allocation.  However, runtime speed is probably slower
    because of the branch to check where the storage is.  (How much
    slower?)

  - In the rare two element case, there's one allocation of 32B instead
    of one allocation of 24B.  Depending on the malloc, this might be
    equivalent, or might be more expensive.  Runtime speed to visit them
    should be dominated by the single dereference in both cases.

  - In the rare 3+ element case, there's 1 x N*16B allocation instead of
    (N-1) x 24B allocations.  This is where the patch might add value
    (both memory footprint and runtime speed).

But it's speculative enough that it's needs supporting data.
> On May 2, 2014, at 5:56 PM, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> 
>> Does anyone have a specific testcase where GVN uses gobs of memory?