This is an archive of the discontinued LLVM Phabricator instance.

[AA][Intrinsics] Add separate_storage assumptions.

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



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

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 '' 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
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
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.
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.


Spurious newline.


Spurious indent.


Spurious newline

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.

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.
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



nit: double space


Please use 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
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

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?