Print SCoPs under CLooG format.
[official-gcc/graphite-test-results.git] / gcc / rtl.c
blobfe9c9514f1cd40624b9af8ab00ad8ebbc861b4bb
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.
5 This file is part of GCC.
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.
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.
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/>. */
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
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
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). */
45 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) sizeof FORMAT - 1 ,
47 const unsigned char rtx_length[NUM_RTX_CODE] = {
48 #include "rtl.def"
51 #undef DEF_RTL_EXPR
53 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string. */
55 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) NAME ,
57 const char * const rtx_name[NUM_RTX_CODE] = {
58 #include "rtl.def" /* rtl expressions are documented here */
61 #undef DEF_RTL_EXPR
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. */
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. */
95 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) FORMAT ,
96 #include "rtl.def" /* rtl expressions are defined here */
97 #undef DEF_RTL_EXPR
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. */
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
109 /* Indexed by rtx code, gives the size of the rtx in bytes. */
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)),
117 #include "rtl.def"
118 #undef DEF_RTL_EXPR
121 /* Names for kinds of NOTEs and REG_NOTEs. */
123 const char * const note_insn_name[NOTE_INSN_MAX] =
125 #define DEF_INSN_NOTE(NAME) #NAME,
126 #include "insn-notes.def"
127 #undef DEF_INSN_NOTE
130 const char * const reg_note_name[REG_NOTE_MAX] =
132 #define DEF_REG_NOTE(NAME) #NAME,
133 #include "reg-notes.def"
134 #undef DEF_REG_NOTE
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
145 /* Allocate an rtx vector of N elements.
146 Store the length, and initialize all elements to zero. */
148 rtvec
149 rtvec_alloc (int n)
151 rtvec rt;
153 rt = ggc_alloc_rtvec (n);
154 /* Clear out the vector. */
155 memset (&rt->elem[0], 0, n * sizeof (rtx));
157 PUT_NUM_ELEM (rt, n);
159 #ifdef GATHER_STATISTICS
160 rtvec_alloc_counts++;
161 rtvec_alloc_sizes += n * sizeof (rtx);
162 #endif
164 return rt;
167 /* Create a bitwise copy of VEC. */
169 rtvec
170 shallow_copy_rtvec (rtvec vec)
172 rtvec newvec;
173 int n;
175 n = GET_NUM_ELEM (vec);
176 newvec = rtvec_alloc (n);
177 memcpy (&newvec->elem[0], &vec->elem[0], sizeof (rtx) * n);
178 return newvec;
181 /* Return the number of bytes occupied by rtx value X. */
183 unsigned int
184 rtx_size (const_rtx x)
186 if (GET_CODE (x) == SYMBOL_REF && SYMBOL_REF_HAS_BLOCK_INFO_P (x))
187 return RTX_HDR_SIZE + sizeof (struct block_symbol);
188 return RTX_CODE_SIZE (GET_CODE (x));
191 /* Allocate an rtx of code CODE. The CODE is stored in the rtx;
192 all the rest is initialized to zero. */
195 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
197 rtx rt;
199 rt = (rtx) ggc_alloc_zone_pass_stat (RTX_CODE_SIZE (code), &rtl_zone);
201 /* We want to clear everything up to the FLD array. Normally, this
202 is one int, but we don't want to assume that and it isn't very
203 portable anyway; this is. */
205 memset (rt, 0, RTX_HDR_SIZE);
206 PUT_CODE (rt, code);
208 #ifdef GATHER_STATISTICS
209 rtx_alloc_counts[code]++;
210 rtx_alloc_sizes[code] += RTX_CODE_SIZE (code);
211 #endif
213 return rt;
217 /* Return true if ORIG is a sharable CONST. */
219 bool
220 shared_const_p (const_rtx orig)
222 gcc_assert (GET_CODE (orig) == CONST);
224 /* CONST can be shared if it contains a SYMBOL_REF. If it contains
225 a LABEL_REF, it isn't sharable. */
226 return (GET_CODE (XEXP (orig, 0)) == PLUS
227 && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
228 && CONST_INT_P(XEXP (XEXP (orig, 0), 1)));
232 /* Create a new copy of an rtx.
233 Recursively copies the operands of the rtx,
234 except for those few rtx codes that are sharable. */
237 copy_rtx (rtx orig)
239 rtx copy;
240 int i, j;
241 RTX_CODE code;
242 const char *format_ptr;
244 code = GET_CODE (orig);
246 switch (code)
248 case REG:
249 case DEBUG_EXPR:
250 case VALUE:
251 case CONST_INT:
252 case CONST_DOUBLE:
253 case CONST_FIXED:
254 case CONST_VECTOR:
255 case SYMBOL_REF:
256 case CODE_LABEL:
257 case PC:
258 case CC0:
259 case SCRATCH:
260 /* SCRATCH must be shared because they represent distinct values. */
261 return orig;
262 case CLOBBER:
263 if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
264 return orig;
265 break;
267 case CONST:
268 if (shared_const_p (orig))
269 return orig;
270 break;
272 /* A MEM with a constant address is not sharable. The problem is that
273 the constant address may need to be reloaded. If the mem is shared,
274 then reloading one copy of this mem will cause all copies to appear
275 to have been reloaded. */
277 default:
278 break;
281 /* Copy the various flags, fields, and other information. We assume
282 that all fields need copying, and then clear the fields that should
283 not be copied. That is the sensible default behavior, and forces
284 us to explicitly document why we are *not* copying a flag. */
285 copy = shallow_copy_rtx (orig);
287 /* We do not copy the USED flag, which is used as a mark bit during
288 walks over the RTL. */
289 RTX_FLAG (copy, used) = 0;
291 /* We do not copy FRAME_RELATED for INSNs. */
292 if (INSN_P (orig))
293 RTX_FLAG (copy, frame_related) = 0;
294 RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
295 RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
297 format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
299 for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
300 switch (*format_ptr++)
302 case 'e':
303 if (XEXP (orig, i) != NULL)
304 XEXP (copy, i) = copy_rtx (XEXP (orig, i));
305 break;
307 case 'E':
308 case 'V':
309 if (XVEC (orig, i) != NULL)
311 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
312 for (j = 0; j < XVECLEN (copy, i); j++)
313 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
315 break;
317 case 't':
318 case 'w':
319 case 'i':
320 case 's':
321 case 'S':
322 case 'T':
323 case 'u':
324 case 'B':
325 case '0':
326 /* These are left unchanged. */
327 break;
329 default:
330 gcc_unreachable ();
332 return copy;
335 /* Create a new copy of an rtx. Only copy just one level. */
338 shallow_copy_rtx_stat (const_rtx orig MEM_STAT_DECL)
340 const unsigned int size = rtx_size (orig);
341 rtx const copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
342 return (rtx) memcpy (copy, orig, size);
345 /* Nonzero when we are generating CONCATs. */
346 int generating_concat_p;
348 /* Nonzero when we are expanding trees to RTL. */
349 int currently_expanding_to_rtl;
353 /* Same as rtx_equal_p, but call CB on each pair of rtx if CB is not NULL.
354 When the callback returns true, we continue with the new pair.
355 Whenever changing this function check if rtx_equal_p below doesn't need
356 changing as well. */
359 rtx_equal_p_cb (const_rtx x, const_rtx y, rtx_equal_p_callback_function cb)
361 int i;
362 int j;
363 enum rtx_code code;
364 const char *fmt;
365 rtx nx, ny;
367 if (x == y)
368 return 1;
369 if (x == 0 || y == 0)
370 return 0;
372 /* Invoke the callback first. */
373 if (cb != NULL
374 && ((*cb) (&x, &y, &nx, &ny)))
375 return rtx_equal_p_cb (nx, ny, cb);
377 code = GET_CODE (x);
378 /* Rtx's of different codes cannot be equal. */
379 if (code != GET_CODE (y))
380 return 0;
382 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
383 (REG:SI x) and (REG:HI x) are NOT equivalent. */
385 if (GET_MODE (x) != GET_MODE (y))
386 return 0;
388 /* MEMs refering to different address space are not equivalent. */
389 if (code == MEM && MEM_ADDR_SPACE (x) != MEM_ADDR_SPACE (y))
390 return 0;
392 /* Some RTL can be compared nonrecursively. */
393 switch (code)
395 case REG:
396 return (REGNO (x) == REGNO (y));
398 case LABEL_REF:
399 return XEXP (x, 0) == XEXP (y, 0);
401 case SYMBOL_REF:
402 return XSTR (x, 0) == XSTR (y, 0);
404 case DEBUG_EXPR:
405 case VALUE:
406 case SCRATCH:
407 case CONST_DOUBLE:
408 case CONST_INT:
409 case CONST_FIXED:
410 return 0;
412 default:
413 break;
416 /* Compare the elements. If any pair of corresponding elements
417 fail to match, return 0 for the whole thing. */
419 fmt = GET_RTX_FORMAT (code);
420 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
422 switch (fmt[i])
424 case 'w':
425 if (XWINT (x, i) != XWINT (y, i))
426 return 0;
427 break;
429 case 'n':
430 case 'i':
431 if (XINT (x, i) != XINT (y, i))
432 return 0;
433 break;
435 case 'V':
436 case 'E':
437 /* Two vectors must have the same length. */
438 if (XVECLEN (x, i) != XVECLEN (y, i))
439 return 0;
441 /* And the corresponding elements must match. */
442 for (j = 0; j < XVECLEN (x, i); j++)
443 if (rtx_equal_p_cb (XVECEXP (x, i, j),
444 XVECEXP (y, i, j), cb) == 0)
445 return 0;
446 break;
448 case 'e':
449 if (rtx_equal_p_cb (XEXP (x, i), XEXP (y, i), cb) == 0)
450 return 0;
451 break;
453 case 'S':
454 case 's':
455 if ((XSTR (x, i) || XSTR (y, i))
456 && (! XSTR (x, i) || ! XSTR (y, i)
457 || strcmp (XSTR (x, i), XSTR (y, i))))
458 return 0;
459 break;
461 case 'u':
462 /* These are just backpointers, so they don't matter. */
463 break;
465 case '0':
466 case 't':
467 break;
469 /* It is believed that rtx's at this level will never
470 contain anything but integers and other rtx's,
471 except for within LABEL_REFs and SYMBOL_REFs. */
472 default:
473 gcc_unreachable ();
476 return 1;
479 /* Return 1 if X and Y are identical-looking rtx's.
480 This is the Lisp function EQUAL for rtx arguments.
481 Whenever changing this function check if rtx_equal_p_cb above doesn't need
482 changing as well. */
485 rtx_equal_p (const_rtx x, const_rtx y)
487 int i;
488 int j;
489 enum rtx_code code;
490 const char *fmt;
492 if (x == y)
493 return 1;
494 if (x == 0 || y == 0)
495 return 0;
497 code = GET_CODE (x);
498 /* Rtx's of different codes cannot be equal. */
499 if (code != GET_CODE (y))
500 return 0;
502 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
503 (REG:SI x) and (REG:HI x) are NOT equivalent. */
505 if (GET_MODE (x) != GET_MODE (y))
506 return 0;
508 /* MEMs refering to different address space are not equivalent. */
509 if (code == MEM && MEM_ADDR_SPACE (x) != MEM_ADDR_SPACE (y))
510 return 0;
512 /* Some RTL can be compared nonrecursively. */
513 switch (code)
515 case REG:
516 return (REGNO (x) == REGNO (y));
518 case LABEL_REF:
519 return XEXP (x, 0) == XEXP (y, 0);
521 case SYMBOL_REF:
522 return XSTR (x, 0) == XSTR (y, 0);
524 case DEBUG_EXPR:
525 case VALUE:
526 case SCRATCH:
527 case CONST_DOUBLE:
528 case CONST_INT:
529 case CONST_FIXED:
530 return 0;
532 default:
533 break;
536 /* Compare the elements. If any pair of corresponding elements
537 fail to match, return 0 for the whole thing. */
539 fmt = GET_RTX_FORMAT (code);
540 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
542 switch (fmt[i])
544 case 'w':
545 if (XWINT (x, i) != XWINT (y, i))
546 return 0;
547 break;
549 case 'n':
550 case 'i':
551 if (XINT (x, i) != XINT (y, i))
552 return 0;
553 break;
555 case 'V':
556 case 'E':
557 /* Two vectors must have the same length. */
558 if (XVECLEN (x, i) != XVECLEN (y, i))
559 return 0;
561 /* And the corresponding elements must match. */
562 for (j = 0; j < XVECLEN (x, i); j++)
563 if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
564 return 0;
565 break;
567 case 'e':
568 if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
569 return 0;
570 break;
572 case 'S':
573 case 's':
574 if ((XSTR (x, i) || XSTR (y, i))
575 && (! XSTR (x, i) || ! XSTR (y, i)
576 || strcmp (XSTR (x, i), XSTR (y, i))))
577 return 0;
578 break;
580 case 'u':
581 /* These are just backpointers, so they don't matter. */
582 break;
584 case '0':
585 case 't':
586 break;
588 /* It is believed that rtx's at this level will never
589 contain anything but integers and other rtx's,
590 except for within LABEL_REFs and SYMBOL_REFs. */
591 default:
592 gcc_unreachable ();
595 return 1;
598 void
599 dump_rtx_statistics (void)
601 #ifdef GATHER_STATISTICS
602 int i;
603 int total_counts = 0;
604 int total_sizes = 0;
605 fprintf (stderr, "\nRTX Kind Count Bytes\n");
606 fprintf (stderr, "---------------------------------------\n");
607 for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
608 if (rtx_alloc_counts[i])
610 fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
611 rtx_alloc_counts[i], rtx_alloc_sizes[i]);
612 total_counts += rtx_alloc_counts[i];
613 total_sizes += rtx_alloc_sizes[i];
615 if (rtvec_alloc_counts)
617 fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
618 rtvec_alloc_counts, rtvec_alloc_sizes);
619 total_counts += rtvec_alloc_counts;
620 total_sizes += rtvec_alloc_sizes;
622 fprintf (stderr, "---------------------------------------\n");
623 fprintf (stderr, "%-20s %7d %10d\n",
624 "Total", total_counts, total_sizes);
625 fprintf (stderr, "---------------------------------------\n");
626 #endif
629 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
630 void
631 rtl_check_failed_bounds (const_rtx r, int n, const char *file, int line,
632 const char *func)
634 internal_error
635 ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
636 n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
637 func, trim_filename (file), line);
640 void
641 rtl_check_failed_type1 (const_rtx r, int n, int c1, const char *file, int line,
642 const char *func)
644 internal_error
645 ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
646 n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
647 func, trim_filename (file), line);
650 void
651 rtl_check_failed_type2 (const_rtx r, int n, int c1, int c2, const char *file,
652 int line, const char *func)
654 internal_error
655 ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
656 n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
657 func, trim_filename (file), line);
660 void
661 rtl_check_failed_code1 (const_rtx r, enum rtx_code code, const char *file,
662 int line, const char *func)
664 internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
665 GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
666 trim_filename (file), line);
669 void
670 rtl_check_failed_code2 (const_rtx r, enum rtx_code code1, enum rtx_code code2,
671 const char *file, int line, const char *func)
673 internal_error
674 ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
675 GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
676 func, trim_filename (file), line);
679 void
680 rtl_check_failed_code_mode (const_rtx r, enum rtx_code code, enum machine_mode mode,
681 bool not_mode, const char *file, int line,
682 const char *func)
684 internal_error ((not_mode
685 ? ("RTL check: expected code '%s' and not mode '%s', "
686 "have code '%s' and mode '%s' in %s, at %s:%d")
687 : ("RTL check: expected code '%s' and mode '%s', "
688 "have code '%s' and mode '%s' in %s, at %s:%d")),
689 GET_RTX_NAME (code), GET_MODE_NAME (mode),
690 GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
691 func, trim_filename (file), line);
694 /* Report that line LINE of FILE tried to access the block symbol fields
695 of a non-block symbol. FUNC is the function that contains the line. */
697 void
698 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
700 internal_error
701 ("RTL check: attempt to treat non-block symbol as a block symbol "
702 "in %s, at %s:%d", func, trim_filename (file), line);
705 /* XXX Maybe print the vector? */
706 void
707 rtvec_check_failed_bounds (const_rtvec r, int n, const char *file, int line,
708 const char *func)
710 internal_error
711 ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
712 n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
714 #endif /* ENABLE_RTL_CHECKING */
716 #if defined ENABLE_RTL_FLAG_CHECKING
717 void
718 rtl_check_failed_flag (const char *name, const_rtx r, const char *file,
719 int line, const char *func)
721 internal_error
722 ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
723 name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
725 #endif /* ENABLE_RTL_FLAG_CHECKING */