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_build_pointer_plus (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_build_pointer_plus (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_build_pointer_plus (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 = NULL_TREE;
 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   if (comb->rest)
 451     expr = add_elt_to_tree (expr, type, comb->rest, double_int_one, comb);
 452
 453   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
 454      unsigned.  */
 455   if (double_int_negative_p (comb->offset))
 456     {
 457       off = double_int_neg (comb->offset);
 458       sgn = double_int_minus_one;
 459     }
 460   else
 461     {
 462       off = comb->offset;
 463       sgn = double_int_one;
 464     }
 465   return add_elt_to_tree (expr, type, double_int_to_tree (type1, off), sgn,
 466                           comb);
 467 }
 468
 469 /* Copies the tree elements of COMB to ensure that they are not shared.  */
 470
 471 void
 472 unshare_aff_combination (aff_tree *comb)
 473 {
 474   unsigned i;
 475
 476   for (i = 0; i < comb->n; i++)
 477     comb->elts[i].val = unshare_expr (comb->elts[i].val);
 478   if (comb->rest)
 479     comb->rest = unshare_expr (comb->rest);
 480 }
 481
 482 /* Remove M-th element from COMB.  */
 483
 484 void
 485 aff_combination_remove_elt (aff_tree *comb, unsigned m)
 486 {
 487   comb->n--;
 488   if (m <= comb->n)
 489     comb->elts[m] = comb->elts[comb->n];
 490   if (comb->rest)
 491     {
 492       comb->elts[comb->n].coef = double_int_one;
 493       comb->elts[comb->n].val = comb->rest;
 494       comb->rest = NULL_TREE;
 495       comb->n++;
 496     }
 497 }
 498
 499 /* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
 500    C * COEF is added to R.  */
 501
 502
 503 static void
 504 aff_combination_add_product (aff_tree *c, double_int coef, tree val,
 505                              aff_tree *r)
 506 {
 507   unsigned i;
 508   tree aval, type;
 509
 510   for (i = 0; i < c->n; i++)
 511     {
 512       aval = c->elts[i].val;
 513       if (val)
 514         {
 515           type = TREE_TYPE (aval);
 516           aval = fold_build2 (MULT_EXPR, type, aval,
 517                               fold_convert (type, val));
 518         }
 519
 520       aff_combination_add_elt (r, aval,
 521                                double_int_mul (coef, c->elts[i].coef));
 522     }
 523
 524   if (c->rest)
 525     {
 526       aval = c->rest;
 527       if (val)
 528         {
 529           type = TREE_TYPE (aval);
 530           aval = fold_build2 (MULT_EXPR, type, aval,
 531                               fold_convert (type, val));
 532         }
 533
 534       aff_combination_add_elt (r, aval, coef);
 535     }
 536
 537   if (val)
 538     aff_combination_add_elt (r, val,
 539                              double_int_mul (coef, c->offset));
 540   else
 541     aff_combination_add_cst (r, double_int_mul (coef, c->offset));
 542 }
 543
 544 /* Multiplies C1 by C2, storing the result to R  */
 545
 546 void
 547 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
 548 {
 549   unsigned i;
 550   gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
 551
 552   aff_combination_zero (r, c1->type);
 553
 554   for (i = 0; i < c2->n; i++)
 555     aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
 556   if (c2->rest)
 557     aff_combination_add_product (c1, double_int_one, c2->rest, r);
 558   aff_combination_add_product (c1, c2->offset, NULL, r);
 559 }
 560
 561 /* Returns the element of COMB whose value is VAL, or NULL if no such
 562    element exists.  If IDX is not NULL, it is set to the index of VAL in
 563    COMB.  */
 564
 565 static struct aff_comb_elt *
 566 aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
 567 {
 568   unsigned i;
 569
 570   for (i = 0; i < comb->n; i++)
 571     if (operand_equal_p (comb->elts[i].val, val, 0))
 572       {
 573         if (idx)
 574           *idx = i;
 575
 576         return &comb->elts[i];
 577       }
 578
 579   return NULL;
 580 }
 581
 582 /* Element of the cache that maps ssa name NAME to its expanded form
 583    as an affine expression EXPANSION.  */
 584
 585 struct name_expansion
 586 {
 587   aff_tree expansion;
 588
 589   /* True if the expansion for the name is just being generated.  */
 590   unsigned in_progress : 1;
 591 };
 592
 593 /* Expands SSA names in COMB recursively.  CACHE is used to cache the
 594    results.  */
 595
 596 void
 597 aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
 598                         struct pointer_map_t **cache ATTRIBUTE_UNUSED)
 599 {
 600   unsigned i;
 601   aff_tree to_add, current, curre;
 602   tree e, rhs;
 603   gimple def;
 604   double_int scale;
 605   void **slot;
 606   struct name_expansion *exp;
 607
 608   aff_combination_zero (&to_add, comb->type);
 609   for (i = 0; i < comb->n; i++)
 610     {
 611       tree type, name;
 612       enum tree_code code;
 613
 614       e = comb->elts[i].val;
 615       type = TREE_TYPE (e);
 616       name = e;
 617       /* Look through some conversions.  */
 618       if (TREE_CODE (e) == NOP_EXPR
 619           && (TYPE_PRECISION (type)
 620               >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
 621         name = TREE_OPERAND (e, 0);
 622       if (TREE_CODE (name) != SSA_NAME)
 623         continue;
 624       def = SSA_NAME_DEF_STMT (name);
 625       if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
 626         continue;
 627
 628       code = gimple_assign_rhs_code (def);
 629       if (code != SSA_NAME
 630           && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
 631           && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
 632               || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
 633         continue;
 634
 635       /* We do not know whether the reference retains its value at the
 636          place where the expansion is used.  */
 637       if (TREE_CODE_CLASS (code) == tcc_reference)
 638         continue;
 639
 640       if (!*cache)
 641         *cache = pointer_map_create ();
 642       slot = pointer_map_insert (*cache, e);
 643       exp = (struct name_expansion *) *slot;
 644
 645       if (!exp)
 646         {
 647           exp = XNEW (struct name_expansion);
 648           exp->in_progress = 1;
 649           *slot = exp;
 650           /* In principle this is a generally valid folding, but
 651              it is not unconditionally an optimization, so do it
 652              here and not in fold_unary.  */
 653           /* Convert (T1)(X *+- CST) into (T1)X *+- (T1)CST if T1 is wider
 654              than the type of X and overflow for the type of X is
 655              undefined.  */
 656           if (e != name
 657               && INTEGRAL_TYPE_P (type)
 658               && INTEGRAL_TYPE_P (TREE_TYPE (name))
 659               && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (name))
 660               && TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (name))
 661               && (code == PLUS_EXPR || code == MINUS_EXPR || code == MULT_EXPR)
 662               && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
 663             rhs = fold_build2 (code, type,
 664                                fold_convert (type, gimple_assign_rhs1 (def)),
 665                                fold_convert (type, gimple_assign_rhs2 (def)));
 666           else
 667             {
 668               rhs = gimple_assign_rhs_to_tree (def);
 669               if (e != name)
 670                 rhs = fold_convert (type, rhs);
 671             }
 672           tree_to_aff_combination_expand (rhs, comb->type, &current, cache);
 673           exp->expansion = current;
 674           exp->in_progress = 0;
 675         }
 676       else
 677         {
 678           /* Since we follow the definitions in the SSA form, we should not
 679              enter a cycle unless we pass through a phi node.  */
 680           gcc_assert (!exp->in_progress);
 681           current = exp->expansion;
 682         }
 683
 684       /* Accumulate the new terms to TO_ADD, so that we do not modify
 685          COMB while traversing it; include the term -coef * E, to remove
 686          it from COMB.  */
 687       scale = comb->elts[i].coef;
 688       aff_combination_zero (&curre, comb->type);
 689       aff_combination_add_elt (&curre, e, double_int_neg (scale));
 690       aff_combination_scale (&current, scale);
 691       aff_combination_add (&to_add, &current);
 692       aff_combination_add (&to_add, &curre);
 693     }
 694   aff_combination_add (comb, &to_add);
 695 }
 696
 697 /* Similar to tree_to_aff_combination, but follows SSA name definitions
 698    and expands them recursively.  CACHE is used to cache the expansions
 699    of the ssa names, to avoid exponential time complexity for cases
 700    like
 701
 702    a1 = a0 + a0;
 703    a2 = a1 + a1;
 704    a3 = a2 + a2;
 705    ...  */
 706
 707 void
 708 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
 709                                 struct pointer_map_t **cache)
 710 {
 711   tree_to_aff_combination (expr, type, comb);
 712   aff_combination_expand (comb, cache);
 713 }
 714
 715 /* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
 716    pointer_map_traverse.  */
 717
 718 static bool
 719 free_name_expansion (const void *key ATTRIBUTE_UNUSED, void **value,
 720                      void *data ATTRIBUTE_UNUSED)
 721 {
 722   struct name_expansion *const exp = (struct name_expansion *) *value;
 723
 724   free (exp);
 725   return true;
 726 }
 727
 728 /* Frees memory allocated for the CACHE used by
 729    tree_to_aff_combination_expand.  */
 730
 731 void
 732 free_affine_expand_cache (struct pointer_map_t **cache)
 733 {
 734   if (!*cache)
 735     return;
 736
 737   pointer_map_traverse (*cache, free_name_expansion, NULL);
 738   pointer_map_destroy (*cache);
 739   *cache = NULL;
 740 }
 741
 742 /* If VAL != CST * DIV for any constant CST, returns false.
 743    Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
 744    additionally compares CST and MULT, and if they are different,
 745    returns false.  Finally, if neither of these two cases occur,
 746    true is returned, and if CST != 0, CST is stored to MULT and
 747    MULT_SET is set to true.  */
 748
 749 static bool
 750 double_int_constant_multiple_p (double_int val, double_int div,
 751                                 bool *mult_set, double_int *mult)
 752 {
 753   double_int rem, cst;
 754
 755   if (double_int_zero_p (val))
 756     return true;
 757
 758   if (double_int_zero_p (div))
 759     return false;
 760
 761   cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem);
 762   if (!double_int_zero_p (rem))
 763     return false;
 764
 765   if (*mult_set && !double_int_equal_p (*mult, cst))
 766     return false;
 767
 768   *mult_set = true;
 769   *mult = cst;
 770   return true;
 771 }
 772
 773 /* Returns true if VAL = X * DIV for some constant X.  If this is the case,
 774    X is stored to MULT.  */
 775
 776 bool
 777 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
 778                                      double_int *mult)
 779 {
 780   bool mult_set = false;
 781   unsigned i;
 782
 783   if (val->n == 0 && double_int_zero_p (val->offset))
 784     {
 785       *mult = double_int_zero;
 786       return true;
 787     }
 788   if (val->n != div->n)
 789     return false;
 790
 791   if (val->rest || div->rest)
 792     return false;
 793
 794   if (!double_int_constant_multiple_p (val->offset, div->offset,
 795                                        &mult_set, mult))
 796     return false;
 797
 798   for (i = 0; i < div->n; i++)
 799     {
 800       struct aff_comb_elt *elt
 801               = aff_combination_find_elt (val, div->elts[i].val, NULL);
 802       if (!elt)
 803         return false;
 804       if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef,
 805                                            &mult_set, mult))
 806         return false;
 807     }
 808
 809   gcc_assert (mult_set);
 810   return true;
 811 }
 812
 813 /* Prints the affine VAL to the FILE. */
 814
 815 static void
 816 print_aff (FILE *file, aff_tree *val)
 817 {
 818   unsigned i;
 819   bool uns = TYPE_UNSIGNED (val->type);
 820   if (POINTER_TYPE_P (val->type))
 821     uns = false;
 822   fprintf (file, "{\n  type = ");
 823   print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
 824   fprintf (file, "\n  offset = ");
 825   dump_double_int (file, val->offset, uns);
 826   if (val->n > 0)
 827     {
 828       fprintf (file, "\n  elements = {\n");
 829       for (i = 0; i < val->n; i++)
 830         {
 831           fprintf (file, "    [%d] = ", i);
 832           print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
 833
 834           fprintf (file, " * ");
 835           dump_double_int (file, val->elts[i].coef, uns);
 836           if (i != val->n - 1)
 837             fprintf (file, ", \n");
 838         }
 839       fprintf (file, "\n  }");
 840   }
 841   if (val->rest)
 842     {
 843       fprintf (file, "\n  rest = ");
 844       print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
 845     }
 846   fprintf (file, "\n}");
 847 }
 848
 849 /* Prints the affine VAL to the standard error, used for debugging.  */
 850
 851 DEBUG_FUNCTION void
 852 debug_aff (aff_tree *val)
 853 {
 854   print_aff (stderr, val);
 855   fprintf (stderr, "\n");
 856 }
 857
 858 /* Returns address of the reference REF in ADDR.  The size of the accessed
 859    location is stored to SIZE.  */
 860
 861 void
 862 get_inner_reference_aff (tree ref, aff_tree *addr, double_int *size)
 863 {
 864   HOST_WIDE_INT bitsize, bitpos;
 865   tree toff;
 866   enum machine_mode mode;
 867   int uns, vol;
 868   aff_tree tmp;
 869   tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
 870                                    &uns, &vol, false);
 871   tree base_addr = build_fold_addr_expr (base);
 872
 873   /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT.  */
 874
 875   tree_to_aff_combination (base_addr, sizetype, addr);
 876
 877   if (toff)
 878     {
 879       tree_to_aff_combination (toff, sizetype, &tmp);
 880       aff_combination_add (addr, &tmp);
 881     }
 882
 883   aff_combination_const (&tmp, sizetype,
 884                          shwi_to_double_int (bitpos / BITS_PER_UNIT));
 885   aff_combination_add (addr, &tmp);
 886
 887   *size = shwi_to_double_int ((bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT);
 888 }
 889
 890 /* Returns true if a region of size SIZE1 at position 0 and a region of
 891    size SIZE2 at position DIFF cannot overlap.  */
 892
 893 bool
 894 aff_comb_cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
 895 {
 896   double_int d, bound;
 897
 898   /* Unless the difference is a constant, we fail.  */
 899   if (diff->n != 0)
 900     return false;
 901
 902   d = diff->offset;
 903   if (double_int_negative_p (d))
 904     {
 905       /* The second object is before the first one, we succeed if the last
 906          element of the second object is before the start of the first one.  */
 907       bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
 908       return double_int_negative_p (bound);
 909     }
 910   else
 911     {
 912       /* We succeed if the second object starts after the first one ends.  */
 913       return double_int_scmp (size1, d) <= 0;
 914     }
 915 }
 916