1/* Memory address lowering and addressing mode selection.
2 Copyright (C) 2004 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 2, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING. If not, write to the Free
18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
1902110-1301, USA. */
20
21/* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
22 that directly map to addressing modes of the target. */
23
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
46/* TODO -- handling of symbols (according to Richard Hendersons
47 comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
48
49 There are at least 5 different kinds of symbols that we can run up against:
50
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
56
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"))).
60
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).
64
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. */
69
70/* A "template" for memory address, used to determine whether the address is
71 valid for mode. */
72
73struct mem_addr_template GTY (())
74{
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. */
80};
81
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. */
84
85static GTY (()) struct mem_addr_template templates[32];
86
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))
93
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. */
97
98static void
99gen_addr_rtx (rtx symbol, rtx base, rtx index, rtx step, rtx offset,
100 rtx *addr, rtx **step_p, rtx **offset_p)
101{
102 rtx act_elem;
103
104 *addr = NULL_RTX;
105 if (step_p)
106 *step_p = NULL;
107 if (offset_p)
108 *offset_p = NULL;
109
110 if (index)
111 {
112 act_elem = index;
113 if (step)
114 {
115 act_elem = gen_rtx_MULT (Pmode, act_elem, step);
116
117 if (step_p)
118 *step_p = &XEXP (act_elem, 1);
119 }
120
121 *addr = act_elem;
122 }
123
124 if (base)
125 {
126 if (*addr)
127 *addr = gen_rtx_PLUS (Pmode, *addr, base);
128 else
129 *addr = base;
130 }
131
132 if (symbol)
133 {
134 act_elem = symbol;
135 if (offset)
136 {
137 act_elem = gen_rtx_CONST (Pmode,
138 gen_rtx_PLUS (Pmode, act_elem, offset));
139 if (offset_p)
140 *offset_p = &XEXP (XEXP (act_elem, 0), 1);
141 }
142
143 if (*addr)
144 *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
145 else
146 *addr = act_elem;
147 }
148 else if (offset)
149 {
150 if (*addr)
151 {
152 *addr = gen_rtx_PLUS (Pmode, *addr, offset);
153 if (offset_p)
154 *offset_p = &XEXP (*addr, 1);
155 }
156 else
157 {
158 *addr = offset;
159 if (offset_p)
160 *offset_p = addr;
161 }
162 }
163
164 if (!*addr)
165 *addr = const0_rtx;
166}
167
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". */
172
173rtx
174addr_for_mem_ref (struct mem_address *addr, bool really_expand)
175{
176 rtx address, sym, bse, idx, st, off;
177 static bool templates_initialized = false;
178 struct mem_addr_template *templ;
179
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);
183 else
184 st = NULL_RTX;
185
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);
189 else
190 off = NULL_RTX;
191
192 if (!really_expand)
193 {
194 /* Reuse the templates for addresses, so that we do not waste memory. */
195 if (!templates_initialized)
196 {
197 unsigned i;
198
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);
203
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),
210 &templates[i].ref,
211 &templates[i].step_p,
212 &templates[i].off_p);
213 }
214
215 templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
216 st, off);
217 if (st)
218 *templ->step_p = st;
219 if (off)
220 *templ->off_p = off;
221
222 return templ->ref;
223 }
224
225 /* Otherwise really expand the expressions. */
226 sym = (addr->symbol
227 ? expand_expr (build_addr (addr->symbol, current_function_decl),
228 NULL_RTX, Pmode, EXPAND_NORMAL)
229 : NULL_RTX);
230 bse = (addr->base
231 ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
232 : NULL_RTX);
233 idx = (addr->index
234 ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
235 : NULL_RTX);
236
237 gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
238 return address;
239}
240
241/* Returns address of MEM_REF in TYPE. */
242
243tree
244tree_mem_ref_addr (tree type, tree mem_ref)
245{
246 tree addr;
247 tree act_elem;
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;
251
252 if (sym)
253 addr_base = fold_convert (type, build_addr (sym, current_function_decl));
254 else if (base && POINTER_TYPE_P (TREE_TYPE (base)))
255 {
256 addr_base = fold_convert (type, base);
257 base = NULL_TREE;
258 }
259
260 act_elem = TMR_INDEX (mem_ref);
261 if (act_elem)
262 {
263 if (step)
264 act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
265 addr_off = act_elem;
266 }
267
268 act_elem = base;
269 if (act_elem)
270 {
271 if (addr_off)
272 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
273 else
274 addr_off = act_elem;
275 }
276
277 if (!zero_p (offset))
278 {
279 if (addr_off)
280 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
281 else
282 addr_off = offset;
283 }
284
285 if (addr_off)
286 {
287 addr = fold_convert (type, addr_off);
288 if (addr_base)
289 addr = fold_build2 (PLUS_EXPR, type, addr_base, addr);
290 }
291 else if (addr_base)
292 addr = addr_base;
293 else
294 addr = build_int_cst (type, 0);
295
296 return addr;
297}
298
299/* Returns true if a memory reference in MODE and with parameters given by
300 ADDR is valid on the current target. */
301
302static bool
303valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
304{
305 rtx address;
306
307 address = addr_for_mem_ref (addr, false);
308 if (!address)
309 return false;
310
311 return memory_address_p (mode, address);
312}
313
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
316 TARGET_MEM_REF. */
317
318static tree
319create_mem_ref_raw (tree type, struct mem_address *addr)
320{
321 if (!valid_mem_ref_p (TYPE_MODE (type), addr))
322 return NULL_TREE;
323
324 if (addr->step && integer_onep (addr->step))
325 addr->step = NULL_TREE;
326
327 if (addr->offset && zero_p (addr->offset))
328 addr->offset = NULL_TREE;
329
330 return build7 (TARGET_MEM_REF, type,
331 addr->symbol, addr->base, addr->index,
332 addr->step, addr->offset, NULL, NULL);
333}
334
335/* Returns true if OBJ is an object whose address is a link time constant. */
336
337static bool
338fixed_address_object_p (tree obj)
339{
340 return (TREE_CODE (obj) == VAR_DECL
341 && (TREE_STATIC (obj)
342 || DECL_EXTERNAL (obj)));
343}
344
345/* Remove M-th element from COMB. */
346
347static void
348aff_combination_remove_elt (struct affine_tree_combination *comb, unsigned m)
349{
350 comb->n--;
351 if (m <= comb->n)
352 {
353 comb->coefs[m] = comb->coefs[comb->n];
354 comb->elts[m] = comb->elts[comb->n];
355 }
356 if (comb->rest)
357 {
358 comb->coefs[comb->n] = 1;
359 comb->elts[comb->n] = comb->rest;
360 comb->rest = NULL_TREE;
361 comb->n++;
362 }
363}
364
365/* If ADDR contains an address of object that is a link time constant,
366 move it to PARTS->symbol. */
367
368static void
369move_fixed_address_to_symbol (struct mem_address *parts,
370 struct affine_tree_combination *addr)
371{
372 unsigned i;
373 tree val = NULL_TREE;
374
375 for (i = 0; i < addr->n; i++)
376 {
377 if (addr->coefs[i] != 1)
378 continue;
379
380 val = addr->elts[i];
381 if (TREE_CODE (val) == ADDR_EXPR
382 && fixed_address_object_p (TREE_OPERAND (val, 0)))
383 break;
384 }
385
386 if (i == addr->n)
387 return;
388
389 parts->symbol = TREE_OPERAND (val, 0);
390 aff_combination_remove_elt (addr, i);
391}
392
393/* If ADDR contains an address of a dereferenced pointer, move it to
394 PARTS->base. */
395
396static void
397move_pointer_to_base (struct mem_address *parts,
398 struct affine_tree_combination *addr)
399{
400 unsigned i;
401 tree val = NULL_TREE;
402
403 for (i = 0; i < addr->n; i++)
404 {
405 if (addr->coefs[i] != 1)
406 continue;
407
408 val = addr->elts[i];
409 if (POINTER_TYPE_P (TREE_TYPE (val)))
410 break;
411 }
412
413 if (i == addr->n)
414 return;
415
416 parts->base = val;
417 aff_combination_remove_elt (addr, i);
418}
419
420/* Adds ELT to PARTS. */
421
422static void
423add_to_parts (struct mem_address *parts, tree elt)
424{
425 tree type;
426
427 if (!parts->index)
428 {
429 parts->index = elt;
430 return;
431 }
432
433 if (!parts->base)
434 {
435 parts->base = elt;
436 return;
437 }
438
439 /* Add ELT to base. */
440 type = TREE_TYPE (parts->base);
441 parts->base = fold_build2 (PLUS_EXPR, type,
442 parts->base,
443 fold_convert (type, elt));
444}
445
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. */
449
450static void
451most_expensive_mult_to_index (struct mem_address *parts,
452 struct affine_tree_combination *addr)
453{
454 unsigned HOST_WIDE_INT best_mult = 0;
455 unsigned best_mult_cost = 0, acost;
456 tree mult_elt = NULL_TREE, elt;
457 unsigned i, j;
458
459 for (i = 0; i < addr->n; i++)
460 {
461 if (addr->coefs[i] == 1
462 || !multiplier_allowed_in_address_p (addr->coefs[i]))
463 continue;
464
465 acost = multiply_by_cost (addr->coefs[i], Pmode);
466
467 if (acost > best_mult_cost)
468 {
469 best_mult_cost = acost;
470 best_mult = addr->coefs[i];
471 }
472 }
473
474 if (!best_mult)
475 return;
476
477 for (i = j = 0; i < addr->n; i++)
478 {
479 if (addr->coefs[i] != best_mult)
480 {
481 addr->coefs[j] = addr->coefs[i];
482 addr->elts[j] = addr->elts[i];
483 j++;
484 continue;
485 }
486
487 elt = fold_convert (sizetype, addr->elts[i]);
488 if (!mult_elt)
489 mult_elt = elt;
490 else
491 mult_elt = fold_build2 (PLUS_EXPR, sizetype, mult_elt, elt);
492 }
493 addr->n = j;
494
495 parts->index = mult_elt;
496 parts->step = build_int_cst_type (sizetype, best_mult);
497}
498
499/* Splits address ADDR into PARTS.
500
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. */
507
508static void
509addr_to_parts (struct affine_tree_combination *addr, struct mem_address *parts)
510{
511 unsigned i;
512 tree part;
513
514 parts->symbol = NULL_TREE;
515 parts->base = NULL_TREE;
516 parts->index = NULL_TREE;
517 parts->step = NULL_TREE;
518
519 if (addr->offset)
520 parts->offset = build_int_cst_type (sizetype, addr->offset);
521 else
522 parts->offset = NULL_TREE;
523
524 /* Try to find a symbol. */
525 move_fixed_address_to_symbol (parts, addr);
526
527 /* First move the most expensive feasible multiplication
528 to index. */
529 most_expensive_mult_to_index (parts, addr);
530
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. */
534 if (!parts->symbol)
535 move_pointer_to_base (parts, addr);
536
537 /* Then try to process the remaining elements. */
538 for (i = 0; i < addr->n; i++)
539 {
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);
545 }
546 if (addr->rest)
547 add_to_parts (parts, fold_convert (sizetype, addr->rest));
548}
549
550/* Force the PARTS to register. */
551
552static void
553gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
554{
555 if (parts->base)
556 parts->base = force_gimple_operand_bsi (bsi, parts->base,
557 true, NULL_TREE);
558 if (parts->index)
559 parts->index = force_gimple_operand_bsi (bsi, parts->index,
560 true, NULL_TREE);
561}
562
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. */
566
567tree
568create_mem_ref (block_stmt_iterator *bsi, tree type,
569 struct affine_tree_combination *addr)
570{
571 tree mem_ref, tmp;
572 tree atype;
573 struct mem_address parts;
574
575 addr_to_parts (addr, &parts);
576 gimplify_mem_ref_parts (bsi, &parts);
577 mem_ref = create_mem_ref_raw (type, &parts);
578 if (mem_ref)
579 return mem_ref;
580
581 /* The expression is too complicated. Try making it simpler. */
582
583 if (parts.step && !integer_onep (parts.step))
584 {
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),
590 true, NULL_TREE);
591 parts.step = NULL_TREE;
592
593 mem_ref = create_mem_ref_raw (type, &parts);
594 if (mem_ref)
595 return mem_ref;
596 }
597
598 if (parts.symbol)
599 {
600 tmp = build_addr (parts.symbol, current_function_decl);
601 gcc_assert (is_gimple_val (tmp));
602
603 /* Add the symbol to base, eventually forcing it to register. */
604 if (parts.base)
605 {
606 gcc_assert (TREE_TYPE (parts.base) == sizetype);
607
608 if (parts.index)
609 {
610 atype = TREE_TYPE (tmp);
611 parts.base = force_gimple_operand_bsi (bsi,
612 fold_build2 (PLUS_EXPR, atype,
613 fold_convert (atype, parts.base),
614 tmp),
615 true, NULL_TREE);
616 }
617 else
618 {
619 parts.index = parts.base;
620 parts.base = tmp;
621 }
622 }
623 else
624 parts.base = tmp;
625 parts.symbol = NULL_TREE;
626
627 mem_ref = create_mem_ref_raw (type, &parts);
628 if (mem_ref)
629 return mem_ref;
630 }
631
632 if (parts.index)
633 {
634 /* Add index to base. */
635 if (parts.base)
636 {
637 atype = TREE_TYPE (parts.base);
638 parts.base = force_gimple_operand_bsi (bsi,
639 fold_build2 (PLUS_EXPR, atype,
640 parts.base,
641 fold_convert (atype, parts.index)),
642 true, NULL_TREE);
643 }
644 else
645 parts.base = parts.index;
646 parts.index = NULL_TREE;
647
648 mem_ref = create_mem_ref_raw (type, &parts);
649 if (mem_ref)
650 return mem_ref;
651 }
652
653 if (parts.offset && !integer_zerop (parts.offset))
654 {
655 /* Try adding offset to base. */
656 if (parts.base)
657 {
658 atype = TREE_TYPE (parts.base);
659 parts.base = force_gimple_operand_bsi (bsi,
660 fold_build2 (PLUS_EXPR, atype,
661 parts.base,
662 fold_convert (atype, parts.offset)),
663 true, NULL_TREE);
664 }
665 else
666 parts.base = parts.offset;
667
668 parts.offset = NULL_TREE;
669
670 mem_ref = create_mem_ref_raw (type, &parts);
671 if (mem_ref)
672 return mem_ref;
673 }
674
675 /* Verify that the address is in the simplest possible shape
676 (only a register). If we cannot create such a memory reference,
677 something is really wrong. */
678 gcc_assert (parts.symbol == NULL_TREE);
679 gcc_assert (parts.index == NULL_TREE);
680 gcc_assert (!parts.step || integer_onep (parts.step));
681 gcc_assert (!parts.offset || integer_zerop (parts.offset));
682 gcc_unreachable ();
683}
684
685/* Copies components of the address from OP to ADDR. */
686
687void
688get_address_description (tree op, struct mem_address *addr)
689{
690 addr->symbol = TMR_SYMBOL (op);
691 addr->base = TMR_BASE (op);
692 addr->index = TMR_INDEX (op);
693 addr->step = TMR_STEP (op);
694 addr->offset = TMR_OFFSET (op);
695}
696
697/* Copies the additional information attached to target_mem_ref FROM to TO. */
698
699void
700copy_mem_ref_info (tree to, tree from)
701{
702 /* Copy the annotation, to preserve the aliasing information. */
703 TMR_TAG (to) = TMR_TAG (from);
704
705 /* And the info about the original reference. */
706 TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
707}
708
709/* Move constants in target_mem_ref REF to offset. Returns the new target
710 mem ref if anything changes, NULL_TREE otherwise. */
711
712tree
713maybe_fold_tmr (tree ref)
714{
715 struct mem_address addr;
716 bool changed = false;
717 tree ret, off;
718
719 get_address_description (ref, &addr);
720
721 if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
722 {
723 if (addr.offset)
724 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
725 addr.offset,
726 fold_convert (sizetype, addr.base));
727 else
728 addr.offset = addr.base;
729
730 addr.base = NULL_TREE;
731 changed = true;
732 }
733
734 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
735 {
736 off = addr.index;
737 if (addr.step)
738 {
739 off = fold_binary_to_constant (MULT_EXPR, sizetype,
740 off, addr.step);
741 addr.step = NULL_TREE;
742 }
743
744 if (addr.offset)
745 {
746 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
747 addr.offset, off);
748 }
749 else
750 addr.offset = off;
751
752 addr.index = NULL_TREE;
753 changed = true;
754 }
755
756 if (!changed)
757 return NULL_TREE;
758
759 ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
760 if (!ret)
761 return NULL_TREE;
762
763 copy_mem_ref_info (ret, ref);
764 return ret;
765}
766
767/* Dump PARTS to FILE. */
768
769extern void dump_mem_address (FILE *, struct mem_address *);
770void
771dump_mem_address (FILE *file, struct mem_address *parts)
772{
773 if (parts->symbol)
774 {
775 fprintf (file, "symbol: ");
776 print_generic_expr (file, parts->symbol, TDF_SLIM);
777 fprintf (file, "\n");
778 }
779 if (parts->base)
780 {
781 fprintf (file, "base: ");
782 print_generic_expr (file, parts->base, TDF_SLIM);
783 fprintf (file, "\n");
784 }
785 if (parts->index)
786 {
787 fprintf (file, "index: ");
788 print_generic_expr (file, parts->index, TDF_SLIM);
789 fprintf (file, "\n");
790 }
791 if (parts->step)
792 {
793 fprintf (file, "step: ");
794 print_generic_expr (file, parts->step, TDF_SLIM);
795 fprintf (file, "\n");
796 }
797 if (parts->offset)
798 {
799 fprintf (file, "offset: ");
800 print_generic_expr (file, parts->offset, TDF_SLIM);
801 fprintf (file, "\n");
802 }
803}
804
805#include "gt-tree-ssa-address.h"
2 Copyright (C) 2004 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 2, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING. If not, write to the Free
18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
1902110-1301, USA. */
20
21/* Utility functions for manipulation with TARGET_MEM_REFs -- tree expressions
22 that directly map to addressing modes of the target. */
23
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
46/* TODO -- handling of symbols (according to Richard Hendersons
47 comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
48
49 There are at least 5 different kinds of symbols that we can run up against:
50
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
56
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"))).
60
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).
64
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. */
69
70/* A "template" for memory address, used to determine whether the address is
71 valid for mode. */
72
73struct mem_addr_template GTY (())
74{
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. */
80};
81
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. */
84
85static GTY (()) struct mem_addr_template templates[32];
86
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))
93
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. */
97
98static void
99gen_addr_rtx (rtx symbol, rtx base, rtx index, rtx step, rtx offset,
100 rtx *addr, rtx **step_p, rtx **offset_p)
101{
102 rtx act_elem;
103
104 *addr = NULL_RTX;
105 if (step_p)
106 *step_p = NULL;
107 if (offset_p)
108 *offset_p = NULL;
109
110 if (index)
111 {
112 act_elem = index;
113 if (step)
114 {
115 act_elem = gen_rtx_MULT (Pmode, act_elem, step);
116
117 if (step_p)
118 *step_p = &XEXP (act_elem, 1);
119 }
120
121 *addr = act_elem;
122 }
123
124 if (base)
125 {
126 if (*addr)
127 *addr = gen_rtx_PLUS (Pmode, *addr, base);
128 else
129 *addr = base;
130 }
131
132 if (symbol)
133 {
134 act_elem = symbol;
135 if (offset)
136 {
137 act_elem = gen_rtx_CONST (Pmode,
138 gen_rtx_PLUS (Pmode, act_elem, offset));
139 if (offset_p)
140 *offset_p = &XEXP (XEXP (act_elem, 0), 1);
141 }
142
143 if (*addr)
144 *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
145 else
146 *addr = act_elem;
147 }
148 else if (offset)
149 {
150 if (*addr)
151 {
152 *addr = gen_rtx_PLUS (Pmode, *addr, offset);
153 if (offset_p)
154 *offset_p = &XEXP (*addr, 1);
155 }
156 else
157 {
158 *addr = offset;
159 if (offset_p)
160 *offset_p = addr;
161 }
162 }
163
164 if (!*addr)
165 *addr = const0_rtx;
166}
167
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". */
172
173rtx
174addr_for_mem_ref (struct mem_address *addr, bool really_expand)
175{
176 rtx address, sym, bse, idx, st, off;
177 static bool templates_initialized = false;
178 struct mem_addr_template *templ;
179
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);
183 else
184 st = NULL_RTX;
185
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);
189 else
190 off = NULL_RTX;
191
192 if (!really_expand)
193 {
194 /* Reuse the templates for addresses, so that we do not waste memory. */
195 if (!templates_initialized)
196 {
197 unsigned i;
198
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);
203
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),
210 &templates[i].ref,
211 &templates[i].step_p,
212 &templates[i].off_p);
213 }
214
215 templ = templates + TEMPL_IDX (addr->symbol, addr->base, addr->index,
216 st, off);
217 if (st)
218 *templ->step_p = st;
219 if (off)
220 *templ->off_p = off;
221
222 return templ->ref;
223 }
224
225 /* Otherwise really expand the expressions. */
226 sym = (addr->symbol
227 ? expand_expr (build_addr (addr->symbol, current_function_decl),
228 NULL_RTX, Pmode, EXPAND_NORMAL)
229 : NULL_RTX);
230 bse = (addr->base
231 ? expand_expr (addr->base, NULL_RTX, Pmode, EXPAND_NORMAL)
232 : NULL_RTX);
233 idx = (addr->index
234 ? expand_expr (addr->index, NULL_RTX, Pmode, EXPAND_NORMAL)
235 : NULL_RTX);
236
237 gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
238 return address;
239}
240
241/* Returns address of MEM_REF in TYPE. */
242
243tree
244tree_mem_ref_addr (tree type, tree mem_ref)
245{
246 tree addr;
247 tree act_elem;
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;
251
252 if (sym)
253 addr_base = fold_convert (type, build_addr (sym, current_function_decl));
254 else if (base && POINTER_TYPE_P (TREE_TYPE (base)))
255 {
256 addr_base = fold_convert (type, base);
257 base = NULL_TREE;
258 }
259
260 act_elem = TMR_INDEX (mem_ref);
261 if (act_elem)
262 {
263 if (step)
264 act_elem = fold_build2 (MULT_EXPR, sizetype, act_elem, step);
265 addr_off = act_elem;
266 }
267
268 act_elem = base;
269 if (act_elem)
270 {
271 if (addr_off)
272 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, act_elem);
273 else
274 addr_off = act_elem;
275 }
276
277 if (!zero_p (offset))
278 {
279 if (addr_off)
280 addr_off = fold_build2 (PLUS_EXPR, sizetype, addr_off, offset);
281 else
282 addr_off = offset;
283 }
284
285 if (addr_off)
286 {
287 addr = fold_convert (type, addr_off);
288 if (addr_base)
289 addr = fold_build2 (PLUS_EXPR, type, addr_base, addr);
290 }
291 else if (addr_base)
292 addr = addr_base;
293 else
294 addr = build_int_cst (type, 0);
295
296 return addr;
297}
298
299/* Returns true if a memory reference in MODE and with parameters given by
300 ADDR is valid on the current target. */
301
302static bool
303valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
304{
305 rtx address;
306
307 address = addr_for_mem_ref (addr, false);
308 if (!address)
309 return false;
310
311 return memory_address_p (mode, address);
312}
313
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
316 TARGET_MEM_REF. */
317
318static tree
319create_mem_ref_raw (tree type, struct mem_address *addr)
320{
321 if (!valid_mem_ref_p (TYPE_MODE (type), addr))
322 return NULL_TREE;
323
324 if (addr->step && integer_onep (addr->step))
325 addr->step = NULL_TREE;
326
327 if (addr->offset && zero_p (addr->offset))
328 addr->offset = NULL_TREE;
329
330 return build7 (TARGET_MEM_REF, type,
331 addr->symbol, addr->base, addr->index,
332 addr->step, addr->offset, NULL, NULL);
333}
334
335/* Returns true if OBJ is an object whose address is a link time constant. */
336
337static bool
338fixed_address_object_p (tree obj)
339{
340 return (TREE_CODE (obj) == VAR_DECL
341 && (TREE_STATIC (obj)
342 || DECL_EXTERNAL (obj)));
343}
344
345/* Remove M-th element from COMB. */
346
347static void
348aff_combination_remove_elt (struct affine_tree_combination *comb, unsigned m)
349{
350 comb->n--;
351 if (m <= comb->n)
352 {
353 comb->coefs[m] = comb->coefs[comb->n];
354 comb->elts[m] = comb->elts[comb->n];
355 }
356 if (comb->rest)
357 {
358 comb->coefs[comb->n] = 1;
359 comb->elts[comb->n] = comb->rest;
360 comb->rest = NULL_TREE;
361 comb->n++;
362 }
363}
364
365/* If ADDR contains an address of object that is a link time constant,
366 move it to PARTS->symbol. */
367
368static void
369move_fixed_address_to_symbol (struct mem_address *parts,
370 struct affine_tree_combination *addr)
371{
372 unsigned i;
373 tree val = NULL_TREE;
374
375 for (i = 0; i < addr->n; i++)
376 {
377 if (addr->coefs[i] != 1)
378 continue;
379
380 val = addr->elts[i];
381 if (TREE_CODE (val) == ADDR_EXPR
382 && fixed_address_object_p (TREE_OPERAND (val, 0)))
383 break;
384 }
385
386 if (i == addr->n)
387 return;
388
389 parts->symbol = TREE_OPERAND (val, 0);
390 aff_combination_remove_elt (addr, i);
391}
392
393/* If ADDR contains an address of a dereferenced pointer, move it to
394 PARTS->base. */
395
396static void
397move_pointer_to_base (struct mem_address *parts,
398 struct affine_tree_combination *addr)
399{
400 unsigned i;
401 tree val = NULL_TREE;
402
403 for (i = 0; i < addr->n; i++)
404 {
405 if (addr->coefs[i] != 1)
406 continue;
407
408 val = addr->elts[i];
409 if (POINTER_TYPE_P (TREE_TYPE (val)))
410 break;
411 }
412
413 if (i == addr->n)
414 return;
415
416 parts->base = val;
417 aff_combination_remove_elt (addr, i);
418}
419
420/* Adds ELT to PARTS. */
421
422static void
423add_to_parts (struct mem_address *parts, tree elt)
424{
425 tree type;
426
427 if (!parts->index)
428 {
429 parts->index = elt;
430 return;
431 }
432
433 if (!parts->base)
434 {
435 parts->base = elt;
436 return;
437 }
438
439 /* Add ELT to base. */
440 type = TREE_TYPE (parts->base);
441 parts->base = fold_build2 (PLUS_EXPR, type,
442 parts->base,
443 fold_convert (type, elt));
444}
445
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. */
449
450static void
451most_expensive_mult_to_index (struct mem_address *parts,
452 struct affine_tree_combination *addr)
453{
454 unsigned HOST_WIDE_INT best_mult = 0;
455 unsigned best_mult_cost = 0, acost;
456 tree mult_elt = NULL_TREE, elt;
457 unsigned i, j;
458
459 for (i = 0; i < addr->n; i++)
460 {
461 if (addr->coefs[i] == 1
462 || !multiplier_allowed_in_address_p (addr->coefs[i]))
463 continue;
464
465 acost = multiply_by_cost (addr->coefs[i], Pmode);
466
467 if (acost > best_mult_cost)
468 {
469 best_mult_cost = acost;
470 best_mult = addr->coefs[i];
471 }
472 }
473
474 if (!best_mult)
475 return;
476
477 for (i = j = 0; i < addr->n; i++)
478 {
479 if (addr->coefs[i] != best_mult)
480 {
481 addr->coefs[j] = addr->coefs[i];
482 addr->elts[j] = addr->elts[i];
483 j++;
484 continue;
485 }
486
487 elt = fold_convert (sizetype, addr->elts[i]);
488 if (!mult_elt)
489 mult_elt = elt;
490 else
491 mult_elt = fold_build2 (PLUS_EXPR, sizetype, mult_elt, elt);
492 }
493 addr->n = j;
494
495 parts->index = mult_elt;
496 parts->step = build_int_cst_type (sizetype, best_mult);
497}
498
499/* Splits address ADDR into PARTS.
500
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. */
507
508static void
509addr_to_parts (struct affine_tree_combination *addr, struct mem_address *parts)
510{
511 unsigned i;
512 tree part;
513
514 parts->symbol = NULL_TREE;
515 parts->base = NULL_TREE;
516 parts->index = NULL_TREE;
517 parts->step = NULL_TREE;
518
519 if (addr->offset)
520 parts->offset = build_int_cst_type (sizetype, addr->offset);
521 else
522 parts->offset = NULL_TREE;
523
524 /* Try to find a symbol. */
525 move_fixed_address_to_symbol (parts, addr);
526
527 /* First move the most expensive feasible multiplication
528 to index. */
529 most_expensive_mult_to_index (parts, addr);
530
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. */
534 if (!parts->symbol)
535 move_pointer_to_base (parts, addr);
536
537 /* Then try to process the remaining elements. */
538 for (i = 0; i < addr->n; i++)
539 {
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);
545 }
546 if (addr->rest)
547 add_to_parts (parts, fold_convert (sizetype, addr->rest));
548}
549
550/* Force the PARTS to register. */
551
552static void
553gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
554{
555 if (parts->base)
556 parts->base = force_gimple_operand_bsi (bsi, parts->base,
557 true, NULL_TREE);
558 if (parts->index)
559 parts->index = force_gimple_operand_bsi (bsi, parts->index,
560 true, NULL_TREE);
561}
562
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. */
566
567tree
568create_mem_ref (block_stmt_iterator *bsi, tree type,
569 struct affine_tree_combination *addr)
570{
571 tree mem_ref, tmp;
572 tree atype;
573 struct mem_address parts;
574
575 addr_to_parts (addr, &parts);
576 gimplify_mem_ref_parts (bsi, &parts);
577 mem_ref = create_mem_ref_raw (type, &parts);
578 if (mem_ref)
579 return mem_ref;
580
581 /* The expression is too complicated. Try making it simpler. */
582
583 if (parts.step && !integer_onep (parts.step))
584 {
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),
590 true, NULL_TREE);
591 parts.step = NULL_TREE;
592
593 mem_ref = create_mem_ref_raw (type, &parts);
594 if (mem_ref)
595 return mem_ref;
596 }
597
598 if (parts.symbol)
599 {
600 tmp = build_addr (parts.symbol, current_function_decl);
601 gcc_assert (is_gimple_val (tmp));
602
603 /* Add the symbol to base, eventually forcing it to register. */
604 if (parts.base)
605 {
606 gcc_assert (TREE_TYPE (parts.base) == sizetype);
607
608 if (parts.index)
609 {
610 atype = TREE_TYPE (tmp);
611 parts.base = force_gimple_operand_bsi (bsi,
612 fold_build2 (PLUS_EXPR, atype,
613 fold_convert (atype, parts.base),
614 tmp),
615 true, NULL_TREE);
616 }
617 else
618 {
619 parts.index = parts.base;
620 parts.base = tmp;
621 }
622 }
623 else
624 parts.base = tmp;
625 parts.symbol = NULL_TREE;
626
627 mem_ref = create_mem_ref_raw (type, &parts);
628 if (mem_ref)
629 return mem_ref;
630 }
631
632 if (parts.index)
633 {
634 /* Add index to base. */
635 if (parts.base)
636 {
637 atype = TREE_TYPE (parts.base);
638 parts.base = force_gimple_operand_bsi (bsi,
639 fold_build2 (PLUS_EXPR, atype,
640 parts.base,
641 fold_convert (atype, parts.index)),
642 true, NULL_TREE);
643 }
644 else
645 parts.base = parts.index;
646 parts.index = NULL_TREE;
647
648 mem_ref = create_mem_ref_raw (type, &parts);
649 if (mem_ref)
650 return mem_ref;
651 }
652
653 if (parts.offset && !integer_zerop (parts.offset))
654 {
655 /* Try adding offset to base. */
656 if (parts.base)
657 {
658 atype = TREE_TYPE (parts.base);
659 parts.base = force_gimple_operand_bsi (bsi,
660 fold_build2 (PLUS_EXPR, atype,
661 parts.base,
662 fold_convert (atype, parts.offset)),
663 true, NULL_TREE);
664 }
665 else
666 parts.base = parts.offset;
667
668 parts.offset = NULL_TREE;
669
670 mem_ref = create_mem_ref_raw (type, &parts);
671 if (mem_ref)
672 return mem_ref;
673 }
674
675 /* Verify that the address is in the simplest possible shape
676 (only a register). If we cannot create such a memory reference,
677 something is really wrong. */
678 gcc_assert (parts.symbol == NULL_TREE);
679 gcc_assert (parts.index == NULL_TREE);
680 gcc_assert (!parts.step || integer_onep (parts.step));
681 gcc_assert (!parts.offset || integer_zerop (parts.offset));
682 gcc_unreachable ();
683}
684
685/* Copies components of the address from OP to ADDR. */
686
687void
688get_address_description (tree op, struct mem_address *addr)
689{
690 addr->symbol = TMR_SYMBOL (op);
691 addr->base = TMR_BASE (op);
692 addr->index = TMR_INDEX (op);
693 addr->step = TMR_STEP (op);
694 addr->offset = TMR_OFFSET (op);
695}
696
697/* Copies the additional information attached to target_mem_ref FROM to TO. */
698
699void
700copy_mem_ref_info (tree to, tree from)
701{
702 /* Copy the annotation, to preserve the aliasing information. */
703 TMR_TAG (to) = TMR_TAG (from);
704
705 /* And the info about the original reference. */
706 TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
707}
708
709/* Move constants in target_mem_ref REF to offset. Returns the new target
710 mem ref if anything changes, NULL_TREE otherwise. */
711
712tree
713maybe_fold_tmr (tree ref)
714{
715 struct mem_address addr;
716 bool changed = false;
717 tree ret, off;
718
719 get_address_description (ref, &addr);
720
721 if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
722 {
723 if (addr.offset)
724 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
725 addr.offset,
726 fold_convert (sizetype, addr.base));
727 else
728 addr.offset = addr.base;
729
730 addr.base = NULL_TREE;
731 changed = true;
732 }
733
734 if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
735 {
736 off = addr.index;
737 if (addr.step)
738 {
739 off = fold_binary_to_constant (MULT_EXPR, sizetype,
740 off, addr.step);
741 addr.step = NULL_TREE;
742 }
743
744 if (addr.offset)
745 {
746 addr.offset = fold_binary_to_constant (PLUS_EXPR, sizetype,
747 addr.offset, off);
748 }
749 else
750 addr.offset = off;
751
752 addr.index = NULL_TREE;
753 changed = true;
754 }
755
756 if (!changed)
757 return NULL_TREE;
758
759 ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
760 if (!ret)
761 return NULL_TREE;
762
763 copy_mem_ref_info (ret, ref);
764 return ret;
765}
766
767/* Dump PARTS to FILE. */
768
769extern void dump_mem_address (FILE *, struct mem_address *);
770void
771dump_mem_address (FILE *file, struct mem_address *parts)
772{
773 if (parts->symbol)
774 {
775 fprintf (file, "symbol: ");
776 print_generic_expr (file, parts->symbol, TDF_SLIM);
777 fprintf (file, "\n");
778 }
779 if (parts->base)
780 {
781 fprintf (file, "base: ");
782 print_generic_expr (file, parts->base, TDF_SLIM);
783 fprintf (file, "\n");
784 }
785 if (parts->index)
786 {
787 fprintf (file, "index: ");
788 print_generic_expr (file, parts->index, TDF_SLIM);
789 fprintf (file, "\n");
790 }
791 if (parts->step)
792 {
793 fprintf (file, "step: ");
794 print_generic_expr (file, parts->step, TDF_SLIM);
795 fprintf (file, "\n");
796 }
797 if (parts->offset)
798 {
799 fprintf (file, "offset: ");
800 print_generic_expr (file, parts->offset, TDF_SLIM);
801 fprintf (file, "\n");
802 }
803}
804
805#include "gt-tree-ssa-address.h"