/* Dataflow support routines.
- Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005
+ Free Software Foundation, Inc.
Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz,
mhayes@redhat.com)
df = df_init ();
- df_analyse (df, 0, DF_ALL);
+ df_analyze (df, 0, DF_ALL);
df_dump (df, DF_ALL, stderr);
df_init simply creates a poor man's object (df) that needs to be
passed to all the dataflow routines. df_finish destroys this
-object and frees up any allocated memory.
+object and frees up any allocated memory. DF_ALL says to analyze
+everything.
-df_analyse performs the following:
+df_analyze performs the following:
1. Records defs and uses by scanning the insns in each basic block
or by scanning the insns queued by df_insn_modify.
updating then all the changed, new, or deleted insns needs to be
marked with df_insn_modify (or df_insns_modify) either directly or
indirectly (say through calling df_insn_delete). df_insn_modify
-marks all the modified insns to get processed the next time df_analyse
+marks all the modified insns to get processed the next time df_analyze
is called.
Beware that tinkering with insns may invalidate the dataflow information.
The philosophy behind these routines is that once the dataflow
-information has been gathered, the user should store what they require
+information has been gathered, the user should store what they require
before they tinker with any insn. Once a reg is replaced, for example,
then the reg-def/reg-use chains will point to the wrong place. Once a
-whole lot of changes have been made, df_analyse can be called again
+whole lot of changes have been made, df_analyze can be called again
to update the dataflow information. Currently, this is not very smart
with regard to propagating changes to the dataflow so it should not
be called very often.
the reg-def lists contain all the refs that define a given register
while the insn-use lists contain all the refs used by an insn.
-Note that the reg-def and reg-use chains are generally short (except for the
-hard registers) and thus it is much faster to search these chains
-rather than searching the def or use bitmaps.
+Note that the reg-def and reg-use chains are generally short (except for
+the hard registers) and thus it is much faster to search these chains
+rather than searching the def or use bitmaps.
If the insns are in SSA form then the reg-def and use-def lists
should only contain the single defining ref.
+
TODO:
1) Incremental dataflow analysis.
so we do not affect the existing dataflow information.
My current strategy is to queue up all modified, created, or deleted
-insns so when df_analyse is called we can easily determine all the new
+insns so when df_analyze is called we can easily determine all the new
or deleted refs. Currently the global dataflow information is
recomputed from scratch but this could be propagated more efficiently.
-2) Improved global data flow computation using depth first search.
-
-3) Reduced memory requirements.
+2) Reduced memory requirements.
We could operate a pool of ref structures. When a ref is deleted it
gets returned to the pool (say by linking on to a chain of free refs).
periodically squeeze the def and use tables and associated bitmaps and
renumber the def and use ids.
-4) Ordering of reg-def and reg-use lists.
+3) Ordering of reg-def and reg-use lists.
Should the first entry in the def list be the first def (within a BB)?
Similarly, should the first entry in the use list be the last use
-(within a BB)?
+(within a BB)?
+
+4) Working with a sub-CFG.
+
+Often the whole CFG does not need to be analyzed, for example,
+when optimizing a loop, only certain registers are of interest.
+Perhaps there should be a bitmap argument to df_analyze to specify
+which registers should be analyzed?
-5) Working with a sub-CFG.
-Often the whole CFG does not need to be analysed, for example,
-when optimising a loop, only certain registers are of interest.
-Perhaps there should be a bitmap argument to df_analyse to specify
- which registers should be analysed? */
+NOTES:
-#define HANDLE_SUBREG
+Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
+both a use and a def. These are both marked read/write to show that they
+are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
+will generate a use of reg 42 followed by a def of reg 42 (both marked
+read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
+generates a use of reg 41 then a def of reg 41 (both marked read/write),
+even though reg 41 is decremented before it is used for the memory
+address in this second example.
+
+A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
+for which the number of word_mode units covered by the outer mode is
+smaller than that covered by the inner mode, invokes a read-modify-write.
+operation. We generate both a use and a def and again mark them
+read/write.
+Paradoxical subreg writes don't leave a trace of the old content, so they
+are write-only operations. */
#include "config.h"
#include "system.h"
-#include "rtl.h"
-#include "insn-config.h"
-#include "recog.h"
-#include "function.h"
-#include "regs.h"
-#include "obstack.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "function.h"
+#include "regs.h"
+#include "alloc-pool.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+#include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
-
-#define FOR_ALL_BBS(BB, CODE) \
-do { \
- int node_; \
- for (node_ = 0; node_ < n_basic_blocks; node_++) \
- {(BB) = BASIC_BLOCK (node_); CODE;};} while (0)
-
-#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
-do { \
- unsigned int node_; \
- EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
- {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
-
-#define FOR_EACH_BB_IN_BITMAP_REV(BITMAP, MIN, BB, CODE) \
-do { \
- unsigned int node_; \
- EXECUTE_IF_SET_IN_BITMAP_REV (BITMAP, node_, \
- {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
-
-#define FOR_EACH_BB_IN_SBITMAP(BITMAP, MIN, BB, CODE) \
-do { \
- unsigned int node_; \
- EXECUTE_IF_SET_IN_SBITMAP (BITMAP, MIN, node_, \
- {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
-
-#define obstack_chunk_alloc xmalloc
-#define obstack_chunk_free free
-
-static struct obstack df_ref_obstack;
+#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
+ do \
+ { \
+ unsigned int node_; \
+ bitmap_iterator bi; \
+ EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, bi) \
+ { \
+ (BB) = BASIC_BLOCK (node_); \
+ CODE; \
+ } \
+ } \
+ while (0)
+
+static alloc_pool df_ref_pool;
+static alloc_pool df_link_pool;
static struct df *ddf;
-static void df_reg_table_realloc PARAMS((struct df *, int));
-#if 0
-static void df_def_table_realloc PARAMS((struct df *, int));
-#endif
-static void df_insn_table_realloc PARAMS((struct df *, int));
-static void df_bitmaps_alloc PARAMS((struct df *, int));
-static void df_bitmaps_free PARAMS((struct df *, int));
-static void df_free PARAMS((struct df *));
-static void df_alloc PARAMS((struct df *, int));
-
-static rtx df_reg_clobber_gen PARAMS((unsigned int));
-static rtx df_reg_use_gen PARAMS((unsigned int));
-
-static inline struct df_link *df_link_create PARAMS((struct ref *,
- struct df_link *));
-static struct df_link *df_ref_unlink PARAMS((struct df_link **, struct ref *));
-static void df_def_unlink PARAMS((struct df *, struct ref *));
-static void df_use_unlink PARAMS((struct df *, struct ref *));
-static void df_insn_refs_unlink PARAMS ((struct df *, basic_block, rtx));
+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 rtx df_reg_use_gen (unsigned int);
+
+static inline struct df_link *df_link_create (struct ref *, struct df_link *);
+static struct df_link *df_ref_unlink (struct df_link **, struct ref *);
+static void df_def_unlink (struct df *, struct ref *);
+static void df_use_unlink (struct df *, struct ref *);
+static void df_insn_refs_unlink (struct df *, basic_block, rtx);
#if 0
-static void df_bb_refs_unlink PARAMS ((struct df *, basic_block));
-static void df_refs_unlink PARAMS ((struct df *, bitmap));
+static void df_bb_refs_unlink (struct df *, basic_block);
+static void df_refs_unlink (struct df *, bitmap);
#endif
-static struct ref *df_ref_create PARAMS((struct df *,
- rtx, rtx *, basic_block, rtx,
- enum df_ref_type));
-static void df_ref_record_1 PARAMS((struct df *, rtx, rtx *,
- basic_block, rtx, enum df_ref_type));
-static void df_ref_record PARAMS((struct df *, rtx, rtx *,
- basic_block bb, rtx, enum df_ref_type));
-static void df_def_record_1 PARAMS((struct df *, rtx, basic_block, rtx));
-static void df_defs_record PARAMS((struct df *, rtx, basic_block, rtx));
-static void df_uses_record PARAMS((struct df *, rtx *,
- enum df_ref_type, basic_block, rtx));
-static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx));
-static void df_bb_refs_record PARAMS((struct df *, basic_block));
-static void df_refs_record PARAMS((struct df *, bitmap));
-
-static int df_visit_next_rc PARAMS ((struct df *, sbitmap));
-static int df_visit_next_rts PARAMS ((struct df *, sbitmap));
-static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
-static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
-static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
-static void df_reg_use_chain_create PARAMS((struct df *, bitmap));
-static void df_bb_du_chain_create PARAMS((struct df *, basic_block, bitmap));
-static void df_du_chain_create PARAMS((struct df *, bitmap));
-static void df_bb_ud_chain_create PARAMS((struct df *, basic_block));
-static void df_ud_chain_create PARAMS((struct df *, bitmap));
-static void df_rd_global_compute PARAMS((struct df *, bitmap));
-static void df_ru_global_compute PARAMS((struct df *, bitmap));
-static void df_lr_global_compute PARAMS((struct df *, bitmap));
-static void df_bb_rd_local_compute PARAMS((struct df *, basic_block));
-static void df_rd_local_compute PARAMS((struct df *, bitmap));
-static void df_bb_ru_local_compute PARAMS((struct df *, basic_block));
-static void df_ru_local_compute PARAMS((struct df *, bitmap));
-static void df_bb_lr_local_compute PARAMS((struct df *, basic_block));
-static void df_lr_local_compute PARAMS((struct df *, bitmap));
-static void df_bb_reg_info_compute PARAMS((struct df *, basic_block, bitmap));
-static void df_reg_info_compute PARAMS((struct df *, bitmap));
-
-static int df_bb_luids_set PARAMS((struct df *df, basic_block));
-static int df_luids_set PARAMS((struct df *df, bitmap));
-
-static int df_modified_p PARAMS ((struct df *, bitmap));
-static int df_refs_queue PARAMS ((struct df *));
-static int df_refs_process PARAMS ((struct df *));
-static int df_bb_refs_update PARAMS ((struct df *, basic_block));
-static int df_refs_update PARAMS ((struct df *));
-static void df_analyse_1 PARAMS((struct df *, bitmap, int, int));
-
-static void df_insns_modify PARAMS((struct df *, basic_block,
- rtx, rtx));
-static int df_rtx_mem_replace PARAMS ((rtx *, void *));
-static int df_rtx_reg_replace PARAMS ((rtx *, void *));
-void df_refs_reg_replace PARAMS ((struct df *, bitmap,
- struct df_link *, rtx, rtx));
-
-static int df_def_dominates_all_uses_p PARAMS((struct df *, struct ref *def));
-static int df_def_dominates_uses_p PARAMS((struct df *,
- struct ref *def, bitmap));
-static struct ref *df_bb_regno_last_use_find PARAMS((struct df *, basic_block,
- unsigned int));
-static struct ref *df_bb_regno_first_def_find PARAMS((struct df *, basic_block,
- unsigned int));
-static struct ref *df_bb_insn_regno_last_use_find PARAMS((struct df *,
- basic_block,
- rtx, unsigned int));
-static struct ref *df_bb_insn_regno_first_def_find PARAMS((struct df *,
- basic_block,
- rtx, unsigned int));
-
-static void df_chain_dump PARAMS((struct df_link *, FILE *file));
-static void df_chain_dump_regno PARAMS((struct df_link *, FILE *file));
-static void df_regno_debug PARAMS ((struct df *, unsigned int, FILE *));
-static void df_ref_debug PARAMS ((struct df *, struct ref *, FILE *));
+static struct ref *df_ref_create (struct df *, rtx, rtx *, rtx,
+ enum df_ref_type, enum df_ref_flags);
+static void df_ref_record_1 (struct df *, rtx, rtx *, rtx, enum df_ref_type,
+ enum df_ref_flags);
+static void df_ref_record (struct df *, rtx, rtx *, rtx, enum df_ref_type,
+ enum df_ref_flags);
+static void df_def_record_1 (struct df *, rtx, basic_block, rtx);
+static void df_defs_record (struct df *, rtx, basic_block, rtx);
+static void df_uses_record (struct df *, rtx *, enum df_ref_type,
+ basic_block, rtx, enum df_ref_flags);
+static void df_insn_refs_record (struct df *, basic_block, rtx);
+static void df_bb_refs_record (struct df *, basic_block);
+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 void df_ud_chain_create (struct df *, bitmap);
+static void df_bb_rd_local_compute (struct df *, basic_block, bitmap);
+static void df_rd_local_compute (struct df *, bitmap);
+static void df_bb_ru_local_compute (struct df *, basic_block);
+static void df_ru_local_compute (struct df *, bitmap);
+static void df_bb_lr_local_compute (struct df *, basic_block);
+static void df_lr_local_compute (struct df *, bitmap);
+static void df_bb_reg_info_compute (struct df *, basic_block, bitmap);
+static void df_reg_info_compute (struct df *, bitmap);
+
+static int df_bb_luids_set (struct df *df, basic_block);
+static int df_luids_set (struct df *df, bitmap);
+
+static int df_modified_p (struct df *, bitmap);
+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_analyze_1 (struct df *, bitmap, int, int);
+
+static void df_insns_modify (struct df *, basic_block, rtx, rtx);
+static int df_rtx_mem_replace (rtx *, void *);
+static int df_rtx_reg_replace (rtx *, void *);
+void df_refs_reg_replace (struct df *, bitmap, struct df_link *, rtx, rtx);
+
+static int df_def_dominates_all_uses_p (struct df *, struct ref *def);
+static int df_def_dominates_uses_p (struct df *, struct ref *def, bitmap);
+static struct ref *df_bb_insn_regno_last_use_find (struct df *, basic_block,
+ rtx, unsigned int);
+static struct ref *df_bb_insn_regno_first_def_find (struct df *, basic_block,
+ rtx, unsigned int);
+
+static void df_chain_dump (struct df_link *, FILE *file);
+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);
\f
/* Local memory allocation/deallocation routines. */
-/* Increase the insn info table by SIZE more elements. */
+/* Increase the insn info table to have space for at least SIZE + 1
+ elements. */
static void
-df_insn_table_realloc (df, size)
- struct df *df;
- int size;
+df_insn_table_realloc (struct df *df, unsigned int size)
{
- /* Make table 25 percent larger by default. */
- if (! size)
- size = df->insn_size / 4;
+ size++;
+ if (size <= df->insn_size)
+ return;
- size += df->insn_size;
-
- df->insns = (struct insn_info *)
- xrealloc (df->insns, size * sizeof (struct insn_info));
-
- memset (df->insns + df->insn_size, 0,
+ /* Make the table a little larger than requested, so we do not need
+ to enlarge it so often. */
+ size += df->insn_size / 4;
+
+ df->insns = xrealloc (df->insns, size * sizeof (struct insn_info));
+
+ memset (df->insns + df->insn_size, 0,
(size - df->insn_size) * sizeof (struct insn_info));
df->insn_size = size;
}
}
+/* Increase the bb info table to have space for at least SIZE + 1
+ elements. */
-/* Increase the reg info table by SIZE more elements. */
static void
-df_reg_table_realloc (df, size)
- struct df *df;
- int size;
+df_bb_table_realloc (struct df *df, unsigned int size)
{
- /* Make table 25 percent larger by default. */
- if (! size)
- size = df->reg_size / 4;
+ size++;
+ if (size <= df->n_bbs)
+ return;
- size += df->reg_size;
+ /* Make the table a little larger than requested, so we do not need
+ to enlarge it so often. */
+ size += df->n_bbs / 4;
- df->regs = (struct reg_info *)
- xrealloc (df->regs, size * sizeof (struct reg_info));
+ df->bbs = xrealloc (df->bbs, size * sizeof (struct bb_info));
- /* Zero the new entries. */
- memset (df->regs + df->reg_size, 0,
- (size - df->reg_size) * sizeof (struct reg_info));
+ memset (df->bbs + df->n_bbs, 0, (size - df->n_bbs) * sizeof (struct bb_info));
- df->reg_size = size;
+ df->n_bbs = size;
}
-
-#if 0
-/* Not currently used. */
+/* Increase the reg info table by SIZE more elements. */
static void
-df_def_table_realloc (df, size)
- struct df *df;
- int size;
+df_reg_table_realloc (struct df *df, int size)
{
- int i;
- struct ref *refs;
-
/* Make table 25 percent larger by default. */
if (! size)
- size = df->def_size / 4;
+ size = df->reg_size / 4;
- df->def_size += size;
- df->defs = xrealloc (df->defs,
- df->def_size * sizeof (*df->defs));
+ size += df->reg_size;
+ if (size < max_reg_num ())
+ size = max_reg_num ();
- /* Allocate a new block of memory and link into list of blocks
- that will need to be freed later. */
+ df->regs = xrealloc (df->regs, size * sizeof (struct reg_info));
+ df->reg_def_last = xrealloc (df->reg_def_last,
+ size * sizeof (struct ref *));
- refs = xmalloc (size * sizeof (*refs));
-
- /* Link all the new refs together, overloading the chain field. */
- for (i = 0; i < size - 1; i++)
- refs[i].chain = (struct df_link *)(refs + i + 1);
- refs[size - 1].chain = 0;
-}
-#endif
+ /* Zero the new entries. */
+ memset (df->regs + df->reg_size, 0,
+ (size - df->reg_size) * sizeof (struct reg_info));
+ df->reg_size = size;
+}
/* Allocate bitmaps for each basic block. */
+
static void
-df_bitmaps_alloc (df, flags)
- struct df *df;
- int flags;
+df_bitmaps_alloc (struct df *df, bitmap blocks, int flags)
{
- unsigned int i;
- int dflags = 0;
-
- /* 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);
+ basic_block bb;
df->n_defs = df->def_id;
df->n_uses = df->use_id;
- for (i = 0; i < df->n_bbs; i++)
+ if (!blocks)
+ blocks = df->all_blocks;
+
+ FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
- basic_block bb = BASIC_BLOCK (i);
struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
- if (flags & DF_RD && ! bb_info->rd_in)
+
+ if (flags & DF_RD)
{
- /* 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 (!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 && ! bb_info->ru_in)
+ if (flags & DF_RU)
{
- /* 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 (!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 && ! bb_info->lr_in)
+ if (flags & DF_LR)
{
- /* 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;
+ 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);
+ }
}
- }
+ });
}
/* Free bitmaps for each basic block. */
static void
-df_bitmaps_free (df, flags)
- struct df *df ATTRIBUTE_UNUSED;
- int flags;
+df_bitmaps_free (struct df *df, int flags)
{
- unsigned int i;
+ basic_block bb;
- for (i = 0; i < df->n_bbs; i++)
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (!bb_info)
}
-/* Allocate and initialise dataflow memory. */
+/* Allocate and initialize dataflow memory. */
static void
-df_alloc (df, n_regs)
- struct df *df;
- int n_regs;
+df_alloc (struct df *df, int n_regs)
{
int n_insns;
- int i;
+ basic_block bb;
- gcc_obstack_init (&df_ref_obstack);
+ df_link_pool = create_alloc_pool ("df_link pool", sizeof (struct df_link),
+ 100);
+ df_ref_pool = create_alloc_pool ("df_ref pool", sizeof (struct ref), 100);
/* Perhaps we should use LUIDs to save memory for the insn_refs
table. This is only a small saving; a few pointers. */
df->uses = xmalloc (df->use_size * sizeof (*df->uses));
df->n_regs = n_regs;
- df->n_bbs = n_basic_blocks;
+ 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);
df->flags = 0;
- df->bbs = xcalloc (df->n_bbs, sizeof (struct bb_info));
+ df->bbs = xcalloc (last_basic_block, sizeof (struct bb_info));
df->all_blocks = BITMAP_XMALLOC ();
- for (i = 0; i < n_basic_blocks; i++)
- bitmap_set_bit (df->all_blocks, i);
+ FOR_EACH_BB (bb)
+ bitmap_set_bit (df->all_blocks, bb->index);
}
/* Free all the dataflow info. */
static void
-df_free (df)
- struct df *df;
+df_free (struct df *df)
{
df_bitmaps_free (df, DF_ALL);
df->regs = 0;
df->reg_size = 0;
- if (df->bbs_modified)
- BITMAP_XFREE (df->bbs_modified);
+ BITMAP_XFREE (df->bbs_modified);
df->bbs_modified = 0;
- if (df->insns_modified)
- BITMAP_XFREE (df->insns_modified);
+ BITMAP_XFREE (df->insns_modified);
df->insns_modified = 0;
BITMAP_XFREE (df->all_blocks);
df->all_blocks = 0;
- obstack_free (&df_ref_obstack, NULL);
+ free_alloc_pool (df_ref_pool);
+ free_alloc_pool (df_link_pool);
}
\f
/* Local miscellaneous routines. */
/* Return a USE for register REGNO. */
-static rtx df_reg_use_gen (regno)
- unsigned int regno;
-{
- rtx reg;
- rtx use;
-
- reg = regno >= FIRST_PSEUDO_REGISTER
- ? regno_reg_rtx[regno] : gen_rtx_REG (reg_raw_mode[regno], regno);
-
- use = gen_rtx_USE (GET_MODE (reg), reg);
- return use;
-}
-
-
-/* Return a CLOBBER for register REGNO. */
-static rtx df_reg_clobber_gen (regno)
- unsigned int regno;
+static rtx df_reg_use_gen (unsigned int regno)
{
rtx reg;
rtx use;
- reg = regno >= FIRST_PSEUDO_REGISTER
- ? regno_reg_rtx[regno] : gen_rtx_REG (reg_raw_mode[regno], regno);
+ reg = regno_reg_rtx[regno];
- use = gen_rtx_CLOBBER (GET_MODE (reg), reg);
+ use = gen_rtx_USE (GET_MODE (reg), reg);
return use;
}
\f
/* Create a link in a def-use or use-def chain. */
static inline struct df_link *
-df_link_create (ref, next)
- struct ref *ref;
- struct df_link *next;
+df_link_create (struct ref *ref, struct df_link *next)
{
struct df_link *link;
- link = (struct df_link *) obstack_alloc (&df_ref_obstack,
- sizeof (*link));
+ link = pool_alloc (df_link_pool);
link->next = next;
link->ref = ref;
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_unlink (phead, ref)
- struct df_link **phead;
- struct ref *ref;
+df_ref_unlink (struct df_link **phead, struct ref *ref)
{
struct df_link *link = *phead;
/* Only a single ref. It must be the one we want.
If not, the def-use and use-def chains are likely to
be inconsistent. */
- if (link->ref != ref)
- abort ();
+ gcc_assert (link->ref == ref);
+
/* Now have an empty chain. */
*phead = NULL;
}
/* Unlink REF from all def-use/use-def chains, etc. */
int
-df_ref_remove (df, ref)
- struct df *df;
- struct ref *ref;
+df_ref_remove (struct df *df, struct ref *ref)
{
if (DF_REF_REG_DEF_P (ref))
{
/* Unlink DEF from use-def and reg-def chains. */
-static void
-df_def_unlink (df, def)
- struct df *df ATTRIBUTE_UNUSED;
- struct ref *def;
+static void
+df_def_unlink (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
{
struct df_link *du_link;
unsigned int dregno = DF_REF_REGNO (def);
/* Unlink use from def-use and reg-use chains. */
-static void
-df_use_unlink (df, use)
- struct df *df ATTRIBUTE_UNUSED;
- struct ref *use;
+static void
+df_use_unlink (struct df *df ATTRIBUTE_UNUSED, struct ref *use)
{
struct df_link *ud_link;
unsigned int uregno = DF_REF_REGNO (use);
/* Create a new ref of type DF_REF_TYPE for register REG at address
LOC within INSN of BB. */
static struct ref *
-df_ref_create (df, reg, loc, bb, insn, ref_type)
- struct df *df;
- rtx reg;
- rtx *loc;
- basic_block bb;
- rtx insn;
- enum df_ref_type ref_type;
+df_ref_create (struct df *df, rtx reg, rtx *loc, rtx insn,
+ enum df_ref_type ref_type, enum df_ref_flags ref_flags)
{
struct ref *this_ref;
- unsigned int uid;
-
- this_ref = (struct ref *) obstack_alloc (&df_ref_obstack,
- sizeof (*this_ref));
+
+ this_ref = pool_alloc (df_ref_pool);
DF_REF_REG (this_ref) = reg;
DF_REF_LOC (this_ref) = loc;
- DF_REF_BB (this_ref) = bb;
DF_REF_INSN (this_ref) = insn;
DF_REF_CHAIN (this_ref) = 0;
DF_REF_TYPE (this_ref) = ref_type;
- uid = INSN_UID (insn);
+ DF_REF_FLAGS (this_ref) = ref_flags;
+ DF_REF_DATA (this_ref) = NULL;
if (ref_type == DF_REF_REG_DEF)
{
{
/* Make table 25 percent larger. */
df->def_size += (df->def_size / 4);
- df->defs = xrealloc (df->defs,
+ df->defs = xrealloc (df->defs,
df->def_size * sizeof (*df->defs));
}
DF_REF_ID (this_ref) = df->def_id;
{
/* Make table 25 percent larger. */
df->use_size += (df->use_size / 4);
- df->uses = xrealloc (df->uses,
+ df->uses = xrealloc (df->uses,
df->use_size * sizeof (*df->uses));
}
DF_REF_ID (this_ref) = df->use_id;
/* Create a new reference of type DF_REF_TYPE for a single register REG,
used inside the LOC rtx of INSN. */
static void
-df_ref_record_1 (df, reg, loc, bb, insn, ref_type)
- struct df *df;
- rtx reg;
- rtx *loc;
- basic_block bb;
- rtx insn;
- enum df_ref_type ref_type;
+df_ref_record_1 (struct df *df, rtx reg, rtx *loc, rtx insn,
+ enum df_ref_type ref_type, enum df_ref_flags ref_flags)
{
- df_ref_create (df, reg, loc, bb, insn, ref_type);
+ df_ref_create (df, reg, loc, insn, ref_type, ref_flags);
}
/* Create new references of type DF_REF_TYPE for each part of register REG
at address LOC within INSN of BB. */
static void
-df_ref_record (df, reg, loc, bb, insn, ref_type)
- struct df *df;
- rtx reg;
- rtx *loc;
- basic_block bb;
- rtx insn;
- enum df_ref_type ref_type;
+df_ref_record (struct df *df, rtx reg, rtx *loc, rtx insn,
+ enum df_ref_type ref_type, enum df_ref_flags ref_flags)
{
unsigned int regno;
- if (GET_CODE (reg) != REG && GET_CODE (reg) != SUBREG)
- abort ();
+ gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
/* For the reg allocator we are interested in some SUBREG rtx's, but not
all. Notably only those representing a word extraction from a multi-word
XXX Is that true? We could also use the global word_mode variable. */
if (GET_CODE (reg) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (reg)) < GET_MODE_SIZE (word_mode)
- || GET_MODE_SIZE (GET_MODE (reg))
+ || GET_MODE_SIZE (GET_MODE (reg))
>= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg)))))
{
loc = &SUBREG_REG (reg);
reg = *loc;
+ ref_flags |= DF_REF_STRIPPED;
}
regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
{
int i;
int endregno;
-
+
if (! (df->flags & DF_HARD_REGS))
return;
- /* GET_MODE (reg) is correct here. We don't want to go into a SUBREG
+ /* GET_MODE (reg) is correct here. We do not want to go into a SUBREG
for the mode, because we only want to add references to regs, which
- are really referenced. E.g. a (subreg:SI (reg:DI 0) 0) does _not_
+ are really referenced. E.g., a (subreg:SI (reg:DI 0) 0) does _not_
reference the whole reg 0 in DI mode (which would also include
reg 1, at least, if 0 and 1 are SImode registers). */
- endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ endregno = hard_regno_nregs[regno][GET_MODE (reg)];
+ if (GET_CODE (reg) == SUBREG)
+ regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
+ SUBREG_BYTE (reg), GET_MODE (reg));
+ endregno += regno;
for (i = regno; i < endregno; i++)
- df_ref_record_1 (df, gen_rtx_REG (reg_raw_mode[i], i),
- loc, bb, insn, ref_type);
+ df_ref_record_1 (df, regno_reg_rtx[i],
+ loc, insn, ref_type, ref_flags);
}
else
{
- df_ref_record_1 (df, reg, loc, bb, insn, ref_type);
+ df_ref_record_1 (df, reg, loc, insn, ref_type, ref_flags);
}
}
+/* A set to a non-paradoxical SUBREG for which the number of word_mode units
+ covered by the outer mode is smaller than that covered by the inner mode,
+ is a read-modify-write operation.
+ This function returns true iff the SUBREG X is such a SUBREG. */
+bool
+read_modify_subreg_p (rtx x)
+{
+ unsigned int isize, osize;
+ if (GET_CODE (x) != SUBREG)
+ return false;
+ isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
+ osize = GET_MODE_SIZE (GET_MODE (x));
+ return (isize > osize && isize > UNITS_PER_WORD);
+}
+
+
/* Process all the registers defined in the rtx, X. */
static void
-df_def_record_1 (df, x, bb, insn)
- struct df *df;
- rtx x;
- basic_block bb;
- rtx insn;
+df_def_record_1 (struct df *df, rtx x, basic_block bb, rtx insn)
{
- rtx *loc = &SET_DEST (x);
- rtx dst = *loc;
+ rtx *loc;
+ rtx dst;
+ enum df_ref_flags flags = 0;
+
+ /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
+ construct. */
+ if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
+ loc = &XEXP (x, 0);
+ else
+ loc = &SET_DEST (x);
+ dst = *loc;
/* Some targets place small structures in registers for
return values of functions. */
int i;
for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
- df_def_record_1 (df, XVECEXP (dst, 0, i), bb, insn);
+ {
+ rtx temp = XVECEXP (dst, 0, i);
+ if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
+ || GET_CODE (temp) == SET)
+ df_def_record_1 (df, temp, bb, insn);
+ }
return;
}
- /* May be, we should flag the use of strict_low_part somehow. Might be
- handy for the reg allocator. */
-#ifdef HANDLE_SUBREG
+ /* Maybe, we should flag the use of STRICT_LOW_PART somehow. It might
+ be handy for the reg allocator. */
while (GET_CODE (dst) == STRICT_LOW_PART
- || GET_CODE (dst) == ZERO_EXTRACT
- || GET_CODE (dst) == SIGN_EXTRACT)
- {
- loc = &XEXP (dst, 0);
- dst = *loc;
- }
- /* For the reg allocator we are interested in exact register references.
- This means, we want to know, if only a part of a register is
- used/defd. */
-/*
- if (GET_CODE (dst) == SUBREG)
- {
- loc = &XEXP (dst, 0);
- dst = *loc;
- } */
-#else
-
- while (GET_CODE (dst) == SUBREG
|| GET_CODE (dst) == ZERO_EXTRACT
- || GET_CODE (dst) == SIGN_EXTRACT
- || GET_CODE (dst) == STRICT_LOW_PART)
+ || read_modify_subreg_p (dst))
{
+ /* Strict low part always contains SUBREG, but we do not want to make
+ it appear outside, as whole register is always considered. */
+ if (GET_CODE (dst) == STRICT_LOW_PART)
+ {
+ loc = &XEXP (dst, 0);
+ dst = *loc;
+ }
loc = &XEXP (dst, 0);
dst = *loc;
+ flags |= DF_REF_READ_WRITE;
}
-#endif
- if (GET_CODE (dst) == REG
- || (GET_CODE (dst) == SUBREG && GET_CODE (SUBREG_REG (dst)) == REG))
- df_ref_record (df, dst, loc, bb, insn, DF_REF_REG_DEF);
+ if (REG_P (dst)
+ || (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))))
+ df_ref_record (df, dst, loc, insn, DF_REF_REG_DEF, flags);
}
/* Process all the registers defined in the pattern rtx, X. */
static void
-df_defs_record (df, x, bb, insn)
- struct df *df;
- rtx x;
- basic_block bb;
- rtx insn;
+df_defs_record (struct df *df, rtx x, basic_block bb, rtx insn)
{
RTX_CODE code = GET_CODE (x);
/* Process all the registers used in the rtx at address LOC. */
static void
-df_uses_record (df, loc, ref_type, bb, insn)
- struct df *df;
- rtx *loc;
- enum df_ref_type ref_type;
- basic_block bb;
- rtx insn;
+df_uses_record (struct df *df, rtx *loc, enum df_ref_type ref_type,
+ basic_block bb, rtx insn, enum df_ref_flags flags)
{
RTX_CODE code;
rtx x;
-
retry:
x = *loc;
+ if (!x)
+ return;
code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case PC:
+ case CC0:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return;
case CLOBBER:
/* If we are clobbering a MEM, mark any registers inside the address
as being used. */
- if (GET_CODE (XEXP (x, 0)) == MEM)
- df_uses_record (df, &XEXP (XEXP (x, 0), 0),
- DF_REF_REG_MEM_STORE, bb, insn);
+ if (MEM_P (XEXP (x, 0)))
+ df_uses_record (df, &XEXP (XEXP (x, 0), 0),
+ DF_REF_REG_MEM_STORE, bb, insn, flags);
/* If we're clobbering a REG then we have a def so ignore. */
return;
case MEM:
- df_uses_record (df, &XEXP (x, 0), DF_REF_REG_MEM_LOAD, bb, insn);
+ df_uses_record (df, &XEXP (x, 0), DF_REF_REG_MEM_LOAD, bb, insn, 0);
return;
case SUBREG:
/* While we're here, optimize this case. */
-#if defined(HANDLE_SUBREG)
- /* In case the SUBREG is not of a register, don't optimize. */
- if (GET_CODE (SUBREG_REG (x)) != REG)
+ /* In case the SUBREG is not of a REG, do not optimize. */
+ if (!REG_P (SUBREG_REG (x)))
{
loc = &SUBREG_REG (x);
- df_uses_record (df, loc, ref_type, bb, insn);
- return;
- }
-#else
- loc = &SUBREG_REG (x);
- x = *loc;
- if (GET_CODE (x) != REG)
- {
- df_uses_record (df, loc, ref_type, bb, insn);
+ df_uses_record (df, loc, ref_type, bb, insn, flags);
return;
}
-#endif
-
/* ... Fall through ... */
case REG:
- /* See a register (or subreg) other than being set. */
- df_ref_record (df, x, loc, bb, insn, ref_type);
+ df_ref_record (df, x, loc, insn, ref_type, flags);
return;
case SET:
{
rtx dst = SET_DEST (x);
- int use_dst = 0;
- /* If storing into MEM, don't show it as being used. But do
- show the address as being used. */
- if (GET_CODE (dst) == MEM)
- {
- df_uses_record (df, &XEXP (dst, 0),
- DF_REF_REG_MEM_STORE,
- bb, insn);
- df_uses_record (df, &SET_SRC (x), DF_REF_REG_USE, bb, insn);
- return;
- }
-
-#if 1 && defined(HANDLE_SUBREG)
- /* Look for sets that perform a read-modify-write. */
- while (GET_CODE (dst) == STRICT_LOW_PART
- || GET_CODE (dst) == ZERO_EXTRACT
- || GET_CODE (dst) == SIGN_EXTRACT)
- {
- if (GET_CODE (dst) == STRICT_LOW_PART)
- {
- dst = XEXP (dst, 0);
- if (GET_CODE (dst) != SUBREG)
- abort ();
- /* A strict_low_part uses the whole reg not only the subreg. */
- df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb, insn);
- }
- else
- {
- df_uses_record (df, &XEXP (dst, 0), DF_REF_REG_USE, bb, insn);
- dst = XEXP (dst, 0);
- }
- }
- if (GET_CODE (dst) == SUBREG)
- {
- /* Paradoxical or too small subreg's are read-mod-write. */
- if (GET_MODE_SIZE (GET_MODE (dst)) < GET_MODE_SIZE (word_mode)
- || GET_MODE_SIZE (GET_MODE (dst))
- >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
- use_dst = 1;
- }
- /* In the original code also some SUBREG rtx's were considered
- read-modify-write (those with
- REG_SIZE(SUBREG_REG(dst)) > REG_SIZE(dst) )
- e.g. a (subreg:QI (reg:SI A) 0). I can't see this. The only
- reason for a read cycle for reg A would be to somehow preserve
- the bits outside of the subreg:QI. But for this a strict_low_part
- was necessary anyway, and this we handled already. */
-#else
- while (GET_CODE (dst) == STRICT_LOW_PART
- || GET_CODE (dst) == ZERO_EXTRACT
- || GET_CODE (dst) == SIGN_EXTRACT
- || GET_CODE (dst) == SUBREG)
- {
- /* A SUBREG of a smaller size does not use the old value. */
- if (GET_CODE (dst) != SUBREG
- || (REG_SIZE (SUBREG_REG (dst)) > REG_SIZE (dst)))
- use_dst = 1;
- dst = XEXP (dst, 0);
- }
-#endif
+ df_uses_record (df, &SET_SRC (x), DF_REF_REG_USE, bb, insn, 0);
- if ((GET_CODE (dst) == PARALLEL && GET_MODE (dst) == BLKmode)
- || GET_CODE (dst) == REG || GET_CODE (dst) == SUBREG)
+ switch (GET_CODE (dst))
{
-#if 1 || !defined(HANDLE_SUBREG)
- if (use_dst)
- df_uses_record (df, &SET_DEST (x), DF_REF_REG_USE, bb, insn);
-#endif
- df_uses_record (df, &SET_SRC (x), DF_REF_REG_USE, bb, insn);
- return;
+ case SUBREG:
+ if (read_modify_subreg_p (dst))
+ {
+ df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
+ insn, DF_REF_READ_WRITE);
+ break;
+ }
+ /* Fall through. */
+ case REG:
+ case PARALLEL:
+ case PC:
+ case CC0:
+ break;
+ case MEM:
+ df_uses_record (df, &XEXP (dst, 0),
+ DF_REF_REG_MEM_STORE,
+ bb, insn, 0);
+ break;
+ case STRICT_LOW_PART:
+ /* A strict_low_part uses the whole REG and not just the
+ SUBREG. */
+ dst = XEXP (dst, 0);
+ gcc_assert (GET_CODE (dst) == SUBREG);
+ df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
+ insn, DF_REF_READ_WRITE);
+ break;
+ case ZERO_EXTRACT:
+ case SIGN_EXTRACT:
+ df_uses_record (df, &XEXP (dst, 0), DF_REF_REG_USE, bb, insn,
+ DF_REF_READ_WRITE);
+ df_uses_record (df, &XEXP (dst, 1), DF_REF_REG_USE, bb, insn, 0);
+ df_uses_record (df, &XEXP (dst, 2), DF_REF_REG_USE, bb, insn, 0);
+ dst = XEXP (dst, 0);
+ break;
+ default:
+ gcc_unreachable ();
}
+ return;
}
- break;
case RETURN:
break;
Consider for instance a volatile asm that changes the fpu rounding
mode. An insn should not be moved across this even if it only uses
- pseudo-regs because it might give an incorrectly rounded result.
+ pseudo-regs because it might give an incorrectly rounded result.
For now, just mark any regs we can find in ASM_OPERANDS as
used. */
- /* For all ASM_OPERANDS, we must traverse the vector of input operands.
+ /* For all ASM_OPERANDS, we must traverse the vector of input operands.
We can not just fall through here since then we would be confused
by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
traditional asms unlike their normal usage. */
int j;
for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
- df_uses_record (df, &ASM_OPERANDS_INPUT (x, j),
- DF_REF_REG_USE, bb, insn);
+ df_uses_record (df, &ASM_OPERANDS_INPUT (x, j),
+ DF_REF_REG_USE, bb, insn, 0);
return;
}
break;
case PRE_MODIFY:
case POST_MODIFY:
/* Catch the def of the register being modified. */
- df_ref_record (df, XEXP (x, 0), &XEXP (x, 0), bb, insn, DF_REF_REG_DEF);
+ df_ref_record (df, XEXP (x, 0), &XEXP (x, 0), insn, DF_REF_REG_DEF, DF_REF_READ_WRITE);
/* ... Fall through to handle uses ... */
/* Recursively scan the operands of this expression. */
{
- register const char *fmt = GET_RTX_FORMAT (code);
+ const char *fmt = GET_RTX_FORMAT (code);
int i;
-
+
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
loc = &XEXP (x, 0);
goto retry;
}
- df_uses_record (df, &XEXP (x, i), ref_type, bb, insn);
+ df_uses_record (df, &XEXP (x, i), ref_type, bb, insn, flags);
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
df_uses_record (df, &XVECEXP (x, i, j), ref_type,
- bb, insn);
+ bb, insn, flags);
}
}
}
/* Record all the df within INSN of basic block BB. */
static void
-df_insn_refs_record (df, bb, insn)
- struct df *df;
- basic_block bb;
- rtx insn;
+df_insn_refs_record (struct df *df, basic_block bb, rtx insn)
{
int i;
if (INSN_P (insn))
{
- /* Record register defs */
+ rtx note;
+
+ /* Record register defs. */
df_defs_record (df, PATTERN (insn), bb, insn);
-
- if (GET_CODE (insn) == CALL_INSN)
+
+ if (df->flags & DF_EQUIV_NOTES)
+ for (note = REG_NOTES (insn); note;
+ note = XEXP (note, 1))
+ {
+ switch (REG_NOTE_KIND (note))
+ {
+ case REG_EQUIV:
+ case REG_EQUAL:
+ df_uses_record (df, &XEXP (note, 0), DF_REF_REG_USE,
+ bb, insn, 0);
+ default:
+ break;
+ }
+ }
+
+ if (CALL_P (insn))
{
rtx note;
rtx x;
-
+
/* Record the registers used to pass arguments. */
for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
note = XEXP (note, 1))
{
if (GET_CODE (XEXP (note, 0)) == USE)
- df_uses_record (df, &SET_DEST (XEXP (note, 0)), DF_REF_REG_USE,
- bb, insn);
+ df_uses_record (df, &XEXP (XEXP (note, 0), 0), DF_REF_REG_USE,
+ bb, insn, 0);
}
/* The stack ptr is used (honorarily) by a CALL insn. */
x = df_reg_use_gen (STACK_POINTER_REGNUM);
- df_uses_record (df, &SET_DEST (x), DF_REF_REG_USE, bb, insn);
-
+ df_uses_record (df, &XEXP (x, 0), DF_REF_REG_USE, bb, insn, 0);
+
if (df->flags & DF_HARD_REGS)
{
/* Calls may also reference any of the global registers,
if (global_regs[i])
{
x = df_reg_use_gen (i);
- df_uses_record (df, &SET_DEST (x),
- DF_REF_REG_USE, bb, insn);
+ df_uses_record (df, &XEXP (x, 0),
+ DF_REF_REG_USE, bb, insn, 0);
}
}
}
-
+
/* Record the register uses. */
- df_uses_record (df, &PATTERN (insn),
- DF_REF_REG_USE, bb, insn);
-
+ df_uses_record (df, &PATTERN (insn),
+ DF_REF_REG_USE, bb, insn, 0);
- if (GET_CODE (insn) == CALL_INSN)
+ if (CALL_P (insn))
{
rtx note;
- if (df->flags & DF_HARD_REGS)
- {
- /* Kill all registers invalidated by a call. */
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
- {
- rtx reg_clob = df_reg_clobber_gen (i);
- df_defs_record (df, reg_clob, bb, insn);
- }
- }
-
+ /* We do not record hard registers clobbered by the call,
+ since there are awfully many of them and "defs" created
+ through them are not interesting (since no use can be legally
+ reached by them). So we must just make sure we include them when
+ computing kill bitmaps. */
+
/* There may be extra registers to be clobbered. */
for (note = CALL_INSN_FUNCTION_USAGE (insn);
note;
/* Record all the refs within the basic block BB. */
static void
-df_bb_refs_record (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_refs_record (struct df *df, basic_block bb)
{
rtx insn;
/* Scan the block an insn at a time from beginning to end. */
- for (insn = bb->head; ; insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
{
/* Record defs within INSN. */
df_insn_refs_record (df, bb, insn);
}
- if (insn == bb->end)
- break;
}
}
/* Record all the refs in the basic blocks specified by BLOCKS. */
static void
-df_refs_record (df, blocks)
- struct df *df;
- bitmap blocks;
+df_refs_record (struct df *df, bitmap blocks)
{
basic_block bb;
\f
/* 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 (df, bb)
- struct df *df;
- basic_block bb;
+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
- apprear at the start of the chain. */
-
- for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
- insn = PREV_INSN (insn))
+ 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);
if (! INSN_P (insn))
continue;
-
+
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
unsigned int dregno = DF_REF_REGNO (def);
-
- df->regs[dregno].defs
- = df_link_create (def, df->regs[dregno].defs);
+
+ /* Do not add ref's to the chain twice, i.e., only add new
+ refs. XXX the same could be done by testing if the
+ current insn is a modified (or a new) one. This would be
+ faster. */
+ 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. */
+ are a list of definitions for each register. If REDO is true, add
+ all defs, otherwise just add the new defs. */
+
static void
-df_reg_def_chain_create (df, blocks)
- struct df *df;
- bitmap blocks;
+df_reg_def_chain_create (struct df *df, bitmap blocks, bool redo)
{
basic_block bb;
+#ifdef ENABLE_CHECKING
+ unsigned regno;
+#endif
+ unsigned old_def_id_save = df->def_id_save;
+
+ if (redo)
+ {
+#ifdef ENABLE_CHECKING
+ for (regno = 0; regno < df->n_regs; regno++)
+ gcc_assert (!df->regs[regno].defs);
+#endif
+
+ /* Pretend that all defs are new. */
+ df->def_id_save = 0;
+ }
- FOR_EACH_BB_IN_BITMAP/*_REV*/ (blocks, 0, bb,
+ FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
+
+ df->def_id_save = old_def_id_save;
}
+/* Remove all reg-def chains stored in the dataflow object DF. */
+
+static void
+df_reg_def_chain_clean (struct df *df)
+{
+ unsigned regno;
+
+ for (regno = 0; regno < df->n_regs; regno++)
+ free_reg_ref_chain (&df->regs[regno].defs);
+}
/* 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 (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_reg_use_chain_create (struct df *df, basic_block bb)
{
rtx insn;
-
- /* Scan in forward order so that the last uses appear at the
- start of the chain. */
-
- for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
- insn = NEXT_INSN (insn))
+
+ /* 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);
if (! INSN_P (insn))
continue;
-
+
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
unsigned int uregno = DF_REF_REGNO (use);
-
+
+ /* Do not add ref's to the chain twice, i.e., only add new
+ refs. XXX the same could be done by testing if the
+ current insn is a modified (or a new) one. This would be
+ faster. */
+ if (DF_REF_ID (use) < df->use_id_save)
+ continue;
+
df->regs[uregno].uses
= df_link_create (use, df->regs[uregno].uses);
}
/* Create reg-use chains for each basic block within BLOCKS. These
- are a list of uses for each register. */
+ 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 (df, blocks)
- struct df *df;
- bitmap blocks;
+df_reg_use_chain_create (struct df *df, bitmap blocks, bool redo)
{
basic_block bb;
+#ifdef ENABLE_CHECKING
+ unsigned regno;
+#endif
+ unsigned old_use_id_save = df->use_id_save;
+
+ if (redo)
+ {
+#ifdef ENABLE_CHECKING
+ for (regno = 0; regno < df->n_regs; regno++)
+ gcc_assert (!df->regs[regno].uses);
+#endif
+
+ /* 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;
}
+/* Remove all reg-use chains stored in the dataflow object DF. */
+
+static void
+df_reg_use_chain_clean (struct df *df)
+{
+ unsigned regno;
+
+ for (regno = 0; regno < df->n_regs; regno++)
+ free_reg_ref_chain (&df->regs[regno].uses);
+}
/* Create def-use chains from reaching use bitmaps for basic block BB. */
static void
-df_bb_du_chain_create (df, bb, ru)
- struct df *df;
- basic_block bb;
- bitmap ru;
+df_bb_du_chain_create (struct df *df, basic_block bb, bitmap ru)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
-
+
bitmap_copy (ru, bb_info->ru_out);
-
+
/* For each def in BB create a linked list (chain) of uses
reached from the def. */
- for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
- insn = PREV_INSN (insn))
+ FOR_BB_INSNS_REVERSE (bb, insn)
{
struct df_link *def_link;
struct df_link *use_link;
if (! INSN_P (insn))
continue;
-
+
/* For each def in insn... */
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
unsigned int dregno = DF_REF_REGNO (def);
-
+
DF_REF_CHAIN (def) = 0;
/* While the reg-use chains are not essential, it
is _much_ faster to search these short lists rather
than all the reaching uses, especially for large functions. */
- for (use_link = df->regs[dregno].uses; use_link;
+ for (use_link = df->regs[dregno].uses; use_link;
use_link = use_link->next)
{
struct ref *use = use_link->ref;
-
+
if (bitmap_bit_p (ru, DF_REF_ID (use)))
{
- DF_REF_CHAIN (def)
+ DF_REF_CHAIN (def)
= df_link_create (use, DF_REF_CHAIN (def));
-
+
bitmap_clear_bit (ru, DF_REF_ID (use));
}
}
/* Create def-use chains from reaching use bitmaps for basic blocks
in BLOCKS. */
static void
-df_du_chain_create (df, blocks)
- struct df *df;
- bitmap blocks;
+df_du_chain_create (struct df *df, bitmap blocks)
{
bitmap ru;
basic_block bb;
/* Create use-def chains from reaching def bitmaps for basic block BB. */
static void
-df_bb_ud_chain_create (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_ud_chain_create (struct df *df, basic_block bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
struct ref **reg_def_last = df->reg_def_last;
rtx insn;
-
+
memset (reg_def_last, 0, df->n_regs * sizeof (struct ref *));
-
+
/* For each use in BB create a linked list (chain) of defs
that reach the use. */
- for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
- insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *use_link;
if (! INSN_P (insn))
continue;
- /* For each use in insn... */
+ /* For each use in insn... */
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
unsigned int regno = DF_REF_REGNO (use);
-
+
DF_REF_CHAIN (use) = 0;
/* Has regno been defined in this BB yet? If so, use
this BB. */
if (reg_def_last[regno])
{
- DF_REF_CHAIN (use)
+ DF_REF_CHAIN (use)
= df_link_create (reg_def_last[regno], 0);
}
else
_much_ faster to search these short lists rather than
all the reaching defs, especially for large
functions. */
- for (def_link = df->regs[regno].defs; def_link;
+ for (def_link = df->regs[regno].defs; def_link;
def_link = def_link->next)
{
struct ref *def = def_link->ref;
-
+
if (bitmap_bit_p (bb_info->rd_in, DF_REF_ID (def)))
{
- DF_REF_CHAIN (use)
+ DF_REF_CHAIN (use)
= df_link_create (def, DF_REF_CHAIN (use));
}
}
}
}
-
- /* For each def in insn...record the last def of each reg. */
+
+ /* For each def in insn... record the last def of each reg. */
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
int dregno = DF_REF_REGNO (def);
-
+
reg_def_last[dregno] = def;
}
}
/* Create use-def chains from reaching def bitmaps for basic blocks
within BLOCKS. */
static void
-df_ud_chain_create (df, blocks)
- struct df *df;
- bitmap blocks;
+df_ud_chain_create (struct df *df, bitmap blocks)
{
basic_block bb;
}
\f
-/* Use reverse completion order, and the worklist, to figure out what block
- to look at next. */
-static int
-df_visit_next_rc (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- sbitmap blocks;
+static void
+df_rd_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
+ void *out, void *gen, void *kill,
+ void *data ATTRIBUTE_UNUSED)
{
- int i=0;
- for (i = 0; i < n_basic_blocks; i++)
- if (TEST_BIT (blocks, df->rc_order[i]))
- return df->rc_order[i];
- return sbitmap_first_set_bit (blocks);
+ *changed = bitmap_ior_and_compl (out, gen, in, kill);
}
-/* Use reverse topsort order, and the worklist, to figure out what block
- to look at next. */
-static int
-df_visit_next_rts (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- sbitmap blocks;
+static void
+df_ru_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
+ void *out, void *gen, void *kill,
+ void *data ATTRIBUTE_UNUSED)
{
- int i=0;
- for (i = 0; i < n_basic_blocks; i++)
- if (TEST_BIT (blocks, df->rts_order[i]))
- return df->rts_order[i];
- return sbitmap_first_set_bit (blocks);
+ *changed = bitmap_ior_and_compl (in, gen, out, kill);
}
-/* Calculate reaching defs for each basic block in BLOCKS, i.e., the
- defs that are live at the start of a basic block. */
static void
-df_rd_global_compute (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- bitmap blocks;
+df_lr_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
+ void *out, void *use, void *def,
+ void *data ATTRIBUTE_UNUSED)
{
- int i;
- basic_block bb;
- sbitmap worklist;
-
- worklist = sbitmap_alloc (n_basic_blocks);
- sbitmap_zero (worklist);
-
- /* Copy the blocklist to the worklist */
- EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
- {
- SET_BIT (worklist, i);
- });
-
- /* We assume that only the basic blocks in WORKLIST have been
- modified. */
- FOR_EACH_BB_IN_SBITMAP (worklist, 0, bb,
- {
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
- bitmap_copy (bb_info->rd_out, bb_info->rd_gen);
- });
-
- while ((i = df_visit_next_rc (df, worklist)) >= 0)
- {
- struct bb_info *bb_info;
- edge e;
- int changed;
-
- /* Remove this block from the worklist. */
- RESET_BIT (worklist, i);
-
-
- bb = BASIC_BLOCK (i);
- bb_info = DF_BB_INFO (df, bb);
-
- /* Calculate union of predecessor outs. */
- bitmap_zero (bb_info->rd_in);
- for (e = bb->pred; e != 0; e = e->pred_next)
- {
- struct bb_info *pred_refs = DF_BB_INFO (df, e->src);
-
- if (e->src == ENTRY_BLOCK_PTR)
- continue;
-
- bitmap_a_or_b (bb_info->rd_in, bb_info->rd_in,
- pred_refs->rd_out);
- }
-
- /* RD_OUT is the set of defs that are live at the end of the
- BB. These are the defs that are either generated by defs
- (RD_GEN) within the BB or are live at the start (RD_IN)
- and are not killed by other defs (RD_KILL). */
- changed = bitmap_union_of_diff (bb_info->rd_out, bb_info->rd_gen,
- bb_info->rd_in, bb_info->rd_kill);
-
- if (changed)
- {
- /* Add each of this block's successors to the worklist. */
- for (e = bb->succ; e != 0; e = e->succ_next)
- {
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
-
- SET_BIT (worklist, e->dest->index);
- }
- }
- }
- sbitmap_free (worklist);
-}
-
-
-/* Calculate reaching uses for each basic block within BLOCKS, i.e.,
- the uses that are live at the start of a basic block. */
-static void
-df_ru_global_compute (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- bitmap blocks;
-{
- int i;
- basic_block bb;
- sbitmap worklist;
-
- worklist = sbitmap_alloc (n_basic_blocks);
- sbitmap_zero (worklist);
-
- EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
- {
- SET_BIT (worklist, i);
- });
-
- /* We assume that only the basic blocks in WORKLIST have been
- modified. */
- FOR_EACH_BB_IN_SBITMAP (worklist, 0, bb,
- {
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
- bitmap_copy (bb_info->ru_in, bb_info->ru_gen);
- });
-
-
- while ((i = df_visit_next_rts (df, worklist)) >= 0)
- {
- struct bb_info *bb_info;
- edge e;
- int changed;
-
- /* Remove this block from the worklist. */
- RESET_BIT (worklist, i);
-
- bb = BASIC_BLOCK (i);
- bb_info = DF_BB_INFO (df, bb);
-
- /* Calculate union of successor ins. */
- bitmap_zero (bb_info->ru_out);
- for (e = bb->succ; e != 0; e = e->succ_next)
- {
- struct bb_info *succ_refs = DF_BB_INFO (df, e->dest);
-
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
-
- bitmap_a_or_b (bb_info->ru_out, bb_info->ru_out,
- succ_refs->ru_in);
- }
-
- /* RU_IN is the set of uses that are live at the start of the
- BB. These are the uses that are either generated within the
- BB (RU_GEN) or are live at the end (RU_OUT) and are not uses
- killed by defs within the BB (RU_KILL). */
- changed = bitmap_union_of_diff (bb_info->ru_in, bb_info->ru_gen,
- bb_info->ru_out, bb_info->ru_kill);
-
- if (changed)
- {
- /* Add each of this block's predecessors to the worklist. */
- for (e = bb->pred; e != 0; e = e->pred_next)
- {
- if (e->src == ENTRY_BLOCK_PTR)
- continue;
-
- SET_BIT (worklist, e->src->index);
- }
- }
- }
-
- sbitmap_free (worklist);
-}
-
-
-/* Calculate live registers for each basic block within BLOCKS. */
-static void
-df_lr_global_compute (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- bitmap blocks;
-{
- int i;
- basic_block bb;
- bitmap worklist;
-
- worklist = BITMAP_XMALLOC ();
- bitmap_copy (worklist, blocks);
-
- /* We assume that only the basic blocks in WORKLIST have been
- modified. */
- FOR_EACH_BB_IN_BITMAP (worklist, 0, bb,
- {
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
- bitmap_copy (bb_info->lr_in, bb_info->lr_use);
- });
-
- while ((i = bitmap_last_set_bit (worklist)) >= 0)
- {
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
- edge e;
- int changed;
-
- /* Remove this block from the worklist. */
- bitmap_clear_bit (worklist, i);
-
- bb = BASIC_BLOCK (i);
- bb_info = DF_BB_INFO (df, bb);
-
- /* Calculate union of successor ins. */
- bitmap_zero (bb_info->lr_out);
- for (e = bb->succ; e != 0; e = e->succ_next)
- {
- struct bb_info *succ_refs = DF_BB_INFO (df, e->dest);
-
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
-
- bitmap_a_or_b (bb_info->lr_out, bb_info->lr_out,
- succ_refs->lr_in);
- }
-
- /* LR_IN is the set of uses that are live at the start of the
- BB. These are the uses that are either generated by uses
- (LR_USE) within the BB or are live at the end (LR_OUT)
- and are not killed by other uses (LR_DEF). */
- changed = bitmap_union_of_diff (bb_info->lr_in, bb_info->lr_use,
- bb_info->lr_out, bb_info->lr_def);
-
- if (changed)
- {
- /* Add each of this block's predecessors to the worklist. */
- for (e = bb->pred; e != 0; e = e->pred_next)
- {
- if (e->src == ENTRY_BLOCK_PTR)
- continue;
-
- bitmap_set_bit (worklist, e->src->index);
- }
- }
- }
- BITMAP_XFREE (worklist);
+ *changed = bitmap_ior_and_compl (in, use, out, def);
}
/* Compute local reaching def info for basic block BB. */
static void
-df_bb_rd_local_compute (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_rd_local_compute (struct df *df, basic_block bb, bitmap call_killed_defs)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
-
- for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
- insn = NEXT_INSN (insn))
+ bitmap seen = BITMAP_XMALLOC ();
+ bool call_seen = false;
+
+ FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
if (! INSN_P (insn))
continue;
-
+
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
unsigned int regno = DF_REF_REGNO (def);
struct df_link *def2_link;
- for (def2_link = df->regs[regno].defs; def2_link;
+ if (bitmap_bit_p (seen, regno)
+ || (call_seen
+ && regno < FIRST_PSEUDO_REGISTER
+ && TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)))
+ continue;
+
+ for (def2_link = df->regs[regno].defs; def2_link;
def2_link = def2_link->next)
{
struct ref *def2 = def2_link->ref;
be killed by this BB but it keeps things a lot
simpler. */
bitmap_set_bit (bb_info->rd_kill, DF_REF_ID (def2));
-
- /* Zap from the set of gens for this BB. */
- bitmap_clear_bit (bb_info->rd_gen, DF_REF_ID (def2));
}
bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
+ bitmap_set_bit (seen, regno);
+ }
+
+ if (CALL_P (insn) && (df->flags & DF_HARD_REGS))
+ {
+ bitmap_ior_into (bb_info->rd_kill, call_killed_defs);
+ call_seen = 1;
}
}
-
- bb_info->rd_valid = 1;
+
+ BITMAP_XFREE (seen);
}
/* Compute local reaching def info for each basic block within BLOCKS. */
static void
-df_rd_local_compute (df, blocks)
- struct df *df;
- bitmap blocks;
+df_rd_local_compute (struct df *df, bitmap blocks)
{
basic_block bb;
+ bitmap killed_by_call = NULL;
+ unsigned regno;
+ struct df_link *def_link;
+
+ if (df->flags & DF_HARD_REGS)
+ {
+ killed_by_call = BITMAP_XMALLOC ();
+ for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+ {
+ if (!TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ continue;
+
+ for (def_link = df->regs[regno].defs;
+ def_link;
+ def_link = def_link->next)
+ bitmap_set_bit (killed_by_call, DF_REF_ID (def_link->ref));
+ }
+ }
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
- df_bb_rd_local_compute (df, bb);
+ df_bb_rd_local_compute (df, bb, killed_by_call);
});
+
+ if (df->flags & DF_HARD_REGS)
+ BITMAP_XFREE (killed_by_call);
}
/* Compute local reaching use (upward exposed use) info for basic
block BB. */
static void
-df_bb_ru_local_compute (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_ru_local_compute (struct df *df, basic_block bb)
{
/* This is much more tricky than computing reaching defs. With
reaching defs, defs get killed by other defs. With upwards
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
- for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
- insn = PREV_INSN (insn))
+
+ FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
if (! INSN_P (insn))
continue;
-
+
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
unsigned int dregno = DF_REF_REGNO (def);
- for (use_link = df->regs[dregno].uses; use_link;
+ for (use_link = df->regs[dregno].uses; use_link;
use_link = use_link->next)
{
struct ref *use = use_link->ref;
be killed by this BB but it keeps things a lot
simpler. */
bitmap_set_bit (bb_info->ru_kill, DF_REF_ID (use));
-
+
/* Zap from the set of gens for this BB. */
bitmap_clear_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
-
+
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
bitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
- bb_info->ru_valid = 1;
}
/* Compute local reaching use (upward exposed use) info for each basic
block within BLOCKS. */
static void
-df_ru_local_compute (df, blocks)
- struct df *df;
- bitmap blocks;
+df_ru_local_compute (struct df *df, bitmap blocks)
{
basic_block bb;
/* Compute local live variable info for basic block BB. */
static void
-df_bb_lr_local_compute (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_lr_local_compute (struct df *df, basic_block bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
-
- for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
- insn = PREV_INSN (insn))
+
+ FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *link;
if (! INSN_P (insn))
continue;
-
+
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
unsigned int dregno = DF_REF_REGNO (def);
-
+
/* Add def to set of defs in this BB. */
bitmap_set_bit (bb_info->lr_def, dregno);
-
+
bitmap_clear_bit (bb_info->lr_use, dregno);
}
-
+
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
bitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
}
}
- bb_info->lr_valid = 1;
}
/* Compute local live variable info for each basic block within BLOCKS. */
static void
-df_lr_local_compute (df, blocks)
- struct df *df;
- bitmap blocks;
+df_lr_local_compute (struct df *df, bitmap blocks)
{
basic_block bb;
/* Compute register info: lifetime, bb, and number of defs and uses
for basic block BB. */
static void
-df_bb_reg_info_compute (df, bb, live)
- struct df *df;
- basic_block bb;
- bitmap live;
+df_bb_reg_info_compute (struct df *df, basic_block bb, bitmap live)
{
struct reg_info *reg_info = df->regs;
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
-
+
bitmap_copy (live, bb_info->lr_out);
-
- for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
- insn = PREV_INSN (insn))
+
+ FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
struct df_link *link;
-
+ bitmap_iterator bi;
+
if (! INSN_P (insn))
continue;
-
+
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
unsigned int dregno = DF_REF_REGNO (def);
-
+
/* Kill this register. */
bitmap_clear_bit (live, dregno);
reg_info[dregno].n_defs++;
}
-
+
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
unsigned int uregno = DF_REF_REGNO (use);
-
+
/* This register is now live. */
bitmap_set_bit (live, uregno);
reg_info[uregno].n_uses++;
}
-
+
/* Increment lifetimes of all live registers. */
- EXECUTE_IF_SET_IN_BITMAP (live, 0, regno,
- {
- reg_info[regno].lifetime++;
- });
+ EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
+ {
+ reg_info[regno].lifetime++;
+ }
}
}
/* Compute register info: lifetime, bb, and number of defs and uses. */
static void
-df_reg_info_compute (df, blocks)
- struct df *df;
- bitmap blocks;
+df_reg_info_compute (struct df *df, bitmap blocks)
{
basic_block bb;
bitmap live;
/* Assign LUIDs for BB. */
static int
-df_bb_luids_set (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_luids_set (struct df *df, basic_block bb)
{
rtx insn;
int luid = 0;
/* The LUIDs are monotonically increasing for each basic block. */
- for (insn = bb->head; ; insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
DF_INSN_LUID (df, insn) = luid++;
DF_INSN_LUID (df, insn) = luid;
-
- if (insn == bb->end)
- break;
}
return luid;
}
/* Assign LUIDs for each basic block within BLOCKS. */
static int
-df_luids_set (df, blocks)
- struct df *df;
- bitmap blocks;
+df_luids_set (struct df *df, bitmap blocks)
{
basic_block bb;
int total = 0;
/* Perform dataflow analysis using existing DF structure for blocks
within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */
static void
-df_analyse_1 (df, blocks, flags, update)
- struct df *df;
- bitmap blocks;
- int flags;
- int update;
+df_analyze_1 (struct df *df, bitmap blocks, int flags, int update)
{
int aflags;
int dflags;
+ int i;
+ basic_block bb;
+ struct dataflow dflow;
dflags = 0;
aflags = flags;
aflags |= DF_LR;
if (! blocks)
- blocks = df->all_blocks;
+ blocks = df->all_blocks;
df->flags = flags;
if (update)
{
- df_refs_update (df);
+ df_refs_update (df, NULL);
/* More fine grained incremental dataflow analysis would be
nice. For now recompute the whole shebang for the
modified blocks. */
/* 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);
+ df_bitmaps_alloc (df, NULL, aflags);
/* Set the LUIDs for each specified basic block. */
df_luids_set (df, blocks);
regs local to a basic block as it speeds up searching. */
if (aflags & DF_RD_CHAIN)
{
- df_reg_def_chain_create (df, blocks);
+ df_reg_def_chain_create (df, blocks, false);
}
if (aflags & DF_RU_CHAIN)
{
- df_reg_use_chain_create (df, blocks);
+ df_reg_use_chain_create (df, blocks, false);
}
- 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);
-
+ 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);
+ df->inverse_dfs_map = xmalloc (sizeof (int) * last_basic_block);
+ df->inverse_rc_map = xmalloc (sizeof (int) * last_basic_block);
+ df->inverse_rts_map = xmalloc (sizeof (int) * last_basic_block);
+
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
flow_reverse_top_sort_order_compute (df->rts_order);
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ df->inverse_dfs_map[df->dfs_order[i]] = i;
+ df->inverse_rc_map[df->rc_order[i]] = i;
+ df->inverse_rts_map[df->rts_order[i]] = i;
+ }
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;
+ }
- /* Compute the global reaching definitions. */
- df_rd_global_compute (df, df->all_blocks);
+ 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)
if (! (flags & DF_RD))
dflags |= DF_RD;
}
-
+
if (aflags & DF_RU)
{
/* 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);
-
- /* Compute the global reaching uses. */
- df_ru_global_compute (df, 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)
/* Free up bitmaps that are no longer required. */
if (dflags)
- df_bitmaps_free (df, dflags);
+ df_bitmaps_free (df, dflags);
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);
-
- /* Compute the global live variables. */
- df_lr_global_compute (df, 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_reg_info_compute (df, df->all_blocks);
- }
+ }
+
free (df->dfs_order);
free (df->rc_order);
free (df->rts_order);
+ free (df->inverse_rc_map);
+ free (df->inverse_dfs_map);
+ free (df->inverse_rts_map);
}
-/* Initialise dataflow analysis. */
+/* Initialize dataflow analysis. */
struct df *
-df_init ()
+df_init (void)
{
struct df *df;
/* Squirrel away a global for debugging. */
ddf = df;
-
+
return df;
}
/* Start queuing refs. */
static int
-df_refs_queue (df)
- struct df *df;
+df_refs_queue (struct df *df)
{
df->def_id_save = df->def_id;
df->use_id_save = df->use_id;
/* Process queued refs. */
static int
-df_refs_process (df)
- struct df *df;
+df_refs_process (struct df *df)
{
unsigned int i;
/* Update refs for basic block BB. */
-static int
-df_bb_refs_update (df, bb)
- struct df *df;
- basic_block bb;
+static int
+df_bb_refs_update (struct df *df, basic_block bb)
{
rtx insn;
int count = 0;
- /* While we have to scan the chain of insns for this BB, we don't
+ /* While we have to scan the chain of insns for this BB, we do not
need to allocate and queue a long chain of BB/INSN pairs. Using
a bitmap for insns_modified saves memory and avoids queuing
duplicates. */
- for (insn = bb->head; ; insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
{
unsigned int uid;
{
/* Delete any allocated refs of this insn. MPH, FIXME. */
df_insn_refs_unlink (df, bb, insn);
-
+
/* Scan the insn for refs. */
df_insn_refs_record (df, bb, insn);
-
- bitmap_clear_bit (df->insns_modified, uid);
count++;
}
- if (insn == bb->end)
- break;
}
- return count;
-}
+ return count;
+}
+
+
+/* Process all the modified/deleted insns that were queued. */
+static int
+df_refs_update (struct df *df, bitmap blocks)
+{
+ basic_block bb;
+ unsigned 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
+ {
+ bitmap_iterator bi;
+
+ EXECUTE_IF_AND_IN_BITMAP (df->bbs_modified, blocks, 0, bbno, bi)
+ {
+ count += df_bb_refs_update (df, BASIC_BLOCK (bbno));
+ }
+ }
+
+ df_refs_process (df);
+ return count;
+}
+
+
+/* Return nonzero if any of the requested blocks in the bitmap
+ BLOCKS have been modified. */
+static int
+df_modified_p (struct df *df, bitmap blocks)
+{
+ int update = 0;
+ basic_block bb;
+
+ if (!df->n_bbs)
+ return 0;
+
+ FOR_EACH_BB (bb)
+ if (bitmap_bit_p (df->bbs_modified, bb->index)
+ && (! blocks || (blocks == (bitmap) -1) || bitmap_bit_p (blocks, bb->index)))
+ {
+ update = 1;
+ break;
+ }
+
+ 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_analyze (struct df *df, bitmap blocks, int flags)
+{
+ int update;
+
+ /* We could deal with additional basic blocks being created by
+ rescanning everything again. */
+ gcc_assert (!df->n_bbs || df->n_bbs == (unsigned int) last_basic_block);
+
+ update = df_modified_p (df, blocks);
+ if (update || (flags != df->flags))
+ {
+ if (! blocks)
+ {
+ if (df->n_bbs)
+ {
+ /* Recompute everything from scratch. */
+ df_free (df);
+ }
+ /* Allocate and initialize data structures. */
+ df_alloc (df, max_reg_num ());
+ df_analyze_1 (df, 0, flags, 0);
+ update = 1;
+ }
+ else
+ {
+ if (blocks == (bitmap) -1)
+ blocks = df->bbs_modified;
+
+ gcc_assert (df->n_bbs);
+
+ df_analyze_1 (df, blocks, flags, 1);
+ bitmap_zero (df->bbs_modified);
+ bitmap_zero (df->insns_modified);
+ }
+ }
+ 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. Analyze just the part of the cfg
+ graph induced by BLOCKS.
+
+ TODO I am not quite sure how to avoid code duplication with df_analyze_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_analyze_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->flags = flags;
+
+ df_reg_def_chain_clean (df);
+ df_reg_use_chain_clean (df);
+
+ 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);
-/* Process all the modified/deleted insns that were queued. */
-static int
-df_refs_update (df)
- struct df *df;
-{
- basic_block bb;
- int count = 0;
+ flow_depth_first_order_compute (df->dfs_order, df->rc_order);
+ flow_reverse_top_sort_order_compute (df->rts_order);
- if ((unsigned int)max_reg_num () >= df->reg_size)
- df_reg_table_realloc (df, 0);
+ 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);
- df_refs_queue (df);
+ 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);
- FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
+ if (flags & DF_RD)
{
- count += df_bb_refs_update (df, bb);
- });
+ /* Compute the sets of gens and kills for the defs of each bb. */
+ df_rd_local_compute (df, blocks);
- df_refs_process (df);
- return count;
-}
+ 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;
-/* Return non-zero if any of the requested blocks in the bitmap
- BLOCKS have been modified. */
-static int
-df_modified_p (df, blocks)
- struct df *df;
- bitmap blocks;
-{
- unsigned int j;
- int update = 0;
+ iterative_dataflow (&dflow);
+ }
- for (j = 0; j < df->n_bbs; j++)
- if (bitmap_bit_p (df->bbs_modified, j)
- && (! blocks || (blocks == (bitmap) -1) || bitmap_bit_p (blocks, j)))
+ if (flags & DF_UD_CHAIN)
{
- update = 1;
- break;
+ /* Create use-def chains. */
+ df_ud_chain_create (df, blocks);
}
- return update;
-}
+ 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;
+ });
-/* Analyse 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 (df, blocks, flags)
- struct df *df;
- bitmap blocks;
- int flags;
-{
- int update;
+ 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;
- /* We could deal with additional basic blocks being created by
- rescanning everything again. */
- if (df->n_bbs && df->n_bbs != (unsigned int)n_basic_blocks)
- abort ();
+ iterative_dataflow (&dflow);
+ }
- update = df_modified_p (df, blocks);
- if (update || (flags != df->flags))
+ if (flags & DF_DU_CHAIN)
{
- if (! blocks)
+ /* 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)
{
- if (df->n_bbs)
- {
- /* Recompute everything from scratch. */
- df_free (df);
- }
- /* Allocate and initialise data structures. */
- df_alloc (df, max_reg_num ());
- df_analyse_1 (df, 0, flags, 0);
- update = 1;
+ 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;
}
- else
- {
- if (blocks == (bitmap) -1)
- blocks = df->bbs_modified;
- if (! df->n_bbs)
- abort ();
+ 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;
- df_analyse_1 (df, blocks, flags, 1);
- bitmap_zero (df->bbs_modified);
- }
+ iterative_dataflow (&dflow);
}
- return update;
-}
+ 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 (df)
- struct df *df;
+df_finish (struct df *df)
{
df_free (df);
free (df);
}
-
/* Unlink INSN from its reference information. */
static void
-df_insn_refs_unlink (df, bb, insn)
- struct df *df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
+df_insn_refs_unlink (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
{
struct df_link *link;
unsigned int uid;
-
+
uid = INSN_UID (insn);
/* Unlink all refs defined by this insn. */
#if 0
/* Unlink all the insns within BB from their reference information. */
static void
-df_bb_refs_unlink (df, bb)
- struct df *df;
- basic_block bb;
+df_bb_refs_unlink (struct df *df, basic_block bb)
{
rtx insn;
/* Scan the block an insn at a time from beginning to end. */
- for (insn = bb->head; ; insn = NEXT_INSN (insn))
+ for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
/* Unlink refs for INSN. */
df_insn_refs_unlink (df, bb, insn);
}
- if (insn == bb->end)
+ if (insn == BB_END (bb))
break;
}
}
/* Unlink all the refs in the basic blocks specified by BLOCKS.
Not currently used. */
static void
-df_refs_unlink (df, blocks)
- struct df *df;
- bitmap blocks;
+df_refs_unlink (struct df *df, bitmap blocks)
{
basic_block bb;
}
else
{
- FOR_ALL_BBS (bb,
- {
+ FOR_EACH_BB (bb)
df_bb_refs_unlink (df, bb);
- });
}
}
#endif
/* Delete INSN and all its reference information. */
rtx
-df_insn_delete (df, bb, insn)
- struct df *df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
+df_insn_delete (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
{
/* If the insn is a jump, we should perhaps call delete_insn to
handle the JUMP_LABEL? */
/* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label. */
- if (insn == bb->head)
- abort ();
- if (insn == bb->end)
- bb->end = PREV_INSN (insn);
+ gcc_assert (insn != BB_HEAD (bb));
/* Delete the insn. */
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
+ delete_insn (insn);
df_insn_modify (df, bb, insn);
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
harm calling this function if the insn wasn't changed; it will just
slow down the rescanning of refs. */
void
-df_insn_modify (df, bb, insn)
- struct df *df;
- basic_block bb;
- rtx insn;
+df_insn_modify (struct df *df, basic_block bb, rtx insn)
{
unsigned int uid;
uid = INSN_UID (insn);
-
if (uid >= df->insn_size)
- df_insn_table_realloc (df, 0);
+ df_insn_table_realloc (df, uid);
- bitmap_set_bit (df->bbs_modified, bb->index);
+ df_bb_modify (df, bb);
bitmap_set_bit (df->insns_modified, uid);
-#if 0
/* For incremental updating on the fly, perhaps we could make a copy
of all the refs of the original insn and turn them into
anti-refs. When df_refs_update finds these anti-refs, it annihilates
the original refs. If validate_change fails then these anti-refs
will just get ignored. */
- */
-#endif
}
-
typedef struct replace_args
{
rtx match;
instruction currently being scanned and the MEM we are currently
replacing. */
static int
-df_rtx_mem_replace (px, data)
- rtx *px;
- void *data;
+df_rtx_mem_replace (rtx *px, void *data)
{
replace_args *args = (replace_args *) data;
rtx mem = *px;
int
-df_insn_mem_replace (df, bb, insn, mem, reg)
- struct df *df;
- basic_block bb;
- rtx insn;
- rtx mem;
- rtx reg;
+df_insn_mem_replace (struct df *df, basic_block bb, rtx insn, rtx mem, rtx reg)
{
replace_args args;
args.replacement = reg;
args.modified = 0;
- /* Seach and replace all matching mems within insn. */
+ /* Search and replace all matching mems within insn. */
for_each_rtx (&insn, df_rtx_mem_replace, &args);
if (args.modified)
in INSN. REG should be a new pseudo so it won't affect the
dataflow information that we currently have. We should add
the new uses and defs to INSN and then recreate the chains
- when df_analyse is called. */
+ when df_analyze is called. */
return args.modified;
}
points to the rtx being scanned. DATA is actually a pointer to a
structure of arguments. */
static int
-df_rtx_reg_replace (px, data)
- rtx *px;
- void *data;
+df_rtx_reg_replace (rtx *px, void *data)
{
rtx x = *px;
replace_args *args = (replace_args *) data;
BLOCKS of basic blocks with NEWREG. Also update the regs within
REG_NOTES. */
void
-df_refs_reg_replace (df, blocks, chain, oldreg, newreg)
- struct df *df;
- bitmap blocks;
- struct df_link *chain;
- rtx oldreg;
- rtx newreg;
+df_refs_reg_replace (struct df *df, bitmap blocks, struct df_link *chain, rtx oldreg, rtx newreg)
{
struct df_link *link;
replace_args args;
if (! INSN_P (insn))
continue;
- if (bitmap_bit_p (blocks, DF_REF_BBNO (ref)))
- {
- df_ref_reg_replace (df, ref, oldreg, newreg);
+ gcc_assert (bitmap_bit_p (blocks, DF_REF_BBNO (ref)));
+
+ df_ref_reg_replace (df, ref, oldreg, newreg);
- /* Replace occurrences of the reg within the REG_NOTES. */
- if ((! link->next || DF_REF_INSN (ref)
- != DF_REF_INSN (link->next->ref))
- && REG_NOTES (insn))
- {
- args.insn = insn;
- for_each_rtx (®_NOTES (insn), df_rtx_reg_replace, &args);
- }
- }
- else
+ /* Replace occurrences of the reg within the REG_NOTES. */
+ if ((! link->next || DF_REF_INSN (ref)
+ != DF_REF_INSN (link->next->ref))
+ && REG_NOTES (insn))
{
- /* Temporary check to ensure that we have a grip on which
- regs should be replaced. */
- abort ();
+ args.insn = insn;
+ for_each_rtx (®_NOTES (insn), df_rtx_reg_replace, &args);
}
}
}
OLDREG in the REG_NOTES but only for insns containing OLDREG. This
routine expects the reg-use and reg-def chains to be valid. */
int
-df_reg_replace (df, blocks, oldreg, newreg)
- struct df *df;
- bitmap blocks;
- rtx oldreg;
- rtx newreg;
+df_reg_replace (struct df *df, bitmap blocks, rtx oldreg, rtx newreg)
{
unsigned int oldregno = REGNO (oldreg);
/* Try replacing the reg within REF with NEWREG. Do not modify
def-use/use-def chains. */
int
-df_ref_reg_replace (df, ref, oldreg, newreg)
- struct df *df;
- struct ref *ref;
- rtx oldreg;
- rtx newreg;
+df_ref_reg_replace (struct df *df, struct ref *ref, rtx oldreg, rtx newreg)
{
/* Check that insn was deleted by being converted into a NOTE. If
so ignore this insn. */
if (! INSN_P (DF_REF_INSN (ref)))
return 0;
- if (oldreg && oldreg != DF_REF_REG (ref))
- abort ();
+ gcc_assert (!oldreg || oldreg == DF_REF_REG (ref));
if (! validate_change (DF_REF_INSN (ref), DF_REF_LOC (ref), newreg, 1))
return 0;
struct ref*
-df_bb_def_use_swap (df, bb, def_insn, use_insn, regno)
- struct df * df;
- basic_block bb;
- rtx def_insn;
- rtx use_insn;
- unsigned int regno;
+df_bb_def_use_swap (struct df *df, basic_block bb, rtx def_insn, rtx use_insn, unsigned int regno)
{
struct ref *def;
struct ref *use;
}
-/* Record df between FIRST_INSN and LAST_INSN inclusive. All new
+/* Record df between FIRST_INSN and LAST_INSN inclusive. All new
insns must be processed by this routine. */
static void
-df_insns_modify (df, bb, first_insn, last_insn)
- struct df *df;
- basic_block bb;
- rtx first_insn;
- rtx last_insn;
+df_insns_modify (struct df *df, basic_block bb, rtx first_insn, rtx last_insn)
{
rtx insn;
/* A non-const call should not have slipped through the net. If
it does, we need to create a new basic block. Ouch. The
same applies for a label. */
- if ((GET_CODE (insn) == CALL_INSN
- && ! CONST_OR_PURE_CALL_P (insn))
- || GET_CODE (insn) == CODE_LABEL)
- abort ();
+ gcc_assert ((!CALL_P (insn) || CONST_OR_PURE_CALL_P (insn))
+ && !LABEL_P (insn));
uid = INSN_UID (insn);
if (uid >= df->insn_size)
- df_insn_table_realloc (df, 0);
+ df_insn_table_realloc (df, uid);
df_insn_modify (df, bb, insn);
/* Emit PATTERN before INSN within BB. */
rtx
-df_pattern_emit_before (df, pattern, bb, insn)
- struct df *df ATTRIBUTE_UNUSED;
- rtx pattern;
- basic_block bb;
- rtx insn;
+df_pattern_emit_before (struct df *df, rtx pattern, basic_block bb, rtx insn)
{
rtx ret_insn;
rtx prev_insn = PREV_INSN (insn);
/* We should not be inserting before the start of the block. */
- if (insn == bb->head)
- abort ();
+ gcc_assert (insn != BB_HEAD (bb));
ret_insn = emit_insn_before (pattern, insn);
if (ret_insn == insn)
return ret_insn;
-
+
df_insns_modify (df, bb, NEXT_INSN (prev_insn), ret_insn);
return ret_insn;
}
/* Emit PATTERN after INSN within BB. */
rtx
-df_pattern_emit_after (df, pattern, bb, insn)
- struct df *df;
- rtx pattern;
- basic_block bb;
- rtx insn;
+df_pattern_emit_after (struct df *df, rtx pattern, basic_block bb, rtx insn)
{
rtx ret_insn;
/* Emit jump PATTERN after INSN within BB. */
rtx
-df_jump_pattern_emit_after (df, pattern, bb, insn)
- struct df *df;
- rtx pattern;
- basic_block bb;
- rtx insn;
+df_jump_pattern_emit_after (struct df *df, rtx pattern, basic_block bb, rtx insn)
{
rtx ret_insn;
out of a loop where it has been proven that the def-use info
will still be valid. */
rtx
-df_insn_move_before (df, bb, insn, before_bb, before_insn)
- struct df *df;
- basic_block bb;
- rtx insn;
- basic_block before_bb;
- rtx before_insn;
+df_insn_move_before (struct df *df, basic_block bb, rtx insn, basic_block before_bb, rtx before_insn)
{
struct df_link *link;
unsigned int uid;
uid = INSN_UID (insn);
/* Change bb for all df defined and used by this insn. */
- for (link = df->insns[uid].defs; link; link = link->next)
+ for (link = df->insns[uid].defs; link; link = link->next)
DF_REF_BB (link->ref) = before_bb;
- for (link = df->insns[uid].uses; link; link = link->next)
+ for (link = df->insns[uid].uses; link; link = link->next)
DF_REF_BB (link->ref) = before_bb;
/* The lifetimes of the registers used in this insn will be reduced
are likely to be increased. */
/* ???? Perhaps all the insns moved should be stored on a list
- which df_analyse removes when it recalculates data flow. */
+ which df_analyze removes when it recalculates data flow. */
return emit_insn_before (insn, before_insn);
}
int
-df_insn_regno_def_p (df, bb, insn, regno)
- struct df *df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
- unsigned int regno;
+df_insn_regno_def_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
+ rtx insn, unsigned int regno)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
- for (link = df->insns[uid].defs; link; link = link->next)
+ for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
-
+
if (DF_REF_REGNO (def) == regno)
return 1;
}
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;
+}
+
+/* Return 1 if REG is referenced in INSN, zero otherwise. */
+
+int
+df_reg_used (struct df *df, rtx insn, rtx reg)
+{
+ struct df_link *uses;
+
+ for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
+ if (rtx_equal_p (DF_REF_REG (uses->ref), reg))
+ return 1;
+
+ return 0;
+}
static int
-df_def_dominates_all_uses_p (df, def)
- struct df *df ATTRIBUTE_UNUSED;
- struct ref *def;
+df_def_dominates_all_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
{
struct df_link *du_link;
{
struct ref *use = du_link->ref;
struct df_link *ud_link;
-
+
/* Follow use-def chain to check all the defs for this use. */
for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
if (ud_link->ref != def)
int
-df_insn_dominates_all_uses_p (df, bb, insn)
- struct df *df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
+df_insn_dominates_all_uses_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
+ rtx insn)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
- for (link = df->insns[uid].defs; link; link = link->next)
+ for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
-
+
if (! df_def_dominates_all_uses_p (df, def))
return 0;
}
}
-/* Return non-zero if all DF dominates all the uses within the bitmap
+/* Return nonzero if all DF dominates all the uses within the bitmap
BLOCKS. */
static int
-df_def_dominates_uses_p (df, def, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- struct ref *def;
- bitmap blocks;
+df_def_dominates_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def,
+ bitmap blocks)
{
struct df_link *du_link;
}
-/* Return non-zero if all the defs of INSN within BB dominates
+/* Return nonzero if all the defs of INSN within BB dominates
all the corresponding uses. */
int
-df_insn_dominates_uses_p (df, bb, insn, blocks)
- struct df *df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
- bitmap blocks;
+df_insn_dominates_uses_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
+ rtx insn, bitmap blocks)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
- for (link = df->insns[uid].defs; link; link = link->next)
+ for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
/* Return the basic block that REG referenced in or NULL if referenced
in multiple basic blocks. */
basic_block
-df_regno_bb (df, regno)
- struct df *df;
- unsigned int regno;
+df_regno_bb (struct df *df, unsigned int regno)
{
struct df_link *defs = df->regs[regno].defs;
struct df_link *uses = df->regs[regno].uses;
}
-/* Return non-zero if REG used in multiple basic blocks. */
+/* Return nonzero if REG used in multiple basic blocks. */
int
-df_reg_global_p (df, reg)
- struct df *df;
- rtx reg;
+df_reg_global_p (struct df *df, rtx reg)
{
return df_regno_bb (df, REGNO (reg)) != 0;
}
/* Return total lifetime (in insns) of REG. */
int
-df_reg_lifetime (df, reg)
- struct df *df;
- rtx reg;
+df_reg_lifetime (struct df *df, rtx reg)
{
return df->regs[REGNO (reg)].lifetime;
}
-/* Return non-zero if REG live at start of BB. */
+/* Return nonzero if REG live at start of BB. */
int
-df_bb_reg_live_start_p (df, bb, reg)
- struct df *df ATTRIBUTE_UNUSED;
- basic_block bb;
- rtx reg;
+df_bb_reg_live_start_p (struct df *df, basic_block bb, rtx reg)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
-#ifdef ENABLE_CHECKING
- if (! bb_info->lr_in)
- abort ();
-#endif
-
+ gcc_assert (bb_info->lr_in);
+
return bitmap_bit_p (bb_info->lr_in, REGNO (reg));
}
-/* Return non-zero if REG live at end of BB. */
+/* Return nonzero if REG live at end of BB. */
int
-df_bb_reg_live_end_p (df, bb, reg)
- struct df *df ATTRIBUTE_UNUSED;
- basic_block bb;
- rtx reg;
+df_bb_reg_live_end_p (struct df *df, basic_block bb, rtx reg)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
-#ifdef ENABLE_CHECKING
- if (! bb_info->lr_in)
- abort ();
-#endif
+
+ gcc_assert (bb_info->lr_in);
return bitmap_bit_p (bb_info->lr_out, REGNO (reg));
}
/* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
after life of REG2, or 0, if the lives overlap. */
int
-df_bb_regs_lives_compare (df, bb, reg1, reg2)
- struct df *df;
- basic_block bb;
- rtx reg1;
- rtx reg2;
+df_bb_regs_lives_compare (struct df *df, basic_block bb, rtx reg1, rtx reg2)
{
unsigned int regno1 = REGNO (reg1);
unsigned int regno2 = REGNO (reg2);
struct ref *def2;
struct ref *use2;
-
+
/* The regs must be local to BB. */
- if (df_regno_bb (df, regno1) != bb
- || df_regno_bb (df, regno2) != bb)
- abort ();
+ gcc_assert (df_regno_bb (df, regno1) == bb
+ && df_regno_bb (df, regno2) == bb);
def2 = df_bb_regno_first_def_find (df, bb, regno2);
use1 = df_bb_regno_last_use_find (df, bb, regno1);
/* Return last use of REGNO within BB. */
-static struct ref *
-df_bb_regno_last_use_find (df, bb, regno)
- struct df * df;
- basic_block bb ATTRIBUTE_UNUSED;
- unsigned int regno;
+struct ref *
+df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
{
struct df_link *link;
BB, the last use is found first. However, since the BBs are not
ordered, the first use in the chain is not necessarily the last
use in the function. */
- for (link = df->regs[regno].uses; link; link = link->next)
+ for (link = df->regs[regno].uses; link; link = link->next)
{
struct ref *use = link->ref;
/* Return first def of REGNO within BB. */
-static struct ref *
-df_bb_regno_first_def_find (df, bb, regno)
- struct df * df;
- basic_block bb ATTRIBUTE_UNUSED;
- unsigned int regno;
+struct ref *
+df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
{
struct df_link *link;
BB, the first def is found first. However, since the BBs are not
ordered, the first def in the chain is not necessarily the first
def in the function. */
- for (link = df->regs[regno].defs; link; link = link->next)
+ for (link = df->regs[regno].defs; link; link = link->next)
{
struct ref *def = link->ref;
return 0;
}
+/* Return last def of REGNO within BB. */
+struct ref *
+df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
+{
+ struct df_link *link;
+ struct ref *last_def = NULL;
+ int in_bb = 0;
+
+ /* This assumes that the reg-def list is ordered such that for any
+ BB, the first def is found first. However, since the BBs are not
+ ordered, the first def in the chain is not necessarily the first
+ def in the function. */
+ for (link = df->regs[regno].defs; link; link = link->next)
+ {
+ struct ref *def = link->ref;
+ /* The first time in the desired block. */
+ if (DF_REF_BB (def) == bb)
+ in_bb = 1;
+ /* The last def in the desired block. */
+ else if (in_bb)
+ return last_def;
+ last_def = def;
+ }
+ return last_def;
+}
/* Return first use of REGNO inside INSN within BB. */
static struct ref *
-df_bb_insn_regno_last_use_find (df, bb, insn, regno)
- struct df * df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
- unsigned int regno;
+df_bb_insn_regno_last_use_find (struct df *df,
+ basic_block bb ATTRIBUTE_UNUSED, rtx insn,
+ unsigned int regno)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
- for (link = df->insns[uid].uses; link; link = link->next)
+ for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
/* Return first def of REGNO inside INSN within BB. */
static struct ref *
-df_bb_insn_regno_first_def_find (df, bb, insn, regno)
- struct df * df;
- basic_block bb ATTRIBUTE_UNUSED;
- rtx insn;
- unsigned int regno;
+df_bb_insn_regno_first_def_find (struct df *df,
+ basic_block bb ATTRIBUTE_UNUSED, rtx insn,
+ unsigned int regno)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
- for (link = df->insns[uid].defs; link; link = link->next)
+ for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
/* Return insn using REG if the BB contains only a single
use and def of REG. */
rtx
-df_bb_single_def_use_insn_find (df, bb, insn, reg)
- struct df * df;
- basic_block bb;
- rtx insn;
- rtx reg;
+df_bb_single_def_use_insn_find (struct df *df, basic_block bb, rtx insn, rtx reg)
{
struct ref *def;
struct ref *use;
def = df_bb_insn_regno_first_def_find (df, bb, insn, REGNO (reg));
- if (! def)
- abort ();
+ gcc_assert (def);
du_link = DF_REF_CHAIN (def);
/* Check for multiple uses. */
if (du_link->next)
return NULL_RTX;
-
+
return DF_REF_INSN (use);
}
\f
/* Dump a def-use or use-def chain for REF to FILE. */
static void
-df_chain_dump (link, file)
- struct df_link *link;
- FILE *file;
+df_chain_dump (struct df_link *link, FILE *file)
{
fprintf (file, "{ ");
for (; link; link = link->next)
fprintf (file, "}");
}
+
+/* Dump a chain of refs with the associated regno. */
static void
-df_chain_dump_regno (link, file)
- struct df_link *link;
- FILE *file;
+df_chain_dump_regno (struct df_link *link, FILE *file)
{
fprintf (file, "{ ");
for (; link; link = link->next)
{
fprintf (file, "%c%d(%d) ",
- DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
- DF_REF_ID (link->ref),
- DF_REF_REGNO (link->ref));
+ DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
+ DF_REF_ID (link->ref),
+ DF_REF_REGNO (link->ref));
}
fprintf (file, "}");
}
+
/* Dump dataflow info. */
void
-df_dump (df, flags, file)
- struct df *df;
- int flags;
- FILE *file;
+df_dump (struct df *df, int flags, FILE *file)
{
- unsigned int i;
unsigned int j;
+ basic_block bb;
if (! df || ! file)
return;
if (flags & DF_RD)
{
+ basic_block bb;
+
fprintf (file, "Reaching defs:\n");
- for (i = 0; i < df->n_bbs; i++)
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
+ struct bb_info *bb_info = DF_BB_INFO (df, bb);
+
if (! bb_info->rd_in)
continue;
- fprintf (file, "bb %d in \t", i);
+ fprintf (file, "bb %d in \t", bb->index);
dump_bitmap (file, bb_info->rd_in);
- fprintf (file, "bb %d gen \t", i);
+ fprintf (file, "bb %d gen \t", bb->index);
dump_bitmap (file, bb_info->rd_gen);
- fprintf (file, "bb %d kill\t", i);
+ fprintf (file, "bb %d kill\t", bb->index);
dump_bitmap (file, bb_info->rd_kill);
- fprintf (file, "bb %d out \t", i);
+ fprintf (file, "bb %d out \t", bb->index);
dump_bitmap (file, bb_info->rd_out);
}
}
DF_INSN_LUID (df, DF_REF_INSN (df->defs[j])),
DF_REF_INSN_UID (df->defs[j]),
DF_REF_REGNO (df->defs[j]));
+ if (df->defs[j]->flags & DF_REF_READ_WRITE)
+ fprintf (file, "read/write ");
df_chain_dump (DF_REF_CHAIN (df->defs[j]), file);
fprintf (file, "\n");
}
if (flags & DF_RU)
{
fprintf (file, "Reaching uses:\n");
- for (i = 0; i < df->n_bbs; i++)
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
+ struct bb_info *bb_info = DF_BB_INFO (df, bb);
+
if (! bb_info->ru_in)
continue;
- fprintf (file, "bb %d in \t", i);
+ fprintf (file, "bb %d in \t", bb->index);
dump_bitmap (file, bb_info->ru_in);
- fprintf (file, "bb %d gen \t", i);
+ fprintf (file, "bb %d gen \t", bb->index);
dump_bitmap (file, bb_info->ru_gen);
- fprintf (file, "bb %d kill\t", i);
+ fprintf (file, "bb %d kill\t", bb->index);
dump_bitmap (file, bb_info->ru_kill);
- fprintf (file, "bb %d out \t", i);
+ fprintf (file, "bb %d out \t", bb->index);
dump_bitmap (file, bb_info->ru_out);
}
}
DF_INSN_LUID (df, DF_REF_INSN (df->uses[j])),
DF_REF_INSN_UID (df->uses[j]),
DF_REF_REGNO (df->uses[j]));
+ if (df->uses[j]->flags & DF_REF_READ_WRITE)
+ fprintf (file, "read/write ");
df_chain_dump (DF_REF_CHAIN (df->uses[j]), file);
fprintf (file, "\n");
}
if (flags & DF_LR)
{
fprintf (file, "Live regs:\n");
- for (i = 0; i < df->n_bbs; i++)
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
+ struct bb_info *bb_info = DF_BB_INFO (df, bb);
+
if (! bb_info->lr_in)
continue;
- fprintf (file, "bb %d in \t", i);
+ fprintf (file, "bb %d in \t", bb->index);
dump_bitmap (file, bb_info->lr_in);
- fprintf (file, "bb %d use \t", i);
+ fprintf (file, "bb %d use \t", bb->index);
dump_bitmap (file, bb_info->lr_use);
- fprintf (file, "bb %d def \t", i);
+ fprintf (file, "bb %d def \t", bb->index);
dump_bitmap (file, bb_info->lr_def);
- fprintf (file, "bb %d out \t", i);
+ fprintf (file, "bb %d out \t", bb->index);
dump_bitmap (file, bb_info->lr_out);
}
}
fprintf (file, "Register info:\n");
for (j = 0; j < df->n_regs; j++)
{
- if (((flags & DF_REG_INFO)
+ if (((flags & DF_REG_INFO)
&& (reg_info[j].n_uses || reg_info[j].n_defs))
|| ((flags & DF_RD_CHAIN) && reg_info[j].defs)
|| ((flags & DF_RU_CHAIN) && reg_info[j].uses))
- {
- fprintf (file, "reg %d", j);
- if ((flags & DF_RD_CHAIN) && (flags & DF_RU_CHAIN))
- {
- basic_block bb = df_regno_bb (df, j);
-
- if (bb)
- fprintf (file, " bb %d", bb->index);
- else
- fprintf (file, " bb ?");
- }
- if (flags & DF_REG_INFO)
- {
- fprintf (file, " life %d", reg_info[j].lifetime);
- }
+ {
+ fprintf (file, "reg %d", j);
+ if ((flags & DF_RD_CHAIN) && (flags & DF_RU_CHAIN))
+ {
+ basic_block bb = df_regno_bb (df, j);
- if ((flags & DF_REG_INFO) || (flags & DF_RD_CHAIN))
- {
- fprintf (file, " defs ");
- if (flags & DF_REG_INFO)
- fprintf (file, "%d ", reg_info[j].n_defs);
- if (flags & DF_RD_CHAIN)
- df_chain_dump (reg_info[j].defs, file);
- }
+ if (bb)
+ fprintf (file, " bb %d", bb->index);
+ else
+ fprintf (file, " bb ?");
+ }
+ if (flags & DF_REG_INFO)
+ {
+ fprintf (file, " life %d", reg_info[j].lifetime);
+ }
- if ((flags & DF_REG_INFO) || (flags & DF_RU_CHAIN))
- {
- fprintf (file, " uses ");
- if (flags & DF_REG_INFO)
- fprintf (file, "%d ", reg_info[j].n_uses);
- if (flags & DF_RU_CHAIN)
- df_chain_dump (reg_info[j].uses, file);
- }
+ if ((flags & DF_REG_INFO) || (flags & DF_RD_CHAIN))
+ {
+ fprintf (file, " defs ");
+ if (flags & DF_REG_INFO)
+ fprintf (file, "%d ", reg_info[j].n_defs);
+ if (flags & DF_RD_CHAIN)
+ df_chain_dump (reg_info[j].defs, file);
+ }
- fprintf (file, "\n");
- }
+ if ((flags & DF_REG_INFO) || (flags & DF_RU_CHAIN))
+ {
+ fprintf (file, " uses ");
+ if (flags & DF_REG_INFO)
+ fprintf (file, "%d ", reg_info[j].n_uses);
+ if (flags & DF_RU_CHAIN)
+ df_chain_dump (reg_info[j].uses, file);
+ }
+
+ fprintf (file, "\n");
+ }
}
}
fprintf (file, "\n");
void
-df_insn_debug (df, insn, file)
- struct df *df;
- rtx insn;
- FILE *file;
+df_insn_debug (struct df *df, rtx insn, FILE *file)
{
unsigned int uid;
int bbi;
if (df->insns[uid].defs)
bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
- else if (df->insns[uid].uses)
+ else if (df->insns[uid].uses)
bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
else
bbi = -1;
fprintf (file, "\n");
}
+
void
-df_insn_debug_regno (df, insn, file)
- struct df *df;
- rtx insn;
- FILE *file;
+df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
{
unsigned int uid;
int bbi;
if (df->insns[uid].defs)
bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
- else if (df->insns[uid].uses)
+ else if (df->insns[uid].uses)
bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
else
bbi = -1;
fprintf (file, "insn %d bb %d luid %d defs ",
- uid, bbi, DF_INSN_LUID (df, insn));
+ uid, bbi, DF_INSN_LUID (df, insn));
df_chain_dump_regno (df->insns[uid].defs, file);
fprintf (file, " uses ");
df_chain_dump_regno (df->insns[uid].uses, file);
fprintf (file, "\n");
}
+
static void
-df_regno_debug (df, regno, file)
- struct df *df;
- unsigned int regno;
- FILE *file;
+df_regno_debug (struct df *df, unsigned int regno, FILE *file)
{
if (regno >= df->reg_size)
return;
static void
-df_ref_debug (df, ref, file)
- struct df *df;
- struct ref *ref;
- FILE *file;
+df_ref_debug (struct df *df, struct ref *ref, FILE *file)
{
fprintf (file, "%c%d ",
DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
DF_REF_ID (ref));
- fprintf (file, "reg %d bb %d luid %d insn %d chain ",
+ fprintf (file, "reg %d bb %d luid %d insn %d chain ",
DF_REF_REGNO (ref),
- DF_REF_BBNO (ref),
+ DF_REF_BBNO (ref),
DF_INSN_LUID (df, DF_REF_INSN (ref)),
INSN_UID (DF_REF_INSN (ref)));
df_chain_dump (DF_REF_CHAIN (ref), file);
fprintf (file, "\n");
}
+\f
+/* Functions for debugging from GDB. */
-
-void
-debug_df_insn (insn)
- rtx insn;
+void
+debug_df_insn (rtx insn)
{
df_insn_debug (ddf, insn, stderr);
debug_rtx (insn);
}
-void
-debug_df_reg (reg)
- rtx reg;
+void
+debug_df_reg (rtx reg)
{
df_regno_debug (ddf, REGNO (reg), stderr);
}
-void
-debug_df_regno (regno)
- unsigned int regno;
+void
+debug_df_regno (unsigned int regno)
{
df_regno_debug (ddf, regno, stderr);
}
-void
-debug_df_ref (ref)
- struct ref *ref;
+void
+debug_df_ref (struct ref *ref)
{
df_ref_debug (ddf, ref, stderr);
}
-void
-debug_df_defno (defno)
- unsigned int defno;
+void
+debug_df_defno (unsigned int defno)
{
df_ref_debug (ddf, ddf->defs[defno], stderr);
}
-void
-debug_df_useno (defno)
- unsigned int defno;
+void
+debug_df_useno (unsigned int defno)
{
df_ref_debug (ddf, ddf->uses[defno], stderr);
}
-void
-debug_df_chain (link)
- struct df_link *link;
+void
+debug_df_chain (struct df_link *link)
{
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
+\f
+
+/* Perform the set operation OP1 OP OP2, using set representation REPR, and
+ storing the result in OP1. */
+
+static void
+dataflow_set_a_op_b (enum set_representation repr,
+ enum df_confluence_op op,
+ void *op1, void *op2)
+{
+ switch (repr)
+ {
+ case SR_SBITMAP:
+ switch (op)
+ {
+ case DF_UNION:
+ sbitmap_a_or_b (op1, op1, op2);
+ break;
+
+ case DF_INTERSECTION:
+ sbitmap_a_and_b (op1, op1, op2);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ break;
+
+ case SR_BITMAP:
+ switch (op)
+ {
+ case DF_UNION:
+ bitmap_ior_into (op1, op2);
+ break;
+
+ case DF_INTERSECTION:
+ bitmap_and_into (op1, op2);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+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:
+ gcc_unreachable ();
+ }
+}
+
+/* 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;
+ edge_iterator ei;
+
+ SET_BIT (visited, bb->index);
+ gcc_assert (TEST_BIT (pending, bb->index));
+ RESET_BIT (pending, i);
+
+#define HS(E_ANTI, E_ANTI_BB, E_ANTI_START_BB, IN_SET, \
+ E, E_BB, E_START_BB, OUT_SET) \
+ do \
+ { \
+ /* Calculate <conf_op> of predecessor_outs. */ \
+ bitmap_zero (IN_SET[i]); \
+ FOR_EACH_EDGE (e, ei, bb->E_ANTI) \
+ { \
+ 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], \
+ 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_EACH_EDGE (e, ei, bb->E) \
+ { \
+ 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_EACH_EDGE (e, ei, bb->E) \
+ { \
+ 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 (preds, src, ENTRY_BLOCK_PTR, dataflow->in,
+ succs, dest, EXIT_BLOCK_PTR, dataflow->out);
+ else
+ HS (succs, dest, EXIT_BLOCK_PTR, dataflow->out,
+ preds, 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);
+}
OSDN Git Service
