1 /* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004 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_CONST (Pmode
,
139 gen_rtx_PLUS (Pmode
, act_elem
, offset
));
141 *offset_p
= &XEXP (XEXP (act_elem
, 0), 1);
145 *addr
= gen_rtx_PLUS (Pmode
, *addr
, act_elem
);
153 *addr
= gen_rtx_PLUS (Pmode
, *addr
, offset
);
155 *offset_p
= &XEXP (*addr
, 1);
169 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
170 If REALLY_EXPAND is false, just make fake registers instead
171 of really expanding the operands, and perform the expansion in-place
172 by using one of the "templates". */
175 addr_for_mem_ref (struct mem_address
*addr
, bool really_expand
)
177 rtx address
, sym
, bse
, idx
, st
, off
;
178 static bool templates_initialized
= false;
179 struct mem_addr_template
*templ
;
181 if (addr
->step
&& !integer_onep (addr
->step
))
182 st
= immed_double_const (TREE_INT_CST_LOW (addr
->step
),
183 TREE_INT_CST_HIGH (addr
->step
), Pmode
);
187 if (addr
->offset
&& !integer_zerop (addr
->offset
))
188 off
= immed_double_const (TREE_INT_CST_LOW (addr
->offset
),
189 TREE_INT_CST_HIGH (addr
->offset
), Pmode
);
195 /* Reuse the templates for addresses, so that we do not waste memory. */
196 if (!templates_initialized
)
200 templates_initialized
= true;
201 sym
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup ("test_symbol"));
202 bse
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
203 idx
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
205 for (i
= 0; i
< 32; i
++)
206 gen_addr_rtx ((i
& 16 ? sym
: NULL_RTX
),
207 (i
& 8 ? bse
: NULL_RTX
),
208 (i
& 4 ? idx
: NULL_RTX
),
209 (i
& 2 ? const0_rtx
: NULL_RTX
),
210 (i
& 1 ? const0_rtx
: NULL_RTX
),
212 &templates
[i
].step_p
,
213 &templates
[i
].off_p
);
216 templ
= templates
+ TEMPL_IDX (addr
->symbol
, addr
->base
, addr
->index
,
226 /* Otherwise really expand the expressions. */
228 ? expand_expr (build_addr (addr
->symbol
, current_function_decl
),
229 NULL_RTX
, Pmode
, EXPAND_NORMAL
)
232 ? expand_expr (addr
->base
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
235 ? expand_expr (addr
->index
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
238 gen_addr_rtx (sym
, bse
, idx
, st
, off
, &address
, NULL
, NULL
);
242 /* Returns address of MEM_REF in TYPE. */
245 tree_mem_ref_addr (tree type
, tree mem_ref
)
247 tree addr
= NULL_TREE
;
249 tree step
= TMR_STEP (mem_ref
), offset
= TMR_OFFSET (mem_ref
);
251 act_elem
= TMR_INDEX (mem_ref
);
254 act_elem
= fold_convert (type
, act_elem
);
257 act_elem
= fold_build2 (MULT_EXPR
, type
, act_elem
,
258 fold_convert (type
, step
));
262 act_elem
= TMR_BASE (mem_ref
);
265 act_elem
= fold_convert (type
, act_elem
);
268 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
273 act_elem
= TMR_SYMBOL (mem_ref
);
276 act_elem
= fold_convert (type
, build_addr (act_elem
,
277 current_function_decl
));
279 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
284 if (!zero_p (offset
))
286 act_elem
= fold_convert (type
, offset
);
289 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
295 addr
= build_int_cst (type
, 0);
300 /* Returns true if a memory reference in MODE and with parameters given by
301 ADDR is valid on the current target. */
304 valid_mem_ref_p (enum machine_mode mode
, struct mem_address
*addr
)
308 address
= addr_for_mem_ref (addr
, false);
312 return memory_address_p (mode
, address
);
315 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
316 is valid on the current target and if so, creates and returns the
320 create_mem_ref_raw (tree type
, struct mem_address
*addr
)
322 if (!valid_mem_ref_p (TYPE_MODE (type
), addr
))
325 if (addr
->step
&& integer_onep (addr
->step
))
326 addr
->step
= NULL_TREE
;
328 if (addr
->offset
&& zero_p (addr
->offset
))
329 addr
->offset
= NULL_TREE
;
331 return build7 (TARGET_MEM_REF
, type
,
332 addr
->symbol
, addr
->base
, addr
->index
,
333 addr
->step
, addr
->offset
, NULL
, NULL
);
336 /* Returns true if OBJ is an object whose address is a link time constant. */
339 fixed_address_object_p (tree obj
)
341 return (TREE_CODE (obj
) == VAR_DECL
342 && (TREE_STATIC (obj
)
343 || DECL_EXTERNAL (obj
)));
346 /* Adds COEF * ELT to PARTS. TYPE is the type of the address we
350 add_to_parts (struct mem_address
*parts
, tree type
, tree elt
)
353 STRIP_NOPS (elt_core
);
355 /* Check if this is a symbol. */
357 && TREE_CODE (elt_core
) == ADDR_EXPR
358 && fixed_address_object_p (TREE_OPERAND (elt_core
, 0)))
360 parts
->symbol
= TREE_OPERAND (elt_core
, 0);
376 /* Add ELT to base. */
377 parts
->base
= fold_build2 (PLUS_EXPR
, type
, parts
->base
, elt
);
380 /* Finds the most expensive multiplication in ADDR that can be
381 expressed in an addressing mode and move the corresponding
382 element(s) to PARTS. TYPE is the type of the address we
386 most_expensive_mult_to_index (struct mem_address
*parts
, tree type
,
390 double_int best_mult
, amult
, amult_neg
;
391 unsigned best_mult_cost
= 0, acost
;
392 tree mult_elt
= NULL_TREE
, elt
;
394 enum tree_code op_code
;
396 best_mult
= double_int_zero
;
397 for (i
= 0; i
< addr
->n
; i
++)
399 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
402 /* FIXME: Should use the correct memory mode rather than Pmode. */
404 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
406 || !multiplier_allowed_in_address_p (coef
, Pmode
))
409 acost
= multiply_by_cost (coef
, Pmode
);
411 if (acost
> best_mult_cost
)
413 best_mult_cost
= acost
;
414 best_mult
= addr
->elts
[i
].coef
;
421 /* Collect elements multiplied by best_mult. */
422 for (i
= j
= 0; i
< addr
->n
; i
++)
424 amult
= addr
->elts
[i
].coef
;
425 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
427 if (double_int_equal_p (amult
, best_mult
))
429 else if (double_int_equal_p (amult_neg
, best_mult
))
430 op_code
= MINUS_EXPR
;
433 addr
->elts
[j
] = addr
->elts
[i
];
438 elt
= fold_convert (type
, addr
->elts
[i
].val
);
440 mult_elt
= fold_build2 (op_code
, type
, mult_elt
, elt
);
441 else if (op_code
== PLUS_EXPR
)
444 mult_elt
= fold_build1 (NEGATE_EXPR
, type
, elt
);
448 parts
->index
= mult_elt
;
449 parts
->step
= double_int_to_tree (type
, best_mult
);
452 /* Splits address ADDR into PARTS.
454 TODO -- be more clever about the distribution of the elements of ADDR
455 to PARTS. Some architectures do not support anything but single
456 register in address, possibly with a small integer offset; while
457 create_mem_ref will simplify the address to an acceptable shape
458 later, it would be more efficient to know that asking for complicated
459 addressing modes is useless. */
462 addr_to_parts (aff_tree
*addr
, tree type
, struct mem_address
*parts
)
467 parts
->symbol
= NULL_TREE
;
468 parts
->base
= NULL_TREE
;
469 parts
->index
= NULL_TREE
;
470 parts
->step
= NULL_TREE
;
472 if (!double_int_zero_p (addr
->offset
))
473 parts
->offset
= double_int_to_tree (type
, addr
->offset
);
475 parts
->offset
= NULL_TREE
;
477 /* First move the most expensive feasible multiplication
479 most_expensive_mult_to_index (parts
, type
, addr
);
481 /* Then try to process the remaining elements. */
482 for (i
= 0; i
< addr
->n
; i
++)
484 part
= fold_convert (type
, addr
->elts
[i
].val
);
485 if (!double_int_one_p (addr
->elts
[i
].coef
))
486 part
= fold_build2 (MULT_EXPR
, type
, part
,
487 double_int_to_tree (type
, addr
->elts
[i
].coef
));
488 add_to_parts (parts
, type
, part
);
491 add_to_parts (parts
, type
, addr
->rest
);
494 /* Force the PARTS to register. */
497 gimplify_mem_ref_parts (block_stmt_iterator
*bsi
, struct mem_address
*parts
)
500 parts
->base
= force_gimple_operand_bsi (bsi
, parts
->base
,
503 parts
->index
= force_gimple_operand_bsi (bsi
, parts
->index
,
507 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
508 computations are emitted in front of BSI. TYPE is the mode
509 of created memory reference. */
512 create_mem_ref (block_stmt_iterator
*bsi
, tree type
, aff_tree
*addr
)
515 tree addr_type
= build_pointer_type (type
);
516 struct mem_address parts
;
518 addr_to_parts (addr
, addr_type
, &parts
);
519 gimplify_mem_ref_parts (bsi
, &parts
);
520 mem_ref
= create_mem_ref_raw (type
, &parts
);
524 /* The expression is too complicated. Try making it simpler. */
526 if (parts
.step
&& !integer_onep (parts
.step
))
528 /* Move the multiplication to index. */
529 gcc_assert (parts
.index
);
530 parts
.index
= force_gimple_operand_bsi (bsi
,
531 build2 (MULT_EXPR
, addr_type
,
532 parts
.index
, parts
.step
),
534 parts
.step
= NULL_TREE
;
536 mem_ref
= create_mem_ref_raw (type
, &parts
);
543 tmp
= build_addr (parts
.symbol
, current_function_decl
);
545 /* Add the symbol to base, eventually forcing it to register. */
549 parts
.base
= force_gimple_operand_bsi (bsi
,
550 build2 (PLUS_EXPR
, addr_type
,
555 parts
.index
= parts
.base
;
561 parts
.symbol
= NULL_TREE
;
563 mem_ref
= create_mem_ref_raw (type
, &parts
);
570 /* Add base to index. */
572 parts
.index
= force_gimple_operand_bsi (bsi
,
573 build2 (PLUS_EXPR
, addr_type
,
578 parts
.index
= parts
.base
;
579 parts
.base
= NULL_TREE
;
581 mem_ref
= create_mem_ref_raw (type
, &parts
);
586 if (parts
.offset
&& !integer_zerop (parts
.offset
))
588 /* Try adding offset to index. */
590 parts
.index
= force_gimple_operand_bsi (bsi
,
591 build2 (PLUS_EXPR
, addr_type
,
596 parts
.index
= parts
.offset
, bsi
;
598 parts
.offset
= NULL_TREE
;
600 mem_ref
= create_mem_ref_raw (type
, &parts
);
605 /* Verify that the address is in the simplest possible shape
606 (only a register). If we cannot create such a memory reference,
607 something is really wrong. */
608 gcc_assert (parts
.symbol
== NULL_TREE
);
609 gcc_assert (parts
.base
== NULL_TREE
);
610 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
611 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
615 /* Copies components of the address from OP to ADDR. */
618 get_address_description (tree op
, struct mem_address
*addr
)
620 addr
->symbol
= TMR_SYMBOL (op
);
621 addr
->base
= TMR_BASE (op
);
622 addr
->index
= TMR_INDEX (op
);
623 addr
->step
= TMR_STEP (op
);
624 addr
->offset
= TMR_OFFSET (op
);
627 /* Copies the additional information attached to target_mem_ref FROM to TO. */
630 copy_mem_ref_info (tree to
, tree from
)
632 /* Copy the annotation, to preserve the aliasing information. */
633 TMR_TAG (to
) = TMR_TAG (from
);
635 /* And the info about the original reference. */
636 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
639 /* Move constants in target_mem_ref REF to offset. Returns the new target
640 mem ref if anything changes, NULL_TREE otherwise. */
643 maybe_fold_tmr (tree ref
)
645 struct mem_address addr
;
646 bool changed
= false;
649 get_address_description (ref
, &addr
);
651 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
654 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, ptr_type_node
,
655 addr
.offset
, addr
.base
);
657 addr
.offset
= addr
.base
;
659 addr
.base
= NULL_TREE
;
663 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
668 off
= fold_binary_to_constant (MULT_EXPR
, ptr_type_node
,
670 addr
.step
= NULL_TREE
;
675 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, ptr_type_node
,
681 addr
.index
= NULL_TREE
;
688 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
692 copy_mem_ref_info (ret
, ref
);
696 /* Dump PARTS to FILE. */
698 extern void dump_mem_address (FILE *, struct mem_address
*);
700 dump_mem_address (FILE *file
, struct mem_address
*parts
)
704 fprintf (file
, "symbol: ");
705 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
706 fprintf (file
, "\n");
710 fprintf (file
, "base: ");
711 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
712 fprintf (file
, "\n");
716 fprintf (file
, "index: ");
717 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
718 fprintf (file
, "\n");
722 fprintf (file
, "step: ");
723 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
724 fprintf (file
, "\n");
728 fprintf (file
, "offset: ");
729 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
730 fprintf (file
, "\n");
734 #include "gt-tree-ssa-address.h"