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 tree type
= comb
->type
;
114 if (POINTER_TYPE_P (type
))
116 if (comb
->n
< MAX_AFF_ELTS
)
118 comb
->elts
[comb
->n
].coef
= scale
;
119 comb
->elts
[comb
->n
].val
= comb
->rest
;
120 comb
->rest
= NULL_TREE
;
124 comb
->rest
= fold_build2 (MULT_EXPR
, type
, comb
->rest
,
125 double_int_to_tree (type
, scale
));
129 /* Adds ELT * SCALE to COMB. */
132 aff_combination_add_elt (aff_tree
*comb
, tree elt
, double_int scale
)
137 scale
= double_int_ext_for_comb (scale
, comb
);
138 if (double_int_zero_p (scale
))
141 for (i
= 0; i
< comb
->n
; i
++)
142 if (operand_equal_p (comb
->elts
[i
].val
, elt
, 0))
146 new_coef
= double_int_add (comb
->elts
[i
].coef
, scale
);
147 new_coef
= double_int_ext_for_comb (new_coef
, comb
);
148 if (!double_int_zero_p (new_coef
))
150 comb
->elts
[i
].coef
= new_coef
;
155 comb
->elts
[i
] = comb
->elts
[comb
->n
];
159 gcc_assert (comb
->n
== MAX_AFF_ELTS
- 1);
160 comb
->elts
[comb
->n
].coef
= double_int_one
;
161 comb
->elts
[comb
->n
].val
= comb
->rest
;
162 comb
->rest
= NULL_TREE
;
167 if (comb
->n
< MAX_AFF_ELTS
)
169 comb
->elts
[comb
->n
].coef
= scale
;
170 comb
->elts
[comb
->n
].val
= elt
;
176 if (POINTER_TYPE_P (type
))
179 if (double_int_one_p (scale
))
180 elt
= fold_convert (type
, elt
);
182 elt
= fold_build2 (MULT_EXPR
, type
,
183 fold_convert (type
, elt
),
184 double_int_to_tree (type
, scale
));
187 comb
->rest
= fold_build2 (PLUS_EXPR
, type
, comb
->rest
,
196 aff_combination_add_cst (aff_tree
*c
, double_int cst
)
198 c
->offset
= double_int_ext_for_comb (double_int_add (c
->offset
, cst
), c
);
201 /* Adds COMB2 to COMB1. */
204 aff_combination_add (aff_tree
*comb1
, aff_tree
*comb2
)
208 aff_combination_add_cst (comb1
, comb2
->offset
);
209 for (i
= 0; i
< comb2
->n
; i
++)
210 aff_combination_add_elt (comb1
, comb2
->elts
[i
].val
, comb2
->elts
[i
].coef
);
212 aff_combination_add_elt (comb1
, comb2
->rest
, double_int_one
);
215 /* Converts affine combination COMB to TYPE. */
218 aff_combination_convert (aff_tree
*comb
, tree type
)
221 tree comb_type
= comb
->type
;
223 if (TYPE_PRECISION (type
) > TYPE_PRECISION (comb_type
))
225 tree val
= fold_convert (type
, aff_combination_to_tree (comb
));
226 tree_to_aff_combination (val
, type
, comb
);
231 if (comb
->rest
&& !POINTER_TYPE_P (type
))
232 comb
->rest
= fold_convert (type
, comb
->rest
);
234 if (TYPE_PRECISION (type
) == TYPE_PRECISION (comb_type
))
237 comb
->offset
= double_int_ext_for_comb (comb
->offset
, comb
);
238 for (i
= j
= 0; i
< comb
->n
; i
++)
240 double_int new_coef
= double_int_ext_for_comb (comb
->elts
[i
].coef
, comb
);
241 if (double_int_zero_p (new_coef
))
243 comb
->elts
[j
].coef
= new_coef
;
244 comb
->elts
[j
].val
= fold_convert (type
, comb
->elts
[i
].val
);
249 if (comb
->n
< MAX_AFF_ELTS
&& comb
->rest
)
251 comb
->elts
[comb
->n
].coef
= double_int_one
;
252 comb
->elts
[comb
->n
].val
= comb
->rest
;
253 comb
->rest
= NULL_TREE
;
258 /* Splits EXPR into an affine combination of parts. */
261 tree_to_aff_combination (tree expr
, tree type
, aff_tree
*comb
)
265 tree cst
, core
, toffset
;
266 HOST_WIDE_INT bitpos
, bitsize
;
267 enum machine_mode mode
;
268 int unsignedp
, volatilep
;
272 code
= TREE_CODE (expr
);
276 aff_combination_const (comb
, type
, tree_to_double_int (expr
));
279 case POINTER_PLUS_EXPR
:
280 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
281 tree_to_aff_combination (TREE_OPERAND (expr
, 1), sizetype
, &tmp
);
282 aff_combination_add (comb
, &tmp
);
287 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
288 tree_to_aff_combination (TREE_OPERAND (expr
, 1), type
, &tmp
);
289 if (code
== MINUS_EXPR
)
290 aff_combination_scale (&tmp
, double_int_minus_one
);
291 aff_combination_add (comb
, &tmp
);
295 cst
= TREE_OPERAND (expr
, 1);
296 if (TREE_CODE (cst
) != INTEGER_CST
)
298 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
299 aff_combination_scale (comb
, tree_to_double_int (cst
));
303 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
304 aff_combination_scale (comb
, double_int_minus_one
);
309 tree_to_aff_combination (TREE_OPERAND (expr
, 0), type
, comb
);
310 aff_combination_scale (comb
, double_int_minus_one
);
311 aff_combination_add_cst (comb
, double_int_minus_one
);
315 core
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
, &bitpos
,
316 &toffset
, &mode
, &unsignedp
, &volatilep
,
318 if (bitpos
% BITS_PER_UNIT
!= 0)
320 aff_combination_const (comb
, type
,
321 uhwi_to_double_int (bitpos
/ BITS_PER_UNIT
));
322 core
= build_fold_addr_expr (core
);
323 if (TREE_CODE (core
) == ADDR_EXPR
)
324 aff_combination_add_elt (comb
, core
, double_int_one
);
327 tree_to_aff_combination (core
, type
, &tmp
);
328 aff_combination_add (comb
, &tmp
);
332 tree_to_aff_combination (toffset
, type
, &tmp
);
333 aff_combination_add (comb
, &tmp
);
341 aff_combination_elt (comb
, type
, expr
);
344 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
348 add_elt_to_tree (tree expr
, tree type
, tree elt
, double_int scale
,
353 if (POINTER_TYPE_P (type
))
356 scale
= double_int_ext_for_comb (scale
, comb
);
357 elt
= fold_convert (type1
, elt
);
359 if (double_int_one_p (scale
))
362 return fold_convert (type
, elt
);
364 if (POINTER_TYPE_P (type
))
365 return fold_build2 (POINTER_PLUS_EXPR
, type
, expr
, elt
);
366 return fold_build2 (PLUS_EXPR
, type
, expr
, elt
);
369 if (double_int_minus_one_p (scale
))
372 return fold_convert (type
, fold_build1 (NEGATE_EXPR
, type1
, elt
));
374 if (POINTER_TYPE_P (type
))
376 elt
= fold_build1 (NEGATE_EXPR
, type1
, elt
);
377 return fold_build2 (POINTER_PLUS_EXPR
, type
, expr
, elt
);
379 return fold_build2 (MINUS_EXPR
, type
, expr
, elt
);
383 return fold_convert (type
,
384 fold_build2 (MULT_EXPR
, type1
, elt
,
385 double_int_to_tree (type1
, scale
)));
387 if (double_int_negative_p (scale
))
390 scale
= double_int_neg (scale
);
395 elt
= fold_build2 (MULT_EXPR
, type1
, elt
,
396 double_int_to_tree (type1
, scale
));
397 if (POINTER_TYPE_P (type
))
399 if (code
== MINUS_EXPR
)
400 elt
= fold_build1 (NEGATE_EXPR
, type1
, elt
);
401 return fold_build2 (POINTER_PLUS_EXPR
, type
, expr
, elt
);
403 return fold_build2 (code
, type
, expr
, elt
);
406 /* Makes tree from the affine combination COMB. */
409 aff_combination_to_tree (aff_tree
*comb
)
411 tree type
= comb
->type
;
412 tree expr
= comb
->rest
;
416 if (POINTER_TYPE_P (type
))
419 gcc_assert (comb
->n
== MAX_AFF_ELTS
|| comb
->rest
== NULL_TREE
);
421 for (i
= 0; i
< comb
->n
; i
++)
422 expr
= add_elt_to_tree (expr
, type
, comb
->elts
[i
].val
, comb
->elts
[i
].coef
,
425 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
427 if (double_int_negative_p (comb
->offset
))
429 off
= double_int_neg (comb
->offset
);
430 sgn
= double_int_minus_one
;
435 sgn
= double_int_one
;
437 return add_elt_to_tree (expr
, type
, double_int_to_tree (type1
, off
), sgn
,
441 /* Copies the tree elements of COMB to ensure that they are not shared. */
444 unshare_aff_combination (aff_tree
*comb
)
448 for (i
= 0; i
< comb
->n
; i
++)
449 comb
->elts
[i
].val
= unshare_expr (comb
->elts
[i
].val
);
451 comb
->rest
= unshare_expr (comb
->rest
);
454 /* Remove M-th element from COMB. */
457 aff_combination_remove_elt (aff_tree
*comb
, unsigned m
)
461 comb
->elts
[m
] = comb
->elts
[comb
->n
];
464 comb
->elts
[comb
->n
].coef
= double_int_one
;
465 comb
->elts
[comb
->n
].val
= comb
->rest
;
466 comb
->rest
= NULL_TREE
;
471 /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only
472 C * COEF is added to R. */
476 aff_combination_add_product (aff_tree
*c
, double_int coef
, tree val
,
482 for (i
= 0; i
< c
->n
; i
++)
484 aval
= c
->elts
[i
].val
;
487 type
= TREE_TYPE (aval
);
488 aval
= fold_build2 (MULT_EXPR
, type
, aval
,
489 fold_convert (type
, val
));
492 aff_combination_add_elt (r
, aval
,
493 double_int_mul (coef
, c
->elts
[i
].coef
));
501 type
= TREE_TYPE (aval
);
502 aval
= fold_build2 (MULT_EXPR
, type
, aval
,
503 fold_convert (type
, val
));
506 aff_combination_add_elt (r
, aval
, coef
);
510 aff_combination_add_elt (r
, val
,
511 double_int_mul (coef
, c
->offset
));
513 aff_combination_add_cst (r
, double_int_mul (coef
, c
->offset
));
516 /* Multiplies C1 by C2, storing the result to R */
519 aff_combination_mult (aff_tree
*c1
, aff_tree
*c2
, aff_tree
*r
)
522 gcc_assert (TYPE_PRECISION (c1
->type
) == TYPE_PRECISION (c2
->type
));
524 aff_combination_zero (r
, c1
->type
);
526 for (i
= 0; i
< c2
->n
; i
++)
527 aff_combination_add_product (c1
, c2
->elts
[i
].coef
, c2
->elts
[i
].val
, r
);
529 aff_combination_add_product (c1
, double_int_one
, c2
->rest
, r
);
530 aff_combination_add_product (c1
, c2
->offset
, NULL
, r
);
533 /* Returns the element of COMB whose value is VAL, or NULL if no such
534 element exists. If IDX is not NULL, it is set to the index of VAL in
537 static struct aff_comb_elt
*
538 aff_combination_find_elt (aff_tree
*comb
, tree val
, unsigned *idx
)
542 for (i
= 0; i
< comb
->n
; i
++)
543 if (operand_equal_p (comb
->elts
[i
].val
, val
, 0))
548 return &comb
->elts
[i
];
554 /* Element of the cache that maps ssa name NAME to its expanded form
555 as an affine expression EXPANSION. */
557 struct name_expansion
561 /* True if the expansion for the name is just being generated. */
562 unsigned in_progress
: 1;
565 /* Expands SSA names in COMB recursively. CACHE is used to cache the
569 aff_combination_expand (aff_tree
*comb
, struct pointer_map_t
**cache
)
572 aff_tree to_add
, current
, curre
;
576 struct name_expansion
*exp
;
578 aff_combination_zero (&to_add
, comb
->type
);
579 for (i
= 0; i
< comb
->n
; i
++)
581 e
= comb
->elts
[i
].val
;
582 if (TREE_CODE (e
) != SSA_NAME
)
584 def
= SSA_NAME_DEF_STMT (e
);
585 if (TREE_CODE (def
) != GIMPLE_MODIFY_STMT
586 || GIMPLE_STMT_OPERAND (def
, 0) != e
)
589 rhs
= GIMPLE_STMT_OPERAND (def
, 1);
590 if (TREE_CODE (rhs
) != SSA_NAME
592 && !is_gimple_min_invariant (rhs
))
595 /* We do not know whether the reference retains its value at the
596 place where the expansion is used. */
597 if (REFERENCE_CLASS_P (rhs
))
601 *cache
= pointer_map_create ();
602 slot
= pointer_map_insert (*cache
, e
);
607 exp
= XNEW (struct name_expansion
);
608 exp
->in_progress
= 1;
610 tree_to_aff_combination_expand (rhs
, comb
->type
, ¤t
, cache
);
611 exp
->expansion
= current
;
612 exp
->in_progress
= 0;
616 /* Since we follow the definitions in the SSA form, we should not
617 enter a cycle unless we pass through a phi node. */
618 gcc_assert (!exp
->in_progress
);
619 current
= exp
->expansion
;
622 /* Accumulate the new terms to TO_ADD, so that we do not modify
623 COMB while traversing it; include the term -coef * E, to remove
625 scale
= comb
->elts
[i
].coef
;
626 aff_combination_zero (&curre
, comb
->type
);
627 aff_combination_add_elt (&curre
, e
, double_int_neg (scale
));
628 aff_combination_scale (¤t
, scale
);
629 aff_combination_add (&to_add
, ¤t
);
630 aff_combination_add (&to_add
, &curre
);
632 aff_combination_add (comb
, &to_add
);
635 /* Similar to tree_to_aff_combination, but follows SSA name definitions
636 and expands them recursively. CACHE is used to cache the expansions
637 of the ssa names, to avoid exponential time complexity for cases
646 tree_to_aff_combination_expand (tree expr
, tree type
, aff_tree
*comb
,
647 struct pointer_map_t
**cache
)
649 tree_to_aff_combination (expr
, type
, comb
);
650 aff_combination_expand (comb
, cache
);
653 /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
654 pointer_map_traverse. */
657 free_name_expansion (const void *key ATTRIBUTE_UNUSED
, void **value
,
658 void *data ATTRIBUTE_UNUSED
)
660 struct name_expansion
*exp
= *value
;
666 /* Frees memory allocated for the CACHE used by
667 tree_to_aff_combination_expand. */
670 free_affine_expand_cache (struct pointer_map_t
**cache
)
675 pointer_map_traverse (*cache
, free_name_expansion
, NULL
);
676 pointer_map_destroy (*cache
);
680 /* If VAL != CST * DIV for any constant CST, returns false.
681 Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
682 additionally compares CST and MULT, and if they are different,
683 returns false. Finally, if neither of these two cases occur,
684 true is returned, and if CST != 0, CST is stored to MULT and
685 MULT_SET is set to true. */
688 double_int_constant_multiple_p (double_int val
, double_int div
,
689 bool *mult_set
, double_int
*mult
)
693 if (double_int_zero_p (val
))
696 if (double_int_zero_p (div
))
699 cst
= double_int_sdivmod (val
, div
, FLOOR_DIV_EXPR
, &rem
);
700 if (!double_int_zero_p (rem
))
703 if (*mult_set
&& !double_int_equal_p (*mult
, cst
))
711 /* Returns true if VAL = X * DIV for some constant X. If this is the case,
712 X is stored to MULT. */
715 aff_combination_constant_multiple_p (aff_tree
*val
, aff_tree
*div
,
718 bool mult_set
= false;
721 if (val
->n
== 0 && double_int_zero_p (val
->offset
))
723 *mult
= double_int_zero
;
726 if (val
->n
!= div
->n
)
729 if (val
->rest
|| div
->rest
)
732 if (!double_int_constant_multiple_p (val
->offset
, div
->offset
,
736 for (i
= 0; i
< div
->n
; i
++)
738 struct aff_comb_elt
*elt
739 = aff_combination_find_elt (val
, div
->elts
[i
].val
, NULL
);
742 if (!double_int_constant_multiple_p (elt
->coef
, div
->elts
[i
].coef
,
747 gcc_assert (mult_set
);
751 /* Prints the affine VAL to the FILE. */
754 print_aff (FILE *file
, aff_tree
*val
)
757 bool uns
= TYPE_UNSIGNED (val
->type
);
758 if (POINTER_TYPE_P (val
->type
))
760 fprintf (file
, "{\n type = ");
761 print_generic_expr (file
, val
->type
, TDF_VOPS
|TDF_MEMSYMS
);
762 fprintf (file
, "\n offset = ");
763 dump_double_int (file
, val
->offset
, uns
);
766 fprintf (file
, "\n elements = {\n");
767 for (i
= 0; i
< val
->n
; i
++)
769 fprintf (file
, " [%d] = ", i
);
770 print_generic_expr (file
, val
->elts
[i
].val
, TDF_VOPS
|TDF_MEMSYMS
);
772 fprintf (file
, " * ");
773 dump_double_int (file
, val
->elts
[i
].coef
, uns
);
775 fprintf (file
, ", \n");
777 fprintf (file
, "\n }");
781 fprintf (file
, "\n rest = ");
782 print_generic_expr (file
, val
->rest
, TDF_VOPS
|TDF_MEMSYMS
);
784 fprintf (file
, "\n}");
787 /* Prints the affine VAL to the standard error, used for debugging. */
790 debug_aff (aff_tree
*val
)
792 print_aff (stderr
, val
);
793 fprintf (stderr
, "\n");
796 /* Returns address of the reference REF in ADDR. The size of the accessed
797 location is stored to SIZE. */
800 get_inner_reference_aff (tree ref
, aff_tree
*addr
, double_int
*size
)
802 HOST_WIDE_INT bitsize
, bitpos
;
804 enum machine_mode mode
;
807 tree base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toff
, &mode
,
809 tree base_addr
= build_fold_addr_expr (base
);
811 /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
813 tree_to_aff_combination (base_addr
, sizetype
, addr
);
817 tree_to_aff_combination (toff
, sizetype
, &tmp
);
818 aff_combination_add (addr
, &tmp
);
821 aff_combination_const (&tmp
, sizetype
,
822 shwi_to_double_int (bitpos
/ BITS_PER_UNIT
));
823 aff_combination_add (addr
, &tmp
);
825 *size
= shwi_to_double_int ((bitsize
+ BITS_PER_UNIT
- 1) / BITS_PER_UNIT
);