Martin J. O'Riordan via llvm-dev
2018-Mar-06 21:04 UTC
[llvm-dev] Heap Exhaustion during 'DAGCombiner::Run'
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>
Nirav Davé via llvm-dev
2018-Mar-06 21:15 UTC
[llvm-dev] Heap Exhaustion during 'DAGCombiner::Run'
Martin: It sounds like you are doing is more akin to shuffle selection than fusion and therefore it's a better fit for instruction selection than DAGCombining. Try movign it to <Target>ISelDAGToDAG's Select (or potentially PreprocessISelDAG). Th -Nirav On Tue, Mar 6, 2018 at 4:05 PM Martin J. O'Riordan <MartinO at theheart.ie> wrote:> 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> 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/20180306/0d65529f/attachment.html>
Nemanja Ivanovic via llvm-dev
2018-Mar-06 22:29 UTC
[llvm-dev] Heap Exhaustion during 'DAGCombiner::Run'
We do something very similar in the PPC back end. The ISA has a general vector permute (vperm) that any shuffle can be lowered to. But there are also a bunch of specialized permutes that don't require materializing a permute control vector. So what we actually do is a custom legalization for shuffles where we will lower shuffles to various PPC-specific ISD nodes, etc. On Tue, Mar 6, 2018 at 4:15 PM, Nirav Davé via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Martin: > > It sounds like you are doing is more akin to shuffle selection than fusion > and therefore it's a better fit for instruction selection than > DAGCombining. Try movign it to <Target>ISelDAGToDAG's Select (or > potentially PreprocessISelDAG). > > Th > > -Nirav > > > > > On Tue, Mar 6, 2018 at 4:05 PM Martin J. O'Riordan <MartinO at theheart.ie> > wrote: > >> 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> 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 >> >> > _______________________________________________ > 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/20180306/ef38a340/attachment.html>