-/* Global common subexpression elimination
+/* Global common subexpression elimination/Partial redundancy elimination
and global constant/copy propagation for GNU compiler.
- Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
- do rough calc of how many regs are needed in each block, and a rough
calc of how many regs are available in each class and use that to
throttle back the code in cases where RTX_COST is minimal.
- - memory aliasing support
+ - dead store elimination
+ - a store to the same address as a load does not kill the load if the
+ source of the store is also the destination of the load. Handling this
+ allows more load motion, particularly out of loops.
- ability to realloc sbitmap vectors would allow one initial computation
of reg_set_in_block with only subsequent additions, rather than
recomputing it for each pass
- NOTES
- - the classic gcse implementation is kept in for now for comparison
*/
/* References searched while implementing this.
- This list will eventually be deleted but I wanted to have a record of it
- for now.
Compilers Principles, Techniques and Tools
Aho, Sethi, Ullman
Frederick Chow
Stanford Ph.D. thesis, Dec. 1983
-xxx
- Elimination Algorithms for Data Flow Analysis
- B.G. Ryder, M.C. Paull
- ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
-
-reread
A Fast Algorithm for Code Movement Optimization
D.M. Dhamdhere
SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
-yyy
- How to Analyze Large Programs Efficiently and Informatively
- D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
- ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
-
Lazy Code Motion
J. Knoop, O. Ruthing, B. Steffen
ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
Michael Wolfe
Addison-Wesley, 1996
- People wishing to speed up the code here should read xxx, yyy.
+ Advanced Compiler Design and Implementation
+ Steven Muchnick
+ Morgan Kaufmann, 1997
+
+ Building an Optimizing Compiler
+ Robert Morgan
+ Digital Press, 1998
+
+ People wishing to speed up the code here should read:
+ Elimination Algorithms for Data Flow Analysis
+ B.G. Ryder, M.C. Paull
+ ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
+
+ How to Analyze Large Programs Efficiently and Informatively
+ D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
+ ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
+
People wishing to do something different can find various possibilities
in the above papers and elsewhere.
*/
#include "config.h"
-/* Must precede rtl.h for FFS. */
#include "system.h"
+#include "toplev.h"
#include "rtl.h"
+#include "tm_p.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
+#include "function.h"
#include "expr.h"
#include "obstack.h"
heuristics into gcse.c. */
#define FOLLOW_BACK_EDGES 1
-/* We support two GCSE implementations: Classic GCSE (i.e. Dragon Book)
- and PRE (Partial Redundancy Elimination) GCSE (based on Fred Chow's thesis).
- The default is PRE.
+/* We support GCSE via Partial Redundancy Elimination. PRE optimizations
+ are a superset of those done by GCSE.
- In either case we perform the following steps:
+ We perform the following steps:
1) Compute basic block information.
4) Perform global cse.
- 5) Perform another pass of copy/constant propagation [only if PRE].
+ 5) Perform another pass of copy/constant propagation.
Two passes of copy/constant propagation are done because the first one
enables more GCSE and the second one helps to clean up the copies that
Function want_to_gcse_p says what these are.
PRE handles moving invariant expressions out of loops (by treating them as
- partially redundant). This feature of PRE is disabled here (by not
- propagating dataflow information along back edges) because loop.c has more
- involved (and thus typically better) heuristics for what to move out of
- loops.
+ partially redundant).
Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
assignment) based GVN (global value numbering). L. T. Simpson's paper
argue it is not. The number of iterations for the algorithm to converge
is typically 2-4 so I don't view it as that expensive (relatively speaking).
- PRE GCSE depends heavily on the seconds CSE pass to clean up the copies
+ PRE GCSE depends heavily on the second CSE pass to clean up the copies
we create. To make an expression reach the place where it's redundant,
the result of the expression is copied to a new register, and the redundant
expression is deleted by replacing it with this new register. Classic GCSE
**********************
- When -fclassic-gcse, we perform a classic global CSE pass.
- It is based on the algorithms in the Dragon book, and is based on code
- written by Devor Tevi at Intel.
-
- The steps for Classic GCSE are:
-
- 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
- Also recorded are reaching definition "gen" statements (rd_gen)
-
- 2) Compute the reaching definitions (reaching_defs).
- This is a bitmap for each basic block indexed by INSN_CUID that is 1
- for each statement containing a definition that reaches the block.
-
- 3) Compute the available expressions (ae_in).
- This is a bitmap for each basic block indexed by expression number
- that is 1 for each expression that is available at the beginning of
- the block.
-
- 4) Perform GCSE.
- This is done by scanning each instruction looking for sets of the form
- (set (pseudo-reg) (expression)) and checking if `expression' is in the
- hash table. If it is, and if the expression is available, and if only
- one computation of the expression reaches the instruction, we substitute
- the expression for a register containing its value. If there is no
- such register, but the expression is expensive enough we create an
- instruction to copy the result of the expression into and use that.
-
- **********************
-
A fair bit of simplicity is created by creating small functions for simple
tasks, even when the function is only called in one place. This may
measurably slow things down [or may not] by creating more function call
/* -dG dump file. */
static FILE *gcse_file;
+/* Note whether or not we should run jump optimization after gcse. We
+ want to do this for two cases.
+
+ * If we changed any jumps via cprop.
+
+ * If we added any labels via edge splitting. */
+
+static int run_jump_opt_after_gcse;
+
/* Bitmaps are normally not included in debugging dumps.
However it's useful to be able to print them from GDB.
We could create special functions for this, but it's simpler to
/* Non-zero if can_copy_p has been initialized. */
static int can_copy_init_p;
-/* Element I is a list of I's predecessors/successors. */
-static int_list_ptr *s_preds;
-static int_list_ptr *s_succs;
-
-/* Element I is the number of predecessors/successors of basic block I. */
-static int *num_preds;
-static int *num_succs;
+struct reg_use {rtx reg_rtx; };
/* Hash table of expressions. */
struct expr *next_same_hash;
/* List of anticipatable occurrences in basic blocks in the function.
An "anticipatable occurrence" is one that is the first occurrence in the
- basic block and the operands are not modified in the basic block prior
- to the occurrence. */
+ basic block, the operands are not modified in the basic block prior
+ to the occurrence and the output is not used between the start of
+ the block and the occurrence. */
struct occr *antic_occr;
/* List of available occurrence in basic blocks in the function.
An "available occurrence" is one that is the last occurrence in the
not clear whether in the final analysis a sufficient amount of memory would
be saved as the size of the available expression bitmaps would be larger
[one could build a mapping table without holes afterwards though].
- Someday I'll perform the computation and figure it out.
-*/
+ Someday I'll perform the computation and figure it out. */
/* Total size of the expression hash table, in elements. */
-static int expr_hash_table_size;
+static unsigned int expr_hash_table_size;
+
/* The table itself.
This is an array of `expr_hash_table_size' elements. */
static struct expr **expr_hash_table;
/* Total size of the copy propagation hash table, in elements. */
static int set_hash_table_size;
+
/* The table itself.
This is an array of `set_hash_table_size' elements. */
static struct expr **set_hash_table;
static int max_uid;
/* Get the cuid of an insn. */
+#ifdef ENABLE_CHECKING
+#define INSN_CUID(INSN) (INSN_UID (INSN) > max_uid ? (abort (), 0) : uid_cuid[INSN_UID (INSN)])
+#else
#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
+#endif
/* Number of cuids. */
static int max_cuid;
/* Maximum register number in function prior to doing gcse + 1.
Registers created during this pass have regno >= max_gcse_regno.
This is named with "gcse" to not collide with global of same name. */
-static int max_gcse_regno;
+static unsigned int max_gcse_regno;
/* Maximum number of cse-able expressions found. */
static int n_exprs;
+
/* Maximum number of assignments for copy propagation found. */
static int n_sets;
/* Table of registers that are modified.
+
For each register, each element is a list of places where the pseudo-reg
is set.
For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
requires knowledge of which blocks kill which regs [and thus could use
- a bitmap instead of the lists `reg_set_table' uses]. The classic GCSE
- uses the information in lists.
-
- If the classic GCSE pass is deleted `reg_set_table' and could be turned
- into an array of bitmaps (num-bbs x num-regs)
- [however perhaps it may be useful to keep the data as is].
- One advantage of recording things this way is that `reg_set_table' is
- fairly sparse with respect to pseudo regs but for hard regs could be
- fairly dense [relatively speaking].
- And recording sets of pseudo-regs in lists speeds
+ a bitmap instead of the lists `reg_set_table' uses].
+
+ `reg_set_table' and could be turned into an array of bitmaps (num-bbs x
+ num-regs) [however perhaps it may be useful to keep the data as is]. One
+ advantage of recording things this way is that `reg_set_table' is fairly
+ sparse with respect to pseudo regs but for hard regs could be fairly dense
+ [relatively speaking]. And recording sets of pseudo-regs in lists speeds
up functions like compute_transp since in the case of pseudo-regs we only
need to iterate over the number of times a pseudo-reg is set, not over the
number of basic blocks [clearly there is a bit of a slow down in the cases
where a pseudo is set more than once in a block, however it is believed
that the net effect is to speed things up]. This isn't done for hard-regs
because recording call-clobbered hard-regs in `reg_set_table' at each
- function call can consume a fair bit of memory, and iterating over hard-regs
- stored this way in compute_transp will be more expensive. */
+ function call can consume a fair bit of memory, and iterating over
+ hard-regs stored this way in compute_transp will be more expensive. */
-typedef struct reg_set {
+typedef struct reg_set
+{
/* The next setting of this register. */
struct reg_set *next;
/* The insn where it was set. */
rtx insn;
} reg_set;
+
static reg_set **reg_set_table;
+
/* Size of `reg_set_table'.
The table starts out at max_gcse_regno + slop, and is enlarged as
necessary. */
static int reg_set_table_size;
+
/* Amount to grow `reg_set_table' by when it's full. */
#define REG_SET_TABLE_SLOP 100
This isn't intended to be absolutely precise. Its intent is only
to keep an eye on memory usage. */
static int bytes_used;
+
/* GCSE substitutions made. */
static int gcse_subst_count;
/* Number of copy instructions created. */
static int const_prop_count;
/* Number of copys propagated. */
static int copy_prop_count;
-
-extern char *current_function_name;
-extern int current_function_calls_setjmp;
-extern int current_function_calls_longjmp;
\f
/* These variables are used by classic GCSE.
Normally they'd be defined a bit later, but `rd_gen' needs to
Thus we view the bitmaps as 2 dimensional arrays. i.e.
rd_kill[block_num][cuid_num]
- ae_kill[block_num][expr_num]
-*/
+ ae_kill[block_num][expr_num] */
/* For reaching defs */
static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out;
/* for available exprs */
static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
+
+/* Objects of this type are passed around by the null-pointer check
+ removal routines. */
+struct null_pointer_info
+{
+ /* The basic block being processed. */
+ int current_block;
+ /* The first register to be handled in this pass. */
+ unsigned int min_reg;
+ /* One greater than the last register to be handled in this pass. */
+ unsigned int max_reg;
+ sbitmap *nonnull_local;
+ sbitmap *nonnull_killed;
+};
\f
-static void compute_can_copy PROTO ((void));
-
-static char *gmalloc PROTO ((unsigned int));
-static char *grealloc PROTO ((char *, unsigned int));
-static char *gcse_alloc PROTO ((unsigned long));
-static void alloc_gcse_mem PROTO ((rtx));
-static void free_gcse_mem PROTO ((void));
-extern void dump_cuid_table PROTO ((FILE *));
-
-static void alloc_reg_set_mem PROTO ((int));
-static void free_reg_set_mem PROTO ((void));
-static void record_one_set PROTO ((int, rtx));
-static void record_set_info PROTO ((rtx, rtx));
-static void compute_sets PROTO ((rtx));
-
-static void hash_scan_insn PROTO ((rtx, int, int));
-static void hash_scan_set PROTO ((rtx, rtx, int));
-static void hash_scan_clobber PROTO ((rtx, rtx));
-static void hash_scan_call PROTO ((rtx, rtx));
-static void maybe_set_rd_gen PROTO ((int, rtx));
-static int want_to_gcse_p PROTO ((rtx));
-static int oprs_unchanged_p PROTO ((rtx, rtx, int));
-static int oprs_anticipatable_p PROTO ((rtx, rtx));
-static int oprs_available_p PROTO ((rtx, rtx));
-static void insert_expr_in_table PROTO ((rtx, enum machine_mode, rtx, int, int));
-static void insert_set_in_table PROTO ((rtx, rtx));
-static unsigned int hash_expr PROTO ((rtx, enum machine_mode, int *, int));
-static unsigned int hash_expr_1 PROTO ((rtx, enum machine_mode, int *));
-static unsigned int hash_set PROTO ((int, int));
-static int expr_equiv_p PROTO ((rtx, rtx));
-static void record_last_reg_set_info PROTO ((rtx, int));
-static void record_last_mem_set_info PROTO ((rtx));
-static void record_last_set_info PROTO ((rtx, rtx));
-static void compute_hash_table PROTO ((rtx, int));
-static void alloc_set_hash_table PROTO ((int));
-static void free_set_hash_table PROTO ((void));
-static void compute_set_hash_table PROTO ((rtx));
-static void alloc_expr_hash_table PROTO ((int));
-static void free_expr_hash_table PROTO ((void));
-static void compute_expr_hash_table PROTO ((rtx));
-static void dump_hash_table PROTO ((FILE *, char *, struct expr **, int, int));
-static struct expr *lookup_expr PROTO ((rtx));
-static struct expr *lookup_set PROTO ((int, rtx));
-static struct expr *next_set PROTO ((int, struct expr *));
-static void reset_opr_set_tables PROTO ((void));
-static int oprs_not_set_p PROTO ((rtx, rtx));
-static void mark_call PROTO ((rtx, rtx));
-static void mark_set PROTO ((rtx, rtx));
-static void mark_clobber PROTO ((rtx, rtx));
-static void mark_oprs_set PROTO ((rtx));
-
-static void alloc_rd_mem PROTO ((int, int));
-static void free_rd_mem PROTO ((void));
-static void compute_kill_rd PROTO ((void));
-static void handle_rd_kill_set PROTO ((rtx, int, int));
-static void compute_rd PROTO ((void));
-extern void dump_rd_table PROTO ((FILE *, char *, sbitmap *));
-
-static void alloc_avail_expr_mem PROTO ((int, int));
-static void free_avail_expr_mem PROTO ((void));
-static void compute_ae_gen PROTO ((void));
-static void compute_ae_kill PROTO ((void));
-static int expr_killed_p PROTO ((rtx, int));
-static void compute_available PROTO ((void));
-
-static int expr_reaches_here_p PROTO ((struct occr *, struct expr *,
- int, int, char *));
-static rtx computing_insn PROTO ((struct expr *, rtx));
-static int def_reaches_here_p PROTO ((rtx, rtx));
-static int can_disregard_other_sets PROTO ((struct reg_set **, rtx, int));
-static int handle_avail_expr PROTO ((rtx, struct expr *));
-static int classic_gcse PROTO ((void));
-static int one_classic_gcse_pass PROTO ((rtx, int));
-
-static void alloc_cprop_mem PROTO ((int, int));
-static void free_cprop_mem PROTO ((void));
-extern void dump_cprop_data PROTO ((FILE *));
-static void compute_transp PROTO ((rtx, int, sbitmap *, int));
-static void compute_cprop_local_properties PROTO ((void));
-static void compute_cprop_avinout PROTO ((void));
-static void compute_cprop_data PROTO ((void));
-static void find_used_regs PROTO ((rtx));
-static int try_replace_reg PROTO ((rtx, rtx, rtx));
-static struct expr *find_avail_set PROTO ((int, rtx));
-static int cprop_insn PROTO ((rtx));
-static int cprop PROTO ((void));
-static int one_cprop_pass PROTO ((rtx, int));
-
-static void alloc_pre_mem PROTO ((int, int));
-static void free_pre_mem PROTO ((void));
-extern void dump_pre_data PROTO ((FILE *));
-static void compute_pre_local_properties PROTO ((void));
-static void compute_pre_avinout PROTO ((void));
-static void compute_pre_antinout PROTO ((void));
-static void compute_pre_pavinout PROTO ((void));
-static void compute_pre_ppinout PROTO ((void));
-static void compute_pre_data PROTO ((void));
-static int pre_expr_reaches_here_p PROTO ((struct occr *, struct expr *,
- int, char *));
-static void pre_insert_insn PROTO ((struct expr *, int));
-static void pre_insert PROTO ((struct expr **));
-static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
-static void pre_insert_copies PROTO ((void));
-static int pre_delete PROTO ((void));
-static int pre_gcse PROTO ((void));
-static int one_pre_gcse_pass PROTO ((rtx, int));
-
-static void add_label_notes PROTO ((rtx, rtx));
+static void compute_can_copy PARAMS ((void));
+static char *gmalloc PARAMS ((unsigned int));
+static char *grealloc PARAMS ((char *, unsigned int));
+static char *gcse_alloc PARAMS ((unsigned long));
+static void alloc_gcse_mem PARAMS ((rtx));
+static void free_gcse_mem PARAMS ((void));
+static void alloc_reg_set_mem PARAMS ((int));
+static void free_reg_set_mem PARAMS ((void));
+static int get_bitmap_width PARAMS ((int, int, int));
+static void record_one_set PARAMS ((int, rtx));
+static void record_set_info PARAMS ((rtx, rtx, void *));
+static void compute_sets PARAMS ((rtx));
+static void hash_scan_insn PARAMS ((rtx, int, int));
+static void hash_scan_set PARAMS ((rtx, rtx, int));
+static void hash_scan_clobber PARAMS ((rtx, rtx));
+static void hash_scan_call PARAMS ((rtx, rtx));
+static int want_to_gcse_p PARAMS ((rtx));
+static int oprs_unchanged_p PARAMS ((rtx, rtx, int));
+static int oprs_anticipatable_p PARAMS ((rtx, rtx));
+static int oprs_available_p PARAMS ((rtx, rtx));
+static void insert_expr_in_table PARAMS ((rtx, enum machine_mode, rtx,
+ int, int));
+static void insert_set_in_table PARAMS ((rtx, rtx));
+static unsigned int hash_expr PARAMS ((rtx, enum machine_mode, int *, int));
+static unsigned int hash_expr_1 PARAMS ((rtx, enum machine_mode, int *));
+static unsigned int hash_set PARAMS ((int, int));
+static int expr_equiv_p PARAMS ((rtx, rtx));
+static void record_last_reg_set_info PARAMS ((rtx, int));
+static void record_last_mem_set_info PARAMS ((rtx));
+static void record_last_set_info PARAMS ((rtx, rtx, void *));
+static void compute_hash_table PARAMS ((int));
+static void alloc_set_hash_table PARAMS ((int));
+static void free_set_hash_table PARAMS ((void));
+static void compute_set_hash_table PARAMS ((void));
+static void alloc_expr_hash_table PARAMS ((unsigned int));
+static void free_expr_hash_table PARAMS ((void));
+static void compute_expr_hash_table PARAMS ((void));
+static void dump_hash_table PARAMS ((FILE *, const char *, struct expr **,
+ int, int));
+static struct expr *lookup_expr PARAMS ((rtx));
+static struct expr *lookup_set PARAMS ((unsigned int, rtx));
+static struct expr *next_set PARAMS ((unsigned int, struct expr *));
+static void reset_opr_set_tables PARAMS ((void));
+static int oprs_not_set_p PARAMS ((rtx, rtx));
+static void mark_call PARAMS ((rtx));
+static void mark_set PARAMS ((rtx, rtx));
+static void mark_clobber PARAMS ((rtx, rtx));
+static void mark_oprs_set PARAMS ((rtx));
+static void alloc_cprop_mem PARAMS ((int, int));
+static void free_cprop_mem PARAMS ((void));
+static void compute_transp PARAMS ((rtx, int, sbitmap *, int));
+static void compute_transpout PARAMS ((void));
+static void compute_local_properties PARAMS ((sbitmap *, sbitmap *, sbitmap *,
+ int));
+static void compute_cprop_data PARAMS ((void));
+static void find_used_regs PARAMS ((rtx));
+static int try_replace_reg PARAMS ((rtx, rtx, rtx));
+static struct expr *find_avail_set PARAMS ((int, rtx));
+static int cprop_jump PARAMS ((rtx, rtx, struct reg_use *, rtx));
+#ifdef HAVE_cc0
+static int cprop_cc0_jump PARAMS ((rtx, struct reg_use *, rtx));
+#endif
+static int cprop_insn PARAMS ((rtx, int));
+static int cprop PARAMS ((int));
+static int one_cprop_pass PARAMS ((int, int));
+static void alloc_pre_mem PARAMS ((int, int));
+static void free_pre_mem PARAMS ((void));
+static void compute_pre_data PARAMS ((void));
+static int pre_expr_reaches_here_p PARAMS ((int, struct expr *, int));
+static void insert_insn_end_bb PARAMS ((struct expr *, int, int));
+static void pre_insert_copy_insn PARAMS ((struct expr *, rtx));
+static void pre_insert_copies PARAMS ((void));
+static int pre_delete PARAMS ((void));
+static int pre_gcse PARAMS ((void));
+static int one_pre_gcse_pass PARAMS ((int));
+static void add_label_notes PARAMS ((rtx, rtx));
+static void alloc_code_hoist_mem PARAMS ((int, int));
+static void free_code_hoist_mem PARAMS ((void));
+static void compute_code_hoist_vbeinout PARAMS ((void));
+static void compute_code_hoist_data PARAMS ((void));
+static int hoist_expr_reaches_here_p PARAMS ((int, int, int, char *));
+static void hoist_code PARAMS ((void));
+static int one_code_hoisting_pass PARAMS ((void));
+static void alloc_rd_mem PARAMS ((int, int));
+static void free_rd_mem PARAMS ((void));
+static void handle_rd_kill_set PARAMS ((rtx, int, int));
+static void compute_kill_rd PARAMS ((void));
+static void compute_rd PARAMS ((void));
+static void alloc_avail_expr_mem PARAMS ((int, int));
+static void free_avail_expr_mem PARAMS ((void));
+static void compute_ae_gen PARAMS ((void));
+static int expr_killed_p PARAMS ((rtx, int));
+static void compute_ae_kill PARAMS ((sbitmap *, sbitmap *));
+static int expr_reaches_here_p PARAMS ((struct occr *, struct expr *,
+ int, int));
+static rtx computing_insn PARAMS ((struct expr *, rtx));
+static int def_reaches_here_p PARAMS ((rtx, rtx));
+static int can_disregard_other_sets PARAMS ((struct reg_set **, rtx, int));
+static int handle_avail_expr PARAMS ((rtx, struct expr *));
+static int classic_gcse PARAMS ((void));
+static int one_classic_gcse_pass PARAMS ((int));
+static void invalidate_nonnull_info PARAMS ((rtx, rtx, void *));
+static void delete_null_pointer_checks_1 PARAMS ((unsigned int *, sbitmap *,
+ sbitmap *,
+ struct null_pointer_info *));
+static rtx process_insert_insn PARAMS ((struct expr *));
+static int pre_edge_insert PARAMS ((struct edge_list *, struct expr **));
+static int expr_reaches_here_p_work PARAMS ((struct occr *, struct expr *,
+ int, int, char *));
+static int pre_expr_reaches_here_p_work PARAMS ((int, struct expr *,
+ int, char *));
\f
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
-void
+int
gcse_main (f, file)
rtx f;
FILE *file;
/* Point to release obstack data from for each pass. */
char *gcse_obstack_bottom;
- /* It's impossible to construct a correct control flow graph in the
- presense of setjmp, so just punt to be safe. */
+ /* We do not construct an accurate cfg in functions which call
+ setjmp, so just punt to be safe. */
if (current_function_calls_setjmp)
- return;
+ return 0;
+ /* Assume that we do not need to run jump optimizations after gcse. */
+ run_jump_opt_after_gcse = 0;
+
/* For calling dump_foo fns from gdb. */
debug_stderr = stderr;
+ gcse_file = file;
+ /* Identify the basic block information for this function, including
+ successors and predecessors. */
max_gcse_regno = max_reg_num ();
- find_basic_blocks (f, max_gcse_regno, file);
+
+ if (file)
+ dump_flow_info (file);
/* Return if there's nothing to do. */
if (n_basic_blocks <= 1)
- {
- /* Free storage allocated by find_basic_blocks. */
- free_basic_block_vars (0);
- return;
- }
+ return 0;
+
+ /* Trying to perform global optimizations on flow graphs which have
+ a high connectivity will take a long time and is unlikely to be
+ particularly useful.
+
+ In normal circumstances a cfg should have about twice has many edges
+ as blocks. But we do not want to punish small functions which have
+ a couple switch statements. So we require a relatively large number
+ of basic blocks and the ratio of edges to blocks to be high. */
+ if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
+ return 0;
/* See what modes support reg/reg copy operations. */
if (! can_copy_init_p)
}
gcc_obstack_init (&gcse_obstack);
+ bytes_used = 0;
- gcse_file = file;
-
- /* Allocate and compute predecessors/successors. */
-
- s_preds = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
- s_succs = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
- num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
- num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
- bytes_used = 4 * n_basic_blocks * sizeof (int_list_ptr);
- compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
-
- if (file)
- dump_bb_data (file, s_preds, s_succs, 0);
+ /* Record where pseudo-registers are set. This data is kept accurate
+ during each pass. ??? We could also record hard-reg information here
+ [since it's unchanging], however it is currently done during hash table
+ computation.
- /* Record where pseudo-registers are set.
- This data is kept accurate during each pass.
- ??? We could also record hard-reg and memory information here
- [since it's unchanging], however it is currently done during
- hash table computation. */
+ It may be tempting to compute MEM set information here too, but MEM sets
+ will be subject to code motion one day and thus we need to compute
+ information about memory sets when we build the hash tables. */
alloc_reg_set_mem (max_gcse_regno);
compute_sets (f);
alloc_gcse_mem (f);
- changed = one_cprop_pass (f, pass + 1);
+ /* Don't allow constant propagation to modify jumps
+ during this pass. */
+ changed = one_cprop_pass (pass + 1, 0);
if (optimize_size)
- changed |= one_classic_gcse_pass (f, pass + 1);
+ changed |= one_classic_gcse_pass (pass + 1);
else
- changed |= one_pre_gcse_pass (f, pass + 1);
+ {
+ changed |= one_pre_gcse_pass (pass + 1);
+ free_reg_set_mem ();
+ alloc_reg_set_mem (max_reg_num ());
+ compute_sets (f);
+ run_jump_opt_after_gcse = 1;
+ }
if (max_pass_bytes < bytes_used)
max_pass_bytes = bytes_used;
+ /* Free up memory, then reallocate for code hoisting. We can
+ not re-use the existing allocated memory because the tables
+ will not have info for the insns or registers created by
+ partial redundancy elimination. */
free_gcse_mem ();
+ /* It does not make sense to run code hoisting unless we optimizing
+ for code size -- it rarely makes programs faster, and can make
+ them bigger if we did partial redundancy elimination (when optimizing
+ for space, we use a classic gcse algorithm instead of partial
+ redundancy algorithms). */
+ if (optimize_size)
+ {
+ max_gcse_regno = max_reg_num ();
+ alloc_gcse_mem (f);
+ changed |= one_code_hoisting_pass ();
+ free_gcse_mem ();
+
+ if (max_pass_bytes < bytes_used)
+ max_pass_bytes = bytes_used;
+ }
+
if (file)
{
fprintf (file, "\n");
fflush (file);
}
+
obstack_free (&gcse_obstack, gcse_obstack_bottom);
pass++;
}
- /* If we're doing PRE, do one last pass of copy propagation. */
- if (! optimize_size)
- {
- max_gcse_regno = max_reg_num ();
- alloc_gcse_mem (f);
- one_cprop_pass (f, pass + 1);
- free_gcse_mem ();
- }
+ /* Do one last pass of copy propagation, including cprop into
+ conditional jumps. */
+
+ max_gcse_regno = max_reg_num ();
+ alloc_gcse_mem (f);
+ /* This time, go ahead and allow cprop to alter jumps. */
+ one_cprop_pass (pass + 1, 1);
+ free_gcse_mem ();
if (file)
{
pass, pass > 1 ? "es" : "", max_pass_bytes);
}
- /* Free our obstack. */
obstack_free (&gcse_obstack, NULL_PTR);
- /* Free reg_set_table. */
free_reg_set_mem ();
- /* Free storage used to record predecessor/successor data. */
- free_bb_mem ();
- /* Free storage allocated by find_basic_blocks. */
- free_basic_block_vars (0);
+ return run_jump_opt_after_gcse;
}
\f
/* Misc. utilities. */
start_sequence ();
for (i = 0; i < NUM_MACHINE_MODES; i++)
- {
- switch (GET_MODE_CLASS (i))
- {
- case MODE_CC :
+ if (GET_MODE_CLASS (i) == MODE_CC)
+ {
#ifdef AVOID_CCMODE_COPIES
- can_copy_p[i] = 0;
+ can_copy_p[i] = 0;
#else
- reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
- insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
- if (recog (PATTERN (insn), insn, NULL_PTR) >= 0)
- can_copy_p[i] = 1;
-#endif
- break;
- default :
+ reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
+ insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
+ if (recog (PATTERN (insn), insn, NULL_PTR) >= 0)
can_copy_p[i] = 1;
- break;
- }
- }
+#endif
+ }
+ else
+ can_copy_p[i] = 1;
+
end_sequence ();
/* Free the objects we just allocated. */
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- INSN_CUID (insn) = i++;
+ uid_cuid[INSN_UID (insn)] = i++;
else
- INSN_CUID (insn) = i;
+ uid_cuid[INSN_UID (insn)] = i;
}
/* Create a table mapping cuids to insns. */
cuid_insn = (rtx *) gmalloc (n);
bzero ((char *) cuid_insn, n);
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
- {
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- CUID_INSN (i) = insn;
- i++;
- }
- }
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ CUID_INSN (i++) = insn;
/* Allocate vars to track sets of regs. */
-
reg_set_bitmap = (sbitmap) sbitmap_alloc (max_gcse_regno);
/* Allocate vars to track sets of regs, memory per block. */
-
reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
max_gcse_regno);
mem_set_in_block = (char *) gmalloc (n_basic_blocks);
free (mem_set_in_block);
}
-void
-dump_cuid_table (file)
- FILE *file;
+/* Many of the global optimization algorithms work by solving dataflow
+ equations for various expressions. Initially, some local value is
+ computed for each expression in each block. Then, the values across the
+ various blocks are combined (by following flow graph edges) to arrive at
+ global values. Conceptually, each set of equations is independent. We
+ may therefore solve all the equations in parallel, solve them one at a
+ time, or pick any intermediate approach.
+
+ When you're going to need N two-dimensional bitmaps, each X (say, the
+ number of blocks) by Y (say, the number of expressions), call this
+ function. It's not important what X and Y represent; only that Y
+ correspond to the things that can be done in parallel. This function will
+ return an appropriate chunking factor C; you should solve C sets of
+ equations in parallel. By going through this function, we can easily
+ trade space against time; by solving fewer equations in parallel we use
+ less space. */
+
+static int
+get_bitmap_width (n, x, y)
+ int n;
+ int x;
+ int y;
{
- int i;
+ /* It's not really worth figuring out *exactly* how much memory will
+ be used by a particular choice. The important thing is to get
+ something approximately right. */
+ size_t max_bitmap_memory = 10 * 1024 * 1024;
+
+ /* The number of bytes we'd use for a single column of minimum
+ width. */
+ size_t column_size = n * x * sizeof (SBITMAP_ELT_TYPE);
+
+ /* Often, it's reasonable just to solve all the equations in
+ parallel. */
+ if (column_size * SBITMAP_SET_SIZE (y) <= max_bitmap_memory)
+ return y;
+
+ /* Otherwise, pick the largest width we can, without going over the
+ limit. */
+ return SBITMAP_ELT_BITS * ((max_bitmap_memory + column_size - 1)
+ / column_size);
+}
+\f
+/* Compute the local properties of each recorded expression.
+
+ Local properties are those that are defined by the block, irrespective of
+ other blocks.
+
+ An expression is transparent in a block if its operands are not modified
+ in the block.
+
+ An expression is computed (locally available) in a block if it is computed
+ at least once and expression would contain the same value if the
+ computation was moved to the end of the block.
+
+ An expression is locally anticipatable in a block if it is computed at
+ least once and expression would contain the same value if the computation
+ was moved to the beginning of the block.
+
+ We call this routine for cprop, pre and code hoisting. They all compute
+ basically the same information and thus can easily share this code.
+
+ TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
+ properties. If NULL, then it is not necessary to compute or record that
+ particular property.
+
+ SETP controls which hash table to look at. If zero, this routine looks at
+ the expr hash table; if nonzero this routine looks at the set hash table.
+ Additionally, TRANSP is computed as ~TRANSP, since this is really cprop's
+ ABSALTERED. */
+
+static void
+compute_local_properties (transp, comp, antloc, setp)
+ sbitmap *transp;
+ sbitmap *comp;
+ sbitmap *antloc;
+ int setp;
+{
+ unsigned int i, hash_table_size;
+ struct expr **hash_table;
+
+ /* Initialize any bitmaps that were passed in. */
+ if (transp)
+ {
+ if (setp)
+ sbitmap_vector_zero (transp, n_basic_blocks);
+ else
+ sbitmap_vector_ones (transp, n_basic_blocks);
+ }
+
+ if (comp)
+ sbitmap_vector_zero (comp, n_basic_blocks);
+ if (antloc)
+ sbitmap_vector_zero (antloc, n_basic_blocks);
+
+ /* We use the same code for cprop, pre and hoisting. For cprop
+ we care about the set hash table, for pre and hoisting we
+ care about the expr hash table. */
+ hash_table_size = setp ? set_hash_table_size : expr_hash_table_size;
+ hash_table = setp ? set_hash_table : expr_hash_table;
- fprintf (file, "CUID table\n");
- for (i = 0; i < max_cuid; i++)
+ for (i = 0; i < hash_table_size; i++)
{
- rtx insn = CUID_INSN (i);
- if (i != 0 && i % 10 == 0)
- fprintf (file, "\n");
- if (insn != NULL)
- fprintf (file, " %d", INSN_UID (insn));
+ struct expr *expr;
+
+ for (expr = hash_table[i]; expr != NULL; expr = expr->next_same_hash)
+ {
+ int indx = expr->bitmap_index;
+ struct occr *occr;
+
+ /* The expression is transparent in this block if it is not killed.
+ We start by assuming all are transparent [none are killed], and
+ then reset the bits for those that are. */
+ if (transp)
+ compute_transp (expr->expr, indx, transp, setp);
+
+ /* The occurrences recorded in antic_occr are exactly those that
+ we want to set to non-zero in ANTLOC. */
+ if (antloc)
+ for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
+ {
+ SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx);
+
+ /* While we're scanning the table, this is a good place to
+ initialize this. */
+ occr->deleted_p = 0;
+ }
+
+ /* The occurrences recorded in avail_occr are exactly those that
+ we want to set to non-zero in COMP. */
+ if (comp)
+ for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
+ {
+ SET_BIT (comp[BLOCK_NUM (occr->insn)], indx);
+
+ /* While we're scanning the table, this is a good place to
+ initialize this. */
+ occr->copied_p = 0;
+ }
+
+ /* While we're scanning the table, this is a good place to
+ initialize this. */
+ expr->reaching_reg = 0;
+ }
}
- fprintf (file, "\n\n");
}
\f
/* Register set information.
alloc_reg_set_mem (n_regs)
int n_regs;
{
- int n;
+ unsigned int n;
reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
n = reg_set_table_size * sizeof (struct reg_set *);
if (regno >= reg_set_table_size)
{
int new_size = regno + REG_SET_TABLE_SLOP;
- reg_set_table = (struct reg_set **)
- grealloc ((char *) reg_set_table,
- new_size * sizeof (struct reg_set *));
+
+ reg_set_table
+ = (struct reg_set **) grealloc ((char *) reg_set_table,
+ new_size * sizeof (struct reg_set *));
bzero ((char *) (reg_set_table + reg_set_table_size),
(new_size - reg_set_table_size) * sizeof (struct reg_set *));
reg_set_table_size = new_size;
sizeof (struct reg_set));
bytes_used += sizeof (struct reg_set);
new_reg_info->insn = insn;
- new_reg_info->next = NULL;
- if (reg_set_table[regno] == NULL)
- reg_set_table[regno] = new_reg_info;
- else
- {
- reg_info_ptr1 = reg_info_ptr2 = reg_set_table[regno];
- /* ??? One could keep a "last" pointer to speed this up. */
- while (reg_info_ptr1 != NULL)
- {
- reg_info_ptr2 = reg_info_ptr1;
- reg_info_ptr1 = reg_info_ptr1->next;
- }
- reg_info_ptr2->next = new_reg_info;
- }
+ new_reg_info->next = reg_set_table[regno];
+ reg_set_table[regno] = new_reg_info;
}
-/* For communication between next two functions (via note_stores). */
-static rtx record_set_insn;
-
-/* Called from compute_sets via note_stores to handle one
- SET or CLOBBER in an insn. */
+/* Called from compute_sets via note_stores to handle one SET or CLOBBER in
+ an insn. The DATA is really the instruction in which the SET is
+ occurring. */
static void
-record_set_info (dest, setter)
+record_set_info (dest, setter, data)
rtx dest, setter ATTRIBUTE_UNUSED;
+ void *data;
{
- if (GET_CODE (dest) == SUBREG)
- dest = SUBREG_REG (dest);
+ rtx record_set_insn = (rtx) data;
- if (GET_CODE (dest) == REG)
- {
- if (REGNO (dest) >= FIRST_PSEUDO_REGISTER)
- record_one_set (REGNO (dest), record_set_insn);
- }
+ if (GET_CODE (dest) == REG && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
+ record_one_set (REGNO (dest), record_set_insn);
}
/* Scan the function and record each set of each pseudo-register.
- This is called once, at the start of the gcse pass.
- See the comments for `reg_set_table' for further docs. */
+ This is called once, at the start of the gcse pass. See the comments for
+ `reg_set_table' for further documenation. */
static void
compute_sets (f)
rtx f;
{
- rtx insn = f;
+ rtx insn;
- while (insn)
- {
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- record_set_insn = insn;
- note_stores (PATTERN (insn), record_set_info);
- }
- insn = NEXT_INSN (insn);
- }
+ for (insn = f; insn != 0; insn = NEXT_INSN (insn))
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ note_stores (PATTERN (insn), record_set_info, insn);
}
\f
/* Hash table support. */
-#define NEVER_SET -1
-
/* For each register, the cuid of the first/last insn in the block to set it,
or -1 if not set. */
+#define NEVER_SET -1
static int *reg_first_set;
static int *reg_last_set;
to set memory or -1 if not set. `mem_last_set' is also used when
performing GCSE to record whether memory has been set since the beginning
of the block.
+
Note that handling of memory is very simple, we don't make any attempt
to optimize things (later). */
static int mem_first_set;
static int mem_last_set;
-/* Set the appropriate bit in `rd_gen' [the gen for reaching defs] if the
- register set in this insn is not set after this insn in this block. */
-
-static void
-maybe_set_rd_gen (regno, insn)
- int regno;
- rtx insn;
-{
- if (reg_last_set[regno] <= INSN_CUID (insn))
- SET_BIT (rd_gen[BLOCK_NUM (insn)], INSN_CUID (insn));
-}
-
/* Perform a quick check whether X, the source of a set, is something
we want to consider for GCSE. */
want_to_gcse_p (x)
rtx x;
{
- enum rtx_code code = GET_CODE (x);
-
- switch (code)
+ switch (GET_CODE (x))
{
case REG:
case SUBREG:
rtx x, insn;
int avail_p;
{
- int i;
+ int i, j;
enum rtx_code code;
- char *fmt;
-
- /* repeat is used to turn tail-recursion into iteration. */
- repeat:
+ const char *fmt;
if (x == 0)
return 1;
|| reg_first_set[REGNO (x)] >= INSN_CUID (insn));
case MEM:
- if (avail_p)
- {
- if (mem_last_set != NEVER_SET
- && mem_last_set >= INSN_CUID (insn))
- return 0;
- }
+ if (avail_p && mem_last_set != NEVER_SET
+ && mem_last_set >= INSN_CUID (insn))
+ return 0;
+ else if (! avail_p && mem_first_set != NEVER_SET
+ && mem_first_set < INSN_CUID (insn))
+ return 0;
else
- {
- if (mem_first_set != NEVER_SET
- && mem_first_set < INSN_CUID (insn))
- return 0;
- }
- x = XEXP (x, 0);
- goto repeat;
+ return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
case PRE_DEC:
case PRE_INC:
break;
}
- i = GET_RTX_LENGTH (code) - 1;
- fmt = GET_RTX_FORMAT (code);
- for (; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
- rtx tem = XEXP (x, i);
-
- /* If we are about to do the last recursive call
- needed at this level, change it into iteration.
- This function is called enough to be worth it. */
+ /* If we are about to do the last recursive call needed at this
+ level, change it into iteration. This function is called enough
+ to be worth it. */
if (i == 0)
- {
- x = tem;
- goto repeat;
- }
- if (! oprs_unchanged_p (tem, insn, avail_p))
+ return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
+
+ else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
return 0;
}
else if (fmt[i] == 'E')
- {
- int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- {
- if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
- return 0;
- }
- }
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
+ return 0;
}
return 1;
}
/* Hash expression X.
- MODE is only used if X is a CONST_INT.
- A boolean indicating if a volatile operand is found or if the expression
- contains something we don't want to insert in the table is stored in
- DO_NOT_RECORD_P.
+
+ MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
+ indicating if a volatile operand is found or if the expression contains
+ something we don't want to insert in the table.
??? One might want to merge this with canon_hash. Later. */
int i, j;
unsigned hash = 0;
enum rtx_code code;
- char *fmt;
+ const char *fmt;
- /* repeat is used to turn tail-recursion into iteration. */
- repeat:
+ /* Used to turn recursion into iteration. We can't rely on GCC's
+ tail-recursion eliminatio since we need to keep accumulating values
+ in HASH. */
if (x == 0)
return hash;
+ repeat:
code = GET_CODE (x);
switch (code)
{
case REG:
- {
- register int regno = REGNO (x);
- hash += ((unsigned) REG << 7) + regno;
- return hash;
- }
+ hash += ((unsigned int) REG << 7) + REGNO (x);
+ return hash;
case CONST_INT:
- {
- unsigned HOST_WIDE_INT tem = INTVAL (x);
- hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
- return hash;
- }
+ hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
+ + (unsigned int) INTVAL (x));
+ return hash;
case CONST_DOUBLE:
/* This is like the general case, except that it only counts
the integers representing the constant. */
- hash += (unsigned) code + (unsigned) GET_MODE (x);
+ hash += (unsigned int) code + (unsigned int) GET_MODE (x);
if (GET_MODE (x) != VOIDmode)
for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
- {
- unsigned tem = XINT (x, i);
- hash += tem;
- }
+ hash += (unsigned int) XWINT (x, i);
else
- hash += ((unsigned) CONST_DOUBLE_LOW (x)
- + (unsigned) CONST_DOUBLE_HIGH (x));
+ hash += ((unsigned int) CONST_DOUBLE_LOW (x)
+ + (unsigned int) CONST_DOUBLE_HIGH (x));
return hash;
/* Assume there is only one rtx object for any given label. */
case LABEL_REF:
/* We don't hash on the address of the CODE_LABEL to avoid bootstrap
differences and differences between each stage's debugging dumps. */
- hash += ((unsigned) LABEL_REF << 7) + CODE_LABEL_NUMBER (XEXP (x, 0));
+ hash += (((unsigned int) LABEL_REF << 7)
+ + CODE_LABEL_NUMBER (XEXP (x, 0)));
return hash;
case SYMBOL_REF:
final assembler. This also avoids differences in the dump files
between various stages. */
unsigned int h = 0;
- unsigned char *p = (unsigned char *) XSTR (x, 0);
+ const unsigned char *p = (const unsigned char *) XSTR (x, 0);
+
while (*p)
h += (h << 7) + *p++; /* ??? revisit */
- hash += ((unsigned) SYMBOL_REF << 7) + h;
+
+ hash += ((unsigned int) SYMBOL_REF << 7) + h;
return hash;
}
*do_not_record_p = 1;
return 0;
}
- hash += (unsigned) MEM;
+
+ hash += (unsigned int) MEM;
+ hash += MEM_ALIAS_SET (x);
x = XEXP (x, 0);
goto repeat;
break;
}
- i = GET_RTX_LENGTH (code) - 1;
hash += (unsigned) code + (unsigned) GET_MODE (x);
- fmt = GET_RTX_FORMAT (code);
- for (; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
- rtx tem = XEXP (x, i);
-
/* If we are about to do the last recursive call
needed at this level, change it into iteration.
This function is called enough to be worth it. */
if (i == 0)
{
- x = tem;
+ x = XEXP (x, i);
goto repeat;
}
- hash += hash_expr_1 (tem, 0, do_not_record_p);
+
+ hash += hash_expr_1 (XEXP (x, i), 0, do_not_record_p);
if (*do_not_record_p)
return 0;
}
+
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
{
if (*do_not_record_p)
return 0;
}
+
else if (fmt[i] == 's')
{
- register unsigned char *p = (unsigned char *) XSTR (x, i);
+ register const unsigned char *p =
+ (const unsigned char *) XSTR (x, i);
+
if (p)
while (*p)
hash += *p++;
}
else if (fmt[i] == 'i')
- {
- register unsigned tem = XINT (x, i);
- hash += tem;
- }
+ hash += (unsigned int) XINT (x, i);
else
abort ();
}
/* Hash a set of register REGNO.
- Sets are hashed on the register that is set.
- This simplifies the PRE copy propagation code.
+ Sets are hashed on the register that is set. This simplifies the PRE copy
+ propagation code.
??? May need to make things more elaborate. Later, as necessary. */
{
register int i, j;
register enum rtx_code code;
- register char *fmt;
+ register const char *fmt;
if (x == y)
return 1;
+
if (x == 0 || y == 0)
return x == y;
case REG:
return REGNO (x) == REGNO (y);
+ case MEM:
+ /* Can't merge two expressions in different alias sets, since we can
+ decide that the expression is transparent in a block when it isn't,
+ due to it being set with the different alias set. */
+ if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
+ return 0;
+ break;
+
/* For commutative operations, check both orders. */
case PLUS:
case MULT:
cur_expr = expr_hash_table[hash];
found = 0;
- while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x)))
+ while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
{
/* If the expression isn't found, save a pointer to the end of
the list. */
cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
bytes_used += sizeof (struct expr);
if (expr_hash_table[hash] == NULL)
- {
- /* This is the first pattern that hashed to this index. */
- expr_hash_table[hash] = cur_expr;
- }
+ /* This is the first pattern that hashed to this index. */
+ expr_hash_table[hash] = cur_expr;
else
- {
- /* Add EXPR to end of this hash chain. */
- last_expr->next_same_hash = cur_expr;
- }
+ /* Add EXPR to end of this hash chain. */
+ last_expr->next_same_hash = cur_expr;
+
/* Set the fields of the expr element. */
cur_expr->expr = x;
cur_expr->bitmap_index = n_exprs++;
}
/* Now record the occurrence(s). */
-
if (antic_p)
{
antic_occr = cur_expr->antic_occr;
}
if (antic_occr)
- {
- /* Found another instance of the expression in the same basic block.
- Prefer the currently recorded one. We want the first one in the
- block and the block is scanned from start to end. */
- ; /* nothing to do */
- }
+ /* Found another instance of the expression in the same basic block.
+ Prefer the currently recorded one. We want the first one in the
+ block and the block is scanned from start to end. */
+ ; /* nothing to do */
else
{
/* First occurrence of this expression in this basic block. */
cur_expr->antic_occr = antic_occr;
else
last_occr->next = antic_occr;
+
antic_occr->insn = insn;
antic_occr->next = NULL;
}
}
if (avail_occr)
- {
- /* Found another instance of the expression in the same basic block.
- Prefer this occurrence to the currently recorded one. We want
- the last one in the block and the block is scanned from start
- to end. */
- avail_occr->insn = insn;
- }
+ /* Found another instance of the expression in the same basic block.
+ Prefer this occurrence to the currently recorded one. We want
+ the last one in the block and the block is scanned from start
+ to end. */
+ avail_occr->insn = insn;
else
{
/* First occurrence of this expression in this basic block. */
avail_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
+
/* First occurrence of this expression in any block? */
if (cur_expr->avail_occr == NULL)
cur_expr->avail_occr = avail_occr;
else
last_occr->next = avail_occr;
+
avail_occr->insn = insn;
avail_occr->next = NULL;
}
cur_expr = set_hash_table[hash];
found = 0;
- while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x)))
+ while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
{
/* If the expression isn't found, save a pointer to the end of
the list. */
cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
bytes_used += sizeof (struct expr);
if (set_hash_table[hash] == NULL)
- {
- /* This is the first pattern that hashed to this index. */
- set_hash_table[hash] = cur_expr;
- }
+ /* This is the first pattern that hashed to this index. */
+ set_hash_table[hash] = cur_expr;
else
- {
- /* Add EXPR to end of this hash chain. */
- last_expr->next_same_hash = cur_expr;
- }
+ /* Add EXPR to end of this hash chain. */
+ last_expr->next_same_hash = cur_expr;
+
/* Set the fields of the expr element.
We must copy X because it can be modified when copy propagation is
performed on its operands. */
}
/* Now record the occurrence. */
-
cur_occr = cur_expr->avail_occr;
/* Search for another occurrence in the same basic block. */
}
if (cur_occr)
- {
- /* Found another instance of the expression in the same basic block.
- Prefer this occurrence to the currently recorded one. We want
- the last one in the block and the block is scanned from start
- to end. */
- cur_occr->insn = insn;
- }
+ /* Found another instance of the expression in the same basic block.
+ Prefer this occurrence to the currently recorded one. We want the
+ last one in the block and the block is scanned from start to end. */
+ cur_occr->insn = insn;
else
{
/* First occurrence of this expression in this basic block. */
cur_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
+
/* First occurrence of this expression in any block? */
if (cur_expr->avail_occr == NULL)
cur_expr->avail_occr = cur_occr;
else
last_occr->next = cur_occr;
+
cur_occr->insn = insn;
cur_occr->next = NULL;
}
}
-/* Scan pattern PAT of INSN and add an entry to the hash table.
- If SET_P is non-zero, this is for the assignment hash table,
- otherwise it is for the expression hash table. */
+/* Scan pattern PAT of INSN and add an entry to the hash table. If SET_P is
+ non-zero, this is for the assignment hash table, otherwise it is for the
+ expression hash table. */
static void
hash_scan_set (pat, insn, set_p)
{
/* An expression is not anticipatable if its operands are
modified before this insn. */
- int antic_p = ! optimize_size && oprs_anticipatable_p (src, insn);
+ int antic_p = oprs_anticipatable_p (src, insn);
/* An expression is not available if its operands are
subsequently modified, including this insn. */
int avail_p = oprs_available_p (src, insn);
+
insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p);
}
+
/* Record sets for constant/copy propagation. */
else if (set_p
&& regno >= FIRST_PSEUDO_REGISTER
&& ((GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)])
- /* ??? CONST_INT:wip */
- || GET_CODE (src) == CONST_INT)
+ || GET_CODE (src) == CONST_INT
+ || GET_CODE (src) == SYMBOL_REF
+ || GET_CODE (src) == CONST_DOUBLE)
/* A copy is not available if its src or dest is subsequently
modified. Here we want to search from INSN+1 on, but
oprs_available_p searches from INSN on. */
&& oprs_available_p (pat, tmp))))
insert_set_in_table (pat, insn);
}
-
- /* Check if first/last set in this block for classic gcse,
- but not for copy/constant propagation. */
- if (optimize_size && !set_p)
-
- {
- rtx dest = SET_DEST (pat);
-
- while (GET_CODE (dest) == SUBREG
- || GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
- || GET_CODE (dest) == STRICT_LOW_PART)
- dest = XEXP (dest, 0);
- if (GET_CODE (dest) == REG)
- maybe_set_rd_gen (REGNO (dest), insn);
- }
}
static void
int in_libcall_block;
{
rtx pat = PATTERN (insn);
+ int i;
/* Pick out the sets of INSN and for other forms of instructions record
what's been modified. */
if (GET_CODE (pat) == SET && ! in_libcall_block)
- hash_scan_set (pat, insn, set_p);
- else if (GET_CODE (pat) == PARALLEL)
{
- int i;
-
- for (i = 0; i < XVECLEN (pat, 0); i++)
- {
- rtx x = XVECEXP (pat, 0, i);
+ /* Ignore obvious no-ops. */
+ if (SET_SRC (pat) != SET_DEST (pat))
+ hash_scan_set (pat, insn, set_p);
+ }
+ else if (GET_CODE (pat) == PARALLEL)
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
- if (GET_CODE (x) == SET)
- {
- if (GET_CODE (SET_SRC (x)) == CALL)
- hash_scan_call (SET_SRC (x), insn);
+ if (GET_CODE (x) == SET)
+ {
+ if (GET_CODE (SET_SRC (x)) == CALL)
+ hash_scan_call (SET_SRC (x), insn);
+ }
+ else if (GET_CODE (x) == CLOBBER)
+ hash_scan_clobber (x, insn);
+ else if (GET_CODE (x) == CALL)
+ hash_scan_call (x, insn);
+ }
- /* Check if first/last set in this block for classic
- gcse, but not for constant/copy propagation. */
- if (optimize_size && !set_p)
- {
- rtx dest = SET_DEST (x);
-
- while (GET_CODE (dest) == SUBREG
- || GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
- || GET_CODE (dest) == STRICT_LOW_PART)
- dest = XEXP (dest, 0);
- if (GET_CODE (dest) == REG)
- maybe_set_rd_gen (REGNO (dest), insn);
- }
- }
- else if (GET_CODE (x) == CLOBBER)
- hash_scan_clobber (x, insn);
- else if (GET_CODE (x) == CALL)
- hash_scan_call (x, insn);
- }
- }
else if (GET_CODE (pat) == CLOBBER)
hash_scan_clobber (pat, insn);
else if (GET_CODE (pat) == CALL)
static void
dump_hash_table (file, name, table, table_size, total_size)
FILE *file;
- char *name;
+ const char *name;
struct expr **table;
int table_size, total_size;
{
int i;
/* Flattened out table, so it's printed in proper order. */
- struct expr **flat_table = (struct expr **) alloca (total_size * sizeof (struct expr *));
- unsigned int *hash_val = (unsigned int *) alloca (total_size * sizeof (unsigned int));
+ struct expr **flat_table;
+ unsigned int *hash_val;
+ struct expr *expr;
- bzero ((char *) flat_table, total_size * sizeof (struct expr *));
- for (i = 0; i < table_size; i++)
- {
- struct expr *expr;
+ flat_table
+ = (struct expr **) xcalloc (total_size, sizeof (struct expr *));
+ hash_val = (unsigned int *) xmalloc (total_size * sizeof (unsigned int));
- for (expr = table[i]; expr != NULL; expr = expr->next_same_hash)
- {
- flat_table[expr->bitmap_index] = expr;
- hash_val[expr->bitmap_index] = i;
- }
- }
+ for (i = 0; i < table_size; i++)
+ for (expr = table[i]; expr != NULL; expr = expr->next_same_hash)
+ {
+ flat_table[expr->bitmap_index] = expr;
+ hash_val[expr->bitmap_index] = i;
+ }
fprintf (file, "%s hash table (%d buckets, %d entries)\n",
name, table_size, total_size);
for (i = 0; i < total_size; i++)
- {
- struct expr *expr = flat_table[i];
-
- fprintf (file, "Index %d (hash value %d)\n ",
- expr->bitmap_index, hash_val[i]);
- print_rtl (file, expr->expr);
- fprintf (file, "\n");
- }
+ if (flat_table[i] != 0)
+ {
+ expr = flat_table[i];
+ fprintf (file, "Index %d (hash value %d)\n ",
+ expr->bitmap_index, hash_val[i]);
+ print_rtl (file, expr->expr);
+ fprintf (file, "\n");
+ }
fprintf (file, "\n");
+
+ free (flat_table);
+ free (hash_val);
}
/* Record register first/last/block set information for REGNO in INSN.
+
reg_first_set records the first place in the block where the register
is set and is used to compute "anticipatability".
+
reg_last_set records the last place in the block where the register
is set and is used to compute "availability".
+
reg_set_in_block records whether the register is set in the block
and is used to compute "transparency". */
{
if (reg_first_set[regno] == NEVER_SET)
reg_first_set[regno] = INSN_CUID (insn);
+
reg_last_set[regno] = INSN_CUID (insn);
SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno);
}
{
if (mem_first_set == NEVER_SET)
mem_first_set = INSN_CUID (insn);
+
mem_last_set = INSN_CUID (insn);
mem_set_in_block[BLOCK_NUM (insn)] = 1;
}
-/* Used for communicating between next two routines. */
-static rtx last_set_insn;
-
/* Called from compute_hash_table via note_stores to handle one
- SET or CLOBBER in an insn. */
+ SET or CLOBBER in an insn. DATA is really the instruction in which
+ the SET is taking place. */
static void
-record_last_set_info (dest, setter)
+record_last_set_info (dest, setter, data)
rtx dest, setter ATTRIBUTE_UNUSED;
+ void *data;
{
+ rtx last_set_insn = (rtx) data;
+
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
- they are of the form (set (pseudo-reg) src),
- src is something we want to perform const/copy propagation on,
- none of the operands or target are subsequently modified in the block
+
Currently src must be a pseudo-reg or a const_int.
F is the first insn.
SET_P is non-zero for computing the assignment hash table. */
static void
-compute_hash_table (f, set_p)
- rtx f ATTRIBUTE_UNUSED;
+compute_hash_table (set_p)
int set_p;
{
int bb;
for (bb = 0; bb < n_basic_blocks; bb++)
{
rtx insn;
- int regno;
+ unsigned int regno;
int in_libcall_block;
- int i;
+ unsigned int i;
/* First pass over the instructions records information used to
determine when registers and memory are first and last set.
for (i = 0; i < max_gcse_regno; i++)
reg_first_set[i] = reg_last_set[i] = NEVER_SET;
+
mem_first_set = NEVER_SET;
mem_last_set = NEVER_SET;
&& regno != FRAME_POINTER_REGNUM)
|| global_regs[regno])
record_last_reg_set_info (insn, regno);
+
if (! CONST_CALL_P (insn))
record_last_mem_set_info (insn);
}
- last_set_insn = insn;
- note_stores (PATTERN (insn), record_last_set_info);
+ note_stores (PATTERN (insn), record_last_set_info, insn);
}
/* The next pass builds the hash table. */
for (insn = BLOCK_HEAD (bb), in_libcall_block = 0;
insn && insn != NEXT_INSN (BLOCK_END (bb));
insn = NEXT_INSN (insn))
- {
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
- in_libcall_block = 1;
- else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
- in_libcall_block = 0;
- hash_scan_insn (insn, set_p, in_libcall_block);
- }
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ {
+ if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
+ in_libcall_block = 1;
+ else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ in_libcall_block = 0;
+ hash_scan_insn (insn, set_p, in_libcall_block);
}
}
free (reg_first_set);
free (reg_last_set);
+
/* Catch bugs early. */
reg_first_set = reg_last_set = 0;
}
set_hash_table_size = n_insns / 4;
if (set_hash_table_size < 11)
set_hash_table_size = 11;
+
/* Attempt to maintain efficient use of hash table.
Making it an odd number is simplest for now.
??? Later take some measurements. */
/* Compute the hash table for doing copy/const propagation. */
static void
-compute_set_hash_table (f)
- rtx f;
+compute_set_hash_table ()
{
/* Initialize count of number of entries in hash table. */
n_sets = 0;
- bzero ((char *) set_hash_table, set_hash_table_size * sizeof (struct expr *));
+ bzero ((char *) set_hash_table,
+ set_hash_table_size * sizeof (struct expr *));
- compute_hash_table (f, 1);
+ compute_hash_table (1);
}
/* Allocate space for the expression hash table.
static void
alloc_expr_hash_table (n_insns)
- int n_insns;
+ unsigned int n_insns;
{
int n;
/* Make sure the amount is usable. */
if (expr_hash_table_size < 11)
expr_hash_table_size = 11;
+
/* Attempt to maintain efficient use of hash table.
Making it an odd number is simplest for now.
??? Later take some measurements. */
/* Compute the hash table for doing GCSE. */
static void
-compute_expr_hash_table (f)
- rtx f;
+compute_expr_hash_table ()
{
/* Initialize count of number of entries in hash table. */
n_exprs = 0;
- bzero ((char *) expr_hash_table, expr_hash_table_size * sizeof (struct expr *));
+ bzero ((char *) expr_hash_table,
+ expr_hash_table_size * sizeof (struct expr *));
- compute_hash_table (f, 0);
+ compute_hash_table (0);
}
\f
/* Expression tracking support. */
return expr;
}
-/* Lookup REGNO in the set table.
- If PAT is non-NULL look for the entry that matches it, otherwise return
- the first entry for REGNO.
- The result is a pointer to the table entry, or NULL if not found. */
+/* Lookup REGNO in the set table. If PAT is non-NULL look for the entry that
+ matches it, otherwise return the first entry for REGNO. The result is a
+ pointer to the table entry, or NULL if not found. */
static struct expr *
lookup_set (regno, pat)
- int regno;
+ unsigned int regno;
rtx pat;
{
unsigned int hash = hash_set (regno, set_hash_table_size);
static struct expr *
next_set (regno, expr)
- int regno;
+ unsigned int regno;
struct expr *expr;
{
do
expr = expr->next_same_hash;
while (expr && REGNO (SET_DEST (expr->expr)) != regno);
+
return expr;
}
/* Maintain a bitmap of which regs have been set since beginning of
the block. */
sbitmap_zero (reg_set_bitmap);
+
/* Also keep a record of the last instruction to modify memory.
For now this is very trivial, we only record whether any memory
location has been modified. */
oprs_not_set_p (x, insn)
rtx x, insn;
{
- int i;
+ int i, j;
enum rtx_code code;
- char *fmt;
-
- /* repeat is used to turn tail-recursion into iteration. */
-repeat:
+ const char *fmt;
if (x == 0)
return 1;
case MEM:
if (mem_last_set != 0)
return 0;
- x = XEXP (x, 0);
- goto repeat;
+ else
+ return oprs_not_set_p (XEXP (x, 0), insn);
case REG:
return ! TEST_BIT (reg_set_bitmap, REGNO (x));
break;
}
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
- int not_set_p;
/* If we are about to do the last recursive call
needed at this level, change it into iteration.
This function is called enough to be worth it. */
if (i == 0)
- {
- x = XEXP (x, 0);
- goto repeat;
- }
- not_set_p = oprs_not_set_p (XEXP (x, i), insn);
- if (! not_set_p)
+ return oprs_not_set_p (XEXP (x, i), insn);
+
+ if (! oprs_not_set_p (XEXP (x, i), insn))
return 0;
}
else if (fmt[i] == 'E')
- {
- int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- {
- int not_set_p = oprs_not_set_p (XVECEXP (x, i, j), insn);
- if (! not_set_p)
- return 0;
- }
- }
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
+ return 0;
}
return 1;
/* Mark things set by a CALL. */
static void
-mark_call (pat, insn)
- rtx pat ATTRIBUTE_UNUSED, insn;
+mark_call (insn)
+ rtx insn;
{
mem_last_set = INSN_CUID (insn);
}
mem_last_set = INSN_CUID (insn);
if (GET_CODE (SET_SRC (pat)) == CALL)
- mark_call (SET_SRC (pat), insn);
+ mark_call (insn);
}
/* Record things set by a CLOBBER. */
rtx insn;
{
rtx pat = PATTERN (insn);
+ int i;
if (GET_CODE (pat) == SET)
mark_set (pat, insn);
else if (GET_CODE (pat) == PARALLEL)
- {
- int i;
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+
+ if (GET_CODE (x) == SET)
+ mark_set (x, insn);
+ else if (GET_CODE (x) == CLOBBER)
+ mark_clobber (x, insn);
+ else if (GET_CODE (x) == CALL)
+ mark_call (insn);
+ }
- for (i = 0; i < XVECLEN (pat, 0); i++)
- {
- rtx x = XVECEXP (pat, 0, i);
-
- if (GET_CODE (x) == SET)
- mark_set (x, insn);
- else if (GET_CODE (x) == CLOBBER)
- mark_clobber (x, insn);
- else if (GET_CODE (x) == CALL)
- mark_call (x, insn);
- }
- }
else if (GET_CODE (pat) == CLOBBER)
mark_clobber (pat, insn);
else if (GET_CODE (pat) == CALL)
- mark_call (pat, insn);
+ mark_call (insn);
}
+
\f
/* Classic GCSE reaching definition support. */
free (rd_out);
}
-/* Add INSN to the kills of BB.
- REGNO, set in BB, is killed by INSN. */
+/* Add INSN to the kills of BB. REGNO, set in BB, is killed by INSN. */
static void
handle_rd_kill_set (insn, regno, bb)
rtx insn;
int regno, bb;
{
- struct reg_set *this_reg = reg_set_table[regno];
-
- while (this_reg)
- {
- if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
- SET_BIT (rd_kill[bb], INSN_CUID (this_reg->insn));
- this_reg = this_reg->next;
- }
-}
-
-void
-dump_rd_table (file, title, bmap)
- FILE *file;
- char *title;
- sbitmap *bmap;
-{
- int bb,cuid,i,j,n;
+ struct reg_set *this_reg;
- fprintf (file, "%s\n", title);
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- fprintf (file, "BB %d\n", bb);
- dump_sbitmap (file, bmap[bb]);
- for (i = n = cuid = 0; i < bmap[bb]->size; i++)
- {
- for (j = 0; j < SBITMAP_ELT_BITS; j++, cuid++)
- {
- if ((bmap[bb]->elms[i] & (1 << j)) != 0)
- {
- if (n % 10 == 0)
- fprintf (file, " ");
- fprintf (file, " %d", INSN_UID (CUID_INSN (cuid)));
- n++;
- }
- }
- }
- if (n != 0)
- fprintf (file, "\n");
- }
- fprintf (file, "\n");
+ for (this_reg = reg_set_table[regno]; this_reg; this_reg = this_reg ->next)
+ if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
+ SET_BIT (rd_kill[bb], INSN_CUID (this_reg->insn));
}
/* Compute the set of kill's for reaching definitions. */
static void
compute_kill_rd ()
{
- int bb,cuid;
+ int bb, cuid;
+ int regno, i;
/* For each block
For each set bit in `gen' of the block (i.e each insn which
- generates a definition in the block)
- Call the reg set by the insn corresponding to that bit regx
- Look at the linked list starting at reg_set_table[regx]
- For each setting of regx in the linked list, which is not in
- this block
- Set the bit in `kill' corresponding to that insn
- */
-
+ generates a definition in the block)
+ Call the reg set by the insn corresponding to that bit regx
+ Look at the linked list starting at reg_set_table[regx]
+ For each setting of regx in the linked list, which is not in
+ this block
+ Set the bit in `kill' corresponding to that insn. */
for (bb = 0; bb < n_basic_blocks; bb++)
- {
- for (cuid = 0; cuid < max_cuid; cuid++)
+ for (cuid = 0; cuid < max_cuid; cuid++)
+ if (TEST_BIT (rd_gen[bb], cuid))
{
- if (TEST_BIT (rd_gen[bb], cuid))
- {
- rtx insn = CUID_INSN (cuid);
- rtx pat = PATTERN (insn);
+ rtx insn = CUID_INSN (cuid);
+ rtx pat = PATTERN (insn);
- if (GET_CODE (insn) == CALL_INSN)
- {
- int regno;
-
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- {
- if ((call_used_regs[regno]
- && regno != STACK_POINTER_REGNUM
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+ {
+ if ((call_used_regs[regno]
+ && regno != STACK_POINTER_REGNUM
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
- && regno != HARD_FRAME_POINTER_REGNUM
+ && regno != HARD_FRAME_POINTER_REGNUM
#endif
#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
- && ! (regno == ARG_POINTER_REGNUM
- && fixed_regs[regno])
+ && ! (regno == ARG_POINTER_REGNUM
+ && fixed_regs[regno])
#endif
#if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
- && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
+ && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
#endif
- && regno != FRAME_POINTER_REGNUM)
- || global_regs[regno])
- handle_rd_kill_set (insn, regno, bb);
- }
- }
+ && regno != FRAME_POINTER_REGNUM)
+ || global_regs[regno])
+ handle_rd_kill_set (insn, regno, bb);
+ }
+ }
- if (GET_CODE (pat) == PARALLEL)
+ if (GET_CODE (pat) == PARALLEL)
+ {
+ for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
{
- int i;
+ enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
- /* We work backwards because ... */
- for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
- {
- enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
- if ((code == SET || code == CLOBBER)
- && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
- handle_rd_kill_set (insn,
- REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
- bb);
- }
+ if ((code == SET || code == CLOBBER)
+ && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
+ handle_rd_kill_set (insn,
+ REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
+ bb);
}
- else if (GET_CODE (pat) == SET)
- {
- if (GET_CODE (SET_DEST (pat)) == REG)
- {
- /* Each setting of this register outside of this block
- must be marked in the set of kills in this block. */
- handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
- }
- }
- /* FIXME: CLOBBER? */
- }
+ }
+ else if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == REG)
+ /* Each setting of this register outside of this block
+ must be marked in the set of kills in this block. */
+ handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
}
- }
}
/* Compute the reaching definitions as in
{
changed = 0;
for (bb = 0; bb < n_basic_blocks; bb++)
- {
- sbitmap_union_of_predecessors (reaching_defs[bb], rd_out,
- bb, s_preds);
+ {
+ sbitmap_union_of_preds (reaching_defs[bb], rd_out, bb);
changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
reaching_defs[bb], rd_kill[bb]);
- }
+ }
passes++;
}
static void
compute_ae_gen ()
{
- int i;
+ unsigned int i;
+ struct expr *expr;
+ struct occr *occr;
/* For each recorded occurrence of each expression, set ae_gen[bb][expr].
This is all we have to do because an expression is not recorded if it
is not available, and the only expressions we want to work with are the
ones that are recorded. */
-
for (i = 0; i < expr_hash_table_size; i++)
- {
- struct expr *expr = expr_hash_table[i];
- while (expr != NULL)
- {
- struct occr *occr = expr->avail_occr;
- while (occr != NULL)
- {
- SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
- occr = occr->next;
- }
- expr = expr->next_same_hash;
- }
- }
+ for (expr = expr_hash_table[i]; expr != 0; expr = expr->next_same_hash)
+ for (occr = expr->avail_occr; occr != 0; occr = occr->next)
+ SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
}
/* Return non-zero if expression X is killed in BB. */
rtx x;
int bb;
{
- int i;
+ int i, j;
enum rtx_code code;
- char *fmt;
-
- /* repeat is used to turn tail-recursion into iteration. */
- repeat:
+ const char *fmt;
if (x == 0)
return 1;
case MEM:
if (mem_set_in_block[bb])
return 1;
- x = XEXP (x, 0);
- goto repeat;
+ else
+ return expr_killed_p (XEXP (x, 0), bb);
case PC:
case CC0: /*FIXME*/
break;
}
- i = GET_RTX_LENGTH (code) - 1;
- fmt = GET_RTX_FORMAT (code);
- for (; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
- rtx tem = XEXP (x, i);
-
/* If we are about to do the last recursive call
needed at this level, change it into iteration.
This function is called enough to be worth it. */
if (i == 0)
- {
- x = tem;
- goto repeat;
- }
- if (expr_killed_p (tem, bb))
+ return expr_killed_p (XEXP (x, i), bb);
+ else if (expr_killed_p (XEXP (x, i), bb))
return 1;
}
else if (fmt[i] == 'E')
- {
- int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- {
- if (expr_killed_p (XVECEXP (x, i, j), bb))
- return 1;
- }
- }
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (expr_killed_p (XVECEXP (x, i, j), bb))
+ return 1;
}
return 0;
/* Compute the set of available expressions killed in each basic block. */
static void
-compute_ae_kill ()
+compute_ae_kill (ae_gen, ae_kill)
+ sbitmap *ae_gen, *ae_kill;
{
- int bb,i;
+ int bb;
+ unsigned int i;
+ struct expr *expr;
for (bb = 0; bb < n_basic_blocks; bb++)
- {
- for (i = 0; i < expr_hash_table_size; i++)
+ for (i = 0; i < expr_hash_table_size; i++)
+ for (expr = expr_hash_table[i]; expr; expr = expr->next_same_hash)
{
- struct expr *expr = expr_hash_table[i];
-
- for ( ; expr != NULL; expr = expr->next_same_hash)
- {
- /* Skip EXPR if generated in this block. */
- if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
- continue;
-
- if (expr_killed_p (expr->expr, bb))
- SET_BIT (ae_kill[bb], expr->bitmap_index);
- }
- }
- }
-}
-
-/* Compute available expressions.
-
- Implement the algorithm to find available expressions
- as given in the Aho Sethi Ullman book, pages 627-631. */
-
-static void
-compute_available ()
-{
- int bb, changed, passes;
-
- sbitmap_zero (ae_in[0]);
-
- sbitmap_copy (ae_out[0] /*dst*/, ae_gen[0] /*src*/);
+ /* Skip EXPR if generated in this block. */
+ if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
+ continue;
- for (bb = 1; bb < n_basic_blocks; bb++)
- sbitmap_difference (ae_out[bb], u_bitmap, ae_kill[bb]);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 1; bb < n_basic_blocks; bb++)
- {
- sbitmap_intersect_of_predecessors (ae_in[bb], ae_out,
- bb, s_preds);
- changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb],
- ae_in[bb], ae_kill[bb]);
+ if (expr_killed_p (expr->expr, bb))
+ SET_BIT (ae_kill[bb], expr->bitmap_index);
}
- passes++;
- }
-
- if (gcse_file)
- fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
}
\f
/* Actually perform the Classic GCSE optimizations. */
the closest such expression. */
static int
-expr_reaches_here_p (occr, expr, bb, check_self_loop, visited)
+expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited)
struct occr *occr;
struct expr *expr;
int bb;
int check_self_loop;
char *visited;
{
- int_list_ptr pred;
-
- if (visited == NULL)
- {
- visited = (char *) alloca (n_basic_blocks);
- bzero (visited, n_basic_blocks);
- }
+ edge pred;
- for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
+ for (pred = BASIC_BLOCK(bb)->pred; pred != NULL; pred = pred->pred_next)
{
- int pred_bb = INT_LIST_VAL (pred);
+ int pred_bb = pred->src->index;
if (visited[pred_bb])
- {
- /* This predecessor has already been visited.
- Nothing to do. */
+ /* This predecessor has already been visited. Nothing to do. */
;
- }
else if (pred_bb == bb)
- {
+ {
/* BB loops on itself. */
if (check_self_loop
&& TEST_BIT (ae_gen[pred_bb], expr->bitmap_index)
&& BLOCK_NUM (occr->insn) == pred_bb)
return 1;
+
visited[pred_bb] = 1;
- }
+ }
+
/* Ignore this predecessor if it kills the expression. */
else if (TEST_BIT (ae_kill[pred_bb], expr->bitmap_index))
visited[pred_bb] = 1;
+
/* Does this predecessor generate this expression? */
else if (TEST_BIT (ae_gen[pred_bb], expr->bitmap_index))
{
so we just need to check the block number. */
if (BLOCK_NUM (occr->insn) == pred_bb)
return 1;
+
visited[pred_bb] = 1;
}
+
/* Neither gen nor kill. */
else
- {
+ {
visited[pred_bb] = 1;
- if (expr_reaches_here_p (occr, expr, pred_bb, check_self_loop, visited))
+ if (expr_reaches_here_p_work (occr, expr, pred_bb, check_self_loop,
+ visited))
+
return 1;
- }
+ }
}
/* All paths have been checked. */
return 0;
}
+/* This wrapper for expr_reaches_here_p_work() is to ensure that any
+ memory allocated for that function is returned. */
+
+static int
+expr_reaches_here_p (occr, expr, bb, check_self_loop)
+ struct occr *occr;
+ struct expr *expr;
+ int bb;
+ int check_self_loop;
+{
+ int rval;
+ char *visited = (char *) xcalloc (n_basic_blocks, 1);
+
+ rval = expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited);
+
+ free (visited);
+ return rval;
+}
+
/* Return the instruction that computes EXPR that reaches INSN's basic block.
If there is more than one such instruction, return NULL.
if (expr->avail_occr->next == NULL)
{
if (BLOCK_NUM (expr->avail_occr->insn) == bb)
- {
- /* The available expression is actually itself
- (i.e. a loop in the flow graph) so do nothing. */
- return NULL;
- }
+ /* The available expression is actually itself
+ (i.e. a loop in the flow graph) so do nothing. */
+ return NULL;
+
/* (FIXME) Case that we found a pattern that was created by
a substitution that took place. */
return expr->avail_occr->insn;
The only time we care about this is when the expression
is generated later in the block [and thus there's a loop].
We let the normal cse pass handle the other cases. */
- if (INSN_CUID (insn) < INSN_CUID (occr->insn))
- {
- if (expr_reaches_here_p (occr, expr, bb, 1, NULL))
- {
- can_reach++;
- if (can_reach > 1)
- return NULL;
- insn_computes_expr = occr->insn;
- }
- }
- }
- else /* Computation of the pattern outside this block. */
- {
- if (expr_reaches_here_p (occr, expr, bb, 0, NULL))
+ if (INSN_CUID (insn) < INSN_CUID (occr->insn)
+ && expr_reaches_here_p (occr, expr, bb, 1))
{
can_reach++;
if (can_reach > 1)
return NULL;
+
insn_computes_expr = occr->insn;
}
}
+ else if (expr_reaches_here_p (occr, expr, bb, 0))
+ {
+ can_reach++;
+ if (can_reach > 1)
+ return NULL;
+
+ insn_computes_expr = occr->insn;
+ }
}
if (insn_computes_expr == NULL)
abort ();
+
return insn_computes_expr;
}
}
if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn))
{
if (INSN_CUID (def_insn) < INSN_CUID (insn))
- {
+ {
if (GET_CODE (PATTERN (def_insn)) == PARALLEL)
return 1;
- if (GET_CODE (PATTERN (def_insn)) == CLOBBER)
+ else if (GET_CODE (PATTERN (def_insn)) == CLOBBER)
reg = XEXP (PATTERN (def_insn), 0);
else if (GET_CODE (PATTERN (def_insn)) == SET)
reg = SET_DEST (PATTERN (def_insn));
else
abort ();
+
return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn);
}
else
return 0;
}
-/* Return non-zero if *ADDR_THIS_REG can only have one value at INSN.
- The value returned is the number of definitions that reach INSN.
- Returning a value of zero means that [maybe] more than one definition
- reaches INSN and the caller can't perform whatever optimization it is
- trying. i.e. it is always safe to return zero. */
+/* Return non-zero if *ADDR_THIS_REG can only have one value at INSN. The
+ value returned is the number of definitions that reach INSN. Returning a
+ value of zero means that [maybe] more than one definition reaches INSN and
+ the caller can't perform whatever optimization it is trying. i.e. it is
+ always safe to return zero. */
static int
can_disregard_other_sets (addr_this_reg, insn, for_combine)
int for_combine;
{
int number_of_reaching_defs = 0;
- struct reg_set *this_reg = *addr_this_reg;
+ struct reg_set *this_reg;
- while (this_reg)
- {
- if (def_reaches_here_p (insn, this_reg->insn))
- {
- number_of_reaching_defs++;
- /* Ignore parallels for now. */
- if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL)
- return 0;
- if (!for_combine
- && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER
- || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
- SET_SRC (PATTERN (insn)))))
- {
- /* A setting of the reg to a different value reaches INSN. */
+ for (this_reg = *addr_this_reg; this_reg != 0; this_reg = this_reg->next)
+ if (def_reaches_here_p (insn, this_reg->insn))
+ {
+ number_of_reaching_defs++;
+ /* Ignore parallels for now. */
+ if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL)
+ return 0;
+
+ if (!for_combine
+ && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER
+ || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
+ SET_SRC (PATTERN (insn)))))
+ /* A setting of the reg to a different value reaches INSN. */
+ return 0;
+
+ if (number_of_reaching_defs > 1)
+ {
+ /* If in this setting the value the register is being set to is
+ equal to the previous value the register was set to and this
+ setting reaches the insn we are trying to do the substitution
+ on then we are ok. */
+ if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER)
return 0;
- }
- if (number_of_reaching_defs > 1)
- {
- /* If in this setting the value the register is being
- set to is equal to the previous value the register
- was set to and this setting reaches the insn we are
- trying to do the substitution on then we are ok. */
-
- if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER)
- return 0;
- if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
- SET_SRC (PATTERN (insn))))
- return 0;
- }
- *addr_this_reg = this_reg;
- }
+ else if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
+ SET_SRC (PATTERN (insn))))
+ return 0;
+ }
- /* prev_this_reg = this_reg; */
- this_reg = this_reg->next;
- }
+ *addr_this_reg = this_reg;
+ }
return number_of_reaching_defs;
}
/* At this point we know only one computation of EXPR outside of this
block reaches this insn. Now try to find a register that the
expression is computed into. */
-
if (GET_CODE (SET_SRC (PATTERN (insn_computes_expr))) == REG)
{
/* This is the case when the available expression that reaches
here has already been handled as an available expression. */
- int regnum_for_replacing = REGNO (SET_SRC (PATTERN (insn_computes_expr)));
+ unsigned int regnum_for_replacing
+ = REGNO (SET_SRC (PATTERN (insn_computes_expr)));
+
/* If the register was created by GCSE we can't use `reg_set_table',
however we know it's set only once. */
if (regnum_for_replacing >= max_gcse_regno
if (!found_setting)
{
- int regnum_for_replacing = REGNO (SET_DEST (PATTERN (insn_computes_expr)));
+ unsigned int regnum_for_replacing
+ = REGNO (SET_DEST (PATTERN (insn_computes_expr)));
+
/* This shouldn't happen. */
if (regnum_for_replacing >= max_gcse_regno)
abort ();
+
this_reg = reg_set_table[regnum_for_replacing];
+
/* If the register the expression is computed into is set only once,
or only one set reaches this insn, use it. */
if (this_reg->next == NULL
gcse_subst_count++;
if (gcse_file != NULL)
{
- fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d %s insn %d\n",
- INSN_UID (insn), REGNO (to),
- use_src ? "from" : "set in",
+ fprintf (gcse_file, "GCSE: Replacing the source in insn %d with",
+ INSN_UID (insn));
+ fprintf (gcse_file, " reg %d %s insn %d\n",
+ REGNO (to), use_src ? "from" : "set in",
INSN_UID (insn_computes_expr));
}
-
}
}
+
/* The register that the expr is computed into is set more than once. */
else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/)
{
an insn. I think this is ok. */
new_insn
= emit_insn_after (gen_rtx_SET (VOIDmode, to,
- SET_DEST (PATTERN (insn_computes_expr))),
- insn_computes_expr);
+ SET_DEST (PATTERN
+ (insn_computes_expr))),
+ insn_computes_expr);
+
/* Keep block number table up to date. */
set_block_num (new_insn, BLOCK_NUM (insn_computes_expr));
+
/* Keep register set table up to date. */
record_one_set (REGNO (to), new_insn);
gcse_create_count++;
if (gcse_file != NULL)
- {
- fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d, computed in insn %d,\n",
+ {
+ fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d",
INSN_UID (NEXT_INSN (insn_computes_expr)),
- REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))),
+ REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))));
+ fprintf (gcse_file, ", computed in insn %d,\n",
INSN_UID (insn_computes_expr));
- fprintf (gcse_file, " into newly allocated reg %d\n", REGNO (to));
- }
+ fprintf (gcse_file, " into newly allocated reg %d\n",
+ REGNO (to));
+ }
pat = PATTERN (insn);
/* Do register replacement for INSN. */
changed = validate_change (insn, &SET_SRC (pat),
- SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr))),
+ SET_DEST (PATTERN
+ (NEXT_INSN (insn_computes_expr))),
0);
/* We should be able to ignore the return code from validate_change but
gcse_subst_count++;
if (gcse_file != NULL)
{
- fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d set in insn %d\n",
+ fprintf (gcse_file,
+ "GCSE: Replacing the source in insn %d with reg %d ",
INSN_UID (insn),
- REGNO (SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr)))),
+ REGNO (SET_DEST (PATTERN (NEXT_INSN
+ (insn_computes_expr)))));
+ fprintf (gcse_file, "set in insn %d\n",
INSN_UID (insn_computes_expr));
}
-
}
}
return changed;
}
-/* Perform classic GCSE.
- This is called by one_classic_gcse_pass after all the dataflow analysis
- has been done.
+/* Perform classic GCSE. This is called by one_classic_gcse_pass after all
+ the dataflow analysis has been done.
The result is non-zero if a change was made. */
insn = NEXT_INSN (insn))
{
/* Is insn of form (set (pseudo-reg) ...)? */
-
if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) == SET
&& GET_CODE (SET_DEST (PATTERN (insn))) == REG
/* ??? Need to be careful w.r.t. mods done to INSN. */
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
mark_oprs_set (insn);
- }
+ }
}
return changed;
Return non-zero if a change was made. */
static int
-one_classic_gcse_pass (f, pass)
- rtx f;
+one_classic_gcse_pass (pass)
int pass;
{
int changed = 0;
alloc_expr_hash_table (max_cuid);
alloc_rd_mem (n_basic_blocks, max_cuid);
- compute_expr_hash_table (f);
+ compute_expr_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "Expression", expr_hash_table,
expr_hash_table_size, n_exprs);
+
if (n_exprs > 0)
{
compute_kill_rd ();
compute_rd ();
alloc_avail_expr_mem (n_basic_blocks, n_exprs);
compute_ae_gen ();
- compute_ae_kill ();
- compute_available ();
+ compute_ae_kill (ae_gen, ae_kill);
+ compute_available (ae_gen, ae_kill, ae_out, ae_in);
changed = classic_gcse ();
free_avail_expr_mem ();
}
+
free_rd_mem ();
free_expr_hash_table ();
if (gcse_file)
{
fprintf (gcse_file, "\n");
- fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
- current_function_name, pass,
- bytes_used, gcse_subst_count, gcse_create_count);
+ fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs,",
+ current_function_name, pass, bytes_used, gcse_subst_count);
+ fprintf (gcse_file, "%d insns created\n", gcse_create_count);
}
return changed;
/* Compute copy/constant propagation working variables. */
/* Local properties of assignments. */
-
static sbitmap *cprop_pavloc;
static sbitmap *cprop_absaltered;
/* Global properties of assignments (computed from the local properties). */
-
static sbitmap *cprop_avin;
static sbitmap *cprop_avout;
-/* Allocate vars used for copy/const propagation.
- N_BLOCKS is the number of basic blocks.
- N_SETS is the number of sets. */
+/* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
+ basic blocks. N_SETS is the number of sets. */
static void
alloc_cprop_mem (n_blocks, n_sets)
free (cprop_avout);
}
-/* Dump copy/const propagation data. */
-
-void
-dump_cprop_data (file)
- FILE *file;
-{
- dump_sbitmap_vector (file, "CPROP partially locally available sets", "BB",
- cprop_pavloc, n_basic_blocks);
- dump_sbitmap_vector (file, "CPROP absolutely altered sets", "BB",
- cprop_absaltered, n_basic_blocks);
-
- dump_sbitmap_vector (file, "CPROP available incoming sets", "BB",
- cprop_avin, n_basic_blocks);
- dump_sbitmap_vector (file, "CPROP available outgoing sets", "BB",
- cprop_avout, n_basic_blocks);
-}
-
-/* For each block, compute whether X is transparent.
- X is either an expression or an assignment [though we don't care which,
- for this context an assignment is treated as an expression].
- For each block where an element of X is modified, set (SET_P == 1) or reset
- (SET_P == 0) the INDX bit in BMAP. */
+/* For each block, compute whether X is transparent. X is either an
+ expression or an assignment [though we don't care which, for this context
+ an assignment is treated as an expression]. For each block where an
+ element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX
+ bit in BMAP. */
static void
compute_transp (x, indx, bmap, set_p)
sbitmap *bmap;
int set_p;
{
- int bb,i;
+ int bb, i, j;
enum rtx_code code;
- char *fmt;
+ reg_set *r;
+ const char *fmt;
- /* repeat is used to turn tail-recursion into iteration. */
+ /* repeat is used to turn tail-recursion into iteration since GCC
+ can't do it when there's no return value. */
repeat:
if (x == 0)
switch (code)
{
case REG:
- {
- reg_set *r;
- int regno = REGNO (x);
+ if (set_p)
+ {
+ if (REGNO (x) < FIRST_PSEUDO_REGISTER)
+ {
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ if (TEST_BIT (reg_set_in_block[bb], REGNO (x)))
+ SET_BIT (bmap[bb], indx);
+ }
+ else
+ {
+ for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
+ SET_BIT (bmap[BLOCK_NUM (r->insn)], indx);
+ }
+ }
+ else
+ {
+ if (REGNO (x) < FIRST_PSEUDO_REGISTER)
+ {
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ if (TEST_BIT (reg_set_in_block[bb], REGNO (x)))
+ RESET_BIT (bmap[bb], indx);
+ }
+ else
+ {
+ for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
+ RESET_BIT (bmap[BLOCK_NUM (r->insn)], indx);
+ }
+ }
- if (set_p)
- {
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- for (bb = 0; bb < n_basic_blocks; bb++)
- if (TEST_BIT (reg_set_in_block[bb], regno))
- SET_BIT (bmap[bb], indx);
- }
- else
- {
- for (r = reg_set_table[regno]; r != NULL; r = r->next)
- {
- bb = BLOCK_NUM (r->insn);
- SET_BIT (bmap[bb], indx);
- }
- }
- }
- else
- {
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- for (bb = 0; bb < n_basic_blocks; bb++)
- if (TEST_BIT (reg_set_in_block[bb], regno))
- RESET_BIT (bmap[bb], indx);
- }
- else
- {
- for (r = reg_set_table[regno]; r != NULL; r = r->next)
- {
- bb = BLOCK_NUM (r->insn);
- RESET_BIT (bmap[bb], indx);
- }
- }
- }
- return;
- }
+ return;
case MEM:
if (set_p)
if (mem_set_in_block[bb])
RESET_BIT (bmap[bb], indx);
}
+
x = XEXP (x, 0);
goto repeat;
break;
}
- i = GET_RTX_LENGTH (code) - 1;
- fmt = GET_RTX_FORMAT (code);
- for (; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
- rtx tem = XEXP (x, i);
-
/* If we are about to do the last recursive call
needed at this level, change it into iteration.
This function is called enough to be worth it. */
if (i == 0)
{
- x = tem;
+ x = XEXP (x, i);
goto repeat;
}
- compute_transp (tem, indx, bmap, set_p);
- }
- else if (fmt[i] == 'E')
- {
- int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
- }
- }
-}
-
-static void
-compute_cprop_local_properties ()
-{
- int i;
-
- sbitmap_vector_zero (cprop_absaltered, n_basic_blocks);
- sbitmap_vector_zero (cprop_pavloc, n_basic_blocks);
-
- for (i = 0; i < set_hash_table_size; i++)
- {
- struct expr *expr;
-
- for (expr = set_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
- {
- struct occr *occr;
- int indx = expr->bitmap_index;
-
- /* The assignment is absolutely altered if any operand is modified
- by this block [excluding the assignment itself].
- We start by assuming all are transparent [none are killed], and
- then setting the bits for those that are. */
-
- compute_transp (expr->expr, indx, cprop_absaltered, 1);
-
- /* The occurrences recorded in avail_occr are exactly those that
- we want to set to non-zero in PAVLOC. */
-
- for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
- {
- int bb = BLOCK_NUM (occr->insn);
- SET_BIT (cprop_pavloc[bb], indx);
- }
- }
- }
-}
-
-static void
-compute_cprop_avinout ()
-{
- int bb, changed, passes;
- sbitmap_zero (cprop_avin[0]);
- sbitmap_vector_ones (cprop_avout, n_basic_blocks);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- if (bb != 0)
- sbitmap_intersect_of_predecessors (cprop_avin[bb], cprop_avout,
- bb, s_preds);
- changed |= sbitmap_union_of_diff (cprop_avout[bb],
- cprop_pavloc[bb],
- cprop_avin[bb],
- cprop_absaltered[bb]);
+ compute_transp (XEXP (x, i), indx, bmap, set_p);
}
- passes++;
+ else if (fmt[i] == 'E')
+ for (j = 0; j < XVECLEN (x, i); j++)
+ compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
}
-
- if (gcse_file)
- fprintf (gcse_file, "cprop avail expr computation: %d passes\n", passes);
}
/* Top level routine to do the dataflow analysis needed by copy/const
static void
compute_cprop_data ()
{
- compute_cprop_local_properties ();
- compute_cprop_avinout ();
+ compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, 1);
+ compute_available (cprop_pavloc, cprop_absaltered,
+ cprop_avout, cprop_avin);
}
\f
/* Copy/constant propagation. */
-struct reg_use {
- rtx reg_rtx;
-};
-
/* Maximum number of register uses in an insn that we handle. */
#define MAX_USES 8
/* Index into `reg_use_table' while building it. */
static int reg_use_count;
-/* Set up a list of register numbers used in INSN.
- The found uses are stored in `reg_use_table'.
- `reg_use_count' is initialized to zero before entry, and
- contains the number of uses in the table upon exit.
+/* Set up a list of register numbers used in INSN. The found uses are stored
+ in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
+ and contains the number of uses in the table upon exit.
- ??? If a register appears multiple times we will record it multiple
- times. This doesn't hurt anything but it will slow things down. */
+ ??? If a register appears multiple times we will record it multiple times.
+ This doesn't hurt anything but it will slow things down. */
static void
find_used_regs (x)
rtx x;
{
- int i;
+ int i, j;
enum rtx_code code;
- char *fmt;
+ const char *fmt;
- /* repeat is used to turn tail-recursion into iteration. */
+ /* repeat is used to turn tail-recursion into iteration since GCC
+ can't do it when there's no return value. */
repeat:
if (x == 0)
case REG:
if (reg_use_count == MAX_USES)
return;
+
reg_use_table[reg_use_count].reg_rtx = x;
reg_use_count++;
return;
/* Recursively scan the operands of this expression. */
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
x = XEXP (x, 0);
goto repeat;
}
+
find_used_regs (XEXP (x, i));
}
else if (fmt[i] == 'E')
- {
- int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- find_used_regs (XVECEXP (x, i, j));
- }
+ for (j = 0; j < XVECLEN (x, i); j++)
+ find_used_regs (XVECEXP (x, i, j));
}
}
try_replace_reg (from, to, insn)
rtx from, to, insn;
{
- return validate_replace_src (from, to, insn);
+ rtx note;
+ rtx src;
+ int success;
+ rtx set;
+
+ note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
+
+ if (!note)
+ note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
+
+ /* If this fails we could try to simplify the result of the
+ replacement and attempt to recognize the simplified insn.
+
+ But we need a general simplify_rtx that doesn't have pass
+ specific state variables. I'm not aware of one at the moment. */
+
+ success = validate_replace_src (from, to, insn);
+ set = single_set (insn);
+
+ /* We've failed to do replacement. Try to add REG_EQUAL note to not loose
+ information. */
+ if (!success && !note)
+ {
+ if (!set)
+ return 0;
+
+ note = REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_EQUAL,
+ copy_rtx (SET_SRC (set)),
+ REG_NOTES (insn));
+ }
+
+ /* Always do the replacement in REQ_EQUAL and REG_EQUIV notes. Also
+ try to simplify them. */
+ if (note)
+ {
+ rtx simplified;
+
+ src = XEXP (note, 0);
+ replace_rtx (src, from, to);
+
+ /* Try to simplify resulting note. */
+ simplified = simplify_rtx (src);
+ if (simplified)
+ {
+ src = simplified;
+ XEXP (note, 0) = src;
+ }
+
+ /* REG_EQUAL may get simplified into register.
+ We don't allow that. Remove that note. This code ought
+ not to hapen, because previous code ought to syntetize
+ reg-reg move, but be on the safe side. */
+ else if (REG_P (src))
+ remove_note (insn, note);
+ }
+ return success;
}
-/* Find a set of REGNO that is available on entry to INSN's block.
- Returns NULL if not found. */
+/* Find a set of REGNOs that are available on entry to INSN's block. Returns
+ NULL no such set is found. */
static struct expr *
find_avail_set (regno, insn)
int regno;
rtx insn;
{
- struct expr *set = lookup_set (regno, NULL_RTX);
+ /* SET1 contains the last set found that can be returned to the caller for
+ use in a substitution. */
+ struct expr *set1 = 0;
+
+ /* Loops are not possible here. To get a loop we would need two sets
+ available at the start of the block containing INSN. ie we would
+ need two sets like this available at the start of the block:
+
+ (set (reg X) (reg Y))
+ (set (reg Y) (reg X))
+
+ This can not happen since the set of (reg Y) would have killed the
+ set of (reg X) making it unavailable at the start of this block. */
+ while (1)
+ {
+ rtx src;
+ struct expr *set = lookup_set (regno, NULL_RTX);
+
+ /* Find a set that is available at the start of the block
+ which contains INSN. */
+ while (set)
+ {
+ if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
+ break;
+ set = next_set (regno, set);
+ }
- while (set)
- {
- if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
+ /* If no available set was found we've reached the end of the
+ (possibly empty) copy chain. */
+ if (set == 0)
+ break;
+
+ if (GET_CODE (set->expr) != SET)
+ abort ();
+
+ src = SET_SRC (set->expr);
+
+ /* We know the set is available.
+ Now check that SRC is ANTLOC (i.e. none of the source operands
+ have changed since the start of the block).
+
+ If the source operand changed, we may still use it for the next
+ iteration of this loop, but we may not use it for substitutions. */
+
+ if (CONSTANT_P (src) || oprs_not_set_p (src, insn))
+ set1 = set;
+
+ /* If the source of the set is anything except a register, then
+ we have reached the end of the copy chain. */
+ if (GET_CODE (src) != REG)
break;
- set = next_set (regno, set);
- }
- return set;
+ /* Follow the copy chain, ie start another iteration of the loop
+ and see if we have an available copy into SRC. */
+ regno = REGNO (src);
+ }
+
+ /* SET1 holds the last set that was available and anticipatable at
+ INSN. */
+ return set1;
+}
+
+/* Subroutine of cprop_insn that tries to propagate constants into
+ JUMP_INSNS. INSN must be a conditional jump; COPY is a copy of it
+ that we can use for substitutions.
+ REG_USED is the use we will try to replace, SRC is the constant we
+ will try to substitute for it.
+ Returns nonzero if a change was made. */
+
+static int
+cprop_jump (insn, copy, reg_used, src)
+ rtx insn, copy;
+ struct reg_use *reg_used;
+ rtx src;
+{
+ rtx set = PATTERN (copy);
+ rtx temp;
+
+ /* Replace the register with the appropriate constant. */
+ replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
+
+ temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
+ GET_MODE (SET_SRC (set)),
+ GET_MODE (XEXP (SET_SRC (set), 0)),
+ XEXP (SET_SRC (set), 0),
+ XEXP (SET_SRC (set), 1),
+ XEXP (SET_SRC (set), 2));
+
+ /* If no simplification can be made, then try the next
+ register. */
+ if (temp == 0)
+ return 0;
+
+ SET_SRC (set) = temp;
+
+ /* That may have changed the structure of TEMP, so
+ force it to be rerecognized if it has not turned
+ into a nop or unconditional jump. */
+
+ INSN_CODE (copy) = -1;
+ if ((SET_DEST (set) == pc_rtx
+ && (SET_SRC (set) == pc_rtx
+ || GET_CODE (SET_SRC (set)) == LABEL_REF))
+ || recog (PATTERN (copy), copy, NULL) >= 0)
+ {
+ /* This has either become an unconditional jump
+ or a nop-jump. We'd like to delete nop jumps
+ here, but doing so confuses gcse. So we just
+ make the replacement and let later passes
+ sort things out. */
+ PATTERN (insn) = set;
+ INSN_CODE (insn) = -1;
+
+ /* One less use of the label this insn used to jump to
+ if we turned this into a NOP jump. */
+ if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
+ --LABEL_NUSES (JUMP_LABEL (insn));
+
+ /* If this has turned into an unconditional jump,
+ then put a barrier after it so that the unreachable
+ code will be deleted. */
+ if (GET_CODE (SET_SRC (set)) == LABEL_REF)
+ emit_barrier_after (insn);
+
+ run_jump_opt_after_gcse = 1;
+
+ const_prop_count++;
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file,
+ "CONST-PROP: Replacing reg %d in insn %d with constant ",
+ REGNO (reg_used->reg_rtx), INSN_UID (insn));
+ print_rtl (gcse_file, src);
+ fprintf (gcse_file, "\n");
+ }
+
+ return 1;
+ }
+ return 0;
}
+#ifdef HAVE_cc0
+
+/* Subroutine of cprop_insn that tries to propagate constants into JUMP_INSNS
+ for machines that have CC0. INSN is a single set that stores into CC0;
+ the insn following it is a conditional jump. REG_USED is the use we will
+ try to replace, SRC is the constant we will try to substitute for it.
+ Returns nonzero if a change was made. */
+
+static int
+cprop_cc0_jump (insn, reg_used, src)
+ rtx insn;
+ struct reg_use *reg_used;
+ rtx src;
+{
+ rtx jump = NEXT_INSN (insn);
+ rtx copy = copy_rtx (jump);
+ rtx set = PATTERN (copy);
+
+ /* We need to copy the source of the cc0 setter, as cprop_jump is going to
+ substitute into it. */
+ replace_rtx (SET_SRC (set), cc0_rtx, copy_rtx (SET_SRC (PATTERN (insn))));
+ if (! cprop_jump (jump, copy, reg_used, src))
+ return 0;
+
+ /* If we succeeded, delete the cc0 setter. */
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (insn) = 0;
+ return 1;
+ }
+#endif
+
/* Perform constant and copy propagation on INSN.
The result is non-zero if a change was made. */
static int
-cprop_insn (insn)
+cprop_insn (insn, alter_jumps)
rtx insn;
+ int alter_jumps;
{
struct reg_use *reg_used;
int changed = 0;
+ rtx note;
- /* ??? For now only propagate into SETs. */
- if (GET_CODE (insn) != INSN
+ /* Only propagate into SETs. Note that a conditional jump is a
+ SET with pc_rtx as the destination. */
+ if ((GET_CODE (insn) != INSN
+ && GET_CODE (insn) != JUMP_INSN)
|| GET_CODE (PATTERN (insn)) != SET)
return 0;
reg_use_count = 0;
find_used_regs (PATTERN (insn));
+
+ note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
+ if (!note)
+ note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
- reg_used = ®_use_table[0];
- for ( ; reg_use_count > 0; reg_used++, reg_use_count--)
+ /* We may win even when propagating constants into notes. */
+ if (note)
+ find_used_regs (XEXP (note, 0));
+
+ for (reg_used = ®_use_table[0]; reg_use_count > 0;
+ reg_used++, reg_use_count--)
{
+ unsigned int regno = REGNO (reg_used->reg_rtx);
rtx pat, src;
struct expr *set;
- int regno = REGNO (reg_used->reg_rtx);
/* Ignore registers created by GCSE.
We do this because ... */
/* ??? We might be able to handle PARALLELs. Later. */
if (GET_CODE (pat) != SET)
abort ();
+
src = SET_SRC (pat);
- if (GET_CODE (src) == CONST_INT)
+ /* Constant propagation. */
+ if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE
+ || GET_CODE (src) == SYMBOL_REF)
{
- if (try_replace_reg (reg_used->reg_rtx, src, insn))
+ /* Handle normal insns first. */
+ if (GET_CODE (insn) == INSN
+ && try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
- fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
- regno, INSN_UID (insn));
- fprintf (gcse_file, HOST_WIDE_INT_PRINT_DEC, INTVAL (src));
+ fprintf (gcse_file, "CONST-PROP: Replacing reg %d in ",
+ regno);
+ fprintf (gcse_file, "insn %d with constant ",
+ INSN_UID (insn));
+ print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
/* The original insn setting reg_used may or may not now be
deletable. We leave the deletion to flow. */
}
+
+ /* Try to propagate a CONST_INT into a conditional jump.
+ We're pretty specific about what we will handle in this
+ code, we can extend this as necessary over time.
+
+ Right now the insn in question must look like
+ (set (pc) (if_then_else ...)) */
+ else if (alter_jumps
+ && GET_CODE (insn) == JUMP_INSN
+ && condjump_p (insn)
+ && ! simplejump_p (insn))
+ changed |= cprop_jump (insn, copy_rtx (insn), reg_used, src);
+#ifdef HAVE_cc0
+ /* Similar code for machines that use a pair of CC0 setter and
+ conditional jump insn. */
+ else if (alter_jumps
+ && GET_CODE (PATTERN (insn)) == SET
+ && SET_DEST (PATTERN (insn)) == cc0_rtx
+ && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && condjump_p (NEXT_INSN (insn))
+ && ! simplejump_p (NEXT_INSN (insn)))
+ changed |= cprop_cc0_jump (insn, reg_used, src);
+#endif
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& REGNO (src) != regno)
{
- /* We know the set is available.
- Now check that SET_SRC is ANTLOC (i.e. none of the source operands
- have changed since the start of the block). */
- if (oprs_not_set_p (src, insn))
+ if (try_replace_reg (reg_used->reg_rtx, src, insn))
{
- if (try_replace_reg (reg_used->reg_rtx, src, insn))
+ changed = 1;
+ copy_prop_count++;
+ if (gcse_file != NULL)
{
- changed = 1;
- copy_prop_count++;
- if (gcse_file != NULL)
- {
- fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n",
- regno, INSN_UID (insn), REGNO (src));
- }
-
- /* The original insn setting reg_used may or may not now be
- deletable. We leave the deletion to flow. */
- /* FIXME: If it turns out that the insn isn't deletable,
- then we may have unnecessarily extended register lifetimes
- and made things worse. */
+ fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d",
+ regno, INSN_UID (insn));
+ fprintf (gcse_file, " with reg %d\n", REGNO (src));
}
+
+ /* The original insn setting reg_used may or may not now be
+ deletable. We leave the deletion to flow. */
+ /* FIXME: If it turns out that the insn isn't deletable,
+ then we may have unnecessarily extended register lifetimes
+ and made things worse. */
}
}
}
return changed;
}
-/* Forward propagate copies.
- This includes copies and constants.
- Return non-zero if a change was made. */
+/* Forward propagate copies. This includes copies and constants. Return
+ non-zero if a change was made. */
static int
-cprop ()
+cprop (alter_jumps)
+ int alter_jumps;
{
int bb, changed;
rtx insn;
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
- changed |= cprop_insn (insn);
+ changed |= cprop_insn (insn, alter_jumps);
/* Keep track of everything modified by this insn. */
- /* ??? Need to be careful w.r.t. mods done to INSN. */
- mark_oprs_set (insn);
+ /* ??? Need to be careful w.r.t. mods done to INSN. Don't
+ call mark_oprs_set if we turned the insn into a NOTE. */
+ if (GET_CODE (insn) != NOTE)
+ mark_oprs_set (insn);
}
- }
+ }
}
if (gcse_file != NULL)
PASS is the pass count. */
static int
-one_cprop_pass (f, pass)
- rtx f;
+one_cprop_pass (pass, alter_jumps)
int pass;
+ int alter_jumps;
{
int changed = 0;
copy_prop_count = 0;
alloc_set_hash_table (max_cuid);
- compute_set_hash_table (f);
+ compute_set_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "SET", set_hash_table, set_hash_table_size,
n_sets);
{
alloc_cprop_mem (n_basic_blocks, n_sets);
compute_cprop_data ();
- changed = cprop ();
+ changed = cprop (alter_jumps);
free_cprop_mem ();
}
+
free_set_hash_table ();
if (gcse_file)
{
- fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, %d const props, %d copy props\n",
- current_function_name, pass,
- bytes_used, const_prop_count, copy_prop_count);
- fprintf (gcse_file, "\n");
+ fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, ",
+ current_function_name, pass, bytes_used);
+ fprintf (gcse_file, "%d const props, %d copy props\n\n",
+ const_prop_count, copy_prop_count);
}
return changed;
}
\f
-/* Compute PRE working variables. */
+/* Compute PRE+LCM working variables. */
/* Local properties of expressions. */
/* Nonzero for expressions that are transparent in the block. */
-static sbitmap *pre_transp;
-/* Nonzero for expressions that are computed (available) in the block. */
-static sbitmap *pre_comp;
-/* Nonzero for expressions that are locally anticipatable in the block. */
-static sbitmap *pre_antloc;
-
-/* Global properties (computed from the expression local properties). */
-/* Nonzero for expressions that are available on block entry/exit. */
-static sbitmap *pre_avin;
-static sbitmap *pre_avout;
-/* Nonzero for expressions that are anticipatable on block entry/exit. */
-static sbitmap *pre_antin;
-static sbitmap *pre_antout;
-/* Nonzero for expressions that are partially available on block entry/exit. */
-static sbitmap *pre_pavin;
-static sbitmap *pre_pavout;
-/* Nonzero for expressions that are "placement possible" on block entry/exit. */
-static sbitmap *pre_ppin;
-static sbitmap *pre_ppout;
+static sbitmap *transp;
/* Nonzero for expressions that are transparent at the end of the block.
This is only zero for expressions killed by abnormal critical edge
created by a calls. */
-static sbitmap *pre_transpout;
+static sbitmap *transpout;
+
+/* Nonzero for expressions that are computed (available) in the block. */
+static sbitmap *comp;
+
+/* Nonzero for expressions that are locally anticipatable in the block. */
+static sbitmap *antloc;
+
+/* Nonzero for expressions where this block is an optimal computation
+ point. */
+static sbitmap *pre_optimal;
+
+/* Nonzero for expressions which are redundant in a particular block. */
+static sbitmap *pre_redundant;
+
+/* Nonzero for expressions which should be inserted on a specific edge. */
+static sbitmap *pre_insert_map;
+
+/* Nonzero for expressions which should be deleted in a specific block. */
+static sbitmap *pre_delete_map;
+
+/* Contains the edge_list returned by pre_edge_lcm. */
+static struct edge_list *edge_list;
+
+static sbitmap *temp_bitmap;
-/* Used while performing PRE to denote which insns are redundant. */
-static sbitmap pre_redundant;
+/* Redundant insns. */
+static sbitmap pre_redundant_insns;
/* Allocate vars used for PRE analysis. */
alloc_pre_mem (n_blocks, n_exprs)
int n_blocks, n_exprs;
{
- pre_transp = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_comp = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- pre_avin = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_avout = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_antin = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_antout = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- pre_pavin = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_pavout = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_ppin = sbitmap_vector_alloc (n_blocks, n_exprs);
- pre_ppout = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- pre_transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
+ transp = sbitmap_vector_alloc (n_blocks, n_exprs);
+ comp = sbitmap_vector_alloc (n_blocks, n_exprs);
+ antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
+ temp_bitmap = sbitmap_vector_alloc (n_blocks, n_exprs);
+
+ pre_optimal = NULL;
+ pre_redundant = NULL;
+ pre_insert_map = NULL;
+ pre_delete_map = NULL;
+ ae_in = NULL;
+ ae_out = NULL;
+ u_bitmap = NULL;
+ transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
+ ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
+
+ /* pre_insert and pre_delete are allocated later. */
}
/* Free vars used for PRE analysis. */
static void
free_pre_mem ()
{
- free (pre_transp);
- free (pre_comp);
- free (pre_antloc);
- free (pre_avin);
- free (pre_avout);
- free (pre_antin);
- free (pre_antout);
-
- free (pre_pavin);
- free (pre_pavout);
- free (pre_ppin);
- free (pre_ppout);
- free (pre_transpout);
+ free (transp);
+ free (comp);
+ free (antloc);
+ free (temp_bitmap);
+
+ if (pre_optimal)
+ free (pre_optimal);
+ if (pre_redundant)
+ free (pre_redundant);
+ if (pre_insert_map)
+ free (pre_insert_map);
+ if (pre_delete_map)
+ free (pre_delete_map);
+ if (transpout)
+ free (transpout);
+
+ if (ae_in)
+ free (ae_in);
+ if (ae_out)
+ free (ae_out);
+ if (ae_kill)
+ free (ae_kill);
+ if (u_bitmap)
+ free (u_bitmap);
+
+ transp = comp = antloc = NULL;
+ pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
+ transpout = ae_in = ae_out = ae_kill = NULL;
+ u_bitmap = NULL;
+
}
-/* Dump PRE data. */
+/* Top level routine to do the dataflow analysis needed by PRE. */
-void
-dump_pre_data (file)
- FILE *file;
+static void
+compute_pre_data ()
{
- dump_sbitmap_vector (file, "PRE locally transparent expressions", "BB",
- pre_transp, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE locally available expressions", "BB",
- pre_comp, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE locally anticipatable expressions", "BB",
- pre_antloc, n_basic_blocks);
-
- dump_sbitmap_vector (file, "PRE available incoming expressions", "BB",
- pre_avin, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE available outgoing expressions", "BB",
- pre_avout, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE anticipatable incoming expressions", "BB",
- pre_antin, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE anticipatable outgoing expressions", "BB",
- pre_antout, n_basic_blocks);
-
- dump_sbitmap_vector (file, "PRE partially available incoming expressions", "BB",
- pre_pavin, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE partially available outgoing expressions", "BB",
- pre_pavout, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE placement possible on incoming", "BB",
- pre_ppin, n_basic_blocks);
- dump_sbitmap_vector (file, "PRE placement possible on outgoing", "BB",
- pre_ppout, n_basic_blocks);
-
- dump_sbitmap_vector (file, "PRE transparent on outgoing", "BB",
- pre_transpout, n_basic_blocks);
-}
+ int i;
-/* Compute the local properties of each recorded expression.
- Local properties are those that are defined by the block, irrespective
- of other blocks.
+ compute_local_properties (transp, comp, antloc, 0);
+ compute_transpout ();
+ sbitmap_vector_zero (ae_kill, n_basic_blocks);
- An expression is transparent in a block if its operands are not modified
- in the block.
+ /* Compute ae_kill for each basic block using:
- An expression is computed (locally available) in a block if it is computed
- at least once and expression would contain the same value if the
- computation was moved to the end of the block.
-
- An expression is locally anticipatable in a block if it is computed at
- least once and expression would contain the same value if the computation
- was moved to the beginning of the block. */
-
-static void
-compute_pre_local_properties ()
-{
- int i;
-
- sbitmap_vector_ones (pre_transp, n_basic_blocks);
- sbitmap_vector_zero (pre_comp, n_basic_blocks);
- sbitmap_vector_zero (pre_antloc, n_basic_blocks);
-
- for (i = 0; i < expr_hash_table_size; i++)
- {
- struct expr *expr;
-
- for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
- {
- struct occr *occr;
- int indx = expr->bitmap_index;
-
- /* The expression is transparent in this block if it is not killed.
- We start by assuming all are transparent [none are killed], and then
- reset the bits for those that are. */
-
- compute_transp (expr->expr, indx, pre_transp, 0);
-
- /* The occurrences recorded in antic_occr are exactly those that
- we want to set to non-zero in ANTLOC. */
-
- for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
- {
- int bb = BLOCK_NUM (occr->insn);
- SET_BIT (pre_antloc[bb], indx);
-
- /* While we're scanning the table, this is a good place to
- initialize this. */
- occr->deleted_p = 0;
- }
-
- /* The occurrences recorded in avail_occr are exactly those that
- we want to set to non-zero in COMP. */
-
- for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
- {
- int bb = BLOCK_NUM (occr->insn);
- SET_BIT (pre_comp[bb], indx);
-
- /* While we're scanning the table, this is a good place to
- initialize this. */
- occr->copied_p = 0;
- }
-
- /* While we're scanning the table, this is a good place to
- initialize this. */
- expr->reaching_reg = 0;
- }
- }
-}
-
-/* Compute expression availability at entrance and exit of each block. */
-
-static void
-compute_pre_avinout ()
-{
- int bb, changed, passes;
-
- sbitmap_zero (pre_avin[0]);
- sbitmap_vector_ones (pre_avout, n_basic_blocks);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- if (bb != 0)
- sbitmap_intersect_of_predecessors (pre_avin[bb], pre_avout,
- bb, s_preds);
- changed |= sbitmap_a_or_b_and_c (pre_avout[bb], pre_comp[bb],
- pre_transp[bb], pre_avin[bb]);
- }
- passes++;
- }
-
- if (gcse_file)
- fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
-}
-
-/* Compute expression anticipatability at entrance and exit of each block. */
-
-static void
-compute_pre_antinout ()
-{
- int bb, changed, passes;
-
- sbitmap_zero (pre_antout[n_basic_blocks - 1]);
- sbitmap_vector_ones (pre_antin, n_basic_blocks);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- /* We scan the blocks in the reverse order to speed up
- the convergence. */
- for (bb = n_basic_blocks - 1; bb >= 0; bb--)
- {
- if (bb != n_basic_blocks - 1)
- sbitmap_intersect_of_successors (pre_antout[bb], pre_antin,
- bb, s_succs);
- changed |= sbitmap_a_or_b_and_c (pre_antin[bb], pre_antloc[bb],
- pre_transp[bb], pre_antout[bb]);
- }
- passes++;
- }
-
- if (gcse_file)
- fprintf (gcse_file, "antic expr computation: %d passes\n", passes);
-}
-
-/* Compute expression partial availability at entrance and exit of
- each block. */
-
-static void
-compute_pre_pavinout ()
-{
- int bb, changed, passes;
-
- sbitmap_zero (pre_pavin[0]);
- sbitmap_vector_zero (pre_pavout, n_basic_blocks);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- if (bb != 0)
- sbitmap_union_of_predecessors (pre_pavin[bb], pre_pavout,
- bb, s_preds);
- changed |= sbitmap_a_or_b_and_c (pre_pavout[bb], pre_comp[bb],
- pre_transp[bb], pre_pavin[bb]);
- }
- passes++;
- }
-
- if (gcse_file)
- fprintf (gcse_file, "partially avail expr computation: %d passes\n", passes);
-}
-
-/* Compute transparent outgoing information for each block.
-
- An expression is transparent to an edge unless it is killed by
- the edge itself. This can only happen with abnormal control flow,
- when the edge is traversed through a call. This happens with
- non-local labels and exceptions.
-
- This would not be necessary if we split the edge. While this is
- normally impossible for abnormal critical edges, with some effort
- it should be possible with exception handling, since we still have
- control over which handler should be invoked. But due to increased
- EH table sizes, this may not be worthwhile. */
-
-static void
-compute_pre_transpout ()
-{
- int bb;
-
- sbitmap_vector_ones (pre_transpout, n_basic_blocks);
-
- for (bb = 0; bb < n_basic_blocks; ++bb)
- {
- int i;
-
- /* Note that flow inserted a nop a the end of basic blocks that
- end in call instructions for reasons other than abnormal
- control flow. */
- if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
- continue;
-
- for (i = 0; i < expr_hash_table_size; i++)
- {
- struct expr *expr;
- for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
- if (GET_CODE (expr->expr) == MEM)
- {
- rtx addr = XEXP (expr->expr, 0);
-
- if (GET_CODE (addr) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (addr))
- continue;
-
- /* ??? Optimally, we would use interprocedural alias
- analysis to determine if this mem is actually killed
- by this call. */
- RESET_BIT (pre_transpout[bb], expr->bitmap_index);
- }
- }
- }
-}
-
-/* Compute "placement possible" information on entrance and exit of
- each block.
-
- From Fred Chow's Thesis:
- A computation `e' is PP at a point `p' if it is anticipated at `p' and
- all the anticipated e's can be rendered redundant by zero or more
- insertions at that point and some other points in the procedure, and
- these insertions satisfy the conditions that the insertions are always
- at points that `e' is anticipated and the first anticipated e's after the
- insertions are rendered redundant. */
+ ~(TRANSP | COMP)
-static void
-compute_pre_ppinout ()
-{
- int bb, i, changed, size, passes;
-
- sbitmap_vector_ones (pre_ppin, n_basic_blocks);
- /* ??? Inefficient as we set pre_ppin[0] twice, but simple. */
- sbitmap_zero (pre_ppin[0]);
-
- sbitmap_vector_ones (pre_ppout, n_basic_blocks);
- /* ??? Inefficient as we set pre_ppout[n_basic_blocks-1] twice, but simple. */
- sbitmap_zero (pre_ppout[n_basic_blocks - 1]);
+ This is significantly faster than compute_ae_kill. */
- size = pre_ppin[0]->size;
- passes = 0;
- changed = 1;
- while (changed)
+ for (i = 0; i < n_basic_blocks; i++)
{
- changed = 0;
- for (bb = 1; bb < n_basic_blocks; bb++)
- {
- sbitmap_ptr antin = pre_antin[bb]->elms;
- sbitmap_ptr pavin = pre_pavin[bb]->elms;
- sbitmap_ptr antloc = pre_antloc[bb]->elms;
- sbitmap_ptr transp = pre_transp[bb]->elms;
- sbitmap_ptr ppout = pre_ppout[bb]->elms;
- sbitmap_ptr ppin = pre_ppin[bb]->elms;
-
- for (i = 0; i < size; i++)
- {
- int_list_ptr pred;
- SBITMAP_ELT_TYPE tmp = *antin & *pavin & (*antloc | (*transp & *ppout));
- SBITMAP_ELT_TYPE pred_val = (SBITMAP_ELT_TYPE) -1;
-
- for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
- {
- int pred_bb = INT_LIST_VAL (pred);
- sbitmap_ptr ppout_j,avout_j;
-
- if (pred_bb == ENTRY_BLOCK)
- continue;
-
- /* If this is a back edge, propagate info along the back
- edge to allow for loop invariant code motion.
-
- See FOLLOW_BACK_EDGES at the top of this file for a longer
- discussion about loop invariant code motion in pre. */
- if (! FOLLOW_BACK_EDGES
- && (INSN_CUID (BLOCK_HEAD (bb))
- < INSN_CUID (BLOCK_END (pred_bb))))
- {
- pred_val = 0;
- }
- else
- {
- ppout_j = pre_ppout[pred_bb]->elms + i;
- avout_j = pre_avout[pred_bb]->elms + i;
- pred_val &= *ppout_j | *avout_j;
- }
- }
- tmp &= pred_val;
- *ppin = tmp;
- antin++; pavin++; antloc++; transp++; ppout++; ppin++;
- }
- }
-
- for (bb = 0; bb < n_basic_blocks - 1; bb++)
- {
- sbitmap_ptr ppout = pre_ppout[bb]->elms;
- sbitmap_ptr transpout = pre_transpout[bb]->elms;
-
- for (i = 0; i < size; i++)
- {
- int_list_ptr succ;
- SBITMAP_ELT_TYPE tmp = *transpout;
-
- for (succ = s_succs[bb]; succ != NULL; succ = succ->next)
- {
- int succ_bb = INT_LIST_VAL (succ);
- sbitmap_ptr ppin;
-
- if (succ_bb == EXIT_BLOCK)
- continue;
-
- ppin = pre_ppin[succ_bb]->elms + i;
- tmp &= *ppin;
- }
-
- if (*ppout != tmp)
- {
- changed = 1;
- *ppout = tmp;
- }
-
- ppout++; transpout++;
- }
- }
-
- passes++;
+ sbitmap_a_or_b (ae_kill[i], transp[i], comp[i]);
+ sbitmap_not (ae_kill[i], ae_kill[i]);
}
- if (gcse_file)
- fprintf (gcse_file, "placement possible computation: %d passes\n", passes);
-}
-
-/* Top level routine to do the dataflow analysis needed by PRE. */
-
-static void
-compute_pre_data ()
-{
- compute_pre_local_properties ();
- compute_pre_avinout ();
- compute_pre_antinout ();
- compute_pre_pavinout ();
- compute_pre_transpout ();
- compute_pre_ppinout ();
- if (gcse_file)
- fprintf (gcse_file, "\n");
+ edge_list = pre_edge_lcm (gcse_file, n_exprs, transp, comp, antloc,
+ ae_kill, &pre_insert_map, &pre_delete_map);
}
\f
/* PRE utilities */
-/* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
+/* Return non-zero if an occurrence of expression EXPR in OCCR_BB would reach
+ block BB.
VISITED is a pointer to a working buffer for tracking which BB's have
been visited. It is NULL for the top-level call.
the closest such expression. */
static int
-pre_expr_reaches_here_p (occr, expr, bb, visited)
- struct occr *occr;
+pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited)
+ int occr_bb;
struct expr *expr;
int bb;
char *visited;
{
- int_list_ptr pred;
-
- if (visited == NULL)
- {
- visited = (char *) alloca (n_basic_blocks);
- bzero (visited, n_basic_blocks);
- }
+ edge pred;
- for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
+ for (pred = BASIC_BLOCK (bb)->pred; pred != NULL; pred = pred->pred_next)
{
- int pred_bb = INT_LIST_VAL (pred);
+ int pred_bb = pred->src->index;
- if (pred_bb == ENTRY_BLOCK
+ if (pred->src == ENTRY_BLOCK_PTR
/* Has predecessor has already been visited? */
|| visited[pred_bb])
- {
- /* Nothing to do. */
- }
+ ;/* Nothing to do. */
+
/* Does this predecessor generate this expression? */
- else if (TEST_BIT (pre_comp[pred_bb], expr->bitmap_index))
+ else if (TEST_BIT (comp[pred_bb], expr->bitmap_index))
{
/* Is this the occurrence we're looking for?
Note that there's only one generating occurrence per block
so we just need to check the block number. */
- if (BLOCK_NUM (occr->insn) == pred_bb)
+ if (occr_bb == pred_bb)
return 1;
+
visited[pred_bb] = 1;
}
/* Ignore this predecessor if it kills the expression. */
- else if (! TEST_BIT (pre_transp[pred_bb], expr->bitmap_index))
+ else if (! TEST_BIT (transp[pred_bb], expr->bitmap_index))
visited[pred_bb] = 1;
+
/* Neither gen nor kill. */
else
- {
+ {
visited[pred_bb] = 1;
- if (pre_expr_reaches_here_p (occr, expr, pred_bb, visited))
+ if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
return 1;
- }
+ }
}
/* All paths have been checked. */
return 0;
}
+
+/* The wrapper for pre_expr_reaches_here_work that ensures that any
+ memory allocated for that function is returned. */
+
+static int
+pre_expr_reaches_here_p (occr_bb, expr, bb)
+ int occr_bb;
+ struct expr *expr;
+ int bb;
+{
+ int rval;
+ char *visited = (char *) xcalloc (n_basic_blocks, 1);
+
+ rval = pre_expr_reaches_here_p_work(occr_bb, expr, bb, visited);
+
+ free (visited);
+ return rval;
+}
\f
-/* Add EXPR to the end of basic block BB. */
+
+/* Given an expr, generate RTL which we can insert at the end of a BB,
+ or on an edge. Set the block number of any insns generated to
+ the value of BB. */
+
+static rtx
+process_insert_insn (expr)
+ struct expr *expr;
+{
+ rtx reg = expr->reaching_reg;
+ rtx pat, copied_expr;
+ rtx first_new_insn;
+
+ start_sequence ();
+ copied_expr = copy_rtx (expr->expr);
+ emit_move_insn (reg, copied_expr);
+ first_new_insn = get_insns ();
+ pat = gen_sequence ();
+ end_sequence ();
+
+ return pat;
+}
+
+/* Add EXPR to the end of basic block BB.
+
+ This is used by both the PRE and code hoisting.
+
+ For PRE, we want to verify that the expr is either transparent
+ or locally anticipatable in the target block. This check makes
+ no sense for code hoisting. */
static void
-pre_insert_insn (expr, bb)
+insert_insn_end_bb (expr, bb, pre)
struct expr *expr;
int bb;
+ int pre;
{
rtx insn = BLOCK_END (bb);
rtx new_insn;
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
rtx pat;
+ int i;
- pat = gen_rtx_SET (VOIDmode, reg, copy_rtx (expr->expr));
+ pat = process_insert_insn (expr);
/* If the last insn is a jump, insert EXPR in front [taking care to
handle cc0, etc. properly]. */
}
#endif
/* FIXME: What if something in cc0/jump uses value set in new insn? */
- new_insn = emit_insn_before (pat, insn);
- add_label_notes (SET_SRC (pat), new_insn);
- if (BLOCK_HEAD (bb) == insn)
- BLOCK_HEAD (bb) = new_insn;
+ new_insn = emit_block_insn_before (pat, insn, BASIC_BLOCK (bb));
}
+
/* Likewise if the last insn is a call, as will happen in the presence
of exception handling. */
else if (GET_CODE (insn) == CALL_INSN)
/* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
we search backward and place the instructions before the first
parameter is loaded. Do this for everyone for consistency and a
- presumtion that we'll get better code elsewhere as well. */
-
- /* It should always be the case that we can put these instructions
- anywhere in the basic block. Check this. */
- /* ??? Well, it would be the case if we'd split all critical edges.
- Since we didn't, we may very well abort. */
- if (!TEST_BIT (pre_antloc[bb], expr->bitmap_index)
- && !TEST_BIT (pre_transp[bb], expr->bitmap_index))
+ presumtion that we'll get better code elsewhere as well.
+
+ It should always be the case that we can put these instructions
+ anywhere in the basic block with performing PRE optimizations.
+ Check this. */
+
+ if (pre
+ && !TEST_BIT (antloc[bb], expr->bitmap_index)
+ && !TEST_BIT (transp[bb], expr->bitmap_index))
abort ();
/* Since different machines initialize their parameter registers
if (GET_CODE (XEXP (p, 0)) == USE
&& GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
{
- int regno = REGNO (XEXP (XEXP (p, 0), 0));
- if (regno >= FIRST_PSEUDO_REGISTER)
+ if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER)
abort ();
- SET_HARD_REG_BIT (parm_regs, regno);
+
+ SET_HARD_REG_BIT (parm_regs, REGNO (XEXP (XEXP (p, 0), 0)));
nparm_regs++;
}
}
}
- new_insn = emit_insn_before (pat, insn);
- if (BLOCK_HEAD (bb) == insn)
- BLOCK_HEAD (bb) = new_insn;
+ /* If we found all the parameter loads, then we want to insert
+ before the first parameter load.
+
+ If we did not find all the parameter loads, then we might have
+ stopped on the head of the block, which could be a CODE_LABEL.
+ If we inserted before the CODE_LABEL, then we would be putting
+ the insn in the wrong basic block. In that case, put the insn
+ after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
+ while (GET_CODE (insn) == CODE_LABEL
+ || (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
+ insn = NEXT_INSN (insn);
+
+ new_insn = emit_block_insn_before (pat, insn, BASIC_BLOCK (bb));
}
else
{
new_insn = emit_insn_after (pat, insn);
- add_label_notes (SET_SRC (pat), new_insn);
BLOCK_END (bb) = new_insn;
}
- /* Keep block number table up to date. */
- set_block_num (new_insn, bb);
- /* Keep register set table up to date. */
- record_one_set (regno, new_insn);
-
- gcse_create_count++;
-
- if (gcse_file)
+ /* Keep block number table up to date.
+ Note, PAT could be a multiple insn sequence, we have to make
+ sure that each insn in the sequence is handled. */
+ if (GET_CODE (pat) == SEQUENCE)
{
- fprintf (gcse_file, "PRE: end of bb %d, insn %d, copying expression %d to reg %d\n",
- bb, INSN_UID (new_insn), expr->bitmap_index, regno);
- }
-}
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx insn = XVECEXP (pat, 0, i);
-/* Insert partially redundant expressions at the ends of appropriate basic
- blocks making them now redundant. */
+ set_block_num (insn, bb);
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ add_label_notes (PATTERN (insn), new_insn);
-static void
-pre_insert (index_map)
- struct expr **index_map;
+ note_stores (PATTERN (insn), record_set_info, insn);
+ }
+ }
+ else
+ {
+ add_label_notes (SET_SRC (pat), new_insn);
+ set_block_num (new_insn, bb);
+
+ /* Keep register set table up to date. */
+ record_one_set (regno, new_insn);
+ }
+
+ gcse_create_count++;
+
+ if (gcse_file)
+ {
+ fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, ",
+ bb, INSN_UID (new_insn));
+ fprintf (gcse_file, "copying expression %d to reg %d\n",
+ expr->bitmap_index, regno);
+ }
+}
+
+/* Insert partially redundant expressions on edges in the CFG to make
+ the expressions fully redundant. */
+
+static int
+pre_edge_insert (edge_list, index_map)
+ struct edge_list *edge_list;
+ struct expr **index_map;
{
- int bb, i, size;
+ int e, i, j, num_edges, set_size, did_insert = 0;
+ sbitmap *inserted;
- /* Compute INSERT = PPOUT & (~AVOUT) & (~PPIN | ~TRANSP) for each
- expression. Where INSERT == TRUE, add the expression at the end of
- the basic block. */
+ /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
+ if it reaches any of the deleted expressions. */
- size = pre_ppout[0]->size;
- for (bb = 0; bb < n_basic_blocks; bb++)
+ set_size = pre_insert_map[0]->size;
+ num_edges = NUM_EDGES (edge_list);
+ inserted = sbitmap_vector_alloc (num_edges, n_exprs);
+ sbitmap_vector_zero (inserted, num_edges);
+
+ for (e = 0; e < num_edges; e++)
{
int indx;
- sbitmap_ptr ppout = pre_ppout[bb]->elms;
- sbitmap_ptr avout = pre_avout[bb]->elms;
- sbitmap_ptr ppin = pre_ppin[bb]->elms;
- sbitmap_ptr transp = pre_transp[bb]->elms;
-
- for (i = indx = 0;
- i < size;
- i++, indx += SBITMAP_ELT_BITS, ppout++, avout++, ppin++, transp++)
+ basic_block pred = INDEX_EDGE_PRED_BB (edge_list, e);
+ int bb = pred->index;
+
+ for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
{
- int j;
- SBITMAP_ELT_TYPE insert = *ppout & (~*avout) & (~*ppin | ~*transp);
+ SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
- for (j = indx; insert != 0 && j < n_exprs; j++, insert >>= 1)
- {
- if ((insert & 1) != 0
- /* If the basic block isn't reachable, PPOUT will be TRUE.
- However, we don't want to insert a copy here because the
- expression may not really be redundant. So only insert
- an insn if the expression was deleted. */
- && index_map[j]->reaching_reg != NULL)
- pre_insert_insn (index_map[j], bb);
- }
+ for (j = indx; insert && j < n_exprs; j++, insert >>= 1)
+ if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
+ {
+ struct expr *expr = index_map[j];
+ struct occr *occr;
+
+ /* Now look at each deleted occurence of this expression. */
+ for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
+ {
+ if (! occr->deleted_p)
+ continue;
+
+ /* Insert this expression on this edge if if it would
+ reach the deleted occurence in BB. */
+ if (!TEST_BIT (inserted[e], j))
+ {
+ rtx insn;
+ edge eg = INDEX_EDGE (edge_list, e);
+
+ /* We can't insert anything on an abnormal and
+ critical edge, so we insert the insn at the end of
+ the previous block. There are several alternatives
+ detailed in Morgans book P277 (sec 10.5) for
+ handling this situation. This one is easiest for
+ now. */
+
+ if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
+ insert_insn_end_bb (index_map[j], bb, 0);
+ else
+ {
+ insn = process_insert_insn (index_map[j]);
+ insert_insn_on_edge (insn, eg);
+ }
+
+ if (gcse_file)
+ {
+ fprintf (gcse_file, "PRE/HOIST: edge (%d,%d), ",
+ bb,
+ INDEX_EDGE_SUCC_BB (edge_list, e)->index);
+ fprintf (gcse_file, "copy expression %d\n",
+ expr->bitmap_index);
+ }
+
+ SET_BIT (inserted[e], j);
+ did_insert = 1;
+ gcse_create_count++;
+ }
+ }
+ }
}
}
+
+ free (inserted);
+ return did_insert;
}
-/* Copy the result of INSN to REG.
- INDX is the expression number. */
+/* Copy the result of INSN to REG. INDX is the expression number. */
static void
pre_insert_copy_insn (expr, insn)
int indx = expr->bitmap_index;
rtx set = single_set (insn);
rtx new_insn;
+ int bb = BLOCK_NUM (insn);
if (!set)
abort ();
+
new_insn = emit_insn_after (gen_rtx_SET (VOIDmode, reg, SET_DEST (set)),
insn);
+
/* Keep block number table up to date. */
- set_block_num (new_insn, BLOCK_NUM (insn));
+ set_block_num (new_insn, bb);
+
/* Keep register set table up to date. */
record_one_set (regno, new_insn);
+ if (insn == BLOCK_END (bb))
+ BLOCK_END (bb) = new_insn;
gcse_create_count++;
if (gcse_file)
- {
- fprintf (gcse_file, "PRE: bb %d, insn %d, copying expression %d in insn %d to reg %d\n",
- BLOCK_NUM (insn), INSN_UID (new_insn), indx, INSN_UID (insn), regno);
- }
+ fprintf (gcse_file,
+ "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
+ BLOCK_NUM (insn), INSN_UID (new_insn), indx,
+ INSN_UID (insn), regno);
}
/* Copy available expressions that reach the redundant expression
static void
pre_insert_copies ()
{
- int i;
+ unsigned int i;
+ struct expr *expr;
+ struct occr *occr;
+ struct occr *avail;
/* For each available expression in the table, copy the result to
`reaching_reg' if the expression reaches a deleted one.
Need to do some profiling. */
for (i = 0; i < expr_hash_table_size; i++)
- {
- struct expr *expr;
-
- for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
- {
- struct occr *occr;
-
- /* If the basic block isn't reachable, PPOUT will be TRUE.
- However, we don't want to insert a copy here because the
- expression may not really be redundant. So only insert
- an insn if the expression was deleted.
- This test also avoids further processing if the expression
- wasn't deleted anywhere. */
- if (expr->reaching_reg == NULL)
- continue;
+ for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
+ {
+ /* If the basic block isn't reachable, PPOUT will be TRUE. However,
+ we don't want to insert a copy here because the expression may not
+ really be redundant. So only insert an insn if the expression was
+ deleted. This test also avoids further processing if the
+ expression wasn't deleted anywhere. */
+ if (expr->reaching_reg == NULL)
+ continue;
+
+ for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
+ {
+ if (! occr->deleted_p)
+ continue;
- for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
- {
- struct occr *avail;
+ for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
+ {
+ rtx insn = avail->insn;
- if (! occr->deleted_p)
- continue;
+ /* No need to handle this one if handled already. */
+ if (avail->copied_p)
+ continue;
- for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
- {
- rtx insn = avail->insn;
+ /* Don't handle this one if it's a redundant one. */
+ if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
+ continue;
- /* No need to handle this one if handled already. */
- if (avail->copied_p)
- continue;
- /* Don't handle this one if it's a redundant one. */
- if (TEST_BIT (pre_redundant, INSN_CUID (insn)))
- continue;
- /* Or if the expression doesn't reach the deleted one. */
- if (! pre_expr_reaches_here_p (avail, expr,
- BLOCK_NUM (occr->insn),
- NULL))
- continue;
+ /* Or if the expression doesn't reach the deleted one. */
+ if (! pre_expr_reaches_here_p (BLOCK_NUM (avail->insn), expr,
+ BLOCK_NUM (occr->insn)))
+ continue;
- /* Copy the result of avail to reaching_reg. */
- pre_insert_copy_insn (expr, insn);
- avail->copied_p = 1;
- }
- }
- }
- }
+ /* Copy the result of avail to reaching_reg. */
+ pre_insert_copy_insn (expr, insn);
+ avail->copied_p = 1;
+ }
+ }
+ }
}
/* Delete redundant computations.
- These are ones that satisy ANTLOC & PPIN.
Deletion is done by changing the insn to copy the `reaching_reg' of
the expression into the result of the SET. It is left to later passes
(cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
static int
pre_delete ()
{
- int i, changed;
+ unsigned int i;
+ int bb, changed;
+ struct expr *expr;
+ struct occr *occr;
+
+ /* Compute the expressions which are redundant and need to be replaced by
+ copies from the reaching reg to the target reg. */
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ sbitmap_copy (temp_bitmap[bb], pre_delete_map[bb]);
changed = 0;
for (i = 0; i < expr_hash_table_size; i++)
- {
- struct expr *expr;
-
- for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
- {
- struct occr *occr;
- int indx = expr->bitmap_index;
+ for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
+ {
+ int indx = expr->bitmap_index;
- /* We only need to search antic_occr since we require
- ANTLOC != 0. */
+ /* We only need to search antic_occr since we require
+ ANTLOC != 0. */
- for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
- {
- rtx insn = occr->insn;
- rtx set;
- int bb = BLOCK_NUM (insn);
- sbitmap ppin = pre_ppin[bb];
+ for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
+ {
+ rtx insn = occr->insn;
+ rtx set;
+ int bb = BLOCK_NUM (insn);
- if (TEST_BIT (ppin, indx))
- {
- set = single_set (insn);
- if (! set)
- abort ();
-
- /* Create a pseudo-reg to store the result of reaching
- expressions into. Get the mode for the new pseudo
- from the mode of the original destination pseudo. */
- if (expr->reaching_reg == NULL)
- expr->reaching_reg
- = gen_reg_rtx (GET_MODE (SET_DEST (set)));
-
- /* In theory this should never fail since we're creating
- a reg->reg copy.
-
- However, on the x86 some of the movXX patterns actually
- contain clobbers of scratch regs. This may cause the
- insn created by validate_change to not patch any pattern
- and thus cause validate_change to fail. */
- if (validate_change (insn, &SET_SRC (set),
- expr->reaching_reg, 0))
- {
- occr->deleted_p = 1;
- SET_BIT (pre_redundant, INSN_CUID (insn));
- changed = 1;
- gcse_subst_count++;
- }
+ if (TEST_BIT (temp_bitmap[bb], indx))
+ {
+ set = single_set (insn);
+ if (! set)
+ abort ();
+
+ /* Create a pseudo-reg to store the result of reaching
+ expressions into. Get the mode for the new pseudo from
+ the mode of the original destination pseudo. */
+ if (expr->reaching_reg == NULL)
+ expr->reaching_reg
+ = gen_reg_rtx (GET_MODE (SET_DEST (set)));
+
+ /* In theory this should never fail since we're creating
+ a reg->reg copy.
+
+ However, on the x86 some of the movXX patterns actually
+ contain clobbers of scratch regs. This may cause the
+ insn created by validate_change to not match any pattern
+ and thus cause validate_change to fail. */
+ if (validate_change (insn, &SET_SRC (set),
+ expr->reaching_reg, 0))
+ {
+ occr->deleted_p = 1;
+ SET_BIT (pre_redundant_insns, INSN_CUID (insn));
+ changed = 1;
+ gcse_subst_count++;
+ }
- if (gcse_file)
- {
- fprintf (gcse_file, "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n",
- INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg));
- }
- }
- }
- }
- }
+ if (gcse_file)
+ {
+ fprintf (gcse_file,
+ "PRE: redundant insn %d (expression %d) in ",
+ INSN_UID (insn), indx);
+ fprintf (gcse_file, "bb %d, reaching reg is %d\n",
+ bb, REGNO (expr->reaching_reg));
+ }
+ }
+ }
+ }
return changed;
}
This is called by one_pre_gcse_pass after all the dataflow analysis
has been done.
- This is based on the original Morel-Renvoise paper and Fred Chow's thesis.
+ This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
+ lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
+ Compiler Design and Implementation.
- The M-R paper uses "TRANSP" to describe an expression as being transparent
- in a block where as Chow's thesis uses "ALTERED". We use TRANSP.
+ ??? A new pseudo reg is created to hold the reaching expression. The nice
+ thing about the classical approach is that it would try to use an existing
+ reg. If the register can't be adequately optimized [i.e. we introduce
+ reload problems], one could add a pass here to propagate the new register
+ through the block.
- ??? A new pseudo reg is created to hold the reaching expression.
- The nice thing about the classical approach is that it would try to
- use an existing reg. If the register can't be adequately optimized
- [i.e. we introduce reload problems], one could add a pass here to
- propagate the new register through the block.
-
- ??? We don't handle single sets in PARALLELs because we're [currently]
- not able to copy the rest of the parallel when we insert copies to create
- full redundancies from partial redundancies. However, there's no reason
- why we can't handle PARALLELs in the cases where there are no partial
+ ??? We don't handle single sets in PARALLELs because we're [currently] not
+ able to copy the rest of the parallel when we insert copies to create full
+ redundancies from partial redundancies. However, there's no reason why we
+ can't handle PARALLELs in the cases where there are no partial
redundancies. */
static int
pre_gcse ()
{
- int i;
- int changed;
+ unsigned int i;
+ int did_insert, changed;
struct expr **index_map;
+ struct expr *expr;
/* Compute a mapping from expression number (`bitmap_index') to
hash table entry. */
- index_map = (struct expr **) alloca (n_exprs * sizeof (struct expr *));
- bzero ((char *) index_map, n_exprs * sizeof (struct expr *));
+ index_map = (struct expr **) xcalloc (n_exprs, sizeof (struct expr *));
for (i = 0; i < expr_hash_table_size; i++)
- {
- struct expr *expr;
-
- for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
- index_map[expr->bitmap_index] = expr;
- }
+ for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
+ index_map[expr->bitmap_index] = expr;
/* Reset bitmap used to track which insns are redundant. */
- pre_redundant = sbitmap_alloc (max_cuid);
- sbitmap_zero (pre_redundant);
+ pre_redundant_insns = sbitmap_alloc (max_cuid);
+ sbitmap_zero (pre_redundant_insns);
/* Delete the redundant insns first so that
- we know what register to use for the new insns and for the other
ones with reaching expressions
- we know which insns are redundant when we go to create copies */
+
changed = pre_delete ();
- /* Insert insns in places that make partially redundant expressions
- fully redundant. */
- pre_insert (index_map);
+ did_insert = pre_edge_insert (edge_list, index_map);
/* In other places with reaching expressions, copy the expression to the
- specially allocated pseudo-reg that reaches the redundant expression. */
+ specially allocated pseudo-reg that reaches the redundant expr. */
pre_insert_copies ();
+ if (did_insert)
+ {
+ commit_edge_insertions ();
+ changed = 1;
+ }
- free (pre_redundant);
-
+ free (index_map);
+ free (pre_redundant_insns);
return changed;
}
Return non-zero if a change was made. */
static int
-one_pre_gcse_pass (f, pass)
- rtx f;
+one_pre_gcse_pass (pass)
int pass;
{
int changed = 0;
gcse_create_count = 0;
alloc_expr_hash_table (max_cuid);
- compute_expr_hash_table (f);
+ add_noreturn_fake_exit_edges ();
+ compute_expr_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "Expression", expr_hash_table,
expr_hash_table_size, n_exprs);
+
if (n_exprs > 0)
{
alloc_pre_mem (n_basic_blocks, n_exprs);
compute_pre_data ();
changed |= pre_gcse ();
+ free_edge_list (edge_list);
free_pre_mem ();
}
+
+ remove_fake_edges ();
free_expr_hash_table ();
if (gcse_file)
{
- fprintf (gcse_file, "\n");
- fprintf (gcse_file, "PRE GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
- current_function_name, pass,
- bytes_used, gcse_subst_count, gcse_create_count);
+ fprintf (gcse_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
+ current_function_name, pass, bytes_used);
+ fprintf (gcse_file, "%d substs, %d insns created\n",
+ gcse_subst_count, gcse_create_count);
}
return changed;
{
enum rtx_code code = GET_CODE (x);
int i, j;
- char *fmt;
+ const char *fmt;
if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
{
/* This code used to ignore labels that referred to dispatch tables to
- avoid flow generating (slighly) worse code.
+ avoid flow generating (slighly) worse code.
+
+ We no longer ignore such label references (see LABEL_REF handling in
+ mark_jump_label for additional information). */
- We no longer ignore such label references (see LABEL_REF handling in
- mark_jump_label for additional information). */
REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
return;
}
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
add_label_notes (XEXP (x, i), insn);
add_label_notes (XVECEXP (x, i, j), insn);
}
}
+
+/* Compute transparent outgoing information for each block.
+
+ An expression is transparent to an edge unless it is killed by
+ the edge itself. This can only happen with abnormal control flow,
+ when the edge is traversed through a call. This happens with
+ non-local labels and exceptions.
+
+ This would not be necessary if we split the edge. While this is
+ normally impossible for abnormal critical edges, with some effort
+ it should be possible with exception handling, since we still have
+ control over which handler should be invoked. But due to increased
+ EH table sizes, this may not be worthwhile. */
+
+static void
+compute_transpout ()
+{
+ int bb;
+ unsigned int i;
+ struct expr *expr;
+
+ sbitmap_vector_ones (transpout, n_basic_blocks);
+
+ for (bb = 0; bb < n_basic_blocks; ++bb)
+ {
+ /* Note that flow inserted a nop a the end of basic blocks that
+ end in call instructions for reasons other than abnormal
+ control flow. */
+ if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
+ continue;
+
+ for (i = 0; i < expr_hash_table_size; i++)
+ for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
+ if (GET_CODE (expr->expr) == MEM)
+ {
+ if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
+ continue;
+
+ /* ??? Optimally, we would use interprocedural alias
+ analysis to determine if this mem is actually killed
+ by this call. */
+ RESET_BIT (transpout[bb], expr->bitmap_index);
+ }
+ }
+}
+
+/* Removal of useless null pointer checks */
+
+/* Called via note_stores. X is set by SETTER. If X is a register we must
+ invalidate nonnull_local and set nonnull_killed. DATA is really a
+ `null_pointer_info *'.
+
+ We ignore hard registers. */
+
+static void
+invalidate_nonnull_info (x, setter, data)
+ rtx x;
+ rtx setter ATTRIBUTE_UNUSED;
+ void *data;
+{
+ unsigned int regno;
+ struct null_pointer_info *npi = (struct null_pointer_info *) data;
+
+ while (GET_CODE (x) == SUBREG)
+ x = SUBREG_REG (x);
+
+ /* Ignore anything that is not a register or is a hard register. */
+ if (GET_CODE (x) != REG
+ || REGNO (x) < npi->min_reg
+ || REGNO (x) >= npi->max_reg)
+ return;
+
+ regno = REGNO (x) - npi->min_reg;
+
+ RESET_BIT (npi->nonnull_local[npi->current_block], regno);
+ SET_BIT (npi->nonnull_killed[npi->current_block], regno);
+}
+
+/* Do null-pointer check elimination for the registers indicated in
+ NPI. NONNULL_AVIN and NONNULL_AVOUT are pre-allocated sbitmaps;
+ they are not our responsibility to free. */
+
+static void
+delete_null_pointer_checks_1 (block_reg, nonnull_avin, nonnull_avout, npi)
+ unsigned int *block_reg;
+ sbitmap *nonnull_avin;
+ sbitmap *nonnull_avout;
+ struct null_pointer_info *npi;
+{
+ int bb;
+ int current_block;
+ sbitmap *nonnull_local = npi->nonnull_local;
+ sbitmap *nonnull_killed = npi->nonnull_killed;
+
+ /* Compute local properties, nonnull and killed. A register will have
+ the nonnull property if at the end of the current block its value is
+ known to be nonnull. The killed property indicates that somewhere in
+ the block any information we had about the register is killed.
+
+ Note that a register can have both properties in a single block. That
+ indicates that it's killed, then later in the block a new value is
+ computed. */
+ sbitmap_vector_zero (nonnull_local, n_basic_blocks);
+ sbitmap_vector_zero (nonnull_killed, n_basic_blocks);
+
+ for (current_block = 0; current_block < n_basic_blocks; current_block++)
+ {
+ rtx insn, stop_insn;
+
+ /* Set the current block for invalidate_nonnull_info. */
+ npi->current_block = current_block;
+
+ /* Scan each insn in the basic block looking for memory references and
+ register sets. */
+ stop_insn = NEXT_INSN (BLOCK_END (current_block));
+ for (insn = BLOCK_HEAD (current_block);
+ insn != stop_insn;
+ insn = NEXT_INSN (insn))
+ {
+ rtx set;
+ rtx reg;
+
+ /* Ignore anything that is not a normal insn. */
+ if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+ continue;
+
+ /* Basically ignore anything that is not a simple SET. We do have
+ to make sure to invalidate nonnull_local and set nonnull_killed
+ for such insns though. */
+ set = single_set (insn);
+ if (!set)
+ {
+ note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
+ continue;
+ }
+
+ /* See if we've got a useable memory load. We handle it first
+ in case it uses its address register as a dest (which kills
+ the nonnull property). */
+ if (GET_CODE (SET_SRC (set)) == MEM
+ && GET_CODE ((reg = XEXP (SET_SRC (set), 0))) == REG
+ && REGNO (reg) >= npi->min_reg
+ && REGNO (reg) < npi->max_reg)
+ SET_BIT (nonnull_local[current_block],
+ REGNO (reg) - npi->min_reg);
+
+ /* Now invalidate stuff clobbered by this insn. */
+ note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
+
+ /* And handle stores, we do these last since any sets in INSN can
+ not kill the nonnull property if it is derived from a MEM
+ appearing in a SET_DEST. */
+ if (GET_CODE (SET_DEST (set)) == MEM
+ && GET_CODE ((reg = XEXP (SET_DEST (set), 0))) == REG
+ && REGNO (reg) >= npi->min_reg
+ && REGNO (reg) < npi->max_reg)
+ SET_BIT (nonnull_local[current_block],
+ REGNO (reg) - npi->min_reg);
+ }
+ }
+
+ /* Now compute global properties based on the local properties. This
+ is a classic global availablity algorithm. */
+ compute_available (nonnull_local, nonnull_killed,
+ nonnull_avout, nonnull_avin);
+
+ /* Now look at each bb and see if it ends with a compare of a value
+ against zero. */
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ rtx last_insn = BLOCK_END (bb);
+ rtx condition, earliest;
+ int compare_and_branch;
+
+ /* Since MIN_REG is always at least FIRST_PSEUDO_REGISTER, and
+ since BLOCK_REG[BB] is zero if this block did not end with a
+ comparison against zero, this condition works. */
+ if (block_reg[bb] < npi->min_reg
+ || block_reg[bb] >= npi->max_reg)
+ continue;
+
+ /* LAST_INSN is a conditional jump. Get its condition. */
+ condition = get_condition (last_insn, &earliest);
+
+ /* If we can't determine the condition then skip. */
+ if (! condition)
+ continue;
+
+ /* Is the register known to have a nonzero value? */
+ if (!TEST_BIT (nonnull_avout[bb], block_reg[bb] - npi->min_reg))
+ continue;
+
+ /* Try to compute whether the compare/branch at the loop end is one or
+ two instructions. */
+ if (earliest == last_insn)
+ compare_and_branch = 1;
+ else if (earliest == prev_nonnote_insn (last_insn))
+ compare_and_branch = 2;
+ else
+ continue;
+
+ /* We know the register in this comparison is nonnull at exit from
+ this block. We can optimize this comparison. */
+ if (GET_CODE (condition) == NE)
+ {
+ rtx new_jump;
+
+ new_jump = emit_jump_insn_before (gen_jump (JUMP_LABEL (last_insn)),
+ last_insn);
+ JUMP_LABEL (new_jump) = JUMP_LABEL (last_insn);
+ LABEL_NUSES (JUMP_LABEL (new_jump))++;
+ emit_barrier_after (new_jump);
+ }
+ delete_insn (last_insn);
+ if (compare_and_branch == 2)
+ delete_insn (earliest);
+
+ /* Don't check this block again. (Note that BLOCK_END is
+ invalid here; we deleted the last instruction in the
+ block.) */
+ block_reg[bb] = 0;
+ }
+}
+
+/* Find EQ/NE comparisons against zero which can be (indirectly) evaluated
+ at compile time.
+
+ This is conceptually similar to global constant/copy propagation and
+ classic global CSE (it even uses the same dataflow equations as cprop).
+
+ If a register is used as memory address with the form (mem (reg)), then we
+ know that REG can not be zero at that point in the program. Any instruction
+ which sets REG "kills" this property.
+
+ So, if every path leading to a conditional branch has an available memory
+ reference of that form, then we know the register can not have the value
+ zero at the conditional branch.
+
+ So we merely need to compute the local properies and propagate that data
+ around the cfg, then optimize where possible.
+
+ We run this pass two times. Once before CSE, then again after CSE. This
+ has proven to be the most profitable approach. It is rare for new
+ optimization opportunities of this nature to appear after the first CSE
+ pass.
+
+ This could probably be integrated with global cprop with a little work. */
+
+void
+delete_null_pointer_checks (f)
+ rtx f ATTRIBUTE_UNUSED;
+{
+ sbitmap *nonnull_avin, *nonnull_avout;
+ unsigned int *block_reg;
+ int bb;
+ int reg;
+ int regs_per_pass;
+ int max_reg;
+ struct null_pointer_info npi;
+
+ /* If we have only a single block, then there's nothing to do. */
+ if (n_basic_blocks <= 1)
+ return;
+
+ /* Trying to perform global optimizations on flow graphs which have
+ a high connectivity will take a long time and is unlikely to be
+ particularly useful.
+
+ In normal circumstances a cfg should have about twice has many edges
+ as blocks. But we do not want to punish small functions which have
+ a couple switch statements. So we require a relatively large number
+ of basic blocks and the ratio of edges to blocks to be high. */
+ if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
+ return;
+
+ /* We need four bitmaps, each with a bit for each register in each
+ basic block. */
+ max_reg = max_reg_num ();
+ regs_per_pass = get_bitmap_width (4, n_basic_blocks, max_reg);
+
+ /* Allocate bitmaps to hold local and global properties. */
+ npi.nonnull_local = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
+ npi.nonnull_killed = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
+ nonnull_avin = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
+ nonnull_avout = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
+
+ /* Go through the basic blocks, seeing whether or not each block
+ ends with a conditional branch whose condition is a comparison
+ against zero. Record the register compared in BLOCK_REG. */
+ block_reg = (unsigned int *) xcalloc (n_basic_blocks, sizeof (int));
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ rtx last_insn = BLOCK_END (bb);
+ rtx condition, earliest, reg;
+
+ /* We only want conditional branches. */
+ if (GET_CODE (last_insn) != JUMP_INSN
+ || !any_condjump_p (last_insn)
+ || !onlyjump_p (last_insn))
+ continue;
+
+ /* LAST_INSN is a conditional jump. Get its condition. */
+ condition = get_condition (last_insn, &earliest);
+
+ /* If we were unable to get the condition, or it is not a equality
+ comparison against zero then there's nothing we can do. */
+ if (!condition
+ || (GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
+ || GET_CODE (XEXP (condition, 1)) != CONST_INT
+ || (XEXP (condition, 1)
+ != CONST0_RTX (GET_MODE (XEXP (condition, 0)))))
+ continue;
+
+ /* We must be checking a register against zero. */
+ reg = XEXP (condition, 0);
+ if (GET_CODE (reg) != REG)
+ continue;
+
+ block_reg[bb] = REGNO (reg);
+ }
+
+ /* Go through the algorithm for each block of registers. */
+ for (reg = FIRST_PSEUDO_REGISTER; reg < max_reg; reg += regs_per_pass)
+ {
+ npi.min_reg = reg;
+ npi.max_reg = MIN (reg + regs_per_pass, max_reg);
+ delete_null_pointer_checks_1 (block_reg, nonnull_avin,
+ nonnull_avout, &npi);
+ }
+
+ /* Free the table of registers compared at the end of every block. */
+ free (block_reg);
+
+ /* Free bitmaps. */
+ free (npi.nonnull_local);
+ free (npi.nonnull_killed);
+ free (nonnull_avin);
+ free (nonnull_avout);
+}
+
+/* Code Hoisting variables and subroutines. */
+
+/* Very busy expressions. */
+static sbitmap *hoist_vbein;
+static sbitmap *hoist_vbeout;
+
+/* Hoistable expressions. */
+static sbitmap *hoist_exprs;
+
+/* Dominator bitmaps. */
+static sbitmap *dominators;
+
+/* ??? We could compute post dominators and run this algorithm in
+ reverse to to perform tail merging, doing so would probably be
+ more effective than the tail merging code in jump.c.
+
+ It's unclear if tail merging could be run in parallel with
+ code hoisting. It would be nice. */
+
+/* Allocate vars used for code hoisting analysis. */
+
+static void
+alloc_code_hoist_mem (n_blocks, n_exprs)
+ int n_blocks, n_exprs;
+{
+ antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
+ transp = sbitmap_vector_alloc (n_blocks, n_exprs);
+ comp = sbitmap_vector_alloc (n_blocks, n_exprs);
+
+ hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
+ hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
+ hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
+ transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
+
+ dominators = sbitmap_vector_alloc (n_blocks, n_blocks);
+}
+
+/* Free vars used for code hoisting analysis. */
+
+static void
+free_code_hoist_mem ()
+{
+ free (antloc);
+ free (transp);
+ free (comp);
+
+ free (hoist_vbein);
+ free (hoist_vbeout);
+ free (hoist_exprs);
+ free (transpout);
+
+ free (dominators);
+}
+
+/* Compute the very busy expressions at entry/exit from each block.
+
+ An expression is very busy if all paths from a given point
+ compute the expression. */
+
+static void
+compute_code_hoist_vbeinout ()
+{
+ int bb, changed, passes;
+
+ sbitmap_vector_zero (hoist_vbeout, n_basic_blocks);
+ sbitmap_vector_zero (hoist_vbein, n_basic_blocks);
+
+ passes = 0;
+ changed = 1;
+
+ while (changed)
+ {
+ changed = 0;
+
+ /* We scan the blocks in the reverse order to speed up
+ the convergence. */
+ for (bb = n_basic_blocks - 1; bb >= 0; bb--)
+ {
+ changed |= sbitmap_a_or_b_and_c (hoist_vbein[bb], antloc[bb],
+ hoist_vbeout[bb], transp[bb]);
+ if (bb != n_basic_blocks - 1)
+ sbitmap_intersection_of_succs (hoist_vbeout[bb], hoist_vbein, bb);
+ }
+
+ passes++;
+ }
+
+ if (gcse_file)
+ fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes);
+}
+
+/* Top level routine to do the dataflow analysis needed by code hoisting. */
+
+static void
+compute_code_hoist_data ()
+{
+ compute_local_properties (transp, comp, antloc, 0);
+ compute_transpout ();
+ compute_code_hoist_vbeinout ();
+ compute_flow_dominators (dominators, NULL);
+ if (gcse_file)
+ fprintf (gcse_file, "\n");
+}
+
+/* Determine if the expression identified by EXPR_INDEX would
+ reach BB unimpared if it was placed at the end of EXPR_BB.
+
+ It's unclear exactly what Muchnick meant by "unimpared". It seems
+ to me that the expression must either be computed or transparent in
+ *every* block in the path(s) from EXPR_BB to BB. Any other definition
+ would allow the expression to be hoisted out of loops, even if
+ the expression wasn't a loop invariant.
+
+ Contrast this to reachability for PRE where an expression is
+ considered reachable if *any* path reaches instead of *all*
+ paths. */
+
+static int
+hoist_expr_reaches_here_p (expr_bb, expr_index, bb, visited)
+ int expr_bb;
+ int expr_index;
+ int bb;
+ char *visited;
+{
+ edge pred;
+ int visited_allocated_locally = 0;
+
+
+ if (visited == NULL)
+ {
+ visited_allocated_locally = 1;
+ visited = xcalloc (n_basic_blocks, 1);
+ }
+
+ visited[expr_bb] = 1;
+ for (pred = BASIC_BLOCK (bb)->pred; pred != NULL; pred = pred->pred_next)
+ {
+ int pred_bb = pred->src->index;
+
+ if (pred->src == ENTRY_BLOCK_PTR)
+ break;
+ else if (visited[pred_bb])
+ continue;
+
+ /* Does this predecessor generate this expression? */
+ else if (TEST_BIT (comp[pred_bb], expr_index))
+ break;
+ else if (! TEST_BIT (transp[pred_bb], expr_index))
+ break;
+
+ /* Not killed. */
+ else
+ {
+ visited[pred_bb] = 1;
+ if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
+ pred_bb, visited))
+ break;
+ }
+ }
+ if (visited_allocated_locally)
+ free (visited);
+
+ return (pred == NULL);
+}
+\f
+/* Actually perform code hoisting. */
+
+static void
+hoist_code ()
+{
+ int bb, dominated;
+ unsigned int i;
+ struct expr **index_map;
+ struct expr *expr;
+
+ sbitmap_vector_zero (hoist_exprs, n_basic_blocks);
+
+ /* Compute a mapping from expression number (`bitmap_index') to
+ hash table entry. */
+
+ index_map = (struct expr **) xcalloc (n_exprs, sizeof (struct expr *));
+ for (i = 0; i < expr_hash_table_size; i++)
+ for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
+ index_map[expr->bitmap_index] = expr;
+
+ /* Walk over each basic block looking for potentially hoistable
+ expressions, nothing gets hoisted from the entry block. */
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ int found = 0;
+ int insn_inserted_p;
+
+ /* Examine each expression that is very busy at the exit of this
+ block. These are the potentially hoistable expressions. */
+ for (i = 0; i < hoist_vbeout[bb]->n_bits; i++)
+ {
+ int hoistable = 0;
+
+ if (TEST_BIT (hoist_vbeout[bb], i) && TEST_BIT (transpout[bb], i))
+ {
+ /* We've found a potentially hoistable expression, now
+ we look at every block BB dominates to see if it
+ computes the expression. */
+ for (dominated = 0; dominated < n_basic_blocks; dominated++)
+ {
+ /* Ignore self dominance. */
+ if (bb == dominated
+ || ! TEST_BIT (dominators[dominated], bb))
+ continue;
+
+ /* We've found a dominated block, now see if it computes
+ the busy expression and whether or not moving that
+ expression to the "beginning" of that block is safe. */
+ if (!TEST_BIT (antloc[dominated], i))
+ continue;
+
+ /* Note if the expression would reach the dominated block
+ unimpared if it was placed at the end of BB.
+
+ Keep track of how many times this expression is hoistable
+ from a dominated block into BB. */
+ if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
+ hoistable++;
+ }
+
+ /* If we found more than one hoistable occurence of this
+ expression, then note it in the bitmap of expressions to
+ hoist. It makes no sense to hoist things which are computed
+ in only one BB, and doing so tends to pessimize register
+ allocation. One could increase this value to try harder
+ to avoid any possible code expansion due to register
+ allocation issues; however experiments have shown that
+ the vast majority of hoistable expressions are only movable
+ from two successors, so raising this threshhold is likely
+ to nullify any benefit we get from code hoisting. */
+ if (hoistable > 1)
+ {
+ SET_BIT (hoist_exprs[bb], i);
+ found = 1;
+ }
+ }
+ }
+
+ /* If we found nothing to hoist, then quit now. */
+ if (! found)
+ continue;
+
+ /* Loop over all the hoistable expressions. */
+ for (i = 0; i < hoist_exprs[bb]->n_bits; i++)
+ {
+ /* We want to insert the expression into BB only once, so
+ note when we've inserted it. */
+ insn_inserted_p = 0;
+
+ /* These tests should be the same as the tests above. */
+ if (TEST_BIT (hoist_vbeout[bb], i))
+ {
+ /* We've found a potentially hoistable expression, now
+ we look at every block BB dominates to see if it
+ computes the expression. */
+ for (dominated = 0; dominated < n_basic_blocks; dominated++)
+ {
+ /* Ignore self dominance. */
+ if (bb == dominated
+ || ! TEST_BIT (dominators[dominated], bb))
+ continue;
+
+ /* We've found a dominated block, now see if it computes
+ the busy expression and whether or not moving that
+ expression to the "beginning" of that block is safe. */
+ if (!TEST_BIT (antloc[dominated], i))
+ continue;
+
+ /* The expression is computed in the dominated block and
+ it would be safe to compute it at the start of the
+ dominated block. Now we have to determine if the
+ expresion would reach the dominated block if it was
+ placed at the end of BB. */
+ if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
+ {
+ struct expr *expr = index_map[i];
+ struct occr *occr = expr->antic_occr;
+ rtx insn;
+ rtx set;
+
+ /* Find the right occurence of this expression. */
+ while (BLOCK_NUM (occr->insn) != dominated && occr)
+ occr = occr->next;
+
+ /* Should never happen. */
+ if (!occr)
+ abort ();
+
+ insn = occr->insn;
+
+ set = single_set (insn);
+ if (! set)
+ abort ();
+
+ /* Create a pseudo-reg to store the result of reaching
+ expressions into. Get the mode for the new pseudo
+ from the mode of the original destination pseudo. */
+ if (expr->reaching_reg == NULL)
+ expr->reaching_reg
+ = gen_reg_rtx (GET_MODE (SET_DEST (set)));
+
+ /* In theory this should never fail since we're creating
+ a reg->reg copy.
+
+ However, on the x86 some of the movXX patterns
+ actually contain clobbers of scratch regs. This may
+ cause the insn created by validate_change to not
+ match any pattern and thus cause validate_change to
+ fail. */
+ if (validate_change (insn, &SET_SRC (set),
+ expr->reaching_reg, 0))
+ {
+ occr->deleted_p = 1;
+ if (!insn_inserted_p)
+ {
+ insert_insn_end_bb (index_map[i], bb, 0);
+ insn_inserted_p = 1;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ free (index_map);
+}
+
+/* Top level routine to perform one code hoisting (aka unification) pass
+
+ Return non-zero if a change was made. */
+
+static int
+one_code_hoisting_pass ()
+{
+ int changed = 0;
+
+ alloc_expr_hash_table (max_cuid);
+ compute_expr_hash_table ();
+ if (gcse_file)
+ dump_hash_table (gcse_file, "Code Hosting Expressions", expr_hash_table,
+ expr_hash_table_size, n_exprs);
+
+ if (n_exprs > 0)
+ {
+ alloc_code_hoist_mem (n_basic_blocks, n_exprs);
+ compute_code_hoist_data ();
+ hoist_code ();
+ free_code_hoist_mem ();
+ }
+
+ free_expr_hash_table ();
+
+ return changed;
+}
OSDN Git Service
