1 /* Operations with affine combinations of trees.
2 Copyright (C) 2005, 2007, 2008, 2010 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"
25 #include "tree-pretty-print.h"
26 #include "tree-dump.h"
27 #include "pointer-set.h"
28 #include "tree-affine.h"
32 /* Extends CST as appropriate for the affine combinations COMB. */
35 double_int_ext_for_comb (double_int cst
, aff_tree
*comb
)
37 return double_int_sext (cst
, TYPE_PRECISION (comb
->type
));
40 /* Initializes affine combination COMB so that its value is zero in TYPE. */
43 aff_combination_zero (aff_tree
*comb
, tree type
)
46 comb
->offset
= double_int_zero
;
48 comb
->rest
= NULL_TREE
;
51 /* Sets COMB to CST. */
54 aff_combination_const (aff_tree
*comb
, tree type
, double_int cst
)
56 aff_combination_zero (comb
, type
);
57 comb
->offset
= double_int_ext_for_comb (cst
, comb
);
60 /* Sets COMB to single element ELT. */
63 aff_combination_elt (aff_tree
*comb
, tree type
, tree elt
)
65 aff_combination_zero (comb
, type
);
68 comb
->elts
[0].val
= elt
;
69 comb
->elts
[0].coef
= double_int_one
;
72 /* Scales COMB by SCALE. */
75 aff_combination_scale (aff_tree
*comb
, double_int scale
)
79 scale
= double_int_ext_for_comb (scale
, comb
);
80 if (double_int_one_p (scale
))
83 if (double_int_zero_p (scale
))
85 aff_combination_zero (comb
, comb
->type
);
90 = double_int_ext_for_comb (double_int_mul (scale
, comb
->offset
), comb
);
91 for (i
= 0, j
= 0; i
< comb
->n
; i
++)
96 = double_int_ext_for_comb (double_int_mul (scale
, comb
->elts
[i
].coef
),
98 /* A coefficient may become zero due to overflow. Remove the zero
100 if (double_int_zero_p (new_coef
))
102 comb
->elts
[j
].coef
= new_coef
;
103 comb
->elts
[j
].val
= comb
->elts
[i
].val
;
110 tree type
= comb
->type
;
111 if (POINTER_TYPE_P (type
))
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
, type
, comb
->rest
,
122 double_int_to_tree (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
));
184 comb
->rest
= fold_build2 (PLUS_EXPR
, type
, comb
->rest
,
193 aff_combination_add_cst (aff_tree
*c
, double_int cst
)
195 c
->offset
= double_int_ext_for_comb (double_int_add (c
->offset
, cst
), c
);
198 /* Adds COMB2 to COMB1. */
201 aff_combination_add (aff_tree
*comb1
, aff_tree
*comb2
)
205 aff_combination_add_cst (comb1
, comb2
->offset
);
206 for (i
= 0; i
< comb2
->n
; i
++)
207 aff_combination_add_elt (comb1
, comb2
->elts
[i
].val
, comb2
->elts
[i
].coef
);
209 aff_combination_add_elt (comb1
, comb2
->rest
, double_int_one
);
212 /* Converts affine combination COMB to TYPE. */
215 aff_combination_convert (aff_tree
*comb
, tree type
)
218 tree comb_type
= comb
->type
;
220 if (TYPE_PRECISION (type
) > TYPE_PRECISION (comb_type
))
222 tree val
= fold_convert (type
, aff_combination_to_tree (comb
));
223 tree_to_aff_combination (val
, type
, comb
);
228 if (comb
->rest
&& !POINTER_TYPE_P (type
))
229 comb
->rest
= fold_convert (type
, comb
->rest
);
231 if (TYPE_PRECISION (type
) == TYPE_PRECISION (comb_type
))
234 comb
->offset
= double_int_ext_for_comb (comb
->offset
, comb
);
235 for (i
= j
= 0; i
< comb
->n
; i
++)
237 double_int new_coef
= double_int_ext_for_comb (comb
->elts
[i
].coef
, comb
);
238 if (double_int_zero_p (new_coef
))
240 comb
->elts
[j
].coef
= new_coef
;
241 comb
->elts
[j
].val
= fold_convert (type
, comb
->elts
[i
].val
);
246 if (comb
->n
< MAX_AFF_ELTS
&& comb
->rest
)
248 comb
->elts
[comb
->n
].coef
= double_int_one
;
249 comb
->elts
[comb
->n
].val
= comb
->rest
;
250 comb
->rest
= NULL_TREE
;
255 /* Splits EXPR into an affine combination of parts. */
258 tree_to_aff_combination (tree expr
, tree type
, aff_tree
*comb
)
262 tree cst
, core
, toffset
;
263 HOST_WIDE_INT bitpos
, bitsize
;
264 enum machine_mode mode
;
265 int unsignedp
, volatilep
;
269 code
= TREE_CODE (expr
);
273 aff_combination_const (comb
, type
, tree_to_double_int (expr
));
276 case POINTER_PLUS_EXPR
:
277 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
278 tree_to_aff_combination (TREE_OPERAND (expr
, 1), sizetype
, &tmp
);
279 aff_combination_add (comb
, &tmp
);
284 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
285 tree_to_aff_combination (TREE_OPERAND (expr
, 1), type
, &tmp
);
286 if (code
== MINUS_EXPR
)
287 aff_combination_scale (&tmp
, double_int_minus_one
);
288 aff_combination_add (comb
, &tmp
);
292 cst
= TREE_OPERAND (expr
, 1);
293 if (TREE_CODE (cst
) != INTEGER_CST
)
295 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
296 aff_combination_scale (comb
, tree_to_double_int (cst
));
300 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
301 aff_combination_scale (comb
, double_int_minus_one
);
306 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
307 aff_combination_scale (comb
, double_int_minus_one
);
308 aff_combination_add_cst (comb
, double_int_minus_one
);
312 core
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
, &bitpos
,
313 &toffset
, &mode
, &unsignedp
, &volatilep
,
315 if (bitpos
% BITS_PER_UNIT
!= 0)
317 aff_combination_const (comb
, type
,
318 uhwi_to_double_int (bitpos
/ BITS_PER_UNIT
));
319 core
= build_fold_addr_expr (core
);
320 if (TREE_CODE (core
) == ADDR_EXPR
)
321 aff_combination_add_elt (comb
, core
, double_int_one
);
324 tree_to_aff_combination (core
, type
, &tmp
);
325 aff_combination_add (comb
, &tmp
);
329 tree_to_aff_combination (toffset
, type
, &tmp
);
330 aff_combination_add (comb
, &tmp
);
338 aff_combination_elt (comb
, type
, expr
);
341 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
345 add_elt_to_tree (tree expr
, tree type
, tree elt
, double_int scale
,
350 if (POINTER_TYPE_P (type
))
353 scale
= double_int_ext_for_comb (scale
, comb
);
354 elt
= fold_convert (type1
, elt
);
356 if (double_int_one_p (scale
))
359 return fold_convert (type
, elt
);
361 if (POINTER_TYPE_P (type
))
362 return fold_build2 (POINTER_PLUS_EXPR
, type
, expr
, elt
);
363 return fold_build2 (PLUS_EXPR
, type
, expr
, elt
);
366 if (double_int_minus_one_p (scale
))
369 return fold_convert (type
, fold_build1 (NEGATE_EXPR
, type1
, elt
));
371 if (POINTER_TYPE_P (type
))
373 elt
= fold_build1 (NEGATE_EXPR
, type1
, elt
);
374 return fold_build2 (POINTER_PLUS_EXPR
, type
, expr
, elt
);
376 return fold_build2 (MINUS_EXPR
, type
, expr
, elt
);
380 return fold_convert (type
,
381 fold_build2 (MULT_EXPR
, type1
, elt
,
382 double_int_to_tree (type1
, scale
)));
384 if (double_int_negative_p (scale
))
387 scale
= double_int_neg (scale
);
392 elt
= fold_build2 (MULT_EXPR
, type1
, elt
,
393 double_int_to_tree (type1
, scale
));
394 if (POINTER_TYPE_P (type
))
396 if (code
== MINUS_EXPR
)
397 elt
= fold_build1 (NEGATE_EXPR
, type1
, elt
);
398 return fold_build2 (POINTER_PLUS_EXPR
, type
, expr
, elt
);
400 return fold_build2 (code
, type
, expr
, elt
);
403 /* Makes tree from the affine combination COMB. */
406 aff_combination_to_tree (aff_tree
*comb
)
408 tree type
= comb
->type
;
409 tree expr
= comb
->rest
;
413 if (POINTER_TYPE_P (type
))
416 gcc_assert (comb
->n
== MAX_AFF_ELTS
|| comb
->rest
== NULL_TREE
);
418 for (i
= 0; i
< comb
->n
; i
++)
419 expr
= add_elt_to_tree (expr
, type
, comb
->elts
[i
].val
, comb
->elts
[i
].coef
,
422 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
424 if (double_int_negative_p (comb
->offset
))
426 off
= double_int_neg (comb
->offset
);
427 sgn
= double_int_minus_one
;
432 sgn
= double_int_one
;
434 return add_elt_to_tree (expr
, type
, double_int_to_tree (type1
, off
), sgn
,
438 /* Copies the tree elements of COMB to ensure that they are not shared. */
441 unshare_aff_combination (aff_tree
*comb
)
445 for (i
= 0; i
< comb
->n
; i
++)
446 comb
->elts
[i
].val
= unshare_expr (comb
->elts
[i
].val
);
448 comb
->rest
= unshare_expr (comb
->rest
);
451 /* Remove M-th element from COMB. */
454 aff_combination_remove_elt (aff_tree
*comb
, unsigned m
)
458 comb
->elts
[m
] = comb
->elts
[comb
->n
];
461 comb
->elts
[comb
->n
].coef
= double_int_one
;
462 comb
->elts
[comb
->n
].val
= comb
->rest
;
463 comb
->rest
= NULL_TREE
;
468 /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only
469 C * COEF is added to R. */
473 aff_combination_add_product (aff_tree
*c
, double_int coef
, tree val
,
479 for (i
= 0; i
< c
->n
; i
++)
481 aval
= c
->elts
[i
].val
;
484 type
= TREE_TYPE (aval
);
485 aval
= fold_build2 (MULT_EXPR
, type
, aval
,
486 fold_convert (type
, val
));
489 aff_combination_add_elt (r
, aval
,
490 double_int_mul (coef
, c
->elts
[i
].coef
));
498 type
= TREE_TYPE (aval
);
499 aval
= fold_build2 (MULT_EXPR
, type
, aval
,
500 fold_convert (type
, val
));
503 aff_combination_add_elt (r
, aval
, coef
);
507 aff_combination_add_elt (r
, val
,
508 double_int_mul (coef
, c
->offset
));
510 aff_combination_add_cst (r
, double_int_mul (coef
, c
->offset
));
513 /* Multiplies C1 by C2, storing the result to R */
516 aff_combination_mult (aff_tree
*c1
, aff_tree
*c2
, aff_tree
*r
)
519 gcc_assert (TYPE_PRECISION (c1
->type
) == TYPE_PRECISION (c2
->type
));
521 aff_combination_zero (r
, c1
->type
);
523 for (i
= 0; i
< c2
->n
; i
++)
524 aff_combination_add_product (c1
, c2
->elts
[i
].coef
, c2
->elts
[i
].val
, r
);
526 aff_combination_add_product (c1
, double_int_one
, c2
->rest
, r
);
527 aff_combination_add_product (c1
, c2
->offset
, NULL
, r
);
530 /* Returns the element of COMB whose value is VAL, or NULL if no such
531 element exists. If IDX is not NULL, it is set to the index of VAL in
534 static struct aff_comb_elt
*
535 aff_combination_find_elt (aff_tree
*comb
, tree val
, unsigned *idx
)
539 for (i
= 0; i
< comb
->n
; i
++)
540 if (operand_equal_p (comb
->elts
[i
].val
, val
, 0))
545 return &comb
->elts
[i
];
551 /* Element of the cache that maps ssa name NAME to its expanded form
552 as an affine expression EXPANSION. */
554 struct name_expansion
558 /* True if the expansion for the name is just being generated. */
559 unsigned in_progress
: 1;
562 /* Expands SSA names in COMB recursively. CACHE is used to cache the
566 aff_combination_expand (aff_tree
*comb ATTRIBUTE_UNUSED
,
567 struct pointer_map_t
**cache ATTRIBUTE_UNUSED
)
570 aff_tree to_add
, current
, curre
;
575 struct name_expansion
*exp
;
577 aff_combination_zero (&to_add
, comb
->type
);
578 for (i
= 0; i
< comb
->n
; i
++)
583 e
= comb
->elts
[i
].val
;
584 type
= TREE_TYPE (e
);
586 /* Look through some conversions. */
587 if (TREE_CODE (e
) == NOP_EXPR
588 && (TYPE_PRECISION (type
)
589 >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e
, 0)))))
590 name
= TREE_OPERAND (e
, 0);
591 if (TREE_CODE (name
) != SSA_NAME
)
593 def
= SSA_NAME_DEF_STMT (name
);
594 if (!is_gimple_assign (def
) || gimple_assign_lhs (def
) != name
)
597 code
= gimple_assign_rhs_code (def
);
599 && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
))
600 && (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
601 || !is_gimple_min_invariant (gimple_assign_rhs1 (def
))))
604 /* We do not know whether the reference retains its value at the
605 place where the expansion is used. */
606 if (TREE_CODE_CLASS (code
) == tcc_reference
)
610 *cache
= pointer_map_create ();
611 slot
= pointer_map_insert (*cache
, e
);
612 exp
= (struct name_expansion
*) *slot
;
616 exp
= XNEW (struct name_expansion
);
617 exp
->in_progress
= 1;
619 /* In principle this is a generally valid folding, but
620 it is not unconditionally an optimization, so do it
621 here and not in fold_unary. */
622 /* Convert (T1)(X *+- CST) into (T1)X *+- (T1)CST if T1 is wider
623 than the type of X and overflow for the type of X is
626 && INTEGRAL_TYPE_P (type
)
627 && INTEGRAL_TYPE_P (TREE_TYPE (name
))
628 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (name
))
629 && TYPE_PRECISION (type
) > TYPE_PRECISION (TREE_TYPE (name
))
630 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
|| code
== MULT_EXPR
)
631 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
632 rhs
= fold_build2 (code
, type
,
633 fold_convert (type
, gimple_assign_rhs1 (def
)),
634 fold_convert (type
, gimple_assign_rhs2 (def
)));
637 rhs
= gimple_assign_rhs_to_tree (def
);
639 rhs
= fold_convert (type
, rhs
);
641 tree_to_aff_combination_expand (rhs
, comb
->type
, ¤t
, cache
);
642 exp
->expansion
= current
;
643 exp
->in_progress
= 0;
647 /* Since we follow the definitions in the SSA form, we should not
648 enter a cycle unless we pass through a phi node. */
649 gcc_assert (!exp
->in_progress
);
650 current
= exp
->expansion
;
653 /* Accumulate the new terms to TO_ADD, so that we do not modify
654 COMB while traversing it; include the term -coef * E, to remove
656 scale
= comb
->elts
[i
].coef
;
657 aff_combination_zero (&curre
, comb
->type
);
658 aff_combination_add_elt (&curre
, e
, double_int_neg (scale
));
659 aff_combination_scale (¤t
, scale
);
660 aff_combination_add (&to_add
, ¤t
);
661 aff_combination_add (&to_add
, &curre
);
663 aff_combination_add (comb
, &to_add
);
666 /* Similar to tree_to_aff_combination, but follows SSA name definitions
667 and expands them recursively. CACHE is used to cache the expansions
668 of the ssa names, to avoid exponential time complexity for cases
677 tree_to_aff_combination_expand (tree expr
, tree type
, aff_tree
*comb
,
678 struct pointer_map_t
**cache
)
680 tree_to_aff_combination (expr
, type
, comb
);
681 aff_combination_expand (comb
, cache
);
684 /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
685 pointer_map_traverse. */
688 free_name_expansion (const void *key ATTRIBUTE_UNUSED
, void **value
,
689 void *data ATTRIBUTE_UNUSED
)
691 struct name_expansion
*const exp
= (struct name_expansion
*) *value
;
697 /* Frees memory allocated for the CACHE used by
698 tree_to_aff_combination_expand. */
701 free_affine_expand_cache (struct pointer_map_t
**cache
)
706 pointer_map_traverse (*cache
, free_name_expansion
, NULL
);
707 pointer_map_destroy (*cache
);
711 /* If VAL != CST * DIV for any constant CST, returns false.
712 Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
713 additionally compares CST and MULT, and if they are different,
714 returns false. Finally, if neither of these two cases occur,
715 true is returned, and if CST != 0, CST is stored to MULT and
716 MULT_SET is set to true. */
719 double_int_constant_multiple_p (double_int val
, double_int div
,
720 bool *mult_set
, double_int
*mult
)
724 if (double_int_zero_p (val
))
727 if (double_int_zero_p (div
))
730 cst
= double_int_sdivmod (val
, div
, FLOOR_DIV_EXPR
, &rem
);
731 if (!double_int_zero_p (rem
))
734 if (*mult_set
&& !double_int_equal_p (*mult
, cst
))
742 /* Returns true if VAL = X * DIV for some constant X. If this is the case,
743 X is stored to MULT. */
746 aff_combination_constant_multiple_p (aff_tree
*val
, aff_tree
*div
,
749 bool mult_set
= false;
752 if (val
->n
== 0 && double_int_zero_p (val
->offset
))
754 *mult
= double_int_zero
;
757 if (val
->n
!= div
->n
)
760 if (val
->rest
|| div
->rest
)
763 if (!double_int_constant_multiple_p (val
->offset
, div
->offset
,
767 for (i
= 0; i
< div
->n
; i
++)
769 struct aff_comb_elt
*elt
770 = aff_combination_find_elt (val
, div
->elts
[i
].val
, NULL
);
773 if (!double_int_constant_multiple_p (elt
->coef
, div
->elts
[i
].coef
,
778 gcc_assert (mult_set
);
782 /* Prints the affine VAL to the FILE. */
785 print_aff (FILE *file
, aff_tree
*val
)
788 bool uns
= TYPE_UNSIGNED (val
->type
);
789 if (POINTER_TYPE_P (val
->type
))
791 fprintf (file
, "{\n type = ");
792 print_generic_expr (file
, val
->type
, TDF_VOPS
|TDF_MEMSYMS
);
793 fprintf (file
, "\n offset = ");
794 dump_double_int (file
, val
->offset
, uns
);
797 fprintf (file
, "\n elements = {\n");
798 for (i
= 0; i
< val
->n
; i
++)
800 fprintf (file
, " [%d] = ", i
);
801 print_generic_expr (file
, val
->elts
[i
].val
, TDF_VOPS
|TDF_MEMSYMS
);
803 fprintf (file
, " * ");
804 dump_double_int (file
, val
->elts
[i
].coef
, uns
);
806 fprintf (file
, ", \n");
808 fprintf (file
, "\n }");
812 fprintf (file
, "\n rest = ");
813 print_generic_expr (file
, val
->rest
, TDF_VOPS
|TDF_MEMSYMS
);
815 fprintf (file
, "\n}");
818 /* Prints the affine VAL to the standard error, used for debugging. */
821 debug_aff (aff_tree
*val
)
823 print_aff (stderr
, val
);
824 fprintf (stderr
, "\n");
827 /* Returns address of the reference REF in ADDR. The size of the accessed
828 location is stored to SIZE. */
831 get_inner_reference_aff (tree ref
, aff_tree
*addr
, double_int
*size
)
833 HOST_WIDE_INT bitsize
, bitpos
;
835 enum machine_mode mode
;
838 tree base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toff
, &mode
,
840 tree base_addr
= build_fold_addr_expr (base
);
842 /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
844 tree_to_aff_combination (base_addr
, sizetype
, addr
);
848 tree_to_aff_combination (toff
, sizetype
, &tmp
);
849 aff_combination_add (addr
, &tmp
);
852 aff_combination_const (&tmp
, sizetype
,
853 shwi_to_double_int (bitpos
/ BITS_PER_UNIT
));
854 aff_combination_add (addr
, &tmp
);
856 *size
= shwi_to_double_int ((bitsize
+ BITS_PER_UNIT
- 1) / BITS_PER_UNIT
);