[MemorySSA] Add OptimizeUses flag

[Prazek]

Summary

This will help much in testing updating
of memory accesses with invariant.group in the future.

[• dberlin]

Please, no.
If you need a flag, please make a hidden command line flag.

This should not be user controllable.

[Prazek]

In D30344#685994, @dberlin wrote:

Please, no.
If you need a flag, please make a hidden command line flag.

This should not be user controllable.

Is there a way to pass command line flag in unit tests?
I will have to write a couple of tests using invariant.group, and I would like to avoid hacky tricks like in this test, which would make it simpler.

[• dberlin]

Could you explain the issue with optimizing uses that is making it hard to write tests?
I mean, at worst we could add a protected constructor, but i'd like to understand the underlying issue first.

[• dberlin]

(because otherwise, you aren't testing the thing that users use :P)

[Prazek]

In D30344#686029, @dberlin wrote:

Could you explain the issue with optimizing uses that is making it hard to write tests?
I mean, at worst we could add a protected constructor, but i'd like to understand the underlying issue first.

I would like to make the walker smart enough to optimize invariant.group as good as in OptimizeUses.
If invariant.group attributest will be set before buildin mssa, then it will be optimized by UseOptimizer
The only way to test it right now is either:

• create loads/stores, setup memory ssa, add invariant.group
• setup mssa, start adding new stores and loads with invariant.group

[• dberlin]

Can't you just call setDefiningAccess on the uses in question to set them?

[Prazek]

In D30344#686088, @dberlin wrote:

Can't you just call setDefiningAccess on the uses in question to set them?

Not sure what do you mean, so I will describe it with more details with new resaon.

I want to have separate list (or other strusture) having only memory accesses with invariant group.
I would like to make a unit test to check if getClobberingAccess returns the best memory def without help of OptimizeUses.

creating instructions, building mssa, then setting up invariant group attributes, and then calling getClobberingAccess won't work, because the link list for invariant groups will be empty (unless mssa would have method like "addInvariantGroupToMemoryAccess", which we probably don't want to have, because no passes should need it.

other way is to create mssa; create instructions with invariant group; insert each instruction into mssa; then call getClobberingAccess, but this seems to be more painfull, than just:

create instructions with invariant group; create mssa WITHOUT optimizing uses; test getClobberingAccess

[• dberlin]

In D30344#686639, @Prazek wrote:

In D30344#686088, @dberlin wrote:

Can't you just call setDefiningAccess on the uses in question to set them?

Not sure what do you mean, so I will describe it with more details with new resaon.

i mean if the uses are getting optimized, you can just reset them to their original access.

I want to have separate list (or other strusture) having only memory accesses with invariant group.

I'm not strongly opposed, but it'd have to have a good reason.
This strikes me as invariant.group possibly not being well designed if we have to do this to make it work well in something that actually wants to process them en-masse.
But i'll set that aside.

I would like to make a unit test to check if getClobberingAccess returns the best memory def without help of OptimizeUses.

Okay.

So just call setDefiningAccess on the use and reset it to the nearest store.

creating instructions, building mssa, then setting up invariant group attributes, and then calling getClobberingAccess won't work, because the link list for invariant groups will be empty

The optimal way to test would seem to me to be:
create instructions, add invariant group attributes, build memoryssa, store away,what things optimized, reset defining access on each load to nearest store, call get clobbering access, compare that we got exactly same result as we did before.

THis verifies both ways give the same results.

What am i missing?

other way is to create mssa; create instructions with invariant group; insert each instruction into mssa; then call getClobberingAccess, but this seems to be more painfull, than just:

Why is this more painful?
It's almost certainly <100 lines of code, and even then, can be done trivially with a simpler helper function.

create instructions with invariant group; create mssa WITHOUT optimizing uses; test getClobberingAccess

Except you aren't testing a thing that a user would use here?
You are also basically embedded strong knowledge about MSSA into your test.
What if i added a trivial optimizer during renaming or otherwise change the linking?
Now your test breaks.
Whereas, if you take the "painful" approach, it just always works.
Or if you just set the test up to be the way you want it, using setDefiningAccess, it will also always work.

I would strongly prefer one of these two methods over trying to control, internally, for testing, what memoryssa does, with flags you pass during building it.

include/llvm/Transforms/Utils/MemorySSA.h

 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
 
 class MemorySSAWalker;
 
 /// \brief Encapsulates MemorySSA, including all data associated with memory
 /// accesses.
 class MemorySSA {
 public:
-  MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
+  MemorySSA(Function &, AliasAnalysis *, DominatorTree *,
+            bool OptimizeUses = true);
   ~MemorySSA();
 
   MemorySSAWalker *getWalker();
 
   /// \brief Given a memory Mod/Ref'ing instruction, get the MemorySSA
   /// access associated with it. If passed a basic block gets the memory phi
   /// node that exists for that block, if there is one. Otherwise, this will get
   /// a MemoryUseOrDef.
void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
 
 private:
   class CachingWalker;
   class OptimizeUses;
 
   CachingWalker *getWalkerImpl();
-  void buildMemorySSA();
+  void buildMemorySSA(bool OptimizeUses);
   void optimizeUses();
 
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
   using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
 
   void
   determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);

lib/Transforms/Utils/MemorySSA.cpp

for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
     if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI))
       UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
     else
       Accesses->erase(AI);
     AI = Next;
   }
 }
 
-MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT)
+MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT,
+                     bool OptimizeUses)
     : AA(AA), DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr),
       NextID(INVALID_MEMORYACCESS_ID) {
-  buildMemorySSA();
+  buildMemorySSA(OptimizeUses);
 }
 
 MemorySSA::~MemorySSA() {
   // Drop all our references
   for (const auto &Pair : PerBlockAccesses)
     for (MemoryAccess &MA : *Pair.second)
       MA.dropAllReferences();
 }
std::sort(IDFBlocks.begin(), IDFBlocks.end(),
               return BBNumbers.lookup(A) < BBNumbers.lookup(B);
             });
 
   // Now place MemoryPhi nodes.
   for (auto &BB : IDFBlocks)
     createMemoryPhi(BB);
 }
 
-void MemorySSA::buildMemorySSA() {
+void MemorySSA::buildMemorySSA(bool DoOptimizeUses) {
   // We create an access to represent "live on entry", for things like
   // arguments or users of globals, where the memory they use is defined before
   // the beginning of the function. We do not actually insert it into the IR.
   // We do not define a live on exit for the immediate uses, and thus our
   // semantics do *not* imply that something with no immediate uses can simply
   // be removed.
   BasicBlock &StartingPoint = F.getEntryBlock();
   LiveOnEntryDef = make_unique<MemoryDef>(F.getContext(), nullptr, nullptr,
void MemorySSA::buildMemorySSA(bool DoOptimizeUses) {
   // filled in with all blocks.
   SmallPtrSet<BasicBlock *, 16> Visited;
   renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
 
   CachingWalker *Walker = getWalkerImpl();
 
   // We're doing a batch of updates; don't drop useful caches between them.
   Walker->setAutoResetWalker(false);
+  if (DoOptimizeUses)
     OptimizeUses(this, Walker, AA, DT).optimizeUses();
   Walker->setAutoResetWalker(true);
   Walker->resetClobberWalker();
 
   // Mark the uses in unreachable blocks as live on entry, so that they go
   // somewhere.
   for (auto &BB : F)
     if (!Visited.count(&BB))
       markUnreachableAsLiveOnEntry(&BB);

unittests/Transforms/Utils/MemorySSA.cpp

struct TestAnalyses {
     AssumptionCache AC;
     AAResults AA;
     BasicAAResult BAA;
     // We need to defer MSSA construction until AA is *entirely* set up, which
     // requires calling addAAResult. Hence, we just use a pointer here.
     std::unique_ptr<MemorySSA> MSSA;
     MemorySSAWalker *Walker;
 
-    TestAnalyses(MemorySSATest &Test)
+    TestAnalyses(MemorySSATest &Test, bool OptimizeMSSAUses)
         : DT(*Test.F), AC(*Test.F), AA(Test.TLI),
           BAA(Test.DL, Test.TLI, AC, &DT) {
       AA.addAAResult(BAA);
-      MSSA = make_unique<MemorySSA>(*Test.F, &AA, &DT);
+      MSSA = make_unique<MemorySSA>(*Test.F, &AA, &DT, OptimizeMSSAUses);
       Walker = MSSA->getWalker();
     }
   };
 
   std::unique_ptr<TestAnalyses> Analyses;
 
-  void setupAnalyses() {
+  void setupAnalyses(bool OptimizeMSSAUses = true) {
     assert(F);
-    Analyses.reset(new TestAnalyses(*this));
+    Analyses.reset(new TestAnalyses(*this, OptimizeMSSAUses));
   }
 
 public:
   MemorySSATest()
       : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
 };
 
 TEST_F(MemorySSATest, CreateALoad) {
TEST_F(MemorySSATest, PartialWalkerCacheWithPhis) {
   EXPECT_EQ(BottomClobber, Phi);
 
   // This query will first check the cache for {%a, BStore}. It should point to
   // FirstStore, not to the store after FirstStore.
   MemoryAccess *UseClobber = Walker->getClobberingMemoryAccess(ALoad);
   EXPECT_EQ(UseClobber, MSSA.getMemoryAccess(FirstStore));
 }
 
-// Test that our walker properly handles loads with the invariant group
-// attribute. It's a bit hacky, since we add the invariant attribute *after*
-// building MSSA. Otherwise, the use optimizer will optimize it for us, which
-// isn't what we want.
-// FIXME: It may be easier/cleaner to just add an 'optimize uses?' flag to MSSA.
+// Test that our walker properly handles loads with the `invariant.load`
+// attribute.
 TEST_F(MemorySSATest, WalkerInvariantLoadOpt) {
   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
                        GlobalValue::ExternalLinkage, "F", &M);
   B.SetInsertPoint(BasicBlock::Create(C, "", F));
   Type *Int8 = Type::getInt8Ty(C);
   Constant *One = ConstantInt::get(Int8, 1);
   Value *AllocA = B.CreateAlloca(Int8, One, "");
 
   Instruction *Store = B.CreateStore(One, AllocA);
   Instruction *Load = B.CreateLoad(AllocA);
+  Load->setMetadata(LLVMContext::MD_invariant_load, MDNode::get(C, {}));
 
-  setupAnalyses();
+  setupAnalyses(/*OptimizeMSSAUses*/ false);
   MemorySSA &MSSA = *Analyses->MSSA;
   MemorySSAWalker *Walker = Analyses->Walker;
 
   auto *LoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(Load));
   auto *StoreMA = cast<MemoryDef>(MSSA.getMemoryAccess(Store));
   EXPECT_EQ(LoadMA->getDefiningAccess(), StoreMA);
 
   // ...At the time of writing, no cache should exist for LoadMA. Be a bit
   // flexible to future changes.
   Walker->invalidateInfo(LoadMA);
-  Load->setMetadata(LLVMContext::MD_invariant_load, MDNode::get(C, {}));
 
   MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LoadMA);
   EXPECT_EQ(LoadClobber, MSSA.getLiveOnEntryDef());
 }
 
 // Test loads get reoptimized properly by the walker.
 TEST_F(MemorySSATest, WalkerReopt) {
   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),