[PATCH, ivopts] Handle type-converted IVs better
Adam Nemet
anemet@caviumnetworks.com
Fri Sep 15 16:04:00 GMT 2006
In the loop below before the store, the value is casted to int.
ivopts decides that it is simpler to formulate that use in terms of a
new induction variable {0, +, 1} instead of using the candidate
derived from data_offset.
long last_data_offset;
int store;
char *data;
f ()
{
long data_offset = last_data_offset;
char *p;
for (p = data; *p; p++)
{
data_offset++;
g (data_offset);
store = data_offset + 1;
}
}
This is because when it estimates the cost of the data_offset
candidate it works with this over-complicated expression:
(int) ((unsigned int) (data_offset_5 + 2)
- (unsigned int) data_offset_5
+ (unsigned int) data_offset_11 - 1)
Instead of trying to fold this which I am not even sure is valid in
the generic case (can we remove overflows?) I took a different
approach.
When a use of an IV is expressed using another candidate I check
whether the IV in question is a type-converted version of a different
IV. If yes then I try to express the candidate from the original IV
and type-cast the result.
With this I get the simplified expression in the above case:
(int) ((unsigned int) data_offset_11 + 1)
The rest of the patch just adds the required infrastucture so that I
can recurse in get_computation_aff with a different IV. I also needed
to keep the ssa_name for the IVs around so that I can query their
definitions later.
Tested on mipsisa64-elf and boostrapped and tested on
x86_64-unknown-linux-gnu.
Comments? OK to install?
Adam
* tree-ssa-loop-ivopts.c (record_use): Don't clear
use.iv.ssa_name.
(dump_iv_properties): New function to dump an iv without ssa_name.
Move code from dump_iv.
(dump_iv, dump_use, dump_cand): Use dump_iv_properties.
(aff_combination_convert): New function.
(get_computation_aff): Take an iv instead of a use. Take
ivopts_data instead of loop. Compute uutype earlier. If iv is
type-converted from another iv, do computation on the original iv
and then convert the result.
(get_computation_at, get_computation): Take ivopts_data instead
of the current loop. Adjust call to get_computation_aff.
(get_computation_cost_at): Adjust call to get_computation_at.
(rewrite_use_nonlinear_expr, rewrite_use_compare): Adjust call to
get_computation.
(rewrite_use_address): Adjust call to get_computation_aff.
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c (revision 116739)
--- tree-ssa-loop-ivopts.c (working copy)
*************** single_dom_exit (struct loop *loop)
*** 360,378 ****
return exit;
}
! /* Dumps information about the induction variable IV to FILE. */
! extern void dump_iv (FILE *, struct iv *);
! void
! dump_iv (FILE *file, struct iv *iv)
{
- if (iv->ssa_name)
- {
- fprintf (file, "ssa name ");
- print_generic_expr (file, iv->ssa_name, TDF_SLIM);
- fprintf (file, "\n");
- }
-
fprintf (file, " type ");
print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
fprintf (file, "\n");
--- 360,370 ----
return exit;
}
! /* Dumps the properties of induction variable IV to FILE. */
! static void
! dump_iv_properties (FILE *file, struct iv *iv)
{
fprintf (file, " type ");
print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
fprintf (file, "\n");
*************** dump_iv (FILE *file, struct iv *iv)
*** 405,410 ****
--- 397,418 ----
fprintf (file, " is a biv\n");
}
+ /* Dumps information about the induction variable IV to FILE. */
+
+ extern void dump_iv (FILE *, struct iv *);
+ void
+ dump_iv (FILE *file, struct iv *iv)
+ {
+ if (iv->ssa_name)
+ {
+ fprintf (file, "ssa name ");
+ print_generic_expr (file, iv->ssa_name, TDF_SLIM);
+ fprintf (file, "\n");
+ }
+
+ dump_iv_properties (file, iv);
+ }
+
/* Dumps information about the USE to FILE. */
extern void dump_use (FILE *, struct iv_use *);
*************** dump_use (FILE *file, struct iv_use *use
*** 440,446 ****
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
! dump_iv (file, use->iv);
if (use->related_cands)
{
--- 448,454 ----
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
! dump_iv_properties (file, use->iv);
if (use->related_cands)
{
*************** dump_cand (FILE *file, struct iv_cand *c
*** 505,511 ****
break;
}
! dump_iv (file, iv);
}
/* Returns the info for ssa version VER. */
--- 513,519 ----
break;
}
! dump_iv_properties (file, iv);
}
/* Returns the info for ssa version VER. */
*************** record_use (struct ivopts_data *data, tr
*** 1143,1152 ****
use->op_p = use_p;
use->related_cands = BITMAP_ALLOC (NULL);
- /* To avoid showing ssa name in the dumps, if it was not reset by the
- caller. */
- iv->ssa_name = NULL_TREE;
-
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
--- 1151,1156 ----
*************** aff_combination_add (struct affine_tree_
*** 2762,2767 ****
--- 2766,2793 ----
aff_combination_add_elt (comb1, comb2->rest, 1);
}
+ /* Convert COMB to TYPE. */
+
+ static void
+ aff_combination_convert (tree type, struct affine_tree_combination *comb)
+ {
+ unsigned prec = TYPE_PRECISION (type);
+ unsigned i;
+
+ comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
+ comb->offset = comb->offset & comb->mask;
+
+ /* The type of the elements can be different from comb->type only as
+ much as what STRIP_NOPS would remove. We can just directly cast
+ to TYPE. */
+ for (i = 0; i < comb->n; i++)
+ comb->elts[i] = fold_convert (type, comb->elts[i]);
+ if (comb->rest)
+ comb->rest = fold_convert (type, comb->rest);
+
+ comb->type = type;
+ }
+
/* Splits EXPR into an affine combination of parts. */
static void
*************** fold_affine_expr (tree expr)
*** 2951,2967 ****
return aff_combination_to_tree (&comb);
}
! /* Determines the expression by that USE is expressed from induction variable
! CAND at statement AT in LOOP. The expression is stored in a decomposed
! form into AFF. Returns false if USE cannot be expressed using CAND. */
static bool
! get_computation_aff (struct loop *loop,
! struct iv_use *use, struct iv_cand *cand, tree at,
struct affine_tree_combination *aff)
{
! tree ubase = use->iv->base;
! tree ustep = use->iv->step;
tree cbase = cand->iv->base;
tree cstep = cand->iv->step;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
--- 2977,2994 ----
return aff_combination_to_tree (&comb);
}
! /* Determines the expression IV from induction variable CAND at
! statement AT in LOOP. The expression is stored in a decomposed
! form into AFF. Returns false if IV cannot be expressed using
! CAND. */
static bool
! get_computation_aff (struct ivopts_data *data,
! struct iv *iv, struct iv_cand *cand, tree at,
struct affine_tree_combination *aff)
{
! tree ubase = iv->base;
! tree ustep = iv->step;
tree cbase = cand->iv->base;
tree cstep = cand->iv->step;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
*************** get_computation_aff (struct loop *loop,
*** 2973,2978 ****
--- 3000,3033 ----
struct affine_tree_combination cbase_aff, expr_aff;
tree cstep_orig = cstep, ustep_orig = ustep;
double_int rat;
+ struct loop *loop = data->current_loop;
+
+ if (TYPE_UNSIGNED (utype))
+ uutype = utype;
+ else
+ uutype = unsigned_type_for (utype);
+
+ /* If IV is just a type-converted version of another induction
+ variable do the computation on that iv instead and then cast the
+ result. This way we only cast after getting a chance to simplify
+ the arithmetic below. */
+ if (iv->ssa_name)
+ {
+ tree iv_def = SSA_NAME_DEF_STMT (iv->ssa_name);
+
+ if (TREE_CODE (iv_def) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (iv_def, 1)) == CONVERT_EXPR)
+ {
+ struct iv *orig =
+ get_iv (data, TREE_OPERAND (TREE_OPERAND (iv_def, 1), 0));
+
+ if (orig && get_computation_aff (data, orig, cand, at, aff))
+ {
+ aff_combination_convert (uutype, aff);
+ return true;
+ }
+ }
+ }
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
*************** get_computation_aff (struct loop *loop,
*** 2988,2998 ****
expr = fold_convert (ctype, expr);
}
! if (TYPE_UNSIGNED (utype))
! uutype = utype;
! else
{
- uutype = unsigned_type_for (utype);
ubase = fold_convert (uutype, ubase);
ustep = fold_convert (uutype, ustep);
}
--- 3043,3050 ----
expr = fold_convert (ctype, expr);
}
! if (utype != uutype)
{
ubase = fold_convert (uutype, ubase);
ustep = fold_convert (uutype, ustep);
}
*************** get_computation_aff (struct loop *loop,
*** 3103,3115 ****
CAND at statement AT in LOOP. The computation is unshared. */
static tree
! get_computation_at (struct loop *loop,
struct iv_use *use, struct iv_cand *cand, tree at)
{
struct affine_tree_combination aff;
tree type = TREE_TYPE (use->iv->base);
! if (!get_computation_aff (loop, use, cand, at, &aff))
return NULL_TREE;
unshare_aff_combination (&aff);
return fold_convert (type, aff_combination_to_tree (&aff));
--- 3155,3167 ----
CAND at statement AT in LOOP. The computation is unshared. */
static tree
! get_computation_at (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand, tree at)
{
struct affine_tree_combination aff;
tree type = TREE_TYPE (use->iv->base);
! if (!get_computation_aff (data, use->iv, cand, at, &aff))
return NULL_TREE;
unshare_aff_combination (&aff);
return fold_convert (type, aff_combination_to_tree (&aff));
*************** get_computation_at (struct loop *loop,
*** 3119,3127 ****
CAND in LOOP. The computation is unshared. */
static tree
! get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
{
! return get_computation_at (loop, use, cand, use->stmt);
}
/* Returns cost of addition in MODE. */
--- 3171,3180 ----
CAND in LOOP. The computation is unshared. */
static tree
! get_computation (struct ivopts_data *data, struct iv_use *use,
! struct iv_cand *cand)
{
! return get_computation_at (data, use, cand, use->stmt);
}
/* Returns cost of addition in MODE. */
*************** get_computation_cost_at (struct ivopts_d
*** 3834,3840 ****
fallback:
{
/* Just get the expression, expand it and measure the cost. */
! tree comp = get_computation_at (data->current_loop, use, cand, at);
if (!comp)
return INFTY;
--- 3887,3893 ----
fallback:
{
/* Just get the expression, expand it and measure the cost. */
! tree comp = get_computation_at (data, use, cand, at);
if (!comp)
return INFTY;
*************** rewrite_use_nonlinear_expr (struct ivopt
*** 5264,5270 ****
unshare_expr (step)));
}
else
! comp = get_computation (data->current_loop, use, cand);
switch (TREE_CODE (use->stmt))
{
--- 5317,5323 ----
unshare_expr (step)));
}
else
! comp = get_computation (data, use, cand);
switch (TREE_CODE (use->stmt))
{
*************** rewrite_use_address (struct ivopts_data
*** 5434,5440 ****
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
tree ref;
! get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
unshare_aff_combination (&aff);
ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
--- 5487,5493 ----
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
tree ref;
! get_computation_aff (data, use->iv, cand, use->stmt, &aff);
unshare_aff_combination (&aff);
ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
*************** rewrite_use_compare (struct ivopts_data
*** 5476,5482 ****
/* The induction variable elimination failed; just express the original
giv. */
! comp = get_computation (data->current_loop, use, cand);
cond = *use->op_p;
op_p = &TREE_OPERAND (cond, 0);
--- 5529,5535 ----
/* The induction variable elimination failed; just express the original
giv. */
! comp = get_computation (data, use, cand);
cond = *use->op_p;
op_p = &TREE_OPERAND (cond, 0);
More information about the Gcc-patches
mailing list