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         parts.base = force_gimple_operand_bsi (bsi,
 529                                                build2 (PLUS_EXPR, addr_type,
 530                                                        parts.base, tmp),
 531                                                true, NULL_TREE);
 532       else
 533         parts.base = tmp;
 534       parts.symbol = NULL_TREE;
 535
 536       mem_ref = create_mem_ref_raw (type, &parts);
 537       if (mem_ref)
 538         return mem_ref;
 539     }
 540
 541   if (parts.base)
 542     {
 543       /* Add base to index.  */
 544       if (parts.index)
 545         parts.index = force_gimple_operand_bsi (bsi,
 546                                                 build2 (PLUS_EXPR, addr_type,
 547                                                         parts.base,
 548                                                         parts.index),
 549                                                 true, NULL_TREE);
 550       else
 551         parts.index = parts.base;
 552       parts.base = NULL_TREE;
 553
 554       mem_ref = create_mem_ref_raw (type, &parts);
 555       if (mem_ref)
 556         return mem_ref;
 557     }
 558
 559   if (parts.offset && !integer_zerop (parts.offset))
 560     {
 561       /* Try adding offset to index.  */
 562       if (parts.index)
 563         parts.index = force_gimple_operand_bsi (bsi,
 564                                                 build2 (PLUS_EXPR, addr_type,
 565                                                         parts.index,
 566                                                         parts.offset),
 567                                                 true, NULL_TREE);
 568       else
 569         parts.index = parts.offset, bsi;
 570
 571       parts.offset = NULL_TREE;
 572
 573       mem_ref = create_mem_ref_raw (type, &parts);
 574       if (mem_ref)
 575         return mem_ref;
 576     }
 577
 578   /* Verify that the address is in the simplest possible shape
 579      (only a register).  If we cannot create such a memory reference,
 580      something is really wrong.  */
 581   gcc_assert (parts.symbol == NULL_TREE);
 582   gcc_assert (parts.base == NULL_TREE);
 583   gcc_assert (!parts.step || integer_onep (parts.step));
 584   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 585   gcc_unreachable ();
 586 }
 587
 588 /* Copies components of the address from OP to ADDR.  */
 589
 590 void
 591 get_address_description (tree op, struct mem_address *addr)
 592 {
 593   addr->symbol = TMR_SYMBOL (op);
 594   addr->base = TMR_BASE (op);
 595   addr->index = TMR_INDEX (op);
 596   addr->step = TMR_STEP (op);
 597   addr->offset = TMR_OFFSET (op);
 598 }
 599
 600 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 601
 602 void
 603 copy_mem_ref_info (tree to, tree from)
 604 {
 605   /* Copy the annotation, to preserve the aliasing information.  */
 606   TMR_TAG (to) = TMR_TAG (from);
 607
 608   /* And the info about the original reference.  */
 609   TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
 610 }
 611
 612 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 613    mem ref if anything changes, NULL_TREE otherwise.  */
 614
 615 tree
 616 maybe_fold_tmr (tree ref)
 617 {
 618   struct mem_address addr;
 619   bool changed = false;
 620   tree ret, off;
 621
 622   get_address_description (ref, &addr);
 623
 624   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
 625     {
 626       if (addr.offset)
 627         addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 628                                                addr.offset, addr.base);
 629       else
 630         addr.offset = addr.base;
 631
 632       addr.base = NULL_TREE;
 633       changed = true;
 634     }
 635
 636   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 637     {
 638       off = addr.index;
 639       if (addr.step)
 640         {
 641           off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
 642                                          off, addr.step);
 643           addr.step = NULL_TREE;
 644         }
 645
 646       if (addr.offset)
 647         {
 648           addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 649                                                  addr.offset, off);
 650         }
 651       else
 652         addr.offset = off;
 653
 654       addr.index = NULL_TREE;
 655       changed = true;
 656     }
 657
 658   if (!changed)
 659     return NULL_TREE;
 660
 661   ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
 662   if (!ret)
 663     return NULL_TREE;
 664
 665   copy_mem_ref_info (ret, ref);
 666   return ret;
 667 }
 668
 669 /* Dump PARTS to FILE.  */
 670
 671 extern void dump_mem_address (FILE *, struct mem_address *);
 672 void
 673 dump_mem_address (FILE *file, struct mem_address *parts)
 674 {
 675   if (parts->symbol)
 676     {
 677       fprintf (file, "symbol: ");
 678       print_generic_expr (file, parts->symbol, TDF_SLIM);
 679       fprintf (file, "\n");
 680     }
 681   if (parts->base)
 682     {
 683       fprintf (file, "base: ");
 684       print_generic_expr (file, parts->base, TDF_SLIM);
 685       fprintf (file, "\n");
 686     }
 687   if (parts->index)
 688     {
 689       fprintf (file, "index: ");
 690       print_generic_expr (file, parts->index, TDF_SLIM);
 691       fprintf (file, "\n");
 692     }
 693   if (parts->step)
 694     {
 695       fprintf (file, "step: ");
 696       print_generic_expr (file, parts->step, TDF_SLIM);
 697       fprintf (file, "\n");
 698     }
 699   if (parts->offset)
 700     {
 701       fprintf (file, "offset: ");
 702       print_generic_expr (file, parts->offset, TDF_SLIM);
 703       fprintf (file, "\n");
 704     }
 705 }
 706
 707 #include "gt-tree-ssa-address.h"