This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by davide on May 10 2017, 10:38 AM.

Details

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.

Diff Detail

Event Timeline

davide created this revision.May 10 2017, 10:38 AM
dberlin edited edge metadata.May 10 2017, 11:18 AM

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.

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.

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.

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.

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

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 this revision to Diff 98514.May 10 2017, 1:15 PM

Updated patch.

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 accepted this revision.May 11 2017, 5:45 PM

Sorry, thought i accepted this one already :)

This revision is now accepted and ready to land.May 11 2017, 5:45 PM
This revision was automatically updated to reflect the committed changes.