gcc/tree-affine.c

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