Branch data Line data Source code
1 : : /* Operations with affine combinations of trees.
2 : : Copyright (C) 2005-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
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
9 : : later version.
10 : :
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
14 : : for more details.
15 : :
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/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "rtl.h"
25 : : #include "tree.h"
26 : : #include "gimple.h"
27 : : #include "ssa.h"
28 : : #include "tree-pretty-print.h"
29 : : #include "fold-const.h"
30 : : #include "tree-affine.h"
31 : : #include "gimplify.h"
32 : : #include "dumpfile.h"
33 : : #include "cfgexpand.h"
34 : : #include "value-query.h"
35 : :
36 : : /* Extends CST as appropriate for the affine combinations COMB. */
37 : :
38 : : static widest_int
39 : 141121124 : wide_int_ext_for_comb (const widest_int &cst, tree type)
40 : : {
41 : 141121124 : return wi::sext (cst, TYPE_PRECISION (type));
42 : : }
43 : :
44 : : /* Likewise for polynomial offsets. */
45 : :
46 : : static poly_widest_int
47 : 204291488 : wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
48 : : {
49 : 204291488 : return wi::sext (cst, TYPE_PRECISION (type));
50 : : }
51 : :
52 : : /* Initializes affine combination COMB so that its value is zero in TYPE. */
53 : :
54 : : static void
55 : 167280460 : aff_combination_zero (aff_tree *comb, tree type)
56 : : {
57 : 167280460 : int i;
58 : 167280460 : comb->type = type;
59 : 167280460 : comb->offset = 0;
60 : 167280460 : comb->n = 0;
61 : 1505524140 : for (i = 0; i < MAX_AFF_ELTS; i++)
62 : 1338243680 : comb->elts[i].coef = 0;
63 : 167280460 : comb->rest = NULL_TREE;
64 : 167280460 : }
65 : :
66 : : /* Sets COMB to CST. */
67 : :
68 : : void
69 : 87165129 : aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
70 : : {
71 : 87165129 : aff_combination_zero (comb, type);
72 : 87165129 : comb->offset = wide_int_ext_for_comb (cst, comb->type);;
73 : 87165129 : }
74 : :
75 : : /* Sets COMB to single element ELT. */
76 : :
77 : : void
78 : 41326257 : aff_combination_elt (aff_tree *comb, tree type, tree elt)
79 : : {
80 : 41326257 : aff_combination_zero (comb, type);
81 : :
82 : 41326257 : comb->n = 1;
83 : 41326257 : comb->elts[0].val = elt;
84 : 41326257 : comb->elts[0].coef = 1;
85 : 41326257 : }
86 : :
87 : : /* Scales COMB by SCALE. */
88 : :
89 : : void
90 : 38460834 : aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
91 : : {
92 : 38460834 : unsigned i, j;
93 : :
94 : 38460834 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
95 : 38460834 : if (scale == 1)
96 : : return;
97 : :
98 : 28154734 : if (scale == 0)
99 : : {
100 : 140 : aff_combination_zero (comb, comb->type);
101 : 140 : return;
102 : : }
103 : :
104 : 28154594 : comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
105 : 51120828 : for (i = 0, j = 0; i < comb->n; i++)
106 : : {
107 : 22966234 : widest_int new_coef
108 : 22966234 : = wide_int_ext_for_comb (scale * comb->elts[i].coef, comb->type);
109 : : /* A coefficient may become zero due to overflow. Remove the zero
110 : : elements. */
111 : 22966234 : if (new_coef == 0)
112 : 2 : continue;
113 : 22966232 : comb->elts[j].coef = new_coef;
114 : 22966232 : comb->elts[j].val = comb->elts[i].val;
115 : 22966232 : j++;
116 : 22966234 : }
117 : 28154594 : comb->n = j;
118 : :
119 : 28154594 : if (comb->rest)
120 : : {
121 : 138 : tree type = comb->type;
122 : 138 : if (POINTER_TYPE_P (type))
123 : 105 : type = sizetype;
124 : 138 : if (comb->n < MAX_AFF_ELTS)
125 : : {
126 : 0 : comb->elts[comb->n].coef = scale;
127 : 0 : comb->elts[comb->n].val = comb->rest;
128 : 0 : comb->rest = NULL_TREE;
129 : 0 : comb->n++;
130 : : }
131 : : else
132 : 138 : comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
133 : : wide_int_to_tree (type, scale));
134 : : }
135 : 38460834 : }
136 : :
137 : : /* Adds ELT * SCALE to COMB. */
138 : :
139 : : void
140 : 31574485 : aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
141 : : {
142 : 31574485 : unsigned i;
143 : 31574485 : tree type;
144 : :
145 : 31574485 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
146 : 31574485 : if (scale == 0)
147 : : return;
148 : :
149 : 44710391 : for (i = 0; i < comb->n; i++)
150 : 21545238 : if (operand_equal_p (comb->elts[i].val, elt, 0))
151 : : {
152 : 8409332 : widest_int new_coef
153 : 8409332 : = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
154 : 8409332 : if (new_coef != 0)
155 : : {
156 : 119513 : comb->elts[i].coef = new_coef;
157 : 119513 : return;
158 : : }
159 : :
160 : 8289819 : comb->n--;
161 : 8289819 : comb->elts[i] = comb->elts[comb->n];
162 : :
163 : 8289819 : if (comb->rest)
164 : : {
165 : 166 : gcc_assert (comb->n == MAX_AFF_ELTS - 1);
166 : 166 : comb->elts[comb->n].coef = 1;
167 : 166 : comb->elts[comb->n].val = comb->rest;
168 : 166 : comb->rest = NULL_TREE;
169 : 166 : comb->n++;
170 : : }
171 : 8289819 : return;
172 : 8409332 : }
173 : 23165153 : if (comb->n < MAX_AFF_ELTS)
174 : : {
175 : 23164597 : comb->elts[comb->n].coef = scale;
176 : 23164597 : comb->elts[comb->n].val = elt;
177 : 23164597 : comb->n++;
178 : 23164597 : return;
179 : : }
180 : :
181 : 556 : type = comb->type;
182 : 556 : if (POINTER_TYPE_P (type))
183 : 274 : type = sizetype;
184 : :
185 : 556 : if (scale == 1)
186 : 420 : elt = fold_convert (type, elt);
187 : : else
188 : 136 : elt = fold_build2 (MULT_EXPR, type,
189 : : fold_convert (type, elt),
190 : : wide_int_to_tree (type, scale));
191 : :
192 : 556 : if (comb->rest)
193 : 14 : comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
194 : : elt);
195 : : else
196 : 542 : comb->rest = elt;
197 : 31574485 : }
198 : :
199 : : /* Adds CST to C. */
200 : :
201 : : static void
202 : 88848844 : aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
203 : : {
204 : 88848844 : c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
205 : 88848844 : }
206 : :
207 : : /* Adds COMB2 to COMB1. */
208 : :
209 : : void
210 : 84886865 : aff_combination_add (aff_tree *comb1, aff_tree *comb2)
211 : : {
212 : 84886865 : unsigned i;
213 : :
214 : 84886865 : aff_combination_add_cst (comb1, comb2->offset);
215 : 190060223 : for (i = 0; i < comb2->n; i++)
216 : 20286493 : aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
217 : 84886865 : if (comb2->rest)
218 : 138 : aff_combination_add_elt (comb1, comb2->rest, 1);
219 : 84886865 : }
220 : :
221 : : /* Converts affine combination COMB to TYPE. */
222 : :
223 : : void
224 : 27875606 : aff_combination_convert (aff_tree *comb, tree type)
225 : : {
226 : 27875606 : unsigned i, j;
227 : 27875606 : tree comb_type = comb->type;
228 : :
229 : 27875606 : if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
230 : : {
231 : 835422 : tree val = fold_convert (type, aff_combination_to_tree (comb));
232 : 835422 : tree_to_aff_combination (val, type, comb);
233 : 835422 : return;
234 : : }
235 : :
236 : 27040184 : comb->type = type;
237 : 27040184 : if (comb->rest && !POINTER_TYPE_P (type))
238 : 170 : comb->rest = fold_convert (type, comb->rest);
239 : :
240 : 27040184 : if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
241 : : return;
242 : :
243 : 122921 : comb->offset = wide_int_ext_for_comb (comb->offset, comb->type);
244 : 158900 : for (i = j = 0; i < comb->n; i++)
245 : : {
246 : 35979 : if (comb->elts[i].coef == 0)
247 : 0 : continue;
248 : 35979 : comb->elts[j].coef = comb->elts[i].coef;
249 : 35979 : comb->elts[j].val = fold_convert (type, comb->elts[i].val);
250 : 35979 : j++;
251 : : }
252 : :
253 : 122921 : comb->n = j;
254 : 122921 : if (comb->n < MAX_AFF_ELTS && comb->rest)
255 : : {
256 : 0 : comb->elts[comb->n].coef = 1;
257 : 0 : comb->elts[comb->n].val = comb->rest;
258 : 0 : comb->rest = NULL_TREE;
259 : 0 : comb->n++;
260 : : }
261 : : }
262 : :
263 : : /* Tries to handle OP0 CODE OP1 as affine combination of parts. Returns
264 : : true when that was successful and returns the combination in COMB. */
265 : :
266 : : static bool
267 : 23646662 : expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
268 : : tree op0, tree op1 = NULL_TREE)
269 : : {
270 : 23646662 : aff_tree tmp;
271 : :
272 : 23646662 : switch (code)
273 : : {
274 : 348667 : case POINTER_PLUS_EXPR:
275 : 348667 : tree_to_aff_combination (op0, type, comb);
276 : 348667 : tree_to_aff_combination (op1, sizetype, &tmp);
277 : 348667 : aff_combination_add (comb, &tmp);
278 : 348667 : return true;
279 : :
280 : 13354720 : case PLUS_EXPR:
281 : 13354720 : case MINUS_EXPR:
282 : 13354720 : tree_to_aff_combination (op0, type, comb);
283 : 13354720 : tree_to_aff_combination (op1, type, &tmp);
284 : 13354720 : if (code == MINUS_EXPR)
285 : 541871 : aff_combination_scale (&tmp, -1);
286 : 13354720 : aff_combination_add (comb, &tmp);
287 : 13354720 : return true;
288 : :
289 : 6849437 : case MULT_EXPR:
290 : 6849437 : if (TREE_CODE (op1) != INTEGER_CST)
291 : : break;
292 : 5945034 : tree_to_aff_combination (op0, type, comb);
293 : 5945034 : aff_combination_scale (comb, wi::to_widest (op1));
294 : 5945034 : return true;
295 : :
296 : 100385 : case NEGATE_EXPR:
297 : 100385 : tree_to_aff_combination (op0, type, comb);
298 : 100385 : aff_combination_scale (comb, -1);
299 : 100385 : return true;
300 : :
301 : 10145 : case BIT_NOT_EXPR:
302 : : /* ~x = -x - 1 */
303 : 10145 : tree_to_aff_combination (op0, type, comb);
304 : 10145 : aff_combination_scale (comb, -1);
305 : 10145 : aff_combination_add_cst (comb, -1);
306 : 10145 : return true;
307 : :
308 : 2983308 : CASE_CONVERT:
309 : 2983308 : {
310 : 2983308 : tree otype = type;
311 : 2983308 : tree inner = op0;
312 : 2983308 : tree itype = TREE_TYPE (inner);
313 : 2983308 : enum tree_code icode = TREE_CODE (inner);
314 : :
315 : : /* STRIP_NOPS */
316 : 2983308 : if (tree_nop_conversion_p (otype, itype))
317 : : {
318 : 11756 : tree_to_aff_combination (op0, type, comb);
319 : 11756 : return true;
320 : : }
321 : :
322 : : /* In principle this is a valid folding, but it isn't necessarily
323 : : an optimization, so do it here and not in fold_unary. */
324 : 2971552 : if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
325 : 226967 : && TREE_CODE (itype) == INTEGER_TYPE
326 : 226967 : && TREE_CODE (otype) == INTEGER_TYPE
327 : 3198515 : && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
328 : : {
329 : 170875 : tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1);
330 : :
331 : : /* If inner type has undefined overflow behavior, fold conversion
332 : : for below two cases:
333 : : (T1)(X *+- CST) -> (T1)X *+- (T1)CST
334 : : (T1)(X + X) -> (T1)X + (T1)X. */
335 : 170875 : if (TYPE_OVERFLOW_UNDEFINED (itype)
336 : 80845 : && (TREE_CODE (op1) == INTEGER_CST
337 : 3951 : || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
338 : : {
339 : 76894 : op0 = fold_convert (otype, op0);
340 : 76894 : op1 = fold_convert (otype, op1);
341 : 82286 : return expr_to_aff_combination (comb, icode, otype, op0, op1);
342 : : }
343 : 93981 : wide_int minv, maxv;
344 : : /* If inner type has wrapping overflow behavior, fold conversion
345 : : for below case:
346 : : (T1)(X *+- CST) -> (T1)X *+- (T1)CST
347 : : if X *+- CST doesn't overflow by range information. */
348 : 93981 : int_range_max vr;
349 : 93981 : if (TYPE_UNSIGNED (itype)
350 : 89800 : && TYPE_OVERFLOW_WRAPS (itype)
351 : 89800 : && TREE_CODE (op1) == INTEGER_CST
352 : 133704 : && get_range_query (cfun)->range_of_expr (vr, op0)
353 : 66852 : && !vr.varying_p ()
354 : 109766 : && !vr.undefined_p ())
355 : : {
356 : 15771 : wide_int minv = vr.lower_bound ();
357 : 15771 : wide_int maxv = vr.upper_bound ();
358 : 15771 : wi::overflow_type overflow = wi::OVF_NONE;
359 : 15771 : signop sign = UNSIGNED;
360 : 15771 : if (icode == PLUS_EXPR)
361 : 11975 : wi::add (maxv, wi::to_wide (op1), sign, &overflow);
362 : 3796 : else if (icode == MULT_EXPR)
363 : 3796 : wi::mul (maxv, wi::to_wide (op1), sign, &overflow);
364 : : else
365 : 0 : wi::sub (minv, wi::to_wide (op1), sign, &overflow);
366 : :
367 : 15771 : if (overflow == wi::OVF_NONE)
368 : : {
369 : 5392 : op0 = fold_convert (otype, op0);
370 : 5392 : op1 = fold_convert (otype, op1);
371 : 5392 : return expr_to_aff_combination (comb, icode, otype, op0,
372 : : op1);
373 : : }
374 : 15771 : }
375 : 93981 : }
376 : : }
377 : : break;
378 : :
379 : 904403 : default:;
380 : : }
381 : :
382 : : return false;
383 : 23646662 : }
384 : :
385 : : /* Splits EXPR into an affine combination of parts. */
386 : :
387 : : void
388 : 142705037 : tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
389 : : {
390 : 142705037 : aff_tree tmp;
391 : 142705037 : enum tree_code code;
392 : 142705037 : tree core, toffset;
393 : 142705037 : poly_int64 bitpos, bitsize, bytepos;
394 : 142705037 : machine_mode mode;
395 : 142705037 : int unsignedp, reversep, volatilep;
396 : :
397 : 142705037 : STRIP_NOPS (expr);
398 : :
399 : 142705037 : code = TREE_CODE (expr);
400 : 142705037 : switch (code)
401 : : {
402 : 20368529 : case POINTER_PLUS_EXPR:
403 : 20368529 : case PLUS_EXPR:
404 : 20368529 : case MINUS_EXPR:
405 : 20368529 : case MULT_EXPR:
406 : 20368529 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
407 : 20368529 : TREE_OPERAND (expr, 1)))
408 : : return;
409 : : break;
410 : :
411 : 109712 : case NEGATE_EXPR:
412 : 109712 : case BIT_NOT_EXPR:
413 : 109712 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0)))
414 : : return;
415 : : break;
416 : :
417 : 2958183 : CASE_CONVERT:
418 : : /* ??? TREE_TYPE (expr) should be equal to type here, but IVOPTS
419 : : calls this with not showing an outer widening cast. */
420 : 2958183 : if (expr_to_aff_combination (comb, code,
421 : 2958183 : TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
422 : : {
423 : 82286 : aff_combination_convert (comb, type);
424 : 82286 : return;
425 : : }
426 : : break;
427 : :
428 : 10146477 : case ADDR_EXPR:
429 : : /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
430 : 10146477 : if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
431 : : {
432 : 596177 : expr = TREE_OPERAND (expr, 0);
433 : 596177 : tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
434 : 596177 : tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
435 : 596177 : aff_combination_add (comb, &tmp);
436 : 596177 : return;
437 : : }
438 : 9550300 : core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
439 : : &toffset, &mode, &unsignedp, &reversep,
440 : : &volatilep);
441 : 19100600 : if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
442 : : break;
443 : 9550300 : aff_combination_const (comb, type, bytepos);
444 : 9550300 : if (TREE_CODE (core) == MEM_REF)
445 : : {
446 : 244273 : tree mem_offset = TREE_OPERAND (core, 1);
447 : 244273 : aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset));
448 : 244273 : core = TREE_OPERAND (core, 0);
449 : : }
450 : : else
451 : 9306027 : core = build_fold_addr_expr (core);
452 : :
453 : 9550300 : if (TREE_CODE (core) == ADDR_EXPR)
454 : 9306027 : aff_combination_add_elt (comb, core, 1);
455 : : else
456 : : {
457 : 244273 : tree_to_aff_combination (core, type, &tmp);
458 : 244273 : aff_combination_add (comb, &tmp);
459 : : }
460 : 9550300 : if (toffset)
461 : : {
462 : 62713 : tree_to_aff_combination (toffset, type, &tmp);
463 : 62713 : aff_combination_add (comb, &tmp);
464 : : }
465 : : return;
466 : :
467 : 109122136 : default:
468 : 109122136 : {
469 : 109122136 : if (poly_int_tree_p (expr))
470 : : {
471 : 71523149 : aff_combination_const (comb, type, wi::to_poly_widest (expr));
472 : 71523149 : return;
473 : : }
474 : : break;
475 : : }
476 : : }
477 : :
478 : 41312888 : aff_combination_elt (comb, type, expr);
479 : 142705037 : }
480 : :
481 : : /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
482 : : combination COMB. */
483 : :
484 : : static tree
485 : 39710239 : add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
486 : : {
487 : 39710239 : enum tree_code code;
488 : :
489 : 39710239 : widest_int scale = wide_int_ext_for_comb (scale_in, type);
490 : :
491 : 39710239 : elt = fold_convert (type, elt);
492 : 39710239 : if (scale == 1)
493 : : {
494 : 33893549 : if (!expr)
495 : : return elt;
496 : :
497 : 13272852 : return fold_build2 (PLUS_EXPR, type, expr, elt);
498 : : }
499 : :
500 : 5816690 : if (scale == -1)
501 : : {
502 : 2707045 : if (!expr)
503 : 1619458 : return fold_build1 (NEGATE_EXPR, type, elt);
504 : :
505 : 1087587 : return fold_build2 (MINUS_EXPR, type, expr, elt);
506 : : }
507 : :
508 : 3109645 : if (!expr)
509 : 1864754 : return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
510 : :
511 : 1244891 : if (wi::neg_p (scale))
512 : : {
513 : 355531 : code = MINUS_EXPR;
514 : 355531 : scale = -scale;
515 : : }
516 : : else
517 : : code = PLUS_EXPR;
518 : :
519 : 1244891 : elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
520 : 1244891 : return fold_build2 (code, type, expr, elt);
521 : 39710239 : }
522 : :
523 : : /* Makes tree from the affine combination COMB. */
524 : :
525 : : tree
526 : 24104909 : aff_combination_to_tree (aff_tree *comb)
527 : : {
528 : 24104909 : tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
529 : 24104909 : unsigned i;
530 : 24104909 : poly_widest_int off;
531 : 24104909 : int sgn;
532 : :
533 : 24104909 : gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
534 : :
535 : 24104909 : i = 0;
536 : 24104909 : if (POINTER_TYPE_P (type))
537 : : {
538 : 110639 : type = sizetype;
539 : 114565 : if (comb->n > 0 && comb->elts[0].coef == 1
540 : 221119 : && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
541 : : {
542 : 106554 : base = comb->elts[0].val;
543 : 106554 : ++i;
544 : : }
545 : : }
546 : :
547 : 39710009 : for (; i < comb->n; i++)
548 : 15605100 : expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);
549 : :
550 : 24104909 : if (comb->rest)
551 : 230 : expr = add_elt_to_tree (expr, type, comb->rest, 1);
552 : :
553 : : /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
554 : : unsigned. */
555 : 24104909 : if (known_lt (comb->offset, 0))
556 : : {
557 : 2152929 : off = -comb->offset;
558 : 2152929 : sgn = -1;
559 : : }
560 : : else
561 : : {
562 : 21951980 : off = comb->offset;
563 : 21951980 : sgn = 1;
564 : : }
565 : 24104909 : expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);
566 : :
567 : 24104909 : if (base)
568 : 106554 : return fold_build_pointer_plus (base, expr);
569 : : else
570 : 23998355 : return fold_convert (comb->type, expr);
571 : 24104909 : }
572 : :
573 : : /* Copies the tree elements of COMB to ensure that they are not shared. */
574 : :
575 : : void
576 : 1807893 : unshare_aff_combination (aff_tree *comb)
577 : : {
578 : 1807893 : unsigned i;
579 : :
580 : 3889019 : for (i = 0; i < comb->n; i++)
581 : 2081126 : comb->elts[i].val = unshare_expr (comb->elts[i].val);
582 : 1807893 : if (comb->rest)
583 : 0 : comb->rest = unshare_expr (comb->rest);
584 : 1807893 : }
585 : :
586 : : /* Remove M-th element from COMB. */
587 : :
588 : : void
589 : 1773762 : aff_combination_remove_elt (aff_tree *comb, unsigned m)
590 : : {
591 : 1773762 : comb->n--;
592 : 1773762 : if (m <= comb->n)
593 : 1773762 : comb->elts[m] = comb->elts[comb->n];
594 : 1773762 : if (comb->rest)
595 : : {
596 : 0 : comb->elts[comb->n].coef = 1;
597 : 0 : comb->elts[comb->n].val = comb->rest;
598 : 0 : comb->rest = NULL_TREE;
599 : 0 : comb->n++;
600 : : }
601 : 1773762 : }
602 : :
603 : : /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only
604 : : C * COEF is added to R. */
605 : :
606 : :
607 : : static void
608 : 3707561 : aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
609 : : aff_tree *r)
610 : : {
611 : 3707561 : unsigned i;
612 : 3707561 : tree aval, type;
613 : :
614 : 4970508 : for (i = 0; i < c->n; i++)
615 : : {
616 : 1262947 : aval = c->elts[i].val;
617 : 1262947 : if (val)
618 : : {
619 : 0 : type = TREE_TYPE (aval);
620 : 0 : aval = fold_build2 (MULT_EXPR, type, aval,
621 : : fold_convert (type, val));
622 : : }
623 : :
624 : 1262947 : aff_combination_add_elt (r, aval, coef * c->elts[i].coef);
625 : : }
626 : :
627 : 3707561 : if (c->rest)
628 : : {
629 : 0 : aval = c->rest;
630 : 0 : if (val)
631 : : {
632 : 0 : type = TREE_TYPE (aval);
633 : 0 : aval = fold_build2 (MULT_EXPR, type, aval,
634 : : fold_convert (type, val));
635 : : }
636 : :
637 : 0 : aff_combination_add_elt (r, aval, coef);
638 : : }
639 : :
640 : 3707561 : if (val)
641 : : {
642 : 0 : if (c->offset.is_constant ())
643 : : /* Access coeffs[0] directly, for efficiency. */
644 : 0 : aff_combination_add_elt (r, val, coef * c->offset.coeffs[0]);
645 : : else
646 : : {
647 : : /* c->offset is polynomial, so multiply VAL rather than COEF
648 : : by it. */
649 : : tree offset = wide_int_to_tree (TREE_TYPE (val), c->offset);
650 : : val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset);
651 : : aff_combination_add_elt (r, val, coef);
652 : : }
653 : : }
654 : : else
655 : 3707561 : aff_combination_add_cst (r, coef * c->offset);
656 : 3707561 : }
657 : :
658 : : /* Multiplies C1 by C2, storing the result to R */
659 : :
660 : : void
661 : 3707561 : aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
662 : : {
663 : 3707561 : unsigned i;
664 : 3707561 : gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
665 : :
666 : 3707561 : aff_combination_zero (r, c1->type);
667 : :
668 : 7415122 : for (i = 0; i < c2->n; i++)
669 : 0 : aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
670 : 3707561 : if (c2->rest)
671 : 0 : aff_combination_add_product (c1, 1, c2->rest, r);
672 : 3707561 : if (c2->offset.is_constant ())
673 : : /* Access coeffs[0] directly, for efficiency. */
674 : 3707561 : aff_combination_add_product (c1, c2->offset.coeffs[0], NULL, r);
675 : : else
676 : : {
677 : : /* c2->offset is polynomial, so do the multiplication in tree form. */
678 : : tree offset = wide_int_to_tree (c2->type, c2->offset);
679 : : aff_combination_add_product (c1, 1, offset, r);
680 : : }
681 : 3707561 : }
682 : :
683 : : /* Returns the element of COMB whose value is VAL, or NULL if no such
684 : : element exists. If IDX is not NULL, it is set to the index of VAL in
685 : : COMB. */
686 : :
687 : : static class aff_comb_elt *
688 : 1215619 : aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
689 : : {
690 : 1215619 : unsigned i;
691 : :
692 : 1531930 : for (i = 0; i < comb->n; i++)
693 : 1221224 : if (operand_equal_p (comb->elts[i].val, val, 0))
694 : : {
695 : 904913 : if (idx)
696 : 0 : *idx = i;
697 : :
698 : 904913 : return &comb->elts[i];
699 : : }
700 : :
701 : : return NULL;
702 : : }
703 : :
704 : : /* Element of the cache that maps ssa name NAME to its expanded form
705 : : as an affine expression EXPANSION. */
706 : :
707 : 246808 : class name_expansion
708 : : {
709 : : public:
710 : : aff_tree expansion;
711 : :
712 : : /* True if the expansion for the name is just being generated. */
713 : : unsigned in_progress : 1;
714 : : };
715 : :
716 : : /* Expands SSA names in COMB recursively. CACHE is used to cache the
717 : : results. */
718 : :
719 : : void
720 : 34369029 : aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
721 : : hash_map<tree, name_expansion *> **cache)
722 : : {
723 : 34369029 : unsigned i;
724 : 103107087 : aff_tree to_add, current, curre;
725 : 34369029 : tree e;
726 : 34369029 : gimple *def;
727 : 34369029 : widest_int scale;
728 : 34369029 : class name_expansion *exp;
729 : :
730 : 34369029 : aff_combination_zero (&to_add, comb->type);
731 : 37897956 : for (i = 0; i < comb->n; i++)
732 : : {
733 : 3528927 : tree type, name;
734 : 3528927 : enum tree_code code;
735 : :
736 : 3528927 : e = comb->elts[i].val;
737 : 3528927 : type = TREE_TYPE (e);
738 : 3528927 : name = e;
739 : : /* Look through some conversions. */
740 : 3354718 : if (CONVERT_EXPR_P (e)
741 : 3528927 : && (TYPE_PRECISION (type)
742 : 174209 : >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
743 : 126867 : name = TREE_OPERAND (e, 0);
744 : 3528927 : if (TREE_CODE (name) != SSA_NAME)
745 : 2816583 : continue;
746 : 3255455 : def = SSA_NAME_DEF_STMT (name);
747 : 3255455 : if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
748 : 1879896 : continue;
749 : :
750 : 1375559 : code = gimple_assign_rhs_code (def);
751 : 1394078 : if (code != SSA_NAME
752 : 1374123 : && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
753 : 1394083 : && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
754 : 18524 : || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
755 : 18519 : continue;
756 : :
757 : : /* We do not know whether the reference retains its value at the
758 : : place where the expansion is used. */
759 : 1357040 : if (TREE_CODE_CLASS (code) == tcc_reference)
760 : 484102 : continue;
761 : :
762 : 872938 : name_expansion **slot = NULL;
763 : 872938 : if (*cache)
764 : 755014 : slot = (*cache)->get (name);
765 : 755014 : exp = slot ? *slot : NULL;
766 : 872938 : if (!exp)
767 : : {
768 : : /* Only bother to handle cases tree_to_aff_combination will. */
769 : 222296 : switch (code)
770 : : {
771 : 102009 : case POINTER_PLUS_EXPR:
772 : 102009 : case PLUS_EXPR:
773 : 102009 : case MINUS_EXPR:
774 : 102009 : case MULT_EXPR:
775 : 102009 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
776 : : gimple_assign_rhs1 (def),
777 : : gimple_assign_rhs2 (def)))
778 : 66399 : continue;
779 : : break;
780 : 818 : case NEGATE_EXPR:
781 : 818 : case BIT_NOT_EXPR:
782 : 818 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
783 : : gimple_assign_rhs1 (def)))
784 : 0 : continue;
785 : : break;
786 : 25125 : CASE_CONVERT:
787 : 25125 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
788 : : gimple_assign_rhs1 (def)))
789 : : /* This makes us always expand conversions which we did
790 : : in the past and makes gcc.dg/tree-ssa/ivopts-lt-2.c
791 : : PASS, eliminating one induction variable in IVOPTs.
792 : : ??? But it is really excessive and we should try
793 : : harder to do without it. */
794 : 26738 : aff_combination_elt (¤t, TREE_TYPE (name),
795 : 13369 : fold_convert (TREE_TYPE (name),
796 : : gimple_assign_rhs1 (def)));
797 : : break;
798 : 149 : case ADDR_EXPR:
799 : 149 : case INTEGER_CST:
800 : 149 : case POLY_INT_CST:
801 : 149 : tree_to_aff_combination (gimple_assign_rhs1 (def),
802 : 149 : TREE_TYPE (name), ¤t);
803 : 149 : break;
804 : 94195 : default:
805 : 94195 : continue;
806 : : }
807 : 61702 : exp = XNEW (class name_expansion);
808 : 61702 : ::new (static_cast<void *> (exp)) name_expansion ();
809 : 61702 : exp->in_progress = 1;
810 : 61702 : if (!*cache)
811 : 26257 : *cache = new hash_map<tree, name_expansion *>;
812 : 61702 : (*cache)->put (name, exp);
813 : 61702 : aff_combination_expand (¤t, cache);
814 : 61702 : exp->expansion = current;
815 : 61702 : exp->in_progress = 0;
816 : : }
817 : : else
818 : : {
819 : : /* Since we follow the definitions in the SSA form, we should not
820 : : enter a cycle unless we pass through a phi node. */
821 : 650642 : gcc_assert (!exp->in_progress);
822 : 650642 : current = exp->expansion;
823 : : }
824 : 712344 : if (!useless_type_conversion_p (comb->type, current.type))
825 : 101447 : aff_combination_convert (¤t, comb->type);
826 : :
827 : : /* Accumulate the new terms to TO_ADD, so that we do not modify
828 : : COMB while traversing it; include the term -coef * E, to remove
829 : : it from COMB. */
830 : 712344 : scale = comb->elts[i].coef;
831 : 712344 : aff_combination_zero (&curre, comb->type);
832 : 712344 : aff_combination_add_elt (&curre, e, -scale);
833 : 712344 : aff_combination_scale (¤t, scale);
834 : 712344 : aff_combination_add (&to_add, ¤t);
835 : 712344 : aff_combination_add (&to_add, &curre);
836 : : }
837 : 34369029 : aff_combination_add (comb, &to_add);
838 : 34369029 : }
839 : :
840 : : /* Similar to tree_to_aff_combination, but follows SSA name definitions
841 : : and expands them recursively. CACHE is used to cache the expansions
842 : : of the ssa names, to avoid exponential time complexity for cases
843 : : like
844 : :
845 : : a1 = a0 + a0;
846 : : a2 = a1 + a1;
847 : : a3 = a2 + a2;
848 : : ... */
849 : :
850 : : void
851 : 34189011 : tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
852 : : hash_map<tree, name_expansion *> **cache)
853 : : {
854 : 34189011 : tree_to_aff_combination (expr, type, comb);
855 : 34189011 : aff_combination_expand (comb, cache);
856 : 34189011 : }
857 : :
858 : : /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
859 : : hash_map::traverse. */
860 : :
861 : : bool
862 : 61702 : free_name_expansion (tree const &, name_expansion **value, void *)
863 : : {
864 : 61702 : (*value)->~name_expansion ();
865 : 61702 : free (*value);
866 : 61702 : return true;
867 : : }
868 : :
869 : : /* Frees memory allocated for the CACHE used by
870 : : tree_to_aff_combination_expand. */
871 : :
872 : : void
873 : 1700881 : free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
874 : : {
875 : 1700881 : if (!*cache)
876 : : return;
877 : :
878 : 87959 : (*cache)->traverse<void *, free_name_expansion> (NULL);
879 : 52514 : delete (*cache);
880 : 26257 : *cache = NULL;
881 : : }
882 : :
883 : : /* If VAL == CST * DIV for any constant CST, returns true.
884 : : and if *MULT_SET is true, additionally compares CST and MULT
885 : : and if they are different, returns false. If true is returned, CST is
886 : : stored to MULT and MULT_SET is set to true unless VAL and DIV are both zero
887 : : in which case neither MULT nor MULT_SET are updated. */
888 : :
889 : : static bool
890 : 17100911 : wide_int_constant_multiple_p (const poly_widest_int &val,
891 : : const poly_widest_int &div,
892 : : bool *mult_set, poly_widest_int *mult)
893 : : {
894 : 17100911 : poly_widest_int cst;
895 : :
896 : 17100911 : if (known_eq (val, 0))
897 : : {
898 : 1195612 : if (known_eq (div, 0))
899 : : return true;
900 : :
901 : 223 : if (*mult_set && maybe_ne (*mult, 0))
902 : 0 : return false;
903 : 223 : *mult_set = true;
904 : 223 : *mult = 0;
905 : 223 : return true;
906 : : }
907 : :
908 : 15905299 : if (maybe_eq (div, 0))
909 : : return false;
910 : :
911 : 15904174 : if (!multiple_p (val, div, &cst))
912 : : return false;
913 : :
914 : 14131608 : if (*mult_set && maybe_ne (*mult, cst))
915 : : return false;
916 : :
917 : 14111477 : *mult_set = true;
918 : 14111477 : *mult = cst;
919 : 14111477 : return true;
920 : 17100911 : }
921 : :
922 : : /* Returns true if VAL = X * DIV for some constant X. If this is the case,
923 : : X is stored to MULT. */
924 : :
925 : : bool
926 : 17018653 : aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
927 : : poly_widest_int *mult)
928 : : {
929 : 17018653 : bool mult_set = false;
930 : 17018653 : unsigned i;
931 : :
932 : 17018653 : if (val->n == 0 && known_eq (val->offset, 0))
933 : : {
934 : 46329 : *mult = 0;
935 : 46329 : return true;
936 : : }
937 : 16972324 : if (val->n != div->n)
938 : : return false;
939 : :
940 : 16195998 : if (val->rest || div->rest)
941 : : return false;
942 : :
943 : 16195998 : if (!wide_int_constant_multiple_p (val->offset, div->offset,
944 : : &mult_set, mult))
945 : : return false;
946 : :
947 : 15307089 : for (i = 0; i < div->n; i++)
948 : : {
949 : 1215619 : class aff_comb_elt *elt
950 : 1215619 : = aff_combination_find_elt (val, div->elts[i].val, NULL);
951 : 1215619 : if (!elt)
952 : : return false;
953 : 904913 : if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
954 : : &mult_set, mult))
955 : : return false;
956 : : }
957 : :
958 : 14091470 : gcc_assert (mult_set);
959 : : return true;
960 : : }
961 : :
962 : : /* Prints the affine VAL to the FILE. */
963 : :
964 : : static void
965 : 0 : print_aff (FILE *file, aff_tree *val)
966 : : {
967 : 0 : unsigned i;
968 : 0 : signop sgn = TYPE_SIGN (val->type);
969 : 0 : if (POINTER_TYPE_P (val->type))
970 : 0 : sgn = SIGNED;
971 : 0 : fprintf (file, "{\n type = ");
972 : 0 : print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
973 : 0 : fprintf (file, "\n offset = ");
974 : 0 : print_dec (val->offset, file, sgn);
975 : 0 : if (val->n > 0)
976 : : {
977 : 0 : fprintf (file, "\n elements = {\n");
978 : 0 : for (i = 0; i < val->n; i++)
979 : : {
980 : 0 : fprintf (file, " [%d] = ", i);
981 : 0 : print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
982 : :
983 : 0 : fprintf (file, " * ");
984 : 0 : print_dec (val->elts[i].coef, file, sgn);
985 : 0 : if (i != val->n - 1)
986 : 0 : fprintf (file, ", \n");
987 : : }
988 : 0 : fprintf (file, "\n }");
989 : : }
990 : 0 : if (val->rest)
991 : : {
992 : 0 : fprintf (file, "\n rest = ");
993 : 0 : print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
994 : : }
995 : 0 : fprintf (file, "\n}");
996 : 0 : }
997 : :
998 : : /* Prints the affine VAL to the standard error, used for debugging. */
999 : :
1000 : : DEBUG_FUNCTION void
1001 : 0 : debug_aff (aff_tree *val)
1002 : : {
1003 : 0 : print_aff (stderr, val);
1004 : 0 : fprintf (stderr, "\n");
1005 : 0 : }
1006 : :
1007 : : /* Computes address of the reference REF in ADDR. The size of the accessed
1008 : : location is stored to SIZE. Returns the ultimate containing object to
1009 : : which REF refers. */
1010 : :
1011 : : tree
1012 : 5885514 : get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1013 : : {
1014 : 5885514 : poly_int64 bitsize, bitpos;
1015 : 5885514 : tree toff;
1016 : 5885514 : machine_mode mode;
1017 : 5885514 : int uns, rev, vol;
1018 : 5885514 : aff_tree tmp;
1019 : 5885514 : tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1020 : : &uns, &rev, &vol);
1021 : 5885514 : tree base_addr = build_fold_addr_expr (base);
1022 : :
1023 : : /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
1024 : :
1025 : 5885514 : tree_to_aff_combination (base_addr, sizetype, addr);
1026 : :
1027 : 5885514 : if (toff)
1028 : : {
1029 : 189920 : tree_to_aff_combination (toff, sizetype, &tmp);
1030 : 189920 : aff_combination_add (addr, &tmp);
1031 : : }
1032 : :
1033 : 5885514 : aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos));
1034 : 5885514 : aff_combination_add (addr, &tmp);
1035 : :
1036 : 5885514 : *size = bits_to_bytes_round_up (bitsize);
1037 : :
1038 : 11771028 : return base;
1039 : 5885514 : }
1040 : :
1041 : : /* Returns true if a region of size SIZE1 at position 0 and a region of
1042 : : size SIZE2 at position DIFF cannot overlap. */
1043 : :
1044 : : bool
1045 : 2942849 : aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
1046 : : const poly_widest_int &size2)
1047 : : {
1048 : : /* Unless the difference is a constant, we fail. */
1049 : 2942849 : if (diff->n != 0)
1050 : : return false;
1051 : :
1052 : 1952550 : if (!ordered_p (diff->offset, 0))
1053 : : return false;
1054 : :
1055 : 1952550 : if (maybe_lt (diff->offset, 0))
1056 : : {
1057 : : /* The second object is before the first one, we succeed if the last
1058 : : element of the second object is before the start of the first one. */
1059 : 249035 : return known_le (diff->offset + size2, 0);
1060 : : }
1061 : : else
1062 : : {
1063 : : /* We succeed if the second object starts after the first one ends. */
1064 : 1703515 : return known_le (size1, diff->offset);
1065 : : }
1066 : : }
1067 : :
|
