Patchwork Fix computation of offset in ivopt

login
register
mail settings
Submitter Bin Cheng
Date Sept. 30, 2013, 5:39 a.m.
Message ID <002901cebd9f$5f7cb0a0$1e7611e0$@arm.com>
Download mbox | patch
Permalink /patch/278919/
State New
Headers show

Comments

Bin Cheng - Sept. 30, 2013, 5:39 a.m.
> -----Original Message-----
> From: Richard Biener [mailto:richard.guenther@gmail.com]
> Sent: Friday, September 27, 2013 4:30 PM
> To: Bin Cheng
> Cc: GCC Patches
> Subject: Re: [PATCH]Fix computation of offset in ivopt
> 
> On Fri, Sep 27, 2013 at 7:07 AM, bin.cheng <bin.cheng@arm.com> wrote:
> >
> >
> >   case INTEGER_CST:
> >       //.......
> >       *offset = int_cst_value (expr);
> > change to
> >   case INTEGER_CST:
> >       //.......
> >       *offset = sext_hwi (int_cst_value (expr), type);
> >
> > and
> >   case MULT_EXPR:
> >       //.......
> >       *offset = sext_hwi (int_cst_value (expr), type); to
> >   case MULT_EXPR:
> >       //.......
> >      HOST_WIDE_INT xxx = (HOST_WIDE_INT)off0 * int_cst_value (op1);
> >       *offset = sext_hwi (xxx, type);
> >
> > Any comments?
> 
> The issue is of course that we end up converting offsets to sizetype at
some
> point which makes them all appear unsigned.  The fix for this is to simply
> interpret them as signed ... but it's really a mess ;)
> 

Hi,  this is updated patch which calculates signed offset in strip_offset_1
then sign extend it in strip_offset.

Bootstrap and test on x86_64/x86/arm. Is it OK?

Thanks.
bin

2013-09-30  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type.
	Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF.
	(strip_offset): Sign extend before return.
Richard Guenther - Oct. 1, 2013, 10:50 a.m.
On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng <bin.cheng@arm.com> wrote:
>
>
>> -----Original Message-----
>> From: Richard Biener [mailto:richard.guenther@gmail.com]
>> Sent: Friday, September 27, 2013 4:30 PM
>> To: Bin Cheng
>> Cc: GCC Patches
>> Subject: Re: [PATCH]Fix computation of offset in ivopt
>>
>> On Fri, Sep 27, 2013 at 7:07 AM, bin.cheng <bin.cheng@arm.com> wrote:
>> >
>> >
>> >   case INTEGER_CST:
>> >       //.......
>> >       *offset = int_cst_value (expr);
>> > change to
>> >   case INTEGER_CST:
>> >       //.......
>> >       *offset = sext_hwi (int_cst_value (expr), type);
>> >
>> > and
>> >   case MULT_EXPR:
>> >       //.......
>> >       *offset = sext_hwi (int_cst_value (expr), type); to
>> >   case MULT_EXPR:
>> >       //.......
>> >      HOST_WIDE_INT xxx = (HOST_WIDE_INT)off0 * int_cst_value (op1);
>> >       *offset = sext_hwi (xxx, type);
>> >
>> > Any comments?
>>
>> The issue is of course that we end up converting offsets to sizetype at
> some
>> point which makes them all appear unsigned.  The fix for this is to simply
>> interpret them as signed ... but it's really a mess ;)
>>
>
> Hi,  this is updated patch which calculates signed offset in strip_offset_1
> then sign extend it in strip_offset.
>
> Bootstrap and test on x86_64/x86/arm. Is it OK?

I don't think you need

+  /* Sign extend off if expr is in type which has lower precision
+     than HOST_WIDE_INT.  */
+  if (TYPE_PRECISION (TREE_TYPE (expr)) <= HOST_BITS_PER_WIDE_INT)
+    off = sext_hwi (off, TYPE_PRECISION (TREE_TYPE (expr)));

at least it would be suspicious if you did ...

The only case that I can think of points to a bug in strip_offset_1
again, namely if sizetype (the type of all offsets) is smaller than
a HOST_WIDE_INT in which case

+    boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
+    *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT;

is wrong as boffset / BITS_PER_UNIT does not do a signed division
then (for negative boffset which AFAIK does not happen - but it would
be technically allowed).  Thus, the predicates like

+    && cst_and_fits_in_hwi (tmp)

would need to be amended with a check that the MSB is not set.

Btw, the cst_and_fits_in_hwi implementation is odd:

bool
cst_and_fits_in_hwi (const_tree x)
{
  if (TREE_CODE (x) != INTEGER_CST)
    return false;

  if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
    return false;

  return (TREE_INT_CST_HIGH (x) == 0
          || TREE_INT_CST_HIGH (x) == -1);
}

the precision check seems totally pointless and I wonder what's
the point of this routine as there is host_integerp () already
and tree_low_cst instead of int_cst_value - oh, I see, the latter
forcefully sign-extends .... that should make the extension
not necessary.

Btw, int_cst_value sounds like a very bad name for a value-changing
function.

Richard.


> Thanks.
> bin
>
> 2013-09-30  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type.
>         Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF.
>         (strip_offset): Sign extend before return.
Bin.Cheng - Oct. 1, 2013, 4:13 p.m.
On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng <bin.cheng@arm.com> wrote:
>>
>>
>
> I don't think you need
>
> +  /* Sign extend off if expr is in type which has lower precision
> +     than HOST_WIDE_INT.  */
> +  if (TYPE_PRECISION (TREE_TYPE (expr)) <= HOST_BITS_PER_WIDE_INT)
> +    off = sext_hwi (off, TYPE_PRECISION (TREE_TYPE (expr)));
>
> at least it would be suspicious if you did ...
There is a problem for example of the first message.  The iv base if like:
pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4
I am not sure why but it seems (-4/0xFFFFFFFC) is represented by
(1073741823*4).  For each operand strip_offset_1 returns exactly the
positive number and result of multiplication never get its chance of
sign extend.  That's why the sign extend is necessary to fix the
problem. Or it should be fixed elsewhere by representing iv base with:
"pretmp_184 + ((sizetype) KeyIndex_180 + 4294967295) * 4" in the first place.

>
> The only case that I can think of points to a bug in strip_offset_1
> again, namely if sizetype (the type of all offsets) is smaller than
> a HOST_WIDE_INT in which case
>
> +    boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
> +    *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT;
>
> is wrong as boffset / BITS_PER_UNIT does not do a signed division
> then (for negative boffset which AFAIK does not happen - but it would
> be technically allowed).  Thus, the predicates like
>
> +    && cst_and_fits_in_hwi (tmp)
>
> would need to be amended with a check that the MSB is not set.
So I can handle it like:

+    abs_boffset = abs_hwi (boffset);
+    xxxxx = abs_boffset / BITS_PER_UNIT;
+    if (boffset < 0)
+      xxxxx = -xxxxx;
+    *offset = off0 + int_cst_value (tmp) + xxxxx;

Right?

>
> Btw, the cst_and_fits_in_hwi implementation is odd:
>
> bool
> cst_and_fits_in_hwi (const_tree x)
> {
>   if (TREE_CODE (x) != INTEGER_CST)
>     return false;
>
>   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
>     return false;
>
>   return (TREE_INT_CST_HIGH (x) == 0
>           || TREE_INT_CST_HIGH (x) == -1);
> }
>
> the precision check seems totally pointless and I wonder what's
> the point of this routine as there is host_integerp () already
> and tree_low_cst instead of int_cst_value - oh, I see, the latter
> forcefully sign-extends .... that should make the extension
> not necessary.
See above.

Thanks.
bin
Richard Guenther - Oct. 2, 2013, 8:32 a.m.
On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng <bin.cheng@arm.com> wrote:
>>>
>>>
>>
>> I don't think you need
>>
>> +  /* Sign extend off if expr is in type which has lower precision
>> +     than HOST_WIDE_INT.  */
>> +  if (TYPE_PRECISION (TREE_TYPE (expr)) <= HOST_BITS_PER_WIDE_INT)
>> +    off = sext_hwi (off, TYPE_PRECISION (TREE_TYPE (expr)));
>>
>> at least it would be suspicious if you did ...
> There is a problem for example of the first message.  The iv base if like:
> pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4
> I am not sure why but it seems (-4/0xFFFFFFFC) is represented by
> (1073741823*4).  For each operand strip_offset_1 returns exactly the
> positive number and result of multiplication never get its chance of
> sign extend.  That's why the sign extend is necessary to fix the
> problem. Or it should be fixed elsewhere by representing iv base with:
> "pretmp_184 + ((sizetype) KeyIndex_180 + 4294967295) * 4" in the first place.

Yeah, that's why I said the whole issue with forcing all offsets to be
unsigned is a mess ...

There is really no good answer besides not doing that I fear.

Yes, in the above case we could fold the whole thing differently
(interpret the offset of a POINTER_PLUS_EXPR as signed).  You
can try tracking down the offender, but it'll get non-trivial easily
as you have to consider the fact that GCC will treat signed
operations as having undefined behavior on overflow.

So I see why you want to do the extension above (re-interpret the
result), I suppose we can live with it but please make sure to
add a big fat ??? comment before it explaining why it is necessary.

Richard.

>>
>> The only case that I can think of points to a bug in strip_offset_1
>> again, namely if sizetype (the type of all offsets) is smaller than
>> a HOST_WIDE_INT in which case
>>
>> +    boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
>> +    *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT;
>>
>> is wrong as boffset / BITS_PER_UNIT does not do a signed division
>> then (for negative boffset which AFAIK does not happen - but it would
>> be technically allowed).  Thus, the predicates like
>>
>> +    && cst_and_fits_in_hwi (tmp)
>>
>> would need to be amended with a check that the MSB is not set.
> So I can handle it like:
>
> +    abs_boffset = abs_hwi (boffset);
> +    xxxxx = abs_boffset / BITS_PER_UNIT;
> +    if (boffset < 0)
> +      xxxxx = -xxxxx;
> +    *offset = off0 + int_cst_value (tmp) + xxxxx;
>
> Right?
>
>>
>> Btw, the cst_and_fits_in_hwi implementation is odd:
>>
>> bool
>> cst_and_fits_in_hwi (const_tree x)
>> {
>>   if (TREE_CODE (x) != INTEGER_CST)
>>     return false;
>>
>>   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
>>     return false;
>>
>>   return (TREE_INT_CST_HIGH (x) == 0
>>           || TREE_INT_CST_HIGH (x) == -1);
>> }
>>
>> the precision check seems totally pointless and I wonder what's
>> the point of this routine as there is host_integerp () already
>> and tree_low_cst instead of int_cst_value - oh, I see, the latter
>> forcefully sign-extends .... that should make the extension
>> not necessary.
> See above.
>
> Thanks.
> bin
Bin.Cheng - Oct. 3, 2013, 4:30 a.m.
Sorry that I don't understand tree type system well, so here are two
more questions, could you please explain little bit more?  Thanks very
much.

On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng <bin.cheng@arm.com> wrote:
>
> I don't think you need
>
> +  /* Sign extend off if expr is in type which has lower precision
> +     than HOST_WIDE_INT.  */
> +  if (TYPE_PRECISION (TREE_TYPE (expr)) <= HOST_BITS_PER_WIDE_INT)
> +    off = sext_hwi (off, TYPE_PRECISION (TREE_TYPE (expr)));
Is it possible to have type of expr smaller than the type of embedded
offset (i.e., sizetype)?  Should the sign extend be against sizetype
or it's safe with TREE_TYPE(expr)?

>
> at least it would be suspicious if you did ...
>
> The only case that I can think of points to a bug in strip_offset_1
> again, namely if sizetype (the type of all offsets) is smaller than
> a HOST_WIDE_INT in which case
>
> +    boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
> +    *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT;
>
> is wrong as boffset / BITS_PER_UNIT does not do a signed division
> then (for negative boffset which AFAIK does not happen - but it would
> be technically allowed).  Thus, the predicates like
>
> +    && cst_and_fits_in_hwi (tmp)
>
> would need to be amended with a check that the MSB is not set.
I am confused, why "boffset / BITS_PER_UNIT" won't do signed division
and how it relates to "sizetype smaller than HOST_WIDE_INT"?  If
sizetype is smaller, won't int_cst_value sign extends it into
HOST_WIDE_INT?

Thanks.
bin
Bin.Cheng - Oct. 8, 2013, 5:19 a.m.
On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng <bin.cheng@arm.com> wrote:
>>

>
> I don't think you need
>
> +  /* Sign extend off if expr is in type which has lower precision
> +     than HOST_WIDE_INT.  */
> +  if (TYPE_PRECISION (TREE_TYPE (expr)) <= HOST_BITS_PER_WIDE_INT)
> +    off = sext_hwi (off, TYPE_PRECISION (TREE_TYPE (expr)));
>
> at least it would be suspicious if you did ...
>
> The only case that I can think of points to a bug in strip_offset_1
> again, namely if sizetype (the type of all offsets) is smaller than
> a HOST_WIDE_INT in which case
>
> +    boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
> +    *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT;
>
> is wrong as boffset / BITS_PER_UNIT does not do a signed division
> then (for negative boffset which AFAIK does not happen - but it would
> be technically allowed).  Thus, the predicates like
>
> +    && cst_and_fits_in_hwi (tmp)
>
> would need to be amended with a check that the MSB is not set.
I think it twice and have below understandings.
1) "boffset / BITS_PER_UNIT" does not do signed division because
boffset might be negative and BIT_PER_UNIT could be defined as
unsigned for a target.
2) if sizetype is smaller enough than HOST_WIDE_INT, and if field
offset is large enough to have MSB set, then boffset would be computed
negative by int_cst_value.
3) If sizetype is as large as HOST_WIDE_INT, boffset would be negative
only if the field offset is a very large number with MSB set, but that
would be impossible for any structure.

Are these understandings right? And sorry to bother with the stupid
questions.  Thanks.

Patch

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 202599)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -2037,12 +2037,12 @@  find_interesting_uses (struct ivopts_data *data)
 
 static tree
 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
-		unsigned HOST_WIDE_INT *offset)
+		HOST_WIDE_INT *offset)
 {
   tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
   enum tree_code code;
   tree type, orig_type = TREE_TYPE (expr);
-  unsigned HOST_WIDE_INT off0, off1, st;
+  HOST_WIDE_INT off0, off1, st;
   tree orig_expr = expr;
 
   STRIP_NOPS (expr);
@@ -2133,19 +2133,26 @@  strip_offset_1 (tree expr, bool inside_addr, bool
       break;
 
     case COMPONENT_REF:
-      if (!inside_addr)
-	return orig_expr;
+      {
+	tree field;
+	HOST_WIDE_INT boffset = 0;
+	if (!inside_addr)
+	  return orig_expr;
 
-      tmp = component_ref_field_offset (expr);
-      if (top_compref
-	  && cst_and_fits_in_hwi (tmp))
-	{
-	  /* Strip the component reference completely.  */
-	  op0 = TREE_OPERAND (expr, 0);
-	  op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
-	  *offset = off0 + int_cst_value (tmp);
-	  return op0;
-	}
+	tmp = component_ref_field_offset (expr);
+	field = TREE_OPERAND (expr, 1);
+	if (top_compref
+	    && cst_and_fits_in_hwi (tmp)
+	    && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field)))
+	  {
+	    /* Strip the component reference completely.  */
+	    op0 = TREE_OPERAND (expr, 0);
+	    op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
+	    boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
+	    *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT;
+	    return op0;
+	  }
+      }
       break;
 
     case ADDR_EXPR:
@@ -2196,7 +2203,16 @@  strip_offset_1 (tree expr, bool inside_addr, bool
 static tree
 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
 {
-  return strip_offset_1 (expr, false, false, offset);
+  HOST_WIDE_INT off;
+  tree core = strip_offset_1 (expr, false, false, &off);
+
+  /* Sign extend off if expr is in type which has lower precision
+     than HOST_WIDE_INT.  */
+  if (TYPE_PRECISION (TREE_TYPE (expr)) <= HOST_BITS_PER_WIDE_INT)
+    off = sext_hwi (off, TYPE_PRECISION (TREE_TYPE (expr)));
+
+  *offset = off;
+  return core;
 }
 
 /* Returns variant of TYPE that can be used as base for different uses.