/* Data flow analysis for GNU compiler.
- Copyright (C) 1987, 88, 92-98, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+ 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
a REG_INC element is added to the insn's REG_NOTES list.
life_analysis fills in certain vectors containing information about
- register usage: reg_n_refs, reg_n_deaths, reg_n_sets, reg_live_length,
- reg_n_calls_crosses and reg_basic_block.
+ register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
+ REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
life_analysis sets current_function_sp_is_unchanging if the function
doesn't modify the stack pointer. */
#include "toplev.h"
#include "recog.h"
#include "insn-flags.h"
+#include "expr.h"
#include "obstack.h"
/* The special entry and exit blocks. */
-struct basic_block_def entry_exit_blocks[2] =
-{
- {
- NULL, /* head */
+struct basic_block_def entry_exit_blocks[2]
+= {{NULL, /* head */
NULL, /* end */
NULL, /* pred */
NULL, /* succ */
static rtx label_value_list;
-/* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
-
-#define INSN_VOLATILE(INSN) bitmap_bit_p (uid_volatile, INSN_UID (INSN))
-#define SET_INSN_VOLATILE(INSN) bitmap_set_bit (uid_volatile, INSN_UID (INSN))
-static bitmap uid_volatile;
-
/* Forward declarations */
-static int count_basic_blocks PROTO((rtx));
-static rtx find_basic_blocks_1 PROTO((rtx));
-static void create_basic_block PROTO((int, rtx, rtx, rtx));
-static void clear_edges PROTO((void));
-static void make_edges PROTO((rtx));
-static void make_edge PROTO((sbitmap *, basic_block,
- basic_block, int));
-static void make_label_edge PROTO((sbitmap *, basic_block,
- rtx, int));
-static void make_eh_edge PROTO((sbitmap *, eh_nesting_info *,
- basic_block, rtx, int));
-static void mark_critical_edges PROTO((void));
-static void move_stray_eh_region_notes PROTO((void));
-static void record_active_eh_regions PROTO((rtx));
-
-static void commit_one_edge_insertion PROTO((edge));
-
-static void delete_unreachable_blocks PROTO((void));
-static void delete_eh_regions PROTO((void));
-static int can_delete_note_p PROTO((rtx));
-static int delete_block PROTO((basic_block));
-static void expunge_block PROTO((basic_block));
-static rtx flow_delete_insn PROTO((rtx));
-static int can_delete_label_p PROTO((rtx));
-static int merge_blocks_move_predecessor_nojumps PROTO((basic_block,
+static int count_basic_blocks PARAMS ((rtx));
+static rtx find_basic_blocks_1 PARAMS ((rtx));
+static void create_basic_block PARAMS ((int, rtx, rtx, rtx));
+static void clear_edges PARAMS ((void));
+static void make_edges PARAMS ((rtx));
+static void make_label_edge PARAMS ((sbitmap *, basic_block,
+ rtx, int));
+static void make_eh_edge PARAMS ((sbitmap *, eh_nesting_info *,
+ basic_block, rtx, int));
+static void mark_critical_edges PARAMS ((void));
+static void move_stray_eh_region_notes PARAMS ((void));
+static void record_active_eh_regions PARAMS ((rtx));
+
+static void commit_one_edge_insertion PARAMS ((edge));
+
+static void delete_unreachable_blocks PARAMS ((void));
+static void delete_eh_regions PARAMS ((void));
+static int can_delete_note_p PARAMS ((rtx));
+static int delete_block PARAMS ((basic_block));
+static void expunge_block PARAMS ((basic_block));
+static int can_delete_label_p PARAMS ((rtx));
+static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
+ basic_block));
+static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
basic_block));
-static int merge_blocks_move_successor_nojumps PROTO((basic_block,
- basic_block));
-static void merge_blocks_nomove PROTO((basic_block, basic_block));
-static int merge_blocks PROTO((edge,basic_block,basic_block));
-static void try_merge_blocks PROTO((void));
-static void tidy_fallthru_edge PROTO((edge,basic_block,basic_block));
-static void calculate_loop_depth PROTO((rtx));
-
-static int verify_wide_reg_1 PROTO((rtx *, void *));
-static void verify_wide_reg PROTO((int, rtx, rtx));
-static void verify_local_live_at_start PROTO((regset, basic_block));
-static int set_noop_p PROTO((rtx));
-static int noop_move_p PROTO((rtx));
-static void notice_stack_pointer_modification PROTO ((rtx, rtx, void *));
-static void record_volatile_insns PROTO((rtx));
-static void mark_reg PROTO((regset, rtx));
-static void mark_regs_live_at_end PROTO((regset));
-static void life_analysis_1 PROTO((rtx, int, int));
-static void calculate_global_regs_live PROTO((sbitmap, sbitmap, int));
-static void propagate_block PROTO((regset, rtx, rtx,
- regset, int, int));
-static int insn_dead_p PROTO((rtx, regset, int, rtx));
-static int libcall_dead_p PROTO((rtx, regset, rtx, rtx));
-static void mark_set_regs PROTO((regset, regset, rtx,
- rtx, regset, int));
-static void mark_set_1 PROTO((regset, regset, rtx,
- rtx, regset, int));
+static void merge_blocks_nomove PARAMS ((basic_block, basic_block));
+static int merge_blocks PARAMS ((edge,basic_block,basic_block));
+static void try_merge_blocks PARAMS ((void));
+static void tidy_fallthru_edge PARAMS ((edge,basic_block,basic_block));
+static void tidy_fallthru_edges PARAMS ((void));
+static int verify_wide_reg_1 PARAMS ((rtx *, void *));
+static void verify_wide_reg PARAMS ((int, rtx, rtx));
+static void verify_local_live_at_start PARAMS ((regset, basic_block));
+static int set_noop_p PARAMS ((rtx));
+static int noop_move_p PARAMS ((rtx));
+static void delete_noop_moves PARAMS ((rtx));
+static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
+static void notice_stack_pointer_modification PARAMS ((rtx));
+static void mark_reg PARAMS ((rtx, void *));
+static void mark_regs_live_at_end PARAMS ((regset));
+static void calculate_global_regs_live PARAMS ((sbitmap, sbitmap, int));
+static void propagate_block PARAMS ((basic_block, regset,
+ regset, int));
+static int insn_dead_p PARAMS ((rtx, regset, int, rtx));
+static int libcall_dead_p PARAMS ((rtx, regset, rtx, rtx));
+static void mark_set_regs PARAMS ((regset, regset, rtx,
+ rtx, regset, int));
+static void mark_set_1 PARAMS ((regset, regset, rtx,
+ rtx, regset, int));
#ifdef AUTO_INC_DEC
-static void find_auto_inc PROTO((regset, rtx, rtx));
-static int try_pre_increment_1 PROTO((rtx));
-static int try_pre_increment PROTO((rtx, rtx, HOST_WIDE_INT));
+static void find_auto_inc PARAMS ((regset, rtx, rtx));
+static int try_pre_increment_1 PARAMS ((rtx));
+static int try_pre_increment PARAMS ((rtx, rtx, HOST_WIDE_INT));
#endif
-static void mark_used_regs PROTO((regset, regset, rtx, int, rtx));
-void dump_flow_info PROTO((FILE *));
-void debug_flow_info PROTO((void));
-static void dump_edge_info PROTO((FILE *, edge, int));
-
-static int_list_ptr alloc_int_list_node PROTO ((int_list_block **));
-static int_list_ptr add_int_list_node PROTO ((int_list_block **,
- int_list **, int));
-
-static void add_pred_succ PROTO ((int, int, int_list_ptr *,
- int_list_ptr *, int *, int *));
-
-static void count_reg_sets_1 PROTO ((rtx));
-static void count_reg_sets PROTO ((rtx));
-static void count_reg_references PROTO ((rtx));
-static void invalidate_mems_from_autoinc PROTO ((rtx));
-static void remove_edge PROTO ((edge));
-static void remove_fake_successors PROTO ((basic_block));
+static void mark_used_regs PARAMS ((regset, regset, rtx, int, rtx));
+void dump_flow_info PARAMS ((FILE *));
+void debug_flow_info PARAMS ((void));
+static void dump_edge_info PARAMS ((FILE *, edge, int));
+
+static void count_reg_sets_1 PARAMS ((rtx));
+static void count_reg_sets PARAMS ((rtx));
+static void count_reg_references PARAMS ((rtx));
+static void invalidate_mems_from_autoinc PARAMS ((rtx));
+static void remove_fake_successors PARAMS ((basic_block));
+static void flow_nodes_print PARAMS ((const char *, const sbitmap, FILE *));
+static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
+static void flow_loops_cfg_dump PARAMS ((const struct loops *, FILE *));
+static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *));
+static int flow_loop_exits_find PARAMS ((const sbitmap, edge **));
+static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
+static int flow_depth_first_order_compute PARAMS ((int *));
+static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
+static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
+static void flow_loops_tree_build PARAMS ((struct loops *));
+static int flow_loop_level_compute PARAMS ((struct loop *, int));
+static int flow_loops_level_compute PARAMS ((struct loops *));
+static basic_block get_common_dest PARAMS ((basic_block, basic_block));
+static basic_block chain_reorder_blocks PARAMS ((edge, basic_block));
+static void make_reorder_chain PARAMS ((basic_block));
+static void fixup_reorder_chain PARAMS ((void));
/* This function is always defined so it can be called from the
debugger, and it is declared extern so we don't get warnings about
it being unused. */
-void verify_flow_info PROTO ((void));
-
+void verify_flow_info PARAMS ((void));
+int flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
+void clear_log_links PARAMS ((rtx));
\f
/* Find basic blocks of the current function.
F is the first insn of the function and NREGS the number of register
numbers in use. */
void
-find_basic_blocks (f, nregs, file, do_cleanup)
+find_basic_blocks (f, nregs, file)
rtx f;
int nregs ATTRIBUTE_UNUSED;
FILE *file ATTRIBUTE_UNUSED;
- int do_cleanup;
{
int max_uid;
compute_bb_for_insn (max_uid);
/* Discover the edges of our cfg. */
-
record_active_eh_regions (f);
make_edges (label_value_list);
- /* Delete unreachable blocks, then merge blocks when possible. */
-
- if (do_cleanup)
- {
- delete_unreachable_blocks ();
- move_stray_eh_region_notes ();
- record_active_eh_regions (f);
- try_merge_blocks ();
- }
-
- /* Mark critical edges. */
+ /* Do very simple cleanup now, for the benefit of code that runs between
+ here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
+ tidy_fallthru_edges ();
mark_critical_edges ();
- /* Discover the loop depth at the start of each basic block to aid
- register allocation. */
- calculate_loop_depth (f);
-
- /* Kill the data we won't maintain. */
- label_value_list = NULL_RTX;
-
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
|| (prev_code == CALL_INSN && call_had_abnormal_edge))))
{
count++;
-
- /* If the previous insn was a call that did not create an
- abnormal edge, we want to add a nop so that the CALL_INSN
- itself is not at basic_block_end. This allows us to
- easily distinguish between normal calls and those which
- create abnormal edges in the flow graph. */
-
- if (count > 0 && prev_call != 0 && !call_had_abnormal_edge)
- {
- rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
- emit_insn_after (nop, prev_call);
- }
}
/* Record whether this call created an edge. */
prev_call = insn;
call_had_abnormal_edge = 0;
- /* If there is a specified EH region, we have an edge. */
- if (eh_region && region > 0)
+ /* If there is an EH region or rethrow, we have an edge. */
+ if ((eh_region && region > 0)
+ || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
call_had_abnormal_edge = 1;
else
{
int region = (note ? XWINT (XEXP (note, 0), 0) : 1);
call_has_abnormal_edge = 0;
- /* If there is an EH region, we have an edge. */
- if (eh_list && region > 0)
+ /* If there is an EH region or rethrow, we have an edge. */
+ if ((eh_list && region > 0)
+ || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
call_has_abnormal_edge = 1;
else
{
return label_value_list;
}
+/* Tidy the CFG by deleting unreachable code and whatnot. */
+
+void
+cleanup_cfg (f)
+ rtx f;
+{
+ delete_unreachable_blocks ();
+ move_stray_eh_region_notes ();
+ record_active_eh_regions (f);
+ try_merge_blocks ();
+ mark_critical_edges ();
+
+ /* Kill the data we won't maintain. */
+ label_value_list = NULL_RTX;
+}
+
/* Create a new basic block consisting of the instructions between
HEAD and END inclusive. Reuses the note and basic block struct
in BB_NOTE, if any. */
if (code == CALL_INSN || asynchronous_exceptions)
{
- /* If there's an EH region active at the end of a block,
- add the appropriate edges. */
- if (bb->eh_end >= 0)
- make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
+ /* Add any appropriate EH edges. We do this unconditionally
+ since there may be a REG_EH_REGION or REG_EH_RETHROW note
+ on the call, and this needn't be within an EH region. */
+ make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
/* If we have asynchronous exceptions, do the same for *all*
exception regions active in the block. */
/* Create an edge between two basic blocks. FLAGS are auxiliary information
about the edge that is accumulated between calls. */
-static void
+void
make_edge (edge_cache, src, dst, flags)
sbitmap *edge_cache;
basic_block src, dst;
basic_block jump_block;
rtx pos;
- if ((e->flags & EDGE_CRITICAL) == 0)
+ if ((e->flags & EDGE_CRITICAL) == 0
+ && e->src != ENTRY_BLOCK_PTR)
{
/* Non critical -- we can simply add a jump to the end
of the existing predecessor. */
pos = emit_jump_insn_after (gen_jump (old_succ->head),
jump_block->end);
jump_block->end = pos;
+ if (basic_block_for_insn)
+ set_block_for_insn (pos, jump_block);
emit_barrier_after (pos);
/* ... let jump know that label is in use, ... */
BASIC_BLOCK (i) = bb;
bb->index = i;
- /* Create the basic block note. */
- if (old_succ != EXIT_BLOCK_PTR)
+ /* Create the basic block note.
+
+ Where we place the note can have a noticable impact on the generated
+ code. Consider this cfg:
+
+
+ E
+ |
+ 0
+ / \
+ +->1-->2--->E
+ | |
+ +--+
+
+ If we need to insert an insn on the edge from block 0 to block 1,
+ we want to ensure the instructions we insert are outside of any
+ loop notes that physically sit between block 0 and block 1. Otherwise
+ we confuse the loop optimizer into thinking the loop is a phony. */
+ if (old_succ != EXIT_BLOCK_PTR
+ && PREV_INSN (old_succ->head)
+ && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
+ && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
+ bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
+ PREV_INSN (old_succ->head));
+ else if (old_succ != EXIT_BLOCK_PTR)
bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
else
bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
commit_one_edge_insertion (e)
edge e;
{
- rtx before = NULL_RTX, after = NULL_RTX, tmp;
+ rtx before = NULL_RTX, after = NULL_RTX, insns, tmp;
basic_block bb;
+ /* Pull the insns off the edge now since the edge might go away. */
+ insns = e->insns;
+ e->insns = NULL_RTX;
+
/* Figure out where to put these things. If the destination has
one predecessor, insert there. Except for the exit block. */
if (e->dest->pred->pred_next == NULL
&& e->src != ENTRY_BLOCK_PTR)
{
bb = e->src;
+ /* It is possible to have a non-simple jump here. Consider a target
+ where some forms of unconditional jumps clobber a register. This
+ happens on the fr30 for example.
+
+ We know this block has a single successor, so we can just emit
+ the queued insns before the jump. */
if (GET_CODE (bb->end) == JUMP_INSN)
{
- /* ??? Is it possible to wind up with non-simple jumps? Perhaps
- a jump with delay slots already filled? */
- if (! simplejump_p (bb->end))
- abort ();
-
before = bb->end;
}
else
}
/* Now that we've found the spot, do the insertion. */
- tmp = e->insns;
- e->insns = NULL_RTX;
/* Set the new block number for these insns, if structure is allocated. */
if (basic_block_for_insn)
{
rtx i;
- for (i = tmp; i != NULL_RTX; i = NEXT_INSN (i))
+ for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
set_block_for_insn (i, bb);
}
if (before)
{
- emit_insns_before (tmp, before);
+ emit_insns_before (insns, before);
if (before == bb->head)
- bb->head = tmp;
+ bb->head = insns;
}
else
{
- tmp = emit_insns_after (tmp, after);
+ rtx last = emit_insns_after (insns, after);
if (after == bb->end)
- bb->end = tmp;
+ {
+ bb->end = last;
+
+ if (GET_CODE (last) == JUMP_INSN)
+ {
+ if (returnjump_p (last))
+ {
+ /* ??? Remove all outgoing edges from BB and add one
+ for EXIT. This is not currently a problem because
+ this only happens for the (single) epilogue, which
+ already has a fallthru edge to EXIT. */
+
+ e = bb->succ;
+ if (e->dest != EXIT_BLOCK_PTR
+ || e->succ_next != NULL
+ || (e->flags & EDGE_FALLTHRU) == 0)
+ abort ();
+ e->flags &= ~EDGE_FALLTHRU;
+
+ emit_barrier_after (last);
+ }
+ else
+ abort ();
+ }
+ }
}
}
int i;
basic_block bb;
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
+
i = -1;
bb = ENTRY_BLOCK_PTR;
while (1)
deleted_handler |= delete_block (b);
}
- /* Fix up edges that now fall through, or rather should now fall through
- but previously required a jump around now deleted blocks. Simplify
- the search by only examining blocks numerically adjacent, since this
- is how find_basic_blocks created them. */
-
- for (i = 1; i < n_basic_blocks; ++i)
- {
- basic_block b = BASIC_BLOCK (i - 1);
- basic_block c = BASIC_BLOCK (i);
- edge s;
-
- /* We care about simple conditional or unconditional jumps with
- a single successor.
-
- If we had a conditional branch to the next instruction when
- find_basic_blocks was called, then there will only be one
- out edge for the block which ended with the conditional
- branch (since we do not create duplicate edges).
-
- Furthermore, the edge will be marked as a fallthru because we
- merge the flags for the duplicate edges. So we do not want to
- check that the edge is not a FALLTHRU edge. */
- if ((s = b->succ) != NULL
- && s->succ_next == NULL
- && s->dest == c
- /* If the jump insn has side effects, we can't tidy the edge. */
- && (GET_CODE (b->end) != JUMP_INSN
- || onlyjump_p (b->end)))
- tidy_fallthru_edge (s, b, c);
- }
+ tidy_fallthru_edges ();
/* If we deleted an exception handler, we may have EH region begin/end
blocks to remove as well. */
{
int num = NOTE_EH_HANDLER (insn);
/* A NULL handler indicates a region is no longer needed,
- as long as it isn't the target of a rethrow. */
+ as long as its rethrow label isn't used. */
if (get_first_handler (num) == NULL && ! rethrow_used (num))
{
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
/* Delete INSN by patching it out. Return the next insn. */
-static rtx
+rtx
flow_delete_insn (insn)
rtx insn;
{
}
}
-/* The given edge should potentially a fallthru edge. If that is in
- fact true, delete the unconditional jump and barriers that are in
- the way. */
+/* The given edge should potentially be a fallthru edge. If that is in
+ fact true, delete the jump and barriers that are in the way. */
static void
tidy_fallthru_edge (e, b, c)
e->flags |= EDGE_FALLTHRU;
}
-/* Discover and record the loop depth at the head of each basic block. */
+/* Fix up edges that now fall through, or rather should now fall through
+ but previously required a jump around now deleted blocks. Simplify
+ the search by only examining blocks numerically adjacent, since this
+ is how find_basic_blocks created them. */
static void
-calculate_loop_depth (insns)
- rtx insns;
+tidy_fallthru_edges ()
{
- basic_block bb;
- rtx insn;
- int i = 0, depth = 1;
+ int i;
- bb = BASIC_BLOCK (i);
- for (insn = insns; insn ; insn = NEXT_INSN (insn))
+ for (i = 1; i < n_basic_blocks; ++i)
{
- if (insn == bb->head)
- {
- bb->loop_depth = depth;
- if (++i >= n_basic_blocks)
- break;
- bb = BASIC_BLOCK (i);
- }
+ basic_block b = BASIC_BLOCK (i - 1);
+ basic_block c = BASIC_BLOCK (i);
+ edge s;
- if (GET_CODE (insn) == NOTE)
- {
- if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
- depth++;
- else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
- depth--;
+ /* We care about simple conditional or unconditional jumps with
+ a single successor.
- /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error. */
- if (depth == 0)
- abort ();
- }
+ If we had a conditional branch to the next instruction when
+ find_basic_blocks was called, then there will only be one
+ out edge for the block which ended with the conditional
+ branch (since we do not create duplicate edges).
+
+ Furthermore, the edge will be marked as a fallthru because we
+ merge the flags for the duplicate edges. So we do not want to
+ check that the edge is not a FALLTHRU edge. */
+ if ((s = b->succ) != NULL
+ && s->succ_next == NULL
+ && s->dest == c
+ /* If the jump insn has side effects, we can't tidy the edge. */
+ && (GET_CODE (b->end) != JUMP_INSN
+ || onlyjump_p (b->end)))
+ tidy_fallthru_edge (s, b, c);
}
}
+
+/* Discover and record the loop depth at the head of each basic block. */
+
+void
+calculate_loop_depth (dump)
+ FILE *dump;
+{
+ struct loops loops;
+
+ /* The loop infrastructure does the real job for us. */
+ flow_loops_find (&loops);
+
+ if (dump)
+ flow_loops_dump (&loops, dump, 0);
+
+ flow_loops_free (&loops);
+}
\f
/* Perform data flow analysis.
F is the first insn of the function and NREGS the number of register numbers
int remove_dead_code;
{
#ifdef ELIMINABLE_REGS
- register size_t i;
+ register int i;
static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
int flags;
-
+ sbitmap all_blocks;
+
/* Record which registers will be eliminated. We use this in
mark_used_regs. */
CLEAR_HARD_REG_SET (elim_reg_set);
#ifdef ELIMINABLE_REGS
- for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
+ for (i = 0; i < (int) (sizeof eliminables / sizeof eliminables[0]); i++)
SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
#else
SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
#endif
- /* Allocate a bitmap to be filled in by record_volatile_insns. */
- uid_volatile = BITMAP_XMALLOC ();
-
/* We want alias analysis information for local dead store elimination. */
init_alias_analysis ();
- flags = PROP_FINAL;
- if (! remove_dead_code)
- flags &= ~(PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE);
- life_analysis_1 (f, nregs, flags);
+ if (! optimize)
+ flags = PROP_DEATH_NOTES | PROP_REG_INFO;
+ else
+ {
+ flags = PROP_FINAL;
+ if (! remove_dead_code)
+ flags &= ~(PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE);
+ }
+
+ /* The post-reload life analysis have (on a global basis) the same
+ registers live as was computed by reload itself. elimination
+ Otherwise offsets and such may be incorrect.
+
+ Reload will make some registers as live even though they do not
+ appear in the rtl. */
+ if (reload_completed)
+ flags &= ~PROP_REG_INFO;
+
+ max_regno = nregs;
+
+ /* Always remove no-op moves. Do this before other processing so
+ that we don't have to keep re-scanning them. */
+ delete_noop_moves (f);
+ /* Some targets can emit simpler epilogues if they know that sp was
+ not ever modified during the function. After reload, of course,
+ we've already emitted the epilogue so there's no sense searching. */
if (! reload_completed)
- mark_constant_function ();
+ notice_stack_pointer_modification (f);
+
+ /* Allocate and zero out data structures that will record the
+ data from lifetime analysis. */
+ allocate_reg_life_data ();
+ allocate_bb_life_data ();
+ reg_next_use = (rtx *) xcalloc (nregs, sizeof (rtx));
+ all_blocks = sbitmap_alloc (n_basic_blocks);
+ sbitmap_ones (all_blocks);
+
+ /* Find the set of registers live on function exit. */
+ mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
+
+ /* "Update" life info from zero. It'd be nice to begin the
+ relaxation with just the exit and noreturn blocks, but that set
+ is not immediately handy. */
+
+ if (flags & PROP_REG_INFO)
+ memset (regs_ever_live, 0, sizeof(regs_ever_live));
+ update_life_info (all_blocks, UPDATE_LIFE_GLOBAL, flags);
+ /* Clean up. */
+ sbitmap_free (all_blocks);
+ free (reg_next_use);
+ reg_next_use = NULL;
end_alias_analysis ();
if (file)
dump_flow_info (file);
- BITMAP_FREE (uid_volatile);
- free (uid_volatile);
free_basic_block_vars (1);
}
}
}
-/* Updates death notes starting with the basic blocks set in BLOCKS.
+/* Updates life information starting with the basic blocks set in BLOCKS.
If LOCAL_ONLY, such as after splitting or peepholeing, we are only
expecting local modifications to basic blocks. If we find extra
BLOCK_FOR_INSN is assumed to be correct.
- ??? PROP_FLAGS should not contain PROP_LOG_LINKS. Need to set up
- reg_next_use for that. Including PROP_REG_INFO does not refresh
+ PROP_FLAGS should not contain PROP_LOG_LINKS unless the caller sets
+ up reg_next_use. Including PROP_REG_INFO does not properly refresh
regs_ever_live unless the caller resets it to zero. */
void
int prop_flags;
{
regset tmp;
+ regset_head tmp_head;
int i;
- tmp = ALLOCA_REG_SET ();
+ tmp = INITIALIZE_REG_SET (tmp_head);
/* For a global update, we go through the relaxation process again. */
if (extent != UPDATE_LIFE_LOCAL)
basic_block bb = BASIC_BLOCK (i);
COPY_REG_SET (tmp, bb->global_live_at_end);
- propagate_block (tmp, bb->head, bb->end, (regset) NULL, i,
- prop_flags);
+ propagate_block (bb, tmp, (regset) NULL, prop_flags);
if (extent == UPDATE_LIFE_LOCAL)
verify_local_live_at_start (tmp, bb);
});
FREE_REG_SET (tmp);
+
+ if (prop_flags & PROP_REG_INFO)
+ {
+ /* The only pseudos that are live at the beginning of the function
+ are those that were not set anywhere in the function. local-alloc
+ doesn't know how to handle these correctly, so mark them as not
+ local to any one basic block. */
+ EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
+ FIRST_PSEUDO_REGISTER, i,
+ { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
+
+ /* We have a problem with any pseudoreg that lives across the setjmp.
+ ANSI says that if a user variable does not change in value between
+ the setjmp and the longjmp, then the longjmp preserves it. This
+ includes longjmp from a place where the pseudo appears dead.
+ (In principle, the value still exists if it is in scope.)
+ If the pseudo goes in a hard reg, some other value may occupy
+ that hard reg where this pseudo is dead, thus clobbering the pseudo.
+ Conclusion: such a pseudo must not go in a hard reg. */
+ EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
+ FIRST_PSEUDO_REGISTER, i,
+ {
+ if (regno_reg_rtx[i] != 0)
+ {
+ REG_LIVE_LENGTH (i) = -1;
+ REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
+ }
+ });
+ }
}
/* Free the variables allocated by find_basic_blocks.
{
rtx src = SET_SRC (set);
rtx dst = SET_DEST (set);
- if (GET_CODE (src) == REG && GET_CODE (dst) == REG
- && REGNO (src) == REGNO (dst))
- return 1;
- if (GET_CODE (src) != SUBREG || GET_CODE (dst) != SUBREG
- || SUBREG_WORD (src) != SUBREG_WORD (dst))
- return 0;
- src = SUBREG_REG (src);
- dst = SUBREG_REG (dst);
- if (GET_CODE (src) == REG && GET_CODE (dst) == REG
- && REGNO (src) == REGNO (dst))
- return 1;
- return 0;
+
+ if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
+ {
+ if (SUBREG_WORD (src) != SUBREG_WORD (dst))
+ return 0;
+ src = SUBREG_REG (src);
+ dst = SUBREG_REG (dst);
+ }
+
+ return (GET_CODE (src) == REG && GET_CODE (dst) == REG
+ && REGNO (src) == REGNO (dst));
}
/* Return nonzero if an insn consists only of SETs, each of which only sets a
return 0;
}
+/* Delete any insns that copy a register to itself. */
+
+static void
+delete_noop_moves (f)
+ rtx f;
+{
+ rtx insn;
+ for (insn = f; insn; insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == INSN && noop_move_p (insn))
+ {
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (insn) = 0;
+ }
+ }
+}
+
+/* Determine if the stack pointer is constant over the life of the function.
+ Only useful before prologues have been emitted. */
+
static void
-notice_stack_pointer_modification (x, pat, data)
+notice_stack_pointer_modification_1 (x, pat, data)
rtx x;
rtx pat ATTRIBUTE_UNUSED;
void *data ATTRIBUTE_UNUSED;
current_function_sp_is_unchanging = 0;
}
-/* Record which insns refer to any volatile memory
- or for any reason can't be deleted just because they are dead stores.
- Also, delete any insns that copy a register to itself.
- And see if the stack pointer is modified. */
static void
-record_volatile_insns (f)
+notice_stack_pointer_modification (f)
rtx f;
{
rtx insn;
+
+ /* Assume that the stack pointer is unchanging if alloca hasn't
+ been used. */
+ current_function_sp_is_unchanging = !current_function_calls_alloca;
+ if (! current_function_sp_is_unchanging)
+ return;
+
for (insn = f; insn; insn = NEXT_INSN (insn))
{
- enum rtx_code code1 = GET_CODE (insn);
- if (code1 == CALL_INSN)
- SET_INSN_VOLATILE (insn);
- else if (code1 == INSN || code1 == JUMP_INSN)
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
- if (GET_CODE (PATTERN (insn)) != USE
- && volatile_refs_p (PATTERN (insn)))
- SET_INSN_VOLATILE (insn);
-
- /* A SET that makes space on the stack cannot be dead.
- (Such SETs occur only for allocating variable-size data,
- so they will always have a PLUS or MINUS according to the
- direction of stack growth.)
- Even if this function never uses this stack pointer value,
- signal handlers do! */
- else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET
- && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
-#ifdef STACK_GROWS_DOWNWARD
- && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS
-#else
- && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
-#endif
- && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx)
- SET_INSN_VOLATILE (insn);
-
- /* Delete (in effect) any obvious no-op moves. */
- else if (noop_move_p (insn))
- {
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
- }
+ /* Check if insn modifies the stack pointer. */
+ note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
+ NULL);
+ if (! current_function_sp_is_unchanging)
+ return;
}
-
- /* Check if insn modifies the stack pointer. */
- if ( current_function_sp_is_unchanging
- && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- note_stores (PATTERN (insn),
- notice_stack_pointer_modification,
- NULL);
}
}
/* Mark a register in SET. Hard registers in large modes get all
of their component registers set as well. */
static void
-mark_reg (set, reg)
- regset set;
+mark_reg (reg, xset)
rtx reg;
+ void *xset;
{
+ regset set = (regset) xset;
int regno = REGNO (reg);
+ if (GET_MODE (reg) == BLKmode)
+ abort ();
+
SET_REGNO_REG_SET (set, regno);
if (regno < FIRST_PSEUDO_REGISTER)
{
mark_regs_live_at_end (set)
regset set;
{
- tree type;
int i;
/* If exiting needs the right stack value, consider the stack pointer
}
/* Mark function return value. */
- /* ??? Only do this after reload. Consider a non-void function that
- omits a return statement. Across that edge we'll have the return
- register live, and no set for it. Thus the return register will
- be live back through the CFG to the entry, and thus we die. A
- possible solution is to emit a clobber at exits without returns. */
-
- type = TREE_TYPE (DECL_RESULT (current_function_decl));
- if (reload_completed
- && type != void_type_node)
- {
- rtx outgoing;
-
- if (current_function_returns_struct
- || current_function_returns_pcc_struct)
- type = build_pointer_type (type);
-
-#ifdef FUNCTION_OUTGOING_VALUE
- outgoing = FUNCTION_OUTGOING_VALUE (type, current_function_decl);
-#else
- outgoing = FUNCTION_VALUE (type, current_function_decl);
-#endif
-
- if (GET_CODE (outgoing) == REG)
- mark_reg (set, outgoing);
- else if (GET_CODE (outgoing) == PARALLEL)
- {
- int len = XVECLEN (outgoing, 0);
-
- /* Check for a NULL entry, used to indicate that the parameter
- goes on the stack and in registers. */
- i = (XEXP (XVECEXP (outgoing, 0, 0), 0) ? 0 : 1);
-
- for ( ; i < len; ++i)
- {
- rtx r = XVECEXP (outgoing, 0, i);
- if (GET_CODE (r) == REG)
- mark_reg (set, r);
- }
- }
- else
- abort ();
- }
+ diddle_return_value (mark_reg, set);
}
-/* Determine which registers are live at the start of each
- basic block of the function whose first insn is F.
- NREGS is the number of registers used in F.
- We allocate the vector basic_block_live_at_start
- and the regsets that it points to, and fill them with the data.
- regset_size and regset_bytes are also set here. */
+/* Propagate global life info around the graph of basic blocks. Begin
+ considering blocks with their corresponding bit set in BLOCKS_IN.
+ BLOCKS_OUT is set for every block that was changed. */
static void
-life_analysis_1 (f, nregs, flags)
- rtx f;
- int nregs;
+calculate_global_regs_live (blocks_in, blocks_out, flags)
+ sbitmap blocks_in, blocks_out;
int flags;
{
- char save_regs_ever_live[FIRST_PSEUDO_REGISTER];
- register int i;
-
- max_regno = nregs;
+ basic_block *queue, *qhead, *qtail, *qend;
+ regset tmp, new_live_at_end;
+ regset_head tmp_head;
+ regset_head new_live_at_end_head;
+ int i;
- /* Allocate and zero out many data structures
- that will record the data from lifetime analysis. */
+ tmp = INITIALIZE_REG_SET (tmp_head);
+ new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
- allocate_reg_life_data ();
- allocate_bb_life_data ();
+ /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
+ because the `head == tail' style test for an empty queue doesn't
+ work with a full queue. */
+ queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
+ qtail = queue;
+ qhead = qend = queue + n_basic_blocks + 2;
- reg_next_use = (rtx *) xcalloc (nregs, sizeof (rtx));
+ /* Clear out the garbage that might be hanging out in bb->aux. */
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ BASIC_BLOCK (i)->aux = NULL;
- /* Assume that the stack pointer is unchanging if alloca hasn't been used.
- This will be cleared by record_volatile_insns if it encounters an insn
- which modifies the stack pointer. */
- current_function_sp_is_unchanging = !current_function_calls_alloca;
- record_volatile_insns (f);
+ /* Queue the blocks set in the initial mask. Do this in reverse block
+ number order so that we are more likely for the first round to do
+ useful work. We use AUX non-null to flag that the block is queued. */
+ EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ *--qhead = bb;
+ bb->aux = bb;
+ });
- /* Find the set of registers live on function exit. Do this before
- zeroing regs_ever_live, as we use that data post-reload. */
- mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
-
- /* The post-reload life analysis have (on a global basis) the same
- registers live as was computed by reload itself. elimination
- Otherwise offsets and such may be incorrect.
-
- Reload will make some registers as live even though they do not
- appear in the rtl. */
- if (reload_completed)
- memcpy (save_regs_ever_live, regs_ever_live, sizeof (regs_ever_live));
- memset (regs_ever_live, 0, sizeof regs_ever_live);
-
- /* Compute register life at block boundaries. It'd be nice to
- begin with just the exit and noreturn blocks, but that set
- is not immediately handy. */
- {
- sbitmap blocks;
- blocks = sbitmap_alloc (n_basic_blocks);
- sbitmap_ones (blocks);
- calculate_global_regs_live (blocks, blocks, flags & PROP_SCAN_DEAD_CODE);
- }
-
- /* The only pseudos that are live at the beginning of the function are
- those that were not set anywhere in the function. local-alloc doesn't
- know how to handle these correctly, so mark them as not local to any
- one basic block. */
-
- EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
- FIRST_PSEUDO_REGISTER, i,
- { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
-
- /* Now the life information is accurate. Make one more pass over each
- basic block to delete dead stores, create autoincrement addressing
- and record how many times each register is used, is set, or dies. */
- {
- regset tmp;
- tmp = ALLOCA_REG_SET ();
-
- for (i = n_basic_blocks - 1; i >= 0; --i)
- {
- basic_block bb = BASIC_BLOCK (i);
-
- COPY_REG_SET (tmp, bb->global_live_at_end);
- propagate_block (tmp, bb->head, bb->end, (regset) NULL, i, flags);
- }
-
- FREE_REG_SET (tmp);
- }
-
- /* We have a problem with any pseudoreg that lives across the setjmp.
- ANSI says that if a user variable does not change in value between
- the setjmp and the longjmp, then the longjmp preserves it. This
- includes longjmp from a place where the pseudo appears dead.
- (In principle, the value still exists if it is in scope.)
- If the pseudo goes in a hard reg, some other value may occupy
- that hard reg where this pseudo is dead, thus clobbering the pseudo.
- Conclusion: such a pseudo must not go in a hard reg. */
- EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
- FIRST_PSEUDO_REGISTER, i,
- {
- if (regno_reg_rtx[i] != 0)
- {
- REG_LIVE_LENGTH (i) = -1;
- REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
- }
- });
-
- /* Restore regs_ever_live that was provided by reload. */
- if (reload_completed)
- memcpy (regs_ever_live, save_regs_ever_live, sizeof (regs_ever_live));
-
- /* Clean up. */
- free (reg_next_use);
- reg_next_use = NULL;
-}
-
-/* Propagate global life info around the graph of basic blocks. Begin
- considering blocks with their corresponding bit set in BLOCKS_IN.
- BLOCKS_OUT is set for every block that was changed. */
-
-static void
-calculate_global_regs_live (blocks_in, blocks_out, flags)
- sbitmap blocks_in, blocks_out;
- int flags;
-{
- basic_block *queue, *qhead, *qtail, *qend;
- regset tmp, new_live_at_end;
- int i;
-
- tmp = ALLOCA_REG_SET ();
- new_live_at_end = ALLOCA_REG_SET ();
-
- /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
- because the `head == tail' style test for an empty queue doesn't
- work with a full queue. */
- queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
- qtail = queue;
- qhead = qend = queue + n_basic_blocks + 2;
-
- /* Queue the blocks set in the initial mask. Do this in reverse block
- number order so that we are more likely for the first round to do
- useful work. We use AUX non-null to flag that the block is queued. */
- EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
- {
- basic_block bb = BASIC_BLOCK (i);
- *--qhead = bb;
- bb->aux = bb;
- });
-
- sbitmap_zero (blocks_out);
+ sbitmap_zero (blocks_out);
while (qhead != qtail)
{
/* Rescan the block insn by insn to turn (a copy of) live_at_end
into live_at_start. */
- propagate_block (new_live_at_end, bb->head, bb->end,
- bb->local_set, bb->index, flags);
+ propagate_block (bb, new_live_at_end, bb->local_set, flags);
/* If live_at start didn't change, no need to go farther. */
if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
BNUM is the number of the basic block. */
static void
-propagate_block (old, first, last, significant, bnum, flags)
- register regset old;
- rtx first;
- rtx last;
+propagate_block (bb, old, significant, flags)
+ basic_block bb;
+ regset old;
regset significant;
- int bnum;
int flags;
{
register rtx insn;
rtx prev;
regset live;
+ regset_head live_head;
regset dead;
+ regset_head dead_head;
/* Find the loop depth for this block. Ignore loop level changes in the
middle of the basic block -- for register allocation purposes, the
important uses will be in the blocks wholely contained within the loop
not in the loop pre-header or post-trailer. */
- loop_depth = BASIC_BLOCK (bnum)->loop_depth;
+ loop_depth = bb->loop_depth;
- dead = ALLOCA_REG_SET ();
- live = ALLOCA_REG_SET ();
+ dead = INITIALIZE_REG_SET (live_head);
+ live = INITIALIZE_REG_SET (dead_head);
cc0_live = 0;
/* Scan the block an insn at a time from end to beginning. */
- for (insn = last; ; insn = prev)
+ for (insn = bb->end; ; insn = prev)
{
prev = PREV_INSN (insn);
if (flags & PROP_SCAN_DEAD_CODE)
{
- insn_is_dead = (insn_dead_p (PATTERN (insn), old, 0, REG_NOTES (insn))
- /* Don't delete something that refers to volatile storage! */
- && ! INSN_VOLATILE (insn));
+ insn_is_dead = insn_dead_p (PATTERN (insn), old, 0,
+ REG_NOTES (insn));
libcall_is_dead = (insn_is_dead && note != 0
- && libcall_dead_p (PATTERN (insn), old, note, insn));
+ && libcall_dead_p (PATTERN (insn), old,
+ note, insn));
}
/* We almost certainly don't want to delete prologue or epilogue
instructions. Warn about probable compiler losage. */
- if ((flags & PROP_KILL_DEAD_CODE)
- && insn_is_dead
+ if (insn_is_dead
&& reload_completed
&& (HAVE_epilogue || HAVE_prologue)
&& prologue_epilogue_contains (insn))
{
- warning ("ICE: would have deleted prologue/epilogue insn");
- debug_rtx (insn);
+ if (flags & PROP_KILL_DEAD_CODE)
+ {
+ warning ("ICE: would have deleted prologue/epilogue insn");
+ if (!inhibit_warnings)
+ debug_rtx (insn);
+ }
libcall_is_dead = insn_is_dead = 0;
}
LABEL_NUSES (label)--;
/* If this label was attached to an ADDR_VEC, it's
- safe to delete the ADDR_VEC. In fact, it's pretty much
- mandatory to delete it, because the ADDR_VEC may
+ safe to delete the ADDR_VEC. In fact, it's pretty
+ much mandatory to delete it, because the ADDR_VEC may
be referencing labels that no longer exist. */
if (LABEL_NUSES (label) == 0
&& (next = next_nonnote_insn (label)) != NULL
}
- /* On final pass, update counts of how many insns each reg is live
- at. */
+ /* On final pass, update counts of how many insns in which
+ each reg is live. */
if (flags & PROP_REG_INFO)
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
- { REG_LIVE_LENGTH (i)++; });
+ EXECUTE_IF_SET_IN_REG_SET (old, 0, i, { REG_LIVE_LENGTH (i)++; });
}
- flushed: ;
- if (insn == first)
+ flushed:
+ if (insn == bb->head)
break;
}
{
rtx r = SET_DEST (x);
- /* A SET that is a subroutine call cannot be dead. */
- if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
- return 0;
-
#ifdef HAVE_cc0
if (GET_CODE (r) == CC0)
return ! cc0_live;
#endif
- if (GET_CODE (r) == MEM && ! MEM_VOLATILE_P (r))
+ /* A SET that is a subroutine call cannot be dead. */
+ if (GET_CODE (SET_SRC (x)) == CALL)
+ {
+ if (! call_ok)
+ return 0;
+ }
+
+ /* Don't eliminate loads from volatile memory or volatile asms. */
+ else if (volatile_refs_p (SET_SRC (x)))
+ return 0;
+
+ if (GET_CODE (r) == MEM)
{
rtx temp;
+
+ if (MEM_VOLATILE_P (r))
+ return 0;
+
/* Walk the set of memory locations we are currently tracking
and see if one is an identical match to this memory location.
If so, this memory write is dead (remember, we're walking
temp = XEXP (temp, 1);
}
}
+ else
+ {
+ while (GET_CODE (r) == SUBREG
+ || GET_CODE (r) == STRICT_LOW_PART
+ || GET_CODE (r) == ZERO_EXTRACT)
+ r = XEXP (r, 0);
+
+ if (GET_CODE (r) == REG)
+ {
+ int regno = REGNO (r);
- while (GET_CODE (r) == SUBREG || GET_CODE (r) == STRICT_LOW_PART
- || GET_CODE (r) == ZERO_EXTRACT)
- r = XEXP (r, 0);
+ /* Obvious. */
+ if (REGNO_REG_SET_P (needed, regno))
+ return 0;
- if (GET_CODE (r) == REG)
- {
- int regno = REGNO (r);
+ /* If this is a hard register, verify that subsequent
+ words are not needed. */
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
+
+ while (--n > 0)
+ if (REGNO_REG_SET_P (needed, regno+n))
+ return 0;
+ }
+
+ /* Don't delete insns to set global regs. */
+ if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
+ return 0;
+
+ /* Make sure insns to set the stack pointer aren't deleted. */
+ if (regno == STACK_POINTER_REGNUM)
+ return 0;
- /* Don't delete insns to set global regs. */
- if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
- /* Make sure insns to set frame pointer aren't deleted. */
- || (regno == FRAME_POINTER_REGNUM
+ /* Make sure insns to set the frame pointer aren't deleted. */
+ if (regno == FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
+ return 0;
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- || (regno == HARD_FRAME_POINTER_REGNUM
+ if (regno == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
+ return 0;
#endif
+
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
/* Make sure insns to set arg pointer are never deleted
- (if the arg pointer isn't fixed, there will be a USE for
- it, so we can treat it normally). */
- || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
+ (if the arg pointer isn't fixed, there will be a USE
+ for it, so we can treat it normally). */
+ if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
+ return 0;
#endif
- || REGNO_REG_SET_P (needed, regno))
- return 0;
-
- /* If this is a hard register, verify that subsequent words are
- not needed. */
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
- while (--n > 0)
- if (REGNO_REG_SET_P (needed, regno+n))
- return 0;
+ /* Otherwise, the set is dead. */
+ return 1;
}
-
- return 1;
}
}
- /* If performing several activities,
- insn is dead if each activity is individually dead.
- Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
- that's inside a PARALLEL doesn't make the insn worth keeping. */
+ /* If performing several activities, insn is dead if each activity
+ is individually dead. Also, CLOBBERs and USEs can be ignored; a
+ CLOBBER or USE that's inside a PARALLEL doesn't make the insn
+ worth keeping. */
else if (code == PARALLEL)
{
int i = XVECLEN (x, 0);
/* Count (weighted) references, stores, etc. This counts a
register twice if it is modified, but that is correct. */
REG_N_SETS (regno)++;
- REG_N_REFS (regno) += loop_depth;
+ REG_N_REFS (regno) += loop_depth + 1;
/* The insns where a reg is live are normally counted
elsewhere, but we want the count to include the insn
/* Count an extra reference to the reg. When a reg is
incremented, spilling it is worse, so we want to make
that less likely. */
- REG_N_REFS (regno) += loop_depth;
+ REG_N_REFS (regno) += loop_depth + 1;
/* Count the increment as a setting of the register,
even though it isn't a SET in rtl. */
it was allocated to the pseudos. If the register will not
be eliminated, reload will set it live at that point. */
- if (! TEST_HARD_REG_BIT (elim_reg_set, regno))
+ if ((flags & PROP_REG_INFO)
+ && ! TEST_HARD_REG_BIT (elim_reg_set, regno))
regs_ever_live[regno] = 1;
return;
}
/* Count (weighted) number of uses of each reg. */
- REG_N_REFS (regno) += loop_depth;
+ REG_N_REFS (regno) += loop_depth + 1;
}
}
}
break;
- case RETURN:
- /* ??? This info should have been gotten from mark_regs_live_at_end,
- as applied to the EXIT block, and propagated along the edge that
- connects this block to the EXIT. */
- break;
-
case ASM_OPERANDS:
case UNSPEC_VOLATILE:
case TRAP_IF:
less likely. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
- REG_N_REFS (regno) += loop_depth;
+ REG_N_REFS (regno) += loop_depth + 1;
REG_N_SETS (regno)++;
}
return 1;
else if (tem != 0)
return (rtx) (HOST_WIDE_INT) 1;
}
- if (fmt[i] == 'E')
+ else if (fmt[i] == 'E')
{
register int j;
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
This is part of making a debugging dump. */
void
+dump_regset (r, outf)
+ regset r;
+ FILE *outf;
+{
+ int i;
+ if (r == NULL)
+ {
+ fputs (" (nil)", outf);
+ return;
+ }
+
+ EXECUTE_IF_SET_IN_REG_SET (r, 0, i,
+ {
+ fprintf (outf, " %d", i);
+ if (i < FIRST_PSEUDO_REGISTER)
+ fprintf (outf, " [%s]",
+ reg_names[i]);
+ });
+}
+
+void
+debug_regset (r)
+ regset r;
+{
+ dump_regset (r, stderr);
+ putc ('\n', stderr);
+}
+
+void
dump_flow_info (file)
FILE *file;
{
for (i = 0; i < n_basic_blocks; i++)
{
register basic_block bb = BASIC_BLOCK (i);
- register int regno;
register edge e;
- fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
- i, INSN_UID (bb->head), INSN_UID (bb->end));
+ fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d.\n",
+ i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth);
fprintf (file, "Predecessors: ");
for (e = bb->pred; e ; e = e->pred_next)
dump_edge_info (file, e, 1);
fprintf (file, "\nRegisters live at start:");
- if (bb->global_live_at_start)
- {
- for (regno = 0; regno < max_regno; regno++)
- if (REGNO_REG_SET_P (bb->global_live_at_start, regno))
- fprintf (file, " %d", regno);
- }
- else
- fprintf (file, " n/a");
+ dump_regset (bb->global_live_at_start, file);
fprintf (file, "\nRegisters live at end:");
- if (bb->global_live_at_end)
- {
- for (regno = 0; regno < max_regno; regno++)
- if (REGNO_REG_SET_P (bb->global_live_at_end, regno))
- fprintf (file, " %d", regno);
- }
- else
- fprintf (file, " n/a");
+ dump_regset (bb->global_live_at_end, file);
putc('\n', file);
}
}
\f
+/* Print out one basic block with live information at start and end. */
+void
+dump_bb (bb, outf)
+ basic_block bb;
+ FILE *outf;
+{
+ rtx insn;
+ rtx last;
+ edge e;
+
+ fprintf (outf, ";; Basic block %d, loop depth %d",
+ bb->index, bb->loop_depth - 1);
+ if (bb->eh_beg != -1 || bb->eh_end != -1)
+ fprintf (outf, ", eh regions %d/%d", bb->eh_beg, bb->eh_end);
+ putc ('\n', outf);
+
+ fputs (";; Predecessors: ", outf);
+ for (e = bb->pred; e ; e = e->pred_next)
+ dump_edge_info (outf, e, 0);
+ putc ('\n', outf);
+
+ fputs (";; Registers live at start:", outf);
+ dump_regset (bb->global_live_at_start, outf);
+ putc ('\n', outf);
+
+ for (insn = bb->head, last = NEXT_INSN (bb->end);
+ insn != last;
+ insn = NEXT_INSN (insn))
+ print_rtl_single (outf, insn);
+
+ fputs (";; Registers live at end:", outf);
+ dump_regset (bb->global_live_at_end, outf);
+ putc ('\n', outf);
+
+ fputs (";; Successors: ", outf);
+ for (e = bb->succ; e; e = e->succ_next)
+ dump_edge_info (outf, e, 1);
+ putc ('\n', outf);
+}
+
+void
+debug_bb (bb)
+ basic_block bb;
+{
+ dump_bb (bb, stderr);
+}
+
+void
+debug_bb_n (n)
+ int n;
+{
+ dump_bb (BASIC_BLOCK(n), stderr);
+}
+
/* Like print_rtl, but also print out live information for the start of each
basic block. */
{
fprintf (outf, ";; Start of basic block %d, registers live:",
bb->index);
-
- EXECUTE_IF_SET_IN_REG_SET (bb->global_live_at_start, 0, i,
- {
- fprintf (outf, " %d", i);
- if (i < FIRST_PSEUDO_REGISTER)
- fprintf (outf, " [%s]",
- reg_names[i]);
- });
+ dump_regset (bb->global_live_at_start, outf);
putc ('\n', outf);
}
if (in_bb_p[INSN_UID(tmp_rtx)] == NOT_IN_BB
&& GET_CODE (tmp_rtx) != NOTE
- && GET_CODE (tmp_rtx) != BARRIER
- && ! obey_regdecls)
+ && GET_CODE (tmp_rtx) != BARRIER)
fprintf (outf, ";; Insn is not within a basic block\n");
else if (in_bb_p[INSN_UID(tmp_rtx)] == IN_MULTIPLE_BB)
fprintf (outf, ";; Insn is in multiple basic blocks\n");
}
}
-\f
-/* Integer list support. */
-
-/* Allocate a node from list *HEAD_PTR. */
-
-static int_list_ptr
-alloc_int_list_node (head_ptr)
- int_list_block **head_ptr;
+/* Compute dominator relationships using new flow graph structures. */
+void
+compute_flow_dominators (dominators, post_dominators)
+ sbitmap *dominators;
+ sbitmap *post_dominators;
{
- struct int_list_block *first_blk = *head_ptr;
+ int bb;
+ sbitmap *temp_bitmap;
+ edge e;
+ basic_block *worklist, *tos;
- if (first_blk == NULL || first_blk->nodes_left <= 0)
- {
- first_blk = (struct int_list_block *) xmalloc (sizeof (struct int_list_block));
- first_blk->nodes_left = INT_LIST_NODES_IN_BLK;
- first_blk->next = *head_ptr;
- *head_ptr = first_blk;
- }
+ /* Allocate a worklist array/queue. Entries are only added to the
+ list if they were not already on the list. So the size is
+ bounded by the number of basic blocks. */
+ tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
+ * n_basic_blocks);
- first_blk->nodes_left--;
- return &first_blk->nodes[first_blk->nodes_left];
-}
+ temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
-/* Pointer to head of predecessor/successor block list. */
-static int_list_block *pred_int_list_blocks;
+ if (dominators)
+ {
+ /* The optimistic setting of dominators requires us to put every
+ block on the work list initially. */
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ *tos++ = BASIC_BLOCK (bb);
+ BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
+ }
-/* Add a new node to integer list LIST with value VAL.
- LIST is a pointer to a list object to allow for different implementations.
- If *LIST is initially NULL, the list is empty.
- The caller must not care whether the element is added to the front or
- to the end of the list (to allow for different implementations). */
+ /* We want a maximal solution, so initially assume everything dominates
+ everything else. */
+ sbitmap_vector_ones (dominators, n_basic_blocks);
-static int_list_ptr
-add_int_list_node (blk_list, list, val)
- int_list_block **blk_list;
- int_list **list;
- int val;
-{
- int_list_ptr p = alloc_int_list_node (blk_list);
+ /* Mark successors of the entry block so we can identify them below. */
+ for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ e->dest->aux = ENTRY_BLOCK_PTR;
- p->val = val;
- p->next = *list;
- *list = p;
- return p;
-}
+ /* Iterate until the worklist is empty. */
+ while (tos != worklist)
+ {
+ /* Take the first entry off the worklist. */
+ basic_block b = *--tos;
+ bb = b->index;
+
+ /* Compute the intersection of the dominators of all the
+ predecessor blocks.
+
+ If one of the predecessor blocks is the ENTRY block, then the
+ intersection of the dominators of the predecessor blocks is
+ defined as the null set. We can identify such blocks by the
+ special value in the AUX field in the block structure. */
+ if (b->aux == ENTRY_BLOCK_PTR)
+ {
+ /* Do not clear the aux field for blocks which are
+ successors of the ENTRY block. That way we we never
+ add them to the worklist again.
-/* Free the blocks of lists at BLK_LIST. */
+ The intersect of dominators of the preds of this block is
+ defined as the null set. */
+ sbitmap_zero (temp_bitmap[bb]);
+ }
+ else
+ {
+ /* Clear the aux field of this block so it can be added to
+ the worklist again if necessary. */
+ b->aux = NULL;
+ sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
+ }
-void
-free_int_list (blk_list)
- int_list_block **blk_list;
-{
- int_list_block *p, *next;
+ /* Make sure each block always dominates itself. */
+ SET_BIT (temp_bitmap[bb], bb);
- for (p = *blk_list; p != NULL; p = next)
- {
- next = p->next;
- free (p);
+ /* If the out state of this block changed, then we need to
+ add the successors of this block to the worklist if they
+ are not already on the worklist. */
+ if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
+ {
+ for (e = b->succ; e; e = e->succ_next)
+ {
+ if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
+ {
+ *tos++ = e->dest;
+ e->dest->aux = e;
+ }
+ }
+ }
+ }
}
- /* Mark list as empty for the next function we compile. */
- *blk_list = NULL;
-}
-\f
-/* Predecessor/successor computation. */
-
-/* Mark PRED_BB a precessor of SUCC_BB,
- and conversely SUCC_BB a successor of PRED_BB. */
-
-static void
-add_pred_succ (pred_bb, succ_bb, s_preds, s_succs, num_preds, num_succs)
- int pred_bb;
- int succ_bb;
- int_list_ptr *s_preds;
- int_list_ptr *s_succs;
- int *num_preds;
- int *num_succs;
-{
- if (succ_bb != EXIT_BLOCK)
- {
- add_int_list_node (&pred_int_list_blocks, &s_preds[succ_bb], pred_bb);
- num_preds[succ_bb]++;
- }
- if (pred_bb != ENTRY_BLOCK)
+ if (post_dominators)
{
- add_int_list_node (&pred_int_list_blocks, &s_succs[pred_bb], succ_bb);
- num_succs[pred_bb]++;
- }
-}
-
-/* Convert edge lists into pred/succ lists for backward compatibility. */
+ /* The optimistic setting of dominators requires us to put every
+ block on the work list initially. */
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ *tos++ = BASIC_BLOCK (bb);
+ BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
+ }
-void
-compute_preds_succs (s_preds, s_succs, num_preds, num_succs)
- int_list_ptr *s_preds;
- int_list_ptr *s_succs;
- int *num_preds;
- int *num_succs;
-{
- int i, n = n_basic_blocks;
- edge e;
+ /* We want a maximal solution, so initially assume everything post
+ dominates everything else. */
+ sbitmap_vector_ones (post_dominators, n_basic_blocks);
- memset (s_preds, 0, n_basic_blocks * sizeof (int_list_ptr));
- memset (s_succs, 0, n_basic_blocks * sizeof (int_list_ptr));
- memset (num_preds, 0, n_basic_blocks * sizeof (int));
- memset (num_succs, 0, n_basic_blocks * sizeof (int));
+ /* Mark predecessors of the exit block so we can identify them below. */
+ for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ e->src->aux = EXIT_BLOCK_PTR;
- for (i = 0; i < n; ++i)
- {
- basic_block bb = BASIC_BLOCK (i);
-
- for (e = bb->succ; e ; e = e->succ_next)
- add_pred_succ (i, e->dest->index, s_preds, s_succs,
- num_preds, num_succs);
- }
+ /* Iterate until the worklist is empty. */
+ while (tos != worklist)
+ {
+ /* Take the first entry off the worklist. */
+ basic_block b = *--tos;
+ bb = b->index;
+
+ /* Compute the intersection of the post dominators of all the
+ successor blocks.
+
+ If one of the successor blocks is the EXIT block, then the
+ intersection of the dominators of the successor blocks is
+ defined as the null set. We can identify such blocks by the
+ special value in the AUX field in the block structure. */
+ if (b->aux == EXIT_BLOCK_PTR)
+ {
+ /* Do not clear the aux field for blocks which are
+ predecessors of the EXIT block. That way we we never
+ add them to the worklist again.
- for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
- add_pred_succ (ENTRY_BLOCK, e->dest->index, s_preds, s_succs,
- num_preds, num_succs);
-}
+ The intersect of dominators of the succs of this block is
+ defined as the null set. */
+ sbitmap_zero (temp_bitmap[bb]);
+ }
+ else
+ {
+ /* Clear the aux field of this block so it can be added to
+ the worklist again if necessary. */
+ b->aux = NULL;
+ sbitmap_intersection_of_succs (temp_bitmap[bb],
+ post_dominators, bb);
+ }
-void
-dump_bb_data (file, preds, succs, live_info)
- FILE *file;
- int_list_ptr *preds;
- int_list_ptr *succs;
- int live_info;
-{
- int bb;
- int_list_ptr p;
+ /* Make sure each block always post dominates itself. */
+ SET_BIT (temp_bitmap[bb], bb);
- fprintf (file, "BB data\n\n");
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- fprintf (file, "BB %d, start %d, end %d\n", bb,
- INSN_UID (BLOCK_HEAD (bb)), INSN_UID (BLOCK_END (bb)));
- fprintf (file, " preds:");
- for (p = preds[bb]; p != NULL; p = p->next)
- {
- int pred_bb = INT_LIST_VAL (p);
- if (pred_bb == ENTRY_BLOCK)
- fprintf (file, " entry");
- else
- fprintf (file, " %d", pred_bb);
- }
- fprintf (file, "\n");
- fprintf (file, " succs:");
- for (p = succs[bb]; p != NULL; p = p->next)
- {
- int succ_bb = INT_LIST_VAL (p);
- if (succ_bb == EXIT_BLOCK)
- fprintf (file, " exit");
- else
- fprintf (file, " %d", succ_bb);
- }
- if (live_info)
- {
- int regno;
- fprintf (file, "\nRegisters live at start:");
- for (regno = 0; regno < max_regno; regno++)
- if (REGNO_REG_SET_P (BASIC_BLOCK (bb)->global_live_at_start, regno))
- fprintf (file, " %d", regno);
- fprintf (file, "\n");
+ /* If the out state of this block changed, then we need to
+ add the successors of this block to the worklist if they
+ are not already on the worklist. */
+ if (sbitmap_a_and_b (post_dominators[bb],
+ post_dominators[bb],
+ temp_bitmap[bb]))
+ {
+ for (e = b->pred; e; e = e->pred_next)
+ {
+ if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
+ {
+ *tos++ = e->src;
+ e->src->aux = e;
+ }
+ }
+ }
}
- fprintf (file, "\n");
}
- fprintf (file, "\n");
+ free (temp_bitmap);
}
-/* Free basic block data storage. */
-
-void
-free_bb_mem ()
-{
- free_int_list (&pred_int_list_blocks);
-}
+/* Given DOMINATORS, compute the immediate dominators into IDOM. */
-/* Compute dominator relationships. */
void
-compute_dominators (dominators, post_dominators, s_preds, s_succs)
+compute_immediate_dominators (idom, dominators)
+ int *idom;
sbitmap *dominators;
- sbitmap *post_dominators;
- int_list_ptr *s_preds;
- int_list_ptr *s_succs;
{
- int bb, changed, passes;
- sbitmap *temp_bitmap;
-
- temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- sbitmap_vector_ones (dominators, n_basic_blocks);
- sbitmap_vector_ones (post_dominators, n_basic_blocks);
- sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
-
- sbitmap_zero (dominators[0]);
- SET_BIT (dominators[0], 0);
+ sbitmap *tmp;
+ int b;
- sbitmap_zero (post_dominators[n_basic_blocks - 1]);
- SET_BIT (post_dominators[n_basic_blocks - 1], 0);
+ tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 1; bb < n_basic_blocks; bb++)
- {
- sbitmap_intersect_of_predecessors (temp_bitmap[bb], dominators,
- bb, s_preds);
- SET_BIT (temp_bitmap[bb], bb);
- changed |= sbitmap_a_and_b (dominators[bb],
- dominators[bb],
- temp_bitmap[bb]);
- sbitmap_intersect_of_successors (temp_bitmap[bb], post_dominators,
- bb, s_succs);
- SET_BIT (temp_bitmap[bb], bb);
- changed |= sbitmap_a_and_b (post_dominators[bb],
- post_dominators[bb],
- temp_bitmap[bb]);
- }
- passes++;
- }
-
- free (temp_bitmap);
-}
-
-/* Compute dominator relationships using new flow graph structures. */
-void
-compute_flow_dominators (dominators, post_dominators)
- sbitmap *dominators;
- sbitmap *post_dominators;
-{
- int bb, changed, passes;
- sbitmap *temp_bitmap;
-
- temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- sbitmap_vector_ones (dominators, n_basic_blocks);
- sbitmap_vector_ones (post_dominators, n_basic_blocks);
- sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
-
- sbitmap_zero (dominators[0]);
- SET_BIT (dominators[0], 0);
-
- sbitmap_zero (post_dominators[n_basic_blocks - 1]);
- SET_BIT (post_dominators[n_basic_blocks - 1], 0);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 1; bb < n_basic_blocks; bb++)
- {
- sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
- SET_BIT (temp_bitmap[bb], bb);
- changed |= sbitmap_a_and_b (dominators[bb],
- dominators[bb],
- temp_bitmap[bb]);
- sbitmap_intersection_of_succs (temp_bitmap[bb], post_dominators, bb);
- SET_BIT (temp_bitmap[bb], bb);
- changed |= sbitmap_a_and_b (post_dominators[bb],
- post_dominators[bb],
- temp_bitmap[bb]);
- }
- passes++;
- }
-
- free (temp_bitmap);
-}
-
-/* Given DOMINATORS, compute the immediate dominators into IDOM. */
-
-void
-compute_immediate_dominators (idom, dominators)
- int *idom;
- sbitmap *dominators;
-{
- sbitmap *tmp;
- int b;
-
- tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-
- /* Begin with tmp(n) = dom(n) - { n }. */
- for (b = n_basic_blocks; --b >= 0; )
+ /* Begin with tmp(n) = dom(n) - { n }. */
+ for (b = n_basic_blocks; --b >= 0; )
{
sbitmap_copy (tmp[b], dominators[b]);
RESET_BIT (tmp[b], b);
/* Count (weighted) references, stores, etc. This counts a
register twice if it is modified, but that is correct. */
REG_N_SETS (regno)++;
-
- REG_N_REFS (regno) += loop_depth;
+ REG_N_REFS (regno) += loop_depth + 1;
}
}
}
case REG:
if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
- REG_N_REFS (REGNO (x)) += loop_depth;
+ REG_N_REFS (REGNO (x)) += loop_depth + 1;
return;
case SET:
More accurate reference counts generally lead to better register allocation.
F is the first insn to be scanned.
+
LOOP_STEP denotes how much loop_depth should be incremented per
- loop nesting level in order to increase the ref count more for references
- in a loop.
+ loop nesting level in order to increase the ref count more for
+ references in a loop.
It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
possibly other information which is used by the register allocators. */
void
recompute_reg_usage (f, loop_step)
- rtx f;
- int loop_step;
+ rtx f ATTRIBUTE_UNUSED;
+ int loop_step ATTRIBUTE_UNUSED;
{
rtx insn;
int i, max_reg;
+ int index;
/* Clear out the old data. */
max_reg = max_reg_num ();
/* Scan each insn in the chain and count how many times each register is
set/used. */
- loop_depth = 1;
- for (insn = f; insn; insn = NEXT_INSN (insn))
+ for (index = 0; index < n_basic_blocks; index++)
{
- /* Keep track of loop depth. */
- if (GET_CODE (insn) == NOTE)
- {
- /* Look for loop boundaries. */
- if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
- loop_depth -= loop_step;
- else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
- loop_depth += loop_step;
-
- /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
- Abort now rather than setting register status incorrectly. */
- if (loop_depth == 0)
- abort ();
- }
- else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- rtx links;
+ basic_block bb = BASIC_BLOCK (index);
+ loop_depth = bb->loop_depth;
+ for (insn = bb->head; insn; insn = NEXT_INSN (insn))
+ {
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ {
+ rtx links;
- /* This call will increment REG_N_SETS for each SET or CLOBBER
- of a register in INSN. It will also increment REG_N_REFS
- by the loop depth for each set of a register in INSN. */
- count_reg_sets (PATTERN (insn));
+ /* This call will increment REG_N_SETS for each SET or CLOBBER
+ of a register in INSN. It will also increment REG_N_REFS
+ by the loop depth for each set of a register in INSN. */
+ count_reg_sets (PATTERN (insn));
- /* count_reg_sets does not detect autoincrement address modes, so
- detect them here by looking at the notes attached to INSN. */
- for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
- {
- if (REG_NOTE_KIND (links) == REG_INC)
- /* Count (weighted) references, stores, etc. This counts a
- register twice if it is modified, but that is correct. */
- REG_N_SETS (REGNO (XEXP (links, 0)))++;
- }
+ /* count_reg_sets does not detect autoincrement address modes, so
+ detect them here by looking at the notes attached to INSN. */
+ for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
+ {
+ if (REG_NOTE_KIND (links) == REG_INC)
+ /* Count (weighted) references, stores, etc. This counts a
+ register twice if it is modified, but that is correct. */
+ REG_N_SETS (REGNO (XEXP (links, 0)))++;
+ }
- /* This call will increment REG_N_REFS by the current loop depth for
- each reference to a register in INSN. */
- count_reg_references (PATTERN (insn));
+ /* This call will increment REG_N_REFS by the current loop depth for
+ each reference to a register in INSN. */
+ count_reg_references (PATTERN (insn));
- /* count_reg_references will not include counts for arguments to
- function calls, so detect them here by examining the
- CALL_INSN_FUNCTION_USAGE data. */
- if (GET_CODE (insn) == CALL_INSN)
- {
- rtx note;
+ /* count_reg_references will not include counts for arguments to
+ function calls, so detect them here by examining the
+ CALL_INSN_FUNCTION_USAGE data. */
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ rtx note;
- for (note = CALL_INSN_FUNCTION_USAGE (insn);
- note;
- note = XEXP (note, 1))
- if (GET_CODE (XEXP (note, 0)) == USE)
- count_reg_references (XEXP (XEXP (note, 0), 0));
+ for (note = CALL_INSN_FUNCTION_USAGE (insn);
+ note;
+ note = XEXP (note, 1))
+ if (GET_CODE (XEXP (note, 0)) == USE)
+ count_reg_references (XEXP (XEXP (note, 0), 0));
+ }
}
+ if (insn == bb->end)
+ break;
}
}
}
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
num_edges++;
- elist = xmalloc (sizeof (struct edge_list));
+ elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
elist->num_blocks = block_count;
elist->num_edges = num_edges;
- elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
+ elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
num_edges = 0;
}
/* This function will remove an edge from the flow graph. */
-static void
+void
remove_edge (e)
edge e;
{
if (BASIC_BLOCK (x)->succ == NULL)
make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
}
+\f
+/* Dump the list of basic blocks in the bitmap NODES. */
+static void
+flow_nodes_print (str, nodes, file)
+ const char *str;
+ const sbitmap nodes;
+ FILE *file;
+{
+ int node;
+
+ fprintf (file, "%s { ", str);
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
+ fputs ("}\n", file);
+}
+
+
+/* Dump the list of exiting edges in the array EDGES. */
+static void
+flow_exits_print (str, edges, num_edges, file)
+ const char *str;
+ const edge *edges;
+ int num_edges;
+ FILE *file;
+{
+ int i;
+
+ fprintf (file, "%s { ", str);
+ for (i = 0; i < num_edges; i++)
+ fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
+ fputs ("}\n", file);
+}
+
+
+/* Dump loop related CFG information. */
+static void
+flow_loops_cfg_dump (loops, file)
+ const struct loops *loops;
+ FILE *file;
+{
+ int i;
+
+ if (! loops->num || ! file || ! loops->cfg.dom)
+ return;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ edge succ;
+
+ fprintf (file, ";; %d succs { ", i);
+ for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
+ fprintf (file, "%d ", succ->dest->index);
+ flow_nodes_print ("} dom", loops->cfg.dom[i], file);
+ }
+
+
+ /* Dump the DFS node order. */
+ if (loops->cfg.dfs_order)
+ {
+ fputs (";; DFS order: ", file);
+ for (i = 0; i < n_basic_blocks; i++)
+ fprintf (file, "%d ", loops->cfg.dfs_order[i]);
+ fputs ("\n", file);
+ }
+}
+
+
+/* Return non-zero if the nodes of LOOP are a subset of OUTER. */
+static int
+flow_loop_nested_p (outer, loop)
+ struct loop *outer;
+ struct loop *loop;
+{
+ return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
+}
+
+
+/* Dump the loop information specified by LOOPS to the stream FILE. */
+void
+flow_loops_dump (loops, file, verbose)
+ const struct loops *loops;
+ FILE *file;
+ int verbose;
+{
+ int i;
+ int num_loops;
+
+ num_loops = loops->num;
+ if (! num_loops || ! file)
+ return;
+
+ fprintf (file, ";; %d loops found, %d levels\n",
+ num_loops, loops->levels);
+
+ for (i = 0; i < num_loops; i++)
+ {
+ struct loop *loop = &loops->array[i];
+
+ fprintf (file, ";; loop %d (%d to %d):\n;; header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
+ i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
+ loop->header->index, loop->latch->index,
+ loop->pre_header ? loop->pre_header->index : -1,
+ loop->depth, loop->level,
+ (long) (loop->outer ? (loop->outer - loops->array) : -1));
+ fprintf (file, ";; %d", loop->num_nodes);
+ flow_nodes_print (" nodes", loop->nodes, file);
+ fprintf (file, ";; %d", loop->num_exits);
+ flow_exits_print (" exits", loop->exits, loop->num_exits, file);
+
+ if (loop->shared)
+ {
+ int j;
+
+ for (j = 0; j < i; j++)
+ {
+ struct loop *oloop = &loops->array[j];
+
+ if (loop->header == oloop->header)
+ {
+ int disjoint;
+ int smaller;
+
+ smaller = loop->num_nodes < oloop->num_nodes;
+
+ /* If the union of LOOP and OLOOP is different than
+ the larger of LOOP and OLOOP then LOOP and OLOOP
+ must be disjoint. */
+ disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
+ smaller ? oloop : loop);
+ fprintf (file, ";; loop header %d shared by loops %d, %d %s\n",
+ loop->header->index, i, j,
+ disjoint ? "disjoint" : "nested");
+ }
+ }
+ }
+
+ if (verbose)
+ {
+ /* Print diagnostics to compare our concept of a loop with
+ what the loop notes say. */
+ if (GET_CODE (PREV_INSN (loop->first->head)) != NOTE
+ || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
+ != NOTE_INSN_LOOP_BEG)
+ fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
+ INSN_UID (PREV_INSN (loop->first->head)));
+ if (GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
+ || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
+ != NOTE_INSN_LOOP_END)
+ fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
+ INSN_UID (NEXT_INSN (loop->last->end)));
+ }
+ }
+
+ if (verbose)
+ flow_loops_cfg_dump (loops, file);
+}
+
+
+/* Free all the memory allocated for LOOPS. */
+void
+flow_loops_free (loops)
+ struct loops *loops;
+{
+ if (loops->array)
+ {
+ int i;
+
+ if (! loops->num)
+ abort ();
+
+ /* Free the loop descriptors. */
+ for (i = 0; i < loops->num; i++)
+ {
+ struct loop *loop = &loops->array[i];
+
+ if (loop->nodes)
+ sbitmap_free (loop->nodes);
+ if (loop->exits)
+ free (loop->exits);
+ }
+ free (loops->array);
+ loops->array = NULL;
+
+ if (loops->cfg.dom)
+ sbitmap_vector_free (loops->cfg.dom);
+ if (loops->cfg.dfs_order)
+ free (loops->cfg.dfs_order);
+
+ sbitmap_free (loops->shared_headers);
+ }
+}
+
+
+/* Find the exits from the loop using the bitmap of loop nodes NODES
+ and store in EXITS array. Return the number of exits from the
+ loop. */
+static int
+flow_loop_exits_find (nodes, exits)
+ const sbitmap nodes;
+ edge **exits;
+{
+ edge e;
+ int node;
+ int num_exits;
+
+ *exits = NULL;
+
+ /* Check all nodes within the loop to see if there are any
+ successors not in the loop. Note that a node may have multiple
+ exiting edges. */
+ num_exits = 0;
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
+ for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
+ {
+ basic_block dest = e->dest;
+
+ if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
+ num_exits++;
+ }
+ });
+
+ if (! num_exits)
+ return 0;
+
+ *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
+
+ /* Store all exiting edges into an array. */
+ num_exits = 0;
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
+ for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
+ {
+ basic_block dest = e->dest;
+
+ if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
+ (*exits)[num_exits++] = e;
+ }
+ });
+
+ return num_exits;
+}
+
+
+/* Find the nodes contained within the loop with header HEADER and
+ latch LATCH and store in NODES. Return the number of nodes within
+ the loop. */
+static int
+flow_loop_nodes_find (header, latch, nodes)
+ basic_block header;
+ basic_block latch;
+ sbitmap nodes;
+{
+ basic_block *stack;
+ int sp;
+ int num_nodes = 0;
+
+ stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
+ sp = 0;
+
+ /* Start with only the loop header in the set of loop nodes. */
+ sbitmap_zero (nodes);
+ SET_BIT (nodes, header->index);
+ num_nodes++;
+ header->loop_depth++;
+
+ /* Push the loop latch on to the stack. */
+ if (! TEST_BIT (nodes, latch->index))
+ {
+ SET_BIT (nodes, latch->index);
+ latch->loop_depth++;
+ num_nodes++;
+ stack[sp++] = latch;
+ }
+
+ while (sp)
+ {
+ basic_block node;
+ edge e;
+
+ node = stack[--sp];
+ for (e = node->pred; e; e = e->pred_next)
+ {
+ basic_block ancestor = e->src;
+
+ /* If each ancestor not marked as part of loop, add to set of
+ loop nodes and push on to stack. */
+ if (ancestor != ENTRY_BLOCK_PTR
+ && ! TEST_BIT (nodes, ancestor->index))
+ {
+ SET_BIT (nodes, ancestor->index);
+ ancestor->loop_depth++;
+ num_nodes++;
+ stack[sp++] = ancestor;
+ }
+ }
+ }
+ free (stack);
+ return num_nodes;
+}
+
+
+/* Compute the depth first search order and store in the array
+ DFS_ORDER, marking the nodes visited in VISITED. Returns the
+ number of nodes visited. */
+static int
+flow_depth_first_order_compute (dfs_order)
+ int *dfs_order;
+{
+ edge e;
+ edge *stack;
+ int sp;
+ int dfsnum = 0;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = (edge *) xmalloc (n_basic_blocks * sizeof (edge));
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (n_basic_blocks);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Start with the first successor edge from the entry block. */
+ e = ENTRY_BLOCK_PTR->succ;
+ while (e)
+ {
+ basic_block src = e->src;
+ basic_block dest = e->dest;
+
+ /* Mark that we have visited this node. */
+ if (src != ENTRY_BLOCK_PTR)
+ SET_BIT (visited, src->index);
+
+ /* If this node has not been visited before, push the current
+ edge on to the stack and proceed with the first successor
+ edge of this node. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
+ && dest->succ)
+ {
+ stack[sp++] = e;
+ e = dest->succ;
+ }
+ else
+ {
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
+ && ! dest->succ)
+ {
+ /* DEST has no successors (for example, a non-returning
+ function is called) so do not push the current edge
+ but carry on with its next successor. */
+ dfs_order[dest->index] = n_basic_blocks - ++dfsnum;
+ SET_BIT (visited, dest->index);
+ }
+
+ while (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ {
+ dfs_order[src->index] = n_basic_blocks - ++dfsnum;
+
+ /* Pop edge off stack. */
+ e = stack[--sp];
+ src = e->src;
+ }
+ e = e->succ_next;
+ }
+ }
+ free (stack);
+ sbitmap_free (visited);
+
+ /* The number of nodes visited should not be greater than
+ n_basic_blocks. */
+ if (dfsnum > n_basic_blocks)
+ abort ();
+
+ /* There are some nodes left in the CFG that are unreachable. */
+ if (dfsnum < n_basic_blocks)
+ abort ();
+ return dfsnum;
+}
+
+
+/* Return the block for the pre-header of the loop with header
+ HEADER where DOM specifies the dominator information. Return NULL if
+ there is no pre-header. */
+static basic_block
+flow_loop_pre_header_find (header, dom)
+ basic_block header;
+ const sbitmap *dom;
+{
+ basic_block pre_header;
+ edge e;
+
+ /* If block p is a predecessor of the header and is the only block
+ that the header does not dominate, then it is the pre-header. */
+ pre_header = NULL;
+ for (e = header->pred; e; e = e->pred_next)
+ {
+ basic_block node = e->src;
+
+ if (node != ENTRY_BLOCK_PTR
+ && ! TEST_BIT (dom[node->index], header->index))
+ {
+ if (pre_header == NULL)
+ pre_header = node;
+ else
+ {
+ /* There are multiple edges into the header from outside
+ the loop so there is no pre-header block. */
+ pre_header = NULL;
+ break;
+ }
+ }
+ }
+ return pre_header;
+}
+
+
+/* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
+ previously added. The insertion algorithm assumes that the loops
+ are added in the order found by a depth first search of the CFG. */
+static void
+flow_loop_tree_node_add (prevloop, loop)
+ struct loop *prevloop;
+ struct loop *loop;
+{
+
+ if (flow_loop_nested_p (prevloop, loop))
+ {
+ prevloop->inner = loop;
+ loop->outer = prevloop;
+ return;
+ }
+
+ while (prevloop->outer)
+ {
+ if (flow_loop_nested_p (prevloop->outer, loop))
+ {
+ prevloop->next = loop;
+ loop->outer = prevloop->outer;
+ return;
+ }
+ prevloop = prevloop->outer;
+ }
+
+ prevloop->next = loop;
+ loop->outer = NULL;
+}
+
+
+/* Build the loop hierarchy tree for LOOPS. */
+static void
+flow_loops_tree_build (loops)
+ struct loops *loops;
+{
+ int i;
+ int num_loops;
+
+ num_loops = loops->num;
+ if (! num_loops)
+ return;
+
+ /* Root the loop hierarchy tree with the first loop found.
+ Since we used a depth first search this should be the
+ outermost loop. */
+ loops->tree = &loops->array[0];
+ loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
+
+ /* Add the remaining loops to the tree. */
+ for (i = 1; i < num_loops; i++)
+ flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
+}
+
+
+/* Helper function to compute loop nesting depth and enclosed loop level
+ for the natural loop specified by LOOP at the loop depth DEPTH.
+ Returns the loop level. */
+static int
+flow_loop_level_compute (loop, depth)
+ struct loop *loop;
+ int depth;
+{
+ struct loop *inner;
+ int level = 1;
+
+ if (! loop)
+ return 0;
+
+ /* Traverse loop tree assigning depth and computing level as the
+ maximum level of all the inner loops of this loop. The loop
+ level is equivalent to the height of the loop in the loop tree
+ and corresponds to the number of enclosed loop levels (including
+ itself). */
+ for (inner = loop->inner; inner; inner = inner->next)
+ {
+ int ilevel;
+
+ ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
+
+ if (ilevel > level)
+ level = ilevel;
+ }
+ loop->level = level;
+ loop->depth = depth;
+ return level;
+}
+
+
+/* Compute the loop nesting depth and enclosed loop level for the loop
+ hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
+ level. */
+
+static int
+flow_loops_level_compute (loops)
+ struct loops *loops;
+{
+ struct loop *loop;
+ int level;
+ int levels = 0;
+
+ /* Traverse all the outer level loops. */
+ for (loop = loops->tree; loop; loop = loop->next)
+ {
+ level = flow_loop_level_compute (loop, 1);
+ if (level > levels)
+ levels = level;
+ }
+ return levels;
+}
+
+
+/* Find all the natural loops in the function and save in LOOPS structure
+ and recalculate loop_depth information in basic block structures.
+ Return the number of natural loops found. */
+
+int
+flow_loops_find (loops)
+ struct loops *loops;
+{
+ int i;
+ int b;
+ int num_loops;
+ edge e;
+ sbitmap headers;
+ sbitmap *dom;
+ int *dfs_order;
+
+ loops->num = 0;
+ loops->array = NULL;
+ loops->tree = NULL;
+ dfs_order = NULL;
+
+ /* Taking care of this degenerate case makes the rest of
+ this code simpler. */
+ if (n_basic_blocks == 0)
+ return 0;
+
+ /* Compute the dominators. */
+ dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ compute_flow_dominators (dom, NULL);
+
+ /* Count the number of loop edges (back edges). This should be the
+ same as the number of natural loops. Also clear the loop_depth
+ and as we work from inner->outer in a loop nest we call
+ find_loop_nodes_find which will increment loop_depth for nodes
+ within the current loop, which happens to enclose inner loops. */
+
+ num_loops = 0;
+ for (b = 0; b < n_basic_blocks; b++)
+ {
+ BASIC_BLOCK (b)->loop_depth = 0;
+ for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
+ {
+ basic_block latch = e->src;
+
+ /* Look for back edges where a predecessor is dominated
+ by this block. A natural loop has a single entry
+ node (header) that dominates all the nodes in the
+ loop. It also has single back edge to the header
+ from a latch node. Note that multiple natural loops
+ may share the same header. */
+ if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
+ num_loops++;
+ }
+ }
+
+ if (num_loops)
+ {
+ /* Compute depth first search order of the CFG so that outer
+ natural loops will be found before inner natural loops. */
+ dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
+ flow_depth_first_order_compute (dfs_order);
+
+ /* Allocate loop structures. */
+ loops->array
+ = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
+
+ headers = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (headers);
+
+ loops->shared_headers = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (loops->shared_headers);
+
+ /* Find and record information about all the natural loops
+ in the CFG. */
+ num_loops = 0;
+ for (b = 0; b < n_basic_blocks; b++)
+ {
+ basic_block header;
+
+ /* Search the nodes of the CFG in DFS order that we can find
+ outer loops first. */
+ header = BASIC_BLOCK (dfs_order[b]);
+
+ /* Look for all the possible latch blocks for this header. */
+ for (e = header->pred; e; e = e->pred_next)
+ {
+ basic_block latch = e->src;
+
+ /* Look for back edges where a predecessor is dominated
+ by this block. A natural loop has a single entry
+ node (header) that dominates all the nodes in the
+ loop. It also has single back edge to the header
+ from a latch node. Note that multiple natural loops
+ may share the same header. */
+ if (latch != ENTRY_BLOCK_PTR
+ && TEST_BIT (dom[latch->index], header->index))
+ {
+ struct loop *loop;
+
+ loop = loops->array + num_loops;
+
+ loop->header = header;
+ loop->latch = latch;
+
+ /* Keep track of blocks that are loop headers so
+ that we can tell which loops should be merged. */
+ if (TEST_BIT (headers, header->index))
+ SET_BIT (loops->shared_headers, header->index);
+ SET_BIT (headers, header->index);
+
+ /* Find nodes contained within the loop. */
+ loop->nodes = sbitmap_alloc (n_basic_blocks);
+ loop->num_nodes
+ = flow_loop_nodes_find (header, latch, loop->nodes);
+
+ /* Compute first and last blocks within the loop.
+ These are often the same as the loop header and
+ loop latch respectively, but this is not always
+ the case. */
+ loop->first
+ = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
+ loop->last
+ = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
+
+ /* Find edges which exit the loop. Note that a node
+ may have several exit edges. */
+ loop->num_exits
+ = flow_loop_exits_find (loop->nodes, &loop->exits);
+
+ /* Look to see if the loop has a pre-header node. */
+ loop->pre_header
+ = flow_loop_pre_header_find (header, dom);
+
+ num_loops++;
+ }
+ }
+ }
+
+ /* Natural loops with shared headers may either be disjoint or
+ nested. Disjoint loops with shared headers cannot be inner
+ loops and should be merged. For now just mark loops that share
+ headers. */
+ for (i = 0; i < num_loops; i++)
+ if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
+ loops->array[i].shared = 1;
+
+ sbitmap_free (headers);
+ }
+
+ loops->num = num_loops;
+
+ /* Save CFG derived information to avoid recomputing it. */
+ loops->cfg.dom = dom;
+ loops->cfg.dfs_order = dfs_order;
+
+ /* Build the loop hierarchy tree. */
+ flow_loops_tree_build (loops);
+
+ /* Assign the loop nesting depth and enclosed loop level for each
+ loop. */
+ loops->levels = flow_loops_level_compute (loops);
+
+ return num_loops;
+}
+
+
+/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
+int
+flow_loop_outside_edge_p (loop, e)
+ const struct loop *loop;
+ edge e;
+{
+ if (e->dest != loop->header)
+ abort ();
+ return (e->src == ENTRY_BLOCK_PTR)
+ || ! TEST_BIT (loop->nodes, e->src->index);
+}
+
+
+typedef struct reorder_block_def {
+ int flags;
+ int index;
+ basic_block add_jump;
+ edge succ;
+ rtx end;
+ int block_begin;
+ int block_end;
+} *reorder_block_def;
+
+#define REORDER_BLOCK_HEAD 0x1
+#define REORDER_BLOCK_VISITED 0x2
+#define REORDER_MOVED_BLOCK_END 0x3
+
+#define REORDER_BLOCK_FLAGS(bb) \
+ ((reorder_block_def) (bb)->aux)->flags
+
+#define REORDER_BLOCK_INDEX(bb) \
+ ((reorder_block_def) (bb)->aux)->index
+
+#define REORDER_BLOCK_ADD_JUMP(bb) \
+ ((reorder_block_def) (bb)->aux)->add_jump
+
+#define REORDER_BLOCK_SUCC(bb) \
+ ((reorder_block_def) (bb)->aux)->succ
+
+#define REORDER_BLOCK_OLD_END(bb) \
+ ((reorder_block_def) (bb)->aux)->end
+
+#define REORDER_BLOCK_BEGIN(bb) \
+ ((reorder_block_def) (bb)->aux)->block_begin
+
+#define REORDER_BLOCK_END(bb) \
+ ((reorder_block_def) (bb)->aux)->block_end
+
+
+static int reorder_index;
+static basic_block reorder_last_visited;
+
+enum reorder_skip_type {REORDER_SKIP_BEFORE, REORDER_SKIP_AFTER,
+ REORDER_SKIP_BLOCK_END};
+
+static rtx skip_insns_between_block PARAMS ((basic_block,
+ enum reorder_skip_type));
+
+/* Skip over insns BEFORE or AFTER BB which are typically associated with
+ basic block BB. */
+
+static rtx
+skip_insns_between_block (bb, skip_type)
+ basic_block bb;
+ enum reorder_skip_type skip_type;
+{
+ rtx insn, last_insn;
+
+ if (skip_type == REORDER_SKIP_BEFORE)
+ {
+ if (bb == ENTRY_BLOCK_PTR)
+ return 0;
+
+ last_insn = bb->head;
+ for (insn = PREV_INSN (bb->head);
+ insn && insn != BASIC_BLOCK (bb->index - 1)->end;
+ last_insn = insn, insn = PREV_INSN (insn))
+ {
+ if (NEXT_INSN (insn) != last_insn)
+ break;
+
+ if (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END)
+ continue;
+
+ break;
+ }
+ }
+
+ else
+ {
+ last_insn = bb->end;
+
+ if (bb == EXIT_BLOCK_PTR)
+ return 0;
+
+ for (insn = NEXT_INSN (bb->end);
+ insn;
+ last_insn = insn, insn = NEXT_INSN (insn))
+ {
+ if (bb->index + 1 != n_basic_blocks
+ && insn == BASIC_BLOCK (bb->index + 1)->head)
+ break;
+
+ if (GET_CODE (insn) == BARRIER
+ || GET_CODE (insn) == JUMP_INSN
+ || (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)))
+ continue;
+
+ if (GET_CODE (insn) == CODE_LABEL
+ && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
+ || GET_CODE (PATTERN
+ (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
+ {
+ insn = NEXT_INSN (insn);
+ continue;
+ }
+ break;
+ }
+
+ if (skip_type == REORDER_SKIP_BLOCK_END)
+ {
+ int found_block_end = 0;
+
+ for (; insn; last_insn = insn, insn = NEXT_INSN (insn))
+ {
+ if (bb->index + 1 != n_basic_blocks
+ && insn == BASIC_BLOCK (bb->index + 1)->head)
+ break;
+
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
+ {
+ found_block_end = 1;
+ continue;
+ }
+
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
+ continue;
+
+ if (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) >= 0
+ && NEXT_INSN (insn)
+ && (NOTE_LINE_NUMBER (NEXT_INSN (insn))
+ == NOTE_INSN_BLOCK_END))
+ continue;
+ break;
+ }
+
+ if (! found_block_end)
+ last_insn = 0;
+ }
+ }
+
+ return last_insn;
+}
+
+
+/* Return common destination for blocks BB0 and BB1. */
+
+static basic_block
+get_common_dest (bb0, bb1)
+ basic_block bb0, bb1;
+{
+ edge e0, e1;
+
+ for (e0 = bb0->succ; e0; e0 = e0->succ_next)
+ {
+ for (e1 = bb1->succ; e1; e1 = e1->succ_next)
+ {
+ if (e0->dest == e1->dest)
+ {
+ return e0->dest;
+ }
+ }
+ }
+ return 0;
+}
+
+
+/* Move the destination block for edge E after chain end block CEB
+ Adding jumps and labels is deferred until fixup_reorder_chain. */
+
+static basic_block
+chain_reorder_blocks (e, ceb)
+ edge e;
+ basic_block ceb;
+{
+ basic_block sb = e->src;
+ basic_block db = e->dest;
+ rtx cebe_insn, cebbe_insn, dbh_insn, dbe_insn;
+ edge ee, last_edge;
+
+ enum cond_types {NO_COND, PREDICT_THEN_WITH_ELSE, PREDICT_ELSE,
+ PREDICT_THEN_NO_ELSE, PREDICT_NOT_THEN_NO_ELSE};
+ enum cond_types cond_type;
+ enum cond_block_types {NO_COND_BLOCK, THEN_BLOCK, ELSE_BLOCK,
+ NO_ELSE_BLOCK};
+ enum cond_block_types cond_block_type;
+
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ "Edge from basic block %d to basic block %d last visited %d\n",
+ sb->index, db->index, ceb->index);
+
+ dbh_insn = skip_insns_between_block (db, REORDER_SKIP_BEFORE);
+ cebe_insn = skip_insns_between_block (ceb, REORDER_SKIP_AFTER);
+ cebbe_insn = skip_insns_between_block (ceb, REORDER_SKIP_BLOCK_END);
+
+ {
+ int block_begins = 0;
+ rtx insn;
+
+ for (insn = dbh_insn; insn && insn != db->end; insn = NEXT_INSN (insn))
+ {
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG)
+ {
+ block_begins += 1;
+ break;
+ }
+ }
+ REORDER_BLOCK_BEGIN (sb) = block_begins;
+ }
+
+ if (cebbe_insn)
+ {
+ int block_ends = 0;
+ rtx insn;
+
+ for (insn = cebe_insn; insn; insn = NEXT_INSN (insn))
+ {
+ if (PREV_INSN (insn) == cebbe_insn)
+ break;
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
+ {
+ block_ends += 1;
+ continue;
+ }
+ }
+ REORDER_BLOCK_END (ceb) = block_ends;
+ }
+
+ /* Blocks are in original order. */
+ if (sb->index == ceb->index
+ && ceb->index + 1 == db->index && NEXT_INSN (cebe_insn))
+ return db;
+
+ /* Get the type of block and type of condition. */
+ cond_type = NO_COND;
+ cond_block_type = NO_COND_BLOCK;
+ if (GET_CODE (sb->end) == JUMP_INSN && ! simplejump_p (sb->end)
+ && condjump_p (sb->end))
+ {
+ if (e->flags & EDGE_FALLTHRU)
+ cond_block_type = THEN_BLOCK;
+ else if (get_common_dest (sb->succ->dest, sb))
+ cond_block_type = NO_ELSE_BLOCK;
+ else
+ cond_block_type = ELSE_BLOCK;
+
+ if (sb->succ->succ_next
+ && get_common_dest (sb->succ->dest, sb))
+ {
+ if (cond_block_type == THEN_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_THEN_NO_ELSE;
+ else
+ cond_type = PREDICT_NOT_THEN_NO_ELSE;
+ }
+ else if (cond_block_type == NO_ELSE_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_NOT_THEN_NO_ELSE;
+ else
+ cond_type = PREDICT_THEN_NO_ELSE;
+ }
+ }
+ else
+ {
+ if (cond_block_type == THEN_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_THEN_WITH_ELSE;
+ else
+ cond_type = PREDICT_ELSE;
+ }
+ else if (cond_block_type == ELSE_BLOCK
+ && sb->succ->dest != EXIT_BLOCK_PTR)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_ELSE;
+ else
+ cond_type = PREDICT_THEN_WITH_ELSE;
+ }
+ }
+ }
+
+ if (rtl_dump_file)
+ {
+ static const char * cond_type_str [] = {"not cond jump", "predict then",
+ "predict else",
+ "predict then w/o else",
+ "predict not then w/o else"};
+ static const char * cond_block_type_str [] = {"not then or else block",
+ "then block",
+ "else block",
+ "then w/o else block"};
+
+ fprintf (rtl_dump_file, " %s (looking at %s)\n",
+ cond_type_str[(int)cond_type],
+ cond_block_type_str[(int)cond_block_type]);
+ }
+
+ /* Reflect that then block will move and we'll jump to it. */
+ if (cond_block_type != THEN_BLOCK
+ && (cond_type == PREDICT_ELSE
+ || cond_type == PREDICT_NOT_THEN_NO_ELSE))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ " then jump from block %d to block %d\n",
+ sb->index, sb->succ->dest->index);
+
+ /* Jump to reordered then block. */
+ REORDER_BLOCK_ADD_JUMP (sb) = sb->succ->dest;
+ }
+
+ /* Reflect that then block will jump back when we have no else. */
+ if (cond_block_type != THEN_BLOCK
+ && cond_type == PREDICT_NOT_THEN_NO_ELSE)
+ {
+ for (ee = sb->succ->dest->succ;
+ ee && ! (ee->flags & EDGE_FALLTHRU);
+ ee = ee->succ_next)
+ continue;
+
+ if (ee && ! (GET_CODE (sb->succ->dest->end) == JUMP_INSN
+ && ! simplejump_p (sb->succ->dest->end)))
+ {
+ REORDER_BLOCK_ADD_JUMP (sb->succ->dest) = ee->dest;
+ }
+ }
+
+ /* Reflect that else block will jump back. */
+ if (cond_block_type == ELSE_BLOCK
+ && (cond_type == PREDICT_THEN_WITH_ELSE || cond_type == PREDICT_ELSE))
+ {
+ last_edge=db->succ;
+
+ if (last_edge
+ && last_edge->dest != EXIT_BLOCK_PTR
+ && GET_CODE (last_edge->dest->head) == CODE_LABEL
+ && ! (GET_CODE (db->end) == JUMP_INSN))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ " else jump from block %d to block %d\n",
+ db->index, last_edge->dest->index);
+
+ REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
+ }
+ }
+
+ /* This block's successor has already been reordered. This can happen
+ when we reorder a chain starting at a then or else. */
+ for (last_edge = db->succ;
+ last_edge && ! (last_edge->flags & EDGE_FALLTHRU);
+ last_edge = last_edge->succ_next)
+ continue;
+
+ if (last_edge
+ && last_edge->dest != EXIT_BLOCK_PTR
+ && (REORDER_BLOCK_FLAGS (last_edge->dest)
+ & REORDER_BLOCK_VISITED))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ " end of chain jump from block %d to block %d\n",
+ db->index, last_edge->dest->index);
+
+ REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
+ }
+
+ dbh_insn = skip_insns_between_block (db, REORDER_SKIP_BEFORE);
+ cebe_insn = skip_insns_between_block (ceb, REORDER_SKIP_AFTER);
+ dbe_insn = skip_insns_between_block (db, REORDER_SKIP_AFTER);
+
+ /* Leave behind any lexical block markers. */
+ if (debug_info_level > DINFO_LEVEL_TERSE
+ && ceb->index + 1 < db->index)
+ {
+ rtx insn, last_insn = get_last_insn ();
+ insn = NEXT_INSN (ceb->end);
+ if (! insn)
+ insn = REORDER_BLOCK_OLD_END (ceb);
+
+ if (NEXT_INSN (cebe_insn) == 0)
+ set_last_insn (cebe_insn);
+ for (; insn && insn != db->head/*dbh_insn*/;
+ insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG))
+ {
+ cebe_insn = emit_note_after (NOTE_INSN_BLOCK_BEG, cebe_insn);
+ delete_insn (insn);
+ }
+ if (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
+ {
+ cebe_insn = emit_note_after (NOTE_INSN_BLOCK_END, cebe_insn);
+ delete_insn (insn);
+ }
+ }
+ set_last_insn (last_insn);
+ }
+
+ /* Rechain predicted block. */
+ NEXT_INSN (cebe_insn) = dbh_insn;
+ PREV_INSN (dbh_insn) = cebe_insn;
+
+ REORDER_BLOCK_OLD_END (db) = NEXT_INSN (dbe_insn);
+ if (db->index != n_basic_blocks - 1)
+ NEXT_INSN (dbe_insn) = 0;
+
+ return db;
+}
+
+
+/* Reorder blocks starting at block B. */
+
+static void
+make_reorder_chain (bb)
+ basic_block bb;
+{
+ edge e;
+ basic_block visited_edge = NULL;
+ rtx block_end;
+ int probability;
+
+ if (bb == EXIT_BLOCK_PTR)
+ return;
+
+ /* Find the most probable block. */
+ e = bb->succ;
+ block_end = bb->end;
+ if (GET_CODE (block_end) == JUMP_INSN && condjump_p (block_end))
+ {
+ rtx note = find_reg_note (block_end, REG_BR_PROB, 0);
+
+ if (note)
+ probability = XINT (XEXP (note, 0), 0);
+ else
+ probability = 0;
+
+ if (probability >= REG_BR_PROB_BASE / 2)
+ e = bb->succ->succ_next;
+ }
+
+ /* Add chosen successor to chain and recurse on it. */
+ if (e && e->dest != EXIT_BLOCK_PTR
+ && e->dest != e->src
+ && (! (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
+ || (REORDER_BLOCK_FLAGS (e->dest) == REORDER_BLOCK_HEAD)))
+ {
+ if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
+ {
+ REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_HEAD;
+ REORDER_BLOCK_INDEX (bb) = reorder_index++;
+ REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
+ }
+
+ if (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
+ REORDER_BLOCK_FLAGS (e->dest) &= ~REORDER_BLOCK_HEAD;
+
+ REORDER_BLOCK_SUCC (bb) = e;
+
+ visited_edge = e->dest;
+
+ reorder_last_visited = chain_reorder_blocks (e, bb);
+
+ if (e->dest
+ && ! (REORDER_BLOCK_FLAGS (e->dest)
+ & REORDER_BLOCK_VISITED))
+ make_reorder_chain (e->dest);
+ }
+ else
+ {
+ if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
+ {
+ REORDER_BLOCK_INDEX (bb) = reorder_index++;
+ REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
+ }
+ }
+
+ /* Recurse on the successors. */
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest && e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (e->dest
+ && e->dest != e->src
+ && e->dest != visited_edge
+ && ! (REORDER_BLOCK_FLAGS (e->dest)
+ & REORDER_BLOCK_VISITED))
+ {
+ reorder_last_visited
+ = chain_reorder_blocks (e, reorder_last_visited);
+ make_reorder_chain (e->dest);
+ }
+ }
+}
+
+
+/* Fixup jumps and labels after reordering basic blocks. */
+
+static void
+fixup_reorder_chain ()
+{
+ int i, j;
+ rtx insn;
+
+ /* Set the new last insn. */
+ for (i = 0;
+ i < n_basic_blocks - 1
+ && REORDER_BLOCK_INDEX (BASIC_BLOCK (i)) != n_basic_blocks;
+ i++)
+ continue;
+
+ for (insn = BASIC_BLOCK (i)->head;
+ NEXT_INSN (insn) != 0;
+ insn = NEXT_INSN (insn))
+ continue;
+
+ set_last_insn (insn);
+
+ /* Add jumps and labels to fixup blocks. */
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ if (REORDER_BLOCK_ADD_JUMP (BASIC_BLOCK (i)))
+ {
+ rtx new_label = gen_label_rtx ();
+ rtx label_insn, jump_insn, barrier_insn;
+
+ label_insn = emit_label_before (new_label,
+ REORDER_BLOCK_ADD_JUMP (BASIC_BLOCK (i))->head);
+ REORDER_BLOCK_ADD_JUMP (BASIC_BLOCK (i))->head = label_insn;
+
+ jump_insn = emit_jump_insn_after (gen_jump (label_insn),
+ BASIC_BLOCK (i)->end);
+ JUMP_LABEL (jump_insn) = label_insn;
+ ++LABEL_NUSES (label_insn);
+ barrier_insn = emit_barrier_after (jump_insn);
+ if (GET_CODE (BASIC_BLOCK (i)->end) != JUMP_INSN)
+ BASIC_BLOCK (i)->end = barrier_insn;
+ /* Add block for jump. Typically this is when a then is not
+ predicted and we are jumping to the moved then block. */
+ else
+ {
+ basic_block b;
+
+ b = (basic_block) obstack_alloc (function_obstack, sizeof (*b));
+ VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+ BASIC_BLOCK (n_basic_blocks - 1) = b;
+ b->index = n_basic_blocks - 1;
+ b->head = emit_note_before (NOTE_INSN_BASIC_BLOCK, jump_insn);
+ NOTE_BASIC_BLOCK (b->head) = b;
+ b->end = barrier_insn;
+
+ {
+ basic_block nb = BASIC_BLOCK (n_basic_blocks - 1);
+ nb->global_live_at_start
+ = OBSTACK_ALLOC_REG_SET (function_obstack);
+ nb->global_live_at_end
+ = OBSTACK_ALLOC_REG_SET (function_obstack);
+
+ COPY_REG_SET (nb->global_live_at_start,
+ BASIC_BLOCK (i)->global_live_at_start);
+ COPY_REG_SET (nb->global_live_at_end,
+ BASIC_BLOCK (i)->global_live_at_start);
+ if (BASIC_BLOCK (i)->local_set)
+ {
+ OBSTACK_ALLOC_REG_SET (function_obstack);
+ COPY_REG_SET (nb->local_set, BASIC_BLOCK (i)->local_set);
+ }
+ else
+ BASIC_BLOCK (nb->index)->local_set = 0;
+
+ nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
+ REORDER_BLOCK_INDEX (BASIC_BLOCK (n_basic_blocks - 1))
+ = REORDER_BLOCK_INDEX (BASIC_BLOCK (i)) + 1;
+ /* Relink to new block. */
+ nb->succ = BASIC_BLOCK (i)->succ;
+
+ make_edge (0, BASIC_BLOCK (i), nb, 0);
+ BASIC_BLOCK (i)->succ->succ_next
+ = BASIC_BLOCK (i)->succ->succ_next->succ_next;
+ nb->succ->succ_next = 0;
+ /* Fix reorder block index to reflect new block. */
+ for (j = 0; j < n_basic_blocks - 1; j++)
+ {
+ basic_block bbj = BASIC_BLOCK (j);
+ basic_block bbi = BASIC_BLOCK (i);
+ if (REORDER_BLOCK_INDEX (bbj)
+ >= REORDER_BLOCK_INDEX (bbi) + 1)
+ REORDER_BLOCK_INDEX (bbj)++;
+ }
+ }
+ }
+ }
+ }
+}
+
+
+/* Reorder basic blocks. */
+
+void
+reorder_basic_blocks ()
+{
+ int i, j;
+ struct loops loops_info;
+ int num_loops;
+ rtx last_insn;
+
+ if (profile_arc_flag)
+ return;
+
+ if (n_basic_blocks <= 1)
+ return;
+
+ /* Exception edges are not currently handled. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ edge e;
+
+ for (e = BASIC_BLOCK (i)->succ; e && ! (e->flags & EDGE_EH);
+ e = e->succ_next)
+ continue;
+
+ if (e && (e->flags & EDGE_EH))
+ return;
+ }
+
+ reorder_index = 0;
+
+ /* Find natural loops using the CFG. */
+ num_loops = flow_loops_find (&loops_info);
+
+ /* Dump loop information. */
+ flow_loops_dump (&loops_info, rtl_dump_file, 0);
+
+ /* Estimate using heuristics if no profiling info is available. */
+ if (! flag_branch_probabilities)
+ estimate_probability (&loops_info);
+
+ reorder_last_visited = BASIC_BLOCK (0);
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def));
+ }
+
+ last_insn
+ = NEXT_INSN (skip_insns_between_block (BASIC_BLOCK (n_basic_blocks - 1),
+ REORDER_SKIP_AFTER));
+
+ make_reorder_chain (BASIC_BLOCK (0));
+
+ fixup_reorder_chain ();
+
+#ifdef ENABLE_CHECKING
+ {
+ rtx insn, last_insn;
+ last_insn = get_insns ();
+ for (insn = NEXT_INSN (get_insns ());
+ insn && PREV_INSN (insn) == last_insn
+ && NEXT_INSN (PREV_INSN (insn)) == insn;
+ last_insn = insn,
+ insn = NEXT_INSN (insn))
+ continue;
+
+ if (insn)
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "insn chaining error at %d\n",
+ INSN_UID (last_insn));
+ abort();
+ }
+ }
+#endif
+
+ /* Put basic_block_info in new order. */
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ for (j = i; i != REORDER_BLOCK_INDEX (BASIC_BLOCK (j)); j++)
+ continue;
+
+ if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j)) == i
+ && i != j)
+ {
+ basic_block tempbb;
+ int temprbi;
+ int rbi = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
+
+ temprbi = BASIC_BLOCK (rbi)->index;
+ BASIC_BLOCK (rbi)->index = BASIC_BLOCK (j)->index;
+ BASIC_BLOCK (j)->index = temprbi;
+ tempbb = BASIC_BLOCK (rbi);
+ BASIC_BLOCK (rbi) = BASIC_BLOCK (j);
+ BASIC_BLOCK (j) = tempbb;
+ }
+ }
+
+ NEXT_INSN (BASIC_BLOCK (n_basic_blocks - 1)->end) = last_insn;
+
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ free (BASIC_BLOCK (i)->aux);
+ }
+
+ /* Free loop information. */
+ flow_loops_free (&loops_info);
+}
+
+
+/* Clear LOG_LINKS fields of insns in a chain. */
+void
+clear_log_links (insns)
+ rtx insns;
+{
+ rtx i;
+ for (i = insns; i; i = NEXT_INSN (i))
+ if (GET_RTX_CLASS (GET_CODE (i)) == 'i')
+ LOG_LINKS (i) = 0;
+}
OSDN Git Service
