/* Instruction scheduling pass.
- Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
+ 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
-later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful, but WITHOUT
-ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to the Free
-the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
\f
#include "config.h"
#include "system.h"
-#include "toplev.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
-#include "tm_p.h"
-#include "regs.h"
+#include "obstack.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
#include "insn-attr.h"
#include "sched-int.h"
+#include "tree-pass.h"
-#ifdef INSN_SCHEDULING
-/* target_units bitmask has 1 for each unit in the cpu. It should be
- possible to compute this variable from the machine description.
- But currently it is computed by examining the insn list. Since
- this is only needed for visualization, it seems an acceptable
- solution. (For understanding the mapping of bits to units, see
- definition of function_units[] in "insn-attrtab.c".) */
-
-static int target_units = 0;
-
-static char *safe_concat PARAMS ((char *, char *, const char *));
-static int get_visual_tbl_length PARAMS ((void));
-static void print_exp PARAMS ((char *, rtx, int));
-static void print_value PARAMS ((char *, rtx, int));
-static void print_pattern PARAMS ((char *, rtx, int));
-static void print_insn PARAMS ((char *, rtx, int));
-
-/* Print names of units on which insn can/should execute, for debugging. */
-
-void
-insn_print_units (insn)
- rtx insn;
-{
- int i;
- int unit = insn_unit (insn);
-
- if (unit == -1)
- fprintf (sched_dump, "none");
- else if (unit >= 0)
- fprintf (sched_dump, "%s", function_units[unit].name);
- else
- {
- fprintf (sched_dump, "[");
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if (unit & 1)
- {
- fprintf (sched_dump, "%s", function_units[i].name);
- if (unit != 1)
- fprintf (sched_dump, " ");
- }
- fprintf (sched_dump, "]");
- }
-}
-
-/* MAX_VISUAL_LINES is the maximum number of lines in visualization table
- of a basic block. If more lines are needed, table is splitted to two.
- n_visual_lines is the number of lines printed so far for a block.
- visual_tbl contains the block visualization info.
- vis_no_unit holds insns in a cycle that are not mapped to any unit. */
-#define MAX_VISUAL_LINES 100
-#define INSN_LEN 30
-int n_visual_lines;
-static unsigned visual_tbl_line_length;
-char *visual_tbl;
-int n_vis_no_unit;
-rtx vis_no_unit[10];
-
-/* Finds units that are in use in this fuction. Required only
- for visualization. */
-
-void
-init_target_units ()
-{
- rtx insn;
- int unit;
-
- for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
- {
- if (! INSN_P (insn))
- continue;
-
- unit = insn_unit (insn);
-
- if (unit < 0)
- target_units |= ~unit;
- else
- target_units |= (1 << unit);
- }
-}
-
-/* Return the length of the visualization table. */
-
-static int
-get_visual_tbl_length ()
-{
- int unit, i;
- int n, n1;
- char *s;
-
- /* Compute length of one field in line. */
- s = (char *) alloca (INSN_LEN + 6);
- sprintf (s, " %33s", "uname");
- n1 = strlen (s);
-
- /* Compute length of one line. */
- n = strlen (";; ");
- n += n1;
- for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
- if (function_units[unit].bitmask & target_units)
- for (i = 0; i < function_units[unit].multiplicity; i++)
- n += n1;
- n += n1;
- n += strlen ("\n") + 2;
-
- visual_tbl_line_length = n;
-
- /* Compute length of visualization string. */
- return (MAX_VISUAL_LINES * n);
-}
-
-/* Init block visualization debugging info. */
-
-void
-init_block_visualization ()
-{
- strcpy (visual_tbl, "");
- n_visual_lines = 0;
- n_vis_no_unit = 0;
-}
+static char *safe_concat (char *, char *, const char *);
#define BUF_LEN 2048
static char *
-safe_concat (buf, cur, str)
- char *buf;
- char *cur;
- const char *str;
+safe_concat (char *buf, char *cur, const char *str)
{
char *end = buf + BUF_LEN - 2; /* Leave room for null. */
int c;
may be stored in objects representing values. */
static void
-print_exp (buf, x, verbose)
- char *buf;
- rtx x;
- int verbose;
+print_exp (char *buf, const_rtx x, int verbose)
{
char tmp[BUF_LEN];
const char *st[4];
{
case PLUS:
op[0] = XEXP (x, 0);
- if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ if (CONST_INT_P (XEXP (x, 1))
&& INTVAL (XEXP (x, 1)) < 0)
{
st[1] = "-";
op[0] = XEXP (x, 0);
st[1] = "++";
break;
+ case PRE_MODIFY:
+ st[0] = "pre ";
+ op[0] = XEXP (XEXP (x, 1), 0);
+ st[1] = "+=";
+ op[1] = XEXP (XEXP (x, 1), 1);
+ break;
+ case POST_MODIFY:
+ st[0] = "post ";
+ op[0] = XEXP (XEXP (x, 1), 0);
+ st[1] = "+=";
+ op[1] = XEXP (XEXP (x, 1), 1);
+ break;
case CALL:
st[0] = "call ";
op[0] = XEXP (x, 0);
fun = "trap_if";
op[0] = TRAP_CONDITION (x);
break;
+ case PREFETCH:
+ fun = "prefetch";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
+ op[2] = XEXP (x, 2);
+ break;
case UNSPEC:
case UNSPEC_VOLATILE:
{
cur = safe_concat (buf, cur, ")");
} /* print_exp */
-/* Prints rtxes, I customly classified as values. They're constants,
+/* Prints rtxes, I customarily classified as values. They're constants,
registers, labels, symbols and memory accesses. */
-static void
-print_value (buf, x, verbose)
- char *buf;
- rtx x;
- int verbose;
+void
+print_value (char *buf, const_rtx x, int verbose)
{
char t[BUF_LEN];
char *cur = buf;
switch (GET_CODE (x))
{
case CONST_INT:
- sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
+ sprintf (t, HOST_WIDE_INT_PRINT_HEX,
+ (unsigned HOST_WIDE_INT) INTVAL (x));
cur = safe_concat (buf, cur, t);
break;
case CONST_DOUBLE:
- sprintf (t, "<0x%lx,0x%lx>", (long) XWINT (x, 2), (long) XWINT (x, 3));
+ if (FLOAT_MODE_P (GET_MODE (x)))
+ real_to_decimal (t, CONST_DOUBLE_REAL_VALUE (x), sizeof (t), 0, 1);
+ else
+ sprintf (t,
+ "<" HOST_WIDE_INT_PRINT_HEX "," HOST_WIDE_INT_PRINT_HEX ">",
+ (unsigned HOST_WIDE_INT) CONST_DOUBLE_LOW (x),
+ (unsigned HOST_WIDE_INT) CONST_DOUBLE_HIGH (x));
+ cur = safe_concat (buf, cur, t);
+ break;
+ case CONST_FIXED:
+ fixed_to_decimal (t, CONST_FIXED_VALUE (x), sizeof (t));
cur = safe_concat (buf, cur, t);
break;
case CONST_STRING:
if (REGNO (x) < FIRST_PSEUDO_REGISTER)
{
int c = reg_names[REGNO (x)][0];
- if (c >= '0' && c <= '9')
+ if (ISDIGIT (c))
cur = safe_concat (buf, cur, "%");
cur = safe_concat (buf, cur, reg_names[REGNO (x)]);
sprintf (t, "r%d", REGNO (x));
cur = safe_concat (buf, cur, t);
}
+ if (verbose
+#ifdef INSN_SCHEDULING
+ && !current_sched_info
+#endif
+ )
+ {
+ sprintf (t, ":%s", GET_MODE_NAME (GET_MODE (x)));
+ cur = safe_concat (buf, cur, t);
+ }
break;
case SUBREG:
print_value (t, SUBREG_REG (x), verbose);
cur = safe_concat (buf, cur, t);
- sprintf (t, "#%d", SUBREG_WORD (x));
+ sprintf (t, "#%d", SUBREG_BYTE (x));
cur = safe_concat (buf, cur, t);
break;
case SCRATCH:
cur = safe_concat (buf, cur, t);
cur = safe_concat (buf, cur, "]");
break;
+ case DEBUG_EXPR:
+ sprintf (t, "D#%i", DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)));
+ cur = safe_concat (buf, cur, t);
+ break;
default:
print_exp (t, x, verbose);
cur = safe_concat (buf, cur, t);
/* The next step in insn detalization, its pattern recognition. */
-static void
-print_pattern (buf, x, verbose)
- char *buf;
- rtx x;
- int verbose;
+void
+print_pattern (char *buf, const_rtx x, int verbose)
{
char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
print_value (t1, XEXP (x, 0), verbose);
sprintf (buf, "use %s", t1);
break;
+ case VAR_LOCATION:
+ print_value (t1, PAT_VAR_LOCATION_LOC (x), verbose);
+ sprintf (buf, "loc %s", t1);
+ break;
case COND_EXEC:
if (GET_CODE (COND_EXEC_TEST (x)) == NE
&& XEXP (COND_EXEC_TEST (x), 1) == const0_rtx)
print_value (t1, XEXP (COND_EXEC_TEST (x), 0), verbose);
else if (GET_CODE (COND_EXEC_TEST (x)) == EQ
- && XEXP (COND_EXEC_TEST (x), 1) == const0_rtx)
- {
+ && XEXP (COND_EXEC_TEST (x), 1) == const0_rtx)
+ {
t1[0] = '!';
print_value (t1 + 1, XEXP (COND_EXEC_TEST (x), 0), verbose);
}
else
- print_value (t1, COND_EXEC_TEST (x), verbose);
+ print_value (t1, COND_EXEC_TEST (x), verbose);
print_pattern (t2, COND_EXEC_CODE (x), verbose);
sprintf (buf, "(%s) %s", t1, t2);
break;
}
break;
case SEQUENCE:
- {
- int i;
-
- sprintf (t1, "%%{");
- for (i = 0; i < XVECLEN (x, 0); i++)
- {
- print_insn (t2, XVECEXP (x, 0, i), verbose);
- sprintf (t3, "%s%s;", t1, t2);
- strcpy (t1, t3);
- }
- sprintf (buf, "%s%%}", t1);
- }
- break;
+ /* Should never see SEQUENCE codes until after reorg. */
+ gcc_unreachable ();
case ASM_INPUT:
sprintf (buf, "asm {%s}", XSTR (x, 0));
break;
(Probably the last "option" should be extended somehow, since it
depends now on sched.c inner variables ...) */
-static void
-print_insn (buf, x, verbose)
- char *buf;
- rtx x;
- int verbose;
+void
+print_insn (char *buf, const_rtx x, int verbose)
{
char t[BUF_LEN];
- rtx insn = x;
+ const_rtx insn = x;
switch (GET_CODE (x))
{
case INSN:
print_pattern (t, PATTERN (x), verbose);
- if (verbose)
+#ifdef INSN_SCHEDULING
+ if (verbose && current_sched_info)
sprintf (buf, "%s: %s", (*current_sched_info->print_insn) (x, 1),
t);
else
- sprintf (buf, "%-4d %s", INSN_UID (x), t);
+#endif
+ sprintf (buf, " %4d %s", INSN_UID (x), t);
+ break;
+
+ case DEBUG_INSN:
+ {
+ const char *name = "?";
+
+ if (DECL_P (INSN_VAR_LOCATION_DECL (insn)))
+ {
+ tree id = DECL_NAME (INSN_VAR_LOCATION_DECL (insn));
+ char idbuf[32];
+ if (id)
+ name = IDENTIFIER_POINTER (id);
+ else if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn))
+ == DEBUG_EXPR_DECL)
+ {
+ sprintf (idbuf, "D#%i",
+ DEBUG_TEMP_UID (INSN_VAR_LOCATION_DECL (insn)));
+ name = idbuf;
+ }
+ else
+ {
+ sprintf (idbuf, "D.%i",
+ DECL_UID (INSN_VAR_LOCATION_DECL (insn)));
+ name = idbuf;
+ }
+ }
+ if (VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
+ sprintf (buf, " %4d: debug %s optimized away", INSN_UID (insn), name);
+ else
+ {
+ print_pattern (t, INSN_VAR_LOCATION_LOC (insn), verbose);
+ sprintf (buf, " %4d: debug %s => %s", INSN_UID (insn), name, t);
+ }
+ }
break;
+
case JUMP_INSN:
print_pattern (t, PATTERN (x), verbose);
- if (verbose)
+#ifdef INSN_SCHEDULING
+ if (verbose && current_sched_info)
sprintf (buf, "%s: jump %s", (*current_sched_info->print_insn) (x, 1),
t);
else
- sprintf (buf, "%-4d %s", INSN_UID (x), t);
+#endif
+ sprintf (buf, " %4d %s", INSN_UID (x), t);
break;
case CALL_INSN:
x = PATTERN (insn);
}
else
strcpy (t, "call <...>");
- if (verbose)
- sprintf (buf, "%s: %s", (*current_sched_info->print_insn) (x, 1), t);
+#ifdef INSN_SCHEDULING
+ if (verbose && current_sched_info)
+ sprintf (buf, "%s: %s", (*current_sched_info->print_insn) (insn, 1), t);
else
- sprintf (buf, "%-4d %s", INSN_UID (insn), t);
+#endif
+ sprintf (buf, " %4d %s", INSN_UID (insn), t);
break;
case CODE_LABEL:
sprintf (buf, "L%d:", INSN_UID (x));
break;
case BARRIER:
- sprintf (buf, "i% 4d: barrier", INSN_UID (x));
+ sprintf (buf, "i%4d: barrier", INSN_UID (x));
break;
case NOTE:
- if (NOTE_LINE_NUMBER (x) > 0)
- sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
- NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
- else
- sprintf (buf, "%4d %s", INSN_UID (x),
- GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
+ sprintf (buf, " %4d %s", INSN_UID (x),
+ GET_NOTE_INSN_NAME (NOTE_KIND (x)));
break;
default:
- if (verbose)
- {
- sprintf (buf, "Not an INSN at all\n");
- debug_rtx (x);
- }
- else
- sprintf (buf, "i%-4d <What?>", INSN_UID (x));
+ sprintf (buf, "i%4d <What %s?>", INSN_UID (x),
+ GET_RTX_NAME (GET_CODE (x)));
}
} /* print_insn */
-/* Print visualization debugging info. */
-
+/* Emit a slim dump of X (an insn) to the file F, including any register
+ note attached to the instruction. */
void
-print_block_visualization (s)
- const char *s;
+dump_insn_slim (FILE *f, rtx x)
{
- int unit, i;
-
- /* Print header. */
- fprintf (sched_dump, "\n;; ==================== scheduling visualization %s \n", s);
-
- /* Print names of units. */
- fprintf (sched_dump, ";; %-8s", "clock");
- for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
- if (function_units[unit].bitmask & target_units)
- for (i = 0; i < function_units[unit].multiplicity; i++)
- fprintf (sched_dump, " %-33s", function_units[unit].name);
- fprintf (sched_dump, " %-8s\n", "no-unit");
-
- fprintf (sched_dump, ";; %-8s", "=====");
- for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
- if (function_units[unit].bitmask & target_units)
- for (i = 0; i < function_units[unit].multiplicity; i++)
- fprintf (sched_dump, " %-33s", "==============================");
- fprintf (sched_dump, " %-8s\n", "=======");
-
- /* Print insns in each cycle. */
- fprintf (sched_dump, "%s\n", visual_tbl);
+ char t[BUF_LEN + 32];
+ rtx note;
+
+ print_insn (t, x, 1);
+ fputs (t, f);
+ putc ('\n', f);
+ if (INSN_P (x) && REG_NOTES (x))
+ for (note = REG_NOTES (x); note; note = XEXP (note, 1))
+ {
+ print_value (t, XEXP (note, 0), 1);
+ fprintf (f, " %s: %s\n",
+ GET_REG_NOTE_NAME (REG_NOTE_KIND (note)), t);
+ }
}
-/* Print insns in the 'no_unit' column of visualization. */
-
+/* Emit a slim dump of X (an insn) to stderr. */
void
-visualize_no_unit (insn)
- rtx insn;
+debug_insn_slim (rtx x)
{
- vis_no_unit[n_vis_no_unit] = insn;
- n_vis_no_unit++;
+ dump_insn_slim (stderr, x);
}
-/* Print insns scheduled in clock, for visualization. */
-
+/* Provide a slim dump the instruction chain starting at FIRST to F, honoring
+ the dump flags given in FLAGS. Currently, TDF_BLOCKS and TDF_DETAILS
+ include more information on the basic blocks. */
void
-visualize_scheduled_insns (clock)
- int clock;
+print_rtl_slim_with_bb (FILE *f, rtx first, int flags)
{
- int i, unit;
-
- /* If no more room, split table into two. */
- if (n_visual_lines >= MAX_VISUAL_LINES)
- {
- print_block_visualization ("(incomplete)");
- init_block_visualization ();
- }
-
- n_visual_lines++;
-
- sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
- for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
- if (function_units[unit].bitmask & target_units)
- for (i = 0; i < function_units[unit].multiplicity; i++)
- {
- int instance = unit + i * FUNCTION_UNITS_SIZE;
- rtx insn = get_unit_last_insn (instance);
-
- /* Print insns that still keep the unit busy. */
- if (insn
- && actual_hazard_this_instance (unit, instance, insn, clock, 0))
- {
- char str[BUF_LEN];
- print_insn (str, insn, 0);
- str[INSN_LEN] = '\0';
- sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
- }
- else
- sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
- }
-
- /* Print insns that are not assigned to any unit. */
- for (i = 0; i < n_vis_no_unit; i++)
- sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
- INSN_UID (vis_no_unit[i]));
- n_vis_no_unit = 0;
-
- sprintf (visual_tbl + strlen (visual_tbl), "\n");
+ print_rtl_slim (f, first, NULL, -1, flags);
}
-/* Print stalled cycles. */
-
+/* Same as above, but stop at LAST or when COUNT == 0.
+ If COUNT < 0 it will stop only at LAST or NULL rtx. */
void
-visualize_stall_cycles (stalls)
- int stalls;
+print_rtl_slim (FILE *f, rtx first, rtx last, int count, int flags)
{
- int i;
- const char *prefix = ";; ";
- const char *suffix = "\n";
- char *p;
+ basic_block current_bb = NULL;
+ rtx insn, tail;
- /* If no more room, split table into two. */
- if (n_visual_lines >= MAX_VISUAL_LINES)
+ tail = last ? NEXT_INSN (last) : NULL_RTX;
+ for (insn = first;
+ (insn != NULL) && (insn != tail) && (count != 0);
+ insn = NEXT_INSN (insn))
{
- print_block_visualization ("(incomplete)");
- init_block_visualization ();
- }
-
- n_visual_lines++;
+ if ((flags & TDF_BLOCKS)
+ && (INSN_P (insn) || NOTE_P (insn))
+ && BLOCK_FOR_INSN (insn)
+ && !current_bb)
+ {
+ current_bb = BLOCK_FOR_INSN (insn);
+ dump_bb_info (current_bb, true, false, flags, ";; ", f);
+ }
- p = visual_tbl + strlen (visual_tbl);
- strcpy (p, prefix);
- p += strlen (prefix);
+ dump_insn_slim (f, insn);
- if ((unsigned)stalls >
- visual_tbl_line_length - strlen (prefix) - strlen (suffix))
- {
- suffix = "[...]\n";
- stalls = visual_tbl_line_length - strlen (prefix) - strlen (suffix);
+ if ((flags & TDF_BLOCKS)
+ && current_bb
+ && insn == BB_END (current_bb))
+ {
+ dump_bb_info (current_bb, false, true, flags, ";; ", f);
+ current_bb = NULL;
+ }
+ if (count > 0)
+ count--;
}
-
- memset (p, '.', stalls);
- p += stalls;
-
- strcpy (p, suffix);
}
-/* Allocate data used for visualization during scheduling. */
-
void
-visualize_alloc ()
+debug_bb_slim (struct basic_block_def *bb)
{
- visual_tbl = xmalloc (get_visual_tbl_length ());
+ print_rtl_slim (stderr, BB_HEAD (bb), BB_END (bb), -1, 32);
}
-/* Free data used for visualization. */
-
void
-visualize_free ()
+debug_bb_n_slim (int n)
{
- free (visual_tbl);
+ struct basic_block_def *bb = BASIC_BLOCK (n);
+ debug_bb_slim (bb);
}
-#endif
+