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
;