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.
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)
