/* 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"
+#include "splay-tree.h"
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
#ifndef HAVE_epilogue
#define HAVE_epilogue 0
#endif
-
#ifndef HAVE_prologue
#define HAVE_prologue 0
#endif
+#ifndef HAVE_sibcall_epilogue
+#define HAVE_sibcall_epilogue 0
+#endif
/* The contents of the current function definition are allocated
in this obstack, and all are freed at the end of the function.
/* 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 */
varray_type reg_n_info;
-/* Size of the reg_n_info table. */
-
-unsigned int reg_n_max;
-
-/* Element N is the next insn that uses (hard or pseudo) register number N
- within the current basic block; or zero, if there is no such insn.
- This is valid only during the final backward scan in propagate_block. */
-
-static rtx *reg_next_use;
-
/* Size of a regset for the current function,
in (1) bytes and (2) elements. */
are another pair, etc. */
rtx regs_may_share;
-/* Depth within loops of basic block being scanned for lifetime analysis,
- plus one. This is the weight attached to references to registers. */
-
-static int loop_depth;
-
-/* During propagate_block, this is non-zero if the value of CC0 is live. */
-
-static int cc0_live;
-
-/* During propagate_block, this contains a list of all the MEMs we are
- tracking for dead store elimination. */
-
-static rtx mem_set_list;
-
/* Set of registers that may be eliminable. These are handled specially
in updating regs_ever_live. */
static rtx label_value_list;
-/* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
+/* Holds information for tracking conditional register life information. */
+struct reg_cond_life_info
+{
+ /* An EXPR_LIST of conditions under which a register is dead. */
+ rtx condition;
+
+ /* ??? Could store mask of bytes that are dead, so that we could finally
+ track lifetimes of multi-word registers accessed via subregs. */
+};
+
+/* For use in communicating between propagate_block and its subroutines.
+ Holds all information needed to compute life and def-use information. */
+
+struct propagate_block_info
+{
+ /* The basic block we're considering. */
+ basic_block bb;
+
+ /* Bit N is set if register N is conditionally or unconditionally live. */
+ regset reg_live;
+
+ /* Bit N is set if register N is set this insn. */
+ regset new_set;
-#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;
+ /* Element N is the next insn that uses (hard or pseudo) register N
+ within the current basic block; or zero, if there is no such insn. */
+ rtx *reg_next_use;
+
+ /* Contains a list of all the MEMs we are tracking for dead store
+ elimination. */
+ rtx mem_set_list;
+
+ /* If non-null, record the set of registers set in the basic block. */
+ regset local_set;
+
+#ifdef HAVE_conditional_execution
+ /* Indexed by register number, holds a reg_cond_life_info for each
+ register that is not unconditionally live or dead. */
+ splay_tree reg_cond_dead;
+
+ /* Bit N is set if register N is in an expression in reg_cond_dead. */
+ regset reg_cond_reg;
+#endif
+
+ /* Non-zero if the value of CC0 is live. */
+ int cc0_live;
+
+ /* Flags controling the set of information propagate_block collects. */
+ int flags;
+};
/* 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 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 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 int merge_blocks PARAMS ((edge,basic_block,basic_block));
+static void try_merge_blocks PARAMS ((void));
+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 int set_phi_alternative_reg PARAMS ((rtx, int, int, void *));
+static void calculate_global_regs_live PARAMS ((sbitmap, sbitmap, int));
+static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
+static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
+static int insn_dead_p PARAMS ((struct propagate_block_info *,
+ rtx, int, rtx));
+static int libcall_dead_p PARAMS ((struct propagate_block_info *,
+ rtx, rtx, rtx));
+static void mark_set_regs PARAMS ((struct propagate_block_info *,
+ rtx, rtx));
+static void mark_set_1 PARAMS ((struct propagate_block_info *,
+ enum rtx_code, rtx, rtx,
+ rtx, int));
+#ifdef HAVE_conditional_execution
+static int mark_regno_cond_dead PARAMS ((struct propagate_block_info *,
+ int, rtx));
+static void free_reg_cond_life_info PARAMS ((splay_tree_value));
+static int flush_reg_cond_reg_1 PARAMS ((splay_tree_node, void *));
+static void flush_reg_cond_reg PARAMS ((struct propagate_block_info *,
+ int));
+static rtx ior_reg_cond PARAMS ((rtx, rtx));
+static rtx not_reg_cond PARAMS ((rtx));
+static rtx nand_reg_cond PARAMS ((rtx, rtx));
+#endif
#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 ((struct propagate_block_info *,
+ rtx, rtx));
+static int try_pre_increment_1 PARAMS ((struct propagate_block_info *,
+ 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));
-
-/* 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));
-
+static void mark_used_reg PARAMS ((struct propagate_block_info *,
+ rtx, rtx, rtx));
+static void mark_used_regs PARAMS ((struct propagate_block_info *,
+ rtx, rtx, rtx));
+void dump_flow_info PARAMS ((FILE *));
+void debug_flow_info PARAMS ((void));
+static void dump_edge_info PARAMS ((FILE *, edge, int));
+
+static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
+ 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 *));
\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
register int count = 0;
int eh_region = 0;
int call_had_abnormal_edge = 0;
- rtx prev_call = NULL_RTX;
prev_code = JUMP_INSN;
for (insn = f; insn; insn = NEXT_INSN (insn))
&& (prev_code == JUMP_INSN
|| prev_code == BARRIER
|| (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);
- }
- }
+ count++;
/* Record whether this call created an edge. */
if (code == CALL_INSN)
{
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
- int region = (note ? XWINT (XEXP (note, 0), 0) : 1);
- prev_call = insn;
+ int region = (note ? INTVAL (XEXP (note, 0)) : 1);
+
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 if (nonlocal_goto_handler_labels && region >= 0)
+ /* If there is a nonlocal goto label and the specified
+ region number isn't -1, we have an edge. (0 means
+ no throw, but might have a nonlocal goto). */
call_had_abnormal_edge = 1;
- else
- {
- /* If there is a nonlocal goto label and the specified
- region number isn't -1, we have an edge. (0 means
- no throw, but might have a nonlocal goto). */
- if (nonlocal_goto_handler_labels && region >= 0)
- call_had_abnormal_edge = 1;
- }
}
- else if (code != NOTE)
- prev_call = NULL_RTX;
if (code != NOTE)
prev_code = code;
++eh_region;
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
--eh_region;
-
}
/* The rest of the compiler works a bit smoother when we don't have to
rtx f;
{
register rtx insn, next;
- int call_has_abnormal_edge = 0;
int i = 0;
rtx bb_note = NULL_RTX;
rtx eh_list = NULL_RTX;
next = NEXT_INSN (insn);
- if (code == CALL_INSN)
- {
- /* Record whether this call created an edge. */
- rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
- 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)
- call_has_abnormal_edge = 1;
- else
- {
- /* If there is a nonlocal goto label and the specified
- region number isn't -1, we have an edge. (0 means
- no throw, but might have a nonlocal goto). */
- if (nonlocal_goto_handler_labels && region >= 0)
- call_has_abnormal_edge = 1;
- }
- }
-
switch (code)
{
case NOTE:
else if (kind == NOTE_INSN_EH_REGION_END)
{
rtx t = eh_list;
+
eh_list = XEXP (eh_list, 1);
free_INSN_LIST_node (t);
}
{
if (bb_note == NULL_RTX)
bb_note = insn;
+
next = flow_delete_insn (insn);
}
-
break;
}
does not imply an abnormal edge, it will be a bit before
everything can be updated. So continue to emit a noop at
the end of such a block. */
- if (GET_CODE (end) == CALL_INSN)
+ if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
{
rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
end = emit_insn_after (nop, end);
create_basic_block (i++, head, end, bb_note);
bb_note = NULL_RTX;
}
+
head = end = insn;
break;
imply an abnormal edge, it will be a bit before everything can
be updated. So continue to emit a noop at the end of such a
block. */
- if (GET_CODE (end) == CALL_INSN)
+ if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
{
rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
end = emit_insn_after (nop, end);
goto new_bb_exclusive;
case CALL_INSN:
- /* A basic block ends at a call that can either throw or
- do a non-local goto. */
- if (call_has_abnormal_edge)
- {
- new_bb_inclusive:
- if (head == NULL_RTX)
- head = insn;
- end = insn;
+ {
+ /* Record whether this call created an edge. */
+ rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
+ int region = (note ? INTVAL (XEXP (note, 0)) : 1);
+ int call_has_abnormal_edge = 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 if (nonlocal_goto_handler_labels && region >= 0)
+ /* If there is a nonlocal goto label and the specified
+ region number isn't -1, we have an edge. (0 means
+ no throw, but might have a nonlocal goto). */
+ call_has_abnormal_edge = 1;
- new_bb_exclusive:
- create_basic_block (i++, head, end, bb_note);
- head = end = NULL_RTX;
- bb_note = NULL_RTX;
- break;
+ /* A basic block ends at a call that can either throw or
+ do a non-local goto. */
+ if (call_has_abnormal_edge)
+ {
+ new_bb_inclusive:
+ if (head == NULL_RTX)
+ head = insn;
+ end = insn;
+
+ new_bb_exclusive:
+ create_basic_block (i++, head, end, bb_note);
+ head = end = NULL_RTX;
+ bb_note = NULL_RTX;
+ break;
+ }
}
/* FALLTHRU */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
{
- rtx lab = XEXP (note, 0), next;
+ rtx lab = XEXP (note, 0), next;
if (lab == eh_return_stub_label)
- ;
+ ;
else if ((next = next_nonnote_insn (lab)) != NULL
&& GET_CODE (next) == JUMP_INSN
&& (GET_CODE (PATTERN (next)) == ADDR_VEC
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. */
-static void
+void
create_basic_block (index, head, end, bb_note)
int index;
rtx head, end, bb_note;
}
}
+ /* If this is a sibling call insn, then this is in effect a
+ combined call and return, and so we need an edge to the
+ exit block. No need to worry about EH edges, since we
+ wouldn't have created the sibling call in the first place. */
+
+ if (code == CALL_INSN && SIBLING_CALL_P (insn))
+ make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
+ else
+
/* If this is a CALL_INSN, then mark it as reaching the active EH
handler for this CALL_INSN. If we're handling asynchronous
exceptions then any insn can reach any of the active handlers.
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. */
/* We do know that a REG_EH_REGION note with a value less
than 0 is guaranteed not to perform a non-local goto. */
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
- if (!note || XINT (XEXP (note, 0), 0) >= 0)
+ if (!note || INTVAL (XEXP (note, 0)) >= 0)
for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
make_label_edge (edge_cache, bb, XEXP (x, 0),
EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
/* 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)
}
/* Delete all unreachable basic blocks. Count down so that we don't
- interfere with the block renumbering that happens in delete_block. */
+ interfere with the block renumbering that happens in flow_delete_block. */
deleted_handler = 0;
/* This block was found. Tidy up the mark. */
b->aux = NULL;
else
- deleted_handler |= delete_block (b);
+ deleted_handler |= flow_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;
/* ??? Preserving all such notes strikes me as wrong. It would be nice
to post-process the stream to remove empty blocks, loops, ranges, etc. */
-static int
-delete_block (b)
+int
+flow_delete_block (b)
basic_block b;
{
int deleted_handler = 0;
- rtx insn, end;
+ rtx insn, end, tmp;
/* If the head of this block is a CODE_LABEL, then it might be the
label for an exception handler which can't be reached.
}
}
- /* Selectively unlink the insn chain. Include any BARRIER that may
- follow the basic block. */
- end = next_nonnote_insn (b->end);
- if (!end || GET_CODE (end) != BARRIER)
- end = b->end;
+ /* Include any jump table following the basic block. */
+ end = b->end;
+ if (GET_CODE (end) == JUMP_INSN
+ && (tmp = JUMP_LABEL (end)) != NULL_RTX
+ && (tmp = NEXT_INSN (tmp)) != NULL_RTX
+ && GET_CODE (tmp) == JUMP_INSN
+ && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
+ || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
+ end = tmp;
+
+ /* Include any barrier that may follow the basic block. */
+ tmp = next_nonnote_insn (end);
+ if (tmp && GET_CODE (tmp) == BARRIER)
+ end = tmp;
+
+ /* Selectively delete the entire chain. */
flow_delete_insn_chain (insn, end);
no_delete_insns:
/* Delete INSN by patching it out. Return the next insn. */
-static rtx
+rtx
flow_delete_insn (insn)
rtx insn;
{
rtx prev = PREV_INSN (insn);
rtx next = NEXT_INSN (insn);
+ rtx note;
PREV_INSN (insn) = NULL_RTX;
NEXT_INSN (insn) = NULL_RTX;
if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
LABEL_NUSES (JUMP_LABEL (insn))--;
+ /* Also if deleting an insn that references a label. */
+ else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX)
+ LABEL_NUSES (XEXP (note, 0))--;
+
return next;
}
return 1;
}
+/* Blocks A and B are to be merged into a single block A. The insns
+ are already contiguous, hence `nomove'. */
+
+void
+merge_blocks_nomove (a, b)
+ basic_block a, b;
+{
+ edge e;
+ rtx b_head, b_end, a_end;
+ rtx del_first = NULL_RTX, del_last = NULL_RTX;
+ int b_empty = 0;
+
+ /* If there was a CODE_LABEL beginning B, delete it. */
+ b_head = b->head;
+ b_end = b->end;
+ if (GET_CODE (b_head) == CODE_LABEL)
+ {
+ /* Detect basic blocks with nothing but a label. This can happen
+ in particular at the end of a function. */
+ if (b_head == b_end)
+ b_empty = 1;
+ del_first = del_last = b_head;
+ b_head = NEXT_INSN (b_head);
+ }
+
+ /* Delete the basic block note. */
+ if (GET_CODE (b_head) == NOTE
+ && NOTE_LINE_NUMBER (b_head) == NOTE_INSN_BASIC_BLOCK)
+ {
+ if (b_head == b_end)
+ b_empty = 1;
+ if (! del_last)
+ del_first = b_head;
+ del_last = b_head;
+ b_head = NEXT_INSN (b_head);
+ }
+
+ /* If there was a jump out of A, delete it. */
+ a_end = a->end;
+ if (GET_CODE (a_end) == JUMP_INSN)
+ {
+ rtx prev;
+
+ prev = prev_nonnote_insn (a_end);
+ if (!prev)
+ prev = a->head;
+
+ del_first = a_end;
+
+#ifdef HAVE_cc0
+ /* If this was a conditional jump, we need to also delete
+ the insn that set cc0. */
+ if (prev && sets_cc0_p (prev))
+ {
+ rtx tmp = prev;
+ prev = prev_nonnote_insn (prev);
+ if (!prev)
+ prev = a->head;
+ del_first = tmp;
+ }
+#endif
+
+ a_end = prev;
+ }
+
+ /* Delete everything marked above as well as crap that might be
+ hanging out between the two blocks. */
+ flow_delete_insn_chain (del_first, del_last);
+
+ /* Normally there should only be one successor of A and that is B, but
+ partway though the merge of blocks for conditional_execution we'll
+ be merging a TEST block with THEN and ELSE successors. Free the
+ whole lot of them and hope the caller knows what they're doing. */
+ while (a->succ)
+ remove_edge (a->succ);
+
+ /* Adjust the edges out of B for the new owner. */
+ for (e = b->succ; e ; e = e->succ_next)
+ e->src = a;
+ a->succ = b->succ;
+
+ /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
+ b->pred = b->succ = NULL;
+
+ /* Reassociate the insns of B with A. */
+ if (!b_empty)
+ {
+ if (basic_block_for_insn)
+ {
+ BLOCK_FOR_INSN (b_head) = a;
+ while (b_head != b_end)
+ {
+ b_head = NEXT_INSN (b_head);
+ BLOCK_FOR_INSN (b_head) = a;
+ }
+ }
+ a_end = b_end;
+ }
+ a->end = a_end;
+
+ expunge_block (b);
+}
+
/* Blocks A and B are to be merged into a single block. A has no incoming
fallthru edge, so it can be moved before B without adding or modifying
any jumps (aside from the jump from A to B). */
return 1;
}
-/* Blocks A and B are to be merged into a single block. The insns
- are already contiguous, hence `nomove'. */
+/* Attempt to merge basic blocks that are potentially non-adjacent.
+ Return true iff the attempt succeeded. */
-static void
-merge_blocks_nomove (a, b)
- basic_block a, b;
+static int
+merge_blocks (e, b, c)
+ edge e;
+ basic_block b, c;
{
- edge e;
- rtx b_head, b_end, a_end;
- int b_empty = 0;
-
- /* If there was a CODE_LABEL beginning B, delete it. */
- b_head = b->head;
- b_end = b->end;
- if (GET_CODE (b_head) == CODE_LABEL)
- {
- /* Detect basic blocks with nothing but a label. This can happen
- in particular at the end of a function. */
- if (b_head == b_end)
- b_empty = 1;
- b_head = flow_delete_insn (b_head);
- }
-
- /* Delete the basic block note. */
- if (GET_CODE (b_head) == NOTE
- && NOTE_LINE_NUMBER (b_head) == NOTE_INSN_BASIC_BLOCK)
- {
- if (b_head == b_end)
- b_empty = 1;
- b_head = flow_delete_insn (b_head);
- }
-
- /* If there was a jump out of A, delete it. */
- a_end = a->end;
- if (GET_CODE (a_end) == JUMP_INSN)
- {
- rtx prev;
-
- prev = prev_nonnote_insn (a_end);
- if (!prev)
- prev = a->head;
-
-#ifdef HAVE_cc0
- /* If this was a conditional jump, we need to also delete
- the insn that set cc0. */
-
- if (prev && sets_cc0_p (prev))
- {
- rtx tmp = prev;
- prev = prev_nonnote_insn (prev);
- if (!prev)
- prev = a->head;
- flow_delete_insn (tmp);
- }
-#endif
-
- /* Note that a->head != a->end, since we should have at least a
- bb note plus the jump, so prev != insn. */
- flow_delete_insn (a_end);
- a_end = prev;
- }
-
- /* By definition, there should only be one successor of A, and that is
- B. Free that edge struct. */
- n_edges--;
- free (a->succ);
-
- /* Adjust the edges out of B for the new owner. */
- for (e = b->succ; e ; e = e->succ_next)
- e->src = a;
- a->succ = b->succ;
-
- /* Reassociate the insns of B with A. */
- if (!b_empty)
- {
- BLOCK_FOR_INSN (b_head) = a;
- while (b_head != b_end)
- {
- b_head = NEXT_INSN (b_head);
- BLOCK_FOR_INSN (b_head) = a;
- }
- a_end = b_head;
- }
- a->end = a_end;
-
- /* Compact the basic block array. */
- expunge_block (b);
-}
-
-/* Attempt to merge basic blocks that are potentially non-adjacent.
- Return true iff the attempt succeeded. */
-
-static int
-merge_blocks (e, b, c)
- edge e;
- basic_block b, c;
-{
- /* If B has a fallthru edge to C, no need to move anything. */
- if (e->flags & EDGE_FALLTHRU)
- {
- /* If a label still appears somewhere and we cannot delete the label,
- then we cannot merge the blocks. The edge was tidied already. */
+ /* If B has a fallthru edge to C, no need to move anything. */
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ /* If a label still appears somewhere and we cannot delete the label,
+ then we cannot merge the blocks. The edge was tidied already. */
rtx insn, stop = NEXT_INSN (c->head);
for (insn = NEXT_INSN (b->end); insn != stop; insn = NEXT_INSN (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
+void
tidy_fallthru_edge (e, b, c)
edge e;
basic_block b, c;
If block B consisted only of this single jump, turn it into a deleted
note. */
q = b->end;
- if (GET_CODE (q) == JUMP_INSN)
+ if (GET_CODE (q) == JUMP_INSN
+ && (simplejump_p (q)
+ || (b->succ == e && e->succ_next == NULL)))
{
#ifdef HAVE_cc0
/* If this was a conditional jump, we need to also delete
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);
}
}
\f
/* Perform data flow analysis.
- F is the first insn of the function and NREGS the number of register numbers
- in use. */
+ F is the first insn of the function; FLAGS is a set of PROP_* flags
+ to be used in accumulating flow info. */
void
-life_analysis (f, nregs, file, remove_dead_code)
+life_analysis (f, file, flags)
rtx f;
- int nregs;
FILE *file;
- int remove_dead_code;
+ int flags;
{
#ifdef ELIMINABLE_REGS
- register size_t i;
+ register int i;
static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
- int flags;
/* 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 ();
+ if (! optimize)
+ flags &= PROP_DEATH_NOTES | PROP_REG_INFO;
+
+ /* 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;
/* We want alias analysis information for local dead store elimination. */
- init_alias_analysis ();
+ if (flags & PROP_SCAN_DEAD_CODE)
+ 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);
+ /* 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 ();
- end_alias_analysis ();
+ /* 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 (NULL, UPDATE_LIFE_GLOBAL, flags);
+
+ /* Clean up. */
+ if (flags & PROP_SCAN_DEAD_CODE)
+ end_alias_analysis ();
if (file)
dump_flow_info (file);
- BITMAP_XFREE (uid_volatile);
free_basic_block_vars (1);
}
void *pregno;
{
rtx x = *px;
- int regno = *(int *) pregno;
+ unsigned int regno = *(int *) pregno;
if (GET_CODE (x) == REG && REGNO (x) == regno)
{
}
}
-/* Updates death notes starting with the basic blocks set in BLOCKS.
+/* Updates life information starting with the basic blocks set in BLOCKS.
+ If BLOCKS is null, consider it to be the universal set.
- If LOCAL_ONLY, such as after splitting or peepholeing, we are only
- expecting local modifications to basic blocks. If we find extra
- registers live at the beginning of a block, then we either killed
+ If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
+ we are only expecting local modifications to basic blocks. If we find
+ extra registers live at the beginning of a block, then we either killed
useful data, or we have a broken split that wants data not provided.
If we find registers removed from live_at_start, that means we have
a broken peephole that is killing a register it shouldn't.
generates subregs of a multi-word pseudo, current life analysis will
lose the kill. So we _can_ have a pseudo go live. How irritating.
- 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
- regs_ever_live unless the caller resets it to zero. */
+ Including PROP_REG_INFO does not properly refresh regs_ever_live
+ unless the caller resets it to zero. */
void
update_life_info (blocks, extent, prop_flags)
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)
count_or_remove_death_notes (blocks, 1);
}
- EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
+ if (blocks)
{
- basic_block bb = BASIC_BLOCK (i);
+ EXECUTE_IF_SET_IN_SBITMAP (blocks, 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,
- prop_flags);
+ COPY_REG_SET (tmp, bb->global_live_at_end);
+ propagate_block (bb, tmp, (regset) NULL, prop_flags);
- if (extent == UPDATE_LIFE_LOCAL)
- verify_local_live_at_start (tmp, bb);
- });
+ if (extent == UPDATE_LIFE_LOCAL)
+ verify_local_live_at_start (tmp, bb);
+ });
+ }
+ else
+ {
+ 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 (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. */
+/* Callback function for for_each_successor_phi. DATA is a regset.
+ Sets the SRC_REGNO, the regno of the phi alternative for phi node
+ INSN, in the regset. */
-static void
-life_analysis_1 (f, nregs, flags)
- rtx f;
- int nregs;
- int flags;
+static int
+set_phi_alternative_reg (insn, dest_regno, src_regno, data)
+ rtx insn ATTRIBUTE_UNUSED;
+ int dest_regno ATTRIBUTE_UNUSED;
+ int src_regno;
+ void *data;
{
- char save_regs_ever_live[FIRST_PSEUDO_REGISTER];
- register int i;
-
- max_regno = nregs;
-
- /* Allocate and zero out many 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));
-
- /* 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);
-
- /* 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);
- sbitmap_free (blocks);
- }
-
- /* 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;
+ regset live = (regset) data;
+ SET_REGNO_REG_SET (live, src_regno);
+ return 0;
}
/* Propagate global life info around the graph of basic blocks. Begin
considering blocks with their corresponding bit set in BLOCKS_IN.
+ If BLOCKS_IN is null, consider it the universal set.
+
BLOCKS_OUT is set for every block that was changed. */
static void
{
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;
- tmp = ALLOCA_REG_SET ();
- new_live_at_end = ALLOCA_REG_SET ();
+ tmp = INITIALIZE_REG_SET (tmp_head);
+ new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
/* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
because the `head == tail' style test for an empty queue doesn't
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
+ /* 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;
+
+ /* 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,
+ if (blocks_in)
{
- basic_block bb = BASIC_BLOCK (i);
- *--qhead = bb;
- bb->aux = bb;
- });
+ EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ *--qhead = bb;
+ bb->aux = bb;
+ });
+ }
+ else
+ {
+ for (i = 0; i < n_basic_blocks; ++i)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ *--qhead = bb;
+ bb->aux = bb;
+ }
+ }
- sbitmap_zero (blocks_out);
+ if (blocks_out)
+ sbitmap_zero (blocks_out);
while (qhead != qtail)
{
IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
}
+ /* Force the stack pointer to be live -- which might not already be
+ the case for blocks within infinite loops. */
+ SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
+
+ /* Regs used in phi nodes are not included in
+ global_live_at_start, since they are live only along a
+ particular edge. Set those regs that are live because of a
+ phi node alternative corresponding to this particular block. */
+ if (in_ssa_form)
+ for_each_successor_phi (bb, &set_phi_alternative_reg,
+ new_live_at_end);
+
if (bb == ENTRY_BLOCK_PTR)
{
COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
/* Let our caller know that BB changed enough to require its
death notes updated. */
- SET_BIT (blocks_out, bb->index);
+ if (blocks_out)
+ SET_BIT (blocks_out, bb->index);
if (! rescan)
{
/* 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))
FREE_REG_SET (tmp);
FREE_REG_SET (new_live_at_end);
- EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
+ if (blocks_out)
{
- basic_block bb = BASIC_BLOCK (i);
- FREE_REG_SET (bb->local_set);
- });
+ EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ FREE_REG_SET (bb->local_set);
+ });
+ }
+ else
+ {
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ FREE_REG_SET (bb->local_set);
+ }
+ }
free (queue);
}
{
int i;
+ max_regno = max_reg_num ();
+
/* Recalculate the register space, in case it has grown. Old style
vector oriented regsets would set regset_{size,bytes} here also. */
allocate_reg_info (max_regno, FALSE, FALSE);
}
}
-/* Compute the registers live at the beginning of a basic block
- from those live at the end.
+/* Delete dead instructions for propagate_block. */
- When called, OLD contains those live at the end.
- On return, it contains those live at the beginning.
- FIRST and LAST are the first and last insns of the basic block.
+static void
+propagate_block_delete_insn (bb, insn)
+ basic_block bb;
+ rtx insn;
+{
+ rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
- FINAL is nonzero if we are doing the final pass which is not
- for computing the life info (since that has already been done)
- but for acting on it. On this pass, we delete dead stores,
- set up the logical links and dead-variables lists of instructions,
- and merge instructions for autoincrement and autodecrement addresses.
+ /* If the insn referred to a label, and that 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 be
+ referencing labels that no longer exist. */
- SIGNIFICANT is nonzero only the first time for each basic block.
- If it is nonzero, it points to a regset in which we store
- a 1 for each register that is set within the block.
+ if (inote)
+ {
+ rtx label = XEXP (inote, 0);
+ rtx next;
+
+ if (LABEL_NUSES (label) == 1
+ && (next = next_nonnote_insn (label)) != NULL
+ && GET_CODE (next) == JUMP_INSN
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ {
+ rtx pat = PATTERN (next);
+ int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
+ int len = XVECLEN (pat, diff_vec_p);
+ int i;
- BNUM is the number of the basic block. */
+ for (i = 0; i < len; i++)
+ LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
-static void
-propagate_block (old, first, last, significant, bnum, flags)
- register regset old;
- rtx first;
- rtx last;
- regset significant;
- int bnum;
- int flags;
+ flow_delete_insn (next);
+ }
+ }
+
+ if (bb->end == insn)
+ bb->end = PREV_INSN (insn);
+ flow_delete_insn (insn);
+}
+
+/* Delete dead libcalls for propagate_block. Return the insn
+ before the libcall. */
+
+static rtx
+propagate_block_delete_libcall (bb, insn, note)
+ basic_block bb;
+ rtx insn, note;
{
- register rtx insn;
- rtx prev;
- regset live;
- regset dead;
+ rtx first = XEXP (note, 0);
+ rtx before = PREV_INSN (first);
- /* 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;
+ if (insn == bb->end)
+ bb->end = before;
+
+ flow_delete_insn_chain (first, insn);
+ return before;
+}
- dead = ALLOCA_REG_SET ();
- live = ALLOCA_REG_SET ();
+/* Update the life-status of regs for one insn. Return the previous insn. */
- cc0_live = 0;
+rtx
+propagate_one_insn (pbi, insn)
+ struct propagate_block_info *pbi;
+ rtx insn;
+{
+ rtx prev = PREV_INSN (insn);
+ int flags = pbi->flags;
+ int insn_is_dead = 0;
+ int libcall_is_dead = 0;
+ rtx note;
+ int i;
- if (flags & PROP_REG_INFO)
- {
- register int i;
+ if (! INSN_P (insn))
+ return prev;
- /* Process the regs live at the end of the block.
- Mark them as not local to any one basic block. */
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
- {
- REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
- });
+ note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
+ if (flags & PROP_SCAN_DEAD_CODE)
+ {
+ insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
+ REG_NOTES (insn));
+ libcall_is_dead = (insn_is_dead && note != 0
+ && libcall_dead_p (pbi, PATTERN (insn),
+ note, insn));
}
- /* Scan the block an insn at a time from end to beginning. */
+ /* We almost certainly don't want to delete prologue or epilogue
+ instructions. Warn about probable compiler losage. */
+ if (insn_is_dead
+ && reload_completed
+ && (((HAVE_epilogue || HAVE_prologue)
+ && prologue_epilogue_contains (insn))
+ || (HAVE_sibcall_epilogue
+ && sibcall_epilogue_contains (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;
+ }
- for (insn = last; ; insn = prev)
+ /* If an instruction consists of just dead store(s) on final pass,
+ delete it. */
+ if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
{
- prev = PREV_INSN (insn);
+ /* Record sets. Do this even for dead instructions, since they
+ would have killed the values if they hadn't been deleted. */
+ mark_set_regs (pbi, PATTERN (insn), insn);
- if (GET_CODE (insn) == NOTE)
+ /* CC0 is now known to be dead. Either this insn used it,
+ in which case it doesn't anymore, or clobbered it,
+ so the next insn can't use it. */
+ pbi->cc0_live = 0;
+
+ if (libcall_is_dead)
{
- /* If this is a call to `setjmp' et al,
- warn if any non-volatile datum is live. */
+ prev = propagate_block_delete_libcall (pbi->bb, insn, note);
+ insn = NEXT_INSN (prev);
+ }
+ else
+ propagate_block_delete_insn (pbi->bb, insn);
+
+ return prev;
+ }
+
+ /* See if this is an increment or decrement that can be merged into
+ a following memory address. */
+#ifdef AUTO_INC_DEC
+ {
+ register rtx x = single_set (insn);
+
+ /* Does this instruction increment or decrement a register? */
+ if (!reload_completed
+ && (flags & PROP_AUTOINC)
+ && x != 0
+ && GET_CODE (SET_DEST (x)) == REG
+ && (GET_CODE (SET_SRC (x)) == PLUS
+ || GET_CODE (SET_SRC (x)) == MINUS)
+ && XEXP (SET_SRC (x), 0) == SET_DEST (x)
+ && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
+ /* Ok, look for a following memory ref we can combine with.
+ If one is found, change the memory ref to a PRE_INC
+ or PRE_DEC, cancel this insn, and return 1.
+ Return 0 if nothing has been done. */
+ && try_pre_increment_1 (pbi, insn))
+ return prev;
+ }
+#endif /* AUTO_INC_DEC */
+
+ CLEAR_REG_SET (pbi->new_set);
+
+ /* If this is not the final pass, and this insn is copying the value of
+ a library call and it's dead, don't scan the insns that perform the
+ library call, so that the call's arguments are not marked live. */
+ if (libcall_is_dead)
+ {
+ /* Record the death of the dest reg. */
+ mark_set_regs (pbi, PATTERN (insn), insn);
+
+ insn = XEXP (note, 0);
+ return PREV_INSN (insn);
+ }
+ else if (GET_CODE (PATTERN (insn)) == SET
+ && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
+ && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
+ && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
+ && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
+ /* We have an insn to pop a constant amount off the stack.
+ (Such insns use PLUS regardless of the direction of the stack,
+ and any insn to adjust the stack by a constant is always a pop.)
+ These insns, if not dead stores, have no effect on life. */
+ ;
+ else
+ {
+ /* Any regs live at the time of a call instruction must not go
+ in a register clobbered by calls. Find all regs now live and
+ record this for them. */
+
+ if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
+ EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
+ { REG_N_CALLS_CROSSED (i)++; });
- if ((flags & PROP_REG_INFO)
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- IOR_REG_SET (regs_live_at_setjmp, old);
+ /* Record sets. Do this even for dead instructions, since they
+ would have killed the values if they hadn't been deleted. */
+ mark_set_regs (pbi, PATTERN (insn), insn);
+
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ register int i;
+ rtx note, cond;
+
+ cond = NULL_RTX;
+ if (GET_CODE (PATTERN (insn)) == COND_EXEC)
+ cond = COND_EXEC_TEST (PATTERN (insn));
+
+ /* Non-constant calls clobber memory. */
+ if (! CONST_CALL_P (insn))
+ free_EXPR_LIST_list (&pbi->mem_set_list);
+
+ /* There may be extra registers to be clobbered. */
+ for (note = CALL_INSN_FUNCTION_USAGE (insn);
+ note;
+ note = XEXP (note, 1))
+ if (GET_CODE (XEXP (note, 0)) == CLOBBER)
+ mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
+ cond, insn, pbi->flags);
+
+ /* Calls change all call-used and global registers. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (call_used_regs[i] && ! global_regs[i]
+ && ! fixed_regs[i])
+ {
+ /* We do not want REG_UNUSED notes for these registers. */
+ mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
+ cond, insn, pbi->flags & ~PROP_DEATH_NOTES);
+ }
}
- /* Update the life-status of regs for this insn.
- First DEAD gets which regs are set in this insn
- then LIVE gets which regs are used in this insn.
- Then the regs live before the insn
- are those live after, with DEAD regs turned off,
- and then LIVE regs turned on. */
+ /* If an insn doesn't use CC0, it becomes dead since we assume
+ that every insn clobbers it. So show it dead here;
+ mark_used_regs will set it live if it is referenced. */
+ pbi->cc0_live = 0;
+
+ /* Record uses. */
+ if (! insn_is_dead)
+ mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
- else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ /* Sometimes we may have inserted something before INSN (such as a move)
+ when we make an auto-inc. So ensure we will scan those insns. */
+#ifdef AUTO_INC_DEC
+ prev = PREV_INSN (insn);
+#endif
+
+ if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
{
register int i;
- rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
- int insn_is_dead = 0;
- int libcall_is_dead = 0;
+ rtx note, cond;
+
+ cond = NULL_RTX;
+ if (GET_CODE (PATTERN (insn)) == COND_EXEC)
+ cond = COND_EXEC_TEST (PATTERN (insn));
+
+ /* Calls use their arguments. */
+ for (note = CALL_INSN_FUNCTION_USAGE (insn);
+ note;
+ note = XEXP (note, 1))
+ if (GET_CODE (XEXP (note, 0)) == USE)
+ mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
+ cond, insn);
+
+ /* The stack ptr is used (honorarily) by a CALL insn. */
+ SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
+
+ /* Calls may also reference any of the global registers,
+ so they are made live. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (global_regs[i])
+ mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
+ cond, 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));
- libcall_is_dead = (insn_is_dead && note != 0
- && libcall_dead_p (PATTERN (insn), old, note, insn));
- }
+ /* 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 (pbi->reg_live, 0, i,
+ { REG_LIVE_LENGTH (i)++; });
- /* 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
- && reload_completed
- && (HAVE_epilogue || HAVE_prologue)
- && prologue_epilogue_contains (insn))
- {
- warning ("ICE: would have deleted prologue/epilogue insn");
- debug_rtx (insn);
- libcall_is_dead = insn_is_dead = 0;
- }
+ return prev;
+}
- /* If an instruction consists of just dead store(s) on final pass,
- "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
- We could really delete it with delete_insn, but that
- can cause trouble for first or last insn in a basic block. */
- if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
- {
- rtx inote;
- /* If the insn referred to a label, note that the label is
- now less used. */
- for (inote = REG_NOTES (insn); inote; inote = XEXP (inote, 1))
- {
- if (REG_NOTE_KIND (inote) == REG_LABEL)
- {
- rtx label = XEXP (inote, 0);
- rtx next;
- 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
- be referencing labels that no longer exist. */
- if (LABEL_NUSES (label) == 0
- && (next = next_nonnote_insn (label)) != NULL
- && GET_CODE (next) == JUMP_INSN
- && (GET_CODE (PATTERN (next)) == ADDR_VEC
- || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
- {
- rtx pat = PATTERN (next);
- int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
- int len = XVECLEN (pat, diff_vec_p);
- int i;
- for (i = 0; i < len; i++)
- LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
- PUT_CODE (next, NOTE);
- NOTE_LINE_NUMBER (next) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (next) = 0;
- }
- }
- }
+/* Initialize a propagate_block_info struct for public consumption.
+ Note that the structure itself is opaque to this file, but that
+ the user can use the regsets provided here. */
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
+struct propagate_block_info *
+init_propagate_block_info (bb, live, local_set, flags)
+ basic_block bb;
+ regset live;
+ regset local_set;
+ int flags;
+{
+ struct propagate_block_info *pbi = xmalloc (sizeof(*pbi));
- /* CC0 is now known to be dead. Either this insn used it,
- in which case it doesn't anymore, or clobbered it,
- so the next insn can't use it. */
- cc0_live = 0;
+ pbi->bb = bb;
+ pbi->reg_live = live;
+ pbi->mem_set_list = NULL_RTX;
+ pbi->local_set = local_set;
+ pbi->cc0_live = 0;
+ pbi->flags = flags;
- /* If this insn is copying the return value from a library call,
- delete the entire library call. */
- if (libcall_is_dead)
- {
- rtx first = XEXP (note, 0);
- rtx p = insn;
- while (INSN_DELETED_P (first))
- first = NEXT_INSN (first);
- while (p != first)
- {
- p = PREV_INSN (p);
- PUT_CODE (p, NOTE);
- NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (p) = 0;
- }
- }
- goto flushed;
- }
+ if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
+ pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
+ else
+ pbi->reg_next_use = NULL;
- CLEAR_REG_SET (dead);
- CLEAR_REG_SET (live);
+ pbi->new_set = BITMAP_XMALLOC ();
- /* See if this is an increment or decrement that can be
- merged into a following memory address. */
-#ifdef AUTO_INC_DEC
- {
- register rtx x = single_set (insn);
-
- /* Does this instruction increment or decrement a register? */
- if (!reload_completed
- && (flags & PROP_AUTOINC)
- && x != 0
- && GET_CODE (SET_DEST (x)) == REG
- && (GET_CODE (SET_SRC (x)) == PLUS
- || GET_CODE (SET_SRC (x)) == MINUS)
- && XEXP (SET_SRC (x), 0) == SET_DEST (x)
- && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
- /* Ok, look for a following memory ref we can combine with.
- If one is found, change the memory ref to a PRE_INC
- or PRE_DEC, cancel this insn, and return 1.
- Return 0 if nothing has been done. */
- && try_pre_increment_1 (insn))
- goto flushed;
- }
-#endif /* AUTO_INC_DEC */
+#ifdef HAVE_conditional_execution
+ pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
+ free_reg_cond_life_info);
+ pbi->reg_cond_reg = BITMAP_XMALLOC ();
- /* If this is not the final pass, and this insn is copying the
- value of a library call and it's dead, don't scan the
- insns that perform the library call, so that the call's
- arguments are not marked live. */
- if (libcall_is_dead)
- {
- /* Mark the dest reg as `significant'. */
- mark_set_regs (old, dead, PATTERN (insn), NULL_RTX,
- significant, flags);
+ /* If this block ends in a conditional branch, for each register live
+ from one side of the branch and not the other, record the register
+ as conditionally dead. */
+ if (GET_CODE (bb->end) == JUMP_INSN
+ && condjump_p (bb->end)
+ && ! simplejump_p (bb->end))
+ {
+ regset_head diff_head;
+ regset diff = INITIALIZE_REG_SET (diff_head);
+ basic_block bb_true, bb_false;
+ rtx cond_true, cond_false;
+ int i;
- insn = XEXP (note, 0);
- prev = PREV_INSN (insn);
- }
- else if (GET_CODE (PATTERN (insn)) == SET
- && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
- && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
- && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
- && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
- /* We have an insn to pop a constant amount off the stack.
- (Such insns use PLUS regardless of the direction of the stack,
- and any insn to adjust the stack by a constant is always a pop.)
- These insns, if not dead stores, have no effect on life. */
- ;
- else
- {
- /* Any regs live at the time of a call instruction
- must not go in a register clobbered by calls.
- Find all regs now live and record this for them. */
-
- if (GET_CODE (insn) == CALL_INSN
- && (flags & PROP_REG_INFO))
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
- {
- REG_N_CALLS_CROSSED (i)++;
- });
-
- /* LIVE gets the regs used in INSN;
- DEAD gets those set by it. Dead insns don't make anything
- live. */
-
- mark_set_regs (old, dead, PATTERN (insn),
- insn, significant, flags);
-
- /* If an insn doesn't use CC0, it becomes dead since we
- assume that every insn clobbers it. So show it dead here;
- mark_used_regs will set it live if it is referenced. */
- cc0_live = 0;
-
- if (! insn_is_dead)
- mark_used_regs (old, live, PATTERN (insn), flags, insn);
-
- /* Sometimes we may have inserted something before INSN (such as
- a move) when we make an auto-inc. So ensure we will scan
- those insns. */
-#ifdef AUTO_INC_DEC
- prev = PREV_INSN (insn);
+ /* Identify the successor blocks. */
+ bb_false = bb->succ->succ_next->dest;
+ bb_true = bb->succ->dest;
+ if (bb->succ->flags & EDGE_FALLTHRU)
+ {
+ basic_block t = bb_false;
+ bb_false = bb_true;
+ bb_true = t;
+ }
+ else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
+ abort ();
+
+ /* Extract the condition from the branch. */
+ cond_true = XEXP (SET_SRC (PATTERN (bb->end)), 0);
+ cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
+ GET_MODE (cond_true), XEXP (cond_true, 0),
+ XEXP (cond_true, 1));
+ if (GET_CODE (XEXP (SET_SRC (PATTERN (bb->end)), 1)) == PC)
+ {
+ rtx t = cond_false;
+ cond_false = cond_true;
+ cond_true = t;
+ }
+
+ /* Compute which register lead different lives in the successors. */
+ if (bitmap_operation (diff, bb_true->global_live_at_start,
+ bb_false->global_live_at_start, BITMAP_XOR))
+ {
+ if (GET_CODE (XEXP (cond_true, 0)) != REG)
+ abort ();
+ SET_REGNO_REG_SET (pbi.reg_cond_reg, REGNO (XEXP (cond_true, 0)));
+
+ /* For each such register, mark it conditionally dead. */
+ EXECUTE_IF_SET_IN_REG_SET
+ (diff, 0, i,
+ {
+ struct reg_cond_life_info *rcli;
+ rtx cond;
+
+ rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
+
+ if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
+ cond = cond_false;
+ else
+ cond = cond_true;
+ rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
+
+ splay_tree_insert (pbi.reg_cond_dead, i,
+ (splay_tree_value) rcli);
+ });
+ }
+
+ FREE_REG_SET (diff);
+ }
#endif
- if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
- {
- register int i;
-
- rtx note;
-
- for (note = CALL_INSN_FUNCTION_USAGE (insn);
- note;
- note = XEXP (note, 1))
- if (GET_CODE (XEXP (note, 0)) == USE)
- mark_used_regs (old, live, XEXP (XEXP (note, 0), 0),
- flags, insn);
-
- /* Each call clobbers all call-clobbered regs that are not
- global or fixed. Note that the function-value reg is a
- call-clobbered reg, and mark_set_regs has already had
- a chance to handle it. */
-
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (call_used_regs[i] && ! global_regs[i]
- && ! fixed_regs[i])
- {
- SET_REGNO_REG_SET (dead, i);
- if (significant)
- SET_REGNO_REG_SET (significant, i);
- }
-
- /* The stack ptr is used (honorarily) by a CALL insn. */
- SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
-
- /* Calls may also reference any of the global registers,
- so they are made live. */
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (global_regs[i])
- mark_used_regs (old, live,
- gen_rtx_REG (reg_raw_mode[i], i),
- flags, insn);
-
- /* Calls also clobber memory. */
- free_EXPR_LIST_list (&mem_set_list);
- }
+ return pbi;
+}
- /* Update OLD for the registers used or set. */
- AND_COMPL_REG_SET (old, dead);
- IOR_REG_SET (old, live);
+/* Release a propagate_block_info struct. */
- }
+void
+free_propagate_block_info (pbi)
+ struct propagate_block_info *pbi;
+{
+ free_EXPR_LIST_list (&pbi->mem_set_list);
- /* On final pass, update counts of how many insns each reg is live
- at. */
- if (flags & PROP_REG_INFO)
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
- { REG_LIVE_LENGTH (i)++; });
- }
- flushed: ;
- if (insn == first)
+ BITMAP_XFREE (pbi->new_set);
+
+#ifdef HAVE_conditional_execution
+ splay_tree_delete (pbi->reg_cond_dead);
+ BITMAP_XFREE (pbi->reg_cond_reg);
+#endif
+
+ if (pbi->reg_next_use)
+ free (pbi->reg_next_use);
+
+ free (pbi);
+}
+
+/* Compute the registers live at the beginning of a basic block BB from
+ those live at the end.
+
+ When called, REG_LIVE contains those live at the end. On return, it
+ contains those live at the beginning.
+
+ LOCAL_SET, if non-null, will be set with all registers killed by
+ this basic block. */
+
+void
+propagate_block (bb, live, local_set, flags)
+ basic_block bb;
+ regset live;
+ regset local_set;
+ int flags;
+{
+ struct propagate_block_info *pbi;
+ rtx insn, prev;
+
+ pbi = init_propagate_block_info (bb, live, local_set, flags);
+
+ if (flags & PROP_REG_INFO)
+ {
+ register int i;
+
+ /* Process the regs live at the end of the block.
+ Mark them as not local to any one basic block. */
+ EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
+ { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
+ }
+
+ /* Scan the block an insn at a time from end to beginning. */
+
+ for (insn = bb->end; ; insn = prev)
+ {
+ /* If this is a call to `setjmp' et al, warn if any
+ non-volatile datum is live. */
+ if ((flags & PROP_REG_INFO)
+ && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
+ IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
+
+ prev = propagate_one_insn (pbi, insn);
+
+ if (insn == bb->head)
break;
}
- FREE_REG_SET (dead);
- FREE_REG_SET (live);
- free_EXPR_LIST_list (&mem_set_list);
+ free_propagate_block_info (pbi);
}
\f
/* Return 1 if X (the body of an insn, or part of it) is just dead stores
pertaining to the insn. */
static int
-insn_dead_p (x, needed, call_ok, notes)
+insn_dead_p (pbi, x, call_ok, notes)
+ struct propagate_block_info *pbi;
rtx x;
- regset needed;
int call_ok;
rtx notes ATTRIBUTE_UNUSED;
{
/* Don't delete insns to set global regs. */
if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
- || REGNO_REG_SET_P (needed, regno))
+ || REGNO_REG_SET_P (pbi->reg_live, regno))
return 0;
}
}
{
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;
+ return ! pbi->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
backwards from the end of the block to the start. */
- temp = mem_set_list;
+ temp = pbi->mem_set_list;
while (temp)
{
if (rtx_equal_p (XEXP (temp, 0), r))
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);
- 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);
- if (GET_CODE (r) == REG)
- {
- int regno = REGNO (r);
+ /* Obvious. */
+ if (REGNO_REG_SET_P (pbi->reg_live, 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 (pbi->reg_live, regno+n))
+ return 0;
+ }
+
+ /* Don't delete insns to set global regs. */
+ if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
+ 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 stack pointer aren't deleted. */
+ if (regno == STACK_POINTER_REGNUM)
+ return 0;
+
+ /* 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);
for (i--; i >= 0; i--)
if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
&& GET_CODE (XVECEXP (x, 0, i)) != USE
- && ! insn_dead_p (XVECEXP (x, 0, i), needed, call_ok, NULL_RTX))
+ && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
return 0;
return 1;
is not necessarily true for hard registers. */
else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
&& REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
- && ! REGNO_REG_SET_P (needed, REGNO (XEXP (x, 0))))
+ && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
return 1;
/* We do not check other CLOBBER or USE here. An insn consisting of just
NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
static int
-libcall_dead_p (x, needed, note, insn)
+libcall_dead_p (pbi, x, note, insn)
+ struct propagate_block_info *pbi;
rtx x;
- regset needed;
rtx note;
rtx insn;
{
call_pat = XVECEXP (call_pat, 0, i);
}
- return insn_dead_p (call_pat, needed, 1, REG_NOTES (call));
+ return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
}
}
return 1;
Find any entries on the mem_set_list that need to be invalidated due
to an address change. */
static void
-invalidate_mems_from_autoinc (insn)
+invalidate_mems_from_autoinc (pbi, insn)
+ struct propagate_block_info *pbi;
rtx insn;
{
rtx note = REG_NOTES (insn);
{
if (REG_NOTE_KIND (note) == REG_INC)
{
- rtx temp = mem_set_list;
+ rtx temp = pbi->mem_set_list;
rtx prev = NULL_RTX;
rtx next;
if (prev)
XEXP (prev, 1) = next;
else
- mem_set_list = next;
+ pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
}
else
FLAGS is the set of operations to perform. */
static void
-mark_set_regs (needed, dead, x, insn, significant, flags)
- regset needed;
- regset dead;
- rtx x;
- rtx insn;
- regset significant;
- int flags;
+mark_set_regs (pbi, x, insn)
+ struct propagate_block_info *pbi;
+ rtx x, insn;
{
- register RTX_CODE code = GET_CODE (x);
+ rtx cond = NULL_RTX;
+ enum rtx_code code;
- if (code == SET || code == CLOBBER)
- mark_set_1 (needed, dead, x, insn, significant, flags);
- else if (code == PARALLEL)
+ retry:
+ switch (code = GET_CODE (x))
{
- register int i;
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
- {
- code = GET_CODE (XVECEXP (x, 0, i));
- if (code == SET || code == CLOBBER)
- mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn,
- significant, flags);
- }
+ case SET:
+ case CLOBBER:
+ mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
+ return;
+
+ case COND_EXEC:
+ cond = COND_EXEC_TEST (x);
+ x = COND_EXEC_CODE (x);
+ goto retry;
+
+ case PARALLEL:
+ {
+ register int i;
+ for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+ {
+ rtx sub = XVECEXP (x, 0, i);
+ switch (code = GET_CODE (sub))
+ {
+ case COND_EXEC:
+ if (cond != NULL_RTX)
+ abort ();
+
+ cond = COND_EXEC_TEST (sub);
+ sub = COND_EXEC_CODE (sub);
+ if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
+ break;
+ /* FALLTHRU */
+
+ case SET:
+ case CLOBBER:
+ mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
+ break;
+
+ default:
+ break;
+ }
+ }
+ break;
+ }
+
+ default:
+ break;
}
}
/* Process a single SET rtx, X. */
static void
-mark_set_1 (needed, dead, x, insn, significant, flags)
- regset needed;
- regset dead;
- rtx x;
- rtx insn;
- regset significant;
+mark_set_1 (pbi, code, reg, cond, insn, flags)
+ struct propagate_block_info *pbi;
+ enum rtx_code code;
+ rtx reg, cond, insn;
int flags;
{
- register int regno = -1;
- register rtx reg = SET_DEST (x);
+ int regno_first = -1, regno_last = -1;
+ int not_dead = 0;
+ int i;
/* Some targets place small structures in registers for
return values of functions. We have to detect this
if (GET_CODE (reg) == PARALLEL
&& GET_MODE (reg) == BLKmode)
{
- register int i;
-
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- mark_set_1 (needed, dead, XVECEXP (reg, 0, i), insn,
- significant, flags);
+ mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
return;
}
- /* Modifying just one hardware register of a multi-reg value
- or just a byte field of a register
- does not mean the value from before this insn is now dead.
- But it does mean liveness of that register at the end of the block
- is significant.
+ /* Modifying just one hardware register of a multi-reg value or just a
+ byte field of a register does not mean the value from before this insn
+ is now dead. Of course, if it was dead after it's unused now. */
+
+ switch (GET_CODE (reg))
+ {
+ case ZERO_EXTRACT:
+ case SIGN_EXTRACT:
+ case STRICT_LOW_PART:
+ /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */
+ do
+ reg = XEXP (reg, 0);
+ while (GET_CODE (reg) == SUBREG
+ || GET_CODE (reg) == ZERO_EXTRACT
+ || GET_CODE (reg) == SIGN_EXTRACT
+ || GET_CODE (reg) == STRICT_LOW_PART);
+ if (GET_CODE (reg) == MEM)
+ break;
+ not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
+ /* FALLTHRU */
+
+ case REG:
+ regno_last = regno_first = REGNO (reg);
+ if (regno_first < FIRST_PSEUDO_REGISTER)
+ regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
+ break;
+
+ case SUBREG:
+ if (GET_CODE (SUBREG_REG (reg)) == REG)
+ {
+ enum machine_mode outer_mode = GET_MODE (reg);
+ enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
- Within mark_set_1, however, we treat it as if the register is
- indeed modified. mark_used_regs will, however, also treat this
- register as being used. Thus, we treat these insns as setting a
- new value for the register as a function of its old value. This
- cases LOG_LINKS to be made appropriately and this will help combine. */
+ /* Identify the range of registers affected. This is moderately
+ tricky for hard registers. See alter_subreg. */
+
+ regno_last = regno_first = REGNO (SUBREG_REG (reg));
+ if (regno_first < FIRST_PSEUDO_REGISTER)
+ {
+#ifdef ALTER_HARD_SUBREG
+ regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
+ inner_mode, regno_first);
+#else
+ regno_first += SUBREG_WORD (reg);
+#endif
+ regno_last = (regno_first
+ + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
+
+ /* Since we've just adjusted the register number ranges, make
+ sure REG matches. Otherwise some_was_live will be clear
+ when it shouldn't have been, and we'll create incorrect
+ REG_UNUSED notes. */
+ reg = gen_rtx_REG (outer_mode, regno_first);
+ }
+ else
+ {
+ /* If the number of words in the subreg is less than the number
+ of words in the full register, we have a well-defined partial
+ set. Otherwise the high bits are undefined.
+
+ This is only really applicable to pseudos, since we just took
+ care of multi-word hard registers. */
+ if (((GET_MODE_SIZE (outer_mode)
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
+ < ((GET_MODE_SIZE (inner_mode)
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
+ not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
+
+ reg = SUBREG_REG (reg);
+ }
+ }
+ else
+ reg = SUBREG_REG (reg);
+ break;
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || GET_CODE (reg) == STRICT_LOW_PART)
- reg = XEXP (reg, 0);
+ default:
+ break;
+ }
/* If this set is a MEM, then it kills any aliased writes.
If this set is a REG, then it kills any MEMs which use the reg. */
if (flags & PROP_SCAN_DEAD_CODE)
{
- if (GET_CODE (reg) == MEM
- || GET_CODE (reg) == REG)
+ if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
{
- rtx temp = mem_set_list;
+ rtx temp = pbi->mem_set_list;
rtx prev = NULL_RTX;
rtx next;
if (prev)
XEXP (prev, 1) = next;
else
- mem_set_list = next;
+ pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
}
else
address modes. Then we may need to kill some entries on the
memory set list. */
if (insn && GET_CODE (reg) == MEM)
- invalidate_mems_from_autoinc (insn);
+ invalidate_mems_from_autoinc (pbi, insn);
if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
/* We do not know the size of a BLKmode store, so we do not track
everything that invalidates it. To be safe, don't eliminate any
stores though SP; none of them should be redundant anyway. */
&& ! reg_mentioned_p (stack_pointer_rtx, reg))
- mem_set_list = alloc_EXPR_LIST (0, reg, mem_set_list);
+ pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
}
if (GET_CODE (reg) == REG
- && (regno = REGNO (reg),
- ! (regno == FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
+ && ! (regno_first == FRAME_POINTER_REGNUM
+ && (! reload_completed || frame_pointer_needed))
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- && ! (regno == HARD_FRAME_POINTER_REGNUM
+ && ! (regno_first == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
#endif
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
- && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
+ && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
#endif
- && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
- /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
+ )
{
- int some_needed = REGNO_REG_SET_P (needed, regno);
- int some_not_needed = ! some_needed;
-
- /* Mark it as a significant register for this basic block. */
- if (significant)
- SET_REGNO_REG_SET (significant, regno);
+ int some_was_live = 0, some_was_dead = 0;
- /* Mark it as dead before this insn. */
- SET_REGNO_REG_SET (dead, regno);
-
- /* A hard reg in a wide mode may really be multiple registers.
- If so, mark all of them just like the first. */
- if (regno < FIRST_PSEUDO_REGISTER)
+ for (i = regno_first; i <= regno_last; ++i)
{
- int n;
-
- /* Nothing below is needed for the stack pointer; get out asap.
- Eg, log links aren't needed, since combine won't use them. */
- if (regno == STACK_POINTER_REGNUM)
- return;
+ int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
+ if (pbi->local_set)
+ SET_REGNO_REG_SET (pbi->local_set, i);
+ if (code != CLOBBER)
+ SET_REGNO_REG_SET (pbi->new_set, i);
+
+ some_was_live |= needed_regno;
+ some_was_dead |= ! needed_regno;
+ }
- n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
- while (--n > 0)
- {
- int regno_n = regno + n;
- int needed_regno = REGNO_REG_SET_P (needed, regno_n);
- if (significant)
- SET_REGNO_REG_SET (significant, regno_n);
-
- SET_REGNO_REG_SET (dead, regno_n);
- some_needed |= needed_regno;
- some_not_needed |= ! needed_regno;
- }
+#ifdef HAVE_conditional_execution
+ /* Consider conditional death in deciding that the register needs
+ a death note. */
+ if (some_was_live
+ /* The stack pointer is never dead. Well, not strictly true,
+ but it's very difficult to tell from here. Hopefully
+ combine_stack_adjustments will fix up the most egregious
+ errors. */
+ && regno_first != STACK_POINTER_REGNUM)
+ {
+ for (i = regno_first; i <= regno_last; ++i)
+ if (! mark_regno_cond_dead (pbi, i, cond))
+ not_dead = 1;
}
+#endif
/* Additional data to record if this is the final pass. */
if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
| PROP_DEATH_NOTES | PROP_AUTOINC))
{
register rtx y;
- register int blocknum = BLOCK_NUM (insn);
+ register int blocknum = pbi->bb->index;
y = NULL_RTX;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- y = reg_next_use[regno];
-
- /* If this is a hard reg, record this function uses the reg. */
-
- if (regno < FIRST_PSEUDO_REGISTER)
{
- register int i;
- int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
-
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- for (i = regno; i < endregno; i++)
- {
- /* The next use is no longer "next", since a store
- intervenes. */
- reg_next_use[i] = 0;
- }
+ y = pbi->reg_next_use[regno_first];
- if (flags & PROP_REG_INFO)
- for (i = regno; i < endregno; i++)
- {
- regs_ever_live[i] = 1;
- REG_N_SETS (i)++;
- }
+ /* The next use is no longer next, since a store intervenes. */
+ for (i = regno_first; i <= regno_last; ++i)
+ pbi->reg_next_use[i] = 0;
}
- else
- {
- /* The next use is no longer "next", since a store
- intervenes. */
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- reg_next_use[regno] = 0;
-
- /* Keep track of which basic blocks each reg appears in. */
- if (flags & PROP_REG_INFO)
+ if (flags & PROP_REG_INFO)
+ {
+ for (i = regno_first; i <= regno_last; ++i)
{
- if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
- REG_BASIC_BLOCK (regno) = blocknum;
- else if (REG_BASIC_BLOCK (regno) != blocknum)
- REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
-
- /* Count (weighted) references, stores, etc. This counts a
+ /* 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_SETS (i) += 1;
+ REG_N_REFS (i) += (optimize_size ? 1
+ : pbi->bb->loop_depth + 1);
+
/* The insns where a reg is live are normally counted
elsewhere, but we want the count to include the insn
where the reg is set, and the normal counting mechanism
would not count it. */
- REG_LIVE_LENGTH (regno)++;
+ REG_LIVE_LENGTH (i) += 1;
+ }
+
+ /* If this is a hard reg, record this function uses the reg. */
+ if (regno_first < FIRST_PSEUDO_REGISTER)
+ {
+ for (i = regno_first; i <= regno_last; i++)
+ regs_ever_live[i] = 1;
+ }
+ else
+ {
+ /* Keep track of which basic blocks each reg appears in. */
+ if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
+ REG_BASIC_BLOCK (regno_first) = blocknum;
+ else if (REG_BASIC_BLOCK (regno_first) != blocknum)
+ REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
}
}
- if (! some_not_needed)
+ if (! some_was_dead)
{
if (flags & PROP_LOG_LINKS)
{
even if reload can make what appear to be valid
assignments later. */
if (y && (BLOCK_NUM (y) == blocknum)
- && (regno >= FIRST_PSEUDO_REGISTER
+ && (regno_first >= FIRST_PSEUDO_REGISTER
|| asm_noperands (PATTERN (y)) < 0))
LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
}
}
- else if (! some_needed)
+ else if (not_dead)
+ ;
+ else if (! some_was_live)
{
if (flags & PROP_REG_INFO)
- REG_N_DEATHS (REGNO (reg))++;
+ REG_N_DEATHS (regno_first) += 1;
if (flags & PROP_DEATH_NOTES)
{
for those parts that were not needed. This case should
be rare. */
- int i;
-
- for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
- i >= 0; i--)
- if (!REGNO_REG_SET_P (needed, regno + i))
+ for (i = regno_first; i <= regno_last; ++i)
+ if (! REGNO_REG_SET_P (pbi->reg_live, i))
REG_NOTES (insn)
- = (alloc_EXPR_LIST
- (REG_UNUSED,
- gen_rtx_REG (reg_raw_mode[regno + i], regno + i),
- REG_NOTES (insn)));
+ = alloc_EXPR_LIST (REG_UNUSED,
+ gen_rtx_REG (reg_raw_mode[i], i),
+ REG_NOTES (insn));
}
}
}
+
+ /* Mark the register as being dead. */
+ if (some_was_live
+ /* The stack pointer is never dead. Well, not strictly true,
+ but it's very difficult to tell from here. Hopefully
+ combine_stack_adjustments will fix up the most egregious
+ errors. */
+ && regno_first != STACK_POINTER_REGNUM)
+ {
+ for (i = regno_first; i <= regno_last; ++i)
+ CLEAR_REGNO_REG_SET (pbi->reg_live, i);
+ }
}
else if (GET_CODE (reg) == REG)
{
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- reg_next_use[regno] = 0;
+ pbi->reg_next_use[regno_first] = 0;
}
/* If this is the last pass and this is a SCRATCH, show it will be dying
}
}
\f
+#ifdef HAVE_conditional_execution
+/* Mark REGNO conditionally dead. Return true if the register is
+ now unconditionally dead. */
+
+static int
+mark_regno_cond_dead (pbi, regno, cond)
+ struct propagate_block_info *pbi;
+ int regno;
+ rtx cond;
+{
+ /* If this is a store to a predicate register, the value of the
+ predicate is changing, we don't know that the predicate as seen
+ before is the same as that seen after. Flush all dependant
+ conditions from reg_cond_dead. This will make all such
+ conditionally live registers unconditionally live. */
+ if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
+ flush_reg_cond_reg (pbi, regno);
+
+ /* If this is an unconditional store, remove any conditional
+ life that may have existed. */
+ if (cond == NULL_RTX)
+ splay_tree_remove (pbi->reg_cond_dead, regno);
+ else
+ {
+ splay_tree_node node;
+ struct reg_cond_life_info *rcli;
+ rtx ncond;
+
+ /* Otherwise this is a conditional set. Record that fact.
+ It may have been conditionally used, or there may be a
+ subsequent set with a complimentary condition. */
+
+ node = splay_tree_lookup (pbi->reg_cond_dead, regno);
+ if (node == NULL)
+ {
+ /* The register was unconditionally live previously.
+ Record the current condition as the condition under
+ which it is dead. */
+ rcli = (struct reg_cond_life_info *)
+ xmalloc (sizeof (*rcli));
+ rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
+ splay_tree_insert (pbi->reg_cond_dead, regno,
+ (splay_tree_value) rcli);
+
+ SET_REGNO_REG_SET (pbi->reg_cond_reg,
+ REGNO (XEXP (cond, 0)));
+
+ /* Not unconditionaly dead. */
+ return 0;
+ }
+ else
+ {
+ /* The register was conditionally live previously.
+ Add the new condition to the old. */
+ rcli = (struct reg_cond_life_info *) node->value;
+ ncond = rcli->condition;
+ ncond = ior_reg_cond (ncond, cond);
+
+ /* If the register is now unconditionally dead,
+ remove the entry in the splay_tree. */
+ if (ncond == const1_rtx)
+ splay_tree_remove (pbi->reg_cond_dead, regno);
+ else
+ {
+ rcli->condition = ncond;
+
+ SET_REGNO_REG_SET (pbi->reg_cond_reg,
+ REGNO (XEXP (cond, 0)));
+
+ /* Not unconditionaly dead. */
+ return 0;
+ }
+ }
+ }
+
+ return 1;
+}
+
+/* Called from splay_tree_delete for pbi->reg_cond_life. */
+
+static void
+free_reg_cond_life_info (value)
+ splay_tree_value value;
+{
+ struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
+ free_EXPR_LIST_list (&rcli->condition);
+ free (rcli);
+}
+
+/* Helper function for flush_reg_cond_reg. */
+
+static int
+flush_reg_cond_reg_1 (node, data)
+ splay_tree_node node;
+ void *data;
+{
+ struct reg_cond_life_info *rcli;
+ int *xdata = (int *) data;
+ unsigned int regno = xdata[0];
+ rtx c, *prev;
+
+ /* Don't need to search if last flushed value was farther on in
+ the in-order traversal. */
+ if (xdata[1] >= (int) node->key)
+ return 0;
+
+ /* Splice out portions of the expression that refer to regno. */
+ rcli = (struct reg_cond_life_info *) node->value;
+ c = *(prev = &rcli->condition);
+ while (c)
+ {
+ if (regno == REGNO (XEXP (XEXP (c, 0), 0)))
+ {
+ rtx next = XEXP (c, 1);
+ free_EXPR_LIST_node (c);
+ c = *prev = next;
+ }
+ else
+ c = *(prev = &XEXP (c, 1));
+ }
+
+ /* If the entire condition is now NULL, signal the node to be removed. */
+ if (! rcli->condition)
+ {
+ xdata[1] = node->key;
+ return -1;
+ }
+ else
+ return 0;
+}
+
+/* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
+
+static void
+flush_reg_cond_reg (pbi, regno)
+ struct propagate_block_info *pbi;
+ int regno;
+{
+ int pair[2];
+
+ pair[0] = regno;
+ pair[1] = -1;
+ while (splay_tree_foreach (pbi->reg_cond_dead,
+ flush_reg_cond_reg_1, pair) == -1)
+ splay_tree_remove (pbi->reg_cond_dead, pair[1]);
+
+ CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
+}
+
+/* Logical arithmetic on predicate conditions. IOR, NOT and NAND.
+ We actually use EXPR_LIST to chain the sub-expressions together
+ instead of IOR because it's easier to manipulate and we have
+ the lists.c functions to reuse nodes.
+
+ Return a new rtl expression as appropriate. */
+
+static rtx
+ior_reg_cond (old, x)
+ rtx old, x;
+{
+ enum rtx_code x_code;
+ rtx x_reg;
+ rtx c;
+
+ /* We expect these conditions to be of the form (eq reg 0). */
+ x_code = GET_CODE (x);
+ if (GET_RTX_CLASS (x_code) != '<'
+ || GET_CODE (x_reg = XEXP (x, 0)) != REG
+ || XEXP (x, 1) != const0_rtx)
+ abort ();
+
+ /* Search the expression for an existing sub-expression of X_REG. */
+ for (c = old; c ; c = XEXP (c, 1))
+ {
+ rtx y = XEXP (c, 0);
+ if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
+ {
+ /* If we find X already present in OLD, we need do nothing. */
+ if (GET_CODE (y) == x_code)
+ return old;
+
+ /* If we find X being a compliment of a condition in OLD,
+ then the entire condition is true. */
+ if (GET_CODE (y) == reverse_condition (x_code))
+ return const1_rtx;
+ }
+ }
+
+ /* Otherwise just add to the chain. */
+ return alloc_EXPR_LIST (0, x, old);
+}
+
+static rtx
+not_reg_cond (x)
+ rtx x;
+{
+ enum rtx_code x_code;
+ rtx x_reg;
+
+ /* We expect these conditions to be of the form (eq reg 0). */
+ x_code = GET_CODE (x);
+ if (GET_RTX_CLASS (x_code) != '<'
+ || GET_CODE (x_reg = XEXP (x, 0)) != REG
+ || XEXP (x, 1) != const0_rtx)
+ abort ();
+
+ return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
+ VOIDmode, x_reg, const0_rtx),
+ NULL_RTX);
+}
+
+static rtx
+nand_reg_cond (old, x)
+ rtx old, x;
+{
+ enum rtx_code x_code;
+ rtx x_reg;
+ rtx c, *prev;
+
+ /* We expect these conditions to be of the form (eq reg 0). */
+ x_code = GET_CODE (x);
+ if (GET_RTX_CLASS (x_code) != '<'
+ || GET_CODE (x_reg = XEXP (x, 0)) != REG
+ || XEXP (x, 1) != const0_rtx)
+ abort ();
+
+ /* Search the expression for an existing sub-expression of X_REG. */
+
+ for (c = *(prev = &old); c ; c = *(prev = &XEXP (c, 1)))
+ {
+ rtx y = XEXP (c, 0);
+ if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
+ {
+ /* If we find X already present in OLD, then we need to
+ splice it out. */
+ if (GET_CODE (y) == x_code)
+ {
+ *prev = XEXP (c, 1);
+ free_EXPR_LIST_node (c);
+ return old ? old : const0_rtx;
+ }
+
+ /* If we find X being a compliment of a condition in OLD,
+ then we need do nothing. */
+ if (GET_CODE (y) == reverse_condition (x_code))
+ return old;
+ }
+ }
+
+ /* Otherwise, by implication, the register in question is now live for
+ the inverse of the condition X. */
+ return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
+ VOIDmode, x_reg, const0_rtx),
+ old);
+}
+#endif /* HAVE_conditional_execution */
+\f
#ifdef AUTO_INC_DEC
/* X is a MEM found in INSN. See if we can convert it into an auto-increment
reference. */
static void
-find_auto_inc (needed, x, insn)
- regset needed;
+find_auto_inc (pbi, x, insn)
+ struct propagate_block_info *pbi;
rtx x;
rtx insn;
{
int regno = REGNO (addr);
/* Is the next use an increment that might make auto-increment? */
- if ((incr = reg_next_use[regno]) != 0
+ if ((incr = pbi->reg_next_use[regno]) != 0
&& (set = single_set (incr)) != 0
&& GET_CODE (set) == SET
&& BLOCK_NUM (incr) == BLOCK_NUM (insn)
? (offset ? PRE_INC : POST_INC)
: (offset ? PRE_DEC : POST_DEC));
- if (dead_or_set_p (incr, addr))
+ if (dead_or_set_p (incr, addr)
+ /* Mustn't autoinc an eliminable register. */
+ && (regno >= FIRST_PSEUDO_REGISTER
+ || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
{
/* This is the simple case. Try to make the auto-inc. If
we can't, we are done. Otherwise, we will do any
Change it to q = p, ...*q..., q = q+size.
Then fall into the usual case. */
rtx insns, temp;
- basic_block bb;
start_sequence ();
emit_move_insn (q, addr);
insns = get_insns ();
end_sequence ();
- bb = BLOCK_FOR_INSN (insn);
- for (temp = insns; temp; temp = NEXT_INSN (temp))
- set_block_for_insn (temp, bb);
+ if (basic_block_for_insn)
+ for (temp = insns; temp; temp = NEXT_INSN (temp))
+ set_block_for_insn (temp, pbi->bb);
/* If we can't make the auto-inc, or can't make the
replacement into Y, exit. There's no point in making
new insn(s) and do the updates. */
emit_insns_before (insns, insn);
- if (BLOCK_FOR_INSN (insn)->head == insn)
- BLOCK_FOR_INSN (insn)->head = insns;
+ if (pbi->bb->head == insn)
+ pbi->bb->head = insns;
/* INCR will become a NOTE and INSN won't contain a
use of ADDR. If a use of ADDR was just placed in
if (GET_CODE (PREV_INSN (insn)) == INSN
&& GET_CODE (PATTERN (PREV_INSN (insn))) == SET
&& SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
- reg_next_use[regno] = PREV_INSN (insn);
+ pbi->reg_next_use[regno] = PREV_INSN (insn);
else
- reg_next_use[regno] = 0;
+ pbi->reg_next_use[regno] = 0;
addr = q;
regno = REGNO (q);
- /* REGNO is now used in INCR which is below INSN, but
- it previously wasn't live here. If we don't mark
- it as needed, we'll put a REG_DEAD note for it
- on this insn, which is incorrect. */
- SET_REGNO_REG_SET (needed, regno);
+ /* REGNO is now used in INCR which is below INSN, but it
+ previously wasn't live here. If we don't mark it as
+ live, we'll put a REG_DEAD note for it on this insn,
+ which is incorrect. */
+ SET_REGNO_REG_SET (pbi->reg_live, regno);
/* If there are any calls between INSN and INCR, show
that REGNO now crosses them. */
register. */
if (SET_DEST (set) == addr)
{
+ /* If the original source was dead, it's dead now. */
+ rtx note = find_reg_note (incr, REG_DEAD, NULL_RTX);
+ if (note && XEXP (note, 0) != addr)
+ CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
+
PUT_CODE (incr, NOTE);
NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (incr) = 0;
/* 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) += pbi->bb->loop_depth + 1;
/* Count the increment as a setting of the register,
even though it isn't a SET in rtl. */
}
#endif /* AUTO_INC_DEC */
\f
-/* Scan expression X and store a 1-bit in LIVE for each reg it uses.
- This is done assuming the registers needed from X
- are those that have 1-bits in NEEDED.
+static void
+mark_used_reg (pbi, reg, cond, insn)
+ struct propagate_block_info *pbi;
+ rtx reg;
+ rtx cond ATTRIBUTE_UNUSED;
+ rtx insn;
+{
+ int regno = REGNO (reg);
+ int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
+ int some_was_dead = ! some_was_live;
+ int some_not_set;
+ int n;
+
+ /* A hard reg in a wide mode may really be multiple registers.
+ If so, mark all of them just like the first. */
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n > 0)
+ {
+ int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
+ some_was_live |= needed_regno;
+ some_was_dead |= ! needed_regno;
+ }
+ }
+
+ if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
+ {
+ /* Record where each reg is used, so when the reg is set we know
+ the next insn that uses it. */
+ pbi->reg_next_use[regno] = insn;
+ }
+
+ if (pbi->flags & PROP_REG_INFO)
+ {
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ /* If this is a register we are going to try to eliminate,
+ don't mark it live here. If we are successful in
+ eliminating it, it need not be live unless it is used for
+ pseudos, in which case it will have been set live when it
+ was allocated to the pseudos. If the register will not
+ be eliminated, reload will set it live at that point.
+
+ Otherwise, record that this function uses this register. */
+ /* ??? The PPC backend tries to "eliminate" on the pic
+ register to itself. This should be fixed. In the mean
+ time, hack around it. */
+
+ if (! (TEST_HARD_REG_BIT (elim_reg_set, regno)
+ && (regno == FRAME_POINTER_REGNUM
+ || regno == ARG_POINTER_REGNUM)))
+ {
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ do
+ regs_ever_live[regno + --n] = 1;
+ while (n > 0);
+ }
+ }
+ else
+ {
+ /* Keep track of which basic block each reg appears in. */
+
+ register int blocknum = pbi->bb->index;
+ if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
+ REG_BASIC_BLOCK (regno) = blocknum;
+ else if (REG_BASIC_BLOCK (regno) != blocknum)
+ REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
+
+ /* Count (weighted) number of uses of each reg. */
+ REG_N_REFS (regno) += pbi->bb->loop_depth + 1;
+ }
+ }
+
+ /* Find out if any of the register was set this insn. */
+ some_not_set = ! REGNO_REG_SET_P (pbi->new_set, regno);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n > 0)
+ some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, regno + n);
+ }
+
+ /* Record and count the insns in which a reg dies. If it is used in
+ this insn and was dead below the insn then it dies in this insn.
+ If it was set in this insn, we do not make a REG_DEAD note;
+ likewise if we already made such a note. */
+ if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
+ && some_was_dead
+ && some_not_set)
+ {
+ /* Check for the case where the register dying partially
+ overlaps the register set by this insn. */
+ if (regno < FIRST_PSEUDO_REGISTER
+ && HARD_REGNO_NREGS (regno, GET_MODE (reg)) > 1)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n >= 0)
+ some_was_live |= REGNO_REG_SET_P (pbi->new_set, regno + n);
+ }
+
+ /* If none of the words in X is needed, make a REG_DEAD note.
+ Otherwise, we must make partial REG_DEAD notes. */
+ if (! some_was_live)
+ {
+ if ((pbi->flags & PROP_DEATH_NOTES)
+ && ! find_regno_note (insn, REG_DEAD, regno))
+ REG_NOTES (insn)
+ = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
+
+ if (pbi->flags & PROP_REG_INFO)
+ REG_N_DEATHS (regno)++;
+ }
+ else
+ {
+ /* Don't make a REG_DEAD note for a part of a register
+ that is set in the insn. */
+
+ n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
+ for (; n >= regno; n--)
+ if (! REGNO_REG_SET_P (pbi->reg_live, n)
+ && ! dead_or_set_regno_p (insn, n))
+ REG_NOTES (insn)
+ = alloc_EXPR_LIST (REG_DEAD,
+ gen_rtx_REG (reg_raw_mode[n], n),
+ REG_NOTES (insn));
+ }
+ }
+
+ SET_REGNO_REG_SET (pbi->reg_live, regno);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n > 0)
+ SET_REGNO_REG_SET (pbi->reg_live, regno + n);
+ }
+
+#ifdef HAVE_conditional_execution
+ /* If this is a conditional use, record that fact. If it is later
+ conditionally set, we'll know to kill the register. */
+ if (cond != NULL_RTX)
+ {
+ splay_tree_node node;
+ struct reg_cond_life_info *rcli;
+ rtx ncond;
+
+ if (some_was_live)
+ {
+ node = splay_tree_lookup (pbi->reg_cond_dead, regno);
+ if (node == NULL)
+ {
+ /* The register was unconditionally live previously.
+ No need to do anything. */
+ }
+ else
+ {
+ /* The register was conditionally live previously.
+ Subtract the new life cond from the old death cond. */
+ rcli = (struct reg_cond_life_info *) node->value;
+ ncond = rcli->condition;
+ ncond = nand_reg_cond (ncond, cond);
+
+ /* If the register is now unconditionally live, remove the
+ entry in the splay_tree. */
+ if (ncond == const0_rtx)
+ {
+ rcli->condition = NULL_RTX;
+ splay_tree_remove (pbi->reg_cond_dead, regno);
+ }
+ else
+ rcli->condition = ncond;
+ }
+ }
+ else
+ {
+ /* The register was not previously live at all. Record
+ the condition under which it is still dead. */
+ rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
+ rcli->condition = not_reg_cond (cond);
+ splay_tree_insert (pbi->reg_cond_dead, regno,
+ (splay_tree_value) rcli);
+ }
+ }
+#endif
+}
- FLAGS is the set of enabled operations.
+/* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
+ This is done assuming the registers needed from X are those that
+ have 1-bits in PBI->REG_LIVE.
- INSN is the containing instruction. If INSN is dead, this function is not
- called. */
+ INSN is the containing instruction. If INSN is dead, this function
+ is not called. */
static void
-mark_used_regs (needed, live, x, flags, insn)
- regset needed;
- regset live;
- rtx x;
- int flags;
- rtx insn;
+mark_used_regs (pbi, x, cond, insn)
+ struct propagate_block_info *pbi;
+ rtx x, cond, insn;
{
register RTX_CODE code;
register int regno;
- int i;
+ int flags = pbi->flags;
retry:
code = GET_CODE (x);
#ifdef HAVE_cc0
case CC0:
- cc0_live = 1;
+ pbi->cc0_live = 1;
return;
#endif
/* If we are clobbering a MEM, mark any registers inside the address
as being used. */
if (GET_CODE (XEXP (x, 0)) == MEM)
- mark_used_regs (needed, live, XEXP (XEXP (x, 0), 0), flags, insn);
+ mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
return;
case MEM:
; /* needn't clear the memory set list */
else
{
- rtx temp = mem_set_list;
+ rtx temp = pbi->mem_set_list;
rtx prev = NULL_RTX;
rtx next;
if (prev)
XEXP (prev, 1) = next;
else
- mem_set_list = next;
+ pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
}
else
address modes. Then we may need to kill some entries on the
memory set list. */
if (insn)
- invalidate_mems_from_autoinc (insn);
+ invalidate_mems_from_autoinc (pbi, insn);
}
#ifdef AUTO_INC_DEC
if (flags & PROP_AUTOINC)
- find_auto_inc (needed, x, insn);
+ find_auto_inc (pbi, x, insn);
#endif
break;
/* While we're here, optimize this case. */
x = SUBREG_REG (x);
-
- /* In case the SUBREG is not of a register, don't optimize */
if (GET_CODE (x) != REG)
- {
- mark_used_regs (needed, live, x, flags, insn);
- return;
- }
-
- /* ... fall through ... */
+ goto retry;
+ /* FALLTHRU */
case REG:
- /* See a register other than being set
- => mark it as needed. */
+ /* See a register other than being set => mark it as needed. */
+ mark_used_reg (pbi, x, cond, insn);
+ return;
- regno = REGNO (x);
+ case SET:
{
- int some_needed = REGNO_REG_SET_P (needed, regno);
- int some_not_needed = ! some_needed;
-
- SET_REGNO_REG_SET (live, regno);
+ register rtx testreg = SET_DEST (x);
+ int mark_dest = 0;
- /* A hard reg in a wide mode may really be multiple registers.
- If so, mark all of them just like the first. */
- if (regno < FIRST_PSEUDO_REGISTER)
+ /* If storing into MEM, don't show it as being used. But do
+ show the address as being used. */
+ if (GET_CODE (testreg) == MEM)
{
- int n;
-
- /* For stack ptr or fixed arg pointer,
- nothing below can be necessary, so waste no more time. */
- if (regno == STACK_POINTER_REGNUM
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- || (regno == HARD_FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed))
-#endif
-#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
- || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
+#ifdef AUTO_INC_DEC
+ if (flags & PROP_AUTOINC)
+ find_auto_inc (pbi, testreg, insn);
#endif
- || (regno == FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
- {
- /* If this is a register we are going to try to eliminate,
- don't mark it live here. If we are successful in
- eliminating it, it need not be live unless it is used for
- pseudos, in which case it will have been set live when
- 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))
- regs_ever_live[regno] = 1;
- return;
- }
- /* No death notes for global register variables;
- their values are live after this function exits. */
- if (global_regs[regno])
- {
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- reg_next_use[regno] = insn;
- return;
- }
-
- n = HARD_REGNO_NREGS (regno, GET_MODE (x));
- while (--n > 0)
- {
- int regno_n = regno + n;
- int needed_regno = REGNO_REG_SET_P (needed, regno_n);
-
- SET_REGNO_REG_SET (live, regno_n);
- some_needed |= needed_regno;
- some_not_needed |= ! needed_regno;
- }
- }
-
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- {
- /* Record where each reg is used, so when the reg
- is set we know the next insn that uses it. */
-
- reg_next_use[regno] = insn;
- }
- if (flags & PROP_REG_INFO)
- {
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- /* If a hard reg is being used,
- record that this function does use it. */
-
- i = HARD_REGNO_NREGS (regno, GET_MODE (x));
- if (i == 0)
- i = 1;
- do
- regs_ever_live[regno + --i] = 1;
- while (i > 0);
- }
- else
- {
- /* Keep track of which basic block each reg appears in. */
-
- register int blocknum = BLOCK_NUM (insn);
-
- if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
- REG_BASIC_BLOCK (regno) = blocknum;
- else if (REG_BASIC_BLOCK (regno) != blocknum)
- REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
-
- /* Count (weighted) number of uses of each reg. */
-
- REG_N_REFS (regno) += loop_depth;
- }
- }
-
- /* Record and count the insns in which a reg dies.
- If it is used in this insn and was dead below the insn
- then it dies in this insn. If it was set in this insn,
- we do not make a REG_DEAD note; likewise if we already
- made such a note. */
-
- if (flags & PROP_DEATH_NOTES)
- {
- if (some_not_needed
- && ! dead_or_set_p (insn, x)
-#if 0
- && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
-#endif
- )
- {
- /* Check for the case where the register dying partially
- overlaps the register set by this insn. */
- if (regno < FIRST_PSEUDO_REGISTER
- && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
- {
- int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
- while (--n >= 0)
- some_needed |= dead_or_set_regno_p (insn, regno + n);
- }
-
- /* If none of the words in X is needed, make a REG_DEAD
- note. Otherwise, we must make partial REG_DEAD notes. */
- if (! some_needed)
- {
- REG_NOTES (insn)
- = alloc_EXPR_LIST (REG_DEAD, x, REG_NOTES (insn));
- REG_N_DEATHS (regno)++;
- }
- else
- {
- int i;
-
- /* Don't make a REG_DEAD note for a part of a register
- that is set in the insn. */
-
- for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
- i >= 0; i--)
- if (!REGNO_REG_SET_P (needed, regno + i)
- && ! dead_or_set_regno_p (insn, regno + i))
- REG_NOTES (insn)
- = (alloc_EXPR_LIST
- (REG_DEAD, gen_rtx_REG (reg_raw_mode[regno + i],
- regno + i),
- REG_NOTES (insn)));
- }
- }
- }
- }
- return;
-
- case SET:
- {
- register rtx testreg = SET_DEST (x);
- int mark_dest = 0;
-
- /* If storing into MEM, don't show it as being used. But do
- show the address as being used. */
- if (GET_CODE (testreg) == MEM)
- {
-#ifdef AUTO_INC_DEC
- if (flags & PROP_AUTOINC)
- find_auto_inc (needed, testreg, insn);
-#endif
- mark_used_regs (needed, live, XEXP (testreg, 0), flags, insn);
- mark_used_regs (needed, live, SET_SRC (x), flags, insn);
+ mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
+ mark_used_regs (pbi, SET_SRC (x), cond, insn);
return;
}
testreg = XEXP (testreg, 0);
}
- /* If this is a store into a register,
- recursively scan the value being stored. */
+ /* If this is a store into a register, recursively scan the
+ value being stored. */
if ((GET_CODE (testreg) == PARALLEL
&& GET_MODE (testreg) == BLKmode)
|| (GET_CODE (testreg) == REG
- && (regno = REGNO (testreg), ! (regno == FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
+ && (regno = REGNO (testreg),
+ ! (regno == FRAME_POINTER_REGNUM
+ && (! reload_completed || frame_pointer_needed)))
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
&& ! (regno == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
&& ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
#endif
))
- /* We used to exclude global_regs here, but that seems wrong.
- Storing in them is like storing in mem. */
{
- mark_used_regs (needed, live, SET_SRC (x), flags, insn);
if (mark_dest)
- mark_used_regs (needed, live, SET_DEST (x), flags, insn);
+ mark_used_regs (pbi, SET_DEST (x), cond, insn);
+ mark_used_regs (pbi, SET_SRC (x), cond, insn);
return;
}
}
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:
So for now, just clear the memory set list and mark any regs
we can find in ASM_OPERANDS as used. */
if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
- free_EXPR_LIST_list (&mem_set_list);
+ free_EXPR_LIST_list (&pbi->mem_set_list);
/* For all ASM_OPERANDS, we must traverse the vector of input operands.
We can not just fall through here since then we would be confused
int j;
for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
- mark_used_regs (needed, live, ASM_OPERANDS_INPUT (x, j),
- flags, insn);
+ mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
}
break;
}
+ case COND_EXEC:
+ if (cond != NULL_RTX)
+ abort ();
+
+ mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
+
+ cond = COND_EXEC_TEST (x);
+ x = COND_EXEC_CODE (x);
+ goto retry;
+
+ case PHI:
+ /* We _do_not_ want to scan operands of phi nodes. Operands of
+ a phi function are evaluated only when control reaches this
+ block along a particular edge. Therefore, regs that appear
+ as arguments to phi should not be added to the global live at
+ start. */
+ return;
default:
break;
x = XEXP (x, 0);
goto retry;
}
- mark_used_regs (needed, live, XEXP (x, i), flags, insn);
+ mark_used_regs (pbi, XEXP (x, i), cond, insn);
}
else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
- mark_used_regs (needed, live, XVECEXP (x, i, j), flags, insn);
+ mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
}
}
}
#ifdef AUTO_INC_DEC
static int
-try_pre_increment_1 (insn)
+try_pre_increment_1 (pbi, insn)
+ struct propagate_block_info *pbi;
rtx insn;
{
/* Find the next use of this reg. If in same basic block,
HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
* INTVAL (XEXP (SET_SRC (x), 1)));
int regno = REGNO (SET_DEST (x));
- rtx y = reg_next_use[regno];
+ rtx y = pbi->reg_next_use[regno];
if (y != 0
&& BLOCK_NUM (y) == BLOCK_NUM (insn)
/* Don't do this if the reg dies, or gets set in y; a standard addressing
less likely. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
- REG_N_REFS (regno) += loop_depth;
+ REG_N_REFS (regno) += pbi->bb->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);
+ 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");
did_output = print_rtl_single (outf, tmp_rtx);
if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
- fprintf (outf, ";; End of basic block %d\n", bb->index);
+ {
+ fprintf (outf, ";; End of basic block %d, registers live:\n",
+ bb->index);
+ dump_regset (bb->global_live_at_end, outf);
+ putc ('\n', outf);
+ }
if (did_output)
putc ('\n', outf);
}
}
-\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;
-{
- struct int_list_block *first_blk = *head_ptr;
-
- 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;
- }
-
- first_blk->nodes_left--;
- return &first_blk->nodes[first_blk->nodes_left];
-}
-
-/* Pointer to head of predecessor/successor block list. */
-static int_list_block *pred_int_list_blocks;
-
-/* 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). */
-
-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);
-
- p->val = val;
- p->next = *list;
- *list = p;
- return p;
-}
-
-/* Free the blocks of lists at BLK_LIST. */
-
-void
-free_int_list (blk_list)
- int_list_block **blk_list;
-{
- int_list_block *p, *next;
-
- for (p = *blk_list; p != NULL; p = next)
- {
- next = p->next;
- free (p);
- }
-
- /* 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)
- {
- 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. */
-
-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;
-
- 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));
-
- 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);
- }
-
- 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);
-}
-
-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;
-
- 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");
- }
- fprintf (file, "\n");
- }
- fprintf (file, "\n");
-}
-
-/* Free basic block data storage. */
-
-void
-free_bb_mem ()
-{
- free_int_list (&pred_int_list_blocks);
-}
-
/* Compute dominator relationships using new flow graph structures. */
void
compute_flow_dominators (dominators, post_dominators)
int bb;
sbitmap *temp_bitmap;
edge e;
- basic_block *worklist, *tos;
+ basic_block *worklist, *workend, *qin, *qout;
+ int qlen;
/* 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);
+ worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
+ workend = &worklist[n_basic_blocks];
temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
{
/* The optimistic setting of dominators requires us to put every
block on the work list initially. */
+ qin = qout = worklist;
for (bb = 0; bb < n_basic_blocks; bb++)
{
- *tos++ = BASIC_BLOCK (bb);
+ *qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ qlen = n_basic_blocks;
+ qin = worklist;
/* We want a maximal solution, so initially assume everything dominates
everything else. */
e->dest->aux = ENTRY_BLOCK_PTR;
/* Iterate until the worklist is empty. */
- while (tos != worklist)
+ while (qlen)
{
/* Take the first entry off the worklist. */
- basic_block b = *--tos;
+ basic_block b = *qout++;
+ if (qout >= workend)
+ qout = worklist;
+ qlen--;
+
bb = b->index;
/* Compute the intersection of the dominators of all the
{
if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
{
- *tos++ = e->dest;
+ *qin++ = e->dest;
+ if (qin >= workend)
+ qin = worklist;
+ qlen++;
+
e->dest->aux = e;
}
}
{
/* The optimistic setting of dominators requires us to put every
block on the work list initially. */
+ qin = qout = worklist;
for (bb = 0; bb < n_basic_blocks; bb++)
{
- *tos++ = BASIC_BLOCK (bb);
+ *qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ qlen = n_basic_blocks;
+ qin = worklist;
/* We want a maximal solution, so initially assume everything post
dominates everything else. */
e->src->aux = EXIT_BLOCK_PTR;
/* Iterate until the worklist is empty. */
- while (tos != worklist)
+ while (qlen)
{
/* Take the first entry off the worklist. */
- basic_block b = *--tos;
+ basic_block b = *qout++;
+ if (qout >= workend)
+ qout = worklist;
+ qlen--;
+
bb = b->index;
/* Compute the intersection of the post dominators of all the
{
if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
{
- *tos++ = e->src;
+ *qin++ = e->src;
+ if (qin >= workend)
+ qin = worklist;
+ qlen++;
+
e->src->aux = e;
}
}
}
}
}
+
+ free (worklist);
free (temp_bitmap);
}
sbitmap_vector_free (tmp);
}
-/* Count for a single SET rtx, X. */
-
-static void
-count_reg_sets_1 (x)
- rtx x;
-{
- register int regno;
- register rtx reg = SET_DEST (x);
+/* Recompute register set/reference counts immediately prior to register
+ allocation.
- /* Find the register that's set/clobbered. */
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || GET_CODE (reg) == STRICT_LOW_PART)
- reg = XEXP (reg, 0);
+ This avoids problems with set/reference counts changing to/from values
+ which have special meanings to the register allocators.
- if (GET_CODE (reg) == PARALLEL
- && GET_MODE (reg) == BLKmode)
- {
- register int i;
- for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- count_reg_sets_1 (XVECEXP (reg, 0, i));
- return;
- }
+ Additionally, the reference counts are the primary component used by the
+ register allocators to prioritize pseudos for allocation to hard regs.
+ More accurate reference counts generally lead to better register allocation.
- if (GET_CODE (reg) == REG)
- {
- regno = REGNO (reg);
- if (regno >= FIRST_PSEUDO_REGISTER)
- {
- /* Count (weighted) references, stores, etc. This counts a
- register twice if it is modified, but that is correct. */
- REG_N_SETS (regno)++;
+ F is the first insn to be scanned.
- REG_N_REFS (regno) += loop_depth;
- }
- }
-}
+ 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.
-/* Increment REG_N_SETS for each SET or CLOBBER found in X; also increment
- REG_N_REFS by the current loop depth for each SET or CLOBBER found. */
+ It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
+ possibly other information which is used by the register allocators. */
-static void
-count_reg_sets (x)
- rtx x;
+void
+recompute_reg_usage (f, loop_step)
+ rtx f ATTRIBUTE_UNUSED;
+ int loop_step ATTRIBUTE_UNUSED;
{
- register RTX_CODE code = GET_CODE (x);
-
- if (code == SET || code == CLOBBER)
- count_reg_sets_1 (x);
- else if (code == PARALLEL)
- {
- register int i;
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
- {
- code = GET_CODE (XVECEXP (x, 0, i));
- if (code == SET || code == CLOBBER)
- count_reg_sets_1 (XVECEXP (x, 0, i));
- }
- }
+ allocate_reg_life_data ();
+ update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO);
}
-/* Increment REG_N_REFS by the current loop depth each register reference
- found in X. */
+/* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
+ blocks. If BLOCKS is NULL, assume the universal set. Returns a count
+ of the number of registers that died. */
-static void
-count_reg_references (x)
- rtx x;
+int
+count_or_remove_death_notes (blocks, kill)
+ sbitmap blocks;
+ int kill;
{
- register RTX_CODE code;
+ int i, count = 0;
- retry:
- code = GET_CODE (x);
- switch (code)
+ for (i = n_basic_blocks - 1; i >= 0; --i)
{
- case LABEL_REF:
- case SYMBOL_REF:
- case CONST_INT:
- case CONST:
- case CONST_DOUBLE:
- case PC:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- case ASM_INPUT:
- return;
-
-#ifdef HAVE_cc0
- case CC0:
- return;
-#endif
-
- case CLOBBER:
- /* If we are clobbering a MEM, mark any registers inside the address
- as being used. */
- if (GET_CODE (XEXP (x, 0)) == MEM)
- count_reg_references (XEXP (XEXP (x, 0), 0));
- return;
-
- case SUBREG:
- /* While we're here, optimize this case. */
- x = SUBREG_REG (x);
-
- /* In case the SUBREG is not of a register, don't optimize */
- if (GET_CODE (x) != REG)
- {
- count_reg_references (x);
- return;
- }
-
- /* ... fall through ... */
-
- case REG:
- if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
- REG_N_REFS (REGNO (x)) += loop_depth;
- return;
-
- case SET:
- {
- register rtx testreg = SET_DEST (x);
- int mark_dest = 0;
-
- /* If storing into MEM, don't show it as being used. But do
- show the address as being used. */
- if (GET_CODE (testreg) == MEM)
- {
- count_reg_references (XEXP (testreg, 0));
- count_reg_references (SET_SRC (x));
- return;
- }
-
- /* Storing in STRICT_LOW_PART is like storing in a reg
- in that this SET might be dead, so ignore it in TESTREG.
- but in some other ways it is like using the reg.
-
- Storing in a SUBREG or a bit field is like storing the entire
- register in that if the register's value is not used
- then this SET is not needed. */
- while (GET_CODE (testreg) == STRICT_LOW_PART
- || GET_CODE (testreg) == ZERO_EXTRACT
- || GET_CODE (testreg) == SIGN_EXTRACT
- || GET_CODE (testreg) == SUBREG)
- {
- /* Modifying a single register in an alternate mode
- does not use any of the old value. But these other
- ways of storing in a register do use the old value. */
- if (GET_CODE (testreg) == SUBREG
- && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
- ;
- else
- mark_dest = 1;
-
- testreg = XEXP (testreg, 0);
- }
-
- /* If this is a store into a register,
- recursively scan the value being stored. */
-
- if ((GET_CODE (testreg) == PARALLEL
- && GET_MODE (testreg) == BLKmode)
- || GET_CODE (testreg) == REG)
- {
- count_reg_references (SET_SRC (x));
- if (mark_dest)
- count_reg_references (SET_DEST (x));
- return;
- }
- }
- break;
-
- default:
- break;
- }
-
- /* Recursively scan the operands of this expression. */
-
- {
- register const char *fmt = GET_RTX_FORMAT (code);
- register int i;
-
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- /* Tail recursive case: save a function call level. */
- if (i == 0)
- {
- x = XEXP (x, 0);
- goto retry;
- }
- count_reg_references (XEXP (x, i));
- }
- else if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- count_reg_references (XVECEXP (x, i, j));
- }
- }
- }
-}
-
-/* Recompute register set/reference counts immediately prior to register
- allocation.
-
- This avoids problems with set/reference counts changing to/from values
- which have special meanings to the register allocators.
-
- Additionally, the reference counts are the primary component used by the
- register allocators to prioritize pseudos for allocation to hard regs.
- 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.
-
- 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 insn;
- int i, max_reg;
-
- /* Clear out the old data. */
- max_reg = max_reg_num ();
- for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
- {
- REG_N_SETS (i) = 0;
- REG_N_REFS (i) = 0;
- }
-
- /* 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))
- {
- /* 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;
-
- /* 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)))++;
- }
-
- /* 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;
-
- 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));
- }
- }
- }
-}
-
-/* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
- blocks. If BLOCKS is NULL, assume the universal set. Returns a count
- of the number of registers that died. */
-
-int
-count_or_remove_death_notes (blocks, kill)
- sbitmap blocks;
- int kill;
-{
- int i, count = 0;
-
- for (i = n_basic_blocks - 1; i >= 0; --i)
- {
- basic_block bb;
- rtx insn;
+ basic_block bb;
+ rtx insn;
if (blocks && ! TEST_BIT (blocks, i))
continue;
and NOTE_INSN_BASIC_BLOCK
- check that all insns are in the basic blocks
(except the switch handling code, barriers and notes)
+ - check that all returns are followed by barriers
In future it can be extended check a lot of other stuff as well
(reachability of basic blocks, life information, etc. etc.). */
}
}
+ if (GET_RTX_CLASS (GET_CODE (x)) == 'i'
+ && GET_CODE (x) == JUMP_INSN
+ && returnjump_p (x) && ! condjump_p (x)
+ && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
+ fatal_insn ("Return not followed by barrier", x);
+
x = NEXT_INSN (x);
}
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);
+}
+
+
+/* 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
