Wrong code at -O2 on x86_64 (recent regression in GVN pass)

[shao-hua-li]

Clang at -O2 emits the wrong code.

Bisected to 84bcfa0, which was committed by @weiguozhi

Compiler explorer: https://godbolt.org/z/rW9chv3hj

% cat a.c
int printf(const char *, ...);
int a, d, e, f, h, j, t, q;
char c, s;
signed char g;
signed char *i = &g;
int *k = &h;
int **l = &k;
signed char **m = &i;
signed char ***r = &m;
static signed char ****n = &r;
long o, u;
int p[7];
void v() {
  t = 0;
  for (; t < 9; t++) {
    q = 0;
    for (; c + q; q++)
      p[q] = 3;
  }
}
void w(long x, char y) {
  for (; o;) {
    v();
    s = x;
    u = y;
  }
}
int main() {
  for (; d <= 3; d++) {
    e = 0;
    for (; e <= 3; e++) {
      int *b;
      f = 3;
      for (; f; f--) {
        w(****n, **l);
        b = &j;
        *b = **l + ***r;
      }
    }
  }
  for (; **l;)
    ;
  printf("%X\n", a);
}
%
% clang -O0 a.c  && ./a.out
0
% clang -O2 a.c && ./a.out
Segmentation fault
%

[weiguozhi]

Thanks for the report! Will investigate it.

[weiguozhi]

It looks unrelated bug triggered by the patch 84bcfa0.

The function iterateOnFunction is called 5 times on main. The patch was triggered only once in the first iteration. If I limit the number of call to iterateOnFunction once or twice, the generated code can work correctly, but if I allow 3 times of call to iterateOnFunction, I will get wrong code.

[weiguozhi]

The problem is in function GVNPass::processBlock, it calls EliminateDuplicatePHINodes to delete duplicated PHI instructions. But GVN uses MemoryDependenceResults *MD to maintain memory dependence information, any deleted instructions must notify MD through MD->removeInstruction, like GVNPass::removeInstruction.

But function EliminateDuplicatePHINodes just silently delete PHI instructions without notify MD, and left some garbage in MD. Later when a new PHI instruction is created at the same address as a deleted PHI instruction, MD may automatically (wrongly) contain dependence information for it. When it is used for optimization, wrong code is generated as the reported test case shows.

[nikic]

Confirmed that https://gist.github.com/nikic/ebaa9312e4f3b1a451ee74ef2c710407 would fix the issue.

[nikic]

I was wondering whether we could make detecting this easier through the use of AssertingVH, but the relevant value is part of using ValueIsLoadPair = PointerIntPair<const Value *, 1, bool>, and there's no easy way to use AssertingVH in there. (Just using std::pair under LLVM_ENABLE_ABI_BREAKING_CHECKS is not enough, because this is also used inside SmallPtrSet, etc.)

[nikic]

Candidate patch: https://reviews.llvm.org/D158849