This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Change compute_available to use iterative dataflow framework
- From: Daniel Berlin <dan at cgsoftware dot com>
- To: <gcc-patches at gcc dot gnu dot org>
- Date: Sat, 15 Dec 2001 16:22:04 -0500 (EST)
- Subject: [PATCH]: Change compute_available to use iterative dataflow framework
The new compute_available actually takes, on average, 1/4 the iterations
the old one did.
The patch would be a lot smaller if including df.h didn't force us to
rename struct bb_info.
2001-12-15 Daniel Berlin <dan@cgsoftware.com>
* lcm.c: Include df.h.
Add available_transfer_function prototype.
(compute_available): Rework to use iterative dataflow framework.
(struct bb_info): s/bb_info/lcm_bb_info/g to avoid conflict
with bb_info in df.h
(available_transfer_function): New function.
* Makefile.in (lcm.o): add df.h to dependencies.
Index: lcm.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/lcm.c,v
retrieving revision 1.32
diff -c -3 -p -w -B -b -r1.32 lcm.c
*** lcm.c 2001/11/11 11:25:26 1.32
--- lcm.c 2001/12/15 21:13:17
*************** Software Foundation, 59 Temple Place - S
*** 60,65 ****
--- 60,66 ----
#include "recog.h"
#include "basic-block.h"
#include "tm_p.h"
+ #include "df.h"
/* We want target macros for the mode switching code to be able to refer
to instruction attribute values. */
*************** static void compute_rev_insert_delete PA
*** 93,100 ****
sbitmap *, sbitmap *,
sbitmap *));
! /* Edge based lcm routines. */
/* Compute expression anticipatability at entrance and exit of each block.
This is done based on the flow graph, and not on the pred-succ lists.
Other than that, its pretty much identical to compute_antinout. */
--- 94,103 ----
sbitmap *, sbitmap *,
sbitmap *));
! static void available_transfer_function PARAMS ((int, int *, sbitmap, sbitmap,
! sbitmap, sbitmap, void *));
+ /* Edge based lcm routines. */
/* Compute expression anticipatability at entrance and exit of each block.
This is done based on the flow graph, and not on the pred-succ lists.
Other than that, its pretty much identical to compute_antinout. */
*************** pre_edge_lcm (file, n_exprs, transp, avl
*** 487,576 ****
return edge_list;
}
!
! /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
! Return the number of passes we performed to iterate to a solution. */
!
! void
! compute_available (avloc, kill, avout, avin)
! sbitmap *avloc, *kill, *avout, *avin;
! {
! int bb;
! edge e;
! basic_block *worklist, *qin, *qout, *qend;
! unsigned 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. */
! qin = qout = worklist
! = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
!
! /* We want a maximal solution. */
! sbitmap_vector_ones (avout, n_basic_blocks);
!
! /* Put every block on the worklist; this is necessary because of the
! optimistic initialization of AVOUT above. */
! for (bb = 0; bb < n_basic_blocks; bb++)
{
! *qin++ = BASIC_BLOCK (bb);
! BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
!
! qin = worklist;
! qend = &worklist[n_basic_blocks];
! qlen = n_basic_blocks;
!
! /* Mark blocks which are successors of the entry block so that we
! can easily identify them below. */
! for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
! e->dest->aux = ENTRY_BLOCK_PTR;
!
! /* Iterate until the worklist is empty. */
! while (qlen)
{
! /* Take the first entry off the worklist. */
! basic_block b = *qout++;
! bb = b->index;
! qlen--;
!
! if (qout >= qend)
! qout = worklist;
!
! /* If one of the predecessor blocks is the ENTRY block, then the
! intersection of avouts is the null set. We can identify such blocks
! by the special value in the AUX field in the block structure. */
! if (b->aux == ENTRY_BLOCK_PTR)
! /* Do not clear the aux field for blocks which are successors of the
! ENTRY block. That way we never add then to the worklist again. */
! sbitmap_zero (avin[bb]);
! else
{
! /* Clear the aux field of this block so that it can be added to
! the worklist again if necessary. */
! b->aux = NULL;
! sbitmap_intersection_of_preds (avin[bb], avout, bb);
}
!
! if (sbitmap_union_of_diff (avout[bb], avloc[bb], avin[bb], kill[bb]))
! /* If the out state of this block changed, then we need
! to add the successors of this block to the worklist
! if they are not already on the worklist. */
! for (e = b->succ; e; e = e->succ_next)
! if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
! {
! *qin++ = e->dest;
! e->dest->aux = e;
! qlen++;
!
! if (qin >= qend)
! qin = worklist;
! }
! }
!
! clear_aux_for_edges ();
! clear_aux_for_blocks ();
! free (worklist);
}
/* Compute the farthest vector for edge based lcm. */
--- 488,535 ----
return edge_list;
}
! /* Availability transfer function */
! static void
! available_transfer_function (bb, changed, in, out, gen, kill, data)
! int bb ATTRIBUTE_UNUSED;
! int *changed;
! sbitmap in,out,gen,kill;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = sbitmap_union_of_diff (out, gen, in, kill);
}
! /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL
! vectors. */
! void
! compute_available (avloc, kill, avout, avin)
! sbitmap *avloc;
! sbitmap *kill;
! sbitmap *avout;
! sbitmap *avin;
{
! int *dfs_order;
! int *rc_order;
! bitmap blocks;
! int *inverse_rc_map;
! int i;
! dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
! rc_order = xmalloc (sizeof (int) * n_basic_blocks);
! inverse_rc_map = xmalloc (sizeof (int) * n_basic_blocks);
! flow_depth_first_order_compute (dfs_order, rc_order);
! blocks = BITMAP_XMALLOC ();
! for (i = 0; i < n_basic_blocks; i ++)
{
! inverse_rc_map[rc_order[i]] = i;
! bitmap_set_bit (blocks, i);
}
! sbitmap_vector_ones (avout, n_basic_blocks);
! iterative_dataflow_sbitmap (avin, avout, avloc, kill, blocks,
! FORWARD, INTERSECTION,
! available_transfer_function, inverse_rc_map, 0);
! BITMAP_XFREE (blocks);
! free (dfs_order);
! free (rc_order);
! free (inverse_rc_map);
}
/* Compute the farthest vector for edge based lcm. */
*************** struct seginfo
*** 876,882 ****
HARD_REG_SET regs_live;
};
! struct bb_info
{
struct seginfo *seginfo;
int computing;
--- 835,841 ----
HARD_REG_SET regs_live;
};
! struct lcm_bb_info
{
struct seginfo *seginfo;
int computing;
*************** static sbitmap *delete;
*** 892,898 ****
static sbitmap *insert;
static struct seginfo * new_seginfo PARAMS ((int, rtx, int, HARD_REG_SET));
! static void add_seginfo PARAMS ((struct bb_info *, struct seginfo *));
static void reg_dies PARAMS ((rtx, HARD_REG_SET));
static void reg_becomes_live PARAMS ((rtx, rtx, void *));
static void make_preds_opaque PARAMS ((basic_block, int));
--- 851,857 ----
static sbitmap *insert;
static struct seginfo * new_seginfo PARAMS ((int, rtx, int, HARD_REG_SET));
! static void add_seginfo PARAMS ((struct lcm_bb_info *, struct seginfo *));
static void reg_dies PARAMS ((rtx, HARD_REG_SET));
static void reg_becomes_live PARAMS ((rtx, rtx, void *));
static void make_preds_opaque PARAMS ((basic_block, int));
*************** new_seginfo (mode, insn, bb, regs_live)
*** 926,932 ****
static void
add_seginfo (head, info)
! struct bb_info *head;
struct seginfo *info;
{
struct seginfo *ptr;
--- 885,891 ----
static void
add_seginfo (head, info)
! struct lcm_bb_info *head;
struct seginfo *info;
{
struct seginfo *ptr;
*************** optimize_mode_switching (file)
*** 1025,1031 ****
static const int num_modes[] = NUM_MODES_FOR_MODE_SWITCHING;
#define N_ENTITIES (sizeof num_modes / sizeof (int))
int entity_map[N_ENTITIES];
! struct bb_info *bb_info[N_ENTITIES];
int i, j;
int n_entities;
int max_num_modes = 0;
--- 984,990 ----
static const int num_modes[] = NUM_MODES_FOR_MODE_SWITCHING;
#define N_ENTITIES (sizeof num_modes / sizeof (int))
int entity_map[N_ENTITIES];
! struct lcm_bb_info *bb_info[N_ENTITIES];
int i, j;
int n_entities;
int max_num_modes = 0;
*************** optimize_mode_switching (file)
*** 1041,1047 ****
{
/* Create the list of segments within each basic block. */
bb_info[n_entities]
! = (struct bb_info *) xcalloc (n_basic_blocks, sizeof **bb_info);
entity_map[n_entities++] = e;
if (num_modes[e] > max_num_modes)
max_num_modes = num_modes[e];
--- 1000,1006 ----
{
/* Create the list of segments within each basic block. */
bb_info[n_entities]
! = (struct lcm_bb_info *) xcalloc (n_basic_blocks, sizeof **bb_info);
entity_map[n_entities++] = e;
if (num_modes[e] > max_num_modes)
max_num_modes = num_modes[e];
*************** optimize_mode_switching (file)
*** 1080,1086 ****
{
int e = entity_map[j];
int no_mode = num_modes[e];
! struct bb_info *info = bb_info[j];
/* Determine what the first use (if any) need for a mode of entity E is.
This will be the mode that is anticipatable for this block.
--- 1039,1045 ----
{
int e = entity_map[j];
int no_mode = num_modes[e];
! struct lcm_bb_info *info = bb_info[j];
/* Determine what the first use (if any) need for a mode of entity E is.
This will be the mode that is anticipatable for this block.
*************** optimize_mode_switching (file)
*** 1182,1188 ****
for (j = n_entities - 1; j >= 0; j--)
{
int m = current_mode[j] = MODE_PRIORITY_TO_MODE (entity_map[j], i);
! struct bb_info *info = bb_info[j];
for (bb = 0 ; bb < n_basic_blocks; bb++)
{
--- 1141,1147 ----
for (j = n_entities - 1; j >= 0; j--)
{
int m = current_mode[j] = MODE_PRIORITY_TO_MODE (entity_map[j], i);
! struct lcm_bb_info *info = bb_info[j];
for (bb = 0 ; bb < n_basic_blocks; bb++)
{
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.806
diff -c -3 -p -w -B -b -r1.806 Makefile.in
*** Makefile.in 2001/12/13 11:34:04 1.806
--- Makefile.in 2001/12/15 21:19:22
*************** resource.o : resource.c $(CONFIG_H) $(RT
*** 1427,1433 ****
$(INSN_ATTR_H) except.h $(PARAMS_H) $(TM_P_H)
lcm.o : lcm.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \
real.h insn-config.h $(INSN_ATTR_H) $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) \
! $(TM_P_H)
ssa.o : ssa.c $(CONFIG_H) $(SYSTEM_H) $(REGS_H) varray.h $(EXPR_H) \
hard-reg-set.h flags.h function.h real.h insn-config.h $(RECOG_H) \
$(BASIC_BLOCK_H) output.h ssa.h
--- 1430,1436 ----
$(INSN_ATTR_H) except.h $(PARAMS_H) $(TM_P_H)
lcm.o : lcm.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \
real.h insn-config.h $(INSN_ATTR_H) $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) \
! $(TM_P_H) df.h
ssa.o : ssa.c $(CONFIG_H) $(SYSTEM_H) $(REGS_H) varray.h $(EXPR_H) \
hard-reg-set.h flags.h function.h real.h insn-config.h $(RECOG_H) \
$(BASIC_BLOCK_H) output.h ssa.h