gcc/tree-affine.c

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