1 /* Operations with affine combinations of trees.
2 Copyright (C) 2005-2022 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
wide_int_ext_for_comb(const widest_int & cst,tree type)39 wide_int_ext_for_comb (const widest_int &cst, tree type)
40 {
41 return wi::sext (cst, TYPE_PRECISION (type));
42 }
43
44 /* Likewise for polynomial offsets. */
45
46 static poly_widest_int
wide_int_ext_for_comb(const poly_widest_int & cst,tree type)47 wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
48 {
49 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
aff_combination_zero(aff_tree * comb,tree type)55 aff_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
68 void
aff_combination_const(aff_tree * comb,tree type,const poly_widest_int & cst)69 aff_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, comb->type);;
73 }
74
75 /* Sets COMB to single element ELT. */
76
77 void
aff_combination_elt(aff_tree * comb,tree type,tree elt)78 aff_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
89 void
aff_combination_scale(aff_tree * comb,const widest_int & scale_in)90 aff_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 (scale_in, comb->type);
95 if (scale == 1)
96 return;
97
98 if (scale == 0)
99 {
100 aff_combination_zero (comb, comb->type);
101 return;
102 }
103
104 comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
105 for (i = 0, j = 0; i < comb->n; i++)
106 {
107 widest_int new_coef
108 = 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 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
139 void
aff_combination_add_elt(aff_tree * comb,tree elt,const widest_int & scale_in)140 aff_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 (scale_in, 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, 0))
151 {
152 widest_int new_coef
153 = wide_int_ext_for_comb (comb->elts[i].coef + scale, 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
201 static void
aff_combination_add_cst(aff_tree * c,const poly_widest_int & cst)202 aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
203 {
204 c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
205 }
206
207 /* Adds COMB2 to COMB1. */
208
209 void
aff_combination_add(aff_tree * comb1,aff_tree * comb2)210 aff_combination_add (aff_tree *comb1, aff_tree *comb2)
211 {
212 unsigned i;
213
214 aff_combination_add_cst (comb1, comb2->offset);
215 for (i = 0; i < comb2->n; i++)
216 aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
217 if (comb2->rest)
218 aff_combination_add_elt (comb1, comb2->rest, 1);
219 }
220
221 /* Converts affine combination COMB to TYPE. */
222
223 void
aff_combination_convert(aff_tree * comb,tree type)224 aff_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 (comb->offset, 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
266 static bool
expr_to_aff_combination(aff_tree * comb,tree_code code,tree type,tree op0,tree op1=NULL_TREE)267 expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
268 tree op0, tree op1 = NULL_TREE)
269 {
270 aff_tree tmp;
271 poly_int64 bitpos, bitsize, bytepos;
272
273 switch (code)
274 {
275 case POINTER_PLUS_EXPR:
276 tree_to_aff_combination (op0, type, comb);
277 tree_to_aff_combination (op1, sizetype, &tmp);
278 aff_combination_add (comb, &tmp);
279 return true;
280
281 case PLUS_EXPR:
282 case MINUS_EXPR:
283 tree_to_aff_combination (op0, type, comb);
284 tree_to_aff_combination (op1, type, &tmp);
285 if (code == MINUS_EXPR)
286 aff_combination_scale (&tmp, -1);
287 aff_combination_add (comb, &tmp);
288 return true;
289
290 case MULT_EXPR:
291 if (TREE_CODE (op1) != INTEGER_CST)
292 break;
293 tree_to_aff_combination (op0, type, comb);
294 aff_combination_scale (comb, wi::to_widest (op1));
295 return true;
296
297 case NEGATE_EXPR:
298 tree_to_aff_combination (op0, type, comb);
299 aff_combination_scale (comb, -1);
300 return true;
301
302 case BIT_NOT_EXPR:
303 /* ~x = -x - 1 */
304 tree_to_aff_combination (op0, type, comb);
305 aff_combination_scale (comb, -1);
306 aff_combination_add_cst (comb, -1);
307 return true;
308
309 CASE_CONVERT:
310 {
311 tree otype = type;
312 tree inner = op0;
313 tree itype = TREE_TYPE (inner);
314 enum tree_code icode = TREE_CODE (inner);
315
316 /* STRIP_NOPS */
317 if (tree_nop_conversion_p (otype, itype))
318 {
319 tree_to_aff_combination (op0, type, comb);
320 return true;
321 }
322
323 /* In principle this is a valid folding, but it isn't necessarily
324 an optimization, so do it here and not in fold_unary. */
325 if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
326 && TREE_CODE (itype) == INTEGER_TYPE
327 && TREE_CODE (otype) == INTEGER_TYPE
328 && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
329 {
330 tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1);
331
332 /* If inner type has undefined overflow behavior, fold conversion
333 for below two cases:
334 (T1)(X *+- CST) -> (T1)X *+- (T1)CST
335 (T1)(X + X) -> (T1)X + (T1)X. */
336 if (TYPE_OVERFLOW_UNDEFINED (itype)
337 && (TREE_CODE (op1) == INTEGER_CST
338 || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
339 {
340 op0 = fold_convert (otype, op0);
341 op1 = fold_convert (otype, op1);
342 return expr_to_aff_combination (comb, icode, otype, op0, op1);
343 }
344 wide_int minv, maxv;
345 /* If inner type has wrapping overflow behavior, fold conversion
346 for below case:
347 (T1)(X *+- CST) -> (T1)X *+- (T1)CST
348 if X *+- CST doesn't overflow by range information. */
349 value_range vr;
350 if (TYPE_UNSIGNED (itype)
351 && TYPE_OVERFLOW_WRAPS (itype)
352 && TREE_CODE (op1) == INTEGER_CST
353 && get_range_query (cfun)->range_of_expr (vr, op0)
354 && vr.kind () == VR_RANGE)
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 (maxv, wi::to_wide (op1), sign, &overflow);
362 else if (icode == MULT_EXPR)
363 wi::mul (maxv, wi::to_wide (op1), sign, &overflow);
364 else
365 wi::sub (minv, wi::to_wide (op1), sign, &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, icode, 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
387 void
tree_to_aff_combination(tree expr,tree type,aff_tree * comb)388 tree_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, &tmp);
435 aff_combination_add (comb, &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 (bitpos, BITS_PER_UNIT, &bytepos))
442 break;
443 aff_combination_const (comb, type, bytepos);
444 if (TREE_CODE (core) == MEM_REF)
445 {
446 tree mem_offset = TREE_OPERAND (core, 1);
447 aff_combination_add_cst (comb, wi::to_poly_widest (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, core, 1);
455 else
456 {
457 tree_to_aff_combination (core, type, &tmp);
458 aff_combination_add (comb, &tmp);
459 }
460 if (toffset)
461 {
462 tree_to_aff_combination (toffset, type, &tmp);
463 aff_combination_add (comb, &tmp);
464 }
465 return;
466
467 default:
468 {
469 if (poly_int_tree_p (expr))
470 {
471 aff_combination_const (comb, type, wi::to_poly_widest (expr));
472 return;
473 }
474 break;
475 }
476 }
477
478 aff_combination_elt (comb, type, expr);
479 }
480
481 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
482 combination COMB. */
483
484 static tree
add_elt_to_tree(tree expr,tree type,tree elt,const widest_int & scale_in)485 add_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 (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 (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
525 tree
aff_combination_to_tree(aff_tree * comb)526 aff_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, comb->elts[i].val, comb->elts[i].coef);
549
550 if (comb->rest)
551 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 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, wide_int_to_tree (type, off), 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
575 void
unshare_aff_combination(aff_tree * comb)576 unshare_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
588 void
aff_combination_remove_elt(aff_tree * comb,unsigned m)589 aff_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
607 static void
aff_combination_add_product(aff_tree * c,const widest_int & coef,tree val,aff_tree * r)608 aff_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 (r, aval, 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 (r, aval, 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 (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 aff_combination_add_cst (r, coef * c->offset);
656 }
657
658 /* Multiplies C1 by C2, storing the result to R */
659
660 void
aff_combination_mult(aff_tree * c1,aff_tree * c2,aff_tree * r)661 aff_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 (r, c1->type);
667
668 for (i = 0; i < c2->n; i++)
669 aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
670 if (c2->rest)
671 aff_combination_add_product (c1, 1, c2->rest, r);
672 if (c2->offset.is_constant ())
673 /* Access coeffs[0] directly, for efficiency. */
674 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 }
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 *
aff_combination_find_elt(aff_tree * comb,tree val,unsigned * idx)688 aff_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, 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
707 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
aff_combination_expand(aff_tree * comb ATTRIBUTE_UNUSED,hash_map<tree,name_expansion * > ** cache)720 aff_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 (&to_add, 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 (def) || gimple_assign_lhs (def) != name)
748 continue;
749
750 code = gimple_assign_rhs_code (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 (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 (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 (¤t, code, TREE_TYPE (name),
776 gimple_assign_rhs1 (def),
777 gimple_assign_rhs2 (def)))
778 continue;
779 break;
780 case NEGATE_EXPR:
781 case BIT_NOT_EXPR:
782 if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
783 gimple_assign_rhs1 (def)))
784 continue;
785 break;
786 CASE_CONVERT:
787 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 aff_combination_elt (¤t, 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 (gimple_assign_rhs1 (def),
802 TREE_TYPE (name), ¤t);
803 break;
804 default:
805 continue;
806 }
807 exp = XNEW (class name_expansion);
808 exp->in_progress = 1;
809 if (!*cache)
810 *cache = new hash_map<tree, name_expansion *>;
811 (*cache)->put (name, exp);
812 aff_combination_expand (¤t, cache);
813 exp->expansion = current;
814 exp->in_progress = 0;
815 }
816 else
817 {
818 /* Since we follow the definitions in the SSA form, we should not
819 enter a cycle unless we pass through a phi node. */
820 gcc_assert (!exp->in_progress);
821 current = exp->expansion;
822 }
823 if (!useless_type_conversion_p (comb->type, current.type))
824 aff_combination_convert (¤t, comb->type);
825
826 /* Accumulate the new terms to TO_ADD, so that we do not modify
827 COMB while traversing it; include the term -coef * E, to remove
828 it from COMB. */
829 scale = comb->elts[i].coef;
830 aff_combination_zero (&curre, comb->type);
831 aff_combination_add_elt (&curre, e, -scale);
832 aff_combination_scale (¤t, scale);
833 aff_combination_add (&to_add, ¤t);
834 aff_combination_add (&to_add, &curre);
835 }
836 aff_combination_add (comb, &to_add);
837 }
838
839 /* Similar to tree_to_aff_combination, but follows SSA name definitions
840 and expands them recursively. CACHE is used to cache the expansions
841 of the ssa names, to avoid exponential time complexity for cases
842 like
843
844 a1 = a0 + a0;
845 a2 = a1 + a1;
846 a3 = a2 + a2;
847 ... */
848
849 void
tree_to_aff_combination_expand(tree expr,tree type,aff_tree * comb,hash_map<tree,name_expansion * > ** cache)850 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
851 hash_map<tree, name_expansion *> **cache)
852 {
853 tree_to_aff_combination (expr, type, comb);
854 aff_combination_expand (comb, cache);
855 }
856
857 /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
858 hash_map::traverse. */
859
860 bool
free_name_expansion(tree const &,name_expansion ** value,void *)861 free_name_expansion (tree const &, name_expansion **value, void *)
862 {
863 free (*value);
864 return true;
865 }
866
867 /* Frees memory allocated for the CACHE used by
868 tree_to_aff_combination_expand. */
869
870 void
free_affine_expand_cache(hash_map<tree,name_expansion * > ** cache)871 free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
872 {
873 if (!*cache)
874 return;
875
876 (*cache)->traverse<void *, free_name_expansion> (NULL);
877 delete (*cache);
878 *cache = NULL;
879 }
880
881 /* If VAL != CST * DIV for any constant CST, returns false.
882 Otherwise, if *MULT_SET is true, additionally compares CST and MULT,
883 and if they are different, returns false. Finally, if neither of these
884 two cases occur, true is returned, and CST is stored to MULT and MULT_SET
885 is set to true. */
886
887 static bool
wide_int_constant_multiple_p(const poly_widest_int & val,const poly_widest_int & div,bool * mult_set,poly_widest_int * mult)888 wide_int_constant_multiple_p (const poly_widest_int &val,
889 const poly_widest_int &div,
890 bool *mult_set, poly_widest_int *mult)
891 {
892 poly_widest_int rem, cst;
893
894 if (known_eq (val, 0))
895 {
896 if (*mult_set && maybe_ne (*mult, 0))
897 return false;
898 *mult_set = true;
899 *mult = 0;
900 return true;
901 }
902
903 if (maybe_eq (div, 0))
904 return false;
905
906 if (!multiple_p (val, div, &cst))
907 return false;
908
909 if (*mult_set && maybe_ne (*mult, cst))
910 return false;
911
912 *mult_set = true;
913 *mult = cst;
914 return true;
915 }
916
917 /* Returns true if VAL = X * DIV for some constant X. If this is the case,
918 X is stored to MULT. */
919
920 bool
aff_combination_constant_multiple_p(aff_tree * val,aff_tree * div,poly_widest_int * mult)921 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
922 poly_widest_int *mult)
923 {
924 bool mult_set = false;
925 unsigned i;
926
927 if (val->n == 0 && known_eq (val->offset, 0))
928 {
929 *mult = 0;
930 return true;
931 }
932 if (val->n != div->n)
933 return false;
934
935 if (val->rest || div->rest)
936 return false;
937
938 if (!wide_int_constant_multiple_p (val->offset, div->offset,
939 &mult_set, mult))
940 return false;
941
942 for (i = 0; i < div->n; i++)
943 {
944 class aff_comb_elt *elt
945 = aff_combination_find_elt (val, div->elts[i].val, NULL);
946 if (!elt)
947 return false;
948 if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
949 &mult_set, mult))
950 return false;
951 }
952
953 gcc_assert (mult_set);
954 return true;
955 }
956
957 /* Prints the affine VAL to the FILE. */
958
959 static void
print_aff(FILE * file,aff_tree * val)960 print_aff (FILE *file, aff_tree *val)
961 {
962 unsigned i;
963 signop sgn = TYPE_SIGN (val->type);
964 if (POINTER_TYPE_P (val->type))
965 sgn = SIGNED;
966 fprintf (file, "{\n type = ");
967 print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
968 fprintf (file, "\n offset = ");
969 print_dec (val->offset, file, sgn);
970 if (val->n > 0)
971 {
972 fprintf (file, "\n elements = {\n");
973 for (i = 0; i < val->n; i++)
974 {
975 fprintf (file, " [%d] = ", i);
976 print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
977
978 fprintf (file, " * ");
979 print_dec (val->elts[i].coef, file, sgn);
980 if (i != val->n - 1)
981 fprintf (file, ", \n");
982 }
983 fprintf (file, "\n }");
984 }
985 if (val->rest)
986 {
987 fprintf (file, "\n rest = ");
988 print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
989 }
990 fprintf (file, "\n}");
991 }
992
993 /* Prints the affine VAL to the standard error, used for debugging. */
994
995 DEBUG_FUNCTION void
debug_aff(aff_tree * val)996 debug_aff (aff_tree *val)
997 {
998 print_aff (stderr, val);
999 fprintf (stderr, "\n");
1000 }
1001
1002 /* Computes address of the reference REF in ADDR. The size of the accessed
1003 location is stored to SIZE. Returns the ultimate containing object to
1004 which REF refers. */
1005
1006 tree
get_inner_reference_aff(tree ref,aff_tree * addr,poly_widest_int * size)1007 get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1008 {
1009 poly_int64 bitsize, bitpos;
1010 tree toff;
1011 machine_mode mode;
1012 int uns, rev, vol;
1013 aff_tree tmp;
1014 tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1015 &uns, &rev, &vol);
1016 tree base_addr = build_fold_addr_expr (base);
1017
1018 /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
1019
1020 tree_to_aff_combination (base_addr, sizetype, addr);
1021
1022 if (toff)
1023 {
1024 tree_to_aff_combination (toff, sizetype, &tmp);
1025 aff_combination_add (addr, &tmp);
1026 }
1027
1028 aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos));
1029 aff_combination_add (addr, &tmp);
1030
1031 *size = bits_to_bytes_round_up (bitsize);
1032
1033 return base;
1034 }
1035
1036 /* Returns true if a region of size SIZE1 at position 0 and a region of
1037 size SIZE2 at position DIFF cannot overlap. */
1038
1039 bool
aff_comb_cannot_overlap_p(aff_tree * diff,const poly_widest_int & size1,const poly_widest_int & size2)1040 aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
1041 const poly_widest_int &size2)
1042 {
1043 /* Unless the difference is a constant, we fail. */
1044 if (diff->n != 0)
1045 return false;
1046
1047 if (!ordered_p (diff->offset, 0))
1048 return false;
1049
1050 if (maybe_lt (diff->offset, 0))
1051 {
1052 /* The second object is before the first one, we succeed if the last
1053 element of the second object is before the start of the first one. */
1054 return known_le (diff->offset + size2, 0);
1055 }
1056 else
1057 {
1058 /* We succeed if the second object starts after the first one ends. */
1059 return known_le (size1, diff->offset);
1060 }
1061 }
1062
1063