1 /* Operations with affine combinations of trees.
2 Copyright (C) 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
30 #include "diagnostic.h"
31 #include "tree-dump.h"
32 #include "tree-affine.h"
34 /* Extends CST as appropriate for the affine combinations COMB. */
37 double_int_ext_for_comb (double_int cst, aff_tree *comb)
39 return double_int_sext (cst, TYPE_PRECISION (comb->type));
42 /* Initializes affine combination COMB so that its value is zero in TYPE. */
45 aff_combination_zero (aff_tree *comb, tree type)
48 comb->offset = double_int_zero;
50 comb->rest = NULL_TREE;
53 /* Sets COMB to CST. */
56 aff_combination_const (aff_tree *comb, tree type, double_int cst)
58 aff_combination_zero (comb, type);
59 comb->offset = double_int_ext_for_comb (cst, comb);
62 /* Sets COMB to single element ELT. */
65 aff_combination_elt (aff_tree *comb, tree type, tree elt)
67 aff_combination_zero (comb, type);
70 comb->elts[0].val = elt;
71 comb->elts[0].coef = double_int_one;
74 /* Scales COMB by SCALE. */
77 aff_combination_scale (aff_tree *comb, double_int scale)
81 scale = double_int_ext_for_comb (scale, comb);
82 if (double_int_one_p (scale))
85 if (double_int_zero_p (scale))
87 aff_combination_zero (comb, comb->type);
92 = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
93 for (i = 0, j = 0; i < comb->n; i++)
98 = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
100 /* A coefficient may become zero due to overflow. Remove the zero
102 if (double_int_zero_p (new_coef))
104 comb->elts[j].coef = new_coef;
105 comb->elts[j].val = comb->elts[i].val;
112 if (comb->n < MAX_AFF_ELTS)
114 comb->elts[comb->n].coef = scale;
115 comb->elts[comb->n].val = comb->rest;
116 comb->rest = NULL_TREE;
120 comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
121 double_int_to_tree (comb->type, scale));
125 /* Adds ELT * SCALE to COMB. */
128 aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
132 scale = double_int_ext_for_comb (scale, comb);
133 if (double_int_zero_p (scale))
136 for (i = 0; i < comb->n; i++)
137 if (operand_equal_p (comb->elts[i].val, elt, 0))
141 new_coef = double_int_add (comb->elts[i].coef, scale);
142 new_coef = double_int_ext_for_comb (new_coef, comb);
143 if (!double_int_zero_p (new_coef))
145 comb->elts[i].coef = new_coef;
150 comb->elts[i] = comb->elts[comb->n];
154 gcc_assert (comb->n == MAX_AFF_ELTS - 1);
155 comb->elts[comb->n].coef = double_int_one;
156 comb->elts[comb->n].val = comb->rest;
157 comb->rest = NULL_TREE;
162 if (comb->n < MAX_AFF_ELTS)
164 comb->elts[comb->n].coef = scale;
165 comb->elts[comb->n].val = elt;
170 if (double_int_one_p (scale))
171 elt = fold_convert (comb->type, elt);
173 elt = fold_build2 (MULT_EXPR, comb->type,
174 fold_convert (comb->type, elt),
175 double_int_to_tree (comb->type, scale));
178 comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
183 /* Adds COMB2 to COMB1. */
186 aff_combination_add (aff_tree *comb1, aff_tree *comb2)
191 = double_int_ext_for_comb (double_int_add (comb1->offset, comb2->offset),
193 for (i = 0; i < comb2->n; i++)
194 aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
196 aff_combination_add_elt (comb1, comb2->rest, double_int_one);
199 /* Converts affine combination COMB to TYPE. */
202 aff_combination_convert (aff_tree *comb, tree type)
205 tree comb_type = comb->type;
207 gcc_assert (TYPE_PRECISION (type) <= TYPE_PRECISION (comb_type));
210 comb->rest = fold_convert (type, comb->rest);
212 if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
215 comb->offset = double_int_ext_for_comb (comb->offset, comb);
216 for (i = j = 0; i < comb->n; i++)
218 double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
219 if (double_int_zero_p (new_coef))
221 comb->elts[j].coef = new_coef;
222 comb->elts[j].val = fold_convert (type, comb->elts[i].val);
227 if (comb->n < MAX_AFF_ELTS && comb->rest)
229 comb->elts[comb->n].coef = double_int_one;
230 comb->elts[comb->n].val = comb->rest;
231 comb->rest = NULL_TREE;
236 /* Splits EXPR into an affine combination of parts. */
239 tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
243 tree cst, core, toffset;
244 HOST_WIDE_INT bitpos, bitsize;
245 enum machine_mode mode;
246 int unsignedp, volatilep;
250 code = TREE_CODE (expr);
254 aff_combination_const (comb, type, tree_to_double_int (expr));
259 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
260 tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
261 if (code == MINUS_EXPR)
262 aff_combination_scale (&tmp, double_int_minus_one);
263 aff_combination_add (comb, &tmp);
267 cst = TREE_OPERAND (expr, 1);
268 if (TREE_CODE (cst) != INTEGER_CST)
270 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
271 aff_combination_scale (comb, tree_to_double_int (cst));
275 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
276 aff_combination_scale (comb, double_int_minus_one);
280 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
281 &toffset, &mode, &unsignedp, &volatilep,
283 if (bitpos % BITS_PER_UNIT != 0)
285 aff_combination_const (comb, type,
286 uhwi_to_double_int (bitpos / BITS_PER_UNIT));
287 core = build_fold_addr_expr (core);
288 if (TREE_CODE (core) == ADDR_EXPR)
289 aff_combination_add_elt (comb, core, double_int_one);
292 tree_to_aff_combination (core, type, &tmp);
293 aff_combination_add (comb, &tmp);
297 tree_to_aff_combination (toffset, type, &tmp);
298 aff_combination_add (comb, &tmp);
306 aff_combination_elt (comb, type, expr);
309 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
313 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
318 scale = double_int_ext_for_comb (scale, comb);
319 elt = fold_convert (type, elt);
321 if (double_int_one_p (scale))
326 return fold_build2 (PLUS_EXPR, type, expr, elt);
329 if (double_int_minus_one_p (scale))
332 return fold_build1 (NEGATE_EXPR, type, elt);
334 return fold_build2 (MINUS_EXPR, type, expr, elt);
338 return fold_build2 (MULT_EXPR, type, elt,
339 double_int_to_tree (type, scale));
341 if (double_int_negative_p (scale))
344 scale = double_int_neg (scale);
349 elt = fold_build2 (MULT_EXPR, type, elt,
350 double_int_to_tree (type, scale));
351 return fold_build2 (code, type, expr, elt);
354 /* Makes tree from the affine combination COMB. */
357 aff_combination_to_tree (aff_tree *comb)
359 tree type = comb->type;
360 tree expr = comb->rest;
364 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
366 for (i = 0; i < comb->n; i++)
367 expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
370 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
372 if (double_int_negative_p (comb->offset))
374 off = double_int_neg (comb->offset);
375 sgn = double_int_minus_one;
380 sgn = double_int_one;
382 return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
386 /* Copies the tree elements of COMB to ensure that they are not shared. */
389 unshare_aff_combination (aff_tree *comb)
393 for (i = 0; i < comb->n; i++)
394 comb->elts[i].val = unshare_expr (comb->elts[i].val);
396 comb->rest = unshare_expr (comb->rest);
399 /* Remove M-th element from COMB. */
402 aff_combination_remove_elt (aff_tree *comb, unsigned m)
406 comb->elts[m] = comb->elts[comb->n];
409 comb->elts[comb->n].coef = double_int_one;
410 comb->elts[comb->n].val = comb->rest;
411 comb->rest = NULL_TREE;