OSDN Git Service

2009-10-15 Andrew Pinski <andrew_pinski@playstation.sony.com>
[pf3gnuchains/gcc-fork.git] / gcc / rtl.c
1 /* RTL utility routines.
2    Copyright (C) 1987, 1988, 1991, 1994, 1997, 1998, 1999, 2000, 2001, 2002,
3    2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This file is compiled twice: once for the generator programs
22    once for the compiler.  */
23 #ifdef GENERATOR_FILE
24 #include "bconfig.h"
25 #else
26 #include "config.h"
27 #endif
28
29 #include "system.h"
30 #include "coretypes.h"
31 #include "tm.h"
32 #include "rtl.h"
33 #include "real.h"
34 #include "ggc.h"
35 #ifdef GENERATOR_FILE
36 # include "errors.h"
37 #else
38 # include "toplev.h"
39 #endif
40
41 \f
42 /* Indexed by rtx code, gives number of operands for an rtx with that code.
43    Does NOT include rtx header data (code and links).  */
44
45 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
46
47 const unsigned char rtx_length[NUM_RTX_CODE] = {
48 #include "rtl.def"
49 };
50
51 #undef DEF_RTL_EXPR
52
53 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
54
55 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
56
57 const char * const rtx_name[NUM_RTX_CODE] = {
58 #include "rtl.def"              /* rtl expressions are documented here */
59 };
60
61 #undef DEF_RTL_EXPR
62
63 /* Indexed by rtx code, gives a sequence of operand-types for
64    rtx's of that code.  The sequence is a C string in which
65    each character describes one operand.  */
66
67 const char * const rtx_format[NUM_RTX_CODE] = {
68   /* "*" undefined.
69          can cause a warning message
70      "0" field is unused (or used in a phase-dependent manner)
71          prints nothing
72      "i" an integer
73          prints the integer
74      "n" like "i", but prints entries from `note_insn_name'
75      "w" an integer of width HOST_BITS_PER_WIDE_INT
76          prints the integer
77      "s" a pointer to a string
78          prints the string
79      "S" like "s", but optional:
80          the containing rtx may end before this operand
81      "T" like "s", but treated specially by the RTL reader;
82          only found in machine description patterns.
83      "e" a pointer to an rtl expression
84          prints the expression
85      "E" a pointer to a vector that points to a number of rtl expressions
86          prints a list of the rtl expressions
87      "V" like "E", but optional:
88          the containing rtx may end before this operand
89      "u" a pointer to another insn
90          prints the uid of the insn.
91      "b" is a pointer to a bitmap header.
92      "B" is a basic block pointer.
93      "t" is a tree pointer.  */
94
95 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
96 #include "rtl.def"              /* rtl expressions are defined here */
97 #undef DEF_RTL_EXPR
98 };
99
100 /* Indexed by rtx code, gives a character representing the "class" of
101    that rtx code.  See rtl.def for documentation on the defined classes.  */
102
103 const enum rtx_class rtx_class[NUM_RTX_CODE] = {
104 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
105 #include "rtl.def"              /* rtl expressions are defined here */
106 #undef DEF_RTL_EXPR
107 };
108
109 /* Indexed by rtx code, gives the size of the rtx in bytes.  */
110
111 const unsigned char rtx_code_size[NUM_RTX_CODE] = {
112 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)                         \
113   ((ENUM) == CONST_INT || (ENUM) == CONST_DOUBLE || (ENUM) == CONST_FIXED\
114    ? RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (HOST_WIDE_INT)        \
115    : RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (rtunion)),
116
117 #include "rtl.def"
118 #undef DEF_RTL_EXPR
119 };
120
121 /* Names for kinds of NOTEs and REG_NOTEs.  */
122
123 const char * const note_insn_name[NOTE_INSN_MAX] =
124 {
125 #define DEF_INSN_NOTE(NAME) #NAME,
126 #include "insn-notes.def"
127 #undef DEF_INSN_NOTE
128 };
129
130 const char * const reg_note_name[REG_NOTE_MAX] =
131 {
132 #define DEF_REG_NOTE(NAME) #NAME,
133 #include "reg-notes.def"
134 #undef DEF_REG_NOTE
135 };
136
137 #ifdef GATHER_STATISTICS
138 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
139 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
140 static int rtvec_alloc_counts;
141 static int rtvec_alloc_sizes;
142 #endif
143
144 \f
145 /* Allocate an rtx vector of N elements.
146    Store the length, and initialize all elements to zero.  */
147
148 rtvec
149 rtvec_alloc (int n)
150 {
151   rtvec rt;
152
153   rt = ggc_alloc_rtvec (n);
154   /* Clear out the vector.  */
155   memset (&rt->elem[0], 0, n * sizeof (rtx));
156
157   PUT_NUM_ELEM (rt, n);
158
159 #ifdef GATHER_STATISTICS
160   rtvec_alloc_counts++;
161   rtvec_alloc_sizes += n * sizeof (rtx);
162 #endif
163
164   return rt;
165 }
166
167 /* Return the number of bytes occupied by rtx value X.  */
168
169 unsigned int
170 rtx_size (const_rtx x)
171 {
172   if (GET_CODE (x) == SYMBOL_REF && SYMBOL_REF_HAS_BLOCK_INFO_P (x))
173     return RTX_HDR_SIZE + sizeof (struct block_symbol);
174   return RTX_CODE_SIZE (GET_CODE (x));
175 }
176
177 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
178    all the rest is initialized to zero.  */
179
180 rtx
181 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
182 {
183   rtx rt;
184
185   rt = (rtx) ggc_alloc_zone_pass_stat (RTX_CODE_SIZE (code), &rtl_zone);
186
187   /* We want to clear everything up to the FLD array.  Normally, this
188      is one int, but we don't want to assume that and it isn't very
189      portable anyway; this is.  */
190
191   memset (rt, 0, RTX_HDR_SIZE);
192   PUT_CODE (rt, code);
193
194 #ifdef GATHER_STATISTICS
195   rtx_alloc_counts[code]++;
196   rtx_alloc_sizes[code] += RTX_CODE_SIZE (code);
197 #endif
198
199   return rt;
200 }
201
202 \f
203 /* Return true if ORIG is a sharable CONST.  */
204
205 bool
206 shared_const_p (const_rtx orig)
207 {
208   gcc_assert (GET_CODE (orig) == CONST);
209   
210   /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
211      a LABEL_REF, it isn't sharable.  */
212   return (GET_CODE (XEXP (orig, 0)) == PLUS
213           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
214           && CONST_INT_P(XEXP (XEXP (orig, 0), 1)));
215 }
216
217
218 /* Create a new copy of an rtx.
219    Recursively copies the operands of the rtx,
220    except for those few rtx codes that are sharable.  */
221
222 rtx
223 copy_rtx (rtx orig)
224 {
225   rtx copy;
226   int i, j;
227   RTX_CODE code;
228   const char *format_ptr;
229
230   code = GET_CODE (orig);
231
232   switch (code)
233     {
234     case REG:
235     case DEBUG_EXPR:
236     case VALUE:
237     case CONST_INT:
238     case CONST_DOUBLE:
239     case CONST_FIXED:
240     case CONST_VECTOR:
241     case SYMBOL_REF:
242     case CODE_LABEL:
243     case PC:
244     case CC0:
245     case SCRATCH:
246       /* SCRATCH must be shared because they represent distinct values.  */
247       return orig;
248     case CLOBBER:
249       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
250         return orig;
251       break;
252
253     case CONST:
254       if (shared_const_p (orig))
255         return orig;
256       break;
257
258       /* A MEM with a constant address is not sharable.  The problem is that
259          the constant address may need to be reloaded.  If the mem is shared,
260          then reloading one copy of this mem will cause all copies to appear
261          to have been reloaded.  */
262
263     default:
264       break;
265     }
266
267   /* Copy the various flags, fields, and other information.  We assume
268      that all fields need copying, and then clear the fields that should
269      not be copied.  That is the sensible default behavior, and forces
270      us to explicitly document why we are *not* copying a flag.  */
271   copy = shallow_copy_rtx (orig);
272
273   /* We do not copy the USED flag, which is used as a mark bit during
274      walks over the RTL.  */
275   RTX_FLAG (copy, used) = 0;
276
277   /* We do not copy FRAME_RELATED for INSNs.  */
278   if (INSN_P (orig))
279     RTX_FLAG (copy, frame_related) = 0;
280   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
281   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
282
283   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
284
285   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
286     switch (*format_ptr++)
287       {
288       case 'e':
289         if (XEXP (orig, i) != NULL)
290           XEXP (copy, i) = copy_rtx (XEXP (orig, i));
291         break;
292
293       case 'E':
294       case 'V':
295         if (XVEC (orig, i) != NULL)
296           {
297             XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
298             for (j = 0; j < XVECLEN (copy, i); j++)
299               XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
300           }
301         break;
302
303       case 't':
304       case 'w':
305       case 'i':
306       case 's':
307       case 'S':
308       case 'T':
309       case 'u':
310       case 'B':
311       case '0':
312         /* These are left unchanged.  */
313         break;
314
315       default:
316         gcc_unreachable ();
317       }
318   return copy;
319 }
320
321 /* Create a new copy of an rtx.  Only copy just one level.  */
322
323 rtx
324 shallow_copy_rtx_stat (const_rtx orig MEM_STAT_DECL)
325 {
326   const unsigned int size = rtx_size (orig);
327   rtx const copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
328   return (rtx) memcpy (copy, orig, size);
329 }
330 \f
331 /* Nonzero when we are generating CONCATs.  */
332 int generating_concat_p;
333
334 /* Nonzero when we are expanding trees to RTL.  */
335 int currently_expanding_to_rtl;
336
337 \f
338
339 /* Same as rtx_equal_p, but call CB on each pair of rtx if CB is not NULL.  
340    When the callback returns true, we continue with the new pair.
341    Whenever changing this function check if rtx_equal_p below doesn't need
342    changing as well.  */
343
344 int
345 rtx_equal_p_cb (const_rtx x, const_rtx y, rtx_equal_p_callback_function cb)
346 {
347   int i;
348   int j;
349   enum rtx_code code;
350   const char *fmt;
351   rtx nx, ny;
352
353   if (x == y)
354     return 1;
355   if (x == 0 || y == 0)
356     return 0;
357
358   /* Invoke the callback first.  */
359   if (cb != NULL
360       && ((*cb) (&x, &y, &nx, &ny)))
361     return rtx_equal_p_cb (nx, ny, cb);
362
363   code = GET_CODE (x);
364   /* Rtx's of different codes cannot be equal.  */
365   if (code != GET_CODE (y))
366     return 0;
367
368   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
369      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
370
371   if (GET_MODE (x) != GET_MODE (y))
372     return 0;
373
374   /* Some RTL can be compared nonrecursively.  */
375   switch (code)
376     {
377     case REG:
378       return (REGNO (x) == REGNO (y));
379
380     case LABEL_REF:
381       return XEXP (x, 0) == XEXP (y, 0);
382
383     case SYMBOL_REF:
384       return XSTR (x, 0) == XSTR (y, 0);
385
386     case DEBUG_EXPR:
387     case VALUE:
388     case SCRATCH:
389     case CONST_DOUBLE:
390     case CONST_INT:
391     case CONST_FIXED:
392       return 0;
393
394     default:
395       break;
396     }
397
398   /* Compare the elements.  If any pair of corresponding elements
399      fail to match, return 0 for the whole thing.  */
400
401   fmt = GET_RTX_FORMAT (code);
402   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
403     {
404       switch (fmt[i])
405         {
406         case 'w':
407           if (XWINT (x, i) != XWINT (y, i))
408             return 0;
409           break;
410
411         case 'n':
412         case 'i':
413           if (XINT (x, i) != XINT (y, i))
414             return 0;
415           break;
416
417         case 'V':
418         case 'E':
419           /* Two vectors must have the same length.  */
420           if (XVECLEN (x, i) != XVECLEN (y, i))
421             return 0;
422
423           /* And the corresponding elements must match.  */
424           for (j = 0; j < XVECLEN (x, i); j++)
425             if (rtx_equal_p_cb (XVECEXP (x, i, j), 
426                                 XVECEXP (y, i, j), cb) == 0)
427               return 0;
428           break;
429
430         case 'e':
431           if (rtx_equal_p_cb (XEXP (x, i), XEXP (y, i), cb) == 0)
432             return 0;
433           break;
434
435         case 'S':
436         case 's':
437           if ((XSTR (x, i) || XSTR (y, i))
438               && (! XSTR (x, i) || ! XSTR (y, i)
439                   || strcmp (XSTR (x, i), XSTR (y, i))))
440             return 0;
441           break;
442
443         case 'u':
444           /* These are just backpointers, so they don't matter.  */
445           break;
446
447         case '0':
448         case 't':
449           break;
450
451           /* It is believed that rtx's at this level will never
452              contain anything but integers and other rtx's,
453              except for within LABEL_REFs and SYMBOL_REFs.  */
454         default:
455           gcc_unreachable ();
456         }
457     }
458   return 1;
459 }
460
461 /* Return 1 if X and Y are identical-looking rtx's.
462    This is the Lisp function EQUAL for rtx arguments.
463    Whenever changing this function check if rtx_equal_p_cb above doesn't need
464    changing as well.  */
465
466 int
467 rtx_equal_p (const_rtx x, const_rtx y)
468 {
469   int i;
470   int j;
471   enum rtx_code code;
472   const char *fmt;
473
474   if (x == y)
475     return 1;
476   if (x == 0 || y == 0)
477     return 0;
478
479   code = GET_CODE (x);
480   /* Rtx's of different codes cannot be equal.  */
481   if (code != GET_CODE (y))
482     return 0;
483
484   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
485      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
486
487   if (GET_MODE (x) != GET_MODE (y))
488     return 0;
489
490   /* Some RTL can be compared nonrecursively.  */
491   switch (code)
492     {
493     case REG:
494       return (REGNO (x) == REGNO (y));
495
496     case LABEL_REF:
497       return XEXP (x, 0) == XEXP (y, 0);
498
499     case SYMBOL_REF:
500       return XSTR (x, 0) == XSTR (y, 0);
501
502     case DEBUG_EXPR:
503     case VALUE:
504     case SCRATCH:
505     case CONST_DOUBLE:
506     case CONST_INT:
507     case CONST_FIXED:
508       return 0;
509
510     default:
511       break;
512     }
513
514   /* Compare the elements.  If any pair of corresponding elements
515      fail to match, return 0 for the whole thing.  */
516
517   fmt = GET_RTX_FORMAT (code);
518   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
519     {
520       switch (fmt[i])
521         {
522         case 'w':
523           if (XWINT (x, i) != XWINT (y, i))
524             return 0;
525           break;
526
527         case 'n':
528         case 'i':
529           if (XINT (x, i) != XINT (y, i))
530             return 0;
531           break;
532
533         case 'V':
534         case 'E':
535           /* Two vectors must have the same length.  */
536           if (XVECLEN (x, i) != XVECLEN (y, i))
537             return 0;
538
539           /* And the corresponding elements must match.  */
540           for (j = 0; j < XVECLEN (x, i); j++)
541             if (rtx_equal_p (XVECEXP (x, i, j),  XVECEXP (y, i, j)) == 0)
542               return 0;
543           break;
544
545         case 'e':
546           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
547             return 0;
548           break;
549
550         case 'S':
551         case 's':
552           if ((XSTR (x, i) || XSTR (y, i))
553               && (! XSTR (x, i) || ! XSTR (y, i)
554                   || strcmp (XSTR (x, i), XSTR (y, i))))
555             return 0;
556           break;
557
558         case 'u':
559           /* These are just backpointers, so they don't matter.  */
560           break;
561
562         case '0':
563         case 't':
564           break;
565
566           /* It is believed that rtx's at this level will never
567              contain anything but integers and other rtx's,
568              except for within LABEL_REFs and SYMBOL_REFs.  */
569         default:
570           gcc_unreachable ();
571         }
572     }
573   return 1;
574 }
575
576 void
577 dump_rtx_statistics (void)
578 {
579 #ifdef GATHER_STATISTICS
580   int i;
581   int total_counts = 0;
582   int total_sizes = 0;
583   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
584   fprintf (stderr, "---------------------------------------\n");
585   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
586     if (rtx_alloc_counts[i])
587       {
588         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
589                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
590         total_counts += rtx_alloc_counts[i];
591         total_sizes += rtx_alloc_sizes[i];
592       }
593   if (rtvec_alloc_counts)
594     {
595       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
596                rtvec_alloc_counts, rtvec_alloc_sizes);
597       total_counts += rtvec_alloc_counts;
598       total_sizes += rtvec_alloc_sizes;
599     }
600   fprintf (stderr, "---------------------------------------\n");
601   fprintf (stderr, "%-20s %7d %10d\n",
602            "Total", total_counts, total_sizes);
603   fprintf (stderr, "---------------------------------------\n");
604 #endif  
605 }
606 \f
607 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
608 void
609 rtl_check_failed_bounds (const_rtx r, int n, const char *file, int line,
610                          const char *func)
611 {
612   internal_error
613     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
614      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
615      func, trim_filename (file), line);
616 }
617
618 void
619 rtl_check_failed_type1 (const_rtx r, int n, int c1, const char *file, int line,
620                         const char *func)
621 {
622   internal_error
623     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
624      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
625      func, trim_filename (file), line);
626 }
627
628 void
629 rtl_check_failed_type2 (const_rtx r, int n, int c1, int c2, const char *file,
630                         int line, const char *func)
631 {
632   internal_error
633     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
634      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
635      func, trim_filename (file), line);
636 }
637
638 void
639 rtl_check_failed_code1 (const_rtx r, enum rtx_code code, const char *file,
640                         int line, const char *func)
641 {
642   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
643                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
644                   trim_filename (file), line);
645 }
646
647 void
648 rtl_check_failed_code2 (const_rtx r, enum rtx_code code1, enum rtx_code code2,
649                         const char *file, int line, const char *func)
650 {
651   internal_error
652     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
653      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
654      func, trim_filename (file), line);
655 }
656
657 void
658 rtl_check_failed_code_mode (const_rtx r, enum rtx_code code, enum machine_mode mode,
659                             bool not_mode, const char *file, int line,
660                             const char *func)
661 {
662   internal_error ((not_mode
663                    ? ("RTL check: expected code '%s' and not mode '%s', "
664                       "have code '%s' and mode '%s' in %s, at %s:%d")
665                    : ("RTL check: expected code '%s' and mode '%s', "
666                       "have code '%s' and mode '%s' in %s, at %s:%d")),
667                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
668                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
669                   func, trim_filename (file), line);
670 }
671
672 /* Report that line LINE of FILE tried to access the block symbol fields
673    of a non-block symbol.  FUNC is the function that contains the line.  */
674
675 void
676 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
677 {
678   internal_error
679     ("RTL check: attempt to treat non-block symbol as a block symbol "
680      "in %s, at %s:%d", func, trim_filename (file), line);
681 }
682
683 /* XXX Maybe print the vector?  */
684 void
685 rtvec_check_failed_bounds (const_rtvec r, int n, const char *file, int line,
686                            const char *func)
687 {
688   internal_error
689     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
690      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
691 }
692 #endif /* ENABLE_RTL_CHECKING */
693
694 #if defined ENABLE_RTL_FLAG_CHECKING
695 void
696 rtl_check_failed_flag (const char *name, const_rtx r, const char *file,
697                        int line, const char *func)
698 {
699   internal_error
700     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
701      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
702 }
703 #endif /* ENABLE_RTL_FLAG_CHECKING */