Jean Christophe Beyler wrote:
> Ok, thanks for all this information and if you can dig that up it
> would be nice too. I'll start looking at that patch and PR33699 to
> see if I can adapt them to my needs.
Here it is.
Paolo
/* Copy propagation on RTL for GNU compiler.
Copyright (C) 2006 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "obstack.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
#include "alloc-pool.h"
#include "timevar.h"
#include "tree-pass.h"
/* The basic idea is to keep a table of registers with the same
value, and replace expressions encountered so that they use the
equivalent register. We do this processing on extended basic
blocks.
Note this can turn a conditional or computed jump into a nop or
an unconditional jump. This is left to be cleaned up by CSE,
for now.
At the start of each basic block, an assignment places a register
in a distinct group number. During scan, when the code copies
one register (or a related expression, see below) into another, we
copy the quantity number. When a register is loaded in any other
way, we allocate a new quantity number to describe the value
generated by this operation. `reg_group[regno].num' records what
quantity register REGNO is currently thought of as containing.
Other expressions:
A CLOBBER rtx in an instruction invalidates its operand for further
reuse.
Related expressions:
Registers that differ only by an additive integer are called related.
Related registers share the same quantity number. */
/* Per-group information tracking. */
struct group_table_elem
{
rtx reg;
HOST_WIDE_INT delta;
/* Basic block in which it was defined. */
basic_block bb;
struct group_table_elem *prev, *next;
};
/* Per-register data, including register->group mapping. */
struct reg_data
{
/* Current group. */
struct group_table_elem *entry;
/* Pointer into the table of group heads, indexed by register number.
Always 0 for unknown values. */
int num;
};
/* Length of group_head vector. */
static int max_group;
/* Next quantity number to be allocated.
This is 1 + the largest number needed so far. */
static int next_group;
/* The table of all groups, indexed by group number. */
static struct group_table_elem **group_head;
/* The table of all pseudos, indexed by regno. */
static struct reg_data *reg_group;
/* Allocation pool. */
static alloc_pool group_elem_pool;
/* Basic block being processed. */
static basic_block current_bb;
/* We store the state of each basic block (not visited, part of current EBB,
finished) in its AUX field. These two functions return the state. */
static inline bool
bb_visited (basic_block bb)
{
return bb->aux != 0;
}
static inline bool
bb_active (basic_block bb)
{
return bb->aux == (void *) 1L;
}
/* Routines to manage the data structures of this pass. */
/* Remove the register DEST from the equivalence tables. */
static struct group_table_elem *
remove_from_group (rtx dest)
{
struct group_table_elem *ent = reg_group[REGNO (dest)].entry;
int num = reg_group[REGNO (dest)].num;
reg_group[REGNO (dest)].num = 0;
reg_group[REGNO (dest)].entry = NULL;
gcc_assert (ent);
if (ent->prev)
ent->prev->next = ent->next;
else
group_head[num] = ent->next;
if (ent->next)
ent->next->prev = ent->prev;
ent->prev = ent->next = NULL;
return ent;
}
/* Check if the entry for register REG in the equivalence tables is up to date.
Remove it and return NULL if it is not. Otherwise, return the entry, or NULL
if it is absent. */
static inline struct group_table_elem *
reg_group_entry (rtx reg)
{
struct group_table_elem *ent = reg_group[REGNO (reg)].entry;
if (ent && !bb_active (ent->bb))
{
remove_from_group (reg);
return NULL;
}
else
return ent;
}
/* Return the head of the equivalence class for REG (removing stale entries).
*/
static struct group_table_elem *
reg_group_head (rtx reg)
{
int num = reg_group[REGNO (reg)].num;
struct group_table_elem *canon_ent = group_head[num];
while (canon_ent && !bb_active (canon_ent->bb))
{
remove_from_group (canon_ent->reg);
canon_ent = group_head[num];
}
return canon_ent;
}
/* Put DEST into a separate equivalence class. */
static void
make_group_head (rtx dest)
{
struct group_table_elem *new_group;
if (reg_group[REGNO (dest)].entry)
new_group = remove_from_group (dest);
else
new_group = (struct group_table_elem *) pool_alloc (group_elem_pool);
new_group->reg = dest;
new_group->delta = 0;
new_group->bb = current_bb;
new_group->prev = new_group->next = NULL;
if (next_group == max_group)
{
max_group *= 2;
group_head = xrealloc (group_head,
max_group * sizeof (struct group_table_elem *));
}
group_head[next_group] = new_group;
}
/* Put DEST into the same equivalence class as SRC, remembering that the two
values
differ by DELTA. */
static void
merge_group (rtx dest, rtx src, HOST_WIDE_INT delta)
{
struct group_table_elem *canon_ent = reg_group_head (src);
struct group_table_elem *new_group;
if (!canon_ent)
make_group_head (dest);
else
{
if (reg_group[REGNO (dest)].entry)
new_group = remove_from_group (dest);
else
new_group = (struct group_table_elem *) pool_alloc (group_elem_pool);
new_group = remove_from_group (dest);
new_group->reg = dest;
new_group->delta = delta;
new_group->bb = current_bb;
new_group->prev = canon_ent;
new_group->next = canon_ent->next;
canon_ent->next->prev = new_group;
canon_ent->next = new_group;
}
}
/* Return whether this pass will operate on DEST. Never replace a hard reg,
because
hard regs can appear in more than one machine mode, and we must preserve the
mode
of each occurrence. Also, some hard regs appear in MEMs that are shared and
mustn't be altered. */
static inline bool
replaceable_reg_p (rtx x)
{
return REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER;
}
/* Return whether PAT sets at most one pseudo. We don't want to mess with
instructions that exchange pseudos and so on; on the other hand, single_set
is not enough because we want to work on instructions that do some arithmetic
and set a condition code register, for example. */
static bool
single_non_hard_reg_set (rtx pat)
{
int i;
int n = 0;
if (GET_CODE (pat) == SET)
return true;
if (GET_CODE (pat) != PARALLEL)
return false;
for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
{
rtx pat2 = XVECEXP (pat, 0, i);
if (GET_CODE (pat2) == SET
&& (!REG_P (SET_DEST (pat2))
|| REGNO (SET_DEST (pat2)) < FIRST_PSEUDO_REGISTER))
n++;
if (n == 2)
return false;
}
return true;
}
/* Callback for note_stores, discarding the values corresponding to the stores.
*/
static void
canon_reg_discard (rtx dest, rtx pat ATTRIBUTE_UNUSED, void *ent
ATTRIBUTE_UNUSED)
{
if (replaceable_reg_p (dest))
make_group_head (dest);
}
/* Callback for note_stores, forming new equivalence classes for the stores. */
static void
canon_reg_update (rtx dest, rtx pat, void *ent ATTRIBUTE_UNUSED)
{
if (!replaceable_reg_p (dest))
return;
if (GET_CODE (pat) == SET && dest == SET_DEST (pat))
{
if (replaceable_reg_p (SET_SRC (pat)))
{
merge_group (SET_DEST (pat), SET_SRC (pat), 0);
return;
}
if (GET_CODE (SET_SRC (pat)) == PLUS
&& replaceable_reg_p (XEXP (SET_SRC (pat), 0))
&& GET_CODE (XEXP (SET_SRC (pat), 1)) == CONST_INT)
{
merge_group (SET_DEST (pat), XEXP (SET_SRC (pat), 0),
INTVAL (XEXP (SET_SRC (pat), 1)));
return;
}
}
else
make_group_head (dest);
}
/* Replace the value at XLOC with the canonical value of REG plus DELTA. */
static void
canon_reg_1 (rtx *xloc, rtx reg, HOST_WIDE_INT delta, rtx insn)
{
struct group_table_elem *ent;
struct group_table_elem *canon_ent;
ent = reg_group_entry (reg);
canon_ent = reg_group_head (reg);
if (ent && ent != canon_ent)
{
rtx repl = plus_constant (ent->reg, delta + ent->delta -
canon_ent->delta);
if (insn)
validate_change (insn, xloc, repl, 1);
else
*xloc = repl;
}
}
/* Callback for for_each_rtx, which looks for PLUS and REG rtx-en and passes
them to canon_reg_1. */
static int
canon_reg (rtx *xloc, void *data)
{
rtx x = *xloc;
rtx insn = data;
if (x)
{
if (REG_P (x) && (!insn || !reg_set_p (x, insn)))
canon_reg_1 (xloc, x, 0, insn);
else if (GET_CODE (x) == PLUS
&& REG_P (XEXP (x, 0))
&& GET_CODE (XEXP (x, 1)) == CONST_INT)
canon_reg_1 (xloc, XEXP (x, 0), INTVAL (XEXP (x, 1)), insn);
}
return 0;
}
/* Process the extended basic block headed at BB. */
static void
canon_reg_ebb (basic_block bb)
{
rtx insn;
edge_iterator ei;
edge e;
bb->aux = (void *) 1L;
current_bb = bb;
FOR_BB_INSNS (bb, insn)
{
if (!INSN_P (insn))
continue;
for_each_rtx (&PATTERN (insn), canon_reg, insn);
if (apply_change_group ())
for_each_rtx (®_NOTES (insn), canon_reg, NULL);
if (single_non_hard_reg_set (PATTERN (insn)))
note_stores (PATTERN (insn), canon_reg_update, NULL);
else
note_stores (PATTERN (insn), canon_reg_discard, NULL);
}
/* Walk extended basic blocks. */
FOR_EACH_EDGE (e, ei, bb->succs)
if (single_pred_p (e->dest))
canon_reg_ebb (e->dest);
bb->aux = (void *) 2L;
}
static bool
gate_handle_canon_reg (void)
{
return optimize > 0;
}
static unsigned int
rest_of_handle_canon_reg (void)
{
basic_block bb;
group_elem_pool = create_alloc_pool ("canon-reg groups",
sizeof (struct group_table_elem), 40);
max_group = max_reg_num () / 2;
group_head = xcalloc (sizeof (struct group_table_elem *), max_group);
reg_group = xcalloc (sizeof (struct reg_data), max_reg_num ());
next_group = 1;
if (dump_file)
dump_flow_info (dump_file, dump_flags);
FOR_ALL_BB (bb)
if (!bb_visited (bb))
canon_reg_ebb (bb);
free_alloc_pool (group_elem_pool);
free (group_head);
free (reg_group);
FOR_ALL_BB (bb)
bb->aux = NULL;
delete_trivially_dead_insns (get_insns (), max_reg_num ());
return 0;
}
struct tree_opt_pass pass_canon_reg =
{
"canonreg", /* name */
gate_handle_canon_reg, /* gate */
rest_of_handle_canon_reg, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
TV_CANON_REG, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_func, /* todo_flags_finish */
0 /* letter */
};
