1/* Operations with affine combinations of trees.
2 Copyright (C) 2005-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
38static widest_int
39wide_int_ext_for_comb (const widest_int &cst, tree type)
40{
41 return wi::sext (x: cst, TYPE_PRECISION (type));
42}
43
44/* Likewise for polynomial offsets. */
45
46static poly_widest_int
47wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
48{
49 return wi::sext (a: cst, TYPE_PRECISION (type));
50}
51
52/* Initializes affine combination COMB so that its value is zero in TYPE. */
53
54static void
55aff_combination_zero (aff_tree *comb, tree type)
56{
57 int i;
58 comb->type = type;
59 comb->offset = 0;
60 comb->n = 0;
61 for (i = 0; i < MAX_AFF_ELTS; i++)
62 comb->elts[i].coef = 0;
63 comb->rest = NULL_TREE;
64}
65
66/* Sets COMB to CST. */
67
68void
69aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
70{
71 aff_combination_zero (comb, type);
72 comb->offset = wide_int_ext_for_comb (cst, type: comb->type);;
73}
74
75/* Sets COMB to single element ELT. */
76
77void
78aff_combination_elt (aff_tree *comb, tree type, tree elt)
79{
80 aff_combination_zero (comb, type);
81
82 comb->n = 1;
83 comb->elts[0].val = elt;
84 comb->elts[0].coef = 1;
85}
86
87/* Scales COMB by SCALE. */
88
89void
90aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
91{
92 unsigned i, j;
93
94 widest_int scale = wide_int_ext_for_comb (cst: scale_in, type: comb->type);
95 if (scale == 1)
96 return;
97
98 if (scale == 0)
99 {
100 aff_combination_zero (comb, type: comb->type);
101 return;
102 }
103
104 comb->offset = wide_int_ext_for_comb (cst: scale * comb->offset, type: comb->type);
105 for (i = 0, j = 0; i < comb->n; i++)
106 {
107 widest_int new_coef
108 = wide_int_ext_for_comb (cst: scale * comb->elts[i].coef, type: comb->type);
109 /* A coefficient may become zero due to overflow. Remove the zero
110 elements. */
111 if (new_coef == 0)
112 continue;
113 comb->elts[j].coef = new_coef;
114 comb->elts[j].val = comb->elts[i].val;
115 j++;
116 }
117 comb->n = j;
118
119 if (comb->rest)
120 {
121 tree type = comb->type;
122 if (POINTER_TYPE_P (type))
123 type = sizetype;
124 if (comb->n < MAX_AFF_ELTS)
125 {
126 comb->elts[comb->n].coef = scale;
127 comb->elts[comb->n].val = comb->rest;
128 comb->rest = NULL_TREE;
129 comb->n++;
130 }
131 else
132 comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
133 wide_int_to_tree (type, scale));
134 }
135}
136
137/* Adds ELT * SCALE to COMB. */
138
139void
140aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
141{
142 unsigned i;
143 tree type;
144
145 widest_int scale = wide_int_ext_for_comb (cst: scale_in, type: comb->type);
146 if (scale == 0)
147 return;
148
149 for (i = 0; i < comb->n; i++)
150 if (operand_equal_p (comb->elts[i].val, elt, flags: 0))
151 {
152 widest_int new_coef
153 = wide_int_ext_for_comb (cst: comb->elts[i].coef + scale, type: comb->type);
154 if (new_coef != 0)
155 {
156 comb->elts[i].coef = new_coef;
157 return;
158 }
159
160 comb->n--;
161 comb->elts[i] = comb->elts[comb->n];
162
163 if (comb->rest)
164 {
165 gcc_assert (comb->n == MAX_AFF_ELTS - 1);
166 comb->elts[comb->n].coef = 1;
167 comb->elts[comb->n].val = comb->rest;
168 comb->rest = NULL_TREE;
169 comb->n++;
170 }
171 return;
172 }
173 if (comb->n < MAX_AFF_ELTS)
174 {
175 comb->elts[comb->n].coef = scale;
176 comb->elts[comb->n].val = elt;
177 comb->n++;
178 return;
179 }
180
181 type = comb->type;
182 if (POINTER_TYPE_P (type))
183 type = sizetype;
184
185 if (scale == 1)
186 elt = fold_convert (type, elt);
187 else
188 elt = fold_build2 (MULT_EXPR, type,
189 fold_convert (type, elt),
190 wide_int_to_tree (type, scale));
191
192 if (comb->rest)
193 comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
194 elt);
195 else
196 comb->rest = elt;
197}
198
199/* Adds CST to C. */
200
201static void
202aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
203{
204 c->offset = wide_int_ext_for_comb (cst: c->offset + cst, type: c->type);
205}
206
207/* Adds COMB2 to COMB1. */
208
209void
210aff_combination_add (aff_tree *comb1, aff_tree *comb2)
211{
212 unsigned i;
213
214 aff_combination_add_cst (c: comb1, cst: comb2->offset);
215 for (i = 0; i < comb2->n; i++)
216 aff_combination_add_elt (comb: comb1, elt: comb2->elts[i].val, scale_in: comb2->elts[i].coef);
217 if (comb2->rest)
218 aff_combination_add_elt (comb: comb1, elt: comb2->rest, scale_in: 1);
219}
220
221/* Converts affine combination COMB to TYPE. */
222
223void
224aff_combination_convert (aff_tree *comb, tree type)
225{
226 unsigned i, j;
227 tree comb_type = comb->type;
228
229 if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
230 {
231 tree val = fold_convert (type, aff_combination_to_tree (comb));
232 tree_to_aff_combination (val, type, comb);
233 return;
234 }
235
236 comb->type = type;
237 if (comb->rest && !POINTER_TYPE_P (type))
238 comb->rest = fold_convert (type, comb->rest);
239
240 if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
241 return;
242
243 comb->offset = wide_int_ext_for_comb (cst: comb->offset, type: comb->type);
244 for (i = j = 0; i < comb->n; i++)
245 {
246 if (comb->elts[i].coef == 0)
247 continue;
248 comb->elts[j].coef = comb->elts[i].coef;
249 comb->elts[j].val = fold_convert (type, comb->elts[i].val);
250 j++;
251 }
252
253 comb->n = j;
254 if (comb->n < MAX_AFF_ELTS && comb->rest)
255 {
256 comb->elts[comb->n].coef = 1;
257 comb->elts[comb->n].val = comb->rest;
258 comb->rest = NULL_TREE;
259 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
266static bool
267expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
268 tree op0, tree op1 = NULL_TREE)
269{
270 aff_tree tmp;
271
272 switch (code)
273 {
274 case POINTER_PLUS_EXPR:
275 tree_to_aff_combination (op0, type, comb);
276 tree_to_aff_combination (op1, sizetype, &tmp);
277 aff_combination_add (comb1: comb, comb2: &tmp);
278 return true;
279
280 case PLUS_EXPR:
281 case MINUS_EXPR:
282 tree_to_aff_combination (op0, type, comb);
283 tree_to_aff_combination (op1, type, &tmp);
284 if (code == MINUS_EXPR)
285 aff_combination_scale (comb: &tmp, scale_in: -1);
286 aff_combination_add (comb1: comb, comb2: &tmp);
287 return true;
288
289 case MULT_EXPR:
290 if (TREE_CODE (op1) != INTEGER_CST)
291 break;
292 tree_to_aff_combination (op0, type, comb);
293 aff_combination_scale (comb, scale_in: wi::to_widest (t: op1));
294 return true;
295
296 case NEGATE_EXPR:
297 tree_to_aff_combination (op0, type, comb);
298 aff_combination_scale (comb, scale_in: -1);
299 return true;
300
301 case BIT_NOT_EXPR:
302 /* ~x = -x - 1 */
303 tree_to_aff_combination (op0, type, comb);
304 aff_combination_scale (comb, scale_in: -1);
305 aff_combination_add_cst (c: comb, cst: -1);
306 return true;
307
308 CASE_CONVERT:
309 {
310 tree otype = type;
311 tree inner = op0;
312 tree itype = TREE_TYPE (inner);
313 enum tree_code icode = TREE_CODE (inner);
314
315 /* STRIP_NOPS */
316 if (tree_nop_conversion_p (otype, itype))
317 {
318 tree_to_aff_combination (op0, type, comb);
319 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 if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
325 && TREE_CODE (itype) == INTEGER_TYPE
326 && TREE_CODE (otype) == INTEGER_TYPE
327 && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
328 {
329 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 if (TYPE_OVERFLOW_UNDEFINED (itype)
336 && (TREE_CODE (op1) == INTEGER_CST
337 || (icode == PLUS_EXPR && operand_equal_p (op0, op1, flags: 0))))
338 {
339 op0 = fold_convert (otype, op0);
340 op1 = fold_convert (otype, op1);
341 return expr_to_aff_combination (comb, code: icode, type: otype, op0, op1);
342 }
343 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 value_range vr;
349 if (TYPE_UNSIGNED (itype)
350 && TYPE_OVERFLOW_WRAPS (itype)
351 && TREE_CODE (op1) == INTEGER_CST
352 && get_range_query (cfun)->range_of_expr (r&: vr, expr: op0)
353 && !vr.varying_p ()
354 && !vr.undefined_p ())
355 {
356 wide_int minv = vr.lower_bound ();
357 wide_int maxv = vr.upper_bound ();
358 wi::overflow_type overflow = wi::OVF_NONE;
359 signop sign = UNSIGNED;
360 if (icode == PLUS_EXPR)
361 wi::add (x: maxv, y: wi::to_wide (t: op1), sgn: sign, overflow: &overflow);
362 else if (icode == MULT_EXPR)
363 wi::mul (x: maxv, y: wi::to_wide (t: op1), sgn: sign, overflow: &overflow);
364 else
365 wi::sub (x: minv, y: wi::to_wide (t: op1), sgn: sign, overflow: &overflow);
366
367 if (overflow == wi::OVF_NONE)
368 {
369 op0 = fold_convert (otype, op0);
370 op1 = fold_convert (otype, op1);
371 return expr_to_aff_combination (comb, code: icode, type: otype, op0,
372 op1);
373 }
374 }
375 }
376 }
377 break;
378
379 default:;
380 }
381
382 return false;
383}
384
385/* Splits EXPR into an affine combination of parts. */
386
387void
388tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
389{
390 aff_tree tmp;
391 enum tree_code code;
392 tree core, toffset;
393 poly_int64 bitpos, bitsize, bytepos;
394 machine_mode mode;
395 int unsignedp, reversep, volatilep;
396
397 STRIP_NOPS (expr);
398
399 code = TREE_CODE (expr);
400 switch (code)
401 {
402 case POINTER_PLUS_EXPR:
403 case PLUS_EXPR:
404 case MINUS_EXPR:
405 case MULT_EXPR:
406 if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
407 TREE_OPERAND (expr, 1)))
408 return;
409 break;
410
411 case NEGATE_EXPR:
412 case BIT_NOT_EXPR:
413 if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0)))
414 return;
415 break;
416
417 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 if (expr_to_aff_combination (comb, code,
421 TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
422 {
423 aff_combination_convert (comb, type);
424 return;
425 }
426 break;
427
428 case ADDR_EXPR:
429 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
430 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
431 {
432 expr = TREE_OPERAND (expr, 0);
433 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
434 tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, comb: &tmp);
435 aff_combination_add (comb1: comb, comb2: &tmp);
436 return;
437 }
438 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
439 &toffset, &mode, &unsignedp, &reversep,
440 &volatilep);
441 if (!multiple_p (a: bitpos, BITS_PER_UNIT, multiple: &bytepos))
442 break;
443 aff_combination_const (comb, type, cst: bytepos);
444 if (TREE_CODE (core) == MEM_REF)
445 {
446 tree mem_offset = TREE_OPERAND (core, 1);
447 aff_combination_add_cst (c: comb, cst: wi::to_poly_widest (t: mem_offset));
448 core = TREE_OPERAND (core, 0);
449 }
450 else
451 core = build_fold_addr_expr (core);
452
453 if (TREE_CODE (core) == ADDR_EXPR)
454 aff_combination_add_elt (comb, elt: core, scale_in: 1);
455 else
456 {
457 tree_to_aff_combination (expr: core, type, comb: &tmp);
458 aff_combination_add (comb1: comb, comb2: &tmp);
459 }
460 if (toffset)
461 {
462 tree_to_aff_combination (expr: toffset, type, comb: &tmp);
463 aff_combination_add (comb1: comb, comb2: &tmp);
464 }
465 return;
466
467 default:
468 {
469 if (poly_int_tree_p (t: expr))
470 {
471 aff_combination_const (comb, type, cst: wi::to_poly_widest (t: expr));
472 return;
473 }
474 break;
475 }
476 }
477
478 aff_combination_elt (comb, type, elt: expr);
479}
480
481/* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
482 combination COMB. */
483
484static tree
485add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
486{
487 enum tree_code code;
488
489 widest_int scale = wide_int_ext_for_comb (cst: scale_in, type);
490
491 elt = fold_convert (type, elt);
492 if (scale == 1)
493 {
494 if (!expr)
495 return elt;
496
497 return fold_build2 (PLUS_EXPR, type, expr, elt);
498 }
499
500 if (scale == -1)
501 {
502 if (!expr)
503 return fold_build1 (NEGATE_EXPR, type, elt);
504
505 return fold_build2 (MINUS_EXPR, type, expr, elt);
506 }
507
508 if (!expr)
509 return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
510
511 if (wi::neg_p (x: scale))
512 {
513 code = MINUS_EXPR;
514 scale = -scale;
515 }
516 else
517 code = PLUS_EXPR;
518
519 elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
520 return fold_build2 (code, type, expr, elt);
521}
522
523/* Makes tree from the affine combination COMB. */
524
525tree
526aff_combination_to_tree (aff_tree *comb)
527{
528 tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
529 unsigned i;
530 poly_widest_int off;
531 int sgn;
532
533 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
534
535 i = 0;
536 if (POINTER_TYPE_P (type))
537 {
538 type = sizetype;
539 if (comb->n > 0 && comb->elts[0].coef == 1
540 && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
541 {
542 base = comb->elts[0].val;
543 ++i;
544 }
545 }
546
547 for (; i < comb->n; i++)
548 expr = add_elt_to_tree (expr, type, elt: comb->elts[i].val, scale_in: comb->elts[i].coef);
549
550 if (comb->rest)
551 expr = add_elt_to_tree (expr, type, elt: comb->rest, scale_in: 1);
552
553 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
554 unsigned. */
555 if (known_lt (comb->offset, 0))
556 {
557 off = -comb->offset;
558 sgn = -1;
559 }
560 else
561 {
562 off = comb->offset;
563 sgn = 1;
564 }
565 expr = add_elt_to_tree (expr, type, elt: wide_int_to_tree (type, cst: off), scale_in: sgn);
566
567 if (base)
568 return fold_build_pointer_plus (base, expr);
569 else
570 return fold_convert (comb->type, expr);
571}
572
573/* Copies the tree elements of COMB to ensure that they are not shared. */
574
575void
576unshare_aff_combination (aff_tree *comb)
577{
578 unsigned i;
579
580 for (i = 0; i < comb->n; i++)
581 comb->elts[i].val = unshare_expr (comb->elts[i].val);
582 if (comb->rest)
583 comb->rest = unshare_expr (comb->rest);
584}
585
586/* Remove M-th element from COMB. */
587
588void
589aff_combination_remove_elt (aff_tree *comb, unsigned m)
590{
591 comb->n--;
592 if (m <= comb->n)
593 comb->elts[m] = comb->elts[comb->n];
594 if (comb->rest)
595 {
596 comb->elts[comb->n].coef = 1;
597 comb->elts[comb->n].val = comb->rest;
598 comb->rest = NULL_TREE;
599 comb->n++;
600 }
601}
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
607static void
608aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
609 aff_tree *r)
610{
611 unsigned i;
612 tree aval, type;
613
614 for (i = 0; i < c->n; i++)
615 {
616 aval = c->elts[i].val;
617 if (val)
618 {
619 type = TREE_TYPE (aval);
620 aval = fold_build2 (MULT_EXPR, type, aval,
621 fold_convert (type, val));
622 }
623
624 aff_combination_add_elt (comb: r, elt: aval, scale_in: coef * c->elts[i].coef);
625 }
626
627 if (c->rest)
628 {
629 aval = c->rest;
630 if (val)
631 {
632 type = TREE_TYPE (aval);
633 aval = fold_build2 (MULT_EXPR, type, aval,
634 fold_convert (type, val));
635 }
636
637 aff_combination_add_elt (comb: r, elt: aval, scale_in: coef);
638 }
639
640 if (val)
641 {
642 if (c->offset.is_constant ())
643 /* Access coeffs[0] directly, for efficiency. */
644 aff_combination_add_elt (comb: r, elt: val, scale_in: 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), cst: c->offset);
650 val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset);
651 aff_combination_add_elt (comb: r, elt: val, scale_in: coef);
652 }
653 }
654 else
655 aff_combination_add_cst (c: r, cst: coef * c->offset);
656}
657
658/* Multiplies C1 by C2, storing the result to R */
659
660void
661aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
662{
663 unsigned i;
664 gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
665
666 aff_combination_zero (comb: r, type: c1->type);
667
668 for (i = 0; i < c2->n; i++)
669 aff_combination_add_product (c: c1, coef: c2->elts[i].coef, val: c2->elts[i].val, r);
670 if (c2->rest)
671 aff_combination_add_product (c: c1, coef: 1, val: c2->rest, r);
672 if (c2->offset.is_constant ())
673 /* Access coeffs[0] directly, for efficiency. */
674 aff_combination_add_product (c: c1, coef: 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 (type: c2->type, cst: c2->offset);
679 aff_combination_add_product (c: c1, coef: 1, val: offset, r);
680 }
681}
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
687static class aff_comb_elt *
688aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
689{
690 unsigned i;
691
692 for (i = 0; i < comb->n; i++)
693 if (operand_equal_p (comb->elts[i].val, val, flags: 0))
694 {
695 if (idx)
696 *idx = i;
697
698 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
707class name_expansion
708{
709public:
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
719void
720aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
721 hash_map<tree, name_expansion *> **cache)
722{
723 unsigned i;
724 aff_tree to_add, current, curre;
725 tree e;
726 gimple *def;
727 widest_int scale;
728 class name_expansion *exp;
729
730 aff_combination_zero (comb: &to_add, type: comb->type);
731 for (i = 0; i < comb->n; i++)
732 {
733 tree type, name;
734 enum tree_code code;
735
736 e = comb->elts[i].val;
737 type = TREE_TYPE (e);
738 name = e;
739 /* Look through some conversions. */
740 if (CONVERT_EXPR_P (e)
741 && (TYPE_PRECISION (type)
742 >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
743 name = TREE_OPERAND (e, 0);
744 if (TREE_CODE (name) != SSA_NAME)
745 continue;
746 def = SSA_NAME_DEF_STMT (name);
747 if (!is_gimple_assign (gs: def) || gimple_assign_lhs (gs: def) != name)
748 continue;
749
750 code = gimple_assign_rhs_code (gs: def);
751 if (code != SSA_NAME
752 && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
753 && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
754 || !is_gimple_min_invariant (gimple_assign_rhs1 (gs: def))))
755 continue;
756
757 /* We do not know whether the reference retains its value at the
758 place where the expansion is used. */
759 if (TREE_CODE_CLASS (code) == tcc_reference)
760 continue;
761
762 name_expansion **slot = NULL;
763 if (*cache)
764 slot = (*cache)->get (k: name);
765 exp = slot ? *slot : NULL;
766 if (!exp)
767 {
768 /* Only bother to handle cases tree_to_aff_combination will. */
769 switch (code)
770 {
771 case POINTER_PLUS_EXPR:
772 case PLUS_EXPR:
773 case MINUS_EXPR:
774 case MULT_EXPR:
775 if (!expr_to_aff_combination (comb: &current, code, TREE_TYPE (name),
776 op0: gimple_assign_rhs1 (gs: def),
777 op1: gimple_assign_rhs2 (gs: def)))
778 continue;
779 break;
780 case NEGATE_EXPR:
781 case BIT_NOT_EXPR:
782 if (!expr_to_aff_combination (comb: &current, code, TREE_TYPE (name),
783 op0: gimple_assign_rhs1 (gs: def)))
784 continue;
785 break;
786 CASE_CONVERT:
787 if (!expr_to_aff_combination (comb: &current, code, TREE_TYPE (name),
788 op0: gimple_assign_rhs1 (gs: 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 aff_combination_elt (comb: &current, TREE_TYPE (name),
795 fold_convert (TREE_TYPE (name),
796 gimple_assign_rhs1 (def)));
797 break;
798 case ADDR_EXPR:
799 case INTEGER_CST:
800 case POLY_INT_CST:
801 tree_to_aff_combination (expr: gimple_assign_rhs1 (gs: def),
802 TREE_TYPE (name), comb: &current);
803 break;
804 default:
805 continue;
806 }
807 exp = XNEW (class name_expansion);
808 ::new (static_cast<void *> (exp)) name_expansion ();
809 exp->in_progress = 1;
810 if (!*cache)
811 *cache = new hash_map<tree, name_expansion *>;
812 (*cache)->put (k: name, v: exp);
813 aff_combination_expand (comb: &current, cache);
814 exp->expansion = current;
815 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 gcc_assert (!exp->in_progress);
822 current = exp->expansion;
823 }
824 if (!useless_type_conversion_p (comb->type, current.type))
825 aff_combination_convert (comb: &current, type: 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 scale = comb->elts[i].coef;
831 aff_combination_zero (comb: &curre, type: comb->type);
832 aff_combination_add_elt (comb: &curre, elt: e, scale_in: -scale);
833 aff_combination_scale (comb: &current, scale_in: scale);
834 aff_combination_add (comb1: &to_add, comb2: &current);
835 aff_combination_add (comb1: &to_add, comb2: &curre);
836 }
837 aff_combination_add (comb1: comb, comb2: &to_add);
838}
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
850void
851tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
852 hash_map<tree, name_expansion *> **cache)
853{
854 tree_to_aff_combination (expr, type, comb);
855 aff_combination_expand (comb, cache);
856}
857
858/* Frees memory occupied by struct name_expansion in *VALUE. Callback for
859 hash_map::traverse. */
860
861bool
862free_name_expansion (tree const &, name_expansion **value, void *)
863{
864 (*value)->~name_expansion ();
865 free (ptr: *value);
866 return true;
867}
868
869/* Frees memory allocated for the CACHE used by
870 tree_to_aff_combination_expand. */
871
872void
873free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
874{
875 if (!*cache)
876 return;
877
878 (*cache)->traverse<void *, free_name_expansion> (NULL);
879 delete (*cache);
880 *cache = NULL;
881}
882
883/* If VAL != CST * DIV for any constant CST, returns false.
884 Otherwise, if *MULT_SET is true, additionally compares CST and MULT,
885 and if they are different, returns false. Finally, if neither of these
886 two cases occur, true is returned, and CST is stored to MULT and MULT_SET
887 is set to true. */
888
889static bool
890wide_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 poly_widest_int rem, cst;
895
896 if (known_eq (val, 0))
897 {
898 if (*mult_set && maybe_ne (a: *mult, b: 0))
899 return false;
900 *mult_set = true;
901 *mult = 0;
902 return true;
903 }
904
905 if (maybe_eq (a: div, b: 0))
906 return false;
907
908 if (!multiple_p (a: val, b: div, multiple: &cst))
909 return false;
910
911 if (*mult_set && maybe_ne (a: *mult, b: cst))
912 return false;
913
914 *mult_set = true;
915 *mult = cst;
916 return true;
917}
918
919/* Returns true if VAL = X * DIV for some constant X. If this is the case,
920 X is stored to MULT. */
921
922bool
923aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
924 poly_widest_int *mult)
925{
926 bool mult_set = false;
927 unsigned i;
928
929 if (val->n == 0 && known_eq (val->offset, 0))
930 {
931 *mult = 0;
932 return true;
933 }
934 if (val->n != div->n)
935 return false;
936
937 if (val->rest || div->rest)
938 return false;
939
940 if (!wide_int_constant_multiple_p (val: val->offset, div: div->offset,
941 mult_set: &mult_set, mult))
942 return false;
943
944 for (i = 0; i < div->n; i++)
945 {
946 class aff_comb_elt *elt
947 = aff_combination_find_elt (comb: val, val: div->elts[i].val, NULL);
948 if (!elt)
949 return false;
950 if (!wide_int_constant_multiple_p (val: elt->coef, div: div->elts[i].coef,
951 mult_set: &mult_set, mult))
952 return false;
953 }
954
955 gcc_assert (mult_set);
956 return true;
957}
958
959/* Prints the affine VAL to the FILE. */
960
961static void
962print_aff (FILE *file, aff_tree *val)
963{
964 unsigned i;
965 signop sgn = TYPE_SIGN (val->type);
966 if (POINTER_TYPE_P (val->type))
967 sgn = SIGNED;
968 fprintf (stream: file, format: "{\n type = ");
969 print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
970 fprintf (stream: file, format: "\n offset = ");
971 print_dec (value: val->offset, file, sgn);
972 if (val->n > 0)
973 {
974 fprintf (stream: file, format: "\n elements = {\n");
975 for (i = 0; i < val->n; i++)
976 {
977 fprintf (stream: file, format: " [%d] = ", i);
978 print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
979
980 fprintf (stream: file, format: " * ");
981 print_dec (wi: val->elts[i].coef, file, sgn);
982 if (i != val->n - 1)
983 fprintf (stream: file, format: ", \n");
984 }
985 fprintf (stream: file, format: "\n }");
986 }
987 if (val->rest)
988 {
989 fprintf (stream: file, format: "\n rest = ");
990 print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
991 }
992 fprintf (stream: file, format: "\n}");
993}
994
995/* Prints the affine VAL to the standard error, used for debugging. */
996
997DEBUG_FUNCTION void
998debug_aff (aff_tree *val)
999{
1000 print_aff (stderr, val);
1001 fprintf (stderr, format: "\n");
1002}
1003
1004/* Computes address of the reference REF in ADDR. The size of the accessed
1005 location is stored to SIZE. Returns the ultimate containing object to
1006 which REF refers. */
1007
1008tree
1009get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1010{
1011 poly_int64 bitsize, bitpos;
1012 tree toff;
1013 machine_mode mode;
1014 int uns, rev, vol;
1015 aff_tree tmp;
1016 tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1017 &uns, &rev, &vol);
1018 tree base_addr = build_fold_addr_expr (base);
1019
1020 /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
1021
1022 tree_to_aff_combination (expr: base_addr, sizetype, comb: addr);
1023
1024 if (toff)
1025 {
1026 tree_to_aff_combination (expr: toff, sizetype, comb: &tmp);
1027 aff_combination_add (comb1: addr, comb2: &tmp);
1028 }
1029
1030 aff_combination_const (comb: &tmp, sizetype, bits_to_bytes_round_down (bitpos));
1031 aff_combination_add (comb1: addr, comb2: &tmp);
1032
1033 *size = bits_to_bytes_round_up (bitsize);
1034
1035 return base;
1036}
1037
1038/* Returns true if a region of size SIZE1 at position 0 and a region of
1039 size SIZE2 at position DIFF cannot overlap. */
1040
1041bool
1042aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
1043 const poly_widest_int &size2)
1044{
1045 /* Unless the difference is a constant, we fail. */
1046 if (diff->n != 0)
1047 return false;
1048
1049 if (!ordered_p (a: diff->offset, b: 0))
1050 return false;
1051
1052 if (maybe_lt (a: diff->offset, b: 0))
1053 {
1054 /* The second object is before the first one, we succeed if the last
1055 element of the second object is before the start of the first one. */
1056 return known_le (diff->offset + size2, 0);
1057 }
1058 else
1059 {
1060 /* We succeed if the second object starts after the first one ends. */
1061 return known_le (size1, diff->offset);
1062 }
1063}
1064
1065

source code of gcc/tree-affine.cc