Patch RFC: Avoid recursive insert into const_desc_htab

The underlying cause of PR 89170 is a bug that appears to have existed
since 2001, when the function decode_addr_const was changed to call
output_constant_def.  The problem is that output_constant_def calls
compare_constant, and when compare_constant sees an ADDR_EXPR, it
calls decode_addr_const.  So it is possible for output_constant_def to
call itself recursively while adding a value to the hash table.  This
only happens if there are already some constants in the hash table
with the same hash code, because that is the only case in which
compare_constant can call decode_addr_constant.  This works fine if
the value whose address is taken is already in the hash table.  And it
works fine if the address is not in the hash table, but adding the
address does not cause the hash table to grow.

But if we call output_constant_def with a constant that includes an
ADDR_EXPR, and if there is already a constant in the hash table with
the same hash code, and if decode_addr_constant calls
output_constant_def recursively with a constant that is not already in
the hash table, and if adding that constant causes the hash table to
grow, then the outer call to output_constant_def will wind up looking
at the wrong hash bucket.  The effect is that output_constant_def will
return an rtx for a different constant.

This unlikely sequence of events actually happened building libgo's
net/http test on PPC64, causing a miscompilation leading to a test
failure filed as PR 89170.

I plan to commit this patch to fix the problem.  I didn't add a test
case since the sequence of events is so hard to recreate.  I added a
check that will detect any future recursive insertion into the hash
table.

Bootstrapped and tested on x86_64-pc-linux-gnu.  Since I haven't
looked at this part of the code in many years, I'll wait a bit to see
if anybody has any comments on the patch.

Ian


2019-02-20  Ian Lance Taylor  <iant@golang.org>

PR go/89170
* varasm.c (decode_addr_const): Call lookup_constant_def rather
than output_constant_def.
(const_desc_htab_inserting): New static variable.
(output_constant_def): Call output_addressed_constants.  Check and
set const_desc_htab_inserting.
(tree_output_constant_def): Likewise.

On Wed, Feb 20, 2019 at 6:53 PM Ian Lance Taylor <iant@golang.org> wrote:
>
> The underlying cause of PR 89170 is a bug that appears to have existed
> since 2001, when the function decode_addr_const was changed to call
> output_constant_def.  The problem is that output_constant_def calls
> compare_constant, and when compare_constant sees an ADDR_EXPR, it
> calls decode_addr_const.  So it is possible for output_constant_def to
> call itself recursively while adding a value to the hash table.  This
> only happens if there are already some constants in the hash table
> with the same hash code, because that is the only case in which
> compare_constant can call decode_addr_constant.  This works fine if
> the value whose address is taken is already in the hash table.  And it
> works fine if the address is not in the hash table, but adding the
> address does not cause the hash table to grow.
>
> But if we call output_constant_def with a constant that includes an
> ADDR_EXPR, and if there is already a constant in the hash table with
> the same hash code, and if decode_addr_constant calls
> output_constant_def recursively with a constant that is not already in
> the hash table, and if adding that constant causes the hash table to
> grow, then the outer call to output_constant_def will wind up looking
> at the wrong hash bucket.  The effect is that output_constant_def will
> return an rtx for a different constant.
>
> This unlikely sequence of events actually happened building libgo's
> net/http test on PPC64, causing a miscompilation leading to a test
> failure filed as PR 89170.
>
> I plan to commit this patch to fix the problem.  I didn't add a test
> case since the sequence of events is so hard to recreate.  I added a
> check that will detect any future recursive insertion into the hash
> table.
>
> Bootstrapped and tested on x86_64-pc-linux-gnu.  Since I haven't
> looked at this part of the code in many years, I'll wait a bit to see
> if anybody has any comments on the patch.

Looks reasonable.  Factoring the common code in
output_constant_def and tree_output_constant_def might be
worth it.

Richard.

> Ian
>
>
> 2019-02-20  Ian Lance Taylor  <iant@golang.org>
>
> PR go/89170
> * varasm.c (decode_addr_const): Call lookup_constant_def rather
> than output_constant_def.
> (const_desc_htab_inserting): New static variable.
> (output_constant_def): Call output_addressed_constants.  Check and
> set const_desc_htab_inserting.
> (tree_output_constant_def): Likewise.

On Thu, Feb 21, 2019 at 1:57 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Wed, Feb 20, 2019 at 6:53 PM Ian Lance Taylor <iant@golang.org> wrote:
> >
> > The underlying cause of PR 89170 is a bug that appears to have existed
> > since 2001, when the function decode_addr_const was changed to call
> > output_constant_def.  The problem is that output_constant_def calls
> > compare_constant, and when compare_constant sees an ADDR_EXPR, it
> > calls decode_addr_const.  So it is possible for output_constant_def to
> > call itself recursively while adding a value to the hash table.  This
> > only happens if there are already some constants in the hash table
> > with the same hash code, because that is the only case in which
> > compare_constant can call decode_addr_constant.  This works fine if
> > the value whose address is taken is already in the hash table.  And it
> > works fine if the address is not in the hash table, but adding the
> > address does not cause the hash table to grow.
> >
> > But if we call output_constant_def with a constant that includes an
> > ADDR_EXPR, and if there is already a constant in the hash table with
> > the same hash code, and if decode_addr_constant calls
> > output_constant_def recursively with a constant that is not already in
> > the hash table, and if adding that constant causes the hash table to
> > grow, then the outer call to output_constant_def will wind up looking
> > at the wrong hash bucket.  The effect is that output_constant_def will
> > return an rtx for a different constant.
> >
> > This unlikely sequence of events actually happened building libgo's
> > net/http test on PPC64, causing a miscompilation leading to a test
> > failure filed as PR 89170.
> >
> > I plan to commit this patch to fix the problem.  I didn't add a test
> > case since the sequence of events is so hard to recreate.  I added a
> > check that will detect any future recursive insertion into the hash
> > table.
> >
> > Bootstrapped and tested on x86_64-pc-linux-gnu.  Since I haven't
> > looked at this part of the code in many years, I'll wait a bit to see
> > if anybody has any comments on the patch.
>
> Looks reasonable.  Factoring the common code in
> output_constant_def and tree_output_constant_def might be
> worth it.

Makes sense.  Done.  Rebootstrapped, retested, and committed as follows.

Ian

2019-02-21  Ian Lance Taylor  <iant@golang.org>

PR go/89170
* varasm.c (decode_addr_const): Call lookup_constant_def rather
than output_constant_def.
(add_constant_to_table): New static function.
(output_constant_def): Call add_constant_to_table.
(tree_output_constant_def): Likewise.
Index: gcc/varasm.c
===================================================================
--- gcc/varasm.c	(revision 268949)
+++ gcc/varasm.c	(working copy)
@@ -2961,7 +2961,9 @@ decode_addr_const (tree exp, struct addr
     case COMPLEX_CST:
     case CONSTRUCTOR:
     case INTEGER_CST:
-      x = output_constant_def (target, 1);
+      x = lookup_constant_def (target);
+      /* Should have been added by output_addressed_constants.  */
+      gcc_assert (x);
       break;
 
     case INDIRECT_REF:
@@ -3424,6 +3426,43 @@ build_constant_desc (tree exp)
   return desc;
 }
 
+/* Subroutine of output_constant_def and tree_output_constant_def:
+   Add a constant to the hash table that tracks which constants
+   already have labels.  */
+
+static constant_descriptor_tree *
+add_constant_to_table (tree exp)
+{
+  /* The hash table methods may call output_constant_def for addressed
+     constants, so handle them first.  */
+  output_addressed_constants (exp);
+
+  /* Sanity check to catch recursive insertion.  */
+  static bool inserting;
+  gcc_assert (!inserting);
+  inserting = true;
+
+  /* Look up EXP in the table of constant descriptors.  If we didn't
+     find it, create a new one.  */
+  struct constant_descriptor_tree key;
+  key.value = exp;
+  key.hash = const_hash_1 (exp);
+  constant_descriptor_tree **loc
+    = const_desc_htab->find_slot_with_hash (&key, key.hash, INSERT);
+
+  inserting = false;
+
+  struct constant_descriptor_tree *desc = *loc;
+  if (!desc)
+    {
+      desc = build_constant_desc (exp);
+      desc->hash = key.hash;
+      *loc = desc;
+    }
+
+  return desc;
+}
+
 /* Return an rtx representing a reference to constant data in memory
    for the constant expression EXP.
 
@@ -3440,24 +3479,7 @@ build_constant_desc (tree exp)
 rtx
 output_constant_def (tree exp, int defer)
 {
-  struct constant_descriptor_tree *desc;
-  struct constant_descriptor_tree key;
-
-  /* Look up EXP in the table of constant descriptors.  If we didn't find
-     it, create a new one.  */
-  key.value = exp;
-  key.hash = const_hash_1 (exp);
-  constant_descriptor_tree **loc
-    = const_desc_htab->find_slot_with_hash (&key, key.hash, INSERT);
-
-  desc = *loc;
-  if (desc == 0)
-    {
-      desc = build_constant_desc (exp);
-      desc->hash = key.hash;
-      *loc = desc;
-    }
-
+  struct constant_descriptor_tree *desc = add_constant_to_table (exp);
   maybe_output_constant_def_contents (desc, defer);
   return desc->rtl;
 }
@@ -3591,25 +3613,8 @@ lookup_constant_def (tree exp)
 tree
 tree_output_constant_def (tree exp)
 {
-  struct constant_descriptor_tree *desc, key;
-  tree decl;
-
-  /* Look up EXP in the table of constant descriptors.  If we didn't find
-     it, create a new one.  */
-  key.value = exp;
-  key.hash = const_hash_1 (exp);
-  constant_descriptor_tree **loc
-    = const_desc_htab->find_slot_with_hash (&key, key.hash, INSERT);
-
-  desc = *loc;
-  if (desc == 0)
-    {
-      desc = build_constant_desc (exp);
-      desc->hash = key.hash;
-      *loc = desc;
-    }
-
-  decl = SYMBOL_REF_DECL (XEXP (desc->rtl, 0));
+  struct constant_descriptor_tree *desc = add_constant_to_table (exp);
+  tree decl = SYMBOL_REF_DECL (XEXP (desc->rtl, 0));
   varpool_node::finalize_decl (decl);
   return decl;
 }