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