This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Prune unnused nodes.
ClosedPublic

Authored by niravd on Feb 11 2019, 12:55 PM.

Details

Summary

Nodes that have no uses are eventually pruned when they are selected
from the worklist. Record nodes newly added to the worklist or DAG and
perform pruning after every combine attempt.

Diff Detail

Repository
rL LLVM

Event Timeline

niravd created this revision.Feb 11 2019, 12:55 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 11 2019, 12:55 PM
niravd updated this revision to Diff 188610.Feb 27 2019, 1:28 PM

Rebase to tip and add FIXME for regression.

RKSimon added inline comments.Feb 27 2019, 1:39 PM
llvm/test/CodeGen/PowerPC/pr39478.ll
10 ↗(On Diff #188610)

This looks like an over-reduced test?

niravd marked an inline comment as done.Feb 28 2019, 8:36 AM
niravd added inline comments.
llvm/test/CodeGen/PowerPC/pr39478.ll
10 ↗(On Diff #188610)

With the improved pruning, we are able to narrow the load to 1 byte which as both the load and store are to undef cancel out the both ops.

RKSimon added inline comments.Feb 28 2019, 9:07 AM
llvm/test/CodeGen/PowerPC/pr39478.ll
10 ↗(On Diff #188610)

I'm hitting issues with this test in D58017 as well, but I'd prefer to see it still do what its supposed to (even if its driving me nuts at the moment....)

IMO we need to replace the undef pointers so it still tests https://bugs.llvm.org/show_bug.cgi?id=39478

nemanjai added inline comments.Mar 4 2019, 3:00 PM
llvm/test/CodeGen/PowerPC/pr39478.ll
10 ↗(On Diff #188610)

I am sorry, I produced this test case by reducing the original input with bugpoint. I can commit an update for it so it doesn't use an undefined pointer as NFC if you'd like so that it stops causing you problems.

jyknight added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
140 ↗(On Diff #188610)

Couldn't this just be represented by an index of the last position in the worklist which has been examined for new-node-prunning, instead of a separate list?

Set it to Worklist.size() after popping entries in getNextWorklistEntry(), and iterate from it to the end of worklist in clearNewUnusedWorklistEntries.

160 ↗(On Diff #188610)

Unused?

205 ↗(On Diff #188610)

Unused?

llvm/test/CodeGen/X86/constant-combines.ll
12–14 ↗(On Diff #188610)

The comment here says this test is now useless.

llvm/test/CodeGen/X86/pr28504.ll
9 ↗(On Diff #188610)

Given this comment, I wonder if this test case is still valid?

llvm/test/CodeGen/X86/pr33844.ll
13 ↗(On Diff #188610)

This looks like it might not be testing what it intended to test anymore, too?

niravd marked 5 inline comments as done.Mar 25 2019, 10:50 AM
niravd added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
140 ↗(On Diff #188610)

Unfortunately, that won't catch all nodes. Nodes added to the worklist may already be in the list and therefore won't be put at the end of the list, but we still need to prune those.

160 ↗(On Diff #188610)

Used at the start of getNextWorklistEntry. I've have it as a helper, because in principle we need to clear dangling nodes after any failed combine as we may have a created a dangling node that will needlessly impede subsequent combines on the same node and we should call it in those cases.

I've added some explanatory comments.

205 ↗(On Diff #188610)

Yes. Pruned.

llvm/test/CodeGen/PowerPC/pr39478.ll
10 ↗(On Diff #188610)

That would be great.

niravd updated this revision to Diff 192150.EditedMar 25 2019, 12:09 PM
niravd marked 3 inline comments as done.

Address some of James' comments.

jyknight added inline comments.Mar 25 2019, 12:13 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
140 ↗(On Diff #188610)

For some reason I had gotten it into my head that this was only important for newly-created nodes, not for all newly-modified nodes, but I see now that's not what this is doing. OK.

160 ↗(On Diff #188610)

I meant the line this comment was attached to -- the local variable "Nodes" looks unused here.

niravd updated this revision to Diff 192453.Mar 27 2019, 9:16 AM
niravd marked 10 inline comments as done.

Address lingering test comments.

niravd updated this revision to Diff 192775.Mar 28 2019, 8:21 PM
niravd retitled this revision from [DAG] Remember nodes added to the worklist for pruning. to [DAGCombine] Prune unnused nodes..
niravd edited the summary of this revision. (Show Details)

Consider inserted nodes for pruning.

jyknight accepted this revision.Mar 29 2019, 9:35 AM

It'd be nice if we knew why adding new nodes to the worklist seemed to cause an issue, but the reduced form as here seems okay as far as it goes.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
696–697 ↗(On Diff #192775)

Might be infinite loop, not exponential time?

This revision is now accepted and ready to land.Mar 29 2019, 9:35 AM
This revision was automatically updated to reflect the committed changes.