gcc/tree-affine.c

   1 /* Operations with affine combinations of trees.
   2    Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "output.h"
  30 #include "diagnostic.h"
  31 #include "tree-dump.h"
  32 #include "pointer-set.h"
  33 #include "tree-affine.h"
  34 #include "tree-gimple.h"
  35
  36 /* Extends CST as appropriate for the affine combinations COMB.  */
  37
  38 double_int
  39 double_int_ext_for_comb (double_int cst, aff_tree *comb)
  40 {
  41   return double_int_sext (cst, TYPE_PRECISION (comb->type));
  42 }
  43
  44 /* Initializes affine combination COMB so that its value is zero in TYPE.  */
  45
  46 static void
  47 aff_combination_zero (aff_tree *comb, tree type)
  48 {
  49   comb->type = type;
  50   comb->offset = double_int_zero;
  51   comb->n = 0;
  52   comb->rest = NULL_TREE;
  53 }
  54
  55 /* Sets COMB to CST.  */
  56
  57 void
  58 aff_combination_const (aff_tree *comb, tree type, double_int cst)
  59 {
  60   aff_combination_zero (comb, type);
  61   comb->offset = double_int_ext_for_comb (cst, comb);
  62 }
  63
  64 /* Sets COMB to single element ELT.  */
  65
  66 void
  67 aff_combination_elt (aff_tree *comb, tree type, tree elt)
  68 {
  69   aff_combination_zero (comb, type);
  70
  71   comb->n = 1;
  72   comb->elts[0].val = elt;
  73   comb->elts[0].coef = double_int_one;
  74 }
  75
  76 /* Scales COMB by SCALE.  */
  77
  78 void
  79 aff_combination_scale (aff_tree *comb, double_int scale)
  80 {
  81   unsigned i, j;
  82
  83   scale = double_int_ext_for_comb (scale, comb);
  84   if (double_int_one_p (scale))
  85     return;
  86
  87   if (double_int_zero_p (scale))
  88     {
  89       aff_combination_zero (comb, comb->type);
  90       return;
  91     }
  92
  93   comb->offset
  94     = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
  95   for (i = 0, j = 0; i < comb->n; i++)
  96     {
  97       double_int new_coef;
  98
  99       new_coef
 100         = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
 101                                    comb);
 102       /* A coefficient may become zero due to overflow.  Remove the zero
 103          elements.  */
 104       if (double_int_zero_p (new_coef))
 105         continue;
 106       comb->elts[j].coef = new_coef;
 107       comb->elts[j].val = comb->elts[i].val;
 108       j++;
 109     }
 110   comb->n = j;
 111
 112   if (comb->rest)
 113     {
 114       if (comb->n < MAX_AFF_ELTS)
 115         {
 116           comb->elts[comb->n].coef = scale;
 117           comb->elts[comb->n].val = comb->rest;
 118           comb->rest = NULL_TREE;
 119           comb->n++;
 120         }
 121       else
 122         comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
 123                                   double_int_to_tree (comb->type, scale));
 124     }
 125 }
 126
 127 /* Adds ELT * SCALE to COMB.  */
 128
 129 void
 130 aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
 131 {
 132   unsigned i;
 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   if (double_int_one_p (scale))
 173     elt = fold_convert (comb->type, elt);
 174   else
 175     elt = fold_build2 (MULT_EXPR, comb->type,
 176                        fold_convert (comb->type, elt),
 177                        double_int_to_tree (comb->type, scale));
 178
 179   if (comb->rest)
 180     comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
 181   else
 182     comb->rest = elt;
 183 }
 184
 185 /* Adds CST to C.  */
 186
 187 static void
 188 aff_combination_add_cst (aff_tree *c, double_int cst)
 189 {
 190   c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c);
 191 }
 192
 193 /* Adds COMB2 to COMB1.  */
 194
 195 void
 196 aff_combination_add (aff_tree *comb1, aff_tree *comb2)
 197 {
 198   unsigned i;
 199
 200   aff_combination_add_cst (comb1, comb2->offset);
 201   for (i = 0; i < comb2->n; i++)
 202     aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
 203   if (comb2->rest)
 204     aff_combination_add_elt (comb1, comb2->rest, double_int_one);
 205 }
 206
 207 /* Converts affine combination COMB to TYPE.  */
 208
 209 void
 210 aff_combination_convert (aff_tree *comb, tree type)
 211 {
 212   unsigned i, j;
 213   tree comb_type = comb->type;
 214
 215   if  (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
 216     {
 217       tree val = fold_convert (type, aff_combination_to_tree (comb));
 218       tree_to_aff_combination (val, type, comb);
 219       return;
 220     }
 221
 222   comb->type = type;
 223   if (comb->rest)
 224     comb->rest = fold_convert (type, comb->rest);
 225
 226   if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
 227     return;
 228
 229   comb->offset = double_int_ext_for_comb (comb->offset, comb);
 230   for (i = j = 0; i < comb->n; i++)
 231     {
 232       double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
 233       if (double_int_zero_p (new_coef))
 234         continue;
 235       comb->elts[j].coef = new_coef;
 236       comb->elts[j].val = fold_convert (type, comb->elts[i].val);
 237       j++;
 238     }
 239
 240   comb->n = j;
 241   if (comb->n < MAX_AFF_ELTS && comb->rest)
 242     {
 243       comb->elts[comb->n].coef = double_int_one;
 244       comb->elts[comb->n].val = comb->rest;
 245       comb->rest = NULL_TREE;
 246       comb->n++;
 247     }
 248 }
 249
 250 /* Splits EXPR into an affine combination of parts.  */
 251
 252 void
 253 tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
 254 {
 255   aff_tree tmp;
 256   enum tree_code code;
 257   tree cst, core, toffset;
 258   HOST_WIDE_INT bitpos, bitsize;
 259   enum machine_mode mode;
 260   int unsignedp, volatilep;
 261
 262   STRIP_NOPS (expr);
 263
 264   code = TREE_CODE (expr);
 265   switch (code)
 266     {
 267     case INTEGER_CST:
 268       aff_combination_const (comb, type, tree_to_double_int (expr));
 269       return;
 270
 271     case POINTER_PLUS_EXPR:
 272       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 273       tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
 274       aff_combination_convert (&tmp, type);
 275       aff_combination_add (comb, &tmp);
 276       return;
 277
 278     case PLUS_EXPR:
 279     case MINUS_EXPR:
 280       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 281       tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
 282       if (code == MINUS_EXPR)
 283         aff_combination_scale (&tmp, double_int_minus_one);
 284       aff_combination_add (comb, &tmp);
 285       return;
 286
 287     case MULT_EXPR:
 288       cst = TREE_OPERAND (expr, 1);
 289       if (TREE_CODE (cst) != INTEGER_CST)
 290         break;
 291       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 292       aff_combination_scale (comb, tree_to_double_int (cst));
 293       return;
 294
 295     case NEGATE_EXPR:
 296       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 297       aff_combination_scale (comb, double_int_minus_one);
 298       return;
 299
 300     case BIT_NOT_EXPR:
 301       /* ~x = -x - 1 */
 302       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 303       aff_combination_scale (comb, double_int_minus_one);
 304       aff_combination_add_cst (comb, double_int_minus_one);
 305       return;
 306
 307     case ADDR_EXPR:
 308       core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
 309                                   &toffset, &mode, &unsignedp, &volatilep,
 310                                   false);
 311       if (bitpos % BITS_PER_UNIT != 0)
 312         break;
 313       aff_combination_const (comb, type,
 314                              uhwi_to_double_int (bitpos / BITS_PER_UNIT));
 315       core = build_fold_addr_expr (core);
 316       if (TREE_CODE (core) == ADDR_EXPR)
 317         aff_combination_add_elt (comb, core, double_int_one);
 318       else
 319         {
 320           tree_to_aff_combination (core, type, &tmp);
 321           aff_combination_add (comb, &tmp);
 322         }
 323       if (toffset)
 324         {
 325           tree_to_aff_combination (toffset, type, &tmp);
 326           aff_combination_add (comb, &tmp);
 327         }
 328       return;
 329
 330     default:
 331       break;
 332     }
 333
 334   aff_combination_elt (comb, type, expr);
 335 }
 336
 337 /* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
 338    combination COMB.  */
 339
 340 static tree
 341 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
 342                  aff_tree *comb)
 343 {
 344   enum tree_code code;
 345
 346   scale = double_int_ext_for_comb (scale, comb);
 347   elt = fold_convert (type, elt);
 348
 349   if (double_int_one_p (scale))
 350     {
 351       if (!expr)
 352         return elt;
 353
 354       return fold_build2 (PLUS_EXPR, type, expr, elt);
 355     }
 356
 357   if (double_int_minus_one_p (scale))
 358     {
 359       if (!expr)
 360         return fold_build1 (NEGATE_EXPR, type, elt);
 361
 362       return fold_build2 (MINUS_EXPR, type, expr, elt);
 363     }
 364
 365   if (!expr)
 366     return fold_build2 (MULT_EXPR, type, elt,
 367                         double_int_to_tree (type, scale));
 368
 369   if (double_int_negative_p (scale))
 370     {
 371       code = MINUS_EXPR;
 372       scale = double_int_neg (scale);
 373     }
 374   else
 375     code = PLUS_EXPR;
 376
 377   elt = fold_build2 (MULT_EXPR, type, elt,
 378                      double_int_to_tree (type, scale));
 379   return fold_build2 (code, type, expr, elt);
 380 }
 381
 382 /* Makes tree from the affine combination COMB.  */
 383
 384 tree
 385 aff_combination_to_tree (aff_tree *comb)
 386 {
 387   tree type = comb->type;
 388   tree expr = comb->rest;
 389   unsigned i;
 390   double_int off, sgn;
 391
 392   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 393
 394   for (i = 0; i < comb->n; i++)
 395     expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
 396                             comb);
 397
 398   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
 399      unsigned.  */
 400   if (double_int_negative_p (comb->offset))
 401     {
 402       off = double_int_neg (comb->offset);
 403       sgn = double_int_minus_one;
 404     }
 405   else
 406     {
 407       off = comb->offset;
 408       sgn = double_int_one;
 409     }
 410   return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
 411                           comb);
 412 }
 413
 414 /* Copies the tree elements of COMB to ensure that they are not shared.  */
 415
 416 void
 417 unshare_aff_combination (aff_tree *comb)
 418 {
 419   unsigned i;
 420
 421   for (i = 0; i < comb->n; i++)
 422     comb->elts[i].val = unshare_expr (comb->elts[i].val);
 423   if (comb->rest)
 424     comb->rest = unshare_expr (comb->rest);
 425 }
 426
 427 /* Remove M-th element from COMB.  */
 428
 429 void
 430 aff_combination_remove_elt (aff_tree *comb, unsigned m)
 431 {
 432   comb->n--;
 433   if (m <= comb->n)
 434     comb->elts[m] = comb->elts[comb->n];
 435   if (comb->rest)
 436     {
 437       comb->elts[comb->n].coef = double_int_one;
 438       comb->elts[comb->n].val = comb->rest;
 439       comb->rest = NULL_TREE;
 440       comb->n++;
 441     }
 442 }
 443
 444 /* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
 445    C * COEF is added to R.  */
 446
 447
 448 static void
 449 aff_combination_add_product (aff_tree *c, double_int coef, tree val,
 450                              aff_tree *r)
 451 {
 452   unsigned i;
 453   tree aval, type;
 454
 455   for (i = 0; i < c->n; i++)
 456     {
 457       aval = c->elts[i].val;
 458       if (val)
 459         {
 460           type = TREE_TYPE (aval);
 461           aval = fold_build2 (MULT_EXPR, type, aval,
 462                               fold_convert (type, val));
 463         }
 464
 465       aff_combination_add_elt (r, aval,
 466                                double_int_mul (coef, c->elts[i].coef));
 467     }
 468
 469   if (c->rest)
 470     {
 471       aval = c->rest;
 472       if (val)
 473         {
 474           type = TREE_TYPE (aval);
 475           aval = fold_build2 (MULT_EXPR, type, aval,
 476                               fold_convert (type, val));
 477         }
 478
 479       aff_combination_add_elt (r, aval, coef);
 480     }
 481
 482   if (val)
 483     aff_combination_add_elt (r, val,
 484                              double_int_mul (coef, c->offset));
 485   else
 486     aff_combination_add_cst (r, double_int_mul (coef, c->offset));
 487 }
 488
 489 /* Multiplies C1 by C2, storing the result to R  */
 490
 491 void
 492 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
 493 {
 494   unsigned i;
 495   gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
 496
 497   aff_combination_zero (r, c1->type);
 498
 499   for (i = 0; i < c2->n; i++)
 500     aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
 501   if (c2->rest)
 502     aff_combination_add_product (c1, double_int_one, c2->rest, r);
 503   aff_combination_add_product (c1, c2->offset, NULL, r);
 504 }
 505
 506 /* Returns the element of COMB whose value is VAL, or NULL if no such
 507    element exists.  If IDX is not NULL, it is set to the index of VAL in
 508    COMB.  */
 509
 510 static struct aff_comb_elt *
 511 aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
 512 {
 513   unsigned i;
 514
 515   for (i = 0; i < comb->n; i++)
 516     if (operand_equal_p (comb->elts[i].val, val, 0))
 517       {
 518         if (idx)
 519           *idx = i;
 520
 521         return &comb->elts[i];
 522       }
 523
 524   return NULL;
 525 }
 526
 527 /* Element of the cache that maps ssa name NAME to its expanded form
 528    as an affine expression EXPANSION.  */
 529
 530 struct name_expansion
 531 {
 532   aff_tree expansion;
 533
 534   /* True if the expansion for the name is just being generated.  */
 535   unsigned in_progress : 1;
 536 };
 537
 538 /* Similar to tree_to_aff_combination, but follows SSA name definitions
 539    and expands them recursively.  CACHE is used to cache the expansions
 540    of the ssa names, to avoid exponential time complexity for cases
 541    like
 542
 543    a1 = a0 + a0;
 544    a2 = a1 + a1;
 545    a3 = a2 + a2;
 546    ...  */
 547
 548 void
 549 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
 550                                 struct pointer_map_t **cache)
 551 {
 552   unsigned i;
 553   aff_tree to_add, current, curre;
 554   tree e, def, rhs;
 555   double_int scale;
 556   void **slot;
 557   struct name_expansion *exp;
 558
 559   tree_to_aff_combination (expr, type, comb);
 560   aff_combination_zero (&to_add, type);
 561   for (i = 0; i < comb->n; i++)
 562     {
 563       e = comb->elts[i].val;
 564       if (TREE_CODE (e) != SSA_NAME)
 565         continue;
 566       def = SSA_NAME_DEF_STMT (e);
 567       if (TREE_CODE (def) != GIMPLE_MODIFY_STMT
 568           || GIMPLE_STMT_OPERAND (def, 0) != e)
 569         continue;
 570
 571       rhs = GIMPLE_STMT_OPERAND (def, 1);
 572       if (TREE_CODE (rhs) != SSA_NAME
 573           && !EXPR_P (rhs)
 574           && !is_gimple_min_invariant (rhs))
 575         continue;
 576
 577       /* We do not know whether the reference retains its value at the
 578          place where the expansion is used.  */
 579       if (REFERENCE_CLASS_P (rhs))
 580         continue;
 581
 582       if (!*cache)
 583         *cache = pointer_map_create ();
 584       slot = pointer_map_insert (*cache, e);
 585       exp = *slot;
 586
 587       if (!exp)
 588         {
 589           exp = XNEW (struct name_expansion);
 590           exp->in_progress = 1;
 591           *slot = exp;
 592           tree_to_aff_combination_expand (rhs, type, &current, cache);
 593           exp->expansion = current;
 594           exp->in_progress = 0;
 595         }
 596       else
 597         {
 598           /* Since we follow the definitions in the SSA form, we should not
 599              enter a cycle unless we pass through a phi node.  */
 600           gcc_assert (!exp->in_progress);
 601           current = exp->expansion;
 602         }
 603
 604       /* Accumulate the new terms to TO_ADD, so that we do not modify
 605          COMB while traversing it; include the term -coef * E, to remove
 606          it from COMB.  */
 607       scale = comb->elts[i].coef;
 608       aff_combination_zero (&curre, type);
 609       aff_combination_add_elt (&curre, e, double_int_neg (scale));
 610       aff_combination_scale (&current, scale);
 611       aff_combination_add (&to_add, &current);
 612       aff_combination_add (&to_add, &curre);
 613     }
 614   aff_combination_add (comb, &to_add);
 615 }
 616
 617 /* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
 618    pointer_map_traverse.  */
 619
 620 static bool
 621 free_name_expansion (void *key ATTRIBUTE_UNUSED, void **value,
 622                      void *data ATTRIBUTE_UNUSED)
 623 {
 624   struct name_expansion *exp = *value;
 625
 626   free (exp);
 627   return true;
 628 }
 629
 630 /* Frees memory allocated for the CACHE used by
 631    tree_to_aff_combination_expand.  */
 632
 633 void
 634 free_affine_expand_cache (struct pointer_map_t **cache)
 635 {
 636   if (!*cache)
 637     return;
 638
 639   pointer_map_traverse (*cache, free_name_expansion, NULL);
 640   pointer_map_destroy (*cache);
 641   *cache = NULL;
 642 }
 643
 644 /* If VAL != CST * DIV for any constant CST, returns false.
 645    Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
 646    additionally compares CST and MULT, and if they are different,
 647    returns false.  Finally, if neither of these two cases occur,
 648    true is returned, and if CST != 0, CST is stored to MULT and
 649    MULT_SET is set to true.  */
 650
 651 static bool
 652 double_int_constant_multiple_p (double_int val, double_int div,
 653                                 bool *mult_set, double_int *mult)
 654 {
 655   double_int rem, cst;
 656
 657   if (double_int_zero_p (val))
 658     return true;
 659
 660   if (double_int_zero_p (div))
 661     return false;
 662
 663   cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem);
 664   if (!double_int_zero_p (rem))
 665     return false;
 666
 667   if (*mult_set && !double_int_equal_p (*mult, cst))
 668     return false;
 669
 670   *mult_set = true;
 671   *mult = cst;
 672   return true;
 673 }
 674
 675 /* Returns true if VAL = X * DIV for some constant X.  If this is the case,
 676    X is stored to MULT.  */
 677
 678 bool
 679 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
 680                                      double_int *mult)
 681 {
 682   bool mult_set = false;
 683   unsigned i;
 684
 685   if (val->n == 0 && double_int_zero_p (val->offset))
 686     {
 687       *mult = double_int_zero;
 688       return true;
 689     }
 690   if (val->n != div->n)
 691     return false;
 692
 693   if (val->rest || div->rest)
 694     return false;
 695
 696   if (!double_int_constant_multiple_p (val->offset, div->offset,
 697                                        &mult_set, mult))
 698     return false;
 699
 700   for (i = 0; i < div->n; i++)
 701     {
 702       struct aff_comb_elt *elt
 703               = aff_combination_find_elt (val, div->elts[i].val, NULL);
 704       if (!elt)
 705         return false;
 706       if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef,
 707                                            &mult_set, mult))
 708         return false;
 709     }
 710
 711   gcc_assert (mult_set);
 712   return true;
 713 }