[EarlyCSEwMemorySSA] Fix failure (w/ expensive checks). Need to resetOptimizeUses for replaced instructions.

[asbirlea]

Summary

Reset optimized uses of a replaced instruction in MemorySSA, in order to correctly update it.
Failure only triggers with EXPENSIVE_CHECKS, as we marked verifyClobberSanity as expensive. This may need to be reconsidered and added under the VerifyMemorySSA bool, so we can check such failures in tests.

TODO after this patch: Remove the special handling in removeMSSA, make it a part of MSSA->removeMemoryAccess(Inst).

[asbirlea]

Add test for second failure.

[asbirlea]

Adding third test-case for new failure.

[george.burgess.iv]

Thanks for this!

This may need to be reconsidered and added under the VerifyMemorySSA bool, so we can check such failures in tests

SGTM.

I don't fully understand the failure this is meant to fix; question inline.

lib/Transforms/Scalar/EarlyCSE.cpp

607

Are these part of the fix? :)

630

AFAICT, this removeMemoryAccess should be doing all of the cache invalidation that we need to do. It should boil down to "point all of the memory things pointing at WI (which, on the first iteration, is MA) to the closest dominating MemoryAccess".

This should implicitly reset all cached Def and Use optimizations. Uses, when we want to find the actual optimized access, will start walking from said closest dominating MemoryAccess. Defs will start walking from their defining access.

Is the reset causing problems (e.g. is it somehow causing a Use to be optimized over its actual clobber)? Or is the replacement not causing invalidation? Or am I missing something?

916

(Seeing this without a corresponding MSSA update is somewhat concerning, though I guess it's reasonable to assume that if the instruction is trivially simplified + isn't trivially dead, it's not a memory instruction?)

[george.burgess.iv]

lib/Transforms/Scalar/EarlyCSE.cpp

607

(Oh, now I see the -verify-memoryssa in tests. Is there an easy way to mark the tests as unsupported if assertions aren't enabled? If we're relying on -verify-memoryssa to do everything, and -verify-memoryssa does nothing if assertions are off, ...)

[asbirlea]

Dropping this, since the issue is not resolvable in general AFAICT. Please see D51960.

lib/Transforms/Scalar/EarlyCSE.cpp

private:
   bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
 
   bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
                            Instruction *EarlierInst, Instruction *LaterInst);
 
   void removeMSSA(Instruction *Inst) {
     if (!MSSA)
       return;
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
     // Removing a store here can leave MemorySSA in an unoptimized state by
     // creating MemoryPhis that have identical arguments and by creating
     // MemoryUses whose defining access is not an actual clobber.  We handle the
     // phi case eagerly here.  The non-optimized MemoryUse case is lazily
     // updated by MemorySSA getClobberingMemoryAccess.
     if (MemoryAccess *MA = MSSA->getMemoryAccess(Inst)) {
       // Optimize MemoryPhi nodes that may become redundant by having all the
       // same input values once MA is removed.
       SmallSetVector<MemoryPhi *, 4> PhisToCheck;
       SmallVector<MemoryAccess *, 8> WorkQueue;
       WorkQueue.push_back(MA);
       // Process MemoryPhi nodes in FIFO order using a ever-growing vector since
       // we shouldn't be processing that many phis and this will avoid an
       // allocation in almost all cases.
       for (unsigned I = 0; I < WorkQueue.size(); ++I) {
         MemoryAccess *WI = WorkQueue[I];
 
         for (auto *U : WI->users())
           if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U))
             PhisToCheck.insert(MP);
 
         MSSAUpdater->removeMemoryAccess(WI);
 
         for (MemoryPhi *MP : PhisToCheck) {
           MemoryAccess *FirstIn = MP->getIncomingValue(0);
           if (llvm::all_of(MP->incoming_values(),
                            [=](Use &In) { return In == FirstIn; }))
             WorkQueue.push_back(MP);
         }
         PhisToCheck.clear();
       }
     }
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
   }
 };
 
 } // end anonymous namespace
 
 /// Determine if the memory referenced by LaterInst is from the same heap
 /// version as EarlierInst.
 /// This is currently called in two scenarios:
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     if (Value *V = SimplifyInstruction(Inst, SQ)) {
       LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V
                         << '\n');
       if (!DebugCounter::shouldExecute(CSECounter)) {
         LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
       } else {
         bool Killed = false;
         if (!Inst->use_empty()) {
+          if (MSSA)
+            MSSAUpdater->resetOptimizeUses(Inst);
           Inst->replaceAllUsesWith(V);
           Changed = true;
         }
         if (isInstructionTriviallyDead(Inst, &TLI)) {
           removeMSSA(Inst);
           Inst->eraseFromParent();
           Changed = true;
           Killed = true;
         }
if (SimpleValue::canHandle(Inst)) {
         LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V
                           << '\n');
         if (!DebugCounter::shouldExecute(CSECounter)) {
           LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
           continue;
         }
         if (auto *I = dyn_cast<Instruction>(V))
           I->andIRFlags(Inst);
+        if (MSSA)
+          MSSAUpdater->resetOptimizeUses(Inst);
         Inst->replaceAllUsesWith(V);
         removeMSSA(Inst);
         Inst->eraseFromParent();
         Changed = true;
         ++NumCSE;
         continue;
       }
 
if (MemInst.isValid() && MemInst.isLoad()) {
         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
         if (Op != nullptr) {
           LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
                             << "  to: " << *InVal.DefInst << '\n');
           if (!DebugCounter::shouldExecute(CSECounter)) {
             LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
             continue;
           }
-          if (!Inst->use_empty())
+          if (!Inst->use_empty()) {
+            if (MSSA)
+              MSSAUpdater->resetOptimizeUses(Inst);
             Inst->replaceAllUsesWith(Op);
+          }
           removeMSSA(Inst);
           Inst->eraseFromParent();
           Changed = true;
           ++NumCSELoad;
           continue;
         }
       }
 
if (CallValue::canHandle(Inst)) {
           isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
                               Inst)) {
         LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
                           << "  to: " << *InVal.first << '\n');
         if (!DebugCounter::shouldExecute(CSECounter)) {
           LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
           continue;
         }
-        if (!Inst->use_empty())
+        if (!Inst->use_empty()) {
+          if (MSSA)
+            MSSAUpdater->resetOptimizeUses(Inst);
           Inst->replaceAllUsesWith(InVal.first);
+        }
         removeMSSA(Inst);
         Inst->eraseFromParent();
         Changed = true;
         ++NumCSECall;
         continue;
       }
 
       // Otherwise, remember that we have this instruction.

test/Transforms/EarlyCSE/reduced_gram2_memssa.ll

+;RUN: opt < %s -early-cse-memssa -verify-memoryssa -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Grammar = type { i8*, i8*, %struct.anon }
+%struct.anon = type { i32, i32, %struct.Term**, [3 x %struct.Term*] }
+%struct.Term = type { i32 }
+
+define dso_local fastcc void @new_term_string(%struct.Grammar* %g) unnamed_addr {
+entry:
+  store i8* undef, i8** undef, align 8
+  %0 = load i8*, i8** undef, align 8
+  %arrayidx = getelementptr inbounds i8, i8* %0, i64 undef
+  store i8 0, i8* %arrayidx, align 1
+  %v = getelementptr inbounds %struct.Grammar, %struct.Grammar* %g, i64 0, i32 2, i32 2
+  %1 = load %struct.Term**, %struct.Term*** %v, align 8
+  unreachable
+}
+

test/Transforms/EarlyCSE/reduced_gram_memssa.ll

+; RUN: opt < %s -early-cse-memssa -verify-memoryssa -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Term = type { i32, i32, i32, i32, i32, i8* }
+
+; Function Attrs: nounwind uwtable
+define dso_local fastcc void @new_term_string() unnamed_addr {
+entry:
+  %string = getelementptr inbounds %struct.Term, %struct.Term* undef, i64 0, i32 5
+  store i8* undef, i8** %string, align 8
+  %0 = load i8*, i8** %string, align 8
+  unreachable
+}
+

test/Transforms/EarlyCSE/reduced_macroblock_memssa.ll

+; RUN: opt < %s -early-cse-memssa -verify-memoryssa -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.ImageParameters = type { i32, i32, i32 }
+
+@img = external dso_local local_unnamed_addr global %struct.ImageParameters*, align 8
+
+; Function Attrs: nounwind uwtable
+define dso_local void @write_one_macroblock() local_unnamed_addr {
+entry:
+  ; MemoryUse(LoE)
+  %0 = load %struct.ImageParameters*, %struct.ImageParameters** @img, align 8
+
+  %Pos_2 = getelementptr inbounds %struct.ImageParameters, %struct.ImageParameters* %0, i64 0, i32 2
+  ; 1 = MemoryDef(LoE)
+  store i32 undef, i32* %Pos_2, align 8
+
+  ; MemoryUse(LoE)
+  %1 = load %struct.ImageParameters*, %struct.ImageParameters** @img, align 8
+
+  %Pos_1 = getelementptr inbounds %struct.ImageParameters, %struct.ImageParameters* %1, i64 0, i32 1
+  ; MemoryUse(1) MayAlias
+  %2 = load i32, i32* %Pos_1, align 4
+  unreachable
+}
+
+