/* Instruction scheduling pass.
- Copyright (C) 1992, 1993, 1994, 1995, 1997 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93-97, 1998 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
broken by
6. choose insn with the least dependences upon the previously
scheduled insn, or finally
- 7. choose insn with lowest UID.
+ 7 choose the insn which has the most insns dependent on it.
+ 8. choose insn with lowest UID.
Memory references complicate matters. Only if we can be certain
that memory references are not part of the data dependency graph
priorities are computed, and (3) block level: insns in the block
are actually scheduled. */
\f
-#include <stdio.h>
#include "config.h"
+#include "system.h"
#include "rtl.h"
#include "basic-block.h"
#include "regs.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
+#include "toplev.h"
extern char *reg_known_equiv_p;
extern rtx *reg_known_value;
#ifdef INSN_SCHEDULING
-/* enable interblock scheduling code */
-
-/* define INTERBLOCK_DEBUG for using the -fsched-max debugging facility */
-/* #define INTERBLOCK_DEBUG */
-
/* 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 examinning the insn list. Since
#define ISSUE_RATE 1
#endif
-/* sched_debug_count is used for debugging the scheduler by limiting
- the number of scheduled insns. It is controlled by the option
- -fsched-max-N (N is a number).
-
- sched-verbose controls the amount of debugging output the
+/* sched-verbose controls the amount of debugging output the
scheduler prints. It is controlled by -fsched-verbose-N:
N>0 and no -DSR : the output is directed to stderr.
N>=10 will direct the printouts to stderr (regardless of -dSR).
N=1: same as -dSR.
N=2: bb's probabilities, detailed ready list info, unit/insn info.
N=3: rtl at abort point, control-flow, regions info.
- N=5: dependences info.
-
- max_rgn_blocks and max_region_insns limit region size for
- interblock scheduling. They are controlled by
- -fsched-interblock-max-blocks-N, -fsched-interblock-max-insns-N */
+ N=5: dependences info. */
#define MAX_RGN_BLOCKS 10
#define MAX_RGN_INSNS 100
-static int sched_debug_count = -1;
static int sched_verbose_param = 0;
static int sched_verbose = 0;
-static int max_rgn_blocks = MAX_RGN_BLOCKS;
-static int max_rgn_insns = MAX_RGN_INSNS;
/* nr_inter/spec counts interblock/speculative motion for the function */
static int nr_inter, nr_spec;
fix_sched_param (param, val)
char *param, *val;
{
- if (!strcmp (param, "max"))
- sched_debug_count = ((sched_debug_count == -1) ?
- atoi (val) : sched_debug_count);
- else if (!strcmp (param, "verbose"))
+ if (!strcmp (param, "verbose"))
sched_verbose_param = atoi (val);
- else if (!strcmp (param, "interblock-max-blocks"))
- max_rgn_blocks = atoi (val);
- else if (!strcmp (param, "interblock-max-insns"))
- max_rgn_insns = atoi (val);
else
warning ("fix_sched_param: unknown param: %s", param);
}
#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
#define BLOCKAGE_RANGE(B) \
(((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
- | (B) & BLOCKAGE_MASK)
+ | ((B) & BLOCKAGE_MASK))
/* Encodings of the `<name>_unit_blockage_range' function. */
#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
The transition (R->S) is implemented in the scheduling loop in
`schedule_block' when the best insn to schedule is chosen.
The transition (R->Q) is implemented in `queue_insn' when an
- insn is found to to have a function unit conflict with the already
+ insn is found to have a function unit conflict with the already
committed insns.
The transitions (P->R and P->Q) are implemented in `schedule_insn' as
insns move from the ready list to the scheduled list.
static void sched_analyze_2 PROTO ((rtx, rtx));
static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
static void sched_analyze PROTO ((rtx, rtx));
-static void sched_note_set PROTO ((int, rtx, int));
-static int rank_for_schedule PROTO ((rtx *, rtx *));
+static void sched_note_set PROTO ((rtx, int));
+static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
static void swap_sort PROTO ((rtx *, int));
static void queue_insn PROTO ((rtx, int));
static int schedule_insn PROTO ((rtx, rtx *, int, int));
static void attach_deaths_insn PROTO ((rtx));
static int new_sometimes_live PROTO ((struct sometimes *, int, int));
static void finish_sometimes_live PROTO ((struct sometimes *, int));
-static int schedule_block PROTO ((int, int, int));
+static int schedule_block PROTO ((int, int));
static rtx regno_use_in PROTO ((int, rtx));
-static void split_hard_reg_notes PROTO ((rtx, rtx, rtx, rtx));
+static void split_hard_reg_notes PROTO ((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));
+static char *safe_concat PROTO ((char *, char *, char *));
/* Main entry point of this file. */
void schedule_insns PROTO ((FILE *));
extern rtx forced_labels;
-static char is_cfg_nonregular PROTO ((void));
-static int uses_reg_or_mem PROTO ((rtx));
-void debug_control_flow PROTO ((void));
-static void build_control_flow PROTO ((void));
-static void build_jmp_edges PROTO ((rtx, int));
+static int is_cfg_nonregular PROTO ((void));
+static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
+ int *, int *));
static void new_edge PROTO ((int, int));
void debug_regions PROTO ((void));
static void find_single_block_region PROTO ((void));
-static void find_rgns PROTO ((void));
+static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
+ int *, int *, sbitmap *));
static int too_large PROTO ((int, int *, int *));
extern void debug_live PROTO ((int, int));
/* speculative scheduling functions */
static int check_live_1 PROTO ((int, rtx));
static void update_live_1 PROTO ((int, rtx));
-static int check_live PROTO ((rtx, int, int));
-static void update_live PROTO ((rtx, int, int));
+static int check_live PROTO ((rtx, int));
+static void update_live PROTO ((rtx, int));
static void set_spec_fed PROTO ((rtx));
static int is_pfree PROTO ((rtx, int, int));
static int find_conditional_protection PROTO ((rtx, int));
static int is_conditionally_protected PROTO ((rtx, int, int));
static int may_trap_exp PROTO ((rtx, int));
-static int classify_insn PROTO ((rtx));
+static int haifa_classify_insn PROTO ((rtx));
+static int is_prisky PROTO ((rtx, int, int));
static int is_exception_free PROTO ((rtx, int, int));
static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
static void find_pre_sched_live PROTO ((int));
static void find_post_sched_live PROTO ((int));
static void update_reg_usage PROTO ((void));
+static int queue_to_ready PROTO ((rtx [], int));
void debug_ready_list PROTO ((rtx[], int));
static void init_target_units PROTO (());
/* Helper functions for instruction scheduling. */
+/* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
+static rtx unused_insn_list;
+
+/* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
+static rtx unused_expr_list;
+
+static void free_list PROTO ((rtx *, rtx *));
+static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
+static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
+
+static void
+free_list (listp, unused_listp)
+ rtx *listp, *unused_listp;
+{
+ register rtx link, prev_link;
+
+ if (*listp == 0)
+ return;
+
+ prev_link = *listp;
+ link = XEXP (prev_link, 1);
+
+ while (link)
+ {
+ prev_link = link;
+ link = XEXP (link, 1);
+ }
+
+ XEXP (prev_link, 1) = *unused_listp;
+ *unused_listp = *listp;
+ *listp = 0;
+}
+
+static rtx
+alloc_INSN_LIST (val, next)
+ rtx val, next;
+{
+ rtx r;
+
+ if (unused_insn_list)
+ {
+ r = unused_insn_list;
+ unused_insn_list = XEXP (r, 1);
+ XEXP (r, 0) = val;
+ XEXP (r, 1) = next;
+ PUT_REG_NOTE_KIND (r, VOIDmode);
+ }
+ else
+ r = gen_rtx_INSN_LIST (VOIDmode, val, next);
+
+ return r;
+}
+
+static rtx
+alloc_EXPR_LIST (kind, val, next)
+ int kind;
+ rtx val, next;
+{
+ rtx r;
+
+ if (unused_insn_list)
+ {
+ r = unused_insn_list;
+ unused_insn_list = XEXP (r, 1);
+ XEXP (r, 0) = val;
+ XEXP (r, 1) = next;
+ PUT_REG_NOTE_KIND (r, kind);
+ }
+ else
+ r = gen_rtx_EXPR_LIST (kind, val, next);
+
+ return r;
+}
+
/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
of dependence that this link represents. */
}
/* Might want to check one level of transitivity to save conses. */
- link = rtx_alloc (INSN_LIST);
+ link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
+ LOG_LINKS (insn) = link;
+
/* Insn dependency, not data dependency. */
PUT_REG_NOTE_KIND (link, dep_type);
- XEXP (link, 0) = elem;
- XEXP (link, 1) = LOG_LINKS (insn);
- LOG_LINKS (insn) = link;
}
/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
rtx insn;
rtx elem;
{
- rtx prev, link;
+ rtx prev, link, next;
int found = 0;
- for (prev = 0, link = LOG_LINKS (insn); link;
- prev = link, link = XEXP (link, 1))
+ for (prev = 0, link = LOG_LINKS (insn); link; link = next)
{
+ next = XEXP (link, 1);
if (XEXP (link, 0) == elem)
{
if (prev)
- XEXP (prev, 1) = XEXP (link, 1);
+ XEXP (prev, 1) = next;
else
- LOG_LINKS (insn) = XEXP (link, 1);
+ LOG_LINKS (insn) = next;
+
+ XEXP (link, 1) = unused_insn_list;
+ unused_insn_list = link;
+
found = 1;
}
+ else
+ prev = link;
}
if (!found)
#define __inline
#endif
+#ifndef HAIFA_INLINE
+#define HAIFA_INLINE __inline
+#endif
+
/* Computation of memory dependencies. */
/* The *_insns and *_mems are paired lists. Each pending memory operation
static int pending_lists_length;
-/* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
-
-static rtx unused_insn_list;
-
-/* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
-
-static rtx unused_expr_list;
-
/* The last insn upon which all memory references must depend.
This is an insn which flushed the pending lists, creating a dependency
between it and all previously pending memory references. This creates
/* functions for construction of the control flow graph. */
/* Return 1 if control flow graph should not be constructed, 0 otherwise.
- Estimate in nr_edges the number of edges on the graph.
+
We decide not to build the control flow graph if there is possibly more
- than one entry to the function, or if computed branches exist. */
+ than one entry to the function, if computed branches exist, of if we
+ have nonlocal gotos. */
-static char
+static int
is_cfg_nonregular ()
{
int b;
rtx insn;
RTX_CODE code;
- rtx nonlocal_label_list = nonlocal_label_rtx_list ();
-
- /* check for non local labels */
- if (nonlocal_label_list)
- {
- return 1;
- }
+ /* If we have a label that could be the target of a nonlocal goto, then
+ the cfg is not well structured. */
+ if (nonlocal_label_rtx_list () != NULL)
+ return 1;
- /* check for labels which cannot be deleted */
+ /* If we have any forced labels, then the cfg is not well structured. */
if (forced_labels)
- {
- return 1;
- }
+ return 1;
- /* check for labels which probably cannot be deleted */
+ /* If this function has a computed jump, then we consider the cfg
+ not well structured. */
+ if (current_function_has_computed_jump)
+ return 1;
+
+ /* If we have exception handlers, then we consider the cfg not well
+ structured. ?!? We should be able to handle this now that flow.c
+ computes an accurate cfg for EH. */
if (exception_handler_labels)
- {
- return 1;
- }
+ return 1;
+ /* If we have non-jumping insns which refer to labels, then we consider
+ the cfg not well structured. */
/* check for labels referred to other thn by jumps */
for (b = 0; b < n_basic_blocks; b++)
for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
- {
- return 1;
- }
+ return 1;
}
if (insn == basic_block_end[b])
break;
}
- nr_edges = 0;
-
- /* check for computed branches */
- for (b = 0; b < n_basic_blocks; b++)
- {
- for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
- {
-
- if (GET_CODE (insn) == JUMP_INSN)
- {
- rtx pat = PATTERN (insn);
- int i;
-
- if (GET_CODE (pat) == PARALLEL)
- {
- int len = XVECLEN (pat, 0);
- int has_use_labelref = 0;
-
- for (i = len - 1; i >= 0; i--)
- if (GET_CODE (XVECEXP (pat, 0, i)) == USE
- && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
- == LABEL_REF))
- {
- nr_edges++;
- has_use_labelref = 1;
- }
-
- if (!has_use_labelref)
- for (i = len - 1; i >= 0; i--)
- if (GET_CODE (XVECEXP (pat, 0, i)) == SET
- && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
- && uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
- {
- return 1;
- }
- }
- /* check for branch table */
- else if (GET_CODE (pat) == ADDR_VEC
- || GET_CODE (pat) == ADDR_DIFF_VEC)
- {
- int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
- int len = XVECLEN (pat, diff_vec_p);
-
- nr_edges += len;
- }
- else
- {
- /* check for computed branch */
- if (GET_CODE (pat) == SET
- && SET_DEST (pat) == pc_rtx
- && uses_reg_or_mem (SET_SRC (pat)))
- {
- return 1;
- }
- }
- }
-
- if (insn == basic_block_end[b])
- break;
- }
- }
-
- /* count for the fallthrough edges */
- for (b = 0; b < n_basic_blocks; b++)
- {
- for (insn = PREV_INSN (basic_block_head[b]);
- insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
- ;
-
- if (!insn && b != 0)
- nr_edges++;
- else if (insn && GET_CODE (insn) != BARRIER)
- nr_edges++;
- }
-
- nr_edges++;
-
+ /* All the tests passed. Consider the cfg well structured. */
return 0;
}
+/* Build the control flow graph and set nr_edges.
-/* Returns 1 if x uses a reg or a mem (function was taken from flow.c).
- x is a target of a jump. Used for the detection of computed
- branches. For each label seen, updates the edges estimation
- counter nr_edges. */
-
-static int
-uses_reg_or_mem (x)
- rtx x;
-{
- enum rtx_code code = GET_CODE (x);
- int i, j;
- char *fmt;
-
- if (code == REG)
- return 1;
-
- if (code == MEM
- && !(GET_CODE (XEXP (x, 0)) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))))
- return 1;
-
- if (code == IF_THEN_ELSE)
- {
- if (uses_reg_or_mem (XEXP (x, 1))
- || uses_reg_or_mem (XEXP (x, 2)))
- return 1;
- else
- return 0;
- }
-
- if (code == LABEL_REF)
- {
- nr_edges++;
-
- return 0;
- }
-
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e'
- && uses_reg_or_mem (XEXP (x, i)))
- return 1;
-
- if (fmt[i] == 'E')
- for (j = 0; j < XVECLEN (x, i); j++)
- if (uses_reg_or_mem (XVECEXP (x, i, j)))
- return 1;
- }
-
- return 0;
-}
-
+ Instead of trying to build a cfg ourselves, we rely on flow to
+ do it for us. Stamp out useless code (and bug) duplication.
-/* Print the control flow graph, for debugging purposes.
- Callable from the debugger. */
+ Return nonzero if an irregularity in the cfg is found which would
+ prevent cross block scheduling. */
-void
-debug_control_flow ()
+static int
+build_control_flow (s_preds, s_succs, num_preds, num_succs)
+ int_list_ptr *s_preds;
+ int_list_ptr *s_succs;
+ int *num_preds;
+ int *num_succs;
{
- int i, e, next;
-
- fprintf (dump, ";; --------- CONTROL FLOW GRAPH --------- \n\n");
+ int i;
+ int_list_ptr succ;
+ int unreachable;
+ /* Count the number of edges in the cfg. */
+ nr_edges = 0;
+ unreachable = 0;
for (i = 0; i < n_basic_blocks; i++)
{
- fprintf (dump, ";;\tBasic block %d: first insn %d, last %d.\n",
- i,
- INSN_UID (basic_block_head[i]),
- INSN_UID (basic_block_end[i]));
-
- fprintf (dump, ";;\tPredecessor blocks:");
- for (e = IN_EDGES (i); e; e = next)
- {
- fprintf (dump, " %d", FROM_BLOCK (e));
+ nr_edges += num_succs[i];
- next = NEXT_IN (e);
-
- if (next == IN_EDGES (i))
- break;
- }
-
- fprintf (dump, "\n;;\tSuccesor blocks:");
- for (e = OUT_EDGES (i); e; e = next)
- {
- fprintf (dump, " %d", TO_BLOCK (e));
-
- next = NEXT_OUT (e);
-
- if (next == OUT_EDGES (i))
- break;
- }
-
- fprintf (dump, " \n\n");
+ /* Unreachable loops with more than one basic block are detected
+ during the DFS traversal in find_rgns.
+ Unreachable loops with a single block are detected here. This
+ test is redundant with the one in find_rgns, but it's much
+ cheaper to go ahead and catch the trivial case here. */
+ if (num_preds[i] == 0
+ || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
+ unreachable = 1;
}
-}
+ /* Account for entry/exit edges. */
+ nr_edges += 2;
-/* build the control flow graph. (also set nr_edges accurately) */
+ in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
+ out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
+ bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
+ bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
-static void
-build_control_flow ()
-{
- int i;
+ edge_table = (edge *) xmalloc ((nr_edges) * sizeof (edge));
+ bzero ((char *) edge_table, ((nr_edges) * sizeof (edge)));
nr_edges = 0;
for (i = 0; i < n_basic_blocks; i++)
- {
- rtx insn;
-
- insn = basic_block_end[i];
- if (GET_CODE (insn) == JUMP_INSN)
- {
- build_jmp_edges (PATTERN (insn), i);
- }
-
- for (insn = PREV_INSN (basic_block_head[i]);
- insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
- ;
-
- /* build fallthrough edges */
- if (!insn && i != 0)
- new_edge (i - 1, i);
- else if (insn && GET_CODE (insn) != BARRIER)
- new_edge (i - 1, i);
- }
+ for (succ = s_succs[i]; succ; succ = succ->next)
+ {
+ if (INT_LIST_VAL (succ) != EXIT_BLOCK)
+ new_edge (i, INT_LIST_VAL (succ));
+ }
/* increment by 1, since edge 0 is unused. */
nr_edges++;
+ return unreachable;
}
-/* construct edges in the control flow graph, from 'source' block, to
- blocks refered to by 'pattern'. */
-
-static
-void
-build_jmp_edges (pattern, source)
- rtx pattern;
- int source;
-{
- register RTX_CODE code;
- register int i;
- register char *fmt;
-
- code = GET_CODE (pattern);
-
- if (code == LABEL_REF)
- {
- register rtx label = XEXP (pattern, 0);
- register int target;
-
- /* This can happen as a result of a syntax error
- and a diagnostic has already been printed. */
- if (INSN_UID (label) == 0)
- return;
-
- target = INSN_BLOCK (label);
- new_edge (source, target);
-
- return;
- }
-
- /* proper handling of ADDR_DIFF_VEC: do not add a non-existing edge
- from the block containing the branch-on-table, to itself. */
- if (code == ADDR_VEC
- || code == ADDR_DIFF_VEC)
- {
- int diff_vec_p = GET_CODE (pattern) == ADDR_DIFF_VEC;
- int len = XVECLEN (pattern, diff_vec_p);
- int k;
-
- for (k = 0; k < len; k++)
- {
- rtx tem = XVECEXP (pattern, diff_vec_p, k);
+/* Record an edge in the control flow graph from SOURCE to TARGET.
- build_jmp_edges (tem, source);
- }
- }
-
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- build_jmp_edges (XEXP (pattern, i), source);
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (pattern, i); j++)
- build_jmp_edges (XVECEXP (pattern, i, j), source);
- }
- }
-}
-
-
-/* construct an edge in the control flow graph, from 'source' to 'target'. */
+ In theory, this is redundant with the s_succs computed above, but
+ we have not converted all of haifa to use information from the
+ integer lists. */
static void
new_edge (source, target)
(*num_bbs)++;
(*num_insns) += (INSN_LUID (basic_block_end[block]) -
INSN_LUID (basic_block_head[block]));
- if ((*num_bbs > max_rgn_blocks) || (*num_insns > max_rgn_insns))
+ if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
return 1;
else
return 0;
if (max_hdr[blk] == -1) \
max_hdr[blk] = hdr; \
else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
- inner[hdr] = 0; \
+ RESET_BIT (inner, hdr); \
else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
{ \
- inner[max_hdr[blk]] = 0; \
+ RESET_BIT (inner,max_hdr[blk]); \
max_hdr[blk] = hdr; \
} \
}
-/* Find regions for interblock scheduling: a loop-free procedure, a reducible
- inner loop, or a basic block not contained in any other region.
- The procedures control flow graph is traversed twice.
- First traversal, a DFS, finds the headers of inner loops in the graph,
- and verifies that there are no unreacable blocks.
- Second traversal processes headers of inner loops, checking that the
- loop is reducible. The loop blocks that form a region are put into the
- region's blocks list in topological order.
+/* Find regions for interblock scheduling.
+
+ A region for scheduling can be:
+
+ * A loop-free procedure, or
+
+ * A reducible inner loop, or
+
+ * A basic block not contained in any other region.
+
- The following variables are changed by the function: rgn_nr, rgn_table,
- rgn_bb_table, block_to_bb and containing_rgn. */
+ ?!? In theory we could build other regions based on extended basic
+ blocks or reverse extended basic blocks. Is it worth the trouble?
+
+ Loop blocks that form a region are put into the region's block list
+ in topological order.
+
+ This procedure stores its results into the following global (ick) variables
+
+ * rgn_nr
+ * rgn_table
+ * rgn_bb_table
+ * block_to_bb
+ * containing region
+
+
+ We use dominator relationships to avoid making regions out of non-reducible
+ loops.
+
+ This procedure needs to be converted to work on pred/succ lists instead
+ of edge tables. That would simplify it somewhat. */
static void
-find_rgns ()
+find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
+ int_list_ptr *s_preds;
+ int_list_ptr *s_succs;
+ int *num_preds;
+ int *num_succs;
+ sbitmap *dom;
{
int *max_hdr, *dfs_nr, *stack, *queue, *degree;
- char *header, *inner, *passed, *in_stack, *in_queue, no_loops = 1;
- int node, child, loop_head, i, j, fst_edge, head, tail;
+ char no_loops = 1;
+ int node, child, loop_head, i, head, tail;
int count = 0, sp, idx = 0, current_edge = out_edges[0];
- int num_bbs, num_insns;
+ int num_bbs, num_insns, unreachable;
int too_large_failure;
- char *reachable;
-
- /*
- The following data structures are computed by the first traversal and
- are used by the second traversal:
- header[i] - flag set if the block i is the header of a loop.
- inner[i] - initially set. It is reset if the the block i is the header
- of a non-inner loop.
- max_hdr[i] - the header of the inner loop containing block i.
- (for a block i not in an inner loop it may be -1 or the
- header of the most inner loop containing the block).
-
- These data structures are used by the first traversal only:
- stack - non-recursive DFS implementation which uses a stack of edges.
- sp - top of the stack of edges
- dfs_nr[i] - the DFS ordering of block i.
- in_stack[i] - flag set if the block i is in the DFS stack.
-
- These data structures are used by the second traversal only:
- queue - queue containing the blocks of the current region.
- head and tail - queue boundaries.
- in_queue[i] - flag set if the block i is in queue */
-
- /* function's inner arrays allocation and initialization */
+
+ /* Note if an edge has been passed. */
+ sbitmap passed;
+
+ /* Note if a block is a natural loop header. */
+ sbitmap header;
+
+ /* Note if a block is an natural inner loop header. */
+ sbitmap inner;
+
+ /* Note if a block is in the block queue. */
+ sbitmap in_queue;
+
+ /* Note if a block is in the block queue. */
+ sbitmap in_stack;
+
+ /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
+ and a mapping from block to its loop header (if the block is contained
+ in a loop, else -1).
+
+ Store results in HEADER, INNER, and MAX_HDR respectively, these will
+ be used as inputs to the second traversal.
+
+ STACK, SP and DFS_NR are only used during the first traversal. */
+
+ /* Allocate and initialize variables for the first traversal. */
max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
stack = (int *) alloca (nr_edges * sizeof (int));
- queue = (int *) alloca (n_basic_blocks * sizeof (int));
- inner = (char *) alloca (n_basic_blocks * sizeof (char));
- header = (char *) alloca (n_basic_blocks * sizeof (char));
- bzero ((char *) header, n_basic_blocks * sizeof (char));
- passed = (char *) alloca (nr_edges * sizeof (char));
- bzero ((char *) passed, nr_edges * sizeof (char));
- in_stack = (char *) alloca (nr_edges * sizeof (char));
- bzero ((char *) in_stack, nr_edges * sizeof (char));
- reachable = (char *) alloca (n_basic_blocks * sizeof (char));
- bzero ((char *) reachable, n_basic_blocks * sizeof (char));
+ inner = sbitmap_alloc (n_basic_blocks);
+ sbitmap_ones (inner);
- in_queue = (char *) alloca (n_basic_blocks * sizeof (char));
+ header = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (header);
+
+ passed = sbitmap_alloc (nr_edges);
+ sbitmap_zero (passed);
+
+ in_queue = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (in_queue);
+
+ in_stack = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (in_stack);
for (i = 0; i < n_basic_blocks; i++)
- {
- inner[i] = 1;
- max_hdr[i] = -1;
- }
+ max_hdr[i] = -1;
- /* First traversal: DFS, finds inner loops in control flow graph */
+ /* DFS traversal to find inner loops in the cfg. */
- reachable[0] = 1;
sp = -1;
while (1)
{
- if (current_edge == 0 || passed[current_edge])
+ if (current_edge == 0 || TEST_BIT (passed, current_edge))
{
- /* Here, if current_edge < 0, this is a leaf block.
- Otherwise current_edge was already passed. Note that in
- the latter case, not only current_edge but also all its
- NEXT_OUT edges are also passed. We have to "climb up on
- edges in the stack", looking for the first (already
- passed) edge whose NEXT_OUT was not passed yet. */
-
- while (sp >= 0 && (current_edge == 0 || passed[current_edge]))
+ /* We have reached a leaf node or a node that was already
+ processed. Pop edges off the stack until we find
+ an edge that has not yet been processed. */
+ while (sp >= 0
+ && (current_edge == 0 || TEST_BIT (passed, current_edge)))
{
+ /* Pop entry off the stack. */
current_edge = stack[sp--];
node = FROM_BLOCK (current_edge);
child = TO_BLOCK (current_edge);
- in_stack[child] = 0;
- if (max_hdr[child] >= 0 && in_stack[max_hdr[child]])
+ RESET_BIT (in_stack, child);
+ if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
current_edge = NEXT_OUT (current_edge);
}
- /* stack empty - the whole graph is traversed. */
- if (sp < 0 && passed[current_edge])
+ /* See if have finished the DFS tree traversal. */
+ if (sp < 0 && TEST_BIT (passed, current_edge))
break;
+
+ /* Nope, continue the traversal with the popped node. */
continue;
}
+ /* Process a node. */
node = FROM_BLOCK (current_edge);
- dfs_nr[node] = ++count;
- in_stack[node] = 1;
child = TO_BLOCK (current_edge);
- reachable[child] = 1;
+ SET_BIT (in_stack, node);
+ dfs_nr[node] = ++count;
- /* found a loop header */
- if (in_stack[child])
+ /* If the successor is in the stack, then we've found a loop.
+ Mark the loop, if it is not a natural loop, then it will
+ be rejected during the second traversal. */
+ if (TEST_BIT (in_stack, child))
{
no_loops = 0;
- header[child] = 1;
- max_hdr[child] = child;
+ SET_BIT (header, child);
UPDATE_LOOP_RELATIONS (node, child);
- passed[current_edge] = 1;
+ SET_BIT (passed, current_edge);
current_edge = NEXT_OUT (current_edge);
continue;
}
- /* the child was already visited once, no need to go down from
- it, everything is traversed there. */
+ /* If the child was already visited, then there is no need to visit
+ it again. Just update the loop relationships and restart
+ with a new edge. */
if (dfs_nr[child])
{
- if (max_hdr[child] >= 0 && in_stack[max_hdr[child]])
+ if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
- passed[current_edge] = 1;
+ SET_BIT (passed, current_edge);
current_edge = NEXT_OUT (current_edge);
continue;
}
- /* this is a step down in the dfs traversal */
+ /* Push an entry on the stack and continue DFS traversal. */
stack[++sp] = current_edge;
- passed[current_edge] = 1;
+ SET_BIT (passed, current_edge);
current_edge = OUT_EDGES (child);
- } /* while (1); */
-
- /* if there are unreachable blocks, or more than one entry to
- the subroutine, give up on interblock scheduling */
- for (i = 1; i < n_basic_blocks; i++)
- {
- if (reachable[i] == 0)
- {
- find_single_block_region ();
- if (sched_verbose >= 3)
- fprintf (stderr, "sched: warning: found an unreachable block %d \n", i);
- return;
- }
}
- /* Second travsersal: find reducible inner loops, and sort
- topologically the blocks of each region */
- degree = dfs_nr; /* reuse dfs_nr array - it is not needed anymore */
- bzero ((char *) in_queue, n_basic_blocks * sizeof (char));
-
- if (no_loops)
- header[0] = 1;
+ /* Another check for unreachable blocks. The earlier test in
+ is_cfg_nonregular only finds unreachable blocks that do not
+ form a loop.
- /* compute the in-degree of every block in the graph */
+ The DFS traversal will mark every block that is reachable from
+ the entry node by placing a nonzero value in dfs_nr. Thus if
+ dfs_nr is zero for any block, then it must be unreachable. */
+ unreachable = 0;
for (i = 0; i < n_basic_blocks; i++)
- {
- fst_edge = IN_EDGES (i);
- if (fst_edge > 0)
- {
- degree[i] = 1;
- current_edge = NEXT_IN (fst_edge);
- while (fst_edge != current_edge)
- {
- ++degree[i];
- current_edge = NEXT_IN (current_edge);
- }
- }
- else
- degree[i] = 0;
- }
+ if (dfs_nr[i] == 0)
+ {
+ unreachable = 1;
+ break;
+ }
- /* pass through all graph blocks, looking for headers of inner loops */
+ /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
+ to hold degree counts. */
+ degree = dfs_nr;
+
+ /* Compute the in-degree of every block in the graph */
for (i = 0; i < n_basic_blocks; i++)
+ degree[i] = num_preds[i];
+
+ /* Do not perform region scheduling if there are any unreachable
+ blocks. */
+ if (!unreachable)
{
+ if (no_loops)
+ SET_BIT (header, 0);
- if (header[i] && inner[i])
- {
+ /* Second travsersal:find reducible inner loops and topologically sort
+ block of each region. */
- /* i is a header of a potentially reducible inner loop, or
- block 0 in a subroutine with no loops at all */
- head = tail = -1;
- too_large_failure = 0;
- loop_head = max_hdr[i];
+ queue = (int *) alloca (n_basic_blocks * sizeof (int));
- /* decrease in_degree of all i's successors, (this is needed
- for the topological ordering) */
- fst_edge = current_edge = OUT_EDGES (i);
- if (fst_edge > 0)
+ /* Find blocks which are inner loop headers. We still have non-reducible
+ loops to consider at this point. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ if (TEST_BIT (header, i) && TEST_BIT (inner, i))
{
- do
+ int_list_ptr ps;
+ int j;
+
+ /* Now check that the loop is reducible. We do this separate
+ from finding inner loops so that we do not find a reducible
+ loop which contains an inner non-reducible loop.
+
+ A simple way to find reducible/natrual loops is to verify
+ that each block in the loop is dominated by the loop
+ header.
+
+ If there exists a block that is not dominated by the loop
+ header, then the block is reachable from outside the loop
+ and thus the loop is not a natural loop. */
+ for (j = 0; j < n_basic_blocks; j++)
{
- --degree[TO_BLOCK (current_edge)];
- current_edge = NEXT_OUT (current_edge);
+ /* First identify blocks in the loop, except for the loop
+ entry block. */
+ if (i == max_hdr[j] && i != j)
+ {
+ /* Now verify that the block is dominated by the loop
+ header. */
+ if (!TEST_BIT (dom[j], i))
+ break;
+ }
}
- while (fst_edge != current_edge);
- }
- /* estimate # insns, and count # blocks in the region. */
- num_bbs = 1;
- num_insns = INSN_LUID (basic_block_end[i]) - INSN_LUID (basic_block_head[i]);
+ /* If we exited the loop early, then I is the header of a non
+ reducible loop and we should quit processing it now. */
+ if (j != n_basic_blocks)
+ continue;
+ /* I is a header of an inner loop, or block 0 in a subroutine
+ with no loops at all. */
+ head = tail = -1;
+ too_large_failure = 0;
+ loop_head = max_hdr[i];
+
+ /* Decrease degree of all I's successors for topological
+ ordering. */
+ for (ps = s_succs[i]; ps; ps = ps->next)
+ if (INT_LIST_VAL (ps) != EXIT_BLOCK
+ && INT_LIST_VAL (ps) != ENTRY_BLOCK)
+ --degree[INT_LIST_VAL(ps)];
+
+ /* Estimate # insns, and count # blocks in the region. */
+ num_bbs = 1;
+ num_insns = (INSN_LUID (basic_block_end[i])
+ - INSN_LUID (basic_block_head[i]));
- /* find all loop latches, if it is a true loop header, or
- all leaves if the graph has no loops at all */
- if (no_loops)
- {
- for (j = 0; j < n_basic_blocks; j++)
- if (out_edges[j] == 0) /* a leaf */
- {
- queue[++tail] = j;
- in_queue[j] = 1;
- if (too_large (j, &num_bbs, &num_insns))
+ /* Find all loop latches (blocks which back edges to the loop
+ header) or all the leaf blocks in the cfg has no loops.
+
+ Place those blocks into the queue. */
+ if (no_loops)
+ {
+ for (j = 0; j < n_basic_blocks; j++)
+ /* Leaf nodes have only a single successor which must
+ be EXIT_BLOCK. */
+ if (num_succs[j] == 1
+ && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
{
- too_large_failure = 1;
- break;
+ queue[++tail] = j;
+ SET_BIT (in_queue, j);
+
+ if (too_large (j, &num_bbs, &num_insns))
+ {
+ too_large_failure = 1;
+ break;
+ }
}
- }
- }
- else
- {
- fst_edge = current_edge = IN_EDGES (i);
- do
+ }
+ else
{
- node = FROM_BLOCK (current_edge);
- if (max_hdr[node] == loop_head && node != i) /* a latch */
+ int_list_ptr ps;
+
+ for (ps = s_preds[i]; ps; ps = ps->next)
{
- queue[++tail] = node;
- in_queue[node] = 1;
+ node = INT_LIST_VAL (ps);
- if (too_large (node, &num_bbs, &num_insns))
+ if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
+ continue;
+
+ if (max_hdr[node] == loop_head && node != i)
{
- too_large_failure = 1;
- break;
+ /* This is a loop latch. */
+ queue[++tail] = node;
+ SET_BIT (in_queue, node);
+
+ if (too_large (node, &num_bbs, &num_insns))
+ {
+ too_large_failure = 1;
+ break;
+ }
}
+
}
- current_edge = NEXT_IN (current_edge);
}
- while (fst_edge != current_edge);
- }
- /* Put in queue[] all blocks that belong to the loop. Check
- that the loop is reducible, traversing back from the loop
- latches up to the loop header. */
- while (head < tail && !too_large_failure)
- {
- child = queue[++head];
- fst_edge = current_edge = IN_EDGES (child);
- do
+ /* Now add all the blocks in the loop to the queue.
+
+ We know the loop is a natural loop; however the algorithm
+ above will not always mark certain blocks as being in the
+ loop. Consider:
+ node children
+ a b,c
+ b c
+ c a,d
+ d b
+
+
+ The algorithm in the DFS traversal may not mark B & D as part
+ of the loop (ie they will not have max_hdr set to A).
+
+ We know they can not be loop latches (else they would have
+ had max_hdr set since they'd have a backedge to a dominator
+ block). So we don't need them on the initial queue.
+
+ We know they are part of the loop because they are dominated
+ by the loop header and can be reached by a backwards walk of
+ the edges starting with nodes on the initial queue.
+
+ It is safe and desirable to include those nodes in the
+ loop/scheduling region. To do so we would need to decrease
+ the degree of a node if it is the target of a backedge
+ within the loop itself as the node is placed in the queue.
+
+ We do not do this because I'm not sure that the actual
+ scheduling code will properly handle this case. ?!? */
+
+ while (head < tail && !too_large_failure)
{
- node = FROM_BLOCK (current_edge);
+ int_list_ptr ps;
+ child = queue[++head];
- if (max_hdr[node] != loop_head)
- { /* another entry to loop, it is irreducible */
- tail = -1;
- break;
- }
- else if (!in_queue[node] && node != i)
+ for (ps = s_preds[child]; ps; ps = ps->next)
{
- queue[++tail] = node;
- in_queue[node] = 1;
+ node = INT_LIST_VAL (ps);
- if (too_large (node, &num_bbs, &num_insns))
+ /* See discussion above about nodes not marked as in
+ this loop during the initial DFS traversal. */
+ if (node == ENTRY_BLOCK || node == EXIT_BLOCK
+ || max_hdr[node] != loop_head)
{
- too_large_failure = 1;
+ tail = -1;
break;
}
+ else if (!TEST_BIT (in_queue, node) && node != i)
+ {
+ queue[++tail] = node;
+ SET_BIT (in_queue, node);
+
+ if (too_large (node, &num_bbs, &num_insns))
+ {
+ too_large_failure = 1;
+ break;
+ }
+ }
}
- current_edge = NEXT_IN (current_edge);
}
- while (fst_edge != current_edge);
- }
- if (tail >= 0 && !too_large_failure)
- {
- /* Place the loop header into list of region blocks */
- degree[i] = -1;
- rgn_bb_table[idx] = i;
- RGN_NR_BLOCKS (nr_regions) = num_bbs;
- RGN_BLOCKS (nr_regions) = idx++;
- CONTAINING_RGN (i) = nr_regions;
- BLOCK_TO_BB (i) = count = 0;
-
- /* remove blocks from queue[], (in topological order), when
- their in_degree becomes 0. We scan the queue over and
- over again until it is empty. Note: there may be a more
- efficient way to do it. */
- while (tail >= 0)
+ if (tail >= 0 && !too_large_failure)
{
- if (head < 0)
- head = tail;
- child = queue[head];
- if (degree[child] == 0)
+ /* Place the loop header into list of region blocks. */
+ degree[i] = -1;
+ rgn_bb_table[idx] = i;
+ RGN_NR_BLOCKS (nr_regions) = num_bbs;
+ RGN_BLOCKS (nr_regions) = idx++;
+ CONTAINING_RGN (i) = nr_regions;
+ BLOCK_TO_BB (i) = count = 0;
+
+ /* Remove blocks from queue[] when their in degree becomes
+ zero. Repeat until no blocks are left on the list. This
+ produces a topological list of blocks in the region. */
+ while (tail >= 0)
{
- degree[child] = -1;
- rgn_bb_table[idx++] = child;
- BLOCK_TO_BB (child) = ++count;
- CONTAINING_RGN (child) = nr_regions;
- queue[head] = queue[tail--];
- fst_edge = current_edge = OUT_EDGES (child);
-
- if (fst_edge > 0)
+ int_list_ptr ps;
+
+ if (head < 0)
+ head = tail;
+ child = queue[head];
+ if (degree[child] == 0)
{
- do
- {
- --degree[TO_BLOCK (current_edge)];
- current_edge = NEXT_OUT (current_edge);
- }
- while (fst_edge != current_edge);
+ degree[child] = -1;
+ rgn_bb_table[idx++] = child;
+ BLOCK_TO_BB (child) = ++count;
+ CONTAINING_RGN (child) = nr_regions;
+ queue[head] = queue[tail--];
+
+ for (ps = s_succs[child]; ps; ps = ps->next)
+ if (INT_LIST_VAL (ps) != ENTRY_BLOCK
+ && INT_LIST_VAL (ps) != EXIT_BLOCK)
+ --degree[INT_LIST_VAL (ps)];
}
+ else
+ --head;
}
- else
- --head;
+ ++nr_regions;
}
- ++nr_regions;
}
}
}
- /* define each of all other blocks as a region itself */
+ /* Any block that did not end up in a region is placed into a region
+ by itself. */
for (i = 0; i < n_basic_blocks; i++)
if (degree[i] >= 0)
{
BLOCK_TO_BB (i) = 0;
}
-} /* find_rgns */
+ free (passed);
+ free (header);
+ free (inner);
+ free (in_queue);
+ free (in_stack);
+}
/* functions for regions scheduling information */
int src;
rtx x;
{
- register i;
+ register int i;
register int regno;
register rtx reg = SET_DEST (x);
int src;
rtx x;
{
- register i;
+ register int i;
register int regno;
register rtx reg = SET_DEST (x);
ready-list or before the scheduling. */
static int
-check_live (insn, src, trg)
+check_live (insn, src)
rtx insn;
int src;
- int trg;
{
/* find the registers set by instruction */
if (GET_CODE (PATTERN (insn)) == SET
block src to trg. */
static void
-update_live (insn, src, trg)
+update_live (insn, src)
rtx insn;
- int src, trg;
+ int src;
{
/* find the registers set by instruction */
if (GET_CODE (PATTERN (insn)) == SET
if (GET_MODE (fore_link) == VOIDmode)
{
/* found a DEF-USE dependence (insn1, insn2) */
- if (classify_insn (insn2) != PFREE_CANDIDATE)
+ if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
/* insn2 not guaranteed to be a 1 base reg load */
continue;
being either PFREE or PRISKY. */
static int
-classify_insn (insn)
+haifa_classify_insn (insn)
rtx insn;
{
rtx pat = PATTERN (insn);
return insn_class;
-} /* classify_insn */
+} /* haifa_classify_insn */
/* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
a load moved speculatively, or if load_insn is protected by
rtx insn;
int bb_src, bb_trg;
{
- int insn_class = classify_insn (insn);
+ int insn_class = haifa_classify_insn (insn);
/* handle non-load insns */
switch (insn_class)
/* Return the INSN_LIST containing INSN in LIST, or NULL
if LIST does not contain INSN. */
-__inline static rtx
+HAIFA_INLINE static rtx
find_insn_list (insn, list)
rtx insn;
rtx list;
/* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
-__inline static char
+HAIFA_INLINE static char
find_insn_mem_list (insn, x, list, list1)
rtx insn, x;
rtx list, list1;
mask if the value is negative. A function unit index is the
non-negative encoding. */
-__inline static int
+HAIFA_INLINE static int
insn_unit (insn)
rtx insn;
{
These values are encoded in an int where the upper half gives the
minimum value and the lower half gives the maximum value. */
-__inline static unsigned int
+HAIFA_INLINE static unsigned int
blockage_range (unit, insn)
int unit;
rtx insn;
/* Return the issue-delay of an insn */
-__inline static int
+HAIFA_INLINE static int
insn_issue_delay (insn)
rtx insn;
{
- rtx link;
int i, delay = 0;
int unit = insn_unit (insn);
instance INSTANCE at time CLOCK if the previous actual hazard cost
was COST. */
-__inline static int
+HAIFA_INLINE static int
actual_hazard_this_instance (unit, instance, insn, clock, cost)
int unit, instance, clock, cost;
rtx insn;
/* Record INSN as having begun execution on the units encoded by UNIT at
time CLOCK. */
-__inline static void
+HAIFA_INLINE static void
schedule_unit (unit, insn, clock)
int unit, clock;
rtx insn;
/* Return the actual hazard cost of executing INSN on the units encoded by
UNIT at time CLOCK if the previous actual hazard cost was COST. */
-__inline static int
+HAIFA_INLINE static int
actual_hazard (unit, insn, clock, cost)
int unit, clock, cost;
rtx insn;
to be used is chosen in preference to one with a unit that is less
used. We are trying to minimize a subsequent actual hazard. */
-__inline static int
+HAIFA_INLINE static int
potential_hazard (unit, insn, cost)
int unit, cost;
rtx insn;
This is the number of cycles between instruction issue and
instruction results. */
-__inline static int
+HAIFA_INLINE static int
insn_cost (insn, link, used)
rtx insn, link, used;
{
rtx next;
int next_priority;
+ if (RTX_INTEGRATED_P (link))
+ continue;
+
next = XEXP (link, 0);
/* critical path is meaningful in block boundaries only */
/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
them to the unused_*_list variables, so that they can be reused. */
-__inline static void
-free_pnd_lst (listp, unused_listp)
- rtx *listp, *unused_listp;
-{
- register rtx link, prev_link;
-
- if (*listp == 0)
- return;
-
- prev_link = *listp;
- link = XEXP (prev_link, 1);
-
- while (link)
- {
- prev_link = link;
- link = XEXP (link, 1);
- }
-
- XEXP (prev_link, 1) = *unused_listp;
- *unused_listp = *listp;
- *listp = 0;
-}
-
static void
free_pending_lists ()
{
-
-
if (current_nr_blocks <= 1)
{
- free_pnd_lst (&pending_read_insns, &unused_insn_list);
- free_pnd_lst (&pending_write_insns, &unused_insn_list);
- free_pnd_lst (&pending_read_mems, &unused_expr_list);
- free_pnd_lst (&pending_write_mems, &unused_expr_list);
+ free_list (&pending_read_insns, &unused_insn_list);
+ free_list (&pending_write_insns, &unused_insn_list);
+ free_list (&pending_read_mems, &unused_expr_list);
+ free_list (&pending_write_mems, &unused_expr_list);
}
else
{
for (bb = 0; bb < current_nr_blocks; bb++)
{
- free_pnd_lst (&bb_pending_read_insns[bb], &unused_insn_list);
- free_pnd_lst (&bb_pending_write_insns[bb], &unused_insn_list);
- free_pnd_lst (&bb_pending_read_mems[bb], &unused_expr_list);
- free_pnd_lst (&bb_pending_write_mems[bb], &unused_expr_list);
+ free_list (&bb_pending_read_insns[bb], &unused_insn_list);
+ free_list (&bb_pending_write_insns[bb], &unused_insn_list);
+ free_list (&bb_pending_read_mems[bb], &unused_expr_list);
+ free_list (&bb_pending_write_mems[bb], &unused_expr_list);
}
}
}
{
register rtx link;
- if (unused_insn_list)
- {
- link = unused_insn_list;
- unused_insn_list = XEXP (link, 1);
- }
- else
- link = rtx_alloc (INSN_LIST);
- XEXP (link, 0) = insn;
- XEXP (link, 1) = *insn_list;
+ link = alloc_INSN_LIST (insn, *insn_list);
*insn_list = link;
- if (unused_expr_list)
- {
- link = unused_expr_list;
- unused_expr_list = XEXP (link, 1);
- }
- else
- link = rtx_alloc (EXPR_LIST);
- XEXP (link, 0) = mem;
- XEXP (link, 1) = *mem_list;
+ link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
*mem_list = link;
pending_lists_length++;
for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- last_pending_memory_flush =
- gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
+ free_list (&last_pending_memory_flush, &unused_insn_list);
+ last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
}
/* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
while (--i >= 0)
{
reg_last_uses[regno + i]
- = gen_rtx (INSN_LIST, VOIDmode,
- insn, reg_last_uses[regno + i]);
+ = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
}
else
{
- reg_last_uses[regno]
- = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
+ reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
sched_analyze_2 (XEXP (x, 0), insn);
sched_analyze_1 (x, insn);
return;
+
+ default:
+ break;
}
/* Other cases: walk the insn. */
EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
{
/* reg_last_sets[r] is now a list of insns */
+ free_list (®_last_sets[i], &unused_insn_list);
reg_last_sets[i]
- = gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
+ = alloc_INSN_LIST (insn, NULL_RTX);
});
CLEAR_REG_SET (reg_pending_sets);
if (reg_pending_sets_all)
{
for (i = 0; i < maxreg; i++)
-
- /* reg_last_sets[r] is now a list of insns */
- reg_last_sets[i]
- = gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
+ {
+ /* reg_last_sets[r] is now a list of insns */
+ free_list (®_last_sets[i], &unused_insn_list);
+ reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
+ }
reg_pending_sets_all = 0;
}
/* Add a pair of fake REG_NOTE which we will later
convert back into a NOTE_INSN_SETJMP note. See
reemit_notes for why we use a pair 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));
+ REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
+ GEN_INT (0),
+ REG_NOTES (insn));
+ REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
+ GEN_INT (NOTE_INSN_SETJMP),
+ REG_NOTES (insn));
}
else
{
function call) on all hard register clobberage. */
/* last_function_call is now a list of insns */
- last_function_call
- = gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
+ free_list(&last_function_call, &unused_insn_list);
+ last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
}
/* See comments on reemit_notes as to why we do this. */
|| 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_RANGE_START
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_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);
+ loop_notes = alloc_EXPR_LIST (REG_DEAD,
+ GEN_INT (NOTE_BLOCK_NUMBER (insn)),
+ loop_notes);
+ loop_notes = alloc_EXPR_LIST (REG_DEAD,
+ GEN_INT (NOTE_LINE_NUMBER (insn)),
+ loop_notes);
CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
}
are scanning forwards. Mark that register as being born. */
static void
-sched_note_set (b, x, death)
- int b;
+sched_note_set (x, death)
rtx x;
int death;
{
static int
rank_for_schedule (x, y)
- rtx *x, *y;
+ const GENERIC_PTR x;
+ const GENERIC_PTR y;
{
- rtx tmp = *y;
- rtx tmp2 = *x;
+ rtx tmp = *(rtx *)y;
+ rtx tmp2 = *(rtx *)x;
rtx link;
- int tmp_class, tmp2_class;
+ int tmp_class, tmp2_class, depend_count1, depend_count2;
int val, priority_val, spec_val, prob_val, weight_val;
- /* schedule reverse is a stress test of the scheduler correctness,
- controlled by -fsched-reverse option. */
- if ((reload_completed && flag_schedule_reverse_after_reload) ||
- (!reload_completed && flag_schedule_reverse_before_reload))
- return INSN_LUID (tmp2) - INSN_LUID (tmp);
-
/* prefer insn with higher priority */
priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
if (priority_val)
return val;
}
+ /* Prefer the insn which has more later insns that depend on it.
+ This gives the scheduler more freedom when scheduling later
+ instructions at the expense of added register pressure. */
+ depend_count1 = 0;
+ for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
+ depend_count1++;
+
+ depend_count2 = 0;
+ for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
+ depend_count2++;
+
+ val = depend_count2 - depend_count1;
+ if (val)
+ return val;
+
/* If insns are equally good, sort by INSN_LUID (original insn order),
so that we make the sort stable. This minimizes instruction movement,
thus minimizing sched's effect on debugging and cross-jumping. */
/* Resort the array A in which only element at index N may be out of order. */
-__inline static void
+HAIFA_INLINE static void
swap_sort (a, n)
rtx *a;
int n;
N_CYCLES after the currently executing insn. Preserve insns
chain for debugging purposes. */
-__inline static void
+HAIFA_INLINE static void
queue_insn (insn, n_cycles)
rtx insn;
int n_cycles;
{
int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
- rtx link = rtx_alloc (INSN_LIST);
- XEXP (link, 0) = insn;
- XEXP (link, 1) = insn_queue[next_q];
+ rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
insn_queue[next_q] = link;
q_size += 1;
/* Return nonzero if PAT is the pattern of an insn which makes a
register live. */
-__inline static int
+HAIFA_INLINE static int
birthing_insn_p (pat)
rtx pat;
{
/* PREV is an insn that is ready to execute. Adjust its priority if that
will help shorten register lifetimes. */
-__inline static void
+HAIFA_INLINE static void
adjust_priority (prev)
rtx prev;
{
|| CANT_MOVE (next)
|| (IS_SPECULATIVE_INSN (next)
&& (insn_issue_delay (next) > 3
- || !check_live (next, INSN_BB (next), target_bb)
+ || !check_live (next, INSN_BB (next))
|| !is_exception_free (next, INSN_BB (next), target_bb)))))
continue;
if (current_nr_blocks <= 1)
abort ();
else
- {
- link = rtx_alloc (EXPR_LIST);
- PUT_REG_NOTE_KIND (link, REG_DEAD);
- }
+ link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
}
else
{
while (reg_note_regs < regs_killed)
{
link = XEXP (link, 1);
+
+ /* LINK might be zero if we killed more registers after scheduling
+ than before, and the last hard register we kill is actually
+ multiple hard regs.
+
+ This is normal for interblock scheduling, so deal with it in
+ that case, else abort. */
+ if (link == NULL_RTX && current_nr_blocks <= 1)
+ abort ();
+ else if (link == NULL_RTX)
+ link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
+ NULL_RTX);
+
reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
: HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
GET_MODE (XEXP (link, 0))));
{
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;
+ temp_reg = gen_rtx_REG (word_mode, 0);
+ temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
dead_notes = temp_link;
reg_note_regs--;
}
#endif
&& regno != STACK_POINTER_REGNUM)
{
- /* ??? 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))
+ if (! all_needed && ! dead_or_set_p (insn, x))
{
/* Check for the case where the register dying partially
overlaps the register set by this insn. */
i >= 0; i--)
if (! REGNO_REG_SET_P (old_live_regs, regno+i)
&& ! dead_or_set_regno_p (insn, regno + i))
- create_reg_dead_note (gen_rtx (REG,
- reg_raw_mode[regno + i],
- regno + i),
+ create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
+ regno + i),
insn);
}
}
return;
case SUBREG:
+ attach_deaths (SUBREG_REG (x), insn,
+ set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
+ <= UNITS_PER_WORD)
+ || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
+ == GET_MODE_SIZE (GET_MODE ((x))))));
+ return;
+
case STRICT_LOW_PART:
- /* These two cases preserve the value of SET_P, so handle them
- separately. */
- attach_deaths (XEXP (x, 0), insn, set_p);
+ attach_deaths (XEXP (x, 0), insn, 0);
return;
case ZERO_EXTRACT:
case SIGN_EXTRACT:
- /* This case preserves the value of SET_P for the first operand, but
- clears it for the other two. */
- attach_deaths (XEXP (x, 0), insn, set_p);
+ attach_deaths (XEXP (x, 0), insn, 0);
attach_deaths (XEXP (x, 1), insn, 0);
attach_deaths (XEXP (x, 2), insn, 0);
return;
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_RANGE_START
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
{
/* Return the head and tail pointers of BB. */
-__inline static void
+HAIFA_INLINE static void
get_block_head_tail (bb, headp, tailp)
int bb;
rtx *headp;
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
{
- sched_note_set (b, PATTERN (insn), 0);
+ sched_note_set (PATTERN (insn), 0);
reg_weight++;
}
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
{
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
reg_weight++;
}
is harmless though, so we will leave it in for now. */
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
}
/* Each call cobbers (makes live) all call-clobbered regs
next_tail = NEXT_INSN (tail);
prev_head = PREV_INSN (head);
- for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
- if (REGNO_REG_SET_P (bb_live_regs, i))
- sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
+ EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
+ {
+ sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
+ });
/* if the block is empty, same regs are alive at its end and its start.
since this is not guaranteed after interblock scheduling, make sure they
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
- sched_note_set (b, PATTERN (insn), 1);
+ sched_note_set (PATTERN (insn), 1);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
}
/* This code keeps life analysis information up to date. */
int regno;
if (n_basic_blocks > 0)
- for (regno = FIRST_PSEUDO_REGISTER; regno < max_regno; regno++)
- if (REGNO_REG_SET_P (basic_block_live_at_start[0], regno))
- sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
+ EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
+ {
+ sched_reg_basic_block[regno]
+ = REG_BLOCK_GLOBAL;
+ });
for (regno = 0; regno < max_regno; regno++)
if (sched_reg_live_length[regno])
#define BUF_LEN 256
+static char *
+safe_concat (buf, cur, str)
+ char *buf;
+ char *cur;
+ char *str;
+{
+ char *end = buf + BUF_LEN - 2; /* leave room for null */
+ int c;
+
+ if (cur > end)
+ {
+ *end = '\0';
+ return end;
+ }
+
+ while (cur < end && (c = *str++) != '\0')
+ *cur++ = c;
+
+ *cur = '\0';
+ return cur;
+}
+
/* This recognizes rtx, I classified as expressions. These are always */
/* represent some action on values or results of other expression, */
/* that may be stored in objects representing values. */
rtx x;
int verbose;
{
- char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
+ char tmp[BUF_LEN];
+ char *st[4];
+ char *cur = buf;
+ char *fun = (char *)0;
+ char *sep;
+ rtx op[4];
+ int i;
+
+ for (i = 0; i < 4; i++)
+ {
+ st[i] = (char *)0;
+ op[i] = NULL_RTX;
+ }
switch (GET_CODE (x))
{
case PLUS:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s+%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "+";
+ op[1] = XEXP (x, 1);
break;
case LO_SUM:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%sl+%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "+low(";
+ op[1] = XEXP (x, 1);
+ st[2] = ")";
break;
case MINUS:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s-%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "-";
+ op[1] = XEXP (x, 1);
break;
case COMPARE:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s??%s", t1, t2);
+ fun = "cmp";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case NEG:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "-%s", t1);
+ st[0] = "-";
+ op[0] = XEXP (x, 0);
break;
case MULT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s*%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "*";
+ op[1] = XEXP (x, 1);
break;
case DIV:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s/%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "/";
+ op[1] = XEXP (x, 1);
break;
case UDIV:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%su/%s", t1, t2);
+ fun = "udiv";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case MOD:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s%%%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "%";
+ op[1] = XEXP (x, 1);
break;
case UMOD:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%su%%%s", t1, t2);
+ fun = "umod";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case SMIN:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "smin (%s, %s)", t1, t2);
+ fun = "smin";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case SMAX:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "smax(%s,%s)", t1, t2);
+ fun = "smax";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case UMIN:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "umin (%s, %s)", t1, t2);
+ fun = "umin";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case UMAX:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "umax(%s,%s)", t1, t2);
+ fun = "umax";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case NOT:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "!%s", t1);
+ st[0] = "!";
+ op[0] = XEXP (x, 0);
break;
case AND:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s&%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "&";
+ op[1] = XEXP (x, 1);
break;
case IOR:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s|%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "|";
+ op[1] = XEXP (x, 1);
break;
case XOR:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s^%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "^";
+ op[1] = XEXP (x, 1);
break;
case ASHIFT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s<<%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "<<";
+ op[1] = XEXP (x, 1);
break;
case LSHIFTRT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s0>%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = " 0>>";
+ op[1] = XEXP (x, 1);
break;
case ASHIFTRT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s>>%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = ">>";
+ op[1] = XEXP (x, 1);
break;
case ROTATE:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s<-<%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "<-<";
+ op[1] = XEXP (x, 1);
break;
case ROTATERT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s>->%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = ">->";
+ op[1] = XEXP (x, 1);
break;
case ABS:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "abs(%s)", t1);
+ fun = "abs";
+ op[0] = XEXP (x, 0);
break;
case SQRT:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "sqrt(%s)", t1);
+ fun = "sqrt";
+ op[0] = XEXP (x, 0);
break;
case FFS:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "ffs(%s)", t1);
+ fun = "ffs";
+ op[0] = XEXP (x, 0);
break;
case EQ:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s == %s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "==";
+ op[1] = XEXP (x, 1);
break;
case NE:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s!=%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "!=";
+ op[1] = XEXP (x, 1);
break;
case GT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s>%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = ">";
+ op[1] = XEXP (x, 1);
break;
case GTU:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s>u%s", t1, t2);
+ fun = "gtu";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case LT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s<%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "<";
+ op[1] = XEXP (x, 1);
break;
case LTU:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s<u%s", t1, t2);
+ fun = "ltu";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case GE:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s>=%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = ">=";
+ op[1] = XEXP (x, 1);
break;
case GEU:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s>=u%s", t1, t2);
+ fun = "geu";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case LE:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s<=%s", t1, t2);
+ op[0] = XEXP (x, 0);
+ st[1] = "<=";
+ op[1] = XEXP (x, 1);
break;
case LEU:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "%s<=u%s", t1, t2);
+ fun = "leu";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
break;
case SIGN_EXTRACT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- print_value (t3, XEXP (x, 2), verbose);
- if (verbose)
- sprintf (buf, "sign_extract(%s,%s,%s)", t1, t2, t3);
- else
- sprintf (buf, "sxt(%s,%s,%s)", t1, t2, t3);
+ fun = (verbose) ? "sign_extract" : "sxt";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
+ op[2] = XEXP (x, 2);
break;
case ZERO_EXTRACT:
- print_value (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- print_value (t3, XEXP (x, 2), verbose);
- if (verbose)
- sprintf (buf, "zero_extract(%s,%s,%s)", t1, t2, t3);
- else
- sprintf (buf, "zxt(%s,%s,%s)", t1, t2, t3);
+ fun = (verbose) ? "zero_extract" : "zxt";
+ op[0] = XEXP (x, 0);
+ op[1] = XEXP (x, 1);
+ op[2] = XEXP (x, 2);
break;
case SIGN_EXTEND:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "sign_extend(%s)", t1);
- else
- sprintf (buf, "sxn(%s)", t1);
+ fun = (verbose) ? "sign_extend" : "sxn";
+ op[0] = XEXP (x, 0);
break;
case ZERO_EXTEND:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "zero_extend(%s)", t1);
- else
- sprintf (buf, "zxn(%s)", t1);
+ fun = (verbose) ? "zero_extend" : "zxn";
+ op[0] = XEXP (x, 0);
break;
case FLOAT_EXTEND:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "float_extend(%s)", t1);
- else
- sprintf (buf, "fxn(%s)", t1);
+ fun = (verbose) ? "float_extend" : "fxn";
+ op[0] = XEXP (x, 0);
break;
case TRUNCATE:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "trunc(%s)", t1);
- else
- sprintf (buf, "trn(%s)", t1);
+ fun = (verbose) ? "trunc" : "trn";
+ op[0] = XEXP (x, 0);
break;
case FLOAT_TRUNCATE:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "float_trunc(%s)", t1);
- else
- sprintf (buf, "ftr(%s)", t1);
+ fun = (verbose) ? "float_trunc" : "ftr";
+ op[0] = XEXP (x, 0);
break;
case FLOAT:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "float(%s)", t1);
- else
- sprintf (buf, "flt(%s)", t1);
+ fun = (verbose) ? "float" : "flt";
+ op[0] = XEXP (x, 0);
break;
case UNSIGNED_FLOAT:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "uns_float(%s)", t1);
- else
- sprintf (buf, "ufl(%s)", t1);
+ fun = (verbose) ? "uns_float" : "ufl";
+ op[0] = XEXP (x, 0);
break;
case FIX:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "fix(%s)", t1);
+ fun = "fix";
+ op[0] = XEXP (x, 0);
break;
case UNSIGNED_FIX:
- print_value (t1, XEXP (x, 0), verbose);
- if (verbose)
- sprintf (buf, "uns_fix(%s)", t1);
- else
- sprintf (buf, "ufx(%s)", t1);
+ fun = (verbose) ? "uns_fix" : "ufx";
+ op[0] = XEXP (x, 0);
break;
case PRE_DEC:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "--%s", t1);
+ st[0] = "--";
+ op[0] = XEXP (x, 0);
break;
case PRE_INC:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "++%s", t1);
+ st[0] = "++";
+ op[0] = XEXP (x, 0);
break;
case POST_DEC:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "%s--", t1);
+ op[0] = XEXP (x, 0);
+ st[1] = "--";
break;
case POST_INC:
- print_value (t1, XEXP (x, 0), verbose);
- sprintf (buf, "%s++", t1);
+ op[0] = XEXP (x, 0);
+ st[1] = "++";
break;
case CALL:
- print_value (t1, XEXP (x, 0), verbose);
+ st[0] = "call ";
+ op[0] = XEXP (x, 0);
if (verbose)
{
- print_value (t2, XEXP (x, 1), verbose);
- sprintf (buf, "call %s argc:%s", t1, t2);
+ st[1] = " argc:";
+ op[1] = XEXP (x, 1);
}
- else
- sprintf (buf, "call %s", t1);
break;
case IF_THEN_ELSE:
- print_exp (t1, XEXP (x, 0), verbose);
- print_value (t2, XEXP (x, 1), verbose);
- print_value (t3, XEXP (x, 2), verbose);
- sprintf (buf, "{(%s)?%s:%s}", t1, t2, t3);
+ st[0] = "{(";
+ op[0] = XEXP (x, 0);
+ st[1] = ")?";
+ op[1] = XEXP (x, 1);
+ st[2] = ":";
+ op[2] = XEXP (x, 2);
+ st[3] = "}";
break;
case TRAP_IF:
- print_value (t1, TRAP_CONDITION (x), verbose);
- sprintf (buf, "trap_if %s", t1);
+ fun = "trap_if";
+ op[0] = TRAP_CONDITION (x);
break;
case UNSPEC:
- {
- int i;
-
- sprintf (t1, "unspec{");
- for (i = 0; i < XVECLEN (x, 0); i++)
- {
- print_pattern (t2, XVECEXP (x, 0, i), verbose);
- sprintf (t3, "%s%s;", t1, t2);
- strcpy (t1, t3);
- }
- sprintf (buf, "%s}", t1);
- }
- break;
case UNSPEC_VOLATILE:
{
- int i;
-
- sprintf (t1, "unspec/v{");
+ cur = safe_concat (buf, cur, "unspec");
+ if (GET_CODE (x) == UNSPEC_VOLATILE)
+ cur = safe_concat (buf, cur, "/v");
+ cur = safe_concat (buf, cur, "[");
+ sep = "";
for (i = 0; i < XVECLEN (x, 0); i++)
{
- print_pattern (t2, XVECEXP (x, 0, i), verbose);
- sprintf (t3, "%s%s;", t1, t2);
- strcpy (t1, t3);
+ print_pattern (tmp, XVECEXP (x, 0, i), verbose);
+ cur = safe_concat (buf, cur, sep);
+ cur = safe_concat (buf, cur, tmp);
+ sep = ",";
}
- sprintf (buf, "%s}", t1);
+ cur = safe_concat (buf, cur, "] ");
+ sprintf (tmp, "%d", XINT (x, 1));
+ cur = safe_concat (buf, cur, tmp);
}
break;
default:
-/* if (verbose) debug_rtx (x); else sprintf (buf, "$$$"); */
- sprintf (buf, "$$$");
+ /* if (verbose) debug_rtx (x); */
+ st[0] = GET_RTX_NAME (GET_CODE (x));
+ break;
+ }
+
+ /* Print this as a function? */
+ if (fun)
+ {
+ cur = safe_concat (buf, cur, fun);
+ cur = safe_concat (buf, cur, "(");
}
-} /* print_exp */
+
+ for (i = 0; i < 4; i++)
+ {
+ if (st[i])
+ cur = safe_concat (buf, cur, st[i]);
+
+ if (op[i])
+ {
+ if (fun && i != 0)
+ cur = safe_concat (buf, cur, ",");
+
+ print_value (tmp, op[i], verbose);
+ cur = safe_concat (buf, cur, tmp);
+ }
+ }
+
+ if (fun)
+ cur = safe_concat (buf, cur, ")");
+} /* print_exp */
/* Prints rtxes, i customly classified as values. They're constants, */
/* registers, labels, symbols and memory accesses. */
int verbose;
{
char t[BUF_LEN];
+ char *cur = buf;
switch (GET_CODE (x))
{
case CONST_INT:
- sprintf (buf, "%Xh", INTVAL (x));
+ sprintf (t, "0x%lx", (long)INTVAL (x));
+ cur = safe_concat (buf, cur, t);
break;
case CONST_DOUBLE:
- print_value (t, XEXP (x, 0), verbose);
- sprintf (buf, "<%s>", t);
+ sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
+ cur = safe_concat (buf, cur, t);
break;
case CONST_STRING:
- sprintf (buf, "\"%s\"", (char *) XEXP (x, 0));
+ cur = safe_concat (buf, cur, "\"");
+ cur = safe_concat (buf, cur, XSTR (x, 0));
+ cur = safe_concat (buf, cur, "\"");
break;
case SYMBOL_REF:
- sprintf (buf, "`%s'", (char *) XEXP (x, 0));
+ cur = safe_concat (buf, cur, "`");
+ cur = safe_concat (buf, cur, XSTR (x, 0));
+ cur = safe_concat (buf, cur, "'");
break;
case LABEL_REF:
- sprintf (buf, "L%d", INSN_UID (XEXP (x, 0)));
+ sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
+ cur = safe_concat (buf, cur, t);
break;
case CONST:
- print_value (buf, XEXP (x, 0), verbose);
+ print_value (t, XEXP (x, 0), verbose);
+ cur = safe_concat (buf, cur, "const(");
+ cur = safe_concat (buf, cur, t);
+ cur = safe_concat (buf, cur, ")");
break;
case HIGH:
- print_value (buf, XEXP (x, 0), verbose);
+ print_value (t, XEXP (x, 0), verbose);
+ cur = safe_concat (buf, cur, "high(");
+ cur = safe_concat (buf, cur, t);
+ cur = safe_concat (buf, cur, ")");
break;
case REG:
- if (GET_MODE (x) == SFmode
- || GET_MODE (x) == DFmode
- || GET_MODE (x) == XFmode
- || GET_MODE (x) == TFmode)
- strcpy (t, "fr");
+ if (REGNO (x) < FIRST_PSEUDO_REGISTER)
+ {
+ int c = reg_names[ REGNO (x) ][0];
+ if (c >= '0' && c <= '9')
+ cur = safe_concat (buf, cur, "%");
+
+ cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
+ }
else
- strcpy (t, "r");
- sprintf (buf, "%s%d", t, REGNO (x));
+ {
+ sprintf (t, "r%d", REGNO (x));
+ cur = safe_concat (buf, cur, t);
+ }
break;
case SUBREG:
- print_value (t, XEXP (x, 0), verbose);
- sprintf (buf, "%s#%d", t, SUBREG_WORD (x));
+ print_value (t, SUBREG_REG (x), verbose);
+ cur = safe_concat (buf, cur, t);
+ sprintf (t, "#%d", SUBREG_WORD (x));
+ cur = safe_concat (buf, cur, t);
break;
case SCRATCH:
- sprintf (buf, "scratch");
+ cur = safe_concat (buf, cur, "scratch");
break;
case CC0:
- sprintf (buf, "cc0");
+ cur = safe_concat (buf, cur, "cc0");
break;
case PC:
- sprintf (buf, "pc");
+ cur = safe_concat (buf, cur, "pc");
break;
case MEM:
print_value (t, XEXP (x, 0), verbose);
- sprintf (buf, "[%s]", t);
+ cur = safe_concat (buf, cur, "[");
+ cur = safe_concat (buf, cur, t);
+ cur = safe_concat (buf, cur, "]");
break;
default:
- print_exp (buf, x, verbose);
+ print_exp (t, x, verbose);
+ cur = safe_concat (buf, cur, t);
+ break;
}
} /* print_value */
}
break;
case ASM_INPUT:
- sprintf (buf, "asm {%s}", XEXP (x, 0));
+ sprintf (buf, "asm {%s}", XSTR (x, 0));
break;
case ADDR_VEC:
break;
Return number of insns scheduled. */
static int
-schedule_block (bb, rgn, rgn_n_insns)
+schedule_block (bb, rgn_n_insns)
int bb;
- int rgn;
int rgn_n_insns;
{
/* Local variables. */
INSN_UID (basic_block_end[b]),
(reload_completed ? "after" : "before"));
fprintf (dump, ";; ======================================================\n");
- if (sched_debug_count >= 0)
- fprintf (dump, ";;\t -- sched_debug_count=%d\n", sched_debug_count);
fprintf (dump, "\n");
visual_tbl = (char *) alloca (get_visual_tbl_length ());
if (!CANT_MOVE (insn)
&& (!IS_SPECULATIVE_INSN (insn)
|| (insn_issue_delay (insn) <= 3
- && check_live (insn, bb_src, target_bb)
+ && check_live (insn, bb_src)
&& is_exception_free (insn, bb_src, target_bb))))
{
if (sched_verbose >= 2)
{
- fprintf (dump, ";;\t\tReady list initially: ");
+ fprintf (dump, ";;\t\tReady list initially: ");
debug_ready_list (ready, n_ready);
}
{
int b1;
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count == 0)
- break;
-#endif
clock_var++;
/* Add to the ready list all pending insns that can be issued now.
if (sched_verbose)
{
- fprintf (dump, ";;\tReady list (t =%3d): ", clock_var);
+ fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
debug_ready_list (ready, n_ready);
}
}
else if (cost == 0)
{
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count == 0)
- break;
-#endif
-
/* an interblock motion? */
if (INSN_BB (insn) != target_bb)
{
if (IS_SPECULATIVE_INSN (insn))
{
- if (!check_live (insn, INSN_BB (insn), target_bb))
+ if (!check_live (insn, INSN_BB (insn)))
{
/* speculative motion, live check failed, remove
insn from ready list */
ready[i] = ready[--n_ready];
continue;
}
- update_live (insn, INSN_BB (insn), target_bb);
+ update_live (insn, INSN_BB (insn));
/* for speculative load, mark insns fed by it. */
if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
can_issue_more--;
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count > 0)
- sched_debug_count--;
-#endif
-
n_ready = schedule_insn (insn, ready, n_ready, clock_var);
/* remove insn from ready list */
if (sched_verbose)
{
visualize_scheduled_insns (b, clock_var);
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count == 0)
- fprintf (dump, "........ sched_debug_count == 0 .................\n");
-#endif
}
}
}
/* Sanity check -- queue must be empty now. Meaningless if region has
- multiple bbs, or if scheduling stopped by sched_debug_count. */
+ multiple bbs. */
if (current_nr_blocks > 1)
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count != 0)
-#endif
- if (!flag_schedule_interblock && q_size != 0)
- abort ();
+ if (!flag_schedule_interblock && q_size != 0)
+ abort ();
/* update head/tail boundaries. */
head = NEXT_INSN (prev_head);
tail = last;
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count == 0)
- /* compensate for stopping scheduling prematurely */
- for (i = sched_target_n_insns; i < target_n_insns; i++)
- tail = move_insn (group_leader (NEXT_INSN (tail)), tail);
-#endif
-
/* Restore-other-notes: NOTE_LIST is the end of a chain of notes
previously found among the insns. Insert them at the beginning
of the insns. */
if (find_insn_list (insn, INSN_DEPEND (x)))
continue;
- new_link = rtx_alloc (INSN_LIST);
+ new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
dep_type = REG_NOTE_KIND (link);
PUT_REG_NOTE_KIND (new_link, dep_type);
- XEXP (new_link, 0) = insn;
- XEXP (new_link, 1) = INSN_DEPEND (x);
-
INSN_DEPEND (x) = new_link;
INSN_DEP_COUNT (insn) += 1;
}
for (bb = 0; bb < n_bbs; bb++)
{
bb_sched_before_next_call[bb] =
- gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
- NULL_RTX, 0, NULL_RTX, NULL_RTX);
+ gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
+ NULL_RTX, 0, NULL_RTX, NULL_RTX);
LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
}
}
last_function_call = 0;
last_pending_memory_flush = 0;
sched_before_next_call
- = gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
- NULL_RTX, 0, NULL_RTX, NULL_RTX);
+ = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
+ NULL_RTX, 0, NULL_RTX, NULL_RTX);
LOG_LINKS (sched_before_next_call) = 0;
}
else
continue;
(bb_reg_last_uses[bb_succ])[reg]
- = gen_rtx (INSN_LIST, VOIDmode, XEXP (u, 0),
- (bb_reg_last_uses[bb_succ])[reg]);
+ = alloc_INSN_LIST (XEXP (u, 0),
+ (bb_reg_last_uses[bb_succ])[reg]);
}
/* reg-last-defs lists are inherited by bb_succ */
continue;
(bb_reg_last_sets[bb_succ])[reg]
- = gen_rtx (INSN_LIST, VOIDmode, XEXP (u, 0),
- (bb_reg_last_sets[bb_succ])[reg]);
+ = alloc_INSN_LIST (XEXP (u, 0),
+ (bb_reg_last_sets[bb_succ])[reg]);
}
}
continue;
bb_last_function_call[bb_succ]
- = gen_rtx (INSN_LIST, VOIDmode, XEXP (u, 0),
- bb_last_function_call[bb_succ]);
+ = alloc_INSN_LIST (XEXP (u, 0),
+ bb_last_function_call[bb_succ]);
}
/* last_pending_memory_flush is inherited by bb_succ */
continue;
bb_last_pending_memory_flush[bb_succ]
- = gen_rtx (INSN_LIST, VOIDmode, XEXP (u, 0),
- bb_last_pending_memory_flush[bb_succ]);
+ = alloc_INSN_LIST (XEXP (u, 0),
+ bb_last_pending_memory_flush[bb_succ]);
}
/* sched_before_next_call is inherited by bb_succ */
}
while (e != first_edge);
}
+
+ /* Free up the INSN_LISTs
+
+ Note this loop is executed max_reg * nr_regions times. It's first
+ implementation accounted for over 90% of the calls to free_list.
+ The list was empty for the vast majority of those calls. On the PA,
+ not calling free_list in those cases improves -O2 compile times by
+ 3-5% on average. */
+ for (b = 0; b < max_reg; ++b)
+ {
+ if (reg_last_sets[b])
+ free_list (®_last_sets[b], &unused_insn_list);
+ if (reg_last_uses[b])
+ free_list (®_last_uses[b], &unused_insn_list);
+ }
+
+ /* Assert that we won't need bb_reg_last_* for this block anymore. */
+ if (current_nr_blocks > 1)
+ {
+ bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
+ bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
+ }
}
/* Print dependences for debugging, callable from debugger */
/* now we can schedule all blocks */
for (bb = 0; bb < current_nr_blocks; bb++)
{
- sched_rgn_n_insns += schedule_block (bb, rgn, rgn_n_insns);
+ sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
#ifdef USE_C_ALLOCA
alloca (0);
#endif
}
-#ifdef INTERBLOCK_DEBUG
- if (sched_debug_count != 0)
-#endif
- /* sanity check: verify that all region insns were scheduled */
- if (sched_rgn_n_insns != rgn_n_insns)
- abort ();
+ /* sanity check: verify that all region insns were scheduled */
+ if (sched_rgn_n_insns != rgn_n_insns)
+ abort ();
/* update register life and usage information */
if (reload_completed == 0)
several smaller hard register references in the split insns. */
static void
-split_hard_reg_notes (note, first, last, orig_insn)
- rtx note, first, last, orig_insn;
+split_hard_reg_notes (note, first, last)
+ rtx note, first, last;
{
rtx reg, temp, link;
int n_regs, i, new_reg;
&& (temp = regno_use_in (new_reg, PATTERN (insn))))
{
/* Create a new reg dead note ere. */
- link = rtx_alloc (EXPR_LIST);
- PUT_REG_NOTE_KIND (link, REG_DEAD);
- XEXP (link, 0) = temp;
- XEXP (link, 1) = REG_NOTES (insn);
+ link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
REG_NOTES (insn) = link;
/* If killed multiple registers here, then add in the excess. */
if (GET_CODE (dest) == REG)
{
+ /* If the original insn already used this register, we may not add new
+ notes for it. One example for a split that needs this test is
+ when a multi-word memory access with register-indirect addressing
+ is split into multiple memory accesses with auto-increment and
+ one adjusting add instruction for the address register. */
+ if (reg_referenced_p (dest, PATTERN (orig_insn)))
+ return;
for (tem = last; tem != insn; tem = PREV_INSN (tem))
{
if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
&& !find_regno_note (tem, REG_DEAD, REGNO (dest)))
{
- rtx note = rtx_alloc (EXPR_LIST);
- PUT_REG_NOTE_KIND (note, REG_DEAD);
- XEXP (note, 0) = dest;
- XEXP (note, 1) = REG_NOTES (tem);
+ rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
+ REG_NOTES (tem));
REG_NOTES (tem) = note;
}
/* The reg only dies in one insn, the last one that uses
if (GET_CODE (pat) == CLOBBER)
{
- rtx note = rtx_alloc (EXPR_LIST);
- PUT_REG_NOTE_KIND (note, REG_UNUSED);
- XEXP (note, 0) = dest;
- XEXP (note, 1) = REG_NOTES (insn);
+ rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
REG_NOTES (insn) = note;
return;
}
&& 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);
+ split_hard_reg_notes (note, first, last);
else
{
XEXP (note, 1) = REG_NOTES (insn);
break;
case REG_WAS_0:
+ /* If the insn that set the register to 0 was deleted, this
+ note cannot be relied on any longer. The destination might
+ even have been moved to memory.
+ This was observed for SH4 with execute/920501-6.c compilation,
+ -O2 -fomit-frame-pointer -finline-functions . */
+ if (GET_CODE (XEXP (note, 0)) == NOTE
+ || INSN_DELETED_P (XEXP (note, 0)))
+ break;
/* This note applies to the dest of the original insn. Find the
first new insn that now has the same dest, and move the note
there. */
for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
- REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL,
- XEXP (note, 0), REG_NOTES (insn));
+ {
+ REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
+ XEXP (note, 0),
+ REG_NOTES (insn));
+ }
break;
case REG_CC_SETTER:
if (insn_dest != dest)
{
- note = rtx_alloc (EXPR_LIST);
- PUT_REG_NOTE_KIND (note, REG_DEAD);
- XEXP (note, 0) = dest;
- XEXP (note, 1) = REG_NOTES (insn);
+ note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
REG_NOTES (insn) = note;
/* The reg only dies in one insn, the last one
that uses it. */
for (insn = basic_block_head[b];; insn = next)
{
- rtx prev;
- rtx set;
+ rtx set, last, first, notes;
/* Can't use `next_real_insn' because that
might go across CODE_LABELS and short-out basic blocks. */
}
/* Split insns here to get max fine-grain parallelism. */
- prev = PREV_INSN (insn);
- /* 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)
+ first = PREV_INSN (insn);
+ notes = REG_NOTES (insn);
+ last = try_split (PATTERN (insn), insn, 1);
+ if (last != insn)
{
- rtx last, first = PREV_INSN (insn);
- rtx notes = REG_NOTES (insn);
- last = try_split (PATTERN (insn), insn, 1);
- if (last != insn)
+ /* try_split returns the NOTE that INSN became. */
+ first = NEXT_INSN (first);
+ update_flow_info (notes, first, last, insn);
+
+ PUT_CODE (insn, NOTE);
+ NOTE_SOURCE_FILE (insn) = 0;
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ if (insn == basic_block_head[b])
+ basic_block_head[b] = first;
+ if (insn == basic_block_end[b])
{
- /* try_split returns the NOTE that INSN became. */
- first = NEXT_INSN (first);
- update_flow_info (notes, first, last, insn);
-
- PUT_CODE (insn, NOTE);
- NOTE_SOURCE_FILE (insn) = 0;
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- if (insn == basic_block_head[b])
- basic_block_head[b] = first;
- if (insn == basic_block_end[b])
- {
- basic_block_end[b] = last;
- break;
- }
+ basic_block_end[b] = last;
+ break;
}
}
int max_uid;
int b;
- int i;
rtx insn;
int rgn;
for (b = 0; b < n_basic_blocks; b++)
for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
{
- rtx link;
+ rtx link, prev;
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
- for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+ prev = NULL_RTX;
+ link = LOG_LINKS (insn);
+ while (link)
{
rtx x = XEXP (link, 0);
if (INSN_BLOCK (x) != b)
- remove_dependence (insn, x);
+ {
+ remove_dependence (insn, x);
+ link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
+ }
+ else
+ prev = link, link = XEXP (prev, 1);
}
}
}
else
{
- /* an estimation for nr_edges is computed in is_cfg_nonregular () */
- nr_edges = 0;
-
/* verify that a 'good' control flow graph can be built */
- if (is_cfg_nonregular ()
- || nr_edges <= 1)
+ if (is_cfg_nonregular ())
{
find_single_block_region ();
}
else
{
- /* build control flow graph */
- in_edges = (int *) alloca (n_basic_blocks * sizeof (int));
- out_edges = (int *) alloca (n_basic_blocks * sizeof (int));
- bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
- bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
-
- edge_table =
- (edge *) alloca ((nr_edges) * sizeof (edge));
- bzero ((char *) edge_table,
- ((nr_edges) * sizeof (edge)));
- build_control_flow ();
-
- /* identify reducible inner loops and compute regions */
- find_rgns ();
+ int_list_ptr *s_preds, *s_succs;
+ int *num_preds, *num_succs;
+ sbitmap *dom, *pdom;
+
+ s_preds = (int_list_ptr *) alloca (n_basic_blocks
+ * sizeof (int_list_ptr));
+ s_succs = (int_list_ptr *) alloca (n_basic_blocks
+ * sizeof (int_list_ptr));
+ num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
+ num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
+ dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+
+ /* The scheduler runs after flow; therefore, we can't blindly call
+ back into find_basic_blocks since doing so could invalidate the
+ info in basic_block_live_at_start.
+
+ Consider a block consisting entirely of dead stores; after life
+ analysis it would be a block of NOTE_INSN_DELETED notes. If
+ we call find_basic_blocks again, then the block would be removed
+ entirely and invalidate our the register live information.
+
+ We could (should?) recompute register live information. Doing
+ so may even be beneficial. */
+
+ compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
+
+ /* Compute the dominators and post dominators. We don't currently use
+ post dominators, but we should for speculative motion analysis. */
+ compute_dominators (dom, pdom, s_preds, s_succs);
+
+ /* build_control_flow will return nonzero if it detects unreachable
+ blocks or any other irregularity with the cfg which prevents
+ cross block scheduling. */
+ if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
+ find_single_block_region ();
+ else
+ find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
if (sched_verbose >= 3)
- {
- debug_control_flow ();
- debug_regions ();
- }
+ debug_regions ();
+ /* For now. This will move as more and more of haifa is converted
+ to using the cfg code in flow.c */
+ free_bb_mem ();
+ free (dom);
+ free (pdom);
}
}
if (bb_live_regs)
FREE_REG_SET (bb_live_regs);
+
+ if (edge_table)
+ {
+ free (edge_table);
+ edge_table = NULL;
+ }
+
+ if (in_edges)
+ {
+ free (in_edges);
+ in_edges = NULL;
+ }
+ if (out_edges)
+ {
+ free (out_edges);
+ out_edges = NULL;
+ }
}
#endif /* INSN_SCHEDULING */
OSDN Git Service
