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 parts
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
,
428 fold_convert (sizetype
, elt
));
431 /* Finds the most expensive multiplication in ADDR that can be
432 expressed in an addressing mode and move the corresponding
433 element(s) to PARTS. */
436 most_expensive_mult_to_index (struct mem_address
*parts
, aff_tree
*addr
)
439 double_int best_mult
, amult
, amult_neg
;
440 unsigned best_mult_cost
= 0, acost
;
441 tree mult_elt
= NULL_TREE
, elt
;
443 enum tree_code op_code
;
445 best_mult
= double_int_zero
;
446 for (i
= 0; i
< addr
->n
; i
++)
448 if (!double_int_fits_in_shwi_p (addr
->elts
[i
].coef
))
451 /* FIXME: Should use the correct memory mode rather than Pmode. */
453 coef
= double_int_to_shwi (addr
->elts
[i
].coef
);
455 || !multiplier_allowed_in_address_p (coef
, Pmode
))
458 acost
= multiply_by_cost (coef
, Pmode
);
460 if (acost
> best_mult_cost
)
462 best_mult_cost
= acost
;
463 best_mult
= addr
->elts
[i
].coef
;
470 /* Collect elements multiplied by best_mult. */
471 for (i
= j
= 0; i
< addr
->n
; i
++)
473 amult
= addr
->elts
[i
].coef
;
474 amult_neg
= double_int_ext_for_comb (double_int_neg (amult
), addr
);
476 if (double_int_equal_p (amult
, best_mult
))
478 else if (double_int_equal_p (amult_neg
, best_mult
))
479 op_code
= MINUS_EXPR
;
482 addr
->elts
[j
] = addr
->elts
[i
];
487 elt
= fold_convert (sizetype
, addr
->elts
[i
].val
);
489 mult_elt
= fold_build2 (op_code
, sizetype
, mult_elt
, elt
);
490 else if (op_code
== PLUS_EXPR
)
493 mult_elt
= fold_build1 (NEGATE_EXPR
, sizetype
, elt
);
497 parts
->index
= mult_elt
;
498 parts
->step
= double_int_to_tree (sizetype
, best_mult
);
501 /* Splits address ADDR into PARTS.
503 TODO -- be more clever about the distribution of the elements of ADDR
504 to PARTS. Some architectures do not support anything but single
505 register in address, possibly with a small integer offset; while
506 create_mem_ref will simplify the address to an acceptable shape
507 later, it would be more efficient to know that asking for complicated
508 addressing modes is useless. */
511 addr_to_parts (aff_tree
*addr
, struct mem_address
*parts
)
516 parts
->symbol
= NULL_TREE
;
517 parts
->base
= NULL_TREE
;
518 parts
->index
= NULL_TREE
;
519 parts
->step
= NULL_TREE
;
521 if (!double_int_zero_p (addr
->offset
))
522 parts
->offset
= double_int_to_tree (sizetype
, addr
->offset
);
524 parts
->offset
= NULL_TREE
;
526 /* Try to find a symbol. */
527 move_fixed_address_to_symbol (parts
, addr
);
529 /* First move the most expensive feasible multiplication
531 most_expensive_mult_to_index (parts
, addr
);
533 /* Try to find a base of the reference. Since at the moment
534 there is no reliable way how to distinguish between pointer and its
535 offset, this is just a guess. */
537 move_pointer_to_base (parts
, addr
);
539 /* Then try to process the remaining elements. */
540 for (i
= 0; i
< addr
->n
; i
++)
542 part
= fold_convert (sizetype
, addr
->elts
[i
].val
);
543 if (!double_int_one_p (addr
->elts
[i
].coef
))
544 part
= fold_build2 (MULT_EXPR
, sizetype
, part
,
545 double_int_to_tree (sizetype
, addr
->elts
[i
].coef
));
546 add_to_parts (parts
, part
);
549 add_to_parts (parts
, fold_convert (sizetype
, addr
->rest
));
552 /* Force the PARTS to register. */
555 gimplify_mem_ref_parts (block_stmt_iterator
*bsi
, struct mem_address
*parts
)
558 parts
->base
= force_gimple_operand_bsi (bsi
, parts
->base
,
560 true, BSI_SAME_STMT
);
562 parts
->index
= force_gimple_operand_bsi (bsi
, parts
->index
,
564 true, BSI_SAME_STMT
);
567 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
568 computations are emitted in front of BSI. TYPE is the mode
569 of created memory reference. */
572 create_mem_ref (block_stmt_iterator
*bsi
, tree type
, aff_tree
*addr
)
576 struct mem_address parts
;
578 addr_to_parts (addr
, &parts
);
579 gimplify_mem_ref_parts (bsi
, &parts
);
580 mem_ref
= create_mem_ref_raw (type
, &parts
);
584 /* The expression is too complicated. Try making it simpler. */
586 if (parts
.step
&& !integer_onep (parts
.step
))
588 /* Move the multiplication to index. */
589 gcc_assert (parts
.index
);
590 parts
.index
= force_gimple_operand_bsi (bsi
,
591 fold_build2 (MULT_EXPR
, sizetype
,
592 parts
.index
, parts
.step
),
593 true, NULL_TREE
, true, BSI_SAME_STMT
);
594 parts
.step
= NULL_TREE
;
596 mem_ref
= create_mem_ref_raw (type
, &parts
);
603 tmp
= build_addr (parts
.symbol
, current_function_decl
);
604 gcc_assert (is_gimple_val (tmp
));
606 /* Add the symbol to base, eventually forcing it to register. */
609 gcc_assert (useless_type_conversion_p
610 (sizetype
, TREE_TYPE (parts
.base
)));
614 atype
= TREE_TYPE (tmp
);
615 parts
.base
= force_gimple_operand_bsi (bsi
,
616 fold_build2 (PLUS_EXPR
, atype
,
617 fold_convert (atype
, parts
.base
),
619 true, NULL_TREE
, true, BSI_SAME_STMT
);
623 parts
.index
= parts
.base
;
629 parts
.symbol
= NULL_TREE
;
631 mem_ref
= create_mem_ref_raw (type
, &parts
);
638 /* Add index to base. */
641 atype
= TREE_TYPE (parts
.base
);
642 parts
.base
= force_gimple_operand_bsi (bsi
,
643 fold_build2 (POINTER_PLUS_EXPR
, atype
,
646 true, NULL_TREE
, true, BSI_SAME_STMT
);
649 parts
.base
= parts
.index
;
650 parts
.index
= NULL_TREE
;
652 mem_ref
= create_mem_ref_raw (type
, &parts
);
657 if (parts
.offset
&& !integer_zerop (parts
.offset
))
659 /* Try adding offset to base. */
662 atype
= TREE_TYPE (parts
.base
);
663 parts
.base
= force_gimple_operand_bsi (bsi
,
664 fold_build2 (POINTER_PLUS_EXPR
, atype
,
666 fold_convert (sizetype
, parts
.offset
)),
667 true, NULL_TREE
, true, BSI_SAME_STMT
);
670 parts
.base
= parts
.offset
;
672 parts
.offset
= NULL_TREE
;
674 mem_ref
= create_mem_ref_raw (type
, &parts
);
679 /* Verify that the address is in the simplest possible shape
680 (only a register). If we cannot create such a memory reference,
681 something is really wrong. */
682 gcc_assert (parts
.symbol
== NULL_TREE
);
683 gcc_assert (parts
.index
== NULL_TREE
);
684 gcc_assert (!parts
.step
|| integer_onep (parts
.step
));
685 gcc_assert (!parts
.offset
|| integer_zerop (parts
.offset
));
689 /* Copies components of the address from OP to ADDR. */
692 get_address_description (tree op
, struct mem_address
*addr
)
694 addr
->symbol
= TMR_SYMBOL (op
);
695 addr
->base
= TMR_BASE (op
);
696 addr
->index
= TMR_INDEX (op
);
697 addr
->step
= TMR_STEP (op
);
698 addr
->offset
= TMR_OFFSET (op
);
701 /* Copies the additional information attached to target_mem_ref FROM to TO. */
704 copy_mem_ref_info (tree to
, tree from
)
706 /* Copy the annotation, to preserve the aliasing information. */
707 TMR_TAG (to
) = TMR_TAG (from
);
709 /* And the info about the original reference. */
710 TMR_ORIGINAL (to
) = TMR_ORIGINAL (from
);
713 /* Move constants in target_mem_ref REF to offset. Returns the new target
714 mem ref if anything changes, NULL_TREE otherwise. */
717 maybe_fold_tmr (tree ref
)
719 struct mem_address addr
;
720 bool changed
= false;
723 get_address_description (ref
, &addr
);
725 if (addr
.base
&& TREE_CODE (addr
.base
) == INTEGER_CST
)
728 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
730 fold_convert (sizetype
, addr
.base
));
732 addr
.offset
= addr
.base
;
734 addr
.base
= NULL_TREE
;
738 if (addr
.index
&& TREE_CODE (addr
.index
) == INTEGER_CST
)
743 off
= fold_binary_to_constant (MULT_EXPR
, sizetype
,
745 addr
.step
= NULL_TREE
;
750 addr
.offset
= fold_binary_to_constant (PLUS_EXPR
, sizetype
,
756 addr
.index
= NULL_TREE
;
763 ret
= create_mem_ref_raw (TREE_TYPE (ref
), &addr
);
767 copy_mem_ref_info (ret
, ref
);
771 /* Dump PARTS to FILE. */
773 extern void dump_mem_address (FILE *, struct mem_address
*);
775 dump_mem_address (FILE *file
, struct mem_address
*parts
)
779 fprintf (file
, "symbol: ");
780 print_generic_expr (file
, parts
->symbol
, TDF_SLIM
);
781 fprintf (file
, "\n");
785 fprintf (file
, "base: ");
786 print_generic_expr (file
, parts
->base
, TDF_SLIM
);
787 fprintf (file
, "\n");
791 fprintf (file
, "index: ");
792 print_generic_expr (file
, parts
->index
, TDF_SLIM
);
793 fprintf (file
, "\n");
797 fprintf (file
, "step: ");
798 print_generic_expr (file
, parts
->step
, TDF_SLIM
);
799 fprintf (file
, "\n");
803 fprintf (file
, "offset: ");
804 print_generic_expr (file
, parts
->offset
, TDF_SLIM
);
805 fprintf (file
, "\n");
809 #include "gt-tree-ssa-address.h"