1 /* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004, 2006, 2007, 2008, 2009 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
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
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. */
25 #include "coretypes.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
33 #include "diagnostic.h"
34 #include "tree-flow.h"
35 #include "tree-dump.h"
36 #include "tree-pass.h"
39 #include "tree-inline.h"
40 #include "insn-config.h"
44 #include "tree-affine.h"
47 /* TODO -- handling of symbols (according to Richard Hendersons
48 comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
50 There are at least 5 different kinds of symbols that we can run up against:
52 (1) binds_local_p, small data area.
53 (2) binds_local_p, eg local statics
54 (3) !binds_local_p, eg global variables
55 (4) thread local, local_exec
56 (5) thread local, !local_exec
58 Now, (1) won't appear often in an array context, but it certainly can.
59 All you have to do is set -GN high enough, or explicitly mark any
60 random object __attribute__((section (".sdata"))).
62 All of these affect whether or not a symbol is in fact a valid address.
63 The only one tested here is (3). And that result may very well
64 be incorrect for (4) or (5).
66 An incorrect result here does not cause incorrect results out the
67 back end, because the expander in expr.c validizes the address. However
68 it would be nice to improve the handling here in order to produce more
71 /* A "template" for memory address, used to determine whether the address is
74 typedef struct GTY (()) mem_addr_template
{
75 rtx ref
; /* The template. */
76 rtx
* GTY ((skip
)) step_p
; /* The point in template where the step should be
78 rtx
* GTY ((skip
)) off_p
; /* The point in template where the offset should
82 DEF_VEC_O (mem_addr_template
);
83 DEF_VEC_ALLOC_O (mem_addr_template
, gc
);
85 /* The templates. Each of the low five bits of the index corresponds to one
86 component of TARGET_MEM_REF being present, while the high bits identify
87 the address space. See TEMPL_IDX. */
89 static GTY(()) VEC (mem_addr_template
, gc
) *mem_addr_template_list
;
91 #define TEMPL_IDX(AS, SYMBOL, BASE, INDEX, STEP, OFFSET) \
93 | ((SYMBOL != 0) << 4) \
94 | ((BASE != 0) << 3) \
95 | ((INDEX != 0) << 2) \
96 | ((STEP != 0) << 1) \
99 /* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
100 STEP and OFFSET to *ADDR using address mode ADDRESS_MODE. Stores pointers
101 to where step is placed to *STEP_P and offset to *OFFSET_P. */
104 gen_addr_rtx (enum machine_mode address_mode
,
105 rtx symbol
, rtx base
, rtx index
, rtx step
, rtx offset
,
106 rtx
*addr
, rtx
**step_p
, rtx
**offset_p
)
121 act_elem
= gen_rtx_MULT (address_mode
, act_elem
, step
);
124 *step_p
= &XEXP (act_elem
, 1);
133 *addr
= simplify_gen_binary (PLUS
, address_mode
, base
, *addr
);
143 act_elem
= gen_rtx_PLUS (address_mode
, act_elem
, offset
);
146 *offset_p
= &XEXP (act_elem
, 1);
148 if (GET_CODE (symbol
) == SYMBOL_REF
149 || GET_CODE (symbol
) == LABEL_REF
150 || GET_CODE (symbol
) == CONST
)
151 act_elem
= gen_rtx_CONST (address_mode
, act_elem
);
155 *addr
= gen_rtx_PLUS (address_mode
, *addr
, act_elem
);
163 *addr
= gen_rtx_PLUS (address_mode
, *addr
, offset
);
165 *offset_p
= &XEXP (*addr
, 1);
179 /* Returns address for TARGET_MEM_REF with parameters given by ADDR
181 If REALLY_EXPAND is false, just make fake registers instead
182 of really expanding the operands, and perform the expansion in-place
183 by using one of the "templates". */
186 addr_for_mem_ref (struct mem_address
*addr
, addr_space_t as
,
189 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
190 rtx address
, sym
, bse
, idx
, st
, off
;
191 struct mem_addr_template
*templ
;
193 if (addr
->step
&& !integer_onep (addr
->step
))
194 st
= immed_double_const (TREE_INT_CST_LOW (addr
->step
),
195 TREE_INT_CST_HIGH (addr
->step
), address_mode
);
199 if (addr
->offset
&& !integer_zerop (addr
->offset
))
200 off
= immed_double_const (TREE_INT_CST_LOW (addr
->offset
),
201 TREE_INT_CST_HIGH (addr
->offset
), address_mode
);
207 unsigned int templ_index
208 = TEMPL_IDX (as
, addr
->symbol
, addr
->base
, addr
->index
, st
, off
);
211 >= VEC_length (mem_addr_template
, mem_addr_template_list
))
212 VEC_safe_grow_cleared (mem_addr_template
, gc
, mem_addr_template_list
,
215 /* Reuse the templates for addresses, so that we do not waste memory. */
216 templ
= VEC_index (mem_addr_template
, mem_addr_template_list
, templ_index
);
219 sym
= (addr
->symbol
?
220 gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup ("test_symbol"))
223 gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1)
226 gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2)
229 gen_addr_rtx (address_mode
, sym
, bse
, idx
,
230 st
? const0_rtx
: NULL_RTX
,
231 off
? const0_rtx
: NULL_RTX
,
245 /* Otherwise really expand the expressions. */
247 ? expand_expr (build_addr (addr
->symbol
, current_function_decl
),
248 NULL_RTX
, address_mode
, EXPAND_NORMAL
)
251 ? expand_expr (addr
->base
, NULL_RTX
, address_mode
, EXPAND_NORMAL
)
254 ? expand_expr (addr
->index
, NULL_RTX
, address_mode
, EXPAND_NORMAL
)
257 gen_addr_rtx (address_mode
, sym
, bse
, idx
, st
, off
, &address
, NULL
, NULL
);
261 /* Returns address of MEM_REF in TYPE. */
264 tree_mem_ref_addr (tree type
, tree mem_ref
)
268 tree step
= TMR_STEP (mem_ref
), offset
= TMR_OFFSET (mem_ref
);
269 tree sym
= TMR_SYMBOL (mem_ref
), base
= TMR_BASE (mem_ref
);
270 tree addr_base
= NULL_TREE
, addr_off
= NULL_TREE
;
273 addr_base
= fold_convert (type
, build_addr (sym
, current_function_decl
));
274 else if (base
&& POINTER_TYPE_P (TREE_TYPE (base
)))
276 addr_base
= fold_convert (type
, base
);
280 act_elem
= TMR_INDEX (mem_ref
);
284 act_elem
= fold_build2 (MULT_EXPR
, sizetype
, act_elem
, step
);
292 addr_off
= fold_build2 (PLUS_EXPR
, sizetype
, addr_off
, act_elem
);
297 if (offset
&& !integer_zerop (offset
))
300 addr_off
= fold_build2 (PLUS_EXPR
, sizetype
, addr_off
, offset
);
308 addr
= fold_build2 (POINTER_PLUS_EXPR
, type
, addr_base
, addr_off
);
310 addr
= fold_convert (type
, addr_off
);
315 addr
= build_int_cst (type
, 0);
320 /* Returns true if a memory reference in MODE and with parameters given by
321 ADDR is valid on the current target. */
324 valid_mem_ref_p (enum machine_mode mode
, addr_space_t as
,
325 struct mem_address
*addr
)
329 address
= addr_for_mem_ref (addr
, as
, false);
333 return memory_address_addr_space_p (mode
, address
, as
);
336 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
337 is valid on the current target and if so, creates and returns the
341 create_mem_ref_raw (tree type
, struct mem_address
*addr
)
343 if (!valid_mem_ref_p (TYPE_MODE (type
), TYPE_ADDR_SPACE (type
), addr
))
346 if (addr
->step
&& integer_onep (addr
->step
))
347 addr
->step
= NULL_TREE
;
349 if (addr
->offset
&& integer_zerop (addr
->offset
))
350 addr
->offset
= NULL_TREE
;
352 return build6 (TARGET_MEM_REF
, type
,
353 addr
->symbol
, addr
->base
, addr
->index
,
354 addr
->step
, addr
->offset
, NULL
);
357 /* Returns true if OBJ is an object whose address is a link time constant. */
360 fixed_address_object_p (tree obj
)
362 return (TREE_CODE (obj
) == VAR_DECL
363 && (TREE_STATIC (obj
)
364 || DECL_EXTERNAL (obj
))
365 && ! DECL_DLLIMPORT_P (obj
));
368 /* If ADDR contains an address of object that is a link time constant,
369 move it to PARTS->symbol. */
372 move_fixed_address_to_symbol (struct mem_address
*parts
, aff_tree
*addr
)
375 tree val
= NULL_TREE
;
377 for (i
= 0; i
< addr
->n
; i
++)
379 if (!double_int_one_p (addr
->elts
[i
].coef
))
382 val
= addr
->elts
[i
].val
;
383 if (TREE_CODE (val
) == ADDR_EXPR
384 && fixed_address_object_p (TREE_OPERAND (val
, 0)))
391 parts
->symbol
= TREE_OPERAND (val
, 0);
392 aff_combination_remove_elt (addr
, i
);
395 /* If ADDR contains an instance of BASE_HINT, move it to PARTS->base. */
398 move_hint_to_base (tree type
, struct mem_address
*parts
, tree base_hint
,
402 tree val
= NULL_TREE
;
404 for (i
= 0; i
< addr
->n
; i
++)
406 if (!double_int_one_p (addr
->elts
[i
].coef
))
409 val
= addr
->elts
[i
].val
;
410 if (operand_equal_p (val
, base_hint
, 0))
417 /* Cast value to appropriate pointer type. */
418 parts
->base
= fold_convert (build_pointer_type (type
), val
);
419 aff_combination_remove_elt (addr
, i
);
422 /* If ADDR contains an address of a dereferenced pointer, move it to
426 move_pointer_to_base (struct mem_address
*parts
, aff_tree
*addr
)
429 tree val
= NULL_TREE
;
431 for (i
= 0; i
< addr
->n
; i
++)
433 if (!double_int_one_p (addr
->elts
[i
].coef
))
436 val
= addr
->elts
[i
].val
;
437 if (POINTER_TYPE_P (TREE_TYPE (val
)))
445 aff_combination_remove_elt (addr
, i
);
448 /* Adds ELT to PARTS. */
451 add_to_parts (struct mem_address
*parts
, tree elt
)
457 parts
->index
= fold_convert (sizetype
, elt
);
467 /* Add ELT to base. */
468 type
= TREE_TYPE (parts
->base
);
469 if (POINTER_TYPE_P (type
))
470 parts
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
,
472 fold_convert (sizetype
, elt
));
474 parts
->base
= fold_build2 (PLUS_EXPR
, type
,
478 /* Finds the most expensive multiplication in ADDR that can be
479 expressed in an addressing mode and move the corresponding
480 element(s) to PARTS. */
483 most_expensive_mult_to_index (tree type
, struct mem_address
*parts
,
484 aff_tree
*addr
, bool speed
)
486 addr_space_t as
= TYPE_ADDR_SPACE (type
);
487 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
489 double_int best_mult
, amult
, amult_neg
;
490 unsigned best_mult_cost
= 0, acost
;
491 tree mult_elt
= NULL_TREE
, elt
;
493 enum tree_code op_code
;
495 best_mult
= double_int_zero
;
496 for (i
= 0; i
< addr
->n
; i
++)
498 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
501 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
503 || !multiplier_allowed_in_address_p (coef
, TYPE_MODE (type
), as
))
506 acost
= multiply_by_cost (coef
, address_mode
, speed
);
508 if (acost
> best_mult_cost
)
510 best_mult_cost
= acost
;
511 best_mult
= addr
->elts
[i
].coef
;
518 /* Collect elements multiplied by best_mult. */
519 for (i
= j
= 0; i
< addr
->n
; i
++)
521 amult
= addr
->elts
[i
].coef
;
522 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
524 if (double_int_equal_p (amult
, best_mult
))
526 else if (double_int_equal_p (amult_neg
, best_mult
))
527 op_code
= MINUS_EXPR
;
530 addr
->elts
[j
] = addr
->elts
[i
];
535 elt
= fold_convert (sizetype
, addr
->elts
[i
].val
);
537 mult_elt
= fold_build2 (op_code
, sizetype
, mult_elt
, elt
);
538 else if (op_code
== PLUS_EXPR
)
541 mult_elt
= fold_build1 (NEGATE_EXPR
, sizetype
, elt
);
545 parts
->index
= mult_elt
;
546 parts
->step
= double_int_to_tree (sizetype
, best_mult
);
549 /* Splits address ADDR for a memory access of type TYPE into PARTS.
550 If BASE_HINT is non-NULL, it specifies an SSA name to be used
551 preferentially as base of the reference.
553 TODO -- be more clever about the distribution of the elements of ADDR
554 to PARTS. Some architectures do not support anything but single
555 register in address, possibly with a small integer offset; while
556 create_mem_ref will simplify the address to an acceptable shape
557 later, it would be more efficient to know that asking for complicated
558 addressing modes is useless. */
561 addr_to_parts (tree type
, aff_tree
*addr
, tree base_hint
,
562 struct mem_address
*parts
, bool speed
)
567 parts
->symbol
= NULL_TREE
;
568 parts
->base
= NULL_TREE
;
569 parts
->index
= NULL_TREE
;
570 parts
->step
= NULL_TREE
;
572 if (!double_int_zero_p (addr
->offset
))
573 parts
->offset
= double_int_to_tree (sizetype
, addr
->offset
);
575 parts
->offset
= NULL_TREE
;
577 /* Try to find a symbol. */
578 move_fixed_address_to_symbol (parts
, addr
);
580 /* First move the most expensive feasible multiplication
582 most_expensive_mult_to_index (type
, parts
, addr
, speed
);
584 /* Try to find a base of the reference. Since at the moment
585 there is no reliable way how to distinguish between pointer and its
586 offset, this is just a guess. */
587 if (!parts
->symbol
&& base_hint
)
588 move_hint_to_base (type
, parts
, base_hint
, addr
);
589 if (!parts
->symbol
&& !parts
->base
)
590 move_pointer_to_base (parts
, addr
);
592 /* Then try to process the remaining elements. */
593 for (i
= 0; i
< addr
->n
; i
++)
595 part
= fold_convert (sizetype
, addr
->elts
[i
].val
);
596 if (!double_int_one_p (addr
->elts
[i
].coef
))
597 part
= fold_build2 (MULT_EXPR
, sizetype
, part
,
598 double_int_to_tree (sizetype
, addr
->elts
[i
].coef
));
599 add_to_parts (parts
, part
);
602 add_to_parts (parts
, fold_convert (sizetype
, addr
->rest
));
605 /* Force the PARTS to register. */
608 gimplify_mem_ref_parts (gimple_stmt_iterator
*gsi
, struct mem_address
*parts
)
611 parts
->base
= force_gimple_operand_gsi (gsi
, parts
->base
,
613 true, GSI_SAME_STMT
);
615 parts
->index
= force_gimple_operand_gsi (gsi
, parts
->index
,
617 true, GSI_SAME_STMT
);
620 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
621 computations are emitted in front of GSI. TYPE is the mode
622 of created memory reference. */
625 create_mem_ref (gimple_stmt_iterator
*gsi
, tree type
, aff_tree
*addr
,
626 tree base_hint
, bool speed
)
630 struct mem_address parts
;
632 addr_to_parts (type
, addr
, base_hint
, &parts
, speed
);
633 gimplify_mem_ref_parts (gsi
, &parts
);
634 mem_ref
= create_mem_ref_raw (type
, &parts
);
638 /* The expression is too complicated. Try making it simpler. */
640 if (parts
.step
&& !integer_onep (parts
.step
))
642 /* Move the multiplication to index. */
643 gcc_assert (parts
.index
);
644 parts
.index
= force_gimple_operand_gsi (gsi
,
645 fold_build2 (MULT_EXPR
, sizetype
,
646 parts
.index
, parts
.step
),
647 true, NULL_TREE
, true, GSI_SAME_STMT
);
648 parts
.step
= NULL_TREE
;
650 mem_ref
= create_mem_ref_raw (type
, &parts
);
657 tmp
= build_addr (parts
.symbol
, current_function_decl
);
658 gcc_assert (is_gimple_val (tmp
));
660 /* Add the symbol to base, eventually forcing it to register. */
663 gcc_assert (useless_type_conversion_p
664 (sizetype
, TREE_TYPE (parts
.base
)));
668 atype
= TREE_TYPE (tmp
);
669 parts
.base
= force_gimple_operand_gsi (gsi
,
670 fold_build2 (POINTER_PLUS_EXPR
, atype
,
672 fold_convert (sizetype
, parts
.base
)),
673 true, NULL_TREE
, true, GSI_SAME_STMT
);
677 parts
.index
= parts
.base
;
683 parts
.symbol
= NULL_TREE
;
685 mem_ref
= create_mem_ref_raw (type
, &parts
);
692 /* Add index to base. */
695 atype
= TREE_TYPE (parts
.base
);
696 parts
.base
= force_gimple_operand_gsi (gsi
,
697 fold_build2 (POINTER_PLUS_EXPR
, atype
,
700 true, NULL_TREE
, true, GSI_SAME_STMT
);
703 parts
.base
= parts
.index
;
704 parts
.index
= NULL_TREE
;
706 mem_ref
= create_mem_ref_raw (type
, &parts
);
711 if (parts
.offset
&& !integer_zerop (parts
.offset
))
713 /* Try adding offset to base. */
716 atype
= TREE_TYPE (parts
.base
);
717 parts
.base
= force_gimple_operand_gsi (gsi
,
718 fold_build2 (POINTER_PLUS_EXPR
, atype
,
720 fold_convert (sizetype
, parts
.offset
)),
721 true, NULL_TREE
, true, GSI_SAME_STMT
);
724 parts
.base
= parts
.offset
;
726 parts
.offset
= NULL_TREE
;
728 mem_ref
= create_mem_ref_raw (type
, &parts
);
733 /* Verify that the address is in the simplest possible shape
734 (only a register). If we cannot create such a memory reference,
735 something is really wrong. */
736 gcc_assert (parts
.symbol
== NULL_TREE
);
737 gcc_assert (parts
.index
== NULL_TREE
);
738 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
739 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
743 /* Copies components of the address from OP to ADDR. */
746 get_address_description (tree op
, struct mem_address
*addr
)
748 addr
->symbol
= TMR_SYMBOL (op
);
749 addr
->base
= TMR_BASE (op
);
750 addr
->index
= TMR_INDEX (op
);
751 addr
->step
= TMR_STEP (op
);
752 addr
->offset
= TMR_OFFSET (op
);
755 /* Copies the additional information attached to target_mem_ref FROM to TO. */
758 copy_mem_ref_info (tree to
, tree from
)
760 /* And the info about the original reference. */
761 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
764 /* Move constants in target_mem_ref REF to offset. Returns the new target
765 mem ref if anything changes, NULL_TREE otherwise. */
768 maybe_fold_tmr (tree ref
)
770 struct mem_address addr
;
771 bool changed
= false;
774 get_address_description (ref
, &addr
);
776 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
779 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
781 fold_convert (sizetype
, addr
.base
));
783 addr
.offset
= addr
.base
;
785 addr
.base
= NULL_TREE
;
789 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
794 off
= fold_binary_to_constant (MULT_EXPR
, sizetype
,
796 addr
.step
= NULL_TREE
;
801 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
807 addr
.index
= NULL_TREE
;
814 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
818 copy_mem_ref_info (ret
, ref
);
822 /* Dump PARTS to FILE. */
824 extern void dump_mem_address (FILE *, struct mem_address
*);
826 dump_mem_address (FILE *file
, struct mem_address
*parts
)
830 fprintf (file
, "symbol: ");
831 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
832 fprintf (file
, "\n");
836 fprintf (file
, "base: ");
837 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
838 fprintf (file
, "\n");
842 fprintf (file
, "index: ");
843 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
844 fprintf (file
, "\n");
848 fprintf (file
, "step: ");
849 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
850 fprintf (file
, "\n");
854 fprintf (file
, "offset: ");
855 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
856 fprintf (file
, "\n");
860 #include "gt-tree-ssa-address.h"