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