/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005 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 GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* This pass implements list scheduling within basic blocks. It is
run twice: (1) after flow analysis, but before register allocation,
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
-#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
#include "params.h"
#include "sched-int.h"
#include "target.h"
+#include "timevar.h"
+#include "tree-pass.h"
/* Define when we want to do count REG_DEAD notes before and after scheduling
for sanity checking. We can't do that when conditional execution is used,
/* nr_inter/spec counts interblock/speculative motion for the function. */
static int nr_inter, nr_spec;
-/* Control flow graph edges are kept in circular lists. */
-typedef struct
-{
- int from_block;
- int to_block;
- int next_in;
- int next_out;
-}
-haifa_edge;
-static haifa_edge *edge_table;
-
-#define NEXT_IN(edge) (edge_table[edge].next_in)
-#define NEXT_OUT(edge) (edge_table[edge].next_out)
-#define FROM_BLOCK(edge) (edge_table[edge].from_block)
-#define TO_BLOCK(edge) (edge_table[edge].to_block)
-
-/* Number of edges in the control flow graph. (In fact, larger than
- that by 1, since edge 0 is unused.) */
-static int nr_edges;
-
-/* Circular list of incoming/outgoing edges of a block. */
-static int *in_edges;
-static int *out_edges;
-
-#define IN_EDGES(block) (in_edges[block])
-#define OUT_EDGES(block) (out_edges[block])
-
static int is_cfg_nonregular (void);
-static int build_control_flow (struct edge_list *);
-static void new_edge (int, int);
+static bool sched_is_disabled_for_current_region_p (void);
/* A region is the main entity for interblock scheduling: insns
are allowed to move between blocks in the same region, along
/* The number of the region containing a block. */
static int *containing_rgn;
+/* The minimum probability of reaching a source block so that it will be
+ considered for speculative scheduling. */
+static int min_spec_prob;
+
#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
#define BLOCK_TO_BB(block) (block_to_bb[block])
void debug_regions (void);
static void find_single_block_region (void);
-static void find_rgns (struct edge_list *);
+static void find_rgns (void);
static bool too_large (int, int *, int *);
extern void debug_live (int, int);
/* The mapping from bb to block. */
#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
-typedef struct
-{
- int *first_member; /* Pointer to the list start in bitlst_table. */
- int nr_members; /* The number of members of the bit list. */
-}
-bitlst;
-
-static int bitlst_table_last;
-static int *bitlst_table;
-
-static void extract_bitlst (sbitmap, bitlst *);
-
/* Target info declarations.
The block currently being scheduled is referred to as the "target" block,
while other blocks in the region from which insns can be moved to the
target are called "source" blocks. The candidate structure holds info
about such sources: are they valid? Speculative? Etc. */
-typedef bitlst bblst;
+typedef struct
+{
+ basic_block *first_member;
+ int nr_members;
+}
+bblst;
+
typedef struct
{
char is_valid;
Lists of split and update blocks for each candidate of the current
target are in array bblst_table. */
-static int *bblst_table, bblst_size, bblst_last;
+static basic_block *bblst_table;
+static int bblst_size, bblst_last;
#define IS_VALID(src) ( candidate_table[src].is_valid )
#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
static int target_bb;
/* List of edges. */
-typedef bitlst edgelst;
+typedef struct
+{
+ edge *first_member;
+ int nr_members;
+}
+edgelst;
+
+static edge *edgelst_table;
+static int edgelst_last;
+
+static void extract_edgelst (sbitmap, edgelst *);
+
/* Target info functions. */
static void split_edges (int, int, edgelst *);
#define IS_DOMINATED(bb_src, bb_trg) \
( TEST_BIT (dom[bb_src], bb_trg) )
-/* Probability: Prob[i] is a float in [0, 1] which is the probability
- of bb i relative to the region entry. */
-static float *prob;
-
-/* The probability of bb_src, relative to bb_trg. Note, that while the
- 'prob[bb]' is a float in [0, 1], this macro returns an integer
- in [0, 100]. */
-#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
- prob[bb_trg])))
+/* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
+ the probability of bb i relative to the region entry. */
+static int *prob;
/* Bit-set of edges, where bit i stands for edge i. */
typedef sbitmap edgeset;
static int rgn_nr_edges;
/* Array of size rgn_nr_edges. */
-static int *rgn_edges;
-
+static edge *rgn_edges;
/* Mapping from each edge in the graph to its number in the rgn. */
-static int *edge_to_bit;
-#define EDGE_TO_BIT(edge) (edge_to_bit[edge])
+#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
+#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
/* The split edges of a source bb is different for each target
bb. In order to compute this efficiently, the 'potential-split edges'
#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
-/* Parameters affecting the decision of rank_for_schedule().
- ??? Nope. But MIN_PROBABILITY is used in compute_trg_info. */
-#define MIN_PROBABILITY 40
-
/* Speculative scheduling functions. */
static int check_live_1 (int, rtx);
static void update_live_1 (int, rtx);
/* Return 1 if control flow graph should not be constructed, 0 otherwise.
We decide not to build the control flow graph if there is possibly more
- than one entry to the function, if computed branches exist, of if we
- have nonlocal gotos. */
+ than one entry to the function, if computed branches exist, if we
+ have nonlocal gotos, or if we have an unreachable loop. */
static int
is_cfg_nonregular (void)
{
basic_block b;
rtx insn;
- RTX_CODE code;
/* If we have a label that could be the target of a nonlocal goto, then
the cfg is not well structured. */
if (forced_labels)
return 1;
- /* 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 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_EACH_BB (b)
- for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (b, insn)
{
- code = GET_CODE (insn);
- if (INSN_P (insn) && code != JUMP_INSN)
+ /* Check for labels referred by non-jump insns. */
+ if (NONJUMP_INSN_P (insn) || CALL_P (insn))
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
-
if (note
- && ! (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && ! (JUMP_P (NEXT_INSN (insn))
&& find_reg_note (NEXT_INSN (insn), REG_LABEL,
XEXP (note, 0))))
return 1;
}
-
- if (insn == BB_END (b))
- break;
+ /* If this function has a computed jump, then we consider the cfg
+ not well structured. */
+ else if (JUMP_P (insn) && computed_jump_p (insn))
+ return 1;
}
- /* All the tests passed. Consider the cfg well structured. */
- return 0;
-}
-
-/* Build the control flow graph and set nr_edges.
-
- Instead of trying to build a cfg ourselves, we rely on flow to
- do it for us. Stamp out useless code (and bug) duplication.
-
- Return nonzero if an irregularity in the cfg is found which would
- prevent cross block scheduling. */
-
-static int
-build_control_flow (struct edge_list *edge_list)
-{
- int i, unreachable, num_edges;
- basic_block b;
-
- /* This already accounts for entry/exit edges. */
- num_edges = NUM_EDGES (edge_list);
-
/* 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. */
- unreachable = 0;
+ cheaper to go ahead and catch the trivial case here. */
FOR_EACH_BB (b)
{
- if (b->pred == NULL
- || (b->pred->src == b
- && b->pred->pred_next == NULL))
- unreachable = 1;
- }
-
- /* ??? We can kill these soon. */
- in_edges = xcalloc (last_basic_block, sizeof (int));
- out_edges = xcalloc (last_basic_block, sizeof (int));
- edge_table = xcalloc (num_edges, sizeof (haifa_edge));
-
- nr_edges = 0;
- for (i = 0; i < num_edges; i++)
- {
- edge e = INDEX_EDGE (edge_list, i);
-
- if (e->dest != EXIT_BLOCK_PTR
- && e->src != ENTRY_BLOCK_PTR)
- new_edge (e->src->index, e->dest->index);
+ if (EDGE_COUNT (b->preds) == 0
+ || (single_pred_p (b)
+ && single_pred (b) == b))
+ return 1;
}
- /* Increment by 1, since edge 0 is unused. */
- nr_edges++;
-
- return unreachable;
+ /* All the tests passed. Consider the cfg well structured. */
+ return 0;
}
-/* Record 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. */
+/* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
static void
-new_edge (int source, int target)
+extract_edgelst (sbitmap set, edgelst *el)
{
- int e, next_edge;
- int curr_edge, fst_edge;
-
- /* Check for duplicates. */
- fst_edge = curr_edge = OUT_EDGES (source);
- while (curr_edge)
- {
- if (FROM_BLOCK (curr_edge) == source
- && TO_BLOCK (curr_edge) == target)
- {
- return;
- }
-
- curr_edge = NEXT_OUT (curr_edge);
-
- if (fst_edge == curr_edge)
- break;
- }
+ unsigned int i = 0;
+ sbitmap_iterator sbi;
- e = ++nr_edges;
+ /* edgelst table space is reused in each call to extract_edgelst. */
+ edgelst_last = 0;
- FROM_BLOCK (e) = source;
- TO_BLOCK (e) = target;
+ el->first_member = &edgelst_table[edgelst_last];
+ el->nr_members = 0;
- if (OUT_EDGES (source))
- {
- next_edge = NEXT_OUT (OUT_EDGES (source));
- NEXT_OUT (OUT_EDGES (source)) = e;
- NEXT_OUT (e) = next_edge;
- }
- else
- {
- OUT_EDGES (source) = e;
- NEXT_OUT (e) = e;
- }
-
- if (IN_EDGES (target))
- {
- next_edge = NEXT_IN (IN_EDGES (target));
- NEXT_IN (IN_EDGES (target)) = e;
- NEXT_IN (e) = next_edge;
- }
- else
+ /* Iterate over each word in the bitset. */
+ EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)
{
- IN_EDGES (target) = e;
- NEXT_IN (e) = e;
+ edgelst_table[edgelst_last++] = rgn_edges[i];
+ el->nr_members++;
}
}
-/* Translate a bit-set SET to a list BL of the bit-set members. */
-
-static void
-extract_bitlst (sbitmap set, bitlst *bl)
-{
- int i;
-
- /* bblst table space is reused in each call to extract_bitlst. */
- bitlst_table_last = 0;
-
- bl->first_member = &bitlst_table[bitlst_table_last];
- bl->nr_members = 0;
-
- /* Iterate over each word in the bitset. */
- EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
- {
- bitlst_table[bitlst_table_last++] = i;
- (bl->nr_members)++;
- });
-
-}
-
/* Functions for the construction of regions. */
/* Print the regions, for debugging purposes. Callable from debugger. */
{
current_blocks = RGN_BLOCKS (rgn);
- if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
- abort ();
-
+ gcc_assert (bb == BLOCK_TO_BB (BB_TO_BLOCK (bb)));
fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
}
of edge tables. That would simplify it somewhat. */
static void
-find_rgns (struct edge_list *edge_list)
+find_rgns (void)
{
- int *max_hdr, *dfs_nr, *stack, *degree;
+ int *max_hdr, *dfs_nr, *degree;
char no_loops = 1;
int node, child, loop_head, i, head, tail;
int count = 0, sp, idx = 0;
- int current_edge = out_edges[ENTRY_BLOCK_PTR->succ->dest->index];
+ edge_iterator current_edge;
+ edge_iterator *stack;
int num_bbs, num_insns, unreachable;
int too_large_failure;
basic_block bb;
- /* 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 in the block queue. */
sbitmap in_stack;
- int num_edges = NUM_EDGES (edge_list);
-
/* 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).
STACK, SP and DFS_NR are only used during the first traversal. */
/* Allocate and initialize variables for the first traversal. */
- max_hdr = xmalloc (last_basic_block * sizeof (int));
- dfs_nr = xcalloc (last_basic_block, sizeof (int));
- stack = xmalloc (nr_edges * sizeof (int));
+ max_hdr = XNEWVEC (int, last_basic_block);
+ dfs_nr = XCNEWVEC (int, last_basic_block);
+ stack = XNEWVEC (edge_iterator, n_edges);
inner = sbitmap_alloc (last_basic_block);
sbitmap_ones (inner);
header = sbitmap_alloc (last_basic_block);
sbitmap_zero (header);
- passed = sbitmap_alloc (nr_edges);
- sbitmap_zero (passed);
-
in_queue = sbitmap_alloc (last_basic_block);
sbitmap_zero (in_queue);
for (i = 0; i < last_basic_block; i++)
max_hdr[i] = -1;
+ #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
+ #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
+
/* DFS traversal to find inner loops in the cfg. */
+ current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);
sp = -1;
+
while (1)
{
- if (current_edge == 0 || TEST_BIT (passed, current_edge))
+ if (EDGE_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)))
+ while (sp >= 0 && EDGE_PASSED (current_edge))
{
/* Pop entry off the stack. */
current_edge = stack[sp--];
- node = FROM_BLOCK (current_edge);
- child = TO_BLOCK (current_edge);
+ node = ei_edge (current_edge)->src->index;
+ gcc_assert (node != ENTRY_BLOCK);
+ child = ei_edge (current_edge)->dest->index;
+ gcc_assert (child != EXIT_BLOCK);
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);
+ ei_next (¤t_edge);
}
/* See if have finished the DFS tree traversal. */
- if (sp < 0 && TEST_BIT (passed, current_edge))
+ if (sp < 0 && EDGE_PASSED (current_edge))
break;
/* Nope, continue the traversal with the popped node. */
}
/* Process a node. */
- node = FROM_BLOCK (current_edge);
- child = TO_BLOCK (current_edge);
+ node = ei_edge (current_edge)->src->index;
+ gcc_assert (node != ENTRY_BLOCK);
SET_BIT (in_stack, node);
dfs_nr[node] = ++count;
+ /* We don't traverse to the exit block. */
+ child = ei_edge (current_edge)->dest->index;
+ if (child == EXIT_BLOCK)
+ {
+ SET_EDGE_PASSED (current_edge);
+ ei_next (¤t_edge);
+ continue;
+ }
+
/* 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. */
no_loops = 0;
SET_BIT (header, child);
UPDATE_LOOP_RELATIONS (node, child);
- SET_BIT (passed, current_edge);
- current_edge = NEXT_OUT (current_edge);
+ SET_EDGE_PASSED (current_edge);
+ ei_next (¤t_edge);
continue;
}
{
if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
- SET_BIT (passed, current_edge);
- current_edge = NEXT_OUT (current_edge);
+ SET_EDGE_PASSED (current_edge);
+ ei_next (¤t_edge);
continue;
}
/* Push an entry on the stack and continue DFS traversal. */
stack[++sp] = current_edge;
- SET_BIT (passed, current_edge);
- current_edge = OUT_EDGES (child);
-
- /* This is temporary until haifa is converted to use rth's new
- cfg routines which have true entry/exit blocks and the
- appropriate edges from/to those blocks.
-
- Generally we update dfs_nr for a node when we process its
- out edge. However, if the node has no out edge then we will
- not set dfs_nr for that node. This can confuse the scheduler
- into thinking that we have unreachable blocks, which in turn
- disables cross block scheduling.
-
- So, if we have a node with no out edges, go ahead and mark it
- as reachable now. */
- if (current_edge == 0)
- dfs_nr[child] = ++count;
+ SET_EDGE_PASSED (current_edge);
+ current_edge = ei_start (ei_edge (current_edge)->dest->succs);
}
+ /* Reset ->aux field used by EDGE_PASSED. */
+ FOR_ALL_BB (bb)
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->aux = NULL;
+ }
+
+
/* Another check for unreachable blocks. The earlier test in
is_cfg_nonregular only finds unreachable blocks that do not
form a loop.
degree = dfs_nr;
FOR_EACH_BB (bb)
- degree[bb->index] = 0;
- for (i = 0; i < num_edges; i++)
- {
- edge e = INDEX_EDGE (edge_list, i);
-
- if (e->dest != EXIT_BLOCK_PTR)
- degree[e->dest->index]++;
- }
+ degree[bb->index] = EDGE_COUNT (bb->preds);
/* Do not perform region scheduling if there are any unreachable
blocks. */
/* Second traversal:find reducible inner loops and topologically sort
block of each region. */
- queue = xmalloc (n_basic_blocks * sizeof (int));
+ queue = XNEWVEC (int, n_basic_blocks);
/* Find blocks which are inner loop headers. We still have non-reducible
loops to consider at this point. */
if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
{
edge e;
+ edge_iterator ei;
basic_block jbb;
/* Now check that the loop is reducible. We do this separate
/* Decrease degree of all I's successors for topological
ordering. */
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR)
--degree[e->dest->index];
FOR_EACH_BB (jbb)
/* Leaf nodes have only a single successor which must
be EXIT_BLOCK. */
- if (jbb->succ
- && jbb->succ->dest == EXIT_BLOCK_PTR
- && jbb->succ->succ_next == NULL)
+ if (single_succ_p (jbb)
+ && single_succ (jbb) == EXIT_BLOCK_PTR)
{
queue[++tail] = jbb->index;
SET_BIT (in_queue, jbb->index);
{
edge e;
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->src == ENTRY_BLOCK_PTR)
continue;
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).
+ of the loop (i.e. 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
edge e;
child = queue[++head];
- for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
{
node = e->src->index;
CONTAINING_RGN (child) = nr_regions;
queue[head] = queue[tail--];
- for (e = BASIC_BLOCK (child)->succ;
- e;
- e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
if (e->dest != EXIT_BLOCK_PTR)
--degree[e->dest->index];
}
free (max_hdr);
free (dfs_nr);
free (stack);
- sbitmap_free (passed);
sbitmap_free (header);
sbitmap_free (inner);
sbitmap_free (in_queue);
static void
compute_dom_prob_ps (int bb)
{
- int nxt_in_edge, fst_in_edge, pred;
- int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
+ edge_iterator in_ei;
+ edge in_edge;
- prob[bb] = 0.0;
if (IS_RGN_ENTRY (bb))
{
SET_BIT (dom[bb], 0);
- prob[bb] = 1.0;
+ prob[bb] = REG_BR_PROB_BASE;
return;
}
- fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
+ prob[bb] = 0;
/* Initialize dom[bb] to '111..1'. */
sbitmap_ones (dom[bb]);
- do
+ FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
{
- pred = FROM_BLOCK (nxt_in_edge);
- sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
- sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
-
- SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
-
- nr_out_edges = 1;
- nr_rgn_out_edges = 0;
- fst_out_edge = OUT_EDGES (pred);
- nxt_out_edge = NEXT_OUT (fst_out_edge);
+ int pred_bb;
+ edge out_edge;
+ edge_iterator out_ei;
- sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
+ if (in_edge->src == ENTRY_BLOCK_PTR)
+ continue;
- SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
+ pred_bb = BLOCK_TO_BB (in_edge->src->index);
+ sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]);
+ sbitmap_a_or_b (ancestor_edges[bb],
+ ancestor_edges[bb], ancestor_edges[pred_bb]);
- /* The successor doesn't belong in the region? */
- if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
- CONTAINING_RGN (BB_TO_BLOCK (bb)))
- ++nr_rgn_out_edges;
+ SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
- while (fst_out_edge != nxt_out_edge)
- {
- ++nr_out_edges;
- /* The successor doesn't belong in the region? */
- if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
- CONTAINING_RGN (BB_TO_BLOCK (bb)))
- ++nr_rgn_out_edges;
- SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
- nxt_out_edge = NEXT_OUT (nxt_out_edge);
+ sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
- }
+ FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
+ SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
- /* Now nr_rgn_out_edges is the number of region-exit edges from
- pred, and nr_out_edges will be the number of pred out edges
- not leaving the region. */
- nr_out_edges -= nr_rgn_out_edges;
- if (nr_rgn_out_edges > 0)
- prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
- else
- prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
- nxt_in_edge = NEXT_IN (nxt_in_edge);
+ prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
}
- while (fst_in_edge != nxt_in_edge);
SET_BIT (dom[bb], bb);
sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
if (sched_verbose >= 2)
fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
- (int) (100.0 * prob[bb]));
+ (100 * prob[bb]) / REG_BR_PROB_BASE);
}
/* Functions for target info. */
sbitmap_copy (src, pot_split[bb_src]);
sbitmap_difference (src, src, pot_split[bb_trg]);
- extract_bitlst (src, bl);
+ extract_edgelst (src, bl);
sbitmap_free (src);
}
{
candidate *sp;
edgelst el;
- int check_block, update_idx;
- int i, j, k, fst_edge, nxt_edge;
+ int i, j, k, update_idx;
+ basic_block block;
+ sbitmap visited;
+ edge_iterator ei;
+ edge e;
/* Define some of the fields for the target bb as well. */
sp = candidate_table + trg;
sp->is_valid = 1;
sp->is_speculative = 0;
- sp->src_prob = 100;
+ sp->src_prob = REG_BR_PROB_BASE;
+
+ visited = sbitmap_alloc (last_basic_block);
for (i = trg + 1; i < current_nr_blocks; i++)
{
sp->is_valid = IS_DOMINATED (i, trg);
if (sp->is_valid)
{
- sp->src_prob = GET_SRC_PROB (i, trg);
- sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
+ int tf = prob[trg], cf = prob[i];
+
+ /* In CFGs with low probability edges TF can possibly be zero. */
+ sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
+ sp->is_valid = (sp->src_prob >= min_spec_prob);
}
if (sp->is_valid)
if (sp->is_valid)
{
- char *update_blocks;
-
/* Compute split blocks and store them in bblst_table.
The TO block of every split edge is a split block. */
sp->split_bbs.first_member = &bblst_table[bblst_last];
sp->split_bbs.nr_members = el.nr_members;
for (j = 0; j < el.nr_members; bblst_last++, j++)
- bblst_table[bblst_last] =
- TO_BLOCK (rgn_edges[el.first_member[j]]);
+ bblst_table[bblst_last] = el.first_member[j]->dest;
sp->update_bbs.first_member = &bblst_table[bblst_last];
/* Compute update blocks and store them in bblst_table.
add the TO block to the update block list. This list can end
up with a lot of duplicates. We need to weed them out to avoid
overrunning the end of the bblst_table. */
- update_blocks = alloca (last_basic_block);
- memset (update_blocks, 0, last_basic_block);
update_idx = 0;
+ sbitmap_zero (visited);
for (j = 0; j < el.nr_members; j++)
{
- check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
- fst_edge = nxt_edge = OUT_EDGES (check_block);
- do
+ block = el.first_member[j]->src;
+ FOR_EACH_EDGE (e, ei, block->succs)
{
- if (! update_blocks[TO_BLOCK (nxt_edge)])
+ if (!TEST_BIT (visited, e->dest->index))
{
for (k = 0; k < el.nr_members; k++)
- if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
+ if (e == el.first_member[k])
break;
if (k >= el.nr_members)
{
- bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
- update_blocks[TO_BLOCK (nxt_edge)] = 1;
+ bblst_table[bblst_last++] = e->dest;
+ SET_BIT (visited, e->dest->index);
update_idx++;
}
}
-
- nxt_edge = NEXT_OUT (nxt_edge);
}
- while (fst_edge != nxt_edge);
}
sp->update_bbs.nr_members = update_idx;
/* Make sure we didn't overrun the end of bblst_table. */
- if (bblst_last > bblst_size)
- abort ();
+ gcc_assert (bblst_last <= bblst_size);
}
else
{
sp->src_prob = 0;
}
}
+
+ sbitmap_free (visited);
}
/* Print candidates info, for debugging purposes. Callable from debugger. */
fprintf (sched_dump, "split path: ");
for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
{
- int b = candidate_table[i].split_bbs.first_member[j];
+ int b = candidate_table[i].split_bbs.first_member[j]->index;
fprintf (sched_dump, " %d ", b);
}
fprintf (sched_dump, "update path: ");
for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
{
- int b = candidate_table[i].update_bbs.first_member[j];
+ int b = candidate_table[i].update_bbs.first_member[j]->index;
fprintf (sched_dump, " %d ", b);
}
if (reg == 0)
return 1;
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
+ while (GET_CODE (reg) == SUBREG
+ || GET_CODE (reg) == ZERO_EXTRACT
|| GET_CODE (reg) == STRICT_LOW_PART)
reg = XEXP (reg, 0);
{
for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
{
- int b = candidate_table[src].split_bbs.first_member[i];
+ basic_block b = candidate_table[src].split_bbs.first_member[i];
- if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
+ if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start,
regno + j))
{
return 0;
/* Check for pseudo registers. */
for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
{
- int b = candidate_table[src].split_bbs.first_member[i];
+ basic_block b = candidate_table[src].split_bbs.first_member[i];
- if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
+ if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start, regno))
{
return 0;
}
if (reg == 0)
return;
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
+ while (GET_CODE (reg) == SUBREG
+ || GET_CODE (reg) == ZERO_EXTRACT
|| GET_CODE (reg) == STRICT_LOW_PART)
reg = XEXP (reg, 0);
{
for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
{
- int b = candidate_table[src].update_bbs.first_member[i];
+ basic_block b = candidate_table[src].update_bbs.first_member[i];
- SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
+ SET_REGNO_REG_SET (b->il.rtl->global_live_at_start,
regno + j);
}
}
{
for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
{
- int b = candidate_table[src].update_bbs.first_member[i];
+ basic_block b = candidate_table[src].update_bbs.first_member[i];
- SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
+ SET_REGNO_REG_SET (b->il.rtl->global_live_at_start, regno);
}
}
}
(bb_from == bb_to \
|| IS_RGN_ENTRY (bb_from) \
|| (TEST_BIT (ancestor_edges[bb_to], \
- EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))))))
+ EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
/* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
&& IS_REACHABLE (INSN_BB (next), load_insn_bb)
&& load_insn_bb != INSN_BB (next)
&& GET_MODE (link) == VOIDmode
- && (GET_CODE (next) == JUMP_INSN
+ && (JUMP_P (next)
|| find_conditional_protection (next, load_insn_bb)))
return 1;
}
/* Must be a DEF-USE dependence upon non-branch. */
if (GET_MODE (link) != VOIDmode
- || GET_CODE (insn1) == JUMP_INSN)
+ || JUMP_P (insn1))
continue;
/* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
/* insn2 is the similar load, in the target block. */
return 1;
- if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
+ if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
/* insn2 is a similar load, in a split-block. */
return 1;
}
/* Prepare current target block info. */
if (current_nr_blocks > 1)
{
- candidate_table = xmalloc (current_nr_blocks * sizeof (candidate));
+ candidate_table = XNEWVEC (candidate, current_nr_blocks);
bblst_last = 0;
/* bblst_table holds split blocks and update blocks for each block after
the TO blocks of region edges, so there can be at most rgn_nr_edges
of them. */
bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
- bblst_table = xmalloc (bblst_size * sizeof (int));
+ bblst_table = XNEWVEC (basic_block, bblst_size);
- bitlst_table_last = 0;
- bitlst_table = xmalloc (rgn_nr_edges * sizeof (int));
+ edgelst_last = 0;
+ edgelst_table = XNEWVEC (edge, rgn_nr_edges);
compute_trg_info (target_bb);
}
if (!CANT_MOVE (insn)
&& (!IS_SPECULATIVE_INSN (insn)
- || ((((!targetm.sched.use_dfa_pipeline_interface
- || !targetm.sched.use_dfa_pipeline_interface ())
- && insn_issue_delay (insn) <= 3)
- || (targetm.sched.use_dfa_pipeline_interface
- && targetm.sched.use_dfa_pipeline_interface ()
- && (recog_memoized (insn) < 0
- || min_insn_conflict_delay (curr_state,
- insn, insn) <= 3)))
+ || ((recog_memoized (insn) < 0
+ || min_insn_conflict_delay (curr_state,
+ insn, insn) <= 3)
&& check_live (insn, bb_src)
&& is_exception_free (insn, bb_src, target_bb))))
if (INSN_DEP_COUNT (insn) == 0)
static int
can_schedule_ready_p (rtx insn)
{
- if (GET_CODE (insn) == JUMP_INSN)
+ if (JUMP_P (insn))
last_was_jump = 1;
/* An interblock motion? */
&& (!IS_VALID (INSN_BB (next))
|| CANT_MOVE (next)
|| (IS_SPECULATIVE_INSN (next)
- && (0
- || (targetm.sched.use_dfa_pipeline_interface
- && targetm.sched.use_dfa_pipeline_interface ()
- && recog_memoized (next) >= 0
- && min_insn_conflict_delay (curr_state, next,
- next) > 3)
- || ((!targetm.sched.use_dfa_pipeline_interface
- || !targetm.sched.use_dfa_pipeline_interface ())
- && insn_issue_delay (next) > 3)
+ && ((recog_memoized (next) >= 0
+ && min_insn_conflict_delay (curr_state, next, next) > 3)
|| !check_live (next, INSN_BB (next))
|| !is_exception_free (next, INSN_BB (next), target_bb)))))
return 0;
cc0 setters remain at the end because they can't be moved away from
their cc0 user.
+ COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
+
Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
are not moved before reload because we can wind up with register
allocation failures. */
insn = tail;
last = 0;
- while (GET_CODE (insn) == CALL_INSN
- || GET_CODE (insn) == JUMP_INSN
- || (GET_CODE (insn) == INSN
+ while (CALL_P (insn)
+ || JUMP_P (insn)
+ || (NONJUMP_INSN_P (insn)
&& (GET_CODE (PATTERN (insn)) == USE
|| GET_CODE (PATTERN (insn)) == CLOBBER
|| can_throw_internal (insn)
#endif
|| (!reload_completed
&& sets_likely_spilled (PATTERN (insn)))))
- || GET_CODE (insn) == NOTE)
+ || NOTE_P (insn))
{
- if (GET_CODE (insn) != NOTE)
+ if (!NOTE_P (insn))
{
if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
{
- add_dependence (last, insn, REG_DEP_ANTI);
+ if (! sched_insns_conditions_mutex_p (last, insn))
+ add_dependence (last, insn, REG_DEP_ANTI);
INSN_REF_COUNT (insn)++;
}
if (INSN_REF_COUNT (insn) != 0)
continue;
- add_dependence (last, insn, REG_DEP_ANTI);
+ if (! sched_insns_conditions_mutex_p (last, insn))
+ add_dependence (last, insn, REG_DEP_ANTI);
INSN_REF_COUNT (insn) = 1;
}
+
+#ifdef HAVE_conditional_execution
+ /* Finally, if the block ends in a jump, and we are doing intra-block
+ scheduling, make sure that the branch depends on any COND_EXEC insns
+ inside the block to avoid moving the COND_EXECs past the branch insn.
+
+ We only have to do this after reload, because (1) before reload there
+ are no COND_EXEC insns, and (2) the region scheduler is an intra-block
+ scheduler after reload.
+
+ FIXME: We could in some cases move COND_EXEC insns past the branch if
+ this scheduler would be a little smarter. Consider this code:
+
+ T = [addr]
+ C ? addr += 4
+ !C ? X += 12
+ C ? T += 1
+ C ? jump foo
+
+ On a target with a one cycle stall on a memory access the optimal
+ sequence would be:
+
+ T = [addr]
+ C ? addr += 4
+ C ? T += 1
+ C ? jump foo
+ !C ? X += 12
+
+ We don't want to put the 'X += 12' before the branch because it just
+ wastes a cycle of execution time when the branch is taken.
+
+ Note that in the example "!C" will always be true. That is another
+ possible improvement for handling COND_EXECs in this scheduler: it
+ could remove always-true predicates. */
+
+ if (!reload_completed || ! JUMP_P (tail))
+ return;
+
+ insn = tail;
+ while (insn != head)
+ {
+ insn = PREV_INSN (insn);
+
+ /* Note that we want to add this dependency even when
+ sched_insns_conditions_mutex_p returns true. The whole point
+ is that we _want_ this dependency, even if these insns really
+ are independent. */
+ if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
+ add_dependence (tail, insn, REG_DEP_ANTI);
+ }
+#endif
}
/* Data structures for the computation of data dependences in a regions. We
static void
propagate_deps (int bb, struct deps *pred_deps)
{
- int b = BB_TO_BLOCK (bb);
- int e, first_edge;
+ basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb));
+ edge_iterator ei;
+ edge e;
/* bb's structures are inherited by its successors. */
- first_edge = e = OUT_EDGES (b);
- if (e > 0)
- do
- {
- int b_succ = TO_BLOCK (e);
- int bb_succ = BLOCK_TO_BB (b_succ);
- struct deps *succ_deps = bb_deps + bb_succ;
- int reg;
-
- /* Only bbs "below" bb, in the same region, are interesting. */
- if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
- || bb_succ <= bb)
- {
- e = NEXT_OUT (e);
- continue;
- }
+ FOR_EACH_EDGE (e, ei, block->succs)
+ {
+ struct deps *succ_deps;
+ unsigned reg;
+ reg_set_iterator rsi;
+
+ /* Only bbs "below" bb, in the same region, are interesting. */
+ if (e->dest == EXIT_BLOCK_PTR
+ || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
+ || BLOCK_TO_BB (e->dest->index) <= bb)
+ continue;
- /* The reg_last lists are inherited by bb_succ. */
- EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg,
- {
- struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
- struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
-
- succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
- succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
- succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
- succ_rl->clobbers);
- succ_rl->uses_length += pred_rl->uses_length;
- succ_rl->clobbers_length += pred_rl->clobbers_length;
- });
- IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
-
- /* Mem read/write lists are inherited by bb_succ. */
- concat_insn_mem_list (pred_deps->pending_read_insns,
- pred_deps->pending_read_mems,
- &succ_deps->pending_read_insns,
- &succ_deps->pending_read_mems);
- concat_insn_mem_list (pred_deps->pending_write_insns,
- pred_deps->pending_write_mems,
- &succ_deps->pending_write_insns,
- &succ_deps->pending_write_mems);
-
- succ_deps->last_pending_memory_flush
- = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
- succ_deps->last_pending_memory_flush);
-
- succ_deps->pending_lists_length += pred_deps->pending_lists_length;
- succ_deps->pending_flush_length += pred_deps->pending_flush_length;
-
- /* last_function_call is inherited by bb_succ. */
- succ_deps->last_function_call
- = concat_INSN_LIST (pred_deps->last_function_call,
- succ_deps->last_function_call);
+ succ_deps = bb_deps + BLOCK_TO_BB (e->dest->index);
- /* sched_before_next_call is inherited by bb_succ. */
- succ_deps->sched_before_next_call
- = concat_INSN_LIST (pred_deps->sched_before_next_call,
- succ_deps->sched_before_next_call);
+ /* The reg_last lists are inherited by successor. */
+ EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
+ {
+ struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
+ struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
+
+ succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
+ succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
+ succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
+ succ_rl->clobbers);
+ succ_rl->uses_length += pred_rl->uses_length;
+ succ_rl->clobbers_length += pred_rl->clobbers_length;
+ }
+ IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
+
+ /* Mem read/write lists are inherited by successor. */
+ concat_insn_mem_list (pred_deps->pending_read_insns,
+ pred_deps->pending_read_mems,
+ &succ_deps->pending_read_insns,
+ &succ_deps->pending_read_mems);
+ concat_insn_mem_list (pred_deps->pending_write_insns,
+ pred_deps->pending_write_mems,
+ &succ_deps->pending_write_insns,
+ &succ_deps->pending_write_mems);
+
+ succ_deps->last_pending_memory_flush
+ = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
+ succ_deps->last_pending_memory_flush);
+
+ succ_deps->pending_lists_length += pred_deps->pending_lists_length;
+ succ_deps->pending_flush_length += pred_deps->pending_flush_length;
+
+ /* last_function_call is inherited by successor. */
+ succ_deps->last_function_call
+ = concat_INSN_LIST (pred_deps->last_function_call,
+ succ_deps->last_function_call);
- e = NEXT_OUT (e);
- }
- while (e != first_edge);
+ /* sched_before_next_call is inherited by successor. */
+ succ_deps->sched_before_next_call
+ = concat_INSN_LIST (pred_deps->sched_before_next_call,
+ succ_deps->sched_before_next_call);
+ }
/* These lists should point to the right place, for correct
freeing later. */
fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
for (bb = 0; bb < current_nr_blocks; bb++)
{
- if (1)
- {
- rtx head, tail;
- rtx next_tail;
- rtx insn;
-
- get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
- next_tail = NEXT_INSN (tail);
- fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
- BB_TO_BLOCK (bb), bb);
+ rtx head, tail;
+ rtx next_tail;
+ rtx insn;
- if (targetm.sched.use_dfa_pipeline_interface
- && targetm.sched.use_dfa_pipeline_interface ())
- {
- fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
- "insn", "code", "bb", "dep", "prio", "cost",
- "reservation");
- fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
- "----", "----", "--", "---", "----", "----",
- "-----------");
- }
- else
- {
- fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
- "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
- fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
- "----", "----", "--", "---", "----", "----", "--------", "-----");
- }
+ get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+ next_tail = NEXT_INSN (tail);
+ fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
+ BB_TO_BLOCK (bb), bb);
+
+ fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
+ "insn", "code", "bb", "dep", "prio", "cost",
+ "reservation");
+ fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
+ "----", "----", "--", "---", "----", "----",
+ "-----------");
+
+ for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+ {
+ rtx link;
- for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+ if (! INSN_P (insn))
{
- rtx link;
-
- if (! INSN_P (insn))
+ int n;
+ fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
+ if (NOTE_P (insn))
{
- int n;
- fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
- if (GET_CODE (insn) == NOTE)
+ n = NOTE_LINE_NUMBER (insn);
+ if (n < 0)
+ fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
+ else
{
- n = NOTE_LINE_NUMBER (insn);
- if (n < 0)
- fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
- else
- fprintf (sched_dump, "line %d, file %s\n", n,
- NOTE_SOURCE_FILE (insn));
+ expanded_location xloc;
+ NOTE_EXPANDED_LOCATION (xloc, insn);
+ fprintf (sched_dump, "line %d, file %s\n",
+ xloc.line, xloc.file);
}
- else
- fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
- continue;
- }
-
- if (targetm.sched.use_dfa_pipeline_interface
- && targetm.sched.use_dfa_pipeline_interface ())
- {
- fprintf (sched_dump,
- ";; %s%5d%6d%6d%6d%6d%6d ",
- (SCHED_GROUP_P (insn) ? "+" : " "),
- INSN_UID (insn),
- INSN_CODE (insn),
- INSN_BB (insn),
- INSN_DEP_COUNT (insn),
- INSN_PRIORITY (insn),
- insn_cost (insn, 0, 0));
-
- if (recog_memoized (insn) < 0)
- fprintf (sched_dump, "nothing");
- else
- print_reservation (sched_dump, insn);
}
else
- {
- int unit = insn_unit (insn);
- int range
- = (unit < 0
- || function_units[unit].blockage_range_function == 0
- ? 0
- : function_units[unit].blockage_range_function (insn));
- fprintf (sched_dump,
- ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
- (SCHED_GROUP_P (insn) ? "+" : " "),
- INSN_UID (insn),
- INSN_CODE (insn),
- INSN_BB (insn),
- INSN_DEP_COUNT (insn),
- INSN_PRIORITY (insn),
- insn_cost (insn, 0, 0),
- (int) MIN_BLOCKAGE_COST (range),
- (int) MAX_BLOCKAGE_COST (range));
- insn_print_units (insn);
- }
-
- fprintf (sched_dump, "\t: ");
- for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
- fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
- fprintf (sched_dump, "\n");
+ fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
+ continue;
}
+
+ fprintf (sched_dump,
+ ";; %s%5d%6d%6d%6d%6d%6d ",
+ (SCHED_GROUP_P (insn) ? "+" : " "),
+ INSN_UID (insn),
+ INSN_CODE (insn),
+ INSN_BB (insn),
+ INSN_DEP_COUNT (insn),
+ INSN_PRIORITY (insn),
+ insn_cost (insn, 0, 0));
+
+ if (recog_memoized (insn) < 0)
+ fprintf (sched_dump, "nothing");
+ else
+ print_reservation (sched_dump, insn);
+
+ fprintf (sched_dump, "\t: ");
+ for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
+ fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
+ fprintf (sched_dump, "\n");
}
}
fprintf (sched_dump, "\n");
}
\f
+/* Returns true if all the basic blocks of the current region have
+ NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
+static bool
+sched_is_disabled_for_current_region_p (void)
+{
+ int bb;
+
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
+ return false;
+
+ return true;
+}
+
/* Schedule a region. A region is either an inner loop, a loop-free
subroutine, or a single basic block. Each bb in the region is
scheduled after its flow predecessors. */
static void
schedule_region (int rgn)
{
+ basic_block block;
+ edge_iterator ei;
+ edge e;
int bb;
int rgn_n_insns = 0;
int sched_rgn_n_insns = 0;
current_nr_blocks = RGN_NR_BLOCKS (rgn);
current_blocks = RGN_BLOCKS (rgn);
+ /* Don't schedule region that is marked by
+ NOTE_DISABLE_SCHED_OF_BLOCK. */
+ if (sched_is_disabled_for_current_region_p ())
+ return;
+
init_deps_global ();
/* Initializations for region data dependence analysis. */
- bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
+ bb_deps = XNEWVEC (struct deps, current_nr_blocks);
for (bb = 0; bb < current_nr_blocks; bb++)
init_deps (bb_deps + bb);
/* Compute interblock info: probabilities, split-edges, dominators, etc. */
if (current_nr_blocks > 1)
{
- int i;
-
- prob = xmalloc ((current_nr_blocks) * sizeof (float));
+ prob = XNEWVEC (int, current_nr_blocks);
dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
sbitmap_vector_zero (dom, current_nr_blocks);
- /* Edge to bit. */
+
+ /* Use ->aux to implement EDGE_TO_BIT mapping. */
rgn_nr_edges = 0;
- edge_to_bit = xmalloc (nr_edges * sizeof (int));
- for (i = 1; i < nr_edges; i++)
- if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
- EDGE_TO_BIT (i) = rgn_nr_edges++;
- rgn_edges = xmalloc (rgn_nr_edges * sizeof (int));
+ FOR_EACH_BB (block)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ SET_EDGE_TO_BIT (e, rgn_nr_edges++);
+ }
+ rgn_edges = XNEWVEC (edge, rgn_nr_edges);
rgn_nr_edges = 0;
- for (i = 1; i < nr_edges; i++)
- if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
- rgn_edges[rgn_nr_edges++] = i;
+ FOR_EACH_BB (block)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ rgn_edges[rgn_nr_edges++] = e;
+ }
/* Split edges. */
pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
for (note = REG_NOTES (head); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
- {
- remove_note (head, note);
- note = XEXP (note, 1);
- remove_note (head, note);
- }
+ remove_note (head, note);
}
/* Remove remaining note insns from the block, save them in
{
free (candidate_table);
free (bblst_table);
- free (bitlst_table);
+ free (edgelst_table);
}
}
/* Sanity check: verify that all region insns were scheduled. */
- if (sched_rgn_n_insns != rgn_n_insns)
- abort ();
+ gcc_assert (sched_rgn_n_insns == rgn_n_insns);
/* Restore line notes. */
if (write_symbols != NO_DEBUG)
if (current_nr_blocks > 1)
{
+ /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
+ FOR_EACH_BB (block)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ e->aux = NULL;
+ }
+
free (prob);
sbitmap_vector_free (dom);
sbitmap_vector_free (pot_split);
sbitmap_vector_free (ancestor_edges);
- free (edge_to_bit);
free (rgn_edges);
}
}
int rgn;
nr_regions = 0;
- rgn_table = xmalloc ((n_basic_blocks) * sizeof (region));
- rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int));
- block_to_bb = xmalloc ((last_basic_block) * sizeof (int));
- containing_rgn = xmalloc ((last_basic_block) * sizeof (int));
+ rgn_table = XNEWVEC (region, n_basic_blocks);
+ rgn_bb_table = XNEWVEC (int, n_basic_blocks);
+ block_to_bb = XNEWVEC (int, last_basic_block);
+ containing_rgn = XNEWVEC (int, last_basic_block);
/* Compute regions for scheduling. */
if (reload_completed
- || n_basic_blocks == 1
- || !flag_schedule_interblock)
+ || n_basic_blocks == NUM_FIXED_BLOCKS + 1
+ || !flag_schedule_interblock
+ || is_cfg_nonregular ())
{
find_single_block_region ();
}
else
{
- /* Verify that a 'good' control flow graph can be built. */
- if (is_cfg_nonregular ())
- {
- find_single_block_region ();
- }
- else
- {
- struct edge_list *edge_list;
-
- /* The scheduler runs after estimate_probabilities; therefore, we
- can't blindly call back into find_basic_blocks since doing so
- could invalidate the branch probability info. We could,
- however, call cleanup_cfg. */
- edge_list = create_edge_list ();
-
- /* Compute the dominators and post dominators. */
- calculate_dominance_info (CDI_DOMINATORS);
-
- /* 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 (edge_list) != 0)
- find_single_block_region ();
- else
- find_rgns (edge_list);
+ /* Compute the dominators and post dominators. */
+ calculate_dominance_info (CDI_DOMINATORS);
- if (sched_verbose >= 3)
- debug_regions ();
+ /* Find regions. */
+ find_rgns ();
- /* We are done with flow's edge list. */
- free_edge_list (edge_list);
+ if (sched_verbose >= 3)
+ debug_regions ();
- /* For now. This will move as more and more of haifa is converted
- to using the cfg code in flow.c. */
- free_dominance_info (CDI_DOMINATORS);
- }
+ /* For now. This will move as more and more of haifa is converted
+ to using the cfg code in flow.c. */
+ free_dominance_info (CDI_DOMINATORS);
}
if (CHECK_DEAD_NOTES)
{
blocks = sbitmap_alloc (last_basic_block);
- deaths_in_region = xmalloc (sizeof (int) * nr_regions);
+ deaths_in_region = XNEWVEC (int, nr_regions);
/* Remove all death notes from the subroutine. */
for (rgn = 0; rgn < nr_regions; rgn++)
{
count_or_remove_death_notes (NULL, 1);
}
-/* The one entry point in this file. DUMP_FILE is the dump file for
- this pass. */
+/* The one entry point in this file. */
void
-schedule_insns (FILE *dump_file)
+schedule_insns (void)
{
sbitmap large_region_blocks, blocks;
int rgn;
/* Taking care of this degenerate case makes the rest of
this code simpler. */
- if (n_basic_blocks == 0)
+ if (n_basic_blocks == NUM_FIXED_BLOCKS)
return;
nr_inter = 0;
nr_spec = 0;
+ sched_init ();
- sched_init (dump_file);
+ min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
+ / 100);
init_regions ();
current_sched_info = ®ion_sched_info;
-
/* Schedule every region in the subroutine. */
for (rgn = 0; rgn < nr_regions; rgn++)
schedule_region (rgn);
sbitmap_zero (blocks);
SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
- if (deaths_in_region[rgn]
- != count_or_remove_death_notes (blocks, 0))
- abort ();
+ gcc_assert (deaths_in_region[rgn]
+ == count_or_remove_death_notes (blocks, 0));
}
free (deaths_in_region);
}
nr_inter, nr_spec);
}
else
- {
- if (nr_inter > 0)
- abort ();
- }
+ gcc_assert (nr_inter <= 0);
fprintf (sched_dump, "\n\n");
}
sched_finish ();
- 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;
- }
-
sbitmap_free (blocks);
sbitmap_free (large_region_blocks);
}
#endif
+\f
+static bool
+gate_handle_sched (void)
+{
+#ifdef INSN_SCHEDULING
+ return flag_schedule_insns;
+#else
+ return 0;
+#endif
+}
+
+/* Run instruction scheduler. */
+static unsigned int
+rest_of_handle_sched (void)
+{
+#ifdef INSN_SCHEDULING
+ /* Do control and data sched analysis,
+ and write some of the results to dump file. */
+
+ schedule_insns ();
+#endif
+ return 0;
+}
+
+static bool
+gate_handle_sched2 (void)
+{
+#ifdef INSN_SCHEDULING
+ return optimize > 0 && flag_schedule_insns_after_reload;
+#else
+ return 0;
+#endif
+}
+
+/* Run second scheduling pass after reload. */
+static unsigned int
+rest_of_handle_sched2 (void)
+{
+#ifdef INSN_SCHEDULING
+ /* Do control and data sched analysis again,
+ and write some more of the results to dump file. */
+
+ split_all_insns (1);
+
+ if (flag_sched2_use_superblocks || flag_sched2_use_traces)
+ {
+ schedule_ebbs ();
+ /* No liveness updating code yet, but it should be easy to do.
+ reg-stack recomputes the liveness when needed for now. */
+ count_or_remove_death_notes (NULL, 1);
+ cleanup_cfg (CLEANUP_EXPENSIVE);
+ }
+ else
+ schedule_insns ();
+#endif
+ return 0;
+}
+
+struct tree_opt_pass pass_sched =
+{
+ "sched1", /* name */
+ gate_handle_sched, /* gate */
+ rest_of_handle_sched, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_SCHED, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'S' /* letter */
+};
+
+struct tree_opt_pass pass_sched2 =
+{
+ "sched2", /* name */
+ gate_handle_sched2, /* gate */
+ rest_of_handle_sched2, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_SCHED2, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'R' /* letter */
+};
+