This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Use df.c in rtl level invariant motion
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 9 Mar 2004 19:33:16 +0100
- Subject: [lno] Use df.c in rtl level invariant motion
Hello,
this patch makes the rtl level invariant motion to use df.c functions.
To solve efficiency problems, it also speeds up dataflow solver a bit,
by avoiding use of fibheaps (the way they were used was absolutely
nonsensical; it would not be hard to add them back in more senseful
way, but I am not quite sure whether they would pay up in practice) and
unnecessary propagations. It also enables the analysis to be used only
on a subgraph of cfg (in our case just the loop bodies), which also
helps.
Zdenek
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.78
diff -c -3 -p -r1.1.2.78 ChangeLog.lno
*** ChangeLog.lno 9 Mar 2004 17:45:33 -0000 1.1.2.78
--- ChangeLog.lno 9 Mar 2004 18:19:45 -0000
***************
*** 1,3 ****
--- 1,52 ----
+ 2004-03-09 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+
+ * Makefile.in (df.o): Remove FIBHEAP_H dependency.
+ (invariant.o): Add df.h dependency.
+ * df.c: Do not include fibheap.h.
+ (df_bb_table_realloc, df_analyse_subcfg, free_reg_ref_chain,
+ prune_to_subcfg, df_bb_modify, df_find_def, dataflow_set_a_op_b,
+ dataflow_set_copy): New functions.
+ (df_bitmaps_alloc, df_reg_def_chain_create, df_reg_use_chain_create,
+ df_refs_update, df_reg_table_realloc, df_ref_create,
+ df_bb_reg_def_chain_create, df_bb_reg_use_chain_create,
+ df_bb_rd_local_compute, df_bb_ru_local_compute, df_bb_lr_local_compute,
+ df_analyse_1, df_insn_modify): Support analysing only a part of the cfg.
+ (df_rd_transfer_function, df_ru_transfer_function,
+ df_lr_transfer_function): Type of bitmaps changed to void *.
+ (hybrid_search_bitmap, hybrid_search_sbitmap): Merge into ...
+ (hybrid_search): ... new function.
+ (iterative_dataflow_bitmap, iterative_dataflow_sbitmap): Merge into ...
+ (iterative_dataflow): ... new function. Avoid use of fibheaps for
+ a worklist. Do not process basic blocks unnecessarily.
+ * df.h (struct ref): Add data field.
+ (DF_REF_DATA): New macro.
+ (df_analyse_subcfg, df_find_def): Declare.
+ (transfer_function_sbitmap, transfer_function_bitmap): Replaced by ...
+ (transfer_function): ... declare.
+ (iterative_dataflow_sbitmap, iterative_dataflow_bitmap): Replaced by ...
+ (iterative_dataflow): ... declare.
+ (enum set_representation, struct dataflow): New.
+ * loop-invariant.c: Include df.h.
+ (struct loop_data): Remove modified_regs field.
+ (struct def): Remove redundant fields.
+ (struct use): Add insn field.
+ (defs, adef, last_def, m_reg_info, reg_info): Removed.
+ (struct reg): Removed.
+ (record_def, note_insn_stores, find_defs_insn, find_defs_bb,
+ get_current_def, record_dependencies_fer, record_dependencies,
+ move_actual_defs): Removed.
+ (find_defs, find_invariants_insn, create_new_invariant,
+ find_invariants_bb, find_invariants_body, find_invariants,
+ find_invariants_to_move, move_invariant_reg,
+ move_invariants, move_single_loop_invariants,
+ move_loop_invariants): Use df.c.
+ (init_inv_motion_data): Do not initialize removed structures.
+ (free_inv_motion_data, free_loop_data): Do not cleanup removed
+ structures.
+ (check_dependencies, find_invariant_insn, record_uses): New.
+ (record_use): Record the insn.
+ (get_inv_cost): Update comments.
+
2004-03-09 Andreas Jaeger <aj@suse.de>
* common.opt: Put tree-loop-linear at right place.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.17
diff -c -3 -p -r1.903.2.158.2.17 Makefile.in
*** Makefile.in 9 Mar 2004 16:23:13 -0000 1.903.2.158.2.17
--- Makefile.in 9 Mar 2004 18:19:46 -0000
*************** tree-complex.o : tree-complex.c $(CONFIG
*** 1875,1881 ****
flags.h
df.o : df.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
insn-config.h $(RECOG_H) function.h $(REGS_H) alloc-pool.h hard-reg-set.h \
! $(BASIC_BLOCK_H) df.h $(FIBHEAP_H)
var-tracking.o : var-tracking.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(TREE_H) hard-reg-set.h insn-config.h reload.h flags.h \
$(BASIC_BLOCK_H) output.h sbitmap.h alloc-pool.h $(FIBHEAP_H) $(HASHTAB_H)
--- 1875,1881 ----
flags.h
df.o : df.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
insn-config.h $(RECOG_H) function.h $(REGS_H) alloc-pool.h hard-reg-set.h \
! $(BASIC_BLOCK_H) df.h
var-tracking.o : var-tracking.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(TREE_H) hard-reg-set.h insn-config.h reload.h flags.h \
$(BASIC_BLOCK_H) output.h sbitmap.h alloc-pool.h $(FIBHEAP_H) $(HASHTAB_H)
*************** cfgloopanal.o : cfgloopanal.c $(CONFIG_H
*** 1935,1941 ****
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H)
loop-invariant.o : loop-invariant.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H) \
! function.h flags.h
loop-iv.o : loop-iv.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H)
cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
--- 1935,1941 ----
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H)
loop-invariant.o : loop-invariant.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H) \
! function.h flags.h df.h
loop-iv.o : loop-iv.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H)
cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
Index: df.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/df.c,v
retrieving revision 1.32.2.12.4.2
diff -c -3 -p -r1.32.2.12.4.2 df.c
*** df.c 21 Feb 2004 23:09:41 -0000 1.32.2.12.4.2
--- df.c 9 Mar 2004 18:19:46 -0000
*************** and again mark them read/write.
*** 187,193 ****
#include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
- #include "fibheap.h"
#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
do \
--- 187,192 ----
*************** static struct df *ddf;
*** 204,210 ****
static void df_reg_table_realloc (struct df *, int);
static void df_insn_table_realloc (struct df *, unsigned int);
! static void df_bitmaps_alloc (struct df *, int);
static void df_bitmaps_free (struct df *, int);
static void df_free (struct df *);
static void df_alloc (struct df *, int);
--- 203,210 ----
static void df_reg_table_realloc (struct df *, int);
static void df_insn_table_realloc (struct df *, unsigned int);
! static void df_bb_table_realloc (struct df *, unsigned int);
! static void df_bitmaps_alloc (struct df *, bitmap, int);
static void df_bitmaps_free (struct df *, int);
static void df_free (struct df *);
static void df_alloc (struct df *, int);
*************** static void df_bb_refs_record (struct df
*** 237,245 ****
static void df_refs_record (struct df *, bitmap);
static void df_bb_reg_def_chain_create (struct df *, basic_block);
! static void df_reg_def_chain_create (struct df *, bitmap);
static void df_bb_reg_use_chain_create (struct df *, basic_block);
! static void df_reg_use_chain_create (struct df *, bitmap);
static void df_bb_du_chain_create (struct df *, basic_block, bitmap);
static void df_du_chain_create (struct df *, bitmap);
static void df_bb_ud_chain_create (struct df *, basic_block);
--- 237,245 ----
static void df_refs_record (struct df *, bitmap);
static void df_bb_reg_def_chain_create (struct df *, basic_block);
! static void df_reg_def_chain_create (struct df *, bitmap, bool);
static void df_bb_reg_use_chain_create (struct df *, basic_block);
! static void df_reg_use_chain_create (struct df *, bitmap, bool);
static void df_bb_du_chain_create (struct df *, basic_block, bitmap);
static void df_du_chain_create (struct df *, bitmap);
static void df_bb_ud_chain_create (struct df *, basic_block);
*************** static int df_modified_p (struct df *, b
*** 260,266 ****
static int df_refs_queue (struct df *);
static int df_refs_process (struct df *);
static int df_bb_refs_update (struct df *, basic_block);
! static int df_refs_update (struct df *);
static void df_analyse_1 (struct df *, bitmap, int, int);
static void df_insns_modify (struct df *, basic_block, rtx, rtx);
--- 260,266 ----
static int df_refs_queue (struct df *);
static int df_refs_process (struct df *);
static int df_bb_refs_update (struct df *, basic_block);
! static int df_refs_update (struct df *, bitmap);
static void df_analyse_1 (struct df *, bitmap, int, int);
static void df_insns_modify (struct df *, basic_block, rtx, rtx);
*************** static void df_chain_dump (struct df_lin
*** 283,304 ****
static void df_chain_dump_regno (struct df_link *, FILE *file);
static void df_regno_debug (struct df *, unsigned int, FILE *);
static void df_ref_debug (struct df *, struct ref *, FILE *);
! static void df_rd_transfer_function (int, int *, bitmap, bitmap, bitmap,
! bitmap, void *);
! static void df_ru_transfer_function (int, int *, bitmap, bitmap, bitmap,
! bitmap, void *);
! static void df_lr_transfer_function (int, int *, bitmap, bitmap, bitmap,
! bitmap, void *);
! static void hybrid_search_bitmap (basic_block, bitmap *, bitmap *,
! bitmap *, bitmap *, enum df_flow_dir,
! enum df_confluence_op,
! transfer_function_bitmap,
! sbitmap, sbitmap, void *);
! static void hybrid_search_sbitmap (basic_block, sbitmap *, sbitmap *,
! sbitmap *, sbitmap *, enum df_flow_dir,
! enum df_confluence_op,
! transfer_function_sbitmap,
! sbitmap, sbitmap, void *);
/* Local memory allocation/deallocation routines. */
--- 283,296 ----
static void df_chain_dump_regno (struct df_link *, FILE *file);
static void df_regno_debug (struct df *, unsigned int, FILE *);
static void df_ref_debug (struct df *, struct ref *, FILE *);
! static void df_rd_transfer_function (int, int *, void *, void *, void *,
! void *, void *);
! static void df_ru_transfer_function (int, int *, void *, void *, void *,
! void *, void *);
! static void df_lr_transfer_function (int, int *, void *, void *, void *,
! void *, void *);
! static void hybrid_search (basic_block, struct dataflow *,
! sbitmap, sbitmap, sbitmap);
/* Local memory allocation/deallocation routines. */
*************** df_insn_table_realloc (struct df *df, un
*** 331,336 ****
--- 323,348 ----
}
}
+ /* Increase the bb info table to have space for at least SIZE + 1
+ elements. */
+
+ static void
+ df_bb_table_realloc (struct df *df, unsigned int size)
+ {
+ size++;
+ if (size <= df->n_bbs)
+ return;
+
+ /* Make the table a little larger than requested, so we do not need
+ to enlarge it so often. */
+ size += df->n_bbs / 4;
+
+ df->bbs = xrealloc (df->bbs, size * sizeof (struct bb_info));
+
+ memset (df->bbs + df->n_bbs, 0, (size - df->n_bbs) * sizeof (struct bb_info));
+
+ df->n_bbs = size;
+ }
/* Increase the reg info table by SIZE more elements. */
static void
*************** df_reg_table_realloc (struct df *df, int
*** 345,350 ****
--- 357,364 ----
size = max_reg_num ();
df->regs = xrealloc (df->regs, size * sizeof (struct reg_info));
+ df->reg_def_last = xrealloc (df->reg_def_last,
+ size * sizeof (struct ref *));
/* Zero the new entries. */
memset (df->regs + df->reg_size, 0,
*************** df_reg_table_realloc (struct df *df, int
*** 355,421 ****
/* Allocate bitmaps for each basic block. */
static void
! df_bitmaps_alloc (struct df *df, int flags)
{
- int dflags = 0;
basic_block bb;
- /* Free the bitmaps if they need resizing. */
- if ((flags & DF_LR) && df->n_regs < (unsigned int) max_reg_num ())
- dflags |= DF_LR | DF_RU;
- if ((flags & DF_RU) && df->n_uses < df->use_id)
- dflags |= DF_RU;
- if ((flags & DF_RD) && df->n_defs < df->def_id)
- dflags |= DF_RD;
-
- if (dflags)
- df_bitmaps_free (df, dflags);
-
df->n_defs = df->def_id;
df->n_uses = df->use_id;
! FOR_EACH_BB (bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
! if (flags & DF_RD && ! bb_info->rd_in)
{
! /* Allocate bitmaps for reaching definitions. */
! bb_info->rd_kill = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->rd_kill);
! bb_info->rd_gen = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->rd_gen);
! bb_info->rd_in = BITMAP_XMALLOC ();
! bb_info->rd_out = BITMAP_XMALLOC ();
! bb_info->rd_valid = 0;
! }
!
! if (flags & DF_RU && ! bb_info->ru_in)
! {
! /* Allocate bitmaps for upward exposed uses. */
! bb_info->ru_kill = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->ru_kill);
! /* Note the lack of symmetry. */
! bb_info->ru_gen = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->ru_gen);
! bb_info->ru_in = BITMAP_XMALLOC ();
! bb_info->ru_out = BITMAP_XMALLOC ();
! bb_info->ru_valid = 0;
! }
!
! if (flags & DF_LR && ! bb_info->lr_in)
! {
! /* Allocate bitmaps for live variables. */
! bb_info->lr_def = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->lr_def);
! bb_info->lr_use = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->lr_use);
! bb_info->lr_in = BITMAP_XMALLOC ();
! bb_info->lr_out = BITMAP_XMALLOC ();
! bb_info->lr_valid = 0;
}
! }
}
--- 369,447 ----
/* Allocate bitmaps for each basic block. */
+
static void
! df_bitmaps_alloc (struct df *df, bitmap blocks, int flags)
{
basic_block bb;
df->n_defs = df->def_id;
df->n_uses = df->use_id;
! if (!blocks)
! blocks = df->all_blocks;
!
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
! if (flags & DF_RD)
{
! if (!bb_info->rd_in)
! {
! /* Allocate bitmaps for reaching definitions. */
! bb_info->rd_kill = BITMAP_XMALLOC ();
! bb_info->rd_gen = BITMAP_XMALLOC ();
! bb_info->rd_in = BITMAP_XMALLOC ();
! bb_info->rd_out = BITMAP_XMALLOC ();
! }
! else
! {
! bitmap_clear (bb_info->rd_kill);
! bitmap_clear (bb_info->rd_gen);
! bitmap_clear (bb_info->rd_in);
! bitmap_clear (bb_info->rd_out);
! }
}
!
! if (flags & DF_RU)
! {
! if (!bb_info->ru_in)
! {
! /* Allocate bitmaps for upward exposed uses. */
! bb_info->ru_kill = BITMAP_XMALLOC ();
! bb_info->ru_gen = BITMAP_XMALLOC ();
! bb_info->ru_in = BITMAP_XMALLOC ();
! bb_info->ru_out = BITMAP_XMALLOC ();
! }
! else
! {
! bitmap_clear (bb_info->ru_kill);
! bitmap_clear (bb_info->ru_gen);
! bitmap_clear (bb_info->ru_in);
! bitmap_clear (bb_info->ru_out);
! }
! }
!
! if (flags & DF_LR)
! {
! if (!bb_info->lr_in)
! {
! /* Allocate bitmaps for live variables. */
! bb_info->lr_def = BITMAP_XMALLOC ();
! bb_info->lr_use = BITMAP_XMALLOC ();
! bb_info->lr_in = BITMAP_XMALLOC ();
! bb_info->lr_out = BITMAP_XMALLOC ();
! }
! else
! {
! bitmap_clear (bb_info->lr_def);
! bitmap_clear (bb_info->lr_use);
! bitmap_clear (bb_info->lr_in);
! bitmap_clear (bb_info->lr_out);
! }
! }
! });
}
*************** df_alloc (struct df *df, int n_regs)
*** 506,513 ****
df->n_bbs = last_basic_block;
/* Allocate temporary working array used during local dataflow analysis. */
- df->reg_def_last = xmalloc (df->n_regs * sizeof (struct ref *));
-
df_insn_table_realloc (df, n_insns);
df_reg_table_realloc (df, df->n_regs);
--- 532,537 ----
*************** df_free (struct df *df)
*** 570,576 ****
free_alloc_pool (df_ref_pool);
free_alloc_pool (df_link_pool);
-
}
/* Local miscellaneous routines. */
--- 594,599 ----
*************** df_link_create (struct ref *ref, struct
*** 614,619 ****
--- 637,657 ----
return link;
}
+ /* Releases members of the CHAIN. */
+
+ static void
+ free_reg_ref_chain (struct df_link **chain)
+ {
+ struct df_link *act, *next;
+
+ for (act = *chain; act; act = next)
+ {
+ next = act->next;
+ pool_free (df_link_pool, act);
+ }
+
+ *chain = NULL;
+ }
/* Add REF to chain head pointed to by PHEAD. */
static struct df_link *
*************** df_ref_create (struct df *df, rtx reg, r
*** 740,745 ****
--- 778,784 ----
DF_REF_CHAIN (this_ref) = 0;
DF_REF_TYPE (this_ref) = ref_type;
DF_REF_FLAGS (this_ref) = ref_flags;
+ DF_REF_DATA (this_ref) = NULL;
if (ref_type == DF_REF_REG_DEF)
{
*************** df_bb_refs_record (struct df *df, basic_
*** 1216,1230 ****
rtx insn;
/* Scan the block an insn at a time from beginning to end. */
! for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
/* Record defs within INSN. */
df_insn_refs_record (df, bb, insn);
}
- if (insn == BB_END (bb))
- break;
}
}
--- 1255,1267 ----
rtx insn;
/* Scan the block an insn at a time from beginning to end. */
! FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
{
/* Record defs within INSN. */
df_insn_refs_record (df, bb, insn);
}
}
}
*************** df_refs_record (struct df *df, bitmap bl
*** 1243,1263 ****
/* Dataflow analysis routines. */
-
/* Create reg-def chains for basic block BB. These are a list of
definitions for each register. */
static void
df_bb_reg_def_chain_create (struct df *df, basic_block bb)
{
rtx insn;
/* Perhaps the defs should be sorted using a depth first search
! of the CFG (or possibly a breadth first search). We currently
! scan the basic blocks in reverse order so that the first defs
! appear at the start of the chain. */
! for (insn = BB_END (bb); insn && insn != PREV_INSN (BB_HEAD (bb));
! insn = PREV_INSN (insn))
{
struct df_link *link;
unsigned int uid = INSN_UID (insn);
--- 1280,1297 ----
/* Dataflow analysis routines. */
/* Create reg-def chains for basic block BB. These are a list of
definitions for each register. */
+
static void
df_bb_reg_def_chain_create (struct df *df, basic_block bb)
{
rtx insn;
/* Perhaps the defs should be sorted using a depth first search
! of the CFG (or possibly a breadth first search). */
! FOR_BB_INSNS_REVERSE (bb, insn)
{
struct df_link *link;
unsigned int uid = INSN_UID (insn);
*************** df_bb_reg_def_chain_create (struct df *d
*** 1277,1305 ****
if (DF_REF_ID (def) < df->def_id_save)
continue;
! df->regs[dregno].defs
! = df_link_create (def, df->regs[dregno].defs);
}
}
}
/* Create reg-def chains for each basic block within BLOCKS. These
! are a list of definitions for each register. */
static void
! df_reg_def_chain_create (struct df *df, bitmap blocks)
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP/*_REV*/ (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
- }
/* Create reg-use chains for basic block BB. These are a list of uses
for each register. */
static void
df_bb_reg_use_chain_create (struct df *df, basic_block bb)
{
--- 1311,1353 ----
if (DF_REF_ID (def) < df->def_id_save)
continue;
! df->regs[dregno].defs = df_link_create (def, df->regs[dregno].defs);
}
}
}
/* Create reg-def chains for each basic block within BLOCKS. These
! are a list of definitions for each register. If REDO is true, remove the
! old reg-def chains first, otherwise just add new defs to them. */
!
static void
! df_reg_def_chain_create (struct df *df, bitmap blocks, bool redo)
{
basic_block bb;
+ unsigned regno;
+ unsigned old_def_id_save = df->def_id_save;
! if (redo)
! {
! for (regno = 0; regno < df->n_regs; regno++)
! free_reg_ref_chain (&df->regs[regno].defs);
!
! /* Pretend that all defs are new. */
! df->def_id_save = 0;
! }
!
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
+ df->def_id_save = old_def_id_save;
+ }
/* Create reg-use chains for basic block BB. These are a list of uses
for each register. */
+
static void
df_bb_reg_use_chain_create (struct df *df, basic_block bb)
{
*************** df_bb_reg_use_chain_create (struct df *d
*** 1308,1315 ****
/* Scan in forward order so that the last uses appear at the start
of the chain. */
! for (insn = BB_HEAD (bb); insn && insn != NEXT_INSN (BB_END (bb));
! insn = NEXT_INSN (insn))
{
struct df_link *link;
unsigned int uid = INSN_UID (insn);
--- 1356,1362 ----
/* Scan in forward order so that the last uses appear at the start
of the chain. */
! FOR_BB_INSNS (bb, insn)
{
struct df_link *link;
unsigned int uid = INSN_UID (insn);
*************** df_bb_reg_use_chain_create (struct df *d
*** 1337,1352 ****
/* Create reg-use chains for each basic block within BLOCKS. These
! are a list of uses for each register. */
static void
! df_reg_use_chain_create (struct df *df, bitmap blocks)
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_use_chain_create (df, bb);
});
}
--- 1384,1414 ----
/* Create reg-use chains for each basic block within BLOCKS. These
! are a list of uses for each register. If REDO is true, remove the
! old reg-use chains first, otherwise just add new uses to them. */
!
static void
! df_reg_use_chain_create (struct df *df, bitmap blocks, bool redo)
{
basic_block bb;
+ unsigned regno;
+ unsigned old_use_id_save = df->use_id_save;
+
+ if (redo)
+ {
+ for (regno = 0; regno < df->n_regs; regno++)
+ free_reg_ref_chain (&df->regs[regno].uses);
+
+ /* Pretend that all uses are new. */
+ df->use_id_save = 0;
+ }
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_use_chain_create (df, bb);
});
+
+ df->use_id_save = old_use_id_save;
}
*************** df_bb_du_chain_create (struct df *df, ba
*** 1361,1368 ****
/* For each def in BB create a linked list (chain) of uses
reached from the def. */
! for (insn = BB_END (bb); insn && insn != PREV_INSN (BB_HEAD (bb));
! insn = PREV_INSN (insn))
{
struct df_link *def_link;
struct df_link *use_link;
--- 1423,1429 ----
/* For each def in BB create a linked list (chain) of uses
reached from the def. */
! FOR_BB_INSNS_REVERSE (bb, insn)
{
struct df_link *def_link;
struct df_link *use_link;
*************** df_bb_ud_chain_create (struct df *df, ba
*** 1438,1445 ****
/* For each use in BB create a linked list (chain) of defs
that reach the use. */
! for (insn = BB_HEAD (bb); insn && insn != NEXT_INSN (BB_END (bb));
! insn = NEXT_INSN (insn))
{
unsigned int uid = INSN_UID (insn);
struct df_link *use_link;
--- 1499,1505 ----
/* For each use in BB create a linked list (chain) of defs
that reach the use. */
! FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *use_link;
*************** df_ud_chain_create (struct df *df, bitma
*** 1515,1522 ****
static void
! df_rd_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, bitmap in,
! bitmap out, bitmap gen, bitmap kill,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_union_of_diff (out, gen, in, kill);
--- 1575,1582 ----
static void
! df_rd_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
! void *out, void *gen, void *kill,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_union_of_diff (out, gen, in, kill);
*************** df_rd_transfer_function (int bb ATTRIBUT
*** 1524,1531 ****
static void
! df_ru_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, bitmap in,
! bitmap out, bitmap gen, bitmap kill,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_union_of_diff (in, gen, out, kill);
--- 1584,1591 ----
static void
! df_ru_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
! void *out, void *gen, void *kill,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_union_of_diff (in, gen, out, kill);
*************** df_ru_transfer_function (int bb ATTRIBUT
*** 1533,1540 ****
static void
! df_lr_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, bitmap in,
! bitmap out, bitmap use, bitmap def,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_union_of_diff (in, use, out, def);
--- 1593,1600 ----
static void
! df_lr_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
! void *out, void *use, void *def,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_union_of_diff (in, use, out, def);
*************** df_bb_rd_local_compute (struct df *df, b
*** 1548,1555 ****
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! for (insn = BB_HEAD (bb); insn && insn != NEXT_INSN (BB_END (bb));
! insn = NEXT_INSN (insn))
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
--- 1608,1614 ----
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
*************** df_bb_rd_local_compute (struct df *df, b
*** 1581,1588 ****
bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
}
}
-
- bb_info->rd_valid = 1;
}
--- 1640,1645 ----
*************** df_bb_ru_local_compute (struct df *df, b
*** 1612,1619 ****
rtx insn;
! for (insn = BB_END (bb); insn && insn != PREV_INSN (BB_HEAD (bb));
! insn = PREV_INSN (insn))
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
--- 1669,1675 ----
rtx insn;
! FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
*************** df_bb_ru_local_compute (struct df *df, b
*** 1650,1656 ****
bitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
- bb_info->ru_valid = 1;
}
--- 1706,1711 ----
*************** df_bb_lr_local_compute (struct df *df, b
*** 1675,1682 ****
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! for (insn = BB_END (bb); insn && insn != PREV_INSN (BB_HEAD (bb));
! insn = PREV_INSN (insn))
{
unsigned int uid = INSN_UID (insn);
struct df_link *link;
--- 1730,1736 ----
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *link;
*************** df_bb_lr_local_compute (struct df *df, b
*** 1702,1708 ****
bitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
}
}
- bb_info->lr_valid = 1;
}
--- 1756,1761 ----
*************** df_bb_reg_info_compute (struct df *df, b
*** 1730,1737 ****
bitmap_copy (live, bb_info->lr_out);
! for (insn = BB_END (bb); insn && insn != PREV_INSN (BB_HEAD (bb));
! insn = PREV_INSN (insn))
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
--- 1783,1789 ----
bitmap_copy (live, bb_info->lr_out);
! FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
*************** df_bb_luids_set (struct df *df, basic_bl
*** 1796,1809 ****
/* The LUIDs are monotonically increasing for each basic block. */
! for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
DF_INSN_LUID (df, insn) = luid++;
DF_INSN_LUID (df, insn) = luid;
-
- if (insn == BB_END (bb))
- break;
}
return luid;
}
--- 1848,1858 ----
/* The LUIDs are monotonically increasing for each basic block. */
! FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
DF_INSN_LUID (df, insn) = luid++;
DF_INSN_LUID (df, insn) = luid;
}
return luid;
}
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1833,1838 ****
--- 1882,1888 ----
int dflags;
int i;
basic_block bb;
+ struct dataflow dflow;
dflags = 0;
aflags = flags;
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1854,1860 ****
df->flags = flags;
if (update)
{
! df_refs_update (df);
/* More fine grained incremental dataflow analysis would be
nice. For now recompute the whole shebang for the
modified blocks. */
--- 1904,1910 ----
df->flags = flags;
if (update)
{
! df_refs_update (df, NULL);
/* More fine grained incremental dataflow analysis would be
nice. For now recompute the whole shebang for the
modified blocks. */
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1878,1884 ****
/* Allocate the bitmaps now the total number of defs and uses are
known. If the number of defs or uses have changed, then
these bitmaps need to be reallocated. */
! df_bitmaps_alloc (df, aflags);
/* Set the LUIDs for each specified basic block. */
df_luids_set (df, blocks);
--- 1928,1934 ----
/* Allocate the bitmaps now the total number of defs and uses are
known. If the number of defs or uses have changed, then
these bitmaps need to be reallocated. */
! df_bitmaps_alloc (df, NULL, aflags);
/* Set the LUIDs for each specified basic block. */
df_luids_set (df, blocks);
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1889,1900 ****
regs local to a basic block as it speeds up searching. */
if (aflags & DF_RD_CHAIN)
{
! df_reg_def_chain_create (df, blocks);
}
if (aflags & DF_RU_CHAIN)
{
! df_reg_use_chain_create (df, blocks);
}
df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
--- 1939,1950 ----
regs local to a basic block as it speeds up searching. */
if (aflags & DF_RD_CHAIN)
{
! df_reg_def_chain_create (df, blocks, false);
}
if (aflags & DF_RU_CHAIN)
{
! df_reg_use_chain_create (df, blocks, false);
}
df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1915,1941 ****
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
! {
! bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *gen = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *kill = xmalloc (sizeof (bitmap) * last_basic_block);
! FOR_EACH_BB (bb)
! {
! in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
! out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
! gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
! kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
! }
! iterative_dataflow_bitmap (in, out, gen, kill, df->all_blocks,
! DF_FORWARD, DF_UNION, df_rd_transfer_function,
! df->inverse_rc_map, NULL);
! free (in);
! free (out);
! free (gen);
! free (kill);
! }
}
if (aflags & DF_UD_CHAIN)
--- 1965,1997 ----
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
+ dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
+
df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
! FOR_EACH_BB (bb)
! {
! dflow.in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
! dflow.out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
! dflow.gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
! dflow.kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
! }
!
! dflow.repr = SR_BITMAP;
! dflow.dir = DF_FORWARD;
! dflow.conf_op = DF_UNION;
! dflow.transfun = df_rd_transfer_function;
! dflow.n_blocks = n_basic_blocks;
! dflow.order = df->rc_order;
! dflow.data = NULL;
!
! iterative_dataflow (&dflow);
! free (dflow.in);
! free (dflow.out);
! free (dflow.gen);
! free (dflow.kill);
}
if (aflags & DF_UD_CHAIN)
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1951,1977 ****
{
/* Compute the sets of gens and kills for the upwards exposed
uses in each bb. */
df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
! {
! bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *gen = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *kill = xmalloc (sizeof (bitmap) * last_basic_block);
! FOR_EACH_BB (bb)
! {
! in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
! out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
! gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
! kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
! }
! iterative_dataflow_bitmap (in, out, gen, kill, df->all_blocks,
! DF_BACKWARD, DF_UNION, df_ru_transfer_function,
! df->inverse_rts_map, NULL);
! free (in);
! free (out);
! free (gen);
! free (kill);
! }
}
if (aflags & DF_DU_CHAIN)
--- 2007,2040 ----
{
/* Compute the sets of gens and kills for the upwards exposed
uses in each bb. */
+ dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
+
df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
!
! FOR_EACH_BB (bb)
! {
! dflow.in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
! dflow.out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
! dflow.gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
! dflow.kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
! }
!
! dflow.repr = SR_BITMAP;
! dflow.dir = DF_BACKWARD;
! dflow.conf_op = DF_UNION;
! dflow.transfun = df_ru_transfer_function;
! dflow.n_blocks = n_basic_blocks;
! dflow.order = df->rts_order;
! dflow.data = NULL;
!
! iterative_dataflow (&dflow);
! free (dflow.in);
! free (dflow.out);
! free (dflow.gen);
! free (dflow.kill);
}
if (aflags & DF_DU_CHAIN)
*************** df_analyse_1 (struct df *df, bitmap bloc
*** 1990,2016 ****
if (aflags & DF_LR)
{
/* Compute the sets of defs and uses of live variables. */
df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
! {
! bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *use = xmalloc (sizeof (bitmap) * last_basic_block);
! bitmap *def = xmalloc (sizeof (bitmap) * last_basic_block);
! FOR_EACH_BB (bb)
! {
! in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
! out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
! use[bb->index] = DF_BB_INFO (df, bb)->lr_use;
! def[bb->index] = DF_BB_INFO (df, bb)->lr_def;
! }
! iterative_dataflow_bitmap (in, out, use, def, df->all_blocks,
! DF_BACKWARD, DF_UNION, df_lr_transfer_function,
! df->inverse_rts_map, NULL);
! free (in);
! free (out);
! free (use);
! free (def);
! }
}
if (aflags & DF_REG_INFO)
--- 2053,2086 ----
if (aflags & DF_LR)
{
/* Compute the sets of defs and uses of live variables. */
+ dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
+
df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
!
! FOR_EACH_BB (bb)
! {
! dflow.in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
! dflow.out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
! dflow.gen[bb->index] = DF_BB_INFO (df, bb)->lr_use;
! dflow.kill[bb->index] = DF_BB_INFO (df, bb)->lr_def;
! }
!
! dflow.repr = SR_BITMAP;
! dflow.dir = DF_BACKWARD;
! dflow.conf_op = DF_UNION;
! dflow.transfun = df_lr_transfer_function;
! dflow.n_blocks = n_basic_blocks;
! dflow.order = df->rts_order;
! dflow.data = NULL;
!
! iterative_dataflow (&dflow);
! free (dflow.in);
! free (dflow.out);
! free (dflow.gen);
! free (dflow.kill);
}
if (aflags & DF_REG_INFO)
*************** df_bb_refs_update (struct df *df, basic_
*** 2097,2103 ****
a bitmap for insns_modified saves memory and avoids queuing
duplicates. */
! for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
unsigned int uid;
--- 2167,2173 ----
a bitmap for insns_modified saves memory and avoids queuing
duplicates. */
! FOR_BB_INSNS (bb, insn)
{
unsigned int uid;
*************** df_bb_refs_update (struct df *df, basic_
*** 2113,2120 ****
count++;
}
- if (insn == BB_END (bb))
- break;
}
return count;
}
--- 2183,2188 ----
*************** df_bb_refs_update (struct df *df, basic_
*** 2122,2141 ****
/* Process all the modified/deleted insns that were queued. */
static int
! df_refs_update (struct df *df)
{
basic_block bb;
! int count = 0;
! if ((unsigned int) max_reg_num () >= df->reg_size)
df_reg_table_realloc (df, 0);
df_refs_queue (df);
! FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
{
! count += df_bb_refs_update (df, bb);
! });
df_refs_process (df);
return count;
--- 2190,2220 ----
/* Process all the modified/deleted insns that were queued. */
static int
! df_refs_update (struct df *df, bitmap blocks)
{
basic_block bb;
! int count = 0, bbno;
! df->n_regs = max_reg_num ();
! if (df->n_regs >= df->reg_size)
df_reg_table_realloc (df, 0);
df_refs_queue (df);
! if (!blocks)
{
! FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
! {
! count += df_bb_refs_update (df, bb);
! });
! }
! else
! {
! EXECUTE_IF_AND_IN_BITMAP (df->bbs_modified, blocks, 0, bbno,
! {
! count += df_bb_refs_update (df, BASIC_BLOCK (bbno));
! });
! }
df_refs_process (df);
return count;
*************** df_modified_p (struct df *df, bitmap blo
*** 2164,2173 ****
return update;
}
-
/* Analyze dataflow info for the basic blocks specified by the bitmap
BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
modified blocks if BLOCKS is -1. */
int
df_analyse (struct df *df, bitmap blocks, int flags)
{
--- 2243,2252 ----
return update;
}
/* Analyze dataflow info for the basic blocks specified by the bitmap
BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
modified blocks if BLOCKS is -1. */
+
int
df_analyse (struct df *df, bitmap blocks, int flags)
{
*************** df_analyse (struct df *df, bitmap blocks
*** 2209,2214 ****
--- 2288,2502 ----
return update;
}
+ /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
+ the order of the remaining entries. Returns the length of the resulting
+ list. */
+
+ static unsigned
+ prune_to_subcfg (int list[], unsigned len, bitmap blocks)
+ {
+ unsigned act, last;
+
+ for (act = 0, last = 0; act < len; act++)
+ if (bitmap_bit_p (blocks, list[act]))
+ list[last++] = list[act];
+
+ return last;
+ }
+
+ /* Alternative entry point to the analysis. Analyse just the part of the cfg
+ graph induced by BLOCKS.
+
+ TODO I am not quite sure how to avoid code duplication with df_analyse_1
+ here, and simultaneously not make even greater chaos in it. We behave
+ slightly differently in some details, especially in handling modified
+ insns. */
+
+ void
+ df_analyse_subcfg (struct df *df, bitmap blocks, int flags)
+ {
+ rtx insn;
+ basic_block bb;
+ struct dataflow dflow;
+ unsigned n_blocks;
+
+ if (flags & DF_UD_CHAIN)
+ flags |= DF_RD | DF_RD_CHAIN;
+ if (flags & DF_DU_CHAIN)
+ flags |= DF_RU;
+ if (flags & DF_RU)
+ flags |= DF_RU_CHAIN;
+ if (flags & DF_REG_INFO)
+ flags |= DF_LR;
+
+ if (!df->n_bbs)
+ {
+ df_alloc (df, max_reg_num ());
+
+ /* Mark all insns as modified. */
+
+ FOR_EACH_BB (bb)
+ {
+ FOR_BB_INSNS (bb, insn)
+ {
+ df_insn_modify (df, bb, insn);
+ }
+ }
+ }
+
+ df_refs_update (df, blocks);
+
+ /* Clear the updated stuff from ``modified'' bitmaps. */
+ FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
+ {
+ if (bitmap_bit_p (df->bbs_modified, bb->index))
+ {
+ FOR_BB_INSNS (bb, insn)
+ {
+ bitmap_clear_bit (df->insns_modified, INSN_UID (insn));
+ }
+
+ bitmap_clear_bit (df->bbs_modified, bb->index);
+ }
+ });
+
+ /* Allocate the bitmaps now the total number of defs and uses are
+ known. If the number of defs or uses have changed, then
+ these bitmaps need to be reallocated. */
+ df_bitmaps_alloc (df, blocks, flags);
+
+ /* Set the LUIDs for each specified basic block. */
+ df_luids_set (df, blocks);
+
+ /* Recreate reg-def and reg-use chains from scratch so that first
+ def is at the head of the reg-def chain and the last use is at
+ the head of the reg-use chain. This is only important for
+ regs local to a basic block as it speeds up searching. */
+ if (flags & DF_RD_CHAIN)
+ {
+ df_reg_def_chain_create (df, blocks, true);
+ }
+
+ if (flags & DF_RU_CHAIN)
+ {
+ df_reg_use_chain_create (df, blocks, true);
+ }
+
+ df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
+ df->rc_order = xmalloc (sizeof (int) * n_basic_blocks);
+ df->rts_order = xmalloc (sizeof (int) * n_basic_blocks);
+
+ flow_depth_first_order_compute (df->dfs_order, df->rc_order);
+ flow_reverse_top_sort_order_compute (df->rts_order);
+
+ n_blocks = prune_to_subcfg (df->dfs_order, n_basic_blocks, blocks);
+ prune_to_subcfg (df->rc_order, n_basic_blocks, blocks);
+ prune_to_subcfg (df->rts_order, n_basic_blocks, blocks);
+
+ dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
+ dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
+
+ if (flags & DF_RD)
+ {
+ /* Compute the sets of gens and kills for the defs of each bb. */
+ df_rd_local_compute (df, blocks);
+
+ FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
+ {
+ dflow.in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
+ dflow.out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
+ dflow.gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
+ dflow.kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
+ });
+
+ dflow.repr = SR_BITMAP;
+ dflow.dir = DF_FORWARD;
+ dflow.conf_op = DF_UNION;
+ dflow.transfun = df_rd_transfer_function;
+ dflow.n_blocks = n_blocks;
+ dflow.order = df->rc_order;
+ dflow.data = NULL;
+
+ iterative_dataflow (&dflow);
+ }
+
+ if (flags & DF_UD_CHAIN)
+ {
+ /* Create use-def chains. */
+ df_ud_chain_create (df, blocks);
+ }
+
+ if (flags & DF_RU)
+ {
+ /* Compute the sets of gens and kills for the upwards exposed
+ uses in each bb. */
+ df_ru_local_compute (df, blocks);
+
+ FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
+ {
+ dflow.in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
+ dflow.out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
+ dflow.gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
+ dflow.kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
+ });
+
+ dflow.repr = SR_BITMAP;
+ dflow.dir = DF_BACKWARD;
+ dflow.conf_op = DF_UNION;
+ dflow.transfun = df_ru_transfer_function;
+ dflow.n_blocks = n_blocks;
+ dflow.order = df->rts_order;
+ dflow.data = NULL;
+
+ iterative_dataflow (&dflow);
+ }
+
+ if (flags & DF_DU_CHAIN)
+ {
+ /* Create def-use chains. */
+ df_du_chain_create (df, blocks);
+ }
+
+ if (flags & DF_LR)
+ {
+ /* Compute the sets of defs and uses of live variables. */
+ df_lr_local_compute (df, blocks);
+
+ FOR_EACH_BB (bb)
+ {
+ dflow.in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
+ dflow.out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
+ dflow.gen[bb->index] = DF_BB_INFO (df, bb)->lr_use;
+ dflow.kill[bb->index] = DF_BB_INFO (df, bb)->lr_def;
+ }
+
+ dflow.repr = SR_BITMAP;
+ dflow.dir = DF_BACKWARD;
+ dflow.conf_op = DF_UNION;
+ dflow.transfun = df_lr_transfer_function;
+ dflow.n_blocks = n_blocks;
+ dflow.order = df->rts_order;
+ dflow.data = NULL;
+
+ iterative_dataflow (&dflow);
+ }
+
+ if (flags & DF_REG_INFO)
+ {
+ df_reg_info_compute (df, blocks);
+ }
+
+ free (dflow.in);
+ free (dflow.out);
+ free (dflow.gen);
+ free (dflow.kill);
+
+ free (df->dfs_order);
+ free (df->rc_order);
+ free (df->rts_order);
+ }
/* Free all the dataflow info and the DF structure. */
void
*************** df_finish (struct df *df)
*** 2218,2224 ****
free (df);
}
-
/* Unlink INSN from its reference information. */
static void
df_insn_refs_unlink (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
--- 2506,2511 ----
*************** df_insn_delete (struct df *df, basic_blo
*** 2306,2311 ****
--- 2593,2608 ----
return NEXT_INSN (insn);
}
+ /* Mark that basic block BB was modified. */
+
+ static void
+ df_bb_modify (struct df *df, basic_block bb)
+ {
+ if ((unsigned) bb->index >= df->n_bbs)
+ df_bb_table_realloc (df, df->n_bbs);
+
+ bitmap_set_bit (df->bbs_modified, bb->index);
+ }
/* Mark that INSN within BB may have changed (created/modified/deleted).
This may be called multiple times for the same insn. There is no
*************** df_insn_modify (struct df *df, basic_blo
*** 2320,2326 ****
if (uid >= df->insn_size)
df_insn_table_realloc (df, uid);
! bitmap_set_bit (df->bbs_modified, bb->index);
bitmap_set_bit (df->insns_modified, uid);
/* For incremental updating on the fly, perhaps we could make a copy
--- 2617,2623 ----
if (uid >= df->insn_size)
df_insn_table_realloc (df, uid);
! df_bb_modify (df, bb);
bitmap_set_bit (df->insns_modified, uid);
/* For incremental updating on the fly, perhaps we could make a copy
*************** df_insn_modify (struct df *df, basic_blo
*** 2330,2336 ****
will just get ignored. */
}
-
typedef struct replace_args
{
rtx match;
--- 2627,2632 ----
*************** df_insn_regno_def_p (struct df *df, basi
*** 2688,2693 ****
--- 2984,3003 ----
return 0;
}
+ /* Finds the reference corresponding to the definition of REG in INSN.
+ DF is the dataflow object. */
+
+ struct ref *
+ df_find_def (struct df *df, rtx insn, rtx reg)
+ {
+ struct df_link *defs;
+
+ for (defs = DF_INSN_DEFS (df, insn); defs; defs = defs->next)
+ if (rtx_equal_p (DF_REF_REG (defs->ref), reg))
+ return defs->ref;
+
+ return NULL;
+ }
static int
df_def_dominates_all_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
*************** debug_df_chain (struct df_link *link)
*** 3344,3697 ****
}
- /* Hybrid search algorithm from "Implementation Techniques for
- Efficient Data-Flow Analysis of Large Programs". */
static void
! hybrid_search_bitmap (basic_block block, bitmap *in, bitmap *out, bitmap *gen,
! bitmap *kill, enum df_flow_dir dir,
! enum df_confluence_op conf_op,
! transfer_function_bitmap transfun, sbitmap visited,
! sbitmap pending, void *data)
{
! int changed;
! int i = block->index;
! edge e;
! basic_block bb = block;
!
! SET_BIT (visited, block->index);
! if (TEST_BIT (pending, block->index))
{
! if (dir == DF_FORWARD)
{
! /* Calculate <conf_op> of predecessor_outs. */
! bitmap_zero (in[i]);
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR)
! continue;
! switch (conf_op)
! {
! case DF_UNION:
! bitmap_a_or_b (in[i], in[i], out[e->src->index]);
! break;
! case DF_INTERSECTION:
! bitmap_a_and_b (in[i], in[i], out[e->src->index]);
! break;
! }
! }
! }
! else
! {
! /* Calculate <conf_op> of successor ins. */
! bitmap_zero (out[i]);
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! if (e->dest == EXIT_BLOCK_PTR)
! continue;
! switch (conf_op)
! {
! case DF_UNION:
! bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
! break;
! case DF_INTERSECTION:
! bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
! break;
! }
! }
! }
! /* Common part */
! (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
! RESET_BIT (pending, i);
! if (changed)
! {
! if (dir == DF_FORWARD)
! {
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
! continue;
! SET_BIT (pending, e->dest->index);
! }
! }
! else
! {
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
! continue;
! SET_BIT (pending, e->src->index);
! }
! }
}
! }
! if (dir == DF_FORWARD)
! {
! for (e = bb->succ; e != 0; e = e->succ_next)
{
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
! continue;
! if (!TEST_BIT (visited, e->dest->index))
! hybrid_search_bitmap (e->dest, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
}
}
! else
{
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
! continue;
! if (!TEST_BIT (visited, e->src->index))
! hybrid_search_bitmap (e->src, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
! }
}
}
- /* Hybrid search for sbitmaps, rather than bitmaps. */
static void
! hybrid_search_sbitmap (basic_block block, sbitmap *in, sbitmap *out,
! sbitmap *gen, sbitmap *kill, enum df_flow_dir dir,
! enum df_confluence_op conf_op,
! transfer_function_sbitmap transfun, sbitmap visited,
! sbitmap pending, void *data)
{
int changed;
! int i = block->index;
edge e;
- basic_block bb = block;
! SET_BIT (visited, block->index);
! if (TEST_BIT (pending, block->index))
! {
! if (dir == DF_FORWARD)
! {
! /* Calculate <conf_op> of predecessor_outs. */
! sbitmap_zero (in[i]);
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR)
! continue;
! switch (conf_op)
! {
! case DF_UNION:
! sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
! break;
! case DF_INTERSECTION:
! sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
! break;
! }
! }
! }
! else
! {
! /* Calculate <conf_op> of successor ins. */
! sbitmap_zero (out[i]);
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! if (e->dest == EXIT_BLOCK_PTR)
! continue;
! switch (conf_op)
! {
! case DF_UNION:
! sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
! break;
! case DF_INTERSECTION:
! sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
! break;
! }
! }
! }
! /* Common part. */
! (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
! RESET_BIT (pending, i);
! if (changed)
! {
! if (dir == DF_FORWARD)
! {
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
! continue;
! SET_BIT (pending, e->dest->index);
! }
! }
! else
! {
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
! continue;
! SET_BIT (pending, e->src->index);
! }
! }
! }
! }
! if (dir == DF_FORWARD)
! {
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
! continue;
! if (!TEST_BIT (visited, e->dest->index))
! hybrid_search_sbitmap (e->dest, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
! }
! }
else
! {
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
! continue;
! if (!TEST_BIT (visited, e->src->index))
! hybrid_search_sbitmap (e->src, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
! }
! }
}
!
! /* gen = GEN set.
! kill = KILL set.
! in, out = Filled in by function.
! blocks = Blocks to analyze.
! dir = Dataflow direction.
! conf_op = Confluence operation.
! transfun = Transfer function.
! order = Order to iterate in. (Should map block numbers -> order)
! data = Whatever you want. It's passed to the transfer function.
!
! This function will perform iterative bitvector dataflow, producing
! the in and out sets. Even if you only want to perform it for a
! small number of blocks, the vectors for in and out must be large
! enough for *all* blocks, because changing one block might affect
! others. However, it'll only put what you say to analyze on the
! initial worklist.
For forward problems, you probably want to pass in a mapping of
! block number to rc_order (like df->inverse_rc_map).
! */
void
! iterative_dataflow_sbitmap (sbitmap *in, sbitmap *out, sbitmap *gen,
! sbitmap *kill, bitmap blocks,
! enum df_flow_dir dir,
! enum df_confluence_op conf_op,
! transfer_function_sbitmap transfun, int *order,
! void *data)
{
! int i;
! fibheap_t worklist;
! basic_block bb;
! sbitmap visited, pending;
pending = sbitmap_alloc (last_basic_block);
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
! worklist = fibheap_new ();
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
! {
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
! SET_BIT (pending, i);
! if (dir == DF_FORWARD)
! sbitmap_copy (out[i], gen[i]);
! else
! sbitmap_copy (in[i], gen[i]);
! });
!
! while (sbitmap_first_set_bit (pending) != -1)
{
! while (!fibheap_empty (worklist))
! {
! i = (size_t) fibheap_extract_min (worklist);
! bb = BASIC_BLOCK (i);
! if (!TEST_BIT (visited, bb->index))
! hybrid_search_sbitmap (bb, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending, data);
! }
!
! if (sbitmap_first_set_bit (pending) != -1)
! {
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
! {
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
! });
! sbitmap_zero (visited);
! }
else
! {
! break;
! }
! }
!
! sbitmap_free (pending);
! sbitmap_free (visited);
! fibheap_delete (worklist);
! }
!
! /* Exactly the same as iterative_dataflow_sbitmap, except it works on
! bitmaps instead. */
! void
! iterative_dataflow_bitmap (bitmap *in, bitmap *out, bitmap *gen, bitmap *kill,
! bitmap blocks, enum df_flow_dir dir,
! enum df_confluence_op conf_op,
! transfer_function_bitmap transfun, int *order,
! void *data)
! {
! int i;
! fibheap_t worklist;
! basic_block bb;
! sbitmap visited, pending;
!
! pending = sbitmap_alloc (last_basic_block);
! visited = sbitmap_alloc (last_basic_block);
! sbitmap_zero (pending);
! sbitmap_zero (visited);
! worklist = fibheap_new ();
!
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
! {
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
! SET_BIT (pending, i);
! if (dir == DF_FORWARD)
! bitmap_copy (out[i], gen[i]);
! else
! bitmap_copy (in[i], gen[i]);
! });
!
! while (sbitmap_first_set_bit (pending) != -1)
{
! while (!fibheap_empty (worklist))
{
! i = (size_t) fibheap_extract_min (worklist);
! bb = BASIC_BLOCK (i);
! if (!TEST_BIT (visited, bb->index))
! hybrid_search_bitmap (bb, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending, data);
! }
! if (sbitmap_first_set_bit (pending) != -1)
! {
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
! {
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
! });
! sbitmap_zero (visited);
! }
! else
! {
! break;
}
}
sbitmap_free (pending);
sbitmap_free (visited);
! fibheap_delete (worklist);
}
--- 3654,3846 ----
}
static void
! dataflow_set_a_op_b (enum set_representation repr,
! enum df_confluence_op op,
! void *rslt, void *op1, void *op2)
{
! switch (repr)
{
! case SR_SBITMAP:
! switch (op)
{
! case DF_UNION:
! sbitmap_a_or_b (rslt, op1, op2);
! break;
!
! case DF_INTERSECTION:
! sbitmap_a_and_b (rslt, op1, op2);
! break;
!
! default:
! abort ();
}
! break;
!
! case SR_BITMAP:
! switch (op)
{
! case DF_UNION:
! bitmap_a_or_b (rslt, op1, op2);
! break;
!
! case DF_INTERSECTION:
! bitmap_a_and_b (rslt, op1, op2);
! break;
!
! default:
! abort ();
}
+ break;
+
+ default:
+ abort ();
}
! }
!
! static void
! dataflow_set_copy (enum set_representation repr, void *dest, void *src)
! {
! switch (repr)
{
! case SR_SBITMAP:
! sbitmap_copy (dest, src);
! break;
!
! case SR_BITMAP:
! bitmap_copy (dest, src);
! break;
!
! default:
! abort ();
}
}
+ /* Hybrid search algorithm from "Implementation Techniques for
+ Efficient Data-Flow Analysis of Large Programs". */
static void
! hybrid_search (basic_block bb, struct dataflow *dataflow,
! sbitmap visited, sbitmap pending, sbitmap considered)
{
int changed;
! int i = bb->index;
edge e;
! SET_BIT (visited, bb->index);
! if (!TEST_BIT (pending, bb->index))
! abort ();
! RESET_BIT (pending, i);
!
! #define HS(E_ANTI, E_ANTI_NEXT, E_ANTI_BB, E_ANTI_START_BB, IN_SET, \
! E, E_NEXT, E_BB, E_START_BB, OUT_SET) \
! do \
! { \
! /* Calculate <conf_op> of predecessor_outs. */ \
! bitmap_zero (IN_SET[i]); \
! for (e = bb->E_ANTI; e; e = e->E_ANTI_NEXT) \
! { \
! if (e->E_ANTI_BB == E_ANTI_START_BB) \
! continue; \
! if (!TEST_BIT (considered, e->E_ANTI_BB->index)) \
! continue; \
! \
! dataflow_set_a_op_b (dataflow->repr, dataflow->conf_op, \
! IN_SET[i], IN_SET[i], \
! OUT_SET[e->E_ANTI_BB->index]); \
! } \
! \
! (*dataflow->transfun)(i, &changed, \
! dataflow->in[i], dataflow->out[i], \
! dataflow->gen[i], dataflow->kill[i], \
! dataflow->data); \
! \
! if (!changed) \
! break; \
! \
! for (e = bb->E; e; e = e->E_NEXT) \
! { \
! if (e->E_BB == E_START_BB || e->E_BB->index == i) \
! continue; \
! \
! if (!TEST_BIT (considered, e->E_BB->index)) \
! continue; \
! \
! SET_BIT (pending, e->E_BB->index); \
! } \
! \
! for (e = bb->E; e; e = e->E_NEXT) \
! { \
! if (e->E_BB == E_START_BB || e->E_BB->index == i) \
! continue; \
! \
! if (!TEST_BIT (considered, e->E_BB->index)) \
! continue; \
! \
! if (!TEST_BIT (visited, e->E_BB->index)) \
! hybrid_search (e->E_BB, dataflow, visited, pending, considered); \
! } \
! } while (0)
!
! if (dataflow->dir == DF_FORWARD)
! HS (pred, pred_next, src, ENTRY_BLOCK_PTR, dataflow->in,
! succ, succ_next, dest, EXIT_BLOCK_PTR, dataflow->out);
else
! HS (succ, succ_next, dest, EXIT_BLOCK_PTR, dataflow->out,
! pred, pred_next, src, ENTRY_BLOCK_PTR, dataflow->in);
}
! /* This function will perform iterative bitvector dataflow described by
! DATAFLOW, producing the in and out sets. Only the part of the cfg
! induced by blocks in DATAFLOW->order is taken into account.
For forward problems, you probably want to pass in a mapping of
! block number to rc_order (like df->inverse_rc_map). */
!
void
! iterative_dataflow (struct dataflow *dataflow)
{
! unsigned i, idx;
! sbitmap visited, pending, considered;
pending = sbitmap_alloc (last_basic_block);
visited = sbitmap_alloc (last_basic_block);
+ considered = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
! sbitmap_zero (considered);
! for (i = 0; i < dataflow->n_blocks; i++)
{
! idx = dataflow->order[i];
! SET_BIT (pending, idx);
! SET_BIT (considered, idx);
! if (dataflow->dir == DF_FORWARD)
! dataflow_set_copy (dataflow->repr,
! dataflow->out[idx], dataflow->gen[idx]);
else
! dataflow_set_copy (dataflow->repr,
! dataflow->in[idx], dataflow->gen[idx]);
! };
! while (1)
{
! for (i = 0; i < dataflow->n_blocks; i++)
{
! idx = dataflow->order[i];
! if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
! hybrid_search (BASIC_BLOCK (idx), dataflow,
! visited, pending, considered);
}
+
+ if (sbitmap_first_set_bit (pending) == -1)
+ break;
+
+ sbitmap_zero (visited);
}
+
sbitmap_free (pending);
sbitmap_free (visited);
! sbitmap_free (considered);
}
Index: df.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/df.h,v
retrieving revision 1.12.2.4.4.1
diff -c -3 -p -r1.12.2.4.4.1 df.h
*** df.h 21 Feb 2004 23:09:41 -0000 1.12.2.4.4.1
--- df.h 9 Mar 2004 18:19:46 -0000
*************** struct ref
*** 84,89 ****
--- 84,90 ----
unsigned int id; /* Ref index. */
enum df_ref_type type; /* Type of ref. */
enum df_ref_flags flags; /* Various flags. */
+ void *data; /* The data assigned to it by user. */
};
*************** struct df_map
*** 196,201 ****
--- 197,203 ----
#define DF_REF_CHAIN(REF) ((REF)->chain)
#define DF_REF_ID(REF) ((REF)->id)
#define DF_REF_FLAGS(REF) ((REF)->flags)
+ #define DF_REF_DATA(REF) ((REF)->data)
/* Macros to determine the reference type. */
*************** struct df_map
*** 234,239 ****
--- 236,242 ----
extern struct df *df_init (void);
extern int df_analyse (struct df *, bitmap, int);
+ extern void df_analyse_subcfg (struct df *, bitmap, int);
extern void df_finish (struct df *);
*************** extern int df_bb_regs_lives_compare (str
*** 292,297 ****
--- 295,301 ----
extern rtx df_bb_single_def_use_insn_find (struct df *, basic_block, rtx,
rtx);
+ extern struct ref *df_find_def (struct df *, rtx, rtx);
/* Functions for debugging from GDB. */
*************** enum df_flow_dir
*** 330,351 ****
};
! typedef void (*transfer_function_sbitmap) (int, int *, sbitmap, sbitmap,
! sbitmap, sbitmap, void *);
! typedef void (*transfer_function_bitmap) (int, int *, bitmap, bitmap,
! bitmap, bitmap, void *);
! extern void iterative_dataflow_sbitmap (sbitmap *, sbitmap *, sbitmap *,
! sbitmap *, bitmap, enum df_flow_dir,
! enum df_confluence_op,
! transfer_function_sbitmap,
! int *, void *);
!
! extern void iterative_dataflow_bitmap (bitmap *, bitmap *, bitmap *,
! bitmap *, bitmap,
! enum df_flow_dir,
! enum df_confluence_op,
! transfer_function_bitmap,
! int *, void *);
extern bool read_modify_subreg_p (rtx);
--- 334,370 ----
};
! typedef void (*transfer_function) (int, int *, void *, void *,
! void *, void *, void *);
! /* The description of a dataflow problem to solve. */
! enum set_representation
! {
! SR_SBITMAP, /* Represent sets by bitmaps. */
! SR_BITMAP /* Represent sets by sbitmaps. */
! };
!
! struct dataflow
! {
! enum set_representation repr; /* The way the sets are represented. */
!
! /* The following arrays are indexed by block indices, so they must always
! be large enough even if we restrict ourselves just to a subset of cfg. */
! void **gen, **kill; /* Gen and kill sets. */
! void **in, **out; /* Results. */
!
! enum df_flow_dir dir; /* Dataflow direction. */
! enum df_confluence_op conf_op; /* Confluence operator. */
! unsigned n_blocks; /* Number of basic blocks in the
! order. */
! int *order; /* The list of basic blocks to work
! with, in the order they should
! be processed in. */
! transfer_function transfun; /* The transfer function. */
! void *data; /* Data used by the transfer
! function. */
! };
!
! extern void iterative_dataflow (struct dataflow *);
extern bool read_modify_subreg_p (rtx);
Index: loop-invariant.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-invariant.c,v
retrieving revision 1.1.4.2
diff -c -3 -p -r1.1.4.2 loop-invariant.c
*** loop-invariant.c 27 Feb 2004 23:07:31 -0000 1.1.4.2
--- loop-invariant.c 9 Mar 2004 18:19:46 -0000
*************** Software Foundation, 59 Temple Place - S
*** 24,34 ****
eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
We proceed loop by loop -- it is simpler than trying to handle things
! globally and should not lose much; by avoiding looking inside already
! processed subloops (where we would not usually find anything useful anyway)
! we preserve the time complexity linear in number of insns. First we inspect
! all sets inside loop and create a dependency graph on insns (saying "to move
! this insn, you must also move the following insns").
We then need to determine what to move. We estimate the number of registers
used and move as many invariants as possible while we still have enough free
--- 24,32 ----
eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
We proceed loop by loop -- it is simpler than trying to handle things
! globally and should not lose much. First we inspect all sets inside loop
! and create a dependency graph on insns (saying "to move this insn, you must
! also move the following insns").
We then need to determine what to move. We estimate the number of registers
used and move as many invariants as possible while we still have enough free
*************** Software Foundation, 59 Temple Place - S
*** 49,116 ****
#include "output.h"
#include "function.h"
#include "flags.h"
/* The data stored for the loop. */
struct loop_data
{
- bitmap modified_regs; /* The registers modified inside the loop. */
struct loop *outermost_exit; /* The outermost exit of the loop. */
bool has_call; /* True if the loop contains a call. */
};
#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
- /* The definition of a register. */
-
- struct def
- {
- bool simple_p; /* Whether the definition may be simple. */
- bool invar_rhs; /* Whether the insn should be considered for invariant
- motion. */
- unsigned regno; /* Number of the register defined. */
- rtx insn; /* The insn in that the definition occurs. */
- basic_block bb; /* Its basic block. */
- unsigned invariant; /* The number of the associated invariant. */
-
- unsigned n_uses; /* Number of uses. */
- struct use *uses; /* The list of uses. */
-
- struct def *next; /* Next definition. */
- struct def *reg_next; /* Next definition of the same register. */
- };
-
/* The description of an use. */
struct use
{
rtx *pos; /* Position of the use. */
struct use *next; /* Next use in the list. */
};
! /* The list of definitions. */
!
! static struct def *defs, *adef;
! static struct def **last_def;
!
! /* The data stored for each register. */
! struct reg
{
! bool simple_p; /* Whether the register may be simple. */
! bool used; /* Whether the register is used at all. */
!
! struct def *defs; /* The definitions of the register. */
! struct def **def_end; /* End of the chain of the definitions. */
! struct def *actual; /* Actual definition of the register. */
! basic_block last_bb; /* The last basic block in that the register was
! set. */
};
- static unsigned m_reg_info;
- static struct reg *reg_info;
-
/* The data stored for each invariant. */
struct invariant
--- 47,84 ----
#include "output.h"
#include "function.h"
#include "flags.h"
+ #include "df.h"
/* The data stored for the loop. */
struct loop_data
{
struct loop *outermost_exit; /* The outermost exit of the loop. */
bool has_call; /* True if the loop contains a call. */
};
#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
/* The description of an use. */
struct use
{
rtx *pos; /* Position of the use. */
+ rtx insn; /* The insn in that the use occurs. */
struct use *next; /* Next use in the list. */
};
! /* The description of a def. */
! struct def
{
! struct use *uses; /* The list of uses that are uniquely reached
! by it. */
! unsigned n_uses; /* Number of such uses. */
! unsigned invno; /* The corresponding invariant. */
};
/* The data stored for each invariant. */
struct invariant
*************** struct invariant
*** 124,129 ****
--- 92,100 ----
/* The definition of the invariant. */
struct def *def;
+ /* The insn in that it is defined. */
+ rtx insn;
+
/* Whether it is always executed. */
bool always_executed;
*************** check_maybe_invariant (rtx x)
*** 176,182 ****
case REG:
if (HARD_REGISTER_P (x))
{
! /* TODO -- handling of hard regs. */
return false;
}
--- 147,155 ----
case REG:
if (HARD_REGISTER_P (x))
{
! /* TODO -- handling of hard regs. It should not be hard due to usage
! of df.c, but don't forget to include patches from the rtlopt branch
! to speed up handling of call clobbered registers. */
return false;
}
*************** find_exits (struct loop *loop, basic_blo
*** 307,353 ****
LOOP_DATA (loop)->has_call = has_call;
}
- /* Record a definition of a register REGNO in INSN in basic block BB,
- simple if SIMPLE_P. Rhs of the definition may be considered for
- moving if INVAR_RHS is true. */
-
- static void
- record_def (unsigned regno, rtx insn, basic_block bb, bool simple_p,
- bool invar_rhs)
- {
- struct def *def;
- basic_block last_bb;
-
- if (!reg_info[regno].simple_p)
- return;
- last_bb = reg_info[regno].last_bb;
-
- if (!dominated_by_p (CDI_DOMINATORS, bb, last_bb))
- {
- reg_info[regno].simple_p = false;
- return;
- }
-
- def = xmalloc (sizeof (struct def));
- def->simple_p = simple_p;
- def->invar_rhs = invar_rhs;
- def->regno = regno;
- def->insn = insn;
- def->bb = bb;
- def->next = NULL;
- def->invariant = 0;
- def->uses = NULL;
- def->n_uses = 0;
- def->reg_next = NULL;
-
- *last_def = def;
- last_def = &def->next;
-
- *reg_info[regno].def_end = def;
- reg_info[regno].def_end = &def->reg_next;
- reg_info[regno].last_bb = bb;
- }
-
/* Check whether we may assign a value to X from a register. */
static bool
--- 280,285 ----
*************** may_assign_reg_p (rtx x)
*** 361,501 ****
return true;
}
- /* Notes the registers clobbered by the NIS_INSN. Callback for note_stores.
- If not NIS_MAY_BE_SIMPLE, the set may not be considered simple. */
-
- static bool nis_may_be_simple;
- static rtx nis_insn;
- static void
- note_insn_stores (rtx reg, rtx set, void *data ATTRIBUTE_UNUSED)
- {
- bool simple = true, consider_invariantness = true, should_record_def = true;
- unsigned regno = 0;
- rtx areg = SET_DEST (set);
-
- if (!nis_may_be_simple)
- {
- simple = false;
- consider_invariantness = false;
- }
-
- if (!REG_P (areg))
- {
- simple = false;
- if (GET_CODE (reg) == SUBREG)
- reg = SUBREG_REG (reg);
- }
-
- if (!REG_P (reg)
- || HARD_REGISTER_P (reg))
- {
- /* It is not necessary to record the definition in this case,
- since we are not going to use it. */
- should_record_def = false;
- }
- else
- regno = REGNO (reg);
-
- if (!reg_info[regno].simple_p)
- should_record_def = false;
-
- if (GET_CODE (set) != SET
- || set != single_set (nis_insn)
- || !check_maybe_invariant (SET_SRC (set))
- || !may_assign_reg_p (SET_DEST (set))
- /* Until we get rid of LIBCALLS. */
- || find_reg_note (nis_insn, REG_RETVAL, NULL_RTX)
- || find_reg_note (nis_insn, REG_LIBCALL, NULL_RTX)
- || find_reg_note (nis_insn, REG_NO_CONFLICT, NULL_RTX))
- {
- consider_invariantness = false;
- simple = false;
- }
-
- if (should_record_def || consider_invariantness)
- record_def (regno, nis_insn, BLOCK_FOR_INSN (nis_insn), simple,
- consider_invariantness);
- }
-
- /* Finds definitions that may correspond to invariants inside INSN.
- ALWAYS_REACHED is true if the insn is always reached. If IS_NOT_SIMPLE,
- the set may not be simple. */
-
- static void
- find_defs_insn (rtx insn, bool always_reached, bool is_not_simple)
- {
- nis_may_be_simple = !is_not_simple;
-
- if (!always_reached
- && may_trap_p (insn))
- nis_may_be_simple = false;
-
- nis_insn = insn;
- note_stores (PATTERN (insn), note_insn_stores, NULL);
- }
-
- /* Finds definitions that may correspond to invariants inside basic block BB.
- ALWAYS_REACHED is true if the entry of the basic block is always
- reached. */
-
- static void
- find_defs_bb (basic_block bb, bool always_reached)
- {
- rtx insn;
-
- FOR_BB_INSNS (bb, insn)
- {
- if (!INSN_P (insn))
- continue;
-
- if (always_reached
- && GET_CODE (insn) == CALL_INSN
- && !CONST_OR_PURE_CALL_P (insn))
- always_reached = false;
-
- find_defs_insn (insn, always_reached,
- (bb->flags & BB_IRREDUCIBLE_LOOP) != 0);
- }
- }
-
/* Finds definitions that may correspond to invariants in LOOP with body BODY.
! ALWAYS_REACHED is the bitmap of basic blocks in BODY whose entry is always
! reached. */
static void
! find_defs (struct loop *loop, basic_block *body, bitmap always_reached)
{
! unsigned i, regno;
! bitmap modified_regs;
for (i = 0; i < loop->num_nodes; i++)
! {
! if (body[i]->loop_father == loop)
! {
! find_defs_bb (body[i], bitmap_bit_p (always_reached, i));
! continue;
! }
! if (body[i]->loop_father->header != body[i])
! continue;
!
! modified_regs = LOOP_DATA (body[i]->loop_father)->modified_regs;
! EXECUTE_IF_SET_IN_BITMAP (modified_regs, 0, regno,
! {
! record_def (regno, const0_rtx, body[i], false, false);
! });
! }
}
! /* Creates a new invariant for definition DEF, depending on invariants in
! DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
unless the program ends due to a function call. */
static void
! create_new_invariant (struct def *def, bitmap depends_on, bool always_executed)
{
struct invariant *inv = xmalloc (sizeof (struct invariant));
! rtx set = single_set (def->insn);
inv->def = def;
inv->always_executed = always_executed;
--- 293,324 ----
return true;
}
/* Finds definitions that may correspond to invariants in LOOP with body BODY.
! DF is the dataflow object. */
static void
! find_defs (struct loop *loop, basic_block *body, struct df *df)
{
! unsigned i;
! bitmap blocks = BITMAP_XMALLOC ();
for (i = 0; i < loop->num_nodes; i++)
! bitmap_set_bit (blocks, body[i]->index);
! df_analyse_subcfg (df, blocks, DF_UD_CHAIN);
! BITMAP_XFREE (blocks);
}
! /* Creates a new invariant for definition DEF in INSN, depending on invariants
! in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
unless the program ends due to a function call. */
static void
! create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
! bool always_executed)
{
struct invariant *inv = xmalloc (sizeof (struct invariant));
! rtx set = single_set (insn);
inv->def = def;
inv->always_executed = always_executed;
*************** create_new_invariant (struct def *def, b
*** 503,509 ****
/* If the set is simple, usually by moving it we move the whole store out of
the loop. Otherwise we save only cost of the computation. */
! if (def->simple_p)
inv->cost = rtx_cost (set, SET);
else
inv->cost = rtx_cost (SET_SRC (set), SET);
--- 326,332 ----
/* If the set is simple, usually by moving it we move the whole store out of
the loop. Otherwise we save only cost of the computation. */
! if (def)
inv->cost = rtx_cost (set, SET);
else
inv->cost = rtx_cost (SET_SRC (set), SET);
*************** create_new_invariant (struct def *def, b
*** 511,529 ****
inv->move = false;
inv->processed = false;
inv->stamp = 0;
! inv->invno = def->invariant = VARRAY_ACTIVE_SIZE (invariants);
VARRAY_PUSH_GENERIC_PTR_NOGC (invariants, inv);
if (rtl_dump_file)
{
- if (def->simple_p)
- fprintf (rtl_dump_file, "Set of register %d", def->regno);
- else
- fprintf (rtl_dump_file, "Set");
fprintf (rtl_dump_file,
! " in insn %d is invariant (%d), cost %d, depends on ",
! INSN_UID (def->insn), def->invariant, inv->cost);
dump_bitmap (rtl_dump_file, inv->depends_on);
}
}
--- 334,351 ----
inv->move = false;
inv->processed = false;
inv->stamp = 0;
+ inv->insn = insn;
! inv->invno = VARRAY_ACTIVE_SIZE (invariants);
! if (def)
! def->invno = inv->invno;
VARRAY_PUSH_GENERIC_PTR_NOGC (invariants, inv);
if (rtl_dump_file)
{
fprintf (rtl_dump_file,
! "Set in insn %d is invariant (%d), cost %d, depends on ",
! INSN_UID (insn), inv->invno, inv->cost);
dump_bitmap (rtl_dump_file, inv->depends_on);
}
}
*************** create_new_invariant (struct def *def, b
*** 531,686 ****
/* Record USE at DEF. */
static void
! record_use (struct def *def, rtx *use)
{
struct use *u = xmalloc (sizeof (struct use));
-
u->pos = use;
u->next = def->uses;
def->uses = u;
def->n_uses++;
}
! /* Gets current definition of REG in INSN and stores it to DEF.
! If it cannot be (uniquely) determined, or the def is not simple,
! false is returned. */
static bool
! get_current_def (rtx reg, rtx insn, struct def **def)
{
! unsigned regno = REGNO (reg);
! basic_block bb;
!
! if (!reg_info[regno].simple_p)
! return false;
!
! if (!reg_info[regno].actual)
{
! /* Only succeed if there is no def of the register at all. */
! if (reg_info[regno].defs)
! return false;
! *def = NULL;
! return true;
! }
!
! *def = reg_info[regno].actual;
! if (!(*def)->simple_p)
! return false;
! bb = BLOCK_FOR_INSN (insn);
! if (!dominated_by_p (CDI_DOMINATORS, bb, (*def)->bb))
! return false;
! if (!(*def)->reg_next)
! return true;
! /* Check that the use dominates the next definition. This ensures that
! it indeed must be reached by the actual one. */
! if (!dominated_by_p (CDI_DOMINATORS, (*def)->reg_next->bb, bb))
! return false;
! /* Still we could have a problem if the use is in the irreducible loop
! together with the next use. */
! if ((bb->flags & BB_IRREDUCIBLE_LOOP)
! && !(*def)->reg_next->simple_p)
! return false;
return true;
}
! /* Records dependencies and uses in X. Dependencies are marked into
! bitmap passed in DATA. If we depend on non-invariant, RD_FAILED
! is set to true. RD_INSN is the current insn. Callback for
! for_each_rtx. */
! static bool rd_failed;
! static rtx rd_insn;
! static int
! record_dependencies_fer (rtx *x, void *data)
{
! bitmap depends_on = data;
! struct def *def = NULL;
! if (!REG_P (*x))
! return 0;
! reg_info[REGNO (*x)].used = true;
! if (!get_current_def (*x, rd_insn, &def))
! {
! if (depends_on)
! rd_failed = true;
! return 0;
! }
! if (!def)
! return 0;
! if (depends_on)
! bitmap_set_bit (depends_on, def->invariant);
! record_use (def, x);
! return 0;
! }
! /* Records dependencies and uses in X. Dependencies are marked into
! bitmap passed in DATA. If we depend on non-invariant, RD_FAILED
! is set to true. Callback for note_uses. */
! static void
! record_dependencies (rtx *x, void *data)
! {
! for_each_rtx (x, record_dependencies_fer, data);
}
! /* Finds invariants in INSN. ALWAYS_EXECUTED is true if the insn is always
! executed, unless the program ends due to a function call. */
static void
! find_invariants_insn (rtx insn, bool always_executed)
{
! struct def *def;
! bitmap depends_on;
! for (def = adef; def && def->insn == insn; def = def->next)
! if (def->invar_rhs)
! break;
! if (def && def->insn == insn)
! depends_on = BITMAP_XMALLOC ();
! else
! depends_on = NULL;
! rd_failed = false;
! rd_insn = insn;
! note_uses (&PATTERN (insn), record_dependencies, depends_on);
! if (rd_failed)
! {
! BITMAP_XFREE (depends_on);
! def->simple_p = false;
! return;
}
- if (!depends_on)
- return;
-
- create_new_invariant (def, depends_on, always_executed);
}
! /* Moves the pointers to the actual definition for defs in INSN. */
static void
! move_actual_defs (rtx insn)
{
! for (; adef && adef->insn == insn; adef = adef->next)
! reg_info[adef->regno].actual = adef;
}
! /* Finds invariants in basic block BB. ALWAYS_EXECUTED is true if the basic
block is always executed, unless the program ends due to a function
! call. */
static void
! find_invariants_bb (basic_block bb, bool always_executed)
{
rtx insn;
--- 353,512 ----
/* Record USE at DEF. */
static void
! record_use (struct def *def, rtx *use, rtx insn)
{
struct use *u = xmalloc (sizeof (struct use));
u->pos = use;
+ u->insn = insn;
u->next = def->uses;
def->uses = u;
def->n_uses++;
}
! /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
! bitmap. DF is the dataflow object. */
static bool
! check_dependencies (rtx insn, struct df *df, bitmap depends_on)
{
! struct df_link *uses, *defs;
! struct ref *use, *def;
! basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
! struct def *def_data;
!
! for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
{
! use = uses->ref;
! defs = DF_REF_CHAIN (use);
! if (!defs)
! continue;
! if (defs->next)
! return false;
! def = defs->ref;
! def_data = DF_REF_DATA (def);
! if (!def_data)
! return false;
! def_bb = DF_REF_BB (def);
! if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
! return false;
! bitmap_set_bit (depends_on, def_data->invno);
! }
return true;
}
! /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
! executed. ALWAYS_EXECUTED is true if the insn is always executed,
! unless the program ends due to a function call. DF is the dataflow
! object. */
! static void
! find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
! struct df *df)
{
! struct ref *ref;
! struct def *def;
! bitmap depends_on;
! rtx set, dest;
! bool simple = true;
! /* Until we get rid of LIBCALLS. */
! if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
! || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
! || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
! return;
!
! set = single_set (insn);
! if (!set)
! return;
! dest = SET_DEST (set);
! if (GET_CODE (dest) != REG
! || HARD_REGISTER_P (dest))
! simple = false;
! if (!check_maybe_invariant (SET_SRC (set))
! || !may_assign_reg_p (SET_DEST (set)))
! return;
! if (!always_reached
! && may_trap_p (insn))
! return;
! depends_on = BITMAP_XMALLOC ();
! if (!check_dependencies (insn, df, depends_on))
! {
! BITMAP_XFREE (depends_on);
! return;
! }
! if (simple)
! {
! ref = df_find_def (df, insn, dest);
! def = xcalloc (1, sizeof (struct def));
! DF_REF_DATA (ref) = def;
! }
! else
! def = NULL;
! create_new_invariant (def, insn, depends_on, always_executed);
}
! /* Record registers used in INSN that have an unique invariant definition.
! DF is the dataflow object. */
static void
! record_uses (rtx insn, struct df *df)
{
! struct df_link *uses, *defs;
! struct ref *use, *def;
! basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
!
! for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
! {
! use = uses->ref;
! defs = DF_REF_CHAIN (use);
! if (!defs || defs->next)
! continue;
! def = defs->ref;
! if (!DF_REF_DATA (def))
! continue;
! def_bb = DF_REF_BB (def);
! if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
! continue;
! record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
}
}
! /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
! executed. ALWAYS_EXECUTED is true if the insn is always executed,
! unless the program ends due to a function call. DF is the dataflow
! object. */
static void
! find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
! struct df *df)
{
! find_invariant_insn (insn, always_reached, always_executed, df);
! record_uses (insn, df);
}
! /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
! basic block is always executed. ALWAYS_EXECUTED is true if the basic
block is always executed, unless the program ends due to a function
! call. DF is the dataflow object. */
static void
! find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
! struct df *df)
{
rtx insn;
*************** find_invariants_bb (basic_block bb, bool
*** 689,723 ****
if (!INSN_P (insn))
continue;
! find_invariants_insn (insn, always_executed);
! move_actual_defs (insn);
}
}
! /* Finds invariants in LOOP with body BODY. ALWAYS_EXECUTED is the bitmap of
! basic blocks in BODY that are always executed, unless the program ends due
! to a function call. */
static void
find_invariants_body (struct loop *loop, basic_block *body,
! bitmap always_executed)
{
unsigned i;
- adef = defs;
for (i = 0; i < loop->num_nodes; i++)
! {
! if (body[i]->loop_father == loop)
! find_invariants_bb (body[i], bitmap_bit_p (always_executed, i));
! else
! move_actual_defs (const0_rtx);
! }
}
! /* Finds invariants in LOOP. */
static void
! find_invariants (struct loop *loop)
{
bitmap may_exit = BITMAP_XMALLOC ();
bitmap always_reached = BITMAP_XMALLOC ();
--- 515,552 ----
if (!INSN_P (insn))
continue;
! find_invariants_insn (insn, always_reached, always_executed, df);
!
! if (always_reached
! && GET_CODE (insn) == CALL_INSN
! && !CONST_OR_PURE_CALL_P (insn))
! always_reached = false;
}
}
! /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
! basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
! bitmap of basic blocks in BODY that are always executed unless the program
! ends due to a function call. DF is the dataflow object. */
static void
find_invariants_body (struct loop *loop, basic_block *body,
! bitmap always_reached, bitmap always_executed,
! struct df *df)
{
unsigned i;
for (i = 0; i < loop->num_nodes; i++)
! find_invariants_bb (body[i],
! bitmap_bit_p (always_reached, i),
! bitmap_bit_p (always_executed, i),
! df);
}
! /* Finds invariants in LOOP. DF is the dataflow object. */
static void
! find_invariants (struct loop *loop, struct df *df)
{
bitmap may_exit = BITMAP_XMALLOC ();
bitmap always_reached = BITMAP_XMALLOC ();
*************** find_invariants (struct loop *loop)
*** 729,736 ****
compute_always_reached (loop, body, may_exit, always_reached);
compute_always_reached (loop, body, has_exit, always_executed);
! find_defs (loop, body, always_reached);
! find_invariants_body (loop, body, always_executed);
BITMAP_XFREE (always_reached);
BITMAP_XFREE (always_executed);
--- 558,565 ----
compute_always_reached (loop, body, may_exit, always_reached);
compute_always_reached (loop, body, has_exit, always_executed);
! find_defs (loop, body, df);
! find_invariants_body (loop, body, always_reached, always_executed, df);
BITMAP_XFREE (always_reached);
BITMAP_XFREE (always_executed);
*************** get_inv_cost (struct invariant *inv, int
*** 774,782 ****
(*regs_needed)++;
(*comp_cost) += inv->cost;
- /* TODO -- in case there is more than one path to the dependency, we count
- its cost multiple times (and we also might have an exponential time
- complexity). Not really likely to occur in practice. */
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno,
{
dep = VARRAY_GENERIC_PTR_NOGC (invariants, depno);
--- 603,608 ----
*************** get_inv_cost (struct invariant *inv, int
*** 784,789 ****
--- 610,619 ----
get_inv_cost (dep, &acomp_cost, &aregs_needed);
if (aregs_needed
+ /* We need to check always_executed, since if the original value of
+ the invariant may be preserved, we may need to keep it in a
+ separate register. TODO check whether the register has an
+ use outside of the loop. */
&& dep->always_executed
&& !dep->def->uses->next)
{
*************** set_move_mark (unsigned invno)
*** 870,879 ****
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, set_move_mark (invno));
}
! /* Determines which invariants to move. */
static void
! find_invariants_to_move (void)
{
unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
struct invariant *inv = NULL;
--- 700,709 ----
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, set_move_mark (invno));
}
! /* Determines which invariants to move. DF is the dataflow object. */
static void
! find_invariants_to_move (struct df *df)
{
unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
struct invariant *inv = NULL;
*************** find_invariants_to_move (void)
*** 900,910 ****
here to stand for induction variables etc. that we do not detect. */
regs_used = 2;
! for (i = 0; i < (unsigned) max_reg_num (); i++)
{
! if (reg_info[i].simple_p
! && !reg_info[i].defs
! && reg_info[i].used)
{
/* This is a value that is used but not changed inside loop. */
regs_used++;
--- 730,738 ----
here to stand for induction variables etc. that we do not detect. */
regs_used = 2;
! for (i = 0; i < df->n_regs; i++)
{
! if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
{
/* This is a value that is used but not changed inside loop. */
regs_used++;
*************** find_invariants_to_move (void)
*** 914,920 ****
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
! n_inv_uses += inv->def->n_uses;
}
new_regs = 0;
--- 742,749 ----
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
! if (inv->def)
! n_inv_uses += inv->def->n_uses;
}
new_regs = 0;
*************** find_invariants_to_move (void)
*** 926,935 ****
}
}
! /* Move invariant INVNO out of the LOOP. */
static void
! move_invariant_reg (struct loop *loop, unsigned invno)
{
struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
unsigned i;
--- 755,764 ----
}
}
! /* Move invariant INVNO out of the LOOP. DF is the dataflow object. */
static void
! move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
{
struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
unsigned i;
*************** move_invariant_reg (struct loop *loop, u
*** 945,951 ****
{
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i,
{
! move_invariant_reg (loop, i);
});
}
--- 774,780 ----
{
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i,
{
! move_invariant_reg (loop, i, df);
});
}
*************** move_invariant_reg (struct loop *loop, u
*** 954,977 ****
loop, but it does not seem worth finding out) and it has no uses that
would not be dominated by it, we may just move it (TODO). Otherwise we
need to create a temporary register. */
! set = single_set (inv->def->insn);
reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
! emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->def->insn);
SET_DEST (set) = reg;
! reorder_insns (inv->def->insn, inv->def->insn, BB_END (preheader));
/* Replace the uses we know to be dominated. It saves work for copy
propagation, and also it is necessary so that dependent invariants
are computed right. */
for (use = inv->def->uses; use; use = use->next)
! *use->pos = reg;
}
/* Move selected invariant out of the LOOP. Newly created regs are marked
! in TEMPORARY_REGS. */
static void
! move_invariants (struct loop *loop)
{
struct invariant *inv;
unsigned i;
--- 783,811 ----
loop, but it does not seem worth finding out) and it has no uses that
would not be dominated by it, we may just move it (TODO). Otherwise we
need to create a temporary register. */
! set = single_set (inv->insn);
reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
! df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
! BLOCK_FOR_INSN (inv->insn), inv->insn);
SET_DEST (set) = reg;
! reorder_insns (inv->insn, inv->insn, BB_END (preheader));
! df_insn_modify (df, preheader, inv->insn);
/* Replace the uses we know to be dominated. It saves work for copy
propagation, and also it is necessary so that dependent invariants
are computed right. */
for (use = inv->def->uses; use; use = use->next)
! {
! *use->pos = reg;
! df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
! }
}
/* Move selected invariant out of the LOOP. Newly created regs are marked
! in TEMPORARY_REGS. DF is the dataflow object. */
static void
! move_invariants (struct loop *loop, struct df *df)
{
struct invariant *inv;
unsigned i;
*************** move_invariants (struct loop *loop)
*** 980,1045 ****
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
if (inv->move)
! move_invariant_reg (loop, i);
}
}
! /* Initializes invariant motion data for LOOP. MAX_REGNO is the maximum
! register number. */
static void
! init_inv_motion_data (struct loop *loop, unsigned max_regno)
{
- unsigned regno;
-
- if (m_reg_info < max_regno)
- {
- m_reg_info = 2 * max_regno;
- reg_info = xrealloc (reg_info, m_reg_info * sizeof (struct reg));
- }
-
- for (regno = 0; regno < max_regno; regno++)
- {
- reg_info[regno].simple_p = true;
- reg_info[regno].used = false;
- reg_info[regno].defs = NULL;
- reg_info[regno].def_end = ®_info[regno].defs;
- reg_info[regno].actual = NULL;
- reg_info[regno].last_bb = loop_preheader_edge (loop)->src;
- }
-
- defs = NULL;
- last_def = &defs;
-
actual_stamp = 1;
if (!invariants)
VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
}
! /* Frees the data allocated by invariant motion. MAX_REGNO is the maximum
! register number before optimization. Store registers that are set inside
! the loop in MODIFIED_REGS. */
static void
! free_inv_motion_data (unsigned max_regno, bitmap modified_regs)
{
! unsigned regno, i;
! struct def *def, *next;
struct invariant *inv;
! for (regno = 0; regno < max_regno; regno++)
{
! if (!reg_info[regno].simple_p
! || reg_info[regno].defs)
! bitmap_set_bit (modified_regs, regno);
! }
- for (def = defs; def; def = next)
- {
- next = def->next;
free_use_list (def->uses);
free (def);
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
--- 814,856 ----
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
if (inv->move)
! move_invariant_reg (loop, i, df);
}
}
! /* Initializes invariant motion data. */
static void
! init_inv_motion_data (void)
{
actual_stamp = 1;
if (!invariants)
VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
}
! /* Frees the data allocated by invariant motion. DF is the dataflow
! object. */
static void
! free_inv_motion_data (struct df *df)
{
! unsigned i;
! struct def *def;
struct invariant *inv;
! for (i = 0; i < df->n_defs; i++)
{
! if (!df->defs[i])
! continue;
!
! def = DF_REF_DATA (df->defs[i]);
! if (!def)
! continue;
free_use_list (def->uses);
free (def);
+ DF_REF_DATA (df->defs[i]) = NULL;
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
*************** free_inv_motion_data (unsigned max_regno
*** 1051,1070 ****
VARRAY_POP_ALL (invariants);
}
! /* Move the invariants out of the LOOP. */
static void
! move_single_loop_invariants (struct loop *loop)
{
! unsigned max_regno = max_reg_num ();
! init_inv_motion_data (loop, max_regno);
! find_invariants (loop);
! find_invariants_to_move ();
! move_invariants (loop);
! LOOP_DATA (loop)->modified_regs = BITMAP_XMALLOC ();
! free_inv_motion_data (max_regno, LOOP_DATA (loop)->modified_regs);
}
/* Releases the auxiliary data for LOOP. */
--- 862,879 ----
VARRAY_POP_ALL (invariants);
}
! /* Move the invariants out of the LOOP. DF is the dataflow object. */
static void
! move_single_loop_invariants (struct loop *loop, struct df *df)
{
! init_inv_motion_data ();
! find_invariants (loop, df);
! find_invariants_to_move (df);
! move_invariants (loop, df);
! free_inv_motion_data (df);
}
/* Releases the auxiliary data for LOOP. */
*************** free_loop_data (struct loop *loop)
*** 1074,1080 ****
{
struct loop_data *data = LOOP_DATA (loop);
! BITMAP_XFREE (data->modified_regs);
loop->aux = NULL;
}
--- 883,889 ----
{
struct loop_data *data = LOOP_DATA (loop);
! free (data);
loop->aux = NULL;
}
*************** move_loop_invariants (struct loops *loop
*** 1085,1096 ****
{
struct loop *loop;
unsigned i;
!
! if (!reg_info)
! {
! m_reg_info = 2 * max_reg_num ();
! reg_info = xmalloc (m_reg_info * sizeof (struct reg));
! }
/* Process the loops, innermost first. */
loop = loops->tree_root;
--- 894,900 ----
{
struct loop *loop;
unsigned i;
! struct df *df = df_init ();
/* Process the loops, innermost first. */
loop = loops->tree_root;
*************** move_loop_invariants (struct loops *loop
*** 1099,1105 ****
while (loop != loops->tree_root)
{
! move_single_loop_invariants (loop);
if (loop->next)
{
--- 903,909 ----
while (loop != loops->tree_root)
{
! move_single_loop_invariants (loop, df);
if (loop->next)
{
*************** move_loop_invariants (struct loops *loop
*** 1114,1117 ****
--- 918,923 ----
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
free_loop_data (loops->parray[i]);
+
+ df_finish (df);
}