diff mbox series

[C] Fix endless loop in the C FE initializer handling (PR c/85704)

Message ID 20180724085756.GB17988@tucnak
State New
Headers show
Series [C] Fix endless loop in the C FE initializer handling (PR c/85704) | expand

Commit Message

Jakub Jelinek July 24, 2018, 8:57 a.m. UTC 
Hi!

Starting with r258497 aka PR46921 fix the C FE can loop forever
in initializers where a zero length field's initializer has side-effects
(in this testcase merely because it is a compound literal) and that
zero length field is followed by some other fields.

Previously, we'd throw initializers of such zero length fields away,
but after the above mentioned commit we do it only if they have
side-effects.

The problem is that for FIELD_DECLs, output_pending_init_elements
uses just their bit_position to compare whic field precedes or follows the
other one (or if it is the same).  With zero sized FIELD_DECLs that is
ambiguous (as we can have many consecutive FIELD_DECLs that have zero
size and have the same bit_position (plus at most one non-zero sized field
after them) and previously it worked exactly because we'd throw away
all initializers for those fields.  The infinite loop is because we
output_init_element, which sees the initializer has side-effects and doesn't
throw it away, but adds to the pending tree, then returns to
output_pending_init_elements, which looks at the pending elt which is for
the same field again, but constructor_unfilled_fields at that point is
already the next field.  They have the same bit_position though, so next
time it calls output_init_element for it again rather than advancing to
something next, and loops this way forever.

The following patch fixes it by not relying solely on bit_position;
instead a field comparator is introduced, which determines from two
FIELD_DECLs (required to be from the same structure) which one comes first.
If they have different bit_position, the answer is clear, if one of them has
non-zero size, then the non-zero size must be the last one, if they are
pointer equal, they are the same, otherwise it walks the DECL_CHAIN of those
fields (starting from both of them simultaneously) and if it finds the other
field, or walks at the end of DECL_CHAIN (to last field), or to a field with
non-zero size, it stops.  I think walking both is better for the common case
that the two compared fields are close to each other, but we really don't
know which one is first (and hopefully people don't have thousands of
consecutive zero sized FIELD_DECLs, I'd hope they would use an array of them
in those cases).  Another option would be during structure layout attach
some extra ids to FIELD_DECLs that would allow finding out the FIELD_DECL
chain ordering instantly.  Not all FIELD_DECLs are ordered though (e.g. C++
ones I think) and we don't have bits to spare in tree_field_decl.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk and
release branches?

2018-07-24  Jakub Jelinek  <jakub@redhat.com>

	PR c/85704
	* c-typeck.c (field_decl_cmp): New function.
	(output_pending_init_elements): Use it for field comparisons
	instead of pure bit_position comparisons.

	* gcc.c-torture/compile/pr85704.c: New test.


	Jakub

Comments

Jakub Jelinek July 31, 2018, 10:22 a.m. UTC | #1 
Hi!

On Tue, Jul 24, 2018 at 10:57:56AM +0200, Jakub Jelinek wrote:
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk and
> release branches?
> 
> 2018-07-24  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR c/85704
> 	* c-typeck.c (field_decl_cmp): New function.
> 	(output_pending_init_elements): Use it for field comparisons
> 	instead of pure bit_position comparisons.
> 
> 	* gcc.c-torture/compile/pr85704.c: New test.

I'd like to ping this patch.

	Jakub
Joseph Myers July 31, 2018, 8:04 p.m. UTC | #2 
On Tue, 24 Jul 2018, Jakub Jelinek wrote:

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk and
> release branches?
> 
> 2018-07-24  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR c/85704
> 	* c-typeck.c (field_decl_cmp): New function.
> 	(output_pending_init_elements): Use it for field comparisons
> 	instead of pure bit_position comparisons.
> 
> 	* gcc.c-torture/compile/pr85704.c: New test.

OK, though I'm a bit uneasy about both c-decl.c and c-typeck.c having 
static field_decl_cmp functions that do completely different comparisons.
Jakub Jelinek July 31, 2018, 8:09 p.m. UTC | #3 
On Tue, Jul 31, 2018 at 08:04:58PM +0000, Joseph Myers wrote:
> On Tue, 24 Jul 2018, Jakub Jelinek wrote:
> 
> > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk and
> > release branches?
> > 
> > 2018-07-24  Jakub Jelinek  <jakub@redhat.com>
> > 
> > 	PR c/85704
> > 	* c-typeck.c (field_decl_cmp): New function.
> > 	(output_pending_init_elements): Use it for field comparisons
> > 	instead of pure bit_position comparisons.
> > 
> > 	* gcc.c-torture/compile/pr85704.c: New test.
> 
> OK, though I'm a bit uneasy about both c-decl.c and c-typeck.c having 
> static field_decl_cmp functions that do completely different comparisons.

So would you like me to rename it somehow?
init_field_decl_cmp, or field_cmp, or fld_cmp, something else?

	Jakub
Joseph Myers July 31, 2018, 8:10 p.m. UTC | #4 
On Tue, 31 Jul 2018, Jakub Jelinek wrote:

> On Tue, Jul 31, 2018 at 08:04:58PM +0000, Joseph Myers wrote:
> > On Tue, 24 Jul 2018, Jakub Jelinek wrote:
> > 
> > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk and
> > > release branches?
> > > 
> > > 2018-07-24  Jakub Jelinek  <jakub@redhat.com>
> > > 
> > > 	PR c/85704
> > > 	* c-typeck.c (field_decl_cmp): New function.
> > > 	(output_pending_init_elements): Use it for field comparisons
> > > 	instead of pure bit_position comparisons.
> > > 
> > > 	* gcc.c-torture/compile/pr85704.c: New test.
> > 
> > OK, though I'm a bit uneasy about both c-decl.c and c-typeck.c having 
> > static field_decl_cmp functions that do completely different comparisons.
> 
> So would you like me to rename it somehow?
> init_field_decl_cmp, or field_cmp, or fld_cmp, something else?

init_field_decl_cmp seems reasonable (makes clearer what this particular 
comparison is for).
Richard Sandiford March 21, 2019, 10:13 a.m. UTC | #5 
[Sorry for responding to such an old patch]

Jakub Jelinek <jakub@redhat.com> writes:
> +/* For two FIELD_DECLs in the same chain, return -1 if field1
> +   comes before field2, 1 if field1 comes after field2 and
> +   0 if field1 == field2.  */
> +
> +static int
> +field_decl_cmp (tree field1, tree field2)
> +{
> +  if (field1 == field2)
> +    return 0;
> +
> +  tree bitpos1 = bit_position (field1);
> +  tree bitpos2 = bit_position (field2);
> +  if (tree_int_cst_equal (bitpos1, bitpos2))
> +    {
> +      /* If one of the fields has non-zero bitsize, then that
> +	 field must be the last one in a sequence of zero
> +	 sized fields, fields after it will have bigger
> +	 bit_position.  */
> +      if (TREE_TYPE (field1) != error_mark_node
> +	  && COMPLETE_TYPE_P (TREE_TYPE (field1))
> +	  && integer_nonzerop (TREE_TYPE (field1)))
> +	return 1;
> +      if (TREE_TYPE (field2) != error_mark_node
> +	  && COMPLETE_TYPE_P (TREE_TYPE (field2))
> +	  && integer_nonzerop (TREE_TYPE (field2)))
> +	return -1;

Looks like these integer_nonzerop should be testing TYPE_SIZE or
TYPE_SIZE_UNIT -- not sure which is preferred here.

Thanks,
Richard
diff mbox series

Patch

--- gcc/c/c-typeck.c.jj	2018-06-22 19:17:10.308436152 +0200
+++ gcc/c/c-typeck.c	2018-07-23 15:36:56.455204401 +0200
@@ -9330,6 +9330,65 @@  output_init_element (location_t loc, tre
     output_pending_init_elements (0, braced_init_obstack);
 }
 
+/* For two FIELD_DECLs in the same chain, return -1 if field1
+   comes before field2, 1 if field1 comes after field2 and
+   0 if field1 == field2.  */
+
+static int
+field_decl_cmp (tree field1, tree field2)
+{
+  if (field1 == field2)
+    return 0;
+
+  tree bitpos1 = bit_position (field1);
+  tree bitpos2 = bit_position (field2);
+  if (tree_int_cst_equal (bitpos1, bitpos2))
+    {
+      /* If one of the fields has non-zero bitsize, then that
+	 field must be the last one in a sequence of zero
+	 sized fields, fields after it will have bigger
+	 bit_position.  */
+      if (TREE_TYPE (field1) != error_mark_node
+	  && COMPLETE_TYPE_P (TREE_TYPE (field1))
+	  && integer_nonzerop (TREE_TYPE (field1)))
+	return 1;
+      if (TREE_TYPE (field2) != error_mark_node
+	  && COMPLETE_TYPE_P (TREE_TYPE (field2))
+	  && integer_nonzerop (TREE_TYPE (field2)))
+	return -1;
+      /* Otherwise, fallback to DECL_CHAIN walk to find out
+	 which field comes earlier.  Walk chains of both
+	 fields, so that if field1 and field2 are close to each
+	 other in either order, it is found soon even for large
+	 sequences of zero sized fields.  */
+      tree f1 = field1, f2 = field2;
+      while (1)
+	{
+	  f1 = DECL_CHAIN (f1);
+	  f2 = DECL_CHAIN (f2);
+	  if (f1 == NULL_TREE)
+	    {
+	      gcc_assert (f2);
+	      return 1;
+	    }
+	  if (f2 == NULL_TREE)
+	    return -1;
+	  if (f1 == field2)
+	    return -1;
+	  if (f2 == field1)
+	    return 1;
+	  if (!tree_int_cst_equal (bit_position (f1), bitpos1))
+	    return 1;
+	  if (!tree_int_cst_equal (bit_position (f2), bitpos1))
+	    return -1;
+	}
+    }
+  else if (tree_int_cst_lt (bitpos1, bitpos2))
+    return -1;
+  else
+    return 1;
+}
+
 /* Output any pending elements which have become next.
    As we output elements, constructor_unfilled_{fields,index}
    advances, which may cause other elements to become next;
@@ -9401,25 +9460,17 @@  output_pending_init_elements (int all, s
 	}
       else if (RECORD_OR_UNION_TYPE_P (constructor_type))
 	{
-	  tree ctor_unfilled_bitpos, elt_bitpos;
-
 	  /* If the current record is complete we are done.  */
 	  if (constructor_unfilled_fields == NULL_TREE)
 	    break;
 
-	  ctor_unfilled_bitpos = bit_position (constructor_unfilled_fields);
-	  elt_bitpos = bit_position (elt->purpose);
-	  /* We can't compare fields here because there might be empty
-	     fields in between.  */
-	  if (tree_int_cst_equal (elt_bitpos, ctor_unfilled_bitpos))
-	    {
-	      constructor_unfilled_fields = elt->purpose;
-	      output_init_element (input_location, elt->value, elt->origtype,
-				   true, TREE_TYPE (elt->purpose),
-				   elt->purpose, false, false,
-				   braced_init_obstack);
-	    }
-	  else if (tree_int_cst_lt (ctor_unfilled_bitpos, elt_bitpos))
+	  int cmp = field_decl_cmp (constructor_unfilled_fields, elt->purpose);
+	  if (cmp == 0)
+	    output_init_element (input_location, elt->value, elt->origtype,
+				 true, TREE_TYPE (elt->purpose),
+				 elt->purpose, false, false,
+				 braced_init_obstack);
+	  else if (cmp < 0)
 	    {
 	      /* Advance to the next smaller node.  */
 	      if (elt->left)
@@ -9445,8 +9496,8 @@  output_pending_init_elements (int all, s
 		    elt = elt->parent;
 		  elt = elt->parent;
 		  if (elt
-		      && (tree_int_cst_lt (ctor_unfilled_bitpos,
-					   bit_position (elt->purpose))))
+		      && field_decl_cmp (constructor_unfilled_fields,
+					 elt->purpose) < 0)
 		    {
 		      next = elt->purpose;
 		      break;
--- gcc/testsuite/gcc.c-torture/compile/pr85704.c.jj	2018-07-23 16:06:50.430959693 +0200
+++ gcc/testsuite/gcc.c-torture/compile/pr85704.c	2018-07-23 16:06:44.601951278 +0200
@@ -0,0 +1,10 @@ 
+/* PR c/85704 */
+
+struct C { struct {} c; };
+struct D { int d; struct C e; int f; };
+
+void
+foo (struct D *x)
+{
+  *x = (struct D) { .e = (struct C) { .c = {} } };
+}