1 /* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004, 2006, 2007 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"
46 /* TODO -- handling of symbols (according to Richard Hendersons
47 comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
49 There are at least 5 different kinds of symbols that we can run up against:
51 (1) binds_local_p, small data area.
52 (2) binds_local_p, eg local statics
53 (3) !binds_local_p, eg global variables
54 (4) thread local, local_exec
55 (5) thread local, !local_exec
57 Now, (1) won't appear often in an array context, but it certainly can.
58 All you have to do is set -GN high enough, or explicitly mark any
59 random object __attribute__((section (".sdata"))).
61 All of these affect whether or not a symbol is in fact a valid address.
62 The only one tested here is (3). And that result may very well
63 be incorrect for (4) or (5).
65 An incorrect result here does not cause incorrect results out the
66 back end, because the expander in expr.c validizes the address. However
67 it would be nice to improve the handling here in order to produce more
70 /* A "template" for memory address, used to determine whether the address is
73 struct mem_addr_template
GTY (())
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 /* The templates. Each of the five bits of the index corresponds to one
83 component of TARGET_MEM_REF being present, see TEMPL_IDX. */
85 static GTY (()) struct mem_addr_template templates
[32];
87 #define TEMPL_IDX(SYMBOL, BASE, INDEX, STEP, OFFSET) \
88 (((SYMBOL != 0) << 4) \
89 | ((BASE != 0) << 3) \
90 | ((INDEX != 0) << 2) \
91 | ((STEP != 0) << 1) \
94 /* Stores address for memory reference with parameters SYMBOL, BASE, INDEX,
95 STEP and OFFSET to *ADDR. Stores pointers to where step is placed to
96 *STEP_P and offset to *OFFSET_P. */
99 gen_addr_rtx (rtx symbol
, rtx base
, rtx index
, rtx step
, rtx offset
,
100 rtx
*addr
, rtx
**step_p
, rtx
**offset_p
)
115 act_elem
= gen_rtx_MULT (Pmode
, act_elem
, step
);
118 *step_p
= &XEXP (act_elem
, 1);
127 *addr
= simplify_gen_binary (PLUS
, Pmode
, base
, *addr
);
137 act_elem
= gen_rtx_PLUS (Pmode
, act_elem
, offset
);
140 *offset_p
= &XEXP (act_elem
, 1);
142 if (GET_CODE (symbol
) == SYMBOL_REF
143 || GET_CODE (symbol
) == LABEL_REF
144 || GET_CODE (symbol
) == CONST
)
145 act_elem
= gen_rtx_CONST (Pmode
, act_elem
);
149 *addr
= gen_rtx_PLUS (Pmode
, *addr
, act_elem
);
157 *addr
= gen_rtx_PLUS (Pmode
, *addr
, offset
);
159 *offset_p
= &XEXP (*addr
, 1);
173 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
174 If REALLY_EXPAND is false, just make fake registers instead
175 of really expanding the operands, and perform the expansion in-place
176 by using one of the "templates". */
179 addr_for_mem_ref (struct mem_address
*addr
, bool really_expand
)
181 rtx address
, sym
, bse
, idx
, st
, off
;
182 static bool templates_initialized
= false;
183 struct mem_addr_template
*templ
;
185 if (addr
->step
&& !integer_onep (addr
->step
))
186 st
= immed_double_const (TREE_INT_CST_LOW (addr
->step
),
187 TREE_INT_CST_HIGH (addr
->step
), Pmode
);
191 if (addr
->offset
&& !integer_zerop (addr
->offset
))
192 off
= immed_double_const (TREE_INT_CST_LOW (addr
->offset
),
193 TREE_INT_CST_HIGH (addr
->offset
), Pmode
);
199 /* Reuse the templates for addresses, so that we do not waste memory. */
200 if (!templates_initialized
)
204 templates_initialized
= true;
205 sym
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup ("test_symbol"));
206 bse
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
207 idx
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
209 for (i
= 0; i
< 32; i
++)
210 gen_addr_rtx ((i
& 16 ? sym
: NULL_RTX
),
211 (i
& 8 ? bse
: NULL_RTX
),
212 (i
& 4 ? idx
: NULL_RTX
),
213 (i
& 2 ? const0_rtx
: NULL_RTX
),
214 (i
& 1 ? const0_rtx
: NULL_RTX
),
216 &templates
[i
].step_p
,
217 &templates
[i
].off_p
);
220 templ
= templates
+ TEMPL_IDX (addr
->symbol
, addr
->base
, addr
->index
,
230 /* Otherwise really expand the expressions. */
232 ? expand_expr (build_addr (addr
->symbol
, current_function_decl
),
233 NULL_RTX
, Pmode
, EXPAND_NORMAL
)
236 ? expand_expr (addr
->base
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
239 ? expand_expr (addr
->index
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
242 gen_addr_rtx (sym
, bse
, idx
, st
, off
, &address
, NULL
, NULL
);
246 /* Returns address of MEM_REF in TYPE. */
249 tree_mem_ref_addr (tree type
, tree mem_ref
)
253 tree step
= TMR_STEP (mem_ref
), offset
= TMR_OFFSET (mem_ref
);
254 tree sym
= TMR_SYMBOL (mem_ref
), base
= TMR_BASE (mem_ref
);
255 tree addr_base
= NULL_TREE
, addr_off
= NULL_TREE
;
258 addr_base
= fold_convert (type
, build_addr (sym
, current_function_decl
));
259 else if (base
&& POINTER_TYPE_P (TREE_TYPE (base
)))
261 addr_base
= fold_convert (type
, base
);
265 act_elem
= TMR_INDEX (mem_ref
);
269 act_elem
= fold_build2 (MULT_EXPR
, sizetype
, act_elem
, step
);
277 addr_off
= fold_build2 (PLUS_EXPR
, sizetype
, addr_off
, act_elem
);
282 if (offset
&& !integer_zerop (offset
))
285 addr_off
= fold_build2 (PLUS_EXPR
, sizetype
, addr_off
, offset
);
293 addr
= fold_build2 (POINTER_PLUS_EXPR
, type
, addr_base
, addr_off
);
295 addr
= fold_convert (type
, addr_off
);
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
))
349 && ! DECL_DLLIMPORT_P (obj
));
352 /* If ADDR contains an address of object that is a link time constant,
353 move it to PARTS->symbol. */
356 move_fixed_address_to_symbol (struct mem_address
*parts
, aff_tree
*addr
)
359 tree val
= NULL_TREE
;
361 for (i
= 0; i
< addr
->n
; i
++)
363 if (!double_int_one_p (addr
->elts
[i
].coef
))
366 val
= addr
->elts
[i
].val
;
367 if (TREE_CODE (val
) == ADDR_EXPR
368 && fixed_address_object_p (TREE_OPERAND (val
, 0)))
375 parts
->symbol
= TREE_OPERAND (val
, 0);
376 aff_combination_remove_elt (addr
, i
);
379 /* If ADDR contains an address of a dereferenced pointer, move it to
383 move_pointer_to_base (struct mem_address
*parts
, aff_tree
*addr
)
386 tree val
= NULL_TREE
;
388 for (i
= 0; i
< addr
->n
; i
++)
390 if (!double_int_one_p (addr
->elts
[i
].coef
))
393 val
= addr
->elts
[i
].val
;
394 if (POINTER_TYPE_P (TREE_TYPE (val
)))
402 aff_combination_remove_elt (addr
, i
);
405 /* Adds ELT to PARTS. */
408 add_to_parts (struct mem_address
*parts
, tree elt
)
414 parts
->index
= fold_convert (sizetype
, elt
);
424 /* Add ELT to base. */
425 type
= TREE_TYPE (parts
->base
);
426 if (POINTER_TYPE_P (type
))
427 parts
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
,
429 fold_convert (sizetype
, elt
));
431 parts
->base
= fold_build2 (PLUS_EXPR
, type
,
435 /* Finds the most expensive multiplication in ADDR that can be
436 expressed in an addressing mode and move the corresponding
437 element(s) to PARTS. */
440 most_expensive_mult_to_index (struct mem_address
*parts
, aff_tree
*addr
)
443 double_int best_mult
, amult
, amult_neg
;
444 unsigned best_mult_cost
= 0, acost
;
445 tree mult_elt
= NULL_TREE
, elt
;
447 enum tree_code op_code
;
449 best_mult
= double_int_zero
;
450 for (i
= 0; i
< addr
->n
; i
++)
452 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
455 /* FIXME: Should use the correct memory mode rather than Pmode. */
457 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
459 || !multiplier_allowed_in_address_p (coef
, Pmode
))
462 acost
= multiply_by_cost (coef
, Pmode
);
464 if (acost
> best_mult_cost
)
466 best_mult_cost
= acost
;
467 best_mult
= addr
->elts
[i
].coef
;
474 /* Collect elements multiplied by best_mult. */
475 for (i
= j
= 0; i
< addr
->n
; i
++)
477 amult
= addr
->elts
[i
].coef
;
478 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
480 if (double_int_equal_p (amult
, best_mult
))
482 else if (double_int_equal_p (amult_neg
, best_mult
))
483 op_code
= MINUS_EXPR
;
486 addr
->elts
[j
] = addr
->elts
[i
];
491 elt
= fold_convert (sizetype
, addr
->elts
[i
].val
);
493 mult_elt
= fold_build2 (op_code
, sizetype
, mult_elt
, elt
);
494 else if (op_code
== PLUS_EXPR
)
497 mult_elt
= fold_build1 (NEGATE_EXPR
, sizetype
, elt
);
501 parts
->index
= mult_elt
;
502 parts
->step
= double_int_to_tree (sizetype
, best_mult
);
505 /* Splits address ADDR into PARTS.
507 TODO -- be more clever about the distribution of the elements of ADDR
508 to PARTS. Some architectures do not support anything but single
509 register in address, possibly with a small integer offset; while
510 create_mem_ref will simplify the address to an acceptable shape
511 later, it would be more efficient to know that asking for complicated
512 addressing modes is useless. */
515 addr_to_parts (aff_tree
*addr
, struct mem_address
*parts
)
520 parts
->symbol
= NULL_TREE
;
521 parts
->base
= NULL_TREE
;
522 parts
->index
= NULL_TREE
;
523 parts
->step
= NULL_TREE
;
525 if (!double_int_zero_p (addr
->offset
))
526 parts
->offset
= double_int_to_tree (sizetype
, addr
->offset
);
528 parts
->offset
= NULL_TREE
;
530 /* Try to find a symbol. */
531 move_fixed_address_to_symbol (parts
, addr
);
533 /* First move the most expensive feasible multiplication
535 most_expensive_mult_to_index (parts
, addr
);
537 /* Try to find a base of the reference. Since at the moment
538 there is no reliable way how to distinguish between pointer and its
539 offset, this is just a guess. */
541 move_pointer_to_base (parts
, addr
);
543 /* Then try to process the remaining elements. */
544 for (i
= 0; i
< addr
->n
; i
++)
546 part
= fold_convert (sizetype
, addr
->elts
[i
].val
);
547 if (!double_int_one_p (addr
->elts
[i
].coef
))
548 part
= fold_build2 (MULT_EXPR
, sizetype
, part
,
549 double_int_to_tree (sizetype
, addr
->elts
[i
].coef
));
550 add_to_parts (parts
, part
);
553 add_to_parts (parts
, fold_convert (sizetype
, addr
->rest
));
556 /* Force the PARTS to register. */
559 gimplify_mem_ref_parts (block_stmt_iterator
*bsi
, struct mem_address
*parts
)
562 parts
->base
= force_gimple_operand_bsi (bsi
, parts
->base
,
564 true, BSI_SAME_STMT
);
566 parts
->index
= force_gimple_operand_bsi (bsi
, parts
->index
,
568 true, BSI_SAME_STMT
);
571 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
572 computations are emitted in front of BSI. TYPE is the mode
573 of created memory reference. */
576 create_mem_ref (block_stmt_iterator
*bsi
, tree type
, aff_tree
*addr
)
580 struct mem_address parts
;
582 addr_to_parts (addr
, &parts
);
583 gimplify_mem_ref_parts (bsi
, &parts
);
584 mem_ref
= create_mem_ref_raw (type
, &parts
);
588 /* The expression is too complicated. Try making it simpler. */
590 if (parts
.step
&& !integer_onep (parts
.step
))
592 /* Move the multiplication to index. */
593 gcc_assert (parts
.index
);
594 parts
.index
= force_gimple_operand_bsi (bsi
,
595 fold_build2 (MULT_EXPR
, sizetype
,
596 parts
.index
, parts
.step
),
597 true, NULL_TREE
, true, BSI_SAME_STMT
);
598 parts
.step
= NULL_TREE
;
600 mem_ref
= create_mem_ref_raw (type
, &parts
);
607 tmp
= build_addr (parts
.symbol
, current_function_decl
);
608 gcc_assert (is_gimple_val (tmp
));
610 /* Add the symbol to base, eventually forcing it to register. */
613 gcc_assert (useless_type_conversion_p
614 (sizetype
, TREE_TYPE (parts
.base
)));
618 atype
= TREE_TYPE (tmp
);
619 parts
.base
= force_gimple_operand_bsi (bsi
,
620 fold_build2 (PLUS_EXPR
, atype
,
621 fold_convert (atype
, parts
.base
),
623 true, NULL_TREE
, true, BSI_SAME_STMT
);
627 parts
.index
= parts
.base
;
633 parts
.symbol
= NULL_TREE
;
635 mem_ref
= create_mem_ref_raw (type
, &parts
);
642 /* Add index to base. */
645 atype
= TREE_TYPE (parts
.base
);
646 parts
.base
= force_gimple_operand_bsi (bsi
,
647 fold_build2 (POINTER_PLUS_EXPR
, atype
,
650 true, NULL_TREE
, true, BSI_SAME_STMT
);
653 parts
.base
= parts
.index
;
654 parts
.index
= NULL_TREE
;
656 mem_ref
= create_mem_ref_raw (type
, &parts
);
661 if (parts
.offset
&& !integer_zerop (parts
.offset
))
663 /* Try adding offset to base. */
666 atype
= TREE_TYPE (parts
.base
);
667 parts
.base
= force_gimple_operand_bsi (bsi
,
668 fold_build2 (POINTER_PLUS_EXPR
, atype
,
670 fold_convert (sizetype
, parts
.offset
)),
671 true, NULL_TREE
, true, BSI_SAME_STMT
);
674 parts
.base
= parts
.offset
;
676 parts
.offset
= NULL_TREE
;
678 mem_ref
= create_mem_ref_raw (type
, &parts
);
683 /* Verify that the address is in the simplest possible shape
684 (only a register). If we cannot create such a memory reference,
685 something is really wrong. */
686 gcc_assert (parts
.symbol
== NULL_TREE
);
687 gcc_assert (parts
.index
== NULL_TREE
);
688 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
689 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
693 /* Copies components of the address from OP to ADDR. */
696 get_address_description (tree op
, struct mem_address
*addr
)
698 addr
->symbol
= TMR_SYMBOL (op
);
699 addr
->base
= TMR_BASE (op
);
700 addr
->index
= TMR_INDEX (op
);
701 addr
->step
= TMR_STEP (op
);
702 addr
->offset
= TMR_OFFSET (op
);
705 /* Copies the additional information attached to target_mem_ref FROM to TO. */
708 copy_mem_ref_info (tree to
, tree from
)
710 /* Copy the annotation, to preserve the aliasing information. */
711 TMR_TAG (to
) = TMR_TAG (from
);
713 /* And the info about the original reference. */
714 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
717 /* Move constants in target_mem_ref REF to offset. Returns the new target
718 mem ref if anything changes, NULL_TREE otherwise. */
721 maybe_fold_tmr (tree ref
)
723 struct mem_address addr
;
724 bool changed
= false;
727 get_address_description (ref
, &addr
);
729 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
732 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
734 fold_convert (sizetype
, addr
.base
));
736 addr
.offset
= addr
.base
;
738 addr
.base
= NULL_TREE
;
742 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
747 off
= fold_binary_to_constant (MULT_EXPR
, sizetype
,
749 addr
.step
= NULL_TREE
;
754 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
760 addr
.index
= NULL_TREE
;
767 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
771 copy_mem_ref_info (ret
, ref
);
775 /* Dump PARTS to FILE. */
777 extern void dump_mem_address (FILE *, struct mem_address
*);
779 dump_mem_address (FILE *file
, struct mem_address
*parts
)
783 fprintf (file
, "symbol: ");
784 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
785 fprintf (file
, "\n");
789 fprintf (file
, "base: ");
790 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
791 fprintf (file
, "\n");
795 fprintf (file
, "index: ");
796 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
797 fprintf (file
, "\n");
801 fprintf (file
, "step: ");
802 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
803 fprintf (file
, "\n");
807 fprintf (file
, "offset: ");
808 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
809 fprintf (file
, "\n");
813 #include "gt-tree-ssa-address.h"