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)
248 tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
249 tree sym = TMR_SYMBOL (mem_ref), base = TMR_BASE (mem_ref);
250 tree addr_base = NULL_TREE, addr_off = NULL_TREE;
253 addr_base = fold_convert (type, build_addr (sym, current_function_decl));
254 else if (base && POINTER_TYPE_P (TREE_TYPE (base)))
256 addr_base = fold_convert (type, base);
260 act_elem = TMR_INDEX (mem_ref);
264 act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
272 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
277 if (!zero_p (offset))
280 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
287 addr = fold_convert (type, addr_off);
289 addr = fold_build2 (PLUS_EXPR, type, addr_base, addr);
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 /* Remove M-th element from COMB. */
348 aff_combination_remove_elt (struct affine_tree_combination *comb, unsigned m)
353 comb->coefs[m] = comb->coefs[comb->n];
354 comb->elts[m] = comb->elts[comb->n];
358 comb->coefs[comb->n] = 1;
359 comb->elts[comb->n] = comb->rest;
360 comb->rest = NULL_TREE;
365 /* If ADDR contains an address of object that is a link time constant,
366 move it to PARTS->symbol. */
369 move_fixed_address_to_symbol (struct mem_address *parts,
370 struct affine_tree_combination *addr)
373 tree val = NULL_TREE;
375 for (i = 0; i < addr->n; i++)
377 if (addr->coefs[i] != 1)
381 if (TREE_CODE (val) == ADDR_EXPR
382 && fixed_address_object_p (TREE_OPERAND (val, 0)))
389 parts->symbol = TREE_OPERAND (val, 0);
390 aff_combination_remove_elt (addr, i);
393 /* If ADDR contains an address of a dereferenced pointer, move it to
397 move_pointer_to_base (struct mem_address *parts,
398 struct affine_tree_combination *addr)
401 tree val = NULL_TREE;
403 for (i = 0; i < addr->n; i++)
405 if (addr->coefs[i] != 1)
409 if (POINTER_TYPE_P (TREE_TYPE (val)))
417 aff_combination_remove_elt (addr, i);
420 /* Adds ELT to PARTS. */
423 add_to_parts (struct mem_address *parts, tree elt)
439 /* Add ELT to base. */
440 type = TREE_TYPE (parts->base);
441 parts->base = fold_build2 (PLUS_EXPR, type,
443 fold_convert (type, elt));
446 /* Finds the most expensive multiplication in ADDR that can be
447 expressed in an addressing mode and move the corresponding
448 element(s) to PARTS. */
451 most_expensive_mult_to_index (struct mem_address *parts,
452 struct affine_tree_combination *addr)
454 unsigned HOST_WIDE_INT best_mult = 0;
455 unsigned best_mult_cost = 0, acost;
456 tree mult_elt = NULL_TREE, elt;
459 for (i = 0; i < addr->n; i++)
461 if (addr->coefs[i] == 1
462 || !multiplier_allowed_in_address_p (addr->coefs[i]))
465 acost = multiply_by_cost (addr->coefs[i], Pmode);
467 if (acost > best_mult_cost)
469 best_mult_cost = acost;
470 best_mult = addr->coefs[i];
477 for (i = j = 0; i < addr->n; i++)
479 if (addr->coefs[i] != best_mult)
481 addr->coefs[j] = addr->coefs[i];
482 addr->elts[j] = addr->elts[i];
487 elt = fold_convert (sizetype, addr->elts[i]);
491 mult_elt = fold_build2 (PLUS_EXPR, sizetype, mult_elt, elt);
495 parts->index = mult_elt;
496 parts->step = build_int_cst_type (sizetype, best_mult);
499 /* Splits address ADDR into PARTS.
501 TODO -- be more clever about the distribution of the elements of ADDR
502 to PARTS. Some architectures do not support anything but single
503 register in address, possibly with a small integer offset; while
504 create_mem_ref will simplify the address to an acceptable shape
505 later, it would be a small bit more efficient to know that asking
506 for complicated addressing modes is useless. */
509 addr_to_parts (struct affine_tree_combination *addr, struct mem_address *parts)
514 parts->symbol = NULL_TREE;
515 parts->base = NULL_TREE;
516 parts->index = NULL_TREE;
517 parts->step = NULL_TREE;
520 parts->offset = build_int_cst_type (sizetype, addr->offset);
522 parts->offset = NULL_TREE;
524 /* Try to find a symbol. */
525 move_fixed_address_to_symbol (parts, addr);
527 /* First move the most expensive feasible multiplication
529 most_expensive_mult_to_index (parts, addr);
531 /* Try to find a base of the reference. Since at the moment
532 there is no reliable way how to distinguish between pointer and its
533 offset, this is just a guess. */
535 move_pointer_to_base (parts, addr);
537 /* Then try to process the remaining elements. */
538 for (i = 0; i < addr->n; i++)
540 part = fold_convert (sizetype, addr->elts[i]);
541 if (addr->coefs[i] != 1)
542 part = fold_build2 (MULT_EXPR, sizetype, part,
543 build_int_cst_type (sizetype, addr->coefs[i]));
544 add_to_parts (parts, part);
547 add_to_parts (parts, fold_convert (sizetype, addr->rest));
550 /* Force the PARTS to register. */
553 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
556 parts->base = force_gimple_operand_bsi (bsi, parts->base,
559 parts->index = force_gimple_operand_bsi (bsi, parts->index,
563 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
564 computations are emitted in front of BSI. TYPE is the mode
565 of created memory reference. */
568 create_mem_ref (block_stmt_iterator *bsi, tree type,
569 struct affine_tree_combination *addr)
572 tree addr_type = build_pointer_type (type), atype;
573 struct mem_address parts;
575 addr_to_parts (addr, &parts);
576 gimplify_mem_ref_parts (bsi, &parts);
577 mem_ref = create_mem_ref_raw (type, &parts);
581 /* The expression is too complicated. Try making it simpler. */
583 if (parts.step && !integer_onep (parts.step))
585 /* Move the multiplication to index. */
586 gcc_assert (parts.index);
587 parts.index = force_gimple_operand_bsi (bsi,
588 fold_build2 (MULT_EXPR, sizetype,
589 parts.index, parts.step),
591 parts.step = NULL_TREE;
593 mem_ref = create_mem_ref_raw (type, &parts);
600 tmp = fold_convert (addr_type,
601 build_addr (parts.symbol, current_function_decl));
603 /* Add the symbol to base, eventually forcing it to register. */
607 parts.base = force_gimple_operand_bsi (bsi,
608 fold_build2 (PLUS_EXPR, addr_type,
609 fold_convert (addr_type, parts.base),
614 parts.index = parts.base;
620 parts.symbol = NULL_TREE;
622 mem_ref = create_mem_ref_raw (type, &parts);
629 /* Add index to base. */
632 atype = TREE_TYPE (parts.base);
633 parts.base = force_gimple_operand_bsi (bsi,
634 fold_build2 (PLUS_EXPR, atype,
636 fold_convert (atype, parts.index)),
640 parts.base = parts.index;
641 parts.index = NULL_TREE;
643 mem_ref = create_mem_ref_raw (type, &parts);
648 if (parts.offset && !integer_zerop (parts.offset))
650 /* Try adding offset to base. */
653 atype = TREE_TYPE (parts.base);
654 parts.base = force_gimple_operand_bsi (bsi,
655 fold_build2 (PLUS_EXPR, atype,
657 fold_convert (atype, parts.offset)),
661 parts.base = parts.offset;
663 parts.offset = NULL_TREE;
665 mem_ref = create_mem_ref_raw (type, &parts);
670 /* Verify that the address is in the simplest possible shape
671 (only a register). If we cannot create such a memory reference,
672 something is really wrong. */
673 gcc_assert (parts.symbol == NULL_TREE);
674 gcc_assert (parts.index == NULL_TREE);
675 gcc_assert (!parts.step || integer_onep (parts.step));
676 gcc_assert (!parts.offset || integer_zerop (parts.offset));
680 /* Copies components of the address from OP to ADDR. */
683 get_address_description (tree op, struct mem_address *addr)
685 addr->symbol = TMR_SYMBOL (op);
686 addr->base = TMR_BASE (op);
687 addr->index = TMR_INDEX (op);
688 addr->step = TMR_STEP (op);
689 addr->offset = TMR_OFFSET (op);
692 /* Copies the additional information attached to target_mem_ref FROM to TO. */
695 copy_mem_ref_info (tree to, tree from)
697 /* Copy the annotation, to preserve the aliasing information. */
698 TMR_TAG (to) = TMR_TAG (from);
700 /* And the info about the original reference. */
701 TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
704 /* Move constants in target_mem_ref REF to offset. Returns the new target
705 mem ref if anything changes, NULL_TREE otherwise. */
708 maybe_fold_tmr (tree ref)
710 struct mem_address addr;
711 bool changed = false;
714 get_address_description (ref, &addr);
716 if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
719 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
721 fold_convert (sizetype, addr.base));
723 addr.offset = addr.base;
725 addr.base = NULL_TREE;
729 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
734 off = fold_binary_to_constant (MULT_EXPR, sizetype,
736 addr.step = NULL_TREE;
741 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
747 addr.index = NULL_TREE;
754 ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
758 copy_mem_ref_info (ret, ref);
762 /* Dump PARTS to FILE. */
764 extern void dump_mem_address (FILE *, struct mem_address *);
766 dump_mem_address (FILE *file, struct mem_address *parts)
770 fprintf (file, "symbol: ");
771 print_generic_expr (file, parts->symbol, TDF_SLIM);
772 fprintf (file, "\n");
776 fprintf (file, "base: ");
777 print_generic_expr (file, parts->base, TDF_SLIM);
778 fprintf (file, "\n");
782 fprintf (file, "index: ");
783 print_generic_expr (file, parts->index, TDF_SLIM);
784 fprintf (file, "\n");
788 fprintf (file, "step: ");
789 print_generic_expr (file, parts->step, TDF_SLIM);
790 fprintf (file, "\n");
794 fprintf (file, "offset: ");
795 print_generic_expr (file, parts->offset, TDF_SLIM);
796 fprintf (file, "\n");
800 #include "gt-tree-ssa-address.h"