- STACK, SP and DFS_NR are only used during the first traversal. */
-
- /* Allocate and initialize variables for the first traversal. */
- max_hdr = (int *) xmalloc (n_basic_blocks * sizeof (int));
- dfs_nr = (int *) xcalloc (n_basic_blocks, sizeof (int));
- stack = (int *) xmalloc (nr_edges * sizeof (int));
-
- inner = sbitmap_alloc (n_basic_blocks);
- sbitmap_ones (inner);
-
- 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++)
- max_hdr[i] = -1;
-
- /* DFS traversal to find inner loops in the cfg. */
-
- sp = -1;
- while (1)
- {
- if (current_edge == 0 || TEST_BIT (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);
- 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);
- }
-
- /* 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);
- child = TO_BLOCK (current_edge);
- SET_BIT (in_stack, node);
- dfs_nr[node] = ++count;
-
- /* 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;
- SET_BIT (header, child);
- UPDATE_LOOP_RELATIONS (node, child);
- SET_BIT (passed, current_edge);
- current_edge = NEXT_OUT (current_edge);
- continue;
- }
-
- /* 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 && 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);
- 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;
- }
-
- /* Another check for unreachable blocks. The earlier test in
- is_cfg_nonregular only finds unreachable blocks that do not
- form a loop.
-
- 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++)
- if (dfs_nr[i] == 0)
- {
- unreachable = 1;
- break;
- }
-
- /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
- to hold degree counts. */
- degree = dfs_nr;
-
- for (i = 0; i < n_basic_blocks; i++)
- degree[i] = 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]++;
- }
-
- /* Do not perform region scheduling if there are any unreachable
- blocks. */
- if (!unreachable)
- {
- int *queue;
-
- if (no_loops)
- SET_BIT (header, 0);
-
- /* Second travsersal:find reducible inner loops and topologically sort
- block of each region. */
-
- queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
-
- /* 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))
- {
- edge e;
- 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/natural 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++)
- {
- /* 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;
- }
- }
-
- /* 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 (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
- if (e->dest != EXIT_BLOCK_PTR)
- --degree[e->dest->index];
-
- /* Estimate # insns, and count # blocks in the region. */
- num_bbs = 1;
- num_insns = (INSN_LUID (BLOCK_END (i))
- - INSN_LUID (BLOCK_HEAD (i)));
-
- /* Find all loop latches (blocks with 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 (BASIC_BLOCK (j)->succ
- && BASIC_BLOCK (j)->succ->dest == EXIT_BLOCK_PTR
- && BASIC_BLOCK (j)->succ->succ_next == NULL)
- {
- queue[++tail] = j;
- SET_BIT (in_queue, j);
-
- if (too_large (j, &num_bbs, &num_insns))
- {
- too_large_failure = 1;
- break;
- }
- }
- }
- else
- {
- edge e;
-
- for (e = BASIC_BLOCK (i)->pred; e; e = e->pred_next)
- {
- if (e->src == ENTRY_BLOCK_PTR)
- continue;
-
- node = e->src->index;
-
- if (max_hdr[node] == loop_head && node != i)
- {
- /* 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;
- }
- }
- }
- }
-
- /* 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)
- {
- edge e;
- child = queue[++head];
-
- for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
- {
- node = e->src->index;
-
- /* See discussion above about nodes not marked as in
- this loop during the initial DFS traversal. */
- if (e->src == ENTRY_BLOCK_PTR
- || max_hdr[node] != loop_head)
- {
- 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;
- }
- }
- }
- }
-
- 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[] 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)
- {
- if (head < 0)
- head = tail;
- child = queue[head];
- if (degree[child] == 0)
- {
- edge e;
-
- degree[child] = -1;
- rgn_bb_table[idx++] = child;
- BLOCK_TO_BB (child) = ++count;
- CONTAINING_RGN (child) = nr_regions;
- queue[head] = queue[tail--];
-
- for (e = BASIC_BLOCK (child)->succ;
- e;
- e = e->succ_next)
- if (e->dest != EXIT_BLOCK_PTR)
- --degree[e->dest->index];
- }
- else
- --head;
- }
- ++nr_regions;
- }
- }
- }
- free (queue);
- }
-
- /* 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)
- {
- rgn_bb_table[idx] = i;
- RGN_NR_BLOCKS (nr_regions) = 1;
- RGN_BLOCKS (nr_regions) = idx++;
- CONTAINING_RGN (i) = nr_regions++;
- BLOCK_TO_BB (i) = 0;
- }
-
- free (max_hdr);
- free (dfs_nr);
- free (stack);
- free (passed);
- free (header);
- free (inner);
- free (in_queue);
- free (in_stack);
-}
-
-/* Functions for regions scheduling information. */
-
-/* Compute dominators, probability, and potential-split-edges of bb.
- Assume that these values were already computed for bb's predecessors. */
-
-static void
-compute_dom_prob_ps (bb)
- int bb;
-{
- int nxt_in_edge, fst_in_edge, pred;
- int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
-
- prob[bb] = 0.0;
- if (IS_RGN_ENTRY (bb))
- {
- BITSET_ADD (dom[bb], 0, bbset_size);
- prob[bb] = 1.0;
- return;
- }
-
- fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
-
- /* Intialize dom[bb] to '111..1'. */
- BITSET_INVERT (dom[bb], bbset_size);
-
- do
- {
- pred = FROM_BLOCK (nxt_in_edge);
- BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
-
- BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
- edgeset_size);
-
- BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
-
- nr_out_edges = 1;
- nr_rgn_out_edges = 0;
- fst_out_edge = OUT_EDGES (pred);
- nxt_out_edge = NEXT_OUT (fst_out_edge);
- BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
- edgeset_size);
-
- BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
-
- /* 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;
-
- 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;
- BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
- nxt_out_edge = NEXT_OUT (nxt_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);
- }
- while (fst_in_edge != nxt_in_edge);
-
- BITSET_ADD (dom[bb], bb, bbset_size);
- BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
-
- if (sched_verbose >= 2)
- fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
- (int) (100.0 * prob[bb]));
-}
-
-/* Functions for target info. */
-
-/* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
- Note that bb_trg dominates bb_src. */
-
-static void
-split_edges (bb_src, bb_trg, bl)
- int bb_src;
- int bb_trg;
- edgelst *bl;
-{
- int es = edgeset_size;
- edgeset src = (edgeset) xcalloc (es, sizeof (HOST_WIDE_INT));
-
- while (es--)
- src[es] = (pot_split[bb_src])[es];
- BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
- extract_bitlst (src, edgeset_size, edgeset_bitsize, bl);
- free (src);
-}
-
-/* Find the valid candidate-source-blocks for the target block TRG, compute
- their probability, and check if they are speculative or not.
- For speculative sources, compute their update-blocks and split-blocks. */
-
-static void
-compute_trg_info (trg)
- int trg;
-{
- register candidate *sp;
- edgelst el;
- int check_block, update_idx;
- int i, j, k, fst_edge, nxt_edge;
-
- /* 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;
-
- for (i = trg + 1; i < current_nr_blocks; i++)
- {
- sp = candidate_table + 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);
- }
-
- if (sp->is_valid)
- {
- split_edges (i, trg, &el);
- sp->is_speculative = (el.nr_members) ? 1 : 0;
- if (sp->is_speculative && !flag_schedule_speculative)
- sp->is_valid = 0;
- }
-
- if (sp->is_valid)
- {
- 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]]);
- sp->update_bbs.first_member = &bblst_table[bblst_last];
- update_idx = 0;
- 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
- {
- for (k = 0; k < el.nr_members; k++)
- if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
- break;
-
- if (k >= el.nr_members)
- {
- bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
- update_idx++;
- }
-
- nxt_edge = NEXT_OUT (nxt_edge);
- }
- while (fst_edge != nxt_edge);
- }
- sp->update_bbs.nr_members = update_idx;
-
- }
- else
- {
- sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
-
- sp->is_speculative = 0;
- sp->src_prob = 0;
- }
- }
-}
-
-/* Print candidates info, for debugging purposes. Callable from debugger. */
-
-void
-debug_candidate (i)
- int i;
-{
- if (!candidate_table[i].is_valid)
- return;
-
- if (candidate_table[i].is_speculative)
- {
- int j;
- fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
-
- fprintf (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];
-
- fprintf (dump, " %d ", b);
- }
- fprintf (dump, "\n");
-
- fprintf (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];
-
- fprintf (dump, " %d ", b);
- }
- fprintf (dump, "\n");
- }
- else
- {
- fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
- }
-}
-
-/* Print candidates info, for debugging purposes. Callable from debugger. */
-
-void
-debug_candidates (trg)
- int trg;
-{
- int i;
-
- fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
- BB_TO_BLOCK (trg), trg);
- for (i = trg + 1; i < current_nr_blocks; i++)
- debug_candidate (i);
-}
-
-/* Functions for speculative scheduing. */
-
-/* Return 0 if x is a set of a register alive in the beginning of one
- of the split-blocks of src, otherwise return 1. */
-
-static int
-check_live_1 (src, x)
- int src;
- rtx x;
-{
- register int i;
- register int regno;
- register rtx reg = SET_DEST (x);
-
- if (reg == 0)
- return 1;
-
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || GET_CODE (reg) == STRICT_LOW_PART)
- reg = XEXP (reg, 0);
-
- if (GET_CODE (reg) == PARALLEL
- && GET_MODE (reg) == BLKmode)
- {
- register int i;
- for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- if (check_live_1 (src, XVECEXP (reg, 0, i)))
- return 1;
- return 0;
- }
-
- if (GET_CODE (reg) != REG)
- return 1;
-
- regno = REGNO (reg);
-
- if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
- {
- /* Global registers are assumed live. */
- return 0;
- }
- else
- {
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- /* Check for hard registers. */
- int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
- while (--j >= 0)
- {
- for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
- {
- int b = candidate_table[src].split_bbs.first_member[i];
-
- if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
- regno + j))
- {
- return 0;
- }
- }
- }
- }
- else
- {
- /* Check for psuedo registers. */
- for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
- {
- int b = candidate_table[src].split_bbs.first_member[i];
-
- if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
- {
- return 0;
- }
- }
- }
- }
-
- return 1;
-}
-
-/* If x is a set of a register R, mark that R is alive in the beginning
- of every update-block of src. */
-
-static void
-update_live_1 (src, x)
- int src;
- rtx x;
-{
- register int i;
- register int regno;
- register rtx reg = SET_DEST (x);
-
- if (reg == 0)
- return;
-
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || GET_CODE (reg) == STRICT_LOW_PART)
- reg = XEXP (reg, 0);
-
- if (GET_CODE (reg) == PARALLEL
- && GET_MODE (reg) == BLKmode)
- {
- register int i;
- for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- update_live_1 (src, XVECEXP (reg, 0, i));
- return;
- }
-
- if (GET_CODE (reg) != REG)
- return;
-
- /* Global registers are always live, so the code below does not apply
- to them. */
-
- regno = REGNO (reg);
-
- if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
- {
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
- while (--j >= 0)
- {
- for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
- {
- int b = candidate_table[src].update_bbs.first_member[i];
-
- SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
- regno + j);
- }
- }
- }
- else
- {
- for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
- {
- int b = candidate_table[src].update_bbs.first_member[i];
-
- SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
- }
- }
- }
-}
-
-/* Return 1 if insn can be speculatively moved from block src to trg,
- otherwise return 0. Called before first insertion of insn to
- ready-list or before the scheduling. */
-
-static int
-check_live (insn, src)
- rtx insn;
- int src;
-{
- /* Find the registers set by instruction. */
- if (GET_CODE (PATTERN (insn)) == SET
- || GET_CODE (PATTERN (insn)) == CLOBBER)
- return check_live_1 (src, PATTERN (insn));
- else if (GET_CODE (PATTERN (insn)) == PARALLEL)
- {
- int j;
- 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)
- && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
- return 0;
-
- return 1;
- }
-
- return 1;
-}
-
-/* Update the live registers info after insn was moved speculatively from
- block src to trg. */
-
-static void
-update_live (insn, src)
- rtx insn;
- int src;
-{
- /* Find the registers set by instruction. */
- if (GET_CODE (PATTERN (insn)) == SET
- || GET_CODE (PATTERN (insn)) == CLOBBER)
- update_live_1 (src, PATTERN (insn));
- else if (GET_CODE (PATTERN (insn)) == PARALLEL)
- {
- int j;
- 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)
- update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
- }
-}
-
-/* Exception Free Loads:
-
- We define five classes of speculative loads: IFREE, IRISKY,
- PFREE, PRISKY, and MFREE.
-
- IFREE loads are loads that are proved to be exception-free, just
- by examining the load insn. Examples for such loads are loads
- from TOC and loads of global data.
-
- IRISKY loads are loads that are proved to be exception-risky,
- just by examining the load insn. Examples for such loads are
- volatile loads and loads from shared memory.
-
- PFREE loads are loads for which we can prove, by examining other
- insns, that they are exception-free. Currently, this class consists
- of loads for which we are able to find a "similar load", either in
- the target block, or, if only one split-block exists, in that split
- block. Load2 is similar to load1 if both have same single base
- register. We identify only part of the similar loads, by finding
- an insn upon which both load1 and load2 have a DEF-USE dependence.
-
- PRISKY loads are loads for which we can prove, by examining other
- insns, that they are exception-risky. Currently we have two proofs for
- such loads. The first proof detects loads that are probably guarded by a
- test on the memory address. This proof is based on the
- backward and forward data dependence information for the region.
- Let load-insn be the examined load.
- Load-insn is PRISKY iff ALL the following hold:
-
- - insn1 is not in the same block as load-insn
- - there is a DEF-USE dependence chain (insn1, ..., load-insn)
- - test-insn is either a compare or a branch, not in the same block
- as load-insn
- - load-insn is reachable from test-insn
- - there is a DEF-USE dependence chain (insn1, ..., test-insn)
-
- This proof might fail when the compare and the load are fed
- by an insn not in the region. To solve this, we will add to this
- group all loads that have no input DEF-USE dependence.
-
- The second proof detects loads that are directly or indirectly
- fed by a speculative load. This proof is affected by the
- scheduling process. We will use the flag fed_by_spec_load.
- Initially, all insns have this flag reset. After a speculative
- motion of an insn, if insn is either a load, or marked as
- fed_by_spec_load, we will also mark as fed_by_spec_load every
- insn1 for which a DEF-USE dependence (insn, insn1) exists. A
- load which is fed_by_spec_load is also PRISKY.
-
- MFREE (maybe-free) loads are all the remaining loads. They may be
- exception-free, but we cannot prove it.
-
- Now, all loads in IFREE and PFREE classes are considered
- exception-free, while all loads in IRISKY and PRISKY classes are
- considered exception-risky. As for loads in the MFREE class,
- these are considered either exception-free or exception-risky,
- depending on whether we are pessimistic or optimistic. We have
- to take the pessimistic approach to assure the safety of
- speculative scheduling, but we can take the optimistic approach
- by invoking the -fsched_spec_load_dangerous option. */
-
-enum INSN_TRAP_CLASS
-{
- TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
- PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
-};
-
-#define WORST_CLASS(class1, class2) \
-((class1 > class2) ? class1 : class2)
-
-/* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
-#define IS_REACHABLE(bb_from, bb_to) \
-(bb_from == bb_to \
- || IS_RGN_ENTRY (bb_from) \
- || (bitset_member (ancestor_edges[bb_to], \
- EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
- edgeset_size)))
-
-/* Non-zero iff the address is comprised from at most 1 register. */
-#define CONST_BASED_ADDRESS_P(x) \
- (GET_CODE (x) == REG \
- || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
- || (GET_CODE (x) == LO_SUM)) \
- && (GET_CODE (XEXP (x, 0)) == CONST_INT \
- || GET_CODE (XEXP (x, 1)) == CONST_INT)))
-
-/* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
-
-static void
-set_spec_fed (load_insn)
- rtx load_insn;
-{
- rtx link;
-
- for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
- if (GET_MODE (link) == VOIDmode)
- FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
-} /* set_spec_fed */
-
-/* On the path from the insn to load_insn_bb, find a conditional
-branch depending on insn, that guards the speculative load. */
-
-static int
-find_conditional_protection (insn, load_insn_bb)
- rtx insn;
- int load_insn_bb;
-{
- rtx link;
-
- /* Iterate through DEF-USE forward dependences. */
- for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
- {
- rtx next = XEXP (link, 0);
- if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
- CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
- && IS_REACHABLE (INSN_BB (next), load_insn_bb)
- && load_insn_bb != INSN_BB (next)
- && GET_MODE (link) == VOIDmode
- && (GET_CODE (next) == JUMP_INSN
- || find_conditional_protection (next, load_insn_bb)))
- return 1;
- }
- return 0;
-} /* find_conditional_protection */
-
-/* Returns 1 if the same insn1 that participates in the computation
- of load_insn's address is feeding a conditional branch that is
- guarding on load_insn. This is true if we find a the two DEF-USE
- chains:
- insn1 -> ... -> conditional-branch
- insn1 -> ... -> load_insn,
- and if a flow path exist:
- insn1 -> ... -> conditional-branch -> ... -> load_insn,
- and if insn1 is on the path
- region-entry -> ... -> bb_trg -> ... load_insn.
-
- Locate insn1 by climbing on LOG_LINKS from load_insn.
- Locate the branch by following INSN_DEPEND from insn1. */
-
-static int
-is_conditionally_protected (load_insn, bb_src, bb_trg)
- rtx load_insn;
- int bb_src, bb_trg;
-{
- rtx link;
-
- for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
- {
- rtx insn1 = XEXP (link, 0);
-
- /* Must be a DEF-USE dependence upon non-branch. */
- if (GET_MODE (link) != VOIDmode
- || GET_CODE (insn1) == JUMP_INSN)
- continue;
-
- /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
- if (INSN_BB (insn1) == bb_src
- || (CONTAINING_RGN (BLOCK_NUM (insn1))
- != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
- || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
- && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
- continue;
-
- /* Now search for the conditional-branch. */
- if (find_conditional_protection (insn1, bb_src))
- return 1;
-
- /* Recursive step: search another insn1, "above" current insn1. */
- return is_conditionally_protected (insn1, bb_src, bb_trg);
- }
-
- /* The chain does not exist. */
- return 0;
-} /* is_conditionally_protected */
-
-/* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
- load_insn can move speculatively from bb_src to bb_trg. All the
- following must hold:
-
- (1) both loads have 1 base register (PFREE_CANDIDATEs).
- (2) load_insn and load1 have a def-use dependence upon
- the same insn 'insn1'.
- (3) either load2 is in bb_trg, or:
- - there's only one split-block, and
- - load1 is on the escape path, and
-
- From all these we can conclude that the two loads access memory
- addresses that differ at most by a constant, and hence if moving
- load_insn would cause an exception, it would have been caused by
- load2 anyhow. */
-
-static int
-is_pfree (load_insn, bb_src, bb_trg)
- rtx load_insn;
- int bb_src, bb_trg;
-{
- rtx back_link;
- register candidate *candp = candidate_table + bb_src;
-
- if (candp->split_bbs.nr_members != 1)
- /* Must have exactly one escape block. */
- return 0;
-
- for (back_link = LOG_LINKS (load_insn);
- back_link; back_link = XEXP (back_link, 1))
- {
- rtx insn1 = XEXP (back_link, 0);
-
- if (GET_MODE (back_link) == VOIDmode)
- {
- /* Found a DEF-USE dependence (insn1, load_insn). */
- rtx fore_link;
-
- for (fore_link = INSN_DEPEND (insn1);
- fore_link; fore_link = XEXP (fore_link, 1))
- {
- rtx insn2 = XEXP (fore_link, 0);
- if (GET_MODE (fore_link) == VOIDmode)
- {
- /* Found a DEF-USE dependence (insn1, insn2). */
- if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
- /* insn2 not guaranteed to be a 1 base reg load. */
- continue;
-
- if (INSN_BB (insn2) == bb_trg)
- /* insn2 is the similar load, in the target block. */
- return 1;
-
- if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
- /* insn2 is a similar load, in a split-block. */
- return 1;
- }
- }
- }
- }
-
- /* Couldn't find a similar load. */
- return 0;
-} /* is_pfree */
-
-/* Returns a class that insn with GET_DEST(insn)=x may belong to,
- as found by analyzing insn's expression. */
-
-static int
-may_trap_exp (x, is_store)
- rtx x;
- int is_store;
-{
- enum rtx_code code;
-
- if (x == 0)
- return TRAP_FREE;
- code = GET_CODE (x);
- if (is_store)
- {
- if (code == MEM)
- return TRAP_RISKY;
- else
- return TRAP_FREE;
- }
- if (code == MEM)
- {
- /* The insn uses memory: a volatile load. */
- if (MEM_VOLATILE_P (x))
- return IRISKY;
- /* An exception-free load. */
- if (!may_trap_p (x))
- return IFREE;
- /* A load with 1 base register, to be further checked. */
- if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
- return PFREE_CANDIDATE;
- /* No info on the load, to be further checked. */
- return PRISKY_CANDIDATE;
- }
- else
- {
- const char *fmt;
- int i, insn_class = TRAP_FREE;
-
- /* Neither store nor load, check if it may cause a trap. */
- if (may_trap_p (x))
- return TRAP_RISKY;
- /* Recursive step: walk the insn... */
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- int tmp_class = may_trap_exp (XEXP (x, i), is_store);
- insn_class = WORST_CLASS (insn_class, tmp_class);
- }
- else if (fmt[i] == 'E')
- {
- int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- {
- int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
- insn_class = WORST_CLASS (insn_class, tmp_class);
- if (insn_class == TRAP_RISKY || insn_class == IRISKY)
- break;
- }
- }
- if (insn_class == TRAP_RISKY || insn_class == IRISKY)
- break;
- }
- return insn_class;
- }
-}
-
-/* Classifies insn for the purpose of verifying that it can be
- moved speculatively, by examining it's patterns, returning:
- TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
- TRAP_FREE: non-load insn.
- IFREE: load from a globaly safe location.
- IRISKY: volatile load.
- PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
- being either PFREE or PRISKY. */
-
-static int
-haifa_classify_insn (insn)
- rtx insn;
-{
- rtx pat = PATTERN (insn);
- int tmp_class = TRAP_FREE;
- int insn_class = TRAP_FREE;
- enum rtx_code code;
-
- if (GET_CODE (pat) == PARALLEL)
- {
- int i, len = XVECLEN (pat, 0);
-
- for (i = len - 1; i >= 0; i--)
- {
- code = GET_CODE (XVECEXP (pat, 0, i));
- switch (code)
- {
- case CLOBBER:
- /* Test if it is a 'store'. */
- tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
- break;
- case SET:
- /* Test if it is a store. */
- tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
- if (tmp_class == TRAP_RISKY)
- break;
- /* Test if it is a load. */
- tmp_class =
- WORST_CLASS (tmp_class,
- may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
- break;
- case COND_EXEC:
- case TRAP_IF:
- tmp_class = TRAP_RISKY;
- break;
- default:;
- }
- insn_class = WORST_CLASS (insn_class, tmp_class);
- if (insn_class == TRAP_RISKY || insn_class == IRISKY)
- break;
- }
- }
- else
- {
- code = GET_CODE (pat);
- switch (code)
- {
- case CLOBBER:
- /* Test if it is a 'store'. */
- tmp_class = may_trap_exp (XEXP (pat, 0), 1);
- break;
- case SET:
- /* Test if it is a store. */
- tmp_class = may_trap_exp (SET_DEST (pat), 1);
- if (tmp_class == TRAP_RISKY)
- break;
- /* Test if it is a load. */
- tmp_class =
- WORST_CLASS (tmp_class,
- may_trap_exp (SET_SRC (pat), 0));
- break;
- case COND_EXEC:
- case TRAP_IF:
- tmp_class = TRAP_RISKY;
- break;
- default:;
- }
- insn_class = tmp_class;
- }
-
- return insn_class;
-}
-
-/* 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
- a compare on load_insn's address). */
-
-static int
-is_prisky (load_insn, bb_src, bb_trg)
- rtx load_insn;
- int bb_src, bb_trg;
-{
- if (FED_BY_SPEC_LOAD (load_insn))
- return 1;
-
- if (LOG_LINKS (load_insn) == NULL)
- /* Dependence may 'hide' out of the region. */
- return 1;
-
- if (is_conditionally_protected (load_insn, bb_src, bb_trg))
- return 1;
-
- return 0;
-}
-
-/* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
- Return 1 if insn is exception-free (and the motion is valid)
- and 0 otherwise. */
-
-static int
-is_exception_free (insn, bb_src, bb_trg)
- rtx insn;
- int bb_src, bb_trg;
-{
- int insn_class = haifa_classify_insn (insn);
-
- /* Handle non-load insns. */
- switch (insn_class)
- {
- case TRAP_FREE:
- return 1;
- case TRAP_RISKY:
- return 0;
- default:;
- }
-
- /* Handle loads. */
- if (!flag_schedule_speculative_load)
- return 0;
- IS_LOAD_INSN (insn) = 1;
- switch (insn_class)
- {
- case IFREE:
- return (1);
- case IRISKY:
- return 0;
- case PFREE_CANDIDATE:
- if (is_pfree (insn, bb_src, bb_trg))
- return 1;
- /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
- case PRISKY_CANDIDATE:
- if (!flag_schedule_speculative_load_dangerous
- || is_prisky (insn, bb_src, bb_trg))
- return 0;
- break;
- default:;
- }
-
- return flag_schedule_speculative_load_dangerous;
-}
-
-/* Process an insn's memory dependencies. There are four kinds of
- dependencies:
-
- (0) read dependence: read follows read
- (1) true dependence: read follows write
- (2) anti dependence: write follows read
- (3) output dependence: write follows write
-
- We are careful to build only dependencies which actually exist, and
- use transitivity to avoid building too many links. */
-\f
-/* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
- otherwise. */
-
-HAIFA_INLINE static char
-find_insn_mem_list (insn, x, list, list1)
- rtx insn, x;
- rtx list, list1;
-{
- while (list)
- {
- if (XEXP (list, 0) == insn
- && XEXP (list1, 0) == x)
- return 1;
- list = XEXP (list, 1);
- list1 = XEXP (list1, 1);
- }
- return 0;
-}
-
-/* Compute the function units used by INSN. This caches the value
- returned by function_units_used. A function unit is encoded as the
- unit number if the value is non-negative and the compliment of a
- mask if the value is negative. A function unit index is the
- non-negative encoding. */
-
-HAIFA_INLINE static int
-insn_unit (insn)
- rtx insn;
-{
- register int unit = INSN_UNIT (insn);
-
- if (unit == 0)
- {
- recog_memoized (insn);
-
- /* A USE insn, or something else we don't need to understand.
- We can't pass these directly to function_units_used because it will
- trigger a fatal error for unrecognizable insns. */
- if (INSN_CODE (insn) < 0)
- unit = -1;
- else
- {
- unit = function_units_used (insn);
- /* Increment non-negative values so we can cache zero. */
- if (unit >= 0)
- unit++;
- }
- /* We only cache 16 bits of the result, so if the value is out of
- range, don't cache it. */
- if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
- || unit >= 0
- || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
- INSN_UNIT (insn) = unit;
- }
- return (unit > 0 ? unit - 1 : unit);
-}
-
-/* Compute the blockage range for executing INSN on UNIT. This caches
- the value returned by the blockage_range_function for the unit.
- These values are encoded in an int where the upper half gives the
- minimum value and the lower half gives the maximum value. */
-
-HAIFA_INLINE static unsigned int
-blockage_range (unit, insn)
- int unit;
- rtx insn;
-{
- unsigned int blockage = INSN_BLOCKAGE (insn);
- unsigned int range;
-
- if ((int) UNIT_BLOCKED (blockage) != unit + 1)
- {
- range = function_units[unit].blockage_range_function (insn);
- /* We only cache the blockage range for one unit and then only if
- the values fit. */
- if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
- INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
- }
- else
- range = BLOCKAGE_RANGE (blockage);
-
- return range;
-}
-
-/* A vector indexed by function unit instance giving the last insn to use
- the unit. The value of the function unit instance index for unit U
- instance I is (U + I * FUNCTION_UNITS_SIZE). */
-static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
-
-/* A vector indexed by function unit instance giving the minimum time when
- the unit will unblock based on the maximum blockage cost. */
-static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
-
-/* A vector indexed by function unit number giving the number of insns
- that remain to use the unit. */
-static int unit_n_insns[FUNCTION_UNITS_SIZE];
-
-/* Reset the function unit state to the null state. */
-
-static void
-clear_units ()
-{
- bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
- bzero ((char *) unit_tick, sizeof (unit_tick));
- bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
-}
-
-/* Return the issue-delay of an insn. */
-
-HAIFA_INLINE static int
-insn_issue_delay (insn)
- rtx insn;
-{
- int i, delay = 0;
- int unit = insn_unit (insn);
-
- /* Efficiency note: in fact, we are working 'hard' to compute a
- value that was available in md file, and is not available in
- function_units[] structure. It would be nice to have this
- value there, too. */
- if (unit >= 0)
- {
- if (function_units[unit].blockage_range_function &&
- function_units[unit].blockage_function)
- delay = function_units[unit].blockage_function (insn, insn);
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0 && function_units[i].blockage_range_function
- && function_units[i].blockage_function)
- delay = MAX (delay, function_units[i].blockage_function (insn, insn));
-
- return delay;
-}
-
-/* Return the actual hazard cost of executing INSN on the unit UNIT,
- instance INSTANCE at time CLOCK if the previous actual hazard cost
- was COST. */
-
-HAIFA_INLINE static int
-actual_hazard_this_instance (unit, instance, insn, clock, cost)
- int unit, instance, clock, cost;
- rtx insn;
-{
- int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
-
- if (tick - clock > cost)
- {
- /* The scheduler is operating forward, so unit's last insn is the
- executing insn and INSN is the candidate insn. We want a
- more exact measure of the blockage if we execute INSN at CLOCK
- given when we committed the execution of the unit's last insn.
-
- The blockage value is given by either the unit's max blockage
- constant, blockage range function, or blockage function. Use
- the most exact form for the given unit. */
-
- if (function_units[unit].blockage_range_function)
- {
- if (function_units[unit].blockage_function)
- tick += (function_units[unit].blockage_function
- (unit_last_insn[instance], insn)
- - function_units[unit].max_blockage);
- else
- tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
- - function_units[unit].max_blockage);
- }
- if (tick - clock > cost)
- cost = tick - clock;
- }
- return cost;
-}
-
-/* Record INSN as having begun execution on the units encoded by UNIT at
- time CLOCK. */
-
-HAIFA_INLINE static void
-schedule_unit (unit, insn, clock)
- int unit, clock;
- rtx insn;
-{
- int i;
-
- if (unit >= 0)
- {
- int instance = unit;
-#if MAX_MULTIPLICITY > 1
- /* Find the first free instance of the function unit and use that
- one. We assume that one is free. */
- for (i = function_units[unit].multiplicity - 1; i > 0; i--)
- {
- if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
- break;
- instance += FUNCTION_UNITS_SIZE;
- }
-#endif
- unit_last_insn[instance] = insn;
- unit_tick[instance] = (clock + function_units[unit].max_blockage);
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0)
- schedule_unit (i, insn, clock);
-}
-
-/* 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. */
-
-HAIFA_INLINE static int
-actual_hazard (unit, insn, clock, cost)
- int unit, clock, cost;
- rtx insn;
-{
- int i;
-
- if (unit >= 0)
- {
- /* Find the instance of the function unit with the minimum hazard. */
- int instance = unit;
- int best_cost = actual_hazard_this_instance (unit, instance, insn,
- clock, cost);
-#if MAX_MULTIPLICITY > 1
- int this_cost;
-
- if (best_cost > cost)
- {
- for (i = function_units[unit].multiplicity - 1; i > 0; i--)
- {
- instance += FUNCTION_UNITS_SIZE;
- this_cost = actual_hazard_this_instance (unit, instance, insn,
- clock, cost);
- if (this_cost < best_cost)
- {
- best_cost = this_cost;
- if (this_cost <= cost)
- break;
- }
- }
- }
-#endif
- cost = MAX (cost, best_cost);
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0)
- cost = actual_hazard (i, insn, clock, cost);
-
- return cost;
-}
-
-/* Return the potential hazard cost of executing an instruction on the
- units encoded by UNIT if the previous potential hazard cost was COST.
- An insn with a large blockage time is chosen in preference to one
- with a smaller time; an insn that uses a unit that is more likely
- 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. */
-
-HAIFA_INLINE static int
-potential_hazard (unit, insn, cost)
- int unit, cost;
- rtx insn;
-{
- int i, ncost;
- unsigned int minb, maxb;
-
- if (unit >= 0)
- {
- minb = maxb = function_units[unit].max_blockage;
- if (maxb > 1)
- {
- if (function_units[unit].blockage_range_function)
- {
- maxb = minb = blockage_range (unit, insn);
- maxb = MAX_BLOCKAGE_COST (maxb);
- minb = MIN_BLOCKAGE_COST (minb);
- }
-
- if (maxb > 1)
- {
- /* Make the number of instructions left dominate. Make the
- minimum delay dominate the maximum delay. If all these
- are the same, use the unit number to add an arbitrary
- ordering. Other terms can be added. */
- ncost = minb * 0x40 + maxb;
- ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
- if (ncost > cost)
- cost = ncost;
- }
- }
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0)
- cost = potential_hazard (i, insn, cost);
-
- return cost;
-}
-
-/* Compute cost of executing INSN given the dependence LINK on the insn USED.
- This is the number of cycles between instruction issue and
- instruction results. */
-
-HAIFA_INLINE static int
-insn_cost (insn, link, used)
- rtx insn, link, used;
-{
- register int cost = INSN_COST (insn);
-
- if (cost == 0)
- {
- recog_memoized (insn);
-
- /* A USE insn, or something else we don't need to understand.
- We can't pass these directly to result_ready_cost because it will
- trigger a fatal error for unrecognizable insns. */
- if (INSN_CODE (insn) < 0)
- {
- INSN_COST (insn) = 1;
- return 1;
- }
- else
- {
- cost = result_ready_cost (insn);
-
- if (cost < 1)
- cost = 1;
-
- INSN_COST (insn) = cost;
- }
- }
-
- /* In this case estimate cost without caring how insn is used. */
- if (link == 0 && used == 0)
- return cost;
-
- /* A USE insn should never require the value used to be computed. This
- allows the computation of a function's result and parameter values to
- overlap the return and call. */
- recog_memoized (used);
- if (INSN_CODE (used) < 0)
- LINK_COST_FREE (link) = 1;
-
- /* If some dependencies vary the cost, compute the adjustment. Most
- commonly, the adjustment is complete: either the cost is ignored
- (in the case of an output- or anti-dependence), or the cost is
- unchanged. These values are cached in the link as LINK_COST_FREE
- and LINK_COST_ZERO. */
-
- if (LINK_COST_FREE (link))
- cost = 0;
-#ifdef ADJUST_COST
- else if (!LINK_COST_ZERO (link))
- {
- int ncost = cost;
-
- ADJUST_COST (used, link, insn, ncost);
- if (ncost < 1)
- {
- LINK_COST_FREE (link) = 1;
- ncost = 0;
- }
- if (cost == ncost)
- LINK_COST_ZERO (link) = 1;
- cost = ncost;
- }
-#endif
- return cost;
-}
-
-/* Compute the priority number for INSN. */
-
-static int
-priority (insn)
- rtx insn;
-{
- int this_priority;
- rtx link;
-
- if (! INSN_P (insn))
- return 0;
-
- if ((this_priority = INSN_PRIORITY (insn)) == 0)
- {
- if (INSN_DEPEND (insn) == 0)
- this_priority = insn_cost (insn, 0, 0);
- else
- for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
- {
- rtx next;
- int next_priority;
-
- if (RTX_INTEGRATED_P (link))
- continue;
-
- next = XEXP (link, 0);
-
- /* Critical path is meaningful in block boundaries only. */
- if (BLOCK_NUM (next) != BLOCK_NUM (insn))
- continue;
-
- next_priority = insn_cost (insn, link, next) + priority (next);
- if (next_priority > this_priority)
- this_priority = next_priority;
- }
- INSN_PRIORITY (insn) = this_priority;
- }
- return this_priority;
-}
-\f
-/* 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. */
-
-static void
-free_pending_lists ()
-{
- int bb;
-
- for (bb = 0; bb < current_nr_blocks; bb++)
- {
- free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
- free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
- free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
- free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
- }
-}
-
-/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
- The MEM is a memory reference contained within INSN, which we are saving
- so that we can do memory aliasing on it. */
-
-static void
-add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
- struct deps *deps;
- rtx *insn_list, *mem_list, insn, mem;
-{
- register rtx link;
-
- link = alloc_INSN_LIST (insn, *insn_list);
- *insn_list = link;
-
- link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
- *mem_list = link;
-
- deps->pending_lists_length++;
-}
-\f
-/* Make a dependency between every memory reference on the pending lists
- and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
- the read list. */
-
-static void
-flush_pending_lists (deps, insn, only_write)
- struct deps *deps;
- rtx insn;
- int only_write;
-{
- rtx u;
- rtx link;
-
- while (deps->pending_read_insns && ! only_write)
- {
- add_dependence (insn, XEXP (deps->pending_read_insns, 0),
- REG_DEP_ANTI);
-
- link = deps->pending_read_insns;
- deps->pending_read_insns = XEXP (deps->pending_read_insns, 1);
- free_INSN_LIST_node (link);
-
- link = deps->pending_read_mems;
- deps->pending_read_mems = XEXP (deps->pending_read_mems, 1);
- free_EXPR_LIST_node (link);
- }
- while (deps->pending_write_insns)
- {
- add_dependence (insn, XEXP (deps->pending_write_insns, 0),
- REG_DEP_ANTI);
-
- link = deps->pending_write_insns;
- deps->pending_write_insns = XEXP (deps->pending_write_insns, 1);
- free_INSN_LIST_node (link);
-
- link = deps->pending_write_mems;
- deps->pending_write_mems = XEXP (deps->pending_write_mems, 1);
- free_EXPR_LIST_node (link);
- }
- deps->pending_lists_length = 0;
-
- /* last_pending_memory_flush is now a list of insns. */
- for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- free_INSN_LIST_list (&deps->last_pending_memory_flush);
- deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
-}
-
-/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
- rtx, X, creating all dependencies generated by the write to the
- destination of X, and reads of everything mentioned. */
-
-static void
-sched_analyze_1 (deps, x, insn)
- struct deps *deps;
- rtx x;
- rtx insn;
-{
- register int regno;
- register rtx dest = XEXP (x, 0);
- enum rtx_code code = GET_CODE (x);
-
- if (dest == 0)
- return;
-
- if (GET_CODE (dest) == PARALLEL
- && GET_MODE (dest) == BLKmode)
- {
- register int i;
- for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
- sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
- if (GET_CODE (x) == SET)
- sched_analyze_2 (deps, SET_SRC (x), insn);
- return;
- }
-
- while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
- || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
- {
- if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
- {
- /* The second and third arguments are values read by this insn. */
- sched_analyze_2 (deps, XEXP (dest, 1), insn);
- sched_analyze_2 (deps, XEXP (dest, 2), insn);
- }
- dest = XEXP (dest, 0);
- }
-
- if (GET_CODE (dest) == REG)
- {
- register int i;
-
- regno = REGNO (dest);
-
- /* A hard reg in a wide mode may really be multiple registers.
- If so, mark all of them just like the first. */
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
- while (--i >= 0)
- {
- int r = regno + i;
- rtx u;
-
- for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
-
- /* Clobbers need not be ordered with respect to one
- another, but sets must be ordered with respect to a
- pending clobber. */
- if (code == SET)
- {
- free_INSN_LIST_list (&deps->reg_last_uses[r]);
- for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
- SET_REGNO_REG_SET (reg_pending_sets, r);
- }
- else
- SET_REGNO_REG_SET (reg_pending_clobbers, r);
-
- /* Function calls clobber all call_used regs. */
- if (global_regs[r] || (code == SET && call_used_regs[r]))
- for (u = deps->last_function_call; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- }
- }
- else
- {
- rtx u;
-
- for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
-
- if (code == SET)
- {
- free_INSN_LIST_list (&deps->reg_last_uses[regno]);
- for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
- SET_REGNO_REG_SET (reg_pending_sets, regno);
- }
- else
- SET_REGNO_REG_SET (reg_pending_clobbers, regno);
-
- /* Pseudos that are REG_EQUIV to something may be replaced
- by that during reloading. We need only add dependencies for
- the address in the REG_EQUIV note. */
- if (!reload_completed
- && reg_known_equiv_p[regno]
- && GET_CODE (reg_known_value[regno]) == MEM)
- sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
-
- /* Don't let it cross a call after scheduling if it doesn't
- already cross one. */
-
- if (REG_N_CALLS_CROSSED (regno) == 0)
- for (u = deps->last_function_call; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- }
- }
- else if (GET_CODE (dest) == MEM)
- {
- /* Writing memory. */
-
- if (deps->pending_lists_length > 32)
- {
- /* Flush all pending reads and writes to prevent the pending lists
- from getting any larger. Insn scheduling runs too slowly when
- these lists get long. The number 32 was chosen because it
- seems like a reasonable number. When compiling GCC with itself,
- this flush occurs 8 times for sparc, and 10 times for m88k using
- the number 32. */
- flush_pending_lists (deps, insn, 0);
- }
- else
- {
- rtx u;
- rtx pending, pending_mem;
-
- pending = deps->pending_read_insns;
- pending_mem = deps->pending_read_mems;
- while (pending)
- {
- if (anti_dependence (XEXP (pending_mem, 0), dest))
- add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
-
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
- }
-
- pending = deps->pending_write_insns;
- pending_mem = deps->pending_write_mems;
- while (pending)
- {
- if (output_dependence (XEXP (pending_mem, 0), dest))
- add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
-
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
- }
-
- for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- add_insn_mem_dependence (deps, &deps->pending_write_insns,
- &deps->pending_write_mems, insn, dest);
- }
- sched_analyze_2 (deps, XEXP (dest, 0), insn);
- }
-
- /* Analyze reads. */
- if (GET_CODE (x) == SET)
- sched_analyze_2 (deps, SET_SRC (x), insn);
-}
-
-/* Analyze the uses of memory and registers in rtx X in INSN. */
-
-static void
-sched_analyze_2 (deps, x, insn)
- struct deps *deps;
- rtx x;
- rtx insn;
-{
- register int i;
- register int j;
- register enum rtx_code code;
- register const char *fmt;
-
- if (x == 0)
- return;
-
- code = GET_CODE (x);
-
- switch (code)
- {
- case CONST_INT:
- case CONST_DOUBLE:
- case SYMBOL_REF:
- case CONST:
- case LABEL_REF:
- /* Ignore constants. Note that we must handle CONST_DOUBLE here
- because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
- this does not mean that this insn is using cc0. */
- return;
-
-#ifdef HAVE_cc0
- case CC0:
- /* User of CC0 depends on immediately preceding insn. */
- set_sched_group_p (insn);
- return;
-#endif
-
- case REG:
- {
- rtx u;
- int regno = REGNO (x);
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- int i;
-
- i = HARD_REGNO_NREGS (regno, GET_MODE (x));
- while (--i >= 0)
- {
- int r = regno + i;
- deps->reg_last_uses[r]
- = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
-
- for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- /* ??? This should never happen. */
- for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- if (call_used_regs[r] || global_regs[r])
- /* Function calls clobber all call_used regs. */
- for (u = deps->last_function_call; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- }
- }
- else
- {
- deps->reg_last_uses[regno]
- = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
-
- for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- /* ??? This should never happen. */
- for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- /* Pseudos that are REG_EQUIV to something may be replaced
- by that during reloading. We need only add dependencies for
- the address in the REG_EQUIV note. */
- if (!reload_completed
- && reg_known_equiv_p[regno]
- && GET_CODE (reg_known_value[regno]) == MEM)
- sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
-
- /* If the register does not already cross any calls, then add this
- insn to the sched_before_next_call list so that it will still
- not cross calls after scheduling. */
- if (REG_N_CALLS_CROSSED (regno) == 0)
- add_dependence (deps->sched_before_next_call, insn,
- REG_DEP_ANTI);
- }
- return;
- }
-
- case MEM:
- {
- /* Reading memory. */
- rtx u;
- rtx pending, pending_mem;
-
- pending = deps->pending_read_insns;
- pending_mem = deps->pending_read_mems;
- while (pending)
- {
- if (read_dependence (XEXP (pending_mem, 0), x))
- add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
-
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
- }
-
- pending = deps->pending_write_insns;
- pending_mem = deps->pending_write_mems;
- while (pending)
- {
- if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
- x, rtx_varies_p))
- add_dependence (insn, XEXP (pending, 0), 0);
-
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
- }
-
- for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- /* Always add these dependencies to pending_reads, since
- this insn may be followed by a write. */
- add_insn_mem_dependence (deps, &deps->pending_read_insns,
- &deps->pending_read_mems, insn, x);
-
- /* Take advantage of tail recursion here. */
- sched_analyze_2 (deps, XEXP (x, 0), insn);
- return;
- }
-
- /* Force pending stores to memory in case a trap handler needs them. */
- case TRAP_IF:
- flush_pending_lists (deps, insn, 1);
- break;
-
- case ASM_OPERANDS:
- case ASM_INPUT:
- case UNSPEC_VOLATILE:
- {
- rtx u;
-
- /* Traditional and volatile asm instructions must be considered to use
- and clobber all hard registers, all pseudo-registers and all of
- memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
-
- Consider for instance a volatile asm that changes the fpu rounding
- mode. An insn should not be moved across this even if it only uses
- pseudo-regs because it might give an incorrectly rounded result. */
- if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
- {
- int max_reg = max_reg_num ();
- for (i = 0; i < max_reg; i++)
- {
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
- }
- reg_pending_sets_all = 1;
-
- flush_pending_lists (deps, insn, 0);
- }
-
- /* For all ASM_OPERANDS, we must traverse the vector of input operands.
- We can not just fall through here since then we would be confused
- by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
- traditional asms unlike their normal usage. */
-
- if (code == ASM_OPERANDS)
- {
- for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
- sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
- return;
- }
- break;
- }
-
- case PRE_DEC:
- case POST_DEC:
- case PRE_INC:
- case POST_INC:
- /* These both read and modify the result. We must handle them as writes
- to get proper dependencies for following instructions. We must handle
- them as reads to get proper dependencies from this to previous
- instructions. Thus we need to pass them to both sched_analyze_1
- and sched_analyze_2. We must call sched_analyze_2 first in order
- to get the proper antecedent for the read. */
- sched_analyze_2 (deps, XEXP (x, 0), insn);
- sched_analyze_1 (deps, x, insn);
- return;
-
- case POST_MODIFY:
- case PRE_MODIFY:
- /* op0 = op0 + op1 */
- sched_analyze_2 (deps, XEXP (x, 0), insn);
- sched_analyze_2 (deps, XEXP (x, 1), insn);
- sched_analyze_1 (deps, x, insn);
- return;
-
- default:
- break;
- }
-
- /* Other cases: walk the insn. */
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- sched_analyze_2 (deps, XEXP (x, i), insn);
- else if (fmt[i] == 'E')
- for (j = 0; j < XVECLEN (x, i); j++)
- sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
- }
-}
-
-/* Analyze an INSN with pattern X to find all dependencies. */
-
-static void
-sched_analyze_insn (deps, x, insn, loop_notes)
- struct deps *deps;
- rtx x, insn;
- rtx loop_notes;
-{
- register RTX_CODE code = GET_CODE (x);
- rtx link;
- int maxreg = max_reg_num ();
- int i;
-
- if (code == COND_EXEC)
- {
- sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
-
- /* ??? Should be recording conditions so we reduce the number of
- false dependancies. */
- x = COND_EXEC_CODE (x);
- code = GET_CODE (x);
- }
- if (code == SET || code == CLOBBER)
- sched_analyze_1 (deps, x, insn);
- else if (code == PARALLEL)
- {
- register int i;
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
- {
- rtx sub = XVECEXP (x, 0, i);
- code = GET_CODE (sub);
-
- if (code == COND_EXEC)
- {
- sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
- sub = COND_EXEC_CODE (sub);
- code = GET_CODE (sub);
- }
- if (code == SET || code == CLOBBER)
- sched_analyze_1 (deps, sub, insn);
- else
- sched_analyze_2 (deps, sub, insn);
- }
- }
- else
- sched_analyze_2 (deps, x, insn);
-
- /* Mark registers CLOBBERED or used by called function. */
- if (GET_CODE (insn) == CALL_INSN)
- for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
- {
- if (GET_CODE (XEXP (link, 0)) == CLOBBER)
- sched_analyze_1 (deps, XEXP (link, 0), insn);
- else
- sched_analyze_2 (deps, XEXP (link, 0), insn);
- }
-
- /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
- block, then we must be sure that no instructions are scheduled across it.
- Otherwise, the reg_n_refs info (which depends on loop_depth) would
- become incorrect. */
-
- if (loop_notes)
- {
- int max_reg = max_reg_num ();
- int schedule_barrier_found = 0;
- rtx link;
-
- /* Update loop_notes with any notes from this insn. Also determine
- if any of the notes on the list correspond to instruction scheduling
- barriers (loop, eh & setjmp notes, but not range notes. */
- link = loop_notes;
- while (XEXP (link, 1))
- {
- if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
- || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
- || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
- || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
- || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
- schedule_barrier_found = 1;
-
- link = XEXP (link, 1);
- }
- XEXP (link, 1) = REG_NOTES (insn);
- REG_NOTES (insn) = loop_notes;
-
- /* Add dependencies if a scheduling barrier was found. */
- if (schedule_barrier_found)
- {
- for (i = 0; i < max_reg; i++)
- {
- rtx u;
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
- }
- reg_pending_sets_all = 1;
-
- flush_pending_lists (deps, insn, 0);
- }
-
- }
-
- /* Accumulate clobbers until the next set so that it will be output dependent
- on all of them. At the next set we can clear the clobber list, since
- subsequent sets will be output dependent on it. */
- EXECUTE_IF_SET_IN_REG_SET
- (reg_pending_sets, 0, i,
- {
- free_INSN_LIST_list (&deps->reg_last_sets[i]);
- free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
- deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
- });
- EXECUTE_IF_SET_IN_REG_SET
- (reg_pending_clobbers, 0, i,
- {
- deps->reg_last_clobbers[i]
- = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
- });
- CLEAR_REG_SET (reg_pending_sets);
- CLEAR_REG_SET (reg_pending_clobbers);
-
- if (reg_pending_sets_all)
- {
- for (i = 0; i < maxreg; i++)
- {
- free_INSN_LIST_list (&deps->reg_last_sets[i]);
- free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
- deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
- }
-
- reg_pending_sets_all = 0;
- }
-
- /* If a post-call group is still open, see if it should remain so.
- This insn must be a simple move of a hard reg to a pseudo or
- vice-versa.
-
- We must avoid moving these insns for correctness on
- SMALL_REGISTER_CLASS machines, and for special registers like
- PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
- hard regs for all targets. */
-
- if (deps->in_post_call_group_p)
- {
- rtx tmp, set = single_set (insn);
- int src_regno, dest_regno;
-
- if (set == NULL)
- goto end_call_group;
-
- tmp = SET_DEST (set);
- if (GET_CODE (tmp) == SUBREG)
- tmp = SUBREG_REG (tmp);
- if (GET_CODE (tmp) == REG)
- dest_regno = REGNO (tmp);
- else
- goto end_call_group;
-
- tmp = SET_SRC (set);
- if (GET_CODE (tmp) == SUBREG)
- tmp = SUBREG_REG (tmp);
- if (GET_CODE (tmp) == REG)
- src_regno = REGNO (tmp);
- else
- goto end_call_group;
-
- if (src_regno < FIRST_PSEUDO_REGISTER
- || dest_regno < FIRST_PSEUDO_REGISTER)
- {
- set_sched_group_p (insn);
- CANT_MOVE (insn) = 1;
- }
- else
- {
- end_call_group:
- deps->in_post_call_group_p = 0;
- }
- }
-}
-
-/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
- for every dependency. */
-
-static void
-sched_analyze (deps, head, tail)
- struct deps *deps;
- rtx head, tail;
-{
- register rtx insn;
- register rtx u;
- rtx loop_notes = 0;
-
- for (insn = head;; insn = NEXT_INSN (insn))
- {
- if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
- {
- /* Clear out the stale LOG_LINKS from flow. */
- free_INSN_LIST_list (&LOG_LINKS (insn));
-
- /* Clear out stale SCHED_GROUP_P. */
- SCHED_GROUP_P (insn) = 0;
-
- /* Make each JUMP_INSN a scheduling barrier for memory
- references. */
- if (GET_CODE (insn) == JUMP_INSN)
- deps->last_pending_memory_flush
- = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
- sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
- loop_notes = 0;
- }
- else if (GET_CODE (insn) == CALL_INSN)
- {
- rtx x;
- register int i;
-
- /* Clear out stale SCHED_GROUP_P. */
- SCHED_GROUP_P (insn) = 0;
-
- CANT_MOVE (insn) = 1;
-
- /* Clear out the stale LOG_LINKS from flow. */
- free_INSN_LIST_list (&LOG_LINKS (insn));
-
- /* Any instruction using a hard register which may get clobbered
- by a call needs to be marked as dependent on this call.
- This prevents a use of a hard return reg from being moved
- past a void call (i.e. it does not explicitly set the hard
- return reg). */
-
- /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
- all registers, not just hard registers, may be clobbered by this
- call. */
-
- /* Insn, being a CALL_INSN, magically depends on
- `last_function_call' already. */
-
- if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
- && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
- {
- int max_reg = max_reg_num ();
- for (i = 0; i < max_reg; i++)
- {
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
-
- for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
- }
- reg_pending_sets_all = 1;
-
- /* Add a pair of REG_SAVE_NOTEs 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) = alloc_EXPR_LIST (REG_SAVE_NOTE,
- GEN_INT (0),
- REG_NOTES (insn));
- REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
- GEN_INT (NOTE_INSN_SETJMP),
- REG_NOTES (insn));
- }
- else
- {
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (call_used_regs[i] || global_regs[i])
- {
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- SET_REGNO_REG_SET (reg_pending_clobbers, i);
- }
- }
-
- /* For each insn which shouldn't cross a call, add a dependence
- between that insn and this call insn. */
- x = LOG_LINKS (deps->sched_before_next_call);
- while (x)
- {
- add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
- x = XEXP (x, 1);
- }
- free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call));
-
- sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
- loop_notes = 0;
-
- /* In the absence of interprocedural alias analysis, we must flush
- all pending reads and writes, and start new dependencies starting
- from here. But only flush writes for constant calls (which may
- be passed a pointer to something we haven't written yet). */
- flush_pending_lists (deps, insn, CONST_CALL_P (insn));
-
- /* Depend this function call (actually, the user of this
- function call) on all hard register clobberage. */
-
- /* last_function_call is now a list of insns. */
- free_INSN_LIST_list (&deps->last_function_call);
- deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
-
- /* Before reload, begin a post-call group, so as to keep the
- lifetimes of hard registers correct. */
- if (! reload_completed)
- deps->in_post_call_group_p = 1;
- }
-
- /* See comments on reemit_notes as to why we do this.
- ??? Actually, the reemit_notes just say what is done, not why. */
-
- else if (GET_CODE (insn) == NOTE
- && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
- {
- loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
- loop_notes);
- loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
- GEN_INT (NOTE_LINE_NUMBER (insn)),
- loop_notes);
- }
- else if (GET_CODE (insn) == NOTE
- && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
- || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
- && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
- {
- rtx rtx_region;
-
- if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
- rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
- else
- rtx_region = GEN_INT (0);
-
- loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
- rtx_region,
- loop_notes);
- loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
- GEN_INT (NOTE_LINE_NUMBER (insn)),
- loop_notes);
- CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
- }
-
- if (insn == tail)
- return;
- }
- abort ();
-}
-\f
-/* Macros and functions for keeping the priority queue sorted, and
- dealing with queueing and dequeueing of instructions. */
-
-#define SCHED_SORT(READY, N_READY) \
-do { if ((N_READY) == 2) \
- swap_sort (READY, N_READY); \
- else if ((N_READY) > 2) \
- qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
-while (0)
-
-/* Returns a positive value if x is preferred; returns a negative value if
- y is preferred. Should never return 0, since that will make the sort
- unstable. */
-
-static int
-rank_for_schedule (x, y)
- const PTR x;
- const PTR y;
-{
- rtx tmp = *(const rtx *) y;
- rtx tmp2 = *(const rtx *) x;
- rtx link;
- int tmp_class, tmp2_class, depend_count1, depend_count2;
- int val, priority_val, spec_val, prob_val, weight_val;
-
- /* Prefer insn with higher priority. */
- priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
- if (priority_val)
- return priority_val;
-
- /* Prefer an insn with smaller contribution to registers-pressure. */
- if (!reload_completed &&
- (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
- return (weight_val);
-
- /* Some comparison make sense in interblock scheduling only. */
- if (INSN_BB (tmp) != INSN_BB (tmp2))
- {
- /* Prefer an inblock motion on an interblock motion. */
- if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
- return 1;
- if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
- return -1;
-
- /* Prefer a useful motion on a speculative one. */
- if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
- return (spec_val);
-
- /* Prefer a more probable (speculative) insn. */
- prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
- if (prob_val)
- return (prob_val);
- }
-
- /* Compare insns based on their relation to the last-scheduled-insn. */
- if (last_scheduled_insn)
- {
- /* Classify the instructions into three classes:
- 1) Data dependent on last schedule insn.
- 2) Anti/Output dependent on last scheduled insn.
- 3) Independent of last scheduled insn, or has latency of one.
- Choose the insn from the highest numbered class if different. */
- link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
- if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
- tmp_class = 3;
- else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
- tmp_class = 1;
- else
- tmp_class = 2;
-
- link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
- if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
- tmp2_class = 3;
- else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
- tmp2_class = 1;
- else
- tmp2_class = 2;
-
- if ((val = tmp2_class - tmp_class))
- 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. */
- return INSN_LUID (tmp) - INSN_LUID (tmp2);
-}
-
-/* Resort the array A in which only element at index N may be out of order. */
-
-HAIFA_INLINE static void
-swap_sort (a, n)
- rtx *a;
- int n;
-{
- rtx insn = a[n - 1];
- int i = n - 2;
-
- while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
- {
- a[i + 1] = a[i];
- i -= 1;
- }
- a[i + 1] = insn;
-}
-
-static int max_priority;
-
-/* Add INSN to the insn queue so that it can be executed at least
- N_CYCLES after the currently executing insn. Preserve insns
- chain for debugging purposes. */
-
-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 = alloc_INSN_LIST (insn, insn_queue[next_q]);
- insn_queue[next_q] = link;
- q_size += 1;
-
- if (sched_verbose >= 2)
- {
- fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
-
- if (INSN_BB (insn) != target_bb)
- fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
-
- fprintf (dump, "queued for %d cycles.\n", n_cycles);
- }
-
-}
-
-/* PREV is an insn that is ready to execute. Adjust its priority if that
- will help shorten or lengthen register lifetimes as appropriate. Also
- provide a hook for the target to tweek itself. */
-
-HAIFA_INLINE static void
-adjust_priority (prev)
- rtx prev ATTRIBUTE_UNUSED;
-{
- /* ??? There used to be code here to try and estimate how an insn
- affected register lifetimes, but it did it by looking at REG_DEAD
- notes, which we removed in schedule_region. Nor did it try to
- take into account register pressure or anything useful like that.
-
- Revisit when we have a machine model to work with and not before. */
-
-#ifdef ADJUST_PRIORITY
- ADJUST_PRIORITY (prev);
-#endif
-}
-
-/* Clock at which the previous instruction was issued. */
-static int last_clock_var;
-
-/* INSN is the "currently executing insn". Launch each insn which was
- waiting on INSN. READY is a vector of insns which are ready to fire.
- N_READY is the number of elements in READY. CLOCK is the current
- cycle. */
-
-static int
-schedule_insn (insn, ready, n_ready, clock)
- rtx insn;
- rtx *ready;
- int n_ready;
- int clock;
-{
- rtx link;
- int unit;
-
- unit = insn_unit (insn);
-
- if (sched_verbose >= 2)
- {
- fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
- INSN_UID (insn));
- insn_print_units (insn);
- fprintf (dump, "\n");
- }
-
- if (sched_verbose && unit == -1)
- visualize_no_unit (insn);
-
- if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
- schedule_unit (unit, insn, clock);
-
- if (INSN_DEPEND (insn) == 0)
- return n_ready;
-
- /* This is used by the function adjust_priority above. */
- if (n_ready > 0)
- max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
- else
- max_priority = INSN_PRIORITY (insn);
-
- for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
- {
- rtx next = XEXP (link, 0);
- int cost = insn_cost (insn, link, next);
-
- INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
-
- if ((INSN_DEP_COUNT (next) -= 1) == 0)
- {
- int effective_cost = INSN_TICK (next) - clock;
-
- /* For speculative insns, before inserting to ready/queue,
- check live, exception-free, and issue-delay. */
- if (INSN_BB (next) != target_bb
- && (!IS_VALID (INSN_BB (next))
- || CANT_MOVE (next)
- || (IS_SPECULATIVE_INSN (next)
- && (insn_issue_delay (next) > 3
- || !check_live (next, INSN_BB (next))
- || !is_exception_free (next, INSN_BB (next), target_bb)))))
- continue;
-
- if (sched_verbose >= 2)
- {
- fprintf (dump, ";;\t\tdependences resolved: insn %d ",
- INSN_UID (next));
-
- if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
- fprintf (dump, "/b%d ", BLOCK_NUM (next));