gcc/tree-affine.cc

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