Index: gcc/ChangeLog
[gcc.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 "B" is a basic block pointer.
190 "t" is a tree pointer. */
191
192 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) FORMAT ,
193 #include "rtl.def" /* rtl expressions are defined here */
194 #undef DEF_RTL_EXPR
195 };
196
197 /* Indexed by rtx code, gives a character representing the "class" of
198 that rtx code. See rtl.def for documentation on the defined classes. */
199
200 const char rtx_class[NUM_RTX_CODE] = {
201 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) CLASS,
202 #include "rtl.def" /* rtl expressions are defined here */
203 #undef DEF_RTL_EXPR
204 };
205
206 /* Names for kinds of NOTEs and REG_NOTEs. */
207
208 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
209 {
210 "", "NOTE_INSN_DELETED",
211 "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
212 "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
213 "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
214 "NOTE_INSN_LOOP_END_TOP_COND", "NOTE_INSN_FUNCTION_END",
215 "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
216 "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
217 "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
218 "NOTE_INSN_REPEATED_LINE_NUMBER",
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 */