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       core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
 313                                   &toffset, &mode, &unsignedp, &volatilep,
 314                                   false);
 315       if (bitpos % BITS_PER_UNIT != 0)
 316         break;
 317       aff_combination_const (comb, type,
 318                              uhwi_to_double_int (bitpos / BITS_PER_UNIT));
 319       core = build_fold_addr_expr (core);
 320       if (TREE_CODE (core) == ADDR_EXPR)
 321         aff_combination_add_elt (comb, core, double_int_one);
 322       else
 323         {
 324           tree_to_aff_combination (core, type, &tmp);
 325           aff_combination_add (comb, &tmp);
 326         }
 327       if (toffset)
 328         {
 329           tree_to_aff_combination (toffset, type, &tmp);
 330           aff_combination_add (comb, &tmp);
 331         }
 332       return;
 333
 334     default:
 335       break;
 336     }
 337
 338   aff_combination_elt (comb, type, expr);
 339 }
 340
 341 /* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
 342    combination COMB.  */
 343
 344 static tree
 345 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
 346                  aff_tree *comb)
 347 {
 348   enum tree_code code;
 349   tree type1 = type;
 350   if (POINTER_TYPE_P (type))
 351     type1 = sizetype;
 352
 353   scale = double_int_ext_for_comb (scale, comb);
 354   elt = fold_convert (type1, elt);
 355
 356   if (double_int_one_p (scale))
 357     {
 358       if (!expr)
 359         return fold_convert (type, elt);
 360
 361       if (POINTER_TYPE_P (type))
 362         return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt);
 363       return fold_build2 (PLUS_EXPR, type, expr, elt);
 364     }
 365
 366   if (double_int_minus_one_p (scale))
 367     {
 368       if (!expr)
 369         return fold_convert (type, fold_build1 (NEGATE_EXPR, type1, elt));
 370
 371       if (POINTER_TYPE_P (type))
 372         {
 373           elt = fold_build1 (NEGATE_EXPR, type1, elt);
 374           return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt);
 375         }
 376       return fold_build2 (MINUS_EXPR, type, expr, elt);
 377     }
 378
 379   if (!expr)
 380     return fold_convert (type,
 381                          fold_build2 (MULT_EXPR, type1, elt,
 382                                       double_int_to_tree (type1, scale)));
 383
 384   if (double_int_negative_p (scale))
 385     {
 386       code = MINUS_EXPR;
 387       scale = double_int_neg (scale);
 388     }
 389   else
 390     code = PLUS_EXPR;
 391
 392   elt = fold_build2 (MULT_EXPR, type1, elt,
 393                      double_int_to_tree (type1, scale));
 394   if (POINTER_TYPE_P (type))
 395     {
 396       if (code == MINUS_EXPR)
 397         elt = fold_build1 (NEGATE_EXPR, type1, elt);
 398       return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt);
 399     }
 400   return fold_build2 (code, type, expr, elt);
 401 }
 402
 403 /* Makes tree from the affine combination COMB.  */
 404
 405 tree
 406 aff_combination_to_tree (aff_tree *comb)
 407 {
 408   tree type = comb->type;
 409   tree expr = comb->rest;
 410   unsigned i;
 411   double_int off, sgn;
 412   tree type1 = type;
 413   if (POINTER_TYPE_P (type))
 414     type1 = sizetype;
 415
 416   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 417
 418   for (i = 0; i < comb->n; i++)
 419     expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
 420                             comb);
 421
 422   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
 423      unsigned.  */
 424   if (double_int_negative_p (comb->offset))
 425     {
 426       off = double_int_neg (comb->offset);
 427       sgn = double_int_minus_one;
 428     }
 429   else
 430     {
 431       off = comb->offset;
 432       sgn = double_int_one;
 433     }
 434   return add_elt_to_tree (expr, type, double_int_to_tree (type1, off), sgn,
 435                           comb);
 436 }
 437
 438 /* Copies the tree elements of COMB to ensure that they are not shared.  */
 439
 440 void
 441 unshare_aff_combination (aff_tree *comb)
 442 {
 443   unsigned i;
 444
 445   for (i = 0; i < comb->n; i++)
 446     comb->elts[i].val = unshare_expr (comb->elts[i].val);
 447   if (comb->rest)
 448     comb->rest = unshare_expr (comb->rest);
 449 }
 450
 451 /* Remove M-th element from COMB.  */
 452
 453 void
 454 aff_combination_remove_elt (aff_tree *comb, unsigned m)
 455 {
 456   comb->n--;
 457   if (m <= comb->n)
 458     comb->elts[m] = comb->elts[comb->n];
 459   if (comb->rest)
 460     {
 461       comb->elts[comb->n].coef = double_int_one;
 462       comb->elts[comb->n].val = comb->rest;
 463       comb->rest = NULL_TREE;
 464       comb->n++;
 465     }
 466 }
 467
 468 /* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
 469    C * COEF is added to R.  */
 470
 471
 472 static void
 473 aff_combination_add_product (aff_tree *c, double_int coef, tree val,
 474                              aff_tree *r)
 475 {
 476   unsigned i;
 477   tree aval, type;
 478
 479   for (i = 0; i < c->n; i++)
 480     {
 481       aval = c->elts[i].val;
 482       if (val)
 483         {
 484           type = TREE_TYPE (aval);
 485           aval = fold_build2 (MULT_EXPR, type, aval,
 486                               fold_convert (type, val));
 487         }
 488
 489       aff_combination_add_elt (r, aval,
 490                                double_int_mul (coef, c->elts[i].coef));
 491     }
 492
 493   if (c->rest)
 494     {
 495       aval = c->rest;
 496       if (val)
 497         {
 498           type = TREE_TYPE (aval);
 499           aval = fold_build2 (MULT_EXPR, type, aval,
 500                               fold_convert (type, val));
 501         }
 502
 503       aff_combination_add_elt (r, aval, coef);
 504     }
 505
 506   if (val)
 507     aff_combination_add_elt (r, val,
 508                              double_int_mul (coef, c->offset));
 509   else
 510     aff_combination_add_cst (r, double_int_mul (coef, c->offset));
 511 }
 512
 513 /* Multiplies C1 by C2, storing the result to R  */
 514
 515 void
 516 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
 517 {
 518   unsigned i;
 519   gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
 520
 521   aff_combination_zero (r, c1->type);
 522
 523   for (i = 0; i < c2->n; i++)
 524     aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
 525   if (c2->rest)
 526     aff_combination_add_product (c1, double_int_one, c2->rest, r);
 527   aff_combination_add_product (c1, c2->offset, NULL, r);
 528 }
 529
 530 /* Returns the element of COMB whose value is VAL, or NULL if no such
 531    element exists.  If IDX is not NULL, it is set to the index of VAL in
 532    COMB.  */
 533
 534 static struct aff_comb_elt *
 535 aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
 536 {
 537   unsigned i;
 538
 539   for (i = 0; i < comb->n; i++)
 540     if (operand_equal_p (comb->elts[i].val, val, 0))
 541       {
 542         if (idx)
 543           *idx = i;
 544
 545         return &comb->elts[i];
 546       }
 547
 548   return NULL;
 549 }
 550
 551 /* Element of the cache that maps ssa name NAME to its expanded form
 552    as an affine expression EXPANSION.  */
 553
 554 struct name_expansion
 555 {
 556   aff_tree expansion;
 557
 558   /* True if the expansion for the name is just being generated.  */
 559   unsigned in_progress : 1;
 560 };
 561
 562 /* Expands SSA names in COMB recursively.  CACHE is used to cache the
 563    results.  */
 564
 565 void
 566 aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
 567                         struct pointer_map_t **cache ATTRIBUTE_UNUSED)
 568 {
 569   unsigned i;
 570   aff_tree to_add, current, curre;
 571   tree e, rhs;
 572   gimple def;
 573   double_int scale;
 574   void **slot;
 575   struct name_expansion *exp;
 576
 577   aff_combination_zero (&to_add, comb->type);
 578   for (i = 0; i < comb->n; i++)
 579     {
 580       tree type, name;
 581       enum tree_code code;
 582
 583       e = comb->elts[i].val;
 584       type = TREE_TYPE (e);
 585       name = e;
 586       /* Look through some conversions.  */
 587       if (TREE_CODE (e) == NOP_EXPR
 588           && (TYPE_PRECISION (type)
 589               >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
 590         name = TREE_OPERAND (e, 0);
 591       if (TREE_CODE (name) != SSA_NAME)
 592         continue;
 593       def = SSA_NAME_DEF_STMT (name);
 594       if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
 595         continue;
 596
 597       code = gimple_assign_rhs_code (def);
 598       if (code != SSA_NAME
 599           && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
 600           && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
 601               || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
 602         continue;
 603
 604       /* We do not know whether the reference retains its value at the
 605          place where the expansion is used.  */
 606       if (TREE_CODE_CLASS (code) == tcc_reference)
 607         continue;
 608
 609       if (!*cache)
 610         *cache = pointer_map_create ();
 611       slot = pointer_map_insert (*cache, e);
 612       exp = (struct name_expansion *) *slot;
 613
 614       if (!exp)
 615         {
 616           exp = XNEW (struct name_expansion);
 617           exp->in_progress = 1;
 618           *slot = exp;
 619           /* In principle this is a generally valid folding, but
 620              it is not unconditionally an optimization, so do it
 621              here and not in fold_unary.  */
 622           /* Convert (T1)(X *+- CST) into (T1)X *+- (T1)CST if T1 is wider
 623              than the type of X and overflow for the type of X is
 624              undefined.  */
 625           if (e != name
 626               && INTEGRAL_TYPE_P (type)
 627               && INTEGRAL_TYPE_P (TREE_TYPE (name))
 628               && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (name))
 629               && TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (name))
 630               && (code == PLUS_EXPR || code == MINUS_EXPR || code == MULT_EXPR)
 631               && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
 632             rhs = fold_build2 (code, type,
 633                                fold_convert (type, gimple_assign_rhs1 (def)),
 634                                fold_convert (type, gimple_assign_rhs2 (def)));
 635           else
 636             {
 637               rhs = gimple_assign_rhs_to_tree (def);
 638               if (e != name)
 639                 rhs = fold_convert (type, rhs);
 640             }
 641           tree_to_aff_combination_expand (rhs, comb->type, &current, cache);
 642           exp->expansion = current;
 643           exp->in_progress = 0;
 644         }
 645       else
 646         {
 647           /* Since we follow the definitions in the SSA form, we should not
 648              enter a cycle unless we pass through a phi node.  */
 649           gcc_assert (!exp->in_progress);
 650           current = exp->expansion;
 651         }
 652
 653       /* Accumulate the new terms to TO_ADD, so that we do not modify
 654          COMB while traversing it; include the term -coef * E, to remove
 655          it from COMB.  */
 656       scale = comb->elts[i].coef;
 657       aff_combination_zero (&curre, comb->type);
 658       aff_combination_add_elt (&curre, e, double_int_neg (scale));
 659       aff_combination_scale (&current, scale);
 660       aff_combination_add (&to_add, &current);
 661       aff_combination_add (&to_add, &curre);
 662     }
 663   aff_combination_add (comb, &to_add);
 664 }
 665
 666 /* Similar to tree_to_aff_combination, but follows SSA name definitions
 667    and expands them recursively.  CACHE is used to cache the expansions
 668    of the ssa names, to avoid exponential time complexity for cases
 669    like
 670
 671    a1 = a0 + a0;
 672    a2 = a1 + a1;
 673    a3 = a2 + a2;
 674    ...  */
 675
 676 void
 677 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
 678                                 struct pointer_map_t **cache)
 679 {
 680   tree_to_aff_combination (expr, type, comb);
 681   aff_combination_expand (comb, cache);
 682 }
 683
 684 /* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
 685    pointer_map_traverse.  */
 686
 687 static bool
 688 free_name_expansion (const void *key ATTRIBUTE_UNUSED, void **value,
 689                      void *data ATTRIBUTE_UNUSED)
 690 {
 691   struct name_expansion *const exp = (struct name_expansion *) *value;
 692
 693   free (exp);
 694   return true;
 695 }
 696
 697 /* Frees memory allocated for the CACHE used by
 698    tree_to_aff_combination_expand.  */
 699
 700 void
 701 free_affine_expand_cache (struct pointer_map_t **cache)
 702 {
 703   if (!*cache)
 704     return;
 705
 706   pointer_map_traverse (*cache, free_name_expansion, NULL);
 707   pointer_map_destroy (*cache);
 708   *cache = NULL;
 709 }
 710
 711 /* If VAL != CST * DIV for any constant CST, returns false.
 712    Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
 713    additionally compares CST and MULT, and if they are different,
 714    returns false.  Finally, if neither of these two cases occur,
 715    true is returned, and if CST != 0, CST is stored to MULT and
 716    MULT_SET is set to true.  */
 717
 718 static bool
 719 double_int_constant_multiple_p (double_int val, double_int div,
 720                                 bool *mult_set, double_int *mult)
 721 {
 722   double_int rem, cst;
 723
 724   if (double_int_zero_p (val))
 725     return true;
 726
 727   if (double_int_zero_p (div))
 728     return false;
 729
 730   cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem);
 731   if (!double_int_zero_p (rem))
 732     return false;
 733
 734   if (*mult_set && !double_int_equal_p (*mult, cst))
 735     return false;
 736
 737   *mult_set = true;
 738   *mult = cst;
 739   return true;
 740 }
 741
 742 /* Returns true if VAL = X * DIV for some constant X.  If this is the case,
 743    X is stored to MULT.  */
 744
 745 bool
 746 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
 747                                      double_int *mult)
 748 {
 749   bool mult_set = false;
 750   unsigned i;
 751
 752   if (val->n == 0 && double_int_zero_p (val->offset))
 753     {
 754       *mult = double_int_zero;
 755       return true;
 756     }
 757   if (val->n != div->n)
 758     return false;
 759
 760   if (val->rest || div->rest)
 761     return false;
 762
 763   if (!double_int_constant_multiple_p (val->offset, div->offset,
 764                                        &mult_set, mult))
 765     return false;
 766
 767   for (i = 0; i < div->n; i++)
 768     {
 769       struct aff_comb_elt *elt
 770               = aff_combination_find_elt (val, div->elts[i].val, NULL);
 771       if (!elt)
 772         return false;
 773       if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef,
 774                                            &mult_set, mult))
 775         return false;
 776     }
 777
 778   gcc_assert (mult_set);
 779   return true;
 780 }
 781
 782 /* Prints the affine VAL to the FILE. */
 783
 784 void
 785 print_aff (FILE *file, aff_tree *val)
 786 {
 787   unsigned i;
 788   bool uns = TYPE_UNSIGNED (val->type);
 789   if (POINTER_TYPE_P (val->type))
 790     uns = false;
 791   fprintf (file, "{\n  type = ");
 792   print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
 793   fprintf (file, "\n  offset = ");
 794   dump_double_int (file, val->offset, uns);
 795   if (val->n > 0)
 796     {
 797       fprintf (file, "\n  elements = {\n");
 798       for (i = 0; i < val->n; i++)
 799         {
 800           fprintf (file, "    [%d] = ", i);
 801           print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
 802
 803           fprintf (file, " * ");
 804           dump_double_int (file, val->elts[i].coef, uns);
 805           if (i != val->n - 1)
 806             fprintf (file, ", \n");
 807         }
 808       fprintf (file, "\n  }");
 809   }
 810   if (val->rest)
 811     {
 812       fprintf (file, "\n  rest = ");
 813       print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
 814     }
 815   fprintf (file, "\n}");
 816 }
 817
 818 /* Prints the affine VAL to the standard error, used for debugging.  */
 819
 820 DEBUG_FUNCTION void
 821 debug_aff (aff_tree *val)
 822 {
 823   print_aff (stderr, val);
 824   fprintf (stderr, "\n");
 825 }
 826
 827 /* Returns address of the reference REF in ADDR.  The size of the accessed
 828    location is stored to SIZE.  */
 829
 830 void
 831 get_inner_reference_aff (tree ref, aff_tree *addr, double_int *size)
 832 {
 833   HOST_WIDE_INT bitsize, bitpos;
 834   tree toff;
 835   enum machine_mode mode;
 836   int uns, vol;
 837   aff_tree tmp;
 838   tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
 839                                    &uns, &vol, false);
 840   tree base_addr = build_fold_addr_expr (base);
 841
 842   /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT.  */
 843
 844   tree_to_aff_combination (base_addr, sizetype, addr);
 845
 846   if (toff)
 847     {
 848       tree_to_aff_combination (toff, sizetype, &tmp);
 849       aff_combination_add (addr, &tmp);
 850     }
 851
 852   aff_combination_const (&tmp, sizetype,
 853                          shwi_to_double_int (bitpos / BITS_PER_UNIT));
 854   aff_combination_add (addr, &tmp);
 855
 856   *size = shwi_to_double_int ((bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT);
 857 }
 858