This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Remove dead node when it is created by getNegatedExpression
ClosedPublic

Authored by steven.zhang on Aug 18 2020, 5:48 PM.

Details

Summary

We hit the infinite loop reported by https://bugs.llvm.org/show_bug.cgi?id=46877 and the reason is the same as D77319. So we need to remove the dead node we created to avoid the sideeffect on DAGCombiner.

Diff Detail

Event Timeline

steven.zhang created this revision.Aug 18 2020, 5:48 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 18 2020, 5:48 PM
steven.zhang requested review of this revision.Aug 18 2020, 5:48 PM
hans added a comment.Aug 19 2020, 2:39 AM

If it avoids an infinite loop, it can't be an NFC change. Is not possible to reduce the original test case?

qiucf added a comment.EditedAug 20 2020, 2:48 AM

The original test case is too big to get something useful. I happened to grab a basic block from it. It's not small enough to be a test, but it would be much easier to analyze: https://reviews.llvm.org/P8230

The original test case is too big to get something useful. I happened to grab a basic block from it. It's not small enough to be a test, but it would be much easier to analyze: https://reviews.llvm.org/P8230

The test shows that we are not actually infinite looping; we are exponentially increasing compile time with each additional set of FMA combines.

If I limit the live code in the test by changing the final store from "store float %288, float* %80, align 4" and time it:

store float %233, float* %80, align 4 --> "time llc" --> user 0m30.640s
store float %229, float* %80, align 4 --> "time llc" --> user 0m19.956s
store float %224, float* %80, align 4 --> "time llc" --> user 0m10.881s
store float %217, float* %80, align 4 --> "time llc" --> user 0m5.750s

I don't know if that changes the solution or the potential test. Maybe we could add or check some debug statement to track the number of nodes created?

The original test case is too big to get something useful. I happened to grab a basic block from it. It's not small enough to be a test, but it would be much easier to analyze: https://reviews.llvm.org/P8230

Thank you for doing this! The test is small enough to demonstrate the problem I think.

The test shows that we are not actually infinite looping; we are exponentially increasing compile time with each additional set of FMA combines.
If I limit the live code in the test by changing the final store from "store float %288, float* %80, align 4" and time it:
store float %233, float* %80, align 4 --> "time llc" --> user 0m30.640s
store float %229, float* %80, align 4 --> "time llc" --> user 0m19.956s
store float %224, float* %80, align 4 --> "time llc" --> user 0m10.881s
store float %217, float* %80, align 4 --> "time llc" --> user 0m5.750s
I don't know if that changes the solution or the potential test. Maybe we could add or check some debug statement to track the number of nodes created?

Good catch. And it also explains more clear on why the fix works as we are removing the unnecessary dead nodes we created that increase the problem size of the DAGCombine. As the final DAG is the same w/o the fix and I am worried the test is easy to be broken if we check the temp node we created, I tend to have chaofang's test to verify we are not increasing the compiling time. Does it make sense ?

And thank you for all your help on the tests!

Add the reduce tests.

steven.zhang retitled this revision from [NFC][DAGCombine] Remove dead node when it is created by getNegatedExpression to [DAGCombine] Remove dead node when it is created by getNegatedExpression.Aug 20 2020, 9:58 PM
steven.zhang edited the summary of this revision. (Show Details)
spatel accepted this revision.Aug 21 2020, 7:42 AM

LGTM

llvm/test/CodeGen/X86/pr46877.ll
1 ↗(On Diff #286936)

I think if we are going to spend the time to execute a test, we might as well use FileCheck to verify the output asm. That way, we can detect if some future patch is doing something unexpected.

This revision is now accepted and ready to land.Aug 21 2020, 7:42 AM
steven.zhang added inline comments.Aug 23 2020, 4:50 PM
llvm/test/CodeGen/X86/pr46877.ll
1 ↗(On Diff #286936)

ok,I will update the test.

hans added a comment.Aug 25 2020, 8:54 AM

Pushed to 11.x as 4d16d8dfe50eb45545e844c3c9acafd363637dad

Please let me know if there are any follow-ups.

uabelho added a subscriber: uabelho.Mar 2 2021, 2:14 AM

Hi,

I wrote https://bugs.llvm.org/show_bug.cgi?id=49393 that seems to start happening with this patch.

It seems that, craig is working on this bugzallia issue. Thank you for reporting this.