This is an archive of the discontinued LLVM Phabricator instance.

[MemorySSA] Support invariant.group metadata
ClosedPublic

Authored by aeubanks on Sep 1 2021, 11:03 PM.

Details

Summary

The implementation is mostly copied from MemDepAnalysis. We want to look
at all loads and stores to the same pointer operand. Bitcasts and zero
GEPs of a pointer are considered the same pointer value. We choose the
most dominating instruction.

Since updating MemorySSA with invariant.group is non-trivial, for now
handling of invariant.group is not cached in any way, so it's part of
the walker. The number of loads/stores with invariant.group is small for
now anyway. We can revisit if this actually noticeably affects compile
times.

To avoid invariant.group affecting optimized uses, we need to have
optimizeUsesInBlock() not use invariant.group in any way.

Co-authored-by: Piotr Padlewski <prazek@google.com>

Diff Detail

Event Timeline

aeubanks created this revision.Sep 1 2021, 11:03 PM
aeubanks requested review of this revision.Sep 1 2021, 11:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2021, 11:03 PM
Prazek accepted this revision.Sep 2 2021, 5:53 AM

Great! We will need to take a look at what NewGVN missed and understand if this is NewGVN fault, or are we missing something on MSSA site.

llvm/unittests/Analysis/MemorySSATest.cpp
1775

UB: Add new line

This revision is now accepted and ready to land.Sep 2 2021, 5:53 AM
nikic added inline comments.Sep 2 2021, 11:53 AM
llvm/lib/Analysis/MemorySSA.cpp
2481

Does the verifier ensure that invariant.group is only attached to loads and stores?

2514

Might make sense to initialize MostDominatingInstruction = &I and then check !DT.dominates(U, MostDominatingInstruction) here and drop GetMostDominatingInstruction?

If we already found a more dominating candidate, then there's no point in exploring uses of less-dominating candidates anymore.

2534

if (getLoadStorePointerOperand(U) == Ptr && U->hasMetadata(...)) would be a bit more future-proof here (regarding a potential future pointer provenance operand), and I think also reads nicer...

2547

I'd call this UseInvariantGroups or so.

llvm/test/Analysis/MemorySSA/invariant-groups.ll
5

Comment needs update.

I haven't yet looked in depth into the code taken from MemDepAnalysis.

Unit test looks good.

llvm/lib/Analysis/MemorySSA.cpp
1061

Add a comment that this API is not visible outside of MemorySSA, due to the MemorySSAWalker interface.

1463

Please add a comment here explaining why this specific API is called in regards to the stack changes below.

2504

Comment needs updating?

2555

Does it make sense to add an assert here the I is either LoadInst or StoreInst?

Also that the returned access is non-null.

aeubanks updated this revision to Diff 370482.Sep 2 2021, 10:43 PM

address comments

aeubanks added inline comments.Sep 2 2021, 10:47 PM
llvm/lib/Analysis/MemorySSA.cpp
2481

now it does :)

2504

I think it's still technically O(N^2) in the worst case, e.g. if we a have a large BB with many loads/stores with invariant.group MD.

2514

good optimization!

nikic added inline comments.Sep 3 2021, 12:54 AM
llvm/lib/Analysis/MemorySSA.cpp
2504

You can iterate directly over Ptr->users() here.

2526

This check is now redundant, already checked above.

2560

If the found load is atomic or volatile, wouldn't it itself be the clobbering access? If yes, we should check whether ClobberMA is a MemoryUse rather than whether it is a load. Not sure whether invariant group semantics somehow preclude this.

llvm/test/Analysis/MemorySSA/invariant-groups.ll
9

Could use a TODO/FIXME comment that this is just a missing optimization, not a correctness test.

Prazek added inline comments.Sep 3 2021, 3:50 AM
llvm/lib/Analysis/MemorySSA.cpp
2514

+1, good one, haven't thought about this.

2560

I think in theory we should be able to optimzie atomic loads with invariant.group md in the same way - if optimizer gets information that 2 loads are loading the same value (because the value is invariant), then it doesn't matter if we read the value atomically.

I am not sure how we handle atomic loads with !invariant.load, but we should be able handle !invariant.group similarly. But because we don't really care about atomic invariant.loads, we could as well just bail out and not consider any of them in the analysis.

About volatile loads: I guess we can't optimize them at all, the best would be to remove all !invariant.group metadata on such loads while canonicalization, but its better to handle this here too.

asbirlea added inline comments.Sep 3 2021, 11:39 AM
llvm/lib/Analysis/MemorySSA.cpp
2517

nit: move the continue outside, in the if(auto* GEP. condition.

2526

+1, remove second if.

2562

You shouldn't need this assert. The defining access cannot be null. Can simplify to:

if (auto *LI = dyn_cast<LoadInst>(I)) 
  return ClobberMA->getDefiningAccess();
aeubanks updated this revision to Diff 370654.Sep 3 2021, 12:50 PM

address comments

aeubanks updated this revision to Diff 370655.Sep 3 2021, 12:51 PM

small test update

Piotr and I looked over the NewGVN test and there were some interesting missed NewGVN optimizations. These seem like things to be fixed on the NewGVN side.

  1. NewGVN was correctly forwarding a stored value to a load, but wasn't calling instsimplify on that. In these cases, we were loading a function from a vtable definition which instsimplify got, but that wasn't happening with newgvn
  2. NewGVN has trouble CSE'ing loads with different pointee types
  3. NewGVN doesn't support assumes in some cases

is this good to go?

asbirlea accepted this revision.Sep 8 2021, 9:38 AM

Yes.

nikic added inline comments.Sep 8 2021, 10:47 AM
llvm/lib/Analysis/MemorySSA.cpp
2487

Shouldn't this skip isa<Constant> in general? I think you could reach here with a constant expression (say an inttoptr expression).

aeubanks updated this revision to Diff 371400.Sep 8 2021, 11:28 AM

isa<Constant>

llvm/lib/Analysis/MemorySSA.cpp
2487

hmm for some reason I thought most Constants had empty use lists, but that's not true

nikic accepted this revision.Sep 8 2021, 11:41 AM

LGTM as well.

llvm/lib/Analysis/MemorySSA.cpp
2487

I believe there's plans to move in that direction, but they haven't been implemented yet. (And I also think they would be more in the direction of trying to fetch users of a constant asserts, than being simply empty.)

This revision was automatically updated to reflect the committed changes.