[AA][Intrinsics] Add separate_storage assumptions.

[davidtgoldblatt]

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.

[davidtgoldblatt]

Updating per review comments.

[lebedev.ri]

Missing langref changes.

[davidtgoldblatt]

Add langref change for separate_storage attribute.

[nikic]

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]

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?

[davidtgoldblatt]

Per review comments.

[davidtgoldblatt]

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.

[davidtgoldblatt]

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

[nikic]

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.

[davidtgoldblatt]

Movie logic into BasicAA.

[davidtgoldblatt]

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]

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.

[nikic]

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.

[davidtgoldblatt]

Fix langref nit, use update_test_checks.py.

[davidtgoldblatt]

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