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"
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
= gen_rtx_PLUS (Pmode
, *addr
, base
);
137 act_elem
= gen_rtx_CONST (Pmode
,
138 gen_rtx_PLUS (Pmode
, act_elem
, offset
));
140 *offset_p
= &XEXP (XEXP (act_elem
, 0), 1);
144 *addr
= gen_rtx_PLUS (Pmode
, *addr
, act_elem
);
152 *addr
= gen_rtx_PLUS (Pmode
, *addr
, offset
);
154 *offset_p
= &XEXP (*addr
, 1);
168 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
169 If REALLY_EXPAND is false, just make fake registers instead
170 of really expanding the operands, and perform the expansion in-place
171 by using one of the "templates". */
174 addr_for_mem_ref (struct mem_address
*addr
, bool really_expand
)
176 rtx address
, sym
, bse
, idx
, st
, off
;
177 static bool templates_initialized
= false;
178 struct mem_addr_template
*templ
;
180 if (addr
->step
&& !integer_onep (addr
->step
))
181 st
= immed_double_const (TREE_INT_CST_LOW (addr
->step
),
182 TREE_INT_CST_HIGH (addr
->step
), Pmode
);
186 if (addr
->offset
&& !integer_zerop (addr
->offset
))
187 off
= immed_double_const (TREE_INT_CST_LOW (addr
->offset
),
188 TREE_INT_CST_HIGH (addr
->offset
), Pmode
);
194 /* Reuse the templates for addresses, so that we do not waste memory. */
195 if (!templates_initialized
)
199 templates_initialized
= true;
200 sym
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup ("test_symbol"));
201 bse
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
202 idx
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
204 for (i
= 0; i
< 32; i
++)
205 gen_addr_rtx ((i
& 16 ? sym
: NULL_RTX
),
206 (i
& 8 ? bse
: NULL_RTX
),
207 (i
& 4 ? idx
: NULL_RTX
),
208 (i
& 2 ? const0_rtx
: NULL_RTX
),
209 (i
& 1 ? const0_rtx
: NULL_RTX
),
211 &templates
[i
].step_p
,
212 &templates
[i
].off_p
);
215 templ
= templates
+ TEMPL_IDX (addr
->symbol
, addr
->base
, addr
->index
,
225 /* Otherwise really expand the expressions. */
227 ? expand_expr (build_addr (addr
->symbol
, current_function_decl
),
228 NULL_RTX
, Pmode
, EXPAND_NORMAL
)
231 ? expand_expr (addr
->base
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
234 ? expand_expr (addr
->index
, NULL_RTX
, Pmode
, EXPAND_NORMAL
)
237 gen_addr_rtx (sym
, bse
, idx
, st
, off
, &address
, NULL
, NULL
);
241 /* Returns address of MEM_REF in TYPE. */
244 tree_mem_ref_addr (tree type
, tree mem_ref
)
246 tree addr
= NULL_TREE
;
248 tree step
= TMR_STEP (mem_ref
), offset
= TMR_OFFSET (mem_ref
);
250 act_elem
= TMR_INDEX (mem_ref
);
253 act_elem
= fold_convert (type
, act_elem
);
256 act_elem
= fold_build2 (MULT_EXPR
, type
, act_elem
,
257 fold_convert (type
, step
));
261 act_elem
= TMR_BASE (mem_ref
);
264 act_elem
= fold_convert (type
, act_elem
);
267 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
272 act_elem
= TMR_SYMBOL (mem_ref
);
275 act_elem
= fold_convert (type
, build_addr (act_elem
,
276 current_function_decl
));
278 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
283 if (!zero_p (offset
))
285 act_elem
= fold_convert (type
, offset
);
288 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
294 addr
= build_int_cst (type
, 0);
299 /* Returns true if a memory reference in MODE and with parameters given by
300 ADDR is valid on the current target. */
303 valid_mem_ref_p (enum machine_mode mode
, struct mem_address
*addr
)
307 address
= addr_for_mem_ref (addr
, false);
311 return memory_address_p (mode
, address
);
314 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
315 is valid on the current target and if so, creates and returns the
319 create_mem_ref_raw (tree type
, struct mem_address
*addr
)
321 if (!valid_mem_ref_p (TYPE_MODE (type
), addr
))
324 if (addr
->step
&& integer_onep (addr
->step
))
325 addr
->step
= NULL_TREE
;
327 if (addr
->offset
&& zero_p (addr
->offset
))
328 addr
->offset
= NULL_TREE
;
330 return build7 (TARGET_MEM_REF
, type
,
331 addr
->symbol
, addr
->base
, addr
->index
,
332 addr
->step
, addr
->offset
, NULL
, NULL
);
335 /* Returns true if OBJ is an object whose address is a link time constant. */
338 fixed_address_object_p (tree obj
)
340 return (TREE_CODE (obj
) == VAR_DECL
341 && (TREE_STATIC (obj
)
342 || DECL_EXTERNAL (obj
)));
345 /* Adds COEF * ELT to PARTS. TYPE is the type of the address we
349 add_to_parts (struct mem_address
*parts
, tree type
, tree elt
,
350 unsigned HOST_WIDE_INT coef
)
352 /* Check if this is a symbol. */
355 && TREE_CODE (elt
) == ADDR_EXPR
356 && fixed_address_object_p (TREE_OPERAND (elt
, 0)))
358 parts
->symbol
= TREE_OPERAND (elt
, 0);
363 elt
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, elt
),
364 build_int_cst_type (type
, coef
));
366 elt
= fold_convert (type
, elt
);
380 /* Add ELT to base. */
381 parts
->base
= fold_build2 (PLUS_EXPR
, type
, parts
->base
, elt
);
384 /* Finds the most expensive multiplication in ADDR that can be
385 expressed in an addressing mode and move the corresponding
386 element(s) to PARTS. TYPE is the type of the address we
390 most_expensive_mult_to_index (struct mem_address
*parts
, tree type
,
391 struct affine_tree_combination
*addr
)
393 unsigned HOST_WIDE_INT best_mult
= 0;
394 unsigned best_mult_cost
= 0, acost
;
395 tree mult_elt
= NULL_TREE
, elt
;
398 for (i
= 0; i
< addr
->n
; i
++)
400 /* FIXME: Should use the correct memory mode rather than Pmode. */
401 if (addr
->coefs
[i
] == 1
402 || !multiplier_allowed_in_address_p (addr
->coefs
[i
], Pmode
))
405 acost
= multiply_by_cost (addr
->coefs
[i
], Pmode
);
407 if (acost
> best_mult_cost
)
409 best_mult_cost
= acost
;
410 best_mult
= addr
->coefs
[i
];
417 for (i
= j
= 0; i
< addr
->n
; i
++)
419 if (addr
->coefs
[i
] != best_mult
)
421 addr
->coefs
[j
] = addr
->coefs
[i
];
422 addr
->elts
[j
] = addr
->elts
[i
];
427 elt
= fold_convert (type
, addr
->elts
[i
]);
431 mult_elt
= fold_build2 (PLUS_EXPR
, type
, mult_elt
, elt
);
435 parts
->index
= mult_elt
;
436 parts
->step
= build_int_cst_type (type
, best_mult
);
439 /* Splits address ADDR into PARTS.
441 TODO -- be more clever about the distribution of the elements of ADDR
442 to PARTS. Some architectures do not support anything but single
443 register in address, possibly with a small integer offset; while
444 create_mem_ref will simplify the address to an acceptable shape
445 later, it would be a small bit more efficient to know that asking
446 for complicated addressing modes is useless. */
449 addr_to_parts (struct affine_tree_combination
*addr
, tree type
,
450 struct mem_address
*parts
)
454 parts
->symbol
= NULL_TREE
;
455 parts
->base
= NULL_TREE
;
456 parts
->index
= NULL_TREE
;
457 parts
->step
= NULL_TREE
;
460 parts
->offset
= build_int_cst_type (type
, addr
->offset
);
462 parts
->offset
= NULL_TREE
;
464 /* First move the most expensive feasible multiplication
466 most_expensive_mult_to_index (parts
, type
, addr
);
468 /* Then try to process the remaining elements. */
469 for (i
= 0; i
< addr
->n
; i
++)
470 add_to_parts (parts
, type
, addr
->elts
[i
], addr
->coefs
[i
]);
472 add_to_parts (parts
, type
, addr
->rest
, 1);
475 /* Force the PARTS to register. */
478 gimplify_mem_ref_parts (block_stmt_iterator
*bsi
, struct mem_address
*parts
)
481 parts
->base
= force_gimple_operand_bsi (bsi
, parts
->base
,
484 parts
->index
= force_gimple_operand_bsi (bsi
, parts
->index
,
488 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
489 computations are emitted in front of BSI. TYPE is the mode
490 of created memory reference. */
493 create_mem_ref (block_stmt_iterator
*bsi
, tree type
,
494 struct affine_tree_combination
*addr
)
497 tree addr_type
= build_pointer_type (type
);
498 struct mem_address parts
;
500 addr_to_parts (addr
, addr_type
, &parts
);
501 gimplify_mem_ref_parts (bsi
, &parts
);
502 mem_ref
= create_mem_ref_raw (type
, &parts
);
506 /* The expression is too complicated. Try making it simpler. */
508 if (parts
.step
&& !integer_onep (parts
.step
))
510 /* Move the multiplication to index. */
511 gcc_assert (parts
.index
);
512 parts
.index
= force_gimple_operand_bsi (bsi
,
513 build2 (MULT_EXPR
, addr_type
,
514 parts
.index
, parts
.step
),
516 parts
.step
= NULL_TREE
;
518 mem_ref
= create_mem_ref_raw (type
, &parts
);
525 tmp
= build_addr (parts
.symbol
, current_function_decl
);
527 /* Add the symbol to base, eventually forcing it to register. */
531 parts
.base
= force_gimple_operand_bsi (bsi
,
532 build2 (PLUS_EXPR
, addr_type
,
537 parts
.index
= parts
.base
;
543 parts
.symbol
= NULL_TREE
;
545 mem_ref
= create_mem_ref_raw (type
, &parts
);
552 /* Add base to index. */
554 parts
.index
= force_gimple_operand_bsi (bsi
,
555 build2 (PLUS_EXPR
, addr_type
,
560 parts
.index
= parts
.base
;
561 parts
.base
= NULL_TREE
;
563 mem_ref
= create_mem_ref_raw (type
, &parts
);
568 if (parts
.offset
&& !integer_zerop (parts
.offset
))
570 /* Try adding offset to index. */
572 parts
.index
= force_gimple_operand_bsi (bsi
,
573 build2 (PLUS_EXPR
, addr_type
,
578 parts
.index
= parts
.offset
, bsi
;
580 parts
.offset
= NULL_TREE
;
582 mem_ref
= create_mem_ref_raw (type
, &parts
);
587 /* Verify that the address is in the simplest possible shape
588 (only a register). If we cannot create such a memory reference,
589 something is really wrong. */
590 gcc_assert (parts
.symbol
== NULL_TREE
);
591 gcc_assert (parts
.base
== NULL_TREE
);
592 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
593 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
597 /* Copies components of the address from OP to ADDR. */
600 get_address_description (tree op
, struct mem_address
*addr
)
602 addr
->symbol
= TMR_SYMBOL (op
);
603 addr
->base
= TMR_BASE (op
);
604 addr
->index
= TMR_INDEX (op
);
605 addr
->step
= TMR_STEP (op
);
606 addr
->offset
= TMR_OFFSET (op
);
609 /* Copies the additional information attached to target_mem_ref FROM to TO. */
612 copy_mem_ref_info (tree to
, tree from
)
614 /* Copy the annotation, to preserve the aliasing information. */
615 TMR_TAG (to
) = TMR_TAG (from
);
617 /* And the info about the original reference. */
618 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
621 /* Move constants in target_mem_ref REF to offset. Returns the new target
622 mem ref if anything changes, NULL_TREE otherwise. */
625 maybe_fold_tmr (tree ref
)
627 struct mem_address addr
;
628 bool changed
= false;
631 get_address_description (ref
, &addr
);
633 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
636 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, ptr_type_node
,
637 addr
.offset
, addr
.base
);
639 addr
.offset
= addr
.base
;
641 addr
.base
= NULL_TREE
;
645 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
650 off
= fold_binary_to_constant (MULT_EXPR
, ptr_type_node
,
652 addr
.step
= NULL_TREE
;
657 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, ptr_type_node
,
663 addr
.index
= NULL_TREE
;
670 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
674 copy_mem_ref_info (ret
, ref
);
678 /* Dump PARTS to FILE. */
680 extern void dump_mem_address (FILE *, struct mem_address
*);
682 dump_mem_address (FILE *file
, struct mem_address
*parts
)
686 fprintf (file
, "symbol: ");
687 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
688 fprintf (file
, "\n");
692 fprintf (file
, "base: ");
693 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
694 fprintf (file
, "\n");
698 fprintf (file
, "index: ");
699 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
700 fprintf (file
, "\n");
704 fprintf (file
, "step: ");
705 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
706 fprintf (file
, "\n");
710 fprintf (file
, "offset: ");
711 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
712 fprintf (file
, "\n");
716 #include "gt-tree-ssa-address.h"