This is an archive of the discontinued LLVM Phabricator instance.

[AA][Intrinsics] Add separate_storage assumptions.
ClosedPublic

Authored by davidtgoldblatt on Oct 21 2022, 4:37 PM.

Details

Summary

This operand bundle on an assume informs alias analysis that the
arguments point to regions of memory that were allocated separately
(i.e. different heap allocations, different allocas, or different
globals).

As a safety measure, we leave the analysis flag-disabled by default.

Diff Detail

Event Timeline

Matt added a subscriber: Matt.Oct 25 2022, 11:18 AM
davidtgoldblatt retitled this revision from [Intrinsics] Add 'llvm.experimental.separate.storage' intrinsic to [AA][Intrinsics] Add separate_storage assumptions..
davidtgoldblatt edited the summary of this revision. (Show Details)

Updating per review comments.

davidtgoldblatt published this revision for review.Nov 17 2022, 4:52 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 17 2022, 4:52 PM

Missing langref changes.

Add langref change for separate_storage attribute.

nikic added inline comments.Dec 6 2022, 3:38 AM
llvm/include/llvm/IR/Attributes.td
183 ↗(On Diff #478393)

It doesn't make sense to add an actual attribute for this. This would allow you to write something like define foo(ptr separate_storage %arg), and what is that supposed to mean?

We should allow separate_storage as an assume operand bundled only -- there's not fundamental reason why these bundled have to map onto attributes. That's just all we needed historically.

nikic added inline comments.Dec 6 2022, 5:43 AM
llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp
53 ↗(On Diff #478393)

I don't think Loc without pointer is legal in this context. Should be fine to drop this check.

58 ↗(On Diff #478393)

Hm, I wonder if we can use assumptionsFor() here?

Per review comments.

davidtgoldblatt marked 2 inline comments as done.Dec 8 2022, 6:15 PM
davidtgoldblatt added inline comments.
llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp
58 ↗(On Diff #478393)

I think eventually we should be able to, but there's two things that make this tricky:

  • I think the AssumptionCache assumes that the only value that matters for assumptionsFor is the first one (because of the param attribute background?), which would introduce a weird asymmetry in how we can use it.
  • We care about the comparison after a getUnderlyingObject call, but the AssumptionCache doesn't trace through GEPs in findAffectedValues.

(plausibly other issues; I checked that naive attempts at assumptionsFor didn't work, but didn't dig as much into the why).

I think the right thing to do eventually is to rewrite the hints during InstCombine (which should fix issue 2 as well as just speeding things up), but figured it didn't make sense to add extra complication to the AssumptionCache to fix 1 until that was done.

Fix the LangRef changes -- left some junk lying around.

nikic added a comment.Dec 9 2022, 12:00 AM

This looks basically fine to me. My one remaining concern here is compile-time impact. Adding a new SeparateStorageAliasAnalysis pass does add some overhead even if these assumptions are not used (the last two patches add about 0.2% overhead). I think we might be better off just folding this code into BasicAA at an appropriate place, which also saves a good bit of boilerplate.

llvm/docs/LangRef.rst
2514

Spurious newline.

2532

Spurious indent.

2599

Spurious newline

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp
58 ↗(On Diff #478393)

My thinking was that we add the underlying object as the affected value in the assumption cache, but your suggestion to strip that away in InstCombine does sound better.

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll
1 ↗(On Diff #481492)

I don't think you need to specify aa-pipeline here, it's in the default pipeline.

3 ↗(On Diff #481492)

Data layout not necessary.

7 ↗(On Diff #481492)

It would be preferable to make this an aa-eval test, to test AA directly, rather than a pass using it.

Movie logic into BasicAA.

davidtgoldblatt marked 6 inline comments as done.Dec 9 2022, 3:50 PM
davidtgoldblatt added inline comments.
llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll
7 ↗(On Diff #481492)

This is a little hard in the aa-eval of today because of the flow-sensitivity; it can't just print out yes/no/maybe results for all pairs of pointers; it would have to do so out all program locations too. TBAA has a similar sort of issue, uses the same "use gvn to check effects rather than results" trick to get around it too.

The only aa-eval improvements I could think of were:

  • Do the cubic-size "print AA result for every pair of pointers at every program location" output under a flag
  • Have some sort of magic "print aa-eval results at this location" function

Both of which seemed like overkill, although I suppose the first is manageable so long as we make sure to keep any test cases sufficiently compact. WDYT?

nikic accepted this revision.Dec 10 2022, 1:43 AM

LGTM

llvm/docs/LangRef.rst
2582

nit: double space

llvm/test/Analysis/BasicAA/separate_storage.ll
1

Please use update_test_checks.py to generate CHECK lines.

This revision is now accepted and ready to land.Dec 10 2022, 1:43 AM
nikic added inline comments.Dec 10 2022, 1:44 AM
llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll
7 ↗(On Diff #481492)

We could add a mode to print ModRef results rather than AliasResults (like we do for calls). But I think your current test is fine.

Fix langref nit, use update_test_checks.py.

Rebase, futz with parent diffs in arc for wenlei@.

This revision was landed with ongoing or failed builds.Dec 16 2022, 11:05 AM
This revision was automatically updated to reflect the committed changes.
fhahn added a subscriber: fhahn.Aug 14 2023, 4:53 AM

What's the plan for flipping the default for EnableSeparateStorageAnalysis?