This is an archive of the discontinued LLVM Phabricator instance.

[GVN] Strengthen the updating of dominated users
AbandonedPublic

Authored by jonpa on Nov 19 2020, 5:14 AM.

Details

Summary

This is a first effort to replace https://reviews.llvm.org/D90231, which aimed to exclude @llvm.is.constant() from value replacements. Instead, this patch takes the approach of improving GVN so that the failed test case compiles.

propagateEquality() calls replaceDominatedUsesWith() at the point where one Value can replace another one as long as it is dominated from a certain point. This patch makes sure that also the cases where a user that is not dominated by any such call can still be updated if all of its (parents) predecessors are dominated by such an equivalence. In other words, if there are multiple calls to replaceDominatedUsesWith() at different points with the same equivalency, they may together dominate a user.

This is needed to be able to compile Linux Kernel code with multiple __builtin_constant_p calls.

Diff Detail

Event Timeline

jonpa created this revision.Nov 19 2020, 5:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 19 2020, 5:14 AM
jonpa added a comment.Nov 19 2020, 5:59 AM

This seems to have very limited impact on GVN in general: In total, only 3 branches and 2 comparisons less on SPEC 2017 (SystemZ). This means that the patch could probably be reduced to more specifically handle the builtin_constant_p case and not much more...

llvm/lib/Transforms/Utils/Local.cpp
2670

can probably use a range for here, too.

2677

can be range based for via predecessors(UBB).

As of D90231 i'm personally still unconvinced that it is the LLVM code that needs fixing and not the particular code that is using __builtin_constant_p().

jonpa updated this revision to Diff 310007.Dec 7 2020, 1:41 PM
jonpa marked 2 inline comments as done.

Patch updated per review, and also improved to handle even more cases by iteratively accumulating the dominance. This is needed in order to handle the same example with a sanitizer enabled, which inserts new blocks before the inline asm call (see new test case @fun1).

I factored out a dominates(BB) function into the DominanceSources class. I thought about also putting an "accumulateDomince()" method there, but for now that is done directly in replaceDominatedUsesWith().

As of D90231 i'm personally still unconvinced that it is the LLVM code that needs fixing and not the particular code that is using __builtin_constant_p().

The s390 Linux kernel code in question here is (IMO) undoubtedly impractical, but it seems they have their reasons for that and it would be very helpful if clang could support it, or it seems clang can't be used for the Linux kernel on SystemZ, which would be a shame.

jonpa added a comment.Dec 8 2020, 8:47 AM

I have it now confirmed that this patch fixes the kernel issues on SystemZ: "This patch seems to fix all the kernel build issues. It builds, it runs, all looks good...".

As of D90231 i'm personally still unconvinced that it is the LLVM code that needs fixing and not the particular code that is using __builtin_constant_p().

^ still am.
Are langref changes needed to justify these optimization changes?

jonpa abandoned this revision.Jan 15 2021, 8:57 AM

As of D90231 i'm personally still unconvinced that it is the LLVM code that needs fixing and not the particular code that is using __builtin_constant_p().

^ still am.
Are langref changes needed to justify these optimization changes?

The reason was that this code was somehow the result of some kind of generated code via macros that happened to turn out a certain way, I guess. However, the developers have now decided to change this after all to use builtin calls instead.

So you were right, and I abandon this now given that this doesn't give much as a general improvement... Thanks for review.

I wonder if I perhaps should add a small comment somewhere in GVN.cpp that this has been tried without much benefit?