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