From: Xionghu Luo <[email protected]>
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.
gcc/ChangeLog
2020-04-28 Xiong Hu Luo <[email protected]>
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 *);
--
2.21.0.777.g83232e3864
