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