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 (tree_to_double_int (addr->offset), address_mode);
 202   else
 203     off = NULL_RTX;
 204
 205   if (!really_expand)
 206     {
 207       unsigned int templ_index
 208         = TEMPL_IDX (as, addr->symbol, addr->base, addr->index, st, off);
 209
 210       if (templ_index
 211           >= VEC_length (mem_addr_template, mem_addr_template_list))
 212         VEC_safe_grow_cleared (mem_addr_template, gc, mem_addr_template_list,
 213                                templ_index + 1);
 214
 215       /* Reuse the templates for addresses, so that we do not waste memory.  */
 216       templ = VEC_index (mem_addr_template, mem_addr_template_list, templ_index);
 217       if (!templ->ref)
 218         {
 219           sym = (addr->symbol ?
 220                  gen_rtx_SYMBOL_REF (address_mode, ggc_strdup ("test_symbol"))
 221                  : NULL_RTX);
 222           bse = (addr->base ?
 223                  gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1)
 224                  : NULL_RTX);
 225           idx = (addr->index ?
 226                  gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2)
 227                  : NULL_RTX);
 228
 229           gen_addr_rtx (address_mode, sym, bse, idx,
 230                         st? const0_rtx : NULL_RTX,
 231                         off? const0_rtx : NULL_RTX,
 232                         &templ->ref,
 233                         &templ->step_p,
 234                         &templ->off_p);
 235         }
 236
 237       if (st)
 238         *templ->step_p = st;
 239       if (off)
 240         *templ->off_p = off;
 241
 242       return templ->ref;
 243     }
 244
 245   /* Otherwise really expand the expressions.  */
 246   sym = (addr->symbol
 247          ? expand_expr (build_addr (addr->symbol, current_function_decl),
 248                         NULL_RTX, address_mode, EXPAND_NORMAL)
 249          : NULL_RTX);
 250   bse = (addr->base
 251          ? expand_expr (addr->base, NULL_RTX, address_mode, EXPAND_NORMAL)
 252          : NULL_RTX);
 253   idx = (addr->index
 254          ? expand_expr (addr->index, NULL_RTX, address_mode, EXPAND_NORMAL)
 255          : NULL_RTX);
 256
 257   gen_addr_rtx (address_mode, sym, bse, idx, st, off, &address, NULL, NULL);
 258   return address;
 259 }
 260
 261 /* Returns address of MEM_REF in TYPE.  */
 262
 263 tree
 264 tree_mem_ref_addr (tree type, tree mem_ref)
 265 {
 266   tree addr;
 267   tree act_elem;
 268   tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
 269   tree sym = TMR_SYMBOL (mem_ref), base = TMR_BASE (mem_ref);
 270   tree addr_base = NULL_TREE, addr_off = NULL_TREE;
 271
 272   if (sym)
 273     addr_base = fold_convert (type, build_addr (sym, current_function_decl));
 274   else if (base && POINTER_TYPE_P (TREE_TYPE (base)))
 275     {
 276       addr_base = fold_convert (type, base);
 277       base = NULL_TREE;
 278     }
 279
 280   act_elem = TMR_INDEX (mem_ref);
 281   if (act_elem)
 282     {
 283       if (step)
 284         act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
 285       addr_off = act_elem;
 286     }
 287
 288   act_elem = base;
 289   if (act_elem)
 290     {
 291       if (addr_off)
 292         addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
 293       else
 294         addr_off = act_elem;
 295     }
 296
 297   if (offset && !integer_zerop (offset))
 298     {
 299       if (addr_off)
 300         addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
 301       else
 302         addr_off = offset;
 303     }
 304
 305   if (addr_off)
 306     {
 307       if (addr_base)
 308         addr = fold_build2 (POINTER_PLUS_EXPR, type, addr_base, addr_off);
 309       else
 310         addr = fold_convert (type, addr_off);
 311     }
 312   else if (addr_base)
 313     addr = addr_base;
 314   else
 315     addr = build_int_cst (type, 0);
 316
 317   return addr;
 318 }
 319
 320 /* Returns true if a memory reference in MODE and with parameters given by
 321    ADDR is valid on the current target.  */
 322
 323 static bool
 324 valid_mem_ref_p (enum machine_mode mode, addr_space_t as,
 325                  struct mem_address *addr)
 326 {
 327   rtx address;
 328
 329   address = addr_for_mem_ref (addr, as, false);
 330   if (!address)
 331     return false;
 332
 333   return memory_address_addr_space_p (mode, address, as);
 334 }
 335
 336 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
 337    is valid on the current target and if so, creates and returns the
 338    TARGET_MEM_REF.  */
 339
 340 static tree
 341 create_mem_ref_raw (tree type, tree alias_ptr_type, struct mem_address *addr)
 342 {
 343   if (!valid_mem_ref_p (TYPE_MODE (type), TYPE_ADDR_SPACE (type), addr))
 344     return NULL_TREE;
 345
 346   if (addr->step && integer_onep (addr->step))
 347     addr->step = NULL_TREE;
 348
 349   if (addr->offset && integer_zerop (addr->offset))
 350     addr->offset = NULL_TREE;
 351
 352   /* If possible use a plain MEM_REF instead of a TARGET_MEM_REF.  */
 353   if (alias_ptr_type
 354       && !addr->index
 355       && !addr->step
 356       && (!addr->base || POINTER_TYPE_P (TREE_TYPE (addr->base))))
 357     {
 358       tree base, offset;
 359       gcc_assert (!addr->symbol ^ !addr->base);
 360       if (addr->symbol)
 361         base = build_fold_addr_expr (addr->symbol);
 362       else
 363         base = addr->base;
 364       if (addr->offset)
 365         offset = fold_convert (alias_ptr_type, addr->offset);
 366       else
 367         offset = build_int_cst (alias_ptr_type, 0);
 368       return fold_build2 (MEM_REF, type, base, offset);
 369     }
 370
 371   return build6 (TARGET_MEM_REF, type,
 372                  addr->symbol, addr->base, addr->index,
 373                  addr->step, addr->offset, NULL);
 374 }
 375
 376 /* Returns true if OBJ is an object whose address is a link time constant.  */
 377
 378 static bool
 379 fixed_address_object_p (tree obj)
 380 {
 381   return (TREE_CODE (obj) == VAR_DECL
 382           && (TREE_STATIC (obj)
 383               || DECL_EXTERNAL (obj))
 384           && ! DECL_DLLIMPORT_P (obj));
 385 }
 386
 387 /* If ADDR contains an address of object that is a link time constant,
 388    move it to PARTS->symbol.  */
 389
 390 static void
 391 move_fixed_address_to_symbol (struct mem_address *parts, aff_tree *addr)
 392 {
 393   unsigned i;
 394   tree val = NULL_TREE;
 395
 396   for (i = 0; i < addr->n; i++)
 397     {
 398       if (!double_int_one_p (addr->elts[i].coef))
 399         continue;
 400
 401       val = addr->elts[i].val;
 402       if (TREE_CODE (val) == ADDR_EXPR
 403           && fixed_address_object_p (TREE_OPERAND (val, 0)))
 404         break;
 405     }
 406
 407   if (i == addr->n)
 408     return;
 409
 410   parts->symbol = TREE_OPERAND (val, 0);
 411   aff_combination_remove_elt (addr, i);
 412 }
 413
 414 /* If ADDR contains an instance of BASE_HINT, move it to PARTS->base.  */
 415
 416 static void
 417 move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
 418                    aff_tree *addr)
 419 {
 420   unsigned i;
 421   tree val = NULL_TREE;
 422   int qual;
 423
 424   for (i = 0; i < addr->n; i++)
 425     {
 426       if (!double_int_one_p (addr->elts[i].coef))
 427         continue;
 428
 429       val = addr->elts[i].val;
 430       if (operand_equal_p (val, base_hint, 0))
 431         break;
 432     }
 433
 434   if (i == addr->n)
 435     return;
 436
 437   /* Cast value to appropriate pointer type.  We cannot use a pointer
 438      to TYPE directly, as the back-end will assume registers of pointer
 439      type are aligned, and just the base itself may not actually be.
 440      We use void pointer to the type's address space instead.  */
 441   qual = ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (type));
 442   type = build_qualified_type (void_type_node, qual);
 443   parts->base = fold_convert (build_pointer_type (type), val);
 444   aff_combination_remove_elt (addr, i);
 445 }
 446
 447 /* If ADDR contains an address of a dereferenced pointer, move it to
 448    PARTS->base.  */
 449
 450 static void
 451 move_pointer_to_base (struct mem_address *parts, aff_tree *addr)
 452 {
 453   unsigned i;
 454   tree val = NULL_TREE;
 455
 456   for (i = 0; i < addr->n; i++)
 457     {
 458       if (!double_int_one_p (addr->elts[i].coef))
 459         continue;
 460
 461       val = addr->elts[i].val;
 462       if (POINTER_TYPE_P (TREE_TYPE (val)))
 463         break;
 464     }
 465
 466   if (i == addr->n)
 467     return;
 468
 469   parts->base = val;
 470   aff_combination_remove_elt (addr, i);
 471 }
 472
 473 /* Moves the loop variant part V in linear address ADDR to be the index
 474    of PARTS.  */
 475
 476 static void
 477 move_variant_to_index (struct mem_address *parts, aff_tree *addr, tree v)
 478 {
 479   unsigned i;
 480   tree val = NULL_TREE;
 481
 482   gcc_assert (!parts->index);
 483   for (i = 0; i < addr->n; i++)
 484     {
 485       val = addr->elts[i].val;
 486       if (operand_equal_p (val, v, 0))
 487         break;
 488     }
 489
 490   if (i == addr->n)
 491     return;
 492
 493   parts->index = fold_convert (sizetype, val);
 494   parts->step = double_int_to_tree (sizetype, addr->elts[i].coef);
 495   aff_combination_remove_elt (addr, i);
 496 }
 497
 498 /* Adds ELT to PARTS.  */
 499
 500 static void
 501 add_to_parts (struct mem_address *parts, tree elt)
 502 {
 503   tree type;
 504
 505   if (!parts->index)
 506     {
 507       parts->index = fold_convert (sizetype, elt);
 508       return;
 509     }
 510
 511   if (!parts->base)
 512     {
 513       parts->base = elt;
 514       return;
 515     }
 516
 517   /* Add ELT to base.  */
 518   type = TREE_TYPE (parts->base);
 519   if (POINTER_TYPE_P (type))
 520     parts->base = fold_build2 (POINTER_PLUS_EXPR, type,
 521                                parts->base,
 522                                fold_convert (sizetype, elt));
 523   else
 524     parts->base = fold_build2 (PLUS_EXPR, type,
 525                                parts->base, elt);
 526 }
 527
 528 /* Finds the most expensive multiplication in ADDR that can be
 529    expressed in an addressing mode and move the corresponding
 530    element(s) to PARTS.  */
 531
 532 static void
 533 most_expensive_mult_to_index (tree type, struct mem_address *parts,
 534                               aff_tree *addr, bool speed)
 535 {
 536   addr_space_t as = TYPE_ADDR_SPACE (type);
 537   enum machine_mode address_mode = targetm.addr_space.address_mode (as);
 538   HOST_WIDE_INT coef;
 539   double_int best_mult, amult, amult_neg;
 540   unsigned best_mult_cost = 0, acost;
 541   tree mult_elt = NULL_TREE, elt;
 542   unsigned i, j;
 543   enum tree_code op_code;
 544
 545   best_mult = double_int_zero;
 546   for (i = 0; i < addr->n; i++)
 547     {
 548       if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
 549         continue;
 550
 551       coef = double_int_to_shwi (addr->elts[i].coef);
 552       if (coef == 1
 553           || !multiplier_allowed_in_address_p (coef, TYPE_MODE (type), as))
 554         continue;
 555
 556       acost = multiply_by_cost (coef, address_mode, speed);
 557
 558       if (acost > best_mult_cost)
 559         {
 560           best_mult_cost = acost;
 561           best_mult = addr->elts[i].coef;
 562         }
 563     }
 564
 565   if (!best_mult_cost)
 566     return;
 567
 568   /* Collect elements multiplied by best_mult.  */
 569   for (i = j = 0; i < addr->n; i++)
 570     {
 571       amult = addr->elts[i].coef;
 572       amult_neg = double_int_ext_for_comb (double_int_neg (amult), addr);
 573
 574       if (double_int_equal_p (amult, best_mult))
 575         op_code = PLUS_EXPR;
 576       else if (double_int_equal_p (amult_neg, best_mult))
 577         op_code = MINUS_EXPR;
 578       else
 579         {
 580           addr->elts[j] = addr->elts[i];
 581           j++;
 582           continue;
 583         }
 584
 585       elt = fold_convert (sizetype, addr->elts[i].val);
 586       if (mult_elt)
 587         mult_elt = fold_build2 (op_code, sizetype, mult_elt, elt);
 588       else if (op_code == PLUS_EXPR)
 589         mult_elt = elt;
 590       else
 591         mult_elt = fold_build1 (NEGATE_EXPR, sizetype, elt);
 592     }
 593   addr->n = j;
 594
 595   parts->index = mult_elt;
 596   parts->step = double_int_to_tree (sizetype, best_mult);
 597 }
 598
 599 /* Splits address ADDR for a memory access of type TYPE into PARTS.
 600    If BASE_HINT is non-NULL, it specifies an SSA name to be used
 601    preferentially as base of the reference, and IV_CAND is the selected
 602    iv candidate used in ADDR.
 603
 604    TODO -- be more clever about the distribution of the elements of ADDR
 605    to PARTS.  Some architectures do not support anything but single
 606    register in address, possibly with a small integer offset; while
 607    create_mem_ref will simplify the address to an acceptable shape
 608    later, it would be more efficient to know that asking for complicated
 609    addressing modes is useless.  */
 610
 611 static void
 612 addr_to_parts (tree type, aff_tree *addr, tree iv_cand,
 613                tree base_hint, struct mem_address *parts,
 614                bool speed)
 615 {
 616   tree part;
 617   unsigned i;
 618
 619   parts->symbol = NULL_TREE;
 620   parts->base = NULL_TREE;
 621   parts->index = NULL_TREE;
 622   parts->step = NULL_TREE;
 623
 624   if (!double_int_zero_p (addr->offset))
 625     parts->offset = double_int_to_tree (sizetype, addr->offset);
 626   else
 627     parts->offset = NULL_TREE;
 628
 629   /* Try to find a symbol.  */
 630   move_fixed_address_to_symbol (parts, addr);
 631
 632   /* No need to do address parts reassociation if the number of parts
 633      is <= 2 -- in that case, no loop invariant code motion can be
 634      exposed.  */
 635
 636   if (!base_hint && (addr->n > 2))
 637     move_variant_to_index (parts, addr, iv_cand);
 638
 639   /* First move the most expensive feasible multiplication
 640      to index.  */
 641   if (!parts->index)
 642     most_expensive_mult_to_index (type, parts, addr, speed);
 643
 644   /* Try to find a base of the reference.  Since at the moment
 645      there is no reliable way how to distinguish between pointer and its
 646      offset, this is just a guess.  */
 647   if (!parts->symbol && base_hint)
 648     move_hint_to_base (type, parts, base_hint, addr);
 649   if (!parts->symbol && !parts->base)
 650     move_pointer_to_base (parts, addr);
 651
 652   /* Then try to process the remaining elements.  */
 653   for (i = 0; i < addr->n; i++)
 654     {
 655       part = fold_convert (sizetype, addr->elts[i].val);
 656       if (!double_int_one_p (addr->elts[i].coef))
 657         part = fold_build2 (MULT_EXPR, sizetype, part,
 658                             double_int_to_tree (sizetype, addr->elts[i].coef));
 659       add_to_parts (parts, part);
 660     }
 661   if (addr->rest)
 662     add_to_parts (parts, fold_convert (sizetype, addr->rest));
 663 }
 664
 665 /* Force the PARTS to register.  */
 666
 667 static void
 668 gimplify_mem_ref_parts (gimple_stmt_iterator *gsi, struct mem_address *parts)
 669 {
 670   if (parts->base)
 671     parts->base = force_gimple_operand_gsi (gsi, parts->base,
 672                                             true, NULL_TREE,
 673                                             true, GSI_SAME_STMT);
 674   if (parts->index)
 675     parts->index = force_gimple_operand_gsi (gsi, parts->index,
 676                                              true, NULL_TREE,
 677                                              true, GSI_SAME_STMT);
 678 }
 679
 680 /* Creates and returns a TARGET_MEM_REF for address ADDR.  If necessary
 681    computations are emitted in front of GSI.  TYPE is the mode
 682    of created memory reference. IV_CAND is the selected iv candidate in ADDR,
 683    and BASE_HINT is non NULL if IV_CAND comes from a base address
 684    object.  */
 685
 686 tree
 687 create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
 688                 tree alias_ptr_type, tree iv_cand, tree base_hint, bool speed)
 689 {
 690   tree mem_ref, tmp;
 691   tree atype;
 692   struct mem_address parts;
 693
 694   addr_to_parts (type, addr, iv_cand, base_hint, &parts, speed);
 695   gimplify_mem_ref_parts (gsi, &parts);
 696   mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 697   if (mem_ref)
 698     return mem_ref;
 699
 700   /* The expression is too complicated.  Try making it simpler.  */
 701
 702   if (parts.step && !integer_onep (parts.step))
 703     {
 704       /* Move the multiplication to index.  */
 705       gcc_assert (parts.index);
 706       parts.index = force_gimple_operand_gsi (gsi,
 707                                 fold_build2 (MULT_EXPR, sizetype,
 708                                              parts.index, parts.step),
 709                                 true, NULL_TREE, true, GSI_SAME_STMT);
 710       parts.step = NULL_TREE;
 711
 712       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 713       if (mem_ref)
 714         return mem_ref;
 715     }
 716
 717   if (parts.symbol)
 718     {
 719       tmp = build_addr (parts.symbol, current_function_decl);
 720       gcc_assert (is_gimple_val (tmp));
 721
 722       /* Add the symbol to base, eventually forcing it to register.  */
 723       if (parts.base)
 724         {
 725           gcc_assert (useless_type_conversion_p
 726                                 (sizetype, TREE_TYPE (parts.base)));
 727
 728           if (parts.index)
 729             {
 730               atype = TREE_TYPE (tmp);
 731               parts.base = force_gimple_operand_gsi (gsi,
 732                         fold_build2 (POINTER_PLUS_EXPR, atype,
 733                                      tmp,
 734                                      fold_convert (sizetype, parts.base)),
 735                         true, NULL_TREE, true, GSI_SAME_STMT);
 736             }
 737           else
 738             {
 739               parts.index = parts.base;
 740               parts.base = tmp;
 741             }
 742         }
 743       else
 744         parts.base = tmp;
 745       parts.symbol = NULL_TREE;
 746
 747       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 748       if (mem_ref)
 749         return mem_ref;
 750     }
 751
 752   if (parts.index)
 753     {
 754       /* Add index to base.  */
 755       if (parts.base)
 756         {
 757           atype = TREE_TYPE (parts.base);
 758           parts.base = force_gimple_operand_gsi (gsi,
 759                         fold_build2 (POINTER_PLUS_EXPR, atype,
 760                                      parts.base,
 761                                      parts.index),
 762                         true, NULL_TREE, true, GSI_SAME_STMT);
 763         }
 764       else
 765         parts.base = parts.index;
 766       parts.index = NULL_TREE;
 767
 768       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 769       if (mem_ref)
 770         return mem_ref;
 771     }
 772
 773   if (parts.offset && !integer_zerop (parts.offset))
 774     {
 775       /* Try adding offset to base.  */
 776       if (parts.base)
 777         {
 778           atype = TREE_TYPE (parts.base);
 779           parts.base = force_gimple_operand_gsi (gsi,
 780                         fold_build2 (POINTER_PLUS_EXPR, atype,
 781                                      parts.base,
 782                                      fold_convert (sizetype, parts.offset)),
 783                         true, NULL_TREE, true, GSI_SAME_STMT);
 784         }
 785       else
 786         parts.base = parts.offset;
 787
 788       parts.offset = NULL_TREE;
 789
 790       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts);
 791       if (mem_ref)
 792         return mem_ref;
 793     }
 794
 795   /* Verify that the address is in the simplest possible shape
 796      (only a register).  If we cannot create such a memory reference,
 797      something is really wrong.  */
 798   gcc_assert (parts.symbol == NULL_TREE);
 799   gcc_assert (parts.index == NULL_TREE);
 800   gcc_assert (!parts.step || integer_onep (parts.step));
 801   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 802   gcc_unreachable ();
 803 }
 804
 805 /* Copies components of the address from OP to ADDR.  */
 806
 807 void
 808 get_address_description (tree op, struct mem_address *addr)
 809 {
 810   addr->symbol = TMR_SYMBOL (op);
 811   addr->base = TMR_BASE (op);
 812   addr->index = TMR_INDEX (op);
 813   addr->step = TMR_STEP (op);
 814   addr->offset = TMR_OFFSET (op);
 815 }
 816
 817 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 818
 819 void
 820 copy_mem_ref_info (tree to, tree from)
 821 {
 822   /* And the info about the original reference.  */
 823   TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
 824   TREE_SIDE_EFFECTS (to) = TREE_SIDE_EFFECTS (from);
 825   TREE_THIS_VOLATILE (to) = TREE_THIS_VOLATILE (from);
 826 }
 827
 828 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 829    mem ref if anything changes, NULL_TREE otherwise.  */
 830
 831 tree
 832 maybe_fold_tmr (tree ref)
 833 {
 834   struct mem_address addr;
 835   bool changed = false;
 836   tree ret, off;
 837
 838   get_address_description (ref, &addr);
 839
 840   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
 841     {
 842       if (addr.offset)
 843         addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
 844                         addr.offset,
 845                         fold_convert (sizetype, addr.base));
 846       else
 847         addr.offset = addr.base;
 848
 849       addr.base = NULL_TREE;
 850       changed = true;
 851     }
 852
 853   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 854     {
 855       off = addr.index;
 856       if (addr.step)
 857         {
 858           off = fold_binary_to_constant (MULT_EXPR, sizetype,
 859                                          off, addr.step);
 860           addr.step = NULL_TREE;
 861         }
 862
 863       if (addr.offset)
 864         {
 865           addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
 866                                                  addr.offset, off);
 867         }
 868       else
 869         addr.offset = off;
 870
 871       addr.index = NULL_TREE;
 872       changed = true;
 873     }
 874
 875   if (!changed)
 876     return NULL_TREE;
 877
 878   ret = create_mem_ref_raw (TREE_TYPE (ref), NULL_TREE, &addr);
 879   if (!ret)
 880     return NULL_TREE;
 881
 882   copy_mem_ref_info (ret, ref);
 883   return ret;
 884 }
 885
 886 /* Dump PARTS to FILE.  */
 887
 888 extern void dump_mem_address (FILE *, struct mem_address *);
 889 void
 890 dump_mem_address (FILE *file, struct mem_address *parts)
 891 {
 892   if (parts->symbol)
 893     {
 894       fprintf (file, "symbol: ");
 895       print_generic_expr (file, parts->symbol, TDF_SLIM);
 896       fprintf (file, "\n");
 897     }
 898   if (parts->base)
 899     {
 900       fprintf (file, "base: ");
 901       print_generic_expr (file, parts->base, TDF_SLIM);
 902       fprintf (file, "\n");
 903     }
 904   if (parts->index)
 905     {
 906       fprintf (file, "index: ");
 907       print_generic_expr (file, parts->index, TDF_SLIM);
 908       fprintf (file, "\n");
 909     }
 910   if (parts->step)
 911     {
 912       fprintf (file, "step: ");
 913       print_generic_expr (file, parts->step, TDF_SLIM);
 914       fprintf (file, "\n");
 915     }
 916   if (parts->offset)
 917     {
 918       fprintf (file, "offset: ");
 919       print_generic_expr (file, parts->offset, TDF_SLIM);
 920       fprintf (file, "\n");
 921     }
 922 }
 923
 924 #include "gt-tree-ssa-address.h"