1 /* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004, 2006 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
34 #include "diagnostic.h"
35 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "tree-pass.h"
40 #include "tree-inline.h"
41 #include "insn-config.h"
45 #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 struct mem_addr_template
GTY (())
76 rtx ref
; /* The template. */
77 rtx
* GTY ((skip
)) step_p
; /* The point in template where the step should be
79 rtx
* GTY ((skip
)) off_p
; /* The point in template where the offset should
83 /* The templates. Each of the five bits of the index corresponds to one
84 component of TARGET_MEM_REF being present, see TEMPL_IDX. */
86 static GTY (()) struct mem_addr_template templates
[32];
88 #define TEMPL_IDX(SYMBOL, BASE, INDEX, STEP, OFFSET) \
89 (((SYMBOL != 0) << 4) \
90 | ((BASE != 0) << 3) \
91 | ((INDEX != 0) << 2) \
92 | ((STEP != 0) << 1) \
95 /* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
96 STEP and OFFSET to *ADDR. Stores pointers to where step is placed to
97 *STEP_P and offset to *OFFSET_P. */
100 gen_addr_rtx (rtx symbol
, rtx base
, rtx index
, rtx step
, rtx offset
,
101 rtx
*addr
, rtx
**step_p
, rtx
**offset_p
)
116 act_elem
= gen_rtx_MULT (Pmode
, act_elem
, step
);
119 *step_p
= &XEXP (act_elem
, 1);
128 *addr
= gen_rtx_PLUS (Pmode
, *addr
, base
);
138 act_elem
= gen_rtx_PLUS (Pmode
, act_elem
, offset
);
141 *offset_p
= &XEXP (act_elem
, 1);
143 if (GET_CODE (symbol
) == SYMBOL_REF
144 || GET_CODE (symbol
) == LABEL_REF
145 || GET_CODE (symbol
) == CONST
)
146 act_elem
= gen_rtx_CONST (Pmode
, act_elem
);
150 *addr
= gen_rtx_PLUS (Pmode
, *addr
, act_elem
);
158 *addr
= gen_rtx_PLUS (Pmode
, *addr
, offset
);
160 *offset_p
= &XEXP (*addr
, 1);
174 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
175 If REALLY_EXPAND is false, just make fake registers instead
176 of really expanding the operands, and perform the expansion in-place
177 by using one of the "templates". */
180 addr_for_mem_ref (struct mem_address
*addr
, bool really_expand
)
182 rtx address
, sym
, bse
, idx
, st
, off
;
183 static bool templates_initialized
= false;
184 struct mem_addr_template
*templ
;
186 if (addr
->step
&& !integer_onep (addr
->step
))
187 st
= immed_double_const (TREE_INT_CST_LOW (addr
->step
),
188 TREE_INT_CST_HIGH (addr
->step
), Pmode
);
192 if (addr
->offset
&& !integer_zerop (addr
->offset
))
193 off
= immed_double_const (TREE_INT_CST_LOW (addr
->offset
),
194 TREE_INT_CST_HIGH (addr
->offset
), Pmode
);
200 /* Reuse the templates for addresses, so that we do not waste memory. */
201 if (!templates_initialized
)
205 templates_initialized
= true;
206 sym
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup ("test_symbol"));
207 bse
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
208 idx
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
210 for (i
= 0; i
< 32; i
++)
211 gen_addr_rtx ((i
& 16 ? sym
: NULL_RTX
),
212 (i
& 8 ? bse
: NULL_RTX
),
213 (i
& 4 ? idx
: NULL_RTX
),
214 (i
& 2 ? const0_rtx
: NULL_RTX
),
215 (i
& 1 ? const0_rtx
: NULL_RTX
),
217 &templates
[i
].step_p
,
218 &templates
[i
].off_p
);
221 templ
= templates
+ TEMPL_IDX (addr
->symbol
, addr
->base
, addr
->index
,
231 /* Otherwise really expand the expressions. */
233 ? expand_expr (build_addr (addr
->symbol
, current_function_decl
),
234 NULL_RTX
, Pmode
, EXPAND_NORMAL
)
237 ? expand_expr (addr
->base
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
240 ? expand_expr (addr
->index
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
243 gen_addr_rtx (sym
, bse
, idx
, st
, off
, &address
, NULL
, NULL
);
247 /* Returns address of MEM_REF in TYPE. */
250 tree_mem_ref_addr (tree type
, tree mem_ref
)
254 tree step
= TMR_STEP (mem_ref
), offset
= TMR_OFFSET (mem_ref
);
255 tree sym
= TMR_SYMBOL (mem_ref
), base
= TMR_BASE (mem_ref
);
256 tree addr_base
= NULL_TREE
, addr_off
= NULL_TREE
;
259 addr_base
= fold_convert (type
, build_addr (sym
, current_function_decl
));
260 else if (base
&& POINTER_TYPE_P (TREE_TYPE (base
)))
262 addr_base
= fold_convert (type
, base
);
266 act_elem
= TMR_INDEX (mem_ref
);
270 act_elem
= fold_build2 (MULT_EXPR
, sizetype
, act_elem
, step
);
278 addr_off
= fold_build2 (PLUS_EXPR
, sizetype
, addr_off
, act_elem
);
283 if (offset
&& !integer_zerop (offset
))
286 addr_off
= fold_build2 (PLUS_EXPR
, sizetype
, addr_off
, offset
);
293 addr
= fold_convert (type
, addr_off
);
295 addr
= fold_build2 (PLUS_EXPR
, type
, addr_base
, addr
);
300 addr
= build_int_cst (type
, 0);
305 /* Returns true if a memory reference in MODE and with parameters given by
306 ADDR is valid on the current target. */
309 valid_mem_ref_p (enum machine_mode mode
, struct mem_address
*addr
)
313 address
= addr_for_mem_ref (addr
, false);
317 return memory_address_p (mode
, address
);
320 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
321 is valid on the current target and if so, creates and returns the
325 create_mem_ref_raw (tree type
, struct mem_address
*addr
)
327 if (!valid_mem_ref_p (TYPE_MODE (type
), addr
))
330 if (addr
->step
&& integer_onep (addr
->step
))
331 addr
->step
= NULL_TREE
;
333 if (addr
->offset
&& integer_zerop (addr
->offset
))
334 addr
->offset
= NULL_TREE
;
336 return build7 (TARGET_MEM_REF
, type
,
337 addr
->symbol
, addr
->base
, addr
->index
,
338 addr
->step
, addr
->offset
, NULL
, NULL
);
341 /* Returns true if OBJ is an object whose address is a link time constant. */
344 fixed_address_object_p (tree obj
)
346 return (TREE_CODE (obj
) == VAR_DECL
347 && (TREE_STATIC (obj
)
348 || DECL_EXTERNAL (obj
)));
351 /* If ADDR contains an address of object that is a link time constant,
352 move it to PARTS->symbol. */
355 move_fixed_address_to_symbol (struct mem_address
*parts
, aff_tree
*addr
)
358 tree val
= NULL_TREE
;
360 for (i
= 0; i
< addr
->n
; i
++)
362 if (!double_int_one_p (addr
->elts
[i
].coef
))
365 val
= addr
->elts
[i
].val
;
366 if (TREE_CODE (val
) == ADDR_EXPR
367 && fixed_address_object_p (TREE_OPERAND (val
, 0)))
374 parts
->symbol
= TREE_OPERAND (val
, 0);
375 aff_combination_remove_elt (addr
, i
);
378 /* If ADDR contains an address of a dereferenced pointer, move it to
382 move_pointer_to_base (struct mem_address
*parts
, aff_tree
*addr
)
385 tree val
= NULL_TREE
;
387 for (i
= 0; i
< addr
->n
; i
++)
389 if (!double_int_one_p (addr
->elts
[i
].coef
))
392 val
= addr
->elts
[i
].val
;
393 if (POINTER_TYPE_P (TREE_TYPE (val
)))
401 aff_combination_remove_elt (addr
, i
);
404 /* Adds ELT to PARTS. */
407 add_to_parts (struct mem_address
*parts
, tree elt
)
423 /* Add ELT to base. */
424 type
= TREE_TYPE (parts
->base
);
425 parts
->base
= fold_build2 (PLUS_EXPR
, type
,
427 fold_convert (type
, elt
));
430 /* Finds the most expensive multiplication in ADDR that can be
431 expressed in an addressing mode and move the corresponding
432 element(s) to PARTS. */
435 most_expensive_mult_to_index (struct mem_address
*parts
, aff_tree
*addr
)
438 double_int best_mult
, amult
, amult_neg
;
439 unsigned best_mult_cost
= 0, acost
;
440 tree mult_elt
= NULL_TREE
, elt
;
442 enum tree_code op_code
;
444 best_mult
= double_int_zero
;
445 for (i
= 0; i
< addr
->n
; i
++)
447 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
450 /* FIXME: Should use the correct memory mode rather than Pmode. */
452 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
454 || !multiplier_allowed_in_address_p (coef
, Pmode
))
457 acost
= multiply_by_cost (coef
, Pmode
);
459 if (acost
> best_mult_cost
)
461 best_mult_cost
= acost
;
462 best_mult
= addr
->elts
[i
].coef
;
469 /* Collect elements multiplied by best_mult. */
470 for (i
= j
= 0; i
< addr
->n
; i
++)
472 amult
= addr
->elts
[i
].coef
;
473 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
475 if (double_int_equal_p (amult
, best_mult
))
477 else if (double_int_equal_p (amult_neg
, best_mult
))
478 op_code
= MINUS_EXPR
;
481 addr
->elts
[j
] = addr
->elts
[i
];
486 elt
= fold_convert (sizetype
, addr
->elts
[i
].val
);
488 mult_elt
= fold_build2 (op_code
, sizetype
, mult_elt
, elt
);
489 else if (op_code
== PLUS_EXPR
)
492 mult_elt
= fold_build1 (NEGATE_EXPR
, sizetype
, elt
);
496 parts
->index
= mult_elt
;
497 parts
->step
= double_int_to_tree (sizetype
, best_mult
);
500 /* Splits address ADDR into PARTS.
502 TODO -- be more clever about the distribution of the elements of ADDR
503 to PARTS. Some architectures do not support anything but single
504 register in address, possibly with a small integer offset; while
505 create_mem_ref will simplify the address to an acceptable shape
506 later, it would be more efficient to know that asking for complicated
507 addressing modes is useless. */
510 addr_to_parts (aff_tree
*addr
, struct mem_address
*parts
)
515 parts
->symbol
= NULL_TREE
;
516 parts
->base
= NULL_TREE
;
517 parts
->index
= NULL_TREE
;
518 parts
->step
= NULL_TREE
;
520 if (!double_int_zero_p (addr
->offset
))
521 parts
->offset
= double_int_to_tree (sizetype
, addr
->offset
);
523 parts
->offset
= NULL_TREE
;
525 /* Try to find a symbol. */
526 move_fixed_address_to_symbol (parts
, addr
);
528 /* First move the most expensive feasible multiplication
530 most_expensive_mult_to_index (parts
, addr
);
532 /* Try to find a base of the reference. Since at the moment
533 there is no reliable way how to distinguish between pointer and its
534 offset, this is just a guess. */
536 move_pointer_to_base (parts
, addr
);
538 /* Then try to process the remaining elements. */
539 for (i
= 0; i
< addr
->n
; i
++)
541 part
= fold_convert (sizetype
, addr
->elts
[i
].val
);
542 if (!double_int_one_p (addr
->elts
[i
].coef
))
543 part
= fold_build2 (MULT_EXPR
, sizetype
, part
,
544 double_int_to_tree (sizetype
, addr
->elts
[i
].coef
));
545 add_to_parts (parts
, part
);
548 add_to_parts (parts
, fold_convert (sizetype
, addr
->rest
));
551 /* Force the PARTS to register. */
554 gimplify_mem_ref_parts (block_stmt_iterator
*bsi
, struct mem_address
*parts
)
557 parts
->base
= force_gimple_operand_bsi (bsi
, parts
->base
,
560 parts
->index
= force_gimple_operand_bsi (bsi
, parts
->index
,
564 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
565 computations are emitted in front of BSI. TYPE is the mode
566 of created memory reference. */
569 create_mem_ref (block_stmt_iterator
*bsi
, tree type
, aff_tree
*addr
)
572 tree addr_type
= build_pointer_type (type
), atype
;
573 struct mem_address parts
;
575 addr_to_parts (addr
, &parts
);
576 gimplify_mem_ref_parts (bsi
, &parts
);
577 mem_ref
= create_mem_ref_raw (type
, &parts
);
581 /* The expression is too complicated. Try making it simpler. */
583 if (parts
.step
&& !integer_onep (parts
.step
))
585 /* Move the multiplication to index. */
586 gcc_assert (parts
.index
);
587 parts
.index
= force_gimple_operand_bsi (bsi
,
588 fold_build2 (MULT_EXPR
, sizetype
,
589 parts
.index
, parts
.step
),
591 parts
.step
= NULL_TREE
;
593 mem_ref
= create_mem_ref_raw (type
, &parts
);
600 tmp
= fold_convert (addr_type
,
601 build_addr (parts
.symbol
, current_function_decl
));
603 /* Add the symbol to base, eventually forcing it to register. */
607 parts
.base
= force_gimple_operand_bsi (bsi
,
608 fold_build2 (PLUS_EXPR
, addr_type
,
609 fold_convert (addr_type
, parts
.base
),
614 parts
.index
= parts
.base
;
620 parts
.symbol
= NULL_TREE
;
622 mem_ref
= create_mem_ref_raw (type
, &parts
);
629 /* Add index to base. */
632 atype
= TREE_TYPE (parts
.base
);
633 parts
.base
= force_gimple_operand_bsi (bsi
,
634 fold_build2 (PLUS_EXPR
, atype
,
636 fold_convert (atype
, parts
.index
)),
640 parts
.base
= parts
.index
;
641 parts
.index
= NULL_TREE
;
643 mem_ref
= create_mem_ref_raw (type
, &parts
);
648 if (parts
.offset
&& !integer_zerop (parts
.offset
))
650 /* Try adding offset to base. */
653 atype
= TREE_TYPE (parts
.base
);
654 parts
.base
= force_gimple_operand_bsi (bsi
,
655 fold_build2 (PLUS_EXPR
, atype
,
657 fold_convert (atype
, parts
.offset
)),
661 parts
.base
= parts
.offset
;
663 parts
.offset
= NULL_TREE
;
665 mem_ref
= create_mem_ref_raw (type
, &parts
);
670 /* Verify that the address is in the simplest possible shape
671 (only a register). If we cannot create such a memory reference,
672 something is really wrong. */
673 gcc_assert (parts
.symbol
== NULL_TREE
);
674 gcc_assert (parts
.index
== NULL_TREE
);
675 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
676 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
680 /* Copies components of the address from OP to ADDR. */
683 get_address_description (tree op
, struct mem_address
*addr
)
685 addr
->symbol
= TMR_SYMBOL (op
);
686 addr
->base
= TMR_BASE (op
);
687 addr
->index
= TMR_INDEX (op
);
688 addr
->step
= TMR_STEP (op
);
689 addr
->offset
= TMR_OFFSET (op
);
692 /* Copies the additional information attached to target_mem_ref FROM to TO. */
695 copy_mem_ref_info (tree to
, tree from
)
697 /* Copy the annotation, to preserve the aliasing information. */
698 TMR_TAG (to
) = TMR_TAG (from
);
700 /* And the info about the original reference. */
701 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
704 /* Move constants in target_mem_ref REF to offset. Returns the new target
705 mem ref if anything changes, NULL_TREE otherwise. */
708 maybe_fold_tmr (tree ref
)
710 struct mem_address addr
;
711 bool changed
= false;
714 get_address_description (ref
, &addr
);
716 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
719 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
721 fold_convert (sizetype
, addr
.base
));
723 addr
.offset
= addr
.base
;
725 addr
.base
= NULL_TREE
;
729 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
734 off
= fold_binary_to_constant (MULT_EXPR
, sizetype
,
736 addr
.step
= NULL_TREE
;
741 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
747 addr
.index
= NULL_TREE
;
754 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
758 copy_mem_ref_info (ret
, ref
);
762 /* Dump PARTS to FILE. */
764 extern void dump_mem_address (FILE *, struct mem_address
*);
766 dump_mem_address (FILE *file
, struct mem_address
*parts
)
770 fprintf (file
, "symbol: ");
771 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
772 fprintf (file
, "\n");
776 fprintf (file
, "base: ");
777 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
778 fprintf (file
, "\n");
782 fprintf (file
, "index: ");
783 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
784 fprintf (file
, "\n");
788 fprintf (file
, "step: ");
789 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
790 fprintf (file
, "\n");
794 fprintf (file
, "offset: ");
795 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
796 fprintf (file
, "\n");
800 #include "gt-tree-ssa-address.h"