[NewGVN] When a store becomes the leader, update the memory leader for the class

[davide]

Summary

When we change the leader to a store:

Changing leader of congruence class 6 from   %2 = load i32, i32* %d, align 4 to    store i32 %1, i32* %d, align 4 because store joined class

we don't update the memory leader so later, when trying to process a load

Setting 2 = MemoryDef(6) equivalent to congruence class 6 with current MemoryAccess leader 7 = MemoryPhi({for.body,2},{if.then,3})
Erasing expression 0x44014f0 from table
Processing MemoryPhi 7 = MemoryPhi({for.body,2},{if.then,3})
Memory Phi value numbered to 3 = MemoryDef(7)
Setting 7 = MemoryPhi({for.body,2},{if.then,3}) equivalent to congruence class 8 with current MemoryAccess leader 3 = MemoryDef(7)
Processing instruction   %2 = load i32, i32* %d, align 4

we crash while looking up the memory leader for the class

opt: ../lib/Transforms/Scalar/NewGVN.cpp:1048: const llvm::MemoryAccess* {anonymous}::NewGVN::lookupMemoryLeader(const llvm::MemoryAccess*) const: Assertion `CC->getMemoryLeader() && "Every MemoryAccess should be mapped to a " "congruence class with a represenative memory " "access"' failed.

[• dberlin]

I'm pretty sure this is wrong.
I'll look into it as soon as i get this machine back together.
We actually do set the leader.
Or at least, we should -

As the code says:

// We rely on the code below handling the MemoryAccess change.

We call moveMemoryToNewCongruenceClass below this which does:

// First, see what happens to the new class
if (!NewClass->getMemoryLeader()) {
  // Should be a new class, or a store becoming a leader of a new class.
  assert(NewClass->size() == 1 ||
         (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
  NewClass->setMemoryLeader(InstMA);

This should give NewClass a memory leader when the store becomes a leader.

[davide]

In D33056#751288, @dberlin wrote:

I'm pretty sure this is wrong.
I'll look into it as soon as i get this machine back together.
We actually do set the leader.
Or at least, we should -

As the code says:

// We rely on the code below handling the MemoryAccess change.

We call moveMemoryToNewCongruenceClass below this which does:

// First, see what happens to the new class
if (!NewClass->getMemoryLeader()) {
  // Should be a new class, or a store becoming a leader of a new class.
  assert(NewClass->size() == 1 ||
         (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
  NewClass->setMemoryLeader(InstMA);

This should give NewClass a memory leader when the store becomes a leader.

In D33056#751288, @dberlin wrote:

I'm pretty sure this is wrong.
I'll look into it as soon as i get this machine back together.
We actually do set the leader.
Or at least, we should -

As the code says:

// We rely on the code below handling the MemoryAccess change.

We call moveMemoryToNewCongruenceClass below this which does:

// First, see what happens to the new class
if (!NewClass->getMemoryLeader()) {
  // Should be a new class, or a store becoming a leader of a new class.
  assert(NewClass->size() == 1 ||
         (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
  NewClass->setMemoryLeader(InstMA);

This should give NewClass a memory leader when the store becomes a leader.

Oh, sure it was. I thought it was skipped because for some reason I messed up MemoryUse and MemoryDef.
Anyway.

This is how we lose the memoryleader:
When we change leader to a store, we set the new memory leader to be:

7 = MemoryPhi({for.body,2},{if.then,3})

Then immediately after we value number that MemoryPhi:

Processing MemoryPhi 12 = MemoryPhi({for.body,4},{if.then,5})
Memory Phi value numbered to 5 = MemoryDef(12)

In valueNumberPHI we call setMemoryClass which resets the leader:

// This may have killed the class if it had no non-memory members
if (OldClass->getMemoryLeader() == From) {
  if (OldClass->memory_empty()) {
    OldClass->setMemoryLeader(nullptr);
  } else {

and the next instruction we process (the load), looks up for that leader and crashes.

[davide]

I think setting the memory leader to nullptr is not quite right.
We do it

if (OldClass->memory_empty()) {
  OldClass->setMemoryLeader(nullptr);

because we think there are no memory members, but this is inconsistent with the fact we have a StoreInst as leader and a StoreCount == 1.

[davide]

I think we might just be missing a check for store count (as it's done in the other place we call getNextMemoryLeader()).
Please let me know what you think, and thanks for catching the mistake!

diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp
index 3c9850b..f7182f2 100644
--- a/lib/Transforms/Scalar/NewGVN.cpp
+++ b/lib/Transforms/Scalar/NewGVN.cpp
@@ -1381,7 +1381,7 @@ bool NewGVN::setMemoryClass(const MemoryAccess *From,
         NewClass->memory_insert(MP);
         // This may have killed the class if it had no non-memory members
         if (OldClass->getMemoryLeader() == From) {
-          if (OldClass->memory_empty()) {
+          if (OldClass->memory_empty() && OldClass->getStoreCount() == 0) {
             OldClass->setMemoryLeader(nullptr);
           } else {
             OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));

fluttershy@SONY-PC C:\Users\fluttershy\work\llvm

[• dberlin]

In D33056#751369, @davide wrote:

I think we might just be missing a check for store count (as it's done in the other place we call getNextMemoryLeader()).
Please let me know what you think, and thanks for catching the mistake!

diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp
index 3c9850b..f7182f2 100644
--- a/lib/Transforms/Scalar/NewGVN.cpp
+++ b/lib/Transforms/Scalar/NewGVN.cpp
@@ -1381,7 +1381,7 @@ bool NewGVN::setMemoryClass(const MemoryAccess *From,
         NewClass->memory_insert(MP);
         // This may have killed the class if it had no non-memory members
         if (OldClass->getMemoryLeader() == From) {
-          if (OldClass->memory_empty()) {
+          if (OldClass->memory_empty() && OldClass->getStoreCount() == 0) {
             OldClass->setMemoryLeader(nullptr);
           } else {
             OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));

fluttershy@SONY-PC C:\Users\fluttershy\work\llvm

Oh, yes, I believe you have discovered the root cause.
Sigh.
I really wish it was easy to unify all this handling into one place.

Can you add a definesNoMemory or something to CongruenceClass, and use it here?
It should be memory_empty && storecount == 0

Then we can also replace this check:

if (OldClass->getStoreCount() != 0 || !OldClass->memory_empty()) {

with it

(This will also force us to make sure the class is in a consistent state. It would also let us add an assert that that if (CC->definesNoMemory()), then <nothing in ->members() is a store> && and memory_empty()) in a few places.
(though this is an expensive assert)

[davide]

Updated patch.

[davide]

While looking at something completely unrelated I noticed:

bool isDead() const {
  // If it's both dead from a value perspective, and dead from a memory
  // perspective, it's really dead.
  return empty() && memory_empty();
}

shouldn't this also do && StoreCount == 0 ?

[• dberlin]

Sorry, thought i accepted this one already :)

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

if (LookupResult != MemoryAccessToClass.end()) {
     auto *OldClass = LookupResult->second;
     if (OldClass != NewClass) {
       // If this is a phi, we have to handle memory member updates.
       if (auto *MP = dyn_cast<MemoryPhi>(From)) {
         OldClass->memory_erase(MP);
         NewClass->memory_insert(MP);
         // This may have killed the class if it had no non-memory members
         if (OldClass->getMemoryLeader() == From) {
-          if (OldClass->memory_empty()) {
+          if (OldClass->definesNoMemory()) {
             OldClass->setMemoryLeader(nullptr);
           } else {
             OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
             DEBUG(dbgs() << "Memory class leader change for class "
                          << OldClass->getID() << " to "
                          << *OldClass->getMemoryLeader()
                          << " due to removal of a memory member " << *From
                          << "\n");

llvm/trunk/test/Transforms/NewGVN/pr32934.ll

+; RUN: opt -S -newgvn %s | FileCheck %s
+
+; CHECK: define void @tinkywinky() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %d = alloca i32, align 4
+; CHECK-NEXT:   store i32 0, i32* null, align 4
+; CHECK-NEXT:   br label %for.cond
+; CHECK: for.cond:                                         ; preds = %if.end, %entry
+; CHECK-NEXT:   %0 = load i32, i32* null, align 4
+; CHECK-NEXT:   %cmp = icmp slt i32 %0, 1
+; CHECK-NEXT:   br i1 %cmp, label %for.body, label %while.cond
+; CHECK: for.body:                                         ; preds = %for.cond
+; CHECK-NEXT:   %1 = load i32, i32* @a, align 4
+; CHECK-NEXT:   store i32 %1, i32* %d, align 4
+; CHECK-NEXT:   br label %L
+; CHECK: L:                                                ; preds = %if.then, %for.body
+; CHECK-NEXT:   %tobool = icmp ne i32 %1, 0
+; CHECK-NEXT:   br i1 %tobool, label %if.then, label %if.end
+; CHECK: if.then:                                          ; preds = %L
+; CHECK-NEXT:   call void (i8*, ...) @printf(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @patatino, i32 0, i32 0))
+; CHECK-NEXT:   br label %L
+; CHECK: if.end:                                           ; preds = %L
+; CHECK-NEXT:   br label %for.cond
+; CHECK: while.cond:                                       ; preds = %while.body, %for.cond
+; CHECK-NEXT:   br i1 undef, label %while.body, label %while.end
+; CHECK: while.body:                                       ; preds = %while.cond
+; CHECK-NEXT:   call void (i8*, ...) @printf(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @patatino, i32 0, i32 0))
+; CHECK-NEXT:   br label %while.cond
+; CHECK: while.end:
+; CHECK-NEXT:   %2 = load i32, i32* @a, align 4
+; CHECK-NEXT:   store i32 %2, i32* undef, align 4
+; CHECK-NEXT:   ret void
+
+@a = external global i32, align 4
+@patatino = external unnamed_addr constant [2 x i8], align 1
+define void @tinkywinky() {
+entry:
+  %d = alloca i32, align 4
+  store i32 0, i32* null, align 4
+  br label %for.cond
+for.cond:
+  %0 = load i32, i32* null, align 4
+  %cmp = icmp slt i32 %0, 1
+  br i1 %cmp, label %for.body, label %while.cond
+for.body:
+  %1 = load i32, i32* @a, align 4
+  store i32 %1, i32* %d, align 4
+  br label %L
+L:
+  %2 = load i32, i32* %d, align 4
+  %tobool = icmp ne i32 %2, 0
+  br i1 %tobool, label %if.then, label %if.end
+if.then:
+  call void (i8*, ...) @printf(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @patatino, i32 0, i32 0))
+  br label %L
+if.end:
+  br label %for.cond
+while.cond:
+  br i1 undef, label %while.body, label %while.end
+while.body:
+  call void (i8*, ...) @printf(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @patatino, i32 0, i32 0))
+  br label %while.cond
+while.end:
+  %3 = load i32, i32* @a, align 4
+  store i32 %3, i32* undef, align 4
+  ret void
+}
+declare void @printf(i8*, ...) #1