gcc/tree-ssa-address.c

   1 /* Memory address lowering and addressing mode selection.
   2    Copyright (C) 2004, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  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 "tm_p.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "tree-pretty-print.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "tree-pass.h"
  36 #include "timevar.h"
  37 #include "flags.h"
  38 #include "tree-inline.h"
  39 #include "tree-affine.h"
  40
  41 /* FIXME: We compute address costs using RTL.  */
  42 #include "insn-config.h"
  43 #include "rtl.h"
  44 #include "recog.h"
  45 #include "expr.h"
  46 #include "ggc.h"
  47 #include "target.h"
  48
  49 /* TODO -- handling of symbols (according to Richard Hendersons
  50    comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
  51
  52    There are at least 5 different kinds of symbols that we can run up against:
  53
  54      (1) binds_local_p, small data area.
  55      (2) binds_local_p, eg local statics
  56      (3) !binds_local_p, eg global variables
  57      (4) thread local, local_exec
  58      (5) thread local, !local_exec
  59
  60    Now, (1) won't appear often in an array context, but it certainly can.
  61    All you have to do is set -GN high enough, or explicitly mark any
  62    random object __attribute__((section (".sdata"))).
  63
  64    All of these affect whether or not a symbol is in fact a valid address.
  65    The only one tested here is (3).  And that result may very well
  66    be incorrect for (4) or (5).
  67
  68    An incorrect result here does not cause incorrect results out the
  69    back end, because the expander in expr.c validizes the address.  However
  70    it would be nice to improve the handling here in order to produce more
  71    precise results.  */
  72
  73 /* A "template" for memory address, used to determine whether the address is
  74    valid for mode.  */
  75
  76 typedef struct GTY (()) mem_addr_template {
  77   rtx ref;                      /* The template.  */
  78   rtx * GTY ((skip)) step_p;    /* The point in template where the step should be
  79                                    filled in.  */
  80   rtx * GTY ((skip)) off_p;     /* The point in template where the offset should
  81                                    be filled in.  */
  82 } mem_addr_template;
  83
  84 DEF_VEC_O (mem_addr_template);
  85 DEF_VEC_ALLOC_O (mem_addr_template, gc);
  86
  87 /* The templates.  Each of the low five bits of the index corresponds to one
  88    component of TARGET_MEM_REF being present, while the high bits identify
  89    the address space.  See TEMPL_IDX.  */
  90
  91 static GTY(()) VEC (mem_addr_template, gc) *mem_addr_template_list;
  92
  93 #define TEMPL_IDX(AS, SYMBOL, BASE, INDEX, STEP, OFFSET) \
  94   (((int) (AS) << 5) \
  95    | ((SYMBOL != 0) << 4) \
  96    | ((BASE != 0) << 3) \
  97    | ((INDEX != 0) << 2) \
  98    | ((STEP != 0) << 1) \
  99    | (OFFSET != 0))
 100
 101 /* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
 102    STEP and OFFSET to *ADDR using address mode ADDRESS_MODE.  Stores pointers
 103    to where step is placed to *STEP_P and offset to *OFFSET_P.  */
 104
 105 static void
 106 gen_addr_rtx (enum machine_mode address_mode,
 107               rtx symbol, rtx base, rtx index, rtx step, rtx offset,
 108               rtx *addr, rtx **step_p, rtx **offset_p)
 109 {
 110   rtx act_elem;
 111
 112   *addr = NULL_RTX;
 113   if (step_p)
 114     *step_p = NULL;
 115   if (offset_p)
 116     *offset_p = NULL;
 117
 118   if (index)
 119     {
 120       act_elem = index;
 121       if (step)
 122         {
 123           act_elem = gen_rtx_MULT (address_mode, act_elem, step);
 124
 125           if (step_p)
 126             *step_p = &XEXP (act_elem, 1);
 127         }
 128
 129       *addr = act_elem;
 130     }
 131
 132   if (base)
 133     {
 134       if (*addr)
 135         *addr = simplify_gen_binary (PLUS, address_mode, base, *addr);
 136       else
 137         *addr = base;
 138     }
 139
 140   if (symbol)
 141     {
 142       act_elem = symbol;
 143       if (offset)
 144         {
 145           act_elem = gen_rtx_PLUS (address_mode, act_elem, offset);
 146
 147           if (offset_p)
 148             *offset_p = &XEXP (act_elem, 1);
 149
 150           if (GET_CODE (symbol) == SYMBOL_REF
 151               || GET_CODE (symbol) == LABEL_REF
 152               || GET_CODE (symbol) == CONST)
 153             act_elem = gen_rtx_CONST (address_mode, act_elem);
 154         }
 155
 156       if (*addr)
 157         *addr = gen_rtx_PLUS (address_mode, *addr, act_elem);
 158       else
 159         *addr = act_elem;
 160     }
 161   else if (offset)
 162     {
 163       if (*addr)
 164         {
 165           *addr = gen_rtx_PLUS (address_mode, *addr, offset);
 166           if (offset_p)
 167             *offset_p = &XEXP (*addr, 1);
 168         }
 169       else
 170         {
 171           *addr = offset;
 172           if (offset_p)
 173             *offset_p = addr;
 174         }
 175     }
 176
 177   if (!*addr)
 178     *addr = const0_rtx;
 179 }
 180
 181 /* Returns address for TARGET_MEM_REF with parameters given by ADDR
 182    in address space AS.
 183    If REALLY_EXPAND is false, just make fake registers instead
 184    of really expanding the operands, and perform the expansion in-place
 185    by using one of the "templates".  */
 186
 187 rtx
 188 addr_for_mem_ref (struct mem_address *addr, addr_space_t as,
 189                   bool really_expand)
 190 {
 191   enum machine_mode address_mode = targetm.addr_space.address_mode (as);
 192   rtx address, sym, bse, idx, st, off;
 193   struct mem_addr_template *templ;
 194
 195   if (addr->step && !integer_onep (addr->step))
 196     st = immed_double_int_const (tree_to_double_int (addr->step), address_mode);
 197   else
 198     st = NULL_RTX;
 199
 200   if (addr->offset && !integer_zerop (addr->offset))
 201     off = immed_double_int_const
 202             (double_int_sext (tree_to_double_int (addr->offset),
 203                               TYPE_PRECISION (TREE_TYPE (addr->offset))),
 204              address_mode);
 205   else
 206     off = NULL_RTX;
 207
 208   if (!really_expand)
 209     {
 210       unsigned int templ_index
 211         = TEMPL_IDX (as, addr->symbol, addr->base, addr->index, st, off);
 212
 213       if (templ_index
 214           >= VEC_length (mem_addr_template, mem_addr_template_list))
 215         VEC_safe_grow_cleared (mem_addr_template, gc, mem_addr_template_list,
 216                                templ_index + 1);
 217
 218       /* Reuse the templates for addresses, so that we do not waste memory.  */
 219       templ = VEC_index (mem_addr_template, mem_addr_template_list, templ_index);
 220       if (!templ->ref)
 221         {
 222           sym = (addr->symbol ?
 223                  gen_rtx_SYMBOL_REF (address_mode, ggc_strdup ("test_symbol"))
 224                  : NULL_RTX);
 225           bse = (addr->base ?
 226                  gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1)
 227                  : NULL_RTX);
 228           idx = (addr->index ?
 229                  gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2)
 230                  : NULL_RTX);
 231
 232           gen_addr_rtx (address_mode, sym, bse, idx,
 233                         st? const0_rtx : NULL_RTX,
 234                         off? const0_rtx : NULL_RTX,
 235                         &templ->ref,
 236                         &templ->step_p,
 237                         &templ->off_p);
 238         }
 239
 240       if (st)
 241         *templ->step_p = st;
 242       if (off)
 243         *templ->off_p = off;
 244
 245       return templ->ref;
 246     }
 247
 248   /* Otherwise really expand the expressions.  */
 249   sym = (addr->symbol
 250          ? expand_expr (build_addr (addr->symbol, current_function_decl),
 251                         NULL_RTX, address_mode, EXPAND_NORMAL)
 252          : NULL_RTX);
 253   bse = (addr->base
 254          ? expand_expr (addr->base, NULL_RTX, address_mode, EXPAND_NORMAL)
 255          : NULL_RTX);
 256   idx = (addr->index
 257          ? expand_expr (addr->index, NULL_RTX, address_mode, EXPAND_NORMAL)
 258          : NULL_RTX);
 259
 260   gen_addr_rtx (address_mode, sym, bse, idx, st, off, &address, NULL, NULL);
 261   return address;
 262 }
 263
 264 /* Returns address of MEM_REF in TYPE.  */
 265
 266 tree
 267 tree_mem_ref_addr (tree type, tree mem_ref)
 268 {
 269   tree addr;
 270   tree act_elem;
 271   tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
 272   tree sym = TMR_SYMBOL (mem_ref), base = TMR_BASE (mem_ref);
 273   tree addr_base = NULL_TREE, addr_off = NULL_TREE;
 274
 275   if (sym)
 276     addr_base = fold_convert (type, build_addr (sym, current_function_decl));
 277   else if (base && POINTER_TYPE_P (TREE_TYPE (base)))
 278     {
 279       addr_base = fold_convert (type, base);
 280       base = NULL_TREE;
 281     }
 282
 283   act_elem = TMR_INDEX (mem_ref);
 284   if (act_elem)
 285     {
 286       if (step)
 287         act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
 288       addr_off = act_elem;
 289     }
 290
 291   act_elem = base;
 292   if (act_elem)
 293     {
 294       if (addr_off)
 295         addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
 296       else
 297         addr_off = act_elem;
 298     }
 299
 300   if (offset && !integer_zerop (offset))
 301     {
 302       offset = fold_convert (sizetype, offset);
 303       if (addr_off)
 304         addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
 305       else
 306         addr_off = offset;
 307     }
 308
 309   if (addr_off)
 310     {
 311       if (addr_base)
 312         addr = fold_build2 (POINTER_PLUS_EXPR, type, addr_base, addr_off);
 313       else
 314         addr = fold_convert (type, addr_off);
 315     }
 316   else if (addr_base)
 317     addr = addr_base;
 318   else
 319     addr = build_int_cst (type, 0);
 320
 321   return addr;
 322 }
 323
 324 /* Returns true if a memory reference in MODE and with parameters given by
 325    ADDR is valid on the current target.  */
 326
 327 static bool
 328 valid_mem_ref_p (enum machine_mode mode, addr_space_t as,
 329                  struct mem_address *addr)
 330 {
 331   rtx address;
 332
 333   address = addr_for_mem_ref (addr, as, false);
 334   if (!address)
 335     return false;
 336
 337   return memory_address_addr_space_p (mode, address, as);
 338 }
 339
 340 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
 341    is valid on the current target and if so, creates and returns the
 342    TARGET_MEM_REF.  */
 343
 344 static tree
 345 create_mem_ref_raw (tree type, tree alias_ptr_type, struct mem_address *addr)
 346 {
 347   if (!valid_mem_ref_p (TYPE_MODE (type), TYPE_ADDR_SPACE (type), addr))
 348     return NULL_TREE;
 349
 350   if (addr->step && integer_onep (addr->step))
 351     addr->step = NULL_TREE;
 352
 353   if (addr->offset)
 354     addr->offset = fold_convert (alias_ptr_type, addr->offset);
 355   else
 356     addr->offset = build_int_cst (alias_ptr_type, 0);
 357
 358   /* If possible use a plain MEM_REF instead of a TARGET_MEM_REF.  */
 359   if (alias_ptr_type
 360       && !addr->index
 361       && !addr->step
 362       && (!addr->base || POINTER_TYPE_P (TREE_TYPE (addr->base))))
 363     {
 364       tree base;
 365       gcc_assert (!addr->symbol ^ !addr->base);
 366       if (addr->symbol)
 367         base = build_fold_addr_expr (addr->symbol);
 368       else
 369         base = addr->base;
 370       return fold_build2 (MEM_REF, type, base, addr->offset);
 371     }
 372
 373   return build5 (TARGET_MEM_REF, type,
 374                  addr->symbol, addr->base, addr->index,
 375                  addr->step, addr->offset);
 376 }
 377
 378 /* Returns true if OBJ is an object whose address is a link time constant.  */
 379
 380 static bool
 381 fixed_address_object_p (tree obj)
 382 {
 383   return (TREE_CODE (obj) == VAR_DECL
 384           && (TREE_STATIC (obj)
 385               || DECL_EXTERNAL (obj))
 386           && ! DECL_DLLIMPORT_P (obj));
 387 }
 388
 389 /* If ADDR contains an address of object that is a link time constant,
 390    move it to PARTS->symbol.  */
 391
 392 static void
 393 move_fixed_address_to_symbol (struct mem_address *parts, aff_tree *addr)
 394 {
 395   unsigned i;
 396   tree val = NULL_TREE;
 397
 398   for (i = 0; i < addr->n; i++)
 399     {
 400       if (!double_int_one_p (addr->elts[i].coef))
 401         continue;
 402
 403       val = addr->elts[i].val;
 404       if (TREE_CODE (val) == ADDR_EXPR
 405           && fixed_address_object_p (TREE_OPERAND (val, 0)))
 406         break;
 407     }
 408
 409   if (i == addr->n)
 410     return;
 411
 412   parts->symbol = TREE_OPERAND (val, 0);
 413   aff_combination_remove_elt (addr, i);
 414 }
 415
 416 /* If ADDR contains an instance of BASE_HINT, move it to PARTS->base.  */
 417
 418 static void
 419 move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
 420                    aff_tree *addr)
 421 {
 422   unsigned i;
 423   tree val = NULL_TREE;
 424   int qual;
 425
 426   for (i = 0; i < addr->n; i++)
 427     {
 428       if (!double_int_one_p (addr->elts[i].coef))
 429         continue;
 430
 431       val = addr->elts[i].val;
 432       if (operand_equal_p (val, base_hint, 0))
 433         break;
 434     }
 435
 436   if (i == addr->n)
 437     return;
 438
 439   /* Cast value to appropriate pointer type.  We cannot use a pointer
 440      to TYPE directly, as the back-end will assume registers of pointer
 441      type are aligned, and just the base itself may not actually be.
 442      We use void pointer to the type's address space instead.  */
 443   qual = ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (type));
 444   type = build_qualified_type (void_type_node, qual);
 445   parts->base = fold_convert (build_pointer_type (type), val);
 446   aff_combination_remove_elt (addr, i);
 447 }
 448
 449 /* If ADDR contains an address of a dereferenced pointer, move it to
 450    PARTS->base.  */
 451
 452 static void
 453 move_pointer_to_base (struct mem_address *parts, aff_tree *addr)
 454 {
 455   unsigned i;
 456   tree val = NULL_TREE;
 457
 458   for (i = 0; i < addr->n; i++)
 459     {
 460       if (!double_int_one_p (addr->elts[i].coef))
 461         continue;
 462
 463       val = addr->elts[i].val;
 464       if (POINTER_TYPE_P (TREE_TYPE (val)))
 465         break;
 466     }
 467
 468   if (i == addr->n)
 469     return;
 470
 471   parts->base = val;
 472   aff_combination_remove_elt (addr, i);
 473 }
 474
 475 /* Moves the loop variant part V in linear address ADDR to be the index
 476    of PARTS.  */
 477
 478 static void
 479 move_variant_to_index (struct mem_address *parts, aff_tree *addr, tree v)
 480 {
 481   unsigned i;
 482   tree val = NULL_TREE;
 483
 484   gcc_assert (!parts->index);
 485   for (i = 0; i < addr->n; i++)
 486     {
 487       val = addr->elts[i].val;
 488       if (operand_equal_p (val, v, 0))
 489         break;
 490     }
 491
 492   if (i == addr->n)
 493     return;
 494
 495   parts->index = fold_convert (sizetype, val);
 496   parts->step = double_int_to_tree (sizetype, addr->elts[i].coef);
 497   aff_combination_remove_elt (addr, i);
 498 }
 499
 500 /* Adds ELT to PARTS.  */
 501
 502 static void
 503 add_to_parts (struct mem_address *parts, tree elt)
 504 {
 505   tree type;
 506
 507   if (!parts->index)
 508     {
 509       parts->index = fold_convert (sizetype, elt);
 510       return;
 511     }
 512
 513   if (!parts->base)
 514     {
 515       parts->base = elt;
 516       return;
 517     }
 518
 519   /* Add ELT to base.  */
 520   type = TREE_TYPE (parts->base);
 521   if (POINTER_TYPE_P (type))
 522     parts->base = fold_build2 (POINTER_PLUS_EXPR, type,
 523                                parts->base,
 524                                fold_convert (sizetype, elt));
 525   else
 526     parts->base = fold_build2 (PLUS_EXPR, type,
 527                                parts->base, elt);
 528 }
 529
 530 /* Finds the most expensive multiplication in ADDR that can be
 531    expressed in an addressing mode and move the corresponding
 532    element(s) to PARTS.  */
 533
 534 static void
 535 most_expensive_mult_to_index (tree type, struct mem_address *parts,
 536                               aff_tree *addr, bool speed)
 537 {
 538   addr_space_t as = TYPE_ADDR_SPACE (type);
 539   enum machine_mode address_mode = targetm.addr_space.address_mode (as);
 540   HOST_WIDE_INT coef;
 541   double_int best_mult, amult, amult_neg;
 542   unsigned best_mult_cost = 0, acost;
 543   tree mult_elt = NULL_TREE, elt;
 544   unsigned i, j;
 545   enum tree_code op_code;
 546
 547   best_mult = double_int_zero;
 548   for (i = 0; i < addr->n; i++)
 549     {
 550       if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
 551         continue;
 552
 553       coef = double_int_to_shwi (addr->elts[i].coef);
 554       if (coef == 1
 555           || !multiplier_allowed_in_address_p (coef, TYPE_MODE (type), as))
 556         continue;
 557
 558       acost = multiply_by_cost (coef, address_mode, speed);
 559
 560       if (acost > best_mult_cost)
 561         {
 562           best_mult_cost = acost;
 563           best_mult = addr->elts[i].coef;
 564         }
 565     }
 566
 567   if (!best_mult_cost)
 568     return;
 569
 570   /* Collect elements multiplied by best_mult.  */
 571   for (i = j = 0; i < addr->n; i++)
 572     {
 573       amult = addr->elts[i].coef;
 574       amult_neg = double_int_ext_for_comb (double_int_neg (amult), addr);
 575
 576       if (double_int_equal_p (amult, best_mult))
 577         op_code = PLUS_EXPR;
 578       else if (double_int_equal_p (amult_neg, best_mult))
 579         op_code = MINUS_EXPR;
 580       else
 581         {
 582           addr->elts[j] = addr->elts[i];
 583           j++;
 584           continue;
 585         }
 586
 587       elt = fold_convert (sizetype, addr->elts[i].val);
 588       if (mult_elt)
 589         mult_elt = fold_build2 (op_code, sizetype, mult_elt, elt);
 590       else if (op_code == PLUS_EXPR)
 591         mult_elt = elt;
 592       else
 593         mult_elt = fold_build1 (NEGATE_EXPR, sizetype, elt);
 594     }
 595   addr->n = j;
 596
 597   parts->index = mult_elt;
 598   parts->step = double_int_to_tree (sizetype, best_mult);
 599 }
 600
 601 /* Splits address ADDR for a memory access of type TYPE into PARTS.
 602    If BASE_HINT is non-NULL, it specifies an SSA name to be used
 603    preferentially as base of the reference, and IV_CAND is the selected
 604    iv candidate used in ADDR.
 605
 606    TODO -- be more clever about the distribution of the elements of ADDR
 607    to PARTS.  Some architectures do not support anything but single
 608    register in address, possibly with a small integer offset; while
 609    create_mem_ref will simplify the address to an acceptable shape
 610    later, it would be more efficient to know that asking for complicated
 611    addressing modes is useless.  */
 612
 613 static void
 614 addr_to_parts (tree type, aff_tree *addr, tree iv_cand,
 615                tree base_hint, struct mem_address *parts,
 616                bool speed)
 617 {
 618   tree part;
 619   unsigned i;
 620
 621   parts->symbol = NULL_TREE;
 622   parts->base = NULL_TREE;
 623   parts->index = NULL_TREE;
 624   parts->step = NULL_TREE;
 625
 626   if (!double_int_zero_p (addr->offset))
 627     parts->offset = double_int_to_tree (sizetype, addr->offset);
 628   else
 629     parts->offset = NULL_TREE;
 630
 631   /* Try to find a symbol.  */
 632   move_fixed_address_to_symbol (parts, addr);
 633
 634   /* No need to do address parts reassociation if the number of parts
 635      is <= 2 -- in that case, no loop invariant code motion can be
 636      exposed.  */
 637
 638   if (!base_hint && (addr->n > 2))
 639     move_variant_to_index (parts, addr, iv_cand);
 640
 641   /* First move the most expensive feasible multiplication
 642      to index.  */
 643   if (!parts->index)
 644     most_expensive_mult_to_index (type, parts, addr, speed);
 645
 646   /* Try to find a base of the reference.  Since at the moment
 647      there is no reliable way how to distinguish between pointer and its
 648      offset, this is just a guess.  */
 649   if (!parts->symbol && base_hint)
 650     move_hint_to_base (type, parts, base_hint, addr);
 651   if (!parts->symbol && !parts->base)
 652     move_pointer_to_base (parts, addr);
 653
 654   /* Then try to process the remaining elements.  */
 655   for (i = 0; i < addr->n; i++)
 656     {
 657       part = fold_convert (sizetype, addr->elts[i].val);
 658       if (!double_int_one_p (addr->elts[i].coef))
 659         part = fold_build2 (MULT_EXPR, sizetype, part,
 660                             double_int_to_tree (sizetype, addr->elts[i].coef));
 661       add_to_parts (parts, part);
 662     }
 663   if (addr->rest)
 664     add_to_parts (parts, fold_convert (sizetype, addr->rest));
 665 }
 666
 667 /* Force the PARTS to register.  */
 668
 669 static void
 670 gimplify_mem_ref_parts (gimple_stmt_iterator *gsi, struct mem_address *parts)
 671 {
 672   if (parts->base)
 673     parts->base = force_gimple_operand_gsi (gsi, parts->base,
 674                                             true, NULL_TREE,
 675                                             true, GSI_SAME_STMT);
 676   if (parts->index)
 677     parts->index = force_gimple_operand_gsi (gsi, parts->index,
 678                                              true, NULL_TREE,
 679                                              true, GSI_SAME_STMT);
 680 }
 681
 682 /* Creates and returns a TARGET_MEM_REF for address ADDR.  If necessary
 683    computations are emitted in front of GSI.  TYPE is the mode
 684    of created memory reference. IV_CAND is the selected iv candidate in ADDR,
 685    and BASE_HINT is non NULL if IV_CAND comes from a base address
 686    object.  */
 687
 688 tree
 689 create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
 690                 tree alias_ptr_type, tree iv_cand, tree base_hint, bool speed)
 691 {
 692   tree mem_ref, tmp;
 693   tree atype;
 694   struct mem_address parts;
 695
 696   addr_to_parts (type, addr, iv_cand, base_hint, &parts, speed);
 697   gimplify_mem_ref_parts (gsi, &parts);
 698   mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 699   if (mem_ref)
 700     return mem_ref;
 701
 702   /* The expression is too complicated.  Try making it simpler.  */
 703
 704   if (parts.step && !integer_onep (parts.step))
 705     {
 706       /* Move the multiplication to index.  */
 707       gcc_assert (parts.index);
 708       parts.index = force_gimple_operand_gsi (gsi,
 709                                 fold_build2 (MULT_EXPR, sizetype,
 710                                              parts.index, parts.step),
 711                                 true, NULL_TREE, true, GSI_SAME_STMT);
 712       parts.step = NULL_TREE;
 713
 714       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 715       if (mem_ref)
 716         return mem_ref;
 717     }
 718
 719   if (parts.symbol)
 720     {
 721       tmp = build_addr (parts.symbol, current_function_decl);
 722       gcc_assert (is_gimple_val (tmp));
 723
 724       /* Add the symbol to base, eventually forcing it to register.  */
 725       if (parts.base)
 726         {
 727           gcc_assert (useless_type_conversion_p
 728                                 (sizetype, TREE_TYPE (parts.base)));
 729
 730           if (parts.index)
 731             {
 732               atype = TREE_TYPE (tmp);
 733               parts.base = force_gimple_operand_gsi (gsi,
 734                         fold_build2 (POINTER_PLUS_EXPR, atype,
 735                                      tmp,
 736                                      fold_convert (sizetype, parts.base)),
 737                         true, NULL_TREE, true, GSI_SAME_STMT);
 738             }
 739           else
 740             {
 741               parts.index = parts.base;
 742               parts.base = tmp;
 743             }
 744         }
 745       else
 746         parts.base = tmp;
 747       parts.symbol = NULL_TREE;
 748
 749       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 750       if (mem_ref)
 751         return mem_ref;
 752     }
 753
 754   if (parts.index)
 755     {
 756       /* Add index to base.  */
 757       if (parts.base)
 758         {
 759           atype = TREE_TYPE (parts.base);
 760           parts.base = force_gimple_operand_gsi (gsi,
 761                         fold_build2 (POINTER_PLUS_EXPR, atype,
 762                                      parts.base,
 763                                      parts.index),
 764                         true, NULL_TREE, true, GSI_SAME_STMT);
 765         }
 766       else
 767         parts.base = parts.index;
 768       parts.index = NULL_TREE;
 769
 770       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 771       if (mem_ref)
 772         return mem_ref;
 773     }
 774
 775   if (parts.offset && !integer_zerop (parts.offset))
 776     {
 777       /* Try adding offset to base.  */
 778       if (parts.base)
 779         {
 780           atype = TREE_TYPE (parts.base);
 781           parts.base = force_gimple_operand_gsi (gsi,
 782                         fold_build2 (POINTER_PLUS_EXPR, atype,
 783                                      parts.base,
 784                                      fold_convert (sizetype, parts.offset)),
 785                         true, NULL_TREE, true, GSI_SAME_STMT);
 786         }
 787       else
 788         parts.base = parts.offset;
 789
 790       parts.offset = NULL_TREE;
 791
 792       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 793       if (mem_ref)
 794         return mem_ref;
 795     }
 796
 797   /* Verify that the address is in the simplest possible shape
 798      (only a register).  If we cannot create such a memory reference,
 799      something is really wrong.  */
 800   gcc_assert (parts.symbol == NULL_TREE);
 801   gcc_assert (parts.index == NULL_TREE);
 802   gcc_assert (!parts.step || integer_onep (parts.step));
 803   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 804   gcc_unreachable ();
 805 }
 806
 807 /* Copies components of the address from OP to ADDR.  */
 808
 809 void
 810 get_address_description (tree op, struct mem_address *addr)
 811 {
 812   addr->symbol = TMR_SYMBOL (op);
 813   addr->base = TMR_BASE (op);
 814   addr->index = TMR_INDEX (op);
 815   addr->step = TMR_STEP (op);
 816   addr->offset = TMR_OFFSET (op);
 817 }
 818
 819 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 820
 821 void
 822 copy_mem_ref_info (tree to, tree from)
 823 {
 824   /* And the info about the original reference.  */
 825   TREE_SIDE_EFFECTS (to) = TREE_SIDE_EFFECTS (from);
 826   TREE_THIS_VOLATILE (to) = TREE_THIS_VOLATILE (from);
 827 }
 828
 829 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 830    mem ref if anything changes, NULL_TREE otherwise.  */
 831
 832 tree
 833 maybe_fold_tmr (tree ref)
 834 {
 835   struct mem_address addr;
 836   bool changed = false;
 837   tree ret, off;
 838
 839   get_address_description (ref, &addr);
 840
 841   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
 842     {
 843       addr.offset = fold_binary_to_constant (PLUS_EXPR,
 844                                              TREE_TYPE (addr.offset),
 845                                              addr.offset, addr.base);
 846       addr.base = NULL_TREE;
 847       changed = true;
 848     }
 849
 850   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 851     {
 852       off = addr.index;
 853       if (addr.step)
 854         {
 855           off = fold_binary_to_constant (MULT_EXPR, sizetype,
 856                                          off, addr.step);
 857           addr.step = NULL_TREE;
 858         }
 859
 860       addr.offset = fold_binary_to_constant (PLUS_EXPR,
 861                                              TREE_TYPE (addr.offset),
 862                                              addr.offset, off);
 863       addr.index = NULL_TREE;
 864       changed = true;
 865     }
 866
 867   if (!changed)
 868     return NULL_TREE;
 869
 870   ret = create_mem_ref_raw (TREE_TYPE (ref), TREE_TYPE (addr.offset), &addr);
 871   if (!ret)
 872     return NULL_TREE;
 873
 874   copy_mem_ref_info (ret, ref);
 875   return ret;
 876 }
 877
 878 /* Dump PARTS to FILE.  */
 879
 880 extern void dump_mem_address (FILE *, struct mem_address *);
 881 void
 882 dump_mem_address (FILE *file, struct mem_address *parts)
 883 {
 884   if (parts->symbol)
 885     {
 886       fprintf (file, "symbol: ");
 887       print_generic_expr (file, parts->symbol, TDF_SLIM);
 888       fprintf (file, "\n");
 889     }
 890   if (parts->base)
 891     {
 892       fprintf (file, "base: ");
 893       print_generic_expr (file, parts->base, TDF_SLIM);
 894       fprintf (file, "\n");
 895     }
 896   if (parts->index)
 897     {
 898       fprintf (file, "index: ");
 899       print_generic_expr (file, parts->index, TDF_SLIM);
 900       fprintf (file, "\n");
 901     }
 902   if (parts->step)
 903     {
 904       fprintf (file, "step: ");
 905       print_generic_expr (file, parts->step, TDF_SLIM);
 906       fprintf (file, "\n");
 907     }
 908   if (parts->offset)
 909     {
 910       fprintf (file, "offset: ");
 911       print_generic_expr (file, parts->offset, TDF_SLIM);
 912       fprintf (file, "\n");
 913     }
 914 }
 915
 916 #include "gt-tree-ssa-address.h"