Fix tree-optimization/91169

Message ID 1764855.0oU1eeNi03@arcturus.home
State New
Headers show
Series
  • Fix tree-optimization/91169
Related show

Commit Message

Eric Botcazou Aug. 1, 2019, 8:27 a.m.
Hi,

this fixes the cd2a31a regression in the ACATS testsuite on 32-bit targets 
introduced by the recent change to get_array_ctor_element_at_index:

	* fold-const.h (get_array_ctor_element_at_index): Adjust.
	* fold-const.c (get_array_ctor_element_at_index): Add
	ctor_idx output parameter informing the caller where in
	the constructor the element was (not) found.  Add early exit
	for when the ctor is sorted.

This change overlooks that the index can wrap around during the traversal of 
the CONSTRUCTOR and therefore causes the function to return bogus values as 
soon as this happens.  Moreover, given this chunk of added code:

      else if (in_gimple_form)
	/* We're past the element we search for.  Note during parsing
	   the elements might not be sorted.
	   ???  We should use a binary search and a flag on the
	   CONSTRUCTOR as to whether elements are sorted in declaration
	   order.  */
	break;

I would respectfully suggest that the author thinks about redoing things from 
scratch here.  In the meantime, the attached patch kludges around the issue.

Tested on x86_64-suse-linux, OK for the mainline?


2019-08-01  Eric Botcazou  <ebotcazou@adacore.com>

	PR tree-optimization/91169
	* fold-const.c (get_array_ctor_element_at_index): Remove early exit and
	do not return a bogus ctor_idx when the index wraps around.

-- 
Eric Botcazou

Comments

Richard Biener Aug. 1, 2019, 9:20 a.m. | #1
On Thu, Aug 1, 2019 at 10:27 AM Eric Botcazou <ebotcazou@adacore.com> wrote:
>

> Hi,

>

> this fixes the cd2a31a regression in the ACATS testsuite on 32-bit targets

> introduced by the recent change to get_array_ctor_element_at_index:

>

>         * fold-const.h (get_array_ctor_element_at_index): Adjust.

>         * fold-const.c (get_array_ctor_element_at_index): Add

>         ctor_idx output parameter informing the caller where in

>         the constructor the element was (not) found.  Add early exit

>         for when the ctor is sorted.

>

> This change overlooks that the index can wrap around during the traversal of

> the CONSTRUCTOR and therefore causes the function to return bogus values as

> soon as this happens.  Moreover, given this chunk of added code:


So isn't this an issue with the code before when we have a RANGE_EXPR
that covers the wrapping point?  Then index > max_index and may not
catch the found element with

    /* Do we have match?  */
    if (wi::cmpu (access_index, index) >= 0
        && wi::cmpu (access_index, max_index) <= 0)
      return cval;

?  We seem to be careful to convert the indices to the index type but
above use unsigned compares - isn't that the underlying issue?  So
isn't

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c    (revision 273968)
+++ gcc/fold-const.c    (working copy)
@@ -11864,9 +11864,13 @@ get_array_ctor_element_at_index (tree ct
        }
     }

+  signop index_sgn = UNSIGNED;
   if (index_type)
-    access_index = wi::ext (access_index, TYPE_PRECISION (index_type),
-                           TYPE_SIGN (index_type));
+    {
+      index_sgn = TYPE_SIGN (index_type);
+      access_index = wi::ext (access_index, TYPE_PRECISION (index_type),
+                             TYPE_SIGN (index_type));
+    }

   offset_int index = low_bound - 1;
   if (index_type)
@@ -11903,9 +11907,9 @@ get_array_ctor_element_at_index (tree ct
        }

       /* Do we have match?  */
-      if (wi::cmpu (access_index, index) >= 0)
+      if (wi::cmp (access_index, index, index_sgn) >= 0)
        {
-         if (wi::cmpu (access_index, max_index) <= 0)
+         if (wi::cmp (access_index, max_index, index_sgn) <= 0)
            {
              if (ctor_idx)
                *ctor_idx = cnt;


>       else if (in_gimple_form)

>         /* We're past the element we search for.  Note during parsing

>            the elements might not be sorted.

>            ???  We should use a binary search and a flag on the

>            CONSTRUCTOR as to whether elements are sorted in declaration

>            order.  */

>         break;

>

> I would respectfully suggest that the author thinks about redoing things from

> scratch here.  In the meantime, the attached patch kludges around the issue.


I'm not sure how "doing from scratch" would fix things - we simply rely
on reliably detecting an element match.

I wonder how much we can rely on the array domain type to be in sync
with the constructor field entries.

Also we're using offset_int here - doesn't that break when with
Ada we have an array type with domain [uint128_t_max - 1, uint128_t_max + 2]
in a type larger than int128_t?  Or, since we're interpreting it
inconsistently signed/unsigned, a 128bit integer typed domain wraps
around the sign?

If that's not an issue then using signed compare unconditionally is
a valid fix as well I guess.

But in reality 'index' should never really wrap, that is, if the domain
is of 'int' type and starts with INT_MAX then the array shall not have
more than 1 element.  No?

The patch you posted isn't a real fix btw, since iff the break was
hit we either missed an index that is present or we found a gap
but then we can break.

So I'd appreciate more explanation on how the index "wraps".

Richard.

> Tested on x86_64-suse-linux, OK for the mainline?

>

>

> 2019-08-01  Eric Botcazou  <ebotcazou@adacore.com>

>

>         PR tree-optimization/91169

>         * fold-const.c (get_array_ctor_element_at_index): Remove early exit and

>         do not return a bogus ctor_idx when the index wraps around.

>

> --

> Eric Botcazou
Eric Botcazou Aug. 1, 2019, 5:12 p.m. | #2
> So isn't this an issue with the code before when we have a RANGE_EXPR

> that covers the wrapping point?


No, see the reduced testcase attached in the PR.

> Then index > max_index and may not catch the found element with

> 

>     /* Do we have match?  */

>     if (wi::cmpu (access_index, index) >= 0

>         && wi::cmpu (access_index, max_index) <= 0)

>       return cval;

> 

> ?  We seem to be careful to convert the indices to the index type but

> above use unsigned compares - isn't that the underlying issue?


Not really, everything is properly unsigned at this point, so the traversal 
wraps around in an unsigned type.

> I'm not sure how "doing from scratch" would fix things - we simply rely

> on reliably detecting an element match.

> 

> I wonder how much we can rely on the array domain type to be in sync

> with the constructor field entries.


At least we need to take into account the wraparound.

> Also we're using offset_int here - doesn't that break when with

> Ada we have an array type with domain [uint128_t_max - 1, uint128_t_max + 2]

> in a type larger than int128_t?  Or, since we're interpreting it

> inconsistently signed/unsigned, a 128bit integer typed domain wraps

> around the sign?


Integer types are limited to 64 bits in GNAT.

> If that's not an issue then using signed compare unconditionally is

> a valid fix as well I guess.


But all the types are unsigned here so this doesn't seem appealing.

> But in reality 'index' should never really wrap, that is, if the domain

> is of 'int' type and starts with INT_MAX then the array shall not have

> more than 1 element.  No?


The range is [-1, 1] converted to sizetype, which is unsigned, so the low 
bound is UINT32_MAX and the high bound is 1.

> The patch you posted isn't a real fix btw, since iff the break was

> hit we either missed an index that is present or we found a gap

> but then we can break.


No, we cannot break if the index wraps around, that's the bug.

> So I'd appreciate more explanation on how the index "wraps".


See above.  I can rewind the entire chain of events if need be, but this is a 
long one starting a long time ago with the initial blunder with PLUS_EXPR and 
sizetype.

-- 
Eric Botcazou
Richard Biener Aug. 2, 2019, 8:24 a.m. | #3
On Thu, Aug 1, 2019 at 7:11 PM Eric Botcazou <ebotcazou@adacore.com> wrote:
>

> > So isn't this an issue with the code before when we have a RANGE_EXPR

> > that covers the wrapping point?

>

> No, see the reduced testcase attached in the PR.

>

> > Then index > max_index and may not catch the found element with

> >

> >     /* Do we have match?  */

> >     if (wi::cmpu (access_index, index) >= 0

> >         && wi::cmpu (access_index, max_index) <= 0)

> >       return cval;

> >

> > ?  We seem to be careful to convert the indices to the index type but

> > above use unsigned compares - isn't that the underlying issue?

>

> Not really, everything is properly unsigned at this point, so the traversal

> wraps around in an unsigned type.

>

> > I'm not sure how "doing from scratch" would fix things - we simply rely

> > on reliably detecting an element match.

> >

> > I wonder how much we can rely on the array domain type to be in sync

> > with the constructor field entries.

>

> At least we need to take into account the wraparound.

>

> > Also we're using offset_int here - doesn't that break when with

> > Ada we have an array type with domain [uint128_t_max - 1, uint128_t_max + 2]

> > in a type larger than int128_t?  Or, since we're interpreting it

> > inconsistently signed/unsigned, a 128bit integer typed domain wraps

> > around the sign?

>

> Integer types are limited to 64 bits in GNAT.

>

> > If that's not an issue then using signed compare unconditionally is

> > a valid fix as well I guess.

>

> But all the types are unsigned here so this doesn't seem appealing.

>

> > But in reality 'index' should never really wrap, that is, if the domain

> > is of 'int' type and starts with INT_MAX then the array shall not have

> > more than 1 element.  No?

>

> The range is [-1, 1] converted to sizetype, which is unsigned, so the low

> bound is UINT32_MAX and the high bound is 1.


Oh.  OK, now I see.  Still, if we have this domain and a CONSTRUCTOR
with a RANGE_EXPR UINT32_MAX, 1 and we are asking for access_index
zero then the old code did

    /* Do we have match?  */
    if (wi::cmpu (access_index, index) >= 0
        && wi::cmpu (access_index, max_index) <= 0)
      return cval;

and index == UINT32_MAX, max_index == 1.  So we don't match it
but return NULL, assuming the constructor value is zero?

Not sure if the Ada FE ever creates RANGE_EXPRs for CONSTRUCTOR
entries, for single-valued entries the check of course works.  But as it
was written above I assumed certain ordering conditions must hold...
(grepping shows no traces of RANGE_EXPR in gigi)

I'm hoping for a GCC C extension to specify array domains so the
GIMPLE FE can be used to play with these kind of things...

> > The patch you posted isn't a real fix btw, since iff the break was

> > hit we either missed an index that is present or we found a gap

> > but then we can break.

>

> No, we cannot break if the index wraps around, that's the bug.

>

> > So I'd appreciate more explanation on how the index "wraps".

>

> See above.  I can rewind the entire chain of events if need be, but this is a

> long one starting a long time ago with the initial blunder with PLUS_EXPR and

> sizetype.


Yeah.  Note that you can very well use signed TYPE_DOMAIN nowadays
(OK, no guarantees...).

I think we should kludge around similar to how we do in stor-layout.c
which does

                /* ???  When it is obvious that the range is signed
                   represent it using ssizetype.  */
                if (TREE_CODE (lb) == INTEGER_CST
                    && TREE_CODE (ub) == INTEGER_CST
                    && TYPE_UNSIGNED (TREE_TYPE (lb))
                    && tree_int_cst_lt (ub, lb))
                  {
                    lb = wide_int_to_tree (ssizetype,
                                           offset_int::from (wi::to_wide (lb),
                                                             SIGNED));
                    ub = wide_int_to_tree (ssizetype,
                                           offset_int::from (wi::to_wide (ub),
                                                             SIGNED));
                  }

So I am testing the attached.

Richard.

>

> --

> Eric Botcazou
Richard Biener Aug. 2, 2019, 10:59 a.m. | #4
On Fri, Aug 2, 2019 at 10:24 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>

> On Thu, Aug 1, 2019 at 7:11 PM Eric Botcazou <ebotcazou@adacore.com> wrote:

> >

> > > So isn't this an issue with the code before when we have a RANGE_EXPR

> > > that covers the wrapping point?

> >

> > No, see the reduced testcase attached in the PR.

> >

> > > Then index > max_index and may not catch the found element with

> > >

> > >     /* Do we have match?  */

> > >     if (wi::cmpu (access_index, index) >= 0

> > >         && wi::cmpu (access_index, max_index) <= 0)

> > >       return cval;

> > >

> > > ?  We seem to be careful to convert the indices to the index type but

> > > above use unsigned compares - isn't that the underlying issue?

> >

> > Not really, everything is properly unsigned at this point, so the traversal

> > wraps around in an unsigned type.

> >

> > > I'm not sure how "doing from scratch" would fix things - we simply rely

> > > on reliably detecting an element match.

> > >

> > > I wonder how much we can rely on the array domain type to be in sync

> > > with the constructor field entries.

> >

> > At least we need to take into account the wraparound.

> >

> > > Also we're using offset_int here - doesn't that break when with

> > > Ada we have an array type with domain [uint128_t_max - 1, uint128_t_max + 2]

> > > in a type larger than int128_t?  Or, since we're interpreting it

> > > inconsistently signed/unsigned, a 128bit integer typed domain wraps

> > > around the sign?

> >

> > Integer types are limited to 64 bits in GNAT.

> >

> > > If that's not an issue then using signed compare unconditionally is

> > > a valid fix as well I guess.

> >

> > But all the types are unsigned here so this doesn't seem appealing.

> >

> > > But in reality 'index' should never really wrap, that is, if the domain

> > > is of 'int' type and starts with INT_MAX then the array shall not have

> > > more than 1 element.  No?

> >

> > The range is [-1, 1] converted to sizetype, which is unsigned, so the low

> > bound is UINT32_MAX and the high bound is 1.

>

> Oh.  OK, now I see.  Still, if we have this domain and a CONSTRUCTOR

> with a RANGE_EXPR UINT32_MAX, 1 and we are asking for access_index

> zero then the old code did

>

>     /* Do we have match?  */

>     if (wi::cmpu (access_index, index) >= 0

>         && wi::cmpu (access_index, max_index) <= 0)

>       return cval;

>

> and index == UINT32_MAX, max_index == 1.  So we don't match it

> but return NULL, assuming the constructor value is zero?

>

> Not sure if the Ada FE ever creates RANGE_EXPRs for CONSTRUCTOR

> entries, for single-valued entries the check of course works.  But as it

> was written above I assumed certain ordering conditions must hold...

> (grepping shows no traces of RANGE_EXPR in gigi)

>

> I'm hoping for a GCC C extension to specify array domains so the

> GIMPLE FE can be used to play with these kind of things...

>

> > > The patch you posted isn't a real fix btw, since iff the break was

> > > hit we either missed an index that is present or we found a gap

> > > but then we can break.

> >

> > No, we cannot break if the index wraps around, that's the bug.

> >

> > > So I'd appreciate more explanation on how the index "wraps".

> >

> > See above.  I can rewind the entire chain of events if need be, but this is a

> > long one starting a long time ago with the initial blunder with PLUS_EXPR and

> > sizetype.

>

> Yeah.  Note that you can very well use signed TYPE_DOMAIN nowadays

> (OK, no guarantees...).

>

> I think we should kludge around similar to how we do in stor-layout.c

> which does

>

>                 /* ???  When it is obvious that the range is signed

>                    represent it using ssizetype.  */

>                 if (TREE_CODE (lb) == INTEGER_CST

>                     && TREE_CODE (ub) == INTEGER_CST

>                     && TYPE_UNSIGNED (TREE_TYPE (lb))

>                     && tree_int_cst_lt (ub, lb))

>                   {

>                     lb = wide_int_to_tree (ssizetype,

>                                            offset_int::from (wi::to_wide (lb),

>                                                              SIGNED));

>                     ub = wide_int_to_tree (ssizetype,

>                                            offset_int::from (wi::to_wide (ub),

>                                                              SIGNED));

>                   }

>

> So I am testing the attached.


Testing went OK but it looks like acats doesn't honor
RUNTESTFLAGS so I got no multilib testing for it :/
And the PR didn't contain sth I could plug into gnat.dg so I checked
with visual inspection of dumps on the reduced testcase.
I notice pretty-printing is also confused about the wrapping ;)

  static struct p__intarray___PAD intarray = {.F={-100, [0]=0, 100}};

the [0]= is not necessary.

Anyway, I can see bogus IL before and still after the proposed patch :/
This is because I forgot to adjust cfield handling of setting index.

So I'm testing the adjusted patch attached which fixes the IL
and for testing have patched gcc/testsuite/ada/acats/run_all.sh
to add -m32.

Richard.

> Richard.

>

> >

> > --

> > Eric Botcazou
Rainer Orth Aug. 2, 2019, 11:25 a.m. | #5
Hi Richard,

> Testing went OK but it looks like acats doesn't honor

> RUNTESTFLAGS so I got no multilib testing for it :/


indeed, see PR testsuite/37703.  I had the beginnings of a patch

	http://gcc.gnu.org/ml/gcc-patches/2011-01/msg02310.html
        http://gcc.gnu.org/ml/gcc-patches/2011-02/msg01469.html

but that got stuck years ago.

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University
Eric Botcazou Aug. 5, 2019, 8:28 a.m. | #6
> Testing went OK but it looks like acats doesn't honor

> RUNTESTFLAGS so I got no multilib testing for it :/

> And the PR didn't contain sth I could plug into gnat.dg so I checked

> with visual inspection of dumps on the reduced testcase.


Sorry about that, gnat.dg/array37.adb now attached.

> I notice pretty-printing is also confused about the wrapping ;)

> 

>   static struct p__intarray___PAD intarray = {.F={-100, [0]=0, 100}};

> 

> the [0]= is not necessary.

> 

> Anyway, I can see bogus IL before and still after the proposed patch :/

> This is because I forgot to adjust cfield handling of setting index.

> 

> So I'm testing the adjusted patch attached which fixes the IL

> and for testing have patched gcc/testsuite/ada/acats/run_all.sh

> to add -m32.


Thanks!

-- 
Eric Botcazou
-- { dg-do run }
-- { dg-options "-O" }

procedure Array37 is

  type Arr is array (Integer range -1 .. 1) of Integer;

  A : Arr := (-100, 0, 100);

  function Ident (I : Integer) return Integer IS
  begin
    return I;
  end;

begin
  if Ident (A (1)) <= Ident (A (0)) then
    raise Program_Error;
  end if;
end;
Richard Biener Aug. 5, 2019, 12:28 p.m. | #7
On Mon, Aug 5, 2019 at 10:28 AM Eric Botcazou <ebotcazou@adacore.com> wrote:
>

> > Testing went OK but it looks like acats doesn't honor

> > RUNTESTFLAGS so I got no multilib testing for it :/

> > And the PR didn't contain sth I could plug into gnat.dg so I checked

> > with visual inspection of dumps on the reduced testcase.

>

> Sorry about that, gnat.dg/array37.adb now attached.

>

> > I notice pretty-printing is also confused about the wrapping ;)

> >

> >   static struct p__intarray___PAD intarray = {.F={-100, [0]=0, 100}};

> >

> > the [0]= is not necessary.

> >

> > Anyway, I can see bogus IL before and still after the proposed patch :/

> > This is because I forgot to adjust cfield handling of setting index.

> >

> > So I'm testing the adjusted patch attached which fixes the IL

> > and for testing have patched gcc/testsuite/ada/acats/run_all.sh

> > to add -m32.

>

> Thanks!


Fixed as follows - I've added checking asserts that wrapping doesn't
occur and also fixed another bug which treated

 { .el = { RANGE [1, 4], 0 }, .el = { NULL_TREE, 1 } }

as setting [2] to 1.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

Patch

Index: fold-const.c
===================================================================
--- fold-const.c	(revision 273907)
+++ fold-const.c	(working copy)
@@ -11841,9 +11841,9 @@  fold_ternary_loc (location_t loc, enum tree_code c
 /* Gets the element ACCESS_INDEX from CTOR, which must be a CONSTRUCTOR
    of an array (or vector).  *CTOR_IDX if non-NULL is updated with the
    constructor element index of the value returned.  If the element is
-   not found NULL_TREE is returned and *CTOR_IDX is updated to
-   the index of the element after the ACCESS_INDEX position (which
-   may be outside of the CTOR array).  */
+   not found, then NULL_TREE is returned and *CTOR_IDX is updated to
+   the index of the element after the ACCESS_INDEX position (which may
+   be outside of the CTOR array).  */
 
 tree
 get_array_ctor_element_at_index (tree ctor, offset_int access_index,
@@ -11874,8 +11874,9 @@  get_array_ctor_element_at_index (tree ctor, offset
 		     TYPE_SIGN (index_type));
 
   offset_int max_index;
-  unsigned cnt;
+  unsigned cnt, after_cnt;
   tree cfield, cval;
+  bool after_cnt_valid = false;
 
   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
     {
@@ -11895,10 +11896,15 @@  get_array_ctor_element_at_index (tree ctor, offset
 	}
       else
 	{
+	  const offset_int old_index = index;
 	  index += 1;
 	  if (index_type)
-	    index = wi::ext (index, TYPE_PRECISION (index_type),
-			     TYPE_SIGN (index_type));
+	    {
+	      index = wi::ext (index, TYPE_PRECISION (index_type),
+			       TYPE_SIGN (index_type));
+	      if (wi::cmpu (index, old_index) <= 0)
+		after_cnt_valid = false;
+	    }
 	  max_index = index;
 	}
 
@@ -11912,16 +11918,20 @@  get_array_ctor_element_at_index (tree ctor, offset
 	      return cval;
 	    }
 	}
-      else if (in_gimple_form)
-	/* We're past the element we search for.  Note during parsing
-	   the elements might not be sorted.
-	   ???  We should use a binary search and a flag on the
-	   CONSTRUCTOR as to whether elements are sorted in declaration
-	   order.  */
-	break;
+
+      /* We may be past the element we search for.  Note that during parsing
+	 the elements might not be sorted.  Note also that the index may wrap
+	 around during the traversal of the constructor if it was signed.
+	 ??? We should use a binary search and a flag on the CONSTRUCTOR as
+	 to whether elements are sorted in declaration order.  */
+      else if (in_gimple_form && !after_cnt_valid)
+	{
+	  after_cnt = cnt;
+	  after_cnt_valid = true;
+	}
     }
   if (ctor_idx)
-    *ctor_idx = cnt;
+    *ctor_idx = after_cnt_valid ? after_cnt : cnt;
   return NULL_TREE;
 }