#include "config.h"
#include "system.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "ssa.h"
#include "insn-config.h"
#include "recog.h"
#include "output.h"
typedef struct {
bitmap *data;
int length;
} control_dependent_block_to_edge_map_s, *control_dependent_block_to_edge_map;
static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create
PARAMS((size_t num_basic_blocks));
static void set_control_dependent_block_to_edge_map_bit
PARAMS ((control_dependent_block_to_edge_map c, basic_block bb,
int edge_index));
static void control_dependent_block_to_edge_map_free
PARAMS ((control_dependent_block_to_edge_map c));
static void find_all_control_dependences
PARAMS ((struct edge_list *el, dominance_info pdom,
control_dependent_block_to_edge_map cdbte));
static void find_control_dependence
PARAMS ((struct edge_list *el, int edge_index, dominance_info pdom,
control_dependent_block_to_edge_map cdbte));
static basic_block find_pdom
PARAMS ((dominance_info pdom, basic_block block));
static int inherently_necessary_register_1
PARAMS ((rtx *current_rtx, void *data));
static int inherently_necessary_register
PARAMS ((rtx current_rtx));
static int find_inherently_necessary
PARAMS ((rtx current_rtx));
static int propagate_necessity_through_operand
PARAMS ((rtx *current_rtx, void *data));
static void note_inherently_necessary_set
PARAMS ((rtx, rtx, void *));
#define KILL_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 1
#define RESURRECT_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 0
#define UNNECESSARY_P(INSN) INSN_DEAD_CODE_P(INSN)
static void mark_all_insn_unnecessary
PARAMS ((void));
#define EXECUTE_IF_UNNECESSARY(INSN, CODE) \
{ \
rtx INSN; \
\
for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN)) \
if (INSN_DEAD_CODE_P (INSN)) { \
CODE; \
} \
}
static rtx find_block_label
PARAMS ((basic_block bb));
static void delete_insn_bb
PARAMS ((rtx insn));
static control_dependent_block_to_edge_map
control_dependent_block_to_edge_map_create (num_basic_blocks)
size_t num_basic_blocks;
{
int i;
control_dependent_block_to_edge_map c
= xmalloc (sizeof (control_dependent_block_to_edge_map_s));
c->length = num_basic_blocks - (INVALID_BLOCK+1);
c->data = xmalloc ((size_t) c->length*sizeof (bitmap));
for (i = 0; i < c->length; ++i)
c->data[i] = BITMAP_XMALLOC ();
return c;
}
static void
set_control_dependent_block_to_edge_map_bit (c, bb, edge_index)
control_dependent_block_to_edge_map c;
basic_block bb;
int edge_index;
{
if (bb->index - (INVALID_BLOCK+1) >= c->length)
abort ();
bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)],
edge_index);
}
#define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
EXECUTE_IF_SET_IN_BITMAP \
(CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
EDGE_NUMBER, CODE)
static void
control_dependent_block_to_edge_map_free (c)
control_dependent_block_to_edge_map c;
{
int i;
for (i = 0; i < c->length; ++i)
BITMAP_XFREE (c->data[i]);
free ((PTR) c);
}
static void
find_all_control_dependences (el, pdom, cdbte)
struct edge_list *el;
dominance_info pdom;
control_dependent_block_to_edge_map cdbte;
{
int i;
for (i = 0; i < NUM_EDGES (el); ++i)
find_control_dependence (el, i, pdom, cdbte);
}
static void
find_control_dependence (el, edge_index, pdom, cdbte)
struct edge_list *el;
int edge_index;
dominance_info pdom;
control_dependent_block_to_edge_map cdbte;
{
basic_block current_block;
basic_block ending_block;
if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
abort ();
ending_block =
(INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
? ENTRY_BLOCK_PTR->next_bb
: find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
current_block != ending_block && current_block != EXIT_BLOCK_PTR;
current_block = find_pdom (pdom, current_block))
{
set_control_dependent_block_to_edge_map_bit (cdbte,
current_block,
edge_index);
}
}
static basic_block
find_pdom (pdom, block)
dominance_info pdom;
basic_block block;
{
if (!block)
abort ();
if (block->index == INVALID_BLOCK)
abort ();
if (block == ENTRY_BLOCK_PTR)
return ENTRY_BLOCK_PTR->next_bb;
else if (block == EXIT_BLOCK_PTR)
return EXIT_BLOCK_PTR;
else
{
basic_block bb = get_immediate_dominator (pdom, block);
if (!bb)
return EXIT_BLOCK_PTR;
return bb;
}
}
static int
inherently_necessary_register_1 (current_rtx, data)
rtx *current_rtx;
void *data ATTRIBUTE_UNUSED;
{
rtx x = *current_rtx;
if (x == NULL_RTX)
return 0;
switch (GET_CODE (x))
{
case CLOBBER:
return -1;
break;
case PC:
return 0;
break;
case REG:
if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx)
return 0;
else
return !0;
break;
default:
return 0;
break;
}
}
static int
inherently_necessary_register (current_rtx)
rtx current_rtx;
{
return for_each_rtx (¤t_rtx,
&inherently_necessary_register_1, NULL);
}
static void
note_inherently_necessary_set (dest, set, data)
rtx set ATTRIBUTE_UNUSED;
rtx dest;
void *data;
{
int *inherently_necessary_set_p = (int *) data;
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == STRICT_LOW_PART
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == SIGN_EXTRACT)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == MEM
|| GET_CODE (dest) == UNSPEC
|| GET_CODE (dest) == UNSPEC_VOLATILE)
*inherently_necessary_set_p = 1;
}
static int
find_inherently_necessary (x)
rtx x;
{
if (x == NULL_RTX)
return 0;
else if (inherently_necessary_register (x))
return !0;
else
switch (GET_CODE (x))
{
case CALL_INSN:
case BARRIER:
case PREFETCH:
return !0;
case CODE_LABEL:
case NOTE:
return 0;
case JUMP_INSN:
return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
case INSN:
{
int inherently_necessary_set = 0;
note_stores (PATTERN (x),
note_inherently_necessary_set,
&inherently_necessary_set);
return (inherently_necessary_set
|| GET_CODE (PATTERN (x)) == ASM_INPUT
|| asm_noperands (PATTERN (x)) >= 0);
}
default:
abort ();
break;
}
}
static int
propagate_necessity_through_operand (current_rtx, data)
rtx *current_rtx;
void *data;
{
rtx x = *current_rtx;
varray_type *unprocessed_instructions = (varray_type *) data;
if (x == NULL_RTX)
return 0;
switch ( GET_CODE (x))
{
case REG:
if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
{
rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
if (insn != NULL_RTX && UNNECESSARY_P (insn))
{
RESURRECT_INSN (insn);
VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
}
}
return 0;
default:
return 0;
}
}
static void
mark_all_insn_unnecessary ()
{
rtx insn;
for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
KILL_INSN (insn);
}
static rtx
find_block_label (bb)
basic_block bb;
{
rtx insn = bb->head;
if (LABEL_P (insn))
return insn;
else
{
rtx new_label = emit_label_before (gen_label_rtx (), insn);
if (insn == bb->head)
bb->head = new_label;
return new_label;
}
}
static void
delete_insn_bb (insn)
rtx insn;
{
if (!insn)
abort ();
if (! INSN_P (insn))
return;
delete_insn (insn);
}
void
ssa_eliminate_dead_code ()
{
rtx insn;
basic_block bb;
varray_type unprocessed_instructions;
control_dependent_block_to_edge_map cdbte;
dominance_info pdom;
struct edge_list *el;
mark_all_insn_unnecessary ();
VARRAY_RTX_INIT (unprocessed_instructions, 64,
"unprocessed instructions");
cdbte = control_dependent_block_to_edge_map_create (last_basic_block);
connect_infinite_loops_to_exit ();
pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
el = create_edge_list ();
find_all_control_dependences (el, pdom, cdbte);
for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
if (find_inherently_necessary (insn))
{
RESURRECT_INSN (insn);
VARRAY_PUSH_RTX (unprocessed_instructions, insn);
}
while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
{
rtx current_instruction;
int edge_number;
current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
VARRAY_POP (unprocessed_instructions);
if (INSN_P (current_instruction)
&& !JUMP_TABLE_DATA_P (current_instruction))
{
EXECUTE_IF_CONTROL_DEPENDENT
(cdbte, current_instruction, edge_number,
{
rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
if (GET_CODE (jump_insn) == JUMP_INSN
&& UNNECESSARY_P (jump_insn))
{
RESURRECT_INSN (jump_insn);
VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
}
});
for_each_rtx (¤t_instruction,
&propagate_necessity_through_operand,
(PTR) &unprocessed_instructions);
if (PHI_NODE_P (current_instruction))
{
rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
int num_elem = GET_NUM_ELEM (phi_vec);
int v;
for (v = num_elem - 2; v >= 0; v -= 2)
{
basic_block bb;
bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
EXECUTE_IF_CONTROL_DEPENDENT
(cdbte, bb->end, edge_number,
{
rtx jump_insn;
jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
if (((GET_CODE (jump_insn) == JUMP_INSN))
&& UNNECESSARY_P (jump_insn))
{
RESURRECT_INSN (jump_insn);
VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
}
});
}
}
}
}
EXECUTE_IF_UNNECESSARY (insn,
{
if (any_condjump_p (insn))
{
basic_block bb = BLOCK_FOR_INSN (insn);
basic_block pdom_bb = find_pdom (pdom, bb);
rtx lbl;
edge e;
if (pdom_bb == EXIT_BLOCK_PTR)
{
e = bb->succ;
while (e)
{
edge temp = e;
e = e->succ_next;
if ((temp->flags & EDGE_FALLTHRU) == 0)
{
if (temp->dest != EXIT_BLOCK_PTR)
{
rtx insn
= first_insn_after_basic_block_note (temp->dest);
while (PHI_NODE_P (insn))
{
remove_phi_alternative (PATTERN (insn), temp->src);
insn = NEXT_INSN (insn);
}
}
remove_edge (temp);
}
}
PUT_CODE (insn, NOTE);
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
continue;
}
e = bb->succ;
while (e)
{
edge temp = e;
e = e->succ_next;
if (temp->flags & EDGE_ABNORMAL)
continue;
if (temp->dest != EXIT_BLOCK_PTR)
{
rtx insn = first_insn_after_basic_block_note (temp->dest);
while (PHI_NODE_P (insn))
{
remove_phi_alternative (PATTERN (insn), temp->src);
insn = NEXT_INSN (insn);
}
}
remove_edge (temp);
}
make_edge (bb, pdom_bb, 0);
lbl = find_block_label (pdom_bb);
SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
INSN_CODE (insn) = -1;
JUMP_LABEL (insn) = lbl;
LABEL_NUSES (lbl)++;
emit_barrier_after (insn);
}
else if (!JUMP_P (insn))
delete_insn_bb (insn);
});
remove_fake_edges ();
FOR_EACH_BB (bb)
{
if (bb->succ == NULL)
{
rtx next = NEXT_INSN (bb->end);
if (!next || GET_CODE (next) != BARRIER)
emit_barrier_after (bb->end);
}
}
for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
RESURRECT_INSN (insn);
if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
abort ();
control_dependent_block_to_edge_map_free (cdbte);
free ((PTR) pdom);
free_edge_list (el);
}