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 "tree-affine.h"
  33
  34 /* Extends CST as appropriate for the affine combinations COMB.  */
  35
  36 double_int
  37 double_int_ext_for_comb (double_int cst, aff_tree *comb)
  38 {
  39   return double_int_sext (cst, TYPE_PRECISION (comb->type));
  40 }
  41
  42 /* Initializes affine combination COMB so that its value is zero in TYPE.  */
  43
  44 static void
  45 aff_combination_zero (aff_tree *comb, tree type)
  46 {
  47   comb->type = type;
  48   comb->offset = double_int_zero;
  49   comb->n = 0;
  50   comb->rest = NULL_TREE;
  51 }
  52
  53 /* Sets COMB to CST.  */
  54
  55 void
  56 aff_combination_const (aff_tree *comb, tree type, double_int cst)
  57 {
  58   aff_combination_zero (comb, type);
  59   comb->offset = double_int_ext_for_comb (cst, comb);
  60 }
  61
  62 /* Sets COMB to single element ELT.  */
  63
  64 void
  65 aff_combination_elt (aff_tree *comb, tree type, tree elt)
  66 {
  67   aff_combination_zero (comb, type);
  68
  69   comb->n = 1;
  70   comb->elts[0].val = elt;
  71   comb->elts[0].coef = double_int_one;
  72 }
  73
  74 /* Scales COMB by SCALE.  */
  75
  76 void
  77 aff_combination_scale (aff_tree *comb, double_int scale)
  78 {
  79   unsigned i, j;
  80
  81   scale = double_int_ext_for_comb (scale, comb);
  82   if (double_int_one_p (scale))
  83     return;
  84
  85   if (double_int_zero_p (scale))
  86     {
  87       aff_combination_zero (comb, comb->type);
  88       return;
  89     }
  90
  91   comb->offset
  92     = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
  93   for (i = 0, j = 0; i < comb->n; i++)
  94     {
  95       double_int new_coef;
  96
  97       new_coef
  98         = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
  99                                    comb);
 100       /* A coefficient may become zero due to overflow.  Remove the zero
 101          elements.  */
 102       if (double_int_zero_p (new_coef))
 103         continue;
 104       comb->elts[j].coef = new_coef;
 105       comb->elts[j].val = comb->elts[i].val;
 106       j++;
 107     }
 108   comb->n = j;
 109
 110   if (comb->rest)
 111     {
 112       if (comb->n < MAX_AFF_ELTS)
 113         {
 114           comb->elts[comb->n].coef = scale;
 115           comb->elts[comb->n].val = comb->rest;
 116           comb->rest = NULL_TREE;
 117           comb->n++;
 118         }
 119       else
 120         comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
 121                                   double_int_to_tree (comb->type, scale));
 122     }
 123 }
 124
 125 /* Adds ELT * SCALE to COMB.  */
 126
 127 void
 128 aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
 129 {
 130   unsigned i;
 131
 132   scale = double_int_ext_for_comb (scale, comb);
 133   if (double_int_zero_p (scale))
 134     return;
 135
 136   for (i = 0; i < comb->n; i++)
 137     if (operand_equal_p (comb->elts[i].val, elt, 0))
 138       {
 139         double_int new_coef;
 140
 141         new_coef = double_int_add (comb->elts[i].coef, scale);
 142         new_coef = double_int_ext_for_comb (new_coef, comb);
 143         if (!double_int_zero_p (new_coef))
 144           {
 145             comb->elts[i].coef = new_coef;
 146             return;
 147           }
 148
 149         comb->n--;
 150         comb->elts[i] = comb->elts[comb->n];
 151
 152         if (comb->rest)
 153           {
 154             gcc_assert (comb->n == MAX_AFF_ELTS - 1);
 155             comb->elts[comb->n].coef = double_int_one;
 156             comb->elts[comb->n].val = comb->rest;
 157             comb->rest = NULL_TREE;
 158             comb->n++;
 159           }
 160         return;
 161       }
 162   if (comb->n < MAX_AFF_ELTS)
 163     {
 164       comb->elts[comb->n].coef = scale;
 165       comb->elts[comb->n].val = elt;
 166       comb->n++;
 167       return;
 168     }
 169
 170   if (double_int_one_p (scale))
 171     elt = fold_convert (comb->type, elt);
 172   else
 173     elt = fold_build2 (MULT_EXPR, comb->type,
 174                        fold_convert (comb->type, elt),
 175                        double_int_to_tree (comb->type, scale));
 176
 177   if (comb->rest)
 178     comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
 179   else
 180     comb->rest = elt;
 181 }
 182
 183 /* Adds CST to C.  */
 184
 185 static void
 186 aff_combination_add_cst (aff_tree *c, double_int cst)
 187 {
 188   c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c);
 189 }
 190
 191 /* Adds COMB2 to COMB1.  */
 192
 193 void
 194 aff_combination_add (aff_tree *comb1, aff_tree *comb2)
 195 {
 196   unsigned i;
 197
 198   aff_combination_add_cst (comb1, comb2->offset);
 199   for (i = 0; i < comb2->n; i++)
 200     aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
 201   if (comb2->rest)
 202     aff_combination_add_elt (comb1, comb2->rest, double_int_one);
 203 }
 204
 205 /* Converts affine combination COMB to TYPE.  */
 206
 207 void
 208 aff_combination_convert (aff_tree *comb, tree type)
 209 {
 210   unsigned i, j;
 211   tree comb_type = comb->type;
 212
 213   if  (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
 214     {
 215       tree val = fold_convert (type, aff_combination_to_tree (comb));
 216       tree_to_aff_combination (val, type, comb);
 217       return;
 218     }
 219
 220   comb->type = type;
 221   if (comb->rest)
 222     comb->rest = fold_convert (type, comb->rest);
 223
 224   if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
 225     return;
 226
 227   comb->offset = double_int_ext_for_comb (comb->offset, comb);
 228   for (i = j = 0; i < comb->n; i++)
 229     {
 230       double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
 231       if (double_int_zero_p (new_coef))
 232         continue;
 233       comb->elts[j].coef = new_coef;
 234       comb->elts[j].val = fold_convert (type, comb->elts[i].val);
 235       j++;
 236     }
 237
 238   comb->n = j;
 239   if (comb->n < MAX_AFF_ELTS && comb->rest)
 240     {
 241       comb->elts[comb->n].coef = double_int_one;
 242       comb->elts[comb->n].val = comb->rest;
 243       comb->rest = NULL_TREE;
 244       comb->n++;
 245     }
 246 }
 247
 248 /* Splits EXPR into an affine combination of parts.  */
 249
 250 void
 251 tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
 252 {
 253   aff_tree tmp;
 254   enum tree_code code;
 255   tree cst, core, toffset;
 256   HOST_WIDE_INT bitpos, bitsize;
 257   enum machine_mode mode;
 258   int unsignedp, volatilep;
 259
 260   STRIP_NOPS (expr);
 261
 262   code = TREE_CODE (expr);
 263   switch (code)
 264     {
 265     case INTEGER_CST:
 266       aff_combination_const (comb, type, tree_to_double_int (expr));
 267       return;
 268
 269     case PLUS_EXPR:
 270     case MINUS_EXPR:
 271       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 272       tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
 273       if (code == MINUS_EXPR)
 274         aff_combination_scale (&tmp, double_int_minus_one);
 275       aff_combination_add (comb, &tmp);
 276       return;
 277
 278     case MULT_EXPR:
 279       cst = TREE_OPERAND (expr, 1);
 280       if (TREE_CODE (cst) != INTEGER_CST)
 281         break;
 282       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 283       aff_combination_scale (comb, tree_to_double_int (cst));
 284       return;
 285
 286     case NEGATE_EXPR:
 287       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 288       aff_combination_scale (comb, double_int_minus_one);
 289       return;
 290
 291     case BIT_NOT_EXPR:
 292       /* ~x = -x - 1 */
 293       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
 294       aff_combination_scale (comb, double_int_minus_one);
 295       aff_combination_add_cst (comb, double_int_minus_one);
 296       return;
 297
 298     case ADDR_EXPR:
 299       core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
 300                                   &toffset, &mode, &unsignedp, &volatilep,
 301                                   false);
 302       if (bitpos % BITS_PER_UNIT != 0)
 303         break;
 304       aff_combination_const (comb, type,
 305                              uhwi_to_double_int (bitpos / BITS_PER_UNIT));
 306       core = build_fold_addr_expr (core);
 307       if (TREE_CODE (core) == ADDR_EXPR)
 308         aff_combination_add_elt (comb, core, double_int_one);
 309       else
 310         {
 311           tree_to_aff_combination (core, type, &tmp);
 312           aff_combination_add (comb, &tmp);
 313         }
 314       if (toffset)
 315         {
 316           tree_to_aff_combination (toffset, type, &tmp);
 317           aff_combination_add (comb, &tmp);
 318         }
 319       return;
 320
 321     default:
 322       break;
 323     }
 324
 325   aff_combination_elt (comb, type, expr);
 326 }
 327
 328 /* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
 329    combination COMB.  */
 330
 331 static tree
 332 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
 333                  aff_tree *comb)
 334 {
 335   enum tree_code code;
 336
 337   scale = double_int_ext_for_comb (scale, comb);
 338   elt = fold_convert (type, elt);
 339
 340   if (double_int_one_p (scale))
 341     {
 342       if (!expr)
 343         return elt;
 344
 345       return fold_build2 (PLUS_EXPR, type, expr, elt);
 346     }
 347
 348   if (double_int_minus_one_p (scale))
 349     {
 350       if (!expr)
 351         return fold_build1 (NEGATE_EXPR, type, elt);
 352
 353       return fold_build2 (MINUS_EXPR, type, expr, elt);
 354     }
 355
 356   if (!expr)
 357     return fold_build2 (MULT_EXPR, type, elt,
 358                         double_int_to_tree (type, scale));
 359
 360   if (double_int_negative_p (scale))
 361     {
 362       code = MINUS_EXPR;
 363       scale = double_int_neg (scale);
 364     }
 365   else
 366     code = PLUS_EXPR;
 367
 368   elt = fold_build2 (MULT_EXPR, type, elt,
 369                      double_int_to_tree (type, scale));
 370   return fold_build2 (code, type, expr, elt);
 371 }
 372
 373 /* Makes tree from the affine combination COMB.  */
 374
 375 tree
 376 aff_combination_to_tree (aff_tree *comb)
 377 {
 378   tree type = comb->type;
 379   tree expr = comb->rest;
 380   unsigned i;
 381   double_int off, sgn;
 382
 383   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 384
 385   for (i = 0; i < comb->n; i++)
 386     expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
 387                             comb);
 388
 389   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
 390      unsigned.  */
 391   if (double_int_negative_p (comb->offset))
 392     {
 393       off = double_int_neg (comb->offset);
 394       sgn = double_int_minus_one;
 395     }
 396   else
 397     {
 398       off = comb->offset;
 399       sgn = double_int_one;
 400     }
 401   return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
 402                           comb);
 403 }
 404
 405 /* Copies the tree elements of COMB to ensure that they are not shared.  */
 406
 407 void
 408 unshare_aff_combination (aff_tree *comb)
 409 {
 410   unsigned i;
 411
 412   for (i = 0; i < comb->n; i++)
 413     comb->elts[i].val = unshare_expr (comb->elts[i].val);
 414   if (comb->rest)
 415     comb->rest = unshare_expr (comb->rest);
 416 }
 417
 418 /* Remove M-th element from COMB.  */
 419
 420 void
 421 aff_combination_remove_elt (aff_tree *comb, unsigned m)
 422 {
 423   comb->n--;
 424   if (m <= comb->n)
 425     comb->elts[m] = comb->elts[comb->n];
 426   if (comb->rest)
 427     {
 428       comb->elts[comb->n].coef = double_int_one;
 429       comb->elts[comb->n].val = comb->rest;
 430       comb->rest = NULL_TREE;
 431       comb->n++;
 432     }
 433 }
 434
 435 /* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
 436    C * COEF is added to R.  */
 437
 438
 439 static void
 440 aff_combination_add_product (aff_tree *c, double_int coef, tree val,
 441                              aff_tree *r)
 442 {
 443   unsigned i;
 444   tree aval, type;
 445
 446   for (i = 0; i < c->n; i++)
 447     {
 448       aval = c->elts[i].val;
 449       if (val)
 450         {
 451           type = TREE_TYPE (aval);
 452           aval = fold_build2 (MULT_EXPR, type, aval,
 453                               fold_convert (type, val));
 454         }
 455
 456       aff_combination_add_elt (r, aval,
 457                                double_int_mul (coef, c->elts[i].coef));
 458     }
 459
 460   if (c->rest)
 461     {
 462       aval = c->rest;
 463       if (val)
 464         {
 465           type = TREE_TYPE (aval);
 466           aval = fold_build2 (MULT_EXPR, type, aval,
 467                               fold_convert (type, val));
 468         }
 469
 470       aff_combination_add_elt (r, aval, coef);
 471     }
 472
 473   if (val)
 474     aff_combination_add_elt (r, val,
 475                              double_int_mul (coef, c->offset));
 476   else
 477     aff_combination_add_cst (r, double_int_mul (coef, c->offset));
 478 }
 479
 480 /* Multiplies C1 by C2, storing the result to R  */
 481
 482 void
 483 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
 484 {
 485   unsigned i;
 486   gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
 487
 488   aff_combination_zero (r, c1->type);
 489
 490   for (i = 0; i < c2->n; i++)
 491     aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
 492   if (c2->rest)
 493     aff_combination_add_product (c1, double_int_one, c2->rest, r);
 494   aff_combination_add_product (c1, c2->offset, NULL, r);
 495 }