llvm dev - Mar 2018 - Heap Exhaustion during 'DAGCombiner::Run'

Hi LLVM-Devs,

I am in the process of updating our out-of-tree implementation from v5.0 to
v6.0 RC3, and while it builds and mostly runs, I am having trouble with a
small number of tests where the 'WorklistMap' in
'DAGCombiner::Run' never
becomes empty.  This is resulting in a runaway state of continuous heap
allocation until the process exhausts all system memory.

But I can't get a handle on why it is doing this, and it is not obvious to
me that the changes between v5.0 and v6.0 RC3 invalidate our implementation
in a way that might cause this.  The only time I see our code entered is
when lowering is called for vector element insert by 'LegalizeOp'.  Does
anybody have an advice on how I should approach debugging this?

Thanks,

	MartinO

Martin:

I suspect this is an issue with post-DAG legalization store merging in the
DAGCombiner. If you have a custom lowered type the DAGCombiner may end up
merging a set of stores and immediately splitting them up in legalization.
You should be able to disable this pass universally by overriding
mergeStoresAfterLegalization() or conditionally for cases that shouldn't
match with canMergeStoresTo.

You should able able to verify by finding the loop of nodes considered with
"-debug" on.

-Nirav




On Sun, Feb 25, 2018 at 9:36 AM Martin J. O'Riordan via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi LLVM-Devs,
>
> I am in the process of updating our out-of-tree implementation from v5.0 to
> v6.0 RC3, and while it builds and mostly runs, I am having trouble with a
> small number of tests where the 'WorklistMap' in
'DAGCombiner::Run' never
> becomes empty.  This is resulting in a runaway state of continuous heap
> allocation until the process exhausts all system memory.
>
> But I can't get a handle on why it is doing this, and it is not obvious
to
> me that the changes between v5.0 and v6.0 RC3 invalidate our implementation
> in a way that might cause this.  The only time I see our code entered is
> when lowering is called for vector element insert by 'LegalizeOp'. 
Does
> anybody have an advice on how I should approach debugging this?
>
> Thanks,
>
>         MartinO
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180301/62c105ca/attachment.html>

Thanks for this advice Nirav.  I have only just returned to working on this
after being side-tracked to other tasks.

 

All the best,

 

            MartinO

 

From: Nirav Davé [mailto:niravd at google.com] 
Sent: 01 March 2018 20:45
To: MartinO at theheart.ie
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Heap Exhaustion during 'DAGCombiner::Run'

 

Martin:

 

I suspect this is an issue with post-DAG legalization store merging in the
DAGCombiner. If you have a custom lowered type the DAGCombiner may end up
merging a set of stores and immediately splitting them up in legalization. You
should be able to disable this pass universally by overriding
mergeStoresAfterLegalization() or conditionally for cases that shouldn't
match with canMergeStoresTo.

 

You should able able to verify by finding the loop of nodes considered with
"-debug" on.

 

-Nirav

 

 

 

On Sun, Feb 25, 2018 at 9:36 AM Martin J. O'Riordan via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >
wrote:

Hi LLVM-Devs,

I am in the process of updating our out-of-tree implementation from v5.0 to
v6.0 RC3, and while it builds and mostly runs, I am having trouble with a
small number of tests where the 'WorklistMap' in
'DAGCombiner::Run' never
becomes empty.  This is resulting in a runaway state of continuous heap
allocation until the process exhausts all system memory.

But I can't get a handle on why it is doing this, and it is not obvious to
me that the changes between v5.0 and v6.0 RC3 invalidate our implementation
in a way that might cause this.  The only time I see our code entered is
when lowering is called for vector element insert by 'LegalizeOp'.  Does
anybody have an advice on how I should approach debugging this?

Thanks,

        MartinO


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> 
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180305/8f41de7c/attachment.html>

We discovered what is happening.

 

SDAGCombiner essentially looks at various combinations of nodes to do with
vectors, and when it can, it creates a vector shuffle.  The problem is, that our
vector shuffle lowering builds new trees with vector element, or vector
sub-vector insert sequences.  The generic DAGCombiner, reconstructs these into a
new shuffle, and so the loop continues - we reduce it, and DAGCombiner
re-abstracts it.

 

Our shuffle lowering produces (produced) very optimal code sequences for our
target, and has not been changed significantly since LLVM v3.4; but changes
between v5.0 and v6.0 have introduced this DAG reduction dependency loop.

 

Is there any advice to Out-of-Tree implementations about how to re-write their
lowering code for shuffle so as to avoid this kind of infinite dependency
coupling?

 

Thanks,

 

    MartinO

 

From: Nirav Davé [mailto:niravd at google.com] 
Sent: 01 March 2018 20:45
To: MartinO at theheart.ie
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Heap Exhaustion during 'DAGCombiner::Run'

 

Martin:

 

I suspect this is an issue with post-DAG legalization store merging in the
DAGCombiner. If you have a custom lowered type the DAGCombiner may end up
merging a set of stores and immediately splitting them up in legalization. You
should be able to disable this pass universally by overriding
mergeStoresAfterLegalization() or conditionally for cases that shouldn't
match with canMergeStoresTo.

 

You should able able to verify by finding the loop of nodes considered with
"-debug" on.

 

-Nirav

 

 

 

On Sun, Feb 25, 2018 at 9:36 AM Martin J. O'Riordan via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >
wrote:

Hi LLVM-Devs,

I am in the process of updating our out-of-tree implementation from v5.0 to
v6.0 RC3, and while it builds and mostly runs, I am having trouble with a
small number of tests where the 'WorklistMap' in
'DAGCombiner::Run' never
becomes empty.  This is resulting in a runaway state of continuous heap
allocation until the process exhausts all system memory.

But I can't get a handle on why it is doing this, and it is not obvious to
me that the changes between v5.0 and v6.0 RC3 invalidate our implementation
in a way that might cause this.  The only time I see our code entered is
when lowering is called for vector element insert by 'LegalizeOp'.  Does
anybody have an advice on how I should approach debugging this?

Thanks,

        MartinO


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> 
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180306/ea1144d4/attachment.html>