gcc/tree-ssa-address.c

   1 /* Memory address lowering and addressing mode selection.
   2    Copyright (C) 2004 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 /* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
  22    that directly map to addressing modes of the target.  */
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "tm.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "diagnostic.h"
  35 #include "tree-flow.h"
  36 #include "tree-dump.h"
  37 #include "tree-pass.h"
  38 #include "timevar.h"
  39 #include "flags.h"
  40 #include "tree-inline.h"
  41 #include "insn-config.h"
  42 #include "recog.h"
  43 #include "expr.h"
  44 #include "ggc.h"
  45
  46 /* TODO -- handling of symbols (according to Richard Hendersons
  47    comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
  48
  49    There are at least 5 different kinds of symbols that we can run up against:
  50
  51      (1) binds_local_p, small data area.
  52      (2) binds_local_p, eg local statics
  53      (3) !binds_local_p, eg global variables
  54      (4) thread local, local_exec
  55      (5) thread local, !local_exec
  56
  57    Now, (1) won't appear often in an array context, but it certainly can.
  58    All you have to do is set -GN high enough, or explicitly mark any
  59    random object __attribute__((section (".sdata"))).
  60
  61    All of these affect whether or not a symbol is in fact a valid address.
  62    The only one tested here is (3).  And that result may very well
  63    be incorrect for (4) or (5).
  64
  65    An incorrect result here does not cause incorrect results out the
  66    back end, because the expander in expr.c validizes the address.  However
  67    it would be nice to improve the handling here in order to produce more
  68    precise results.  */
  69
  70 /* A "template" for memory address, used to determine whether the address is
  71    valid for mode.  */
  72
  73 struct mem_addr_template GTY (())
  74 {
  75   rtx ref;                      /* The template.  */
  76   rtx * GTY ((skip)) step_p;    /* The point in template where the step should be
  77                                    filled in.  */
  78   rtx * GTY ((skip)) off_p;     /* The point in template where the offset should
  79                                    be filled in.  */
  80 };
  81
  82 /* The templates.  Each of the five bits of the index corresponds to one
  83    component of TARGET_MEM_REF being present, see TEMPL_IDX.  */
  84
  85 static GTY (()) struct mem_addr_template templates[32];
  86
  87 #define TEMPL_IDX(SYMBOL, BASE, INDEX, STEP, OFFSET) \
  88   (((SYMBOL != 0) << 4) \
  89    | ((BASE != 0) << 3) \
  90    | ((INDEX != 0) << 2) \
  91    | ((STEP != 0) << 1) \
  92    | (OFFSET != 0))
  93
  94 /* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
  95    STEP and OFFSET to *ADDR.  Stores pointers to where step is placed to
  96    *STEP_P and offset to *OFFSET_P.  */
  97
  98 static void
  99 gen_addr_rtx (rtx symbol, rtx base, rtx index, rtx step, rtx offset,
 100               rtx *addr, rtx **step_p, rtx **offset_p)
 101 {
 102   rtx act_elem;
 103
 104   *addr = NULL_RTX;
 105   if (step_p)
 106     *step_p = NULL;
 107   if (offset_p)
 108     *offset_p = NULL;
 109
 110   if (index)
 111     {
 112       act_elem = index;
 113       if (step)
 114         {
 115           act_elem = gen_rtx_MULT (Pmode, act_elem, step);
 116
 117           if (step_p)
 118             *step_p = &XEXP (act_elem, 1);
 119         }
 120
 121       *addr = act_elem;
 122     }
 123
 124   if (base)
 125     {
 126       if (*addr)
 127         *addr = gen_rtx_PLUS (Pmode, *addr, base);
 128       else
 129         *addr = base;
 130     }
 131
 132   if (symbol)
 133     {
 134       act_elem = symbol;
 135       if (offset)
 136         {
 137           act_elem = gen_rtx_CONST (Pmode,
 138                                     gen_rtx_PLUS (Pmode, act_elem, offset));
 139           if (offset_p)
 140             *offset_p = &XEXP (XEXP (act_elem, 0), 1);
 141         }
 142
 143       if (*addr)
 144         *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
 145       else
 146         *addr = act_elem;
 147     }
 148   else if (offset)
 149     {
 150       if (*addr)
 151         {
 152           *addr = gen_rtx_PLUS (Pmode, *addr, offset);
 153           if (offset_p)
 154             *offset_p = &XEXP (*addr, 1);
 155         }
 156       else
 157         {
 158           *addr = offset;
 159           if (offset_p)
 160             *offset_p = addr;
 161         }
 162     }
 163
 164   if (!*addr)
 165     *addr = const0_rtx;
 166 }
 167
 168 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
 169    If REALLY_EXPAND is false, just make fake registers instead
 170    of really expanding the operands, and perform the expansion in-place
 171    by using one of the "templates".  */
 172
 173 rtx
 174 addr_for_mem_ref (struct mem_address *addr, bool really_expand)
 175 {
 176   rtx address, sym, bse, idx, st, off;
 177   static bool templates_initialized = false;
 178   struct mem_addr_template *templ;
 179
 180   if (addr->step && !integer_onep (addr->step))
 181     st = immed_double_const (TREE_INT_CST_LOW (addr->step),
 182                              TREE_INT_CST_HIGH (addr->step), Pmode);
 183   else
 184     st = NULL_RTX;
 185
 186   if (addr->offset && !integer_zerop (addr->offset))
 187     off = immed_double_const (TREE_INT_CST_LOW (addr->offset),
 188                               TREE_INT_CST_HIGH (addr->offset), Pmode);
 189   else
 190     off = NULL_RTX;
 191
 192   if (!really_expand)
 193     {
 194       /* Reuse the templates for addresses, so that we do not waste memory.  */
 195       if (!templates_initialized)
 196         {
 197           unsigned i;
 198
 199           templates_initialized = true;
 200           sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup ("test_symbol"));
 201           bse = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
 202           idx = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
 203
 204           for (i = 0; i < 32; i++)
 205             gen_addr_rtx ((i & 16 ? sym : NULL_RTX),
 206                           (i & 8 ? bse : NULL_RTX),
 207                           (i & 4 ? idx : NULL_RTX),
 208                           (i & 2 ? const0_rtx : NULL_RTX),
 209                           (i & 1 ? const0_rtx : NULL_RTX),
 210                           &templates[i].ref,
 211                           &templates[i].step_p,
 212                           &templates[i].off_p);
 213         }
 214
 215       templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
 216                                      st, off);
 217       if (st)
 218         *templ->step_p = st;
 219       if (off)
 220         *templ->off_p = off;
 221
 222       return templ->ref;
 223     }
 224
 225   /* Otherwise really expand the expressions.  */
 226   sym = (addr->symbol
 227          ? expand_expr (build_addr (addr->symbol, current_function_decl),
 228                         NULL_RTX, Pmode, EXPAND_NORMAL)
 229          : NULL_RTX);
 230   bse = (addr->base
 231          ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
 232          : NULL_RTX);
 233   idx = (addr->index
 234          ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
 235          : NULL_RTX);
 236
 237   gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
 238   return address;
 239 }
 240
 241 /* Returns address of MEM_REF in TYPE.  */
 242
 243 tree
 244 tree_mem_ref_addr (tree type, tree mem_ref)
 245 {
 246   tree addr = NULL_TREE;
 247   tree act_elem;
 248   tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
 249
 250   act_elem = TMR_INDEX (mem_ref);
 251   if (act_elem)
 252     {
 253       act_elem = fold_convert (type, act_elem);
 254
 255       if (step)
 256         act_elem = fold_build2 (MULT_EXPR, type, act_elem,
 257                                 fold_convert (type, step));
 258       addr = act_elem;
 259     }
 260
 261   act_elem = TMR_BASE (mem_ref);
 262   if (act_elem)
 263     {
 264       act_elem = fold_convert (type, act_elem);
 265
 266       if (addr)
 267         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
 268       else
 269         addr = act_elem;
 270     }
 271
 272   act_elem = TMR_SYMBOL (mem_ref);
 273   if (act_elem)
 274     {
 275       act_elem = fold_convert (type, build_addr (act_elem,
 276                                                  current_function_decl));
 277       if (addr)
 278         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
 279       else
 280         addr = act_elem;
 281     }
 282
 283   if (!zero_p (offset))
 284     {
 285       act_elem = fold_convert (type, offset);
 286
 287       if (addr)
 288         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
 289       else
 290         addr = act_elem;
 291     }
 292
 293   if (!addr)
 294     addr = build_int_cst (type, 0);
 295
 296   return addr;
 297 }
 298
 299 /* Returns true if a memory reference in MODE and with parameters given by
 300    ADDR is valid on the current target.  */
 301
 302 static bool
 303 valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
 304 {
 305   rtx address;
 306
 307   address = addr_for_mem_ref (addr, false);
 308   if (!address)
 309     return false;
 310
 311   return memory_address_p (mode, address);
 312 }
 313
 314 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
 315    is valid on the current target and if so, creates and returns the
 316    TARGET_MEM_REF.  */
 317
 318 static tree
 319 create_mem_ref_raw (tree type, struct mem_address *addr)
 320 {
 321   if (!valid_mem_ref_p (TYPE_MODE (type), addr))
 322     return NULL_TREE;
 323
 324   if (addr->step && integer_onep (addr->step))
 325     addr->step = NULL_TREE;
 326
 327   if (addr->offset && zero_p (addr->offset))
 328     addr->offset = NULL_TREE;
 329
 330   return build7 (TARGET_MEM_REF, type,
 331                  addr->symbol, addr->base, addr->index,
 332                  addr->step, addr->offset, NULL, NULL);
 333 }
 334
 335 /* Returns true if OBJ is an object whose address is a link time constant.  */
 336
 337 static bool
 338 fixed_address_object_p (tree obj)
 339 {
 340   return (TREE_CODE (obj) == VAR_DECL
 341           && (TREE_STATIC (obj)
 342               || DECL_EXTERNAL (obj)));
 343 }
 344
 345 /* Adds COEF * ELT to PARTS.  TYPE is the type of the address we
 346    construct.  */
 347
 348 static void
 349 add_to_parts (struct mem_address *parts, tree type, tree elt,
 350               unsigned HOST_WIDE_INT coef)
 351 {
 352   /* Check if this is a symbol.  */
 353   if (!parts->symbol
 354       && coef == 1
 355       && TREE_CODE (elt) == ADDR_EXPR
 356       && fixed_address_object_p (TREE_OPERAND (elt, 0)))
 357     {
 358       parts->symbol = TREE_OPERAND (elt, 0);
 359       return;
 360     }
 361
 362   if (coef != 1)
 363     elt = fold_build2 (MULT_EXPR, type, fold_convert (type, elt),
 364                        build_int_cst_type (type, coef));
 365   else
 366     elt = fold_convert (type, elt);
 367
 368   if (!parts->base)
 369     {
 370       parts->base = elt;
 371       return;
 372     }
 373
 374   if (!parts->index)
 375     {
 376       parts->index = elt;
 377       return;
 378     }
 379
 380   /* Add ELT to base.  */
 381   parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
 382 }
 383
 384 /* Finds the most expensive multiplication in ADDR that can be
 385    expressed in an addressing mode and move the corresponding
 386    element(s) to PARTS.  TYPE is the type of the address we
 387    construct.  */
 388
 389 static void
 390 most_expensive_mult_to_index (struct mem_address *parts, tree type,
 391                               struct affine_tree_combination *addr)
 392 {
 393   unsigned HOST_WIDE_INT best_mult = 0;
 394   unsigned best_mult_cost = 0, acost;
 395   tree mult_elt = NULL_TREE, elt;
 396   unsigned i, j;
 397
 398   for (i = 0; i < addr->n; i++)
 399     {
 400       if (addr->coefs[i] == 1
 401           || !multiplier_allowed_in_address_p (addr->coefs[i]))
 402         continue;
 403
 404       acost = multiply_by_cost (addr->coefs[i], Pmode);
 405
 406       if (acost > best_mult_cost)
 407         {
 408           best_mult_cost = acost;
 409           best_mult = addr->coefs[i];
 410         }
 411     }
 412
 413   if (!best_mult)
 414     return;
 415
 416   for (i = j = 0; i < addr->n; i++)
 417     {
 418       if (addr->coefs[i] != best_mult)
 419         {
 420           addr->coefs[j] = addr->coefs[i];
 421           addr->elts[j] = addr->elts[i];
 422           j++;
 423           continue;
 424         }
 425
 426       elt = fold_convert (type, addr->elts[i]);
 427       if (!mult_elt)
 428         mult_elt = elt;
 429       else
 430         mult_elt = fold_build2 (PLUS_EXPR, type, mult_elt, elt);
 431     }
 432   addr->n = j;
 433
 434   parts->index = mult_elt;
 435   parts->step = build_int_cst_type (type, best_mult);
 436 }
 437
 438 /* Splits address ADDR into PARTS.
 439
 440    TODO -- be more clever about the distribution of the elements of ADDR
 441    to PARTS.  Some architectures do not support anything but single
 442    register in address, possibly with a small integer offset; while
 443    create_mem_ref will simplify the address to an acceptable shape
 444    later, it would be a small bit more efficient to know that asking
 445    for complicated addressing modes is useless.  */
 446
 447 static void
 448 addr_to_parts (struct affine_tree_combination *addr, tree type,
 449                struct mem_address *parts)
 450 {
 451   unsigned i;
 452
 453   parts->symbol = NULL_TREE;
 454   parts->base = NULL_TREE;
 455   parts->index = NULL_TREE;
 456   parts->step = NULL_TREE;
 457
 458   if (addr->offset)
 459     parts->offset = build_int_cst_type (type, addr->offset);
 460   else
 461     parts->offset = NULL_TREE;
 462
 463   /* First move the most expensive feasible multiplication
 464      to index.  */
 465   most_expensive_mult_to_index (parts, type, addr);
 466
 467   /* Then try to process the remaining elements.  */
 468   for (i = 0; i < addr->n; i++)
 469     add_to_parts (parts, type, addr->elts[i], addr->coefs[i]);
 470   if (addr->rest)
 471     add_to_parts (parts, type, addr->rest, 1);
 472 }
 473
 474 /* Force the PARTS to register.  */
 475
 476 static void
 477 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
 478 {
 479   if (parts->base)
 480     parts->base = force_gimple_operand_bsi (bsi, parts->base,
 481                                             true, NULL_TREE);
 482   if (parts->index)
 483     parts->index = force_gimple_operand_bsi (bsi, parts->index,
 484                                              true, NULL_TREE);
 485 }
 486
 487 /* Creates and returns a TARGET_MEM_REF for address ADDR.  If necessary
 488    computations are emitted in front of BSI.  TYPE is the mode
 489    of created memory reference.  */
 490
 491 tree
 492 create_mem_ref (block_stmt_iterator *bsi, tree type,
 493                 struct affine_tree_combination *addr)
 494 {
 495   tree mem_ref, tmp;
 496   tree addr_type = build_pointer_type (type);
 497   struct mem_address parts;
 498
 499   addr_to_parts (addr, addr_type, &parts);
 500   gimplify_mem_ref_parts (bsi, &parts);
 501   mem_ref = create_mem_ref_raw (type, &parts);
 502   if (mem_ref)
 503     return mem_ref;
 504
 505   /* The expression is too complicated.  Try making it simpler.  */
 506
 507   if (parts.step && !integer_onep (parts.step))
 508     {
 509       /* Move the multiplication to index.  */
 510       gcc_assert (parts.index);
 511       parts.index = force_gimple_operand_bsi (bsi,
 512                                               build2 (MULT_EXPR, addr_type,
 513                                                       parts.index, parts.step),
 514                                               true, NULL_TREE);
 515       parts.step = NULL_TREE;
 516
 517       mem_ref = create_mem_ref_raw (type, &parts);
 518       if (mem_ref)
 519         return mem_ref;
 520     }
 521
 522   if (parts.symbol)
 523     {
 524       tmp = build_addr (parts.symbol, current_function_decl);
 525
 526       /* Add the symbol to base, eventually forcing it to register.  */
 527       if (parts.base)
 528         {
 529           if (parts.index)
 530             parts.base = force_gimple_operand_bsi (bsi,
 531                                                    build2 (PLUS_EXPR, addr_type,
 532                                                            parts.base, tmp),
 533                                                    true, NULL_TREE);
 534           else
 535             {
 536               parts.index = parts.base;
 537               parts.base = tmp;
 538             }
 539         }
 540       else
 541         parts.base = tmp;
 542       parts.symbol = NULL_TREE;
 543
 544       mem_ref = create_mem_ref_raw (type, &parts);
 545       if (mem_ref)
 546         return mem_ref;
 547     }
 548
 549   if (parts.base)
 550     {
 551       /* Add base to index.  */
 552       if (parts.index)
 553         parts.index = force_gimple_operand_bsi (bsi,
 554                                                 build2 (PLUS_EXPR, addr_type,
 555                                                         parts.base,
 556                                                         parts.index),
 557                                                 true, NULL_TREE);
 558       else
 559         parts.index = parts.base;
 560       parts.base = NULL_TREE;
 561
 562       mem_ref = create_mem_ref_raw (type, &parts);
 563       if (mem_ref)
 564         return mem_ref;
 565     }
 566
 567   if (parts.offset && !integer_zerop (parts.offset))
 568     {
 569       /* Try adding offset to index.  */
 570       if (parts.index)
 571         parts.index = force_gimple_operand_bsi (bsi,
 572                                                 build2 (PLUS_EXPR, addr_type,
 573                                                         parts.index,
 574                                                         parts.offset),
 575                                                 true, NULL_TREE);
 576       else
 577         parts.index = parts.offset, bsi;
 578
 579       parts.offset = NULL_TREE;
 580
 581       mem_ref = create_mem_ref_raw (type, &parts);
 582       if (mem_ref)
 583         return mem_ref;
 584     }
 585
 586   /* Verify that the address is in the simplest possible shape
 587      (only a register).  If we cannot create such a memory reference,
 588      something is really wrong.  */
 589   gcc_assert (parts.symbol == NULL_TREE);
 590   gcc_assert (parts.base == NULL_TREE);
 591   gcc_assert (!parts.step || integer_onep (parts.step));
 592   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 593   gcc_unreachable ();
 594 }
 595
 596 /* Copies components of the address from OP to ADDR.  */
 597
 598 void
 599 get_address_description (tree op, struct mem_address *addr)
 600 {
 601   addr->symbol = TMR_SYMBOL (op);
 602   addr->base = TMR_BASE (op);
 603   addr->index = TMR_INDEX (op);
 604   addr->step = TMR_STEP (op);
 605   addr->offset = TMR_OFFSET (op);
 606 }
 607
 608 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 609
 610 void
 611 copy_mem_ref_info (tree to, tree from)
 612 {
 613   /* Copy the annotation, to preserve the aliasing information.  */
 614   TMR_TAG (to) = TMR_TAG (from);
 615
 616   /* And the info about the original reference.  */
 617   TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
 618 }
 619
 620 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 621    mem ref if anything changes, NULL_TREE otherwise.  */
 622
 623 tree
 624 maybe_fold_tmr (tree ref)
 625 {
 626   struct mem_address addr;
 627   bool changed = false;
 628   tree ret, off;
 629
 630   get_address_description (ref, &addr);
 631
 632   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
 633     {
 634       if (addr.offset)
 635         addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 636                                                addr.offset, addr.base);
 637       else
 638         addr.offset = addr.base;
 639
 640       addr.base = NULL_TREE;
 641       changed = true;
 642     }
 643
 644   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 645     {
 646       off = addr.index;
 647       if (addr.step)
 648         {
 649           off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
 650                                          off, addr.step);
 651           addr.step = NULL_TREE;
 652         }
 653
 654       if (addr.offset)
 655         {
 656           addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 657                                                  addr.offset, off);
 658         }
 659       else
 660         addr.offset = off;
 661
 662       addr.index = NULL_TREE;
 663       changed = true;
 664     }
 665
 666   if (!changed)
 667     return NULL_TREE;
 668
 669   ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
 670   if (!ret)
 671     return NULL_TREE;
 672
 673   copy_mem_ref_info (ret, ref);
 674   return ret;
 675 }
 676
 677 /* Dump PARTS to FILE.  */
 678
 679 extern void dump_mem_address (FILE *, struct mem_address *);
 680 void
 681 dump_mem_address (FILE *file, struct mem_address *parts)
 682 {
 683   if (parts->symbol)
 684     {
 685       fprintf (file, "symbol: ");
 686       print_generic_expr (file, parts->symbol, TDF_SLIM);
 687       fprintf (file, "\n");
 688     }
 689   if (parts->base)
 690     {
 691       fprintf (file, "base: ");
 692       print_generic_expr (file, parts->base, TDF_SLIM);
 693       fprintf (file, "\n");
 694     }
 695   if (parts->index)
 696     {
 697       fprintf (file, "index: ");
 698       print_generic_expr (file, parts->index, TDF_SLIM);
 699       fprintf (file, "\n");
 700     }
 701   if (parts->step)
 702     {
 703       fprintf (file, "step: ");
 704       print_generic_expr (file, parts->step, TDF_SLIM);
 705       fprintf (file, "\n");
 706     }
 707   if (parts->offset)
 708     {
 709       fprintf (file, "offset: ");
 710       print_generic_expr (file, parts->offset, TDF_SLIM);
 711       fprintf (file, "\n");
 712     }
 713 }
 714
 715 #include "gt-tree-ssa-address.h"