Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-affine.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 12 Feb 2010 23:39:51 +0900 |
parents | a06113de4d67 |
children | b7f97abdc517 |
rev | line source |
---|---|
0 | 1 /* Operations with affine combinations of trees. |
2 Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 |
0 | 4 This file is part of GCC. |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
5 |
0 | 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. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
10 |
0 | 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. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
15 |
0 | 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 "tm.h" | |
24 #include "tree.h" | |
25 #include "rtl.h" | |
26 #include "tm_p.h" | |
27 #include "hard-reg-set.h" | |
28 #include "output.h" | |
29 #include "diagnostic.h" | |
30 #include "tree-dump.h" | |
31 #include "pointer-set.h" | |
32 #include "tree-affine.h" | |
33 #include "gimple.h" | |
34 #include "flags.h" | |
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 tree type = comb->type; | |
115 if (POINTER_TYPE_P (type)) | |
116 type = sizetype; | |
117 if (comb->n < MAX_AFF_ELTS) | |
118 { | |
119 comb->elts[comb->n].coef = scale; | |
120 comb->elts[comb->n].val = comb->rest; | |
121 comb->rest = NULL_TREE; | |
122 comb->n++; | |
123 } | |
124 else | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
125 comb->rest = fold_build2 (MULT_EXPR, type, comb->rest, |
0 | 126 double_int_to_tree (type, scale)); |
127 } | |
128 } | |
129 | |
130 /* Adds ELT * SCALE to COMB. */ | |
131 | |
132 void | |
133 aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale) | |
134 { | |
135 unsigned i; | |
136 tree type; | |
137 | |
138 scale = double_int_ext_for_comb (scale, comb); | |
139 if (double_int_zero_p (scale)) | |
140 return; | |
141 | |
142 for (i = 0; i < comb->n; i++) | |
143 if (operand_equal_p (comb->elts[i].val, elt, 0)) | |
144 { | |
145 double_int new_coef; | |
146 | |
147 new_coef = double_int_add (comb->elts[i].coef, scale); | |
148 new_coef = double_int_ext_for_comb (new_coef, comb); | |
149 if (!double_int_zero_p (new_coef)) | |
150 { | |
151 comb->elts[i].coef = new_coef; | |
152 return; | |
153 } | |
154 | |
155 comb->n--; | |
156 comb->elts[i] = comb->elts[comb->n]; | |
157 | |
158 if (comb->rest) | |
159 { | |
160 gcc_assert (comb->n == MAX_AFF_ELTS - 1); | |
161 comb->elts[comb->n].coef = double_int_one; | |
162 comb->elts[comb->n].val = comb->rest; | |
163 comb->rest = NULL_TREE; | |
164 comb->n++; | |
165 } | |
166 return; | |
167 } | |
168 if (comb->n < MAX_AFF_ELTS) | |
169 { | |
170 comb->elts[comb->n].coef = scale; | |
171 comb->elts[comb->n].val = elt; | |
172 comb->n++; | |
173 return; | |
174 } | |
175 | |
176 type = comb->type; | |
177 if (POINTER_TYPE_P (type)) | |
178 type = sizetype; | |
179 | |
180 if (double_int_one_p (scale)) | |
181 elt = fold_convert (type, elt); | |
182 else | |
183 elt = fold_build2 (MULT_EXPR, type, | |
184 fold_convert (type, elt), | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
185 double_int_to_tree (type, scale)); |
0 | 186 |
187 if (comb->rest) | |
188 comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest, | |
189 elt); | |
190 else | |
191 comb->rest = elt; | |
192 } | |
193 | |
194 /* Adds CST to C. */ | |
195 | |
196 static void | |
197 aff_combination_add_cst (aff_tree *c, double_int cst) | |
198 { | |
199 c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c); | |
200 } | |
201 | |
202 /* Adds COMB2 to COMB1. */ | |
203 | |
204 void | |
205 aff_combination_add (aff_tree *comb1, aff_tree *comb2) | |
206 { | |
207 unsigned i; | |
208 | |
209 aff_combination_add_cst (comb1, comb2->offset); | |
210 for (i = 0; i < comb2->n; i++) | |
211 aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef); | |
212 if (comb2->rest) | |
213 aff_combination_add_elt (comb1, comb2->rest, double_int_one); | |
214 } | |
215 | |
216 /* Converts affine combination COMB to TYPE. */ | |
217 | |
218 void | |
219 aff_combination_convert (aff_tree *comb, tree type) | |
220 { | |
221 unsigned i, j; | |
222 tree comb_type = comb->type; | |
223 | |
224 if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type)) | |
225 { | |
226 tree val = fold_convert (type, aff_combination_to_tree (comb)); | |
227 tree_to_aff_combination (val, type, comb); | |
228 return; | |
229 } | |
230 | |
231 comb->type = type; | |
232 if (comb->rest && !POINTER_TYPE_P (type)) | |
233 comb->rest = fold_convert (type, comb->rest); | |
234 | |
235 if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type)) | |
236 return; | |
237 | |
238 comb->offset = double_int_ext_for_comb (comb->offset, comb); | |
239 for (i = j = 0; i < comb->n; i++) | |
240 { | |
241 double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb); | |
242 if (double_int_zero_p (new_coef)) | |
243 continue; | |
244 comb->elts[j].coef = new_coef; | |
245 comb->elts[j].val = fold_convert (type, comb->elts[i].val); | |
246 j++; | |
247 } | |
248 | |
249 comb->n = j; | |
250 if (comb->n < MAX_AFF_ELTS && comb->rest) | |
251 { | |
252 comb->elts[comb->n].coef = double_int_one; | |
253 comb->elts[comb->n].val = comb->rest; | |
254 comb->rest = NULL_TREE; | |
255 comb->n++; | |
256 } | |
257 } | |
258 | |
259 /* Splits EXPR into an affine combination of parts. */ | |
260 | |
261 void | |
262 tree_to_aff_combination (tree expr, tree type, aff_tree *comb) | |
263 { | |
264 aff_tree tmp; | |
265 enum tree_code code; | |
266 tree cst, core, toffset; | |
267 HOST_WIDE_INT bitpos, bitsize; | |
268 enum machine_mode mode; | |
269 int unsignedp, volatilep; | |
270 | |
271 STRIP_NOPS (expr); | |
272 | |
273 code = TREE_CODE (expr); | |
274 switch (code) | |
275 { | |
276 case INTEGER_CST: | |
277 aff_combination_const (comb, type, tree_to_double_int (expr)); | |
278 return; | |
279 | |
280 case POINTER_PLUS_EXPR: | |
281 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
282 tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); | |
283 aff_combination_add (comb, &tmp); | |
284 return; | |
285 | |
286 case PLUS_EXPR: | |
287 case MINUS_EXPR: | |
288 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
289 tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp); | |
290 if (code == MINUS_EXPR) | |
291 aff_combination_scale (&tmp, double_int_minus_one); | |
292 aff_combination_add (comb, &tmp); | |
293 return; | |
294 | |
295 case MULT_EXPR: | |
296 cst = TREE_OPERAND (expr, 1); | |
297 if (TREE_CODE (cst) != INTEGER_CST) | |
298 break; | |
299 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
300 aff_combination_scale (comb, tree_to_double_int (cst)); | |
301 return; | |
302 | |
303 case NEGATE_EXPR: | |
304 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
305 aff_combination_scale (comb, double_int_minus_one); | |
306 return; | |
307 | |
308 case BIT_NOT_EXPR: | |
309 /* ~x = -x - 1 */ | |
310 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
311 aff_combination_scale (comb, double_int_minus_one); | |
312 aff_combination_add_cst (comb, double_int_minus_one); | |
313 return; | |
314 | |
315 case ADDR_EXPR: | |
316 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, | |
317 &toffset, &mode, &unsignedp, &volatilep, | |
318 false); | |
319 if (bitpos % BITS_PER_UNIT != 0) | |
320 break; | |
321 aff_combination_const (comb, type, | |
322 uhwi_to_double_int (bitpos / BITS_PER_UNIT)); | |
323 core = build_fold_addr_expr (core); | |
324 if (TREE_CODE (core) == ADDR_EXPR) | |
325 aff_combination_add_elt (comb, core, double_int_one); | |
326 else | |
327 { | |
328 tree_to_aff_combination (core, type, &tmp); | |
329 aff_combination_add (comb, &tmp); | |
330 } | |
331 if (toffset) | |
332 { | |
333 tree_to_aff_combination (toffset, type, &tmp); | |
334 aff_combination_add (comb, &tmp); | |
335 } | |
336 return; | |
337 | |
338 default: | |
339 break; | |
340 } | |
341 | |
342 aff_combination_elt (comb, type, expr); | |
343 } | |
344 | |
345 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine | |
346 combination COMB. */ | |
347 | |
348 static tree | |
349 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, | |
350 aff_tree *comb) | |
351 { | |
352 enum tree_code code; | |
353 tree type1 = type; | |
354 if (POINTER_TYPE_P (type)) | |
355 type1 = sizetype; | |
356 | |
357 scale = double_int_ext_for_comb (scale, comb); | |
358 elt = fold_convert (type1, elt); | |
359 | |
360 if (double_int_one_p (scale)) | |
361 { | |
362 if (!expr) | |
363 return fold_convert (type, elt); | |
364 | |
365 if (POINTER_TYPE_P (type)) | |
366 return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt); | |
367 return fold_build2 (PLUS_EXPR, type, expr, elt); | |
368 } | |
369 | |
370 if (double_int_minus_one_p (scale)) | |
371 { | |
372 if (!expr) | |
373 return fold_convert (type, fold_build1 (NEGATE_EXPR, type1, elt)); | |
374 | |
375 if (POINTER_TYPE_P (type)) | |
376 { | |
377 elt = fold_build1 (NEGATE_EXPR, type1, elt); | |
378 return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt); | |
379 } | |
380 return fold_build2 (MINUS_EXPR, type, expr, elt); | |
381 } | |
382 | |
383 if (!expr) | |
384 return fold_convert (type, | |
385 fold_build2 (MULT_EXPR, type1, elt, | |
386 double_int_to_tree (type1, scale))); | |
387 | |
388 if (double_int_negative_p (scale)) | |
389 { | |
390 code = MINUS_EXPR; | |
391 scale = double_int_neg (scale); | |
392 } | |
393 else | |
394 code = PLUS_EXPR; | |
395 | |
396 elt = fold_build2 (MULT_EXPR, type1, elt, | |
397 double_int_to_tree (type1, scale)); | |
398 if (POINTER_TYPE_P (type)) | |
399 { | |
400 if (code == MINUS_EXPR) | |
401 elt = fold_build1 (NEGATE_EXPR, type1, elt); | |
402 return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt); | |
403 } | |
404 return fold_build2 (code, type, expr, elt); | |
405 } | |
406 | |
407 /* Makes tree from the affine combination COMB. */ | |
408 | |
409 tree | |
410 aff_combination_to_tree (aff_tree *comb) | |
411 { | |
412 tree type = comb->type; | |
413 tree expr = comb->rest; | |
414 unsigned i; | |
415 double_int off, sgn; | |
416 tree type1 = type; | |
417 if (POINTER_TYPE_P (type)) | |
418 type1 = sizetype; | |
419 | |
420 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); | |
421 | |
422 for (i = 0; i < comb->n; i++) | |
423 expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef, | |
424 comb); | |
425 | |
426 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is | |
427 unsigned. */ | |
428 if (double_int_negative_p (comb->offset)) | |
429 { | |
430 off = double_int_neg (comb->offset); | |
431 sgn = double_int_minus_one; | |
432 } | |
433 else | |
434 { | |
435 off = comb->offset; | |
436 sgn = double_int_one; | |
437 } | |
438 return add_elt_to_tree (expr, type, double_int_to_tree (type1, off), sgn, | |
439 comb); | |
440 } | |
441 | |
442 /* Copies the tree elements of COMB to ensure that they are not shared. */ | |
443 | |
444 void | |
445 unshare_aff_combination (aff_tree *comb) | |
446 { | |
447 unsigned i; | |
448 | |
449 for (i = 0; i < comb->n; i++) | |
450 comb->elts[i].val = unshare_expr (comb->elts[i].val); | |
451 if (comb->rest) | |
452 comb->rest = unshare_expr (comb->rest); | |
453 } | |
454 | |
455 /* Remove M-th element from COMB. */ | |
456 | |
457 void | |
458 aff_combination_remove_elt (aff_tree *comb, unsigned m) | |
459 { | |
460 comb->n--; | |
461 if (m <= comb->n) | |
462 comb->elts[m] = comb->elts[comb->n]; | |
463 if (comb->rest) | |
464 { | |
465 comb->elts[comb->n].coef = double_int_one; | |
466 comb->elts[comb->n].val = comb->rest; | |
467 comb->rest = NULL_TREE; | |
468 comb->n++; | |
469 } | |
470 } | |
471 | |
472 /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only | |
473 C * COEF is added to R. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
474 |
0 | 475 |
476 static void | |
477 aff_combination_add_product (aff_tree *c, double_int coef, tree val, | |
478 aff_tree *r) | |
479 { | |
480 unsigned i; | |
481 tree aval, type; | |
482 | |
483 for (i = 0; i < c->n; i++) | |
484 { | |
485 aval = c->elts[i].val; | |
486 if (val) | |
487 { | |
488 type = TREE_TYPE (aval); | |
489 aval = fold_build2 (MULT_EXPR, type, aval, | |
490 fold_convert (type, val)); | |
491 } | |
492 | |
493 aff_combination_add_elt (r, aval, | |
494 double_int_mul (coef, c->elts[i].coef)); | |
495 } | |
496 | |
497 if (c->rest) | |
498 { | |
499 aval = c->rest; | |
500 if (val) | |
501 { | |
502 type = TREE_TYPE (aval); | |
503 aval = fold_build2 (MULT_EXPR, type, aval, | |
504 fold_convert (type, val)); | |
505 } | |
506 | |
507 aff_combination_add_elt (r, aval, coef); | |
508 } | |
509 | |
510 if (val) | |
511 aff_combination_add_elt (r, val, | |
512 double_int_mul (coef, c->offset)); | |
513 else | |
514 aff_combination_add_cst (r, double_int_mul (coef, c->offset)); | |
515 } | |
516 | |
517 /* Multiplies C1 by C2, storing the result to R */ | |
518 | |
519 void | |
520 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) | |
521 { | |
522 unsigned i; | |
523 gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type)); | |
524 | |
525 aff_combination_zero (r, c1->type); | |
526 | |
527 for (i = 0; i < c2->n; i++) | |
528 aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); | |
529 if (c2->rest) | |
530 aff_combination_add_product (c1, double_int_one, c2->rest, r); | |
531 aff_combination_add_product (c1, c2->offset, NULL, r); | |
532 } | |
533 | |
534 /* Returns the element of COMB whose value is VAL, or NULL if no such | |
535 element exists. If IDX is not NULL, it is set to the index of VAL in | |
536 COMB. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
537 |
0 | 538 static struct aff_comb_elt * |
539 aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx) | |
540 { | |
541 unsigned i; | |
542 | |
543 for (i = 0; i < comb->n; i++) | |
544 if (operand_equal_p (comb->elts[i].val, val, 0)) | |
545 { | |
546 if (idx) | |
547 *idx = i; | |
548 | |
549 return &comb->elts[i]; | |
550 } | |
551 | |
552 return NULL; | |
553 } | |
554 | |
555 /* Element of the cache that maps ssa name NAME to its expanded form | |
556 as an affine expression EXPANSION. */ | |
557 | |
558 struct name_expansion | |
559 { | |
560 aff_tree expansion; | |
561 | |
562 /* True if the expansion for the name is just being generated. */ | |
563 unsigned in_progress : 1; | |
564 }; | |
565 | |
566 /* Expands SSA names in COMB recursively. CACHE is used to cache the | |
567 results. */ | |
568 | |
569 void | |
570 aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED, | |
571 struct pointer_map_t **cache ATTRIBUTE_UNUSED) | |
572 { | |
573 unsigned i; | |
574 aff_tree to_add, current, curre; | |
575 tree e, rhs; | |
576 gimple def; | |
577 double_int scale; | |
578 void **slot; | |
579 struct name_expansion *exp; | |
580 | |
581 aff_combination_zero (&to_add, comb->type); | |
582 for (i = 0; i < comb->n; i++) | |
583 { | |
584 tree type, name; | |
585 enum tree_code code; | |
586 | |
587 e = comb->elts[i].val; | |
588 type = TREE_TYPE (e); | |
589 name = e; | |
590 /* Look through some conversions. */ | |
591 if (TREE_CODE (e) == NOP_EXPR | |
592 && (TYPE_PRECISION (type) | |
593 >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0))))) | |
594 name = TREE_OPERAND (e, 0); | |
595 if (TREE_CODE (name) != SSA_NAME) | |
596 continue; | |
597 def = SSA_NAME_DEF_STMT (name); | |
598 if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name) | |
599 continue; | |
600 | |
601 code = gimple_assign_rhs_code (def); | |
602 if (code != SSA_NAME | |
603 && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
604 && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS | |
605 || !is_gimple_min_invariant (gimple_assign_rhs1 (def)))) | |
606 continue; | |
607 | |
608 /* We do not know whether the reference retains its value at the | |
609 place where the expansion is used. */ | |
610 if (TREE_CODE_CLASS (code) == tcc_reference) | |
611 continue; | |
612 | |
613 if (!*cache) | |
614 *cache = pointer_map_create (); | |
615 slot = pointer_map_insert (*cache, e); | |
616 exp = (struct name_expansion *) *slot; | |
617 | |
618 if (!exp) | |
619 { | |
620 exp = XNEW (struct name_expansion); | |
621 exp->in_progress = 1; | |
622 *slot = exp; | |
623 /* In principle this is a generally valid folding, but | |
624 it is not unconditionally an optimization, so do it | |
625 here and not in fold_unary. */ | |
626 /* Convert (T1)(X *+- CST) into (T1)X *+- (T1)CST if T1 is wider | |
627 than the type of X and overflow for the type of X is | |
628 undefined. */ | |
629 if (e != name | |
630 && INTEGRAL_TYPE_P (type) | |
631 && INTEGRAL_TYPE_P (TREE_TYPE (name)) | |
632 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (name)) | |
633 && TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (name)) | |
634 && (code == PLUS_EXPR || code == MINUS_EXPR || code == MULT_EXPR) | |
635 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST) | |
636 rhs = fold_build2 (code, type, | |
637 fold_convert (type, gimple_assign_rhs1 (def)), | |
638 fold_convert (type, gimple_assign_rhs2 (def))); | |
639 else | |
640 { | |
641 rhs = gimple_assign_rhs_to_tree (def); | |
642 if (e != name) | |
643 rhs = fold_convert (type, rhs); | |
644 } | |
645 tree_to_aff_combination_expand (rhs, comb->type, ¤t, cache); | |
646 exp->expansion = current; | |
647 exp->in_progress = 0; | |
648 } | |
649 else | |
650 { | |
651 /* Since we follow the definitions in the SSA form, we should not | |
652 enter a cycle unless we pass through a phi node. */ | |
653 gcc_assert (!exp->in_progress); | |
654 current = exp->expansion; | |
655 } | |
656 | |
657 /* Accumulate the new terms to TO_ADD, so that we do not modify | |
658 COMB while traversing it; include the term -coef * E, to remove | |
659 it from COMB. */ | |
660 scale = comb->elts[i].coef; | |
661 aff_combination_zero (&curre, comb->type); | |
662 aff_combination_add_elt (&curre, e, double_int_neg (scale)); | |
663 aff_combination_scale (¤t, scale); | |
664 aff_combination_add (&to_add, ¤t); | |
665 aff_combination_add (&to_add, &curre); | |
666 } | |
667 aff_combination_add (comb, &to_add); | |
668 } | |
669 | |
670 /* Similar to tree_to_aff_combination, but follows SSA name definitions | |
671 and expands them recursively. CACHE is used to cache the expansions | |
672 of the ssa names, to avoid exponential time complexity for cases | |
673 like | |
674 | |
675 a1 = a0 + a0; | |
676 a2 = a1 + a1; | |
677 a3 = a2 + a2; | |
678 ... */ | |
679 | |
680 void | |
681 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, | |
682 struct pointer_map_t **cache) | |
683 { | |
684 tree_to_aff_combination (expr, type, comb); | |
685 aff_combination_expand (comb, cache); | |
686 } | |
687 | |
688 /* Frees memory occupied by struct name_expansion in *VALUE. Callback for | |
689 pointer_map_traverse. */ | |
690 | |
691 static bool | |
692 free_name_expansion (const void *key ATTRIBUTE_UNUSED, void **value, | |
693 void *data ATTRIBUTE_UNUSED) | |
694 { | |
695 struct name_expansion *const exp = (struct name_expansion *) *value; | |
696 | |
697 free (exp); | |
698 return true; | |
699 } | |
700 | |
701 /* Frees memory allocated for the CACHE used by | |
702 tree_to_aff_combination_expand. */ | |
703 | |
704 void | |
705 free_affine_expand_cache (struct pointer_map_t **cache) | |
706 { | |
707 if (!*cache) | |
708 return; | |
709 | |
710 pointer_map_traverse (*cache, free_name_expansion, NULL); | |
711 pointer_map_destroy (*cache); | |
712 *cache = NULL; | |
713 } | |
714 | |
715 /* If VAL != CST * DIV for any constant CST, returns false. | |
716 Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true, | |
717 additionally compares CST and MULT, and if they are different, | |
718 returns false. Finally, if neither of these two cases occur, | |
719 true is returned, and if CST != 0, CST is stored to MULT and | |
720 MULT_SET is set to true. */ | |
721 | |
722 static bool | |
723 double_int_constant_multiple_p (double_int val, double_int div, | |
724 bool *mult_set, double_int *mult) | |
725 { | |
726 double_int rem, cst; | |
727 | |
728 if (double_int_zero_p (val)) | |
729 return true; | |
730 | |
731 if (double_int_zero_p (div)) | |
732 return false; | |
733 | |
734 cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem); | |
735 if (!double_int_zero_p (rem)) | |
736 return false; | |
737 | |
738 if (*mult_set && !double_int_equal_p (*mult, cst)) | |
739 return false; | |
740 | |
741 *mult_set = true; | |
742 *mult = cst; | |
743 return true; | |
744 } | |
745 | |
746 /* Returns true if VAL = X * DIV for some constant X. If this is the case, | |
747 X is stored to MULT. */ | |
748 | |
749 bool | |
750 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, | |
751 double_int *mult) | |
752 { | |
753 bool mult_set = false; | |
754 unsigned i; | |
755 | |
756 if (val->n == 0 && double_int_zero_p (val->offset)) | |
757 { | |
758 *mult = double_int_zero; | |
759 return true; | |
760 } | |
761 if (val->n != div->n) | |
762 return false; | |
763 | |
764 if (val->rest || div->rest) | |
765 return false; | |
766 | |
767 if (!double_int_constant_multiple_p (val->offset, div->offset, | |
768 &mult_set, mult)) | |
769 return false; | |
770 | |
771 for (i = 0; i < div->n; i++) | |
772 { | |
773 struct aff_comb_elt *elt | |
774 = aff_combination_find_elt (val, div->elts[i].val, NULL); | |
775 if (!elt) | |
776 return false; | |
777 if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef, | |
778 &mult_set, mult)) | |
779 return false; | |
780 } | |
781 | |
782 gcc_assert (mult_set); | |
783 return true; | |
784 } | |
785 | |
786 /* Prints the affine VAL to the FILE. */ | |
787 | |
788 void | |
789 print_aff (FILE *file, aff_tree *val) | |
790 { | |
791 unsigned i; | |
792 bool uns = TYPE_UNSIGNED (val->type); | |
793 if (POINTER_TYPE_P (val->type)) | |
794 uns = false; | |
795 fprintf (file, "{\n type = "); | |
796 print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS); | |
797 fprintf (file, "\n offset = "); | |
798 dump_double_int (file, val->offset, uns); | |
799 if (val->n > 0) | |
800 { | |
801 fprintf (file, "\n elements = {\n"); | |
802 for (i = 0; i < val->n; i++) | |
803 { | |
804 fprintf (file, " [%d] = ", i); | |
805 print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
806 |
0 | 807 fprintf (file, " * "); |
808 dump_double_int (file, val->elts[i].coef, uns); | |
809 if (i != val->n - 1) | |
810 fprintf (file, ", \n"); | |
811 } | |
812 fprintf (file, "\n }"); | |
813 } | |
814 if (val->rest) | |
815 { | |
816 fprintf (file, "\n rest = "); | |
817 print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS); | |
818 } | |
819 fprintf (file, "\n}"); | |
820 } | |
821 | |
822 /* Prints the affine VAL to the standard error, used for debugging. */ | |
823 | |
824 void | |
825 debug_aff (aff_tree *val) | |
826 { | |
827 print_aff (stderr, val); | |
828 fprintf (stderr, "\n"); | |
829 } | |
830 | |
831 /* Returns address of the reference REF in ADDR. The size of the accessed | |
832 location is stored to SIZE. */ | |
833 | |
834 void | |
835 get_inner_reference_aff (tree ref, aff_tree *addr, double_int *size) | |
836 { | |
837 HOST_WIDE_INT bitsize, bitpos; | |
838 tree toff; | |
839 enum machine_mode mode; | |
840 int uns, vol; | |
841 aff_tree tmp; | |
842 tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode, | |
843 &uns, &vol, false); | |
844 tree base_addr = build_fold_addr_expr (base); | |
845 | |
846 /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */ | |
847 | |
848 tree_to_aff_combination (base_addr, sizetype, addr); | |
849 | |
850 if (toff) | |
851 { | |
852 tree_to_aff_combination (toff, sizetype, &tmp); | |
853 aff_combination_add (addr, &tmp); | |
854 } | |
855 | |
856 aff_combination_const (&tmp, sizetype, | |
857 shwi_to_double_int (bitpos / BITS_PER_UNIT)); | |
858 aff_combination_add (addr, &tmp); | |
859 | |
860 *size = shwi_to_double_int ((bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT); | |
861 } | |
862 |