[PATCH][committed] Always initialize hash table elements

[Jeff Law <law at redhat dot com>]

The recently added code to try and optimize certain binary operations
when both operands were equal had a subtle bug.

Specifically, when that optimization applied, it failed to initialize
the hash table element returned from the failed lookup.   That hash
table element would be kept in the empty/uninitialized state which has
special meaning...

Under the right set of circumstances that could result in items being in
the hash table that we couldn't lookup (we could find them via a
traversal though).

The sequence of events from the BZ testcase looks like this:

Enter object1 into slot X
Enter object2 into slot Y (after rehashing due to conflict)

Y must be < X to trigger the bug because the next step requires a
reallocation of the table.  WHen we reallocate we walk through the old
table from first to last and insert the objects into the new table.

That results in object2 going into slot X and object1 going into slot Y
in the new table.

Then we remove object2 from the hash table.  This leaves slot X in a
deleted state.

Then we lookup object3 and get back slot X which will be put into an
empty state.  Since we didn't get a hit in the table, we try to lookup
an alternate form that would allow us to prove object3 has a constant
value.  That succeeds and we never re-initialize slot X, leaving it in
the deleted state.

The deleted state is important as it also means uninitialized.  The
generic bits of hash-table.h (reasonably) assume that a slot in the
empty/uninitialized state  implies that no other objects with a
conflicting hash are in the table.

So when we try to lookup object1 in the table, it misses because slot1
is uninitialized/empty -- which triggers the assert as we know object1
must be in the hash table.

[ Yes, I could almost certainly trigger this in a simpler way. ]

The fix is to ensure we initialize the slot properly after a miss, but
when we are able to prove the expression has a constant value.

Bootstrapped and regression tested on x86_64.  Installed on the trunk.

Jeff

commit 85f11a8902c4f7ec06111b197d37b26e40be6e0a
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Sep 1 15:32:15 2017 +0000

            PR tree-optimization/82052
            * tree-ssa-scopedtables.c (avail_exprs_stack::lookup_avail_expr):
            Always initialize the returned slot after a hash table miss
            when INSERT is true.
    
            PR tree-optimization/82052
            * gcc.c-torture/compile/pr82052.c: New test.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@251600 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 60824ea8a2e..f9e49e0cc94 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2017-09-01  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/82052
+	* tree-ssa-scopedtables.c (avail_exprs_stack::lookup_avail_expr):
+	Always initialize the returned slot after a hash table miss
+	when INSERT is true.
+
 2017-09-01  Alexander Monakov  <amonakov@ispras.ru>
 
 	* config/s390/s390.md (mem_signal_fence): Remove.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index b3045634838..9ace97b5b25 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2017-09-01  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/82052
+	* gcc.c-torture/compile/pr82052.c: New test.
+
 2017-09-01  Jakub Jelinek  <jakub@redhat.com>
 
 	PR sanitizer/81923
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr82052.c b/gcc/testsuite/gcc.c-torture/compile/pr82052.c
new file mode 100644
index 00000000000..44419855745
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr82052.c
@@ -0,0 +1,391 @@
+typedef unsigned char uint8_t;
+typedef unsigned short uint16_t;
+typedef unsigned uint32_t;
+char a, t9, t22;
+uint32_t c[56];
+uint32_t d, t, t1, t5, t13, t19, t31, t36, t40;
+struct {
+  unsigned f0 : 1;
+  unsigned f7 : 4;
+} l, t3;
+uint16_t g, t17, t29 = 65531, t42 = 1;
+short m, t6, t11, t12, t20, t27 = 1, t34 = 7, t38, t43, s;
+uint8_t p, u, t2, t4, t14, t24, t33, t44 = 50, t90;
+int f, h = 5, n, o = 40211, q, v = 2, w, t7, t8, t10, t15, t16, t18, t21, t25,
+       t26, t28, t30 = 3743393910, t32, t37 = 105423096, t39, t46, t47, t48,
+       t49, t88, t89, x, y;
+char r;
+char t23;
+uint16_t t35[][7][2];
+static uint8_t t41;
+char z[][8][3];
+char fn1(char p1, int p2) { return p1 < 0 ?: p1 >> p2; }
+short fn2() {}
+void fn3(uint8_t p1) { d = d >> 8 ^ c[(d ^ p1) & 5]; }
+void fn4(uint32_t p1, int p2) {
+  int e;
+  uint8_t b = e;
+  d = 8 ^ c[(d ^ b) & 5];
+  fn3(e >> 8);
+  fn3(e >> 6);
+  fn3(e >> 24);
+  if (p2)
+    printf(0);
+}
+int fn5(p1) {
+  if (t37)
+    for (; t28;)
+      ;
+}
+uint16_t fn6(char p1, int p2) {
+  int k;
+  for (; t32; t32++)
+    for (; t32 < 8; t32++)
+      fn4(t23, k);
+}
+uint8_t fn7(p1) { return 1; }
+uint32_t fn8(uint8_t p1, uint32_t p2) {
+  t22 = t44 | 1;
+  t34--;
+  l.f7 = p2;
+  fn4(t18, t88);
+  fn4(t17, t88);
+  fn4(t3.f0, t88);
+  fn4(t16, t88);
+  fn4(t15, t88);
+  fn4(t14, t88);
+  fn4(t13, t88);
+  fn4(t12, t88);
+  fn4(t11, t88);
+  fn4(t3.f7, t88);
+  fn4(h, t39);
+  fn4(t10, t88);
+  fn4(t9, t88);
+  fn4(t8, t88);
+  fn4(t7, t88);
+  fn4(t6, t88);
+  fn4(t5, t88);
+  return t32;
+}
+uint32_t fn9(p1) {
+  h = 5;
+  int t45;
+  for (; o; o = 0)
+    if (n)
+      break;
+  f = 0;
+  for (; f < 10; f++) {
+    t45 = 0;
+    for (; t45 < 3; t45++)
+      fn4(z[f][t32][t45], f);
+  }
+  return t4;
+}
+short fn10(char p1, uint16_t p2, char p3, char p5) {
+  int i, k, t91;
+  z[t24][h][t89] = i = 0;
+  for (; i < 6; i++)
+    fn4(t38, 1);
+  if (p3 <= p1 != t90)
+    fn4(t41, 3);
+  else {
+    t91 = 0;
+    for (; t91 < 3; t91++) {
+      fn4(z[t32][i][t91], t37);
+      if (t37) {
+        fn4(z[t39][t39][k], f);
+        if (f)
+          printf("", t39);
+        printf("", t32);
+      }
+    }
+  }
+  for (; p; p++) {
+    if (x)
+      break;
+    if (t37)
+      break;
+  }
+  for (; t24; t24++)
+    t29++;
+  w = t29 = p5;
+}
+static int fn11() {
+  char t50, t52;
+  short t51, t56 = 49061, t65;
+  uint32_t t53 = 3, t55 = 4272075807, t64;
+  int t54 = 14,
+      t57 = ~(t55 | t30 & t | ~(~t37 | (v | t43 / t53) | g >> (t56 & f))),
+      t58 = ~(t57 ^ t53 | (t55 >> f & t37) / ~v & ~(t56 / ~g));
+  uint16_t t59 = ~(t57 / (g | t | ~(t58 & t43) & t30 / (t55 / ~(v ^ t37))));
+LABEL_XgXgd:
+  if (!(t56 < t58)) {
+    t57 = t30;
+    t58 = t59 = g;
+    t30 = ~(t58 & ~v & t & t56 | t53);
+    f = ~t57 | ~t & ~(t30 ^ f) / ~(t37 ^ ~t55 & (t43 | t59 | v)) ^ g;
+    if (t37) {
+      printf("", (long long)t30, (long long)f);
+      g = ~(~(~g | ~v << ~t37) << ~f << t43 | t53 / (t30 | t55));
+      f = ~(~t59 ^ ~(~(t56 & t37) ^ t) >> t43 | ~t30 / t53 >> t57);
+    }
+  }
+  int t60 = ~((~t42 >> t24 | ~-~(~s & t33) & u ^ t | 4 ^ t30 & r) + t32);
+  uint32_t t61 =
+      ~(-(t30 ^ t33) & -(~(t60 & t | 4 | ~r & t42) + (~t32 >> s) & -t24));
+  uint8_t t62 = ~(~(t61 & ~(s | t33 | u)) ^ t60 | -(t | -t30) & ~(t24 & r));
+  if (s) {
+    t61 = t;
+  LABEL_RhRhd:
+    t32 = ~(t33 & (t24 | r) + u + t60 | (t32 | (~s | t) & t42) + 4);
+    t = ~(-(t32 ^ ~t60 ^ t42) & (t33 | t) + t62 + u ^ ~s + ~(~t30 - t61));
+    u = ~(r & ~s ^ -t33 | t24) + t + t32 + t60 + (t62 & t42 ^ u);
+    if (t61 > t24) {
+      printf("", (long long)t32);
+      u = ~(~(~t60 | t30) | ~t) + (t42 ^ t62 & ~t32 | ~s & r + (4 & u));
+    }
+    while (t53 || t40) {
+      t60 = 0;
+      for (; t60 < 8; t60++)
+        fn4(t23, t32);
+    }
+    if (t32)
+      if (t60 || t42 > t24) {
+        printf("", u);
+        goto LABEL_ahahd;
+      }
+  }
+  t32 = t60;
+  t = t61;
+  u = t62;
+  t30 = t57;
+  int t63 = ~(~t53 >> t30 | l.f7 / ~t54 - t34 + ~t44 / (~q | t43) | ~t39);
+  if (t29 < t40)
+    for (;; t40++)
+      for (; t48; t48++)
+        t38 = 0;
+  if (t40)
+    t63 = q;
+  t64 = t53;
+  t65 = t34;
+  q = ~l.f7 % ~(~t65 / ~t43 - t44 & t54 | t39 % (~t30 | q & (t56 | t53)));
+LABEL_ahahd:
+  t53 = ~(~t30 % ~t34 & ~t44 + ((t63 | t43) + (q | t65 | -l.f7) & t53));
+  uint8_t t66 =
+      -(-t29 & (-t42 & (u + t30 ^ t36) ^ t24 >> -t54 / t37 & (-l.f7 | ~t2)));
+  uint16_t t67 = -(-(~t24 + t54 ^ ~t2 >> l.f7 ^ t42) | u | t29);
+  int t68 = -t24 & t42 & ~l.f7 ^ -t66 ^ u;
+  if (u)
+    t54 = ~(~t37 / -t42 * t2 - t66) + ~(-(t54 / t67) % t29) & t68;
+  t34 = ~(~(t54 - t64) % t44 % (t34 - (l.f7 & t39))) + (t53 | t43 || q) - t63;
+  if (t30 > q) {
+    p++;
+    z[t44][t58][t57] = 1;
+    t1++;
+  }
+  if (t2 && t44)
+    q = t63;
+  int t69 = ~(~t1 / v & (t40 && t54) << (q & t32)) ^ t28 / t53 & t39;
+  if (t69 < t30) {
+    uint8_t t70 = ~t32 + t46 + r | s ^ v & t55 << ~t40 | l.f0 & t33,
+            t71 = ~(~t55 | (v | t33) + (~(~t32 + ~t70) ^ t46 | l.f0) + ~s);
+    char t72 = -(t55 | r | ~s | ~t46 ^ t71 << t40 ^ t31 | v ^ t33) & -t70;
+    if (t31 < t71) {
+      uint8_t t73 = -((v + u & -f) % ~r + ~(~t29 | t42) | ~t54 * (t46 ^ t36)),
+              t74 = ~(-f | t42 + t54);
+      char t75 = ~(~(-t46 ^ r / v | ~t74 + t54 - t73) - ~t29);
+      if (t33) {
+        t73 = u;
+        t33 = ~(-t73 / ~(~(~v * f / t54) / -(-(t33 | u) & t75 + t29) ^ t46));
+        r = r * ~t75 & (t29 ^ t36) ^ t73 * -t74 % t46 - ~u + t33;
+        printf("", (long long)u);
+        r = -(~(t73 & t36 & (t33 & t46) % ~r) / ~(t54 / ~t74 << -v));
+        t33 = ~((t33 ^ -(t74 ^ r)) + (-t46 << t42 | ~f) + ~t29 / v) >> ~u * t73;
+        goto LABEL_RhRhd;
+      }
+      l.f0 = -(-t55 | -(-t32 << s & t71) ^ r & -(t46 + t70));
+      r = ~(~t31 | -(-(t70 | t71 + t46) ^ -s ^ (-l.f0 ^ t72 ^ t40) & t74));
+      if (l.f0 && l.f0 > t70)
+        printf("", t74);
+    LABEL_RhRhh:
+      if (v > r)
+        goto LABEL_XgXgd;
+      if (r && t72) {
+        printf("", (long long)r);
+        goto LABEL_XgXgd;
+      }
+    }
+    t33 = t70;
+    l.f0 = t71;
+    r = t72;
+    t54 = ~(~t69 | (q & t28) / ~(t32 && t1) / t39 | ~v ^ (t30 && t40));
+    if (t54 && t44) {
+      for (; s; s++)
+        for (; t27; t27++)
+          for (; t28; t28++)
+            z[s][t27][t28] = 0;
+      for (; t32; t32++)
+        fn4(y, t46);
+    }
+    printf("", t47, t32, t32);
+    printf("", (long long)t54);
+    if (t28 && t69) {
+      printf("", (long long)t53);
+      goto LABEL_ahahd;
+    }
+  }
+  if (t32 > 4097347)
+    for (; t69 < 2; t69++) {
+      for (; t49; t49++)
+        for (; t46; t46++)
+          z[u][1][1] = 1;
+      fn4(t35[t69][f][t69], t37);
+      if (t37)
+        for (; t58 < 3; t58++)
+          z[t24][t63][t58] = 1;
+      printf("", t69, f, t69);
+    }
+  if (t44 <= 50 && t44)
+    t53 = t64;
+  while (t36 && t55 < t2)
+    for (; t57;) {
+      fn4(t41, v);
+      if (v)
+        printf("", t58, t54, t57);
+    }
+  f = t58;
+  if (t)
+    g = t59;
+  uint8_t t76 = (t33 & l.f0 % t30) + t40 ^ 4 * t53 / u + l.f7;
+  uint16_t t77 = ~(-(-t29 % ((t30 + t76 ^ -u) * ~(g ^ t40) ^ t53)) * ~-~t33);
+  uint32_t t78 =
+      ~(l.f0 + t29 % (4 * (l.f7 / t53 | g) % t30 + ~t33)) - (t77 + ~u);
+  if (t78 < t40) {
+  LABEL__h_hl:
+    t77 = t29;
+    t78 = t40;
+    u = ~(t33 >> l.f7) - (g * (t76 | u) >> t78 | ~(l.f0 << t40 ^ 4 | t30));
+    t29 = ~(l.f0 | ~t53 % t76 * t78 % u + t29 | g) % ~-~t40 | l.f7;
+    t40 = ~(-t78 / 4 % t30 % ~(t33 | t29 | -t77) + ~(-l.f7 % ~t40 & l.f0) * -u);
+    if (l.f7) {
+      printf("", (long long)u);
+      goto LABEL_RhRhh;
+    }
+    if (t76 > t77) {
+      printf("", (long long)t29);
+      printf("", (long long)t40);
+      t40 = ~(-t53 % ((-t33 << t78) % l.f7)) | t40 / g * -t29 >> u;
+      u = ~(4 % l.f7 * ~t29 | t78 / t53 + t40 & ~g * t33 % t76 - u);
+      goto LABEL__h_hl;
+    }
+  }
+  t29 = t40 = t78;
+  short t79 = h;
+  uint32_t t80 = ~(~(t37 % (t32 || t44)) % ~(~u & t28 || t33 - h));
+  uint8_t t81 = t33 / t34 / t32;
+  if (t31 > g)
+    q = 2;
+  uint8_t t82 =
+      -(l.f7 + ~t24 + (~t2 ^ -t30) | ~(-(4 & t34 + t43) | ~(t36 | o | t53)));
+  short t83 = ~(-(l.f7 + t34 & t53 | (4 + (o >> t24) | t30) | t2 | t36) + ~t82);
+  int t84 = ~(t2 | ~(t53 < t24) ^ o) + (t83 + t30 ^ t43 & l.f7 > 4) >> ~-~t34;
+  t30 = ~(~t82 + t30 + t2 | -o & t84 + ~(4 | -t36) & (t43 & (t34 & ~l.f7)));
+  t40 = ~(~v << ~t40 / t27) - ~(v & t2 * p) % ~t27 % (~h - t) & ~o;
+  t27 = ~(1 % v + t27 >> -t27 / (-t ^ -h) & -t37 ^ o);
+  v = -(t2 + t40 ^ v) % (-t27 | ~p % h & t37 / o + ~t27 & t);
+  if (h > 5) {
+    printf("", (long long)t40);
+    goto LABEL_ahahd;
+  }
+  if (t37 > 431447816) {
+    printf("", (long long)t27);
+    goto LABEL_XgXgd;
+  }
+  if (1 > t27) {
+    printf("", (long long)v);
+    goto LABEL_RhRhd;
+  }
+  t30 = t84;
+  s = h;
+  t31 = t80;
+  t52 = fn1(t53, 4);
+  x = fn5(f && fn2(t46 = g = t52,
+                   fn6(fn7(fn8(f, fn9(fn10(t51, f, t53, t53)))) < t21, t53)));
+  t50 = a - t55;
+  t54 = (t20 == (0 != t19)) + t50;
+  if (t33 < t54 || t30)
+    q = t54;
+  for (; t24; ++t24) {
+    int t85 = -(~(t55 | -t36) ^ t40 + o | ~g & (t43 ^ t56)),
+        t86 = t55 ^ t36 << l.f7 ^ g & (t56 ^ t85 | ~t44 | t37);
+    uint32_t t87 = l.f7 + ~t40 ^ t44 ^ (t56 ^ ~t55 + g ^ -t85 & t43 & o);
+    if (t87) {
+      t86 = t37;
+      if (t44)
+        goto LABEL_ahahd;
+      if (t87) {
+        printf("", (long long)t55);
+        continue;
+      }
+    }
+    o = t37 = t86;
+    t55 = t87;
+  }
+  return t26;
+}
+int main() {
+  int i, j, k;
+  {
+    uint32_t t92;
+    int i, j;
+    i = 0;
+    for (; i < 56; i++) {
+      t92 = i;
+      j = 8;
+      for (; j; j--)
+        if (t92 & 1)
+          t92 = t92 >> 1 ^ 2;
+        else
+          t92 >>= 1;
+      c[i] = t92;
+    }
+  }
+  fn11();
+  fn4(f, 0);
+  printf("", g);
+  fn4(h, 0);
+  printf("", l.f0);
+  fn4(n, 0);
+  fn4(o, 0);
+  printf("", p);
+  fn4(t, 0);
+  printf("", m);
+  printf("", s);
+  fn4(q, 0);
+  printf("", r);
+  printf("", u);
+  fn4(v, 0);
+  for (; i < 4; i++) {
+    j = 0;
+    for (; j < 5; j++)
+      ;
+  }
+  for (; i < 0; i++)
+    for (; k < 3; k++)
+      fn4(z[i][j][k], 0);
+  fn4(t1, 0);
+  i = 0;
+  for (; i < 7; i++) {
+    j = 0;
+    for (; j < 8; j++)
+      fn4(t23, 0);
+  }
+  printf("", t24);
+  fn4(t28, 0);
+  printf("", t29);
+  fn4(t28, 0);
+  printf("", t29);
+  fn4(t25, 0);
+  fn4(t30, 0);
+  printf("", t27);
+}
diff --git a/gcc/tree-ssa-scopedtables.c b/gcc/tree-ssa-scopedtables.c
index 6e1fd582814..27e0c68b846 100644
--- a/gcc/tree-ssa-scopedtables.c
+++ b/gcc/tree-ssa-scopedtables.c
@@ -258,15 +258,24 @@ avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p)
     {
       /* If we did not find the expression in the hash table, we may still
 	 be able to produce a result for some expressions.  */
-      tree alt = avail_exprs_stack::simplify_binary_operation (stmt, element);
-      if (alt)
-	return alt;
+      tree retval = avail_exprs_stack::simplify_binary_operation (stmt,
+								  element);
 
+      /* We have, in effect, allocated *SLOT for ELEMENT at this point.
+	 We must initialize *SLOT to a real entry, even if we found a
+	 way to prove ELEMENT was a constant after not finding ELEMENT
+	 in the hash table.
+
+	 An uninitialized or empty slot is an indication no prior objects
+	 entered into the hash table had a hash collection with ELEMENT.
+
+	 If we fail to do so and had such entries in the table, they
+	 would become unreachable.  */
       class expr_hash_elt *element2 = new expr_hash_elt (element);
       *slot = element2;
 
       record_expr (element2, NULL, '2');
-      return NULL_TREE;
+      return retval;
     }
 
   /* If we found a redundant memory operation do an alias walk to