gcc/tree-affine.c

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