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