[gcc/testsuite]
[official-gcc.git] / gcc / tree-ssa-address.c
blob5e354a17ce97c7a8edf30aea77a83a0845bf8409
1 /* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
21 that directly map to addressing modes of the target. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "backend.h"
27 #include "target.h"
28 #include "rtl.h"
29 #include "tree.h"
30 #include "gimple.h"
31 #include "memmodel.h"
32 #include "stringpool.h"
33 #include "tree-vrp.h"
34 #include "tree-ssanames.h"
35 #include "expmed.h"
36 #include "insn-config.h"
37 #include "emit-rtl.h"
38 #include "recog.h"
39 #include "tree-pretty-print.h"
40 #include "fold-const.h"
41 #include "stor-layout.h"
42 #include "gimple-iterator.h"
43 #include "gimplify-me.h"
44 #include "tree-ssa-loop-ivopts.h"
45 #include "expr.h"
46 #include "tree-dfa.h"
47 #include "dumpfile.h"
48 #include "tree-affine.h"
49 #include "gimplify.h"
51 /* FIXME: We compute address costs using RTL. */
52 #include "tree-ssa-address.h"
54 /* TODO -- handling of symbols (according to Richard Hendersons
55 comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
57 There are at least 5 different kinds of symbols that we can run up against:
59 (1) binds_local_p, small data area.
60 (2) binds_local_p, eg local statics
61 (3) !binds_local_p, eg global variables
62 (4) thread local, local_exec
63 (5) thread local, !local_exec
65 Now, (1) won't appear often in an array context, but it certainly can.
66 All you have to do is set -GN high enough, or explicitly mark any
67 random object __attribute__((section (".sdata"))).
69 All of these affect whether or not a symbol is in fact a valid address.
70 The only one tested here is (3). And that result may very well
71 be incorrect for (4) or (5).
73 An incorrect result here does not cause incorrect results out the
74 back end, because the expander in expr.c validizes the address. However
75 it would be nice to improve the handling here in order to produce more
76 precise results. */
78 /* A "template" for memory address, used to determine whether the address is
79 valid for mode. */
81 struct GTY (()) mem_addr_template {
82 rtx ref; /* The template. */
83 rtx * GTY ((skip)) step_p; /* The point in template where the step should be
84 filled in. */
85 rtx * GTY ((skip)) off_p; /* The point in template where the offset should
86 be filled in. */
90 /* The templates. Each of the low five bits of the index corresponds to one
91 component of TARGET_MEM_REF being present, while the high bits identify
92 the address space. See TEMPL_IDX. */
94 static GTY(()) vec<mem_addr_template, va_gc> *mem_addr_template_list;
96 #define TEMPL_IDX(AS, SYMBOL, BASE, INDEX, STEP, OFFSET) \
97 (((int) (AS) << 5) \
98 | ((SYMBOL != 0) << 4) \
99 | ((BASE != 0) << 3) \
100 | ((INDEX != 0) << 2) \
101 | ((STEP != 0) << 1) \
102 | (OFFSET != 0))
104 /* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
105 STEP and OFFSET to *ADDR using address mode ADDRESS_MODE. Stores pointers
106 to where step is placed to *STEP_P and offset to *OFFSET_P. */
108 static void
109 gen_addr_rtx (machine_mode address_mode,
110 rtx symbol, rtx base, rtx index, rtx step, rtx offset,
111 rtx *addr, rtx **step_p, rtx **offset_p)
113 rtx act_elem;
115 *addr = NULL_RTX;
116 if (step_p)
117 *step_p = NULL;
118 if (offset_p)
119 *offset_p = NULL;
121 if (index && index != const0_rtx)
123 act_elem = index;
124 if (step)
126 act_elem = gen_rtx_MULT (address_mode, act_elem, step);
128 if (step_p)
129 *step_p = &XEXP (act_elem, 1);
132 *addr = act_elem;
135 if (base && base != const0_rtx)
137 if (*addr)
138 *addr = simplify_gen_binary (PLUS, address_mode, base, *addr);
139 else
140 *addr = base;
143 if (symbol)
145 act_elem = symbol;
146 if (offset)
148 act_elem = gen_rtx_PLUS (address_mode, act_elem, offset);
150 if (offset_p)
151 *offset_p = &XEXP (act_elem, 1);
153 if (GET_CODE (symbol) == SYMBOL_REF
154 || GET_CODE (symbol) == LABEL_REF
155 || GET_CODE (symbol) == CONST)
156 act_elem = gen_rtx_CONST (address_mode, act_elem);
159 if (*addr)
160 *addr = gen_rtx_PLUS (address_mode, *addr, act_elem);
161 else
162 *addr = act_elem;
164 else if (offset)
166 if (*addr)
168 *addr = gen_rtx_PLUS (address_mode, *addr, offset);
169 if (offset_p)
170 *offset_p = &XEXP (*addr, 1);
172 else
174 *addr = offset;
175 if (offset_p)
176 *offset_p = addr;
180 if (!*addr)
181 *addr = const0_rtx;
184 /* Returns address for TARGET_MEM_REF with parameters given by ADDR
185 in address space AS.
186 If REALLY_EXPAND is false, just make fake registers instead
187 of really expanding the operands, and perform the expansion in-place
188 by using one of the "templates". */
191 addr_for_mem_ref (struct mem_address *addr, addr_space_t as,
192 bool really_expand)
194 scalar_int_mode address_mode = targetm.addr_space.address_mode (as);
195 scalar_int_mode pointer_mode = targetm.addr_space.pointer_mode (as);
196 rtx address, sym, bse, idx, st, off;
197 struct mem_addr_template *templ;
199 if (addr->step && !integer_onep (addr->step))
200 st = immed_wide_int_const (addr->step, pointer_mode);
201 else
202 st = NULL_RTX;
204 if (addr->offset && !integer_zerop (addr->offset))
206 offset_int dc = offset_int::from (addr->offset, SIGNED);
207 off = immed_wide_int_const (dc, pointer_mode);
209 else
210 off = NULL_RTX;
212 if (!really_expand)
214 unsigned int templ_index
215 = TEMPL_IDX (as, addr->symbol, addr->base, addr->index, st, off);
217 if (templ_index >= vec_safe_length (mem_addr_template_list))
218 vec_safe_grow_cleared (mem_addr_template_list, templ_index + 1);
220 /* Reuse the templates for addresses, so that we do not waste memory. */
221 templ = &(*mem_addr_template_list)[templ_index];
222 if (!templ->ref)
224 sym = (addr->symbol ?
225 gen_rtx_SYMBOL_REF (pointer_mode, ggc_strdup ("test_symbol"))
226 : NULL_RTX);
227 bse = (addr->base ?
228 gen_raw_REG (pointer_mode, LAST_VIRTUAL_REGISTER + 1)
229 : NULL_RTX);
230 idx = (addr->index ?
231 gen_raw_REG (pointer_mode, LAST_VIRTUAL_REGISTER + 2)
232 : NULL_RTX);
234 gen_addr_rtx (pointer_mode, sym, bse, idx,
235 st? const0_rtx : NULL_RTX,
236 off? const0_rtx : NULL_RTX,
237 &templ->ref,
238 &templ->step_p,
239 &templ->off_p);
242 if (st)
243 *templ->step_p = st;
244 if (off)
245 *templ->off_p = off;
247 return templ->ref;
250 /* Otherwise really expand the expressions. */
251 sym = (addr->symbol
252 ? expand_expr (addr->symbol, NULL_RTX, pointer_mode, EXPAND_NORMAL)
253 : NULL_RTX);
254 bse = (addr->base
255 ? expand_expr (addr->base, NULL_RTX, pointer_mode, EXPAND_NORMAL)
256 : NULL_RTX);
257 idx = (addr->index
258 ? expand_expr (addr->index, NULL_RTX, pointer_mode, EXPAND_NORMAL)
259 : NULL_RTX);
261 gen_addr_rtx (pointer_mode, sym, bse, idx, st, off, &address, NULL, NULL);
262 if (pointer_mode != address_mode)
263 address = convert_memory_address (address_mode, address);
264 return address;
267 /* implement addr_for_mem_ref() directly from a tree, which avoids exporting
268 the mem_address structure. */
271 addr_for_mem_ref (tree exp, addr_space_t as, bool really_expand)
273 struct mem_address addr;
274 get_address_description (exp, &addr);
275 return addr_for_mem_ref (&addr, as, really_expand);
278 /* Returns address of MEM_REF in TYPE. */
280 tree
281 tree_mem_ref_addr (tree type, tree mem_ref)
283 tree addr;
284 tree act_elem;
285 tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
286 tree addr_base = NULL_TREE, addr_off = NULL_TREE;
288 addr_base = fold_convert (type, TMR_BASE (mem_ref));
290 act_elem = TMR_INDEX (mem_ref);
291 if (act_elem)
293 if (step)
294 act_elem = fold_build2 (MULT_EXPR, TREE_TYPE (act_elem),
295 act_elem, step);
296 addr_off = act_elem;
299 act_elem = TMR_INDEX2 (mem_ref);
300 if (act_elem)
302 if (addr_off)
303 addr_off = fold_build2 (PLUS_EXPR, TREE_TYPE (addr_off),
304 addr_off, act_elem);
305 else
306 addr_off = act_elem;
309 if (offset && !integer_zerop (offset))
311 if (addr_off)
312 addr_off = fold_build2 (PLUS_EXPR, TREE_TYPE (addr_off), addr_off,
313 fold_convert (TREE_TYPE (addr_off), offset));
314 else
315 addr_off = offset;
318 if (addr_off)
319 addr = fold_build_pointer_plus (addr_base, addr_off);
320 else
321 addr = addr_base;
323 return addr;
326 /* Returns true if a memory reference in MODE and with parameters given by
327 ADDR is valid on the current target. */
329 bool
330 valid_mem_ref_p (machine_mode mode, addr_space_t as,
331 struct mem_address *addr)
333 rtx address;
335 address = addr_for_mem_ref (addr, as, false);
336 if (!address)
337 return false;
339 return memory_address_addr_space_p (mode, address, as);
342 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
343 is valid on the current target and if so, creates and returns the
344 TARGET_MEM_REF. If VERIFY is false omit the verification step. */
346 static tree
347 create_mem_ref_raw (tree type, tree alias_ptr_type, struct mem_address *addr,
348 bool verify)
350 tree base, index2;
352 if (verify
353 && !valid_mem_ref_p (TYPE_MODE (type), TYPE_ADDR_SPACE (type), addr))
354 return NULL_TREE;
356 if (addr->step && integer_onep (addr->step))
357 addr->step = NULL_TREE;
359 if (addr->offset)
360 addr->offset = fold_convert (alias_ptr_type, addr->offset);
361 else
362 addr->offset = build_int_cst (alias_ptr_type, 0);
364 if (addr->symbol)
366 base = addr->symbol;
367 index2 = addr->base;
369 else if (addr->base
370 && POINTER_TYPE_P (TREE_TYPE (addr->base)))
372 base = addr->base;
373 index2 = NULL_TREE;
375 else
377 base = build_int_cst (build_pointer_type (type), 0);
378 index2 = addr->base;
381 /* If possible use a plain MEM_REF instead of a TARGET_MEM_REF.
382 ??? As IVOPTs does not follow restrictions to where the base
383 pointer may point to create a MEM_REF only if we know that
384 base is valid. */
385 if ((TREE_CODE (base) == ADDR_EXPR || TREE_CODE (base) == INTEGER_CST)
386 && (!index2 || integer_zerop (index2))
387 && (!addr->index || integer_zerop (addr->index)))
388 return fold_build2 (MEM_REF, type, base, addr->offset);
390 return build5 (TARGET_MEM_REF, type,
391 base, addr->offset, addr->index, addr->step, index2);
394 /* Returns true if OBJ is an object whose address is a link time constant. */
396 static bool
397 fixed_address_object_p (tree obj)
399 return (VAR_P (obj)
400 && (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
401 && ! DECL_DLLIMPORT_P (obj));
404 /* If ADDR contains an address of object that is a link time constant,
405 move it to PARTS->symbol. */
407 void
408 move_fixed_address_to_symbol (struct mem_address *parts, aff_tree *addr)
410 unsigned i;
411 tree val = NULL_TREE;
413 for (i = 0; i < addr->n; i++)
415 if (addr->elts[i].coef != 1)
416 continue;
418 val = addr->elts[i].val;
419 if (TREE_CODE (val) == ADDR_EXPR
420 && fixed_address_object_p (TREE_OPERAND (val, 0)))
421 break;
424 if (i == addr->n)
425 return;
427 parts->symbol = val;
428 aff_combination_remove_elt (addr, i);
431 /* Return true if ADDR contains an instance of BASE_HINT and it's moved to
432 PARTS->base. */
434 static bool
435 move_hint_to_base (tree type, struct mem_address *parts, tree base_hint,
436 aff_tree *addr)
438 unsigned i;
439 tree val = NULL_TREE;
440 int qual;
442 for (i = 0; i < addr->n; i++)
444 if (addr->elts[i].coef != 1)
445 continue;
447 val = addr->elts[i].val;
448 if (operand_equal_p (val, base_hint, 0))
449 break;
452 if (i == addr->n)
453 return false;
455 /* Cast value to appropriate pointer type. We cannot use a pointer
456 to TYPE directly, as the back-end will assume registers of pointer
457 type are aligned, and just the base itself may not actually be.
458 We use void pointer to the type's address space instead. */
459 qual = ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (type));
460 type = build_qualified_type (void_type_node, qual);
461 parts->base = fold_convert (build_pointer_type (type), val);
462 aff_combination_remove_elt (addr, i);
463 return true;
466 /* If ADDR contains an address of a dereferenced pointer, move it to
467 PARTS->base. */
469 static void
470 move_pointer_to_base (struct mem_address *parts, aff_tree *addr)
472 unsigned i;
473 tree val = NULL_TREE;
475 for (i = 0; i < addr->n; i++)
477 if (addr->elts[i].coef != 1)
478 continue;
480 val = addr->elts[i].val;
481 if (POINTER_TYPE_P (TREE_TYPE (val)))
482 break;
485 if (i == addr->n)
486 return;
488 parts->base = val;
489 aff_combination_remove_elt (addr, i);
492 /* Moves the loop variant part V in linear address ADDR to be the index
493 of PARTS. */
495 static void
496 move_variant_to_index (struct mem_address *parts, aff_tree *addr, tree v)
498 unsigned i;
499 tree val = NULL_TREE;
501 gcc_assert (!parts->index);
502 for (i = 0; i < addr->n; i++)
504 val = addr->elts[i].val;
505 if (operand_equal_p (val, v, 0))
506 break;
509 if (i == addr->n)
510 return;
512 parts->index = fold_convert (sizetype, val);
513 parts->step = wide_int_to_tree (sizetype, addr->elts[i].coef);
514 aff_combination_remove_elt (addr, i);
517 /* Adds ELT to PARTS. */
519 static void
520 add_to_parts (struct mem_address *parts, tree elt)
522 tree type;
524 if (!parts->index)
526 parts->index = fold_convert (sizetype, elt);
527 return;
530 if (!parts->base)
532 parts->base = elt;
533 return;
536 /* Add ELT to base. */
537 type = TREE_TYPE (parts->base);
538 if (POINTER_TYPE_P (type))
539 parts->base = fold_build_pointer_plus (parts->base, elt);
540 else
541 parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
544 /* Returns true if multiplying by RATIO is allowed in an address. Test the
545 validity for a memory reference accessing memory of mode MODE in address
546 space AS. */
548 static bool
549 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, machine_mode mode,
550 addr_space_t as)
552 #define MAX_RATIO 128
553 unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mode;
554 static vec<sbitmap> valid_mult_list;
555 sbitmap valid_mult;
557 if (data_index >= valid_mult_list.length ())
558 valid_mult_list.safe_grow_cleared (data_index + 1);
560 valid_mult = valid_mult_list[data_index];
561 if (!valid_mult)
563 machine_mode address_mode = targetm.addr_space.address_mode (as);
564 rtx reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
565 rtx reg2 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
566 rtx addr, scaled;
567 HOST_WIDE_INT i;
569 valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
570 bitmap_clear (valid_mult);
571 scaled = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
572 addr = gen_rtx_fmt_ee (PLUS, address_mode, scaled, reg2);
573 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
575 XEXP (scaled, 1) = gen_int_mode (i, address_mode);
576 if (memory_address_addr_space_p (mode, addr, as)
577 || memory_address_addr_space_p (mode, scaled, as))
578 bitmap_set_bit (valid_mult, i + MAX_RATIO);
581 if (dump_file && (dump_flags & TDF_DETAILS))
583 fprintf (dump_file, " allowed multipliers:");
584 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
585 if (bitmap_bit_p (valid_mult, i + MAX_RATIO))
586 fprintf (dump_file, " %d", (int) i);
587 fprintf (dump_file, "\n");
588 fprintf (dump_file, "\n");
591 valid_mult_list[data_index] = valid_mult;
594 if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
595 return false;
597 return bitmap_bit_p (valid_mult, ratio + MAX_RATIO);
600 /* Finds the most expensive multiplication in ADDR that can be
601 expressed in an addressing mode and move the corresponding
602 element(s) to PARTS. */
604 static void
605 most_expensive_mult_to_index (tree type, struct mem_address *parts,
606 aff_tree *addr, bool speed)
608 addr_space_t as = TYPE_ADDR_SPACE (type);
609 machine_mode address_mode = targetm.addr_space.address_mode (as);
610 HOST_WIDE_INT coef;
611 unsigned best_mult_cost = 0, acost;
612 tree mult_elt = NULL_TREE, elt;
613 unsigned i, j;
614 enum tree_code op_code;
616 offset_int best_mult = 0;
617 for (i = 0; i < addr->n; i++)
619 if (!wi::fits_shwi_p (addr->elts[i].coef))
620 continue;
622 coef = addr->elts[i].coef.to_shwi ();
623 if (coef == 1
624 || !multiplier_allowed_in_address_p (coef, TYPE_MODE (type), as))
625 continue;
627 acost = mult_by_coeff_cost (coef, address_mode, speed);
629 if (acost > best_mult_cost)
631 best_mult_cost = acost;
632 best_mult = offset_int::from (addr->elts[i].coef, SIGNED);
636 if (!best_mult_cost)
637 return;
639 /* Collect elements multiplied by best_mult. */
640 for (i = j = 0; i < addr->n; i++)
642 offset_int amult = offset_int::from (addr->elts[i].coef, SIGNED);
643 offset_int amult_neg = -wi::sext (amult, TYPE_PRECISION (addr->type));
645 if (amult == best_mult)
646 op_code = PLUS_EXPR;
647 else if (amult_neg == best_mult)
648 op_code = MINUS_EXPR;
649 else
651 addr->elts[j] = addr->elts[i];
652 j++;
653 continue;
656 elt = fold_convert (sizetype, addr->elts[i].val);
657 if (mult_elt)
658 mult_elt = fold_build2 (op_code, sizetype, mult_elt, elt);
659 else if (op_code == PLUS_EXPR)
660 mult_elt = elt;
661 else
662 mult_elt = fold_build1 (NEGATE_EXPR, sizetype, elt);
664 addr->n = j;
666 parts->index = mult_elt;
667 parts->step = wide_int_to_tree (sizetype, best_mult);
670 /* Splits address ADDR for a memory access of type TYPE into PARTS.
671 If BASE_HINT is non-NULL, it specifies an SSA name to be used
672 preferentially as base of the reference, and IV_CAND is the selected
673 iv candidate used in ADDR. Store true to VAR_IN_BASE if variant
674 part of address is split to PARTS.base.
676 TODO -- be more clever about the distribution of the elements of ADDR
677 to PARTS. Some architectures do not support anything but single
678 register in address, possibly with a small integer offset; while
679 create_mem_ref will simplify the address to an acceptable shape
680 later, it would be more efficient to know that asking for complicated
681 addressing modes is useless. */
683 static void
684 addr_to_parts (tree type, aff_tree *addr, tree iv_cand, tree base_hint,
685 struct mem_address *parts, bool *var_in_base, bool speed)
687 tree part;
688 unsigned i;
690 parts->symbol = NULL_TREE;
691 parts->base = NULL_TREE;
692 parts->index = NULL_TREE;
693 parts->step = NULL_TREE;
695 if (addr->offset != 0)
696 parts->offset = wide_int_to_tree (sizetype, addr->offset);
697 else
698 parts->offset = NULL_TREE;
700 /* Try to find a symbol. */
701 move_fixed_address_to_symbol (parts, addr);
703 /* Since at the moment there is no reliable way to know how to
704 distinguish between pointer and its offset, we decide if var
705 part is the pointer based on guess. */
706 *var_in_base = (base_hint != NULL && parts->symbol == NULL);
707 if (*var_in_base)
708 *var_in_base = move_hint_to_base (type, parts, base_hint, addr);
709 else
710 move_variant_to_index (parts, addr, iv_cand);
712 /* First move the most expensive feasible multiplication to index. */
713 if (!parts->index)
714 most_expensive_mult_to_index (type, parts, addr, speed);
716 /* Move pointer into base. */
717 if (!parts->symbol && !parts->base)
718 move_pointer_to_base (parts, addr);
720 /* Then try to process the remaining elements. */
721 for (i = 0; i < addr->n; i++)
723 part = fold_convert (sizetype, addr->elts[i].val);
724 if (addr->elts[i].coef != 1)
725 part = fold_build2 (MULT_EXPR, sizetype, part,
726 wide_int_to_tree (sizetype, addr->elts[i].coef));
727 add_to_parts (parts, part);
729 if (addr->rest)
730 add_to_parts (parts, fold_convert (sizetype, addr->rest));
733 /* Force the PARTS to register. */
735 static void
736 gimplify_mem_ref_parts (gimple_stmt_iterator *gsi, struct mem_address *parts)
738 if (parts->base)
739 parts->base = force_gimple_operand_gsi_1 (gsi, parts->base,
740 is_gimple_mem_ref_addr, NULL_TREE,
741 true, GSI_SAME_STMT);
742 if (parts->index)
743 parts->index = force_gimple_operand_gsi (gsi, parts->index,
744 true, NULL_TREE,
745 true, GSI_SAME_STMT);
748 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
749 computations are emitted in front of GSI. TYPE is the mode
750 of created memory reference. IV_CAND is the selected iv candidate in ADDR,
751 and BASE_HINT is non NULL if IV_CAND comes from a base address
752 object. */
754 tree
755 create_mem_ref (gimple_stmt_iterator *gsi, tree type, aff_tree *addr,
756 tree alias_ptr_type, tree iv_cand, tree base_hint, bool speed)
758 bool var_in_base;
759 tree mem_ref, tmp;
760 struct mem_address parts;
762 addr_to_parts (type, addr, iv_cand, base_hint, &parts, &var_in_base, speed);
763 gimplify_mem_ref_parts (gsi, &parts);
764 mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
765 if (mem_ref)
766 return mem_ref;
768 /* The expression is too complicated. Try making it simpler. */
770 /* Merge symbol into other parts. */
771 if (parts.symbol)
773 tmp = parts.symbol;
774 parts.symbol = NULL_TREE;
775 gcc_assert (is_gimple_val (tmp));
777 if (parts.base)
779 gcc_assert (useless_type_conversion_p (sizetype,
780 TREE_TYPE (parts.base)));
782 if (parts.index)
784 /* Add the symbol to base, eventually forcing it to register. */
785 tmp = fold_build_pointer_plus (tmp, parts.base);
786 tmp = force_gimple_operand_gsi_1 (gsi, tmp,
787 is_gimple_mem_ref_addr,
788 NULL_TREE, true,
789 GSI_SAME_STMT);
791 else
793 /* Move base to index, then move the symbol to base. */
794 parts.index = parts.base;
796 parts.base = tmp;
798 else
799 parts.base = tmp;
801 mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
802 if (mem_ref)
803 return mem_ref;
806 /* Move multiplication to index by transforming address expression:
807 [... + index << step + ...]
808 into:
809 index' = index << step;
810 [... + index' + ,,,]. */
811 if (parts.step && !integer_onep (parts.step))
813 gcc_assert (parts.index);
814 parts.index = force_gimple_operand_gsi (gsi,
815 fold_build2 (MULT_EXPR, sizetype,
816 parts.index, parts.step),
817 true, NULL_TREE, true, GSI_SAME_STMT);
818 parts.step = NULL_TREE;
820 mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
821 if (mem_ref)
822 return mem_ref;
825 /* Add offset to invariant part by transforming address expression:
826 [base + index + offset]
827 into:
828 base' = base + offset;
829 [base' + index]
831 index' = index + offset;
832 [base + index']
833 depending on which one is invariant. */
834 if (parts.offset && !integer_zerop (parts.offset))
836 tree old_base = unshare_expr (parts.base);
837 tree old_index = unshare_expr (parts.index);
838 tree old_offset = unshare_expr (parts.offset);
840 tmp = parts.offset;
841 parts.offset = NULL_TREE;
842 /* Add offset to invariant part. */
843 if (!var_in_base)
845 if (parts.base)
847 tmp = fold_build_pointer_plus (parts.base, tmp);
848 tmp = force_gimple_operand_gsi_1 (gsi, tmp,
849 is_gimple_mem_ref_addr,
850 NULL_TREE, true,
851 GSI_SAME_STMT);
853 parts.base = tmp;
855 else
857 if (parts.index)
859 tmp = fold_build_pointer_plus (parts.index, tmp);
860 tmp = force_gimple_operand_gsi_1 (gsi, tmp,
861 is_gimple_mem_ref_addr,
862 NULL_TREE, true,
863 GSI_SAME_STMT);
865 parts.index = tmp;
868 mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
869 if (mem_ref)
870 return mem_ref;
872 /* Restore parts.base, index and offset so that we can check if
873 [base + offset] addressing mode is supported in next step.
874 This is necessary for targets only support [base + offset],
875 but not [base + index] addressing mode. */
876 parts.base = old_base;
877 parts.index = old_index;
878 parts.offset = old_offset;
881 /* Transform [base + index + ...] into:
882 base' = base + index;
883 [base' + ...]. */
884 if (parts.index)
886 tmp = parts.index;
887 parts.index = NULL_TREE;
888 /* Add index to base. */
889 if (parts.base)
891 tmp = fold_build_pointer_plus (parts.base, tmp);
892 tmp = force_gimple_operand_gsi_1 (gsi, tmp,
893 is_gimple_mem_ref_addr,
894 NULL_TREE, true, GSI_SAME_STMT);
896 parts.base = tmp;
898 mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
899 if (mem_ref)
900 return mem_ref;
903 /* Transform [base + offset] into:
904 base' = base + offset;
905 [base']. */
906 if (parts.offset && !integer_zerop (parts.offset))
908 tmp = parts.offset;
909 parts.offset = NULL_TREE;
910 /* Add offset to base. */
911 if (parts.base)
913 tmp = fold_build_pointer_plus (parts.base, tmp);
914 tmp = force_gimple_operand_gsi_1 (gsi, tmp,
915 is_gimple_mem_ref_addr,
916 NULL_TREE, true, GSI_SAME_STMT);
918 parts.base = tmp;
920 mem_ref = create_mem_ref_raw (type, alias_ptr_type, &parts, true);
921 if (mem_ref)
922 return mem_ref;
925 /* Verify that the address is in the simplest possible shape
926 (only a register). If we cannot create such a memory reference,
927 something is really wrong. */
928 gcc_assert (parts.symbol == NULL_TREE);
929 gcc_assert (parts.index == NULL_TREE);
930 gcc_assert (!parts.step || integer_onep (parts.step));
931 gcc_assert (!parts.offset || integer_zerop (parts.offset));
932 gcc_unreachable ();
935 /* Copies components of the address from OP to ADDR. */
937 void
938 get_address_description (tree op, struct mem_address *addr)
940 if (TREE_CODE (TMR_BASE (op)) == ADDR_EXPR)
942 addr->symbol = TMR_BASE (op);
943 addr->base = TMR_INDEX2 (op);
945 else
947 addr->symbol = NULL_TREE;
948 if (TMR_INDEX2 (op))
950 gcc_assert (integer_zerop (TMR_BASE (op)));
951 addr->base = TMR_INDEX2 (op);
953 else
954 addr->base = TMR_BASE (op);
956 addr->index = TMR_INDEX (op);
957 addr->step = TMR_STEP (op);
958 addr->offset = TMR_OFFSET (op);
961 /* Copies the reference information from OLD_REF to NEW_REF, where
962 NEW_REF should be either a MEM_REF or a TARGET_MEM_REF. */
964 void
965 copy_ref_info (tree new_ref, tree old_ref)
967 tree new_ptr_base = NULL_TREE;
969 gcc_assert (TREE_CODE (new_ref) == MEM_REF
970 || TREE_CODE (new_ref) == TARGET_MEM_REF);
972 TREE_SIDE_EFFECTS (new_ref) = TREE_SIDE_EFFECTS (old_ref);
973 TREE_THIS_VOLATILE (new_ref) = TREE_THIS_VOLATILE (old_ref);
975 new_ptr_base = TREE_OPERAND (new_ref, 0);
977 /* We can transfer points-to information from an old pointer
978 or decl base to the new one. */
979 if (new_ptr_base
980 && TREE_CODE (new_ptr_base) == SSA_NAME
981 && !SSA_NAME_PTR_INFO (new_ptr_base))
983 tree base = get_base_address (old_ref);
984 if (!base)
986 else if ((TREE_CODE (base) == MEM_REF
987 || TREE_CODE (base) == TARGET_MEM_REF)
988 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
989 && SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0)))
991 struct ptr_info_def *new_pi;
992 unsigned int align, misalign;
994 duplicate_ssa_name_ptr_info
995 (new_ptr_base, SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0)));
996 new_pi = SSA_NAME_PTR_INFO (new_ptr_base);
997 /* We have to be careful about transferring alignment information. */
998 if (get_ptr_info_alignment (new_pi, &align, &misalign)
999 && TREE_CODE (old_ref) == MEM_REF
1000 && !(TREE_CODE (new_ref) == TARGET_MEM_REF
1001 && (TMR_INDEX2 (new_ref)
1002 /* TODO: Below conditions can be relaxed if TMR_INDEX
1003 is an indcution variable and its initial value and
1004 step are aligned. */
1005 || (TMR_INDEX (new_ref) && !TMR_STEP (new_ref))
1006 || (TMR_STEP (new_ref)
1007 && (TREE_INT_CST_LOW (TMR_STEP (new_ref))
1008 < align)))))
1010 unsigned int inc = (mem_ref_offset (old_ref).to_short_addr ()
1011 - mem_ref_offset (new_ref).to_short_addr ());
1012 adjust_ptr_info_misalignment (new_pi, inc);
1014 else
1015 mark_ptr_info_alignment_unknown (new_pi);
1017 else if (VAR_P (base)
1018 || TREE_CODE (base) == PARM_DECL
1019 || TREE_CODE (base) == RESULT_DECL)
1021 struct ptr_info_def *pi = get_ptr_info (new_ptr_base);
1022 pt_solution_set_var (&pi->pt, base);
1027 /* Move constants in target_mem_ref REF to offset. Returns the new target
1028 mem ref if anything changes, NULL_TREE otherwise. */
1030 tree
1031 maybe_fold_tmr (tree ref)
1033 struct mem_address addr;
1034 bool changed = false;
1035 tree new_ref, off;
1037 get_address_description (ref, &addr);
1039 if (addr.base
1040 && TREE_CODE (addr.base) == INTEGER_CST
1041 && !integer_zerop (addr.base))
1043 addr.offset = fold_binary_to_constant (PLUS_EXPR,
1044 TREE_TYPE (addr.offset),
1045 addr.offset, addr.base);
1046 addr.base = NULL_TREE;
1047 changed = true;
1050 if (addr.symbol
1051 && TREE_CODE (TREE_OPERAND (addr.symbol, 0)) == MEM_REF)
1053 addr.offset = fold_binary_to_constant
1054 (PLUS_EXPR, TREE_TYPE (addr.offset),
1055 addr.offset,
1056 TREE_OPERAND (TREE_OPERAND (addr.symbol, 0), 1));
1057 addr.symbol = TREE_OPERAND (TREE_OPERAND (addr.symbol, 0), 0);
1058 changed = true;
1060 else if (addr.symbol
1061 && handled_component_p (TREE_OPERAND (addr.symbol, 0)))
1063 HOST_WIDE_INT offset;
1064 addr.symbol = build_fold_addr_expr
1065 (get_addr_base_and_unit_offset
1066 (TREE_OPERAND (addr.symbol, 0), &offset));
1067 addr.offset = int_const_binop (PLUS_EXPR,
1068 addr.offset, size_int (offset));
1069 changed = true;
1072 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
1074 off = addr.index;
1075 if (addr.step)
1077 off = fold_binary_to_constant (MULT_EXPR, sizetype,
1078 off, addr.step);
1079 addr.step = NULL_TREE;
1082 addr.offset = fold_binary_to_constant (PLUS_EXPR,
1083 TREE_TYPE (addr.offset),
1084 addr.offset, off);
1085 addr.index = NULL_TREE;
1086 changed = true;
1089 if (!changed)
1090 return NULL_TREE;
1092 /* If we have propagated something into this TARGET_MEM_REF and thus
1093 ended up folding it, always create a new TARGET_MEM_REF regardless
1094 if it is valid in this for on the target - the propagation result
1095 wouldn't be anyway. */
1096 new_ref = create_mem_ref_raw (TREE_TYPE (ref),
1097 TREE_TYPE (addr.offset), &addr, false);
1098 TREE_SIDE_EFFECTS (new_ref) = TREE_SIDE_EFFECTS (ref);
1099 TREE_THIS_VOLATILE (new_ref) = TREE_THIS_VOLATILE (ref);
1100 return new_ref;
1103 /* Dump PARTS to FILE. */
1105 extern void dump_mem_address (FILE *, struct mem_address *);
1106 void
1107 dump_mem_address (FILE *file, struct mem_address *parts)
1109 if (parts->symbol)
1111 fprintf (file, "symbol: ");
1112 print_generic_expr (file, TREE_OPERAND (parts->symbol, 0), TDF_SLIM);
1113 fprintf (file, "\n");
1115 if (parts->base)
1117 fprintf (file, "base: ");
1118 print_generic_expr (file, parts->base, TDF_SLIM);
1119 fprintf (file, "\n");
1121 if (parts->index)
1123 fprintf (file, "index: ");
1124 print_generic_expr (file, parts->index, TDF_SLIM);
1125 fprintf (file, "\n");
1127 if (parts->step)
1129 fprintf (file, "step: ");
1130 print_generic_expr (file, parts->step, TDF_SLIM);
1131 fprintf (file, "\n");
1133 if (parts->offset)
1135 fprintf (file, "offset: ");
1136 print_generic_expr (file, parts->offset, TDF_SLIM);
1137 fprintf (file, "\n");
1141 #include "gt-tree-ssa-address.h"