| Message ID | 001501ceb906$56da1c00$048e5400$@arm.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng <bin.cheng@arm.com> wrote: > Hi, > This patch fix two minor bugs when computing offset in IVOPT. > 1) Considering below example: > #define MAX 100 > struct tag > { > int i; > int j; > } > struct tag arr[MAX] > > int foo (int len) > { > int i = 0; > for (; i < len; i++) > { > access arr[i].j; > } > } > > Without this patch, the offset computed by strip_offset_1 for address > arr[i].j is ZERO, which is apparently not. > > 2) Considering below example: > //... > <bb 15>: > KeyIndex_66 = KeyIndex_194 + 4294967295; > if (KeyIndex_66 != 0) > goto <bb 16>; > else > goto <bb 18>; > > <bb 16>: > > <bb 17>: > # KeyIndex_194 = PHI <KeyIndex_66(16), KeyIndex_180(73)> > _62 = KeyIndex_194 + 1073741823; > _63 = _62 * 4; > _64 = pretmp_184 + _63; > _65 = *_64; > if (_65 == 0) > goto <bb 15>; > else > goto <bb 71>; > //... > > There are iv use and candidate like: > > use 1 > address > in statement _65 = *_64; > > at position *_64 > type handletype * > base pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4 > step 4294967292 > base object (void *) pretmp_184 > related candidates > > candidate 6 > var_before ivtmp.16 > var_after ivtmp.16 > incremented before use 1 > type unsigned int > base (unsigned int) (pretmp_184 + (sizetype) KeyIndex_180 * 4) > step 4294967292 > base object (void *) pretmp_184 > Candidate 6 is related to use 1 > > In function get_computation_cost_at for use 1 using cand 6, ubase and cbase > are: > pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4 > pretmp_184 + (sizetype) KeyIndex_180 * 4 > > The cstepi computed in HOST_WIDE_INT is : 0xfffffffffffffffc, while offset > computed in TYPE(utype) is : 0xfffffffc. Though they both stand for value > "-4" in different precision, statement "offset -= ratio * cstepi" returns > 0x100000000, which is wrong. > > Tested on x86_64 and arm. Is it OK? + field = TREE_OPERAND (expr, 1); + if (DECL_FIELD_BIT_OFFSET (field) + && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field))) + boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)); + + 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) + boffset / BITS_PER_UNIT; + return op0; + } the failure paths seem mangled, that is, if cst_and_fits_in_hwi is false for either offset part you may end up doing half accounting and not stripping. Btw, DECL_FIELD_BIT_OFFSET is always non-NULL. I suggest to rewrite to if (!inside_addr) return orig_expr; 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))) { ... } note that this doesn't really handle overflows correctly as + *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT; may still overflow. @@ -4133,6 +4142,9 @@ get_computation_cost_at (struct ivopts_data *data, bitmap_clear (*depends_on); } + /* Sign-extend offset if utype has lower precision than HOST_WIDE_INT. */ + offset = sext_hwi (offset, TYPE_PRECISION (utype)); + offset is computed elsewhere in difference_cost and the bug to me seems that it is unsigned. sign-extending it here is odd at least (and the extension should probably happen at sizetype precision, not that of utype). Richard. > Thanks. > bin > > > 2013-09-24 Bin Cheng <bin.cheng@arm.com> > > * tree-ssa-loop-ivopts.c (strip_offset_1): Count > DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. > (get_computation_cost_at): Sign extend offset.
On Tue, 2013-09-24 at 12:31 +0200, Richard Biener wrote: > On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng <bin.cheng@arm.com> wrote: > > Hi, > > This patch fix two minor bugs when computing offset in IVOPT. > > 1) Considering below example: > > #define MAX 100 > > struct tag > > { > > int i; > > int j; > > } > > struct tag arr[MAX] > > > > int foo (int len) > > { > > int i = 0; > > for (; i < len; i++) > > { > > access arr[i].j; > > } > > } > > > > Without this patch, the offset computed by strip_offset_1 for address > > arr[i].j is ZERO, which is apparently not. > > > > 2) Considering below example: > > //... > > <bb 15>: > > KeyIndex_66 = KeyIndex_194 + 4294967295; > > if (KeyIndex_66 != 0) > > goto <bb 16>; > > else > > goto <bb 18>; > > > > <bb 16>: > > > > <bb 17>: > > # KeyIndex_194 = PHI <KeyIndex_66(16), KeyIndex_180(73)> > > _62 = KeyIndex_194 + 1073741823; > > _63 = _62 * 4; > > _64 = pretmp_184 + _63; > > _65 = *_64; > > if (_65 == 0) > > goto <bb 15>; > > else > > goto <bb 71>; > > //... > > > > There are iv use and candidate like: > > > > use 1 > > address > > in statement _65 = *_64; > > > > at position *_64 > > type handletype * > > base pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4 > > step 4294967292 > > base object (void *) pretmp_184 > > related candidates > > > > candidate 6 > > var_before ivtmp.16 > > var_after ivtmp.16 > > incremented before use 1 > > type unsigned int > > base (unsigned int) (pretmp_184 + (sizetype) KeyIndex_180 * 4) > > step 4294967292 > > base object (void *) pretmp_184 > > Candidate 6 is related to use 1 > > > > In function get_computation_cost_at for use 1 using cand 6, ubase and cbase > > are: > > pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4 > > pretmp_184 + (sizetype) KeyIndex_180 * 4 > > > > The cstepi computed in HOST_WIDE_INT is : 0xfffffffffffffffc, while offset > > computed in TYPE(utype) is : 0xfffffffc. Though they both stand for value > > "-4" in different precision, statement "offset -= ratio * cstepi" returns > > 0x100000000, which is wrong. > > > > Tested on x86_64 and arm. Is it OK? > > + field = TREE_OPERAND (expr, 1); > + if (DECL_FIELD_BIT_OFFSET (field) > + && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field))) > + boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)); > + > + 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) + boffset / BITS_PER_UNIT; > + return op0; > + } > > the failure paths seem mangled, that is, if cst_and_fits_in_hwi is false > for either offset part you may end up doing half accounting and not > stripping. > > Btw, DECL_FIELD_BIT_OFFSET is always non-NULL. I suggest to > rewrite to > > if (!inside_addr) > return orig_expr; > > 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))) > { > ... > } > > note that this doesn't really handle overflows correctly as > > + *offset = off0 + int_cst_value (tmp) + boffset / BITS_PER_UNIT; > > may still overflow. > > @@ -4133,6 +4142,9 @@ get_computation_cost_at (struct ivopts_data *data, > bitmap_clear (*depends_on); > } > > + /* Sign-extend offset if utype has lower precision than HOST_WIDE_INT. */ > + offset = sext_hwi (offset, TYPE_PRECISION (utype)); > + > > offset is computed elsewhere in difference_cost and the bug to me seems that > it is unsigned. sign-extending it here is odd at least (and the extension > should probably happen at sizetype precision, not that of utype). > After reading "overflow" and "ivopt", I was wondering whether http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55190 is somehow related. Cheers, Oleg
> -----Original Message----- > From: Richard Biener [mailto:richard.guenther@gmail.com] > Sent: Tuesday, September 24, 2013 6:31 PM > To: Bin Cheng > Cc: GCC Patches > Subject: Re: [PATCH]Fix computation of offset in ivopt > > On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng <bin.cheng@arm.com> wrote: > > + field = TREE_OPERAND (expr, 1); > + if (DECL_FIELD_BIT_OFFSET (field) > + && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field))) > + boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)); > + > + 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) + boffset / BITS_PER_UNIT; > + return op0; > + } > > the failure paths seem mangled, that is, if cst_and_fits_in_hwi is false for > either offset part you may end up doing half accounting and not stripping. > > Btw, DECL_FIELD_BIT_OFFSET is always non-NULL. I suggest to rewrite to > > if (!inside_addr) > return orig_expr; > > 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))) > { > ... > } Will be refined. > > note that this doesn't really handle overflows correctly as > > + *offset = off0 + int_cst_value (tmp) + boffset / > + BITS_PER_UNIT; > > may still overflow. Since it's "unsigned + signed + signed", according to implicit conversion, the signed operand will be converted to unsigned, so the overflow would only happen when off0 is huge number and tmp/boffset is large positive number, right? Do I need to check whether off0 is larger than the overflowed result? Also there is signed->unsigned problem here, see below. > > @@ -4133,6 +4142,9 @@ get_computation_cost_at (struct ivopts_data *data, > bitmap_clear (*depends_on); > } > > + /* Sign-extend offset if utype has lower precision than > + HOST_WIDE_INT. */ offset = sext_hwi (offset, TYPE_PRECISION > + (utype)); > + > > offset is computed elsewhere in difference_cost and the bug to me seems > that it is unsigned. sign-extending it here is odd at least (and the extension > should probably happen at sizetype precision, not that of utype). I agree, The root cause is in split_offset_1, in which offset is computed. Every time offset is computed in this function with a signed operand (like "int_cst_value (tmp)" above), we need to take care the possible negative number problem. Take this case as an example, we need to do below change: 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? Thanks. bin
> -----Original Message----- > From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches- > owner@gcc.gnu.org] On Behalf Of bin.cheng > Sent: Friday, September 27, 2013 1:07 PM > To: 'Richard Biener' > Cc: GCC Patches > Subject: RE: [PATCH]Fix computation of offset in ivopt > > > > > -----Original Message----- > > From: Richard Biener [mailto:richard.guenther@gmail.com] > > Sent: Tuesday, September 24, 2013 6:31 PM > > To: Bin Cheng > > Cc: GCC Patches > > Subject: Re: [PATCH]Fix computation of offset in ivopt > > > > On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng <bin.cheng@arm.com> wrote: > > > > + field = TREE_OPERAND (expr, 1); > > + if (DECL_FIELD_BIT_OFFSET (field) > > + && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field))) > > + boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)); > > + > > + 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) + boffset / > BITS_PER_UNIT; > > + return op0; > > + } > > > > the failure paths seem mangled, that is, if cst_and_fits_in_hwi is > > false > for > > either offset part you may end up doing half accounting and not stripping. > > > > Btw, DECL_FIELD_BIT_OFFSET is always non-NULL. I suggest to rewrite > > to > > > > if (!inside_addr) > > return orig_expr; > > > > 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))) > > { > > ... > > } > Will be refined. > > > > > note that this doesn't really handle overflows correctly as > > > > + *offset = off0 + int_cst_value (tmp) + boffset / > > + BITS_PER_UNIT; > > > > may still overflow. > Since it's "unsigned + signed + signed", according to implicit conversion, the > signed operand will be converted to unsigned, so the overflow would only > happen when off0 is huge number and tmp/boffset is large positive number, > right? Do I need to check whether off0 is larger than the overflowed result? > Also there is signed->unsigned problem here, see below. > > > > > @@ -4133,6 +4142,9 @@ get_computation_cost_at (struct ivopts_data > *data, > > bitmap_clear (*depends_on); > > } > > > > + /* Sign-extend offset if utype has lower precision than > > + HOST_WIDE_INT. */ offset = sext_hwi (offset, TYPE_PRECISION > > + (utype)); > > + > > > > offset is computed elsewhere in difference_cost and the bug to me > > seems that it is unsigned. sign-extending it here is odd at least > > (and the > extension > > should probably happen at sizetype precision, not that of utype). > I agree, The root cause is in split_offset_1, in which offset is computed. > Every time offset is computed in this function with a signed operand (like > "int_cst_value (tmp)" above), we need to take care the possible negative > number problem. Take this case as an example, we need to do below > change: > > 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? Thought twice, I guess we can compute signed offset in strip_offset_1 and sign extend it for strip_offset, thus we don't need to change every computation of offset in that function. Thanks. bin
On Fri, Sep 27, 2013 at 7:07 AM, bin.cheng <bin.cheng@arm.com> wrote: > > >> -----Original Message----- >> From: Richard Biener [mailto:richard.guenther@gmail.com] >> Sent: Tuesday, September 24, 2013 6:31 PM >> To: Bin Cheng >> Cc: GCC Patches >> Subject: Re: [PATCH]Fix computation of offset in ivopt >> >> On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng <bin.cheng@arm.com> wrote: >> >> + field = TREE_OPERAND (expr, 1); >> + if (DECL_FIELD_BIT_OFFSET (field) >> + && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field))) >> + boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)); >> + >> + 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) + boffset / > BITS_PER_UNIT; >> + return op0; >> + } >> >> the failure paths seem mangled, that is, if cst_and_fits_in_hwi is false > for >> either offset part you may end up doing half accounting and not stripping. >> >> Btw, DECL_FIELD_BIT_OFFSET is always non-NULL. I suggest to rewrite to >> >> if (!inside_addr) >> return orig_expr; >> >> 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))) >> { >> ... >> } > Will be refined. > >> >> note that this doesn't really handle overflows correctly as >> >> + *offset = off0 + int_cst_value (tmp) + boffset / >> + BITS_PER_UNIT; >> >> may still overflow. > Since it's "unsigned + signed + signed", according to implicit conversion, > the signed operand will be converted to unsigned, so the overflow would only > happen when off0 is huge number and tmp/boffset is large positive number, > right? Do I need to check whether off0 is larger than the overflowed > result? Also there is signed->unsigned problem here, see below. > >> >> @@ -4133,6 +4142,9 @@ get_computation_cost_at (struct ivopts_data *data, >> bitmap_clear (*depends_on); >> } >> >> + /* Sign-extend offset if utype has lower precision than >> + HOST_WIDE_INT. */ offset = sext_hwi (offset, TYPE_PRECISION >> + (utype)); >> + >> >> offset is computed elsewhere in difference_cost and the bug to me seems >> that it is unsigned. sign-extending it here is odd at least (and the > extension >> should probably happen at sizetype precision, not that of utype). > I agree, The root cause is in split_offset_1, in which offset is computed. > Every time offset is computed in this function with a signed operand (like > "int_cst_value (tmp)" above), we need to take care the possible negative > number problem. Take this case as an example, we need to do below change: > > 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 ;) Richard. > Thanks. > bin > > >
> -----Original Message----- > From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches- > owner@gcc.gnu.org] On Behalf Of Oleg Endo > Sent: Wednesday, September 25, 2013 1:41 AM > To: Richard Biener > Cc: Bin Cheng; GCC Patches > Subject: Re: [PATCH]Fix computation of offset in ivopt > > > > > After reading "overflow" and "ivopt", I was wondering whether > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55190 is somehow related. No, this patch is irrelevant. But I do have some thought on the pr55190 and will follow in the bug entry. Thanks. bin
Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 200774) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -2133,19 +2133,28 @@ 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; - } + field = TREE_OPERAND (expr, 1); + if (DECL_FIELD_BIT_OFFSET (field) + && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field))) + boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)); + + 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) + boffset / BITS_PER_UNIT; + return op0; + } + } break; case ADDR_EXPR: @@ -4133,6 +4142,9 @@ get_computation_cost_at (struct ivopts_data *data, bitmap_clear (*depends_on); } + /* Sign-extend offset if utype has lower precision than HOST_WIDE_INT. */ + offset = sext_hwi (offset, TYPE_PRECISION (utype)); + /* If we are after the increment, the value of the candidate is higher by one iteration. */ if (stmt_is_after_inc)
Hi, This patch fix two minor bugs when computing offset in IVOPT. 1) Considering below example: #define MAX 100 struct tag { int i; int j; } struct tag arr[MAX] int foo (int len) { int i = 0; for (; i < len; i++) { access arr[i].j; } } Without this patch, the offset computed by strip_offset_1 for address arr[i].j is ZERO, which is apparently not. 2) Considering below example: //... <bb 15>: KeyIndex_66 = KeyIndex_194 + 4294967295; if (KeyIndex_66 != 0) goto <bb 16>; else goto <bb 18>; <bb 16>: <bb 17>: # KeyIndex_194 = PHI <KeyIndex_66(16), KeyIndex_180(73)> _62 = KeyIndex_194 + 1073741823; _63 = _62 * 4; _64 = pretmp_184 + _63; _65 = *_64; if (_65 == 0) goto <bb 15>; else goto <bb 71>; //... There are iv use and candidate like: use 1 address in statement _65 = *_64; at position *_64 type handletype * base pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4 step 4294967292 base object (void *) pretmp_184 related candidates candidate 6 var_before ivtmp.16 var_after ivtmp.16 incremented before use 1 type unsigned int base (unsigned int) (pretmp_184 + (sizetype) KeyIndex_180 * 4) step 4294967292 base object (void *) pretmp_184 Candidate 6 is related to use 1 In function get_computation_cost_at for use 1 using cand 6, ubase and cbase are: pretmp_184 + ((sizetype) KeyIndex_180 + 1073741823) * 4 pretmp_184 + (sizetype) KeyIndex_180 * 4 The cstepi computed in HOST_WIDE_INT is : 0xfffffffffffffffc, while offset computed in TYPE(utype) is : 0xfffffffc. Though they both stand for value "-4" in different precision, statement "offset -= ratio * cstepi" returns 0x100000000, which is wrong. Tested on x86_64 and arm. Is it OK? Thanks. bin 2013-09-24 Bin Cheng <bin.cheng@arm.com> * tree-ssa-loop-ivopts.c (strip_offset_1): Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. (get_computation_cost_at): Sign extend offset.