]>
Commit | Line | Data |
---|---|---|
73f30c63 ZD |
1 | /* Operations with affine combinations of trees. |
2 | Copyright (C) 2005 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 2, 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 COPYING. If not, write to the Free | |
18 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA | |
19 | 02110-1301, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "hard-reg-set.h" | |
29 | #include "output.h" | |
30 | #include "diagnostic.h" | |
31 | #include "tree-dump.h" | |
bbc8a8dc | 32 | #include "pointer-set.h" |
73f30c63 | 33 | #include "tree-affine.h" |
bbc8a8dc | 34 | #include "tree-gimple.h" |
73f30c63 ZD |
35 | |
36 | /* Extends CST as appropriate for the affine combinations COMB. */ | |
37 | ||
38 | double_int | |
39 | double_int_ext_for_comb (double_int cst, aff_tree *comb) | |
40 | { | |
41 | return double_int_sext (cst, TYPE_PRECISION (comb->type)); | |
42 | } | |
43 | ||
44 | /* Initializes affine combination COMB so that its value is zero in TYPE. */ | |
45 | ||
46 | static void | |
47 | aff_combination_zero (aff_tree *comb, tree type) | |
48 | { | |
49 | comb->type = type; | |
50 | comb->offset = double_int_zero; | |
51 | comb->n = 0; | |
52 | comb->rest = NULL_TREE; | |
53 | } | |
54 | ||
55 | /* Sets COMB to CST. */ | |
56 | ||
57 | void | |
58 | aff_combination_const (aff_tree *comb, tree type, double_int cst) | |
59 | { | |
60 | aff_combination_zero (comb, type); | |
61 | comb->offset = double_int_ext_for_comb (cst, comb); | |
62 | } | |
63 | ||
64 | /* Sets COMB to single element ELT. */ | |
65 | ||
66 | void | |
67 | aff_combination_elt (aff_tree *comb, tree type, tree elt) | |
68 | { | |
69 | aff_combination_zero (comb, type); | |
70 | ||
71 | comb->n = 1; | |
72 | comb->elts[0].val = elt; | |
73 | comb->elts[0].coef = double_int_one; | |
74 | } | |
75 | ||
76 | /* Scales COMB by SCALE. */ | |
77 | ||
78 | void | |
79 | aff_combination_scale (aff_tree *comb, double_int scale) | |
80 | { | |
81 | unsigned i, j; | |
82 | ||
83 | scale = double_int_ext_for_comb (scale, comb); | |
84 | if (double_int_one_p (scale)) | |
85 | return; | |
86 | ||
87 | if (double_int_zero_p (scale)) | |
88 | { | |
89 | aff_combination_zero (comb, comb->type); | |
90 | return; | |
91 | } | |
92 | ||
93 | comb->offset | |
94 | = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb); | |
95 | for (i = 0, j = 0; i < comb->n; i++) | |
96 | { | |
97 | double_int new_coef; | |
98 | ||
99 | new_coef | |
100 | = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef), | |
101 | comb); | |
102 | /* A coefficient may become zero due to overflow. Remove the zero | |
103 | elements. */ | |
104 | if (double_int_zero_p (new_coef)) | |
105 | continue; | |
106 | comb->elts[j].coef = new_coef; | |
107 | comb->elts[j].val = comb->elts[i].val; | |
108 | j++; | |
109 | } | |
110 | comb->n = j; | |
111 | ||
112 | if (comb->rest) | |
113 | { | |
114 | if (comb->n < MAX_AFF_ELTS) | |
115 | { | |
116 | comb->elts[comb->n].coef = scale; | |
117 | comb->elts[comb->n].val = comb->rest; | |
118 | comb->rest = NULL_TREE; | |
119 | comb->n++; | |
120 | } | |
121 | else | |
122 | comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest, | |
123 | double_int_to_tree (comb->type, scale)); | |
124 | } | |
125 | } | |
126 | ||
127 | /* Adds ELT * SCALE to COMB. */ | |
128 | ||
129 | void | |
130 | aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale) | |
131 | { | |
132 | unsigned i; | |
133 | ||
134 | scale = double_int_ext_for_comb (scale, comb); | |
135 | if (double_int_zero_p (scale)) | |
136 | return; | |
137 | ||
138 | for (i = 0; i < comb->n; i++) | |
139 | if (operand_equal_p (comb->elts[i].val, elt, 0)) | |
140 | { | |
141 | double_int new_coef; | |
142 | ||
143 | new_coef = double_int_add (comb->elts[i].coef, scale); | |
144 | new_coef = double_int_ext_for_comb (new_coef, comb); | |
145 | if (!double_int_zero_p (new_coef)) | |
146 | { | |
147 | comb->elts[i].coef = new_coef; | |
148 | return; | |
149 | } | |
150 | ||
151 | comb->n--; | |
152 | comb->elts[i] = comb->elts[comb->n]; | |
153 | ||
154 | if (comb->rest) | |
155 | { | |
156 | gcc_assert (comb->n == MAX_AFF_ELTS - 1); | |
157 | comb->elts[comb->n].coef = double_int_one; | |
158 | comb->elts[comb->n].val = comb->rest; | |
159 | comb->rest = NULL_TREE; | |
160 | comb->n++; | |
161 | } | |
162 | return; | |
163 | } | |
164 | if (comb->n < MAX_AFF_ELTS) | |
165 | { | |
166 | comb->elts[comb->n].coef = scale; | |
167 | comb->elts[comb->n].val = elt; | |
168 | comb->n++; | |
169 | return; | |
170 | } | |
171 | ||
172 | if (double_int_one_p (scale)) | |
173 | elt = fold_convert (comb->type, elt); | |
174 | else | |
175 | elt = fold_build2 (MULT_EXPR, comb->type, | |
176 | fold_convert (comb->type, elt), | |
177 | double_int_to_tree (comb->type, scale)); | |
178 | ||
179 | if (comb->rest) | |
180 | comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt); | |
181 | else | |
182 | comb->rest = elt; | |
183 | } | |
184 | ||
7e2ac86c ZD |
185 | /* Adds CST to C. */ |
186 | ||
187 | static void | |
188 | aff_combination_add_cst (aff_tree *c, double_int cst) | |
189 | { | |
190 | c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c); | |
191 | } | |
192 | ||
73f30c63 ZD |
193 | /* Adds COMB2 to COMB1. */ |
194 | ||
195 | void | |
196 | aff_combination_add (aff_tree *comb1, aff_tree *comb2) | |
197 | { | |
198 | unsigned i; | |
199 | ||
7e2ac86c | 200 | aff_combination_add_cst (comb1, comb2->offset); |
73f30c63 ZD |
201 | for (i = 0; i < comb2->n; i++) |
202 | aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef); | |
203 | if (comb2->rest) | |
204 | aff_combination_add_elt (comb1, comb2->rest, double_int_one); | |
205 | } | |
206 | ||
207 | /* Converts affine combination COMB to TYPE. */ | |
208 | ||
209 | void | |
210 | aff_combination_convert (aff_tree *comb, tree type) | |
211 | { | |
212 | unsigned i, j; | |
213 | tree comb_type = comb->type; | |
214 | ||
7e2ac86c ZD |
215 | if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type)) |
216 | { | |
217 | tree val = fold_convert (type, aff_combination_to_tree (comb)); | |
218 | tree_to_aff_combination (val, type, comb); | |
219 | return; | |
220 | } | |
221 | ||
73f30c63 ZD |
222 | comb->type = type; |
223 | if (comb->rest) | |
224 | comb->rest = fold_convert (type, comb->rest); | |
225 | ||
226 | if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type)) | |
227 | return; | |
228 | ||
229 | comb->offset = double_int_ext_for_comb (comb->offset, comb); | |
230 | for (i = j = 0; i < comb->n; i++) | |
231 | { | |
232 | double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb); | |
233 | if (double_int_zero_p (new_coef)) | |
234 | continue; | |
235 | comb->elts[j].coef = new_coef; | |
236 | comb->elts[j].val = fold_convert (type, comb->elts[i].val); | |
237 | j++; | |
238 | } | |
239 | ||
240 | comb->n = j; | |
241 | if (comb->n < MAX_AFF_ELTS && comb->rest) | |
242 | { | |
243 | comb->elts[comb->n].coef = double_int_one; | |
244 | comb->elts[comb->n].val = comb->rest; | |
245 | comb->rest = NULL_TREE; | |
246 | comb->n++; | |
247 | } | |
248 | } | |
249 | ||
250 | /* Splits EXPR into an affine combination of parts. */ | |
251 | ||
252 | void | |
253 | tree_to_aff_combination (tree expr, tree type, aff_tree *comb) | |
254 | { | |
255 | aff_tree tmp; | |
256 | enum tree_code code; | |
257 | tree cst, core, toffset; | |
258 | HOST_WIDE_INT bitpos, bitsize; | |
259 | enum machine_mode mode; | |
260 | int unsignedp, volatilep; | |
261 | ||
262 | STRIP_NOPS (expr); | |
263 | ||
264 | code = TREE_CODE (expr); | |
265 | switch (code) | |
266 | { | |
267 | case INTEGER_CST: | |
268 | aff_combination_const (comb, type, tree_to_double_int (expr)); | |
269 | return; | |
270 | ||
5be014d5 AP |
271 | case POINTER_PLUS_EXPR: |
272 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
273 | tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); | |
274 | aff_combination_convert (&tmp, type); | |
275 | aff_combination_add (comb, &tmp); | |
276 | return; | |
277 | ||
73f30c63 ZD |
278 | case PLUS_EXPR: |
279 | case MINUS_EXPR: | |
280 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
281 | tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp); | |
282 | if (code == MINUS_EXPR) | |
283 | aff_combination_scale (&tmp, double_int_minus_one); | |
284 | aff_combination_add (comb, &tmp); | |
285 | return; | |
286 | ||
287 | case MULT_EXPR: | |
288 | cst = TREE_OPERAND (expr, 1); | |
289 | if (TREE_CODE (cst) != INTEGER_CST) | |
290 | break; | |
291 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
292 | aff_combination_scale (comb, tree_to_double_int (cst)); | |
293 | return; | |
294 | ||
295 | case NEGATE_EXPR: | |
296 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
297 | aff_combination_scale (comb, double_int_minus_one); | |
298 | return; | |
299 | ||
7e2ac86c ZD |
300 | case BIT_NOT_EXPR: |
301 | /* ~x = -x - 1 */ | |
302 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
303 | aff_combination_scale (comb, double_int_minus_one); | |
304 | aff_combination_add_cst (comb, double_int_minus_one); | |
305 | return; | |
306 | ||
73f30c63 ZD |
307 | case ADDR_EXPR: |
308 | core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, | |
309 | &toffset, &mode, &unsignedp, &volatilep, | |
310 | false); | |
311 | if (bitpos % BITS_PER_UNIT != 0) | |
312 | break; | |
313 | aff_combination_const (comb, type, | |
314 | uhwi_to_double_int (bitpos / BITS_PER_UNIT)); | |
315 | core = build_fold_addr_expr (core); | |
316 | if (TREE_CODE (core) == ADDR_EXPR) | |
317 | aff_combination_add_elt (comb, core, double_int_one); | |
318 | else | |
319 | { | |
320 | tree_to_aff_combination (core, type, &tmp); | |
321 | aff_combination_add (comb, &tmp); | |
322 | } | |
323 | if (toffset) | |
324 | { | |
325 | tree_to_aff_combination (toffset, type, &tmp); | |
326 | aff_combination_add (comb, &tmp); | |
327 | } | |
328 | return; | |
329 | ||
330 | default: | |
331 | break; | |
332 | } | |
333 | ||
334 | aff_combination_elt (comb, type, expr); | |
335 | } | |
336 | ||
337 | /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine | |
338 | combination COMB. */ | |
339 | ||
340 | static tree | |
341 | add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, | |
342 | aff_tree *comb) | |
343 | { | |
344 | enum tree_code code; | |
345 | ||
346 | scale = double_int_ext_for_comb (scale, comb); | |
347 | elt = fold_convert (type, elt); | |
348 | ||
349 | if (double_int_one_p (scale)) | |
350 | { | |
351 | if (!expr) | |
352 | return elt; | |
353 | ||
354 | return fold_build2 (PLUS_EXPR, type, expr, elt); | |
355 | } | |
356 | ||
357 | if (double_int_minus_one_p (scale)) | |
358 | { | |
359 | if (!expr) | |
360 | return fold_build1 (NEGATE_EXPR, type, elt); | |
361 | ||
362 | return fold_build2 (MINUS_EXPR, type, expr, elt); | |
363 | } | |
364 | ||
365 | if (!expr) | |
366 | return fold_build2 (MULT_EXPR, type, elt, | |
367 | double_int_to_tree (type, scale)); | |
368 | ||
369 | if (double_int_negative_p (scale)) | |
370 | { | |
371 | code = MINUS_EXPR; | |
372 | scale = double_int_neg (scale); | |
373 | } | |
374 | else | |
375 | code = PLUS_EXPR; | |
376 | ||
377 | elt = fold_build2 (MULT_EXPR, type, elt, | |
378 | double_int_to_tree (type, scale)); | |
379 | return fold_build2 (code, type, expr, elt); | |
380 | } | |
381 | ||
382 | /* Makes tree from the affine combination COMB. */ | |
383 | ||
384 | tree | |
385 | aff_combination_to_tree (aff_tree *comb) | |
386 | { | |
387 | tree type = comb->type; | |
388 | tree expr = comb->rest; | |
389 | unsigned i; | |
390 | double_int off, sgn; | |
391 | ||
392 | gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); | |
393 | ||
394 | for (i = 0; i < comb->n; i++) | |
395 | expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef, | |
396 | comb); | |
397 | ||
398 | /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is | |
399 | unsigned. */ | |
400 | if (double_int_negative_p (comb->offset)) | |
401 | { | |
402 | off = double_int_neg (comb->offset); | |
403 | sgn = double_int_minus_one; | |
404 | } | |
405 | else | |
406 | { | |
407 | off = comb->offset; | |
408 | sgn = double_int_one; | |
409 | } | |
410 | return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn, | |
411 | comb); | |
412 | } | |
413 | ||
414 | /* Copies the tree elements of COMB to ensure that they are not shared. */ | |
415 | ||
416 | void | |
417 | unshare_aff_combination (aff_tree *comb) | |
418 | { | |
419 | unsigned i; | |
420 | ||
421 | for (i = 0; i < comb->n; i++) | |
422 | comb->elts[i].val = unshare_expr (comb->elts[i].val); | |
423 | if (comb->rest) | |
424 | comb->rest = unshare_expr (comb->rest); | |
425 | } | |
426 | ||
427 | /* Remove M-th element from COMB. */ | |
428 | ||
429 | void | |
430 | aff_combination_remove_elt (aff_tree *comb, unsigned m) | |
431 | { | |
432 | comb->n--; | |
433 | if (m <= comb->n) | |
434 | comb->elts[m] = comb->elts[comb->n]; | |
435 | if (comb->rest) | |
436 | { | |
437 | comb->elts[comb->n].coef = double_int_one; | |
438 | comb->elts[comb->n].val = comb->rest; | |
439 | comb->rest = NULL_TREE; | |
440 | comb->n++; | |
441 | } | |
442 | } | |
7e2ac86c ZD |
443 | |
444 | /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only | |
445 | C * COEF is added to R. */ | |
446 | ||
447 | ||
448 | static void | |
449 | aff_combination_add_product (aff_tree *c, double_int coef, tree val, | |
450 | aff_tree *r) | |
451 | { | |
452 | unsigned i; | |
453 | tree aval, type; | |
454 | ||
455 | for (i = 0; i < c->n; i++) | |
456 | { | |
457 | aval = c->elts[i].val; | |
458 | if (val) | |
459 | { | |
460 | type = TREE_TYPE (aval); | |
461 | aval = fold_build2 (MULT_EXPR, type, aval, | |
462 | fold_convert (type, val)); | |
463 | } | |
464 | ||
465 | aff_combination_add_elt (r, aval, | |
466 | double_int_mul (coef, c->elts[i].coef)); | |
467 | } | |
468 | ||
469 | if (c->rest) | |
470 | { | |
471 | aval = c->rest; | |
472 | if (val) | |
473 | { | |
474 | type = TREE_TYPE (aval); | |
475 | aval = fold_build2 (MULT_EXPR, type, aval, | |
476 | fold_convert (type, val)); | |
477 | } | |
478 | ||
479 | aff_combination_add_elt (r, aval, coef); | |
480 | } | |
481 | ||
482 | if (val) | |
483 | aff_combination_add_elt (r, val, | |
484 | double_int_mul (coef, c->offset)); | |
485 | else | |
486 | aff_combination_add_cst (r, double_int_mul (coef, c->offset)); | |
487 | } | |
488 | ||
489 | /* Multiplies C1 by C2, storing the result to R */ | |
490 | ||
491 | void | |
492 | aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) | |
493 | { | |
494 | unsigned i; | |
495 | gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type)); | |
496 | ||
497 | aff_combination_zero (r, c1->type); | |
498 | ||
499 | for (i = 0; i < c2->n; i++) | |
500 | aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); | |
501 | if (c2->rest) | |
502 | aff_combination_add_product (c1, double_int_one, c2->rest, r); | |
503 | aff_combination_add_product (c1, c2->offset, NULL, r); | |
504 | } | |
bbc8a8dc ZD |
505 | |
506 | /* Returns the element of COMB whose value is VAL, or NULL if no such | |
507 | element exists. If IDX is not NULL, it is set to the index of VAL in | |
508 | COMB. */ | |
509 | ||
510 | static struct aff_comb_elt * | |
511 | aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx) | |
512 | { | |
513 | unsigned i; | |
514 | ||
515 | for (i = 0; i < comb->n; i++) | |
516 | if (operand_equal_p (comb->elts[i].val, val, 0)) | |
517 | { | |
518 | if (idx) | |
519 | *idx = i; | |
520 | ||
521 | return &comb->elts[i]; | |
522 | } | |
523 | ||
524 | return NULL; | |
525 | } | |
526 | ||
527 | /* Element of the cache that maps ssa name NAME to its expanded form | |
528 | as an affine expression EXPANSION. */ | |
529 | ||
530 | struct name_expansion | |
531 | { | |
532 | aff_tree expansion; | |
533 | ||
534 | /* True if the expansion for the name is just being generated. */ | |
535 | unsigned in_progress : 1; | |
536 | }; | |
537 | ||
538 | /* Similar to tree_to_aff_combination, but follows SSA name definitions | |
539 | and expands them recursively. CACHE is used to cache the expansions | |
540 | of the ssa names, to avoid exponential time complexity for cases | |
541 | like | |
542 | ||
543 | a1 = a0 + a0; | |
544 | a2 = a1 + a1; | |
545 | a3 = a2 + a2; | |
546 | ... */ | |
547 | ||
548 | void | |
549 | tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, | |
550 | struct pointer_map_t **cache) | |
551 | { | |
552 | unsigned i; | |
553 | aff_tree to_add, current, curre; | |
554 | tree e, def, rhs; | |
555 | double_int scale; | |
556 | void **slot; | |
557 | struct name_expansion *exp; | |
558 | ||
559 | tree_to_aff_combination (expr, type, comb); | |
560 | aff_combination_zero (&to_add, type); | |
561 | for (i = 0; i < comb->n; i++) | |
562 | { | |
563 | e = comb->elts[i].val; | |
564 | if (TREE_CODE (e) != SSA_NAME) | |
565 | continue; | |
566 | def = SSA_NAME_DEF_STMT (e); | |
567 | if (TREE_CODE (def) != GIMPLE_MODIFY_STMT | |
568 | || GIMPLE_STMT_OPERAND (def, 0) != e) | |
569 | continue; | |
570 | ||
571 | rhs = GIMPLE_STMT_OPERAND (def, 1); | |
572 | if (TREE_CODE (rhs) != SSA_NAME | |
573 | && !EXPR_P (rhs) | |
574 | && !is_gimple_min_invariant (rhs)) | |
575 | continue; | |
576 | ||
577 | /* We do not know whether the reference retains its value at the | |
578 | place where the expansion is used. */ | |
579 | if (REFERENCE_CLASS_P (rhs)) | |
580 | continue; | |
581 | ||
582 | if (!*cache) | |
583 | *cache = pointer_map_create (); | |
584 | slot = pointer_map_insert (*cache, e); | |
585 | exp = *slot; | |
586 | ||
587 | if (!exp) | |
588 | { | |
589 | exp = XNEW (struct name_expansion); | |
590 | exp->in_progress = 1; | |
591 | *slot = exp; | |
592 | tree_to_aff_combination_expand (rhs, type, ¤t, cache); | |
593 | exp->expansion = current; | |
594 | exp->in_progress = 0; | |
595 | } | |
596 | else | |
597 | { | |
598 | /* Since we follow the definitions in the SSA form, we should not | |
599 | enter a cycle unless we pass through a phi node. */ | |
600 | gcc_assert (!exp->in_progress); | |
601 | current = exp->expansion; | |
602 | } | |
603 | ||
604 | /* Accumulate the new terms to TO_ADD, so that we do not modify | |
605 | COMB while traversing it; include the term -coef * E, to remove | |
606 | it from COMB. */ | |
607 | scale = comb->elts[i].coef; | |
608 | aff_combination_zero (&curre, type); | |
609 | aff_combination_add_elt (&curre, e, double_int_neg (scale)); | |
610 | aff_combination_scale (¤t, scale); | |
611 | aff_combination_add (&to_add, ¤t); | |
612 | aff_combination_add (&to_add, &curre); | |
613 | } | |
614 | aff_combination_add (comb, &to_add); | |
615 | } | |
616 | ||
617 | /* Frees memory occupied by struct name_expansion in *VALUE. Callback for | |
618 | pointer_map_traverse. */ | |
619 | ||
620 | static bool | |
621 | free_name_expansion (void *key ATTRIBUTE_UNUSED, void **value, | |
622 | void *data ATTRIBUTE_UNUSED) | |
623 | { | |
624 | struct name_expansion *exp = *value; | |
625 | ||
626 | free (exp); | |
627 | return true; | |
628 | } | |
629 | ||
630 | /* Frees memory allocated for the CACHE used by | |
631 | tree_to_aff_combination_expand. */ | |
632 | ||
633 | void | |
634 | free_affine_expand_cache (struct pointer_map_t **cache) | |
635 | { | |
636 | if (!*cache) | |
637 | return; | |
638 | ||
639 | pointer_map_traverse (*cache, free_name_expansion, NULL); | |
640 | pointer_map_destroy (*cache); | |
641 | *cache = NULL; | |
642 | } | |
643 | ||
644 | /* If VAL != CST * DIV for any constant CST, returns false. | |
645 | Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true, | |
646 | additionally compares CST and MULT, and if they are different, | |
c80b4100 | 647 | returns false. Finally, if neither of these two cases occur, |
bbc8a8dc ZD |
648 | true is returned, and if CST != 0, CST is stored to MULT and |
649 | MULT_SET is set to true. */ | |
650 | ||
651 | static bool | |
652 | double_int_constant_multiple_p (double_int val, double_int div, | |
653 | bool *mult_set, double_int *mult) | |
654 | { | |
655 | double_int rem, cst; | |
656 | ||
657 | if (double_int_zero_p (val)) | |
658 | return true; | |
659 | ||
660 | if (double_int_zero_p (div)) | |
661 | return false; | |
662 | ||
663 | cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem); | |
664 | if (!double_int_zero_p (rem)) | |
665 | return false; | |
666 | ||
667 | if (*mult_set && !double_int_equal_p (*mult, cst)) | |
668 | return false; | |
669 | ||
670 | *mult_set = true; | |
671 | *mult = cst; | |
672 | return true; | |
673 | } | |
674 | ||
675 | /* Returns true if VAL = X * DIV for some constant X. If this is the case, | |
676 | X is stored to MULT. */ | |
677 | ||
678 | bool | |
679 | aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, | |
680 | double_int *mult) | |
681 | { | |
682 | bool mult_set = false; | |
683 | unsigned i; | |
684 | ||
685 | if (val->n == 0 && double_int_zero_p (val->offset)) | |
686 | { | |
687 | *mult = double_int_zero; | |
688 | return true; | |
689 | } | |
690 | if (val->n != div->n) | |
691 | return false; | |
692 | ||
693 | if (val->rest || div->rest) | |
694 | return false; | |
695 | ||
696 | if (!double_int_constant_multiple_p (val->offset, div->offset, | |
697 | &mult_set, mult)) | |
698 | return false; | |
699 | ||
700 | for (i = 0; i < div->n; i++) | |
701 | { | |
702 | struct aff_comb_elt *elt | |
703 | = aff_combination_find_elt (val, div->elts[i].val, NULL); | |
704 | if (!elt) | |
705 | return false; | |
706 | if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef, | |
707 | &mult_set, mult)) | |
708 | return false; | |
709 | } | |
710 | ||
711 | gcc_assert (mult_set); | |
712 | return true; | |
713 | } |