<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/77852>77852</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Non-determinsm in GVNSink
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug,
            llvm:codegen,
            llvm:GVN
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          ilovepi
      </td>
    </tr>
</table>

<pre>
    We've found non-deterministic behavior when using GNVSink.

A reproducer is included here.
[gvn-reduced.zip](https://github.com/llvm/llvm-project/files/13909537/gvn-reduced.zip)

I've included the reduced case, my reduction script, and some IR files from -print-after-all w/ the module context.
In case it helps, I'm including theC++ code here.

```cpp
#define a(e, ab) e->ac = e->ac ?: ab
#define b(e, ab) return a(e, ab)
struct A {
  long d;
  const char *ac;
};
bool g();
char a;
bool f;
static bool h(unsigned *i, bool p2) {
  A *e = 0;
  if (p2)
    ;
  char b;
  do {
    if (g())
      if (b) {
        if (f)
          b(e, "");
        if (a)
          b(e, "");
      }
    b = 7;
  } while (a);
  *i = 5;
  return true;
}
bool fn3(bool i) {
  unsigned c(h(&c, i));
  return true;
}
```

Ultimately, what we're seeing is that sometimes the GVNSink pass doesn't transform the IR. It seems that depending on the ordering of blocks in the Predecessors list, GVN may or may not trigger. 

This is non-deterministic, because the list is ordered by pointer, which has no stable ordering w.r.t. the order in which blocks are analyzed and values sunk. This happens here https://github.com/llvm/llvm-project/blob/93b47053c6bce5862ba4a5f7d9f6d5cbaa8cbf41/llvm/lib/Transforms/Scalar/GVNSink.cpp#L778

In fact, when I attempted to sort this list based on the ordering of blocks in the function, several tests broke due to the optimization no longer occurring. GVNSink/struct.ll is one I remember offhand, but there were others, too.

After playing around with some of this, I suspected that the `break` around https://github.com/llvm/llvm-project/blob/93b47053c6bce5862ba4a5f7d9f6d5cbaa8cbf41/llvm/lib/Transforms/Scalar/GVNSink.cpp#L798 was the big issue, since it bails out differently based on the ordering of the blocks, but replacing it with a `continue` (and incrementing the iterator) causes other code gen issues, despite fixing the nondeterminism.

Note that the use of `stable_sort` later in this routine doesn't fix this issue as it occurs after the nondeterminism has already been introduced in the LockStepReverseIterator.



</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMVk1v47wR_jX0ZRBDpmzLPvjgbOrAwCIodrfpseDHyGJDkQJJxev99cVQliOnLdp9T28QyNKQM3zm6xmKGM3JIe7Y6pGtnmaiT40PO2P9O3ZmJr2-7P6OjFfvCLXvnQbn3YPGhKE1zsRkFEhsxLvxAc4NOuijcSd4fnn9btzbnBVPrNgPzz0E7ILXvcIAJoJxyvYaNTQYcNy5ejy9u4eAtEvPf5mOrZ4Y3zQpdZGVe8YPjB9OJjW9nCvfMn6w9n38eeiC_yeqxPihNhYj44dFuS22q7IirU-G-XaK7jg4eQOVGoTrblAiIuNfoL0MomS8g6iC6RKJhdMQfYtw_Ab5XKiDb-GhC8alB1EnDA_CWjgzfsh2W697i6C8S_gzXV0_unwOmAQN2i6SZQLVXjFRWFODXxh_ZPwRlNd4F7nhuS6Gf9V1VwkvNdbGIQjGN9kNIRnfAj6w8i9CASufJu8HVu5pwyddea8bMPXBfbI46MQUepVgD6x6HCQA1rsTaFbeBMq7mEA1IgDje6FuS6x6ur1L7y2cGN-Q7VGYdcT9nvr2GZPIFUnShvFN73J5azrFENC80nHyYYJvT-uYI1FMUJoaGN_k3aMIYOoFYZETgfZTq6OB0YWplXFNfkIyXas_adDfLQ-M8_y_nRw_VRZ_RJmif_uUOR7VZAurnuDcGIu3AyZrfG-ywmoivJZJCj3eZXiSOldSFOjVfArFLXeK-j_HcK0IvbkG8_8859YS0z75m02mFQnthSyeG5HgTDQXECIitZqJkEhMjZ1MizF37vPrC_EadCJG0B6jY7xKkIJwsfahzZuO3-ZwTGSovRrR2KHLHexd3uKDxpC_a5DWqzeiw7zy14AaFcboQwRrYmaY59cXaMUFfMg_ztOR5nTCMIepWz8a4tX47ySdax-V6CPmU8gwbcw4UIO8QOeNSxiGeBjVQCPIEMQkpJ0gPs_DPM0_vCDgg8LVEREQhBP28gt15sZ3YXuMEHv3NocMsRFdhy5m_oLf5nZpvWT8sC3lsipWpVpLhavNmkuxFKu60tt6rVdKCrFRsl4uJnYM6f0Yk0Xz4bsSVgTGD9fMzok4efm1qjZ308FBLVQagoMOjiBSwrZLNCk8RB8SJPIsB1aKiPp_p7ruXR4lZDXiOwZhIWFMEWTwbwi6RzKejXTJtOaXyJPH-cyoGMAr1QcyPh8rk_HDwMBza3OCHcIRArbYSlKo60Y4ncuhJ8iUgDM9PL3noZO8v5_bNMCgs-JCXoiQrwFnk5ph6Pk6e57HFcQ-dqhyVKjuCTpbFzKgeGPrYlT-c2Z8u4GzGNpcGiKA2Ge2jMapPJalMDaC7xNoU9cY0CV7-e_JzoZywsdwB-ysUJld0hBBQeGhe4BxPVKEiFmdppFPOSN5nvpgEgaRfCCSzG0ch4wN94ATugFvPkpj7ExCqM3PUd1598EH7V16X3zCj2wRQfiaUA19_w8qbQJmRRp6PZd58H2ie8EHBdbm57CUcYCI5GOuzwj5CvQfcGSKETag0BeQSE64NNwQ9dgkX716-56w-0YNEvF4jcP9rSc_Z3pX6m25FTPcLapiVSyqarmaNbtiu6wLsRYLzWu53i6wLtZLveDbYltpzfnM7HjBl8ViwYui4Hw5L7FaSrkuC4W4WKw2bFlgK4ydU1nNfTjNspe7qtqs-MwKiTbmKzTnsj_l2fqFcZ6LsNxTik7oPoufX19ItHqahV2ud9mfIlsWRCHx46RkksXdy4TRI10Jx4af9cHufruhxmI5ZA_-FQAA___uWLzQ">