|
0
|
1 /* Operations with affine combinations of trees.
|
|
|
2 Copyright (C) 2005, 2007, 2008 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 "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
|
|
|
125 comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
|
|
|
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),
|
|
|
185 double_int_to_tree (type, scale));
|
|
|
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. */
|
|
|
474
|
|
|
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. */
|
|
|
537
|
|
|
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);
|
|
|
806
|
|
|
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
|
