Hi,
This is mostly a small memory and pointer-chasing cleanup. We always
know exactly what form an assignment takes so there is no need to
record assignments as SET-rtxen.
Bootstrapped and tested on x86_64-unknown-linux-gnu. OK?
Ciao!
Steven
* cprop.c (struct expr): Split 'expr' field in 'dest' and 'src'.
(expr_equiv_p): Remove.
(insert_set_in_table): Look at <dest, src> pair instead of expr.
(hash_scan_set): Update call to insert_set_in_table.
(dump_hash_table): Dump <dest, src> pair.
(lookup_set): Simplify. Lookup <dest, src> pair.
(compute_transp): Remove, fold heavily simplified code into...
(compute_local_properties): ...here. Expect COMP and TRANSP
unconditionally.
(find_avail_set): Take set directly from struct expr.
(find_bypass-set): Likewise.
(bypass_block): Likewise.
(cprop_insn): Likewise. Remove redundant INSN_P test.
*** cprop.c.v5 2011-04-02 00:56:57.000000000 +0200
--- cprop.c.v6 2011-04-02 15:54:38.000000000 +0200
*************** static struct obstack cprop_obstack;
*** 55,77 ****
struct reg_use {rtx reg_rtx; };
- /* Hash table of expressions. */
-
- struct expr
- {
- /* The expression (SET_SRC for expressions, PATTERN for assignments). */
- rtx expr;
- /* Index in the available expression bitmaps. */
- int bitmap_index;
- /* Next entry with the same hash. */
- struct expr *next_same_hash;
- /* List of available occurrence in basic blocks in the function.
- An "available occurrence" is one that is the last occurrence in the
- basic block and the operands are not modified by following statements in
- the basic block [including this insn]. */
- struct occr *avail_occr;
- };
-
/* Occurrence of an expression.
There is one per basic block. If a pattern appears more than once the
last appearance is used. */
--- 55,60 ----
*************** typedef struct occr *occr_t;
*** 88,94 ****
DEF_VEC_P (occr_t);
DEF_VEC_ALLOC_P (occr_t, heap);
! /* Expression and copy propagation hash tables.
Each hash table is an array of buckets.
??? It is known that if it were an array of entries, structure elements
`next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
--- 71,96 ----
DEF_VEC_P (occr_t);
DEF_VEC_ALLOC_P (occr_t, heap);
! /* Hash table entry for an assignment expressions. */
!
! struct expr
! {
! /* The expression (DEST := SRC). */
! rtx dest;
! rtx src;
!
! /* Index in the available expression bitmaps. */
! int bitmap_index;
! /* Next entry with the same hash. */
! struct expr *next_same_hash;
! /* List of available occurrence in basic blocks in the function.
! An "available occurrence" is one that is the last occurrence in the
! basic block and the operands are not modified by following statements in
! the basic block [including this insn]. */
! struct occr *avail_occr;
! };
!
! /* Hash table for copy propagation expressions.
Each hash table is an array of buckets.
??? It is known that if it were an array of entries, structure elements
`next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
*************** hash_set (int regno, int hash_table_size
*** 175,214 ****
return hash % hash_table_size;
}
! /* Return nonzero if exp1 is equivalent to exp2. */
!
! static int
! expr_equiv_p (const_rtx x, const_rtx y)
! {
! return exp_equiv_p (x, y, 0, true);
! }
!
! /* Insert pattern X in INSN in the hash table.
! X is a SET of a reg to either another reg or a constant.
! If it is already present, record it as the last occurrence in INSN's
! basic block. */
static void
! insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table)
{
! int found;
unsigned int hash;
struct expr *cur_expr, *last_expr = NULL;
struct occr *cur_occr;
! gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x)));
!
! hash = hash_set (REGNO (SET_DEST (x)), table->size);
! cur_expr = table->table[hash];
! found = 0;
!
! while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
{
! /* If the expression isn't found, save a pointer to the end of
! the list. */
last_expr = cur_expr;
- cur_expr = cur_expr->next_same_hash;
}
if (! found)
--- 177,207 ----
return hash % hash_table_size;
}
! /* Insert assignment DEST:=SET from INSN in the hash table.
! DEST is a register and SET is a register or a suitable constant.
! If the assignment is already present in the table, record it as
! the last occurrence in INSN's basic block. */
static void
! insert_set_in_table (rtx dest, rtx src, rtx insn, struct hash_table_d *table)
{
! bool found = false;
unsigned int hash;
struct expr *cur_expr, *last_expr = NULL;
struct occr *cur_occr;
! hash = hash_set (REGNO (dest), table->size);
! for (cur_expr = table->table[hash]; cur_expr;
! cur_expr = cur_expr->next_same_hash)
{
! if (dest == cur_expr->dest
! && src == cur_expr->src)
! {
! found = true;
! break;
! }
last_expr = cur_expr;
}
if (! found)
*************** insert_set_in_table (rtx x, rtx insn, st
*** 225,231 ****
/* Set the fields of the expr element.
We must copy X because it can be modified when copy propagation is
performed on its operands. */
! cur_expr->expr = copy_rtx (x);
cur_expr->bitmap_index = table->n_elems++;
cur_expr->next_same_hash = NULL;
cur_expr->avail_occr = NULL;
--- 218,225 ----
/* Set the fields of the expr element.
We must copy X because it can be modified when copy propagation is
performed on its operands. */
! cur_expr->dest = copy_rtx (dest);
! cur_expr->src = copy_rtx (src);
cur_expr->bitmap_index = table->n_elems++;
cur_expr->next_same_hash = NULL;
cur_expr->avail_occr = NULL;
*************** hash_scan_set (rtx pat, rtx insn, struct
*** 290,296 ****
for INSN, we miss copy propagation opportunities.
Note that this does not impede profitable constant propagations. We
! "look through" reg-reg sets in lookup_avail_set. */
rtx note = find_reg_equal_equiv_note (insn);
if (note != 0
&& REG_NOTE_KIND (note) == REG_EQUAL
--- 284,290 ----
for INSN, we miss copy propagation opportunities.
Note that this does not impede profitable constant propagations. We
! "look through" reg-reg sets in lookup_set. */
rtx note = find_reg_equal_equiv_note (insn);
if (note != 0
&& REG_NOTE_KIND (note) == REG_EQUAL
*************** hash_scan_set (rtx pat, rtx insn, struct
*** 304,310 ****
&& ! HARD_REGISTER_P (src)
&& reg_available_p (src, insn))
|| cprop_constant_p (src))
! insert_set_in_table (pat, insn, table);
}
}
--- 298,304 ----
&& ! HARD_REGISTER_P (src)
&& reg_available_p (src, insn))
|| cprop_constant_p (src))
! insert_set_in_table (dest, src, insn, table);
}
}
*************** dump_hash_table (FILE *file, const char
*** 368,374 ****
expr = flat_table[i];
fprintf (file, "Index %d (hash value %d)\n ",
expr->bitmap_index, hash_val[i]);
! print_rtl (file, expr->expr);
fprintf (file, "\n");
}
--- 362,370 ----
expr = flat_table[i];
fprintf (file, "Index %d (hash value %d)\n ",
expr->bitmap_index, hash_val[i]);
! print_rtl (file, expr->dest);
! fprintf (file, " := ");
! print_rtl (file, expr->src);
fprintf (file, "\n");
}
*************** lookup_set (unsigned int regno, struct h
*** 497,503 ****
expr = table->table[hash];
! while (expr && REGNO (SET_DEST (expr->expr)) != regno)
expr = expr->next_same_hash;
return expr;
--- 493,499 ----
expr = table->table[hash];
! while (expr && REGNO (expr->dest) != regno)
expr = expr->next_same_hash;
return expr;
*************** next_set (unsigned int regno, struct exp
*** 510,516 ****
{
do
expr = expr->next_same_hash;
! while (expr && REGNO (SET_DEST (expr->expr)) != regno);
return expr;
}
--- 506,512 ----
{
do
expr = expr->next_same_hash;
! while (expr && REGNO (expr->dest) != regno);
return expr;
}
*************** free_cprop_mem (void)
*** 583,658 ****
sbitmap_vector_free (cprop_avout);
}
- /* For each block, compute whether X is transparent. X is either an
- expression or an assignment [though we don't care which, for this context
- an assignment is treated as an expression]. For each block where an
- element of X is modified, set the INDX bit in BMAP. */
-
- static void
- compute_transp (const_rtx x, int indx, sbitmap *bmap)
- {
- int i, j;
- enum rtx_code code;
- const char *fmt;
-
- /* repeat is used to turn tail-recursion into iteration since GCC
- can't do it when there's no return value. */
- repeat:
-
- if (x == 0)
- return;
-
- code = GET_CODE (x);
- switch (code)
- {
- case REG:
- {
- df_ref def;
- for (def = DF_REG_DEF_CHAIN (REGNO (x));
- def;
- def = DF_REF_NEXT_REG (def))
- SET_BIT (bmap[DF_REF_BB (def)->index], indx);
- }
- return;
-
- case PC:
- case CC0: /*FIXME*/
- case CONST:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST_FIXED:
- case CONST_VECTOR:
- case SYMBOL_REF:
- case LABEL_REF:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- return;
-
- default:
- break;
- }
-
- for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0;
i--)
- {
- if (fmt[i] == 'e')
- {
- /* If we are about to do the last recursive call
- needed at this level, change it into iteration.
- This function is called enough to be worth it. */
- if (i == 0)
- {
- x = XEXP (x, i);
- goto repeat;
- }
-
- compute_transp (XEXP (x, i), indx, bmap);
- }
- else if (fmt[i] == 'E')
- for (j = 0; j < XVECLEN (x, i); j++)
- compute_transp (XVECEXP (x, i, j), indx, bmap);
- }
- }
-
/* Compute the local properties of each recorded expression.
Local properties are those that are defined by the block, irrespective of
--- 579,584 ----
*************** compute_transp (const_rtx x, int indx, s
*** 665,675 ****
at least once and expression would contain the same value if the
computation was moved to the end of the block.
! TRANSP and COMP are destination sbitmaps for recording local properties.
! If NULL, then it is not necessary to compute or record that particular
! property.
!
! TRANSP is computed as ~TRANSP, since this is really cprop's ABSALTERED. */
static void
compute_local_properties (sbitmap *transp, sbitmap *comp,
--- 591,597 ----
at least once and expression would contain the same value if the
computation was moved to the end of the block.
! TRANSP and COMP are destination sbitmaps for recording local properties.
*/
static void
compute_local_properties (sbitmap *transp, sbitmap *comp,
*************** compute_local_properties (sbitmap *trans
*** 677,690 ****
{
unsigned int i;
! /* Initialize any bitmaps that were passed in. */
! if (transp)
! {
! sbitmap_vector_zero (transp, last_basic_block);
! }
!
! if (comp)
! sbitmap_vector_zero (comp, last_basic_block);
for (i = 0; i < table->size; i++)
{
--- 599,607 ----
{
unsigned int i;
! /* Initialize the bitmaps that were passed in. */
! sbitmap_vector_zero (transp, last_basic_block);
! sbitmap_vector_zero (comp, last_basic_block);
for (i = 0; i < table->size; i++)
{
*************** compute_local_properties (sbitmap *trans
*** 693,713 ****
for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
{
int indx = expr->bitmap_index;
struct occr *occr;
! /* The expression is transparent in this block if it is not killed.
! We start by assuming all are transparent [none are killed], and
! then reset the bits for those that are. */
! if (transp)
! compute_transp (expr->expr, indx, transp);
/* The occurrences recorded in avail_occr are exactly those that
we want to set to nonzero in COMP. */
! if (comp)
! for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
! {
! SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
! }
}
}
}
--- 610,636 ----
for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
{
int indx = expr->bitmap_index;
+ df_ref def;
struct occr *occr;
! /* The expression is transparent in a block if it is not killed,
! i.e. DEST and SRC are not set or clobbered in the block.
! We start by assuming all are transparent [none are killed],
! and then set the bits for those that are. */
! for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
! def; def = DF_REF_NEXT_REG (def))
! SET_BIT (transp[DF_REF_BB (def)->index], indx);
! if (REG_P (expr->src))
! for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
! def; def = DF_REF_NEXT_REG (def))
! SET_BIT (transp[DF_REF_BB (def)->index], indx);
/* The occurrences recorded in avail_occr are exactly those that
we want to set to nonzero in COMP. */
! for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
! {
! SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
! }
}
}
}
*************** find_avail_set (int regno, rtx insn)
*** 892,900 ****
if (set == 0)
break;
! gcc_assert (GET_CODE (set->expr) == SET);
!
! src = SET_SRC (set->expr);
/* We know the set is available.
Now check that SRC is locally anticipatable (i.e. none of the
--- 815,821 ----
if (set == 0)
break;
! src = set->src;
/* We know the set is available.
Now check that SRC is locally anticipatable (i.e. none of the
*************** cprop_insn (rtx insn)
*** 1080,1094 ****
int changed = 0;
rtx note;
- if (!INSN_P (insn))
- return 0;
-
reg_use_count = 0;
note_uses (&PATTERN (insn), find_used_regs, NULL);
- note = find_reg_equal_equiv_note (insn);
-
/* We may win even when propagating constants into notes. */
if (note)
find_used_regs (&XEXP (note, 0), NULL);
--- 1001,1011 ----
int changed = 0;
rtx note;
reg_use_count = 0;
note_uses (&PATTERN (insn), find_used_regs, NULL);
/* We may win even when propagating constants into notes. */
+ note = find_reg_equal_equiv_note (insn);
if (note)
find_used_regs (&XEXP (note, 0), NULL);
*************** cprop_insn (rtx insn)
*** 1096,1102 ****
reg_used++, reg_use_count--)
{
unsigned int regno = REGNO (reg_used->reg_rtx);
! rtx pat, src;
struct expr *set;
/* If the register has already been set in this block, there's
--- 1013,1019 ----
reg_used++, reg_use_count--)
{
unsigned int regno = REGNO (reg_used->reg_rtx);
! rtx src;
struct expr *set;
/* If the register has already been set in this block, there's
*************** cprop_insn (rtx insn)
*** 1110,1120 ****
if (! set)
continue;
! pat = set->expr;
! /* ??? We might be able to handle PARALLELs. Later. */
! gcc_assert (GET_CODE (pat) == SET);
!
! src = SET_SRC (pat);
/* Constant propagation. */
if (cprop_constant_p (src))
--- 1027,1033 ----
if (! set)
continue;
! src = set->src;
/* Constant propagation. */
if (cprop_constant_p (src))
*************** cprop_insn (rtx insn)
*** 1150,1156 ****
}
/* The original insn setting reg_used may or may not now be
! deletable. We leave the deletion to flow. */
/* FIXME: If it turns out that the insn isn't deletable,
then we may have unnecessarily extended register lifetimes
and made things worse. */
--- 1063,1069 ----
}
/* The original insn setting reg_used may or may not now be
! deletable. We leave the deletion to DCE. */
/* FIXME: If it turns out that the insn isn't deletable,
then we may have unnecessarily extended register lifetimes
and made things worse. */
*************** find_bypass_set (int regno, int bb)
*** 1502,1510 ****
if (set == 0)
break;
! gcc_assert (GET_CODE (set->expr) == SET);
!
! src = SET_SRC (set->expr);
if (cprop_constant_p (src))
result = set;
--- 1415,1421 ----
if (set == 0)
break;
! src = set->src;
if (cprop_constant_p (src))
result = set;
*************** bypass_block (basic_block bb, rtx setcc,
*** 1625,1631 ****
SET_SRC (PATTERN (setcc)));
new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
! SET_SRC (set->expr));
/* Jump bypassing may have already placed instructions on
edges of the CFG. We can't bypass an outgoing edge that
--- 1536,1542 ----
SET_SRC (PATTERN (setcc)));
new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
! set->src);
/* Jump bypassing may have already placed instructions on
edges of the CFG. We can't bypass an outgoing edge that
*************** bypass_block (basic_block bb, rtx setcc,
*** 1677,1683 ****
fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
"in jump_insn %d equals constant ",
regno, INSN_UID (jump));
! print_rtl (dump_file, SET_SRC (set->expr));
fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",
e->src->index, old_dest->index, dest->index);
}
--- 1588,1594 ----
fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
"in jump_insn %d equals constant ",
regno, INSN_UID (jump));
! print_rtl (dump_file, set->src);
fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",
e->src->index, old_dest->index, dest->index);
}
