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"
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_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
)
251 tree addr
= NULL_TREE
;
253 tree step
= TMR_STEP (mem_ref
), offset
= TMR_OFFSET (mem_ref
);
255 act_elem
= TMR_INDEX (mem_ref
);
258 act_elem
= fold_convert (type
, act_elem
);
261 act_elem
= fold_build2 (MULT_EXPR
, type
, act_elem
,
262 fold_convert (type
, step
));
266 act_elem
= TMR_BASE (mem_ref
);
269 act_elem
= fold_convert (type
, act_elem
);
272 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
277 act_elem
= TMR_SYMBOL (mem_ref
);
280 act_elem
= fold_convert (type
, build_addr (act_elem
,
281 current_function_decl
));
283 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
288 if (!zero_p (offset
))
290 act_elem
= fold_convert (type
, offset
);
293 addr
= fold_build2 (PLUS_EXPR
, type
, addr
, act_elem
);
299 addr
= build_int_cst (type
, 0);
304 /* Returns true if a memory reference in MODE and with parameters given by
305 ADDR is valid on the current target. */
308 valid_mem_ref_p (enum machine_mode mode
, struct mem_address
*addr
)
312 address
= addr_for_mem_ref (addr
, false);
316 return memory_address_p (mode
, address
);
319 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
320 is valid on the current target and if so, creates and returns the
324 create_mem_ref_raw (tree type
, struct mem_address
*addr
)
326 if (!valid_mem_ref_p (TYPE_MODE (type
), addr
))
329 if (addr
->step
&& integer_onep (addr
->step
))
330 addr
->step
= NULL_TREE
;
332 if (addr
->offset
&& zero_p (addr
->offset
))
333 addr
->offset
= NULL_TREE
;
335 return build7 (TARGET_MEM_REF
, type
,
336 addr
->symbol
, addr
->base
, addr
->index
,
337 addr
->step
, addr
->offset
, NULL
, NULL
);
340 /* Returns true if OBJ is an object whose address is a link time constant. */
343 fixed_address_object_p (tree obj
)
345 return (TREE_CODE (obj
) == VAR_DECL
346 && (TREE_STATIC (obj
)
347 || DECL_EXTERNAL (obj
)));
350 /* Adds COEF * ELT to PARTS. TYPE is the type of the address we
354 add_to_parts (struct mem_address
*parts
, tree type
, tree elt
,
355 unsigned HOST_WIDE_INT coef
)
357 /* Check if this is a symbol. */
360 && TREE_CODE (elt
) == ADDR_EXPR
361 && fixed_address_object_p (TREE_OPERAND (elt
, 0)))
363 parts
->symbol
= TREE_OPERAND (elt
, 0);
368 elt
= fold_build2 (MULT_EXPR
, type
, fold_convert (type
, elt
),
369 build_int_cst_type (type
, coef
));
371 elt
= fold_convert (type
, elt
);
385 /* Add ELT to base. */
386 parts
->base
= fold_build2 (PLUS_EXPR
, type
, parts
->base
, elt
);
389 /* Finds the most expensive multiplication in ADDR that can be
390 expressed in an addressing mode and move the corresponding
391 element(s) to PARTS. TYPE is the type of the address we
395 most_expensive_mult_to_index (struct mem_address
*parts
, tree type
,
396 struct affine_tree_combination
*addr
)
398 unsigned HOST_WIDE_INT best_mult
= 0;
399 unsigned best_mult_cost
= 0, acost
;
400 tree mult_elt
= NULL_TREE
, elt
;
403 for (i
= 0; i
< addr
->n
; i
++)
405 if (addr
->coefs
[i
] == 1
406 || !multiplier_allowed_in_address_p (addr
->coefs
[i
]))
409 acost
= multiply_by_cost (addr
->coefs
[i
], Pmode
);
411 if (acost
> best_mult_cost
)
413 best_mult_cost
= acost
;
414 best_mult
= addr
->coefs
[i
];
421 for (i
= j
= 0; i
< addr
->n
; i
++)
423 if (addr
->coefs
[i
] != best_mult
)
425 addr
->coefs
[j
] = addr
->coefs
[i
];
426 addr
->elts
[j
] = addr
->elts
[i
];
431 elt
= fold_convert (type
, addr
->elts
[i
]);
435 mult_elt
= fold_build2 (PLUS_EXPR
, type
, mult_elt
, elt
);
439 parts
->index
= mult_elt
;
440 parts
->step
= build_int_cst_type (type
, best_mult
);
443 /* Splits address ADDR into PARTS.
445 TODO -- be more clever about the distribution of the elements of ADDR
446 to PARTS. Some architectures do not support anything but single
447 register in address, possibly with a small integer offset; while
448 create_mem_ref will simplify the address to an acceptable shape
449 later, it would be a small bit more efficient to know that asking
450 for complicated addressing modes is useless. */
453 addr_to_parts (struct affine_tree_combination
*addr
, tree type
,
454 struct mem_address
*parts
)
458 parts
->symbol
= NULL_TREE
;
459 parts
->base
= NULL_TREE
;
460 parts
->index
= NULL_TREE
;
461 parts
->step
= NULL_TREE
;
464 parts
->offset
= build_int_cst_type (type
, addr
->offset
);
466 parts
->offset
= NULL_TREE
;
468 /* First move the most expensive feasible multiplication
470 most_expensive_mult_to_index (parts
, type
, addr
);
472 /* Then try to process the remaining elements. */
473 for (i
= 0; i
< addr
->n
; i
++)
474 add_to_parts (parts
, type
, addr
->elts
[i
], addr
->coefs
[i
]);
476 add_to_parts (parts
, type
, addr
->rest
, 1);
479 /* Force the PARTS to register. */
482 gimplify_mem_ref_parts (block_stmt_iterator
*bsi
, struct mem_address
*parts
)
485 parts
->base
= force_gimple_operand_bsi (bsi
, parts
->base
,
488 parts
->index
= force_gimple_operand_bsi (bsi
, parts
->index
,
492 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
493 computations are emitted in front of BSI. TYPE is the mode
494 of created memory reference. */
497 create_mem_ref (block_stmt_iterator
*bsi
, tree type
,
498 struct affine_tree_combination
*addr
)
501 tree addr_type
= build_pointer_type (type
);
502 struct mem_address parts
;
504 addr_to_parts (addr
, addr_type
, &parts
);
505 gimplify_mem_ref_parts (bsi
, &parts
);
506 mem_ref
= create_mem_ref_raw (type
, &parts
);
510 /* The expression is too complicated. Try making it simpler. */
512 if (parts
.step
&& !integer_onep (parts
.step
))
514 /* Move the multiplication to index. */
515 gcc_assert (parts
.index
);
516 parts
.index
= force_gimple_operand_bsi (bsi
,
517 build2 (MULT_EXPR
, addr_type
,
518 parts
.index
, parts
.step
),
520 parts
.step
= NULL_TREE
;
522 mem_ref
= create_mem_ref_raw (type
, &parts
);
529 tmp
= build_addr (parts
.symbol
, current_function_decl
);
531 /* Add the symbol to base, eventually forcing it to register. */
535 parts
.base
= force_gimple_operand_bsi (bsi
,
536 build2 (PLUS_EXPR
, addr_type
,
541 parts
.index
= parts
.base
;
547 parts
.symbol
= NULL_TREE
;
549 mem_ref
= create_mem_ref_raw (type
, &parts
);
556 /* Add base to index. */
558 parts
.index
= force_gimple_operand_bsi (bsi
,
559 build2 (PLUS_EXPR
, addr_type
,
564 parts
.index
= parts
.base
;
565 parts
.base
= NULL_TREE
;
567 mem_ref
= create_mem_ref_raw (type
, &parts
);
572 if (parts
.offset
&& !integer_zerop (parts
.offset
))
574 /* Try adding offset to index. */
576 parts
.index
= force_gimple_operand_bsi (bsi
,
577 build2 (PLUS_EXPR
, addr_type
,
582 parts
.index
= parts
.offset
, bsi
;
584 parts
.offset
= NULL_TREE
;
586 mem_ref
= create_mem_ref_raw (type
, &parts
);
591 /* Verify that the address is in the simplest possible shape
592 (only a register). If we cannot create such a memory reference,
593 something is really wrong. */
594 gcc_assert (parts
.symbol
== NULL_TREE
);
595 gcc_assert (parts
.base
== NULL_TREE
);
596 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
597 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
601 /* Copies components of the address from OP to ADDR. */
604 get_address_description (tree op
, struct mem_address
*addr
)
606 addr
->symbol
= TMR_SYMBOL (op
);
607 addr
->base
= TMR_BASE (op
);
608 addr
->index
= TMR_INDEX (op
);
609 addr
->step
= TMR_STEP (op
);
610 addr
->offset
= TMR_OFFSET (op
);
613 /* Copies the additional information attached to target_mem_ref FROM to TO. */
616 copy_mem_ref_info (tree to
, tree from
)
618 /* Copy the annotation, to preserve the aliasing information. */
619 TMR_TAG (to
) = TMR_TAG (from
);
621 /* And the info about the original reference. */
622 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
625 /* Move constants in target_mem_ref REF to offset. Returns the new target
626 mem ref if anything changes, NULL_TREE otherwise. */
629 maybe_fold_tmr (tree ref
)
631 struct mem_address addr
;
632 bool changed
= false;
635 get_address_description (ref
, &addr
);
637 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
640 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, ptr_type_node
,
641 addr
.offset
, addr
.base
);
643 addr
.offset
= addr
.base
;
645 addr
.base
= NULL_TREE
;
649 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
654 off
= fold_binary_to_constant (MULT_EXPR
, ptr_type_node
,
656 addr
.step
= NULL_TREE
;
661 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, ptr_type_node
,
667 addr
.index
= NULL_TREE
;
674 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
678 copy_mem_ref_info (ret
, ref
);
682 /* Dump PARTS to FILE. */
684 extern void dump_mem_address (FILE *, struct mem_address
*);
686 dump_mem_address (FILE *file
, struct mem_address
*parts
)
690 fprintf (file
, "symbol: ");
691 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
692 fprintf (file
, "\n");
696 fprintf (file
, "base: ");
697 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
698 fprintf (file
, "\n");
702 fprintf (file
, "index: ");
703 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
704 fprintf (file
, "\n");
708 fprintf (file
, "step: ");
709 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
710 fprintf (file
, "\n");
714 fprintf (file
, "offset: ");
715 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
716 fprintf (file
, "\n");
720 #include "gt-tree-ssa-address.h"