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 : #include "vr-values.h"
36 : #include "range-op.h"
37 :
38 : /* Extends CST as appropriate for the affine combinations COMB. */
39 :
40 : static widest_int
41 155360571 : wide_int_ext_for_comb (const widest_int &cst, tree type)
42 : {
43 155360571 : return wi::sext (cst, TYPE_PRECISION (type));
44 : }
45 :
46 : /* Likewise for polynomial offsets. */
47 :
48 : static poly_widest_int
49 243273455 : wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
50 : {
51 243273455 : return wi::sext (cst, TYPE_PRECISION (type));
52 : }
53 :
54 : /* Initializes affine combination COMB so that its value is zero in TYPE. */
55 :
56 : static void
57 194661476 : aff_combination_zero (aff_tree *comb, tree type)
58 : {
59 194661476 : int i;
60 194661476 : comb->type = type;
61 194661476 : comb->offset = 0;
62 194661476 : comb->n = 0;
63 1751953284 : for (i = 0; i < MAX_AFF_ELTS; i++)
64 1557291808 : comb->elts[i].coef = 0;
65 194661476 : comb->rest = NULL_TREE;
66 194661476 : }
67 :
68 : /* Sets COMB to CST. */
69 :
70 : void
71 111989613 : aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
72 : {
73 111989613 : aff_combination_zero (comb, type);
74 111989613 : comb->offset = wide_int_ext_for_comb (cst, comb->type);;
75 111989613 : }
76 :
77 : /* Sets COMB to single element ELT. */
78 :
79 : void
80 42660284 : aff_combination_elt (aff_tree *comb, tree type, tree elt)
81 : {
82 42660284 : aff_combination_zero (comb, type);
83 :
84 42660284 : comb->n = 1;
85 42660284 : comb->elts[0].val = elt;
86 42660284 : comb->elts[0].coef = 1;
87 42660284 : }
88 :
89 : /* Scales COMB by SCALE. */
90 :
91 : void
92 39102247 : aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
93 : {
94 39102247 : unsigned i, j;
95 :
96 39102247 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
97 39102247 : if (scale == 1)
98 : return;
99 :
100 28355181 : if (scale == 0)
101 : {
102 234 : aff_combination_zero (comb, comb->type);
103 234 : return;
104 : }
105 :
106 28354947 : comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
107 51546415 : for (i = 0, j = 0; i < comb->n; i++)
108 : {
109 23191468 : widest_int new_coef
110 23191468 : = wide_int_ext_for_comb (scale * comb->elts[i].coef, comb->type);
111 : /* A coefficient may become zero due to overflow. Remove the zero
112 : elements. */
113 23191468 : if (new_coef == 0)
114 4 : continue;
115 23191464 : comb->elts[j].coef = new_coef;
116 23191464 : comb->elts[j].val = comb->elts[i].val;
117 23191464 : j++;
118 23191468 : }
119 28354947 : comb->n = j;
120 :
121 28354947 : if (comb->rest)
122 : {
123 166 : tree type = comb->type;
124 166 : if (POINTER_TYPE_P (type))
125 112 : type = sizetype;
126 166 : if (comb->n < MAX_AFF_ELTS)
127 : {
128 0 : comb->elts[comb->n].coef = scale;
129 0 : comb->elts[comb->n].val = comb->rest;
130 0 : comb->rest = NULL_TREE;
131 0 : comb->n++;
132 : }
133 : else
134 166 : comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
135 : wide_int_to_tree (type, scale));
136 : }
137 39102247 : }
138 :
139 : /* Adds ELT * SCALE to COMB. */
140 :
141 : void
142 43496662 : aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
143 : {
144 43496662 : unsigned i;
145 43496662 : tree type;
146 :
147 43496662 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
148 43496662 : if (scale == 0)
149 : return;
150 :
151 56948521 : for (i = 0; i < comb->n; i++)
152 22151146 : if (operand_equal_p (comb->elts[i].val, elt, 0))
153 : {
154 8699287 : widest_int new_coef
155 8699287 : = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
156 8699287 : if (new_coef != 0)
157 : {
158 128412 : comb->elts[i].coef = new_coef;
159 128412 : return;
160 : }
161 :
162 8570875 : comb->n--;
163 8570875 : comb->elts[i] = comb->elts[comb->n];
164 :
165 8570875 : if (comb->rest)
166 : {
167 194 : gcc_assert (comb->n == MAX_AFF_ELTS - 1);
168 194 : comb->elts[comb->n].coef = 1;
169 194 : comb->elts[comb->n].val = comb->rest;
170 194 : comb->rest = NULL_TREE;
171 194 : comb->n++;
172 : }
173 : return;
174 8699287 : }
175 34797375 : if (comb->n < MAX_AFF_ELTS)
176 : {
177 34796680 : comb->elts[comb->n].coef = scale;
178 34796680 : comb->elts[comb->n].val = elt;
179 34796680 : comb->n++;
180 34796680 : return;
181 : }
182 :
183 695 : type = comb->type;
184 695 : if (POINTER_TYPE_P (type))
185 314 : type = sizetype;
186 :
187 695 : if (scale == 1)
188 518 : elt = fold_convert (type, elt);
189 : else
190 177 : elt = fold_build2 (MULT_EXPR, type,
191 : fold_convert (type, elt),
192 : wide_int_to_tree (type, scale));
193 :
194 695 : if (comb->rest)
195 42 : comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
196 : elt);
197 : else
198 : comb->rest = elt;
199 43496662 : }
200 :
201 : /* Adds CST to C. */
202 :
203 : static void
204 102803187 : aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
205 : {
206 102803187 : c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
207 102803187 : }
208 :
209 : /* Adds COMB2 to COMB1. */
210 :
211 : void
212 98637514 : aff_combination_add (aff_tree *comb1, aff_tree *comb2)
213 : {
214 98637514 : unsigned i;
215 :
216 98637514 : aff_combination_add_cst (comb1, comb2->offset);
217 218138887 : for (i = 0; i < comb2->n; i++)
218 20863859 : aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
219 98637514 : if (comb2->rest)
220 180 : aff_combination_add_elt (comb1, comb2->rest, 1);
221 98637514 : }
222 :
223 : /* Converts affine combination COMB to TYPE. AT is the range-query context. */
224 :
225 : void
226 28929688 : aff_combination_convert (aff_tree *comb, tree type, gimple *at)
227 : {
228 28929688 : unsigned i, j;
229 28929688 : tree comb_type = comb->type;
230 :
231 28929688 : if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
232 : {
233 886984 : tree val = fold_convert (type, aff_combination_to_tree (comb));
234 886984 : tree_to_aff_combination (val, type, comb, at);
235 886984 : return;
236 : }
237 :
238 28042704 : comb->type = type;
239 28042704 : if (comb->rest && !POINTER_TYPE_P (type))
240 208 : comb->rest = fold_convert (type, comb->rest);
241 :
242 28042704 : if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
243 : return;
244 :
245 125708 : comb->offset = wide_int_ext_for_comb (comb->offset, comb->type);
246 171602 : for (i = j = 0; i < comb->n; i++)
247 : {
248 45894 : if (comb->elts[i].coef == 0)
249 0 : continue;
250 45894 : comb->elts[j].coef = comb->elts[i].coef;
251 45894 : comb->elts[j].val = fold_convert (type, comb->elts[i].val);
252 45894 : j++;
253 : }
254 :
255 125708 : comb->n = j;
256 125708 : if (comb->n < MAX_AFF_ELTS && comb->rest)
257 : {
258 0 : comb->elts[comb->n].coef = 1;
259 0 : comb->elts[comb->n].val = comb->rest;
260 0 : comb->rest = NULL_TREE;
261 0 : comb->n++;
262 : }
263 : }
264 :
265 : /* Tries to handle OP0 CODE OP1 as affine combination of parts. AT is the
266 : range-query context. Returns true when that was successful and returns the
267 : combination in COMB. */
268 :
269 : static bool
270 24573953 : expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
271 : tree op0, tree op1 = NULL_TREE, gimple *at = NULL)
272 : {
273 24573953 : aff_tree tmp;
274 :
275 24573953 : switch (code)
276 : {
277 369001 : case POINTER_PLUS_EXPR:
278 369001 : tree_to_aff_combination (op0, type, comb, at);
279 369001 : tree_to_aff_combination (op1, sizetype, &tmp, at);
280 369001 : aff_combination_add (comb, &tmp);
281 369001 : return true;
282 :
283 14278142 : case PLUS_EXPR:
284 14278142 : case MINUS_EXPR:
285 14278142 : tree_to_aff_combination (op0, type, comb, at);
286 14278142 : tree_to_aff_combination (op1, type, &tmp, at);
287 14278142 : if (code == MINUS_EXPR)
288 563285 : aff_combination_scale (&tmp, -1);
289 14278142 : aff_combination_add (comb, &tmp);
290 14278142 : return true;
291 :
292 6846043 : case MULT_EXPR:
293 6846043 : if (TREE_CODE (op1) != INTEGER_CST)
294 : break;
295 5899047 : tree_to_aff_combination (op0, type, comb, at);
296 5899047 : aff_combination_scale (comb, wi::to_widest (op1));
297 5899047 : return true;
298 :
299 97628 : case NEGATE_EXPR:
300 97628 : tree_to_aff_combination (op0, type, comb, at);
301 97628 : aff_combination_scale (comb, -1);
302 97628 : return true;
303 :
304 3848 : case BIT_NOT_EXPR:
305 : /* ~x = -x - 1 */
306 3848 : tree_to_aff_combination (op0, type, comb, at);
307 3848 : aff_combination_scale (comb, -1);
308 3848 : aff_combination_add_cst (comb, -1);
309 3848 : return true;
310 :
311 2979291 : CASE_CONVERT:
312 2979291 : {
313 2979291 : tree otype = type;
314 2979291 : tree inner = op0;
315 2979291 : tree itype = TREE_TYPE (inner);
316 2979291 : enum tree_code icode = TREE_CODE (inner);
317 :
318 : /* STRIP_NOPS */
319 2979291 : if (tree_nop_conversion_p (otype, itype))
320 : {
321 14027 : tree_to_aff_combination (op0, type, comb, at);
322 14027 : return true;
323 : }
324 :
325 : /* Look through (OTYPE) (ITYPE) IOP. ITYPE and IOTYPE have the
326 : same precision and differ at most in signedness. */
327 2964987 : if (INTEGRAL_NB_TYPE_P (otype)
328 2964480 : && INTEGRAL_NB_TYPE_P (itype)
329 2941708 : && TYPE_PRECISION (otype) > TYPE_PRECISION (itype)
330 4801656 : && CONVERT_EXPR_P (inner))
331 : {
332 92656 : tree iop = TREE_OPERAND (inner, 0);
333 92656 : tree iotype = TREE_TYPE (iop);
334 92656 : tree_code wcode = TREE_CODE (iop);
335 :
336 92640 : if (INTEGRAL_NB_TYPE_P (iotype)
337 185296 : && tree_nop_conversion_p (itype, iotype))
338 : {
339 73354 : int_range_max vr;
340 73354 : range_query *query = get_range_query (cfun);
341 :
342 : /* Distribute the conversions when the operation fits ITYPE:
343 : (OTYPE) (ITYPE) ((IOTYPE) X +- CST)
344 : ->
345 : (OTYPE) (ITYPE) (IOTYPE) X +- (OTYPE) (ITYPE) CST.
346 :
347 : (OTYPE)(ITYPE) (IOTYPE) X will be further simplified to
348 : (OTYPE) X when X fits ITYPE.
349 :
350 : So eventually the simplification is like
351 : (OTYPE) (ITYPE) ((IOTYPE) X + CST)
352 : ->
353 : (OTYPE) X + (OTYPE) (ITYPE) CST.
354 : This is used to handle the complicated convert chain which
355 : is created by unsigned canonicalization in IVOPTS, the
356 : canonicalization itself is used to detect more equality
357 : for iv, so handle the redundancy here. */
358 :
359 73354 : if (!TYPE_UNSIGNED (itype)
360 58584 : && TYPE_UNSIGNED (iotype)
361 58584 : && (wcode == PLUS_EXPR || wcode == MINUS_EXPR)
362 124948 : && TREE_CODE (TREE_OPERAND (iop, 1)) == INTEGER_CST)
363 : {
364 50372 : tree wop0 = fold_convert (itype, TREE_OPERAND (iop, 0));
365 50372 : tree wop1 = fold_convert (itype, TREE_OPERAND (iop, 1));
366 :
367 50372 : if (query->range_of_expr (vr, wop0, at)
368 50372 : && !vr.varying_p ()
369 91981 : && !vr.undefined_p ())
370 : {
371 41247 : wi::overflow_type ovf1 = wi::OVF_NONE;
372 41247 : wi::overflow_type ovf2 = wi::OVF_NONE;
373 41247 : wide_int cst = wi::to_wide (wop1);
374 :
375 : /* IOP has wrapping type IOTYPE, so check signed
376 : overflow explicitly. overflow_free_p uses ITYPE's
377 : undefined-overflow semantics and always returns true. */
378 41247 : if (wcode == PLUS_EXPR)
379 : {
380 41247 : wi::add (vr.lower_bound (), cst, SIGNED, &ovf1);
381 41247 : wi::add (vr.upper_bound (), cst, SIGNED, &ovf2);
382 : }
383 : else
384 : {
385 0 : wi::sub (vr.lower_bound (), cst, SIGNED, &ovf1);
386 0 : wi::sub (vr.upper_bound (), cst, SIGNED, &ovf2);
387 : }
388 :
389 41247 : if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE)
390 : {
391 11006 : wop0 = fold_convert (otype, wop0);
392 11006 : wop1 = fold_convert (otype, wop1);
393 11006 : return expr_to_aff_combination (comb, wcode, otype,
394 : wop0, wop1, at);
395 : }
396 41247 : }
397 : }
398 :
399 : /* Strip the inner conversion when IOP fits ITYPE:
400 : (OTYPE) (ITYPE) IOP -> (OTYPE) IOP.
401 :
402 : (unsigned long) (int) (unsigned) k is simplified to
403 : (unsigned long) k when we know k >= 0. */
404 62348 : if (TYPE_SIGN (itype) == TYPE_SIGN (iotype)
405 62348 : || (TREE_CODE (iop) == INTEGER_CST
406 62348 : ? int_fits_type_p (iop, itype)
407 62348 : : (query->range_of_expr (vr, iop, at)
408 62348 : && range_fits_type_p (&vr, TYPE_PRECISION (itype),
409 62348 : TYPE_SIGN (itype)))))
410 : {
411 7780 : tree_to_aff_combination (fold_convert (otype, iop), type,
412 : comb, at);
413 7780 : return true;
414 : }
415 73354 : }
416 : }
417 :
418 : /* In principle this is a valid folding, but it isn't necessarily
419 : an optimization, so do it here and not in fold_unary. */
420 2946478 : if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
421 242567 : && INTEGRAL_NB_TYPE_P (itype)
422 242567 : && INTEGRAL_NB_TYPE_P (otype)
423 3189045 : && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
424 : {
425 188724 : tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1);
426 :
427 : /* If inner type has undefined overflow behavior, fold conversion
428 : for below two cases:
429 : (T1)(X *+- CST) -> (T1)X *+- (T1)CST
430 : (T1)(X + X) -> (T1)X + (T1)X. */
431 188724 : if (TYPE_OVERFLOW_UNDEFINED (itype)
432 92619 : && (TREE_CODE (op1) == INTEGER_CST
433 3640 : || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
434 : {
435 88979 : op0 = fold_convert (otype, op0);
436 88979 : op1 = fold_convert (otype, op1);
437 88979 : return expr_to_aff_combination (comb, icode, otype, op0, op1,
438 103452 : at);
439 : }
440 99745 : wide_int minv, maxv;
441 : /* If inner type has wrapping overflow behavior, fold conversion
442 : for below case:
443 : (T1)(X *+- CST) -> (T1)X *+- (T1)CST
444 : if X *+- CST doesn't overflow by range information. */
445 99745 : int_range_max vr;
446 99745 : if (TYPE_UNSIGNED (itype)
447 95856 : && TYPE_OVERFLOW_WRAPS (itype)
448 95856 : && TREE_CODE (op1) == INTEGER_CST
449 141672 : && get_range_query (cfun)->range_of_expr (vr, op0, at)
450 70836 : && !vr.varying_p ()
451 119733 : && !vr.undefined_p ())
452 : {
453 19974 : wide_int minv = vr.lower_bound ();
454 19974 : wide_int maxv = vr.upper_bound ();
455 19974 : wi::overflow_type overflow = wi::OVF_NONE;
456 19974 : signop sign = UNSIGNED;
457 19974 : if (icode == PLUS_EXPR)
458 15263 : wi::add (maxv, wi::to_wide (op1), sign, &overflow);
459 4711 : else if (icode == MULT_EXPR)
460 4711 : wi::mul (maxv, wi::to_wide (op1), sign, &overflow);
461 : else
462 0 : wi::sub (minv, wi::to_wide (op1), sign, &overflow);
463 :
464 19974 : if (overflow == wi::OVF_NONE)
465 : {
466 6504 : op0 = fold_convert (otype, op0);
467 6504 : op1 = fold_convert (otype, op1);
468 6504 : return expr_to_aff_combination (comb, icode, otype, op0,
469 6504 : op1, at);
470 : }
471 : /* A negative offset can be handled as an exact subtraction:
472 : (T1) (X + CST) -> (T1) X - (T1) -CST.
473 :
474 : This rewrites (int) ((unsigned int) k + UINT_MAX) to
475 : (int) k - 1 when k is known >= 1.
476 :
477 : This also works for the most-negative signed CST: unsigned
478 : negation is modulo 2^precision, so -CST equals CST. */
479 13470 : else if (icode == PLUS_EXPR
480 13470 : && wi::neg_p (wi::to_wide (op1), SIGNED))
481 : {
482 12314 : wide_int pos_cst = wi::neg (wi::to_wide (op1));
483 12314 : int_range<1> cst_range (itype, pos_cst, pos_cst);
484 12314 : range_op_handler minus (MINUS_EXPR);
485 :
486 12314 : if (minus.overflow_free_p (vr, cst_range))
487 : {
488 7969 : op0 = fold_convert (otype, op0);
489 7969 : op1 = fold_convert (otype,
490 : wide_int_to_tree (itype, pos_cst));
491 7969 : return expr_to_aff_combination (comb, MINUS_EXPR,
492 : otype, op0, op1, at);
493 : }
494 12314 : }
495 19974 : }
496 99745 : }
497 : }
498 : break;
499 :
500 946996 : default:;
501 : }
502 :
503 : return false;
504 24573953 : }
505 :
506 : /* Splits EXPR into an affine combination of parts. AT is the range-query
507 : context. */
508 :
509 : void
510 158779697 : tree_to_aff_combination (tree expr, tree type, aff_tree *comb, gimple *at)
511 : {
512 158779697 : aff_tree tmp;
513 158779697 : enum tree_code code;
514 158779697 : tree core, toffset;
515 158779697 : poly_int64 bitpos, bitsize, bytepos;
516 158779697 : machine_mode mode;
517 158779697 : int unsignedp, reversep, volatilep;
518 :
519 158779697 : STRIP_NOPS (expr);
520 :
521 158779697 : code = TREE_CODE (expr);
522 158779697 : switch (code)
523 : {
524 21272684 : case POINTER_PLUS_EXPR:
525 21272684 : case PLUS_EXPR:
526 21272684 : case MINUS_EXPR:
527 21272684 : case MULT_EXPR:
528 21272684 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
529 21272684 : TREE_OPERAND (expr, 1), at))
530 : return;
531 : break;
532 :
533 100883 : case NEGATE_EXPR:
534 100883 : case BIT_NOT_EXPR:
535 100883 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
536 : NULL_TREE, at))
537 : return;
538 : break;
539 :
540 2947644 : CASE_CONVERT:
541 : /* ??? TREE_TYPE (expr) should be equal to type here, but IVOPTS
542 : calls this with not showing an outer widening cast. */
543 2947644 : if (expr_to_aff_combination (comb, code,
544 2947644 : TREE_TYPE (expr), TREE_OPERAND (expr, 0),
545 : NULL_TREE, at))
546 : {
547 122238 : aff_combination_convert (comb, type, at);
548 122238 : return;
549 : }
550 : break;
551 :
552 21340084 : case ADDR_EXPR:
553 : /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
554 21340084 : if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
555 : {
556 630887 : expr = TREE_OPERAND (expr, 0);
557 630887 : tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb, at);
558 630887 : tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp,
559 : at);
560 630887 : aff_combination_add (comb, &tmp);
561 630887 : return;
562 : }
563 20709197 : core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
564 : &toffset, &mode, &unsignedp, &reversep,
565 : &volatilep);
566 41418394 : if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
567 : break;
568 20709197 : aff_combination_const (comb, type, bytepos);
569 20709197 : if (TREE_CODE (core) == MEM_REF)
570 : {
571 233311 : tree mem_offset = TREE_OPERAND (core, 1);
572 233311 : aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset));
573 233311 : core = TREE_OPERAND (core, 0);
574 : }
575 : else
576 20475886 : core = build_fold_addr_expr (core);
577 :
578 20709197 : if (TREE_CODE (core) == ADDR_EXPR)
579 20475886 : aff_combination_add_elt (comb, core, 1);
580 : else
581 : {
582 233311 : tree_to_aff_combination (core, type, &tmp, at);
583 233311 : aff_combination_add (comb, &tmp);
584 : }
585 20709197 : if (toffset)
586 : {
587 62765 : tree_to_aff_combination (toffset, type, &tmp, at);
588 62765 : aff_combination_add (comb, &tmp);
589 : }
590 : return;
591 :
592 113118402 : default:
593 113118402 : {
594 113118402 : if (poly_int_tree_p (expr))
595 : {
596 74181917 : aff_combination_const (comb, type, wi::to_poly_widest (expr));
597 74181917 : return;
598 : }
599 : break;
600 : }
601 : }
602 :
603 42642664 : aff_combination_elt (comb, type, expr);
604 158779697 : }
605 :
606 : /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
607 : combination COMB. */
608 :
609 : static tree
610 40870907 : add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
611 : {
612 40870907 : enum tree_code code;
613 :
614 40870907 : widest_int scale = wide_int_ext_for_comb (scale_in, type);
615 :
616 40870907 : elt = fold_convert (type, elt);
617 40870907 : if (scale == 1)
618 : {
619 34858716 : if (!expr)
620 : return elt;
621 :
622 13635122 : return fold_build2 (PLUS_EXPR, type, expr, elt);
623 : }
624 :
625 6012191 : if (scale == -1)
626 : {
627 2808585 : if (!expr)
628 1675303 : return fold_build1 (NEGATE_EXPR, type, elt);
629 :
630 1133282 : return fold_build2 (MINUS_EXPR, type, expr, elt);
631 : }
632 :
633 3203606 : if (!expr)
634 1892846 : return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
635 :
636 1310760 : if (wi::neg_p (scale))
637 : {
638 339053 : code = MINUS_EXPR;
639 339053 : scale = -scale;
640 : }
641 : else
642 : code = PLUS_EXPR;
643 :
644 1310760 : elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
645 1310760 : return fold_build2 (code, type, expr, elt);
646 40870907 : }
647 :
648 : /* Makes tree from the affine combination COMB. */
649 :
650 : tree
651 24791743 : aff_combination_to_tree (aff_tree *comb)
652 : {
653 24791743 : tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
654 24791743 : unsigned i;
655 24791743 : poly_widest_int off;
656 24791743 : int sgn;
657 :
658 24791743 : gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
659 :
660 24791743 : i = 0;
661 24791743 : if (POINTER_TYPE_P (type))
662 : {
663 122484 : type = sizetype;
664 244819 : if (comb->n > 0 && comb->elts[0].coef == 1
665 244819 : && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
666 : {
667 24791743 : base = comb->elts[0].val;
668 24791743 : ++i;
669 : }
670 : }
671 :
672 40870637 : for (; i < comb->n; i++)
673 16078894 : expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);
674 :
675 24791743 : if (comb->rest)
676 270 : expr = add_elt_to_tree (expr, type, comb->rest, 1);
677 :
678 : /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
679 : unsigned. */
680 24791743 : if (known_lt (comb->offset, 0))
681 : {
682 2230749 : off = -comb->offset;
683 2230749 : sgn = -1;
684 : }
685 : else
686 : {
687 22560994 : off = comb->offset;
688 22560994 : sgn = 1;
689 : }
690 24791743 : expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);
691 :
692 24791743 : if (base)
693 118366 : return fold_build_pointer_plus (base, expr);
694 : else
695 24673377 : return fold_convert (comb->type, expr);
696 24791743 : }
697 :
698 : /* Copies the tree elements of COMB to ensure that they are not shared. */
699 :
700 : void
701 1819382 : unshare_aff_combination (aff_tree *comb)
702 : {
703 1819382 : unsigned i;
704 :
705 3864449 : for (i = 0; i < comb->n; i++)
706 2045067 : comb->elts[i].val = unshare_expr (comb->elts[i].val);
707 1819382 : if (comb->rest)
708 0 : comb->rest = unshare_expr (comb->rest);
709 1819382 : }
710 :
711 : /* Remove M-th element from COMB. */
712 :
713 : void
714 1772739 : aff_combination_remove_elt (aff_tree *comb, unsigned m)
715 : {
716 1772739 : comb->n--;
717 1772739 : if (m <= comb->n)
718 1772739 : comb->elts[m] = comb->elts[comb->n];
719 1772739 : if (comb->rest)
720 : {
721 0 : comb->elts[comb->n].coef = 1;
722 0 : comb->elts[comb->n].val = comb->rest;
723 0 : comb->rest = NULL_TREE;
724 0 : comb->n++;
725 : }
726 1772739 : }
727 :
728 : /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only
729 : C * COEF is added to R. */
730 :
731 :
732 : static void
733 3928514 : aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
734 : aff_tree *r)
735 : {
736 3928514 : unsigned i;
737 3928514 : tree aval, type;
738 :
739 5348285 : for (i = 0; i < c->n; i++)
740 : {
741 1419771 : aval = c->elts[i].val;
742 1419771 : if (val)
743 : {
744 0 : type = TREE_TYPE (aval);
745 0 : aval = fold_build2 (MULT_EXPR, type, aval,
746 : fold_convert (type, val));
747 : }
748 :
749 1419771 : aff_combination_add_elt (r, aval, coef * c->elts[i].coef);
750 : }
751 :
752 3928514 : if (c->rest)
753 : {
754 0 : aval = c->rest;
755 0 : if (val)
756 : {
757 0 : type = TREE_TYPE (aval);
758 0 : aval = fold_build2 (MULT_EXPR, type, aval,
759 : fold_convert (type, val));
760 : }
761 :
762 0 : aff_combination_add_elt (r, aval, coef);
763 : }
764 :
765 3928514 : if (val)
766 : {
767 0 : if (c->offset.is_constant ())
768 : /* Access coeffs[0] directly, for efficiency. */
769 0 : aff_combination_add_elt (r, val, coef * c->offset.coeffs[0]);
770 : else
771 : {
772 : /* c->offset is polynomial, so multiply VAL rather than COEF
773 : by it. */
774 : tree offset = wide_int_to_tree (TREE_TYPE (val), c->offset);
775 : val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset);
776 : aff_combination_add_elt (r, val, coef);
777 : }
778 : }
779 : else
780 3928514 : aff_combination_add_cst (r, coef * c->offset);
781 3928514 : }
782 :
783 : /* Multiplies C1 by C2, storing the result to R */
784 :
785 : void
786 3928514 : aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
787 : {
788 3928514 : unsigned i;
789 3928514 : gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
790 :
791 3928514 : aff_combination_zero (r, c1->type);
792 :
793 7857028 : for (i = 0; i < c2->n; i++)
794 0 : aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
795 3928514 : if (c2->rest)
796 0 : aff_combination_add_product (c1, 1, c2->rest, r);
797 3928514 : if (c2->offset.is_constant ())
798 : /* Access coeffs[0] directly, for efficiency. */
799 3928514 : aff_combination_add_product (c1, c2->offset.coeffs[0], NULL, r);
800 : else
801 : {
802 : /* c2->offset is polynomial, so do the multiplication in tree form. */
803 : tree offset = wide_int_to_tree (c2->type, c2->offset);
804 : aff_combination_add_product (c1, 1, offset, r);
805 : }
806 3928514 : }
807 :
808 : /* Returns the element of COMB whose value is VAL, or NULL if no such
809 : element exists. If IDX is not NULL, it is set to the index of VAL in
810 : COMB. */
811 :
812 : static class aff_comb_elt *
813 1194765 : aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
814 : {
815 1194765 : unsigned i;
816 :
817 1525885 : for (i = 0; i < comb->n; i++)
818 1199923 : if (operand_equal_p (comb->elts[i].val, val, 0))
819 : {
820 868803 : if (idx)
821 0 : *idx = i;
822 :
823 868803 : return &comb->elts[i];
824 : }
825 :
826 : return NULL;
827 : }
828 :
829 : /* Element of the cache that maps ssa name NAME to its expanded form
830 : as an affine expression EXPANSION. */
831 :
832 289012 : class name_expansion
833 : {
834 : public:
835 : aff_tree expansion;
836 :
837 : /* True if the expansion for the name is just being generated. */
838 : unsigned in_progress : 1;
839 : };
840 :
841 : /* Expands SSA names in COMB recursively. CACHE is used to cache the
842 : results. */
843 :
844 : void
845 35353036 : aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
846 : hash_map<tree, name_expansion *> **cache)
847 : {
848 35353036 : unsigned i;
849 106059108 : aff_tree to_add, current, curre;
850 35353036 : tree e;
851 35353036 : gimple *def;
852 35353036 : widest_int scale;
853 35353036 : class name_expansion *exp;
854 :
855 35353036 : aff_combination_zero (&to_add, comb->type);
856 74240963 : for (i = 0; i < comb->n; i++)
857 : {
858 3534891 : tree type, name;
859 3534891 : enum tree_code code;
860 :
861 3534891 : e = comb->elts[i].val;
862 3534891 : type = TREE_TYPE (e);
863 3534891 : name = e;
864 : /* Look through some conversions. */
865 3399790 : if (CONVERT_EXPR_P (e)
866 3534891 : && (TYPE_PRECISION (type)
867 135101 : >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
868 86887 : name = TREE_OPERAND (e, 0);
869 3534891 : if (TREE_CODE (name) != SSA_NAME)
870 2805096 : continue;
871 3313892 : def = SSA_NAME_DEF_STMT (name);
872 3313892 : if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
873 1816120 : continue;
874 :
875 1497772 : code = gimple_assign_rhs_code (def);
876 1516777 : if (code != SSA_NAME
877 1497152 : && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
878 1516781 : && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
879 19009 : || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
880 19005 : continue;
881 :
882 : /* We do not know whether the reference retains its value at the
883 : place where the expansion is used. */
884 1478767 : if (TREE_CODE_CLASS (code) == tcc_reference)
885 584099 : continue;
886 :
887 894668 : name_expansion **slot = NULL;
888 894668 : if (*cache)
889 767605 : slot = (*cache)->get (name);
890 767605 : exp = slot ? *slot : NULL;
891 894668 : if (!exp)
892 : {
893 : /* Only bother to handle cases tree_to_aff_combination will. */
894 237126 : switch (code)
895 : {
896 106044 : case POINTER_PLUS_EXPR:
897 106044 : case PLUS_EXPR:
898 106044 : case MINUS_EXPR:
899 106044 : case MULT_EXPR:
900 106044 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
901 : gimple_assign_rhs1 (def),
902 : gimple_assign_rhs2 (def)))
903 66223 : continue;
904 : break;
905 593 : case NEGATE_EXPR:
906 593 : case BIT_NOT_EXPR:
907 593 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
908 : gimple_assign_rhs1 (def)))
909 0 : continue;
910 : break;
911 31647 : CASE_CONVERT:
912 31647 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
913 : gimple_assign_rhs1 (def)))
914 : /* This makes us always expand conversions which we did
915 : in the past and makes gcc.dg/tree-ssa/ivopts-lt-2.c
916 : PASS, eliminating one induction variable in IVOPTs.
917 : ??? But it is really excessive and we should try
918 : harder to do without it. */
919 35240 : aff_combination_elt (¤t, TREE_TYPE (name),
920 17620 : fold_convert (TREE_TYPE (name),
921 : gimple_assign_rhs1 (def)));
922 : break;
923 192 : case ADDR_EXPR:
924 192 : case INTEGER_CST:
925 192 : case POLY_INT_CST:
926 192 : tree_to_aff_combination (gimple_assign_rhs1 (def),
927 192 : TREE_TYPE (name), ¤t);
928 192 : break;
929 98650 : default:
930 98650 : continue;
931 : }
932 72253 : exp = XNEW (class name_expansion);
933 72253 : ::new (static_cast<void *> (exp)) name_expansion ();
934 72253 : exp->in_progress = 1;
935 72253 : if (!*cache)
936 30998 : *cache = new hash_map<tree, name_expansion *>;
937 72253 : (*cache)->put (name, exp);
938 72253 : aff_combination_expand (¤t, cache);
939 72253 : exp->expansion = current;
940 72253 : exp->in_progress = 0;
941 : }
942 : else
943 : {
944 : /* Since we follow the definitions in the SSA form, we should not
945 : enter a cycle unless we pass through a phi node. */
946 657542 : gcc_assert (!exp->in_progress);
947 657542 : current = exp->expansion;
948 : }
949 729795 : if (!useless_type_conversion_p (comb->type, current.type))
950 81077 : aff_combination_convert (¤t, comb->type);
951 :
952 : /* Accumulate the new terms to TO_ADD, so that we do not modify
953 : COMB while traversing it; include the term -coef * E, to remove
954 : it from COMB. */
955 729795 : scale = comb->elts[i].coef;
956 729795 : aff_combination_zero (&curre, comb->type);
957 729795 : aff_combination_add_elt (&curre, e, -scale);
958 729795 : aff_combination_scale (¤t, scale);
959 729795 : aff_combination_add (&to_add, ¤t);
960 729795 : aff_combination_add (&to_add, &curre);
961 : }
962 35353036 : aff_combination_add (comb, &to_add);
963 35353036 : }
964 :
965 : /* Similar to tree_to_aff_combination, but follows SSA name definitions
966 : and expands them recursively. CACHE is used to cache the expansions
967 : of the ssa names, to avoid exponential time complexity for cases
968 : like
969 :
970 : a1 = a0 + a0;
971 : a2 = a1 + a1;
972 : a3 = a2 + a2;
973 : ... */
974 :
975 : void
976 35169049 : tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
977 : hash_map<tree, name_expansion *> **cache)
978 : {
979 35169049 : tree_to_aff_combination (expr, type, comb);
980 35169049 : aff_combination_expand (comb, cache);
981 35169049 : }
982 :
983 : /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
984 : hash_map::traverse. */
985 :
986 : bool
987 72253 : free_name_expansion (tree const &, name_expansion **value, void *)
988 : {
989 72253 : (*value)->~name_expansion ();
990 72253 : free (*value);
991 72253 : return true;
992 : }
993 :
994 : /* Frees memory allocated for the CACHE used by
995 : tree_to_aff_combination_expand. */
996 :
997 : void
998 1782801 : free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
999 : {
1000 1782801 : if (!*cache)
1001 : return;
1002 :
1003 103251 : (*cache)->traverse<void *, free_name_expansion> (NULL);
1004 61996 : delete (*cache);
1005 30998 : *cache = NULL;
1006 : }
1007 :
1008 : /* If VAL == CST * DIV for any constant CST, returns true.
1009 : and if *MULT_SET is true, additionally compares CST and MULT
1010 : and if they are different, returns false. If true is returned, CST is
1011 : stored to MULT and MULT_SET is set to true unless VAL and DIV are both zero
1012 : in which case neither MULT nor MULT_SET are updated. */
1013 :
1014 : static bool
1015 17514013 : wide_int_constant_multiple_p (const poly_widest_int &val,
1016 : const poly_widest_int &div,
1017 : bool *mult_set, poly_widest_int *mult)
1018 : {
1019 17514013 : poly_widest_int cst;
1020 :
1021 17514013 : if (known_eq (val, 0))
1022 : {
1023 1175891 : if (known_eq (div, 0))
1024 : return true;
1025 :
1026 321 : if (*mult_set && maybe_ne (*mult, 0))
1027 0 : return false;
1028 321 : *mult_set = true;
1029 321 : *mult = 0;
1030 321 : return true;
1031 : }
1032 :
1033 16338122 : if (maybe_eq (div, 0))
1034 : return false;
1035 :
1036 16336834 : if (!multiple_p (val, div, &cst))
1037 : return false;
1038 :
1039 14492521 : if (*mult_set && maybe_ne (*mult, cst))
1040 : return false;
1041 :
1042 14473519 : *mult_set = true;
1043 14473519 : *mult = cst;
1044 14473519 : return true;
1045 17514013 : }
1046 :
1047 : /* Returns true if VAL = X * DIV for some constant X. If this is the case,
1048 : X is stored to MULT. */
1049 :
1050 : bool
1051 17499508 : aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
1052 : poly_widest_int *mult)
1053 : {
1054 17499508 : bool mult_set = false;
1055 17499508 : unsigned i;
1056 :
1057 17499508 : if (val->n == 0 && known_eq (val->offset, 0))
1058 : {
1059 52929 : *mult = 0;
1060 52929 : return true;
1061 : }
1062 17446579 : if (val->n != div->n)
1063 : return false;
1064 :
1065 16645210 : if (val->rest || div->rest)
1066 : return false;
1067 :
1068 16645210 : if (!wide_int_constant_multiple_p (val->offset, div->offset,
1069 : &mult_set, mult))
1070 : return false;
1071 :
1072 15649410 : for (i = 0; i < div->n; i++)
1073 : {
1074 1194765 : class aff_comb_elt *elt
1075 1194765 : = aff_combination_find_elt (val, div->elts[i].val, NULL);
1076 1194765 : if (!elt)
1077 : return false;
1078 868803 : if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
1079 : &mult_set, mult))
1080 : return false;
1081 : }
1082 :
1083 14454645 : gcc_assert (mult_set);
1084 : return true;
1085 : }
1086 :
1087 : /* Prints the affine VAL to the FILE. */
1088 :
1089 : static void
1090 0 : print_aff (FILE *file, aff_tree *val)
1091 : {
1092 0 : unsigned i;
1093 0 : signop sgn = TYPE_SIGN (val->type);
1094 0 : if (POINTER_TYPE_P (val->type))
1095 0 : sgn = SIGNED;
1096 0 : fprintf (file, "{\n type = ");
1097 0 : print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
1098 0 : fprintf (file, "\n offset = ");
1099 0 : print_dec (val->offset, file, sgn);
1100 0 : if (val->n > 0)
1101 : {
1102 0 : fprintf (file, "\n elements = {\n");
1103 0 : for (i = 0; i < val->n; i++)
1104 : {
1105 0 : fprintf (file, " [%d] = ", i);
1106 0 : print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
1107 :
1108 0 : fprintf (file, " * ");
1109 0 : print_dec (val->elts[i].coef, file, sgn);
1110 0 : if (i != val->n - 1)
1111 0 : fprintf (file, ", \n");
1112 : }
1113 0 : fprintf (file, "\n }");
1114 : }
1115 0 : if (val->rest)
1116 : {
1117 0 : fprintf (file, "\n rest = ");
1118 0 : print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
1119 : }
1120 0 : fprintf (file, "\n}");
1121 0 : }
1122 :
1123 : /* Prints the affine VAL to the standard error, used for debugging. */
1124 :
1125 : DEBUG_FUNCTION void
1126 0 : debug_aff (aff_tree *val)
1127 : {
1128 0 : print_aff (stderr, val);
1129 0 : fprintf (stderr, "\n");
1130 0 : }
1131 :
1132 : /* Computes address of the reference REF in ADDR. The size of the accessed
1133 : location is stored to SIZE. Returns the ultimate containing object to
1134 : which REF refers. */
1135 :
1136 : tree
1137 16874469 : get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1138 : {
1139 16874469 : poly_int64 bitsize, bitpos;
1140 16874469 : tree toff;
1141 16874469 : machine_mode mode;
1142 16874469 : int uns, rev, vol;
1143 16874469 : aff_tree tmp;
1144 16874469 : tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1145 : &uns, &rev, &vol);
1146 16874469 : tree base_addr = build_fold_addr_expr (base);
1147 :
1148 : /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
1149 :
1150 16874469 : tree_to_aff_combination (base_addr, sizetype, addr);
1151 :
1152 16874469 : if (toff)
1153 : {
1154 166118 : tree_to_aff_combination (toff, sizetype, &tmp);
1155 166118 : aff_combination_add (addr, &tmp);
1156 : }
1157 :
1158 16874469 : poly_int64 bytepos = bits_to_bytes_round_down (bitpos);
1159 16874469 : aff_combination_const (&tmp, sizetype, bytepos);
1160 16874469 : aff_combination_add (addr, &tmp);
1161 :
1162 16874469 : *size = bits_to_bytes_round_up (bitpos + bitsize) - bytepos;
1163 :
1164 33748938 : return base;
1165 16874469 : }
1166 :
1167 : /* Returns true if a region of size SIZE1 at position 0 and a region of
1168 : size SIZE2 at position DIFF cannot overlap. */
1169 :
1170 : bool
1171 2868360 : aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
1172 : const poly_widest_int &size2)
1173 : {
1174 : /* Unless the difference is a constant, we fail. */
1175 2868360 : if (diff->n != 0)
1176 : return false;
1177 :
1178 1868114 : if (!ordered_p (diff->offset, 0))
1179 : return false;
1180 :
1181 1868114 : if (maybe_lt (diff->offset, 0))
1182 : {
1183 : /* The second object is before the first one, we succeed if the last
1184 : element of the second object is before the start of the first one. */
1185 238735 : return known_le (diff->offset + size2, 0);
1186 : }
1187 : else
1188 : {
1189 : /* We succeed if the second object starts after the first one ends. */
1190 1629379 : return known_le (size1, diff->offset);
1191 : }
1192 : }
|
