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