Re: [PATCH]Fix computation of offset in ivopt
On Thu, Nov 7, 2013 at 6:47 PM, Richard Biener richard.guent...@gmail.com wrote: On Wed, Nov 6, 2013 at 6:06 PM, Richard Sandiford rdsandif...@googlemail.com wrote: Hi, bin.cheng bin.ch...@arm.com writes: Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop-ivopts.c(revision 203267) +++ 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,32 @@ strip_offset_1 (tree expr, bool inside_addr, bool break; case COMPONENT_REF: - if (!inside_addr) - return orig_expr; + { + tree 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); - return op0; - } + 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))) While comparing output for wide-int and mainline, I noticed that this condition is now always false on x86_64, since DECL_FIELD_BIT_OFFSET is a 128-bit bitsizetype and since cst_and_fits_in_hwi rejects constants with precision greater than HWI: if (TREE_CODE (x) != INTEGER_CST) return false; if (TYPE_PRECISION (TREE_TYPE (x)) HOST_BITS_PER_WIDE_INT) return false; I think that's simply overly restrictive on the side of cst_and_fits_in_hwi. I suppose this function is meant to complement int_cst_value (digging in history might be nice here). Should this be host_integerp (DECL_FIELD_BIT_OFFSET (field), 0) instead? That's not the same as it rejects -1U. The function seems to ask if the value, if casted to unsigned fits in a HOST_WIDE_INT. So just drop the precision check from cst_and_fits_in_hwi. Hi, With check in of patch lowering address expression in ivo, that piece of code won't be executed anymore. So still need to drop precision check in cst_and_fits_in_hwi? The major part of strip_offset_1 can be cleaned now. Thanks, bin -- Best Regards.
Re: [PATCH]Fix computation of offset in ivopt
On Wed, Nov 13, 2013 at 12:18 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Thu, Nov 7, 2013 at 6:47 PM, Richard Biener richard.guent...@gmail.com wrote: On Wed, Nov 6, 2013 at 6:06 PM, Richard Sandiford rdsandif...@googlemail.com wrote: Hi, bin.cheng bin.ch...@arm.com writes: Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop-ivopts.c(revision 203267) +++ 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,32 @@ strip_offset_1 (tree expr, bool inside_addr, bool break; case COMPONENT_REF: - if (!inside_addr) - return orig_expr; + { + tree 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); - return op0; - } + 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))) While comparing output for wide-int and mainline, I noticed that this condition is now always false on x86_64, since DECL_FIELD_BIT_OFFSET is a 128-bit bitsizetype and since cst_and_fits_in_hwi rejects constants with precision greater than HWI: if (TREE_CODE (x) != INTEGER_CST) return false; if (TYPE_PRECISION (TREE_TYPE (x)) HOST_BITS_PER_WIDE_INT) return false; I think that's simply overly restrictive on the side of cst_and_fits_in_hwi. I suppose this function is meant to complement int_cst_value (digging in history might be nice here). Should this be host_integerp (DECL_FIELD_BIT_OFFSET (field), 0) instead? That's not the same as it rejects -1U. The function seems to ask if the value, if casted to unsigned fits in a HOST_WIDE_INT. So just drop the precision check from cst_and_fits_in_hwi. Hi, With check in of patch lowering address expression in ivo, that piece of code won't be executed anymore. So still need to drop precision check in cst_and_fits_in_hwi? The major part of strip_offset_1 can be cleaned now. I think it's a good cleanup, so if you can bootstrap test that change separately? Thanks, Richard. Thanks, bin -- Best Regards.
Re: [PATCH]Fix computation of offset in ivopt
On Wed, Nov 13, 2013 at 7:26 PM, Richard Biener richard.guent...@gmail.com wrote: On Wed, Nov 13, 2013 at 12:18 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Thu, Nov 7, 2013 at 6:47 PM, Richard Biener richard.guent...@gmail.com wrote: On Wed, Nov 6, 2013 at 6:06 PM, Richard Sandiford rdsandif...@googlemail.com wrote: Hi, bin.cheng bin.ch...@arm.com writes: Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop-ivopts.c(revision 203267) +++ 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,32 @@ strip_offset_1 (tree expr, bool inside_addr, bool break; case COMPONENT_REF: - if (!inside_addr) - return orig_expr; + { + tree 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); - return op0; - } + 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))) While comparing output for wide-int and mainline, I noticed that this condition is now always false on x86_64, since DECL_FIELD_BIT_OFFSET is a 128-bit bitsizetype and since cst_and_fits_in_hwi rejects constants with precision greater than HWI: if (TREE_CODE (x) != INTEGER_CST) return false; if (TYPE_PRECISION (TREE_TYPE (x)) HOST_BITS_PER_WIDE_INT) return false; I think that's simply overly restrictive on the side of cst_and_fits_in_hwi. I suppose this function is meant to complement int_cst_value (digging in history might be nice here). Should this be host_integerp (DECL_FIELD_BIT_OFFSET (field), 0) instead? That's not the same as it rejects -1U. The function seems to ask if the value, if casted to unsigned fits in a HOST_WIDE_INT. So just drop the precision check from cst_and_fits_in_hwi. Hi, With check in of patch lowering address expression in ivo, that piece of code won't be executed anymore. So still need to drop precision check in cst_and_fits_in_hwi? The major part of strip_offset_1 can be cleaned now. I think it's a good cleanup, so if you can bootstrap test that change separately? Will do. -- Best Regards.
Re: [PATCH]Fix computation of offset in ivopt
On Wed, Nov 6, 2013 at 6:06 PM, Richard Sandiford rdsandif...@googlemail.com wrote: Hi, bin.cheng bin.ch...@arm.com writes: Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop-ivopts.c(revision 203267) +++ 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,32 @@ strip_offset_1 (tree expr, bool inside_addr, bool break; case COMPONENT_REF: - if (!inside_addr) - return orig_expr; + { + tree 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); - return op0; - } + 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))) While comparing output for wide-int and mainline, I noticed that this condition is now always false on x86_64, since DECL_FIELD_BIT_OFFSET is a 128-bit bitsizetype and since cst_and_fits_in_hwi rejects constants with precision greater than HWI: if (TREE_CODE (x) != INTEGER_CST) return false; if (TYPE_PRECISION (TREE_TYPE (x)) HOST_BITS_PER_WIDE_INT) return false; I think that's simply overly restrictive on the side of cst_and_fits_in_hwi. I suppose this function is meant to complement int_cst_value (digging in history might be nice here). Should this be host_integerp (DECL_FIELD_BIT_OFFSET (field), 0) instead? That's not the same as it rejects -1U. The function seems to ask if the value, if casted to unsigned fits in a HOST_WIDE_INT. So just drop the precision check from cst_and_fits_in_hwi. Richard. + { + HOST_WIDE_INT boffset, abs_off; + + /* 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)); + abs_off = abs_hwi (boffset) / BITS_PER_UNIT; + if (boffset 0) + abs_off = -abs_off; + + *offset = off0 + int_cst_value (tmp) + abs_off; + return op0; + } + } break; Thanks, Richard
Re: [PATCH]Fix computation of offset in ivopt
Hi, bin.cheng bin.ch...@arm.com writes: Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop-ivopts.c(revision 203267) +++ 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,32 @@ strip_offset_1 (tree expr, bool inside_addr, bool break; case COMPONENT_REF: - if (!inside_addr) - return orig_expr; + { + tree 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); - return op0; - } + 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))) While comparing output for wide-int and mainline, I noticed that this condition is now always false on x86_64, since DECL_FIELD_BIT_OFFSET is a 128-bit bitsizetype and since cst_and_fits_in_hwi rejects constants with precision greater than HWI: if (TREE_CODE (x) != INTEGER_CST) return false; if (TYPE_PRECISION (TREE_TYPE (x)) HOST_BITS_PER_WIDE_INT) return false; Should this be host_integerp (DECL_FIELD_BIT_OFFSET (field), 0) instead? + { + HOST_WIDE_INT boffset, abs_off; + + /* 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)); + abs_off = abs_hwi (boffset) / BITS_PER_UNIT; + if (boffset 0) + abs_off = -abs_off; + + *offset = off0 + int_cst_value (tmp) + abs_off; + return op0; + } + } break; Thanks, Richard
Re: [PATCH]Fix computation of offset in ivopt
On Thu, Nov 7, 2013 at 1:06 AM, Richard Sandiford rdsandif...@googlemail.com wrote: Hi, bin.cheng bin.ch...@arm.com writes: Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop-ivopts.c(revision 203267) +++ 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,32 @@ strip_offset_1 (tree expr, bool inside_addr, bool break; case COMPONENT_REF: - if (!inside_addr) - return orig_expr; + { + tree 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); - return op0; - } + 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))) While comparing output for wide-int and mainline, I noticed that this condition is now always false on x86_64, since DECL_FIELD_BIT_OFFSET is a 128-bit bitsizetype and since cst_and_fits_in_hwi rejects constants with precision greater than HWI: Hi, Sorry for this, I should have handled the bsizetype in the first place. What I am not sure is how to do with big DECL_FIELD_BIT_OFFSET which even can't be accepted by host_integerp. Generally it's very unlikely to happen and we don't handle such exceptions in GCC, right? I will send a patch fixing the issue. Hopefully, with the patch just got approved at http://gcc.gnu.org/ml/gcc-patches/2013-10/msg02367.html , IVOPT will never see complex address expressions any more, and major part of strip_offset_1 (maybe other functions) can be cleaned. Thanks, bin if (TREE_CODE (x) != INTEGER_CST) return false; if (TYPE_PRECISION (TREE_TYPE (x)) HOST_BITS_PER_WIDE_INT) return false; Should this be host_integerp (DECL_FIELD_BIT_OFFSET (field), 0) instead? + { + HOST_WIDE_INT boffset, abs_off; + + /* 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)); + abs_off = abs_hwi (boffset) / BITS_PER_UNIT; + if (boffset 0) + abs_off = -abs_off; + + *offset = off0 + int_cst_value (tmp) + abs_off; + return op0; + } + } break; Thanks, Richard -- Best Regards.
Re: [PATCH]Fix computation of offset in ivopt
On Mon, Oct 21, 2013 at 8:21 PM, Richard Biener richard.guent...@gmail.com wrote: On Fri, Oct 18, 2013 at 5:48 PM, Bin.Cheng amker.ch...@gmail.com wrote: Hi Richard, Is the first patch OK? Since there is a patch depending on it. http://gcc.gnu.org/ml/gcc-patches/2013-09/msg01931.html Yes. I committed the patch fixing strip_offset_1 as r204116. Since the root cause of the second issue is POINTER_PLUS_EXPR requires an unsigned offset operand and can't be fixed as in the second patch, I will discard that patch. Thanks. bin On Fri, Oct 18, 2013 at 7:18 PM, Richard Biener richard.guent...@gmail.com wrote: On Thu, Oct 17, 2013 at 7:52 AM, bin.cheng bin.ch...@arm.com wrote: Hi, As noted in previous messages, GCC forces offset to unsigned in middle end. It also gets offset value and stores it in HOST_WIDE_INT then uses it in various computation. In this scenario, It should use int_cst_value to do additional sign extension against the type of tree node, otherwise we might lose sign information. Take function fold_plusminus_mult_expr as an example, the sign information of arg01/arg11 might be lost because it uses TREE_INT_CST_LOW directly. I think this is the offender of the problem in this thread. I think we should fix the offender, rather the hacking strip_offset as in the original patch, so I split original patch into two as attached, with one fixing the offset of COMPONENT_REF in strip_offset_1, the other fixing the mentioned sign extension problem. Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. The above means that strip_offset_1 cannot reliably look through MULT_EXPRs as that can make an offset X * CST that is effectively signed surely unsigned in the process. Think of this looking into X * CST as performing a division - whose result is dependent on the sign of X which we lost with our unsigned casting. Now, removing the MULT_EXPR look-through might be too pessimizing ... but it may be worth trying to see if it fixes your issue? In this context I also remember a new bug filed recently of us not folding x /[ex] 4 * 4 to x. In the past I was working multiple times on stopping doing that (make all offsets unsigned), but I never managed to finish ... Richard. Bootstrap and test on x86/x86_64/arm. Is it OK? Thanks. bin Patch a: 2013-10-17 Bin Cheng bin.ch...@arm.com * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type. Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. Patch b: 2013-10-17 Bin Cheng bin.ch...@arm.com * fold-const.c (fold_plusminus_mult_expr): Use int_cst_value instead of TREE_INT_CST_LOW. gcc/testsuite/ChangeLog 2013-10-17 Bin Cheng bin.ch...@arm.com * gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test. -Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Wednesday, October 02, 2013 4:32 PM To: Bin.Cheng Cc: Bin Cheng; GCC Patches Subject: Re: [PATCH]Fix computation of offset in ivopt On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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
Re: [PATCH]Fix computation of offset in ivopt
On Fri, Oct 18, 2013 at 5:48 PM, Bin.Cheng amker.ch...@gmail.com wrote: Hi Richard, Is the first patch OK? Since there is a patch depending on it. http://gcc.gnu.org/ml/gcc-patches/2013-09/msg01931.html Yes. Richard. Thanks. bin On Fri, Oct 18, 2013 at 7:18 PM, Richard Biener richard.guent...@gmail.com wrote: On Thu, Oct 17, 2013 at 7:52 AM, bin.cheng bin.ch...@arm.com wrote: Hi, As noted in previous messages, GCC forces offset to unsigned in middle end. It also gets offset value and stores it in HOST_WIDE_INT then uses it in various computation. In this scenario, It should use int_cst_value to do additional sign extension against the type of tree node, otherwise we might lose sign information. Take function fold_plusminus_mult_expr as an example, the sign information of arg01/arg11 might be lost because it uses TREE_INT_CST_LOW directly. I think this is the offender of the problem in this thread. I think we should fix the offender, rather the hacking strip_offset as in the original patch, so I split original patch into two as attached, with one fixing the offset of COMPONENT_REF in strip_offset_1, the other fixing the mentioned sign extension problem. Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. The above means that strip_offset_1 cannot reliably look through MULT_EXPRs as that can make an offset X * CST that is effectively signed surely unsigned in the process. Think of this looking into X * CST as performing a division - whose result is dependent on the sign of X which we lost with our unsigned casting. Now, removing the MULT_EXPR look-through might be too pessimizing ... but it may be worth trying to see if it fixes your issue? In this context I also remember a new bug filed recently of us not folding x /[ex] 4 * 4 to x. In the past I was working multiple times on stopping doing that (make all offsets unsigned), but I never managed to finish ... Richard. Bootstrap and test on x86/x86_64/arm. Is it OK? Thanks. bin Patch a: 2013-10-17 Bin Cheng bin.ch...@arm.com * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type. Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. Patch b: 2013-10-17 Bin Cheng bin.ch...@arm.com * fold-const.c (fold_plusminus_mult_expr): Use int_cst_value instead of TREE_INT_CST_LOW. gcc/testsuite/ChangeLog 2013-10-17 Bin Cheng bin.ch...@arm.com * gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test. -Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Wednesday, October 02, 2013 4:32 PM To: Bin.Cheng Cc: Bin Cheng; GCC Patches Subject: Re: [PATCH]Fix computation of offset in ivopt On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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
Re: [PATCH]Fix computation of offset in ivopt
On Fri, Oct 18, 2013 at 7:18 PM, Richard Biener richard.guent...@gmail.com wrote: On Thu, Oct 17, 2013 at 7:52 AM, bin.cheng bin.ch...@arm.com wrote: Hi, As noted in previous messages, GCC forces offset to unsigned in middle end. It also gets offset value and stores it in HOST_WIDE_INT then uses it in various computation. In this scenario, It should use int_cst_value to do additional sign extension against the type of tree node, otherwise we might lose sign information. Take function fold_plusminus_mult_expr as an example, the sign information of arg01/arg11 might be lost because it uses TREE_INT_CST_LOW directly. I think this is the offender of the problem in this thread. I think we should fix the offender, rather the hacking strip_offset as in the original patch, so I split original patch into two as attached, with one fixing the offset of COMPONENT_REF in strip_offset_1, the other fixing the mentioned sign extension problem. Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. As far as the patch itself. I think the preceding host_integerp already checks for this case: int host_integerp (const_tree t, int pos) { if (t == NULL_TREE) return 0; return (TREE_CODE (t) == INTEGER_CST ((TREE_INT_CST_HIGH (t) == 0 (HOST_WIDE_INT) TREE_INT_CST_LOW (t) = 0) || (! pos TREE_INT_CST_HIGH (t) == -1 (HOST_WIDE_INT) TREE_INT_CST_LOW (t) 0 !TYPE_UNSIGNED (TREE_TYPE (t))) || (pos TREE_INT_CST_HIGH (t) == 0))); } Since the call is host_integerp (xxx, 0), it returns 0 for large unsigned numbers, right? The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. The above means that strip_offset_1 cannot reliably look through MULT_EXPRs as that can make an offset X * CST that is effectively signed surely unsigned in the process. Think of this looking into X * CST as performing a division - whose result is dependent on the sign of X which we lost with our unsigned casting. Now, removing the MULT_EXPR look-through might be too pessimizing ... but it may be worth trying to see if it fixes your issue? In this context I also remember a new bug filed recently of us not folding x /[ex] 4 * 4 to x. In the past I was working multiple times on stopping doing that (make all offsets unsigned), but I never managed to finish ... Richard. Bootstrap and test on x86/x86_64/arm. Is it OK? Thanks. bin Patch a: 2013-10-17 Bin Cheng bin.ch...@arm.com * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type. Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. Patch b: 2013-10-17 Bin Cheng bin.ch...@arm.com * fold-const.c (fold_plusminus_mult_expr): Use int_cst_value instead of TREE_INT_CST_LOW. gcc/testsuite/ChangeLog 2013-10-17 Bin Cheng bin.ch...@arm.com * gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test. -Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Wednesday, October 02, 2013 4:32 PM To: Bin.Cheng Cc: Bin Cheng; GCC Patches Subject: Re: [PATCH]Fix computation of offset in ivopt On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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
Re: [PATCH]Fix computation of offset in ivopt
On Thu, Oct 17, 2013 at 7:52 AM, bin.cheng bin.ch...@arm.com wrote: Hi, As noted in previous messages, GCC forces offset to unsigned in middle end. It also gets offset value and stores it in HOST_WIDE_INT then uses it in various computation. In this scenario, It should use int_cst_value to do additional sign extension against the type of tree node, otherwise we might lose sign information. Take function fold_plusminus_mult_expr as an example, the sign information of arg01/arg11 might be lost because it uses TREE_INT_CST_LOW directly. I think this is the offender of the problem in this thread. I think we should fix the offender, rather the hacking strip_offset as in the original patch, so I split original patch into two as attached, with one fixing the offset of COMPONENT_REF in strip_offset_1, the other fixing the mentioned sign extension problem. Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. The above means that strip_offset_1 cannot reliably look through MULT_EXPRs as that can make an offset X * CST that is effectively signed surely unsigned in the process. Think of this looking into X * CST as performing a division - whose result is dependent on the sign of X which we lost with our unsigned casting. Now, removing the MULT_EXPR look-through might be too pessimizing ... but it may be worth trying to see if it fixes your issue? In this context I also remember a new bug filed recently of us not folding x /[ex] 4 * 4 to x. In the past I was working multiple times on stopping doing that (make all offsets unsigned), but I never managed to finish ... Richard. Bootstrap and test on x86/x86_64/arm. Is it OK? Thanks. bin Patch a: 2013-10-17 Bin Cheng bin.ch...@arm.com * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type. Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. Patch b: 2013-10-17 Bin Cheng bin.ch...@arm.com * fold-const.c (fold_plusminus_mult_expr): Use int_cst_value instead of TREE_INT_CST_LOW. gcc/testsuite/ChangeLog 2013-10-17 Bin Cheng bin.ch...@arm.com * gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test. -Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Wednesday, October 02, 2013 4:32 PM To: Bin.Cheng Cc: Bin Cheng; GCC Patches Subject: Re: [PATCH]Fix computation of offset in ivopt On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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
Re: [PATCH]Fix computation of offset in ivopt
On 10/18/2013 01:18 PM, Richard Biener wrote: Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. I still have patches to keep pointer types in ivopts (using a new POINTER_PLUSV_EXPR). Would that help in this case? Last time I posted them they met an unenthusiastic reception so I've never bothered to repost them. Bernd
Re: [PATCH]Fix computation of offset in ivopt
On Fri, Oct 18, 2013 at 2:02 PM, Bernd Schmidt ber...@codesourcery.com wrote: On 10/18/2013 01:18 PM, Richard Biener wrote: Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. I still have patches to keep pointer types in ivopts (using a new POINTER_PLUSV_EXPR). Would that help in this case? Last time I posted them they met an unenthusiastic reception so I've never bothered to repost them. Can you point me to that patch? Or shortly elaborate on keep pointer types in ivopts? I think this issue is about decomposing offset computations into a constant and a variable part, which after foldings messed up the unsigned computation can result in odd constant offset parts. So it's rather because the offset operand of POINTER_PLUS_EXPR is fixed as sizetype. Richard. Bernd
Re: [PATCH]Fix computation of offset in ivopt
On 10/18/2013 02:10 PM, Richard Biener wrote: On Fri, Oct 18, 2013 at 2:02 PM, Bernd Schmidt ber...@codesourcery.com wrote: On 10/18/2013 01:18 PM, Richard Biener wrote: Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. I still have patches to keep pointer types in ivopts (using a new POINTER_PLUSV_EXPR). Would that help in this case? Last time I posted them they met an unenthusiastic reception so I've never bothered to repost them. Can you point me to that patch? Or shortly elaborate on keep pointer types in ivopts? I think this issue is about decomposing offset computations into a constant and a variable part, which after foldings messed up the unsigned computation can result in odd constant offset parts. So it's rather because the offset operand of POINTER_PLUS_EXPR is fixed as sizetype. Okay, my patch doesn't address that part, it only ensures the pointer base values are kept and arithmetic on them is done using POINTER_PLUS. The original patch was here. http://gcc.gnu.org/ml/gcc-patches/2012-03/msg01104.html Bernd
Re: [PATCH]Fix computation of offset in ivopt
On Fri, Oct 18, 2013 at 2:26 PM, Bernd Schmidt ber...@codesourcery.com wrote: On 10/18/2013 02:10 PM, Richard Biener wrote: On Fri, Oct 18, 2013 at 2:02 PM, Bernd Schmidt ber...@codesourcery.com wrote: On 10/18/2013 01:18 PM, Richard Biener wrote: Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. I still have patches to keep pointer types in ivopts (using a new POINTER_PLUSV_EXPR). Would that help in this case? Last time I posted them they met an unenthusiastic reception so I've never bothered to repost them. Can you point me to that patch? Or shortly elaborate on keep pointer types in ivopts? I think this issue is about decomposing offset computations into a constant and a variable part, which after foldings messed up the unsigned computation can result in odd constant offset parts. So it's rather because the offset operand of POINTER_PLUS_EXPR is fixed as sizetype. Okay, my patch doesn't address that part, it only ensures the pointer base values are kept and arithmetic on them is done using POINTER_PLUS. Ah, I recently fixed parts of that I think ... 2013-09-02 Richard Biener rguent...@suse.de * tree-affine.c (add_elt_to_tree): Avoid converting all pointer arithmetic to sizetype. maybe you can double-check if the result is what you desired ;) Richard. The original patch was here. http://gcc.gnu.org/ml/gcc-patches/2012-03/msg01104.html Bernd
Re: [PATCH]Fix computation of offset in ivopt
Hi Richard, Is the first patch OK? Since there is a patch depending on it. http://gcc.gnu.org/ml/gcc-patches/2013-09/msg01931.html Thanks. bin On Fri, Oct 18, 2013 at 7:18 PM, Richard Biener richard.guent...@gmail.com wrote: On Thu, Oct 17, 2013 at 7:52 AM, bin.cheng bin.ch...@arm.com wrote: Hi, As noted in previous messages, GCC forces offset to unsigned in middle end. It also gets offset value and stores it in HOST_WIDE_INT then uses it in various computation. In this scenario, It should use int_cst_value to do additional sign extension against the type of tree node, otherwise we might lose sign information. Take function fold_plusminus_mult_expr as an example, the sign information of arg01/arg11 might be lost because it uses TREE_INT_CST_LOW directly. I think this is the offender of the problem in this thread. I think we should fix the offender, rather the hacking strip_offset as in the original patch, so I split original patch into two as attached, with one fixing the offset of COMPONENT_REF in strip_offset_1, the other fixing the mentioned sign extension problem. Index: gcc/fold-const.c === --- gcc/fold-const.c (revision 203267) +++ gcc/fold-const.c (working copy) @@ -7270,8 +7270,8 @@ fold_plusminus_mult_expr (location_t loc, enum tre HOST_WIDE_INT int01, int11, tmp; bool swap = false; tree maybe_same; - int01 = TREE_INT_CST_LOW (arg01); - int11 = TREE_INT_CST_LOW (arg11); + int01 = int_cst_value (arg01); + int11 = int_cst_value (arg11); this is not correct - it will mishandle all large unsigned numbers. The real issue is that we rely on twos-complement arithmetic to work when operating on pointer offsets (because we convert them all to unsigned sizetype). That makes interpreting the offsets or expressions that compute offsets hard (or impossible in some cases), as you can see from the issues in IVOPTs. The above means that strip_offset_1 cannot reliably look through MULT_EXPRs as that can make an offset X * CST that is effectively signed surely unsigned in the process. Think of this looking into X * CST as performing a division - whose result is dependent on the sign of X which we lost with our unsigned casting. Now, removing the MULT_EXPR look-through might be too pessimizing ... but it may be worth trying to see if it fixes your issue? In this context I also remember a new bug filed recently of us not folding x /[ex] 4 * 4 to x. In the past I was working multiple times on stopping doing that (make all offsets unsigned), but I never managed to finish ... Richard. Bootstrap and test on x86/x86_64/arm. Is it OK? Thanks. bin Patch a: 2013-10-17 Bin Cheng bin.ch...@arm.com * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type. Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. Patch b: 2013-10-17 Bin Cheng bin.ch...@arm.com * fold-const.c (fold_plusminus_mult_expr): Use int_cst_value instead of TREE_INT_CST_LOW. gcc/testsuite/ChangeLog 2013-10-17 Bin Cheng bin.ch...@arm.com * gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test. -Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Wednesday, October 02, 2013 4:32 PM To: Bin.Cheng Cc: Bin Cheng; GCC Patches Subject: Re: [PATCH]Fix computation of offset in ivopt On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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
RE: [PATCH]Fix computation of offset in ivopt
Hi, As noted in previous messages, GCC forces offset to unsigned in middle end. It also gets offset value and stores it in HOST_WIDE_INT then uses it in various computation. In this scenario, It should use int_cst_value to do additional sign extension against the type of tree node, otherwise we might lose sign information. Take function fold_plusminus_mult_expr as an example, the sign information of arg01/arg11 might be lost because it uses TREE_INT_CST_LOW directly. I think this is the offender of the problem in this thread. I think we should fix the offender, rather the hacking strip_offset as in the original patch, so I split original patch into two as attached, with one fixing the offset of COMPONENT_REF in strip_offset_1, the other fixing the mentioned sign extension problem. Bootstrap and test on x86/x86_64/arm. Is it OK? Thanks. bin Patch a: 2013-10-17 Bin Cheng bin.ch...@arm.com * tree-ssa-loop-ivopts.c (strip_offset_1): Change parameter type. Count DECL_FIELD_BIT_OFFSET when computing offset for COMPONENT_REF. Patch b: 2013-10-17 Bin Cheng bin.ch...@arm.com * fold-const.c (fold_plusminus_mult_expr): Use int_cst_value instead of TREE_INT_CST_LOW. gcc/testsuite/ChangeLog 2013-10-17 Bin Cheng bin.ch...@arm.com * gcc.dg/tree-ssa/ivopts-outside-loop-use-1.c: New test. -Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Wednesday, October 02, 2013 4:32 PM To: Bin.Cheng Cc: Bin Cheng; GCC Patches Subject: Re: [PATCH]Fix computation of offset in ivopt On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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); +x = abs_boffset / BITS_PER_UNIT; +if (boffset 0) + x = -x; +*offset = off0 + int_cst_value (tmp) + x; 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 Index: gcc/tree-ssa-loop-ivopts.c === --- gcc/tree-ssa-loop
Re: [PATCH]Fix computation of offset in ivopt
On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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. -- Best Regards.
Re: [PATCH]Fix computation of offset in ivopt
On Tue, Oct 1, 2013 at 6:13 PM, Bin.Cheng amker.ch...@gmail.com wrote: On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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); +x = abs_boffset / BITS_PER_UNIT; +if (boffset 0) + x = -x; +*offset = off0 + int_cst_value (tmp) + x; 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
Re: [PATCH]Fix computation of offset in ivopt
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.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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 -- Best Regards.
Re: [PATCH]Fix computation of offset in ivopt
On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@arm.com wrote: -Original Message- From: Richard Biener [mailto:richard.guent...@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.ch...@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.ch...@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.
Re: [PATCH]Fix computation of offset in ivopt
On Tue, Oct 1, 2013 at 6:50 PM, Richard Biener richard.guent...@gmail.com wrote: On Mon, Sep 30, 2013 at 7:39 AM, bin.cheng bin.ch...@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/0xFFFC) 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); +x = abs_boffset / BITS_PER_UNIT; +if (boffset 0) + x = -x; +*offset = off0 + int_cst_value (tmp) + x; 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
RE: [PATCH]Fix computation of offset in ivopt
-Original Message- From: gcc-patches-ow...@gcc.gnu.org [mailto:gcc-patches- ow...@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
RE: [PATCH]Fix computation of offset in ivopt
-Original Message- From: Richard Biener [mailto:richard.guent...@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.ch...@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.ch...@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.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.
RE: [PATCH]Fix computation of offset in ivopt
-Original Message- From: gcc-patches-ow...@gcc.gnu.org [mailto:gcc-patches- ow...@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.guent...@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.ch...@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
Re: [PATCH]Fix computation of offset in ivopt
On Fri, Sep 27, 2013 at 7:07 AM, bin.cheng bin.ch...@arm.com wrote: -Original Message- From: Richard Biener [mailto:richard.guent...@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.ch...@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
RE: [PATCH]Fix computation of offset in ivopt
-Original Message- From: Richard Biener [mailto:richard.guent...@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.ch...@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
Re: [PATCH]Fix computation of offset in ivopt
On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng bin.ch...@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 : 0xfffc, while offset computed in TYPE(utype) is : 0xfffc. Though they both stand for value -4 in different precision, statement offset -= ratio * cstepi returns 0x1, 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.ch...@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.
Re: [PATCH]Fix computation of offset in ivopt
On Tue, 2013-09-24 at 12:31 +0200, Richard Biener wrote: On Tue, Sep 24, 2013 at 11:13 AM, bin.cheng bin.ch...@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 : 0xfffc, while offset computed in TYPE(utype) is : 0xfffc. Though they both stand for value -4 in different precision, statement offset -= ratio * cstepi returns 0x1, 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