Compute live-in for MemorySSA

[• dberlin]

Summary

While working on some unit tests for an optimization, i discovered some cases where live-in computation eliminations useless phis for MemorySSA.
The calculation is cheap, and we can always disable it later, so enable it for now.

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

264

In case the change made here isn't obvious - we used to try to insert the block into the set *for each relevant instruction we found in the block* (IE N attempts per block), and now we only insert it into the set once per block.

[• dberlin]

• Update comment

[majnemer]

This LGTM. An argument could be made, either for or against, that the change to minimize the number of attempts to update DefiningBlocks could be split out.

lib/Transforms/Utils/MemorySSA.cpp

308–313

Any reason not to use the range-based predecessors?
It should make the code a little shorter:

for (BasicBlock *P : predecessors(BB))
  LiveInBlockWorklist.push_back(P);

I guess you could also use append instead:

LiveInBlockWorklist.append(pred_begin(BB), pred_end(BB));

test/Transforms/Util/MemorySSA/livein.ll

27

Would you mind adding a space between that semicolon and the CHECK to match the others?

[george.burgess.iv]

It seems this was committed as r260014. Closing.

lib/Transforms/Utils/MemorySSA.cpp

MemorySSAWalker *MemorySSA::buildMemorySSA(AliasAnalysis *AA,
   BasicBlock &StartingPoint = F.getEntryBlock();
   LiveOnEntryDef = make_unique<MemoryDef>(F.getContext(), nullptr, nullptr,
                                           &StartingPoint, NextID++);
 
   // We maintain lists of memory accesses per-block, trading memory for time. We
   // could just look up the memory access for every possible instruction in the
   // stream.
   SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
-
+  SmallPtrSet<BasicBlock *, 32> DefUseBlocks;
   // Go through each block, figure out where defs occur, and chain together all
   // the accesses.
   for (BasicBlock &B : F) {
+    bool InsertIntoDefUse = false;
+    bool InsertIntoDef = false;
     AccessListType *Accesses = nullptr;
     for (Instruction &I : B) {
       MemoryAccess *MA = createNewAccess(&I, true);
       if (!MA)
         continue;
       if (isa<MemoryDef>(MA))
-        DefiningBlocks.insert(&B);
+        InsertIntoDef = true;
+      else if (isa<MemoryUse>(MA))
+        InsertIntoDefUse = true;
+
       if (!Accesses)
         Accesses = getOrCreateAccessList(&B);
       Accesses->push_back(MA);
     }
+    if (InsertIntoDef)
+      DefiningBlocks.insert(&B);
+    if (InsertIntoDefUse)
+      DefUseBlocks.insert(&B);
+  }
+
+  // Compute live-in.
+  // Live in is normally defined as "all the blocks on the path from each def to
+  // each of it's uses".
+  // MemoryDef's are implicit uses of previous state, so they are also uses.
+  // This means we don't really have def-only instructions.  The only
+  // MemoryDef's that are not really uses are those that are of the LiveOnEntry
+  // variable (because liveonentry can reach anywhere, and every def is a
+  // must-kill of LiveOnEntry).
+  // In theory, you could precisely compute live-in by using alias-analysis to
+  // diambiguate which defs are reached by live on entry (IE not killed by some
+  // def on some path from entry) and which are not. This would tell you which
+  // defs have "uses" that need to be kept alive.
+  // In practice, this would be really expensive and difficult. So we simply
+  // assume all defs are also uses that need to be kept live.
+  // Because of this, the end result of this live-in computation will be "the
+  // entire set of basic blocks that reach any use".
+
+  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
+  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(DefUseBlocks.begin(),
+                                                    DefUseBlocks.end());
+  // Now that we have a set of blocks where a value is live-in, recursively add
+  // predecessors until we find the full region the value is live.
+  while (!LiveInBlockWorklist.empty()) {
+    BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
+
+    // The block really is live in here, insert it into the set.  If already in
+    // the set, then it has already been processed.
+    if (!LiveInBlocks.insert(BB).second)
+      continue;
+
+    // Since the value is live into BB, it is either defined in a predecessor or
+    // live into it to.
+    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+      BasicBlock *P = *PI;
+
+      // Otherwise it is, add to the worklist.
+      LiveInBlockWorklist.push_back(P);
+    }
   }
 
   // Determine where our MemoryPhi's should go
   IDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
+  IDFs.setLiveInBlocks(LiveInBlocks);
   SmallVector<BasicBlock *, 32> IDFBlocks;
   IDFs.calculate(IDFBlocks);
 
   // Now place MemoryPhi nodes.
   for (auto &BB : IDFBlocks) {
     // Insert phi node
     AccessListType *Accesses = getOrCreateAccessList(BB);
     MemoryPhi *Phi = new MemoryPhi(F.getContext(), BB, NextID++);

test/Transforms/Util/MemorySSA/livein.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+define void @F(i8*) {
+  br i1 true, label %left, label %right
+left:
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  store i8 16, i8* %0
+  br label %merge
+right:
+  br label %merge
+
+merge:
+; CHECK-NOT: 2 = MemoryPhi
+ret void 
+}
+
+define void @F2(i8*) {
+  br i1 true, label %left, label %right
+left:
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  store i8 16, i8* %0
+  br label %merge
+right:
+  br label %merge
+
+merge:
+;CHECK: 2 = MemoryPhi({left,1},{right,liveOnEntry})
+%c = load i8, i8* %0
+ret void 
+}