This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] affine combinations cleanup (again)
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: roger at eyesopen dot com
- Date: Mon, 6 Mar 2006 22:48:10 +0100
- Subject: [patch] affine combinations cleanup (again)
Hello,
here is the patch that makes coefficients of affine combinations
double_ints (so that we do not have to special-case situations when
coefficients do not fit into HOST_WIDE_INT), updated for the new
version of double_int.
Bootstrapped & regtested on i686 and ia64.
Zdenek
* tree-affine.c: New file.
* tree-affine.h: New file.
* double_int.c (double_int_zext, double_int_sext): Fix thinko.
* tree-ssa-loop-ivopts.c: Include tree-affine.h.
(aff_combination_const, aff_combination_elt, aff_combination_scale,
aff_combination_add_elt, aff_combination_add, tree_to_aff_combination,
add_elt_to_tree, unshare_aff_combination, aff_combination_to_tree):
Moved to tree-affine.c.
(get_computation_aff): Use double_int coefficients for aff functions.
* tree-ssa-address.c: Include tree-affine.h.
(fixed_address_object_p): Export.
(add_to_parts): Do not take coef argument.
(most_expensive_mult_to_index, addr_to_parts): Work with double_ints.
* tree-flow.h (MAX_AFF_ELTS, struct affine_tree_combination):
Moved to tree-affine.h.
* Makefile.in (tree-affine.o): Add.
(tree-ssa-loop-ivopts.o, tree-ssa-address.o): Add tree-affine.h
dependency.
Index: double-int.c
===================================================================
*** double-int.c (revision 111787)
--- double-int.c (working copy)
*************** double_int_zext (double_int cst, unsigne
*** 72,79 ****
double_int mask = double_int_mask (prec);
double_int r;
! r.low = cst.low & ~mask.low;
! r.high = cst.high & ~mask.high;
return r;
}
--- 72,79 ----
double_int mask = double_int_mask (prec);
double_int r;
! r.low = cst.low & mask.low;
! r.high = cst.high & mask.high;
return r;
}
*************** double_int_sext (double_int cst, unsigne
*** 96,108 ****
}
if (((snum >> (prec - 1)) & 1) == 1)
{
! r.low = cst.low | mask.low;
! r.high = cst.high | mask.high;
}
else
{
! r.low = cst.low & ~mask.low;
! r.high = cst.high & ~mask.high;
}
return r;
--- 96,108 ----
}
if (((snum >> (prec - 1)) & 1) == 1)
{
! r.low = cst.low | ~mask.low;
! r.high = cst.high | ~mask.high;
}
else
{
! r.low = cst.low & mask.low;
! r.high = cst.high & mask.high;
}
return r;
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c (revision 111787)
--- 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
*************** constant_multiple_of (tree type, tree to
*** 2590,2905 ****
}
}
- /* 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);
- }
-
- /* 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;
-
- /* Handle the special case produced by get_computation_aff when
- the type does not fit in HOST_WIDE_INT. */
- if (comb->n == 0 && comb->offset == 0)
- return fold_convert (type, expr);
-
- 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);
- }
-
/* 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. */
--- 2591,2596 ----
*************** get_computation_aff (struct loop *loop,
*** 3030,3040 ****
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;
}
--- 2721,2727 ----
expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
}
! tree_to_aff_combination (expr, uutype, aff);
return true;
}
*************** get_computation_aff (struct loop *loop,
*** 3045,3052 ****
tree_to_aff_combination (ubase, uutype, aff);
tree_to_aff_combination (cbase, uutype, &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);
aff_combination_add (aff, &expr_aff);
--- 2732,2739 ----
tree_to_aff_combination (ubase, uutype, aff);
tree_to_aff_combination (cbase, uutype, &cbase_aff);
tree_to_aff_combination (expr, uutype, &expr_aff);
! aff_combination_scale (&cbase_aff, shwi_to_double_int (-ratioi));
! aff_combination_scale (&expr_aff, shwi_to_double_int (ratioi));
aff_combination_add (aff, &cbase_aff);
aff_combination_add (aff, &expr_aff);
Index: tree-ssa-address.c
===================================================================
*** tree-ssa-address.c (revision 111787)
--- 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,438 ****
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++)
{
! if (addr->coefs[i] == 1
! || !multiplier_allowed_in_address_p (addr->coefs[i]))
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,449 ----
static void
most_expensive_mult_to_index (struct mem_address *parts, tree type,
! aff_tree *addr)
{
! HOST_WIDE_INT coef;
! double_int best_mult = {0, 0}, amult, amult_neg;
unsigned best_mult_cost = 0, acost;
tree mult_elt = NULL_TREE, elt;
unsigned i, j;
+ enum tree_code op_code;
for (i = 0; i < addr->n; i++)
{
! if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
! continue;
!
! coef = double_int_to_shwi (addr->elts[i].coef);
! if (coef == 1
! || !multiplier_allowed_in_address_p (coef))
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
*** 441,453 ****
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;
--- 452,464 ----
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
*** 455,462 ****
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;
--- 466,473 ----
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
*** 466,474 ****
/* 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. */
--- 477,491 ----
/* 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
*** 489,496 ****
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);
--- 506,512 ----
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 111787)
--- tree-flow.h (working copy)
*************** extern void remove_unused_locals (void);
*** 870,902 ****
/* 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
--- 870,875 ----
*************** struct mem_address
*** 904,909 ****
--- 877,883 ----
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 111787)
--- Makefile.in (working copy)
*************** OBJS-common = \
*** 966,972 ****
tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o \
tree-vect-patterns.o tree-ssa-loop-prefetch.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 \
--- 966,972 ----
tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o \
tree-vect-patterns.o tree-ssa-loop-prefetch.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
*** 1964,1970 ****
$(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) \
--- 1964,1970 ----
$(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
*** 1990,1996 ****
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) \
--- 1990,1999 ----
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) \