new file mode 100644
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+unsigned long foo (char);
+void addressing (char *arr1, unsigned long n) {
+ for (unsigned long i = 0; i < n;) {
+ *arr1 += 1;
+ unsigned long advance = foo (*arr1);
+ arr1 += advance;
+ i += advance;
+ }
+}
+/* { dg-final { scan-tree-dump-times "= PHI <" 1 "ivopts"} } */
new file mode 100644
@@ -0,0 +1,14 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+unsigned long foo (char);
+void addressing (char *arr1, char *arr2, unsigned long n) {
+ for (unsigned long i = 0; i < n;) {
+ *arr1 += *arr2;
+ unsigned long advance = foo (*arr1);
+ arr1 += advance;
+ arr2 += advance;
+ i += advance;
+ }
+}
+/* { dg-final { scan-tree-dump-times "= PHI <" 1 "ivopts"} } */
@@ -12,6 +12,6 @@ tr3 (short array[], unsigned int n)
return sum;
}
-/* { dg-final { scan-tree-dump-times "PHI <ivtmp" 1 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times "PHI <ivtmp" 0 "ivopts"} } */
/* { dg-final { scan-tree-dump-times "PHI <x" 0 "ivopts"} } */
-/* { dg-final { scan-tree-dump-times ", x" 0 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times ", x" 1 "ivopts"} } */
@@ -12,6 +12,6 @@ tr1 (int array[], unsigned int n)
return sum;
}
-/* { dg-final { scan-tree-dump-times "PHI <ivtmp" 1 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times "PHI <ivtmp" 0 "ivopts"} } */
/* { dg-final { scan-tree-dump-times "PHI <x" 0 "ivopts"} } */
-/* { dg-final { scan-tree-dump-times ", x" 0 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times ", x" 1 "ivopts"} } */
@@ -1171,6 +1171,72 @@ chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
}
+static tree
+chrec_get_symbol_defined_in_loop (tree chrec, unsigned loop_nb,
+ bool *multiple,
+ hash_set<const_tree> &visited)
+{
+ int i, n;
+
+ if (chrec == NULL_TREE)
+ return NULL_TREE;
+
+ if (is_gimple_min_invariant (chrec))
+ return NULL_TREE;
+
+ if (TREE_CODE (chrec) == SSA_NAME)
+ {
+ gimple *def;
+ loop_p def_loop, loop;
+
+ if (SSA_NAME_IS_DEFAULT_DEF (chrec))
+ return NULL_TREE;
+
+ def = SSA_NAME_DEF_STMT (chrec);
+ def_loop = loop_containing_stmt (def);
+ loop = get_loop (cfun, loop_nb);
+
+ if (def_loop == NULL)
+ return NULL_TREE;
+
+ if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
+ return chrec;
+
+ return NULL_TREE;
+ }
+
+ if (visited.add (chrec))
+ return NULL_TREE;
+
+ tree res = NULL_TREE;
+ n = TREE_OPERAND_LENGTH (chrec);
+ for (i = 0; i < n; i++)
+ {
+ tree new_res
+ = chrec_get_symbol_defined_in_loop (TREE_OPERAND (chrec, i), loop_nb,
+ multiple, visited);
+ if (!new_res)
+ continue;
+
+ if (res)
+ *multiple = true;
+
+ res = new_res;
+ }
+ return res;
+}
+
+/* Find's a single loop variant SSA symbol from within CHREC if there is one.
+ If there are multiple, then MULTIPLE gets set to true. */
+
+tree
+chrec_get_symbol_defined_in_loop (tree chrec, unsigned loop_nb,
+ bool *multiple)
+{
+ hash_set<const_tree> visited;
+ return chrec_get_symbol_defined_in_loop (chrec, loop_nb, multiple, visited);
+}
+
/* Determines whether the chrec contains undetermined coefficients. */
static bool
@@ -85,6 +85,7 @@ extern bool eq_evolutions_p (const_tree, const_tree);
extern bool is_multivariate_chrec (const_tree);
extern bool chrec_contains_symbols (const_tree, class loop * = NULL);
extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
+extern tree chrec_get_symbol_defined_in_loop (tree, unsigned, bool*);
extern bool chrec_contains_undetermined (const_tree);
extern bool tree_contains_chrecs (const_tree, int *);
extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
@@ -127,12 +128,15 @@ no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
return true;
}
-/* Build a polynomial chain of recurrence. */
+/* Build a polynomial chain of recurrence.
+ Disallows a loop variant value in LEFT unless ALLOW_LOOP_VARIANT_LEFT is
+ true. */
inline tree
build_polynomial_chrec (unsigned loop_num,
tree left,
- tree right)
+ tree right,
+ bool allow_loop_variant_left = false)
{
bool val;
@@ -140,8 +144,8 @@ build_polynomial_chrec (unsigned loop_num,
|| right == chrec_dont_know)
return chrec_dont_know;
- if (!no_evolution_in_loop_p (left, loop_num, &val)
- || !val)
+ if (!allow_evolution_left
+ && (!no_evolution_in_loop_p (left, loop_num, &val) || !val))
return chrec_dont_know;
/* Types of left and right sides of a chrec should be compatible, but
@@ -171,13 +171,14 @@ struct iv
{
tree base; /* Initial value of the iv. */
tree base_object; /* A memory object to that the induction variable points. */
- tree step; /* Step of the iv (constant only). */
+ tree step; /* Step of the iv. */
tree ssa_name; /* The ssa name with the value. */
struct iv_use *nonlin_use; /* The identifier in the use if it is the case. */
bool biv_p; /* Is it a biv? */
bool no_overflow; /* True if the iv doesn't overflow. */
bool have_address_use;/* For biv, indicate if it's used in any address
type use. */
+ bool affine_p; /* Are the step and base loop invariant? */
};
/* Per-ssa version information (induction variable descriptions, etc.). */
@@ -488,6 +489,8 @@ public:
/* IV uses from which this common candidate is derived. */
auto_vec<struct iv_use *> uses;
hashval_t hash;
+ /* Are the base and step loop invariant? */
+ bool affine_p;
};
/* Hashtable helpers. */
@@ -802,6 +805,8 @@ dump_iv (FILE *file, struct iv *iv, bool dump_name, unsigned indent_level)
fprintf (file, "%s Biv:\t%c\n", p, iv->biv_p ? 'Y' : 'N');
+ fprintf (file, "%s Affine:\t%c\n", p, iv->affine_p? 'Y' : 'N');
+
fprintf (file, "%s Overflowness wrto loop niter:\t%s\n",
p, iv->no_overflow ? "No-overflow" : "Overflow");
}
@@ -990,6 +995,69 @@ stmt_after_increment (class loop *loop, struct iv_cand *cand, gimple *stmt)
}
}
+/* Returns true if STMT if before the place where the original induction
+ variable CAND is incremented. */
+
+static bool
+stmt_before_ip_normal_pos (class loop *loop, gimple *stmt)
+{
+ basic_block stmt_bb = gimple_bb (stmt);
+ basic_block inc_bb = ip_normal_pos (loop);
+ if (!inc_bb)
+ return false;
+
+ return dominated_by_p (CDI_DOMINATORS, inc_bb, stmt_bb);
+}
+
+/* Returns true if STMT is before the place where the original induction
+ variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
+ if the positions are identical. */
+
+static bool
+stmt_before_inc_pos (struct iv_cand *cand, gimple *step_stmt,
+ bool true_if_equal)
+{
+ basic_block incr_bb = gimple_bb (cand->incremented_at);
+ basic_block step_bb = gimple_bb (step_stmt);
+
+ if (!dominated_by_p (CDI_DOMINATORS, incr_bb, step_bb))
+ return false;
+
+ if (step_bb != incr_bb)
+ return true;
+
+ if (true_if_equal
+ && gimple_uid (step_stmt) == gimple_uid (cand->incremented_at))
+ return true;
+ return gimple_uid (cand->incremented_at) > gimple_uid (step_stmt);
+}
+
+/* Returns true if STMT is before the place where the induction variable
+ CAND is incremented in LOOP. */
+
+static bool
+stmt_before_increment (struct iv_cand *cand, gimple *stmt, class loop* loop)
+{
+ switch (cand->pos)
+ {
+ case IP_ORIGINAL:
+ return true;
+
+ case IP_END:
+ case IP_NORMAL:
+ return stmt_before_ip_normal_pos (loop, stmt);
+
+ case IP_BEFORE_USE:
+ return stmt_before_inc_pos (cand, stmt, false);
+
+ case IP_AFTER_USE:
+ return stmt_before_inc_pos (cand, stmt, true);
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
/* walk_tree callback for contains_abnormal_ssa_name_p. */
static tree
@@ -1152,11 +1220,12 @@ determine_base_object (struct ivopts_data *data, tree expr)
}
/* Allocates an induction variable with given initial value BASE and step STEP
- for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. */
+ for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. AFFINE_P
+ implies the STEP and BASE are both loop invariant. */
static struct iv *
alloc_iv (struct ivopts_data *data, tree base, tree step,
- bool no_overflow = false)
+ bool no_overflow, bool affine_p)
{
tree expr = base;
struct iv *iv = (struct iv*) obstack_alloc (&data->iv_obstack,
@@ -1189,23 +1258,25 @@ alloc_iv (struct ivopts_data *data, tree base, tree step,
no_overflow = true;
iv->no_overflow = no_overflow;
iv->have_address_use = false;
+ iv->affine_p = affine_p;
return iv;
}
/* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
- doesn't overflow. */
+ doesn't overflow. AFFINE_P implies both the STEP and BASE are loop
+ invariant. */
static void
set_iv (struct ivopts_data *data, tree iv, tree base, tree step,
- bool no_overflow)
+ bool no_overflow, bool affine_p)
{
struct version_info *info = name_info (data, iv);
gcc_assert (!info->iv);
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
- info->iv = alloc_iv (data, base, step, no_overflow);
+ info->iv = alloc_iv (data, base, step, no_overflow, affine_p);
info->iv->ssa_name = iv;
}
@@ -1230,7 +1301,7 @@ get_iv (struct ivopts_data *data, tree var)
{
if (POINTER_TYPE_P (type))
type = sizetype;
- set_iv (data, var, var, build_int_cst (type, 0), true);
+ set_iv (data, var, var, build_int_cst (type, 0), true, true);
}
}
@@ -1264,58 +1335,146 @@ extract_single_var_from_expr (tree expr)
return (TREE_CODE (expr) == SSA_NAME) ? expr : NULL;
}
+/* Attempts to find a loop variant induction variable from that makes up PHI.
+ Returns true if a value is found successfully and the evolution of the
+ variant IV is returned as a chrec in EVOLUTION. */
+
+static bool
+find_loop_variant_biv (struct ivopts_data *data, gphi *phi, tree *evolution)
+{
+ /* Fallback for possibly loop variant steps. */
+ int i, n = gimple_phi_num_args (phi);
+ class loop *loop = data->current_loop;
+ tree init_cond = analyze_initial_condition (phi);
+ *evolution = chrec_not_analyzed_yet;
+
+ for (i = 0; i < n; i++)
+ {
+ tree arg = PHI_ARG_DEF (phi, i);
+ tree ev_fn = chrec_dont_know;
+
+ /* Select the edges that enter the loop body. */
+ basic_block bb = gimple_phi_arg_edge (phi, i)->src;
+ if (!flow_bb_inside_loop_p (loop, bb))
+ continue;
+
+ scev_dfs dfs (loop, phi, init_cond);
+ if (!dfs.get_ev (&ev_fn, arg))
+ return false;
+
+ /* Do not deal with converts, as we cannot work out safety bounds.
+ */
+ if (CONVERT_EXPR_P (ev_fn))
+ return false;
+
+ /* If evolution is not a chrec, then we dont know what to do. */
+ if (!tree_is_chrec (ev_fn))
+ return false;
+
+ /* If the evolution is a polynomial of degree >2 then we cant
+ handle it. */
+ if (TREE_OPERAND_LENGTH (ev_fn) > 2)
+ return false;
+
+ if (!chrec_contains_symbols_defined_in_loop (ev_fn, loop->num))
+ return false;
+
+ tree step = CHREC_RIGHT (ev_fn);
+ tree base = CHREC_LEFT (ev_fn);
+
+ bool multiple = false;
+ tree step_variant
+ = chrec_get_symbol_defined_in_loop (step, loop->num, &multiple);
+ if (multiple)
+ return false;
+ if (!step_variant)
+ return false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "step variant: ");
+ print_generic_expr (dump_file, (tree) step_variant, TDF_SLIM);
+ fputc ('\n', dump_file);
+ }
+
+ tree base_variant
+ = chrec_get_symbol_defined_in_loop (base, loop->num, &multiple);
+ if (multiple)
+ return false;
+ gcc_assert (!base_variant);
+ *evolution = chrec_merge (*evolution, ev_fn);
+ }
+ return true;
+}
+
/* Finds basic ivs. */
static bool
find_bivs (struct ivopts_data *data)
{
gphi *phi;
- affine_iv iv;
tree step, type, base, stop;
+ bool no_overflow;
bool found = false;
class loop *loop = data->current_loop;
gphi_iterator psi;
+ bool affine_p;
for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
phi = psi.phi ();
-
+ affine_iv iv;
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
continue;
if (virtual_operand_p (PHI_RESULT (phi)))
continue;
- if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
- continue;
-
- if (integer_zerop (iv.step))
+ type = TREE_TYPE (PHI_RESULT (phi));
+ if (!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type))
continue;
+ if (simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
+ {
+ step = iv.step;
+ base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+ /* Stop expanding iv base at the first ssa var referred by iv step.
+ Ideally we should stop at any ssa var, because that's expensive
+ and unusual to happen, we just do it on the first one.
+
+ See PR64705 for the rationale. */
+ stop = extract_single_var_from_expr (step);
+ base = expand_simple_operations (base, stop);
+ if (contains_abnormal_ssa_name_p (base)
+ || contains_abnormal_ssa_name_p (step))
+ continue;
- step = iv.step;
- base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
- /* Stop expanding iv base at the first ssa var referred by iv step.
- Ideally we should stop at any ssa var, because that's expensive
- and unusual to happen, we just do it on the first one.
-
- See PR64705 for the rationale. */
- stop = extract_single_var_from_expr (step);
- base = expand_simple_operations (base, stop);
- if (contains_abnormal_ssa_name_p (base)
- || contains_abnormal_ssa_name_p (step))
- continue;
+ if (integer_zerop (iv.step))
+ continue;
- type = TREE_TYPE (PHI_RESULT (phi));
- base = fold_convert (type, base);
- if (step)
+ affine_p = true;
+ no_overflow = iv.no_overflow;
+ }
+ else
{
- if (POINTER_TYPE_P (type))
- step = convert_to_ptrofftype (step);
- else
- step = fold_convert (type, step);
+ tree evolution;
+ if (!find_loop_variant_biv (data, phi, &evolution))
+ continue;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "found variant increment IV: ");
+ print_generic_expr (dump_file, evolution, TDF_SLIM);
+ fputc ('\n', dump_file);
+ }
+
+ step = CHREC_RIGHT (evolution);
+ base = CHREC_LEFT (evolution);
+
+ no_overflow = false;
+ affine_p = false;
}
- set_iv (data, PHI_RESULT (phi), base, step, iv.no_overflow);
+ set_iv (data, PHI_RESULT (phi), base, step, no_overflow, affine_p);
found = true;
}
@@ -1372,16 +1531,16 @@ mark_bivs (struct ivopts_data *data)
}
/* Checks whether STMT defines a linear induction variable and stores its
- parameters to IV. */
+ parameters to BASE, STEP, NO_OVERFLOW, and AFFINE_P. */
static bool
-find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
+find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, tree *base,
+ tree *step, bool *no_overflow, bool *affine_p)
{
tree lhs, stop;
class loop *loop = data->current_loop;
- iv->base = NULL_TREE;
- iv->step = NULL_TREE;
+ affine_iv iv = {};
if (gimple_code (stmt) != GIMPLE_ASSIGN)
return false;
@@ -1390,7 +1549,7 @@ find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, &iv, true))
return false;
/* Stop expanding iv base at the first ssa var referred by iv step.
@@ -1398,10 +1557,10 @@ find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
and unusual to happen, we just do it on the first one.
See PR64705 for the rationale. */
- stop = extract_single_var_from_expr (iv->step);
- iv->base = expand_simple_operations (iv->base, stop);
- if (contains_abnormal_ssa_name_p (iv->base)
- || contains_abnormal_ssa_name_p (iv->step))
+ stop = extract_single_var_from_expr (iv.step);
+ iv.base = expand_simple_operations (iv.base, stop);
+ if (contains_abnormal_ssa_name_p (iv.base)
+ || contains_abnormal_ssa_name_p (iv.step))
return false;
/* If STMT could throw, then do not consider STMT as defining a GIV.
@@ -1410,6 +1569,126 @@ find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
if (stmt_could_throw_p (cfun, stmt))
return false;
+ *base = iv.base;
+ *step = iv.step;
+ *no_overflow = iv.no_overflow;
+ *affine_p = true;
+
+ return true;
+}
+
+/* If we can prove that TOP = cst * BOT for some constant cst,
+ store cst to MUL and return true. Otherwise return false.
+ The returned value is always sign-extended, regardless of the
+ signedness of TOP and BOT. */
+
+static bool
+constant_multiple_of (tree top, tree bot, widest_int *mul,
+ struct ivopts_data *data)
+{
+ aff_tree aff_top, aff_bot;
+ tree_to_aff_combination_expand (top, TREE_TYPE (top), &aff_top,
+ &data->name_expansion_cache);
+ tree_to_aff_combination_expand (bot, TREE_TYPE (bot), &aff_bot,
+ &data->name_expansion_cache);
+
+ poly_widest_int poly_mul;
+ if (aff_combination_constant_multiple_p (&aff_top, &aff_bot, &poly_mul)
+ && poly_mul.is_constant (mul))
+ return true;
+
+ return false;
+}
+
+/* Attempts to find a loop variant general induction variable in stmt.
+ Returns true if a value is found successfully, and returns the relevant
+ values in BASE, STEP, NO_OVERFLOW, and AFFINE_P. */
+
+static bool
+find_loop_variant_givs_in_stmt (struct ivopts_data *data, gimple *stmt,
+ tree *base, tree *step, bool *no_overflow,
+ bool *affine_p)
+{
+ /* Fallback for possibly loop variant steps. */
+
+ class loop *loop = data->current_loop;
+ tree ev_fn = chrec_dont_know;
+
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ tree lhs = gimple_assign_lhs (stmt);
+ if (TREE_CODE (lhs) != SSA_NAME)
+ return false;
+
+ scev_dfs dfs (loop, NULL, NULL);
+ if (dfs.get_ev (&ev_fn, lhs, stmt) != t_true)
+ return false;
+
+ /* Do not deal with converts, as we cannot work out safety bounds. */
+ if (CONVERT_EXPR_P (ev_fn))
+ return false;
+
+ /* If evolution is not a chrec, then we dont know what to do. */
+ if (!tree_is_chrec (ev_fn))
+ return false;
+
+ /* If the evolution is a polynomial of degree >2 then we can't handle it. */
+ if (TREE_OPERAND_LENGTH (ev_fn) > 2)
+ return false;
+
+ if (!chrec_contains_symbols_defined_in_loop (ev_fn, loop->num))
+ return false;
+
+ if (stmt_could_throw_p (cfun, stmt))
+ return false;
+
+ *step = CHREC_RIGHT (ev_fn);
+ *base = CHREC_LEFT (ev_fn);
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (*step)))
+ return false;
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (*base))
+ && !POINTER_TYPE_P (TREE_TYPE (*base)))
+ return false;
+
+ *no_overflow = false;
+ *affine_p = false;
+
+ /* We need to check that the base (LHS) is some multiple of the step (RHS)
+ plus a constant. */
+ bool multiple = false;
+ tree step_variant
+ = chrec_get_symbol_defined_in_loop (*step, loop->num, &multiple);
+ if (multiple)
+ return false;
+ if (!step_variant)
+ return false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "step variant: ");
+ print_generic_expr (dump_file, (tree) step_variant, TDF_SLIM);
+ fputc ('\n', dump_file);
+ }
+
+ tree base_variant
+ = chrec_get_symbol_defined_in_loop (*base, loop->num, &multiple);
+ if (multiple)
+ return false;
+
+ /* Base and step have different loop variants. That will not work. */
+ if (!base_variant)
+ return true;
+
+ /* Require the step variant to be a multiple of the base variant, or vice
+ versa. */
+ widest_int mul1;
+ widest_int mul2;
+ if (!constant_multiple_of (base_variant, step_variant, &mul1, data)
+ && !constant_multiple_of (step_variant, base_variant, &mul2, data))
+ return false;
+
return true;
}
@@ -1418,12 +1697,17 @@ find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
static void
find_givs_in_stmt (struct ivopts_data *data, gimple *stmt)
{
- affine_iv iv;
+ tree base, step;
+ bool no_overflow, affine_p;
- if (!find_givs_in_stmt_scev (data, stmt, &iv))
+ if (!find_givs_in_stmt_scev (data, stmt, &base, &step, &no_overflow,
+ &affine_p)
+ && !find_loop_variant_givs_in_stmt (data, stmt, &base, &step,
+ &no_overflow, &affine_p))
return;
- set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step, iv.no_overflow);
+ set_iv (data, gimple_assign_lhs (stmt), base, step, no_overflow,
+ affine_p);
}
/* Finds general ivs in basic block BB. */
@@ -2003,6 +2287,7 @@ struct ifs_ivopts_data
struct ivopts_data *ivopts_data;
gimple *stmt;
tree step;
+ bool affine_p;
};
static bool
@@ -2083,6 +2368,7 @@ idx_find_step (tree base, tree *idx, void *data)
step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step);
+ dta->affine_p = iv->affine_p && dta->affine_p;
if (dta->ivopts_data->bivs_not_used_in_addr)
{
@@ -2113,29 +2399,6 @@ idx_record_use (tree base, tree *idx,
return true;
}
-/* If we can prove that TOP = cst * BOT for some constant cst,
- store cst to MUL and return true. Otherwise return false.
- The returned value is always sign-extended, regardless of the
- signedness of TOP and BOT. */
-
-static bool
-constant_multiple_of (tree top, tree bot, widest_int *mul,
- struct ivopts_data *data)
-{
- aff_tree aff_top, aff_bot;
- tree_to_aff_combination_expand (top, TREE_TYPE (top), &aff_top,
- &data->name_expansion_cache);
- tree_to_aff_combination_expand (bot, TREE_TYPE (bot), &aff_bot,
- &data->name_expansion_cache);
-
- poly_widest_int poly_mul;
- if (aff_combination_constant_multiple_p (&aff_top, &aff_bot, &poly_mul)
- && poly_mul.is_constant (mul))
- return true;
-
- return false;
-}
-
/* Return true if memory reference REF with step STEP may be unaligned. */
static bool
@@ -2232,6 +2495,7 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
tree base = *op_p, step = size_zero_node;
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;
+ bool affine_p = true;
/* Do not play with volatile memory references. A bit too conservative,
perhaps, but safe. */
@@ -2259,6 +2523,7 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
TMR_BASE (base) = civ->base;
step = civ->step;
+ affine_p = civ->affine_p;
}
if (TMR_INDEX2 (base)
&& TREE_CODE (TMR_INDEX2 (base)) == SSA_NAME)
@@ -2269,6 +2534,7 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
TMR_INDEX2 (base) = civ->base;
step = civ->step;
+ affine_p = civ->affine_p;
}
if (TMR_INDEX (base)
&& TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
@@ -2286,6 +2552,7 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
step = fold_build2 (PLUS_EXPR, type, step, astep);
+ affine_p = civ->affine_p;
}
}
@@ -2298,10 +2565,12 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
ifs_ivopts_data.ivopts_data = data;
ifs_ivopts_data.stmt = stmt;
ifs_ivopts_data.step = size_zero_node;
+ ifs_ivopts_data.affine_p = true;;
if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
|| integer_zerop (ifs_ivopts_data.step))
goto fail;
step = ifs_ivopts_data.step;
+ affine_p = ifs_ivopts_data.affine_p;
/* Check that the base expression is addressable. This needs
to be done after substituting bases of IVs into it. */
@@ -2333,7 +2602,7 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
}
}
- civ = alloc_iv (data, base, step);
+ civ = alloc_iv (data, base, step, false, affine_p);
/* Fail if base object of this memory reference is unknown. */
if (civ->base_object == NULL_TREE)
goto fail;
@@ -2417,7 +2686,7 @@ find_address_like_use (struct ivopts_data *data, gimple *stmt, tree *op_p,
mem_type = get_mem_type_for_internal_fn (call, op_p);
if (mem_type)
{
- iv = alloc_iv (data, iv->base, iv->step);
+ iv = alloc_iv (data, iv->base, iv->step, false, iv->affine_p);
record_group_use (data, op_p, iv, stmt, USE_PTR_ADDRESS, mem_type);
return true;
}
@@ -2971,7 +3240,7 @@ find_inv_vars_cb (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
tree steptype = TREE_TYPE (op);
if (POINTER_TYPE_P (steptype))
steptype = sizetype;
- set_iv (idata, op, op, build_int_cst (steptype, 0), true);
+ set_iv (idata, op, op, build_int_cst (steptype, 0), true, true);
record_invariant (idata, op, false);
}
}
@@ -3067,8 +3336,8 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_)
static struct iv_cand *
add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
enum iv_position pos, struct iv_use *use,
- gimple *incremented_at, struct iv *orig_iv = NULL,
- bool doloop = false)
+ gimple *incremented_at, struct iv *orig_iv,
+ bool doloop, bool affine_p)
{
unsigned i;
struct iv_cand *cand = NULL;
@@ -3134,7 +3403,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
{
cand = XCNEW (struct iv_cand);
cand->id = i;
- cand->iv = alloc_iv (data, base, step);
+ cand->iv = alloc_iv (data, base, step, false, affine_p);
cand->pos = pos;
if (pos != IP_ORIGINAL)
{
@@ -3154,7 +3423,9 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
{
find_inv_vars (data, &step, &cand->inv_vars);
- iv_inv_expr_ent *inv_expr = get_loop_invariant_expr (data, step);
+ iv_inv_expr_ent *inv_expr = NULL;
+ if (affine_p)
+ inv_expr = get_loop_invariant_expr (data, step);
/* Share bitmap between inv_vars and inv_exprs for cand. */
if (inv_expr != NULL)
{
@@ -3221,7 +3492,7 @@ allow_ip_end_pos_p (class loop *loop)
static void
add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
- bool important, struct iv_use *use)
+ bool important, struct iv_use *use, bool affine_p)
{
basic_block use_bb = gimple_bb (use->stmt);
machine_mode mem_mode;
@@ -3260,7 +3531,7 @@ add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
new_step = fold_convert (TREE_TYPE (base), new_step);
new_base = fold_build2 (code, TREE_TYPE (base), base, new_step);
add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
- use->stmt);
+ use->stmt, NULL, false, affine_p);
}
if (((USE_LOAD_POST_INCREMENT (mem_mode)
|| USE_STORE_POST_INCREMENT (mem_mode))
@@ -3270,7 +3541,7 @@ add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
&& known_eq (GET_MODE_SIZE (mem_mode), -cstepi)))
{
add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
- use->stmt);
+ use->stmt, NULL, false, affine_p);
}
}
@@ -3281,17 +3552,18 @@ add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
static void
add_candidate (struct ivopts_data *data, tree base, tree step, bool important,
- struct iv_use *use, struct iv *orig_iv = NULL,
- bool doloop = false)
+ struct iv_use *use, struct iv *orig_iv,
+ bool doloop, bool affine_p)
{
if (ip_normal_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL, orig_iv,
- doloop);
+ doloop, affine_p);
/* Exclude doloop candidate here since it requires decrement then comparison
and jump, the IP_END position doesn't match. */
if (!doloop && ip_end_pos (data->current_loop)
&& allow_ip_end_pos_p (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_END, use, NULL, orig_iv);
+ add_candidate_1 (data, base, step, important, IP_END, use, NULL, orig_iv,
+ false, affine_p);
}
/* Adds standard iv candidates. */
@@ -3299,24 +3571,26 @@ add_candidate (struct ivopts_data *data, tree base, tree step, bool important,
static void
add_standard_iv_candidates (struct ivopts_data *data)
{
- add_candidate (data, integer_zero_node, integer_one_node, true, NULL);
+ add_candidate (data, integer_zero_node, integer_one_node, true, NULL, NULL,
+ false, true);
/* The same for a double-integer type if it is still fast enough. */
if (TYPE_PRECISION
(long_integer_type_node) > TYPE_PRECISION (integer_type_node)
&& TYPE_PRECISION (long_integer_type_node) <= BITS_PER_WORD)
add_candidate (data, build_int_cst (long_integer_type_node, 0),
- build_int_cst (long_integer_type_node, 1), true, NULL);
+ build_int_cst (long_integer_type_node, 1), true, NULL, NULL,
+ false, true);
/* The same for a double-integer type if it is still fast enough. */
if (TYPE_PRECISION
(long_long_integer_type_node) > TYPE_PRECISION (long_integer_type_node)
&& TYPE_PRECISION (long_long_integer_type_node) <= BITS_PER_WORD)
add_candidate (data, build_int_cst (long_long_integer_type_node, 0),
- build_int_cst (long_long_integer_type_node, 1), true, NULL);
+ build_int_cst (long_long_integer_type_node, 1), true, NULL,
+ NULL, false, true);
}
-
/* Adds candidates bases on the old induction variable IV. */
static void
@@ -3335,20 +3609,23 @@ add_iv_candidate_for_biv (struct ivopts_data *data, struct iv *iv)
tree step = fold_convert (sizetype, iv->step);
/* Add iv cand of same precision as index part in TARGET_MEM_REF. */
- add_candidate (data, base, step, true, NULL, iv);
+ add_candidate (data, base, step, true, NULL, iv, false, iv->affine_p);
/* Add iv cand of the original type only if it has nonlinear use. */
if (iv->nonlin_use)
- add_candidate (data, iv->base, iv->step, true, NULL);
+ add_candidate (data, iv->base, iv->step, true, NULL, NULL, false,
+ iv->affine_p);
}
else
- add_candidate (data, iv->base, iv->step, true, NULL);
+ add_candidate (data, iv->base, iv->step, true, NULL, NULL, false,
+ iv->affine_p);
/* The same, but with initial value zero. */
if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
- add_candidate (data, size_int (0), iv->step, true, NULL);
+ add_candidate (data, size_int (0), iv->step, true, NULL, NULL, false,
+ iv->affine_p);
else
add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
- iv->step, true, NULL);
+ iv->step, true, NULL, NULL, false, iv->affine_p);
phi = SSA_NAME_DEF_STMT (iv->ssa_name);
if (gimple_code (phi) == GIMPLE_PHI)
@@ -3363,7 +3640,8 @@ add_iv_candidate_for_biv (struct ivopts_data *data, struct iv *iv)
{
cand = add_candidate_1 (data,
iv->base, iv->step, true, IP_ORIGINAL, NULL,
- SSA_NAME_DEF_STMT (def));
+ SSA_NAME_DEF_STMT (def), NULL, false,
+ iv->affine_p);
if (cand)
{
cand->var_before = iv->ssa_name;
@@ -3396,7 +3674,7 @@ add_iv_candidate_for_bivs (struct ivopts_data *data)
static void
record_common_cand (struct ivopts_data *data, tree base,
- tree step, struct iv_use *use)
+ tree step, struct iv_use *use, bool affine_p)
{
class iv_common_cand ent;
class iv_common_cand **slot;
@@ -3414,6 +3692,7 @@ record_common_cand (struct ivopts_data *data, tree base,
(*slot)->step = step;
(*slot)->uses.create (8);
(*slot)->hash = ent.hash;
+ (*slot)->affine_p = affine_p;
data->iv_common_cands.safe_push ((*slot));
}
@@ -3458,13 +3737,14 @@ add_iv_candidate_derived_from_uses (struct ivopts_data *data)
cand_1 = NULL;
cand_2 = NULL;
if (ip_normal_pos (data->current_loop))
- cand_1 = add_candidate_1 (data, ptr->base, ptr->step,
- false, IP_NORMAL, NULL, NULL);
+ cand_1 = add_candidate_1 (data, ptr->base, ptr->step, false, IP_NORMAL,
+ NULL, NULL, NULL, false, ptr->affine_p);
if (ip_end_pos (data->current_loop)
&& allow_ip_end_pos_p (data->current_loop))
cand_2 = add_candidate_1 (data, ptr->base, ptr->step,
- false, IP_END, NULL, NULL);
+ false, IP_END, NULL, NULL, NULL, false,
+ ptr->affine_p);
/* Bind deriving uses and the new candidates. */
for (j = 0; j < ptr->uses.length (); j++)
@@ -3501,20 +3781,23 @@ add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
basetype = lang_hooks.types.type_for_mode (TYPE_MODE (basetype),
TYPE_UNSIGNED (basetype));
add_candidate (data, fold_convert (basetype, iv->base),
- fold_convert (basetype, iv->step), false, NULL);
+ fold_convert (basetype, iv->step), false, NULL, NULL,
+ false, iv->affine_p);
return;
}
- add_candidate (data, iv->base, iv->step, false, use);
+ add_candidate (data, iv->base, iv->step, false, use, NULL, false,
+ iv->affine_p);
/* Record common candidate for use in case it can be shared by others. */
- record_common_cand (data, iv->base, iv->step, use);
+ record_common_cand (data, iv->base, iv->step, use, iv->affine_p);
/* Record common candidate with initial value zero. */
basetype = TREE_TYPE (iv->base);
if (POINTER_TYPE_P (basetype))
basetype = sizetype;
- record_common_cand (data, build_int_cst (basetype, 0), iv->step, use);
+ record_common_cand (data, build_int_cst (basetype, 0), iv->step, use,
+ iv->affine_p);
/* Compare the cost of an address with an unscaled index with the cost of
an address with a scaled index and add candidate if useful. */
@@ -3533,7 +3816,7 @@ add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
&& multiple_p (step, fact, &new_step))
add_candidate (data, size_int (0),
wide_int_to_tree (sizetype, new_step),
- true, NULL);
+ true, NULL, NULL, false, iv->affine_p);
}
/* Record common candidate with constant offset stripped in base.
@@ -3541,8 +3824,9 @@ add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
base = strip_offset (iv->base, &offset);
if (maybe_ne (offset, 0U) || base != iv->base)
{
- record_common_cand (data, base, iv->step, use);
- add_candidate (data, base, iv->step, false, use);
+ record_common_cand (data, base, iv->step, use, iv->affine_p);
+ add_candidate (data, base, iv->step, false, use, NULL, false,
+ iv->affine_p);
}
/* Record common candidate with base_object removed in base. */
@@ -3555,19 +3839,19 @@ add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
STRIP_NOPS (step);
base = TREE_OPERAND (base, 1);
step = fold_convert (sizetype, step);
- record_common_cand (data, base, step, use);
+ record_common_cand (data, base, step, use, iv->affine_p);
/* Also record common candidate with offset stripped. */
tree alt_base, alt_offset;
split_constant_offset (base, &alt_base, &alt_offset);
if (!integer_zerop (alt_offset))
- record_common_cand (data, alt_base, step, use);
+ record_common_cand (data, alt_base, step, use, iv->affine_p);
}
/* At last, add auto-incremental candidates. Make such variables
important since other iv uses with same base object may be based
on it. */
if (use != NULL && address_p (use->type))
- add_autoinc_candidates (data, iv->base, iv->step, true, use);
+ add_autoinc_candidates (data, iv->base, iv->step, true, use, iv->affine_p);
}
/* Adds candidates based on the uses. */
@@ -4764,7 +5048,7 @@ get_address_cost (struct ivopts_data *data, struct iv_use *use,
simple_inv = (aff_inv == NULL
|| aff_combination_const_p (aff_inv)
|| aff_combination_singleton_var_p (aff_inv));
- if (!aff_combination_zero_p (aff_inv))
+ if (!aff_combination_zero_p (aff_inv) && cand->iv->affine_p)
comp_inv = aff_combination_to_tree (aff_inv);
if (comp_inv != NULL_TREE)
cost = force_var_cost (data, comp_inv, inv_vars);
@@ -4873,6 +5157,10 @@ get_computation_cost (struct ivopts_data *data, struct iv_use *use,
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
return infinite_cost;
+ /* You cannot compute an affine iv from a non-affine iv. */
+ if (use->iv->affine_p != cand->iv->affine_p)
+ return infinite_cost;
+
if (address_p
|| (use->iv->base_object
&& cand->iv->base_object
@@ -5919,7 +6207,8 @@ add_iv_candidate_for_doloop (struct ivopts_data *data)
base = fold_convert (ntype, base);
}
- add_candidate (data, base, build_int_cst (ntype, -1), true, NULL, NULL, true);
+ add_candidate (data, base, build_int_cst (ntype, -1), true, NULL, NULL, true,
+ true);
}
/* Finds the candidates for the induction variables. */
@@ -6103,6 +6392,50 @@ determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
gcc_assert (cand->iv != NULL);
+ /* If the candidate has a loop variant step, then we need to check we can
+ safely create this iv group with this candidate. */
+ if (!cand->iv->affine_p)
+ {
+ bool multiple = false;
+ tree step_variant_ssa_node
+ = chrec_get_symbol_defined_in_loop (cand->iv->step,
+ data->current_loop->num, &multiple);
+ tree base_variant_ssa_node
+ = chrec_get_symbol_defined_in_loop (cand->iv->base,
+ data->current_loop->num, &multiple);
+
+ gcc_assert (!multiple && step_variant_ssa_node);
+
+ /* If this IV cand has:
+ - a base with a loop variant node
+ - the increment before the variant step definition
+ - another iv as its increment
+ Then it's not possible. */
+ if (base_variant_ssa_node
+ || !stmt_before_increment (cand,
+ SSA_NAME_DEF_STMT (step_variant_ssa_node),
+ data->current_loop)
+ || get_iv (data, step_variant_ssa_node))
+ {
+ /* Cannot use this candidate as the increment comes before it is
+ the calculation of the step. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Cannot use cand: ");
+ dump_cand (dump_file, cand);
+ fprintf (dump_file, " as step variant does not dominate "
+ "increment or base is variant\n");
+ }
+
+ /* TODO: we could check if it's possible to move the step calculation
+ earlier. */
+
+ cand->cost = INFTY;
+ cand->cost_step = INFTY;
+ return;
+ }
+ }
+
/* There are two costs associated with the candidate -- its increment
and its initialization. The second is almost negligible for any loop
that rolls enough, so we take it just very little into account. */
@@ -7362,21 +7695,35 @@ create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
base = unshare_expr (cand->iv->base);
- /* The step computation could invoke UB when the loop does not iterate.
- Avoid inserting it on the preheader in its native form but rewrite
- it to a well-defined form. This also helps masking SCEV issues
- which freely re-associates the IV computations when building up
- CHRECs without much regard for signed overflow invoking UB. */
- gimple_seq stmts = NULL;
- tree step = force_gimple_operand (unshare_expr (cand->iv->step), &stmts,
- true, NULL_TREE);
- if (stmts)
+ tree step;
+ if (cand->iv->affine_p)
+ {
+ /* The step computation could invoke UB when the loop does not iterate.
+ Avoid inserting it on the preheader in its native form but rewrite
+ it to a well-defined form. This also helps masking SCEV issues
+ which freely re-associates the IV computations when building up
+ CHRECs without much regard for signed overflow invoking UB. */
+ gimple_seq stmts = NULL;
+ step = force_gimple_operand (unshare_expr (cand->iv->step), &stmts,
+ true, NULL_TREE);
+ if (stmts)
+ {
+ for (auto gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
+ rewrite_to_defined_unconditional (&gsi);
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (
+ data->current_loop),
+ stmts);
+ }
+ }
+
+ else
{
- for (auto gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
- if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
- rewrite_to_defined_unconditional (&gsi);
- gsi_insert_seq_on_edge_immediate
- (loop_preheader_edge (data->current_loop), stmts);
+ /* If the step is loop variant, then we must calculate this within the
+ loop. TODO: Cost this. */
+ step = unshare_expr (cand->iv->step);
+ step = force_gimple_operand_gsi (&incr_pos, step, true, NULL_TREE, true,
+ GSI_SAME_STMT);
}
create_iv (base, PLUS_EXPR, step,
@@ -7462,6 +7809,10 @@ rewrite_use_nonlinear_expr (struct ivopts_data *data,
{
if (expr_invariant_in_loop_p (data->current_loop, op))
return;
+ /* If the increment is loop_variant, check if this is the loop
+ increment. */
+ if (!use->iv->affine_p && operand_equal_p (use->iv->step, op))
+ return;
if (TREE_CODE (op) == SSA_NAME)
{
struct iv *iv = get_iv (data, op);
@@ -8322,6 +8673,8 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *data, class loop *loop,
/* Remove the ivs that are unused after rewriting. */
remove_unused_ivs (data, toremove);
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+
finish:
free (body);
free_loop_data (data);