gcc/tree-affine.cc

   1 /* Operations with affine combinations of trees.
   2    Copyright (C) 2005-2022 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   poly_int64 bitpos, bitsize, bytepos;
 272
 273   switch (code)
 274     {
 275     case POINTER_PLUS_EXPR:
 276       tree_to_aff_combination (op0, type, comb);
 277       tree_to_aff_combination (op1, sizetype, &tmp);
 278       aff_combination_add (comb, &tmp);
 279       return true;
 280
 281     case PLUS_EXPR:
 282     case MINUS_EXPR:
 283       tree_to_aff_combination (op0, type, comb);
 284       tree_to_aff_combination (op1, type, &tmp);
 285       if (code == MINUS_EXPR)
 286         aff_combination_scale (&tmp, -1);
 287       aff_combination_add (comb, &tmp);
 288       return true;
 289
 290     case MULT_EXPR:
 291       if (TREE_CODE (op1) != INTEGER_CST)
 292         break;
 293       tree_to_aff_combination (op0, type, comb);
 294       aff_combination_scale (comb, wi::to_widest (op1));
 295       return true;
 296
 297     case NEGATE_EXPR:
 298       tree_to_aff_combination (op0, type, comb);
 299       aff_combination_scale (comb, -1);
 300       return true;
 301
 302     case BIT_NOT_EXPR:
 303       /* ~x = -x - 1 */
 304       tree_to_aff_combination (op0, type, comb);
 305       aff_combination_scale (comb, -1);
 306       aff_combination_add_cst (comb, -1);
 307       return true;
 308
 309     CASE_CONVERT:
 310       {
 311         tree otype = type;
 312         tree inner = op0;
 313         tree itype = TREE_TYPE (inner);
 314         enum tree_code icode = TREE_CODE (inner);
 315
 316         /* STRIP_NOPS  */
 317         if (tree_nop_conversion_p (otype, itype))
 318           {
 319             tree_to_aff_combination (op0, type, comb);
 320             return true;
 321           }
 322
 323         /* In principle this is a valid folding, but it isn't necessarily
 324            an optimization, so do it here and not in fold_unary.  */
 325         if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
 326             && TREE_CODE (itype) == INTEGER_TYPE
 327             && TREE_CODE (otype) == INTEGER_TYPE
 328             && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
 329           {
 330             tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1);
 331
 332             /* If inner type has undefined overflow behavior, fold conversion
 333                for below two cases:
 334                  (T1)(X *+- CST) -> (T1)X *+- (T1)CST
 335                  (T1)(X + X)     -> (T1)X + (T1)X.  */
 336             if (TYPE_OVERFLOW_UNDEFINED (itype)
 337                 && (TREE_CODE (op1) == INTEGER_CST
 338                     || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
 339               {
 340                 op0 = fold_convert (otype, op0);
 341                 op1 = fold_convert (otype, op1);
 342                 return expr_to_aff_combination (comb, icode, otype, op0, op1);
 343               }
 344             wide_int minv, maxv;
 345             /* If inner type has wrapping overflow behavior, fold conversion
 346                for below case:
 347                  (T1)(X *+- CST) -> (T1)X *+- (T1)CST
 348                if X *+- CST doesn't overflow by range information.  */
 349             value_range vr;
 350             if (TYPE_UNSIGNED (itype)
 351                 && TYPE_OVERFLOW_WRAPS (itype)
 352                 && TREE_CODE (op1) == INTEGER_CST
 353                 && get_range_query (cfun)->range_of_expr (vr, op0)
 354                 && vr.kind () == VR_RANGE)
 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           exp->in_progress = 1;
 809           if (!*cache)
 810             *cache = new hash_map<tree, name_expansion *>;
 811           (*cache)->put (name, exp);
 812           aff_combination_expand (&current, cache);
 813           exp->expansion = current;
 814           exp->in_progress = 0;
 815         }
 816       else
 817         {
 818           /* Since we follow the definitions in the SSA form, we should not
 819              enter a cycle unless we pass through a phi node.  */
 820           gcc_assert (!exp->in_progress);
 821           current = exp->expansion;
 822         }
 823       if (!useless_type_conversion_p (comb->type, current.type))
 824         aff_combination_convert (&current, comb->type);
 825
 826       /* Accumulate the new terms to TO_ADD, so that we do not modify
 827          COMB while traversing it; include the term -coef * E, to remove
 828          it from COMB.  */
 829       scale = comb->elts[i].coef;
 830       aff_combination_zero (&curre, comb->type);
 831       aff_combination_add_elt (&curre, e, -scale);
 832       aff_combination_scale (&current, scale);
 833       aff_combination_add (&to_add, &current);
 834       aff_combination_add (&to_add, &curre);
 835     }
 836   aff_combination_add (comb, &to_add);
 837 }
 838
 839 /* Similar to tree_to_aff_combination, but follows SSA name definitions
 840    and expands them recursively.  CACHE is used to cache the expansions
 841    of the ssa names, to avoid exponential time complexity for cases
 842    like
 843
 844    a1 = a0 + a0;
 845    a2 = a1 + a1;
 846    a3 = a2 + a2;
 847    ...  */
 848
 849 void
 850 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
 851                                 hash_map<tree, name_expansion *> **cache)
 852 {
 853   tree_to_aff_combination (expr, type, comb);
 854   aff_combination_expand (comb, cache);
 855 }
 856
 857 /* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
 858    hash_map::traverse.  */
 859
 860 bool
 861 free_name_expansion (tree const &, name_expansion **value, void *)
 862 {
 863   free (*value);
 864   return true;
 865 }
 866
 867 /* Frees memory allocated for the CACHE used by
 868    tree_to_aff_combination_expand.  */
 869
 870 void
 871 free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
 872 {
 873   if (!*cache)
 874     return;
 875
 876   (*cache)->traverse<void *, free_name_expansion> (NULL);
 877   delete (*cache);
 878   *cache = NULL;
 879 }
 880
 881 /* If VAL != CST * DIV for any constant CST, returns false.
 882    Otherwise, if *MULT_SET is true, additionally compares CST and MULT,
 883    and if they are different, returns false.  Finally, if neither of these
 884    two cases occur, true is returned, and CST is stored to MULT and MULT_SET
 885    is set to true.  */
 886
 887 static bool
 888 wide_int_constant_multiple_p (const poly_widest_int &val,
 889                               const poly_widest_int &div,
 890                               bool *mult_set, poly_widest_int *mult)
 891 {
 892   poly_widest_int rem, cst;
 893
 894   if (known_eq (val, 0))
 895     {
 896       if (*mult_set && maybe_ne (*mult, 0))
 897         return false;
 898       *mult_set = true;
 899       *mult = 0;
 900       return true;
 901     }
 902
 903   if (maybe_eq (div, 0))
 904     return false;
 905
 906   if (!multiple_p (val, div, &cst))
 907     return false;
 908
 909   if (*mult_set && maybe_ne (*mult, cst))
 910     return false;
 911
 912   *mult_set = true;
 913   *mult = cst;
 914   return true;
 915 }
 916
 917 /* Returns true if VAL = X * DIV for some constant X.  If this is the case,
 918    X is stored to MULT.  */
 919
 920 bool
 921 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
 922                                      poly_widest_int *mult)
 923 {
 924   bool mult_set = false;
 925   unsigned i;
 926
 927   if (val->n == 0 && known_eq (val->offset, 0))
 928     {
 929       *mult = 0;
 930       return true;
 931     }
 932   if (val->n != div->n)
 933     return false;
 934
 935   if (val->rest || div->rest)
 936     return false;
 937
 938   if (!wide_int_constant_multiple_p (val->offset, div->offset,
 939                                      &mult_set, mult))
 940     return false;
 941
 942   for (i = 0; i < div->n; i++)
 943     {
 944       class aff_comb_elt *elt
 945               = aff_combination_find_elt (val, div->elts[i].val, NULL);
 946       if (!elt)
 947         return false;
 948       if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
 949                                          &mult_set, mult))
 950         return false;
 951     }
 952
 953   gcc_assert (mult_set);
 954   return true;
 955 }
 956
 957 /* Prints the affine VAL to the FILE. */
 958
 959 static void
 960 print_aff (FILE *file, aff_tree *val)
 961 {
 962   unsigned i;
 963   signop sgn = TYPE_SIGN (val->type);
 964   if (POINTER_TYPE_P (val->type))
 965     sgn = SIGNED;
 966   fprintf (file, "{\n  type = ");
 967   print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
 968   fprintf (file, "\n  offset = ");
 969   print_dec (val->offset, file, sgn);
 970   if (val->n > 0)
 971     {
 972       fprintf (file, "\n  elements = {\n");
 973       for (i = 0; i < val->n; i++)
 974         {
 975           fprintf (file, "    [%d] = ", i);
 976           print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
 977
 978           fprintf (file, " * ");
 979           print_dec (val->elts[i].coef, file, sgn);
 980           if (i != val->n - 1)
 981             fprintf (file, ", \n");
 982         }
 983       fprintf (file, "\n  }");
 984   }
 985   if (val->rest)
 986     {
 987       fprintf (file, "\n  rest = ");
 988       print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
 989     }
 990   fprintf (file, "\n}");
 991 }
 992
 993 /* Prints the affine VAL to the standard error, used for debugging.  */
 994
 995 DEBUG_FUNCTION void
 996 debug_aff (aff_tree *val)
 997 {
 998   print_aff (stderr, val);
 999   fprintf (stderr, "\n");
1000 }
1001
1002 /* Computes address of the reference REF in ADDR.  The size of the accessed
1003    location is stored to SIZE.  Returns the ultimate containing object to
1004    which REF refers.  */
1005
1006 tree
1007 get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
1008 {
1009   poly_int64 bitsize, bitpos;
1010   tree toff;
1011   machine_mode mode;
1012   int uns, rev, vol;
1013   aff_tree tmp;
1014   tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
1015                                    &uns, &rev, &vol);
1016   tree base_addr = build_fold_addr_expr (base);
1017
1018   /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT.  */
1019
1020   tree_to_aff_combination (base_addr, sizetype, addr);
1021
1022   if (toff)
1023     {
1024       tree_to_aff_combination (toff, sizetype, &tmp);
1025       aff_combination_add (addr, &tmp);
1026     }
1027
1028   aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos));
1029   aff_combination_add (addr, &tmp);
1030
1031   *size = bits_to_bytes_round_up (bitsize);
1032
1033   return base;
1034 }
1035
1036 /* Returns true if a region of size SIZE1 at position 0 and a region of
1037    size SIZE2 at position DIFF cannot overlap.  */
1038
1039 bool
1040 aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
1041                            const poly_widest_int &size2)
1042 {
1043   /* Unless the difference is a constant, we fail.  */
1044   if (diff->n != 0)
1045     return false;
1046
1047   if (!ordered_p (diff->offset, 0))
1048     return false;
1049
1050   if (maybe_lt (diff->offset, 0))
1051     {
1052       /* The second object is before the first one, we succeed if the last
1053          element of the second object is before the start of the first one.  */
1054       return known_le (diff->offset + size2, 0);
1055     }
1056   else
1057     {
1058       /* We succeed if the second object starts after the first one ends.  */
1059       return known_le (size1, diff->offset);
1060     }
1061 }
1062