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. */
358 gcc_assert (!addr
->symbol
^ !addr
->base
);
360 base
= build_fold_addr_expr (addr
->symbol
);
364 offset
= fold_convert (alias_ptr_type
, addr
->offset
);
366 offset
= build_int_cst (alias_ptr_type
, 0);
367 return fold_build2 (MEM_REF
, type
, base
, offset
);
370 return build6 (TARGET_MEM_REF
, type
,
371 addr
->symbol
, addr
->base
, addr
->index
,
372 addr
->step
, addr
->offset
, NULL
);
375 /* Returns true if OBJ is an object whose address is a link time constant. */
378 fixed_address_object_p (tree obj
)
380 return (TREE_CODE (obj
) == VAR_DECL
381 && (TREE_STATIC (obj
)
382 || DECL_EXTERNAL (obj
))
383 && ! DECL_DLLIMPORT_P (obj
));
386 /* If ADDR contains an address of object that is a link time constant,
387 move it to PARTS->symbol. */
390 move_fixed_address_to_symbol (struct mem_address
*parts
, aff_tree
*addr
)
393 tree val
= NULL_TREE
;
395 for (i
= 0; i
< addr
->n
; i
++)
397 if (!double_int_one_p (addr
->elts
[i
].coef
))
400 val
= addr
->elts
[i
].val
;
401 if (TREE_CODE (val
) == ADDR_EXPR
402 && fixed_address_object_p (TREE_OPERAND (val
, 0)))
409 parts
->symbol
= TREE_OPERAND (val
, 0);
410 aff_combination_remove_elt (addr
, i
);
413 /* If ADDR contains an instance of BASE_HINT, move it to PARTS->base. */
416 move_hint_to_base (tree type
, struct mem_address
*parts
, tree base_hint
,
420 tree val
= NULL_TREE
;
423 for (i
= 0; i
< addr
->n
; i
++)
425 if (!double_int_one_p (addr
->elts
[i
].coef
))
428 val
= addr
->elts
[i
].val
;
429 if (operand_equal_p (val
, base_hint
, 0))
436 /* Cast value to appropriate pointer type. We cannot use a pointer
437 to TYPE directly, as the back-end will assume registers of pointer
438 type are aligned, and just the base itself may not actually be.
439 We use void pointer to the type's address space instead. */
440 qual
= ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (type
));
441 type
= build_qualified_type (void_type_node
, qual
);
442 parts
->base
= fold_convert (build_pointer_type (type
), val
);
443 aff_combination_remove_elt (addr
, i
);
446 /* If ADDR contains an address of a dereferenced pointer, move it to
450 move_pointer_to_base (struct mem_address
*parts
, aff_tree
*addr
)
453 tree val
= NULL_TREE
;
455 for (i
= 0; i
< addr
->n
; i
++)
457 if (!double_int_one_p (addr
->elts
[i
].coef
))
460 val
= addr
->elts
[i
].val
;
461 if (POINTER_TYPE_P (TREE_TYPE (val
)))
469 aff_combination_remove_elt (addr
, i
);
472 /* Adds ELT to PARTS. */
475 add_to_parts (struct mem_address
*parts
, tree elt
)
481 parts
->index
= fold_convert (sizetype
, elt
);
491 /* Add ELT to base. */
492 type
= TREE_TYPE (parts
->base
);
493 if (POINTER_TYPE_P (type
))
494 parts
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
,
496 fold_convert (sizetype
, elt
));
498 parts
->base
= fold_build2 (PLUS_EXPR
, type
,
502 /* Finds the most expensive multiplication in ADDR that can be
503 expressed in an addressing mode and move the corresponding
504 element(s) to PARTS. */
507 most_expensive_mult_to_index (tree type
, struct mem_address
*parts
,
508 aff_tree
*addr
, bool speed
)
510 addr_space_t as
= TYPE_ADDR_SPACE (type
);
511 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
513 double_int best_mult
, amult
, amult_neg
;
514 unsigned best_mult_cost
= 0, acost
;
515 tree mult_elt
= NULL_TREE
, elt
;
517 enum tree_code op_code
;
519 best_mult
= double_int_zero
;
520 for (i
= 0; i
< addr
->n
; i
++)
522 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
525 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
527 || !multiplier_allowed_in_address_p (coef
, TYPE_MODE (type
), as
))
530 acost
= multiply_by_cost (coef
, address_mode
, speed
);
532 if (acost
> best_mult_cost
)
534 best_mult_cost
= acost
;
535 best_mult
= addr
->elts
[i
].coef
;
542 /* Collect elements multiplied by best_mult. */
543 for (i
= j
= 0; i
< addr
->n
; i
++)
545 amult
= addr
->elts
[i
].coef
;
546 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
548 if (double_int_equal_p (amult
, best_mult
))
550 else if (double_int_equal_p (amult_neg
, best_mult
))
551 op_code
= MINUS_EXPR
;
554 addr
->elts
[j
] = addr
->elts
[i
];
559 elt
= fold_convert (sizetype
, addr
->elts
[i
].val
);
561 mult_elt
= fold_build2 (op_code
, sizetype
, mult_elt
, elt
);
562 else if (op_code
== PLUS_EXPR
)
565 mult_elt
= fold_build1 (NEGATE_EXPR
, sizetype
, elt
);
569 parts
->index
= mult_elt
;
570 parts
->step
= double_int_to_tree (sizetype
, best_mult
);
573 /* Splits address ADDR for a memory access of type TYPE into PARTS.
574 If BASE_HINT is non-NULL, it specifies an SSA name to be used
575 preferentially as base of the reference.
577 TODO -- be more clever about the distribution of the elements of ADDR
578 to PARTS. Some architectures do not support anything but single
579 register in address, possibly with a small integer offset; while
580 create_mem_ref will simplify the address to an acceptable shape
581 later, it would be more efficient to know that asking for complicated
582 addressing modes is useless. */
585 addr_to_parts (tree type
, aff_tree
*addr
, tree base_hint
,
586 struct mem_address
*parts
, bool speed
)
591 parts
->symbol
= NULL_TREE
;
592 parts
->base
= NULL_TREE
;
593 parts
->index
= NULL_TREE
;
594 parts
->step
= NULL_TREE
;
596 if (!double_int_zero_p (addr
->offset
))
597 parts
->offset
= double_int_to_tree (sizetype
, addr
->offset
);
599 parts
->offset
= NULL_TREE
;
601 /* Try to find a symbol. */
602 move_fixed_address_to_symbol (parts
, addr
);
604 /* First move the most expensive feasible multiplication
606 most_expensive_mult_to_index (type
, parts
, addr
, speed
);
608 /* Try to find a base of the reference. Since at the moment
609 there is no reliable way how to distinguish between pointer and its
610 offset, this is just a guess. */
611 if (!parts
->symbol
&& base_hint
)
612 move_hint_to_base (type
, parts
, base_hint
, addr
);
613 if (!parts
->symbol
&& !parts
->base
)
614 move_pointer_to_base (parts
, addr
);
616 /* Then try to process the remaining elements. */
617 for (i
= 0; i
< addr
->n
; i
++)
619 part
= fold_convert (sizetype
, addr
->elts
[i
].val
);
620 if (!double_int_one_p (addr
->elts
[i
].coef
))
621 part
= fold_build2 (MULT_EXPR
, sizetype
, part
,
622 double_int_to_tree (sizetype
, addr
->elts
[i
].coef
));
623 add_to_parts (parts
, part
);
626 add_to_parts (parts
, fold_convert (sizetype
, addr
->rest
));
629 /* Force the PARTS to register. */
632 gimplify_mem_ref_parts (gimple_stmt_iterator
*gsi
, struct mem_address
*parts
)
635 parts
->base
= force_gimple_operand_gsi (gsi
, parts
->base
,
637 true, GSI_SAME_STMT
);
639 parts
->index
= force_gimple_operand_gsi (gsi
, parts
->index
,
641 true, GSI_SAME_STMT
);
644 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
645 computations are emitted in front of GSI. TYPE is the mode
646 of created memory reference. */
649 create_mem_ref (gimple_stmt_iterator
*gsi
, tree type
, tree alias_ptr_type
,
650 aff_tree
*addr
, tree base_hint
, bool speed
)
654 struct mem_address parts
;
656 addr_to_parts (type
, addr
, base_hint
, &parts
, speed
);
657 gimplify_mem_ref_parts (gsi
, &parts
);
658 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
662 /* The expression is too complicated. Try making it simpler. */
664 if (parts
.step
&& !integer_onep (parts
.step
))
666 /* Move the multiplication to index. */
667 gcc_assert (parts
.index
);
668 parts
.index
= force_gimple_operand_gsi (gsi
,
669 fold_build2 (MULT_EXPR
, sizetype
,
670 parts
.index
, parts
.step
),
671 true, NULL_TREE
, true, GSI_SAME_STMT
);
672 parts
.step
= NULL_TREE
;
674 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
681 tmp
= build_addr (parts
.symbol
, current_function_decl
);
682 gcc_assert (is_gimple_val (tmp
));
684 /* Add the symbol to base, eventually forcing it to register. */
687 gcc_assert (useless_type_conversion_p
688 (sizetype
, TREE_TYPE (parts
.base
)));
692 atype
= TREE_TYPE (tmp
);
693 parts
.base
= force_gimple_operand_gsi (gsi
,
694 fold_build2 (POINTER_PLUS_EXPR
, atype
,
696 fold_convert (sizetype
, parts
.base
)),
697 true, NULL_TREE
, true, GSI_SAME_STMT
);
701 parts
.index
= parts
.base
;
707 parts
.symbol
= NULL_TREE
;
709 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
716 /* Add index to base. */
719 atype
= TREE_TYPE (parts
.base
);
720 parts
.base
= force_gimple_operand_gsi (gsi
,
721 fold_build2 (POINTER_PLUS_EXPR
, atype
,
724 true, NULL_TREE
, true, GSI_SAME_STMT
);
727 parts
.base
= parts
.index
;
728 parts
.index
= NULL_TREE
;
730 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
735 if (parts
.offset
&& !integer_zerop (parts
.offset
))
737 /* Try adding offset to base. */
740 atype
= TREE_TYPE (parts
.base
);
741 parts
.base
= force_gimple_operand_gsi (gsi
,
742 fold_build2 (POINTER_PLUS_EXPR
, atype
,
744 fold_convert (sizetype
, parts
.offset
)),
745 true, NULL_TREE
, true, GSI_SAME_STMT
);
748 parts
.base
= parts
.offset
;
750 parts
.offset
= NULL_TREE
;
752 mem_ref
= create_mem_ref_raw (type
, alias_ptr_type
, &parts
);
757 /* Verify that the address is in the simplest possible shape
758 (only a register). If we cannot create such a memory reference,
759 something is really wrong. */
760 gcc_assert (parts
.symbol
== NULL_TREE
);
761 gcc_assert (parts
.index
== NULL_TREE
);
762 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
763 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
767 /* Copies components of the address from OP to ADDR. */
770 get_address_description (tree op
, struct mem_address
*addr
)
772 addr
->symbol
= TMR_SYMBOL (op
);
773 addr
->base
= TMR_BASE (op
);
774 addr
->index
= TMR_INDEX (op
);
775 addr
->step
= TMR_STEP (op
);
776 addr
->offset
= TMR_OFFSET (op
);
779 /* Copies the additional information attached to target_mem_ref FROM to TO. */
782 copy_mem_ref_info (tree to
, tree from
)
784 /* And the info about the original reference. */
785 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
786 TREE_SIDE_EFFECTS (to
) = TREE_SIDE_EFFECTS (from
);
787 TREE_THIS_VOLATILE (to
) = TREE_THIS_VOLATILE (from
);
790 /* Move constants in target_mem_ref REF to offset. Returns the new target
791 mem ref if anything changes, NULL_TREE otherwise. */
794 maybe_fold_tmr (tree ref
)
796 struct mem_address addr
;
797 bool changed
= false;
800 get_address_description (ref
, &addr
);
802 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
805 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
807 fold_convert (sizetype
, addr
.base
));
809 addr
.offset
= addr
.base
;
811 addr
.base
= NULL_TREE
;
815 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
820 off
= fold_binary_to_constant (MULT_EXPR
, sizetype
,
822 addr
.step
= NULL_TREE
;
827 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
833 addr
.index
= NULL_TREE
;
840 ret
= create_mem_ref_raw (TREE_TYPE (ref
), NULL_TREE
, &addr
);
844 copy_mem_ref_info (ret
, ref
);
848 /* Dump PARTS to FILE. */
850 extern void dump_mem_address (FILE *, struct mem_address
*);
852 dump_mem_address (FILE *file
, struct mem_address
*parts
)
856 fprintf (file
, "symbol: ");
857 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
858 fprintf (file
, "\n");
862 fprintf (file
, "base: ");
863 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
864 fprintf (file
, "\n");
868 fprintf (file
, "index: ");
869 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
870 fprintf (file
, "\n");
874 fprintf (file
, "step: ");
875 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
876 fprintf (file
, "\n");
880 fprintf (file
, "offset: ");
881 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
882 fprintf (file
, "\n");
886 #include "gt-tree-ssa-address.h"