OSDN Git Service

* tree-ssa-loop-ivopts.c: Include tree-affine.h.
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-address.c
1 /* Memory address lowering and addressing mode selection.
2    Copyright (C) 2004 Free Software Foundation, Inc.
3    
4 This file is part of GCC.
5    
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.
10    
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.
15    
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.  */
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 #include "tree-affine.h"
46
47 /* TODO -- handling of symbols (according to Richard Hendersons
48    comments, http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00949.html):
49    
50    There are at least 5 different kinds of symbols that we can run up against:
51
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
57
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"))).
61
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).
65
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.  */
70
71 /* A "template" for memory address, used to determine whether the address is
72    valid for mode.  */
73
74 struct mem_addr_template GTY (())
75 {
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.  */
81 };
82
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.  */
85
86 static GTY (()) struct mem_addr_template templates[32];
87
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))
94
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.  */
98
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)
102 {
103   rtx act_elem;
104
105   *addr = NULL_RTX;
106   if (step_p)
107     *step_p = NULL;
108   if (offset_p)
109     *offset_p = NULL;
110
111   if (index)
112     {
113       act_elem = index;
114       if (step)
115         {
116           act_elem = gen_rtx_MULT (Pmode, act_elem, step);
117
118           if (step_p)
119             *step_p = &XEXP (act_elem, 1);
120         }
121
122       *addr = act_elem;
123     }
124
125   if (base)
126     {
127       if (*addr)
128         *addr = gen_rtx_PLUS (Pmode, *addr, base);
129       else
130         *addr = base;
131     }
132
133   if (symbol)
134     {
135       act_elem = symbol;
136       if (offset)
137         {
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);
142         }
143
144       if (*addr)
145         *addr = gen_rtx_PLUS (Pmode, *addr, act_elem);
146       else
147         *addr = act_elem;
148     }
149   else if (offset)
150     {
151       if (*addr)
152         {
153           *addr = gen_rtx_PLUS (Pmode, *addr, offset);
154           if (offset_p)
155             *offset_p = &XEXP (*addr, 1);
156         }
157       else
158         {
159           *addr = offset;
160           if (offset_p)
161             *offset_p = addr;
162         }
163     }
164
165   if (!*addr)
166     *addr = const0_rtx;
167 }
168
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".  */
173
174 rtx
175 addr_for_mem_ref (struct mem_address *addr, bool really_expand)
176 {
177   rtx address, sym, bse, idx, st, off;
178   static bool templates_initialized = false;
179   struct mem_addr_template *templ;
180
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;
186
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;
192
193   if (!really_expand)
194     {
195       /* Reuse the templates for addresses, so that we do not waste memory.  */
196       if (!templates_initialized)
197         {
198           unsigned i;
199
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);
204
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);
214         }
215
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;
222
223       return templ->ref;
224     }
225
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);
237
238   gen_addr_rtx (sym, bse, idx, st, off, &address, NULL, NULL);
239   return address;
240 }
241
242 /* Returns address of MEM_REF in TYPE.  */
243
244 tree
245 tree_mem_ref_addr (tree type, tree mem_ref)
246 {
247   tree addr = NULL_TREE;
248   tree act_elem;
249   tree step = TMR_STEP (mem_ref), offset = TMR_OFFSET (mem_ref);
250
251   act_elem = TMR_INDEX (mem_ref);
252   if (act_elem)
253     {
254       act_elem = fold_convert (type, act_elem);
255
256       if (step)
257         act_elem = fold_build2 (MULT_EXPR, type, act_elem,
258                                 fold_convert (type, step));
259       addr = act_elem;
260     }
261
262   act_elem = TMR_BASE (mem_ref);
263   if (act_elem)
264     {
265       act_elem = fold_convert (type, act_elem);
266
267       if (addr)
268         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
269       else
270         addr = act_elem;
271     }
272
273   act_elem = TMR_SYMBOL (mem_ref);
274   if (act_elem)
275     {
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;
282     }
283
284   if (!zero_p (offset))
285     {
286       act_elem = fold_convert (type, offset);
287
288       if (addr)
289         addr = fold_build2 (PLUS_EXPR, type, addr, act_elem);
290       else
291         addr = act_elem;
292     }
293
294   if (!addr)
295     addr = build_int_cst (type, 0);
296
297   return addr;
298 }
299
300 /* Returns true if a memory reference in MODE and with parameters given by
301    ADDR is valid on the current target.  */
302
303 static bool
304 valid_mem_ref_p (enum machine_mode mode, struct mem_address *addr)
305 {
306   rtx address;
307
308   address = addr_for_mem_ref (addr, false);
309   if (!address)
310     return false;
311
312   return memory_address_p (mode, address);
313 }
314
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.  */
318
319 static tree
320 create_mem_ref_raw (tree type, struct mem_address *addr)
321 {
322   if (!valid_mem_ref_p (TYPE_MODE (type), addr))
323     return NULL_TREE;
324
325   if (addr->step && integer_onep (addr->step))
326     addr->step = NULL_TREE;
327
328   if (addr->offset && zero_p (addr->offset))
329     addr->offset = NULL_TREE;
330
331   return build7 (TARGET_MEM_REF, type,
332                  addr->symbol, addr->base, addr->index,
333                  addr->step, addr->offset, NULL, NULL);
334 }
335
336 /* Returns true if OBJ is an object whose address is a link time constant.  */
337
338 static bool
339 fixed_address_object_p (tree obj)
340 {
341   return (TREE_CODE (obj) == VAR_DECL
342           && (TREE_STATIC (obj)
343               || DECL_EXTERNAL (obj)));
344 }
345
346 /* Adds COEF * ELT to PARTS.  TYPE is the type of the address we
347    construct.  */
348
349 static void
350 add_to_parts (struct mem_address *parts, tree type, tree elt)
351 {
352   tree elt_core = elt;
353   STRIP_NOPS (elt_core);
354
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)))
359     {
360       parts->symbol = TREE_OPERAND (elt_core, 0);
361       return;
362     }
363
364   if (!parts->base)
365     {
366       parts->base = elt;
367       return;
368     }
369
370   if (!parts->index)
371     {
372       parts->index = elt;
373       return;
374     }
375
376   /* Add ELT to base.  */
377   parts->base = fold_build2 (PLUS_EXPR, type, parts->base, elt);
378 }
379
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.  */
384
385 static void
386 most_expensive_mult_to_index (struct mem_address *parts, tree type,
387                               aff_tree *addr)
388 {
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;
395
396   best_mult = double_int_zero;
397   for (i = 0; i < addr->n; i++)
398     {
399       if (!double_int_fits_in_shwi_p (addr->elts[i].coef))
400         continue;
401
402       /* FIXME: Should use the correct memory mode rather than Pmode.  */
403
404       coef = double_int_to_shwi (addr->elts[i].coef);
405       if (coef == 1
406           || !multiplier_allowed_in_address_p (coef, Pmode))
407         continue;
408
409       acost = multiply_by_cost (coef, Pmode);
410
411       if (acost > best_mult_cost)
412         {
413           best_mult_cost = acost;
414           best_mult = addr->elts[i].coef;
415         }
416     }
417
418   if (!best_mult_cost)
419     return;
420
421   /* Collect elements multiplied by best_mult.  */
422   for (i = j = 0; i < addr->n; i++)
423     {
424       amult = addr->elts[i].coef;
425       amult_neg = double_int_ext_for_comb (double_int_neg (amult), addr);
426  
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
432         {
433           addr->elts[j] = addr->elts[i];
434           j++;
435           continue;
436         }
437   
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);
445     }
446   addr->n = j;
447   
448   parts->index = mult_elt;
449   parts->step = double_int_to_tree (type, best_mult);
450 }
451
452 /* Splits address ADDR into PARTS.
453    
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.  */
460
461 static void
462 addr_to_parts (aff_tree *addr, tree type, struct mem_address *parts)
463 {
464   tree part;
465   unsigned i;
466
467   parts->symbol = NULL_TREE;
468   parts->base = NULL_TREE;
469   parts->index = NULL_TREE;
470   parts->step = NULL_TREE;
471
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;
476
477   /* First move the most expensive feasible multiplication
478      to index.  */
479   most_expensive_mult_to_index (parts, type, addr);
480
481   /* Then try to process the remaining elements.  */
482   for (i = 0; i < addr->n; i++)
483     {
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);
489     }
490   if (addr->rest)
491     add_to_parts (parts, type, addr->rest);
492 }
493
494 /* Force the PARTS to register.  */
495
496 static void
497 gimplify_mem_ref_parts (block_stmt_iterator *bsi, struct mem_address *parts)
498 {
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);
505 }
506
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.  */
510
511 tree
512 create_mem_ref (block_stmt_iterator *bsi, tree type, aff_tree *addr)
513 {
514   tree mem_ref, tmp;
515   tree addr_type = build_pointer_type (type);
516   struct mem_address parts;
517
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;
523
524   /* The expression is too complicated.  Try making it simpler.  */
525
526   if (parts.step && !integer_onep (parts.step))
527     {
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;
535   
536       mem_ref = create_mem_ref_raw (type, &parts);
537       if (mem_ref)
538         return mem_ref;
539     }
540
541   if (parts.symbol)
542     {
543       tmp = build_addr (parts.symbol, current_function_decl);
544     
545       /* Add the symbol to base, eventually forcing it to register.  */
546       if (parts.base)
547         {
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
554             {
555               parts.index = parts.base;
556               parts.base = tmp;
557             }
558         }
559       else
560         parts.base = tmp;
561       parts.symbol = NULL_TREE;
562
563       mem_ref = create_mem_ref_raw (type, &parts);
564       if (mem_ref)
565         return mem_ref;
566     }
567
568   if (parts.base)
569     {
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;
580
581       mem_ref = create_mem_ref_raw (type, &parts);
582       if (mem_ref)
583         return mem_ref;
584     }
585
586   if (parts.offset && !integer_zerop (parts.offset))
587     {
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;
597
598       parts.offset = NULL_TREE;
599
600       mem_ref = create_mem_ref_raw (type, &parts);
601       if (mem_ref)
602         return mem_ref;
603     }
604
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 ();
613 }
614
615 /* Copies components of the address from OP to ADDR.  */
616
617 void
618 get_address_description (tree op, struct mem_address *addr)
619 {
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);
625 }
626
627 /* Copies the additional information attached to target_mem_ref FROM to TO.  */
628
629 void
630 copy_mem_ref_info (tree to, tree from)
631 {
632   /* Copy the annotation, to preserve the aliasing information.  */
633   TMR_TAG (to) = TMR_TAG (from);
634
635   /* And the info about the original reference.  */
636   TMR_ORIGINAL (to) = TMR_ORIGINAL (from);
637 }
638
639 /* Move constants in target_mem_ref REF to offset.  Returns the new target
640    mem ref if anything changes, NULL_TREE otherwise.  */
641
642 tree
643 maybe_fold_tmr (tree ref)
644 {
645   struct mem_address addr;
646   bool changed = false;
647   tree ret, off;
648
649   get_address_description (ref, &addr);
650
651   if (addr.base && TREE_CODE (addr.base) == INTEGER_CST)
652     {
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;
658
659       addr.base = NULL_TREE;
660       changed = true;
661     }
662
663   if (addr.index && TREE_CODE (addr.index) == INTEGER_CST)
664     {
665       off = addr.index;
666       if (addr.step)
667         {
668           off = fold_binary_to_constant (MULT_EXPR, ptr_type_node,
669                                          off, addr.step);
670           addr.step = NULL_TREE;
671         }
672
673       if (addr.offset)
674         {
675           addr.offset = fold_binary_to_constant (PLUS_EXPR, ptr_type_node,
676                                                  addr.offset, off);
677         }
678       else
679         addr.offset = off;
680
681       addr.index = NULL_TREE;
682       changed = true;
683     }
684
685   if (!changed)
686     return NULL_TREE;
687   
688   ret = create_mem_ref_raw (TREE_TYPE (ref), &addr);
689   if (!ret)
690     return NULL_TREE;
691
692   copy_mem_ref_info (ret, ref);
693   return ret;
694 }
695
696 /* Dump PARTS to FILE.  */
697
698 extern void dump_mem_address (FILE *, struct mem_address *);
699 void
700 dump_mem_address (FILE *file, struct mem_address *parts)
701 {
702   if (parts->symbol)
703     {
704       fprintf (file, "symbol: ");
705       print_generic_expr (file, parts->symbol, TDF_SLIM);
706       fprintf (file, "\n");
707     }
708   if (parts->base)
709     {
710       fprintf (file, "base: ");
711       print_generic_expr (file, parts->base, TDF_SLIM);
712       fprintf (file, "\n");
713     }
714   if (parts->index)
715     {
716       fprintf (file, "index: ");
717       print_generic_expr (file, parts->index, TDF_SLIM);
718       fprintf (file, "\n");
719     }
720   if (parts->step)
721     {
722       fprintf (file, "step: ");
723       print_generic_expr (file, parts->step, TDF_SLIM);
724       fprintf (file, "\n");
725     }
726   if (parts->offset)
727     {
728       fprintf (file, "offset: ");
729       print_generic_expr (file, parts->offset, TDF_SLIM);
730       fprintf (file, "\n");
731     }
732 }
733
734 #include "gt-tree-ssa-address.h"