1 /* Operations with affine combinations of trees.
2 Copyright (C) 2005, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
29 #include "diagnostic.h"
30 #include "tree-dump.h"
31 #include "pointer-set.h"
32 #include "tree-affine.h"
33 #include "tree-gimple.h"
35 /* Extends CST as appropriate for the affine combinations COMB. */
38 double_int_ext_for_comb (double_int cst, aff_tree *comb)
40 return double_int_sext (cst, TYPE_PRECISION (comb->type));
43 /* Initializes affine combination COMB so that its value is zero in TYPE. */
46 aff_combination_zero (aff_tree *comb, tree type)
49 comb->offset = double_int_zero;
51 comb->rest = NULL_TREE;
54 /* Sets COMB to CST. */
57 aff_combination_const (aff_tree *comb, tree type, double_int cst)
59 aff_combination_zero (comb, type);
60 comb->offset = double_int_ext_for_comb (cst, comb);
63 /* Sets COMB to single element ELT. */
66 aff_combination_elt (aff_tree *comb, tree type, tree elt)
68 aff_combination_zero (comb, type);
71 comb->elts[0].val = elt;
72 comb->elts[0].coef = double_int_one;
75 /* Scales COMB by SCALE. */
78 aff_combination_scale (aff_tree *comb, double_int scale)
82 scale = double_int_ext_for_comb (scale, comb);
83 if (double_int_one_p (scale))
86 if (double_int_zero_p (scale))
88 aff_combination_zero (comb, comb->type);
93 = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
94 for (i = 0, j = 0; i < comb->n; i++)
99 = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
101 /* A coefficient may become zero due to overflow. Remove the zero
103 if (double_int_zero_p (new_coef))
105 comb->elts[j].coef = new_coef;
106 comb->elts[j].val = comb->elts[i].val;
113 if (comb->n < MAX_AFF_ELTS)
115 comb->elts[comb->n].coef = scale;
116 comb->elts[comb->n].val = comb->rest;
117 comb->rest = NULL_TREE;
121 comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
122 double_int_to_tree (comb->type, scale));
126 /* Adds ELT * SCALE to COMB. */
129 aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
134 scale = double_int_ext_for_comb (scale, comb);
135 if (double_int_zero_p (scale))
138 for (i = 0; i < comb->n; i++)
139 if (operand_equal_p (comb->elts[i].val, elt, 0))
143 new_coef = double_int_add (comb->elts[i].coef, scale);
144 new_coef = double_int_ext_for_comb (new_coef, comb);
145 if (!double_int_zero_p (new_coef))
147 comb->elts[i].coef = new_coef;
152 comb->elts[i] = comb->elts[comb->n];
156 gcc_assert (comb->n == MAX_AFF_ELTS - 1);
157 comb->elts[comb->n].coef = double_int_one;
158 comb->elts[comb->n].val = comb->rest;
159 comb->rest = NULL_TREE;
164 if (comb->n < MAX_AFF_ELTS)
166 comb->elts[comb->n].coef = scale;
167 comb->elts[comb->n].val = elt;
173 if (POINTER_TYPE_P (type))
176 if (double_int_one_p (scale))
177 elt = fold_convert (type, elt);
179 elt = fold_build2 (MULT_EXPR, type,
180 fold_convert (type, elt),
181 double_int_to_tree (type, scale));
185 if (POINTER_TYPE_P (comb->type))
186 comb->rest = fold_build2 (POINTER_PLUS_EXPR, comb->type,
189 comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest,
199 aff_combination_add_cst (aff_tree *c, double_int cst)
201 c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c);
204 /* Adds COMB2 to COMB1. */
207 aff_combination_add (aff_tree *comb1, aff_tree *comb2)
211 aff_combination_add_cst (comb1, comb2->offset);
212 for (i = 0; i < comb2->n; i++)
213 aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
215 aff_combination_add_elt (comb1, comb2->rest, double_int_one);
218 /* Converts affine combination COMB to TYPE. */
221 aff_combination_convert (aff_tree *comb, tree type)
224 tree comb_type = comb->type;
226 if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
228 tree val = fold_convert (type, aff_combination_to_tree (comb));
229 tree_to_aff_combination (val, type, comb);
235 comb->rest = fold_convert (type, comb->rest);
237 if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
240 comb->offset = double_int_ext_for_comb (comb->offset, comb);
241 for (i = j = 0; i < comb->n; i++)
243 double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
244 if (double_int_zero_p (new_coef))
246 comb->elts[j].coef = new_coef;
247 comb->elts[j].val = fold_convert (type, comb->elts[i].val);
252 if (comb->n < MAX_AFF_ELTS && comb->rest)
254 comb->elts[comb->n].coef = double_int_one;
255 comb->elts[comb->n].val = comb->rest;
256 comb->rest = NULL_TREE;
261 /* Splits EXPR into an affine combination of parts. */
264 tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
268 tree cst, core, toffset;
269 HOST_WIDE_INT bitpos, bitsize;
270 enum machine_mode mode;
271 int unsignedp, volatilep;
275 code = TREE_CODE (expr);
279 aff_combination_const (comb, type, tree_to_double_int (expr));
282 case POINTER_PLUS_EXPR:
283 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
284 tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
285 aff_combination_convert (&tmp, type);
286 aff_combination_add (comb, &tmp);
291 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
292 tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
293 if (code == MINUS_EXPR)
294 aff_combination_scale (&tmp, double_int_minus_one);
295 aff_combination_add (comb, &tmp);
299 cst = TREE_OPERAND (expr, 1);
300 if (TREE_CODE (cst) != INTEGER_CST)
302 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
303 aff_combination_scale (comb, tree_to_double_int (cst));
307 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
308 aff_combination_scale (comb, double_int_minus_one);
313 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
314 aff_combination_scale (comb, double_int_minus_one);
315 aff_combination_add_cst (comb, double_int_minus_one);
319 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
320 &toffset, &mode, &unsignedp, &volatilep,
322 if (bitpos % BITS_PER_UNIT != 0)
324 aff_combination_const (comb, type,
325 uhwi_to_double_int (bitpos / BITS_PER_UNIT));
326 core = build_fold_addr_expr (core);
327 if (TREE_CODE (core) == ADDR_EXPR)
328 aff_combination_add_elt (comb, core, double_int_one);
331 tree_to_aff_combination (core, type, &tmp);
332 aff_combination_add (comb, &tmp);
336 tree_to_aff_combination (toffset, type, &tmp);
337 aff_combination_add (comb, &tmp);
345 aff_combination_elt (comb, type, expr);
348 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
352 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
357 scale = double_int_ext_for_comb (scale, comb);
358 elt = fold_convert (type, elt);
360 if (double_int_one_p (scale))
365 return fold_build2 (PLUS_EXPR, type, expr, elt);
368 if (double_int_minus_one_p (scale))
371 return fold_build1 (NEGATE_EXPR, type, elt);
373 return fold_build2 (MINUS_EXPR, type, expr, elt);
377 return fold_build2 (MULT_EXPR, type, elt,
378 double_int_to_tree (type, scale));
380 if (double_int_negative_p (scale))
383 scale = double_int_neg (scale);
388 elt = fold_build2 (MULT_EXPR, type, elt,
389 double_int_to_tree (type, scale));
390 return fold_build2 (code, type, expr, elt);
393 /* Makes tree from the affine combination COMB. */
396 aff_combination_to_tree (aff_tree *comb)
398 tree type = comb->type;
399 tree expr = comb->rest;
403 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
405 for (i = 0; i < comb->n; i++)
406 expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
409 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
411 if (double_int_negative_p (comb->offset))
413 off = double_int_neg (comb->offset);
414 sgn = double_int_minus_one;
419 sgn = double_int_one;
421 return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
425 /* Copies the tree elements of COMB to ensure that they are not shared. */
428 unshare_aff_combination (aff_tree *comb)
432 for (i = 0; i < comb->n; i++)
433 comb->elts[i].val = unshare_expr (comb->elts[i].val);
435 comb->rest = unshare_expr (comb->rest);
438 /* Remove M-th element from COMB. */
441 aff_combination_remove_elt (aff_tree *comb, unsigned m)
445 comb->elts[m] = comb->elts[comb->n];
448 comb->elts[comb->n].coef = double_int_one;
449 comb->elts[comb->n].val = comb->rest;
450 comb->rest = NULL_TREE;
455 /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only
456 C * COEF is added to R. */
460 aff_combination_add_product (aff_tree *c, double_int coef, tree val,
466 for (i = 0; i < c->n; i++)
468 aval = c->elts[i].val;
471 type = TREE_TYPE (aval);
472 aval = fold_build2 (MULT_EXPR, type, aval,
473 fold_convert (type, val));
476 aff_combination_add_elt (r, aval,
477 double_int_mul (coef, c->elts[i].coef));
485 type = TREE_TYPE (aval);
486 aval = fold_build2 (MULT_EXPR, type, aval,
487 fold_convert (type, val));
490 aff_combination_add_elt (r, aval, coef);
494 aff_combination_add_elt (r, val,
495 double_int_mul (coef, c->offset));
497 aff_combination_add_cst (r, double_int_mul (coef, c->offset));
500 /* Multiplies C1 by C2, storing the result to R */
503 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
506 gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
508 aff_combination_zero (r, c1->type);
510 for (i = 0; i < c2->n; i++)
511 aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
513 aff_combination_add_product (c1, double_int_one, c2->rest, r);
514 aff_combination_add_product (c1, c2->offset, NULL, r);
517 /* Returns the element of COMB whose value is VAL, or NULL if no such
518 element exists. If IDX is not NULL, it is set to the index of VAL in
521 static struct aff_comb_elt *
522 aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
526 for (i = 0; i < comb->n; i++)
527 if (operand_equal_p (comb->elts[i].val, val, 0))
532 return &comb->elts[i];
538 /* Element of the cache that maps ssa name NAME to its expanded form
539 as an affine expression EXPANSION. */
541 struct name_expansion
545 /* True if the expansion for the name is just being generated. */
546 unsigned in_progress : 1;
549 /* Similar to tree_to_aff_combination, but follows SSA name definitions
550 and expands them recursively. CACHE is used to cache the expansions
551 of the ssa names, to avoid exponential time complexity for cases
560 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
561 struct pointer_map_t **cache)
564 aff_tree to_add, current, curre;
568 struct name_expansion *exp;
570 tree_to_aff_combination (expr, type, comb);
571 aff_combination_zero (&to_add, type);
572 for (i = 0; i < comb->n; i++)
574 e = comb->elts[i].val;
575 if (TREE_CODE (e) != SSA_NAME)
577 def = SSA_NAME_DEF_STMT (e);
578 if (TREE_CODE (def) != GIMPLE_MODIFY_STMT
579 || GIMPLE_STMT_OPERAND (def, 0) != e)
582 rhs = GIMPLE_STMT_OPERAND (def, 1);
583 if (TREE_CODE (rhs) != SSA_NAME
585 && !is_gimple_min_invariant (rhs))
588 /* We do not know whether the reference retains its value at the
589 place where the expansion is used. */
590 if (REFERENCE_CLASS_P (rhs))
594 *cache = pointer_map_create ();
595 slot = pointer_map_insert (*cache, e);
600 exp = XNEW (struct name_expansion);
601 exp->in_progress = 1;
603 tree_to_aff_combination_expand (rhs, type, ¤t, cache);
604 exp->expansion = current;
605 exp->in_progress = 0;
609 /* Since we follow the definitions in the SSA form, we should not
610 enter a cycle unless we pass through a phi node. */
611 gcc_assert (!exp->in_progress);
612 current = exp->expansion;
615 /* Accumulate the new terms to TO_ADD, so that we do not modify
616 COMB while traversing it; include the term -coef * E, to remove
618 scale = comb->elts[i].coef;
619 aff_combination_zero (&curre, type);
620 aff_combination_add_elt (&curre, e, double_int_neg (scale));
621 aff_combination_scale (¤t, scale);
622 aff_combination_add (&to_add, ¤t);
623 aff_combination_add (&to_add, &curre);
625 aff_combination_add (comb, &to_add);
628 /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
629 pointer_map_traverse. */
632 free_name_expansion (void *key ATTRIBUTE_UNUSED, void **value,
633 void *data ATTRIBUTE_UNUSED)
635 struct name_expansion *exp = *value;
641 /* Frees memory allocated for the CACHE used by
642 tree_to_aff_combination_expand. */
645 free_affine_expand_cache (struct pointer_map_t **cache)
650 pointer_map_traverse (*cache, free_name_expansion, NULL);
651 pointer_map_destroy (*cache);
655 /* If VAL != CST * DIV for any constant CST, returns false.
656 Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
657 additionally compares CST and MULT, and if they are different,
658 returns false. Finally, if neither of these two cases occur,
659 true is returned, and if CST != 0, CST is stored to MULT and
660 MULT_SET is set to true. */
663 double_int_constant_multiple_p (double_int val, double_int div,
664 bool *mult_set, double_int *mult)
668 if (double_int_zero_p (val))
671 if (double_int_zero_p (div))
674 cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem);
675 if (!double_int_zero_p (rem))
678 if (*mult_set && !double_int_equal_p (*mult, cst))
686 /* Returns true if VAL = X * DIV for some constant X. If this is the case,
687 X is stored to MULT. */
690 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
693 bool mult_set = false;
696 if (val->n == 0 && double_int_zero_p (val->offset))
698 *mult = double_int_zero;
701 if (val->n != div->n)
704 if (val->rest || div->rest)
707 if (!double_int_constant_multiple_p (val->offset, div->offset,
711 for (i = 0; i < div->n; i++)
713 struct aff_comb_elt *elt
714 = aff_combination_find_elt (val, div->elts[i].val, NULL);
717 if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef,
722 gcc_assert (mult_set);