OSDN Git Service

Merge from pch-branch up to tag pch-commit-20020603.
[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    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 2, 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 COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "rtl.h"
25 #include "real.h"
26 #include "ggc.h"
27 #include "errors.h"
28
29 \f
30 /* Indexed by rtx code, gives number of operands for an rtx with that code.
31    Does NOT include rtx header data (code and links).  */
32
33 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
34
35 const unsigned char rtx_length[NUM_RTX_CODE] = {
36 #include "rtl.def"
37 };
38
39 #undef DEF_RTL_EXPR
40
41 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
42
43 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
44
45 const char * const rtx_name[NUM_RTX_CODE] = {
46 #include "rtl.def"              /* rtl expressions are documented here */
47 };
48
49 #undef DEF_RTL_EXPR
50
51 /* Indexed by machine mode, gives the name of that machine mode.
52    This name does not include the letters "mode".  */
53
54 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  NAME,
55
56 const char * const mode_name[NUM_MACHINE_MODES] = {
57 #include "machmode.def"
58 };
59
60 #undef DEF_MACHMODE
61
62 /* Indexed by machine mode, gives the class mode for GET_MODE_CLASS.  */
63
64 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  CLASS,
65
66 const enum mode_class mode_class[NUM_MACHINE_MODES] = {
67 #include "machmode.def"
68 };
69
70 #undef DEF_MACHMODE
71
72 /* Indexed by machine mode, gives the length of the mode, in bits.
73    GET_MODE_BITSIZE uses this.  */
74
75 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  BITSIZE,
76
77 const unsigned short mode_bitsize[NUM_MACHINE_MODES] = {
78 #include "machmode.def"
79 };
80
81 #undef DEF_MACHMODE
82
83 /* Indexed by machine mode, gives the length of the mode, in bytes.
84    GET_MODE_SIZE uses this.  */
85
86 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  SIZE,
87
88 const unsigned char mode_size[NUM_MACHINE_MODES] = {
89 #include "machmode.def"
90 };
91
92 #undef DEF_MACHMODE
93
94 /* Indexed by machine mode, gives the length of the mode's subunit.
95    GET_MODE_UNIT_SIZE uses this.  */
96
97 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  UNIT,
98
99 const unsigned char mode_unit_size[NUM_MACHINE_MODES] = {
100 #include "machmode.def"         /* machine modes are documented here */
101 };
102
103 #undef DEF_MACHMODE
104
105 /* Indexed by machine mode, gives next wider natural mode
106    (QI -> HI -> SI -> DI, etc.)  Widening multiply instructions
107    use this.  */
108
109 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  \
110   (unsigned char) WIDER,
111
112 const unsigned char mode_wider_mode[NUM_MACHINE_MODES] = {
113 #include "machmode.def"         /* machine modes are documented here */
114 };
115
116 #undef DEF_MACHMODE
117
118 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  \
119   ((BITSIZE) >= HOST_BITS_PER_WIDE_INT) ? ~(unsigned HOST_WIDE_INT) 0 : ((unsigned HOST_WIDE_INT) 1 << (BITSIZE)) - 1,
120
121 /* Indexed by machine mode, gives mask of significant bits in mode.  */
122
123 const unsigned HOST_WIDE_INT mode_mask_array[NUM_MACHINE_MODES] = {
124 #include "machmode.def"
125 };
126
127 #undef DEF_MACHMODE
128
129 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER) INNER,
130
131 /* Indexed by machine mode, gives the mode of the inner elements in a
132    vector type.  */
133
134 const enum machine_mode inner_mode_array[NUM_MACHINE_MODES] = {
135 #include "machmode.def"
136 };
137
138 /* Indexed by mode class, gives the narrowest mode for each class.
139    The Q modes are always of width 1 (2 for complex) - it is impossible
140    for any mode to be narrower.
141
142    Note that we use QImode instead of BImode for MODE_INT, since
143    otherwise the middle end will try to use it for bitfields in
144    structures and the like, which we do not want.  Only the target
145    md file should generate BImode widgets.  */
146
147 const enum machine_mode class_narrowest_mode[(int) MAX_MODE_CLASS] = {
148     /* MODE_RANDOM */           VOIDmode,
149     /* MODE_INT */              QImode,
150     /* MODE_FLOAT */            QFmode,
151     /* MODE_PARTIAL_INT */      PQImode,
152     /* MODE_CC */               CCmode,
153     /* MODE_COMPLEX_INT */      CQImode,
154     /* MODE_COMPLEX_FLOAT */    QCmode,
155     /* MODE_VECTOR_INT */       V2QImode,
156     /* MODE_VECTOR_FLOAT */     V2SFmode
157 };
158
159
160 /* Indexed by rtx code, gives a sequence of operand-types for
161    rtx's of that code.  The sequence is a C string in which
162    each character describes one operand.  */
163
164 const char * const rtx_format[NUM_RTX_CODE] = {
165   /* "*" undefined.
166          can cause a warning message
167      "0" field is unused (or used in a phase-dependent manner)
168          prints nothing
169      "i" an integer
170          prints the integer
171      "n" like "i", but prints entries from `note_insn_name'
172      "w" an integer of width HOST_BITS_PER_WIDE_INT
173          prints the integer
174      "s" a pointer to a string
175          prints the string
176      "S" like "s", but optional:
177          the containing rtx may end before this operand
178      "T" like "s", but treated specially by the RTL reader;
179          only found in machine description patterns.
180      "e" a pointer to an rtl expression
181          prints the expression
182      "E" a pointer to a vector that points to a number of rtl expressions
183          prints a list of the rtl expressions
184      "V" like "E", but optional:
185          the containing rtx may end before this operand
186      "u" a pointer to another insn
187          prints the uid of the insn.
188      "b" is a pointer to a bitmap header.
189      "t" is a tree pointer.  */
190
191 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
192 #include "rtl.def"              /* rtl expressions are defined here */
193 #undef DEF_RTL_EXPR
194 };
195
196 /* Indexed by rtx code, gives a character representing the "class" of
197    that rtx code.  See rtl.def for documentation on the defined classes.  */
198
199 const char rtx_class[NUM_RTX_CODE] = {
200 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
201 #include "rtl.def"              /* rtl expressions are defined here */
202 #undef DEF_RTL_EXPR
203 };
204
205 /* Names for kinds of NOTEs and REG_NOTEs.  */
206
207 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
208 {
209   "", "NOTE_INSN_DELETED",
210   "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
211   "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
212   "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
213   "NOTE_INSN_LOOP_END_TOP_COND", "NOTE_INSN_FUNCTION_END",
214   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
215   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
216   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
217   "NOTE_INSN_REPEATED_LINE_NUMBER", "NOTE_INSN_RANGE_BEG",
218   "NOTE_INSN_RANGE_END", "NOTE_INSN_LIVE",
219   "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE",
220   "NOTE_INSN_PREDICTION"
221 };
222
223 const char * const reg_note_name[] =
224 {
225   "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_EQUAL",
226   "REG_WAS_0", "REG_RETVAL", "REG_LIBCALL", "REG_NONNEG",
227   "REG_NO_CONFLICT", "REG_UNUSED", "REG_CC_SETTER", "REG_CC_USER",
228   "REG_LABEL", "REG_DEP_ANTI", "REG_DEP_OUTPUT", "REG_BR_PROB",
229   "REG_EXEC_COUNT", "REG_NOALIAS", "REG_SAVE_AREA", "REG_BR_PRED",
230   "REG_FRAME_RELATED_EXPR", "REG_EH_CONTEXT", "REG_EH_REGION",
231   "REG_SAVE_NOTE", "REG_MAYBE_DEAD", "REG_NORETURN",
232   "REG_NON_LOCAL_GOTO", "REG_SETJMP", "REG_ALWAYS_RETURN",
233   "REG_VTABLE_REF"
234 };
235
236 \f
237 /* Allocate an rtx vector of N elements.
238    Store the length, and initialize all elements to zero.  */
239
240 rtvec
241 rtvec_alloc (n)
242      int n;
243 {
244   rtvec rt;
245
246   rt = ggc_alloc_rtvec (n);
247   /* clear out the vector */
248   memset (&rt->elem[0], 0, n * sizeof (rtx));
249
250   PUT_NUM_ELEM (rt, n);
251   return rt;
252 }
253
254 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
255    all the rest is initialized to zero.  */
256
257 rtx
258 rtx_alloc (code)
259   RTX_CODE code;
260 {
261   rtx rt;
262   int n = GET_RTX_LENGTH (code);
263
264   rt = ggc_alloc_rtx (n);
265
266   /* We want to clear everything up to the FLD array.  Normally, this
267      is one int, but we don't want to assume that and it isn't very
268      portable anyway; this is.  */
269
270   memset (rt, 0, sizeof (struct rtx_def) - sizeof (rtunion));
271   PUT_CODE (rt, code);
272   return rt;
273 }
274
275 \f
276 /* Create a new copy of an rtx.
277    Recursively copies the operands of the rtx,
278    except for those few rtx codes that are sharable.  */
279
280 rtx
281 copy_rtx (orig)
282      rtx orig;
283 {
284   rtx copy;
285   int i, j;
286   RTX_CODE code;
287   const char *format_ptr;
288
289   code = GET_CODE (orig);
290
291   switch (code)
292     {
293     case REG:
294     case QUEUED:
295     case CONST_INT:
296     case CONST_DOUBLE:
297     case CONST_VECTOR:
298     case SYMBOL_REF:
299     case CODE_LABEL:
300     case PC:
301     case CC0:
302     case SCRATCH:
303       /* SCRATCH must be shared because they represent distinct values.  */
304     case ADDRESSOF:
305       return orig;
306
307     case CONST:
308       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
309          a LABEL_REF, it isn't sharable.  */
310       if (GET_CODE (XEXP (orig, 0)) == PLUS
311           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
312           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
313         return orig;
314       break;
315
316       /* A MEM with a constant address is not sharable.  The problem is that
317          the constant address may need to be reloaded.  If the mem is shared,
318          then reloading one copy of this mem will cause all copies to appear
319          to have been reloaded.  */
320
321     default:
322       break;
323     }
324
325   copy = rtx_alloc (code);
326
327   /* Copy the various flags, and other information.  We assume that
328      all fields need copying, and then clear the fields that should
329      not be copied.  That is the sensible default behavior, and forces
330      us to explicitly document why we are *not* copying a flag.  */
331   memcpy (copy, orig, sizeof (struct rtx_def) - sizeof (rtunion));
332
333   /* We do not copy the USED flag, which is used as a mark bit during
334      walks over the RTL.  */
335   RTX_FLAG (copy, used) = 0;
336
337   /* We do not copy FRAME_RELATED for INSNs.  */
338   if (GET_RTX_CLASS (code) == 'i')
339     RTX_FLAG (copy, frame_related) = 0;
340   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
341   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
342
343   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
344
345   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
346     {
347       copy->fld[i] = orig->fld[i];
348       switch (*format_ptr++)
349         {
350         case 'e':
351           if (XEXP (orig, i) != NULL)
352             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
353           break;
354
355         case 'E':
356         case 'V':
357           if (XVEC (orig, i) != NULL)
358             {
359               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
360               for (j = 0; j < XVECLEN (copy, i); j++)
361                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
362             }
363           break;
364
365         case 't':
366         case 'w':
367         case 'i':
368         case 's':
369         case 'S':
370         case 'T':
371         case 'u':
372         case 'B':
373         case '0':
374           /* These are left unchanged.  */
375           break;
376
377         default:
378           abort ();
379         }
380     }
381   return copy;
382 }
383
384 /* Create a new copy of an rtx.  Only copy just one level.  */
385
386 rtx
387 shallow_copy_rtx (orig)
388      rtx orig;
389 {
390   int i;
391   RTX_CODE code = GET_CODE (orig);
392   rtx copy = rtx_alloc (code);
393
394   PUT_MODE (copy, GET_MODE (orig));
395   RTX_FLAG (copy, in_struct) = RTX_FLAG (orig, in_struct);
396   RTX_FLAG (copy, volatil) = RTX_FLAG (orig, volatil);
397   RTX_FLAG (copy, unchanging) = RTX_FLAG (orig, unchanging);
398   RTX_FLAG (copy, integrated) = RTX_FLAG (orig, integrated);
399   RTX_FLAG (copy, frame_related) = RTX_FLAG (orig, frame_related);
400
401   for (i = 0; i < GET_RTX_LENGTH (code); i++)
402     copy->fld[i] = orig->fld[i];
403
404   return copy;
405 }
406
407 /* Return the alignment of MODE. This will be bounded by 1 and
408    BIGGEST_ALIGNMENT.  */
409
410 unsigned int
411 get_mode_alignment (mode)
412      enum machine_mode mode;
413 {
414   unsigned int alignment;
415
416   if (GET_MODE_CLASS (mode) == MODE_COMPLEX_FLOAT
417       || GET_MODE_CLASS (mode) == MODE_COMPLEX_INT)
418     alignment = GET_MODE_UNIT_SIZE (mode);
419   else
420     alignment = GET_MODE_SIZE (mode);
421
422   /* Extract the LSB of the size.  */
423   alignment = alignment & -alignment;
424   alignment *= BITS_PER_UNIT;
425
426   alignment = MIN (BIGGEST_ALIGNMENT, MAX (1, alignment));
427   return alignment;
428 }
429 \f
430 /* This is 1 until after the rtl generation pass.  */
431 int rtx_equal_function_value_matters;
432
433 /* Nonzero when we are generating CONCATs.  */
434 int generating_concat_p;
435 \f
436 /* Return 1 if X and Y are identical-looking rtx's.
437    This is the Lisp function EQUAL for rtx arguments.  */
438
439 int
440 rtx_equal_p (x, y)
441      rtx x, y;
442 {
443   int i;
444   int j;
445   enum rtx_code code;
446   const char *fmt;
447
448   if (x == y)
449     return 1;
450   if (x == 0 || y == 0)
451     return 0;
452
453   code = GET_CODE (x);
454   /* Rtx's of different codes cannot be equal.  */
455   if (code != GET_CODE (y))
456     return 0;
457
458   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
459      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
460
461   if (GET_MODE (x) != GET_MODE (y))
462     return 0;
463
464   /* Some RTL can be compared nonrecursively.  */
465   switch (code)
466     {
467     case REG:
468       /* Until rtl generation is complete, don't consider a reference
469          to the return register of the current function the same as
470          the return from a called function.  This eases the job of
471          function integration.  Once the distinction is no longer
472          needed, they can be considered equivalent.  */
473       return (REGNO (x) == REGNO (y)
474               && (! rtx_equal_function_value_matters
475                   || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
476
477     case LABEL_REF:
478       return XEXP (x, 0) == XEXP (y, 0);
479
480     case SYMBOL_REF:
481       return XSTR (x, 0) == XSTR (y, 0);
482
483     case SCRATCH:
484     case CONST_DOUBLE:
485     case CONST_INT:
486     case CONST_VECTOR:
487       return 0;
488
489     default:
490       break;
491     }
492
493   /* Compare the elements.  If any pair of corresponding elements
494      fail to match, return 0 for the whole things.  */
495
496   fmt = GET_RTX_FORMAT (code);
497   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
498     {
499       switch (fmt[i])
500         {
501         case 'w':
502           if (XWINT (x, i) != XWINT (y, i))
503             return 0;
504           break;
505
506         case 'n':
507         case 'i':
508           if (XINT (x, i) != XINT (y, i))
509             return 0;
510           break;
511
512         case 'V':
513         case 'E':
514           /* Two vectors must have the same length.  */
515           if (XVECLEN (x, i) != XVECLEN (y, i))
516             return 0;
517
518           /* And the corresponding elements must match.  */
519           for (j = 0; j < XVECLEN (x, i); j++)
520             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
521               return 0;
522           break;
523
524         case 'e':
525           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
526             return 0;
527           break;
528
529         case 'S':
530         case 's':
531           if ((XSTR (x, i) || XSTR (y, i))
532               && (! XSTR (x, i) || ! XSTR (y, i)
533                   || strcmp (XSTR (x, i), XSTR (y, i))))
534             return 0;
535           break;
536
537         case 'u':
538           /* These are just backpointers, so they don't matter.  */
539           break;
540
541         case '0':
542         case 't':
543           break;
544
545           /* It is believed that rtx's at this level will never
546              contain anything but integers and other rtx's,
547              except for within LABEL_REFs and SYMBOL_REFs.  */
548         default:
549           abort ();
550         }
551     }
552   return 1;
553 }
554 \f
555 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
556 void
557 rtl_check_failed_bounds (r, n, file, line, func)
558     rtx r;
559     int n;
560     const char *file;
561     int line;
562     const char *func;
563 {
564   internal_error
565     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
566      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
567      func, trim_filename (file), line);
568 }
569
570 void
571 rtl_check_failed_type1 (r, n, c1, file, line, func)
572     rtx r;
573     int n;
574     int c1;
575     const char *file;
576     int line;
577     const char *func;
578 {
579   internal_error
580     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
581      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
582      func, trim_filename (file), line);
583 }
584
585 void
586 rtl_check_failed_type2 (r, n, c1, c2, file, line, func)
587     rtx r;
588     int n;
589     int c1;
590     int c2;
591     const char *file;
592     int line;
593     const char *func;
594 {
595   internal_error
596     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
597      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
598      func, trim_filename (file), line);
599 }
600
601 void
602 rtl_check_failed_code1 (r, code, file, line, func)
603     rtx r;
604     enum rtx_code code;
605     const char *file;
606     int line;
607     const char *func;
608 {
609   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
610                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
611                   trim_filename (file), line);
612 }
613
614 void
615 rtl_check_failed_code2 (r, code1, code2, file, line, func)
616     rtx r;
617     enum rtx_code code1, code2;
618     const char *file;
619     int line;
620     const char *func;
621 {
622   internal_error
623     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
624      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
625      func, trim_filename (file), line);
626 }
627
628 /* XXX Maybe print the vector?  */
629 void
630 rtvec_check_failed_bounds (r, n, file, line, func)
631     rtvec r;
632     int n;
633     const char *file;
634     int line;
635     const char *func;
636 {
637   internal_error
638     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
639      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
640 }
641 #endif /* ENABLE_RTL_CHECKING */
642
643 #if defined ENABLE_RTL_FLAG_CHECKING
644 void
645 rtl_check_failed_flag (name, r, file, line, func)
646     const char *name;
647     rtx r;
648     const char *file;
649     int line;
650     const char *func;
651 {
652   internal_error
653     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
654      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
655 }
656 #endif /* ENABLE_RTL_FLAG_CHECKING */