/* Instruction scheduling pass.
- Copyright (C) 1992 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93-96, 1997 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com)
Enhanced by, and currently maintained by, Jim Wilson (wilson@cygnus.com)
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 Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
/* Instruction scheduling pass.
reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
basic_block_end.
- The information in the line number notes is carefully retained by this
- pass. All other NOTE insns are grouped in their same relative order at
- the beginning of basic blocks that have been scheduled. */
+ The information in the line number notes is carefully retained by
+ this pass. Notes that refer to the starting and ending of
+ exception regions are also carefully retained by this pass. All
+ other NOTE insns are grouped in their same relative order at the
+ beginning of basic blocks that have been scheduled. */
\f
#include <stdio.h>
#include "config.h"
#include "insn-config.h"
#include "insn-attr.h"
+#ifdef INSN_SCHEDULING
/* Arrays set up by scheduling for the same respective purposes as
similar-named arrays set up by flow analysis. We work with these
arrays during the scheduling pass so we can compare values against
by splitting insns. */
static rtx *reg_last_uses;
static rtx *reg_last_sets;
+static regset reg_pending_sets;
+static int reg_pending_sets_all;
/* Vector indexed by INSN_UID giving the original ordering of the insns. */
static int *insn_luid;
static int *insn_tick;
#define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
+/* Data structure for keeping track of register information
+ during that register's life. */
+
+struct sometimes
+{
+ short offset; short bit;
+ short live_length; short calls_crossed;
+};
+
/* Forward declarations. */
-static void sched_analyze_2 ();
-static void schedule_block ();
+static rtx canon_rtx PROTO((rtx));
+static int rtx_equal_for_memref_p PROTO((rtx, rtx));
+static rtx find_symbolic_term PROTO((rtx));
+static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
+ HOST_WIDE_INT));
+static void add_dependence PROTO((rtx, rtx, enum reg_note));
+static void remove_dependence PROTO((rtx, rtx));
+static rtx find_insn_list PROTO((rtx, rtx));
+static int insn_unit PROTO((rtx));
+static unsigned int blockage_range PROTO((int, rtx));
+static void clear_units PROTO((void));
+static void prepare_unit PROTO((int));
+static int actual_hazard_this_instance PROTO((int, int, rtx, int, int));
+static void schedule_unit PROTO((int, rtx, int));
+static int actual_hazard PROTO((int, rtx, int, int));
+static int potential_hazard PROTO((int, rtx, int));
+static int insn_cost PROTO((rtx, rtx, rtx));
+static int priority PROTO((rtx));
+static void free_pending_lists PROTO((void));
+static void add_insn_mem_dependence PROTO((rtx *, rtx *, rtx, rtx));
+static void flush_pending_lists PROTO((rtx, int));
+static void sched_analyze_1 PROTO((rtx, rtx));
+static void sched_analyze_2 PROTO((rtx, rtx));
+static void sched_analyze_insn PROTO((rtx, rtx, rtx));
+static int sched_analyze PROTO((rtx, rtx));
+static void sched_note_set PROTO((int, rtx, int));
+static int rank_for_schedule PROTO((rtx *, rtx *));
+static void swap_sort PROTO((rtx *, int));
+static void queue_insn PROTO((rtx, int));
+static int birthing_insn PROTO((rtx));
+static void adjust_priority PROTO((rtx));
+static int schedule_insn PROTO((rtx, rtx *, int, int));
+static int schedule_select PROTO((rtx *, int, int, FILE *));
+static void create_reg_dead_note PROTO((rtx, rtx));
+static void attach_deaths PROTO((rtx, rtx, int));
+static void attach_deaths_insn PROTO((rtx));
+static rtx unlink_notes PROTO((rtx, rtx));
+static int new_sometimes_live PROTO((struct sometimes *, int, int,
+ int));
+static void finish_sometimes_live PROTO((struct sometimes *, int));
+static rtx reemit_notes PROTO((rtx, rtx));
+static void schedule_block PROTO((int, FILE *));
+static rtx regno_use_in PROTO((int, rtx));
+static void split_hard_reg_notes PROTO((rtx, rtx, rtx, rtx));
+static void new_insn_dead_notes PROTO((rtx, rtx, rtx, rtx));
+static void update_n_sets PROTO((rtx, int));
+static void update_flow_info PROTO((rtx, rtx, rtx, rtx));
/* Main entry point of this file. */
-void schedule_insns ();
+void schedule_insns PROTO((FILE *));
+
+#endif /* INSN_SCHEDULING */
\f
#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
for pseudo-register N. */
static rtx *reg_known_value;
+/* Vector recording for each reg_known_value whether it is due to a
+ REG_EQUIV note. Future passes (viz., reload) may replace the
+ pseudo with the equivalent expression and so we account for the
+ dependences that would be introduced if that happens. */
+/* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
+ assign_parms mention the arg pointer, and there are explicit insns in the
+ RTL that modify the arg pointer. Thus we must ensure that such insns don't
+ get scheduled across each other because that would invalidate the REG_EQUIV
+ notes. One could argue that the REG_EQUIV notes are wrong, but solving
+ the problem in the scheduler will likely give better code, so we do it
+ here. */
+static char *reg_known_equiv_p;
+
/* Indicates number of valid entries in reg_known_value. */
static int reg_known_value_size;
canon_rtx (x)
rtx x;
{
+ /* Recursively look for equivalences. */
if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
&& REGNO (x) <= reg_known_value_size)
- return reg_known_value[REGNO (x)];
+ return reg_known_value[REGNO (x)] == x
+ ? x : canon_rtx (reg_known_value[REGNO (x)]);
else if (GET_CODE (x) == PLUS)
{
rtx x0 = canon_rtx (XEXP (x, 0));
return gen_rtx (PLUS, GET_MODE (x), x0, x1);
}
}
+ /* This gives us much better alias analysis when called from
+ the loop optimizer. Note we want to leave the original
+ MEM alone, but need to return the canonicalized MEM with
+ all the flags with their original values. */
+ else if (GET_CODE (x) == MEM)
+ {
+ rtx copy = copy_rtx (x);
+ XEXP (copy, 0) = canon_rtx (XEXP (copy, 0));
+ x = copy;
+ }
return x;
}
reg_known_value
= (rtx *) oballoc ((maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx))
- FIRST_PSEUDO_REGISTER;
- bzero (reg_known_value+FIRST_PSEUDO_REGISTER,
+ bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER),
(maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
+ reg_known_equiv_p
+ = (char *) oballoc ((maxreg -FIRST_PSEUDO_REGISTER) * sizeof (char))
+ - FIRST_PSEUDO_REGISTER;
+ bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER,
+ (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char));
+
/* Fill in the entries with known constant values. */
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if ((set = single_set (insn)) != 0
&& reg_n_sets[REGNO (SET_DEST (set))] == 1)
|| (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
&& GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- reg_known_value[REGNO (SET_DEST (set))] = XEXP (note, 0);
+ {
+ int regno = REGNO (SET_DEST (set));
+ reg_known_value[regno] = XEXP (note, 0);
+ reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
+ }
/* Fill in the remaining entries. */
while (--maxreg >= FIRST_PSEUDO_REGISTER)
if (code == SYMBOL_REF)
return XSTR (x, 0) == XSTR (y, 0);
+ /* For commutative operations, the RTX match if the operand match in any
+ order. Also handle the simple binary and unary cases without a loop. */
+ if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
+ return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
+ && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
+ || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
+ && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
+ else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
+ return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
+ && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)));
+ else if (GET_RTX_CLASS (code) == '1')
+ return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0));
+
/* Compare the elements. If any pair of corresponding elements
fail to match, return 0 for the whole things. */
Nice to notice that varying addresses cannot conflict with fp if no
local variables had their addresses taken, but that's too hard now. */
+/* ??? In Fortran, references to a array parameter can never conflict with
+ another array parameter. */
+
static int
memrefs_conflict_p (xsize, x, ysize, y, c)
rtx x, y;
return (xsize == 0 || ysize == 0 ||
(c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
- if (y == frame_pointer_rtx || y == stack_pointer_rtx)
+ if (y == frame_pointer_rtx || y == hard_frame_pointer_rtx
+ || y == stack_pointer_rtx)
{
rtx t = y;
int tsize = ysize;
x = t; xsize = tsize;
}
- if (x == frame_pointer_rtx || x == stack_pointer_rtx)
+ if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ || x == stack_pointer_rtx)
{
rtx y1;
changed. A volatile and non-volatile reference can be interchanged
though.
- A MEM_IN_STRUCT reference at a varying address can never conflict with a
- non-MEM_IN_STRUCT reference at a fixed address. */
+ A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
+ conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
+ allow QImode aliasing because the ANSI C standard allows character
+ pointers to alias anything. We are assuming that characters are
+ always QImode here. We also must allow AND addresses, because they may
+ generate accesses outside the object being referenced. This is used to
+ generate aligned addresses from unaligned addresses, for instance, the
+ alpha storeqi_unaligned pattern. */
/* Read dependence: X is read after read in MEM takes place. There can
only be a dependence here if both reads are volatile. */
both an unchanging read and an unchanging write. This won't handle all
cases optimally, but the possible performance loss should be
negligible. */
+ x = canon_rtx (x);
+ mem = canon_rtx (mem);
if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
return 0;
|| (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
SIZE_FOR_MODE (x), XEXP (x, 0), 0)
&& ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
+ && GET_MODE (mem) != QImode
+ && GET_CODE (XEXP (mem, 0)) != AND
&& ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
&& ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
+ && GET_MODE (x) != QImode
+ && GET_CODE (XEXP (x, 0)) != AND
&& ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
}
{
/* If MEM is an unchanging read, then it can't possibly conflict with
the store to X, because there is at most one store to MEM, and it must
- have occured somewhere before MEM. */
+ have occurred somewhere before MEM. */
+ x = canon_rtx (x);
+ mem = canon_rtx (mem);
if (RTX_UNCHANGING_P (mem))
return 0;
|| (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
SIZE_FOR_MODE (x), XEXP (x, 0), 0)
&& ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
+ && GET_MODE (mem) != QImode
+ && GET_CODE (XEXP (mem, 0)) != AND
&& ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
&& ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
+ && GET_MODE (x) != QImode
+ && GET_CODE (XEXP (x, 0)) != AND
&& ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
}
rtx mem;
rtx x;
{
+ x = canon_rtx (x);
+ mem = canon_rtx (mem);
return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
|| (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
SIZE_FOR_MODE (x), XEXP (x, 0), 0)
&& ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
+ && GET_MODE (mem) != QImode
+ && GET_CODE (XEXP (mem, 0)) != AND
&& ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
&& ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
+ && GET_MODE (x) != QImode
+ && GET_CODE (XEXP (x, 0)) != AND
&& ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
}
\f
LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
of dependence that this link represents. */
-void
+static void
add_dependence (insn, elem, dep_type)
rtx insn;
rtx elem;
next = NEXT_INSN (next);
#endif
- if (next && SCHED_GROUP_P (next))
+ if (next && SCHED_GROUP_P (next)
+ && GET_CODE (next) != CODE_LABEL)
{
/* Notes will never intervene here though, so don't bother checking
for them. */
- while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next)))
+ /* We must reject CODE_LABELs, so that we don't get confused by one
+ that has LABEL_PRESERVE_P set, which is represented by the same
+ bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
+ SCHED_GROUP_P. */
+ while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
+ && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
next = NEXT_INSN (next);
/* Again, don't depend an insn on itself. */
/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
of INSN. Abort if not found. */
-void
+
+static void
remove_dependence (insn, elem)
rtx insn;
rtx elem;
}
\f
#ifndef INSN_SCHEDULING
-void schedule_insns () {}
+void
+schedule_insns (dump_file)
+ FILE *dump_file;
+{
+}
#else
#ifndef __GNUC__
#define __inline
static void
clear_units ()
{
- int unit;
-
- bzero (unit_last_insn, sizeof (unit_last_insn));
- bzero (unit_tick, sizeof (unit_tick));
- bzero (unit_n_insns, sizeof (unit_n_insns));
+ bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
+ bzero ((char *) unit_tick, sizeof (unit_tick));
+ bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
}
/* Record an insn as one that will use the units encoded by UNIT. */
int unit, instance, clock, cost;
rtx insn;
{
- int i;
int tick = unit_tick[instance];
if (tick - clock > cost)
{
/* Find the instance of the function unit with the minimum hazard. */
int instance = unit;
- int best = instance;
int best_cost = actual_hazard_this_instance (unit, instance, insn,
clock, cost);
int this_cost;
clock, cost);
if (this_cost < best_cost)
{
- best = instance;
best_cost = this_cost;
if (this_cost <= cost)
break;
{
rtx x = XEXP (prev, 0);
- /* A dependence pointing to a note is always obsolete, because
- sched_analyze_insn will have created any necessary new dependences
- which replace it. Notes can be created when instructions are
- deleted by insn splitting, or by register allocation. */
- if (GET_CODE (x) == NOTE)
+ /* A dependence pointing to a note or deleted insn is always
+ obsolete, because sched_analyze_insn will have created any
+ necessary new dependences which replace it. Notes and deleted
+ insns can be created when instructions are deleted by insn
+ splitting, or by register allocation. */
+ if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
{
remove_dependence (insn, x);
continue;
insn_cost of the current instruction to its priority (e.g.
move the insn_cost call down to the end). */
- if (REG_NOTE_KIND (prev) == 0)
- /* Data dependence. */
- prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
- else
- /* Anti or output dependence. Don't add the latency of this
- insn's result, because it isn't being used. */
- prev_priority = priority (x);
+ prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
if (prev_priority > max_priority)
max_priority = prev_priority;
}
\f
/* Make a dependency between every memory reference on the pending lists
- and INSN, thus flushing the pending lists. */
+ and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
+ the read list. */
static void
-flush_pending_lists (insn)
+flush_pending_lists (insn, only_write)
rtx insn;
+ int only_write;
{
rtx link;
- while (pending_read_insns)
+ while (pending_read_insns && ! only_write)
{
add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
if (GET_CODE (dest) == REG)
{
- register int offset, bit, i;
+ register int i;
regno = REGNO (dest);
if (reg_last_sets[regno + i])
add_dependence (insn, reg_last_sets[regno + i],
REG_DEP_OUTPUT);
- reg_last_sets[regno + i] = insn;
+ reg_pending_sets[(regno + i) / REGSET_ELT_BITS]
+ |= (REGSET_ELT_TYPE) 1 << ((regno + i) % REGSET_ELT_BITS);
if ((call_used_regs[i] || global_regs[i])
&& last_function_call)
/* Function calls clobber all call_used regs. */
reg_last_uses[regno] = 0;
if (reg_last_sets[regno])
add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
- reg_last_sets[regno] = insn;
+ reg_pending_sets[regno / REGSET_ELT_BITS]
+ |= (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
+
+ /* Pseudos that are REG_EQUIV to something may be replaced
+ by that during reloading. We need only add dependencies for
+ the address in the REG_EQUIV note. */
+ if (! reload_completed
+ && reg_known_equiv_p[regno]
+ && GET_CODE (reg_known_value[regno]) == MEM)
+ sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
/* Don't let it cross a call after scheduling if it doesn't
already cross one. */
seems like a reasonable number. When compiling GCC with itself,
this flush occurs 8 times for sparc, and 10 times for m88k using
the number 32. */
- flush_pending_lists (insn);
+ flush_pending_lists (insn, 0);
}
else
{
{
/* If a dependency already exists, don't create a new one. */
if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
- if (anti_dependence (XEXP (pending_mem, 0), dest, insn))
+ if (anti_dependence (XEXP (pending_mem, 0), dest))
add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
pending = XEXP (pending, 1);
{
rtx link, prev;
+ /* User of CC0 depends on immediately preceding insn. */
+ SCHED_GROUP_P (insn) = 1;
+
/* There may be a note before this insn now, but all notes will
be removed before we actually try to schedule the insns, so
it won't cause a problem later. We must avoid it here though. */
-
- /* User of CC0 depends on immediately preceding insn. */
- SCHED_GROUP_P (insn) = 1;
+ prev = prev_nonnote_insn (insn);
/* Make a copy of all dependencies on the immediately previous insn,
and add to this insn. This is so that all the dependencies will
- apply to the group. */
+ apply to the group. Remove an explicit dependence on this insn
+ as SCHED_GROUP_P now represents it. */
- prev = PREV_INSN (insn);
- while (GET_CODE (prev) == NOTE)
- prev = PREV_INSN (prev);
+ if (find_insn_list (prev, LOG_LINKS (insn)))
+ remove_dependence (insn, prev);
for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
- add_dependence (insn, XEXP (link, 0), GET_MODE (link));
+ add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
return;
}
if (reg_last_sets[regno])
add_dependence (insn, reg_last_sets[regno], 0);
+ /* Pseudos that are REG_EQUIV to something may be replaced
+ by that during reloading. We need only add dependencies for
+ the address in the REG_EQUIV note. */
+ if (! reload_completed
+ && reg_known_equiv_p[regno]
+ && GET_CODE (reg_known_value[regno]) == MEM)
+ sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
+
/* If the register does not already cross any calls, then add this
insn to the sched_before_next_call list so that it will still
not cross calls after scheduling. */
rtx u;
/* Traditional and volatile asm instructions must be considered to use
- and clobber all hard registers and all of memory. So must
- TRAP_IF and UNSPEC_VOLATILE operations. */
+ and clobber all hard registers, all pseudo-registers and all of
+ memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
+
+ Consider for instance a volatile asm that changes the fpu rounding
+ mode. An insn should not be moved across this even if it only uses
+ pseudo-regs because it might give an incorrectly rounded result. */
if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
{
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ int max_reg = max_reg_num ();
+ for (i = 0; i < max_reg; i++)
{
for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
- if (GET_CODE (PATTERN (XEXP (u, 0))) != USE)
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
reg_last_uses[i] = 0;
- if (reg_last_sets[i]
- && GET_CODE (PATTERN (reg_last_sets[i])) != USE)
+ if (reg_last_sets[i])
add_dependence (insn, reg_last_sets[i], 0);
- reg_last_sets[i] = insn;
}
+ reg_pending_sets_all = 1;
- flush_pending_lists (insn);
+ flush_pending_lists (insn, 0);
}
/* For all ASM_OPERANDS, we must traverse the vector of input operands.
case POST_DEC:
case PRE_INC:
case POST_INC:
- /* These read and modify the result; just consider them writes. */
+ /* These both read and modify the result. We must handle them as writes
+ to get proper dependencies for following instructions. We must handle
+ them as reads to get proper dependencies from this to previous
+ instructions. Thus we need to pass them to both sched_analyze_1
+ and sched_analyze_2. We must call sched_analyze_2 first in order
+ to get the proper antecedent for the read. */
+ sched_analyze_2 (XEXP (x, 0), insn);
sched_analyze_1 (x, insn);
return;
}
/* Analyze an INSN with pattern X to find all dependencies. */
static void
-sched_analyze_insn (x, insn)
+sched_analyze_insn (x, insn, loop_notes)
rtx x, insn;
+ rtx loop_notes;
{
register RTX_CODE code = GET_CODE (x);
rtx link;
+ int maxreg = max_reg_num ();
+ int i;
if (code == SET || code == CLOBBER)
sched_analyze_1 (x, insn);
else
sched_analyze_2 (x, insn);
- /* Handle function calls. */
+ /* Mark registers CLOBBERED or used by called function. */
if (GET_CODE (insn) == CALL_INSN)
+ for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
+ {
+ if (GET_CODE (XEXP (link, 0)) == CLOBBER)
+ sched_analyze_1 (XEXP (link, 0), insn);
+ else
+ sched_analyze_2 (XEXP (link, 0), insn);
+ }
+
+ /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
+ we must be sure that no instructions are scheduled across it.
+ Otherwise, the reg_n_refs info (which depends on loop_depth) would
+ become incorrect. */
+
+ if (loop_notes)
+ {
+ int max_reg = max_reg_num ();
+ rtx link;
+
+ for (i = 0; i < max_reg; i++)
+ {
+ rtx u;
+ for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ reg_last_uses[i] = 0;
+ if (reg_last_sets[i])
+ add_dependence (insn, reg_last_sets[i], 0);
+ }
+ reg_pending_sets_all = 1;
+
+ flush_pending_lists (insn, 0);
+
+ link = loop_notes;
+ while (XEXP (link, 1))
+ link = XEXP (link, 1);
+ XEXP (link, 1) = REG_NOTES (insn);
+ REG_NOTES (insn) = loop_notes;
+ }
+
+ /* After reload, it is possible for an instruction to have a REG_DEAD note
+ for a register that actually dies a few instructions earlier. For
+ example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
+ In this case, we must consider the insn to use the register mentioned
+ in the REG_DEAD note. Otherwise, we may accidentally move this insn
+ after another insn that sets the register, thus getting obviously invalid
+ rtl. This confuses reorg which believes that REG_DEAD notes are still
+ meaningful.
+
+ ??? We would get better code if we fixed reload to put the REG_DEAD
+ notes in the right places, but that may not be worth the effort. */
+
+ if (reload_completed)
+ {
+ rtx note;
+
+ for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+ if (REG_NOTE_KIND (note) == REG_DEAD)
+ sched_analyze_2 (XEXP (note, 0), insn);
+ }
+
+ for (i = 0; i < regset_size; i++)
+ {
+ REGSET_ELT_TYPE sets = reg_pending_sets[i];
+ if (sets)
+ {
+ register int bit;
+ for (bit = 0; bit < REGSET_ELT_BITS; bit++)
+ if (sets & ((REGSET_ELT_TYPE) 1 << bit))
+ reg_last_sets[i * REGSET_ELT_BITS + bit] = insn;
+ reg_pending_sets[i] = 0;
+ }
+ }
+ if (reg_pending_sets_all)
+ {
+ for (i = 0; i < maxreg; i++)
+ reg_last_sets[i] = insn;
+ reg_pending_sets_all = 0;
+ }
+
+ /* Handle function calls and function returns created by the epilogue
+ threading code. */
+ if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
{
rtx dep_insn;
rtx prev_dep_insn;
/* When scheduling instructions, we make sure calls don't lose their
- accompanying USE insns by depending them one on another in order. */
+ accompanying USE insns by depending them one on another in order.
+
+ Also, we must do the same thing for returns created by the epilogue
+ threading code. Note this code works only in this special case,
+ because other passes make no guarantee that they will never emit
+ an instruction between a USE and a RETURN. There is such a guarantee
+ for USE instructions immediately before a call. */
prev_dep_insn = insn;
dep_insn = PREV_INSN (insn);
while (GET_CODE (dep_insn) == INSN
- && GET_CODE (PATTERN (dep_insn)) == USE)
+ && GET_CODE (PATTERN (dep_insn)) == USE
+ && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
{
SCHED_GROUP_P (prev_dep_insn) = 1;
group. */
for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
- add_dependence (insn, XEXP (link, 0), GET_MODE (link));
+ add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
prev_dep_insn = dep_insn;
dep_insn = PREV_INSN (dep_insn);
register int n_insns = 0;
register rtx u;
register int luid = 0;
+ rtx loop_notes = 0;
for (insn = head; ; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
{
- sched_analyze_insn (PATTERN (insn), insn);
+ sched_analyze_insn (PATTERN (insn), insn, loop_notes);
+ loop_notes = 0;
n_insns += 1;
}
else if (GET_CODE (insn) == CALL_INSN)
{
- rtx dest = 0;
rtx x;
register int i;
past a void call (i.e. it does not explicitly set the hard
return reg). */
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (call_used_regs[i] || global_regs[i])
- {
- for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
- if (GET_CODE (PATTERN (XEXP (u, 0))) != USE)
+ /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
+ all registers, not just hard registers, may be clobbered by this
+ call. */
+
+ /* Insn, being a CALL_INSN, magically depends on
+ `last_function_call' already. */
+
+ if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
+ && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
+ {
+ int max_reg = max_reg_num ();
+ for (i = 0; i < max_reg; i++)
+ {
+ for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- reg_last_uses[i] = 0;
- if (reg_last_sets[i]
- && GET_CODE (PATTERN (reg_last_sets[i])) != USE)
- add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
- reg_last_sets[i] = insn;
- /* Insn, being a CALL_INSN, magically depends on
- `last_function_call' already. */
- }
+ reg_last_uses[i] = 0;
+ if (reg_last_sets[i])
+ add_dependence (insn, reg_last_sets[i], 0);
+ }
+ reg_pending_sets_all = 1;
+
+ /* Add a pair of fake REG_NOTEs which we will later
+ convert back into a NOTE_INSN_SETJMP note. See
+ reemit_notes for why we use a pair of of NOTEs. */
+
+ REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_DEAD,
+ GEN_INT (0),
+ REG_NOTES (insn));
+ REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_DEAD,
+ GEN_INT (NOTE_INSN_SETJMP),
+ REG_NOTES (insn));
+ }
+ else
+ {
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (call_used_regs[i] || global_regs[i])
+ {
+ for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ reg_last_uses[i] = 0;
+ if (reg_last_sets[i])
+ add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
+ reg_pending_sets[i / REGSET_ELT_BITS]
+ |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
+ }
+ }
/* For each insn which shouldn't cross a call, add a dependence
between that insn and this call insn. */
}
LOG_LINKS (sched_before_next_call) = 0;
- sched_analyze_insn (PATTERN (insn), insn);
+ sched_analyze_insn (PATTERN (insn), insn, loop_notes);
+ loop_notes = 0;
- /* We don't need to flush memory for a function call which does
- not involve memory. */
- if (! CONST_CALL_P (insn))
- {
- /* In the absence of interprocedural alias analysis,
- we must flush all pending reads and writes, and
- start new dependencies starting from here. */
- flush_pending_lists (insn);
- }
+ /* In the absence of interprocedural alias analysis, we must flush
+ all pending reads and writes, and start new dependencies starting
+ from here. But only flush writes for constant calls (which may
+ be passed a pointer to something we haven't written yet). */
+ flush_pending_lists (insn, CONST_CALL_P (insn));
/* Depend this function call (actually, the user of this
function call) on all hard register clobberage. */
n_insns += 1;
}
+ /* See comments on reemit_notes as to why we do this. */
+ else if (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
+ || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
+ && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
+ {
+ loop_notes = gen_rtx (EXPR_LIST, REG_DEAD,
+ GEN_INT (NOTE_BLOCK_NUMBER (insn)), loop_notes);
+ loop_notes = gen_rtx (EXPR_LIST, REG_DEAD,
+ GEN_INT (NOTE_LINE_NUMBER (insn)), loop_notes);
+ CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
+ }
+
if (insn == tail)
return n_insns;
}
+
+ abort ();
}
\f
/* Called when we see a set of a register. If death is true, then we are
rtx x;
int death;
{
- register int regno, j;
+ register int regno;
register rtx reg = SET_DEST (x);
int subreg_p = 0;
{
/* Must treat modification of just one hardware register of a multi-reg
value or just a byte field of a register exactly the same way that
- mark_set_1 in flow.c does. */
- if (GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || (GET_CODE (reg) == SUBREG
- && REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg)))
+ mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
+ does not kill the entire register. */
+ if (GET_CODE (reg) != SUBREG
+ || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
subreg_p = 1;
reg = SUBREG_REG (reg);
}
\f
/* Macros and functions for keeping the priority queue sorted, and
- dealing with queueing and unqueueing of instructions. */
+ dealing with queueing and dequeueing of instructions. */
#define SCHED_SORT(READY, NEW_READY, OLD_READY) \
do { if ((NEW_READY) - (OLD_READY) == 1) \
rtx note;
int n_deaths = 0;
+ /* ??? This code has no effect, because REG_DEAD notes are removed
+ before we ever get here. */
for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_DEAD)
n_deaths += 1;
}
break;
}
+#ifdef ADJUST_PRIORITY
+ ADJUST_PRIORITY (prev);
+#endif
}
}
create_reg_dead_note (reg, insn)
rtx reg, insn;
{
- rtx link = dead_notes;
+ rtx link;
- if (link == 0)
- /* In theory, we should not end up with more REG_DEAD reg notes than we
- started with. In practice, this can occur as the result of bugs in
- flow, combine and/or sched. */
+ /* The number of registers killed after scheduling must be the same as the
+ number of registers killed before scheduling. The number of REG_DEAD
+ notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
+ might become one DImode hard register REG_DEAD note, but the number of
+ registers killed will be conserved.
+
+ We carefully remove REG_DEAD notes from the dead_notes list, so that
+ there will be none left at the end. If we run out early, then there
+ is a bug somewhere in flow, combine and/or sched. */
+
+ if (dead_notes == 0)
{
#if 1
abort ();
#endif
}
else
- dead_notes = XEXP (dead_notes, 1);
+ {
+ /* Number of regs killed by REG. */
+ int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
+ : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
+ /* Number of regs killed by REG_DEAD notes taken off the list. */
+ int reg_note_regs;
+
+ link = dead_notes;
+ reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
+ : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
+ GET_MODE (XEXP (link, 0))));
+ while (reg_note_regs < regs_killed)
+ {
+ link = XEXP (link, 1);
+ reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
+ : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
+ GET_MODE (XEXP (link, 0))));
+ }
+ dead_notes = XEXP (link, 1);
+
+ /* If we took too many regs kills off, put the extra ones back. */
+ while (reg_note_regs > regs_killed)
+ {
+ rtx temp_reg, temp_link;
+
+ temp_reg = gen_rtx (REG, word_mode, 0);
+ temp_link = rtx_alloc (EXPR_LIST);
+ PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
+ XEXP (temp_link, 0) = temp_reg;
+ XEXP (temp_link, 1) = dead_notes;
+ dead_notes = temp_link;
+ reg_note_regs--;
+ }
+ }
XEXP (link, 0) = reg;
XEXP (link, 1) = REG_NOTES (insn);
STACK_POINTER_REGNUM, since these are always considered to be
live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
if (regno != FRAME_POINTER_REGNUM
+#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
+ && ! (regno == HARD_FRAME_POINTER_REGNUM)
+#endif
#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
#endif
&& regno != STACK_POINTER_REGNUM)
{
- if (! all_needed && ! dead_or_set_p (insn, x))
+ /* ??? It is perhaps a dead_or_set_p bug that it does
+ not check for REG_UNUSED notes itself. This is necessary
+ for the case where the SET_DEST is a subreg of regno, as
+ dead_or_set_p handles subregs specially. */
+ if (! all_needed && ! dead_or_set_p (insn, x)
+ && ! find_reg_note (insn, REG_UNUSED, x))
{
+ /* Check for the case where the register dying partially
+ overlaps the register set by this insn. */
+ if (regno < FIRST_PSEUDO_REGISTER
+ && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
+ {
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
+ while (--n >= 0)
+ some_needed |= dead_or_set_regno_p (insn, regno + n);
+ }
+
/* If none of the words in X is needed, make a REG_DEAD
note. Otherwise, we must make partial REG_DEAD
notes. */
& ((REGSET_ELT_TYPE) 1
<< ((regno +i) % REGSET_ELT_BITS))) == 0
&& ! dead_or_set_regno_p (insn, regno + i))
- create_reg_dead_note (gen_rtx (REG, word_mode,
+ create_reg_dead_note (gen_rtx (REG,
+ reg_raw_mode[regno + i],
regno + i),
insn);
}
{
rtx x = PATTERN (insn);
register RTX_CODE code = GET_CODE (x);
+ rtx link;
if (code == SET)
{
attach_deaths (XVECEXP (x, 0, i), insn, 0);
}
}
- /* Flow does not add REG_DEAD notes to registers that die in
- clobbers, so we can't either. */
+ /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
+ MEM being clobbered, just like flow. */
+ else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
+ attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
+ /* Otherwise don't add a death note to things being clobbered. */
else if (code != CLOBBER)
attach_deaths (x, insn, 0);
+
+ /* Make death notes for things used in the called function. */
+ if (GET_CODE (insn) == CALL_INSN)
+ for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
+ attach_deaths (XEXP (XEXP (link, 0), 0), insn,
+ GET_CODE (XEXP (link, 0)) == CLOBBER);
}
/* Delete notes beginning with INSN and maybe put them in the chain
if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
/* Record line-number notes so they can be reused. */
LINE_NOTE (insn) = insn;
- else
+
+ /* Don't save away NOTE_INSN_SETJMPs, because they must remain
+ immediately after the call they follow. We use a fake
+ (REG_DEAD (const_int -1)) note to remember them.
+ Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
+ else if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
{
/* Insert the note at the end of the notes list. */
PREV_INSN (insn) = note_list;
return insn;
}
-/* Data structure for keeping track of register information
- during that register's life. */
-
-struct sometimes
-{
- short offset; short bit;
- short live_length; short calls_crossed;
-};
-
/* Constructor for `sometimes' data structure. */
static int
{
register struct sometimes *p;
register int regno = offset * REGSET_ELT_BITS + bit;
- int i;
/* There should never be a register greater than max_regno here. If there
is, it means that a define_split has created a new pseudo reg. This
}
}
+/* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
+ NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
+ NOTEs. The REG_DEAD note following first one is contains the saved
+ value for NOTE_BLOCK_NUMBER which is useful for
+ NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
+ output by the instruction scheduler. Return the new value of LAST. */
+
+static rtx
+reemit_notes (insn, last)
+ rtx insn;
+ rtx last;
+{
+ rtx note;
+
+ for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+ {
+ if (REG_NOTE_KIND (note) == REG_DEAD
+ && GET_CODE (XEXP (note, 0)) == CONST_INT)
+ {
+ if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
+ {
+ CONST_CALL_P (emit_note_after (INTVAL (XEXP (note, 0)), insn))
+ = CONST_CALL_P (note);
+ remove_note (insn, note);
+ note = XEXP (note, 1);
+ }
+ else
+ {
+ last = emit_note_before (INTVAL (XEXP (note, 0)), last);
+ remove_note (insn, note);
+ note = XEXP (note, 1);
+ NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
+ }
+ remove_note (insn, note);
+ }
+ }
+ return last;
+}
+
/* Use modified list scheduling to rearrange insns in basic block
B. FILE, if nonzero, is where we dump interesting output about
this pass. */
FILE *file;
{
rtx insn, last;
- rtx last_note = 0;
rtx *ready, link;
- int i, j, n_ready = 0, new_ready, n_insns = 0;
+ int i, j, n_ready = 0, new_ready, n_insns;
int sched_n_insns = 0;
int clock;
#define NEED_NOTHING 0
i = max_reg_num ();
reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
- bzero (reg_last_uses, i * sizeof (rtx));
+ bzero ((char *) reg_last_uses, i * sizeof (rtx));
reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
- bzero (reg_last_sets, i * sizeof (rtx));
+ bzero ((char *) reg_last_sets, i * sizeof (rtx));
+ reg_pending_sets = (regset) alloca (regset_bytes);
+ bzero ((char *) reg_pending_sets, regset_bytes);
+ reg_pending_sets_all = 0;
clear_units ();
/* Remove certain insns at the beginning from scheduling,
LOG_LINKS (sched_before_next_call) = 0;
- n_insns += sched_analyze (head, tail);
+ n_insns = sched_analyze (head, tail);
if (n_insns == 0)
{
free_pending_lists ();
at the end because they can't be moved away from their cc0 user. */
last = 0;
while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
- || (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE)
+ || (GET_CODE (insn) == INSN
+ && (GET_CODE (PATTERN (insn)) == USE
#ifdef HAVE_cc0
- || sets_cc0_p (PATTERN (insn))
+ || sets_cc0_p (PATTERN (insn))
#endif
+ ))
|| GET_CODE (insn) == NOTE)
{
if (GET_CODE (insn) != NOTE)
{
while (SCHED_GROUP_P (insn))
{
- insn = PREV_INSN (insn);
- while (GET_CODE (insn) == NOTE)
- insn = PREV_INSN (insn);
+ insn = prev_nonnote_insn (insn);
priority (insn);
}
continue;
if (reload_completed == 0)
{
- bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes);
- bzero (bb_dead_regs, regset_bytes);
+ bcopy ((char *) basic_block_live_at_start[b], (char *) bb_live_regs,
+ regset_bytes);
+ bzero ((char *) bb_dead_regs, regset_bytes);
if (b == 0)
{
sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
}
+ /* Each call clobbers (makes live) all call-clobbered regs
+ that are not global or fixed. Note that the function-value
+ reg is a call_clobbered reg. */
+
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ int j;
+ for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
+ if (call_used_regs[j] && ! global_regs[j]
+ && ! fixed_regs[j])
+ {
+ register int offset = j / REGSET_ELT_BITS;
+ register REGSET_ELT_TYPE bit
+ = (REGSET_ELT_TYPE) 1 << (j % REGSET_ELT_BITS);
+
+ bb_live_regs[offset] |= bit;
+ bb_dead_regs[offset] &= ~bit;
+ }
+ }
+
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
{
if ((REG_NOTE_KIND (link) == REG_DEAD
|| REG_NOTE_KIND (link) == REG_UNUSED)
- /* Verify that the REG_NOTE has a legal value. */
+ /* Verify that the REG_NOTE has a valid value. */
&& GET_CODE (XEXP (link, 0)) == REG)
{
register int regno = REGNO (XEXP (link, 0));
sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
}
+ /* Each call clobbers (makes live) all call-clobbered regs that are
+ not global or fixed. Note that the function-value reg is a
+ call_clobbered reg. */
+
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ int j;
+ for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
+ if (call_used_regs[j] && ! global_regs[j]
+ && ! fixed_regs[j])
+ {
+ register int offset = j / REGSET_ELT_BITS;
+ register REGSET_ELT_TYPE bit
+ = (REGSET_ELT_TYPE) 1 << (j % REGSET_ELT_BITS);
+
+ bb_live_regs[offset] |= bit;
+ bb_dead_regs[offset] &= ~bit;
+ }
+ }
+
/* Need to know what registers this insn kills. */
for (prev = 0, link = REG_NOTES (insn); link; link = next)
{
- int regno;
-
next = XEXP (link, 1);
if ((REG_NOTE_KIND (link) == REG_DEAD
|| REG_NOTE_KIND (link) == REG_UNUSED)
- /* Verify that the REG_NOTE has a legal value. */
+ /* Verify that the REG_NOTE has a valid value. */
&& GET_CODE (XEXP (link, 0)) == REG)
{
register int regno = REGNO (XEXP (link, 0));
old_live_regs[j] = live;
if (live)
{
- register REGSET_ELT_TYPE bit;
+ register int bit;
for (bit = 0; bit < REGSET_ELT_BITS; bit++)
if (live & ((REGSET_ELT_TYPE) 1 << bit))
sometimes_max = new_sometimes_live (regs_sometimes_live, j,
/* Q_SIZE will always be zero here. */
q_ptr = 0; clock = 0;
- bzero (insn_queue, sizeof (insn_queue));
+ bzero ((char *) insn_queue, sizeof (insn_queue));
/* Now, perform list scheduling. */
{
if (file)
fprintf (file, "\n");
+ /* We must set n_ready here, to ensure that sorting always
+ occurs when we come back to the SCHED_SORT line above. */
+ n_ready = 0;
continue;
}
}
{
register struct sometimes *p;
- /* A call kills all call used and global registers, except
- for those mentioned in the call pattern which will be
- made live again later. */
+ /* A call kills all call used registers that are not
+ global or fixed, except for those mentioned in the call
+ pattern which will be made live again later. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (call_used_regs[i] || global_regs[i])
+ if (call_used_regs[i] && ! global_regs[i]
+ && ! fixed_regs[i])
{
register int offset = i / REGSET_ELT_BITS;
register REGSET_ELT_TYPE bit
sched_n_insns += 1;
NEXT_INSN (insn) = last;
PREV_INSN (last) = insn;
- last = insn;
/* Everything that precedes INSN now either becomes "ready", if
it can execute immediately before INSN, or "pending", if
/* Schedule all prior insns that must not be moved. */
if (SCHED_GROUP_P (insn))
{
- /* Disable these insns from being launched. */
+ /* Disable these insns from being launched, in case one of the
+ insns in the group has a dependency on an earlier one. */
link = insn;
while (SCHED_GROUP_P (link))
{
INSN_REF_COUNT (link) = 0;
}
- /* None of these insns can move forward into delay slots. */
- while (SCHED_GROUP_P (insn))
+ /* Now handle each group insn like the main insn was handled
+ above. */
+ link = insn;
+ while (SCHED_GROUP_P (link))
{
- insn = PREV_INSN (insn);
- new_ready = schedule_insn (insn, ready, new_ready, clock);
- INSN_PRIORITY (insn) = DONE_PRIORITY;
+ link = PREV_INSN (link);
sched_n_insns += 1;
- NEXT_INSN (insn) = last;
- PREV_INSN (last) = insn;
- last = insn;
+
+ /* ??? Why don't we set LAUNCH_PRIORITY here? */
+ new_ready = schedule_insn (link, ready, new_ready, clock);
+ INSN_PRIORITY (link) = DONE_PRIORITY;
}
}
+
+ /* Put back NOTE_INSN_SETJMP,
+ NOTE_INSN_{LOOP,EHREGION}_{BEGIN,END} notes. */
+
+ /* To prime the loop. We need to handle INSN and all the insns in the
+ sched group. */
+ last = NEXT_INSN (insn);
+ do
+ {
+ insn = PREV_INSN (last);
+
+ /* Maintain a valid chain so emit_note_before works.
+ This is necessary because PREV_INSN (insn) isn't valid
+ (if ! SCHED_GROUP_P) and if it points to an insn already
+ scheduled, a circularity will result. */
+ if (! SCHED_GROUP_P (insn))
+ {
+ NEXT_INSN (prev_head) = insn;
+ PREV_INSN (insn) = prev_head;
+ }
+
+ last = reemit_notes (insn, insn);
+ }
+ while (SCHED_GROUP_P (insn));
}
if (q_size != 0)
abort ();
/* HEAD is now the first insn in the chain of insns that
been scheduled by the loop above.
TAIL is the last of those insns. */
- head = insn;
+ head = last;
/* NOTE_LIST is the end of a chain of notes previously found
among the insns. Insert them at the beginning of the insns. */
head = note_head;
}
- /* In theory, there should be no REG_DEAD notes leftover at the end.
+ /* There should be no REG_DEAD notes leftover at the end.
In practice, this can occur as the result of bugs in flow, combine.c,
and/or sched.c. The values of the REG_DEAD notes remaining are
meaningless, because dead_notes is just used as a free list. */
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
- else if (! (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
+ /* This used to emit line number notes before every non-deleted note.
+ However, this confuses a debugger, because line notes not separated
+ by real instructions all end up at the same address. I can find no
+ use for line number notes before other notes, so none are emitted. */
+ else if (GET_CODE (insn) != NOTE
&& (note = LINE_NOTE (insn)) != 0
&& note != line
&& (line == 0
prev = PREV_INSN (insn);
if (LINE_NOTE (note))
{
- /* Re-use the original line-number note. */
+ /* Re-use the original line-number note. */
LINE_NOTE (note) = 0;
PREV_INSN (note) = prev;
NEXT_INSN (prev) = note;
notes++;
new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
+ RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
}
}
if (file && notes)
REGNO, returning the rtx of the reference found if any. Otherwise,
returns 0. */
-rtx
+static rtx
regno_use_in (regno, x)
int regno;
rtx x;
n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
- /* ??? Could add check here to see whether, the hard register is referenced
- in the same mode as in the original insn. If so, then it has not been
- split, and the rest of the code below is unnecessary. */
-
- for (i = 1; i < n_regs; i++)
+ for (i = 0; i < n_regs; i++)
{
new_reg = REGNO (reg) + i;
XEXP (link, 0) = temp;
XEXP (link, 1) = REG_NOTES (insn);
REG_NOTES (insn) = link;
+
+ /* If killed multiple registers here, then add in the excess. */
+ i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
+
break;
}
/* It isn't mentioned anywhere, so no new reg note is needed for
|| GET_CODE (tem_dest) == SIGN_EXTRACT)
tem_dest = XEXP (tem_dest, 0);
- if (tem_dest != dest)
+ if (! rtx_equal_p (tem_dest, dest))
{
/* Use the same scheme as combine.c, don't put both REG_DEAD
and REG_UNUSED notes on the same insn. */
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
{
- XEXP (note, 1) = REG_NOTES (insn);
- REG_NOTES (insn) = note;
+ /* If this note refers to a multiple word hard register, it
+ may have been split into several smaller hard register
+ references, so handle it specially. */
+ temp = XEXP (note, 0);
+ if (REG_NOTE_KIND (note) == REG_DEAD
+ && GET_CODE (temp) == REG
+ && REGNO (temp) < FIRST_PSEUDO_REGISTER
+ && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
+ split_hard_reg_notes (note, first, last, orig_insn);
+ else
+ {
+ XEXP (note, 1) = REG_NOTES (insn);
+ REG_NOTES (insn) = note;
+ }
/* Sometimes need to convert REG_UNUSED notes to REG_DEAD
notes. */
pattern, so we can safely ignore it. */
if (insn == first)
{
+ /* After reload, REG_DEAD notes come sometimes an
+ instruction after the register actually dies. */
+ if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
+ {
+ XEXP (note, 1) = REG_NOTES (insn);
+ REG_NOTES (insn) = note;
+ break;
+ }
+
if (REG_NOTE_KIND (note) != REG_UNUSED)
abort ();
break;
}
}
-
- /* If this note refers to a multiple word hard register, it may
- have been split into several smaller hard register references.
- Check to see if there are any new register references that
- need REG_NOTES added for them. */
- temp = XEXP (note, 0);
- if (REG_NOTE_KIND (note) == REG_DEAD
- && GET_CODE (temp) == REG
- && REGNO (temp) < FIRST_PSEUDO_REGISTER
- && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)))
- split_hard_reg_notes (note, first, last, orig_insn);
break;
case REG_WAS_0:
uses it. */
break;
}
+ /* If this note refers to a multiple word hard
+ register, it may have been split into several smaller
+ hard register references. We could split the notes,
+ but simply dropping them is good enough. */
+ if (GET_CODE (orig_dest) == REG
+ && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
+ && HARD_REGNO_NREGS (REGNO (orig_dest),
+ GET_MODE (orig_dest)) > 1)
+ break;
/* It must be set somewhere, fail if we couldn't find where it
was set. */
if (insn == last)
/* The original dest must still be set someplace. Abort if we
couldn't find it. */
if (insn == first)
- abort ();
+ {
+ /* However, if this note refers to a multiple word hard
+ register, it may have been split into several smaller
+ hard register references. We could split the notes,
+ but simply dropping them is good enough. */
+ if (GET_CODE (orig_dest) == REG
+ && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
+ && HARD_REGNO_NREGS (REGNO (orig_dest),
+ GET_MODE (orig_dest)) > 1)
+ break;
+ /* Likewise for multi-word memory references. */
+ if (GET_CODE (orig_dest) == MEM
+ && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
+ break;
+ abort ();
+ }
}
break;
XEXP (note, 0) = first;
break;
+ case REG_EXEC_COUNT:
+ /* Move a REG_EXEC_COUNT note to the first insn created. */
+ XEXP (note, 1) = REG_NOTES (first);
+ REG_NOTES (first) = note;
+ break;
+
case REG_RETVAL:
/* Move a REG_RETVAL note to the last insn created, and update
the corresponding REG_LIBCALL note. */
break;
case REG_NONNEG:
+ case REG_BR_PROB:
/* This should be moved to whichever instruction is a JUMP_INSN. */
for (insn = last; ; insn = PREV_INSN (insn))
break;
case REG_INC:
+ /* reload sometimes leaves obsolete REG_INC notes around. */
+ if (reload_completed)
+ break;
/* This should be moved to whichever instruction now has the
increment operation. */
abort ();
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG
+ /* Global registers are always live, so the code below does not
+ apply to them. */
+ && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
+ || ! global_regs[REGNO (dest)])
&& ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
{
for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn))
FILE *dump_file;
{
int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
- int i, b;
+ int b;
rtx insn;
/* Taking care of this degenerate case makes the rest of
sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
bb_dead_regs = (regset) alloca (regset_bytes);
bb_live_regs = (regset) alloca (regset_bytes);
- bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int));
- bzero (sched_reg_live_length, max_regno * sizeof (int));
- bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short));
+ bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
+ bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
+ bcopy ((char *) reg_n_deaths, (char *) sched_reg_n_deaths,
+ max_regno * sizeof (short));
init_alias_analysis ();
}
else
rtx line;
line_note = (rtx *) alloca (max_uid * sizeof (rtx));
- bzero (line_note, max_uid * sizeof (rtx));
+ bzero ((char *) line_note, max_uid * sizeof (rtx));
line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
- bzero (line_note_head, n_basic_blocks * sizeof (rtx));
+ bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
/* Determine the line-number at the start of each basic block.
This must be computed and saved now, because after a basic block's
}
}
- bzero (insn_luid, max_uid * sizeof (int));
- bzero (insn_priority, max_uid * sizeof (int));
- bzero (insn_tick, max_uid * sizeof (int));
- bzero (insn_costs, max_uid * sizeof (short));
- bzero (insn_units, max_uid * sizeof (short));
- bzero (insn_blockage, max_uid * sizeof (unsigned int));
- bzero (insn_ref_count, max_uid * sizeof (int));
+ bzero ((char *) insn_luid, max_uid * sizeof (int));
+ bzero ((char *) insn_priority, max_uid * sizeof (int));
+ bzero ((char *) insn_tick, max_uid * sizeof (int));
+ bzero ((char *) insn_costs, max_uid * sizeof (short));
+ bzero ((char *) insn_units, max_uid * sizeof (short));
+ bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
+ bzero ((char *) insn_ref_count, max_uid * sizeof (int));
/* Schedule each basic block, block by block. */
- if (NEXT_INSN (basic_block_end[n_basic_blocks-1]) == 0
- || (GET_CODE (basic_block_end[n_basic_blocks-1]) != NOTE
- && GET_CODE (basic_block_end[n_basic_blocks-1]) != CODE_LABEL))
+ /* ??? Add a NOTE after the last insn of the last basic block. It is not
+ known why this is done. */
+ /* ??? Perhaps it's done to ensure NEXT_TAIL in schedule_block is a
+ valid insn. */
+
+ insn = basic_block_end[n_basic_blocks-1];
+ if (NEXT_INSN (insn) == 0
+ || (GET_CODE (insn) != NOTE
+ && GET_CODE (insn) != CODE_LABEL
+ /* Don't emit a NOTE if it would end up between an unconditional
+ jump and a BARRIER. */
+ && ! (GET_CODE (insn) == JUMP_INSN
+ && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]);
for (b = 0; b < n_basic_blocks; b++)
{
rtx insn, next;
- rtx insns;
note_list = 0;
/* Split insns here to get max fine-grain parallelism. */
prev = PREV_INSN (insn);
- if (reload_completed == 0)
+ /* It is probably not worthwhile to try to split again in the
+ second pass. However, if flag_schedule_insns is not set,
+ the first and only (if any) scheduling pass is after reload. */
+ if (reload_completed == 0 || ! flag_schedule_insns)
{
rtx last, first = PREV_INSN (insn);
rtx notes = REG_NOTES (insn);
regno, reg_live_length[regno],
sched_reg_live_length[regno]);
- if (reg_n_calls_crossed[regno]
- && ! sched_reg_n_calls_crossed[regno])
- fprintf (dump_file,
- ";; register %d no longer crosses calls\n", regno);
- else if (! reg_n_calls_crossed[regno]
- && sched_reg_n_calls_crossed[regno])
+ if (! reg_n_calls_crossed[regno]
+ && sched_reg_n_calls_crossed[regno])
fprintf (dump_file,
";; register %d now crosses calls\n", regno);
+ else if (reg_n_calls_crossed[regno]
+ && ! sched_reg_n_calls_crossed[regno]
+ && reg_basic_block[regno] != REG_BLOCK_GLOBAL)
+ fprintf (dump_file,
+ ";; register %d no longer crosses calls\n", regno);
+
}
/* Negative values are special; don't overwrite the current
reg_live_length value if it is negative. */
if (reg_live_length[regno] >= 0)
reg_live_length[regno] = sched_reg_live_length[regno];
- reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
+
+ /* We can't change the value of reg_n_calls_crossed to zero for
+ pseudos which are live in more than one block.
+
+ This is because combine might have made an optimization which
+ invalidated basic_block_live_at_start and reg_n_calls_crossed,
+ but it does not update them. If we update reg_n_calls_crossed
+ here, the two variables are now inconsistent, and this might
+ confuse the caller-save code into saving a register that doesn't
+ need to be saved. This is only a problem when we zero calls
+ crossed for a pseudo live in multiple basic blocks.
+
+ Alternatively, we could try to correctly update basic block live
+ at start here in sched, but that seems complicated. */
+ if (sched_reg_n_calls_crossed[regno]
+ || reg_basic_block[regno] != REG_BLOCK_GLOBAL)
+ reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
}
}
}