gcc/tree-ssa-address.c

   1 /* Memory address lowering and addressing mode selection.
   2    Copyright (C) 2004, 2006, 2007, 2008, 2009, 2010, 2011
   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 && base != const0_rtx)
 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   enum machine_mode pointer_mode = targetm.addr_space.pointer_mode (as);
 193   rtx address, sym, bse, idx, st, off;
 194   struct mem_addr_template *templ;
 195
 196   if (addr->step && !integer_onep (addr->step))
 197     st = immed_double_int_const (tree_to_double_int (addr->step), pointer_mode);
 198   else
 199     st = NULL_RTX;
 200
 201   if (addr->offset && !integer_zerop (addr->offset))
 202     off = immed_double_int_const
 203             (double_int_sext (tree_to_double_int (addr->offset),
 204                               TYPE_PRECISION (TREE_TYPE (addr->offset))),
 205              pointer_mode);
 206   else
 207     off = NULL_RTX;
 208
 209   if (!really_expand)
 210     {
 211       unsigned int templ_index
 212         = TEMPL_IDX (as, addr->symbol, addr->base, addr->index, st, off);
 213
 214       if (templ_index
 215           >= VEC_length (mem_addr_template, mem_addr_template_list))
 216         VEC_safe_grow_cleared (mem_addr_template, gc, mem_addr_template_list,
 217                                templ_index + 1);
 218
 219       /* Reuse the templates for addresses, so that we do not waste memory.  */
 220       templ = VEC_index (mem_addr_template, mem_addr_template_list, templ_index);
 221       if (!templ->ref)
 222         {
 223           sym = (addr->symbol ?
 224                  gen_rtx_SYMBOL_REF (pointer_mode, ggc_strdup ("test_symbol"))
 225                  : NULL_RTX);
 226           bse = (addr->base ?
 227                  gen_raw_REG (pointer_mode, LAST_VIRTUAL_REGISTER + 1)
 228                  : NULL_RTX);
 229           idx = (addr->index ?
 230                  gen_raw_REG (pointer_mode, LAST_VIRTUAL_REGISTER + 2)
 231                  : NULL_RTX);
 232
 233           gen_addr_rtx (pointer_mode, sym, bse, idx,
 234                         st? const0_rtx : NULL_RTX,
 235                         off? const0_rtx : NULL_RTX,
 236                         &templ->ref,
 237                         &templ->step_p,
 238                         &templ->off_p);
 239         }
 240
 241       if (st)
 242         *templ->step_p = st;
 243       if (off)
 244         *templ->off_p = off;
 245
 246       return templ->ref;
 247     }
 248
 249   /* Otherwise really expand the expressions.  */
 250   sym = (addr->symbol
 251          ? expand_expr (addr->symbol, NULL_RTX, pointer_mode, EXPAND_NORMAL)
 252          : NULL_RTX);
 253   bse = (addr->base
 254          ? expand_expr (addr->base, NULL_RTX, pointer_mode, EXPAND_NORMAL)
 255          : NULL_RTX);
 256   idx = (addr->index
 257          ? expand_expr (addr->index, NULL_RTX, pointer_mode, EXPAND_NORMAL)
 258          : NULL_RTX);
 259
 260   gen_addr_rtx (pointer_mode, sym, bse, idx, st, off, &address, NULL, NULL);
 261   if (pointer_mode != address_mode)
 262     address = convert_memory_address (address_mode, address);
 263   return address;
 264 }
 265
 266 /* Returns address of MEM_REF in TYPE.  */
 267
 268 tree
 269 tree_mem_ref_addr (tree type, tree mem_ref)
 270 {
 271   tree addr;
 272   tree act_elem;
 273   tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
 274   tree addr_base = NULL_TREE, addr_off = NULL_TREE;
 275
 276   addr_base = fold_convert (type, TMR_BASE (mem_ref));
 277
 278   act_elem = TMR_INDEX (mem_ref);
 279   if (act_elem)
 280     {
 281       if (step)
 282         act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
 283       addr_off = act_elem;
 284     }
 285
 286   act_elem = TMR_INDEX2 (mem_ref);
 287   if (act_elem)
 288     {
 289       if (addr_off)
 290         addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
 291       else
 292         addr_off = act_elem;
 293     }
 294
 295   if (offset && !integer_zerop (offset))
 296     {
 297       offset = fold_convert (sizetype, offset);
 298       if (addr_off)
 299         addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
 300       else
 301         addr_off = offset;
 302     }
 303
 304   if (addr_off)
 305     addr = fold_build_pointer_plus (addr_base, addr_off);
 306   else
 307     addr = addr_base;
 308
 309   return addr;
 310 }
 311
 312 /* Returns true if a memory reference in MODE and with parameters given by
 313    ADDR is valid on the current target.  */
 314
 315 static bool
 316 valid_mem_ref_p (enum machine_mode mode, addr_space_t as,
 317                  struct mem_address *addr)
 318 {
 319   rtx address;
 320
 321   address = addr_for_mem_ref (addr, as, false);
 322   if (!address)
 323     return false;
 324
 325   return memory_address_addr_space_p (mode, address, as);
 326 }
 327
 328 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
 329    is valid on the current target and if so, creates and returns the
 330    TARGET_MEM_REF.  If VERIFY is false omit the verification step.  */
 331
 332 static tree
 333 create_mem_ref_raw (tree type, tree alias_ptr_type, struct mem_address *addr,
 334                     bool verify)
 335 {
 336   tree base, index2;
 337
 338   if (verify
 339       && !valid_mem_ref_p (TYPE_MODE (type), TYPE_ADDR_SPACE (type), addr))
 340     return NULL_TREE;
 341
 342   if (addr->step && integer_onep (addr->step))
 343     addr->step = NULL_TREE;
 344
 345   if (addr->offset)
 346     addr->offset = fold_convert (alias_ptr_type, addr->offset);
 347   else
 348     addr->offset = build_int_cst (alias_ptr_type, 0);
 349
 350   if (addr->symbol)
 351     {
 352       base = addr->symbol;
 353       index2 = addr->base;
 354     }
 355   else if (addr->base
 356            && POINTER_TYPE_P (TREE_TYPE (addr->base)))
 357     {
 358       base = addr->base;
 359       index2 = NULL_TREE;
 360     }
 361   else
 362     {
 363       base = build_int_cst (ptr_type_node, 0);
 364       index2 = addr->base;
 365     }
 366
 367   /* If possible use a plain MEM_REF instead of a TARGET_MEM_REF.
 368      ???  As IVOPTs does not follow restrictions to where the base
 369      pointer may point to create a MEM_REF only if we know that
 370      base is valid.  */
 371   if ((TREE_CODE (base) == ADDR_EXPR || TREE_CODE (base) == INTEGER_CST)
 372       && (!index2 || integer_zerop (index2))
 373       && (!addr->index || integer_zerop (addr->index)))
 374     return fold_build2 (MEM_REF, type, base, addr->offset);
 375
 376   return build5 (TARGET_MEM_REF, type,
 377                  base, addr->offset, addr->index, addr->step, index2);
 378 }
 379
 380 /* Returns true if OBJ is an object whose address is a link time constant.  */
 381
 382 static bool
 383 fixed_address_object_p (tree obj)
 384 {
 385   return (TREE_CODE (obj) == VAR_DECL
 386           && (TREE_STATIC (obj)
 387               || DECL_EXTERNAL (obj))
 388           && ! DECL_DLLIMPORT_P (obj));
 389 }
 390
 391 /* If ADDR contains an address of object that is a link time constant,
 392    move it to PARTS->symbol.  */
 393
 394 static void
 395 move_fixed_address_to_symbol (struct mem_address *parts, aff_tree *addr)
 396 {
 397   unsigned i;
 398   tree val = NULL_TREE;
 399
 400   for (i = 0; i < addr->n; i++)
 401     {
 402       if (!double_int_one_p (addr->elts[i].coef))
 403         continue;
 404
 405       val = addr->elts[i].val;
 406       if (TREE_CODE (val) == ADDR_EXPR
 407           && fixed_address_object_p (TREE_OPERAND (val, 0)))
 408         break;
 409     }
 410
 411   if (i == addr->n)
 412     return;
 413
 414   parts->symbol = val;
 415   aff_combination_remove_elt (addr, i);
 416 }
 417
 418 /* If ADDR contains an instance of BASE_HINT, move it to PARTS->base.  */
 419
 420 static void
 421 move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
 422                    aff_tree *addr)
 423 {
 424   unsigned i;
 425   tree val = NULL_TREE;
 426   int qual;
 427
 428   for (i = 0; i < addr->n; i++)
 429     {
 430       if (!double_int_one_p (addr->elts[i].coef))
 431         continue;
 432
 433       val = addr->elts[i].val;
 434       if (operand_equal_p (val, base_hint, 0))
 435         break;
 436     }
 437
 438   if (i == addr->n)
 439     return;
 440
 441   /* Cast value to appropriate pointer type.  We cannot use a pointer
 442      to TYPE directly, as the back-end will assume registers of pointer
 443      type are aligned, and just the base itself may not actually be.
 444      We use void pointer to the type's address space instead.  */
 445   qual = ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (type));
 446   type = build_qualified_type (void_type_node, qual);
 447   parts->base = fold_convert (build_pointer_type (type), val);
 448   aff_combination_remove_elt (addr, i);
 449 }
 450
 451 /* If ADDR contains an address of a dereferenced pointer, move it to
 452    PARTS->base.  */
 453
 454 static void
 455 move_pointer_to_base (struct mem_address *parts, aff_tree *addr)
 456 {
 457   unsigned i;
 458   tree val = NULL_TREE;
 459
 460   for (i = 0; i < addr->n; i++)
 461     {
 462       if (!double_int_one_p (addr->elts[i].coef))
 463         continue;
 464
 465       val = addr->elts[i].val;
 466       if (POINTER_TYPE_P (TREE_TYPE (val)))
 467         break;
 468     }
 469
 470   if (i == addr->n)
 471     return;
 472
 473   parts->base = val;
 474   aff_combination_remove_elt (addr, i);
 475 }
 476
 477 /* Moves the loop variant part V in linear address ADDR to be the index
 478    of PARTS.  */
 479
 480 static void
 481 move_variant_to_index (struct mem_address *parts, aff_tree *addr, tree v)
 482 {
 483   unsigned i;
 484   tree val = NULL_TREE;
 485
 486   gcc_assert (!parts->index);
 487   for (i = 0; i < addr->n; i++)
 488     {
 489       val = addr->elts[i].val;
 490       if (operand_equal_p (val, v, 0))
 491         break;
 492     }
 493
 494   if (i == addr->n)
 495     return;
 496
 497   parts->index = fold_convert (sizetype, val);
 498   parts->step = double_int_to_tree (sizetype, addr->elts[i].coef);
 499   aff_combination_remove_elt (addr, i);
 500 }
 501
 502 /* Adds ELT to PARTS.  */
 503
 504 static void
 505 add_to_parts (struct mem_address *parts, tree elt)
 506 {
 507   tree type;
 508
 509   if (!parts->index)
 510     {
 511       parts->index = fold_convert (sizetype, elt);
 512       return;
 513     }
 514
 515   if (!parts->base)
 516     {
 517       parts->base = elt;
 518       return;
 519     }
 520
 521   /* Add ELT to base.  */
 522   type = TREE_TYPE (parts->base);
 523   if (POINTER_TYPE_P (type))
 524     parts->base = fold_build_pointer_plus (parts->base, 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_1 (gsi, parts->base,
 674                                             is_gimple_mem_ref_addr, 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   struct mem_address parts;
 694
 695   addr_to_parts (type, addr, iv_cand, base_hint, &parts, speed);
 696   gimplify_mem_ref_parts (gsi, &parts);
 697   mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
 698   if (mem_ref)
 699     return mem_ref;
 700
 701   /* The expression is too complicated.  Try making it simpler.  */
 702
 703   if (parts.step && !integer_onep (parts.step))
 704     {
 705       /* Move the multiplication to index.  */
 706       gcc_assert (parts.index);
 707       parts.index = force_gimple_operand_gsi (gsi,
 708                                 fold_build2 (MULT_EXPR, sizetype,
 709                                              parts.index, parts.step),
 710                                 true, NULL_TREE, true, GSI_SAME_STMT);
 711       parts.step = NULL_TREE;
 712
 713       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
 714       if (mem_ref)
 715         return mem_ref;
 716     }
 717
 718   if (parts.symbol)
 719     {
 720       tmp = parts.symbol;
 721       gcc_assert (is_gimple_val (tmp));
 722
 723       /* Add the symbol to base, eventually forcing it to register.  */
 724       if (parts.base)
 725         {
 726           gcc_assert (useless_type_conversion_p
 727                                 (sizetype, TREE_TYPE (parts.base)));
 728
 729           if (parts.index)
 730             {
 731               parts.base = force_gimple_operand_gsi_1 (gsi,
 732                         fold_build_pointer_plus (tmp, 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           parts.base = force_gimple_operand_gsi_1 (gsi,
 756                         fold_build_pointer_plus (parts.base, parts.index),
 757                         is_gimple_mem_ref_addr, NULL_TREE, true, GSI_SAME_STMT);
 758         }
 759       else
 760         parts.base = parts.index;
 761       parts.index = NULL_TREE;
 762
 763       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
 764       if (mem_ref)
 765         return mem_ref;
 766     }
 767
 768   if (parts.offset && !integer_zerop (parts.offset))
 769     {
 770       /* Try adding offset to base.  */
 771       if (parts.base)
 772         {
 773           parts.base = force_gimple_operand_gsi_1 (gsi,
 774                         fold_build_pointer_plus (parts.base, parts.offset),
 775                         is_gimple_mem_ref_addr, NULL_TREE, true, GSI_SAME_STMT);
 776         }
 777       else
 778         parts.base = parts.offset;
 779
 780       parts.offset = NULL_TREE;
 781
 782       mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
 783       if (mem_ref)
 784         return mem_ref;
 785     }
 786
 787   /* Verify that the address is in the simplest possible shape
 788      (only a register).  If we cannot create such a memory reference,
 789      something is really wrong.  */
 790   gcc_assert (parts.symbol == NULL_TREE);
 791   gcc_assert (parts.index == NULL_TREE);
 792   gcc_assert (!parts.step || integer_onep (parts.step));
 793   gcc_assert (!parts.offset || integer_zerop (parts.offset));
 794   gcc_unreachable ();
 795 }
 796
 797 /* Copies components of the address from OP to ADDR.  */
 798
 799 void
 800 get_address_description (tree op, struct mem_address *addr)
 801 {
 802   if (TREE_CODE (TMR_BASE (op)) == ADDR_EXPR)
 803     {
 804       addr->symbol = TMR_BASE (op);
 805       addr->base = TMR_INDEX2 (op);
 806     }
 807   else
 808     {
 809       addr->symbol = NULL_TREE;
 810       if (TMR_INDEX2 (op))
 811         {
 812           gcc_assert (integer_zerop (TMR_BASE (op)));
 813           addr->base = TMR_INDEX2 (op);
 814         }
 815       else
 816         addr->base = TMR_BASE (op);
 817     }
 818   addr->index = TMR_INDEX (op);
 819   addr->step = TMR_STEP (op);
 820   addr->offset = TMR_OFFSET (op);
 821 }
 822
 823 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
 824
 825 void
 826 copy_mem_ref_info (tree to, tree from)
 827 {
 828   /* And the info about the original reference.  */
 829   TREE_SIDE_EFFECTS (to) = TREE_SIDE_EFFECTS (from);
 830   TREE_THIS_VOLATILE (to) = TREE_THIS_VOLATILE (from);
 831 }
 832
 833 /* Move constants in target_mem_ref REF to offset.  Returns the new target
 834    mem ref if anything changes, NULL_TREE otherwise.  */
 835
 836 tree
 837 maybe_fold_tmr (tree ref)
 838 {
 839   struct mem_address addr;
 840   bool changed = false;
 841   tree ret, off;
 842
 843   get_address_description (ref, &addr);
 844
 845   if (addr.base
 846       && TREE_CODE (addr.base) == INTEGER_CST
 847       && !integer_zerop (addr.base))
 848     {
 849       addr.offset = fold_binary_to_constant (PLUS_EXPR,
 850                                              TREE_TYPE (addr.offset),
 851                                              addr.offset, addr.base);
 852       addr.base = NULL_TREE;
 853       changed = true;
 854     }
 855
 856   if (addr.symbol
 857       && TREE_CODE (TREE_OPERAND (addr.symbol, 0)) == MEM_REF)
 858     {
 859       addr.offset = fold_binary_to_constant
 860                         (PLUS_EXPR, TREE_TYPE (addr.offset),
 861                          addr.offset,
 862                          TREE_OPERAND (TREE_OPERAND (addr.symbol, 0), 1));
 863       addr.symbol = TREE_OPERAND (TREE_OPERAND (addr.symbol, 0), 0);
 864       changed = true;
 865     }
 866   else if (addr.symbol
 867            && handled_component_p (TREE_OPERAND (addr.symbol, 0)))
 868     {
 869       HOST_WIDE_INT offset;
 870       addr.symbol = build_fold_addr_expr
 871                       (get_addr_base_and_unit_offset
 872                          (TREE_OPERAND (addr.symbol, 0), &offset));
 873       addr.offset = int_const_binop (PLUS_EXPR,
 874                                      addr.offset, size_int (offset));
 875       changed = true;
 876     }
 877
 878   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
 879     {
 880       off = addr.index;
 881       if (addr.step)
 882         {
 883           off = fold_binary_to_constant (MULT_EXPR, sizetype,
 884                                          off, addr.step);
 885           addr.step = NULL_TREE;
 886         }
 887
 888       addr.offset = fold_binary_to_constant (PLUS_EXPR,
 889                                              TREE_TYPE (addr.offset),
 890                                              addr.offset, off);
 891       addr.index = NULL_TREE;
 892       changed = true;
 893     }
 894
 895   if (!changed)
 896     return NULL_TREE;
 897
 898   /* If we have propagated something into this TARGET_MEM_REF and thus
 899      ended up folding it, always create a new TARGET_MEM_REF regardless
 900      if it is valid in this for on the target - the propagation result
 901      wouldn't be anyway.  */
 902   ret = create_mem_ref_raw (TREE_TYPE (ref),
 903                             TREE_TYPE (addr.offset), &addr, false);
 904   copy_mem_ref_info (ret, ref);
 905   return ret;
 906 }
 907
 908 /* Dump PARTS to FILE.  */
 909
 910 extern void dump_mem_address (FILE *, struct mem_address *);
 911 void
 912 dump_mem_address (FILE *file, struct mem_address *parts)
 913 {
 914   if (parts->symbol)
 915     {
 916       fprintf (file, "symbol: ");
 917       print_generic_expr (file, TREE_OPERAND (parts->symbol, 0), TDF_SLIM);
 918       fprintf (file, "\n");
 919     }
 920   if (parts->base)
 921     {
 922       fprintf (file, "base: ");
 923       print_generic_expr (file, parts->base, TDF_SLIM);
 924       fprintf (file, "\n");
 925     }
 926   if (parts->index)
 927     {
 928       fprintf (file, "index: ");
 929       print_generic_expr (file, parts->index, TDF_SLIM);
 930       fprintf (file, "\n");
 931     }
 932   if (parts->step)
 933     {
 934       fprintf (file, "step: ");
 935       print_generic_expr (file, parts->step, TDF_SLIM);
 936       fprintf (file, "\n");
 937     }
 938   if (parts->offset)
 939     {
 940       fprintf (file, "offset: ");
 941       print_generic_expr (file, parts->offset, TDF_SLIM);
 942       fprintf (file, "\n");
 943     }
 944 }
 945
 946 #include "gt-tree-ssa-address.h"