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 155346695 : wide_int_ext_for_comb (const widest_int &cst, tree type)
42 : {
43 155346695 : return wi::sext (cst, TYPE_PRECISION (type));
44 : }
45 :
46 : /* Likewise for polynomial offsets. */
47 :
48 : static poly_widest_int
49 244162033 : wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
50 : {
51 244162033 : 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 195009327 : aff_combination_zero (aff_tree *comb, tree type)
58 : {
59 195009327 : int i;
60 195009327 : comb->type = type;
61 195009327 : comb->offset = 0;
62 195009327 : comb->n = 0;
63 1755083943 : for (i = 0; i < MAX_AFF_ELTS; i++)
64 1560074616 : comb->elts[i].coef = 0;
65 195009327 : comb->rest = NULL_TREE;
66 195009327 : }
67 :
68 : /* Sets COMB to CST. */
69 :
70 : void
71 112946269 : aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
72 : {
73 112946269 : aff_combination_zero (comb, type);
74 112946269 : comb->offset = wide_int_ext_for_comb (cst, comb->type);;
75 112946269 : }
76 :
77 : /* Sets COMB to single element ELT. */
78 :
79 : void
80 42220573 : aff_combination_elt (aff_tree *comb, tree type, tree elt)
81 : {
82 42220573 : aff_combination_zero (comb, type);
83 :
84 42220573 : comb->n = 1;
85 42220573 : comb->elts[0].val = elt;
86 42220573 : comb->elts[0].coef = 1;
87 42220573 : }
88 :
89 : /* Scales COMB by SCALE. */
90 :
91 : void
92 38859718 : aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
93 : {
94 38859718 : unsigned i, j;
95 :
96 38859718 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
97 38859718 : if (scale == 1)
98 : return;
99 :
100 28265736 : if (scale == 0)
101 : {
102 234 : aff_combination_zero (comb, comb->type);
103 234 : return;
104 : }
105 :
106 28265502 : comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
107 51337762 : for (i = 0, j = 0; i < comb->n; i++)
108 : {
109 23072260 : widest_int new_coef
110 23072260 : = 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 23072260 : if (new_coef == 0)
114 4 : continue;
115 23072256 : comb->elts[j].coef = new_coef;
116 23072256 : comb->elts[j].val = comb->elts[i].val;
117 23072256 : j++;
118 23072260 : }
119 28265502 : comb->n = j;
120 :
121 28265502 : 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 38859718 : }
138 :
139 : /* Adds ELT * SCALE to COMB. */
140 :
141 : void
142 43933435 : aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
143 : {
144 43933435 : unsigned i;
145 43933435 : tree type;
146 :
147 43933435 : widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
148 43933435 : if (scale == 0)
149 : return;
150 :
151 57383774 : for (i = 0; i < comb->n; i++)
152 21958324 : if (operand_equal_p (comb->elts[i].val, elt, 0))
153 : {
154 8507985 : widest_int new_coef
155 8507985 : = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
156 8507985 : if (new_coef != 0)
157 : {
158 128840 : comb->elts[i].coef = new_coef;
159 128840 : return;
160 : }
161 :
162 8379145 : comb->n--;
163 8379145 : comb->elts[i] = comb->elts[comb->n];
164 :
165 8379145 : 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 8507985 : }
175 35425450 : if (comb->n < MAX_AFF_ELTS)
176 : {
177 35424755 : comb->elts[comb->n].coef = scale;
178 35424755 : comb->elts[comb->n].val = elt;
179 35424755 : comb->n++;
180 35424755 : 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 43933435 : }
200 :
201 : /* Adds CST to C. */
202 :
203 : static void
204 102820392 : aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
205 : {
206 102820392 : c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
207 102820392 : }
208 :
209 : /* Adds COMB2 to COMB1. */
210 :
211 : void
212 98635731 : aff_combination_add (aff_tree *comb1, aff_tree *comb2)
213 : {
214 98635731 : unsigned i;
215 :
216 98635731 : aff_combination_add_cst (comb1, comb2->offset);
217 217909108 : for (i = 0; i < comb2->n; i++)
218 20637646 : aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
219 98635731 : if (comb2->rest)
220 180 : aff_combination_add_elt (comb1, comb2->rest, 1);
221 98635731 : }
222 :
223 : /* Converts affine combination COMB to TYPE. AT is the range-query context. */
224 :
225 : void
226 28878809 : aff_combination_convert (aff_tree *comb, tree type, gimple *at)
227 : {
228 28878809 : unsigned i, j;
229 28878809 : tree comb_type = comb->type;
230 :
231 28878809 : if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
232 : {
233 896707 : tree val = fold_convert (type, aff_combination_to_tree (comb));
234 896707 : tree_to_aff_combination (val, type, comb, at);
235 896707 : return;
236 : }
237 :
238 27982102 : comb->type = type;
239 27982102 : if (comb->rest && !POINTER_TYPE_P (type))
240 208 : comb->rest = fold_convert (type, comb->rest);
241 :
242 27982102 : if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
243 : return;
244 :
245 129870 : comb->offset = wide_int_ext_for_comb (comb->offset, comb->type);
246 177522 : for (i = j = 0; i < comb->n; i++)
247 : {
248 47652 : if (comb->elts[i].coef == 0)
249 0 : continue;
250 47652 : comb->elts[j].coef = comb->elts[i].coef;
251 47652 : comb->elts[j].val = fold_convert (type, comb->elts[i].val);
252 47652 : j++;
253 : }
254 :
255 129870 : comb->n = j;
256 129870 : 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 24302842 : expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
271 : tree op0, tree op1 = NULL_TREE, gimple *at = NULL)
272 : {
273 24302842 : aff_tree tmp;
274 :
275 24302842 : switch (code)
276 : {
277 367249 : case POINTER_PLUS_EXPR:
278 367249 : tree_to_aff_combination (op0, type, comb, at);
279 367249 : tree_to_aff_combination (op1, sizetype, &tmp, at);
280 367249 : aff_combination_add (comb, &tmp);
281 367249 : return true;
282 :
283 13952071 : case PLUS_EXPR:
284 13952071 : case MINUS_EXPR:
285 13952071 : tree_to_aff_combination (op0, type, comb, at);
286 13952071 : tree_to_aff_combination (op1, type, &tmp, at);
287 13952071 : if (code == MINUS_EXPR)
288 559584 : aff_combination_scale (&tmp, -1);
289 13952071 : aff_combination_add (comb, &tmp);
290 13952071 : return true;
291 :
292 6864046 : case MULT_EXPR:
293 6864046 : if (TREE_CODE (op1) != INTEGER_CST)
294 : break;
295 5915464 : tree_to_aff_combination (op0, type, comb, at);
296 5915464 : aff_combination_scale (comb, wi::to_widest (op1));
297 5915464 : return true;
298 :
299 97608 : case NEGATE_EXPR:
300 97608 : tree_to_aff_combination (op0, type, comb, at);
301 97608 : aff_combination_scale (comb, -1);
302 97608 : return true;
303 :
304 3862 : case BIT_NOT_EXPR:
305 : /* ~x = -x - 1 */
306 3862 : tree_to_aff_combination (op0, type, comb, at);
307 3862 : aff_combination_scale (comb, -1);
308 3862 : aff_combination_add_cst (comb, -1);
309 3862 : return true;
310 :
311 3018006 : CASE_CONVERT:
312 3018006 : {
313 3018006 : tree otype = type;
314 3018006 : tree inner = op0;
315 3018006 : tree itype = TREE_TYPE (inner);
316 3018006 : enum tree_code icode = TREE_CODE (inner);
317 :
318 : /* STRIP_NOPS */
319 3018006 : if (tree_nop_conversion_p (otype, itype))
320 : {
321 12811 : tree_to_aff_combination (op0, type, comb, at);
322 12811 : 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 3004918 : if (INTEGRAL_NB_TYPE_P (otype)
328 3004359 : && INTEGRAL_NB_TYPE_P (itype)
329 2981607 : && TYPE_PRECISION (otype) > TYPE_PRECISION (itype)
330 4858169 : && CONVERT_EXPR_P (inner))
331 : {
332 93787 : tree iop = TREE_OPERAND (inner, 0);
333 93787 : tree iotype = TREE_TYPE (iop);
334 93787 : tree_code wcode = TREE_CODE (iop);
335 :
336 93771 : if (INTEGRAL_NB_TYPE_P (iotype)
337 187546 : && tree_nop_conversion_p (itype, iotype))
338 : {
339 74533 : int_range_max vr;
340 74533 : 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 74533 : if (!TYPE_UNSIGNED (itype)
360 58794 : && TYPE_UNSIGNED (iotype)
361 58794 : && (wcode == PLUS_EXPR || wcode == MINUS_EXPR)
362 126407 : && TREE_CODE (TREE_OPERAND (iop, 1)) == INTEGER_CST)
363 : {
364 50612 : tree wop0 = fold_convert (itype, TREE_OPERAND (iop, 0));
365 50612 : tree wop1 = fold_convert (itype, TREE_OPERAND (iop, 1));
366 :
367 50612 : if (query->range_of_expr (vr, wop0, at)
368 50612 : && !vr.varying_p ()
369 92461 : && !vr.undefined_p ())
370 : {
371 41487 : wi::overflow_type ovf1 = wi::OVF_NONE;
372 41487 : wi::overflow_type ovf2 = wi::OVF_NONE;
373 41487 : 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 41487 : if (wcode == PLUS_EXPR)
379 : {
380 41487 : wi::add (vr.lower_bound (), cst, SIGNED, &ovf1);
381 41487 : 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 41487 : if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE)
390 : {
391 10998 : wop0 = fold_convert (otype, wop0);
392 10998 : wop1 = fold_convert (otype, wop1);
393 10998 : return expr_to_aff_combination (comb, wcode, otype,
394 : wop0, wop1, at);
395 : }
396 41487 : }
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 63535 : if (TYPE_SIGN (itype) == TYPE_SIGN (iotype)
405 63535 : || (TREE_CODE (iop) == INTEGER_CST
406 63535 : ? int_fits_type_p (iop, itype)
407 63535 : : (query->range_of_expr (vr, iop, at)
408 63535 : && range_fits_type_p (&vr, TYPE_PRECISION (itype),
409 63535 : TYPE_SIGN (itype)))))
410 : {
411 7833 : tree_to_aff_combination (fold_convert (otype, iop), type,
412 : comb, at);
413 7833 : return true;
414 : }
415 74533 : }
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 2986364 : if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
421 246431 : && INTEGRAL_NB_TYPE_P (itype)
422 246431 : && INTEGRAL_NB_TYPE_P (otype)
423 3232795 : && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
424 : {
425 191486 : 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 191486 : if (TYPE_OVERFLOW_UNDEFINED (itype)
432 92654 : && (TREE_CODE (op1) == INTEGER_CST
433 3666 : || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
434 : {
435 88988 : op0 = fold_convert (otype, op0);
436 88988 : op1 = fold_convert (otype, op1);
437 88988 : return expr_to_aff_combination (comb, icode, otype, op0, op1,
438 103529 : at);
439 : }
440 102498 : 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 102498 : int_range_max vr;
446 102498 : if (TYPE_UNSIGNED (itype)
447 98584 : && TYPE_OVERFLOW_WRAPS (itype)
448 98584 : && TREE_CODE (op1) == INTEGER_CST
449 143130 : && get_range_query (cfun)->range_of_expr (vr, op0, at)
450 71565 : && !vr.varying_p ()
451 122874 : && !vr.undefined_p ())
452 : {
453 20362 : wide_int minv = vr.lower_bound ();
454 20362 : wide_int maxv = vr.upper_bound ();
455 20362 : wi::overflow_type overflow = wi::OVF_NONE;
456 20362 : signop sign = UNSIGNED;
457 20362 : if (icode == PLUS_EXPR)
458 15645 : wi::add (maxv, wi::to_wide (op1), sign, &overflow);
459 4717 : else if (icode == MULT_EXPR)
460 4717 : wi::mul (maxv, wi::to_wide (op1), sign, &overflow);
461 : else
462 0 : wi::sub (minv, wi::to_wide (op1), sign, &overflow);
463 :
464 20362 : if (overflow == wi::OVF_NONE)
465 : {
466 6510 : op0 = fold_convert (otype, op0);
467 6510 : op1 = fold_convert (otype, op1);
468 6510 : return expr_to_aff_combination (comb, icode, otype, op0,
469 6510 : 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 13852 : else if (icode == PLUS_EXPR
480 13852 : && wi::neg_p (wi::to_wide (op1), SIGNED))
481 : {
482 12696 : wide_int pos_cst = wi::neg (wi::to_wide (op1));
483 12696 : int_range<1> cst_range (itype, pos_cst, pos_cst);
484 12696 : range_op_handler minus (MINUS_EXPR);
485 :
486 12696 : if (minus.overflow_free_p (vr, cst_range))
487 : {
488 8031 : op0 = fold_convert (otype, op0);
489 8031 : op1 = fold_convert (otype,
490 : wide_int_to_tree (itype, pos_cst));
491 8031 : return expr_to_aff_combination (comb, MINUS_EXPR,
492 : otype, op0, op1, at);
493 : }
494 12696 : }
495 20362 : }
496 102498 : }
497 : }
498 : break;
499 :
500 948582 : default:;
501 : }
502 :
503 : return false;
504 24302842 : }
505 :
506 : /* Splits EXPR into an affine combination of parts. AT is the range-query
507 : context. */
508 :
509 : void
510 158347528 : tree_to_aff_combination (tree expr, tree type, aff_tree *comb, gimple *at)
511 : {
512 158347528 : aff_tree tmp;
513 158347528 : enum tree_code code;
514 158347528 : tree core, toffset;
515 158347528 : poly_int64 bitpos, bitsize, bytepos;
516 158347528 : machine_mode mode;
517 158347528 : int unsignedp, reversep, volatilep;
518 :
519 158347528 : STRIP_NOPS (expr);
520 :
521 158347528 : code = TREE_CODE (expr);
522 158347528 : switch (code)
523 : {
524 20962704 : case POINTER_PLUS_EXPR:
525 20962704 : case PLUS_EXPR:
526 20962704 : case MINUS_EXPR:
527 20962704 : case MULT_EXPR:
528 20962704 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
529 20962704 : TREE_OPERAND (expr, 1), at))
530 : return;
531 : break;
532 :
533 100875 : case NEGATE_EXPR:
534 100875 : case BIT_NOT_EXPR:
535 100875 : if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
536 : NULL_TREE, at))
537 : return;
538 : break;
539 :
540 2987455 : 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 2987455 : if (expr_to_aff_combination (comb, code,
544 2987455 : TREE_TYPE (expr), TREE_OPERAND (expr, 0),
545 : NULL_TREE, at))
546 : {
547 122360 : aff_combination_convert (comb, type, at);
548 122360 : return;
549 : }
550 : break;
551 :
552 21991479 : case ADDR_EXPR:
553 : /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
554 21991479 : if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
555 : {
556 621514 : expr = TREE_OPERAND (expr, 0);
557 621514 : tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb, at);
558 621514 : tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp,
559 : at);
560 621514 : aff_combination_add (comb, &tmp);
561 621514 : return;
562 : }
563 21369965 : core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
564 : &toffset, &mode, &unsignedp, &reversep,
565 : &volatilep);
566 42739930 : if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
567 : break;
568 21369965 : aff_combination_const (comb, type, bytepos);
569 21369965 : if (TREE_CODE (core) == MEM_REF)
570 : {
571 225179 : tree mem_offset = TREE_OPERAND (core, 1);
572 225179 : aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset));
573 225179 : core = TREE_OPERAND (core, 0);
574 : }
575 : else
576 21144786 : core = build_fold_addr_expr (core);
577 :
578 21369965 : if (TREE_CODE (core) == ADDR_EXPR)
579 21144786 : aff_combination_add_elt (comb, core, 1);
580 : else
581 : {
582 225179 : tree_to_aff_combination (core, type, &tmp, at);
583 225179 : aff_combination_add (comb, &tmp);
584 : }
585 21369965 : if (toffset)
586 : {
587 62938 : tree_to_aff_combination (toffset, type, &tmp, at);
588 62938 : aff_combination_add (comb, &tmp);
589 : }
590 : return;
591 :
592 112305015 : default:
593 112305015 : {
594 112305015 : if (poly_int_tree_p (expr))
595 : {
596 73849551 : aff_combination_const (comb, type, wi::to_poly_widest (expr));
597 73849551 : return;
598 : }
599 : break;
600 : }
601 : }
602 :
603 42202833 : aff_combination_elt (comb, type, expr);
604 158347528 : }
605 :
606 : /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
607 : combination COMB. */
608 :
609 : static tree
610 40973297 : add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
611 : {
612 40973297 : enum tree_code code;
613 :
614 40973297 : widest_int scale = wide_int_ext_for_comb (scale_in, type);
615 :
616 40973297 : elt = fold_convert (type, elt);
617 40973297 : if (scale == 1)
618 : {
619 34948735 : if (!expr)
620 : return elt;
621 :
622 13663172 : return fold_build2 (PLUS_EXPR, type, expr, elt);
623 : }
624 :
625 6024562 : if (scale == -1)
626 : {
627 2804990 : if (!expr)
628 1668261 : return fold_build1 (NEGATE_EXPR, type, elt);
629 :
630 1136729 : return fold_build2 (MINUS_EXPR, type, expr, elt);
631 : }
632 :
633 3219572 : if (!expr)
634 1900832 : return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
635 :
636 1318740 : if (wi::neg_p (scale))
637 : {
638 341444 : code = MINUS_EXPR;
639 341444 : scale = -scale;
640 : }
641 : else
642 : code = PLUS_EXPR;
643 :
644 1318740 : elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
645 1318740 : return fold_build2 (code, type, expr, elt);
646 40973297 : }
647 :
648 : /* Makes tree from the affine combination COMB. */
649 :
650 : tree
651 24854656 : aff_combination_to_tree (aff_tree *comb)
652 : {
653 24854656 : tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
654 24854656 : unsigned i;
655 24854656 : poly_widest_int off;
656 24854656 : int sgn;
657 :
658 24854656 : gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
659 :
660 24854656 : i = 0;
661 24854656 : if (POINTER_TYPE_P (type))
662 : {
663 122637 : type = sizetype;
664 245125 : if (comb->n > 0 && comb->elts[0].coef == 1
665 245125 : && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
666 : {
667 24854656 : base = comb->elts[0].val;
668 24854656 : ++i;
669 : }
670 : }
671 :
672 40973027 : for (; i < comb->n; i++)
673 16118371 : expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);
674 :
675 24854656 : 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 24854656 : if (known_lt (comb->offset, 0))
681 : {
682 2222127 : off = -comb->offset;
683 2222127 : sgn = -1;
684 : }
685 : else
686 : {
687 22632529 : off = comb->offset;
688 22632529 : sgn = 1;
689 : }
690 24854656 : expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);
691 :
692 24854656 : if (base)
693 118478 : return fold_build_pointer_plus (base, expr);
694 : else
695 24736178 : return fold_convert (comb->type, expr);
696 24854656 : }
697 :
698 : /* Copies the tree elements of COMB to ensure that they are not shared. */
699 :
700 : void
701 1816851 : unshare_aff_combination (aff_tree *comb)
702 : {
703 1816851 : unsigned i;
704 :
705 3861225 : for (i = 0; i < comb->n; i++)
706 2044374 : comb->elts[i].val = unshare_expr (comb->elts[i].val);
707 1816851 : if (comb->rest)
708 0 : comb->rest = unshare_expr (comb->rest);
709 1816851 : }
710 :
711 : /* Remove M-th element from COMB. */
712 :
713 : void
714 1787079 : aff_combination_remove_elt (aff_tree *comb, unsigned m)
715 : {
716 1787079 : comb->n--;
717 1787079 : if (m <= comb->n)
718 1787079 : comb->elts[m] = comb->elts[comb->n];
719 1787079 : 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 1787079 : }
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 3955620 : aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
734 : aff_tree *r)
735 : {
736 3955620 : unsigned i;
737 3955620 : tree aval, type;
738 :
739 5384726 : for (i = 0; i < c->n; i++)
740 : {
741 1429106 : aval = c->elts[i].val;
742 1429106 : 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 1429106 : aff_combination_add_elt (r, aval, coef * c->elts[i].coef);
750 : }
751 :
752 3955620 : 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 3955620 : 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 3955620 : aff_combination_add_cst (r, coef * c->offset);
781 3955620 : }
782 :
783 : /* Multiplies C1 by C2, storing the result to R */
784 :
785 : void
786 3955620 : aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
787 : {
788 3955620 : unsigned i;
789 3955620 : gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
790 :
791 3955620 : aff_combination_zero (r, c1->type);
792 :
793 7911240 : for (i = 0; i < c2->n; i++)
794 0 : aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
795 3955620 : if (c2->rest)
796 0 : aff_combination_add_product (c1, 1, c2->rest, r);
797 3955620 : if (c2->offset.is_constant ())
798 : /* Access coeffs[0] directly, for efficiency. */
799 3955620 : 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 3955620 : }
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 1196487 : aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
814 : {
815 1196487 : unsigned i;
816 :
817 1527734 : for (i = 0; i < comb->n; i++)
818 1201640 : if (operand_equal_p (comb->elts[i].val, val, 0))
819 : {
820 870393 : if (idx)
821 0 : *idx = i;
822 :
823 870393 : 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 284800 : 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 35172152 : aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
846 : hash_map<tree, name_expansion *> **cache)
847 : {
848 35172152 : unsigned i;
849 105516456 : aff_tree to_add, current, curre;
850 35172152 : tree e;
851 35172152 : gimple *def;
852 35172152 : widest_int scale;
853 35172152 : class name_expansion *exp;
854 :
855 35172152 : aff_combination_zero (&to_add, comb->type);
856 73894952 : for (i = 0; i < comb->n; i++)
857 : {
858 3550648 : tree type, name;
859 3550648 : enum tree_code code;
860 :
861 3550648 : e = comb->elts[i].val;
862 3550648 : type = TREE_TYPE (e);
863 3550648 : name = e;
864 : /* Look through some conversions. */
865 3415180 : if (CONVERT_EXPR_P (e)
866 3550648 : && (TYPE_PRECISION (type)
867 135468 : >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
868 87254 : name = TREE_OPERAND (e, 0);
869 3550648 : if (TREE_CODE (name) != SSA_NAME)
870 2836169 : continue;
871 3323404 : def = SSA_NAME_DEF_STMT (name);
872 3323404 : if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
873 1838806 : continue;
874 :
875 1484598 : code = gimple_assign_rhs_code (def);
876 1503609 : if (code != SSA_NAME
877 1483978 : && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
878 1503613 : && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
879 19015 : || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
880 19011 : continue;
881 :
882 : /* We do not know whether the reference retains its value at the
883 : place where the expansion is used. */
884 1465587 : if (TREE_CODE_CLASS (code) == tcc_reference)
885 586658 : continue;
886 :
887 878929 : name_expansion **slot = NULL;
888 878929 : if (*cache)
889 751721 : slot = (*cache)->get (name);
890 751721 : exp = slot ? *slot : NULL;
891 878929 : if (!exp)
892 : {
893 : /* Only bother to handle cases tree_to_aff_combination will. */
894 235650 : switch (code)
895 : {
896 106135 : case POINTER_PLUS_EXPR:
897 106135 : case PLUS_EXPR:
898 106135 : case MINUS_EXPR:
899 106135 : case MULT_EXPR:
900 106135 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
901 : gimple_assign_rhs1 (def),
902 : gimple_assign_rhs2 (def)))
903 66308 : continue;
904 : break;
905 595 : case NEGATE_EXPR:
906 595 : case BIT_NOT_EXPR:
907 595 : if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name),
908 : gimple_assign_rhs1 (def)))
909 0 : continue;
910 : break;
911 30551 : CASE_CONVERT:
912 30551 : 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 35480 : aff_combination_elt (¤t, TREE_TYPE (name),
920 17740 : fold_convert (TREE_TYPE (name),
921 : gimple_assign_rhs1 (def)));
922 : break;
923 227 : case ADDR_EXPR:
924 227 : case INTEGER_CST:
925 227 : case POLY_INT_CST:
926 227 : tree_to_aff_combination (gimple_assign_rhs1 (def),
927 227 : TREE_TYPE (name), ¤t);
928 227 : break;
929 98142 : default:
930 98142 : continue;
931 : }
932 71200 : exp = XNEW (class name_expansion);
933 71200 : ::new (static_cast<void *> (exp)) name_expansion ();
934 71200 : exp->in_progress = 1;
935 71200 : if (!*cache)
936 31847 : *cache = new hash_map<tree, name_expansion *>;
937 71200 : (*cache)->put (name, exp);
938 71200 : aff_combination_expand (¤t, cache);
939 71200 : exp->expansion = current;
940 71200 : 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 643279 : gcc_assert (!exp->in_progress);
947 643279 : current = exp->expansion;
948 : }
949 714479 : if (!useless_type_conversion_p (comb->type, current.type))
950 81741 : 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 714479 : scale = comb->elts[i].coef;
956 714479 : aff_combination_zero (&curre, comb->type);
957 714479 : aff_combination_add_elt (&curre, e, -scale);
958 714479 : aff_combination_scale (¤t, scale);
959 714479 : aff_combination_add (&to_add, ¤t);
960 714479 : aff_combination_add (&to_add, &curre);
961 : }
962 35172152 : aff_combination_add (comb, &to_add);
963 35172152 : }
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 34982744 : tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
977 : hash_map<tree, name_expansion *> **cache)
978 : {
979 34982744 : tree_to_aff_combination (expr, type, comb);
980 34982744 : aff_combination_expand (comb, cache);
981 34982744 : }
982 :
983 : /* Frees memory occupied by struct name_expansion in *VALUE. Callback for
984 : hash_map::traverse. */
985 :
986 : bool
987 71200 : free_name_expansion (tree const &, name_expansion **value, void *)
988 : {
989 71200 : (*value)->~name_expansion ();
990 71200 : free (*value);
991 71200 : return true;
992 : }
993 :
994 : /* Frees memory allocated for the CACHE used by
995 : tree_to_aff_combination_expand. */
996 :
997 : void
998 1779264 : free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
999 : {
1000 1779264 : if (!*cache)
1001 : return;
1002 :
1003 103047 : (*cache)->traverse<void *, free_name_expansion> (NULL);
1004 63694 : delete (*cache);
1005 31847 : *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 17418077 : 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 17418077 : poly_widest_int cst;
1020 :
1021 17418077 : if (known_eq (val, 0))
1022 : {
1023 1177623 : 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 16240454 : if (maybe_eq (div, 0))
1034 : return false;
1035 :
1036 16239096 : if (!multiple_p (val, div, &cst))
1037 : return false;
1038 :
1039 14377403 : if (*mult_set && maybe_ne (*mult, cst))
1040 : return false;
1041 :
1042 14358411 : *mult_set = true;
1043 14358411 : *mult = cst;
1044 14358411 : return true;
1045 17418077 : }
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 17404957 : aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
1052 : poly_widest_int *mult)
1053 : {
1054 17404957 : bool mult_set = false;
1055 17404957 : unsigned i;
1056 :
1057 17404957 : if (val->n == 0 && known_eq (val->offset, 0))
1058 : {
1059 53172 : *mult = 0;
1060 53172 : return true;
1061 : }
1062 17351785 : if (val->n != div->n)
1063 : return false;
1064 :
1065 16547684 : if (val->rest || div->rest)
1066 : return false;
1067 :
1068 16547684 : if (!wide_int_constant_multiple_p (val->offset, div->offset,
1069 : &mult_set, mult))
1070 : return false;
1071 :
1072 15536034 : for (i = 0; i < div->n; i++)
1073 : {
1074 1196487 : class aff_comb_elt *elt
1075 1196487 : = aff_combination_find_elt (val, div->elts[i].val, NULL);
1076 1196487 : if (!elt)
1077 : return false;
1078 870393 : if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
1079 : &mult_set, mult))
1080 : return false;
1081 : }
1082 :
1083 14339547 : 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 17501671 : get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1138 : {
1139 17501671 : poly_int64 bitsize, bitpos;
1140 17501671 : tree toff;
1141 17501671 : machine_mode mode;
1142 17501671 : int uns, rev, vol;
1143 17501671 : aff_tree tmp;
1144 17501671 : tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1145 : &uns, &rev, &vol);
1146 17501671 : tree base_addr = build_fold_addr_expr (base);
1147 :
1148 : /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */
1149 :
1150 17501671 : tree_to_aff_combination (base_addr, sizetype, addr);
1151 :
1152 17501671 : if (toff)
1153 : {
1154 169079 : tree_to_aff_combination (toff, sizetype, &tmp);
1155 169079 : aff_combination_add (addr, &tmp);
1156 : }
1157 :
1158 17501671 : poly_int64 bytepos = bits_to_bytes_round_down (bitpos);
1159 17501671 : aff_combination_const (&tmp, sizetype, bytepos);
1160 17501671 : aff_combination_add (addr, &tmp);
1161 :
1162 17501671 : *size = bits_to_bytes_round_up (bitpos + bitsize) - bytepos;
1163 :
1164 35003342 : return base;
1165 17501671 : }
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 2857711 : 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 2857711 : if (diff->n != 0)
1176 : return false;
1177 :
1178 1864509 : if (!ordered_p (diff->offset, 0))
1179 : return false;
1180 :
1181 1864509 : 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 238824 : 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 1625685 : return known_le (size1, diff->offset);
1191 : }
1192 : }
|