gcc/tree-ssa-address.c

   1 /* Memory address lowering and addressing mode selection.
   2    Copyright (C) 2004, 2006 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_PLUS (Pmode, act_elem, offset);
 138
 139           if (offset_p)
 140             *offset_p = &XEXP (act_elem, 1);
 141
 142           if (GET_CODE (symbol) == SYMBOL_REF
 143               || GET_CODE (symbol) == LABEL_REF
 144               || GET_CODE (symbol) == CONST)
 145             act_elem = gen_rtx_CONST (Pmode, act_elem);
 146         }
 147
 148       if (*addr)
 149         *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
 150       else
 151         *addr = act_elem;
 152     }
 153   else if (offset)
 154     {
 155       if (*addr)
 156         {
 157           *addr = gen_rtx_PLUS (Pmode, *addr, offset);
 158           if (offset_p)
 159             *offset_p = &XEXP (*addr, 1);
 160         }
 161       else
 162         {
 163           *addr = offset;
 164           if (offset_p)
 165             *offset_p = addr;
 166         }
 167     }
 168
 169   if (!*addr)
 170     *addr = const0_rtx;
 171 }
 172
 173 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
 174    If REALLY_EXPAND is false, just make fake registers instead
 175    of really expanding the operands, and perform the expansion in-place
 176    by using one of the "templates".  */
 177
 178 rtx
 179 addr_for_mem_ref (struct mem_address *addr, bool really_expand)
 180 {
 181   rtx address, sym, bse, idx, st, off;
 182   static bool templates_initialized = false;
 183   struct mem_addr_template *templ;
 184
 185   if (addr->step && !integer_onep (addr->step))
 186     st = immed_double_const (TREE_INT_CST_LOW (addr->step),
 187                              TREE_INT_CST_HIGH (addr->step), Pmode);
 188   else
 189     st = NULL_RTX;
 190
 191   if (addr->offset && !integer_zerop (addr->offset))
 192     off = immed_double_const (TREE_INT_CST_LOW (addr->offset),
 193                               TREE_INT_CST_HIGH (addr->offset), Pmode);
 194   else
 195     off = NULL_RTX;
 196
 197   if (!really_expand)
 198     {
 199       /* Reuse the templates for addresses, so that we do not waste memory.  */
 200       if (!templates_initialized)
 201         {
 202           unsigned i;
 203
 204           templates_initialized = true;
 205           sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup ("test_symbol"));
 206           bse = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
 207           idx = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
 208
 209           for (i = 0; i < 32; i++)
 210             gen_addr_rtx ((i & 16 ? sym : NULL_RTX),
 211                           (i & 8 ? bse : NULL_RTX),
 212                           (i & 4 ? idx : NULL_RTX),
 213                           (i & 2 ? const0_rtx : NULL_RTX),
 214                           (i & 1 ? const0_rtx : NULL_RTX),
 215                           &templates[i].ref,
 216                           &templates[i].step_p,
 217                           &templates[i].off_p);
 218         }
 219
 220       templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
 221                                      st, off);
 222       if (st)
 223         *templ->step_p = st;
 224       if (off)
 225         *templ->off_p = off;
 226
 227       return templ->ref;
 228     }
 229
 230   /* Otherwise really expand the expressions.  */
 231   sym = (addr->symbol
 232          ? expand_expr (build_addr (addr->symbol, current_function_decl),
 233                         NULL_RTX, Pmode, EXPAND_NORMAL)
 234          : NULL_RTX);
 235   bse = (addr->base
 236          ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
 237          : NULL_RTX);
 238   idx = (addr->index
 239          ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
 240          : NULL_RTX);
 241
 242   gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
 243   return address;
 244 }
 245
 246 /* Returns address of MEM_REF in TYPE.  */
 247
 248 tree
 249 tree_mem_ref_addr (tree type, tree mem_ref)
 250 {
 251   tree addr = NULL_TREE;
 252   tree act_elem;
 253   tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
 254
 255   act_elem = TMR_INDEX (mem_ref);
 256   if (act_elem)
 257     {
 258       act_elem = fold_convert (type, act_elem);
 259
 260       if (step)
 261         act_elem = fold_build2 (MULT_EXPR, type, act_elem,
 262                                 fold_convert (type, step));
 263       addr = act_elem;
 264     }
 265
 266   act_elem = TMR_BASE (mem_ref);
 267   if (act_elem)
 268     {
 269       act_elem = fold_convert (type, act_elem);
 270
 271       if (addr)
 272         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
 273       else
 274         addr = act_elem;
 275     }
 276
 277   act_elem = TMR_SYMBOL (mem_ref);
 278   if (act_elem)
 279     {
 280       act_elem = fold_convert (type, build_addr (act_elem,
 281                                                  current_function_decl));
 282       if (addr)
 283         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
 284       else
 285         addr = act_elem;
 286     }
 287
 288   if (!zero_p (offset))
 289     {
 290       act_elem = fold_convert (type, offset);
 291
 292       if (addr)
 293         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
 294       else
 295         addr = act_elem;
 296     }
 297
 298   if (!addr)
 299     addr = build_int_cst (type, 0);
 300
 301   return addr;
 302 }
 303
 304 /* Returns true if a memory reference in MODE and with parameters given by
 305    ADDR is valid on the current target.  */
 306
 307 static bool
 308 valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
 309 {
 310   rtx address;
 311
 312   address = addr_for_mem_ref (addr, false);
 313   if (!address)
 314     return false;
 315
 316   return memory_address_p (mode, address);
 317 }
 318
 319 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
 320    is valid on the current target and if so, creates and returns the
 321    TARGET_MEM_REF.  */
 322
 323 static tree
 324 create_mem_ref_raw (tree type, struct mem_address *addr)
 325 {
 326   if (!valid_mem_ref_p (TYPE_MODE (type), addr))
 327     return NULL_TREE;
 328
 329   if (addr->step && integer_onep (addr->step))
 330     addr->step = NULL_TREE;
 331
 332   if (addr->offset && zero_p (addr->offset))
 333     addr->offset = NULL_TREE;
 334
 335   return build7 (TARGET_MEM_REF, type,
 336                  addr->symbol, addr->base, addr->index,
 337                  addr->step, addr->offset, NULL, NULL);
 338 }
 339
 340 /* Returns true if OBJ is an object whose address is a link time constant.  */
 341
 342 static bool
 343 fixed_address_object_p (tree obj)
 344 {
 345   return (TREE_CODE (obj) == VAR_DECL
 346           && (TREE_STATIC (obj)
 347               || DECL_EXTERNAL (obj)));
 348 }
 349
 350 /* Adds COEF * ELT to PARTS.  TYPE is the type of the address we
 351    construct.  */
 352
 353 static void
 354 add_to_parts (struct mem_address *parts, tree type, tree elt,
 355               unsigned HOST_WIDE_INT coef)
 356 {
 357   /* Check if this is a symbol.  */
 358   if (!parts->symbol
 359       && coef == 1
 360       && TREE_CODE (elt) == ADDR_EXPR
 361       && fixed_address_object_p (TREE_OPERAND (elt, 0)))
 362     {
 363       parts->symbol = TREE_OPERAND (elt, 0);
 364       return;
 365     }
 366
 367   if (coef != 1)
 368     elt = fold_build2 (MULT_EXPR, type, fold_convert (type, elt),
 369                        build_int_cst_type (type, coef));
 370   else
 371     elt = fold_convert (type, elt);
 372
 373   if (!parts->base)
 374     {
 375       parts->base = elt;
 376       return;
 377     }
 378
 379   if (!parts->index)
 380     {
 381       parts->index = elt;
 382       return;
 383     }
 384
 385   /* Add ELT to base.  */
 386   parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
 387 }
 388
 389 /* Finds the most expensive multiplication in ADDR that can be
 390    expressed in an addressing mode and move the corresponding
 391    element(s) to PARTS.  TYPE is the type of the address we
 392    construct.  */
 393
 394 static void
 395 most_expensive_mult_to_index (struct mem_address *parts, tree type,
 396                               struct affine_tree_combination *addr)
 397 {
 398   unsigned HOST_WIDE_INT best_mult = 0;
 399   unsigned best_mult_cost = 0, acost;
 400   tree mult_elt = NULL_TREE, elt;
 401   unsigned i, j;
 402
 403   for (i = 0; i < addr->n; i++)
 404     {
 405       if (addr->coefs[i] == 1
 406           || !multiplier_allowed_in_address_p (addr->coefs[i]))
 407         continue;
 408
 409       acost = multiply_by_cost (addr->coefs[i], Pmode);
 410
 411       if (acost > best_mult_cost)
 412         {
 413           best_mult_cost = acost;
 414           best_mult = addr->coefs[i];
 415         }
 416     }
 417
 418   if (!best_mult)
 419     return;
 420
 421   for (i = j = 0; i < addr->n; i++)
 422     {
 423       if (addr->coefs[i] != best_mult)
 424         {
 425           addr->coefs[j] = addr->coefs[i];
 426           addr->elts[j] = addr->elts[i];
 427           j++;
 428           continue;
 429         }
 430
 431       elt = fold_convert (type, addr->elts[i]);
 432       if (!mult_elt)
 433         mult_elt = elt;
 434       else
 435         mult_elt = fold_build2 (PLUS_EXPR, type, mult_elt, elt);
 436     }
 437   addr->n = j;
 438
 439   parts->index = mult_elt;
 440   parts->step = build_int_cst_type (type, best_mult);
 441 }
 442
 443 /* Splits address ADDR into PARTS.
 444
 445    TODO -- be more clever about the distribution of the elements of ADDR
 446    to PARTS.  Some architectures do not support anything but single
 447    register in address, possibly with a small integer offset; while
 448    create_mem_ref will simplify the address to an acceptable shape
 449    later, it would be a small bit more efficient to know that asking
 450    for complicated addressing modes is useless.  */
 451
 452 static void
 453 addr_to_parts (struct affine_tree_combination *addr, tree type,
 454                struct mem_address *parts)
 455 {
 456   unsigned i;
 457
 458   parts->symbol = NULL_TREE;
 459   parts->base = NULL_TREE;
 460   parts->index = NULL_TREE;
 461   parts->step = NULL_TREE;
 462
 463   if (addr->offset)
 464     parts->offset = build_int_cst_type (type, addr->offset);
 465   else
 466     parts->offset = NULL_TREE;
 467
 468   /* First move the most expensive feasible multiplication
 469      to index.  */
 470   most_expensive_mult_to_index (parts, type, addr);
 471
 472   /* Then try to process the remaining elements.  */
 473   for (i = 0; i < addr->n; i++)
 474     add_to_parts (parts, type, addr->elts[i], addr->coefs[i]);
 475   if (addr->rest)
 476     add_to_parts (parts, type, addr->rest, 1);
 477 }
 478
 479 /* Force the PARTS to register.  */
 480
 481 static void
 482 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
 483 {
 484   if (parts->base)
 485     parts->base = force_gimple_operand_bsi (bsi, parts->base,
 486                                             true, NULL_TREE);
 487   if (parts->index)
 488     parts->index = force_gimple_operand_bsi (bsi, parts->index,
 489                                              true, NULL_TREE);
 490 }
 491
 492 /* Creates and returns a TARGET_MEM_REF for address ADDR.  If necessary
 493    computations are emitted in front of BSI.  TYPE is the mode
 494    of created memory reference.  */
 495
 496 tree
 497 create_mem_ref (block_stmt_iterator *bsi, tree type,
 498                 struct affine_tree_combination *addr)
 499 {
 500   tree mem_ref, tmp;
 501   tree addr_type = build_pointer_type (type);
 502   struct mem_address parts;
 503
 504   addr_to_parts (addr, addr_type, &parts);
 505   gimplify_mem_ref_parts (bsi, &parts);
 506   mem_ref = create_mem_ref_raw (type, &parts);
 507   if (mem_ref)
 508     return mem_ref;
 509
 510   /* The expression is too complicated.  Try making it simpler.  */
 511
 512   if (parts.step && !integer_onep (parts.step))
 513     {
 514       /* Move the multiplication to index.  */
 515       gcc_assert (parts.index);
 516       parts.index = force_gimple_operand_bsi (bsi,
 517                                               build2 (MULT_EXPR, addr_type,
 518                                                       parts.index, parts.step),
 519                                               true, NULL_TREE);
 520       parts.step = NULL_TREE;
 521
 522       mem_ref = create_mem_ref_raw (type, &parts);
 523       if (mem_ref)
 524         return mem_ref;
 525     }
 526
 527   if (parts.symbol)
 528     {
 529       tmp = build_addr (parts.symbol, current_function_decl);
 530
 531       /* Add the symbol to base, eventually forcing it to register.  */
 532       if (parts.base)
 533         {
 534           if (parts.index)
 535             parts.base = force_gimple_operand_bsi (bsi,
 536                                                    build2 (PLUS_EXPR, addr_type,
 537                                                            parts.base, tmp),
 538                                                    true, NULL_TREE);
 539           else
 540             {
 541               parts.index = parts.base;
 542               parts.base = tmp;
 543             }
 544         }
 545       else
 546         parts.base = tmp;
 547       parts.symbol = NULL_TREE;
 548
 549       mem_ref = create_mem_ref_raw (type, &parts);
 550       if (mem_ref)
 551         return mem_ref;
 552     }
 553
 554   if (parts.base)
 555     {
 556       /* Add base to index.  */
 557       if (parts.index)
 558         parts.index = force_gimple_operand_bsi (bsi,
 559                                                 build2 (PLUS_EXPR, addr_type,
 560                                                         parts.base,
 561                                                         parts.index),
 562                                                 true, NULL_TREE);
 563       else
 564         parts.index = parts.base;
 565       parts.base = NULL_TREE;
 566
 567       mem_ref = create_mem_ref_raw (type, &parts);
 568       if (mem_ref)
 569         return mem_ref;
 570     }
 571
 572   if (parts.offset && !integer_zerop (parts.offset))
 573     {
 574       /* Try adding offset to index.  */
 575       if (parts.index)
 576         parts.index = force_gimple_operand_bsi (bsi,
 577                                                 build2 (PLUS_EXPR, addr_type,
 578                                                         parts.index,
 579                                                         parts.offset),
 580                                                 true, NULL_TREE);
 581       else
 582         parts.index = parts.offset, bsi;
 583
 584       parts.offset = NULL_TREE;
 585
 586       mem_ref = create_mem_ref_raw (type, &parts);
 587       if (mem_ref)
 588         return mem_ref;
 589     }
 590
 591   /* Verify that the address is in the simplest possible shape
 592      (only a register).  If we cannot create such a memory reference,
 593      something is really wrong.  */
 594   gcc_assert (parts.symbol == NULL_TREE);
 595   gcc_assert (parts.base == NULL_TREE);
 596   gcc_assert (!parts.step || integer_onep (parts.step));
 597   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 598   gcc_unreachable ();
 599 }
 600
 601 /* Copies components of the address from OP to ADDR.  */
 602
 603 void
 604 get_address_description (tree op, struct mem_address *addr)
 605 {
 606   addr->symbol = TMR_SYMBOL (op);
 607   addr->base = TMR_BASE (op);
 608   addr->index = TMR_INDEX (op);
 609   addr->step = TMR_STEP (op);
 610   addr->offset = TMR_OFFSET (op);
 611 }
 612
 613 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 614
 615 void
 616 copy_mem_ref_info (tree to, tree from)
 617 {
 618   /* Copy the annotation, to preserve the aliasing information.  */
 619   TMR_TAG (to) = TMR_TAG (from);
 620
 621   /* And the info about the original reference.  */
 622   TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
 623 }
 624
 625 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 626    mem ref if anything changes, NULL_TREE otherwise.  */
 627
 628 tree
 629 maybe_fold_tmr (tree ref)
 630 {
 631   struct mem_address addr;
 632   bool changed = false;
 633   tree ret, off;
 634
 635   get_address_description (ref, &addr);
 636
 637   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
 638     {
 639       if (addr.offset)
 640         addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 641                                                addr.offset, addr.base);
 642       else
 643         addr.offset = addr.base;
 644
 645       addr.base = NULL_TREE;
 646       changed = true;
 647     }
 648
 649   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 650     {
 651       off = addr.index;
 652       if (addr.step)
 653         {
 654           off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
 655                                          off, addr.step);
 656           addr.step = NULL_TREE;
 657         }
 658
 659       if (addr.offset)
 660         {
 661           addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 662                                                  addr.offset, off);
 663         }
 664       else
 665         addr.offset = off;
 666
 667       addr.index = NULL_TREE;
 668       changed = true;
 669     }
 670
 671   if (!changed)
 672     return NULL_TREE;
 673
 674   ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
 675   if (!ret)
 676     return NULL_TREE;
 677
 678   copy_mem_ref_info (ret, ref);
 679   return ret;
 680 }
 681
 682 /* Dump PARTS to FILE.  */
 683
 684 extern void dump_mem_address (FILE *, struct mem_address *);
 685 void
 686 dump_mem_address (FILE *file, struct mem_address *parts)
 687 {
 688   if (parts->symbol)
 689     {
 690       fprintf (file, "symbol: ");
 691       print_generic_expr (file, parts->symbol, TDF_SLIM);
 692       fprintf (file, "\n");
 693     }
 694   if (parts->base)
 695     {
 696       fprintf (file, "base: ");
 697       print_generic_expr (file, parts->base, TDF_SLIM);
 698       fprintf (file, "\n");
 699     }
 700   if (parts->index)
 701     {
 702       fprintf (file, "index: ");
 703       print_generic_expr (file, parts->index, TDF_SLIM);
 704       fprintf (file, "\n");
 705     }
 706   if (parts->step)
 707     {
 708       fprintf (file, "step: ");
 709       print_generic_expr (file, parts->step, TDF_SLIM);
 710       fprintf (file, "\n");
 711     }
 712   if (parts->offset)
 713     {
 714       fprintf (file, "offset: ");
 715       print_generic_expr (file, parts->offset, TDF_SLIM);
 716       fprintf (file, "\n");
 717     }
 718 }
 719
 720 #include "gt-tree-ssa-address.h"