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       /* FIXME: Should use the correct memory mode rather than Pmode.  */
 401       if (addr->coefs[i] == 1
 402           || !multiplier_allowed_in_address_p (addr->coefs[i], Pmode))
 403         continue;
 404
 405       acost = multiply_by_cost (addr->coefs[i], Pmode);
 406
 407       if (acost > best_mult_cost)
 408         {
 409           best_mult_cost = acost;
 410           best_mult = addr->coefs[i];
 411         }
 412     }
 413
 414   if (!best_mult)
 415     return;
 416
 417   for (i = j = 0; i < addr->n; i++)
 418     {
 419       if (addr->coefs[i] != best_mult)
 420         {
 421           addr->coefs[j] = addr->coefs[i];
 422           addr->elts[j] = addr->elts[i];
 423           j++;
 424           continue;
 425         }
 426
 427       elt = fold_convert (type, addr->elts[i]);
 428       if (!mult_elt)
 429         mult_elt = elt;
 430       else
 431         mult_elt = fold_build2 (PLUS_EXPR, type, mult_elt, elt);
 432     }
 433   addr->n = j;
 434
 435   parts->index = mult_elt;
 436   parts->step = build_int_cst_type (type, best_mult);
 437 }
 438
 439 /* Splits address ADDR into PARTS.
 440
 441    TODO -- be more clever about the distribution of the elements of ADDR
 442    to PARTS.  Some architectures do not support anything but single
 443    register in address, possibly with a small integer offset; while
 444    create_mem_ref will simplify the address to an acceptable shape
 445    later, it would be a small bit more efficient to know that asking
 446    for complicated addressing modes is useless.  */
 447
 448 static void
 449 addr_to_parts (struct affine_tree_combination *addr, tree type,
 450                struct mem_address *parts)
 451 {
 452   unsigned i;
 453
 454   parts->symbol = NULL_TREE;
 455   parts->base = NULL_TREE;
 456   parts->index = NULL_TREE;
 457   parts->step = NULL_TREE;
 458
 459   if (addr->offset)
 460     parts->offset = build_int_cst_type (type, addr->offset);
 461   else
 462     parts->offset = NULL_TREE;
 463
 464   /* First move the most expensive feasible multiplication
 465      to index.  */
 466   most_expensive_mult_to_index (parts, type, addr);
 467
 468   /* Then try to process the remaining elements.  */
 469   for (i = 0; i < addr->n; i++)
 470     add_to_parts (parts, type, addr->elts[i], addr->coefs[i]);
 471   if (addr->rest)
 472     add_to_parts (parts, type, addr->rest, 1);
 473 }
 474
 475 /* Force the PARTS to register.  */
 476
 477 static void
 478 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
 479 {
 480   if (parts->base)
 481     parts->base = force_gimple_operand_bsi (bsi, parts->base,
 482                                             true, NULL_TREE);
 483   if (parts->index)
 484     parts->index = force_gimple_operand_bsi (bsi, parts->index,
 485                                              true, NULL_TREE);
 486 }
 487
 488 /* Creates and returns a TARGET_MEM_REF for address ADDR.  If necessary
 489    computations are emitted in front of BSI.  TYPE is the mode
 490    of created memory reference.  */
 491
 492 tree
 493 create_mem_ref (block_stmt_iterator *bsi, tree type,
 494                 struct affine_tree_combination *addr)
 495 {
 496   tree mem_ref, tmp;
 497   tree addr_type = build_pointer_type (type);
 498   struct mem_address parts;
 499
 500   addr_to_parts (addr, addr_type, &parts);
 501   gimplify_mem_ref_parts (bsi, &parts);
 502   mem_ref = create_mem_ref_raw (type, &parts);
 503   if (mem_ref)
 504     return mem_ref;
 505
 506   /* The expression is too complicated.  Try making it simpler.  */
 507
 508   if (parts.step && !integer_onep (parts.step))
 509     {
 510       /* Move the multiplication to index.  */
 511       gcc_assert (parts.index);
 512       parts.index = force_gimple_operand_bsi (bsi,
 513                                               build2 (MULT_EXPR, addr_type,
 514                                                       parts.index, parts.step),
 515                                               true, NULL_TREE);
 516       parts.step = NULL_TREE;
 517
 518       mem_ref = create_mem_ref_raw (type, &parts);
 519       if (mem_ref)
 520         return mem_ref;
 521     }
 522
 523   if (parts.symbol)
 524     {
 525       tmp = build_addr (parts.symbol, current_function_decl);
 526
 527       /* Add the symbol to base, eventually forcing it to register.  */
 528       if (parts.base)
 529         {
 530           if (parts.index)
 531             parts.base = force_gimple_operand_bsi (bsi,
 532                                                    build2 (PLUS_EXPR, addr_type,
 533                                                            parts.base, tmp),
 534                                                    true, NULL_TREE);
 535           else
 536             {
 537               parts.index = parts.base;
 538               parts.base = tmp;
 539             }
 540         }
 541       else
 542         parts.base = tmp;
 543       parts.symbol = NULL_TREE;
 544
 545       mem_ref = create_mem_ref_raw (type, &parts);
 546       if (mem_ref)
 547         return mem_ref;
 548     }
 549
 550   if (parts.base)
 551     {
 552       /* Add base to index.  */
 553       if (parts.index)
 554         parts.index = force_gimple_operand_bsi (bsi,
 555                                                 build2 (PLUS_EXPR, addr_type,
 556                                                         parts.base,
 557                                                         parts.index),
 558                                                 true, NULL_TREE);
 559       else
 560         parts.index = parts.base;
 561       parts.base = NULL_TREE;
 562
 563       mem_ref = create_mem_ref_raw (type, &parts);
 564       if (mem_ref)
 565         return mem_ref;
 566     }
 567
 568   if (parts.offset && !integer_zerop (parts.offset))
 569     {
 570       /* Try adding offset to index.  */
 571       if (parts.index)
 572         parts.index = force_gimple_operand_bsi (bsi,
 573                                                 build2 (PLUS_EXPR, addr_type,
 574                                                         parts.index,
 575                                                         parts.offset),
 576                                                 true, NULL_TREE);
 577       else
 578         parts.index = parts.offset, bsi;
 579
 580       parts.offset = NULL_TREE;
 581
 582       mem_ref = create_mem_ref_raw (type, &parts);
 583       if (mem_ref)
 584         return mem_ref;
 585     }
 586
 587   /* Verify that the address is in the simplest possible shape
 588      (only a register).  If we cannot create such a memory reference,
 589      something is really wrong.  */
 590   gcc_assert (parts.symbol == NULL_TREE);
 591   gcc_assert (parts.base == NULL_TREE);
 592   gcc_assert (!parts.step || integer_onep (parts.step));
 593   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 594   gcc_unreachable ();
 595 }
 596
 597 /* Copies components of the address from OP to ADDR.  */
 598
 599 void
 600 get_address_description (tree op, struct mem_address *addr)
 601 {
 602   addr->symbol = TMR_SYMBOL (op);
 603   addr->base = TMR_BASE (op);
 604   addr->index = TMR_INDEX (op);
 605   addr->step = TMR_STEP (op);
 606   addr->offset = TMR_OFFSET (op);
 607 }
 608
 609 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 610
 611 void
 612 copy_mem_ref_info (tree to, tree from)
 613 {
 614   /* Copy the annotation, to preserve the aliasing information.  */
 615   TMR_TAG (to) = TMR_TAG (from);
 616
 617   /* And the info about the original reference.  */
 618   TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
 619 }
 620
 621 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 622    mem ref if anything changes, NULL_TREE otherwise.  */
 623
 624 tree
 625 maybe_fold_tmr (tree ref)
 626 {
 627   struct mem_address addr;
 628   bool changed = false;
 629   tree ret, off;
 630
 631   get_address_description (ref, &addr);
 632
 633   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
 634     {
 635       if (addr.offset)
 636         addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 637                                                addr.offset, addr.base);
 638       else
 639         addr.offset = addr.base;
 640
 641       addr.base = NULL_TREE;
 642       changed = true;
 643     }
 644
 645   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 646     {
 647       off = addr.index;
 648       if (addr.step)
 649         {
 650           off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
 651                                          off, addr.step);
 652           addr.step = NULL_TREE;
 653         }
 654
 655       if (addr.offset)
 656         {
 657           addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
 658                                                  addr.offset, off);
 659         }
 660       else
 661         addr.offset = off;
 662
 663       addr.index = NULL_TREE;
 664       changed = true;
 665     }
 666
 667   if (!changed)
 668     return NULL_TREE;
 669
 670   ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
 671   if (!ret)
 672     return NULL_TREE;
 673
 674   copy_mem_ref_info (ret, ref);
 675   return ret;
 676 }
 677
 678 /* Dump PARTS to FILE.  */
 679
 680 extern void dump_mem_address (FILE *, struct mem_address *);
 681 void
 682 dump_mem_address (FILE *file, struct mem_address *parts)
 683 {
 684   if (parts->symbol)
 685     {
 686       fprintf (file, "symbol: ");
 687       print_generic_expr (file, parts->symbol, TDF_SLIM);
 688       fprintf (file, "\n");
 689     }
 690   if (parts->base)
 691     {
 692       fprintf (file, "base: ");
 693       print_generic_expr (file, parts->base, TDF_SLIM);
 694       fprintf (file, "\n");
 695     }
 696   if (parts->index)
 697     {
 698       fprintf (file, "index: ");
 699       print_generic_expr (file, parts->index, TDF_SLIM);
 700       fprintf (file, "\n");
 701     }
 702   if (parts->step)
 703     {
 704       fprintf (file, "step: ");
 705       print_generic_expr (file, parts->step, TDF_SLIM);
 706       fprintf (file, "\n");
 707     }
 708   if (parts->offset)
 709     {
 710       fprintf (file, "offset: ");
 711       print_generic_expr (file, parts->offset, TDF_SLIM);
 712       fprintf (file, "\n");
 713     }
 714 }
 715
 716 #include "gt-tree-ssa-address.h"