[MemorySSAUpdater] Mark non-trivial Phi for not to optimize

[zzheng]

Summary

Fix PR36484, as suggested:

<quote>
during moves, mark the direct users of the erased things that were phis as "not to be optimized"
<quote>

[zzheng]

ping?

[efriedma]

Please commit the spelling corrections in lib/Analysis/MemorySSA.cpp separately.

This looks right, but I'm not that familiar with the algorithm; hopefully Daniel will chime in.

include/llvm/Analysis/MemorySSAUpdater.h

65

Can you use AssertingVH<MemoryPHI> here? I don't think you can get any dangling pointers with your algorithm, but it's nice to add some extra checks.

[• dberlin]

This looks right to me (IE if it's wrong, i'm wrong about what will work, it looks implemented correctly)

[george.burgess.iv]

Thanks for the patch!

Just one nit (inline) and a general question: is this new set meant to persist across multiple updates, should the erase in fixupDefs be taking care of everything added in a given query, or should we be clearing it at some point?

(If the answer is "the middle one," would it be easy to assert that the def is empty somewhere?)

Please commit the spelling corrections in lib/Analysis/MemorySSA.cpp separately

+1.

lib/Analysis/MemorySSAUpdater.cpp

329

Nit: Can the count check be removed entirely?

[zzheng]

Addressed comments by Eli and George.

[zzheng]

Just one nit (inline) and a general question: is this new set meant to persist across multiple updates, should the erase in fixupDefs be taking care of everything added in a given query, or should we be clearing it at some point?

(If the answer is "the middle one," would it be easy to assert that the def is empty somewhere?)

At least two GVN-hoist test cases need NonOptPhis be cleared. The patch is scoped at per call of MemorySSAUpdater::moveTo(), so clean-up is placed at the end of this function.

[zzheng]

I'll run a bunch of internal test to validate the patch. I'll commit it after testing if no one objects.

[llvm-commits]

• msg-30867-326.txt162 BDownload

[zzheng]

committed as r329621, spelling errors fixed in r329230

include/llvm/Analysis/MemorySSAUpdater.h

 // the right arguments.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"

 class LLVMContext;
 class raw_ostream;
 
 class MemorySSAUpdater {
 private:
   MemorySSA *MSSA;
   SmallVector<MemoryPhi *, 8> InsertedPHIs;
   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
+  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
 
 public:
   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
   /// below the new def block (and any inserted phis).  RenameUses should be set
   /// to true if the definition may cause new aliases for loads below it.  This
   /// is not the case for hoisting or sinking or other forms of code *movement*.
   /// It *is* the case for straight code insertion.

lib/Analysis/MemorySSAUpdater.cpp

 // Eliminate trivial phis
 // Phis are trivial if they are defined either by themselves, or all the same
 // argument.
 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
 // We recursively try to remove them.
 template <class RangeType>
 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
                                                     RangeType &Operands) {
+  // Bail out on non-opt Phis.
+  if (NonOptPhis.count(Phi))
+    return Phi;
+
   // Detect equal or self arguments
   MemoryAccess *Same = nullptr;
   for (auto &Op : Operands) {
     // If the same or self, good so far
     if (Op == Phi || Op == Same)
       continue;
     // not the same, return the phi since it's not eliminatable by us
     if (Same)

 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
   SmallPtrSet<const BasicBlock *, 8> Seen;
   SmallVector<const BasicBlock *, 16> Worklist;
   for (auto *NewDef : Vars) {
     // First, see if there is a local def after the operand.
     auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
     auto DefIter = NewDef->getDefsIterator();
 
+    // The temporary Phi is being fixed, unmark it for not to optimize.
+    if (MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(NewDef))
+      NonOptPhis.erase(Phi);
+
     // If there is a local def after us, we only have to rename that.
     if (++DefIter != Defs->end()) {
       cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
       continue;
     }
 
     // Otherwise, we need to search down through the CFG.
     // For each of our successors, handle it directly if their is a phi, or
for (auto *NewDef : Vars) {
     }
   }
 }
 
 // Move What before Where in the MemorySSA IR.
 template <class WhereType>
 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                               WhereType Where) {
+  // Mark MemoryPhi users of What not to be optimized.
+  for (auto *U : What->users())
+    if (MemoryPhi *PhiUser = dyn_cast_or_null<MemoryPhi>(U))
+      NonOptPhis.insert(PhiUser);
+
   // Replace all our users with our defining access.
   What->replaceAllUsesWith(What->getDefiningAccess());
 
   // Let MemorySSA take care of moving it around in the lists.
   MSSA->moveTo(What, BB, Where);
 
   // Now reinsert it into the IR and do whatever fixups needed.
   if (auto *MD = dyn_cast<MemoryDef>(What))
     insertDef(MD);
   else
     insertUse(cast<MemoryUse>(What));
+
+  // Clear dangling pointers. We added all MemoryPhi users, but not all
+  // of them are removed by fixupDefs().
+  NonOptPhis.clear();
 }
 
 // Move What before Where in the MemorySSA IR.
 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
   moveTo(What, Where->getBlock(), Where->getIterator());
 }
 
 // Move What after Where in the MemorySSA IR.

test/Transforms/GVNHoist/non-trivial-phi.ll

+; RUN: opt -gvn-hoist %s -S -o - | FileCheck %s
+
+; CHECK: store
+; CHECK-NOT: store
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+define void @f(i8* %p) {
+entry:
+  switch i4 undef, label %if.then30 [
+    i4 4, label %if.end
+    i4 0, label %if.end
+  ]
+
+if.end:
+  br label %if.end19
+
+if.end19:
+  br i1 undef, label %e, label %e.thread
+
+e.thread:
+  store i8 0, i8* %p, align 4
+  br label %if.then30
+
+if.then30:
+  call void @g()
+  unreachable
+
+e:
+  store i8 0, i8* %p, align 4
+  unreachable
+}
+
+declare void @g()