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"
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_PLUS (Pmode, act_elem, offset);
141 *offset_p = &XEXP (act_elem, 1);
143 if (GET_CODE (symbol) == SYMBOL_REF
144 || GET_CODE (symbol) == LABEL_REF
145 || GET_CODE (symbol) == CONST)
146 act_elem = gen_rtx_CONST (Pmode, act_elem);
150 *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
158 *addr = gen_rtx_PLUS (Pmode, *addr, offset);
160 *offset_p = &XEXP (*addr, 1);
174 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
175 If REALLY_EXPAND is false, just make fake registers instead
176 of really expanding the operands, and perform the expansion in-place
177 by using one of the "templates". */
180 addr_for_mem_ref (struct mem_address *addr, bool really_expand)
182 rtx address, sym, bse, idx, st, off;
183 static bool templates_initialized = false;
184 struct mem_addr_template *templ;
186 if (addr->step && !integer_onep (addr->step))
187 st = immed_double_const (TREE_INT_CST_LOW (addr->step),
188 TREE_INT_CST_HIGH (addr->step), Pmode);
192 if (addr->offset && !integer_zerop (addr->offset))
193 off = immed_double_const (TREE_INT_CST_LOW (addr->offset),
194 TREE_INT_CST_HIGH (addr->offset), Pmode);
200 /* Reuse the templates for addresses, so that we do not waste memory. */
201 if (!templates_initialized)
205 templates_initialized = true;
206 sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup ("test_symbol"));
207 bse = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
208 idx = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
210 for (i = 0; i < 32; i++)
211 gen_addr_rtx ((i & 16 ? sym : NULL_RTX),
212 (i & 8 ? bse : NULL_RTX),
213 (i & 4 ? idx : NULL_RTX),
214 (i & 2 ? const0_rtx : NULL_RTX),
215 (i & 1 ? const0_rtx : NULL_RTX),
217 &templates[i].step_p,
218 &templates[i].off_p);
221 templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
231 /* Otherwise really expand the expressions. */
233 ? expand_expr (build_addr (addr->symbol, current_function_decl),
234 NULL_RTX, Pmode, EXPAND_NORMAL)
237 ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
240 ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
243 gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
247 /* Returns address of MEM_REF in TYPE. */
250 tree_mem_ref_addr (tree type, tree mem_ref)
254 tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
255 tree sym = TMR_SYMBOL (mem_ref), base = TMR_BASE (mem_ref);
256 tree addr_base = NULL_TREE, addr_off = NULL_TREE;
259 addr_base = fold_convert (type, build_addr (sym, current_function_decl));
260 else if (base && POINTER_TYPE_P (TREE_TYPE (base)))
262 addr_base = fold_convert (type, base);
266 act_elem = TMR_INDEX (mem_ref);
270 act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
278 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
283 if (offset && !integer_zerop (offset))
286 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
294 addr = fold_build2 (POINTER_PLUS_EXPR, type, addr_base, addr_off);
296 addr = fold_convert (type, addr_off);
301 addr = build_int_cst (type, 0);
306 /* Returns true if a memory reference in MODE and with parameters given by
307 ADDR is valid on the current target. */
310 valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
314 address = addr_for_mem_ref (addr, false);
318 return memory_address_p (mode, address);
321 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
322 is valid on the current target and if so, creates and returns the
326 create_mem_ref_raw (tree type, struct mem_address *addr)
328 if (!valid_mem_ref_p (TYPE_MODE (type), addr))
331 if (addr->step && integer_onep (addr->step))
332 addr->step = NULL_TREE;
334 if (addr->offset && integer_zerop (addr->offset))
335 addr->offset = NULL_TREE;
337 return build7 (TARGET_MEM_REF, type,
338 addr->symbol, addr->base, addr->index,
339 addr->step, addr->offset, NULL, NULL);
342 /* Returns true if OBJ is an object whose address is a link time constant. */
345 fixed_address_object_p (tree obj)
347 return (TREE_CODE (obj) == VAR_DECL
348 && (TREE_STATIC (obj)
349 || DECL_EXTERNAL (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 (PLUS_EXPR, type,
428 fold_convert (type, 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,
561 parts->index = force_gimple_operand_bsi (bsi, parts->index,
565 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
566 computations are emitted in front of BSI. TYPE is the mode
567 of created memory reference. */
570 create_mem_ref (block_stmt_iterator *bsi, tree type, aff_tree *addr)
574 struct mem_address parts;
576 addr_to_parts (addr, &parts);
577 gimplify_mem_ref_parts (bsi, &parts);
578 mem_ref = create_mem_ref_raw (type, &parts);
582 /* The expression is too complicated. Try making it simpler. */
584 if (parts.step && !integer_onep (parts.step))
586 /* Move the multiplication to index. */
587 gcc_assert (parts.index);
588 parts.index = force_gimple_operand_bsi (bsi,
589 fold_build2 (MULT_EXPR, sizetype,
590 parts.index, parts.step),
592 parts.step = NULL_TREE;
594 mem_ref = create_mem_ref_raw (type, &parts);
601 tmp = build_addr (parts.symbol, current_function_decl);
602 gcc_assert (is_gimple_val (tmp));
604 /* Add the symbol to base, eventually forcing it to register. */
607 gcc_assert (useless_type_conversion_p
608 (sizetype, TREE_TYPE (parts.base)));
612 atype = TREE_TYPE (tmp);
613 parts.base = force_gimple_operand_bsi (bsi,
614 fold_build2 (PLUS_EXPR, atype,
615 fold_convert (atype, parts.base),
621 parts.index = parts.base;
627 parts.symbol = NULL_TREE;
629 mem_ref = create_mem_ref_raw (type, &parts);
636 /* Add index to base. */
639 atype = TREE_TYPE (parts.base);
640 parts.base = force_gimple_operand_bsi (bsi,
641 fold_build2 (PLUS_EXPR, atype,
643 fold_convert (atype, parts.index)),
647 parts.base = parts.index;
648 parts.index = NULL_TREE;
650 mem_ref = create_mem_ref_raw (type, &parts);
655 if (parts.offset && !integer_zerop (parts.offset))
657 /* Try adding offset to base. */
660 atype = TREE_TYPE (parts.base);
661 parts.base = force_gimple_operand_bsi (bsi,
662 fold_build2 (POINTER_PLUS_EXPR, atype,
664 fold_convert (sizetype, parts.offset)),
668 parts.base = parts.offset;
670 parts.offset = NULL_TREE;
672 mem_ref = create_mem_ref_raw (type, &parts);
677 /* Verify that the address is in the simplest possible shape
678 (only a register). If we cannot create such a memory reference,
679 something is really wrong. */
680 gcc_assert (parts.symbol == NULL_TREE);
681 gcc_assert (parts.index == NULL_TREE);
682 gcc_assert (!parts.step || integer_onep (parts.step));
683 gcc_assert (!parts.offset || integer_zerop (parts.offset));
687 /* Copies components of the address from OP to ADDR. */
690 get_address_description (tree op, struct mem_address *addr)
692 addr->symbol = TMR_SYMBOL (op);
693 addr->base = TMR_BASE (op);
694 addr->index = TMR_INDEX (op);
695 addr->step = TMR_STEP (op);
696 addr->offset = TMR_OFFSET (op);
699 /* Copies the additional information attached to target_mem_ref FROM to TO. */
702 copy_mem_ref_info (tree to, tree from)
704 /* Copy the annotation, to preserve the aliasing information. */
705 TMR_TAG (to) = TMR_TAG (from);
707 /* And the info about the original reference. */
708 TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
711 /* Move constants in target_mem_ref REF to offset. Returns the new target
712 mem ref if anything changes, NULL_TREE otherwise. */
715 maybe_fold_tmr (tree ref)
717 struct mem_address addr;
718 bool changed = false;
721 get_address_description (ref, &addr);
723 if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
726 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
728 fold_convert (sizetype, addr.base));
730 addr.offset = addr.base;
732 addr.base = NULL_TREE;
736 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
741 off = fold_binary_to_constant (MULT_EXPR, sizetype,
743 addr.step = NULL_TREE;
748 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
754 addr.index = NULL_TREE;
761 ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
765 copy_mem_ref_info (ret, ref);
769 /* Dump PARTS to FILE. */
771 extern void dump_mem_address (FILE *, struct mem_address *);
773 dump_mem_address (FILE *file, struct mem_address *parts)
777 fprintf (file, "symbol: ");
778 print_generic_expr (file, parts->symbol, TDF_SLIM);
779 fprintf (file, "\n");
783 fprintf (file, "base: ");
784 print_generic_expr (file, parts->base, TDF_SLIM);
785 fprintf (file, "\n");
789 fprintf (file, "index: ");
790 print_generic_expr (file, parts->index, TDF_SLIM);
791 fprintf (file, "\n");
795 fprintf (file, "step: ");
796 print_generic_expr (file, parts->step, TDF_SLIM);
797 fprintf (file, "\n");
801 fprintf (file, "offset: ");
802 print_generic_expr (file, parts->offset, TDF_SLIM);
803 fprintf (file, "\n");
807 #include "gt-tree-ssa-address.h"