This is an archive of the discontinued LLVM Phabricator instance.

[GMR] Teach GlobalsModRef to distinguish an important and safe case of no-alias with non-addr-taken globals: they cannot alias a captured pointer.
ClosedPublic

Authored by chandlerc on Jul 22 2015, 5:27 AM.

Details

Summary

If the non-global underlying object would have been a capture were it to
alias the global, we can firmly conclude no-alias. It isn't reasonable
for a transformation to introduce a capture in a way observable by an
alias analysis. Consider, even if it were to temporarily capture one
globals address into another global and then restore the other global
afterward, there would be no way for the load in the alias query to
observe that capture event correctly. If it observes it then the
temporary capturing would have changed the meaning of the program,
making it an invalid transformation. Even instrumentation passes or
a pass which is synthesizing stores to global variables to expose race
conditions in programs could not trigger this unless it queried the
alias analysis infrastructure mid-transform, in which case it seems
reasonable to return results from before the transform started.

See the comments in the change for a more detailed outlining of the
theory here.

This should address the primary performance regression found when the
non-conservatively-correct path of the alias query was disabled.

I haven't yet written a specific test case, but wanted to share the idea
of the technique with others to see if this is sufficiently promising to
be the preferred path forward.

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 30342.Jul 22 2015, 5:27 AM
chandlerc retitled this revision from to [GMR] Teach GlobalsModRef to distinguish an important and safe case of no-alias with non-addr-taken globals: they cannot alias a captured pointer..
chandlerc updated this object.
chandlerc added reviewers: hfinkel, mzolotukhin, pete.
chandlerc added a subscriber: llvm-commits.
chandlerc updated this revision to Diff 30377.Jul 22 2015, 11:36 AM

Replace some ugly and unnecessary code with a cleaner approach.

chandlerc updated this revision to Diff 30555.Jul 23 2015, 8:03 PM

Rebase to ToT

mzolotukhin edited edge metadata.Jul 24 2015, 11:32 AM

Hi Chandler,

I did some preliminary testing again, and it seems that this patch resolves the biggest regressions we saw:

More than 0.5% changes:
=========================================
Benchmark       Old     New     Delta
-----------------------------------------
403.gcc         435.53  415.91  -4.50%
445.gobmk       875.12  866.1   -1.03%
458.sjeng       1045.91 1035.76 -0.97%
=========================================

We observed some other smaller regressions too, but I think my setup is too noisy to detect an effect on them.

Overall the change seems reasonable to me, one question though:

lib/Analysis/IPA/GlobalsModRef.cpp
716–721 ↗(On Diff #30555)

Could you please give an example of how a load from non-global could alias with non-addr-taken global?

I also tested clean compiler with "" and got following results:

More than 0.5% changes:
=========================================
Benchmark       Old     New     Delta
-----------------------------------------
403.gcc         415.91  413.33  -0.62%
429.mcf         388.97  385.67  -0.85%
445.gobmk       866.1   860.82  -0.61%
458.sjeng       1035.76 1071.71  3.47%    <-- probably noisy run
483.xalancbmk   528.78  525.81  -0.56%
=========================================

It means that there are some regressions which didn't recover even with this patch. I think we can investigate them later, after the patch is committed, and they are verified by regular testing.

Thanks for the measurements.

Anyone want to take a look at the code? I'd love an LGTM from someone before submitting.

lib/Analysis/IPA/GlobalsModRef.cpp
716–721 ↗(On Diff #30555)

reg2mem, or spilling an SSA register for some ABI exception handling and then reloading, or any other transformation that uses memory within a function without impacting any other function.

hfinkel accepted this revision.Jul 25 2015, 1:15 PM
hfinkel edited edge metadata.

LGTM, but can we have a test case please?

This revision is now accepted and ready to land.Jul 25 2015, 1:15 PM
hfinkel added inline comments.Jul 25 2015, 3:08 PM
lib/Analysis/IPA/GlobalsModRef.cpp
713 ↗(On Diff #30555)

Also, while I don't think the code here is wrong, the word 'capturing' in the comment could be a bit misleading. The argument in question, for example, could have the 'nocapture' attribute. This is okay, however, because we consider any global's address being passed to a function as having its address taken (even via a nocapture argument).

I think it would be nice for the comment to explain this.

This revision was automatically updated to reflect the committed changes.

As discussed on IRC, I switched the wording to "escaping" as I think that is much more accurate. Sadly, I failed to fully update my change description. Sorry about that.

I did add the basic functional testing that this works. This also should address PR24288 which is another regression reduced out of the change to GMR.

Thanks again for the review!