* [PATCH PR80153]Always generate folded type conversion in tree-affine @ 2017-03-28 12:17 Bin Cheng 2017-03-28 12:39 ` Richard Biener 0 siblings, 1 reply; 11+ messages in thread From: Bin Cheng @ 2017-03-28 12:17 UTC (permalink / raw) To: gcc-patches; +Cc: nd [-- Attachment #1: Type: text/plain, Size: 1395 bytes --] Hi, This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, even worse, it always returns the former expression in aff_combination_tree, which is wrong if the original expression has the latter form. The patch resolves the issue by always returning the latter form expression, i.e, always trying to generate folded expression. Also as analyzed in comment, I think this change won't result in substantial code gen difference. I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. Well, I think the changed behavior is correct, but for case the original pointer candidate is chosen, it should be unnecessary to compute in uutype. Also this adjustment only generates (unsigned)(pointer + offset) which is generated by tree-affine.c. Bootstrap and test on x86_64 and AArch64. Is it OK? 2017-03-27 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/80153 * tree-affine.c (add_elt_to_tree): Convert to type as required by function's parameter. * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. (get_computation_aff): Use utype directly for original candidate. gcc/testsuite/ChangeLog 2017-03-27 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/80153 * gcc.c-torture/execute/pr80153.c: New. [-- Attachment #2: pr80153-20170327.txt --] [-- Type: text/plain, Size: 2585 bytes --] diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c new file mode 100644 index 0000000..3eed578 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c @@ -0,0 +1,48 @@ +/* PR tree-optimization/80153 */ + +void check (int, int, int) __attribute__((noinline)); +void check (int c, int c2, int val) +{ + if (!val) { + __builtin_abort(); + } +} + +static const char *buf; +static int l, i; + +void _fputs(const char *str) __attribute__((noinline)); +void _fputs(const char *str) +{ + buf = str; + i = 0; + l = __builtin_strlen(buf); +} + +char _fgetc() __attribute__((noinline)); +char _fgetc() +{ + char val = buf[i]; + i++; + if (i > l) + return -1; + else + return val; +} + +static const char *string = "oops!\n"; + +int main(void) +{ + int i; + int c; + + _fputs(string); + + for (i = 0; i < __builtin_strlen(string); i++) { + c = _fgetc(); + check(c, string[i], c == string[i]); + } + + return 0; +} diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index e620eea..b10b1aa 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -391,6 +391,8 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt); scale = 1; } + else + elt = fold_convert (type, elt); if (scale == 1) { diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 8dc65881..fa993ab 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step, || contain_complex_addr_expr (expr)) { aff_tree comb; - tree_to_aff_combination (expr, TREE_TYPE (base), &comb); + tree_to_aff_combination (expr, TREE_TYPE (expr), &comb); base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb)); } @@ -3787,6 +3787,12 @@ get_computation_aff (struct loop *loop, overflows, as all the arithmetics will in the end be performed in UUTYPE anyway. */ common_type = determine_common_wider_type (&ubase, &cbase); + /* We don't need to compute in UUTYPE if this is the original candidate, + and candidate/use have the same (pointer) type. */ + if (ctype == utype && common_type == utype + && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype) + && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) + uutype = utype; /* use = ubase - ratio * cbase + ratio * var. */ tree_to_aff_combination (ubase, common_type, aff); ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-28 12:17 [PATCH PR80153]Always generate folded type conversion in tree-affine Bin Cheng @ 2017-03-28 12:39 ` Richard Biener 2017-03-29 15:32 ` Bin.Cheng 0 siblings, 1 reply; 11+ messages in thread From: Richard Biener @ 2017-03-28 12:39 UTC (permalink / raw) To: Bin Cheng; +Cc: gcc-patches, nd On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks > ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, > even worse, it always returns the former expression in aff_combination_tree, which > is wrong if the original expression has the latter form. The patch resolves the issue > by always returning the latter form expression, i.e, always trying to generate folded > expression. Also as analyzed in comment, I think this change won't result in substantial > code gen difference. > I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. > Well, I think the changed behavior is correct, but for case the original pointer candidate > is chosen, it should be unnecessary to compute in uutype. Also this adjustment only > generates (unsigned)(pointer + offset) which is generated by tree-affine.c. > Bootstrap and test on x86_64 and AArch64. Is it OK? Hmm. What is the desired goal? To have all elts added have comb->type as type? Then the type passed to add_elt_to_tree is redundant with comb->type. It looks like it is always passed comb->type now. ISTR from past work in this area that it was important for pointer combinations to allow both pointer and sizetype elts at least. Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case elt is sizetype now, not of pointer type. As said above, we are trying to maintain both pointer and sizetype elts with like: if (scale == 1) { if (!expr) { if (POINTER_TYPE_P (TREE_TYPE (elt))) return elt; else return fold_convert (type1, elt); } where your earilier fold to type would result in not all cases handled the same (depending whether scale was -1 for example). Thus - shouldn't we simply drop the type argument (or rather the comb one? that wide_int_ext_for_comb looks weird given we get a widest_int as input and all the other wide_int_ext_for_comb calls around). And unconditionally convert to type, simplifying the rest of the code? Richard. > 2017-03-27 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/80153 > * tree-affine.c (add_elt_to_tree): Convert to type as required > by function's parameter. > * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. > (get_computation_aff): Use utype directly for original candidate. > > gcc/testsuite/ChangeLog > 2017-03-27 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/80153 > * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-28 12:39 ` Richard Biener @ 2017-03-29 15:32 ` Bin.Cheng 2017-03-30 10:46 ` Richard Biener 0 siblings, 1 reply; 11+ messages in thread From: Bin.Cheng @ 2017-03-29 15:32 UTC (permalink / raw) To: Richard Biener; +Cc: Bin Cheng, gcc-patches, nd [-- Attachment #1: Type: text/plain, Size: 3979 bytes --] On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >> Hi, >> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >> even worse, it always returns the former expression in aff_combination_tree, which >> is wrong if the original expression has the latter form. The patch resolves the issue >> by always returning the latter form expression, i.e, always trying to generate folded >> expression. Also as analyzed in comment, I think this change won't result in substantial >> code gen difference. >> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >> Well, I think the changed behavior is correct, but for case the original pointer candidate >> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >> Bootstrap and test on x86_64 and AArch64. Is it OK? > Thanks for reviewing. > Hmm. What is the desired goal? To have all elts added have > comb->type as type? Then > the type passed to add_elt_to_tree is redundant with comb->type. It > looks like it > is always passed comb->type now. Yes, except pointer type comb->type, elts are converted to comb->type with this patch. The redundant type is removed in updated patch. > > ISTR from past work in this area that it was important for pointer > combinations to allow > both pointer and sizetype elts at least. Yes, It's still important to allow different types for pointer and offset in pointer type comb. I missed a pointer type check condition in the patch, fixed in updated patch. > > Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case > elt is sizetype now, not of pointer type. As said above, we are > trying to maintain > both pointer and sizetype elts with like: > > if (scale == 1) > { > if (!expr) > { > if (POINTER_TYPE_P (TREE_TYPE (elt))) > return elt; > else > return fold_convert (type1, elt); > } > > where your earilier fold to type would result in not all cases handled the same > (depending whether scale was -1 for example). IIUC, it doesn't matter. For comb->type being pointer type, the behavior remains the same. For comb->type being unsigned T, this elt is converted to ptr_offtype, rather than unsigned T, this doesn't matter because ptr_offtype and unsigned T are equal to each other, otherwise tree_to_aff_combination shouldn't distribute it as a single elt. Anyway, this is addressed in updated patch by checking pointer comb->type additionally. BTW, I think "scale==-1" case is a simple heuristic differentiating pointer_base and offset. > > Thus - shouldn't we simply drop the type argument (or rather the comb one? > that wide_int_ext_for_comb looks weird given we get a widest_int as input > and all the other wide_int_ext_for_comb calls around). > > And unconditionally convert to type, simplifying the rest of the code? As said, for pointer type comb, we need to keep current behavior; for other cases, unconditionally convert to comb->type is the goal. Bootstrap and test on x86_64 and AArch64. Is this version OK? Thanks, bin 2017-03-28 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/80153 * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type of parameter COMB. Convert elt to type of COMB it COMB is not of pointer type. (aff_combination_to_tree): Update calls to add_elt_to_tree. * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. (get_computation_aff): Use utype directly for original candidate. gcc/testsuite/ChangeLog 2017-03-28 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/80153 * gcc.c-torture/execute/pr80153.c: New. [-- Attachment #2: pr80153-20170328.txt --] [-- Type: text/plain, Size: 6897 bytes --] diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c new file mode 100644 index 0000000..3eed578 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c @@ -0,0 +1,48 @@ +/* PR tree-optimization/80153 */ + +void check (int, int, int) __attribute__((noinline)); +void check (int c, int c2, int val) +{ + if (!val) { + __builtin_abort(); + } +} + +static const char *buf; +static int l, i; + +void _fputs(const char *str) __attribute__((noinline)); +void _fputs(const char *str) +{ + buf = str; + i = 0; + l = __builtin_strlen(buf); +} + +char _fgetc() __attribute__((noinline)); +char _fgetc() +{ + char val = buf[i]; + i++; + if (i > l) + return -1; + else + return val; +} + +static const char *string = "oops!\n"; + +int main(void) +{ + int i; + int c; + + _fputs(string); + + for (i = 0; i < __builtin_strlen(string); i++) { + c = _fgetc(); + check(c, string[i], c == string[i]); + } + + return 0; +} diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index e620eea..a7f0b6a 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -370,27 +370,28 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb) aff_combination_elt (comb, type, expr); } -/* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine +/* Creates EXPR + ELT * SCALE in COMB's type. EXPR is taken from affine combination COMB. */ static tree -add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, - aff_tree *comb ATTRIBUTE_UNUSED) +add_elt_to_tree (tree expr, tree elt, const widest_int &scale_in, + aff_tree *comb) { enum tree_code code; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; + tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type; widest_int scale = wide_int_ext_for_comb (scale_in, comb); if (scale == -1 + && POINTER_TYPE_P (comb->type) && POINTER_TYPE_P (TREE_TYPE (elt))) { elt = convert_to_ptrofftype (elt); elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt); scale = 1; } + else if (!POINTER_TYPE_P (comb->type)) + elt = fold_convert (comb->type, elt); if (scale == 1) { @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, if (POINTER_TYPE_P (TREE_TYPE (elt))) return elt; else - return fold_convert (type1, elt); + return fold_convert (type, elt); } if (POINTER_TYPE_P (TREE_TYPE (expr))) return fold_build_pointer_plus (expr, elt); if (POINTER_TYPE_P (TREE_TYPE (elt))) return fold_build_pointer_plus (elt, expr); - return fold_build2 (PLUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); } if (scale == -1) { if (!expr) - return fold_build1 (NEGATE_EXPR, type1, - fold_convert (type1, elt)); + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); if (POINTER_TYPE_P (TREE_TYPE (expr))) { @@ -422,14 +421,12 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt); return fold_build_pointer_plus (expr, elt); } - return fold_build2 (MINUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); } - elt = fold_convert (type1, elt); + elt = fold_convert (type, elt); if (!expr) - return fold_build2 (MULT_EXPR, type1, elt, - wide_int_to_tree (type1, scale)); + return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); if (wi::neg_p (scale)) { @@ -439,15 +436,14 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, else code = PLUS_EXPR; - elt = fold_build2 (MULT_EXPR, type1, elt, - wide_int_to_tree (type1, scale)); + elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); if (POINTER_TYPE_P (TREE_TYPE (expr))) { if (code == MINUS_EXPR) - elt = fold_build1 (NEGATE_EXPR, type1, elt); + elt = fold_build1 (NEGATE_EXPR, type, elt); return fold_build_pointer_plus (expr, elt); } - return fold_build2 (code, type1, expr, elt); + return fold_build2 (code, type, expr, elt); } /* Makes tree from the affine combination COMB. */ @@ -455,22 +451,18 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, tree aff_combination_to_tree (aff_tree *comb) { - tree type = comb->type; tree expr = NULL_TREE; unsigned i; widest_int off, sgn; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; + tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type; gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); for (i = 0; i < comb->n; i++) - expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef, - comb); + expr = add_elt_to_tree (expr, comb->elts[i].val, comb->elts[i].coef, comb); if (comb->rest) - expr = add_elt_to_tree (expr, type, comb->rest, 1, comb); + expr = add_elt_to_tree (expr, comb->rest, 1, comb); /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is unsigned. */ @@ -484,8 +476,7 @@ aff_combination_to_tree (aff_tree *comb) off = comb->offset; sgn = 1; } - return add_elt_to_tree (expr, type, wide_int_to_tree (type1, off), sgn, - comb); + return add_elt_to_tree (expr, wide_int_to_tree (type, off), sgn, comb); } /* Copies the tree elements of COMB to ensure that they are not shared. */ diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 8dc65881..fa993ab 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step, || contain_complex_addr_expr (expr)) { aff_tree comb; - tree_to_aff_combination (expr, TREE_TYPE (base), &comb); + tree_to_aff_combination (expr, TREE_TYPE (expr), &comb); base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb)); } @@ -3787,6 +3787,12 @@ get_computation_aff (struct loop *loop, overflows, as all the arithmetics will in the end be performed in UUTYPE anyway. */ common_type = determine_common_wider_type (&ubase, &cbase); + /* We don't need to compute in UUTYPE if this is the original candidate, + and candidate/use have the same (pointer) type. */ + if (ctype == utype && common_type == utype + && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype) + && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) + uutype = utype; /* use = ubase - ratio * cbase + ratio * var. */ tree_to_aff_combination (ubase, common_type, aff); ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-29 15:32 ` Bin.Cheng @ 2017-03-30 10:46 ` Richard Biener 2017-03-30 12:44 ` Bin.Cheng 0 siblings, 1 reply; 11+ messages in thread From: Richard Biener @ 2017-03-30 10:46 UTC (permalink / raw) To: Bin.Cheng; +Cc: Bin Cheng, gcc-patches, nd On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>> Hi, >>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>> even worse, it always returns the former expression in aff_combination_tree, which >>> is wrong if the original expression has the latter form. The patch resolves the issue >>> by always returning the latter form expression, i.e, always trying to generate folded >>> expression. Also as analyzed in comment, I think this change won't result in substantial >>> code gen difference. >>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>> Bootstrap and test on x86_64 and AArch64. Is it OK? >> > Thanks for reviewing. >> Hmm. What is the desired goal? To have all elts added have >> comb->type as type? Then >> the type passed to add_elt_to_tree is redundant with comb->type. It >> looks like it >> is always passed comb->type now. > Yes, except pointer type comb->type, elts are converted to comb->type > with this patch. > The redundant type is removed in updated patch. > >> >> ISTR from past work in this area that it was important for pointer >> combinations to allow >> both pointer and sizetype elts at least. > Yes, It's still important to allow different types for pointer and > offset in pointer type comb. > I missed a pointer type check condition in the patch, fixed in updated patch. >> >> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >> elt is sizetype now, not of pointer type. As said above, we are >> trying to maintain >> both pointer and sizetype elts with like: >> >> if (scale == 1) >> { >> if (!expr) >> { >> if (POINTER_TYPE_P (TREE_TYPE (elt))) >> return elt; >> else >> return fold_convert (type1, elt); >> } >> >> where your earilier fold to type would result in not all cases handled the same >> (depending whether scale was -1 for example). > IIUC, it doesn't matter. For comb->type being pointer type, the > behavior remains the same. > For comb->type being unsigned T, this elt is converted to ptr_offtype, > rather than unsigned T, > this doesn't matter because ptr_offtype and unsigned T are equal to > each other, otherwise > tree_to_aff_combination shouldn't distribute it as a single elt. > Anyway, this is addressed in updated patch by checking pointer > comb->type additionally. > BTW, I think "scale==-1" case is a simple heuristic differentiating > pointer_base and offset. > >> >> Thus - shouldn't we simply drop the type argument (or rather the comb one? >> that wide_int_ext_for_comb looks weird given we get a widest_int as input >> and all the other wide_int_ext_for_comb calls around). >> >> And unconditionally convert to type, simplifying the rest of the code? > As said, for pointer type comb, we need to keep current behavior; for > other cases, > unconditionally convert to comb->type is the goal. > > Bootstrap and test on x86_64 and AArch64. Is this version OK? @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, if (POINTER_TYPE_P (TREE_TYPE (elt))) return elt; else - return fold_convert (type1, elt); + return fold_convert (type, elt); } the conversion should already have been done. For non-pointer comb->type it has been converted to type by your patch. For pointer-type comb->type it should be either pointer type or ptrofftype ('type') already as well. That said, can we do sth like @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t widest_int scale = wide_int_ext_for_comb (scale_in, comb); + if (! POINTER_TYPE_P (comb->type)) + elt = fold_convert (comb->type, elt); + else + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) + || types_compatible_p (TREE_TYPE (elt), type1)); + if (scale == -1 && POINTER_TYPE_P (TREE_TYPE (elt))) { that is clearly do the conversion at the start in a way the state of elt is more clear? Richard. > Thanks, > bin > > 2017-03-28 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/80153 > * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type > of parameter COMB. Convert elt to type of COMB it COMB is not of > pointer type. > (aff_combination_to_tree): Update calls to add_elt_to_tree. > * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. > (get_computation_aff): Use utype directly for original candidate. > > gcc/testsuite/ChangeLog > 2017-03-28 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/80153 > * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-30 10:46 ` Richard Biener @ 2017-03-30 12:44 ` Bin.Cheng 2017-03-30 13:00 ` Richard Biener 0 siblings, 1 reply; 11+ messages in thread From: Bin.Cheng @ 2017-03-30 12:44 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 5824 bytes --] On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener <richard.guenther@gmail.com> wrote: > On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>> Hi, >>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>> even worse, it always returns the former expression in aff_combination_tree, which >>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>> by always returning the latter form expression, i.e, always trying to generate folded >>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>> code gen difference. >>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>> >> Thanks for reviewing. >>> Hmm. What is the desired goal? To have all elts added have >>> comb->type as type? Then >>> the type passed to add_elt_to_tree is redundant with comb->type. It >>> looks like it >>> is always passed comb->type now. >> Yes, except pointer type comb->type, elts are converted to comb->type >> with this patch. >> The redundant type is removed in updated patch. >> >>> >>> ISTR from past work in this area that it was important for pointer >>> combinations to allow >>> both pointer and sizetype elts at least. >> Yes, It's still important to allow different types for pointer and >> offset in pointer type comb. >> I missed a pointer type check condition in the patch, fixed in updated patch. >>> >>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>> elt is sizetype now, not of pointer type. As said above, we are >>> trying to maintain >>> both pointer and sizetype elts with like: >>> >>> if (scale == 1) >>> { >>> if (!expr) >>> { >>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>> return elt; >>> else >>> return fold_convert (type1, elt); >>> } >>> >>> where your earilier fold to type would result in not all cases handled the same >>> (depending whether scale was -1 for example). >> IIUC, it doesn't matter. For comb->type being pointer type, the >> behavior remains the same. >> For comb->type being unsigned T, this elt is converted to ptr_offtype, >> rather than unsigned T, >> this doesn't matter because ptr_offtype and unsigned T are equal to >> each other, otherwise >> tree_to_aff_combination shouldn't distribute it as a single elt. >> Anyway, this is addressed in updated patch by checking pointer >> comb->type additionally. >> BTW, I think "scale==-1" case is a simple heuristic differentiating >> pointer_base and offset. >> >>> >>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>> and all the other wide_int_ext_for_comb calls around). >>> >>> And unconditionally convert to type, simplifying the rest of the code? >> As said, for pointer type comb, we need to keep current behavior; for >> other cases, >> unconditionally convert to comb->type is the goal. >> >> Bootstrap and test on x86_64 and AArch64. Is this version OK? > > @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, > const widest_int &scale_in, > if (POINTER_TYPE_P (TREE_TYPE (elt))) > return elt; > else > - return fold_convert (type1, elt); > + return fold_convert (type, elt); > } > > the conversion should already have been done. For non-pointer comb->type > it has been converted to type by your patch. For pointer-type comb->type > it should be either pointer type or ptrofftype ('type') already as well. > > That said, can we do sth like > > @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t > > widest_int scale = wide_int_ext_for_comb (scale_in, comb); > > + if (! POINTER_TYPE_P (comb->type)) > + elt = fold_convert (comb->type, elt); > + else > + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) > + || types_compatible_p (TREE_TYPE (elt), type1)); Hmm, this assert can be broken since we do STRIP_NOPS converting to aff_tree. It's not compatible for signed and unsigned integer types. Also, with this patch, we can even support elt of short type in a unsigned long comb, though this is useless. > + > if (scale == -1 > && POINTER_TYPE_P (TREE_TYPE (elt))) > { > > that is clearly do the conversion at the start in a way the state > of elt is more clear? Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok after bootstrap/test? Thanks, bin > > Richard. > > > >> Thanks, >> bin >> >> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >> >> PR tree-optimization/80153 >> * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type >> of parameter COMB. Convert elt to type of COMB it COMB is not of >> pointer type. >> (aff_combination_to_tree): Update calls to add_elt_to_tree. >> * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. >> (get_computation_aff): Use utype directly for original candidate. >> >> gcc/testsuite/ChangeLog >> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >> >> PR tree-optimization/80153 >> * gcc.c-torture/execute/pr80153.c: New. [-- Attachment #2: pr80153-20170330.txt --] [-- Type: text/plain, Size: 6837 bytes --] diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c new file mode 100644 index 0000000..3eed578 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c @@ -0,0 +1,48 @@ +/* PR tree-optimization/80153 */ + +void check (int, int, int) __attribute__((noinline)); +void check (int c, int c2, int val) +{ + if (!val) { + __builtin_abort(); + } +} + +static const char *buf; +static int l, i; + +void _fputs(const char *str) __attribute__((noinline)); +void _fputs(const char *str) +{ + buf = str; + i = 0; + l = __builtin_strlen(buf); +} + +char _fgetc() __attribute__((noinline)); +char _fgetc() +{ + char val = buf[i]; + i++; + if (i > l) + return -1; + else + return val; +} + +static const char *string = "oops!\n"; + +int main(void) +{ + int i; + int c; + + _fputs(string); + + for (i = 0; i < __builtin_strlen(string); i++) { + c = _fgetc(); + check(c, string[i], c == string[i]); + } + + return 0; +} diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index e620eea..3ec9263 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -370,20 +370,22 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb) aff_combination_elt (comb, type, expr); } -/* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine +/* Creates EXPR + ELT * SCALE in COMB's type. EXPR is taken from affine combination COMB. */ static tree -add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, - aff_tree *comb ATTRIBUTE_UNUSED) +add_elt_to_tree (tree expr, tree elt, const widest_int &scale_in, + aff_tree *comb) { enum tree_code code; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; + tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type; widest_int scale = wide_int_ext_for_comb (scale_in, comb); + /* Convert elt unconditionally if comb is not pointer type. */ + if (!POINTER_TYPE_P (comb->type)) + elt = fold_convert (comb->type, elt); + if (scale == -1 && POINTER_TYPE_P (TREE_TYPE (elt))) { @@ -394,27 +396,21 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, if (scale == 1) { + /* Elt is of correct type already. */ if (!expr) - { - if (POINTER_TYPE_P (TREE_TYPE (elt))) - return elt; - else - return fold_convert (type1, elt); - } + return elt; if (POINTER_TYPE_P (TREE_TYPE (expr))) return fold_build_pointer_plus (expr, elt); if (POINTER_TYPE_P (TREE_TYPE (elt))) return fold_build_pointer_plus (elt, expr); - return fold_build2 (PLUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); } if (scale == -1) { if (!expr) - return fold_build1 (NEGATE_EXPR, type1, - fold_convert (type1, elt)); + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); if (POINTER_TYPE_P (TREE_TYPE (expr))) { @@ -422,14 +418,12 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt); return fold_build_pointer_plus (expr, elt); } - return fold_build2 (MINUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); } - elt = fold_convert (type1, elt); + elt = fold_convert (type, elt); if (!expr) - return fold_build2 (MULT_EXPR, type1, elt, - wide_int_to_tree (type1, scale)); + return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); if (wi::neg_p (scale)) { @@ -439,15 +433,14 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, else code = PLUS_EXPR; - elt = fold_build2 (MULT_EXPR, type1, elt, - wide_int_to_tree (type1, scale)); + elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); if (POINTER_TYPE_P (TREE_TYPE (expr))) { if (code == MINUS_EXPR) - elt = fold_build1 (NEGATE_EXPR, type1, elt); + elt = fold_build1 (NEGATE_EXPR, type, elt); return fold_build_pointer_plus (expr, elt); } - return fold_build2 (code, type1, expr, elt); + return fold_build2 (code, type, expr, elt); } /* Makes tree from the affine combination COMB. */ @@ -455,22 +448,18 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, tree aff_combination_to_tree (aff_tree *comb) { - tree type = comb->type; tree expr = NULL_TREE; unsigned i; widest_int off, sgn; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; + tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type; gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); for (i = 0; i < comb->n; i++) - expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef, - comb); + expr = add_elt_to_tree (expr, comb->elts[i].val, comb->elts[i].coef, comb); if (comb->rest) - expr = add_elt_to_tree (expr, type, comb->rest, 1, comb); + expr = add_elt_to_tree (expr, comb->rest, 1, comb); /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is unsigned. */ @@ -484,8 +473,7 @@ aff_combination_to_tree (aff_tree *comb) off = comb->offset; sgn = 1; } - return add_elt_to_tree (expr, type, wide_int_to_tree (type1, off), sgn, - comb); + return add_elt_to_tree (expr, wide_int_to_tree (type, off), sgn, comb); } /* Copies the tree elements of COMB to ensure that they are not shared. */ diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 8dc65881..fa993ab 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step, || contain_complex_addr_expr (expr)) { aff_tree comb; - tree_to_aff_combination (expr, TREE_TYPE (base), &comb); + tree_to_aff_combination (expr, TREE_TYPE (expr), &comb); base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb)); } @@ -3787,6 +3787,12 @@ get_computation_aff (struct loop *loop, overflows, as all the arithmetics will in the end be performed in UUTYPE anyway. */ common_type = determine_common_wider_type (&ubase, &cbase); + /* We don't need to compute in UUTYPE if this is the original candidate, + and candidate/use have the same (pointer) type. */ + if (ctype == utype && common_type == utype + && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype) + && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) + uutype = utype; /* use = ubase - ratio * cbase + ratio * var. */ tree_to_aff_combination (ubase, common_type, aff); ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-30 12:44 ` Bin.Cheng @ 2017-03-30 13:00 ` Richard Biener 2017-03-30 13:20 ` Bin.Cheng 0 siblings, 1 reply; 11+ messages in thread From: Richard Biener @ 2017-03-30 13:00 UTC (permalink / raw) To: Bin.Cheng; +Cc: gcc-patches On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>> Hi, >>>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>>> even worse, it always returns the former expression in aff_combination_tree, which >>>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>>> by always returning the latter form expression, i.e, always trying to generate folded >>>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>>> code gen difference. >>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>> >>> Thanks for reviewing. >>>> Hmm. What is the desired goal? To have all elts added have >>>> comb->type as type? Then >>>> the type passed to add_elt_to_tree is redundant with comb->type. It >>>> looks like it >>>> is always passed comb->type now. >>> Yes, except pointer type comb->type, elts are converted to comb->type >>> with this patch. >>> The redundant type is removed in updated patch. >>> >>>> >>>> ISTR from past work in this area that it was important for pointer >>>> combinations to allow >>>> both pointer and sizetype elts at least. >>> Yes, It's still important to allow different types for pointer and >>> offset in pointer type comb. >>> I missed a pointer type check condition in the patch, fixed in updated patch. >>>> >>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>>> elt is sizetype now, not of pointer type. As said above, we are >>>> trying to maintain >>>> both pointer and sizetype elts with like: >>>> >>>> if (scale == 1) >>>> { >>>> if (!expr) >>>> { >>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>> return elt; >>>> else >>>> return fold_convert (type1, elt); >>>> } >>>> >>>> where your earilier fold to type would result in not all cases handled the same >>>> (depending whether scale was -1 for example). >>> IIUC, it doesn't matter. For comb->type being pointer type, the >>> behavior remains the same. >>> For comb->type being unsigned T, this elt is converted to ptr_offtype, >>> rather than unsigned T, >>> this doesn't matter because ptr_offtype and unsigned T are equal to >>> each other, otherwise >>> tree_to_aff_combination shouldn't distribute it as a single elt. >>> Anyway, this is addressed in updated patch by checking pointer >>> comb->type additionally. >>> BTW, I think "scale==-1" case is a simple heuristic differentiating >>> pointer_base and offset. >>> >>>> >>>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>>> and all the other wide_int_ext_for_comb calls around). >>>> >>>> And unconditionally convert to type, simplifying the rest of the code? >>> As said, for pointer type comb, we need to keep current behavior; for >>> other cases, >>> unconditionally convert to comb->type is the goal. >>> >>> Bootstrap and test on x86_64 and AArch64. Is this version OK? >> >> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, >> const widest_int &scale_in, >> if (POINTER_TYPE_P (TREE_TYPE (elt))) >> return elt; >> else >> - return fold_convert (type1, elt); >> + return fold_convert (type, elt); >> } >> >> the conversion should already have been done. For non-pointer comb->type >> it has been converted to type by your patch. For pointer-type comb->type >> it should be either pointer type or ptrofftype ('type') already as well. >> >> That said, can we do sth like >> >> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t >> >> widest_int scale = wide_int_ext_for_comb (scale_in, comb); >> >> + if (! POINTER_TYPE_P (comb->type)) >> + elt = fold_convert (comb->type, elt); >> + else >> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >> + || types_compatible_p (TREE_TYPE (elt), type1)); > Hmm, this assert can be broken since we do STRIP_NOPS converting to > aff_tree. It's not compatible for signed and unsigned integer types. > Also, with this patch, we can even support elt of short type in a > unsigned long comb, though this is useless. > >> + >> if (scale == -1 >> && POINTER_TYPE_P (TREE_TYPE (elt))) >> { >> >> that is clearly do the conversion at the start in a way the state >> of elt is more clear? > Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok > after bootstrap/test? - return fold_build2 (PLUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); folding not needed(?) - return fold_build1 (NEGATE_EXPR, type1, - fold_convert (type1, elt)); + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); likewise. - return fold_build2 (MINUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); likewise. Ok with removing those and re-testing. Thanks, Richard. > Thanks, > bin >> >> Richard. >> >> >> >>> Thanks, >>> bin >>> >>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>> >>> PR tree-optimization/80153 >>> * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type >>> of parameter COMB. Convert elt to type of COMB it COMB is not of >>> pointer type. >>> (aff_combination_to_tree): Update calls to add_elt_to_tree. >>> * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. >>> (get_computation_aff): Use utype directly for original candidate. >>> >>> gcc/testsuite/ChangeLog >>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>> >>> PR tree-optimization/80153 >>> * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-30 13:00 ` Richard Biener @ 2017-03-30 13:20 ` Bin.Cheng 2017-03-30 13:34 ` Bin.Cheng 0 siblings, 1 reply; 11+ messages in thread From: Bin.Cheng @ 2017-03-30 13:20 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >>>> <richard.guenther@gmail.com> wrote: >>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>> Hi, >>>>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>>>> even worse, it always returns the former expression in aff_combination_tree, which >>>>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>>>> by always returning the latter form expression, i.e, always trying to generate folded >>>>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>>>> code gen difference. >>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>>> >>>> Thanks for reviewing. >>>>> Hmm. What is the desired goal? To have all elts added have >>>>> comb->type as type? Then >>>>> the type passed to add_elt_to_tree is redundant with comb->type. It >>>>> looks like it >>>>> is always passed comb->type now. >>>> Yes, except pointer type comb->type, elts are converted to comb->type >>>> with this patch. >>>> The redundant type is removed in updated patch. >>>> >>>>> >>>>> ISTR from past work in this area that it was important for pointer >>>>> combinations to allow >>>>> both pointer and sizetype elts at least. >>>> Yes, It's still important to allow different types for pointer and >>>> offset in pointer type comb. >>>> I missed a pointer type check condition in the patch, fixed in updated patch. >>>>> >>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>>>> elt is sizetype now, not of pointer type. As said above, we are >>>>> trying to maintain >>>>> both pointer and sizetype elts with like: >>>>> >>>>> if (scale == 1) >>>>> { >>>>> if (!expr) >>>>> { >>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>> return elt; >>>>> else >>>>> return fold_convert (type1, elt); >>>>> } >>>>> >>>>> where your earilier fold to type would result in not all cases handled the same >>>>> (depending whether scale was -1 for example). >>>> IIUC, it doesn't matter. For comb->type being pointer type, the >>>> behavior remains the same. >>>> For comb->type being unsigned T, this elt is converted to ptr_offtype, >>>> rather than unsigned T, >>>> this doesn't matter because ptr_offtype and unsigned T are equal to >>>> each other, otherwise >>>> tree_to_aff_combination shouldn't distribute it as a single elt. >>>> Anyway, this is addressed in updated patch by checking pointer >>>> comb->type additionally. >>>> BTW, I think "scale==-1" case is a simple heuristic differentiating >>>> pointer_base and offset. >>>> >>>>> >>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>>>> and all the other wide_int_ext_for_comb calls around). >>>>> >>>>> And unconditionally convert to type, simplifying the rest of the code? >>>> As said, for pointer type comb, we need to keep current behavior; for >>>> other cases, >>>> unconditionally convert to comb->type is the goal. >>>> >>>> Bootstrap and test on x86_64 and AArch64. Is this version OK? >>> >>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, >>> const widest_int &scale_in, >>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>> return elt; >>> else >>> - return fold_convert (type1, elt); >>> + return fold_convert (type, elt); >>> } >>> >>> the conversion should already have been done. For non-pointer comb->type >>> it has been converted to type by your patch. For pointer-type comb->type >>> it should be either pointer type or ptrofftype ('type') already as well. >>> >>> That said, can we do sth like >>> >>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t >>> >>> widest_int scale = wide_int_ext_for_comb (scale_in, comb); >>> >>> + if (! POINTER_TYPE_P (comb->type)) >>> + elt = fold_convert (comb->type, elt); >>> + else >>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>> + || types_compatible_p (TREE_TYPE (elt), type1)); >> Hmm, this assert can be broken since we do STRIP_NOPS converting to >> aff_tree. It's not compatible for signed and unsigned integer types. >> Also, with this patch, we can even support elt of short type in a >> unsigned long comb, though this is useless. >> >>> + >>> if (scale == -1 >>> && POINTER_TYPE_P (TREE_TYPE (elt))) >>> { >>> >>> that is clearly do the conversion at the start in a way the state >>> of elt is more clear? >> Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok >> after bootstrap/test? > > - return fold_build2 (PLUS_EXPR, type1, > - expr, fold_convert (type1, elt)); > + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); > > folding not needed(?) > > - return fold_build1 (NEGATE_EXPR, type1, > - fold_convert (type1, elt)); > + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); > > likewise. > > - return fold_build2 (MINUS_EXPR, type1, > - expr, fold_convert (type1, elt)); > + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); > > likewise. > > Ok with removing those and re-testing. Hmm, I thought twice about the simplification, there are cases not properly handled: >>> + if (! POINTER_TYPE_P (comb->type)) >>> + elt = fold_convert (comb->type, elt); >>> + else >>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>> + || types_compatible_p (TREE_TYPE (elt), type1)); This is not enough, for pointer type comb, if elt is the offset part, we could return signed integer type elt without folding. Though this shouldn't be an issue because it's always converted to ptr_offtype in building pointer_plus, it's better not to create such expressions in the first place. Check condition for unconditionally converting elt should be improved as: >>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>> + elt = fold_convert (comb->type, elt); With this change, folds can be removed as you suggested. I will test new patch for this. Thanks, bin > > Thanks, > Richard. > >> Thanks, >> bin >>> >>> Richard. >>> >>> >>> >>>> Thanks, >>>> bin >>>> >>>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>>> >>>> PR tree-optimization/80153 >>>> * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type >>>> of parameter COMB. Convert elt to type of COMB it COMB is not of >>>> pointer type. >>>> (aff_combination_to_tree): Update calls to add_elt_to_tree. >>>> * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. >>>> (get_computation_aff): Use utype directly for original candidate. >>>> >>>> gcc/testsuite/ChangeLog >>>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>>> >>>> PR tree-optimization/80153 >>>> * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-30 13:20 ` Bin.Cheng @ 2017-03-30 13:34 ` Bin.Cheng 2017-03-30 14:37 ` Richard Biener 0 siblings, 1 reply; 11+ messages in thread From: Bin.Cheng @ 2017-03-30 13:34 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >>>>> <richard.guenther@gmail.com> wrote: >>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>>> Hi, >>>>>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>>>>> even worse, it always returns the former expression in aff_combination_tree, which >>>>>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>>>>> by always returning the latter form expression, i.e, always trying to generate folded >>>>>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>>>>> code gen difference. >>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>>>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>>>> >>>>> Thanks for reviewing. >>>>>> Hmm. What is the desired goal? To have all elts added have >>>>>> comb->type as type? Then >>>>>> the type passed to add_elt_to_tree is redundant with comb->type. It >>>>>> looks like it >>>>>> is always passed comb->type now. >>>>> Yes, except pointer type comb->type, elts are converted to comb->type >>>>> with this patch. >>>>> The redundant type is removed in updated patch. >>>>> >>>>>> >>>>>> ISTR from past work in this area that it was important for pointer >>>>>> combinations to allow >>>>>> both pointer and sizetype elts at least. >>>>> Yes, It's still important to allow different types for pointer and >>>>> offset in pointer type comb. >>>>> I missed a pointer type check condition in the patch, fixed in updated patch. >>>>>> >>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>>>>> elt is sizetype now, not of pointer type. As said above, we are >>>>>> trying to maintain >>>>>> both pointer and sizetype elts with like: >>>>>> >>>>>> if (scale == 1) >>>>>> { >>>>>> if (!expr) >>>>>> { >>>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>> return elt; >>>>>> else >>>>>> return fold_convert (type1, elt); >>>>>> } >>>>>> >>>>>> where your earilier fold to type would result in not all cases handled the same >>>>>> (depending whether scale was -1 for example). >>>>> IIUC, it doesn't matter. For comb->type being pointer type, the >>>>> behavior remains the same. >>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype, >>>>> rather than unsigned T, >>>>> this doesn't matter because ptr_offtype and unsigned T are equal to >>>>> each other, otherwise >>>>> tree_to_aff_combination shouldn't distribute it as a single elt. >>>>> Anyway, this is addressed in updated patch by checking pointer >>>>> comb->type additionally. >>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating >>>>> pointer_base and offset. >>>>> >>>>>> >>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>>>>> and all the other wide_int_ext_for_comb calls around). >>>>>> >>>>>> And unconditionally convert to type, simplifying the rest of the code? >>>>> As said, for pointer type comb, we need to keep current behavior; for >>>>> other cases, >>>>> unconditionally convert to comb->type is the goal. >>>>> >>>>> Bootstrap and test on x86_64 and AArch64. Is this version OK? >>>> >>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, >>>> const widest_int &scale_in, >>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>> return elt; >>>> else >>>> - return fold_convert (type1, elt); >>>> + return fold_convert (type, elt); >>>> } >>>> >>>> the conversion should already have been done. For non-pointer comb->type >>>> it has been converted to type by your patch. For pointer-type comb->type >>>> it should be either pointer type or ptrofftype ('type') already as well. >>>> >>>> That said, can we do sth like >>>> >>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t >>>> >>>> widest_int scale = wide_int_ext_for_comb (scale_in, comb); >>>> >>>> + if (! POINTER_TYPE_P (comb->type)) >>>> + elt = fold_convert (comb->type, elt); >>>> + else >>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >>> Hmm, this assert can be broken since we do STRIP_NOPS converting to >>> aff_tree. It's not compatible for signed and unsigned integer types. >>> Also, with this patch, we can even support elt of short type in a >>> unsigned long comb, though this is useless. >>> >>>> + >>>> if (scale == -1 >>>> && POINTER_TYPE_P (TREE_TYPE (elt))) >>>> { >>>> >>>> that is clearly do the conversion at the start in a way the state >>>> of elt is more clear? >>> Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok >>> after bootstrap/test? >> >> - return fold_build2 (PLUS_EXPR, type1, >> - expr, fold_convert (type1, elt)); >> + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); >> >> folding not needed(?) >> >> - return fold_build1 (NEGATE_EXPR, type1, >> - fold_convert (type1, elt)); >> + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); >> >> likewise. >> >> - return fold_build2 (MINUS_EXPR, type1, >> - expr, fold_convert (type1, elt)); >> + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); >> >> likewise. >> >> Ok with removing those and re-testing. > Hmm, I thought twice about the simplification, there are cases not > properly handled: >>>> + if (! POINTER_TYPE_P (comb->type)) >>>> + elt = fold_convert (comb->type, elt); >>>> + else >>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>> + || types_compatible_p (TREE_TYPE (elt), type1)); > This is not enough, for pointer type comb, if elt is the offset part, > we could return signed integer type elt without folding. Though this > shouldn't be an issue because it's always converted to ptr_offtype in > building pointer_plus, it's better not to create such expressions in > the first place. Check condition for unconditionally converting elt > should be improved as: >>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>> + elt = fold_convert (comb->type, elt); Hmm, precisely as: >>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>> + elt = fold_convert (type, elt); > > With this change, folds can be removed as you suggested. I will test > new patch for this. > > Thanks, > bin >> >> Thanks, >> Richard. >> >>> Thanks, >>> bin >>>> >>>> Richard. >>>> >>>> >>>> >>>>> Thanks, >>>>> bin >>>>> >>>>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>>>> >>>>> PR tree-optimization/80153 >>>>> * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type >>>>> of parameter COMB. Convert elt to type of COMB it COMB is not of >>>>> pointer type. >>>>> (aff_combination_to_tree): Update calls to add_elt_to_tree. >>>>> * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. >>>>> (get_computation_aff): Use utype directly for original candidate. >>>>> >>>>> gcc/testsuite/ChangeLog >>>>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>>>> >>>>> PR tree-optimization/80153 >>>>> * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-30 13:34 ` Bin.Cheng @ 2017-03-30 14:37 ` Richard Biener 2017-04-05 7:25 ` Bin.Cheng 0 siblings, 1 reply; 11+ messages in thread From: Richard Biener @ 2017-03-30 14:37 UTC (permalink / raw) To: Bin.Cheng; +Cc: gcc-patches On Thu, Mar 30, 2017 at 3:20 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener >>>> <richard.guenther@gmail.com> wrote: >>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >>>>>> <richard.guenther@gmail.com> wrote: >>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>>>> Hi, >>>>>>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which >>>>>>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded >>>>>>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>>>>>> code gen difference. >>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>>>>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>>>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>>>>> >>>>>> Thanks for reviewing. >>>>>>> Hmm. What is the desired goal? To have all elts added have >>>>>>> comb->type as type? Then >>>>>>> the type passed to add_elt_to_tree is redundant with comb->type. It >>>>>>> looks like it >>>>>>> is always passed comb->type now. >>>>>> Yes, except pointer type comb->type, elts are converted to comb->type >>>>>> with this patch. >>>>>> The redundant type is removed in updated patch. >>>>>> >>>>>>> >>>>>>> ISTR from past work in this area that it was important for pointer >>>>>>> combinations to allow >>>>>>> both pointer and sizetype elts at least. >>>>>> Yes, It's still important to allow different types for pointer and >>>>>> offset in pointer type comb. >>>>>> I missed a pointer type check condition in the patch, fixed in updated patch. >>>>>>> >>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>>>>>> elt is sizetype now, not of pointer type. As said above, we are >>>>>>> trying to maintain >>>>>>> both pointer and sizetype elts with like: >>>>>>> >>>>>>> if (scale == 1) >>>>>>> { >>>>>>> if (!expr) >>>>>>> { >>>>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>> return elt; >>>>>>> else >>>>>>> return fold_convert (type1, elt); >>>>>>> } >>>>>>> >>>>>>> where your earilier fold to type would result in not all cases handled the same >>>>>>> (depending whether scale was -1 for example). >>>>>> IIUC, it doesn't matter. For comb->type being pointer type, the >>>>>> behavior remains the same. >>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype, >>>>>> rather than unsigned T, >>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to >>>>>> each other, otherwise >>>>>> tree_to_aff_combination shouldn't distribute it as a single elt. >>>>>> Anyway, this is addressed in updated patch by checking pointer >>>>>> comb->type additionally. >>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating >>>>>> pointer_base and offset. >>>>>> >>>>>>> >>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>>>>>> and all the other wide_int_ext_for_comb calls around). >>>>>>> >>>>>>> And unconditionally convert to type, simplifying the rest of the code? >>>>>> As said, for pointer type comb, we need to keep current behavior; for >>>>>> other cases, >>>>>> unconditionally convert to comb->type is the goal. >>>>>> >>>>>> Bootstrap and test on x86_64 and AArch64. Is this version OK? >>>>> >>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, >>>>> const widest_int &scale_in, >>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>> return elt; >>>>> else >>>>> - return fold_convert (type1, elt); >>>>> + return fold_convert (type, elt); >>>>> } >>>>> >>>>> the conversion should already have been done. For non-pointer comb->type >>>>> it has been converted to type by your patch. For pointer-type comb->type >>>>> it should be either pointer type or ptrofftype ('type') already as well. >>>>> >>>>> That said, can we do sth like >>>>> >>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t >>>>> >>>>> widest_int scale = wide_int_ext_for_comb (scale_in, comb); >>>>> >>>>> + if (! POINTER_TYPE_P (comb->type)) >>>>> + elt = fold_convert (comb->type, elt); >>>>> + else >>>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to >>>> aff_tree. It's not compatible for signed and unsigned integer types. >>>> Also, with this patch, we can even support elt of short type in a >>>> unsigned long comb, though this is useless. >>>> >>>>> + >>>>> if (scale == -1 >>>>> && POINTER_TYPE_P (TREE_TYPE (elt))) >>>>> { >>>>> >>>>> that is clearly do the conversion at the start in a way the state >>>>> of elt is more clear? >>>> Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok >>>> after bootstrap/test? >>> >>> - return fold_build2 (PLUS_EXPR, type1, >>> - expr, fold_convert (type1, elt)); >>> + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); >>> >>> folding not needed(?) >>> >>> - return fold_build1 (NEGATE_EXPR, type1, >>> - fold_convert (type1, elt)); >>> + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); >>> >>> likewise. >>> >>> - return fold_build2 (MINUS_EXPR, type1, >>> - expr, fold_convert (type1, elt)); >>> + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); >>> >>> likewise. >>> >>> Ok with removing those and re-testing. >> Hmm, I thought twice about the simplification, there are cases not >> properly handled: >>>>> + if (! POINTER_TYPE_P (comb->type)) >>>>> + elt = fold_convert (comb->type, elt); >>>>> + else >>>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >> This is not enough, for pointer type comb, if elt is the offset part, >> we could return signed integer type elt without folding. Though this >> shouldn't be an issue because it's always converted to ptr_offtype in >> building pointer_plus, it's better not to create such expressions in >> the first place. Check condition for unconditionally converting elt >> should be improved as: >>>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>>> + elt = fold_convert (comb->type, elt); > > Hmm, precisely as: >>>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>>> + elt = fold_convert (type, elt); Yeah, that looks good to me. >> >> With this change, folds can be removed as you suggested. I will test >> new patch for this. >> >> Thanks, >> bin >>> >>> Thanks, >>> Richard. >>> >>>> Thanks, >>>> bin >>>>> >>>>> Richard. >>>>> >>>>> >>>>> >>>>>> Thanks, >>>>>> bin >>>>>> >>>>>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>>>>> >>>>>> PR tree-optimization/80153 >>>>>> * tree-affine.c (add_elt_to_tree): Remove parameter TYPE. Use type >>>>>> of parameter COMB. Convert elt to type of COMB it COMB is not of >>>>>> pointer type. >>>>>> (aff_combination_to_tree): Update calls to add_elt_to_tree. >>>>>> * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. >>>>>> (get_computation_aff): Use utype directly for original candidate. >>>>>> >>>>>> gcc/testsuite/ChangeLog >>>>>> 2017-03-28 Bin Cheng <bin.cheng@arm.com> >>>>>> >>>>>> PR tree-optimization/80153 >>>>>> * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-03-30 14:37 ` Richard Biener @ 2017-04-05 7:25 ` Bin.Cheng 2017-04-05 7:26 ` Bin.Cheng 0 siblings, 1 reply; 11+ messages in thread From: Bin.Cheng @ 2017-04-05 7:25 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches On Thu, Mar 30, 2017 at 2:34 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Thu, Mar 30, 2017 at 3:20 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener >>>>> <richard.guenther@gmail.com> wrote: >>>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >>>>>>> <richard.guenther@gmail.com> wrote: >>>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>>>>> Hi, >>>>>>>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which >>>>>>>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded >>>>>>>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>>>>>>> code gen difference. >>>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>>>>>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>>>>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>>>>>> >>>>>>> Thanks for reviewing. >>>>>>>> Hmm. What is the desired goal? To have all elts added have >>>>>>>> comb->type as type? Then >>>>>>>> the type passed to add_elt_to_tree is redundant with comb->type. It >>>>>>>> looks like it >>>>>>>> is always passed comb->type now. >>>>>>> Yes, except pointer type comb->type, elts are converted to comb->type >>>>>>> with this patch. >>>>>>> The redundant type is removed in updated patch. >>>>>>> >>>>>>>> >>>>>>>> ISTR from past work in this area that it was important for pointer >>>>>>>> combinations to allow >>>>>>>> both pointer and sizetype elts at least. >>>>>>> Yes, It's still important to allow different types for pointer and >>>>>>> offset in pointer type comb. >>>>>>> I missed a pointer type check condition in the patch, fixed in updated patch. >>>>>>>> >>>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>>>>>>> elt is sizetype now, not of pointer type. As said above, we are >>>>>>>> trying to maintain >>>>>>>> both pointer and sizetype elts with like: >>>>>>>> >>>>>>>> if (scale == 1) >>>>>>>> { >>>>>>>> if (!expr) >>>>>>>> { >>>>>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>>> return elt; >>>>>>>> else >>>>>>>> return fold_convert (type1, elt); >>>>>>>> } >>>>>>>> >>>>>>>> where your earilier fold to type would result in not all cases handled the same >>>>>>>> (depending whether scale was -1 for example). >>>>>>> IIUC, it doesn't matter. For comb->type being pointer type, the >>>>>>> behavior remains the same. >>>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype, >>>>>>> rather than unsigned T, >>>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to >>>>>>> each other, otherwise >>>>>>> tree_to_aff_combination shouldn't distribute it as a single elt. >>>>>>> Anyway, this is addressed in updated patch by checking pointer >>>>>>> comb->type additionally. >>>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating >>>>>>> pointer_base and offset. >>>>>>> >>>>>>>> >>>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>>>>>>> and all the other wide_int_ext_for_comb calls around). >>>>>>>> >>>>>>>> And unconditionally convert to type, simplifying the rest of the code? >>>>>>> As said, for pointer type comb, we need to keep current behavior; for >>>>>>> other cases, >>>>>>> unconditionally convert to comb->type is the goal. >>>>>>> >>>>>>> Bootstrap and test on x86_64 and AArch64. Is this version OK? >>>>>> >>>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, >>>>>> const widest_int &scale_in, >>>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>> return elt; >>>>>> else >>>>>> - return fold_convert (type1, elt); >>>>>> + return fold_convert (type, elt); >>>>>> } >>>>>> >>>>>> the conversion should already have been done. For non-pointer comb->type >>>>>> it has been converted to type by your patch. For pointer-type comb->type >>>>>> it should be either pointer type or ptrofftype ('type') already as well. >>>>>> >>>>>> That said, can we do sth like >>>>>> >>>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t >>>>>> >>>>>> widest_int scale = wide_int_ext_for_comb (scale_in, comb); >>>>>> >>>>>> + if (! POINTER_TYPE_P (comb->type)) >>>>>> + elt = fold_convert (comb->type, elt); >>>>>> + else >>>>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >>>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to >>>>> aff_tree. It's not compatible for signed and unsigned integer types. >>>>> Also, with this patch, we can even support elt of short type in a >>>>> unsigned long comb, though this is useless. >>>>> >>>>>> + >>>>>> if (scale == -1 >>>>>> && POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>> { >>>>>> >>>>>> that is clearly do the conversion at the start in a way the state >>>>>> of elt is more clear? >>>>> Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok >>>>> after bootstrap/test? >>>> >>>> - return fold_build2 (PLUS_EXPR, type1, >>>> - expr, fold_convert (type1, elt)); >>>> + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); >>>> >>>> folding not needed(?) >>>> >>>> - return fold_build1 (NEGATE_EXPR, type1, >>>> - fold_convert (type1, elt)); >>>> + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); >>>> >>>> likewise. >>>> >>>> - return fold_build2 (MINUS_EXPR, type1, >>>> - expr, fold_convert (type1, elt)); >>>> + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); >>>> >>>> likewise. >>>> >>>> Ok with removing those and re-testing. >>> Hmm, I thought twice about the simplification, there are cases not >>> properly handled: >>>>>> + if (! POINTER_TYPE_P (comb->type)) >>>>>> + elt = fold_convert (comb->type, elt); >>>>>> + else >>>>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >>> This is not enough, for pointer type comb, if elt is the offset part, >>> we could return signed integer type elt without folding. Though this >>> shouldn't be an issue because it's always converted to ptr_offtype in >>> building pointer_plus, it's better not to create such expressions in >>> the first place. Check condition for unconditionally converting elt >>> should be improved as: >>>>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>> + elt = fold_convert (comb->type, elt); >> >> Hmm, precisely as: >>>>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>> + elt = fold_convert (type, elt); > > Yeah, that looks good to me. > Turned out it's more subtle than expected. Here is the latest version patch which I think makes aff_tree's type semantics more clear. Detailed comment is added in tree-affine.h describing its semantics. /* This aff_tree represents fully folded expression in a distributed way. For example, tree expression: (unsigned long)(A + ((sizetype)((integer)B + C) + (sizetype)D * 2) * 4) can be represented as aff_tree like: { type = unsigned long offset = 0 elts[0] = A * 1 elts[1] = B * 4 elts[2] = C * 4 elts[3] = D * 8 } Note aff_tree has (root) type which is type of the original expression, elements can have their own types which are different to aff_tree's. In general, elements' type is type of folded sub-expression, and with NOP type conversion stripped. For example, elts[0] has type of A, which is type of STRIP_NOPS ((sizetype) A). Given aff_tree represents folded form of the original tree expression, it lacks ability to track whether the original form is of folded form or non-folded form. For example, both tree expressions: (unsigned)((int)A + (int)B) (unsigned)(int)A + (unsigned)(int)B have the same aff_tree repsentation. This imposes restrictions on this facility, i.e, we need to be conservative and always generate the latter form when converting aff_tree back to tree expression. This implies all elements need to be converted to aff_tree's type before converting. Always generating folded expr could lead to information loss because we can no longer know that (int)A + (int)B doesn't overflow. As a result, we should avoid using aff_tree in code generation directly. It should be used when we want to explore CSE opportunities by breaking most associations. It can be then used in code generation if there will be benefit. It's possible to represent POINTER_PLUS_EXPR in aff_tree, the aff_tree has pointer type accordingly. Such aff_tree is special in two ways: 1) It has a base element which is the original base pointer. Other elements belong to offset part of the original expression. When converting back to tree, other elements need to be converted to ptr_offtype, rather than pointer type. 2) In aff_tree computation, base element can be eliminated, it's the user's responsibility to convert the rest aff_tree to ptr_offtype. The rest aff_tree stands for offset part expression, no longer the POINTER_PLUS_EXPR. */ As an real example, use of aff_tree in add_iv_candidate_for_use breaks above semantics. It needs to convert aff_tree to ptr_offtype after removing pointer element. Here I simply choose not to use aff_tree since it's unnecessary. Bootstrap and test on x86_64 and AArch64. Is this version OK? Thanks, bin 2017-04-04 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/80153 * tree-affine.h (struct aff_tree): Add comment. * tree-affine.c (add_elt_to_tree): Remove parameter TYPE, and use parameter COMB's type instead. Preserve elt's pointer type if it is the base pointer of a pointer type COMB. (aff_combination_to_tree): Update calls to add_elt_to_tree. * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. (add_iv_candidate_for_use): Check and remove POINTER_PLUS_EXPR's base part directly, rather than through aff_tree. (get_computation_aff): Use utype directly for original candidate. gcc/testsuite/ChangeLog 2017-04-04 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/80153 * gcc.c-torture/execute/pr80153.c: New. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH PR80153]Always generate folded type conversion in tree-affine 2017-04-05 7:25 ` Bin.Cheng @ 2017-04-05 7:26 ` Bin.Cheng 0 siblings, 0 replies; 11+ messages in thread From: Bin.Cheng @ 2017-04-05 7:26 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 11915 bytes --] And the patch.. On Wed, Apr 5, 2017 at 8:25 AM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Thu, Mar 30, 2017 at 2:34 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Thu, Mar 30, 2017 at 3:20 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener >>>> <richard.guenther@gmail.com> wrote: >>>>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener >>>>>> <richard.guenther@gmail.com> wrote: >>>>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener >>>>>>>> <richard.guenther@gmail.com> wrote: >>>>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>>>>>> Hi, >>>>>>>>>> This patch is to fix PR80153. As analyzed in the PR, root cause is tree_affine lacks >>>>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, >>>>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which >>>>>>>>>> is wrong if the original expression has the latter form. The patch resolves the issue >>>>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded >>>>>>>>>> expression. Also as analyzed in comment, I think this change won't result in substantial >>>>>>>>>> code gen difference. >>>>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c. >>>>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate >>>>>>>>>> is chosen, it should be unnecessary to compute in uutype. Also this adjustment only >>>>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c. >>>>>>>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>>>>>>> >>>>>>>> Thanks for reviewing. >>>>>>>>> Hmm. What is the desired goal? To have all elts added have >>>>>>>>> comb->type as type? Then >>>>>>>>> the type passed to add_elt_to_tree is redundant with comb->type. It >>>>>>>>> looks like it >>>>>>>>> is always passed comb->type now. >>>>>>>> Yes, except pointer type comb->type, elts are converted to comb->type >>>>>>>> with this patch. >>>>>>>> The redundant type is removed in updated patch. >>>>>>>> >>>>>>>>> >>>>>>>>> ISTR from past work in this area that it was important for pointer >>>>>>>>> combinations to allow >>>>>>>>> both pointer and sizetype elts at least. >>>>>>>> Yes, It's still important to allow different types for pointer and >>>>>>>> offset in pointer type comb. >>>>>>>> I missed a pointer type check condition in the patch, fixed in updated patch. >>>>>>>>> >>>>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case >>>>>>>>> elt is sizetype now, not of pointer type. As said above, we are >>>>>>>>> trying to maintain >>>>>>>>> both pointer and sizetype elts with like: >>>>>>>>> >>>>>>>>> if (scale == 1) >>>>>>>>> { >>>>>>>>> if (!expr) >>>>>>>>> { >>>>>>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>>>> return elt; >>>>>>>>> else >>>>>>>>> return fold_convert (type1, elt); >>>>>>>>> } >>>>>>>>> >>>>>>>>> where your earilier fold to type would result in not all cases handled the same >>>>>>>>> (depending whether scale was -1 for example). >>>>>>>> IIUC, it doesn't matter. For comb->type being pointer type, the >>>>>>>> behavior remains the same. >>>>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype, >>>>>>>> rather than unsigned T, >>>>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to >>>>>>>> each other, otherwise >>>>>>>> tree_to_aff_combination shouldn't distribute it as a single elt. >>>>>>>> Anyway, this is addressed in updated patch by checking pointer >>>>>>>> comb->type additionally. >>>>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating >>>>>>>> pointer_base and offset. >>>>>>>> >>>>>>>>> >>>>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one? >>>>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input >>>>>>>>> and all the other wide_int_ext_for_comb calls around). >>>>>>>>> >>>>>>>>> And unconditionally convert to type, simplifying the rest of the code? >>>>>>>> As said, for pointer type comb, we need to keep current behavior; for >>>>>>>> other cases, >>>>>>>> unconditionally convert to comb->type is the goal. >>>>>>>> >>>>>>>> Bootstrap and test on x86_64 and AArch64. Is this version OK? >>>>>>> >>>>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, >>>>>>> const widest_int &scale_in, >>>>>>> if (POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>> return elt; >>>>>>> else >>>>>>> - return fold_convert (type1, elt); >>>>>>> + return fold_convert (type, elt); >>>>>>> } >>>>>>> >>>>>>> the conversion should already have been done. For non-pointer comb->type >>>>>>> it has been converted to type by your patch. For pointer-type comb->type >>>>>>> it should be either pointer type or ptrofftype ('type') already as well. >>>>>>> >>>>>>> That said, can we do sth like >>>>>>> >>>>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t >>>>>>> >>>>>>> widest_int scale = wide_int_ext_for_comb (scale_in, comb); >>>>>>> >>>>>>> + if (! POINTER_TYPE_P (comb->type)) >>>>>>> + elt = fold_convert (comb->type, elt); >>>>>>> + else >>>>>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>>>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >>>>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to >>>>>> aff_tree. It's not compatible for signed and unsigned integer types. >>>>>> Also, with this patch, we can even support elt of short type in a >>>>>> unsigned long comb, though this is useless. >>>>>> >>>>>>> + >>>>>>> if (scale == -1 >>>>>>> && POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>> { >>>>>>> >>>>>>> that is clearly do the conversion at the start in a way the state >>>>>>> of elt is more clear? >>>>>> Yes, thanks. V3 patch attached (with gcc_assert removed). Is it ok >>>>>> after bootstrap/test? >>>>> >>>>> - return fold_build2 (PLUS_EXPR, type1, >>>>> - expr, fold_convert (type1, elt)); >>>>> + return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt)); >>>>> >>>>> folding not needed(?) >>>>> >>>>> - return fold_build1 (NEGATE_EXPR, type1, >>>>> - fold_convert (type1, elt)); >>>>> + return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt)); >>>>> >>>>> likewise. >>>>> >>>>> - return fold_build2 (MINUS_EXPR, type1, >>>>> - expr, fold_convert (type1, elt)); >>>>> + return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt)); >>>>> >>>>> likewise. >>>>> >>>>> Ok with removing those and re-testing. >>>> Hmm, I thought twice about the simplification, there are cases not >>>> properly handled: >>>>>>> + if (! POINTER_TYPE_P (comb->type)) >>>>>>> + elt = fold_convert (comb->type, elt); >>>>>>> + else >>>>>>> + gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt)) >>>>>>> + || types_compatible_p (TREE_TYPE (elt), type1)); >>>> This is not enough, for pointer type comb, if elt is the offset part, >>>> we could return signed integer type elt without folding. Though this >>>> shouldn't be an issue because it's always converted to ptr_offtype in >>>> building pointer_plus, it's better not to create such expressions in >>>> the first place. Check condition for unconditionally converting elt >>>> should be improved as: >>>>>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>> + elt = fold_convert (comb->type, elt); >>> >>> Hmm, precisely as: >>>>>>> + if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt))) >>>>>>> + elt = fold_convert (type, elt); >> >> Yeah, that looks good to me. >> > Turned out it's more subtle than expected. Here is the latest version > patch which I think makes aff_tree's type semantics more clear. > Detailed comment is added in tree-affine.h describing its semantics. > > /* This aff_tree represents fully folded expression in a distributed way. > For example, tree expression: > (unsigned long)(A + ((sizetype)((integer)B + C) + (sizetype)D * 2) * 4) > can be represented as aff_tree like: > { > type = unsigned long > offset = 0 > elts[0] = A * 1 > elts[1] = B * 4 > elts[2] = C * 4 > elts[3] = D * 8 > } > Note aff_tree has (root) type which is type of the original expression, > elements can have their own types which are different to aff_tree's. In > general, elements' type is type of folded sub-expression, and with NOP > type conversion stripped. For example, elts[0] has type of A, which is > type of STRIP_NOPS ((sizetype) A). > > Given aff_tree represents folded form of the original tree expression, > it lacks ability to track whether the original form is of folded form > or non-folded form. For example, both tree expressions: > (unsigned)((int)A + (int)B) > (unsigned)(int)A + (unsigned)(int)B > have the same aff_tree repsentation. This imposes restrictions on this > facility, i.e, we need to be conservative and always generate the latter > form when converting aff_tree back to tree expression. This implies all > elements need to be converted to aff_tree's type before converting. > > Always generating folded expr could lead to information loss because we > can no longer know that (int)A + (int)B doesn't overflow. As a result, > we should avoid using aff_tree in code generation directly. It should > be used when we want to explore CSE opportunities by breaking most > associations. It can be then used in code generation if there will be > benefit. > > It's possible to represent POINTER_PLUS_EXPR in aff_tree, the aff_tree > has pointer type accordingly. Such aff_tree is special in two ways: > 1) It has a base element which is the original base pointer. Other > elements belong to offset part of the original expression. When > converting back to tree, other elements need to be converted to > ptr_offtype, rather than pointer type. > 2) In aff_tree computation, base element can be eliminated, it's the > user's responsibility to convert the rest aff_tree to ptr_offtype. > The rest aff_tree stands for offset part expression, no longer the > POINTER_PLUS_EXPR. */ > > As an real example, use of aff_tree in add_iv_candidate_for_use breaks > above semantics. It needs to convert aff_tree to ptr_offtype after > removing pointer element. Here I simply choose not to use aff_tree > since it's unnecessary. > > Bootstrap and test on x86_64 and AArch64. Is this version OK? > > Thanks, > bin > 2017-04-04 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/80153 > * tree-affine.h (struct aff_tree): Add comment. > * tree-affine.c (add_elt_to_tree): Remove parameter TYPE, and use > parameter COMB's type instead. Preserve elt's pointer type if it > is the base pointer of a pointer type COMB. > (aff_combination_to_tree): Update calls to add_elt_to_tree. > * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types. > (add_iv_candidate_for_use): Check and remove POINTER_PLUS_EXPR's > base part directly, rather than through aff_tree. > (get_computation_aff): Use utype directly for original candidate. > > gcc/testsuite/ChangeLog > 2017-04-04 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/80153 > * gcc.c-torture/execute/pr80153.c: New. [-- Attachment #2: pr80153-20170404.txt --] [-- Type: text/plain, Size: 11405 bytes --] diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c new file mode 100644 index 0000000..3eed578 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c @@ -0,0 +1,48 @@ +/* PR tree-optimization/80153 */ + +void check (int, int, int) __attribute__((noinline)); +void check (int c, int c2, int val) +{ + if (!val) { + __builtin_abort(); + } +} + +static const char *buf; +static int l, i; + +void _fputs(const char *str) __attribute__((noinline)); +void _fputs(const char *str) +{ + buf = str; + i = 0; + l = __builtin_strlen(buf); +} + +char _fgetc() __attribute__((noinline)); +char _fgetc() +{ + char val = buf[i]; + i++; + if (i > l) + return -1; + else + return val; +} + +static const char *string = "oops!\n"; + +int main(void) +{ + int i; + int c; + + _fputs(string); + + for (i = 0; i < __builtin_strlen(string); i++) { + c = _fgetc(); + check(c, string[i], c == string[i]); + } + + return 0; +} diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index e620eea..83c2c6b 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -370,66 +370,54 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb) aff_combination_elt (comb, type, expr); } -/* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine +/* Creates EXPR + ELT * SCALE in COMB's type. EXPR is taken from affine combination COMB. */ static tree -add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, - aff_tree *comb ATTRIBUTE_UNUSED) +add_elt_to_tree (tree expr, tree elt, const widest_int &scale_in, + aff_tree *comb) { enum tree_code code; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; - + /* Result type for this elt. */ + tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type; widest_int scale = wide_int_ext_for_comb (scale_in, comb); - if (scale == -1 - && POINTER_TYPE_P (TREE_TYPE (elt))) - { - elt = convert_to_ptrofftype (elt); - elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt); - scale = 1; - } + /* Preserve elt's pointer type only if below conditions are satisfied: + 1) the result expression is of pointer type; + 2) scale is 1; + 3) expr is not of pointer type. + For all other cases, force it to result type. */ + if (scale != 1 + || !POINTER_TYPE_P (comb->type) + || !POINTER_TYPE_P (TREE_TYPE (elt)) + || (expr != NULL_TREE && POINTER_TYPE_P (TREE_TYPE (expr)))) + elt = fold_convert (type, elt); if (scale == 1) { if (!expr) - { - if (POINTER_TYPE_P (TREE_TYPE (elt))) - return elt; - else - return fold_convert (type1, elt); - } - + return elt; if (POINTER_TYPE_P (TREE_TYPE (expr))) return fold_build_pointer_plus (expr, elt); if (POINTER_TYPE_P (TREE_TYPE (elt))) return fold_build_pointer_plus (elt, expr); - return fold_build2 (PLUS_EXPR, type1, - expr, fold_convert (type1, elt)); + + return fold_build2 (PLUS_EXPR, type, expr, elt); } if (scale == -1) { if (!expr) - return fold_build1 (NEGATE_EXPR, type1, - fold_convert (type1, elt)); - + return fold_build1 (NEGATE_EXPR, type, elt); if (POINTER_TYPE_P (TREE_TYPE (expr))) - { - elt = convert_to_ptrofftype (elt); - elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt); - return fold_build_pointer_plus (expr, elt); - } - return fold_build2 (MINUS_EXPR, type1, - expr, fold_convert (type1, elt)); + return fold_build_pointer_plus (expr, + fold_build1 (NEGATE_EXPR, type, elt)); + + return fold_build2 (MINUS_EXPR, type, expr, elt); } - elt = fold_convert (type1, elt); if (!expr) - return fold_build2 (MULT_EXPR, type1, elt, - wide_int_to_tree (type1, scale)); + return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); if (wi::neg_p (scale)) { @@ -439,15 +427,14 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, else code = PLUS_EXPR; - elt = fold_build2 (MULT_EXPR, type1, elt, - wide_int_to_tree (type1, scale)); + elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); if (POINTER_TYPE_P (TREE_TYPE (expr))) { if (code == MINUS_EXPR) - elt = fold_build1 (NEGATE_EXPR, type1, elt); + elt = fold_build1 (NEGATE_EXPR, type, elt); return fold_build_pointer_plus (expr, elt); } - return fold_build2 (code, type1, expr, elt); + return fold_build2 (code, type, expr, elt); } /* Makes tree from the affine combination COMB. */ @@ -455,22 +442,18 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in, tree aff_combination_to_tree (aff_tree *comb) { - tree type = comb->type; tree expr = NULL_TREE; unsigned i; widest_int off, sgn; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; + tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type; gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); for (i = 0; i < comb->n; i++) - expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef, - comb); + expr = add_elt_to_tree (expr, comb->elts[i].val, comb->elts[i].coef, comb); if (comb->rest) - expr = add_elt_to_tree (expr, type, comb->rest, 1, comb); + expr = add_elt_to_tree (expr, comb->rest, 1, comb); /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is unsigned. */ @@ -484,8 +467,7 @@ aff_combination_to_tree (aff_tree *comb) off = comb->offset; sgn = 1; } - return add_elt_to_tree (expr, type, wide_int_to_tree (type1, off), sgn, - comb); + return add_elt_to_tree (expr, wide_int_to_tree (type, off), sgn, comb); } /* Copies the tree elements of COMB to ensure that they are not shared. */ diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h index b8eb8cc..5b84aef 100644 --- a/gcc/tree-affine.h +++ b/gcc/tree-affine.h @@ -37,6 +37,52 @@ struct aff_comb_elt widest_int coef; }; +/* This aff_tree represents fully folded expression in a distributed way. + For example, tree expression: + (unsigned long)(A + ((sizetype)((integer)B + C) + (sizetype)D * 2) * 4) + can be represented as aff_tree like: + { + type = unsigned long + offset = 0 + elts[0] = A * 1 + elts[1] = B * 4 + elts[2] = C * 4 + elts[3] = D * 8 + } + Note aff_tree has (root) type which is type of the original expression, + elements can have their own types which are different to aff_tree's. In + general, elements' type is type of folded sub-expression, and with NOP + type conversion stripped. For example, elts[0] has type of A, which is + type of STRIP_NOPS ((sizetype) A). + + Given aff_tree represents folded form of the original tree expression, + it lacks ability to track whether the original form is of folded form + or non-folded form. For example, both tree expressions: + (unsigned)((int)A + (int)B) + (unsigned)(int)A + (unsigned)(int)B + have the same aff_tree repsentation. This imposes restrictions on this + facility, i.e, we need to be conservative and always generate the latter + form when converting aff_tree back to tree expression. This implies all + elements need to be converted to aff_tree's type before converting. + + Always generating folded expr could lead to information loss because we + can no longer know that (int)A + (int)B doesn't overflow. As a result, + we should avoid using aff_tree in code generation directly. It should + be used when we want to explore CSE opportunities by breaking most + associations. It can be then used in code generation if there will be + benefit. + + It's possible to represent POINTER_PLUS_EXPR in aff_tree, the aff_tree + has pointer type accordingly. Such aff_tree is special in two ways: + 1) It has a base element which is the original base pointer. Other + elements belong to offset part of the original expression. When + converting back to tree, other elements need to be converted to + ptr_offtype, rather than pointer type. + 2) In aff_tree computation, base element can be eliminated, it's the + user's responsibility to convert the rest aff_tree to ptr_offtype. + The rest aff_tree stands for offset part expression, no longer the + POINTER_PLUS_EXPR. */ + struct aff_tree { /* Type of the result of the combination. */ diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 8dc65881..666f885 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step, || contain_complex_addr_expr (expr)) { aff_tree comb; - tree_to_aff_combination (expr, TREE_TYPE (base), &comb); + tree_to_aff_combination (expr, TREE_TYPE (expr), &comb); base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb)); } @@ -3335,41 +3335,20 @@ add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use) } /* Record common candidate with base_object removed in base. */ - if (iv->base_object != NULL) + base = iv->base; + STRIP_NOPS (base); + if (iv->base_object != NULL && TREE_CODE (base) == POINTER_PLUS_EXPR) { - unsigned i; - aff_tree aff_base; - tree step, base_object = iv->base_object; + tree step = iv->step; - base = iv->base; - step = iv->step; - STRIP_NOPS (base); STRIP_NOPS (step); - STRIP_NOPS (base_object); - tree_to_aff_combination (base, TREE_TYPE (base), &aff_base); - for (i = 0; i < aff_base.n; i++) - { - if (aff_base.elts[i].coef != 1) - continue; - - if (operand_equal_p (aff_base.elts[i].val, base_object, 0)) - break; - } - if (i < aff_base.n) - { - aff_combination_remove_elt (&aff_base, i); - base = aff_combination_to_tree (&aff_base); - basetype = TREE_TYPE (base); - if (POINTER_TYPE_P (basetype)) - basetype = sizetype; - - step = fold_convert (basetype, step); - record_common_cand (data, base, step, use); - /* Also record common candidate with offset stripped. */ - base = strip_offset (base, &offset); - if (offset) - record_common_cand (data, base, step, use); - } + base = TREE_OPERAND (base, 1); + step = fold_convert (sizetype, step); + record_common_cand (data, base, step, use); + /* Also record common candidate with offset stripped. */ + base = strip_offset (base, &offset); + if (offset) + record_common_cand (data, base, step, use); } /* At last, add auto-incremental candidates. Make such variables @@ -3787,6 +3766,12 @@ get_computation_aff (struct loop *loop, overflows, as all the arithmetics will in the end be performed in UUTYPE anyway. */ common_type = determine_common_wider_type (&ubase, &cbase); + /* We don't need to compute in UUTYPE if this is the original candidate, + and candidate/use have the same (pointer) type. */ + if (ctype == utype && common_type == utype + && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype) + && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) + uutype = utype; /* use = ubase - ratio * cbase + ratio * var. */ tree_to_aff_combination (ubase, common_type, aff); ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2017-04-05 7:26 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-03-28 12:17 [PATCH PR80153]Always generate folded type conversion in tree-affine Bin Cheng 2017-03-28 12:39 ` Richard Biener 2017-03-29 15:32 ` Bin.Cheng 2017-03-30 10:46 ` Richard Biener 2017-03-30 12:44 ` Bin.Cheng 2017-03-30 13:00 ` Richard Biener 2017-03-30 13:20 ` Bin.Cheng 2017-03-30 13:34 ` Bin.Cheng 2017-03-30 14:37 ` Richard Biener 2017-04-05 7:25 ` Bin.Cheng 2017-04-05 7:26 ` Bin.Cheng
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).