Line data Source code
1 : /* Operations with affine combinations of trees.
2 : Copyright (C) 2005-2026 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 163646807 : wide_int_ext_for_comb (const widest_int &cst, tree type)
40 : {
41 163646807 : return wi::sext (cst, TYPE_PRECISION (type));
42 : }
43 :
44 : /* Likewise for polynomial offsets. */
45 :
46 : static poly_widest_int
47 253346873 : wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
48 : {
49 253346873 : 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 204282315 : aff_combination_zero (aff_tree *comb, tree type)
56 : {
57 204282315 : int i;
58 204282315 : comb->type = type;
59 204282315 : comb->offset = 0;
60 204282315 : comb->n = 0;
61 1838540835 : for (i = 0; i < MAX_AFF_ELTS; i++)
62 1634258520 : comb->elts[i].coef = 0;
63 204282315 : comb->rest = NULL_TREE;
64 204282315 : }
65 :
66 : /* Sets COMB to CST. */
67 :
68 : void
69 114217133 : aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
70 : {
71 114217133 : aff_combination_zero (comb, type);
72 114217133 : comb->offset = wide_int_ext_for_comb (cst, comb->type);;
73 114217133 : }
74 :
75 : /* Sets COMB to single element ELT. */
76 :
77 : void
78 47000224 : aff_combination_elt (aff_tree *comb, tree type, tree elt)
79 : {
80 47000224 : aff_combination_zero (comb, type);
81 :
82 47000224 : comb->n = 1;
83 47000224 : comb->elts[0].val = elt;
84 47000224 : comb->elts[0].coef = 1;
85 47000224 : }
86 :
87 : /* Scales COMB by SCALE. */
88 :
89 : void
90 42458961 : aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
91 : {
92 42458961 : unsigned i, j;
93 :
94 42458961 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
95 42458961 : if (scale == 1)
96 : return;
97 :
98 30712638 : if (scale == 0)
99 : {
100 182 : aff_combination_zero (comb, comb->type);
101 182 : return;
102 : }
103 :
104 30712456 : comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
105 56284277 : for (i = 0, j = 0; i < comb->n; i++)
106 : {
107 25571821 : widest_int new_coef
108 25571821 : = 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 25571821 : if (new_coef == 0)
112 2 : continue;
113 25571819 : comb->elts[j].coef = new_coef;
114 25571819 : comb->elts[j].val = comb->elts[i].val;
115 25571819 : j++;
116 25571821 : }
117 30712456 : comb->n = j;
118 :
119 30712456 : if (comb->rest)
120 : {
121 110 : tree type = comb->type;
122 110 : if (POINTER_TYPE_P (type))
123 98 : type = sizetype;
124 110 : 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 110 : comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
133 : wide_int_to_tree (type, scale));
134 : }
135 42458961 : }
136 :
137 : /* Adds ELT * SCALE to COMB. */
138 :
139 : void
140 45120486 : aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
141 : {
142 45120486 : unsigned i;
143 45120486 : tree type;
144 :
145 45120486 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
146 45120486 : if (scale == 0)
147 : return;
148 :
149 61301993 : for (i = 0; i < comb->n; i++)
150 25800079 : if (operand_equal_p (comb->elts[i].val, elt, 0))
151 : {
152 9618572 : widest_int new_coef
153 9618572 : = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
154 9618572 : if (new_coef != 0)
155 : {
156 162114 : comb->elts[i].coef = new_coef;
157 162114 : return;
158 : }
159 :
160 9456458 : comb->n--;
161 9456458 : comb->elts[i] = comb->elts[comb->n];
162 :
163 9456458 : if (comb->rest)
164 : {
165 187 : gcc_assert (comb->n == MAX_AFF_ELTS - 1);
166 187 : comb->elts[comb->n].coef = 1;
167 187 : comb->elts[comb->n].val = comb->rest;
168 187 : comb->rest = NULL_TREE;
169 187 : comb->n++;
170 : }
171 9456458 : return;
172 9618572 : }
173 35501914 : if (comb->n < MAX_AFF_ELTS)
174 : {
175 35501246 : comb->elts[comb->n].coef = scale;
176 35501246 : comb->elts[comb->n].val = elt;
177 35501246 : comb->n++;
178 35501246 : return;
179 : }
180 :
181 668 : type = comb->type;
182 668 : if (POINTER_TYPE_P (type))
183 474 : type = sizetype;
184 :
185 668 : if (scale == 1)
186 266 : elt = fold_convert (type, elt);
187 : else
188 402 : elt = fold_build2 (MULT_EXPR, type,
189 : fold_convert (type, elt),
190 : wide_int_to_tree (type, scale));
191 :
192 668 : if (comb->rest)
193 107 : comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
194 : elt);
195 : else
196 561 : comb->rest = elt;
197 45120486 : }
198 :
199 : /* Adds CST to C. */
200 :
201 : static void
202 108289402 : aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
203 : {
204 108289402 : c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
205 108289402 : }
206 :
207 : /* Adds COMB2 to COMB1. */
208 :
209 : void
210 104016154 : aff_combination_add (aff_tree *comb1, aff_tree *comb2)
211 : {
212 104016154 : unsigned i;
213 :
214 104016154 : aff_combination_add_cst (comb1, comb2->offset);
215 231585934 : for (i = 0; i < comb2->n; i++)
216 23553626 : aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
217 104016154 : if (comb2->rest)
218 124 : aff_combination_add_elt (comb1, comb2->rest, 1);
219 104016154 : }
220 :
221 : /* Converts affine combination COMB to TYPE. */
222 :
223 : void
224 31853299 : aff_combination_convert (aff_tree *comb, tree type)
225 : {
226 31853299 : unsigned i, j;
227 31853299 : tree comb_type = comb->type;
228 :
229 31853299 : if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
230 : {
231 898753 : tree val = fold_convert (type, aff_combination_to_tree (comb));
232 898753 : tree_to_aff_combination (val, type, comb);
233 898753 : return;
234 : }
235 :
236 30954546 : comb->type = type;
237 30954546 : if (comb->rest && !POINTER_TYPE_P (type))
238 200 : comb->rest = fold_convert (type, comb->rest);
239 :
240 30954546 : if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
241 : return;
242 :
243 127882 : comb->offset = wide_int_ext_for_comb (comb->offset, comb->type);
244 178987 : for (i = j = 0; i < comb->n; i++)
245 : {
246 51105 : if (comb->elts[i].coef == 0)
247 0 : continue;
248 51105 : comb->elts[j].coef = comb->elts[i].coef;
249 51105 : comb->elts[j].val = fold_convert (type, comb->elts[i].val);
250 51105 : j++;
251 : }
252 :
253 127882 : comb->n = j;
254 127882 : 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 28621348 : expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
268 : tree op0, tree op1 = NULL_TREE)
269 : {
270 28621348 : aff_tree tmp;
271 :
272 28621348 : switch (code)
273 : {
274 6555641 : case POINTER_PLUS_EXPR:
275 6555641 : tree_to_aff_combination (op0, type, comb);
276 6555641 : tree_to_aff_combination (op1, sizetype, &tmp);
277 6555641 : aff_combination_add (comb, &tmp);
278 6555641 : return true;
279 :
280 10564366 : case PLUS_EXPR:
281 10564366 : case MINUS_EXPR:
282 10564366 : tree_to_aff_combination (op0, type, comb);
283 10564366 : tree_to_aff_combination (op1, type, &tmp);
284 10564366 : if (code == MINUS_EXPR)
285 742725 : aff_combination_scale (&tmp, -1);
286 10564366 : aff_combination_add (comb, &tmp);
287 10564366 : return true;
288 :
289 7840967 : case MULT_EXPR:
290 7840967 : if (TREE_CODE (op1) != INTEGER_CST)
291 : break;
292 6826867 : tree_to_aff_combination (op0, type, comb);
293 6826867 : aff_combination_scale (comb, wi::to_widest (op1));
294 6826867 : return true;
295 :
296 127360 : case NEGATE_EXPR:
297 127360 : tree_to_aff_combination (op0, type, comb);
298 127360 : aff_combination_scale (comb, -1);
299 127360 : return true;
300 :
301 7711 : case BIT_NOT_EXPR:
302 : /* ~x = -x - 1 */
303 7711 : tree_to_aff_combination (op0, type, comb);
304 7711 : aff_combination_scale (comb, -1);
305 7711 : aff_combination_add_cst (comb, -1);
306 7711 : return true;
307 :
308 3525303 : CASE_CONVERT:
309 3525303 : {
310 3525303 : tree otype = type;
311 3525303 : tree inner = op0;
312 3525303 : tree itype = TREE_TYPE (inner);
313 3525303 : enum tree_code icode = TREE_CODE (inner);
314 :
315 : /* STRIP_NOPS */
316 3525303 : if (tree_nop_conversion_p (otype, itype))
317 : {
318 13331 : tree_to_aff_combination (op0, type, comb);
319 13331 : 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 3511972 : if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
325 328074 : && TREE_CODE (itype) == INTEGER_TYPE
326 328062 : && TREE_CODE (otype) == INTEGER_TYPE
327 3840030 : && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
328 : {
329 240853 : 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 240853 : if (TYPE_OVERFLOW_UNDEFINED (itype)
336 135541 : && (TREE_CODE (op1) == INTEGER_CST
337 10290 : || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
338 : {
339 125251 : op0 = fold_convert (otype, op0);
340 125251 : op1 = fold_convert (otype, op1);
341 130759 : return expr_to_aff_combination (comb, icode, otype, op0, op1);
342 : }
343 115602 : 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 115602 : int_range_max vr;
349 115602 : if (TYPE_UNSIGNED (itype)
350 105049 : && TYPE_OVERFLOW_WRAPS (itype)
351 105049 : && TREE_CODE (op1) == INTEGER_CST
352 151140 : && get_range_query (cfun)->range_of_expr (vr, op0)
353 75570 : && !vr.varying_p ()
354 131403 : && !vr.undefined_p ())
355 : {
356 15787 : wide_int minv = vr.lower_bound ();
357 15787 : wide_int maxv = vr.upper_bound ();
358 15787 : wi::overflow_type overflow = wi::OVF_NONE;
359 15787 : signop sign = UNSIGNED;
360 15787 : if (icode == PLUS_EXPR)
361 11921 : wi::add (maxv, wi::to_wide (op1), sign, &overflow);
362 3866 : else if (icode == MULT_EXPR)
363 3866 : wi::mul (maxv, wi::to_wide (op1), sign, &overflow);
364 : else
365 0 : wi::sub (minv, wi::to_wide (op1), sign, &overflow);
366 :
367 15787 : if (overflow == wi::OVF_NONE)
368 : {
369 5508 : op0 = fold_convert (otype, op0);
370 5508 : op1 = fold_convert (otype, op1);
371 5508 : return expr_to_aff_combination (comb, icode, otype, op0,
372 : op1);
373 : }
374 15787 : }
375 115602 : }
376 : }
377 : break;
378 :
379 1014100 : default:;
380 : }
381 :
382 : return false;
383 28621348 : }
384 :
385 : /* Splits EXPR into an affine combination of parts. */
386 :
387 : void
388 170102599 : tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
389 : {
390 170102599 : aff_tree tmp;
391 170102599 : enum tree_code code;
392 170102599 : tree core, toffset;
393 170102599 : poly_int64 bitpos, bitsize, bytepos;
394 170102599 : machine_mode mode;
395 170102599 : int unsignedp, reversep, volatilep;
396 :
397 170102599 : STRIP_NOPS (expr);
398 :
399 170102599 : code = TREE_CODE (expr);
400 170102599 : switch (code)
401 : {
402 24718559 : case POINTER_PLUS_EXPR:
403 24718559 : case PLUS_EXPR:
404 24718559 : case MINUS_EXPR:
405 24718559 : case MULT_EXPR:
406 24718559 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
407 24718559 : TREE_OPERAND (expr, 1)))
408 : return;
409 : break;
410 :
411 134368 : case NEGATE_EXPR:
412 134368 : case BIT_NOT_EXPR:
413 134368 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0)))
414 : return;
415 : break;
416 :
417 3496665 : 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 3496665 : if (expr_to_aff_combination (comb, code,
421 3496665 : TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
422 : {
423 130759 : aff_combination_convert (comb, type);
424 130759 : return;
425 : }
426 : break;
427 :
428 20031253 : case ADDR_EXPR:
429 : /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
430 20031253 : if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
431 : {
432 612330 : expr = TREE_OPERAND (expr, 0);
433 612330 : tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
434 612330 : tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
435 612330 : aff_combination_add (comb, &tmp);
436 612330 : return;
437 : }
438 19418923 : core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
439 : &toffset, &mode, &unsignedp, &reversep,
440 : &volatilep);
441 38837846 : if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
442 : break;
443 19418923 : aff_combination_const (comb, type, bytepos);
444 19418923 : if (TREE_CODE (core) == MEM_REF)
445 : {
446 225847 : tree mem_offset = TREE_OPERAND (core, 1);
447 225847 : aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset));
448 225847 : core = TREE_OPERAND (core, 0);
449 : }
450 : else
451 19193076 : core = build_fold_addr_expr (core);
452 :
453 19418923 : if (TREE_CODE (core) == ADDR_EXPR)
454 19193076 : aff_combination_add_elt (comb, core, 1);
455 : else
456 : {
457 225847 : tree_to_aff_combination (core, type, &tmp);
458 225847 : aff_combination_add (comb, &tmp);
459 : }
460 19418923 : if (toffset)
461 : {
462 62876 : tree_to_aff_combination (toffset, type, &tmp);
463 62876 : aff_combination_add (comb, &tmp);
464 : }
465 : return;
466 :
467 121721754 : default:
468 121721754 : {
469 121721754 : if (poly_int_tree_p (expr))
470 : {
471 79044419 : aff_combination_const (comb, type, wi::to_poly_widest (expr));
472 79044419 : return;
473 : }
474 : break;
475 : }
476 : }
477 :
478 46984917 : aff_combination_elt (comb, type, expr);
479 170102599 : }
480 :
481 : /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
482 : combination COMB. */
483 :
484 : static tree
485 40876967 : add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
486 : {
487 40876967 : enum tree_code code;
488 :
489 40876967 : widest_int scale = wide_int_ext_for_comb (scale_in, type);
490 :
491 40876967 : elt = fold_convert (type, elt);
492 40876967 : if (scale == 1)
493 : {
494 34051980 : if (!expr)
495 : return elt;
496 :
497 11793510 : return fold_build2 (PLUS_EXPR, type, expr, elt);
498 : }
499 :
500 6824987 : if (scale == -1)
501 : {
502 3237126 : if (!expr)
503 1937683 : return fold_build1 (NEGATE_EXPR, type, elt);
504 :
505 1299443 : return fold_build2 (MINUS_EXPR, type, expr, elt);
506 : }
507 :
508 3587861 : if (!expr)
509 1636810 : return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
510 :
511 1951051 : if (wi::neg_p (scale))
512 : {
513 355009 : code = MINUS_EXPR;
514 355009 : scale = -scale;
515 : }
516 : else
517 : code = PLUS_EXPR;
518 :
519 1951051 : elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
520 1951051 : return fold_build2 (code, type, expr, elt);
521 40876967 : }
522 :
523 : /* Makes tree from the affine combination COMB. */
524 :
525 : tree
526 25832963 : aff_combination_to_tree (aff_tree *comb)
527 : {
528 25832963 : tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
529 25832963 : unsigned i;
530 25832963 : poly_widest_int off;
531 25832963 : int sgn;
532 :
533 25832963 : gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
534 :
535 25832963 : i = 0;
536 25832963 : if (POINTER_TYPE_P (type))
537 : {
538 2345644 : type = sizetype;
539 2382544 : if (comb->n > 0 && comb->elts[0].coef == 1
540 4689537 : && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
541 : {
542 2306993 : base = comb->elts[0].val;
543 2306993 : ++i;
544 : }
545 : }
546 :
547 40876726 : for (; i < comb->n; i++)
548 15043763 : expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);
549 :
550 25832963 : if (comb->rest)
551 241 : 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 25832963 : if (known_lt (comb->offset, 0))
556 : {
557 2550858 : off = -comb->offset;
558 2550858 : sgn = -1;
559 : }
560 : else
561 : {
562 23282105 : off = comb->offset;
563 23282105 : sgn = 1;
564 : }
565 25832963 : expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);
566 :
567 25832963 : if (base)
568 2306993 : return fold_build_pointer_plus (base, expr);
569 : else
570 23525970 : return fold_convert (comb->type, expr);
571 25832963 : }
572 :
573 : /* Copies the tree elements of COMB to ensure that they are not shared. */
574 :
575 : void
576 1818686 : unshare_aff_combination (aff_tree *comb)
577 : {
578 1818686 : unsigned i;
579 :
580 3897386 : for (i = 0; i < comb->n; i++)
581 2078700 : comb->elts[i].val = unshare_expr (comb->elts[i].val);
582 1818686 : if (comb->rest)
583 0 : comb->rest = unshare_expr (comb->rest);
584 1818686 : }
585 :
586 : /* Remove M-th element from COMB. */
587 :
588 : void
589 1791193 : aff_combination_remove_elt (aff_tree *comb, unsigned m)
590 : {
591 1791193 : comb->n--;
592 1791193 : if (m <= comb->n)
593 1791193 : comb->elts[m] = comb->elts[comb->n];
594 1791193 : 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 1791193 : }
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 4039690 : aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
609 : aff_tree *r)
610 : {
611 4039690 : unsigned i;
612 4039690 : tree aval, type;
613 :
614 5618372 : for (i = 0; i < c->n; i++)
615 : {
616 1578682 : aval = c->elts[i].val;
617 1578682 : 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 1578682 : aff_combination_add_elt (r, aval, coef * c->elts[i].coef);
625 : }
626 :
627 4039690 : 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 4039690 : 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 4039690 : aff_combination_add_cst (r, coef * c->offset);
656 4039690 : }
657 :
658 : /* Multiplies C1 by C2, storing the result to R */
659 :
660 : void
661 4039690 : aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
662 : {
663 4039690 : unsigned i;
664 4039690 : gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
665 :
666 4039690 : aff_combination_zero (r, c1->type);
667 :
668 8079380 : for (i = 0; i < c2->n; i++)
669 0 : aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
670 4039690 : if (c2->rest)
671 0 : aff_combination_add_product (c1, 1, c2->rest, r);
672 4039690 : if (c2->offset.is_constant ())
673 : /* Access coeffs[0] directly, for efficiency. */
674 4039690 : 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 4039690 : }
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 1302435 : aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
689 : {
690 1302435 : unsigned i;
691 :
692 1609421 : for (i = 0; i < comb->n; i++)
693 1307593 : if (operand_equal_p (comb->elts[i].val, val, 0))
694 : {
695 1000607 : if (idx)
696 0 : *idx = i;
697 :
698 1000607 : 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 275168 : 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 38236757 : aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
721 : hash_map<tree, name_expansion *> **cache)
722 : {
723 38236757 : unsigned i;
724 114710271 : aff_tree to_add, current, curre;
725 38236757 : tree e;
726 38236757 : gimple *def;
727 38236757 : widest_int scale;
728 38236757 : class name_expansion *exp;
729 :
730 38236757 : aff_combination_zero (&to_add, comb->type);
731 42079268 : for (i = 0; i < comb->n; i++)
732 : {
733 3842511 : tree type, name;
734 3842511 : enum tree_code code;
735 :
736 3842511 : e = comb->elts[i].val;
737 3842511 : type = TREE_TYPE (e);
738 3842511 : name = e;
739 : /* Look through some conversions. */
740 3622531 : if (CONVERT_EXPR_P (e)
741 3842511 : && (TYPE_PRECISION (type)
742 219980 : >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
743 164867 : name = TREE_OPERAND (e, 0);
744 3842511 : if (TREE_CODE (name) != SSA_NAME)
745 3054182 : continue;
746 3529781 : def = SSA_NAME_DEF_STMT (name);
747 3529781 : if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
748 1980932 : continue;
749 :
750 1548849 : code = gimple_assign_rhs_code (def);
751 1569481 : if (code != SSA_NAME
752 1548349 : && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
753 1569485 : && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
754 20636 : || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
755 20632 : continue;
756 :
757 : /* We do not know whether the reference retains its value at the
758 : place where the expansion is used. */
759 1528217 : if (TREE_CODE_CLASS (code) == tcc_reference)
760 557081 : continue;
761 :
762 971136 : name_expansion **slot = NULL;
763 971136 : if (*cache)
764 832865 : slot = (*cache)->get (name);
765 832865 : exp = slot ? *slot : NULL;
766 971136 : if (!exp)
767 : {
768 : /* Only bother to handle cases tree_to_aff_combination will. */
769 251599 : switch (code)
770 : {
771 111656 : case POINTER_PLUS_EXPR:
772 111656 : case PLUS_EXPR:
773 111656 : case MINUS_EXPR:
774 111656 : case MULT_EXPR:
775 111656 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
776 : gimple_assign_rhs1 (def),
777 : gimple_assign_rhs2 (def)))
778 72424 : continue;
779 : break;
780 703 : case NEGATE_EXPR:
781 703 : case BIT_NOT_EXPR:
782 703 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
783 : gimple_assign_rhs1 (def)))
784 0 : continue;
785 : break;
786 28638 : CASE_CONVERT:
787 28638 : 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 30614 : aff_combination_elt (¤t, TREE_TYPE (name),
795 15307 : fold_convert (TREE_TYPE (name),
796 : gimple_assign_rhs1 (def)));
797 : break;
798 219 : case ADDR_EXPR:
799 219 : case INTEGER_CST:
800 219 : case POLY_INT_CST:
801 219 : tree_to_aff_combination (gimple_assign_rhs1 (def),
802 219 : TREE_TYPE (name), ¤t);
803 219 : break;
804 110383 : default:
805 110383 : continue;
806 : }
807 68792 : exp = XNEW (class name_expansion);
808 68792 : ::new (static_cast<void *> (exp)) name_expansion ();
809 68792 : exp->in_progress = 1;
810 68792 : if (!*cache)
811 29634 : *cache = new hash_map<tree, name_expansion *>;
812 68792 : (*cache)->put (name, exp);
813 68792 : aff_combination_expand (¤t, cache);
814 68792 : exp->expansion = current;
815 68792 : 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 719537 : gcc_assert (!exp->in_progress);
822 719537 : current = exp->expansion;
823 : }
824 788329 : if (!useless_type_conversion_p (comb->type, current.type))
825 118197 : 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 788329 : scale = comb->elts[i].coef;
831 788329 : aff_combination_zero (&curre, comb->type);
832 788329 : aff_combination_add_elt (&curre, e, -scale);
833 788329 : aff_combination_scale (¤t, scale);
834 788329 : aff_combination_add (&to_add, ¤t);
835 788329 : aff_combination_add (&to_add, &curre);
836 : }
837 38236757 : aff_combination_add (comb, &to_add);
838 38236757 : }
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 38052895 : tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
852 : hash_map<tree, name_expansion *> **cache)
853 : {
854 38052895 : tree_to_aff_combination (expr, type, comb);
855 38052895 : aff_combination_expand (comb, cache);
856 38052895 : }
857 :
858 : /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
859 : hash_map::traverse. */
860 :
861 : bool
862 68792 : free_name_expansion (tree const &, name_expansion **value, void *)
863 : {
864 68792 : (*value)->~name_expansion ();
865 68792 : free (*value);
866 68792 : return true;
867 : }
868 :
869 : /* Frees memory allocated for the CACHE used by
870 : tree_to_aff_combination_expand. */
871 :
872 : void
873 1729664 : free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
874 : {
875 1729664 : if (!*cache)
876 : return;
877 :
878 98426 : (*cache)->traverse<void *, free_name_expansion> (NULL);
879 59268 : delete (*cache);
880 29634 : *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 18994209 : 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 18994209 : poly_widest_int cst;
895 :
896 18994209 : if (known_eq (val, 0))
897 : {
898 1279968 : if (known_eq (div, 0))
899 : return true;
900 :
901 258 : if (*mult_set && maybe_ne (*mult, 0))
902 0 : return false;
903 258 : *mult_set = true;
904 258 : *mult = 0;
905 258 : return true;
906 : }
907 :
908 17714241 : if (maybe_eq (div, 0))
909 : return false;
910 :
911 17712798 : if (!multiple_p (val, div, &cst))
912 : return false;
913 :
914 15622447 : if (*mult_set && maybe_ne (*mult, cst))
915 : return false;
916 :
917 15599842 : *mult_set = true;
918 15599842 : *mult = cst;
919 15599842 : return true;
920 18994209 : }
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 18943326 : aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
927 : poly_widest_int *mult)
928 : {
929 18943326 : bool mult_set = false;
930 18943326 : unsigned i;
931 :
932 18943326 : if (val->n == 0 && known_eq (val->offset, 0))
933 : {
934 51774 : *mult = 0;
935 51774 : return true;
936 : }
937 18891552 : if (val->n != div->n)
938 : return false;
939 :
940 17993602 : if (val->rest || div->rest)
941 : return false;
942 :
943 17993602 : if (!wide_int_constant_multiple_p (val->offset, div->offset,
944 : &mult_set, mult))
945 : return false;
946 :
947 16879810 : for (i = 0; i < div->n; i++)
948 : {
949 1302435 : class aff_comb_elt *elt
950 1302435 : = aff_combination_find_elt (val, div->elts[i].val, NULL);
951 1302435 : if (!elt)
952 : return false;
953 1000607 : if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
954 : &mult_set, mult))
955 : return false;
956 : }
957 :
958 15577375 : 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 15528181 : get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1013 : {
1014 15528181 : poly_int64 bitsize, bitpos;
1015 15528181 : tree toff;
1016 15528181 : machine_mode mode;
1017 15528181 : int uns, rev, vol;
1018 15528181 : aff_tree tmp;
1019 15528181 : tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1020 : &uns, &rev, &vol);
1021 15528181 : tree base_addr = build_fold_addr_expr (base);
1022 :
1023 : /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
1024 :
1025 15528181 : tree_to_aff_combination (base_addr, sizetype, addr);
1026 :
1027 15528181 : if (toff)
1028 : {
1029 159810 : tree_to_aff_combination (toff, sizetype, &tmp);
1030 159810 : aff_combination_add (addr, &tmp);
1031 : }
1032 :
1033 15528181 : aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos));
1034 15528181 : aff_combination_add (addr, &tmp);
1035 :
1036 15528181 : *size = bits_to_bytes_round_up (bitsize);
1037 :
1038 31056362 : return base;
1039 15528181 : }
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 2779335 : 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 2779335 : if (diff->n != 0)
1050 : return false;
1051 :
1052 1816856 : if (!ordered_p (diff->offset, 0))
1053 : return false;
1054 :
1055 1816856 : 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 231732 : 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 1585124 : return known_le (size1, diff->offset);
1065 : }
1066 : }
1067 :
|
