1 /* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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
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
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/>. */
21 /* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
22 that directly map to addressing modes of the target. */
26 #include "coretypes.h"
30 #include "basic-block.h"
32 #include "tree-pretty-print.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
35 #include "tree-pass.h"
38 #include "tree-inline.h"
39 #include "tree-affine.h"
41 /* FIXME: We compute address costs using RTL. */
42 #include "insn-config.h"
49 /* TODO -- handling of symbols (according to Richard Hendersons
50 comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
52 There are at least 5 different kinds of symbols that we can run up against:
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
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"))).
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).
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
73 /* A "template" for memory address, used to determine whether the address is
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
80 rtx
* GTY ((skip
)) off_p
; /* The point in template where the offset should
84 DEF_VEC_O (mem_addr_template
);
85 DEF_VEC_ALLOC_O (mem_addr_template
, gc
);
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. */
91 static GTY(()) VEC (mem_addr_template
, gc
) *mem_addr_template_list
;
93 #define TEMPL_IDX(AS, SYMBOL, BASE, INDEX, STEP, OFFSET) \
95 | ((SYMBOL != 0) << 4) \
96 | ((BASE != 0) << 3) \
97 | ((INDEX != 0) << 2) \
98 | ((STEP != 0) << 1) \
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. */
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
)
123 act_elem
= gen_rtx_MULT (address_mode
, act_elem
, step
);
126 *step_p
= &XEXP (act_elem
, 1);
135 *addr
= simplify_gen_binary (PLUS
, address_mode
, base
, *addr
);
145 act_elem
= gen_rtx_PLUS (address_mode
, act_elem
, offset
);
148 *offset_p
= &XEXP (act_elem
, 1);
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
);
157 *addr
= gen_rtx_PLUS (address_mode
, *addr
, act_elem
);
165 *addr
= gen_rtx_PLUS (address_mode
, *addr
, offset
);
167 *offset_p
= &XEXP (*addr
, 1);
181 /* Returns address for TARGET_MEM_REF with parameters given by ADDR
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". */
188 addr_for_mem_ref (struct mem_address
*addr
, addr_space_t as
,
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
;
195 if (addr
->step
&& !integer_onep (addr
->step
))
196 st
= immed_double_int_const (tree_to_double_int (addr
->step
), address_mode
);
200 if (addr
->offset
&& !integer_zerop (addr
->offset
))
201 off
= immed_double_int_const (tree_to_double_int (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
, tree alias_ptr_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 /* If possible use a plain MEM_REF instead of a TARGET_MEM_REF. */
356 && (!addr
->base
|| POINTER_TYPE_P (TREE_TYPE (addr
->base
))))
359 gcc_assert (!addr
->symbol
^ !addr
->base
);
361 base
= build_fold_addr_expr (addr
->symbol
);
365 offset
= fold_convert (alias_ptr_type
, addr
->offset
);
367 offset
= build_int_cst (alias_ptr_type
, 0);
368 return fold_build2 (MEM_REF
, type
, base
, offset
);
371 return build6 (TARGET_MEM_REF
, type
,
372 addr
->symbol
, addr
->base
, addr
->index
,
373 addr
->step
, addr
->offset
, NULL
);
376 /* Returns true if OBJ is an object whose address is a link time constant. */
379 fixed_address_object_p (tree obj
)
381 return (TREE_CODE (obj
) == VAR_DECL
382 && (TREE_STATIC (obj
)
383 || DECL_EXTERNAL (obj
))
384 && ! DECL_DLLIMPORT_P (obj
));
387 /* If ADDR contains an address of object that is a link time constant,
388 move it to PARTS->symbol. */
391 move_fixed_address_to_symbol (struct mem_address
*parts
, aff_tree
*addr
)
394 tree val
= NULL_TREE
;
396 for (i
= 0; i
< addr
->n
; i
++)
398 if (!double_int_one_p (addr
->elts
[i
].coef
))
401 val
= addr
->elts
[i
].val
;
402 if (TREE_CODE (val
) == ADDR_EXPR
403 && fixed_address_object_p (TREE_OPERAND (val
, 0)))
410 parts
->symbol
= TREE_OPERAND (val
, 0);
411 aff_combination_remove_elt (addr
, i
);
414 /* If ADDR contains an instance of BASE_HINT, move it to PARTS->base. */
417 move_hint_to_base (tree type
, struct mem_address
*parts
, tree base_hint
,
421 tree val
= NULL_TREE
;
424 for (i
= 0; i
< addr
->n
; i
++)
426 if (!double_int_one_p (addr
->elts
[i
].coef
))
429 val
= addr
->elts
[i
].val
;
430 if (operand_equal_p (val
, base_hint
, 0))
437 /* Cast value to appropriate pointer type. We cannot use a pointer
438 to TYPE directly, as the back-end will assume registers of pointer
439 type are aligned, and just the base itself may not actually be.
440 We use void pointer to the type's address space instead. */
441 qual
= ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (type
));
442 type
= build_qualified_type (void_type_node
, qual
);
443 parts
->base
= fold_convert (build_pointer_type (type
), val
);
444 aff_combination_remove_elt (addr
, i
);
447 /* If ADDR contains an address of a dereferenced pointer, move it to
451 move_pointer_to_base (struct mem_address
*parts
, aff_tree
*addr
)
454 tree val
= NULL_TREE
;
456 for (i
= 0; i
< addr
->n
; i
++)
458 if (!double_int_one_p (addr
->elts
[i
].coef
))
461 val
= addr
->elts
[i
].val
;
462 if (POINTER_TYPE_P (TREE_TYPE (val
)))
470 aff_combination_remove_elt (addr
, i
);
473 /* Adds ELT to PARTS. */
476 add_to_parts (struct mem_address
*parts
, tree elt
)
482 parts
->index
= fold_convert (sizetype
, elt
);
492 /* Add ELT to base. */
493 type
= TREE_TYPE (parts
->base
);
494 if (POINTER_TYPE_P (type
))
495 parts
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
,
497 fold_convert (sizetype
, elt
));
499 parts
->base
= fold_build2 (PLUS_EXPR
, type
,
503 /* Finds the most expensive multiplication in ADDR that can be
504 expressed in an addressing mode and move the corresponding
505 element(s) to PARTS. */
508 most_expensive_mult_to_index (tree type
, struct mem_address
*parts
,
509 aff_tree
*addr
, bool speed
)
511 addr_space_t as
= TYPE_ADDR_SPACE (type
);
512 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
514 double_int best_mult
, amult
, amult_neg
;
515 unsigned best_mult_cost
= 0, acost
;
516 tree mult_elt
= NULL_TREE
, elt
;
518 enum tree_code op_code
;
520 best_mult
= double_int_zero
;
521 for (i
= 0; i
< addr
->n
; i
++)
523 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
526 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
528 || !multiplier_allowed_in_address_p (coef
, TYPE_MODE (type
), as
))
531 acost
= multiply_by_cost (coef
, address_mode
, speed
);
533 if (acost
> best_mult_cost
)
535 best_mult_cost
= acost
;
536 best_mult
= addr
->elts
[i
].coef
;
543 /* Collect elements multiplied by best_mult. */
544 for (i
= j
= 0; i
< addr
->n
; i
++)
546 amult
= addr
->elts
[i
].coef
;
547 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
549 if (double_int_equal_p (amult
, best_mult
))
551 else if (double_int_equal_p (amult_neg
, best_mult
))
552 op_code
= MINUS_EXPR
;
555 addr
->elts
[j
] = addr
->elts
[i
];
560 elt
= fold_convert (sizetype
, addr
->elts
[i
].val
);
562 mult_elt
= fold_build2 (op_code
, sizetype
, mult_elt
, elt
);
563 else if (op_code
== PLUS_EXPR
)
566 mult_elt
= fold_build1 (NEGATE_EXPR
, sizetype
, elt
);
570 parts
->index
= mult_elt
;
571 parts
->step
= double_int_to_tree (sizetype
, best_mult
);
574 /* Splits address ADDR for a memory access of type TYPE into PARTS.
575 If BASE_HINT is non-NULL, it specifies an SSA name to be used
576 preferentially as base of the reference.
578 TODO -- be more clever about the distribution of the elements of ADDR
579 to PARTS. Some architectures do not support anything but single
580 register in address, possibly with a small integer offset; while
581 create_mem_ref will simplify the address to an acceptable shape
582 later, it would be more efficient to know that asking for complicated
583 addressing modes is useless. */
586 addr_to_parts (tree type
, aff_tree
*addr
, tree base_hint
,
587 struct mem_address
*parts
, bool speed
)
592 parts
->symbol
= NULL_TREE
;
593 parts
->base
= NULL_TREE
;
594 parts
->index
= NULL_TREE
;
595 parts
->step
= NULL_TREE
;
597 if (!double_int_zero_p (addr
->offset
))
598 parts
->offset
= double_int_to_tree (sizetype
, addr
->offset
);
600 parts
->offset
= NULL_TREE
;
602 /* Try to find a symbol. */
603 move_fixed_address_to_symbol (parts
, addr
);
605 /* First move the most expensive feasible multiplication
607 most_expensive_mult_to_index (type
, parts
, addr
, speed
);
609 /* Try to find a base of the reference. Since at the moment
610 there is no reliable way how to distinguish between pointer and its
611 offset, this is just a guess. */
612 if (!parts
->symbol
&& base_hint
)
613 move_hint_to_base (type
, parts
, base_hint
, addr
);
614 if (!parts
->symbol
&& !parts
->base
)
615 move_pointer_to_base (parts
, addr
);
617 /* Then try to process the remaining elements. */
618 for (i
= 0; i
< addr
->n
; i
++)
620 part
= fold_convert (sizetype
, addr
->elts
[i
].val
);
621 if (!double_int_one_p (addr
->elts
[i
].coef
))
622 part
= fold_build2 (MULT_EXPR
, sizetype
, part
,
623 double_int_to_tree (sizetype
, addr
->elts
[i
].coef
));
624 add_to_parts (parts
, part
);
627 add_to_parts (parts
, fold_convert (sizetype
, addr
->rest
));
630 /* Force the PARTS to register. */
633 gimplify_mem_ref_parts (gimple_stmt_iterator
*gsi
, struct mem_address
*parts
)
636 parts
->base
= force_gimple_operand_gsi (gsi
, parts
->base
,
638 true, GSI_SAME_STMT
);
640 parts
->index
= force_gimple_operand_gsi (gsi
, parts
->index
,
642 true, GSI_SAME_STMT
);
645 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
646 computations are emitted in front of GSI. TYPE is the mode
647 of created memory reference. */
650 create_mem_ref (gimple_stmt_iterator
*gsi
, tree type
, tree alias_ptr_type
,
651 aff_tree
*addr
, tree base_hint
, bool speed
)
655 struct mem_address parts
;
657 addr_to_parts (type
, addr
, base_hint
, &parts
, speed
);
658 gimplify_mem_ref_parts (gsi
, &parts
);
659 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
663 /* The expression is too complicated. Try making it simpler. */
665 if (parts
.step
&& !integer_onep (parts
.step
))
667 /* Move the multiplication to index. */
668 gcc_assert (parts
.index
);
669 parts
.index
= force_gimple_operand_gsi (gsi
,
670 fold_build2 (MULT_EXPR
, sizetype
,
671 parts
.index
, parts
.step
),
672 true, NULL_TREE
, true, GSI_SAME_STMT
);
673 parts
.step
= NULL_TREE
;
675 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
682 tmp
= build_addr (parts
.symbol
, current_function_decl
);
683 gcc_assert (is_gimple_val (tmp
));
685 /* Add the symbol to base, eventually forcing it to register. */
688 gcc_assert (useless_type_conversion_p
689 (sizetype
, TREE_TYPE (parts
.base
)));
693 atype
= TREE_TYPE (tmp
);
694 parts
.base
= force_gimple_operand_gsi (gsi
,
695 fold_build2 (POINTER_PLUS_EXPR
, atype
,
697 fold_convert (sizetype
, parts
.base
)),
698 true, NULL_TREE
, true, GSI_SAME_STMT
);
702 parts
.index
= parts
.base
;
708 parts
.symbol
= NULL_TREE
;
710 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
717 /* Add index to base. */
720 atype
= TREE_TYPE (parts
.base
);
721 parts
.base
= force_gimple_operand_gsi (gsi
,
722 fold_build2 (POINTER_PLUS_EXPR
, atype
,
725 true, NULL_TREE
, true, GSI_SAME_STMT
);
728 parts
.base
= parts
.index
;
729 parts
.index
= NULL_TREE
;
731 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
736 if (parts
.offset
&& !integer_zerop (parts
.offset
))
738 /* Try adding offset to base. */
741 atype
= TREE_TYPE (parts
.base
);
742 parts
.base
= force_gimple_operand_gsi (gsi
,
743 fold_build2 (POINTER_PLUS_EXPR
, atype
,
745 fold_convert (sizetype
, parts
.offset
)),
746 true, NULL_TREE
, true, GSI_SAME_STMT
);
749 parts
.base
= parts
.offset
;
751 parts
.offset
= NULL_TREE
;
753 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
758 /* Verify that the address is in the simplest possible shape
759 (only a register). If we cannot create such a memory reference,
760 something is really wrong. */
761 gcc_assert (parts
.symbol
== NULL_TREE
);
762 gcc_assert (parts
.index
== NULL_TREE
);
763 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
764 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
768 /* Copies components of the address from OP to ADDR. */
771 get_address_description (tree op
, struct mem_address
*addr
)
773 addr
->symbol
= TMR_SYMBOL (op
);
774 addr
->base
= TMR_BASE (op
);
775 addr
->index
= TMR_INDEX (op
);
776 addr
->step
= TMR_STEP (op
);
777 addr
->offset
= TMR_OFFSET (op
);
780 /* Copies the additional information attached to target_mem_ref FROM to TO. */
783 copy_mem_ref_info (tree to
, tree from
)
785 /* And the info about the original reference. */
786 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
787 TREE_SIDE_EFFECTS (to
) = TREE_SIDE_EFFECTS (from
);
788 TREE_THIS_VOLATILE (to
) = TREE_THIS_VOLATILE (from
);
791 /* Move constants in target_mem_ref REF to offset. Returns the new target
792 mem ref if anything changes, NULL_TREE otherwise. */
795 maybe_fold_tmr (tree ref
)
797 struct mem_address addr
;
798 bool changed
= false;
801 get_address_description (ref
, &addr
);
803 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
806 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
808 fold_convert (sizetype
, addr
.base
));
810 addr
.offset
= addr
.base
;
812 addr
.base
= NULL_TREE
;
816 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
821 off
= fold_binary_to_constant (MULT_EXPR
, sizetype
,
823 addr
.step
= NULL_TREE
;
828 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
834 addr
.index
= NULL_TREE
;
841 ret
= create_mem_ref_raw (TREE_TYPE (ref
), NULL_TREE
, &addr
);
845 copy_mem_ref_info (ret
, ref
);
849 /* Dump PARTS to FILE. */
851 extern void dump_mem_address (FILE *, struct mem_address
*);
853 dump_mem_address (FILE *file
, struct mem_address
*parts
)
857 fprintf (file
, "symbol: ");
858 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
859 fprintf (file
, "\n");
863 fprintf (file
, "base: ");
864 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
865 fprintf (file
, "\n");
869 fprintf (file
, "index: ");
870 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
871 fprintf (file
, "\n");
875 fprintf (file
, "step: ");
876 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
877 fprintf (file
, "\n");
881 fprintf (file
, "offset: ");
882 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
883 fprintf (file
, "\n");
887 #include "gt-tree-ssa-address.h"