* tree-ssa-operands.h (struct ssa_operand_memory_d):
[official-gcc.git] / gcc / tree-ssa-address.c
blob3fffd1d3fea9e1ce105a412c36562b79fe9c481a
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
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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA. */
21 /* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
22 that directly map to addressing modes of the target. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "output.h"
34 #include "diagnostic.h"
35 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "tree-pass.h"
38 #include "timevar.h"
39 #include "flags.h"
40 #include "tree-inline.h"
41 #include "insn-config.h"
42 #include "recog.h"
43 #include "expr.h"
44 #include "ggc.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
69 precise results. */
71 /* A "template" for memory address, used to determine whether the address is
72 valid for mode. */
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
78 filled in. */
79 rtx * GTY ((skip)) off_p; /* The point in template where the offset should
80 be filled in. */
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) \
93 | (OFFSET != 0))
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. */
99 static void
100 gen_addr_rtx (rtx symbol, rtx base, rtx index, rtx step, rtx offset,
101 rtx *addr, rtx **step_p, rtx **offset_p)
103 rtx act_elem;
105 *addr = NULL_RTX;
106 if (step_p)
107 *step_p = NULL;
108 if (offset_p)
109 *offset_p = NULL;
111 if (index)
113 act_elem = index;
114 if (step)
116 act_elem = gen_rtx_MULT (Pmode, act_elem, step);
118 if (step_p)
119 *step_p = &XEXP (act_elem, 1);
122 *addr = act_elem;
125 if (base)
127 if (*addr)
128 *addr = gen_rtx_PLUS (Pmode, *addr, base);
129 else
130 *addr = base;
133 if (symbol)
135 act_elem = symbol;
136 if (offset)
138 act_elem = gen_rtx_CONST (Pmode,
139 gen_rtx_PLUS (Pmode, act_elem, offset));
140 if (offset_p)
141 *offset_p = &XEXP (XEXP (act_elem, 0), 1);
144 if (*addr)
145 *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
146 else
147 *addr = act_elem;
149 else if (offset)
151 if (*addr)
153 *addr = gen_rtx_PLUS (Pmode, *addr, offset);
154 if (offset_p)
155 *offset_p = &XEXP (*addr, 1);
157 else
159 *addr = offset;
160 if (offset_p)
161 *offset_p = addr;
165 if (!*addr)
166 *addr = const0_rtx;
169 /* Returns address for TARGET_MEM_REF with parameters given by ADDR.
170 If REALLY_EXPAND is false, just make fake registers instead
171 of really expanding the operands, and perform the expansion in-place
172 by using one of the "templates". */
175 addr_for_mem_ref (struct mem_address *addr, bool really_expand)
177 rtx address, sym, bse, idx, st, off;
178 static bool templates_initialized = false;
179 struct mem_addr_template *templ;
181 if (addr->step && !integer_onep (addr->step))
182 st = immed_double_const (TREE_INT_CST_LOW (addr->step),
183 TREE_INT_CST_HIGH (addr->step), Pmode);
184 else
185 st = NULL_RTX;
187 if (addr->offset && !integer_zerop (addr->offset))
188 off = immed_double_const (TREE_INT_CST_LOW (addr->offset),
189 TREE_INT_CST_HIGH (addr->offset), Pmode);
190 else
191 off = NULL_RTX;
193 if (!really_expand)
195 /* Reuse the templates for addresses, so that we do not waste memory. */
196 if (!templates_initialized)
198 unsigned i;
200 templates_initialized = true;
201 sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup ("test_symbol"));
202 bse = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
203 idx = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
205 for (i = 0; i < 32; i++)
206 gen_addr_rtx ((i & 16 ? sym : NULL_RTX),
207 (i & 8 ? bse : NULL_RTX),
208 (i & 4 ? idx : NULL_RTX),
209 (i & 2 ? const0_rtx : NULL_RTX),
210 (i & 1 ? const0_rtx : NULL_RTX),
211 &templates[i].ref,
212 &templates[i].step_p,
213 &templates[i].off_p);
216 templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
217 st, off);
218 if (st)
219 *templ->step_p = st;
220 if (off)
221 *templ->off_p = off;
223 return templ->ref;
226 /* Otherwise really expand the expressions. */
227 sym = (addr->symbol
228 ? expand_expr (build_addr (addr->symbol, current_function_decl),
229 NULL_RTX, Pmode, EXPAND_NORMAL)
230 : NULL_RTX);
231 bse = (addr->base
232 ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
233 : NULL_RTX);
234 idx = (addr->index
235 ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
236 : NULL_RTX);
238 gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
239 return address;
242 /* Returns address of MEM_REF in TYPE. */
244 tree
245 tree_mem_ref_addr (tree type, tree mem_ref)
247 tree addr = NULL_TREE;
248 tree act_elem;
249 tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
251 act_elem = TMR_INDEX (mem_ref);
252 if (act_elem)
254 act_elem = fold_convert (type, act_elem);
256 if (step)
257 act_elem = fold_build2 (MULT_EXPR, type, act_elem,
258 fold_convert (type, step));
259 addr = act_elem;
262 act_elem = TMR_BASE (mem_ref);
263 if (act_elem)
265 act_elem = fold_convert (type, act_elem);
267 if (addr)
268 addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
269 else
270 addr = act_elem;
273 act_elem = TMR_SYMBOL (mem_ref);
274 if (act_elem)
276 act_elem = fold_convert (type, build_addr (act_elem,
277 current_function_decl));
278 if (addr)
279 addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
280 else
281 addr = act_elem;
284 if (offset && !integer_zerop (offset))
286 act_elem = fold_convert (type, offset);
288 if (addr)
289 addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
290 else
291 addr = act_elem;
294 if (!addr)
295 addr = build_int_cst (type, 0);
297 return addr;
300 /* Returns true if a memory reference in MODE and with parameters given by
301 ADDR is valid on the current target. */
303 static bool
304 valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
306 rtx address;
308 address = addr_for_mem_ref (addr, false);
309 if (!address)
310 return false;
312 return memory_address_p (mode, address);
315 /* Checks whether a TARGET_MEM_REF with type TYPE and parameters given by ADDR
316 is valid on the current target and if so, creates and returns the
317 TARGET_MEM_REF. */
319 static tree
320 create_mem_ref_raw (tree type, struct mem_address *addr)
322 if (!valid_mem_ref_p (TYPE_MODE (type), addr))
323 return NULL_TREE;
325 if (addr->step && integer_onep (addr->step))
326 addr->step = NULL_TREE;
328 if (addr->offset && integer_zerop (addr->offset))
329 addr->offset = NULL_TREE;
331 return build7 (TARGET_MEM_REF, type,
332 addr->symbol, addr->base, addr->index,
333 addr->step, addr->offset, NULL, NULL);
336 /* Returns true if OBJ is an object whose address is a link time constant. */
338 static bool
339 fixed_address_object_p (tree obj)
341 return (TREE_CODE (obj) == VAR_DECL
342 && (TREE_STATIC (obj)
343 || DECL_EXTERNAL (obj)));
346 /* Adds COEF * ELT to PARTS. TYPE is the type of the address we
347 construct. */
349 static void
350 add_to_parts (struct mem_address *parts, tree type, tree elt)
352 tree elt_core = elt;
353 STRIP_NOPS (elt_core);
355 /* Check if this is a symbol. */
356 if (!parts->symbol
357 && TREE_CODE (elt_core) == ADDR_EXPR
358 && fixed_address_object_p (TREE_OPERAND (elt_core, 0)))
360 parts->symbol = TREE_OPERAND (elt_core, 0);
361 return;
364 if (!parts->base)
366 parts->base = elt;
367 return;
370 if (!parts->index)
372 parts->index = elt;
373 return;
376 /* Add ELT to base. */
377 parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
380 /* Finds the most expensive multiplication in ADDR that can be
381 expressed in an addressing mode and move the corresponding
382 element(s) to PARTS. TYPE is the type of the address we
383 construct. */
385 static void
386 most_expensive_mult_to_index (struct mem_address *parts, tree type,
387 aff_tree *addr)
389 HOST_WIDE_INT coef;
390 double_int best_mult, amult, amult_neg;
391 unsigned best_mult_cost = 0, acost;
392 tree mult_elt = NULL_TREE, elt;
393 unsigned i, j;
394 enum tree_code op_code;
396 best_mult = double_int_zero;
397 for (i = 0; i < addr->n; i++)
399 if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
400 continue;
402 /* FIXME: Should use the correct memory mode rather than Pmode. */
404 coef = double_int_to_shwi (addr->elts[i].coef);
405 if (coef == 1
406 || !multiplier_allowed_in_address_p (coef, Pmode))
407 continue;
409 acost = multiply_by_cost (coef, Pmode);
411 if (acost > best_mult_cost)
413 best_mult_cost = acost;
414 best_mult = addr->elts[i].coef;
418 if (!best_mult_cost)
419 return;
421 /* Collect elements multiplied by best_mult. */
422 for (i = j = 0; i < addr->n; i++)
424 amult = addr->elts[i].coef;
425 amult_neg = double_int_ext_for_comb (double_int_neg (amult), addr);
427 if (double_int_equal_p (amult, best_mult))
428 op_code = PLUS_EXPR;
429 else if (double_int_equal_p (amult_neg, best_mult))
430 op_code = MINUS_EXPR;
431 else
433 addr->elts[j] = addr->elts[i];
434 j++;
435 continue;
438 elt = fold_convert (type, addr->elts[i].val);
439 if (mult_elt)
440 mult_elt = fold_build2 (op_code, type, mult_elt, elt);
441 else if (op_code == PLUS_EXPR)
442 mult_elt = elt;
443 else
444 mult_elt = fold_build1 (NEGATE_EXPR, type, elt);
446 addr->n = j;
448 parts->index = mult_elt;
449 parts->step = double_int_to_tree (type, best_mult);
452 /* Splits address ADDR into PARTS.
454 TODO -- be more clever about the distribution of the elements of ADDR
455 to PARTS. Some architectures do not support anything but single
456 register in address, possibly with a small integer offset; while
457 create_mem_ref will simplify the address to an acceptable shape
458 later, it would be more efficient to know that asking for complicated
459 addressing modes is useless. */
461 static void
462 addr_to_parts (aff_tree *addr, tree type, struct mem_address *parts)
464 tree part;
465 unsigned i;
467 parts->symbol = NULL_TREE;
468 parts->base = NULL_TREE;
469 parts->index = NULL_TREE;
470 parts->step = NULL_TREE;
472 if (!double_int_zero_p (addr->offset))
473 parts->offset = double_int_to_tree (type, addr->offset);
474 else
475 parts->offset = NULL_TREE;
477 /* First move the most expensive feasible multiplication
478 to index. */
479 most_expensive_mult_to_index (parts, type, addr);
481 /* Then try to process the remaining elements. */
482 for (i = 0; i < addr->n; i++)
484 part = fold_convert (type, addr->elts[i].val);
485 if (!double_int_one_p (addr->elts[i].coef))
486 part = fold_build2 (MULT_EXPR, type, part,
487 double_int_to_tree (type, addr->elts[i].coef));
488 add_to_parts (parts, type, part);
490 if (addr->rest)
491 add_to_parts (parts, type, addr->rest);
494 /* Force the PARTS to register. */
496 static void
497 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
499 if (parts->base)
500 parts->base = force_gimple_operand_bsi (bsi, parts->base,
501 true, NULL_TREE);
502 if (parts->index)
503 parts->index = force_gimple_operand_bsi (bsi, parts->index,
504 true, NULL_TREE);
507 /* Creates and returns a TARGET_MEM_REF for address ADDR. If necessary
508 computations are emitted in front of BSI. TYPE is the mode
509 of created memory reference. */
511 tree
512 create_mem_ref (block_stmt_iterator *bsi, tree type, aff_tree *addr)
514 tree mem_ref, tmp;
515 tree addr_type = build_pointer_type (type);
516 struct mem_address parts;
518 addr_to_parts (addr, addr_type, &parts);
519 gimplify_mem_ref_parts (bsi, &parts);
520 mem_ref = create_mem_ref_raw (type, &parts);
521 if (mem_ref)
522 return mem_ref;
524 /* The expression is too complicated. Try making it simpler. */
526 if (parts.step && !integer_onep (parts.step))
528 /* Move the multiplication to index. */
529 gcc_assert (parts.index);
530 parts.index = force_gimple_operand_bsi (bsi,
531 build2 (MULT_EXPR, addr_type,
532 parts.index, parts.step),
533 true, NULL_TREE);
534 parts.step = NULL_TREE;
536 mem_ref = create_mem_ref_raw (type, &parts);
537 if (mem_ref)
538 return mem_ref;
541 if (parts.symbol)
543 tmp = build_addr (parts.symbol, current_function_decl);
545 /* Add the symbol to base, eventually forcing it to register. */
546 if (parts.base)
548 if (parts.index)
549 parts.base = force_gimple_operand_bsi (bsi,
550 build2 (PLUS_EXPR, addr_type,
551 parts.base, tmp),
552 true, NULL_TREE);
553 else
555 parts.index = parts.base;
556 parts.base = tmp;
559 else
560 parts.base = tmp;
561 parts.symbol = NULL_TREE;
563 mem_ref = create_mem_ref_raw (type, &parts);
564 if (mem_ref)
565 return mem_ref;
568 if (parts.base)
570 /* Add base to index. */
571 if (parts.index)
572 parts.index = force_gimple_operand_bsi (bsi,
573 build2 (PLUS_EXPR, addr_type,
574 parts.base,
575 parts.index),
576 true, NULL_TREE);
577 else
578 parts.index = parts.base;
579 parts.base = NULL_TREE;
581 mem_ref = create_mem_ref_raw (type, &parts);
582 if (mem_ref)
583 return mem_ref;
586 if (parts.offset && !integer_zerop (parts.offset))
588 /* Try adding offset to index. */
589 if (parts.index)
590 parts.index = force_gimple_operand_bsi (bsi,
591 build2 (PLUS_EXPR, addr_type,
592 parts.index,
593 parts.offset),
594 true, NULL_TREE);
595 else
596 parts.index = parts.offset, bsi;
598 parts.offset = NULL_TREE;
600 mem_ref = create_mem_ref_raw (type, &parts);
601 if (mem_ref)
602 return mem_ref;
605 /* Verify that the address is in the simplest possible shape
606 (only a register). If we cannot create such a memory reference,
607 something is really wrong. */
608 gcc_assert (parts.symbol == NULL_TREE);
609 gcc_assert (parts.base == NULL_TREE);
610 gcc_assert (!parts.step || integer_onep (parts.step));
611 gcc_assert (!parts.offset || integer_zerop (parts.offset));
612 gcc_unreachable ();
615 /* Copies components of the address from OP to ADDR. */
617 void
618 get_address_description (tree op, struct mem_address *addr)
620 addr->symbol = TMR_SYMBOL (op);
621 addr->base = TMR_BASE (op);
622 addr->index = TMR_INDEX (op);
623 addr->step = TMR_STEP (op);
624 addr->offset = TMR_OFFSET (op);
627 /* Copies the additional information attached to target_mem_ref FROM to TO. */
629 void
630 copy_mem_ref_info (tree to, tree from)
632 /* Copy the annotation, to preserve the aliasing information. */
633 TMR_TAG (to) = TMR_TAG (from);
635 /* And the info about the original reference. */
636 TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
639 /* Move constants in target_mem_ref REF to offset. Returns the new target
640 mem ref if anything changes, NULL_TREE otherwise. */
642 tree
643 maybe_fold_tmr (tree ref)
645 struct mem_address addr;
646 bool changed = false;
647 tree ret, off;
649 get_address_description (ref, &addr);
651 if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
653 if (addr.offset)
654 addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
655 addr.offset, addr.base);
656 else
657 addr.offset = addr.base;
659 addr.base = NULL_TREE;
660 changed = true;
663 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
665 off = addr.index;
666 if (addr.step)
668 off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
669 off, addr.step);
670 addr.step = NULL_TREE;
673 if (addr.offset)
675 addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
676 addr.offset, off);
678 else
679 addr.offset = off;
681 addr.index = NULL_TREE;
682 changed = true;
685 if (!changed)
686 return NULL_TREE;
688 ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
689 if (!ret)
690 return NULL_TREE;
692 copy_mem_ref_info (ret, ref);
693 return ret;
696 /* Dump PARTS to FILE. */
698 extern void dump_mem_address (FILE *, struct mem_address *);
699 void
700 dump_mem_address (FILE *file, struct mem_address *parts)
702 if (parts->symbol)
704 fprintf (file, "symbol: ");
705 print_generic_expr (file, parts->symbol, TDF_SLIM);
706 fprintf (file, "\n");
708 if (parts->base)
710 fprintf (file, "base: ");
711 print_generic_expr (file, parts->base, TDF_SLIM);
712 fprintf (file, "\n");
714 if (parts->index)
716 fprintf (file, "index: ");
717 print_generic_expr (file, parts->index, TDF_SLIM);
718 fprintf (file, "\n");
720 if (parts->step)
722 fprintf (file, "step: ");
723 print_generic_expr (file, parts->step, TDF_SLIM);
724 fprintf (file, "\n");
726 if (parts->offset)
728 fprintf (file, "offset: ");
729 print_generic_expr (file, parts->offset, TDF_SLIM);
730 fprintf (file, "\n");
734 #include "gt-tree-ssa-address.h"