On Tue, 28 Apr 2020, luoxhu wrote:
>
>
> On 2020/4/28 15:01, Richard Biener wrote:
> > On Tue, 28 Apr 2020, Xionghu Luo wrote:
> >
> >> From: Xionghu Luo <luo...@linux.ibm.com>
> >>
> >> Get and propagate value range info to convert expressions with convert
> >> operation on PLUS_EXPR/MINUS_EXPR/MULT_EXPR when not overflow. i.e.:
> >>
> >> (long unsigned int)((unsigned int)n * 10 + 1)
> >> =>
> >> (long unsigned int)((unsigned int) n * (long unsigned int)10 + (long
> >> unsigned int)1)
> >>
> >> With this patch for affine combination, load/store motion could detect
> >> more address refs independency and promote some memory expressions to
> >> registers within loop.
> >>
> >> PS: Replace the previous "(T1)(X + CST) as (T1)X - (T1)(-CST))"
> >> to "(T1)(X + CST) as (T1)X + (T1)(CST))" for wrapping overflow.
> >>
> >> Bootstrap and regression tested pass on Power8-LE. Any comments?
> >> Thanks.
> >
> > So the core of the patch is adding handling of MULT_EXPR and the rest
> > is a no-op? It's not clear from the patch what passing down a
> > value-range does and your description doesn't say anything about this
> > either.
>
> This patch handles MULT_EXPR first, and also handles (long unsigned int)(n_93
> * 10 + 1) as
> "n_93*10" is not a ssa_name by using the value_range passed down, minv&maxv
> [1,81] is the
> range info of "n_93 * 10 +1", so wi::leu_p (maxv, wi::to_wide (TYPE_MAX_VALUE
> (itype)) in
> expr_to_aff_combination could ensure that no wrapping overflow of this
> converting. Not sure
> if it's better described now... And some debug message as follows:
>
> 131t.lim2:
> # n_93 = PHI <0(2), n_36(7)>
> _118 = n_93 * 10;
> _120 = (long unsigned int) _118;
> _121 = _120 * 8;
> _122 = &C[0][0] + _121;
> *_122 = 0.0;
> _128 = _118 + 1;
> _129 = (long unsigned int) _128;
> _130 = _129 * 8;
> _131 = &C[0][0] + _130;
> *_131 = 0.0;
> _137 = _118 + 2;
> _138 = (long unsigned int) _137;
> _139 = _138 * 8;
> _140 = &C[0][0] + _139;
> *_140 = 0.0;
>
>
> Breakpoint 28, expr_to_aff_combination (comb=0x7fffffffc068, code=NOP_EXPR,
> type=<integer_type 0x7ffff53c07
> e0 long unsigned int>, op0=<plus_expr 0x7ffff56c0988>, op1=<tree 0x0>,
> vr=0x7fffffffc490) at ../../gcc-mast
> er/gcc/tree-affine.c:350
> 92: itype = <integer_type 0x7ffff53c0690 unsigned int>
> 93: otype = <integer_type 0x7ffff53c07e0 long unsigned int>
> 94: icode = PLUS_EXPR
> 95: code = NOP_EXPR
> (gdb) ptree op0
> <mult_expr 0x7ffff56c0960
> type <integer_type 0x7ffff53c0690 unsigned int sizes-gimplified public
> unsigned SI
> size <integer_cst 0x7ffff52f1200 constant 32>
> unit-size <integer_cst 0x7ffff52f1218 constant 4>
> align:32 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type
> 0x7ffff53c0690 precision:32 min <
> integer_cst 0x7ffff52f1230 0> max <integer_cst 0x7ffff52f11e8 4294967295>
> context <translation_unit_decl 0x
> 7ffff5552850 pr83403.c>
> pointer_to_this <pointer_type 0x7ffff53c4c20>>
>
> arg:0 <ssa_name 0x7ffff5394a88 type <integer_type 0x7ffff53c0690 unsigned
> int>
> visited var <var_decl 0x7ffff72e2520 n>
> def_stmt n_93 = PHI <0(2), n_36(7)>
> version:93
> ptr-info 0x7ffff530b680>
> arg:1 <integer_cst 0x7ffff52feda8 type <integer_type 0x7ffff53c0690
> unsigned int> constant 10>>
> (gdb) ptree op1
> <integer_cst 0x7ffff52fed48 type <integer_type 0x7ffff53c0690 unsigned int>
> constant 1>
> (gdb) p minv
> $580 = {
> <wide_int_storage> = {
> val = {1, 0, 140737310886240},
> len = 1,
> precision = 32
> },
> members of generic_wide_int<wide_int_storage>:
> static is_sign_extended = true
> }
> (gdb) p maxv
> $581 = {
> <wide_int_storage> = {
> val = {81, 65, 40},
> len = 1,
> precision = 32
> },
> members of generic_wide_int<wide_int_storage>:
> static is_sign_extended = true
> }
OK, I guess instead of get_range_info expr_to_aff_combination could
simply use determine_value_range (op0, &minv, &maxv) == VR_RANGE
(the && TREE_CODE (op0) == SSA_NAME check can then be removed)?
Thanks,
Richard.
>
> Thanks,
> Xionghu
>
> >
> > Richard.
> >
> >> gcc/ChangeLog
> >>
> >> 2020-04-28 Xiong Hu Luo <luo...@linux.ibm.com>
> >>
> >> PR tree-optimization/83403
> >> * tree-affine.c (aff_combination_convert): New parameter
> >> value_range.
> >> (expr_to_aff_combination): Use range info to check CONVERT
> >> expr on PLUS_EXPR/MINUS_EXPR/MULT_EXPR.
> >> (tree_to_aff_combination): Likewise.
> >> (aff_combination_expand): Get and propagate range info.
> >> * tree-affine.h: Include value-range.h.
> >> (aff_combination_convert): New parameter value_range.
> >> (tree_to_aff_combination): Likewise.
> >> (aff_combination_expand): Likewise.
> >> ---
> >> gcc/tree-affine.c | 66 +++++++++++++++++++++++++++--------------------
> >> gcc/tree-affine.h | 8 +++---
> >> 2 files changed, 43 insertions(+), 31 deletions(-)
> >>
> >> diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
> >> index 0eb8db1b086..63f8acd4c73 100644
> >> --- a/gcc/tree-affine.c
> >> +++ b/gcc/tree-affine.c
> >> @@ -220,7 +220,7 @@ aff_combination_add (aff_tree *comb1, aff_tree *comb2)
> >> /* Converts affine combination COMB to TYPE. */
> >>
> >> void
> >> -aff_combination_convert (aff_tree *comb, tree type)
> >> +aff_combination_convert (aff_tree *comb, tree type, value_range *vr)
> >> {
> >> unsigned i, j;
> >> tree comb_type = comb->type;
> >> @@ -228,7 +228,7 @@ aff_combination_convert (aff_tree *comb, tree type)
> >> if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
> >> {
> >> tree val = fold_convert (type, aff_combination_to_tree (comb));
> >> - tree_to_aff_combination (val, type, comb);
> >> + tree_to_aff_combination (val, type, comb, vr);
> >> return;
> >> }
> >>
> >> @@ -263,8 +263,8 @@ aff_combination_convert (aff_tree *comb, tree type)
> >> true when that was successful and returns the combination in COMB. */
> >>
> >> static bool
> >> -expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
> >> - tree op0, tree op1 = NULL_TREE)
> >> +expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, tree
> >> op0,
> >> + tree op1 = NULL_TREE, value_range *vr = NULL)
> >> {
> >> aff_tree tmp;
> >> poly_int64 bitpos, bitsize, bytepos;
> >> @@ -279,8 +279,8 @@ expr_to_aff_combination (aff_tree *comb, tree_code
> >> code, tree type,
> >>
> >> case PLUS_EXPR:
> >> case MINUS_EXPR:
> >> - tree_to_aff_combination (op0, type, comb);
> >> - tree_to_aff_combination (op1, type, &tmp);
> >> + tree_to_aff_combination (op0, type, comb, vr);
> >> + tree_to_aff_combination (op1, type, &tmp, vr);
> >> if (code == MINUS_EXPR)
> >> aff_combination_scale (&tmp, -1);
> >> aff_combination_add (comb, &tmp);
> >> @@ -289,7 +289,7 @@ expr_to_aff_combination (aff_tree *comb, tree_code
> >> code, tree type,
> >> case MULT_EXPR:
> >> if (TREE_CODE (op1) != INTEGER_CST)
> >> break;
> >> - tree_to_aff_combination (op0, type, comb);
> >> + tree_to_aff_combination (op0, type, comb, vr);
> >> aff_combination_scale (comb, wi::to_widest (op1));
> >> return true;
> >>
> >> @@ -340,27 +340,33 @@ expr_to_aff_combination (aff_tree *comb, tree_code
> >> code, tree type,
> >> op1 = fold_convert (otype, op1);
> >> return expr_to_aff_combination (comb, icode, otype, op0, op1);
> >> }
> >> - wide_int minv, maxv;
> >> +
> >> /* If inner type has wrapping overflow behavior, fold conversion
> >> - for below case:
> >> - (T1)(X - CST) -> (T1)X - (T1)CST
> >> - if X - CST doesn't overflow by range information. Also handle
> >> - (T1)(X + CST) as (T1)(X - (-CST)). */
> >> - if (TYPE_UNSIGNED (itype)
> >> + for below cases:
> >> + (T1)(X *+- CST) -> (T1)X *+- (T1)CST
> >> + when X *+- CST doesn't overflow by range information. */
> >> + if (vr && vr->kind () == VR_RANGE && TYPE_UNSIGNED (itype)
> >> && TYPE_OVERFLOW_WRAPS (itype)
> >> - && TREE_CODE (op0) == SSA_NAME
> >> - && TREE_CODE (op1) == INTEGER_CST
> >> - && icode != MULT_EXPR
> >> - && get_range_info (op0, &minv, &maxv) == VR_RANGE)
> >> + && TREE_CODE (op1) == INTEGER_CST)
> >> {
> >> - if (icode == PLUS_EXPR)
> >> - op1 = wide_int_to_tree (itype, -wi::to_wide (op1));
> >> - if (wi::geu_p (minv, wi::to_wide (op1)))
> >> + wide_int minv, maxv;
> >> + minv = wi::to_wide (vr->min ());
> >> + maxv = wi::to_wide (vr->max ());
> >> + if ((icode == MULT_EXPR || icode == PLUS_EXPR)
> >> + && wi::leu_p (maxv, wi::to_wide (TYPE_MAX_VALUE (itype))))
> >> + {
> >> + op0 = fold_convert (otype, op0);
> >> + op1 = fold_convert (otype, op1);
> >> + return expr_to_aff_combination (comb, icode, otype, op0,
> >> + op1, vr);
> >> + }
> >> + else if (icode == MINUS_EXPR
> >> + && wi::geu_p (minv, wi::to_wide (op1)))
> >> {
> >> op0 = fold_convert (otype, op0);
> >> op1 = fold_convert (otype, op1);
> >> return expr_to_aff_combination (comb, MINUS_EXPR, otype,
> >> - op0, op1);
> >> + op0, op1, vr);
> >> }
> >> }
> >> }
> >> @@ -376,7 +382,7 @@ expr_to_aff_combination (aff_tree *comb, tree_code
> >> code, tree type,
> >> /* Splits EXPR into an affine combination of parts. */
> >>
> >> void
> >> -tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
> >> +tree_to_aff_combination (tree expr, tree type, aff_tree *comb,
> >> value_range *vr)
> >> {
> >> aff_tree tmp;
> >> enum tree_code code;
> >> @@ -408,10 +414,10 @@ tree_to_aff_combination (tree expr, tree type,
> >> aff_tree *comb)
> >> CASE_CONVERT:
> >> /* ??? TREE_TYPE (expr) should be equal to type here, but IVOPTS
> >> calls this with not showing an outer widening cast. */
> >> - if (expr_to_aff_combination (comb, code,
> >> - TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
> >> + if (expr_to_aff_combination (comb, code, TREE_TYPE (expr),
> >> + TREE_OPERAND (expr, 0), NULL_TREE, vr))
> >> {
> >> - aff_combination_convert (comb, type);
> >> + aff_combination_convert (comb, type, vr);
> >> return;
> >> }
> >> break;
> >> @@ -709,7 +715,8 @@ public:
> >>
> >> void
> >> aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
> >> - hash_map<tree, name_expansion *> **cache)
> >> + hash_map<tree, name_expansion *> **cache,
> >> + value_range *vr)
> >> {
> >> unsigned i;
> >> aff_tree to_add, current, curre;
> >> @@ -800,7 +807,10 @@ aff_combination_expand (aff_tree *comb
> >> ATTRIBUTE_UNUSED,
> >> if (!*cache)
> >> *cache = new hash_map<tree, name_expansion *>;
> >> (*cache)->put (name, exp);
> >> - aff_combination_expand (¤t, cache);
> >> + value_range vr = NULL;
> >> + if (!POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (def))))
> >> + get_range_info (gimple_assign_rhs1 (def), vr);
> >> + aff_combination_expand (¤t, cache, &vr);
> >> exp->expansion = current;
> >> exp->in_progress = 0;
> >> }
> >> @@ -812,7 +822,7 @@ aff_combination_expand (aff_tree *comb
> >> ATTRIBUTE_UNUSED,
> >> current = exp->expansion;
> >> }
> >> if (!useless_type_conversion_p (comb->type, current.type))
> >> - aff_combination_convert (¤t, comb->type);
> >> + aff_combination_convert (¤t, comb->type, vr);
> >>
> >> /* Accumulate the new terms to TO_ADD, so that we do not modify
> >> COMB while traversing it; include the term -coef * E, to remove
> >> diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h
> >> index 4ec4924879d..311e5e7c23a 100644
> >> --- a/gcc/tree-affine.h
> >> +++ b/gcc/tree-affine.h
> >> @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3. If not see
> >> #ifndef GCC_TREE_AFFINE_H
> >> #define GCC_TREE_AFFINE_H
> >>
> >> +#include "value-range.h"
> >>
> >> #define MAX_AFF_ELTS 8
> >>
> >> @@ -73,13 +74,14 @@ void aff_combination_mult (aff_tree *, aff_tree *,
> >> aff_tree *);
> >> void aff_combination_add (aff_tree *, aff_tree *);
> >> void aff_combination_add_elt (aff_tree *, tree, const widest_int &);
> >> void aff_combination_remove_elt (aff_tree *, unsigned);
> >> -void aff_combination_convert (aff_tree *, tree);
> >> -void tree_to_aff_combination (tree, tree, aff_tree *);
> >> +void aff_combination_convert (aff_tree *, tree, value_range *vr = NULL);
> >> +void tree_to_aff_combination (tree, tree, aff_tree *, value_range *vr =
> >> NULL);
> >> tree aff_combination_to_tree (aff_tree *);
> >> void unshare_aff_combination (aff_tree *);
> >> bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *,
> >> poly_widest_int *);
> >> -void aff_combination_expand (aff_tree *, hash_map<tree, name_expansion *>
> >> **);
> >> +void aff_combination_expand (aff_tree *, hash_map<tree, name_expansion *>
> >> **,
> >> + value_range *vr = NULL);
> >> void tree_to_aff_combination_expand (tree, tree, aff_tree *,
> >> hash_map<tree, name_expansion *> **);
> >> tree get_inner_reference_aff (tree, aff_tree *, poly_widest_int *);
> >>
> >
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
