This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Cleanup affine combination infrastructure of ivopts
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 14 Dec 2006 02:31:15 +0100
- Subject: [patch] Cleanup affine combination infrastructure of ivopts
Hello,
ivopts contain infrastructure to enable it manipulate and fold
affine expressions (that naturally apear during affine induction
variable optimizations). The problem is that at the moment, we
only support expressions whose coefficients fit in HOST_WIDE_INT;
which means that on several places where they are used, a special
code must be used to handle the case where we work with expressions
in wider types. This is ugly and error-prone, and makes it more
difficult to change the code (which is something I need to do e.g.
in pointer_plus branch now) or to use these utilities on other places
where they might be practical (# of iterations analysis).
This patch fixes the problem by making the coefficients double_ints.
Also, it moves the functions for manipulating affine expressions to
a separate file.
According to my measurements, the change seems to be compile-time
neutral. Bootstrapped & regtested on i686 and x86_64.
Commited.
Zdenek
* tree-ssa-loop-ivopts.c: Include tree-affine.h.
(divide): Removed.
(constant_multiple_of): Fix order of operators for division.
(aff_combination_const, aff_combination_elt, aff_combination_scale,
aff_combination_add_elt, aff_combination_add, aff_combination_convert,
tree_to_aff_combination, add_elt_to_tree, unshare_aff_combination,
aff_combination_to_tree): Moved to tree-affine.c and made to work with
double_int coefficients.
(get_computation_aff, get_computation_at): Work with double_int
coefficients.
(get_computation_cost_at): Do not use divide.
(rewrite_use_nonlinear_expr, rewrite_use_address, rewrite_use_compare):
Assert that expressing the computation did not fail.
* tree-ssa-address.c: Include tree-affine.h.
(add_to_parts, most_expensive_mult_to_index, addr_to_parts,
create_mem_ref): Work with double_int coefficients.
* tree-affine.c: New file.
* tree-affine.h: New file.
* tree-flow.h (struct affine_tree_combination): Removed.
* Makefile.in (tree-affine.o): Add.
(tree-ssa-address.o, tree-ssa-loop-ivopts.o): Add tree-affine.h
dependency.
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c (revision 119834)
--- tree-ssa-loop-ivopts.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 89,94 ****
--- 89,95 ----
#include "cfgloop.h"
#include "params.h"
#include "langhooks.h"
+ #include "tree-affine.h"
/* The infinite cost. */
#define INFTY 10000000
*************** name_info (struct ivopts_data *data, tre
*** 524,580 ****
return ver_info (data, SSA_NAME_VERSION (name));
}
- /* Checks whether there exists number X such that X * B = A, counting modulo
- 2^BITS. */
-
- static bool
- divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
- HOST_WIDE_INT *x)
- {
- unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- unsigned HOST_WIDE_INT inv, ex, val;
- unsigned i;
-
- a &= mask;
- b &= mask;
-
- /* First divide the whole equation by 2 as long as possible. */
- while (!(a & 1) && !(b & 1))
- {
- a >>= 1;
- b >>= 1;
- bits--;
- mask >>= 1;
- }
-
- if (!(b & 1))
- {
- /* If b is still even, a is odd and there is no such x. */
- return false;
- }
-
- /* Find the inverse of b. We compute it as
- b^(2^(bits - 1) - 1) (mod 2^bits). */
- inv = 1;
- ex = b;
- for (i = 0; i < bits - 1; i++)
- {
- inv = (inv * ex) & mask;
- ex = (ex * ex) & mask;
- }
-
- val = (a * inv) & mask;
-
- gcc_assert (((val * b) & mask) == a);
-
- if ((val >> (bits - 1)) & 1)
- val |= ~mask;
-
- *x = val;
-
- return true;
- }
-
/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
emitted in LOOP. */
--- 525,530 ----
*************** constant_multiple_of (tree top, tree bot
*** 2613,2620 ****
if (TREE_CODE (bot) != INTEGER_CST)
return false;
! p0 = double_int_sext (tree_to_double_int (bot), precision);
! p1 = double_int_sext (tree_to_double_int (top), precision);
if (double_int_zero_p (p1))
return false;
*mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
--- 2563,2570 ----
if (TREE_CODE (bot) != INTEGER_CST)
return false;
! p0 = double_int_sext (tree_to_double_int (top), precision);
! p1 = double_int_sext (tree_to_double_int (bot), precision);
if (double_int_zero_p (p1))
return false;
*mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
*************** constant_multiple_of (tree top, tree bot
*** 2626,2979 ****
}
}
- /* Sets COMB to CST. */
-
- static void
- aff_combination_const (struct affine_tree_combination *comb, tree type,
- unsigned HOST_WIDE_INT cst)
- {
- unsigned prec = TYPE_PRECISION (type);
-
- comb->type = type;
- comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
-
- comb->n = 0;
- comb->rest = NULL_TREE;
- comb->offset = cst & comb->mask;
- }
-
- /* Sets COMB to single element ELT. */
-
- static void
- aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
- {
- unsigned prec = TYPE_PRECISION (type);
-
- comb->type = type;
- comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
-
- comb->n = 1;
- comb->elts[0] = elt;
- comb->coefs[0] = 1;
- comb->rest = NULL_TREE;
- comb->offset = 0;
- }
-
- /* Scales COMB by SCALE. */
-
- static void
- aff_combination_scale (struct affine_tree_combination *comb,
- unsigned HOST_WIDE_INT scale)
- {
- unsigned i, j;
-
- if (scale == 1)
- return;
-
- if (scale == 0)
- {
- aff_combination_const (comb, comb->type, 0);
- return;
- }
-
- comb->offset = (scale * comb->offset) & comb->mask;
- for (i = 0, j = 0; i < comb->n; i++)
- {
- comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
- comb->elts[j] = comb->elts[i];
- if (comb->coefs[j] != 0)
- j++;
- }
- comb->n = j;
-
- if (comb->rest)
- {
- if (comb->n < MAX_AFF_ELTS)
- {
- comb->coefs[comb->n] = scale;
- comb->elts[comb->n] = comb->rest;
- comb->rest = NULL_TREE;
- comb->n++;
- }
- else
- comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
- build_int_cst_type (comb->type, scale));
- }
- }
-
- /* Adds ELT * SCALE to COMB. */
-
- static void
- aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
- unsigned HOST_WIDE_INT scale)
- {
- unsigned i;
-
- if (scale == 0)
- return;
-
- for (i = 0; i < comb->n; i++)
- if (operand_equal_p (comb->elts[i], elt, 0))
- {
- comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
- if (comb->coefs[i])
- return;
-
- comb->n--;
- comb->coefs[i] = comb->coefs[comb->n];
- comb->elts[i] = comb->elts[comb->n];
-
- if (comb->rest)
- {
- gcc_assert (comb->n == MAX_AFF_ELTS - 1);
- comb->coefs[comb->n] = 1;
- comb->elts[comb->n] = comb->rest;
- comb->rest = NULL_TREE;
- comb->n++;
- }
- return;
- }
- if (comb->n < MAX_AFF_ELTS)
- {
- comb->coefs[comb->n] = scale;
- comb->elts[comb->n] = elt;
- comb->n++;
- return;
- }
-
- if (scale == 1)
- elt = fold_convert (comb->type, elt);
- else
- elt = fold_build2 (MULT_EXPR, comb->type,
- fold_convert (comb->type, elt),
- build_int_cst_type (comb->type, scale));
-
- if (comb->rest)
- comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
- else
- comb->rest = elt;
- }
-
- /* Adds COMB2 to COMB1. */
-
- static void
- aff_combination_add (struct affine_tree_combination *comb1,
- struct affine_tree_combination *comb2)
- {
- unsigned i;
-
- comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
- for (i = 0; i < comb2->n; i++)
- aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
- if (comb2->rest)
- 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;
-
- /* If the precision of both types is the same, it suffices to change the type
- of the whole combination -- the elements are allowed to have another type
- equivalent wrto STRIP_NOPS. */
- if (prec == TYPE_PRECISION (comb->type))
- {
- comb->type = type;
- return;
- }
-
- 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
- tree_to_aff_combination (tree expr, tree type,
- struct affine_tree_combination *comb)
- {
- struct affine_tree_combination tmp;
- enum tree_code code;
- tree cst, core, toffset;
- HOST_WIDE_INT bitpos, bitsize;
- enum machine_mode mode;
- int unsignedp, volatilep;
-
- STRIP_NOPS (expr);
-
- code = TREE_CODE (expr);
- switch (code)
- {
- case INTEGER_CST:
- aff_combination_const (comb, type, int_cst_value (expr));
- return;
-
- case PLUS_EXPR:
- case MINUS_EXPR:
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
- if (code == MINUS_EXPR)
- aff_combination_scale (&tmp, -1);
- aff_combination_add (comb, &tmp);
- return;
-
- case MULT_EXPR:
- cst = TREE_OPERAND (expr, 1);
- if (TREE_CODE (cst) != INTEGER_CST)
- break;
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- aff_combination_scale (comb, int_cst_value (cst));
- return;
-
- case NEGATE_EXPR:
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- aff_combination_scale (comb, -1);
- return;
-
- case ADDR_EXPR:
- core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
- &toffset, &mode, &unsignedp, &volatilep,
- false);
- if (bitpos % BITS_PER_UNIT != 0)
- break;
- aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
- core = build_fold_addr_expr (core);
- if (TREE_CODE (core) == ADDR_EXPR)
- aff_combination_add_elt (comb, core, 1);
- else
- {
- tree_to_aff_combination (core, type, &tmp);
- aff_combination_add (comb, &tmp);
- }
- if (toffset)
- {
- tree_to_aff_combination (toffset, type, &tmp);
- aff_combination_add (comb, &tmp);
- }
- return;
-
- default:
- break;
- }
-
- aff_combination_elt (comb, type, expr);
- }
-
- /* Creates EXPR + ELT * SCALE in TYPE. MASK is the mask for width of TYPE. */
-
- static tree
- add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
- unsigned HOST_WIDE_INT mask)
- {
- enum tree_code code;
-
- scale &= mask;
- elt = fold_convert (type, elt);
-
- if (scale == 1)
- {
- if (!expr)
- return elt;
-
- return fold_build2 (PLUS_EXPR, type, expr, elt);
- }
-
- if (scale == mask)
- {
- if (!expr)
- return fold_build1 (NEGATE_EXPR, type, elt);
-
- return fold_build2 (MINUS_EXPR, type, expr, elt);
- }
-
- if (!expr)
- return fold_build2 (MULT_EXPR, type, elt,
- build_int_cst_type (type, scale));
-
- if ((scale | (mask >> 1)) == mask)
- {
- /* Scale is negative. */
- code = MINUS_EXPR;
- scale = (-scale) & mask;
- }
- else
- code = PLUS_EXPR;
-
- elt = fold_build2 (MULT_EXPR, type, elt,
- build_int_cst_type (type, scale));
- return fold_build2 (code, type, expr, elt);
- }
-
- /* Copies the tree elements of COMB to ensure that they are not shared. */
-
- static void
- unshare_aff_combination (struct affine_tree_combination *comb)
- {
- unsigned i;
-
- for (i = 0; i < comb->n; i++)
- comb->elts[i] = unshare_expr (comb->elts[i]);
- if (comb->rest)
- comb->rest = unshare_expr (comb->rest);
- }
-
- /* Makes tree from the affine combination COMB. */
-
- static tree
- aff_combination_to_tree (struct affine_tree_combination *comb)
- {
- tree type = comb->type;
- tree expr = comb->rest;
- unsigned i;
- unsigned HOST_WIDE_INT off, sgn;
-
- if (comb->n == 0 && comb->offset == 0)
- {
- if (expr)
- {
- /* Handle the special case produced by get_computation_aff when
- the type does not fit in HOST_WIDE_INT. */
- return fold_convert (type, expr);
- }
- else
- return build_int_cst (type, 0);
- }
-
- gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
-
- for (i = 0; i < comb->n; i++)
- expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
- comb->mask);
-
- if ((comb->offset | (comb->mask >> 1)) == comb->mask)
- {
- /* Offset is negative. */
- off = (-comb->offset) & comb->mask;
- sgn = comb->mask;
- }
- else
- {
- off = comb->offset;
- sgn = 1;
- }
- return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
- comb->mask);
- }
-
/* Folds EXPR using the affine expressions framework. */
static tree
--- 2576,2581 ----
*************** get_computation_aff (struct loop *loop,
*** 3039,3054 ****
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);
! tree common_type;
tree uutype;
! tree expr, delta;
! tree ratio;
! unsigned HOST_WIDE_INT ustepi, cstepi;
! HOST_WIDE_INT ratioi;
! struct affine_tree_combination cbase_aff, expr_aff;
! tree cstep_orig = cstep, ustep_orig = ustep;
double_int rat;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
--- 2641,2651 ----
tree ubase = use->iv->base;
tree ustep = use->iv->step;
tree cbase = cand->iv->base;
! tree cstep = cand->iv->step, cstep_common;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
! tree common_type, var;
tree uutype;
! aff_tree cbase_aff, var_aff;
double_int rat;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
*************** get_computation_aff (struct loop *loop,
*** 3057,3121 ****
return false;
}
! expr = var_at_stmt (loop, cand, at);
!
! if (TREE_TYPE (expr) != ctype)
! {
! /* This may happen with the original ivs. */
! 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);
! }
! if (uutype != ctype)
{
- expr = fold_convert (uutype, expr);
- cbase = fold_convert (uutype, cbase);
cstep = fold_convert (uutype, cstep);
!
! /* If the conversion is not noop, we must take it into account when
! considering the value of the step. */
! if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
! cstep_orig = cstep;
! }
!
! if (cst_and_fits_in_hwi (cstep_orig)
! && cst_and_fits_in_hwi (ustep_orig))
! {
! ustepi = int_cst_value (ustep_orig);
! cstepi = int_cst_value (cstep_orig);
!
! if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
! {
! /* TODO maybe consider case when ustep divides cstep and the ratio is
! a power of 2 (so that the division is fast to execute)? We would
! need to be much more careful with overflows etc. then. */
! return false;
! }
!
! ratio = build_int_cst_type (uutype, ratioi);
}
- else
- {
- if (!constant_multiple_of (ustep_orig, cstep_orig, &rat))
- return false;
- ratio = double_int_to_tree (uutype, rat);
! /* Ratioi is only used to detect special cases when the multiplicative
! factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may
! set it to 0. */
! if (double_int_fits_in_shwi_p (rat))
! ratioi = double_int_to_shwi (rat);
! else
! ratioi = 0;
! }
/* In case both UBASE and CBASE are shortened to UUTYPE from some common
type, we achieve better folding by computing their difference in this
--- 2654,2672 ----
return false;
}
! var = var_at_stmt (loop, cand, at);
! uutype = unsigned_type_for (utype);
! /* If the conversion is not noop, perform it. */
! if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
cstep = fold_convert (uutype, cstep);
! cbase = fold_convert (uutype, cbase);
! var = fold_convert (uutype, var);
}
! if (!constant_multiple_of (ustep, cstep, &rat))
! return false;
/* In case both UBASE and CBASE are shortened to UUTYPE from some common
type, we achieve better folding by computing their difference in this
*************** get_computation_aff (struct loop *loop,
*** 3124,3196 ****
anyway. */
common_type = determine_common_wider_type (&ubase, &cbase);
! /* We may need to shift the value if we are after the increment. */
! if (stmt_after_increment (loop, cand, at))
! {
! if (uutype != common_type)
! cstep = fold_convert (common_type, cstep);
! cbase = fold_build2 (PLUS_EXPR, common_type, cbase, cstep);
! }
!
! /* use = ubase - ratio * cbase + ratio * var.
!
! In general case ubase + ratio * (var - cbase) could be better (one less
! multiplication), but often it is possible to eliminate redundant parts
! of computations from (ubase - ratio * cbase) term, and if it does not
! happen, fold is able to apply the distributive law to obtain this form
! anyway. */
! if (TYPE_PRECISION (common_type) > HOST_BITS_PER_WIDE_INT)
{
! /* Let's compute in trees and just return the result in AFF. This case
! should not be very common, and fold itself is not that bad either,
! so making the aff. functions more complicated to handle this case
! is not that urgent. */
! if (ratioi == 1)
! {
! delta = fold_build2 (MINUS_EXPR, common_type, ubase, cbase);
! if (uutype != common_type)
! delta = fold_convert (uutype, delta);
! expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
! }
! else if (ratioi == -1)
! {
! delta = fold_build2 (PLUS_EXPR, common_type, ubase, cbase);
! if (uutype != common_type)
! delta = fold_convert (uutype, delta);
! expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
! }
else
! {
! delta = fold_build2 (MULT_EXPR, common_type, cbase, ratio);
! delta = fold_build2 (MINUS_EXPR, common_type, ubase, delta);
! if (uutype != common_type)
! delta = fold_convert (uutype, delta);
! expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
! expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
! }
! aff->type = uutype;
! aff->n = 0;
! aff->offset = 0;
! aff->mask = 0;
! aff->rest = expr;
! return true;
}
! /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
! possible to compute ratioi. */
! gcc_assert (ratioi);
!
! tree_to_aff_combination (ubase, common_type, aff);
! tree_to_aff_combination (cbase, common_type, &cbase_aff);
! tree_to_aff_combination (expr, uutype, &expr_aff);
! aff_combination_scale (&cbase_aff, -ratioi);
! aff_combination_scale (&expr_aff, ratioi);
aff_combination_add (aff, &cbase_aff);
if (common_type != uutype)
! aff_combination_convert (uutype, aff);
! aff_combination_add (aff, &expr_aff);
return true;
}
--- 2675,2706 ----
anyway. */
common_type = determine_common_wider_type (&ubase, &cbase);
! /* use = ubase - ratio * cbase + ratio * var. */
! tree_to_aff_combination (ubase, common_type, aff);
! tree_to_aff_combination (cbase, common_type, &cbase_aff);
! tree_to_aff_combination (var, uutype, &var_aff);
! /* We need to shift the value if we are after the increment. */
! if (stmt_after_increment (loop, cand, at))
{
! aff_tree cstep_aff;
!
! if (common_type != uutype)
! cstep_common = fold_convert (common_type, cstep);
else
! cstep_common = cstep;
! tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
! aff_combination_add (&cbase_aff, &cstep_aff);
}
! aff_combination_scale (&cbase_aff, double_int_neg (rat));
aff_combination_add (aff, &cbase_aff);
if (common_type != uutype)
! aff_combination_convert (aff, uutype);
!
! aff_combination_scale (&var_aff, rat);
! aff_combination_add (aff, &var_aff);
return true;
}
*************** static tree
*** 3202,3208 ****
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))
--- 2712,2718 ----
get_computation_at (struct loop *loop,
struct iv_use *use, struct iv_cand *cand, tree at)
{
! aff_tree aff;
tree type = TREE_TYPE (use->iv->base);
if (!get_computation_aff (loop, use, cand, at, &aff))
*************** get_computation_cost_at (struct ivopts_d
*** 3862,3871 ****
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
tree utype = TREE_TYPE (ubase), ctype;
! unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
HOST_WIDE_INT ratio, aratio;
bool var_present, symbol_present;
unsigned cost = 0, n_sums;
*depends_on = NULL;
--- 3372,3382 ----
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
tree utype = TREE_TYPE (ubase), ctype;
! unsigned HOST_WIDE_INT cstepi, offset = 0;
HOST_WIDE_INT ratio, aratio;
bool var_present, symbol_present;
unsigned cost = 0, n_sums;
+ double_int rat;
*depends_on = NULL;
*************** get_computation_cost_at (struct ivopts_d
*** 3913,3938 ****
else
cstepi = 0;
! if (cst_and_fits_in_hwi (ustep)
! && cst_and_fits_in_hwi (cstep))
! {
! ustepi = int_cst_value (ustep);
!
! if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
! return INFTY;
! }
! else
! {
! double_int rat;
!
! if (!constant_multiple_of (ustep, cstep, &rat))
! return INFTY;
! if (double_int_fits_in_shwi_p (rat))
! ratio = double_int_to_shwi (rat);
! else
! return INFTY;
! }
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
--- 3424,3436 ----
else
cstepi = 0;
! if (!constant_multiple_of (ustep, cstep, &rat))
! return INFTY;
! if (double_int_fits_in_shwi_p (rat))
! ratio = double_int_to_shwi (rat);
! else
! return INFTY;
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
*************** rewrite_use_nonlinear_expr (struct ivopt
*** 5427,5433 ****
unshare_expr (step)));
}
else
! comp = get_computation (data->current_loop, use, cand);
switch (TREE_CODE (use->stmt))
{
--- 4925,4934 ----
unshare_expr (step)));
}
else
! {
! comp = get_computation (data->current_loop, use, cand);
! gcc_assert (comp != NULL_TREE);
! }
switch (TREE_CODE (use->stmt))
{
*************** static void
*** 5593,5603 ****
rewrite_use_address (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
! struct affine_tree_combination aff;
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);
--- 5094,5106 ----
rewrite_use_address (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
! aff_tree aff;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
tree ref;
+ bool ok;
! ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
! gcc_assert (ok);
unshare_aff_combination (&aff);
ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
*************** rewrite_use_compare (struct ivopts_data
*** 5640,5645 ****
--- 5143,5149 ----
/* The induction variable elimination failed; just express the original
giv. */
comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
cond = *use->op_p;
op_p = &TREE_OPERAND (cond, 0);
Index: tree-ssa-address.c
===================================================================
*** tree-ssa-address.c (revision 119834)
--- tree-ssa-address.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 42,47 ****
--- 42,48 ----
#include "recog.h"
#include "expr.h"
#include "ggc.h"
+ #include "tree-affine.h"
/* TODO -- handling of symbols (according to Richard Hendersons
comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
*************** fixed_address_object_p (tree obj)
*** 346,370 ****
construct. */
static void
! add_to_parts (struct mem_address *parts, tree type, tree elt,
! unsigned HOST_WIDE_INT coef)
{
/* Check if this is a symbol. */
if (!parts->symbol
! && coef == 1
! && TREE_CODE (elt) == ADDR_EXPR
! && fixed_address_object_p (TREE_OPERAND (elt, 0)))
{
! parts->symbol = TREE_OPERAND (elt, 0);
return;
}
- if (coef != 1)
- elt = fold_build2 (MULT_EXPR, type, fold_convert (type, elt),
- build_int_cst_type (type, coef));
- else
- elt = fold_convert (type, elt);
-
if (!parts->base)
{
parts->base = elt;
--- 347,366 ----
construct. */
static void
! add_to_parts (struct mem_address *parts, tree type, tree elt)
{
+ tree elt_core = elt;
+ STRIP_NOPS (elt_core);
+
/* Check if this is a symbol. */
if (!parts->symbol
! && TREE_CODE (elt_core) == ADDR_EXPR
! && fixed_address_object_p (TREE_OPERAND (elt_core, 0)))
{
! parts->symbol = TREE_OPERAND (elt_core, 0);
return;
}
if (!parts->base)
{
parts->base = elt;
*************** add_to_parts (struct mem_address *parts,
*** 388,439 ****
static void
most_expensive_mult_to_index (struct mem_address *parts, tree type,
! struct affine_tree_combination *addr)
{
! unsigned HOST_WIDE_INT best_mult = 0;
unsigned best_mult_cost = 0, acost;
tree mult_elt = NULL_TREE, elt;
unsigned i, j;
for (i = 0; i < addr->n; i++)
{
/* FIXME: Should use the correct memory mode rather than Pmode. */
! if (addr->coefs[i] == 1
! || !multiplier_allowed_in_address_p (addr->coefs[i], Pmode))
continue;
!
! acost = multiply_by_cost (addr->coefs[i], Pmode);
if (acost > best_mult_cost)
{
best_mult_cost = acost;
! best_mult = addr->coefs[i];
}
}
! if (!best_mult)
return;
for (i = j = 0; i < addr->n; i++)
{
! if (addr->coefs[i] != best_mult)
{
- addr->coefs[j] = addr->coefs[i];
addr->elts[j] = addr->elts[i];
j++;
continue;
}
!
! elt = fold_convert (type, addr->elts[i]);
! if (!mult_elt)
mult_elt = elt;
else
! mult_elt = fold_build2 (PLUS_EXPR, type, mult_elt, elt);
}
addr->n = j;
!
parts->index = mult_elt;
! parts->step = build_int_cst_type (type, best_mult);
}
/* Splits address ADDR into PARTS.
--- 384,452 ----
static void
most_expensive_mult_to_index (struct mem_address *parts, tree type,
! aff_tree *addr)
{
! HOST_WIDE_INT coef;
! double_int best_mult, amult, amult_neg;
unsigned best_mult_cost = 0, acost;
tree mult_elt = NULL_TREE, elt;
unsigned i, j;
+ enum tree_code op_code;
+ best_mult = double_int_zero;
for (i = 0; i < addr->n; i++)
{
+ if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
+ continue;
+
/* FIXME: Should use the correct memory mode rather than Pmode. */
!
! coef = double_int_to_shwi (addr->elts[i].coef);
! if (coef == 1
! || !multiplier_allowed_in_address_p (coef, Pmode))
continue;
!
! acost = multiply_by_cost (coef, Pmode);
if (acost > best_mult_cost)
{
best_mult_cost = acost;
! best_mult = addr->elts[i].coef;
}
}
! if (!best_mult_cost)
return;
+ /* Collect elements multiplied by best_mult. */
for (i = j = 0; i < addr->n; i++)
{
! amult = addr->elts[i].coef;
! amult_neg = double_int_ext_for_comb (double_int_neg (amult), addr);
!
! if (double_int_equal_p (amult, best_mult))
! op_code = PLUS_EXPR;
! else if (double_int_equal_p (amult_neg, best_mult))
! op_code = MINUS_EXPR;
! else
{
addr->elts[j] = addr->elts[i];
j++;
continue;
}
!
! elt = fold_convert (type, addr->elts[i].val);
! if (mult_elt)
! mult_elt = fold_build2 (op_code, type, mult_elt, elt);
! else if (op_code == PLUS_EXPR)
mult_elt = elt;
else
! mult_elt = fold_build1 (NEGATE_EXPR, type, elt);
}
addr->n = j;
!
parts->index = mult_elt;
! parts->step = double_int_to_tree (type, best_mult);
}
/* Splits address ADDR into PARTS.
*************** most_expensive_mult_to_index (struct mem
*** 442,454 ****
to PARTS. Some architectures do not support anything but single
register in address, possibly with a small integer offset; while
create_mem_ref will simplify the address to an acceptable shape
! later, it would be a small bit more efficient to know that asking
! for complicated addressing modes is useless. */
static void
! addr_to_parts (struct affine_tree_combination *addr, tree type,
! struct mem_address *parts)
{
unsigned i;
parts->symbol = NULL_TREE;
--- 455,467 ----
to PARTS. Some architectures do not support anything but single
register in address, possibly with a small integer offset; while
create_mem_ref will simplify the address to an acceptable shape
! later, it would be more efficient to know that asking for complicated
! addressing modes is useless. */
static void
! addr_to_parts (aff_tree *addr, tree type, struct mem_address *parts)
{
+ tree part;
unsigned i;
parts->symbol = NULL_TREE;
*************** addr_to_parts (struct affine_tree_combin
*** 456,463 ****
parts->index = NULL_TREE;
parts->step = NULL_TREE;
! if (addr->offset)
! parts->offset = build_int_cst_type (type, addr->offset);
else
parts->offset = NULL_TREE;
--- 469,476 ----
parts->index = NULL_TREE;
parts->step = NULL_TREE;
! if (!double_int_zero_p (addr->offset))
! parts->offset = double_int_to_tree (type, addr->offset);
else
parts->offset = NULL_TREE;
*************** addr_to_parts (struct affine_tree_combin
*** 467,475 ****
/* Then try to process the remaining elements. */
for (i = 0; i < addr->n; i++)
! add_to_parts (parts, type, addr->elts[i], addr->coefs[i]);
if (addr->rest)
! add_to_parts (parts, type, addr->rest, 1);
}
/* Force the PARTS to register. */
--- 480,494 ----
/* Then try to process the remaining elements. */
for (i = 0; i < addr->n; i++)
! {
! part = fold_convert (type, addr->elts[i].val);
! if (!double_int_one_p (addr->elts[i].coef))
! part = fold_build2 (MULT_EXPR, type, part,
! double_int_to_tree (type, addr->elts[i].coef));
! add_to_parts (parts, type, part);
! }
if (addr->rest)
! add_to_parts (parts, type, addr->rest);
}
/* Force the PARTS to register. */
*************** gimplify_mem_ref_parts (block_stmt_itera
*** 490,497 ****
of created memory reference. */
tree
! create_mem_ref (block_stmt_iterator *bsi, tree type,
! struct affine_tree_combination *addr)
{
tree mem_ref, tmp;
tree addr_type = build_pointer_type (type);
--- 509,515 ----
of created memory reference. */
tree
! create_mem_ref (block_stmt_iterator *bsi, tree type, aff_tree *addr)
{
tree mem_ref, tmp;
tree addr_type = build_pointer_type (type);
Index: tree-affine.c
===================================================================
*** tree-affine.c (revision 0)
--- tree-affine.c (revision 0)
***************
*** 0 ****
--- 1,414 ----
+ /* Operations with affine combinations of trees.
+ Copyright (C) 2005 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-dump.h"
+ #include "tree-affine.h"
+
+ /* Extends CST as appropriate for the affine combinations COMB. */
+
+ double_int
+ double_int_ext_for_comb (double_int cst, aff_tree *comb)
+ {
+ return double_int_sext (cst, TYPE_PRECISION (comb->type));
+ }
+
+ /* Initializes affine combination COMB so that its value is zero in TYPE. */
+
+ static void
+ aff_combination_zero (aff_tree *comb, tree type)
+ {
+ comb->type = type;
+ comb->offset = double_int_zero;
+ comb->n = 0;
+ comb->rest = NULL_TREE;
+ }
+
+ /* Sets COMB to CST. */
+
+ void
+ aff_combination_const (aff_tree *comb, tree type, double_int cst)
+ {
+ aff_combination_zero (comb, type);
+ comb->offset = double_int_ext_for_comb (cst, comb);
+ }
+
+ /* Sets COMB to single element ELT. */
+
+ void
+ aff_combination_elt (aff_tree *comb, tree type, tree elt)
+ {
+ aff_combination_zero (comb, type);
+
+ comb->n = 1;
+ comb->elts[0].val = elt;
+ comb->elts[0].coef = double_int_one;
+ }
+
+ /* Scales COMB by SCALE. */
+
+ void
+ aff_combination_scale (aff_tree *comb, double_int scale)
+ {
+ unsigned i, j;
+
+ scale = double_int_ext_for_comb (scale, comb);
+ if (double_int_one_p (scale))
+ return;
+
+ if (double_int_zero_p (scale))
+ {
+ aff_combination_zero (comb, comb->type);
+ return;
+ }
+
+ comb->offset
+ = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
+ for (i = 0, j = 0; i < comb->n; i++)
+ {
+ double_int new_coef;
+
+ new_coef
+ = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
+ comb);
+ /* A coefficient may become zero due to overflow. Remove the zero
+ elements. */
+ if (double_int_zero_p (new_coef))
+ continue;
+ comb->elts[j].coef = new_coef;
+ comb->elts[j].val = comb->elts[i].val;
+ j++;
+ }
+ comb->n = j;
+
+ if (comb->rest)
+ {
+ if (comb->n < MAX_AFF_ELTS)
+ {
+ comb->elts[comb->n].coef = scale;
+ comb->elts[comb->n].val = comb->rest;
+ comb->rest = NULL_TREE;
+ comb->n++;
+ }
+ else
+ comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
+ double_int_to_tree (comb->type, scale));
+ }
+ }
+
+ /* Adds ELT * SCALE to COMB. */
+
+ void
+ aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
+ {
+ unsigned i;
+
+ scale = double_int_ext_for_comb (scale, comb);
+ if (double_int_zero_p (scale))
+ return;
+
+ for (i = 0; i < comb->n; i++)
+ if (operand_equal_p (comb->elts[i].val, elt, 0))
+ {
+ double_int new_coef;
+
+ new_coef = double_int_add (comb->elts[i].coef, scale);
+ new_coef = double_int_ext_for_comb (new_coef, comb);
+ if (!double_int_zero_p (new_coef))
+ {
+ comb->elts[i].coef = new_coef;
+ return;
+ }
+
+ comb->n--;
+ comb->elts[i] = comb->elts[comb->n];
+
+ if (comb->rest)
+ {
+ gcc_assert (comb->n == MAX_AFF_ELTS - 1);
+ comb->elts[comb->n].coef = double_int_one;
+ comb->elts[comb->n].val = comb->rest;
+ comb->rest = NULL_TREE;
+ comb->n++;
+ }
+ return;
+ }
+ if (comb->n < MAX_AFF_ELTS)
+ {
+ comb->elts[comb->n].coef = scale;
+ comb->elts[comb->n].val = elt;
+ comb->n++;
+ return;
+ }
+
+ if (double_int_one_p (scale))
+ elt = fold_convert (comb->type, elt);
+ else
+ elt = fold_build2 (MULT_EXPR, comb->type,
+ fold_convert (comb->type, elt),
+ double_int_to_tree (comb->type, scale));
+
+ if (comb->rest)
+ comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
+ else
+ comb->rest = elt;
+ }
+
+ /* Adds COMB2 to COMB1. */
+
+ void
+ aff_combination_add (aff_tree *comb1, aff_tree *comb2)
+ {
+ unsigned i;
+
+ comb1->offset
+ = double_int_ext_for_comb (double_int_add (comb1->offset, comb2->offset),
+ comb1);
+ for (i = 0; i < comb2->n; i++)
+ aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
+ if (comb2->rest)
+ aff_combination_add_elt (comb1, comb2->rest, double_int_one);
+ }
+
+ /* Converts affine combination COMB to TYPE. */
+
+ void
+ aff_combination_convert (aff_tree *comb, tree type)
+ {
+ unsigned i, j;
+ tree comb_type = comb->type;
+
+ gcc_assert (TYPE_PRECISION (type) <= TYPE_PRECISION (comb_type));
+ comb->type = type;
+ if (comb->rest)
+ comb->rest = fold_convert (type, comb->rest);
+
+ if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
+ return;
+
+ comb->offset = double_int_ext_for_comb (comb->offset, comb);
+ for (i = j = 0; i < comb->n; i++)
+ {
+ double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
+ if (double_int_zero_p (new_coef))
+ continue;
+ comb->elts[j].coef = new_coef;
+ comb->elts[j].val = fold_convert (type, comb->elts[i].val);
+ j++;
+ }
+
+ comb->n = j;
+ if (comb->n < MAX_AFF_ELTS && comb->rest)
+ {
+ comb->elts[comb->n].coef = double_int_one;
+ comb->elts[comb->n].val = comb->rest;
+ comb->rest = NULL_TREE;
+ comb->n++;
+ }
+ }
+
+ /* Splits EXPR into an affine combination of parts. */
+
+ void
+ tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
+ {
+ aff_tree tmp;
+ enum tree_code code;
+ tree cst, core, toffset;
+ HOST_WIDE_INT bitpos, bitsize;
+ enum machine_mode mode;
+ int unsignedp, volatilep;
+
+ STRIP_NOPS (expr);
+
+ code = TREE_CODE (expr);
+ switch (code)
+ {
+ case INTEGER_CST:
+ aff_combination_const (comb, type, tree_to_double_int (expr));
+ return;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
+ tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
+ if (code == MINUS_EXPR)
+ aff_combination_scale (&tmp, double_int_minus_one);
+ aff_combination_add (comb, &tmp);
+ return;
+
+ case MULT_EXPR:
+ cst = TREE_OPERAND (expr, 1);
+ if (TREE_CODE (cst) != INTEGER_CST)
+ break;
+ tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
+ aff_combination_scale (comb, tree_to_double_int (cst));
+ return;
+
+ case NEGATE_EXPR:
+ tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
+ aff_combination_scale (comb, double_int_minus_one);
+ return;
+
+ case ADDR_EXPR:
+ core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
+ &toffset, &mode, &unsignedp, &volatilep,
+ false);
+ if (bitpos % BITS_PER_UNIT != 0)
+ break;
+ aff_combination_const (comb, type,
+ uhwi_to_double_int (bitpos / BITS_PER_UNIT));
+ core = build_fold_addr_expr (core);
+ if (TREE_CODE (core) == ADDR_EXPR)
+ aff_combination_add_elt (comb, core, double_int_one);
+ else
+ {
+ tree_to_aff_combination (core, type, &tmp);
+ aff_combination_add (comb, &tmp);
+ }
+ if (toffset)
+ {
+ tree_to_aff_combination (toffset, type, &tmp);
+ aff_combination_add (comb, &tmp);
+ }
+ return;
+
+ default:
+ break;
+ }
+
+ aff_combination_elt (comb, type, expr);
+ }
+
+ /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
+ combination COMB. */
+
+ static tree
+ add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
+ aff_tree *comb)
+ {
+ enum tree_code code;
+
+ scale = double_int_ext_for_comb (scale, comb);
+ elt = fold_convert (type, elt);
+
+ if (double_int_one_p (scale))
+ {
+ if (!expr)
+ return elt;
+
+ return fold_build2 (PLUS_EXPR, type, expr, elt);
+ }
+
+ if (double_int_minus_one_p (scale))
+ {
+ if (!expr)
+ return fold_build1 (NEGATE_EXPR, type, elt);
+
+ return fold_build2 (MINUS_EXPR, type, expr, elt);
+ }
+
+ if (!expr)
+ return fold_build2 (MULT_EXPR, type, elt,
+ double_int_to_tree (type, scale));
+
+ if (double_int_negative_p (scale))
+ {
+ code = MINUS_EXPR;
+ scale = double_int_neg (scale);
+ }
+ else
+ code = PLUS_EXPR;
+
+ elt = fold_build2 (MULT_EXPR, type, elt,
+ double_int_to_tree (type, scale));
+ return fold_build2 (code, type, expr, elt);
+ }
+
+ /* Makes tree from the affine combination COMB. */
+
+ tree
+ aff_combination_to_tree (aff_tree *comb)
+ {
+ tree type = comb->type;
+ tree expr = comb->rest;
+ unsigned i;
+ double_int off, sgn;
+
+ gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
+
+ for (i = 0; i < comb->n; i++)
+ expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
+ comb);
+
+ /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
+ unsigned. */
+ if (double_int_negative_p (comb->offset))
+ {
+ off = double_int_neg (comb->offset);
+ sgn = double_int_minus_one;
+ }
+ else
+ {
+ off = comb->offset;
+ sgn = double_int_one;
+ }
+ return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
+ comb);
+ }
+
+ /* Copies the tree elements of COMB to ensure that they are not shared. */
+
+ void
+ unshare_aff_combination (aff_tree *comb)
+ {
+ unsigned i;
+
+ for (i = 0; i < comb->n; i++)
+ comb->elts[i].val = unshare_expr (comb->elts[i].val);
+ if (comb->rest)
+ comb->rest = unshare_expr (comb->rest);
+ }
+
+ /* Remove M-th element from COMB. */
+
+ void
+ aff_combination_remove_elt (aff_tree *comb, unsigned m)
+ {
+ comb->n--;
+ if (m <= comb->n)
+ comb->elts[m] = comb->elts[comb->n];
+ if (comb->rest)
+ {
+ comb->elts[comb->n].coef = double_int_one;
+ comb->elts[comb->n].val = comb->rest;
+ comb->rest = NULL_TREE;
+ comb->n++;
+ }
+ }
Index: tree-affine.h
===================================================================
*** tree-affine.h (revision 0)
--- tree-affine.h (revision 0)
***************
*** 0 ****
--- 1,71 ----
+ /* Operations with affine combinations of trees.
+ Copyright (C) 2005 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
+
+ /* Affine combination of trees. We keep track of at most MAX_AFF_ELTS elements
+ to make things simpler; this is sufficient in most cases. */
+
+ #define MAX_AFF_ELTS 8
+
+ /* Element of an affine combination. */
+
+ struct aff_comb_elt
+ {
+ /* The value of the element. */
+ tree val;
+
+ /* Its coefficient in the combination. */
+ double_int coef;
+ };
+
+ typedef struct affine_tree_combination
+ {
+ /* Type of the result of the combination. */
+ tree type;
+
+ /* Constant offset. */
+ double_int offset;
+
+ /* Number of elements of the combination. */
+ unsigned n;
+
+ /* Elements and their coefficients. Type of elements may be different from
+ TYPE, but their sizes must be the same (STRIP_NOPS is applied to the
+ elements).
+
+ The coefficients are always sign extened from the precision of TYPE
+ (regardless of signedness of TYPE). */
+ struct aff_comb_elt elts[MAX_AFF_ELTS];
+
+ /* Remainder of the expression. Usually NULL, used only if there are more
+ than MAX_AFF_ELTS elements. Type of REST must be TYPE. */
+ tree rest;
+ } aff_tree;
+
+ double_int double_int_ext_for_comb (double_int, aff_tree *);
+ void aff_combination_const (aff_tree *, tree, double_int);
+ void aff_combination_elt (aff_tree *, tree, tree);
+ void aff_combination_scale (aff_tree *, double_int);
+ void aff_combination_add (aff_tree *, aff_tree *);
+ void aff_combination_add_elt (aff_tree *, tree, double_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 *);
+ tree aff_combination_to_tree (aff_tree *);
+ void unshare_aff_combination (aff_tree *);
Index: tree-flow.h
===================================================================
*** tree-flow.h (revision 119834)
--- tree-flow.h (working copy)
*************** extern void remove_unused_locals (void);
*** 1002,1034 ****
/* In tree-ssa-address.c */
- /* Affine combination of trees. We keep track of at most MAX_AFF_ELTS elements
- to make things simpler; this is sufficient in most cases. */
-
- #define MAX_AFF_ELTS 8
-
- struct affine_tree_combination
- {
- /* Type of the result of the combination. */
- tree type;
-
- /* Mask modulo that the operations are performed. */
- unsigned HOST_WIDE_INT mask;
-
- /* Constant offset. */
- unsigned HOST_WIDE_INT offset;
-
- /* Number of elements of the combination. */
- unsigned n;
-
- /* Elements and their coefficients. */
- tree elts[MAX_AFF_ELTS];
- unsigned HOST_WIDE_INT coefs[MAX_AFF_ELTS];
-
- /* Remainder of the expression. */
- tree rest;
- };
-
/* Description of a memory address. */
struct mem_address
--- 1002,1007 ----
*************** struct mem_address
*** 1036,1041 ****
--- 1009,1015 ----
tree symbol, base, index, step, offset;
};
+ struct affine_tree_combination;
tree create_mem_ref (block_stmt_iterator *, tree,
struct affine_tree_combination *);
rtx addr_for_mem_ref (struct mem_address *, bool);
Index: Makefile.in
===================================================================
*** Makefile.in (revision 119834)
--- Makefile.in (working copy)
*************** OBJS-common = \
*** 988,994 ****
tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o \
tree-vect-patterns.o tree-ssa-loop-prefetch.o tree-ssa-coalesce.o \
tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-address.o \
! tree-ssa-math-opts.o \
tree-ssa-loop-ivopts.o tree-if-conv.o tree-ssa-loop-unswitch.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
--- 988,994 ----
tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o \
tree-vect-patterns.o tree-ssa-loop-prefetch.o tree-ssa-coalesce.o \
tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-address.o \
! tree-ssa-math-opts.o tree-affine.o \
tree-ssa-loop-ivopts.o tree-if-conv.o tree-ssa-loop-unswitch.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
*************** tree-ssa-address.o : tree-ssa-address.c
*** 1992,1998 ****
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \
output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(FLAGS_H) $(TREE_INLINE_H) $(RECOG_H) insn-config.h $(EXPR_H) \
! gt-tree-ssa-address.h $(GGC_H)
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
$(TREE_INLINE_H) output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
--- 1992,1998 ----
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \
output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(FLAGS_H) $(TREE_INLINE_H) $(RECOG_H) insn-config.h $(EXPR_H) \
! gt-tree-ssa-address.h $(GGC_H) tree-affine.h
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
$(TREE_INLINE_H) output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
*************** tree-ssa-loop-ivopts.o : tree-ssa-loop-i
*** 2018,2024 ****
output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(GGC_H) $(RECOG_H) insn-config.h $(HASHTAB_H) $(SCEV_H) \
$(CFGLOOP_H) $(PARAMS_H) langhooks.h $(BASIC_BLOCK_H) hard-reg-set.h \
! tree-chrec.h $(VARRAY_H)
tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
--- 2018,2027 ----
output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(GGC_H) $(RECOG_H) insn-config.h $(HASHTAB_H) $(SCEV_H) \
$(CFGLOOP_H) $(PARAMS_H) langhooks.h $(BASIC_BLOCK_H) hard-reg-set.h \
! tree-chrec.h $(VARRAY_H) tree-affine.h
! tree-affine.o : tree-affine.c tree-affine.h $(CONFIG_H) \
! $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \
! output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \