Daily bump.
[official-gcc.git] / gcc / tree-ssa-address.c
blob90a01dca034b33fc4691097cf2b76f50c1852f72
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
9 later version.
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
14 for more details.
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. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "output.h"
33 #include "diagnostic.h"
34 #include "tree-flow.h"
35 #include "tree-dump.h"
36 #include "tree-pass.h"
37 #include "timevar.h"
38 #include "flags.h"
39 #include "tree-inline.h"
40 #include "insn-config.h"
41 #include "recog.h"
42 #include "expr.h"
43 #include "ggc.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
68 precise results. */
70 /* A "template" for memory address, used to determine whether the address is
71 valid for mode. */
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
77 filled in. */
78 rtx * GTY ((skip)) off_p; /* The point in template where the offset should
79 be filled in. */
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) \
92 | (OFFSET != 0))
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. */
98 static void
99 gen_addr_rtx (rtx symbol, rtx base, rtx index, rtx step, rtx offset,
100 rtx *addr, rtx **step_p, rtx **offset_p)
102 rtx act_elem;
104 *addr = NULL_RTX;
105 if (step_p)
106 *step_p = NULL;
107 if (offset_p)
108 *offset_p = NULL;
110 if (index)
112 act_elem = index;
113 if (step)
115 act_elem = gen_rtx_MULT (Pmode, act_elem, step);
117 if (step_p)
118 *step_p = &XEXP (act_elem, 1);
121 *addr = act_elem;
124 if (base)
126 if (*addr)
127 *addr = simplify_gen_binary (PLUS, Pmode, base, *addr);
128 else
129 *addr = base;
132 if (symbol)
134 act_elem = symbol;
135 if (offset)
137 act_elem = gen_rtx_PLUS (Pmode, act_elem, offset);
139 if (offset_p)
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);
148 if (*addr)
149 *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
150 else
151 *addr = act_elem;
153 else if (offset)
155 if (*addr)
157 *addr = gen_rtx_PLUS (Pmode, *addr, offset);
158 if (offset_p)
159 *offset_p = &XEXP (*addr, 1);
161 else
163 *addr = offset;
164 if (offset_p)
165 *offset_p = addr;
169 if (!*addr)
170 *addr = const0_rtx;
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);
188 else
189 st = NULL_RTX;
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);
194 else
195 off = NULL_RTX;
197 if (!really_expand)
199 /* Reuse the templates for addresses, so that we do not waste memory. */
200 if (!templates_initialized)
202 unsigned i;
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),
215 &templates[i].ref,
216 &templates[i].step_p,
217 &templates[i].off_p);
220 templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
221 st, off);
222 if (st)
223 *templ->step_p = st;
224 if (off)
225 *templ->off_p = off;
227 return templ->ref;
230 /* Otherwise really expand the expressions. */
231 sym = (addr->symbol
232 ? expand_expr (build_addr (addr->symbol, current_function_decl),
233 NULL_RTX, Pmode, EXPAND_NORMAL)
234 : NULL_RTX);
235 bse = (addr->base
236 ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
237 : NULL_RTX);
238 idx = (addr->index
239 ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
240 : NULL_RTX);
242 gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
243 return address;
246 /* Returns address of MEM_REF in TYPE. */
248 tree
249 tree_mem_ref_addr (tree type, tree mem_ref)
251 tree addr;
252 tree act_elem;
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;
257 if (sym)
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);
262 base = NULL_TREE;
265 act_elem = TMR_INDEX (mem_ref);
266 if (act_elem)
268 if (step)
269 act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
270 addr_off = act_elem;
273 act_elem = base;
274 if (act_elem)
276 if (addr_off)
277 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
278 else
279 addr_off = act_elem;
282 if (offset && !integer_zerop (offset))
284 if (addr_off)
285 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
286 else
287 addr_off = offset;
290 if (addr_off)
292 if (addr_base)
293 addr = fold_build2 (POINTER_PLUS_EXPR, type, addr_base, addr_off);
294 else
295 addr = fold_convert (type, addr_off);
297 else if (addr_base)
298 addr = addr_base;
299 else
300 addr = build_int_cst (type, 0);
302 return addr;
305 /* Returns true if a memory reference in MODE and with parameters given by
306 ADDR is valid on the current target. */
308 static bool
309 valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
311 rtx address;
313 address = addr_for_mem_ref (addr, false);
314 if (!address)
315 return 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
322 TARGET_MEM_REF. */
324 static tree
325 create_mem_ref_raw (tree type, struct mem_address *addr)
327 if (!valid_mem_ref_p (TYPE_MODE (type), addr))
328 return NULL_TREE;
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. */
343 static bool
344 fixed_address_object_p (tree obj)
346 return (TREE_CODE (obj) == VAR_DECL
347 && (TREE_STATIC (obj)
348 || DECL_EXTERNAL (obj)));
351 /* If ADDR contains an address of object that is a link time constant,
352 move it to PARTS->symbol. */
354 static void
355 move_fixed_address_to_symbol (struct mem_address *parts, aff_tree *addr)
357 unsigned i;
358 tree val = NULL_TREE;
360 for (i = 0; i < addr->n; i++)
362 if (!double_int_one_p (addr->elts[i].coef))
363 continue;
365 val = addr->elts[i].val;
366 if (TREE_CODE (val) == ADDR_EXPR
367 && fixed_address_object_p (TREE_OPERAND (val, 0)))
368 break;
371 if (i == addr->n)
372 return;
374 parts->symbol = TREE_OPERAND (val, 0);
375 aff_combination_remove_elt (addr, i);
378 /* If ADDR contains an address of a dereferenced pointer, move it to
379 PARTS->base. */
381 static void
382 move_pointer_to_base (struct mem_address *parts, aff_tree *addr)
384 unsigned i;
385 tree val = NULL_TREE;
387 for (i = 0; i < addr->n; i++)
389 if (!double_int_one_p (addr->elts[i].coef))
390 continue;
392 val = addr->elts[i].val;
393 if (POINTER_TYPE_P (TREE_TYPE (val)))
394 break;
397 if (i == addr->n)
398 return;
400 parts->base = val;
401 aff_combination_remove_elt (addr, i);
404 /* Adds ELT to PARTS. */
406 static void
407 add_to_parts (struct mem_address *parts, tree elt)
409 tree type;
411 if (!parts->index)
413 parts->index = fold_convert (sizetype, elt);
414 return;
417 if (!parts->base)
419 parts->base = elt;
420 return;
423 /* Add ELT to base. */
424 type = TREE_TYPE (parts->base);
425 parts->base = fold_build2 (POINTER_PLUS_EXPR, type,
426 parts->base,
427 fold_convert (sizetype, elt));
430 /* Finds the most expensive multiplication in ADDR that can be
431 expressed in an addressing mode and move the corresponding
432 element(s) to PARTS. */
434 static void
435 most_expensive_mult_to_index (struct mem_address *parts, aff_tree *addr)
437 HOST_WIDE_INT coef;
438 double_int best_mult, amult, amult_neg;
439 unsigned best_mult_cost = 0, acost;
440 tree mult_elt = NULL_TREE, elt;
441 unsigned i, j;
442 enum tree_code op_code;
444 best_mult = double_int_zero;
445 for (i = 0; i < addr->n; i++)
447 if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
448 continue;
450 /* FIXME: Should use the correct memory mode rather than Pmode. */
452 coef = double_int_to_shwi (addr->elts[i].coef);
453 if (coef == 1
454 || !multiplier_allowed_in_address_p (coef, Pmode))
455 continue;
457 acost = multiply_by_cost (coef, Pmode);
459 if (acost > best_mult_cost)
461 best_mult_cost = acost;
462 best_mult = addr->elts[i].coef;
466 if (!best_mult_cost)
467 return;
469 /* Collect elements multiplied by best_mult. */
470 for (i = j = 0; i < addr->n; i++)
472 amult = addr->elts[i].coef;
473 amult_neg = double_int_ext_for_comb (double_int_neg (amult), addr);
475 if (double_int_equal_p (amult, best_mult))
476 op_code = PLUS_EXPR;
477 else if (double_int_equal_p (amult_neg, best_mult))
478 op_code = MINUS_EXPR;
479 else
481 addr->elts[j] = addr->elts[i];
482 j++;
483 continue;
486 elt = fold_convert (sizetype, addr->elts[i].val);
487 if (mult_elt)
488 mult_elt = fold_build2 (op_code, sizetype, mult_elt, elt);
489 else if (op_code == PLUS_EXPR)
490 mult_elt = elt;
491 else
492 mult_elt = fold_build1 (NEGATE_EXPR, sizetype, elt);
494 addr->n = j;
496 parts->index = mult_elt;
497 parts->step = double_int_to_tree (sizetype, best_mult);
500 /* Splits address ADDR into PARTS.
502 TODO -- be more clever about the distribution of the elements of ADDR
503 to PARTS. Some architectures do not support anything but single
504 register in address, possibly with a small integer offset; while
505 create_mem_ref will simplify the address to an acceptable shape
506 later, it would be more efficient to know that asking for complicated
507 addressing modes is useless. */
509 static void
510 addr_to_parts (aff_tree *addr, struct mem_address *parts)
512 tree part;
513 unsigned i;
515 parts->symbol = NULL_TREE;
516 parts->base = NULL_TREE;
517 parts->index = NULL_TREE;
518 parts->step = NULL_TREE;
520 if (!double_int_zero_p (addr->offset))
521 parts->offset = double_int_to_tree (sizetype, addr->offset);
522 else
523 parts->offset = NULL_TREE;
525 /* Try to find a symbol. */
526 move_fixed_address_to_symbol (parts, addr);
528 /* First move the most expensive feasible multiplication
529 to index. */
530 most_expensive_mult_to_index (parts, addr);
532 /* Try to find a base of the reference. Since at the moment
533 there is no reliable way how to distinguish between pointer and its
534 offset, this is just a guess. */
535 if (!parts->symbol)
536 move_pointer_to_base (parts, addr);
538 /* Then try to process the remaining elements. */
539 for (i = 0; i < addr->n; i++)
541 part = fold_convert (sizetype, addr->elts[i].val);
542 if (!double_int_one_p (addr->elts[i].coef))
543 part = fold_build2 (MULT_EXPR, sizetype, part,
544 double_int_to_tree (sizetype, addr->elts[i].coef));
545 add_to_parts (parts, part);
547 if (addr->rest)
548 add_to_parts (parts, fold_convert (sizetype, addr->rest));
551 /* Force the PARTS to register. */
553 static void
554 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
556 if (parts->base)
557 parts->base = force_gimple_operand_bsi (bsi, parts->base,
558 true, NULL_TREE,
559 true, BSI_SAME_STMT);
560 if (parts->index)
561 parts->index = force_gimple_operand_bsi (bsi, parts->index,
562 true, NULL_TREE,
563 true, BSI_SAME_STMT);
566 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
567 computations are emitted in front of BSI. TYPE is the mode
568 of created memory reference. */
570 tree
571 create_mem_ref (block_stmt_iterator *bsi, tree type, aff_tree *addr)
573 tree mem_ref, tmp;
574 tree atype;
575 struct mem_address parts;
577 addr_to_parts (addr, &parts);
578 gimplify_mem_ref_parts (bsi, &parts);
579 mem_ref = create_mem_ref_raw (type, &parts);
580 if (mem_ref)
581 return mem_ref;
583 /* The expression is too complicated. Try making it simpler. */
585 if (parts.step && !integer_onep (parts.step))
587 /* Move the multiplication to index. */
588 gcc_assert (parts.index);
589 parts.index = force_gimple_operand_bsi (bsi,
590 fold_build2 (MULT_EXPR, sizetype,
591 parts.index, parts.step),
592 true, NULL_TREE, true, BSI_SAME_STMT);
593 parts.step = NULL_TREE;
595 mem_ref = create_mem_ref_raw (type, &parts);
596 if (mem_ref)
597 return mem_ref;
600 if (parts.symbol)
602 tmp = build_addr (parts.symbol, current_function_decl);
603 gcc_assert (is_gimple_val (tmp));
605 /* Add the symbol to base, eventually forcing it to register. */
606 if (parts.base)
608 gcc_assert (useless_type_conversion_p
609 (sizetype, TREE_TYPE (parts.base)));
611 if (parts.index)
613 atype = TREE_TYPE (tmp);
614 parts.base = force_gimple_operand_bsi (bsi,
615 fold_build2 (PLUS_EXPR, atype,
616 fold_convert (atype, parts.base),
617 tmp),
618 true, NULL_TREE, true, BSI_SAME_STMT);
620 else
622 parts.index = parts.base;
623 parts.base = tmp;
626 else
627 parts.base = tmp;
628 parts.symbol = NULL_TREE;
630 mem_ref = create_mem_ref_raw (type, &parts);
631 if (mem_ref)
632 return mem_ref;
635 if (parts.index)
637 /* Add index to base. */
638 if (parts.base)
640 atype = TREE_TYPE (parts.base);
641 parts.base = force_gimple_operand_bsi (bsi,
642 fold_build2 (PLUS_EXPR, atype,
643 parts.base,
644 fold_convert (atype, parts.index)),
645 true, NULL_TREE, true, BSI_SAME_STMT);
647 else
648 parts.base = parts.index;
649 parts.index = NULL_TREE;
651 mem_ref = create_mem_ref_raw (type, &parts);
652 if (mem_ref)
653 return mem_ref;
656 if (parts.offset && !integer_zerop (parts.offset))
658 /* Try adding offset to base. */
659 if (parts.base)
661 atype = TREE_TYPE (parts.base);
662 parts.base = force_gimple_operand_bsi (bsi,
663 fold_build2 (POINTER_PLUS_EXPR, atype,
664 parts.base,
665 fold_convert (sizetype, parts.offset)),
666 true, NULL_TREE, true, BSI_SAME_STMT);
668 else
669 parts.base = parts.offset;
671 parts.offset = NULL_TREE;
673 mem_ref = create_mem_ref_raw (type, &parts);
674 if (mem_ref)
675 return mem_ref;
678 /* Verify that the address is in the simplest possible shape
679 (only a register). If we cannot create such a memory reference,
680 something is really wrong. */
681 gcc_assert (parts.symbol == NULL_TREE);
682 gcc_assert (parts.index == NULL_TREE);
683 gcc_assert (!parts.step || integer_onep (parts.step));
684 gcc_assert (!parts.offset || integer_zerop (parts.offset));
685 gcc_unreachable ();
688 /* Copies components of the address from OP to ADDR. */
690 void
691 get_address_description (tree op, struct mem_address *addr)
693 addr->symbol = TMR_SYMBOL (op);
694 addr->base = TMR_BASE (op);
695 addr->index = TMR_INDEX (op);
696 addr->step = TMR_STEP (op);
697 addr->offset = TMR_OFFSET (op);
700 /* Copies the additional information attached to target_mem_ref FROM to TO. */
702 void
703 copy_mem_ref_info (tree to, tree from)
705 /* Copy the annotation, to preserve the aliasing information. */
706 TMR_TAG (to) = TMR_TAG (from);
708 /* And the info about the original reference. */
709 TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
712 /* Move constants in target_mem_ref REF to offset. Returns the new target
713 mem ref if anything changes, NULL_TREE otherwise. */
715 tree
716 maybe_fold_tmr (tree ref)
718 struct mem_address addr;
719 bool changed = false;
720 tree ret, off;
722 get_address_description (ref, &addr);
724 if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
726 if (addr.offset)
727 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
728 addr.offset,
729 fold_convert (sizetype, addr.base));
730 else
731 addr.offset = addr.base;
733 addr.base = NULL_TREE;
734 changed = true;
737 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
739 off = addr.index;
740 if (addr.step)
742 off = fold_binary_to_constant (MULT_EXPR, sizetype,
743 off, addr.step);
744 addr.step = NULL_TREE;
747 if (addr.offset)
749 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
750 addr.offset, off);
752 else
753 addr.offset = off;
755 addr.index = NULL_TREE;
756 changed = true;
759 if (!changed)
760 return NULL_TREE;
762 ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
763 if (!ret)
764 return NULL_TREE;
766 copy_mem_ref_info (ret, ref);
767 return ret;
770 /* Dump PARTS to FILE. */
772 extern void dump_mem_address (FILE *, struct mem_address *);
773 void
774 dump_mem_address (FILE *file, struct mem_address *parts)
776 if (parts->symbol)
778 fprintf (file, "symbol: ");
779 print_generic_expr (file, parts->symbol, TDF_SLIM);
780 fprintf (file, "\n");
782 if (parts->base)
784 fprintf (file, "base: ");
785 print_generic_expr (file, parts->base, TDF_SLIM);
786 fprintf (file, "\n");
788 if (parts->index)
790 fprintf (file, "index: ");
791 print_generic_expr (file, parts->index, TDF_SLIM);
792 fprintf (file, "\n");
794 if (parts->step)
796 fprintf (file, "step: ");
797 print_generic_expr (file, parts->step, TDF_SLIM);
798 fprintf (file, "\n");
800 if (parts->offset)
802 fprintf (file, "offset: ");
803 print_generic_expr (file, parts->offset, TDF_SLIM);
804 fprintf (file, "\n");
808 #include "gt-tree-ssa-address.h"