X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgcse.c;h=803ab3e5a148a91d4dd3d87c8182f119403a2017;hb=a43fd4afd064952990d3eb5bedc01bee197576bd;hp=b0a592d4d66ccab7938014e8c739f1ae2c832896;hpb=0f11b6b57c70911c59af9493ec631d1d71c59d43;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/gcse.c b/gcc/gcse.c index b0a592d4d66..803ab3e5a14 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -1,7 +1,7 @@ /* Global common subexpression elimination/Partial redundancy elimination and global constant/copy propagation for GNU compiler. Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, - 2006, 2007 Free Software Foundation, Inc. + 2006, 2007, 2008, 2009 Free Software Foundation, Inc. This file is part of GCC. @@ -27,9 +27,6 @@ along with GCC; see the file COPYING3. If not see - 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 */ @@ -172,6 +169,7 @@ along with GCC; see the file COPYING3. If not see #include "hashtab.h" #include "df.h" #include "dbgcnt.h" +#include "target.h" /* Propagate flow information through back edges and thus enable PRE's moving loop invariant calculations out of loops. @@ -190,16 +188,18 @@ along with GCC; see the file COPYING3. If not see We perform the following steps: - 1) Compute basic block information. + 1) Compute table of places where registers are set. - 2) Compute table of places where registers are set. + 2) Perform copy/constant propagation. - 3) Perform copy/constant propagation. - - 4) Perform global cse using lazy code motion if not optimizing + 3) Perform global cse using lazy code motion if not optimizing for size, or code hoisting if we are. - 5) Perform another pass of copy/constant propagation. + 4) Perform another pass of copy/constant propagation. Try to bypass + conditional jumps if the condition can be computed from a value of + an incoming edge. + + 5) Perform store motion. 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 @@ -212,6 +212,11 @@ along with GCC; see the file COPYING3. If not see (set (pseudo-reg) (expression)). Function want_to_gcse_p says what these are. + In addition, expressions in REG_EQUAL notes are candidates for GXSE-ing. + This allows PRE to hoist expressions that are expressed in multiple insns, + such as comprex address calculations (e.g. for PIC code, or loads with a + high part and as lowe part). + PRE handles moving invariant expressions out of loops (by treating them as partially redundant). @@ -235,9 +240,13 @@ along with GCC; see the file COPYING3. If not see It was found doing copy propagation between each pass enables further substitutions. + This study was done before expressions in REG_EQUAL notes were added as + candidate expressions for optimization, and before the GIMPLE optimizers + were added. Probably, multiple passes is even less efficient now than + at the time when the study was conducted. + PRE is quite expensive in complicated functions because the DFA can take - a while to converge. Hence we only perform one pass. The parameter - max-gcse-passes can be modified if one wants to experiment. + a while to converge. Hence we only perform one pass. ********************** @@ -272,13 +281,8 @@ along with GCC; see the file COPYING3. If not see /* GCSE global vars. */ -/* 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; +/* Set to non-zero if CSE should run after all GCSE optimizations are done. */ +int flag_rerun_cse_after_global_opts; /* An obstack for our working variables. */ static struct obstack gcse_obstack; @@ -340,7 +344,7 @@ struct occr [one could build a mapping table without holes afterwards though]. Someday I'll perform the computation and figure it out. */ -struct hash_table +struct hash_table_d { /* The table itself. This is an array of `expr_hash_table_size' elements. */ @@ -357,80 +361,10 @@ struct hash_table }; /* Expression hash table. */ -static struct hash_table expr_hash_table; +static struct hash_table_d expr_hash_table; /* Copy propagation hash table. */ -static struct hash_table set_hash_table; - -/* Mapping of uids to cuids. - Only real insns get cuids. */ -static int *uid_cuid; - -/* Highest UID in UID_CUID. */ -static int max_uid; - -/* Get the cuid of an insn. */ -#ifdef ENABLE_CHECKING -#define INSN_CUID(INSN) \ - (gcc_assert (INSN_UID (INSN) <= max_uid), uid_cuid[INSN_UID (INSN)]) -#else -#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)]) -#endif - -/* Number of cuids. */ -static int max_cuid; - -/* Mapping of cuids to insns. */ -static rtx *cuid_insn; - -/* Get insn from cuid. */ -#define CUID_INSN(CUID) (cuid_insn[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 unsigned int max_gcse_regno; - -/* 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]. - - `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. */ - -typedef struct reg_set -{ - /* The next setting of this register. */ - struct reg_set *next; - /* The index of the block where it was set. */ - int bb_index; -} 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 +static struct hash_table_d set_hash_table; /* This is a list of expressions which are MEMs and will be used by load or store motion. @@ -471,13 +405,6 @@ static htab_t pre_ldst_table = NULL; the start of the basic block. */ static regset reg_set_bitmap; -/* For each block, a bitmap of registers set in the block. - This is used by compute_transp. - It is computed during hash table computation and not by compute_sets - as it includes registers added since the last pass (or between cprop and - gcse) and it's currently not easy to realloc sbitmap vectors. */ -static sbitmap *reg_set_in_block; - /* Array, indexed by basic block number for a list of insns which modify memory within that block. */ static rtx * modify_mem_list; @@ -511,45 +438,38 @@ static int global_const_prop_count; static int global_copy_prop_count; /* For available exprs */ -static sbitmap *ae_kill, *ae_gen; +static sbitmap *ae_kill; static void compute_can_copy (void); static void *gmalloc (size_t) ATTRIBUTE_MALLOC; static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC; -static void *grealloc (void *, size_t); static void *gcse_alloc (unsigned long); static void alloc_gcse_mem (void); static void free_gcse_mem (void); -static void alloc_reg_set_mem (int); -static void free_reg_set_mem (void); -static void record_one_set (int, rtx); -static void record_set_info (rtx, const_rtx, void *); -static void compute_sets (void); -static void hash_scan_insn (rtx, struct hash_table *, int); -static void hash_scan_set (rtx, rtx, struct hash_table *); -static void hash_scan_clobber (rtx, rtx, struct hash_table *); -static void hash_scan_call (rtx, rtx, struct hash_table *); +static void hash_scan_insn (rtx, struct hash_table_d *); +static void hash_scan_set (rtx, rtx, struct hash_table_d *); +static void hash_scan_clobber (rtx, rtx, struct hash_table_d *); +static void hash_scan_call (rtx, rtx, struct hash_table_d *); static int want_to_gcse_p (rtx); -static bool can_assign_to_reg_p (rtx); static bool gcse_constant_p (const_rtx); static int oprs_unchanged_p (const_rtx, const_rtx, int); static int oprs_anticipatable_p (const_rtx, const_rtx); static int oprs_available_p (const_rtx, const_rtx); static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, - struct hash_table *); -static void insert_set_in_table (rtx, rtx, struct hash_table *); + struct hash_table_d *); +static void insert_set_in_table (rtx, rtx, struct hash_table_d *); static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int); static unsigned int hash_set (int, int); static int expr_equiv_p (const_rtx, const_rtx); static void record_last_reg_set_info (rtx, int); static void record_last_mem_set_info (rtx); static void record_last_set_info (rtx, const_rtx, void *); -static void compute_hash_table (struct hash_table *); -static void alloc_hash_table (int, struct hash_table *, int); -static void free_hash_table (struct hash_table *); -static void compute_hash_table_work (struct hash_table *); -static void dump_hash_table (FILE *, const char *, struct hash_table *); -static struct expr *lookup_set (unsigned int, struct hash_table *); +static void compute_hash_table (struct hash_table_d *); +static void alloc_hash_table (struct hash_table_d *, int); +static void free_hash_table (struct hash_table_d *); +static void compute_hash_table_work (struct hash_table_d *); +static void dump_hash_table (FILE *, const char *, struct hash_table_d *); +static struct expr *lookup_set (unsigned int, struct hash_table_d *); static struct expr *next_set (unsigned int, struct expr *); static void reset_opr_set_tables (void); static int oprs_not_set_p (const_rtx, const_rtx); @@ -562,7 +482,7 @@ static void free_cprop_mem (void); static void compute_transp (const_rtx, int, sbitmap *, int); static void compute_transpout (void); static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *, - struct hash_table *); + struct hash_table_d *); static void compute_cprop_data (void); static void find_used_regs (rtx *, void *); static int try_replace_reg (rtx, rtx, rtx); @@ -571,11 +491,10 @@ static int cprop_jump (basic_block, rtx, rtx, rtx, rtx); static void mems_conflict_for_gcse_p (rtx, const_rtx, void *); static int load_killed_in_block_p (const_basic_block, int, const_rtx, int); static void canon_list_insert (rtx, const_rtx, void *); -static int cprop_insn (rtx, int); -static int cprop (int); +static int cprop_insn (rtx); static void find_implicit_sets (void); -static int one_cprop_pass (int, bool, bool); -static bool constprop_register (rtx, rtx, rtx, bool); +static int one_cprop_pass (void); +static bool constprop_register (rtx, rtx, rtx); static struct expr *find_bypass_set (int, int); static bool reg_killed_on_edge (const_rtx, const_edge); static int bypass_block (basic_block, rtx, rtx); @@ -590,14 +509,14 @@ static void pre_insert_copy_insn (struct expr *, rtx); static void pre_insert_copies (void); static int pre_delete (void); static int pre_gcse (void); -static int one_pre_gcse_pass (int); +static int one_pre_gcse_pass (void); static void add_label_notes (rtx, rtx); static void alloc_code_hoist_mem (int, int); static void free_code_hoist_mem (void); static void compute_code_hoist_vbeinout (void); static void compute_code_hoist_data (void); static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *); -static void hoist_code (void); +static int hoist_code (void); static int one_code_hoisting_pass (void); static rtx process_insert_insn (struct expr *); static int pre_edge_insert (struct edge_list *, struct expr **); @@ -608,7 +527,6 @@ static void free_ldst_entry (struct ls_expr *); static void free_ldst_mems (void); static void print_ldst_list (FILE *); static struct ls_expr * find_rtx_in_ldst (rtx); -static int enumerate_ldsts (void); static inline struct ls_expr * first_ls_expr (void); static inline struct ls_expr * next_ls_expr (struct ls_expr *); static int simple_mem (const_rtx); @@ -616,211 +534,26 @@ static void invalidate_any_buried_refs (rtx); static void compute_ld_motion_mems (void); static void trim_ld_motion_mems (void); static void update_ld_motion_stores (struct expr *); -static void reg_set_info (rtx, const_rtx, void *); -static void reg_clear_last_set (rtx, const_rtx, void *); -static bool store_ops_ok (const_rtx, int *); -static rtx extract_mentioned_regs (rtx); -static rtx extract_mentioned_regs_helper (rtx, rtx); -static void find_moveable_store (rtx, int *, int *); -static int compute_store_table (void); -static bool load_kills_store (const_rtx, const_rtx, int); -static bool find_loads (const_rtx, const_rtx, int); -static bool store_killed_in_insn (const_rtx, const_rtx, const_rtx, int); -static bool store_killed_after (const_rtx, const_rtx, const_rtx, const_basic_block, int *, rtx *); -static bool store_killed_before (const_rtx, const_rtx, const_rtx, const_basic_block, int *); -static void build_store_vectors (void); -static void insert_insn_start_basic_block (rtx, basic_block); -static int insert_store (struct ls_expr *, edge); -static void remove_reachable_equiv_notes (basic_block, struct ls_expr *); -static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *); -static void delete_store (struct ls_expr *, basic_block); -static void free_store_memory (void); -static void store_motion (void); static void free_insn_expr_list_list (rtx *); static void clear_modify_mem_tables (void); static void free_modify_mem_tables (void); static rtx gcse_emit_move_after (rtx, rtx, rtx); static void local_cprop_find_used_regs (rtx *, void *); -static bool do_local_cprop (rtx, rtx, bool, rtx*); -static bool adjust_libcall_notes (rtx, rtx, rtx, rtx*); -static void local_cprop_pass (bool); +static bool do_local_cprop (rtx, rtx); +static int local_cprop_pass (void); static bool is_too_expensive (const char *); - - -/* Entry point for global common subexpression elimination. - F is the first instruction in the function. Return nonzero if a - change is mode. */ - -static int -gcse_main (rtx f ATTRIBUTE_UNUSED) -{ - int changed, pass; - /* Bytes used at start of pass. */ - int initial_bytes_used; - /* Maximum number of bytes used by a pass. */ - int max_pass_bytes; - /* Point to release obstack data from for each pass. */ - char *gcse_obstack_bottom; - - /* We do not construct an accurate cfg in functions which call - setjmp, so just punt to be safe. */ - if (current_function_calls_setjmp) - return 0; - - /* Assume that we do not need to run jump optimizations after gcse. */ - run_jump_opt_after_gcse = 0; - - /* Identify the basic block information for this function, including - successors and predecessors. */ - max_gcse_regno = max_reg_num (); - - df_note_add_problem (); - df_analyze (); - - if (dump_file) - dump_flow_info (dump_file, dump_flags); - - /* Return if there's nothing to do, or it is too expensive. */ - if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 - || is_too_expensive (_("GCSE disabled"))) - return 0; - - gcc_obstack_init (&gcse_obstack); - bytes_used = 0; - - /* We need alias. */ - init_alias_analysis (); - /* 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. - - 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 (); - - pass = 0; - initial_bytes_used = bytes_used; - max_pass_bytes = 0; - gcse_obstack_bottom = gcse_alloc (1); - changed = 1; - while (changed && pass < MAX_GCSE_PASSES) - { - changed = 0; - if (dump_file) - fprintf (dump_file, "GCSE pass %d\n\n", pass + 1); - - /* Initialize bytes_used to the space for the pred/succ lists, - and the reg_set_table data. */ - bytes_used = initial_bytes_used; - - /* Each pass may create new registers, so recalculate each time. */ - max_gcse_regno = max_reg_num (); - - alloc_gcse_mem (); - - /* Don't allow constant propagation to modify jumps - during this pass. */ - timevar_push (TV_CPROP1); - changed = one_cprop_pass (pass + 1, false, false); - timevar_pop (TV_CPROP1); - - if (optimize_size) - /* Do nothing. */ ; - else - { - timevar_push (TV_PRE); - changed |= one_pre_gcse_pass (pass + 1); - /* We may have just created new basic blocks. Release and - recompute various things which are sized on the number of - basic blocks. */ - if (changed) - { - free_modify_mem_tables (); - modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); - canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); - } - free_reg_set_mem (); - alloc_reg_set_mem (max_reg_num ()); - compute_sets (); - run_jump_opt_after_gcse = 1; - timevar_pop (TV_PRE); - } - - 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 are 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 don't run the partial redundancy algorithms). */ - if (optimize_size) - { - timevar_push (TV_HOIST); - max_gcse_regno = max_reg_num (); - alloc_gcse_mem (); - changed |= one_code_hoisting_pass (); - free_gcse_mem (); - - if (max_pass_bytes < bytes_used) - max_pass_bytes = bytes_used; - timevar_pop (TV_HOIST); - } - - if (dump_file) - { - fprintf (dump_file, "\n"); - fflush (dump_file); - } - - obstack_free (&gcse_obstack, gcse_obstack_bottom); - pass++; - } - - /* Do one last pass of copy propagation, including cprop into - conditional jumps. */ - - max_gcse_regno = max_reg_num (); - alloc_gcse_mem (); - /* This time, go ahead and allow cprop to alter jumps. */ - timevar_push (TV_CPROP2); - one_cprop_pass (pass + 1, true, true); - timevar_pop (TV_CPROP2); - free_gcse_mem (); - - if (dump_file) - { - fprintf (dump_file, "GCSE of %s: %d basic blocks, ", - current_function_name (), n_basic_blocks); - fprintf (dump_file, "%d pass%s, %d bytes\n\n", - pass, pass > 1 ? "es" : "", max_pass_bytes); - } - - obstack_free (&gcse_obstack, NULL); - free_reg_set_mem (); +#define GNEW(T) ((T *) gmalloc (sizeof (T))) +#define GCNEW(T) ((T *) gcalloc (1, sizeof (T))) - /* We are finished with alias. */ - end_alias_analysis (); +#define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N))) +#define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T))) - if (!optimize_size && flag_gcse_sm) - { - timevar_push (TV_LSM); - store_motion (); - timevar_pop (TV_LSM); - } +#define GNEWVAR(T, S) ((T *) gmalloc ((S))) +#define GCNEWVAR(T, S) ((T *) gcalloc (1, (S))) - /* Record where pseudo-registers are set. */ - return run_jump_opt_after_gcse; -} +#define GOBNEW(T) ((T *) gcse_alloc (sizeof (T))) +#define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S))) /* Misc. utilities. */ @@ -874,6 +607,7 @@ can_copy_p (enum machine_mode mode) return can_copy[mode] != 0; } + /* Cover function to xmalloc to record bytes allocated. */ @@ -893,16 +627,6 @@ gcalloc (size_t nelem, size_t elsize) return xcalloc (nelem, elsize); } -/* Cover function to xrealloc. - We don't record the additional size since we don't know it. - It won't affect memory usage stats much anyway. */ - -static void * -grealloc (void *ptr, size_t size) -{ - return xrealloc (ptr, size); -} - /* Cover function to obstack_alloc. */ static void * @@ -912,55 +636,19 @@ gcse_alloc (unsigned long size) return obstack_alloc (&gcse_obstack, size); } -/* Allocate memory for the cuid mapping array, - and reg/memory set tracking tables. - +/* Allocate memory for the reg/memory set tracking tables. This is called at the start of each pass. */ static void alloc_gcse_mem (void) { - int i; - basic_block bb; - rtx insn; - - /* Find the largest UID and create a mapping from UIDs to CUIDs. - CUIDs are like UIDs except they increase monotonically, have no gaps, - and only apply to real insns. - (Actually, there are gaps, for insn that are not inside a basic block. - but we should never see those anyway, so this is OK.) */ - - max_uid = get_max_uid (); - uid_cuid = gcalloc (max_uid + 1, sizeof (int)); - i = 0; - FOR_EACH_BB (bb) - FOR_BB_INSNS (bb, insn) - { - if (INSN_P (insn)) - uid_cuid[INSN_UID (insn)] = i++; - else - uid_cuid[INSN_UID (insn)] = i; - } - - /* Create a table mapping cuids to insns. */ - - max_cuid = i; - cuid_insn = gcalloc (max_cuid + 1, sizeof (rtx)); - i = 0; - FOR_EACH_BB (bb) - FOR_BB_INSNS (bb, insn) - if (INSN_P (insn)) - CUID_INSN (i++) = insn; - /* Allocate vars to track sets of regs. */ reg_set_bitmap = BITMAP_ALLOC (NULL); - /* Allocate vars to track sets of regs, memory per block. */ - reg_set_in_block = sbitmap_vector_alloc (last_basic_block, max_gcse_regno); /* Allocate array to keep a list of insns which modify memory in each basic block. */ - modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); - canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); + modify_mem_list = GCNEWVEC (rtx, last_basic_block); + canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block); modify_mem_list_set = BITMAP_ALLOC (NULL); blocks_with_calls = BITMAP_ALLOC (NULL); } @@ -970,12 +658,6 @@ alloc_gcse_mem (void) static void free_gcse_mem (void) { - free (uid_cuid); - free (cuid_insn); - - BITMAP_FREE (reg_set_bitmap); - - sbitmap_vector_free (reg_set_in_block); free_modify_mem_tables (); BITMAP_FREE (modify_mem_list_set); BITMAP_FREE (blocks_with_calls); @@ -1010,7 +692,7 @@ free_gcse_mem (void) static void compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc, - struct hash_table *table) + struct hash_table_d *table) { unsigned int i; @@ -1074,86 +756,6 @@ compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc, } } -/* Register set information. - - `reg_set_table' records where each register is set or otherwise - modified. */ - -static struct obstack reg_set_obstack; - -static void -alloc_reg_set_mem (int n_regs) -{ - reg_set_table_size = n_regs + REG_SET_TABLE_SLOP; - reg_set_table = gcalloc (reg_set_table_size, sizeof (struct reg_set *)); - - gcc_obstack_init (®_set_obstack); -} - -static void -free_reg_set_mem (void) -{ - free (reg_set_table); - obstack_free (®_set_obstack, NULL); -} - -/* Record REGNO in the reg_set table. */ - -static void -record_one_set (int regno, rtx insn) -{ - /* Allocate a new reg_set element and link it onto the list. */ - struct reg_set *new_reg_info; - - /* If the table isn't big enough, enlarge it. */ - if (regno >= reg_set_table_size) - { - int new_size = regno + REG_SET_TABLE_SLOP; - - reg_set_table = grealloc (reg_set_table, - new_size * sizeof (struct reg_set *)); - memset (reg_set_table + reg_set_table_size, 0, - (new_size - reg_set_table_size) * sizeof (struct reg_set *)); - reg_set_table_size = new_size; - } - - new_reg_info = obstack_alloc (®_set_obstack, sizeof (struct reg_set)); - bytes_used += sizeof (struct reg_set); - new_reg_info->bb_index = BLOCK_NUM (insn); - new_reg_info->next = reg_set_table[regno]; - reg_set_table[regno] = new_reg_info; -} - -/* 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 (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) -{ - rtx record_set_insn = (rtx) data; - - if (REG_P (dest) && 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 documentation. */ - -static void -compute_sets (void) -{ - basic_block bb; - rtx insn; - - FOR_EACH_BB (bb) - FOR_BB_INSNS (bb, insn) - if (INSN_P (insn)) - note_stores (PATTERN (insn), record_set_info, insn); -} - /* Hash table support. */ struct reg_avail_info @@ -1193,18 +795,28 @@ want_to_gcse_p (rtx x) return 0; default: - return can_assign_to_reg_p (x); + return can_assign_to_reg_without_clobbers_p (x); } } -/* Used internally by can_assign_to_reg_p. */ +/* Used internally by can_assign_to_reg_without_clobbers_p. */ static GTY(()) rtx test_insn; -/* Return true if we can assign X to a pseudo register. */ +/* Return true if we can assign X to a pseudo register such that the + resulting insn does not result in clobbering a hard register as a + side-effect. -static bool -can_assign_to_reg_p (rtx x) + Additionally, if the target requires it, check that the resulting insn + can be copied. If it cannot, this means that X is special and probably + has hidden side-effects we don't want to mess with. + + This function is typically used by code motion passes, to verify + that it is safe to insert an insn without worrying about clobbering + maybe live hard regs. */ + +bool +can_assign_to_reg_without_clobbers_p (rtx x) { int num_clobbers = 0; int icode; @@ -1231,8 +843,18 @@ can_assign_to_reg_p (rtx x) valid. */ PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x)); SET_SRC (PATTERN (test_insn)) = x; - return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0 - && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode))); + + icode = recog (PATTERN (test_insn), test_insn, &num_clobbers); + if (icode < 0) + return false; + + if (num_clobbers > 0 && added_clobbers_hard_reg_p (icode)) + return false; + + if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (test_insn)) + return false; + + return true; } /* Return nonzero if the operands of expression X are unchanged from the @@ -1259,13 +881,13 @@ oprs_unchanged_p (const_rtx x, const_rtx insn, int avail_p) if (info->last_bb != current_bb) return 1; if (avail_p) - return info->last_set < INSN_CUID (insn); + return info->last_set < DF_INSN_LUID (insn); else - return info->first_set >= INSN_CUID (insn); + return info->first_set >= DF_INSN_LUID (insn); } case MEM: - if (load_killed_in_block_p (current_bb, INSN_CUID (insn), + if (load_killed_in_block_p (current_bb, DF_INSN_LUID (insn), x, avail_p)) return 0; else @@ -1364,7 +986,7 @@ mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, } /* Return nonzero if the expression in X (a memory reference) is killed - in block BB before or after the insn with the CUID in UID_LIMIT. + in block BB before or after the insn with the LUID in UID_LIMIT. AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills before UID_LIMIT. @@ -1385,9 +1007,9 @@ load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x, int av rtx setter; /* Ignore entries in the list that do not apply. */ if ((avail_p - && INSN_CUID (XEXP (list_entry, 0)) < uid_limit) + && DF_INSN_LUID (XEXP (list_entry, 0)) < uid_limit) || (! avail_p - && INSN_CUID (XEXP (list_entry, 0)) > uid_limit)) + && DF_INSN_LUID (XEXP (list_entry, 0)) > uid_limit)) { list_entry = XEXP (list_entry, 1); continue; @@ -1490,7 +1112,7 @@ expr_equiv_p (const_rtx x, const_rtx y) static void insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, - int avail_p, struct hash_table *table) + int avail_p, struct hash_table_d *table) { int found, do_not_record_p; unsigned int hash; @@ -1518,7 +1140,7 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, if (! found) { - cur_expr = gcse_alloc (sizeof (struct expr)); + cur_expr = GOBNEW (struct expr); bytes_used += sizeof (struct expr); if (table->table[hash] == NULL) /* This is the first pattern that hashed to this index. */ @@ -1551,7 +1173,7 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, else { /* First occurrence of this expression in this basic block. */ - antic_occr = gcse_alloc (sizeof (struct occr)); + antic_occr = GOBNEW (struct occr); bytes_used += sizeof (struct occr); antic_occr->insn = insn; antic_occr->next = cur_expr->antic_occr; @@ -1575,7 +1197,7 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, else { /* First occurrence of this expression in this basic block. */ - avail_occr = gcse_alloc (sizeof (struct occr)); + avail_occr = GOBNEW (struct occr); bytes_used += sizeof (struct occr); avail_occr->insn = insn; avail_occr->next = cur_expr->avail_occr; @@ -1591,7 +1213,7 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, basic block. */ static void -insert_set_in_table (rtx x, rtx insn, struct hash_table *table) +insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table) { int found; unsigned int hash; @@ -1615,7 +1237,7 @@ insert_set_in_table (rtx x, rtx insn, struct hash_table *table) if (! found) { - cur_expr = gcse_alloc (sizeof (struct expr)); + cur_expr = GOBNEW (struct expr); bytes_used += sizeof (struct expr); if (table->table[hash] == NULL) /* This is the first pattern that hashed to this index. */ @@ -1648,13 +1270,12 @@ insert_set_in_table (rtx x, rtx insn, struct hash_table *table) else { /* First occurrence of this expression in this basic block. */ - cur_occr = gcse_alloc (sizeof (struct occr)); + cur_occr = GOBNEW (struct occr); bytes_used += sizeof (struct occr); - - cur_occr->insn = insn; - cur_occr->next = cur_expr->avail_occr; - cur_occr->deleted_p = 0; - cur_expr->avail_occr = cur_occr; + cur_occr->insn = insn; + cur_occr->next = cur_expr->avail_occr; + cur_occr->deleted_p = 0; + cur_expr->avail_occr = cur_occr; } } @@ -1666,8 +1287,8 @@ gcse_constant_p (const_rtx x) { /* Consider a COMPARE of two integers constant. */ if (GET_CODE (x) == COMPARE - && GET_CODE (XEXP (x, 0)) == CONST_INT - && GET_CODE (XEXP (x, 1)) == CONST_INT) + && CONST_INT_P (XEXP (x, 0)) + && CONST_INT_P (XEXP (x, 1))) return true; /* Consider a COMPARE of the same registers is a constant @@ -1679,14 +1300,16 @@ gcse_constant_p (const_rtx x) && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1)))) return true; - return CONSTANT_P (x); + /* Since X might be inserted more than once we have to take care that it + is sharable. */ + return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x)); } /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or expression one). */ static void -hash_scan_set (rtx pat, rtx insn, struct hash_table *table) +hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) { rtx src = SET_SRC (pat); rtx dest = SET_DEST (pat); @@ -1700,12 +1323,25 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) unsigned int regno = REGNO (dest); rtx tmp; - /* See if a REG_NOTE shows this equivalent to a simpler expression. + /* See if a REG_EQUAL note shows this equivalent to a simpler expression. + This allows us to do a single GCSE pass and still eliminate redundant constants, addresses or other expressions that are - constructed with multiple instructions. */ + constructed with multiple instructions. + + However, keep the original SRC if INSN is a simple reg-reg move. In + In this case, there will almost always be a REG_EQUAL note on the + insn that sets SRC. By recording the REG_EQUAL value here as SRC + for INSN, we miss copy propagation opportunities and we perform the + same PRE GCSE operation repeatedly on the same REG_EQUAL value if we + do more than one PRE GCSE pass. + + Note that this does not impede profitable constant propagations. We + "look through" reg-reg sets in lookup_avail_set. */ note = find_reg_equal_equiv_note (insn); if (note != 0 + && REG_NOTE_KIND (note) == REG_EQUAL + && !REG_P (src) && (table->set_p ? gcse_constant_p (XEXP (note, 0)) : want_to_gcse_p (XEXP (note, 0)))) @@ -1717,9 +1353,11 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) /* Don't GCSE something if we can't do a reg/reg copy. */ && can_copy_p (GET_MODE (dest)) /* GCSE commonly inserts instruction after the insn. We can't - do that easily for EH_REGION notes so disable GCSE on these - for now. */ - && !find_reg_note (insn, REG_EH_REGION, NULL_RTX) + do that easily for EH edges so disable GCSE on these for now. */ + /* ??? We can now easily create new EH landing pads at the + gimple level, for splitting edges; there's no reason we + can't do the same thing at the rtl level. */ + && !can_throw_internal (insn) /* Is SET_SRC something we want to gcse? */ && want_to_gcse_p (src) /* Don't CSE a nop. */ @@ -1779,9 +1417,8 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) /* Don't GCSE something if we can't do a reg/reg copy. */ && can_copy_p (GET_MODE (src)) /* GCSE commonly inserts instruction after the insn. We can't - do that easily for EH_REGION notes so disable GCSE on these - for now. */ - && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX) + do that easily for EH edges so disable GCSE on these for now. */ + && !can_throw_internal (insn) /* Is SET_DEST something we want to gcse? */ && want_to_gcse_p (dest) /* Don't CSE a nop. */ @@ -1812,14 +1449,14 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) static void hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, - struct hash_table *table ATTRIBUTE_UNUSED) + struct hash_table_d *table ATTRIBUTE_UNUSED) { /* Currently nothing to do. */ } static void hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, - struct hash_table *table ATTRIBUTE_UNUSED) + struct hash_table_d *table ATTRIBUTE_UNUSED) { /* Currently nothing to do. */ } @@ -1833,19 +1470,14 @@ hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, are also in the PARALLEL. Later. If SET_P is nonzero, this is for the assignment hash table, - otherwise it is for the expression hash table. - If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should - not record any expressions. */ + otherwise it is for the expression hash table. */ static void -hash_scan_insn (rtx insn, struct hash_table *table, int in_libcall_block) +hash_scan_insn (rtx insn, struct hash_table_d *table) { rtx pat = PATTERN (insn); int i; - if (in_libcall_block) - return; - /* Pick out the sets of INSN and for other forms of instructions record what's been modified. */ @@ -1871,7 +1503,7 @@ hash_scan_insn (rtx insn, struct hash_table *table, int in_libcall_block) } static void -dump_hash_table (FILE *file, const char *name, struct hash_table *table) +dump_hash_table (FILE *file, const char *name, struct hash_table_d *table) { int i; /* Flattened out table, so it's printed in proper order. */ @@ -1879,8 +1511,8 @@ dump_hash_table (FILE *file, const char *name, struct hash_table *table) unsigned int *hash_val; struct expr *expr; - flat_table = xcalloc (table->n_elems, sizeof (struct expr *)); - hash_val = xmalloc (table->n_elems * sizeof (unsigned int)); + flat_table = XCNEWVEC (struct expr *, table->n_elems); + hash_val = XNEWVEC (unsigned int, table->n_elems); for (i = 0; i < (int) table->size; i++) for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) @@ -1917,23 +1549,19 @@ dump_hash_table (FILE *file, const char *name, struct hash_table *table) is set and is used to compute "availability". last_bb records the block for which first_set and last_set are - valid, as a quick test to invalidate them. - - reg_set_in_block records whether the register is set in the block - and is used to compute "transparency". */ + valid, as a quick test to invalidate them. */ static void record_last_reg_set_info (rtx insn, int regno) { struct reg_avail_info *info = ®_avail_info[regno]; - int cuid = INSN_CUID (insn); + int luid = DF_INSN_LUID (insn); - info->last_set = cuid; + info->last_set = luid; if (info->last_bb != current_bb) { info->last_bb = current_bb; - info->first_set = cuid; - SET_BIT (reg_set_in_block[current_bb->index], regno); + info->first_set = luid; } } @@ -2036,35 +1664,25 @@ record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) TABLE is the table computed. */ static void -compute_hash_table_work (struct hash_table *table) +compute_hash_table_work (struct hash_table_d *table) { - unsigned int i; - - /* While we compute the hash table we also compute a bit array of which - registers are set in which blocks. - ??? This isn't needed during const/copy propagation, but it's cheap to - compute. Later. */ - sbitmap_vector_zero (reg_set_in_block, last_basic_block); + int i; /* re-Cache any INSN_LIST nodes we have allocated. */ clear_modify_mem_tables (); /* Some working arrays used to track first and last set in each block. */ - reg_avail_info = gmalloc (max_gcse_regno * sizeof (struct reg_avail_info)); + reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ()); - for (i = 0; i < max_gcse_regno; ++i) + for (i = 0; i < max_reg_num (); ++i) reg_avail_info[i].last_bb = NULL; FOR_EACH_BB (current_bb) { rtx insn; unsigned int regno; - int in_libcall_block; /* First pass over the instructions records information used to - determine when registers and memory are first and last set. - ??? hard-reg reg_set_in_block computation - could be moved to compute_sets since they currently don't change. */ - + determine when registers and memory are first and last set. */ FOR_BB_INSNS (current_bb, insn) { if (! INSN_P (insn)) @@ -2089,18 +1707,9 @@ compute_hash_table_work (struct hash_table *table) BB_HEAD (current_bb), table); /* The next pass builds the hash table. */ - in_libcall_block = 0; FOR_BB_INSNS (current_bb, insn) if (INSN_P (insn)) - { - if (find_reg_note (insn, REG_LIBCALL, NULL_RTX)) - in_libcall_block = 1; - else if (table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX)) - in_libcall_block = 0; - hash_scan_insn (insn, table, in_libcall_block); - if (!table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX)) - in_libcall_block = 0; - } + hash_scan_insn (insn, table); } free (reg_avail_info); @@ -2108,17 +1717,18 @@ compute_hash_table_work (struct hash_table *table) } /* Allocate space for the set/expr hash TABLE. - N_INSNS is the number of instructions in the function. It is used to determine the number of buckets to use. SET_P determines whether set or expression table will be created. */ static void -alloc_hash_table (int n_insns, struct hash_table *table, int set_p) +alloc_hash_table (struct hash_table_d *table, int set_p) { int n; - table->size = n_insns / 4; + n = get_max_insn_count (); + + table->size = n / 4; if (table->size < 11) table->size = 11; @@ -2127,14 +1737,14 @@ alloc_hash_table (int n_insns, struct hash_table *table, int set_p) ??? Later take some measurements. */ table->size |= 1; n = table->size * sizeof (struct expr *); - table->table = gmalloc (n); + table->table = GNEWVAR (struct expr *, n); table->set_p = set_p; } /* Free things allocated by alloc_hash_table. */ static void -free_hash_table (struct hash_table *table) +free_hash_table (struct hash_table_d *table) { free (table->table); } @@ -2143,7 +1753,7 @@ free_hash_table (struct hash_table *table) expression hash table. */ static void -compute_hash_table (struct hash_table *table) +compute_hash_table (struct hash_table_d *table) { /* Initialize count of number of entries in hash table. */ table->n_elems = 0; @@ -2158,7 +1768,7 @@ compute_hash_table (struct hash_table *table) table entry, or NULL if not found. */ static struct expr * -lookup_set (unsigned int regno, struct hash_table *table) +lookup_set (unsigned int regno, struct hash_table_d *table) { unsigned int hash = hash_set (regno, table->size); struct expr *expr; @@ -2278,7 +1888,7 @@ oprs_not_set_p (const_rtx x, const_rtx insn) case MEM: if (load_killed_in_block_p (BLOCK_FOR_INSN (insn), - INSN_CUID (insn), x, 0)) + DF_INSN_LUID (insn), x, 0)) return 0; else return oprs_not_set_p (XEXP (x, 0), insn); @@ -2317,7 +1927,7 @@ oprs_not_set_p (const_rtx x, const_rtx insn) static void mark_call (rtx insn) { - if (! CONST_OR_PURE_CALL_P (insn)) + if (! RTL_CONST_OR_PURE_CALL_P (insn)) record_last_mem_set_info (insn); } @@ -2433,9 +2043,7 @@ static void compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p) { int i, j; - basic_block bb; enum rtx_code code; - reg_set *r; const char *fmt; /* repeat is used to turn tail-recursion into iteration since GCC @@ -2451,31 +2059,19 @@ compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p) case REG: if (set_p) { - if (REGNO (x) < FIRST_PSEUDO_REGISTER) - { - FOR_EACH_BB (bb) - if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x))) - SET_BIT (bmap[bb->index], indx); - } - else - { - for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next) - SET_BIT (bmap[r->bb_index], indx); - } + df_ref def; + for (def = DF_REG_DEF_CHAIN (REGNO (x)); + def; + def = DF_REF_NEXT_REG (def)) + SET_BIT (bmap[DF_REF_BB (def)->index], indx); } else { - if (REGNO (x) < FIRST_PSEUDO_REGISTER) - { - FOR_EACH_BB (bb) - if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x))) - RESET_BIT (bmap[bb->index], indx); - } - else - { - for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next) - RESET_BIT (bmap[r->bb_index], indx); - } + df_ref def; + for (def = DF_REG_DEF_CHAIN (REGNO (x)); + def; + def = DF_REF_NEXT_REG (def)) + RESET_BIT (bmap[DF_REF_BB (def)->index], indx); } return; @@ -2516,7 +2112,7 @@ compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p) dest_addr = XEXP (list_entry, 0); if (canon_true_dependence (dest, GET_MODE (dest), dest_addr, - x, rtx_addr_varies_p)) + x, NULL_RTX, rtx_addr_varies_p)) { if (set_p) SET_BIT (bmap[bb_index], indx); @@ -2680,7 +2276,8 @@ try_replace_reg (rtx from, rtx to, rtx insn) with our replacement. */ if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL) set_unique_reg_note (insn, REG_EQUAL, - simplify_replace_rtx (XEXP (note, 0), from, to)); + simplify_replace_rtx (XEXP (note, 0), from, + copy_rtx (to))); if (!success && set && reg_mentioned_p (from, SET_SRC (set))) { /* If above failed and this is a single set, try to simplify the source of @@ -2788,7 +2385,7 @@ find_avail_set (int regno, rtx insn) static int cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) { - rtx new, set_src, note_src; + rtx new_rtx, set_src, note_src; rtx set = pc_set (jump); rtx note = find_reg_equal_equiv_note (jump); @@ -2820,22 +2417,22 @@ cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) else setcc = NULL_RTX; - new = simplify_replace_rtx (set_src, from, src); + new_rtx = simplify_replace_rtx (set_src, from, src); /* If no simplification can be made, then try the next register. */ - if (rtx_equal_p (new, SET_SRC (set))) + if (rtx_equal_p (new_rtx, SET_SRC (set))) return 0; /* If this is now a no-op delete it, otherwise this must be a valid insn. */ - if (new == pc_rtx) + if (new_rtx == pc_rtx) delete_insn (jump); else { /* Ensure the value computed inside the jump insn to be equivalent to one computed by setcc. */ - if (setcc && modified_in_p (new, setcc)) + if (setcc && modified_in_p (new_rtx, setcc)) return 0; - if (! validate_change (jump, &SET_SRC (set), new, 0)) + if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0)) { /* When (some) constants are not valid in a comparison, and there are two registers to be replaced by constants before the entire @@ -2846,8 +2443,8 @@ cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) we need to attach a note to the branch itself to make this optimization work. */ - if (!rtx_equal_p (new, note_src)) - set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new)); + if (!rtx_equal_p (new_rtx, note_src)) + set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx)); return 0; } @@ -2862,8 +2459,6 @@ cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) delete_insn (setcc); #endif - run_jump_opt_after_gcse = 1; - global_const_prop_count++; if (dump_file != NULL) { @@ -2878,7 +2473,7 @@ cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) /* If a conditional jump has been changed into unconditional jump, remove the jump and make the edge fallthru - this is always called in cfglayout mode. */ - if (new != pc_rtx && simplejump_p (jump)) + if (new_rtx != pc_rtx && simplejump_p (jump)) { edge e; edge_iterator ei; @@ -2897,14 +2492,13 @@ cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) } static bool -constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps) +constprop_register (rtx insn, rtx from, rtx to) { rtx sset; /* Check for reg or cc0 setting instructions followed by conditional branch instructions first. */ - if (alter_jumps - && (sset = single_set (insn)) != NULL + if ((sset = single_set (insn)) != NULL && NEXT_INSN (insn) && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn))) { @@ -2925,7 +2519,7 @@ constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps) Right now the insn in question must look like (set (pc) (if_then_else ...)) */ - else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn)) + else if (any_condjump_p (insn) && onlyjump_p (insn)) return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to); return 0; } @@ -2934,7 +2528,7 @@ constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps) The result is nonzero if a change was made. */ static int -cprop_insn (rtx insn, int alter_jumps) +cprop_insn (rtx insn) { struct reg_use *reg_used; int changed = 0; @@ -2959,11 +2553,6 @@ cprop_insn (rtx insn, int alter_jumps) rtx pat, src; struct expr *set; - /* Ignore registers created by GCSE. - We do this because ... */ - if (regno >= max_gcse_regno) - continue; - /* If the register has already been set in this block, there's nothing we can do. */ if (! oprs_not_set_p (reg_used->reg_rtx, insn)) @@ -2984,7 +2573,7 @@ cprop_insn (rtx insn, int alter_jumps) /* Constant propagation. */ if (gcse_constant_p (src)) { - if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps)) + if (constprop_register (insn, reg_used->reg_rtx, src)) { changed = 1; global_const_prop_count++; @@ -3023,6 +2612,9 @@ cprop_insn (rtx insn, int alter_jumps) } } + if (changed && DEBUG_INSN_P (insn)) + return 0; + return changed; } @@ -3071,11 +2663,10 @@ local_cprop_find_used_regs (rtx *xptr, void *data) find_used_regs (xptr, data); } -/* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall; - their REG_EQUAL notes need updating. */ +/* Try to perform local const/copy propagation on X in INSN. */ static bool -do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp) +do_local_cprop (rtx x, rtx insn) { rtx newreg = NULL, newcnst = NULL; @@ -3096,10 +2687,6 @@ do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp) rtx this_rtx = l->loc; rtx note; - /* Don't CSE non-constant values out of libcall blocks. */ - if (l->in_libcall && ! CONSTANT_P (this_rtx)) - continue; - if (gcse_constant_p (this_rtx)) newcnst = this_rtx; if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER @@ -3112,18 +2699,8 @@ do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp) || ! MEM_P (XEXP (note, 0)))) newreg = this_rtx; } - if (newcnst && constprop_register (insn, x, newcnst, alter_jumps)) + if (newcnst && constprop_register (insn, x, newcnst)) { - /* If we find a case where we can't fix the retval REG_EQUAL notes - match the new register, we either have to abandon this replacement - or fix delete_trivially_dead_insns to preserve the setting insn, - or make it delete the REG_EQUAL note, and fix up all passes that - require the REG_EQUAL note there. */ - bool adjusted; - - adjusted = adjust_libcall_notes (x, newcnst, insn, libcall_sp); - gcc_assert (adjusted); - if (dump_file != NULL) { fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ", @@ -3138,7 +2715,6 @@ do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp) } else if (newreg && newreg != x && try_replace_reg (x, newreg, insn)) { - adjust_libcall_notes (x, newreg, insn, libcall_sp); if (dump_file != NULL) { fprintf (dump_file, @@ -3153,80 +2729,24 @@ do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp) return false; } -/* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall; - their REG_EQUAL notes need updating to reflect that OLDREG has been - replaced with NEWVAL in INSN. Return true if all substitutions could - be made. */ -static bool -adjust_libcall_notes (rtx oldreg, rtx newval, rtx insn, rtx *libcall_sp) -{ - rtx end; - - while ((end = *libcall_sp++)) - { - rtx note = find_reg_equal_equiv_note (end); - - if (! note) - continue; - - if (REG_P (newval)) - { - if (reg_set_between_p (newval, PREV_INSN (insn), end)) - { - do - { - note = find_reg_equal_equiv_note (end); - if (! note) - continue; - if (reg_mentioned_p (newval, XEXP (note, 0))) - return false; - } - while ((end = *libcall_sp++)); - return true; - } - } - XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), oldreg, newval); - df_notes_rescan (end); - insn = end; - } - return true; -} - -#define MAX_NESTED_LIBCALLS 9 +/* Do local const/copy propagation (i.e. within each basic block). */ -/* Do local const/copy propagation (i.e. within each basic block). - If ALTER_JUMPS is true, allow propagating into jump insns, which - could modify the CFG. */ - -static void -local_cprop_pass (bool alter_jumps) +static int +local_cprop_pass (void) { basic_block bb; rtx insn; struct reg_use *reg_used; - rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp; bool changed = false; cselib_init (false); - libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS]; - *libcall_sp = 0; FOR_EACH_BB (bb) { FOR_BB_INSNS (bb, insn) { if (INSN_P (insn)) { - rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); - - if (note) - { - gcc_assert (libcall_sp != libcall_stack); - *--libcall_sp = XEXP (note, 0); - } - note = find_reg_note (insn, REG_RETVAL, NULL_RTX); - if (note) - libcall_sp++; - note = find_reg_equal_equiv_note (insn); + rtx note = find_reg_equal_equiv_note (insn); do { reg_use_count = 0; @@ -3238,8 +2758,7 @@ local_cprop_pass (bool alter_jumps) for (reg_used = ®_use_table[0]; reg_use_count > 0; reg_used++, reg_use_count--) { - if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps, - libcall_sp)) + if (do_local_cprop (reg_used->reg_rtx, insn)) { changed = true; break; @@ -3253,65 +2772,12 @@ local_cprop_pass (bool alter_jumps) cselib_process_insn (insn); } - /* Forget everything at the end of a basic block. Make sure we are - not inside a libcall, they should never cross basic blocks. */ + /* Forget everything at the end of a basic block. */ cselib_clear_table (); - gcc_assert (libcall_sp == &libcall_stack[MAX_NESTED_LIBCALLS]); } cselib_finish (); - /* Global analysis may get into infinite loops for unreachable blocks. */ - if (changed && alter_jumps) - { - delete_unreachable_blocks (); - free_reg_set_mem (); - alloc_reg_set_mem (max_reg_num ()); - compute_sets (); - } -} - -/* Forward propagate copies. This includes copies and constants. Return - nonzero if a change was made. */ - -static int -cprop (int alter_jumps) -{ - int changed; - basic_block bb; - rtx insn; - - /* Note we start at block 1. */ - if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) - { - if (dump_file != NULL) - fprintf (dump_file, "\n"); - return 0; - } - - changed = 0; - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb) - { - /* Reset tables used to keep track of what's still valid [since the - start of the block]. */ - reset_opr_set_tables (); - - FOR_BB_INSNS (bb, insn) - if (INSN_P (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. Don't - call mark_oprs_set if we turned the insn into a NOTE. */ - if (! NOTE_P (insn)) - mark_oprs_set (insn); - } - } - - if (dump_file != NULL) - fprintf (dump_file, "\n"); - return changed; } @@ -3368,14 +2834,19 @@ implicit_set_cond_p (const_rtx cond) following "if (x == 2)", the then branch may be optimized as though the conditional performed an "explicit set", in this example, "x = 2". This function records the set patterns that are implicit at the start of each - basic block. */ + basic block. + + FIXME: This would be more effective if critical edges are pre-split. As + it is now, we can't record implicit sets for blocks that have + critical successor edges. This results in missed optimizations + and in more (unnecessary) work in cfgcleanup.c:thread_jump(). */ static void find_implicit_sets (void) { basic_block bb, dest; unsigned int count; - rtx cond, new; + rtx cond, new_rtx; count = 0; FOR_EACH_BB (bb) @@ -3393,12 +2864,14 @@ find_implicit_sets (void) dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest; - if (dest && single_pred_p (dest) + if (dest + /* Record nothing for a critical edge. */ + && single_pred_p (dest) && dest != EXIT_BLOCK_PTR) { - new = gen_rtx_SET (VOIDmode, XEXP (cond, 0), + new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0), XEXP (cond, 1)); - implicit_sets[dest->index] = new; + implicit_sets[dest->index] = new_rtx; if (dump_file) { fprintf(dump_file, "Implicit set of reg %d in ", @@ -3414,64 +2887,7 @@ find_implicit_sets (void) fprintf (dump_file, "Found %d implicit sets\n", count); } -/* Perform one copy/constant propagation pass. - PASS is the pass count. If CPROP_JUMPS is true, perform constant - propagation into conditional jumps. If BYPASS_JUMPS is true, - perform conditional jump bypassing optimizations. */ - -static int -one_cprop_pass (int pass, bool cprop_jumps, bool bypass_jumps) -{ - int changed = 0; - - global_const_prop_count = local_const_prop_count = 0; - global_copy_prop_count = local_copy_prop_count = 0; - - if (cprop_jumps) - local_cprop_pass (cprop_jumps); - - /* Determine implicit sets. */ - implicit_sets = XCNEWVEC (rtx, last_basic_block); - find_implicit_sets (); - - alloc_hash_table (max_cuid, &set_hash_table, 1); - compute_hash_table (&set_hash_table); - - /* Free implicit_sets before peak usage. */ - free (implicit_sets); - implicit_sets = NULL; - - if (dump_file) - dump_hash_table (dump_file, "SET", &set_hash_table); - if (set_hash_table.n_elems > 0) - { - alloc_cprop_mem (last_basic_block, set_hash_table.n_elems); - compute_cprop_data (); - changed = cprop (cprop_jumps); - if (bypass_jumps) - changed |= bypass_conditional_jumps (); - free_cprop_mem (); - } - - free_hash_table (&set_hash_table); - - if (dump_file) - { - fprintf (dump_file, "CPROP of %s, pass %d: %d bytes needed, ", - current_function_name (), pass, bytes_used); - fprintf (dump_file, "%d local const props, %d local copy props, ", - local_const_prop_count, local_copy_prop_count); - fprintf (dump_file, "%d global const props, %d global copy props\n\n", - global_const_prop_count, global_copy_prop_count); - } - /* Global analysis may get into infinite loops for unreachable blocks. */ - if (changed && cprop_jumps) - delete_unreachable_blocks (); - - return changed; -} - -/* Bypass conditional jumps. */ +/* Bypass conditional jumps. */ /* The value of last_basic_block at the beginning of the jump_bypass pass. The use of redirect_edge_and_branch_force may introduce new @@ -3608,10 +3024,7 @@ bypass_block (basic_block bb, rtx setcc, rtx jump) unsigned int regno = REGNO (reg_used->reg_rtx); basic_block dest, old_dest; struct expr *set; - rtx src, new; - - if (regno >= max_gcse_regno) - continue; + rtx src, new_rtx; set = find_bypass_set (regno, e->src->index); @@ -3629,7 +3042,7 @@ bypass_block (basic_block bb, rtx setcc, rtx jump) SET_DEST (PATTERN (setcc)), SET_SRC (PATTERN (setcc))); - new = simplify_replace_rtx (src, reg_used->reg_rtx, + new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx, SET_SRC (set->expr)); /* Jump bypassing may have already placed instructions on @@ -3637,14 +3050,14 @@ bypass_block (basic_block bb, rtx setcc, rtx jump) has instructions associated with it, as these insns won't get executed if the incoming edge is redirected. */ - if (new == pc_rtx) + if (new_rtx == pc_rtx) { edest = FALLTHRU_EDGE (bb); dest = edest->insns.r ? NULL : edest->dest; } - else if (GET_CODE (new) == LABEL_REF) + else if (GET_CODE (new_rtx) == LABEL_REF) { - dest = BLOCK_FOR_INSN (XEXP (new, 0)); + dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0)); /* Don't bypass edges containing instructions. */ edest = find_edge (bb, dest); if (edest && edest->insns.r) @@ -3729,7 +3142,9 @@ bypass_conditional_jumps (void) { setcc = NULL_RTX; FOR_BB_INSNS (bb, insn) - if (NONJUMP_INSN_P (insn)) + if (DEBUG_INSN_P (insn)) + continue; + else if (NONJUMP_INSN_P (insn)) { if (setcc) break; @@ -3795,9 +3210,6 @@ static sbitmap *pre_delete_map; /* Contains the edge_list returned by pre_edge_lcm. */ static struct edge_list *edge_list; -/* Redundant insns. */ -static sbitmap pre_redundant_insns; - /* Allocate vars used for PRE analysis. */ static void @@ -4120,10 +3532,7 @@ insert_insn_end_basic_block (struct expr *expr, basic_block bb, int pre) while (1) { if (INSN_P (pat)) - { - add_label_notes (PATTERN (pat), new_insn); - note_stores (PATTERN (pat), record_set_info, pat); - } + add_label_notes (PATTERN (pat), new_insn); if (pat == pat_end) break; pat = NEXT_INSN (pat); @@ -4202,7 +3611,7 @@ pre_edge_insert (struct edge_list *edge_list, struct expr **index_map) if (dump_file) { - fprintf (dump_file, "PRE/HOIST: edge (%d,%d), ", + fprintf (dump_file, "PRE: edge (%d,%d), ", bb->index, INDEX_EDGE_SUCC_BB (edge_list, e)->index); fprintf (dump_file, "copy expression %d\n", @@ -4296,17 +3705,11 @@ pre_insert_copy_insn (struct expr *expr, rtx insn) { new_insn = gen_move_insn (old_reg, reg); new_insn = emit_insn_after (new_insn, insn); - - /* Keep register set table up to date. */ - record_one_set (regno, insn); } else { new_insn = gen_move_insn (reg, old_reg); new_insn = emit_insn_after (new_insn, insn); - - /* Keep register set table up to date. */ - record_one_set (regno, new_insn); } } else /* This is possible only in case of a store to memory. */ @@ -4319,9 +3722,6 @@ pre_insert_copy_insn (struct expr *expr, rtx insn) new_insn = emit_insn_before (new_insn, insn); else new_insn = emit_insn_after (new_insn, insn); - - /* Keep register set table up to date. */ - record_one_set (regno, new_insn); } gcse_create_count++; @@ -4378,7 +3778,7 @@ pre_insert_copies (void) continue; /* Don't handle this one if it's a redundant one. */ - if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn))) + if (INSN_DELETED_P (insn)) continue; /* Or if the expression doesn't reach the deleted one. */ @@ -4405,7 +3805,7 @@ pre_insert_copies (void) static rtx gcse_emit_move_after (rtx src, rtx dest, rtx insn) { - rtx new; + rtx new_rtx; rtx set = single_set (insn), set2; rtx note; rtx eqv; @@ -4413,20 +3813,20 @@ gcse_emit_move_after (rtx src, rtx dest, rtx insn) /* This should never fail since we're creating a reg->reg copy we've verified to be valid. */ - new = emit_insn_after (gen_move_insn (dest, src), insn); + new_rtx = emit_insn_after (gen_move_insn (dest, src), insn); /* Note the equivalence for local CSE pass. */ - set2 = single_set (new); + set2 = single_set (new_rtx); if (!set2 || !rtx_equal_p (SET_DEST (set2), dest)) - return new; + return new_rtx; if ((note = find_reg_equal_equiv_note (insn))) eqv = XEXP (note, 0); else eqv = SET_SRC (set); - set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (eqv)); + set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv)); - return new; + return new_rtx; } /* Delete redundant computations. @@ -4470,13 +3870,11 @@ pre_delete (void) 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))); + expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set)); gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); delete_insn (insn); occr->deleted_p = 1; - SET_BIT (pre_redundant_insns, INSN_CUID (insn)); changed = 1; gcse_subst_count++; @@ -4531,10 +3929,6 @@ pre_gcse (void) for (expr = expr_hash_table.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_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 @@ -4553,7 +3947,6 @@ pre_gcse (void) } free (index_map); - sbitmap_free (pre_redundant_insns); return changed; } @@ -4562,14 +3955,26 @@ pre_gcse (void) Return nonzero if a change was made. */ static int -one_pre_gcse_pass (int pass) +one_pre_gcse_pass (void) { int changed = 0; gcse_subst_count = 0; gcse_create_count = 0; - alloc_hash_table (max_cuid, &expr_hash_table, 0); + /* Return if there's nothing to do, or it is too expensive. */ + if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 + || is_too_expensive (_("PRE disabled"))) + return 0; + + /* We need alias. */ + init_alias_analysis (); + + bytes_used = 0; + gcc_obstack_init (&gcse_obstack); + alloc_gcse_mem (); + + alloc_hash_table (&expr_hash_table, 0); add_noreturn_fake_exit_edges (); if (flag_gcse_lm) compute_ld_motion_mems (); @@ -4592,10 +3997,16 @@ one_pre_gcse_pass (int pass) remove_fake_exit_edges (); free_hash_table (&expr_hash_table); + free_gcse_mem (); + obstack_free (&gcse_obstack, NULL); + + /* We are finished with alias. */ + end_alias_analysis (); + if (dump_file) { - fprintf (dump_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ", - current_function_name (), pass, bytes_used); + fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ", + current_function_name (), n_basic_blocks, bytes_used); fprintf (dump_file, "%d substs, %d insns created\n", gcse_subst_count, gcse_create_count); } @@ -4628,18 +4039,15 @@ add_label_notes (rtx x, rtx insn) We no longer ignore such label references (see LABEL_REF handling in mark_jump_label for additional information). */ - if (reg_mentioned_p (XEXP (x, 0), insn)) - { - /* There's no reason for current users to emit jump-insns - with such a LABEL_REF, so we don't have to handle - REG_LABEL_TARGET notes. */ - gcc_assert (!JUMP_P (insn)); - REG_NOTES (insn) - = gen_rtx_INSN_LIST (REG_LABEL_OPERAND, XEXP (x, 0), - REG_NOTES (insn)); - if (LABEL_P (XEXP (x, 0))) - LABEL_NUSES (XEXP (x, 0))++; - } + /* There's no reason for current users to emit jump-insns with + such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET + notes. */ + gcc_assert (!JUMP_P (insn)); + add_reg_note (insn, REG_LABEL_OPERAND, XEXP (x, 0)); + + if (LABEL_P (XEXP (x, 0))) + LABEL_NUSES (XEXP (x, 0))++; + return; } @@ -4677,7 +4085,7 @@ compute_transpout (void) FOR_EACH_BB (bb) { - /* Note that flow inserted a nop a the end of basic blocks that + /* Note that flow inserted a nop at the end of basic blocks that end in call instructions for reasons other than abnormal control flow. */ if (! CALL_P (BB_END (bb))) @@ -4863,7 +4271,7 @@ hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, /* Actually perform code hoisting. */ -static void +static int hoist_code (void) { basic_block bb, dominated; @@ -4871,6 +4279,7 @@ hoist_code (void) unsigned int i,j; struct expr **index_map; struct expr *expr; + int changed = 0; sbitmap_vector_zero (hoist_exprs, last_basic_block); @@ -4997,11 +4406,14 @@ hoist_code (void) from the mode of the original destination pseudo. */ if (expr->reaching_reg == NULL) expr->reaching_reg - = gen_reg_rtx (GET_MODE (SET_DEST (set))); + = gen_reg_rtx_and_attrs (SET_DEST (set)); gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); delete_insn (insn); occr->deleted_p = 1; + changed = 1; + gcse_subst_count++; + if (!insn_inserted_p) { insert_insn_end_basic_block (index_map[i], bb, 0); @@ -5015,6 +4427,8 @@ hoist_code (void) } free (index_map); + + return changed; } /* Top level routine to perform one code hoisting (aka unification) pass @@ -5026,7 +4440,22 @@ one_code_hoisting_pass (void) { int changed = 0; - alloc_hash_table (max_cuid, &expr_hash_table, 0); + gcse_subst_count = 0; + gcse_create_count = 0; + + /* Return if there's nothing to do, or it is too expensive. */ + if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 + || is_too_expensive (_("GCSE disabled"))) + return 0; + + /* We need alias. */ + init_alias_analysis (); + + bytes_used = 0; + gcc_obstack_init (&gcse_obstack); + alloc_gcse_mem (); + + alloc_hash_table (&expr_hash_table, 0); compute_hash_table (&expr_hash_table); if (dump_file) dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table); @@ -5035,11 +4464,24 @@ one_code_hoisting_pass (void) { alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems); compute_code_hoist_data (); - hoist_code (); + changed = hoist_code (); free_code_hoist_mem (); } free_hash_table (&expr_hash_table); + free_gcse_mem (); + obstack_free (&gcse_obstack, NULL); + + /* We are finished with alias. */ + end_alias_analysis (); + + if (dump_file) + { + fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ", + current_function_name (), n_basic_blocks, bytes_used); + fprintf (dump_file, "%d substs, %d insns created\n", + gcse_subst_count, gcse_create_count); + } return changed; } @@ -5073,14 +4515,15 @@ static hashval_t pre_ldst_expr_hash (const void *p) { int do_not_record_p = 0; - const struct ls_expr *x = p; + const struct ls_expr *const x = (const struct ls_expr *) p; return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false); } static int pre_ldst_expr_eq (const void *p1, const void *p2) { - const struct ls_expr *ptr1 = p1, *ptr2 = p2; + const struct ls_expr *const ptr1 = (const struct ls_expr *) p1, + *const ptr2 = (const struct ls_expr *) p2; return expr_equiv_p (ptr1->pattern, ptr2->pattern); } @@ -5202,21 +4645,7 @@ find_rtx_in_ldst (rtx x) slot = htab_find_slot (pre_ldst_table, &e, NO_INSERT); if (!slot || ((struct ls_expr *)*slot)->invalid) return NULL; - return *slot; -} - -/* Assign each element of the list of mems a monotonically increasing value. */ - -static int -enumerate_ldsts (void) -{ - struct ls_expr * ptr; - int n = 0; - - for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) - ptr->index = n++; - - return n; + return (struct ls_expr *) *slot; } /* Return first item in the list. */ @@ -5330,7 +4759,7 @@ compute_ld_motion_mems (void) { FOR_BB_INSNS (bb, insn) { - if (INSN_P (insn)) + if (NONDEBUG_INSN_P (insn)) { if (GET_CODE (PATTERN (insn)) == SET) { @@ -5364,7 +4793,7 @@ compute_ld_motion_mems (void) && GET_CODE (src) != ASM_OPERANDS /* Check for REG manually since want_to_gcse_p returns 0 for all REGs. */ - && can_assign_to_reg_p (src)) + && can_assign_to_reg_without_clobbers_p (src)) ptr->stores = alloc_INSN_LIST (insn, ptr->stores); else ptr->invalid = 1; @@ -5456,7 +4885,7 @@ update_ld_motion_stores (struct expr * expr) rtx pat = PATTERN (insn); rtx src = SET_SRC (pat); rtx reg = expr->reaching_reg; - rtx copy, new; + rtx copy, new_rtx; /* If we've already copied it, continue. */ if (expr->reaching_reg == src) @@ -5471,9 +4900,8 @@ update_ld_motion_stores (struct expr * expr) fprintf (dump_file, "\n"); } - copy = gen_move_insn ( reg, copy_rtx (SET_SRC (pat))); - new = emit_insn_before (copy, insn); - record_one_set (REGNO (reg), new); + copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat))); + new_rtx = emit_insn_before (copy, insn); SET_SRC (pat) = reg; df_insn_rescan (insn); @@ -5484,1305 +4912,278 @@ update_ld_motion_stores (struct expr * expr) } } -/* Store motion code. */ - -#define ANTIC_STORE_LIST(x) ((x)->loads) -#define AVAIL_STORE_LIST(x) ((x)->stores) -#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg) - -/* This is used to communicate the target bitvector we want to use in the - reg_set_info routine when called via the note_stores mechanism. */ -static int * regvec; - -/* And current insn, for the same routine. */ -static rtx compute_store_table_current_insn; - -/* Used in computing the reverse edge graph bit vectors. */ -static sbitmap * st_antloc; - -/* Global holding the number of store expressions we are dealing with. */ -static int num_stores; - -/* Checks to set if we need to mark a register set. Called from - note_stores. */ +/* Return true if the graph is too expensive to optimize. PASS is the + optimization about to be performed. */ -static void -reg_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, - void *data) +static bool +is_too_expensive (const char *pass) { - sbitmap bb_reg = data; + /* 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. - if (GET_CODE (dest) == SUBREG) - dest = SUBREG_REG (dest); + In normal circumstances a cfg should have about twice as many + edges as blocks. But we do not want to punish small functions + which have a couple switch statements. Rather than simply + threshold the number of blocks, uses something with a more + graceful degradation. */ + if (n_edges > 20000 + n_basic_blocks * 4) + { + warning (OPT_Wdisabled_optimization, + "%s: %d basic blocks and %d edges/basic block", + pass, n_basic_blocks, n_edges / n_basic_blocks); - if (REG_P (dest)) + return true; + } + + /* If allocating memory for the cprop bitmap would take up too much + storage it's better just to disable the optimization. */ + if ((n_basic_blocks + * SBITMAP_SET_SIZE (max_reg_num ()) + * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) { - regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn); - if (bb_reg) - SET_BIT (bb_reg, REGNO (dest)); + warning (OPT_Wdisabled_optimization, + "%s: %d basic blocks and %d registers", + pass, n_basic_blocks, max_reg_num ()); + + return true; } + + return false; } -/* Clear any mark that says that this insn sets dest. Called from - note_stores. */ + +/* Main function for the CPROP pass. */ -static void -reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, - void *data) +static int +one_cprop_pass (void) { - int *dead_vec = data; - - if (GET_CODE (dest) == SUBREG) - dest = SUBREG_REG (dest); + int changed = 0; - if (REG_P (dest) && - dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn)) - dead_vec[REGNO (dest)] = 0; -} + /* Return if there's nothing to do, or it is too expensive. */ + if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 + || is_too_expensive (_ ("const/copy propagation disabled"))) + return 0; -/* Return zero if some of the registers in list X are killed - due to set of registers in bitmap REGS_SET. */ + global_const_prop_count = local_const_prop_count = 0; + global_copy_prop_count = local_copy_prop_count = 0; -static bool -store_ops_ok (const_rtx x, int *regs_set) -{ - const_rtx reg; + bytes_used = 0; + gcc_obstack_init (&gcse_obstack); + alloc_gcse_mem (); - for (; x; x = XEXP (x, 1)) + /* Do a local const/copy propagation pass first. The global pass + only handles global opportunities. + If the local pass changes something, remove any unreachable blocks + because the CPROP global dataflow analysis may get into infinite + loops for CFGs with unreachable blocks. + + FIXME: This local pass should not be necessary after CSE (but for + some reason it still is). It is also (proven) not necessary + to run the local pass right after FWPWOP. + + FIXME: The global analysis would not get into infinite loops if it + would use the DF solver (via df_simple_dataflow) instead of + the solver implemented in this file. */ + if (local_cprop_pass ()) { - reg = XEXP (x, 0); - if (regs_set[REGNO(reg)]) - return false; + delete_unreachable_blocks (); + df_analyze (); } - return true; -} - -/* Returns a list of registers mentioned in X. */ -static rtx -extract_mentioned_regs (rtx x) -{ - return extract_mentioned_regs_helper (x, NULL_RTX); -} - -/* Helper for extract_mentioned_regs; ACCUM is used to accumulate used - registers. */ -static rtx -extract_mentioned_regs_helper (rtx x, rtx accum) -{ - int i; - enum rtx_code code; - const char * fmt; + /* Determine implicit sets. */ + implicit_sets = XCNEWVEC (rtx, last_basic_block); + find_implicit_sets (); - /* Repeat is used to turn tail-recursion into iteration. */ - repeat: + alloc_hash_table (&set_hash_table, 1); + compute_hash_table (&set_hash_table); - if (x == 0) - return accum; + /* Free implicit_sets before peak usage. */ + free (implicit_sets); + implicit_sets = NULL; - code = GET_CODE (x); - switch (code) + if (dump_file) + dump_hash_table (dump_file, "SET", &set_hash_table); + if (set_hash_table.n_elems > 0) { - case REG: - return alloc_EXPR_LIST (0, x, accum); + basic_block bb; + rtx insn; - case MEM: - x = XEXP (x, 0); - goto repeat; + alloc_cprop_mem (last_basic_block, set_hash_table.n_elems); + compute_cprop_data (); - case PRE_DEC: - case PRE_INC: - case PRE_MODIFY: - case POST_DEC: - case POST_INC: - case POST_MODIFY: - /* We do not run this function with arguments having side effects. */ - gcc_unreachable (); + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb) + { + /* Reset tables used to keep track of what's still valid [since + the start of the block]. */ + reset_opr_set_tables (); - case PC: - case CC0: /*FIXME*/ - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case CONST_FIXED: - case CONST_VECTOR: - case SYMBOL_REF: - case LABEL_REF: - case ADDR_VEC: - case ADDR_DIFF_VEC: - return accum; + FOR_BB_INSNS (bb, insn) + if (INSN_P (insn)) + { + changed |= cprop_insn (insn); + + /* Keep track of everything modified by this 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 (! NOTE_P (insn)) + mark_oprs_set (insn); + } + } - default: - break; + changed |= bypass_conditional_jumps (); + free_cprop_mem (); } - i = GET_RTX_LENGTH (code) - 1; - fmt = GET_RTX_FORMAT (code); + free_hash_table (&set_hash_table); + free_gcse_mem (); + obstack_free (&gcse_obstack, NULL); - for (; i >= 0; i--) + if (dump_file) { - 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. */ - if (i == 0) - { - x = tem; - goto repeat; - } - - accum = extract_mentioned_regs_helper (tem, accum); - } - else if (fmt[i] == 'E') - { - int j; - - for (j = 0; j < XVECLEN (x, i); j++) - accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum); - } + fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ", + current_function_name (), n_basic_blocks, bytes_used); + fprintf (dump_file, "%d local const props, %d local copy props, ", + local_const_prop_count, local_copy_prop_count); + fprintf (dump_file, "%d global const props, %d global copy props\n\n", + global_const_prop_count, global_copy_prop_count); } - return accum; + return changed; } -/* Determine whether INSN is MEM store pattern that we will consider moving. - REGS_SET_BEFORE is bitmap of registers set before (and including) the - current insn, REGS_SET_AFTER is bitmap of registers set after (and - including) the insn in this basic block. We must be passing through BB from - head to end, as we are using this fact to speed things up. + +/* All the passes implemented in this file. Each pass has its + own gate and execute function, and at the end of the file a + pass definition for passes.c. - The results are stored this way: + We do not construct an accurate cfg in functions which call + setjmp, so none of these passes runs if the function calls + setjmp. + FIXME: Should just handle setjmp via REG_SETJMP notes. */ - -- the first anticipatable expression is added into ANTIC_STORE_LIST - -- if the processed expression is not anticipatable, NULL_RTX is added - there instead, so that we can use it as indicator that no further - expression of this type may be anticipatable - -- if the expression is available, it is added as head of AVAIL_STORE_LIST; - consequently, all of them but this head are dead and may be deleted. - -- if the expression is not available, the insn due to that it fails to be - available is stored in reaching_reg. - - The things are complicated a bit by fact that there already may be stores - to the same MEM from other blocks; also caller must take care of the - necessary cleanup of the temporary markers after end of the basic block. - */ - -static void -find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after) -{ - struct ls_expr * ptr; - rtx dest, set, tmp; - int check_anticipatable, check_available; - basic_block bb = BLOCK_FOR_INSN (insn); - - set = single_set (insn); - if (!set) - return; - - dest = SET_DEST (set); - - if (! MEM_P (dest) || MEM_VOLATILE_P (dest) - || GET_MODE (dest) == BLKmode) - return; - - if (side_effects_p (dest)) - return; - - /* If we are handling exceptions, we must be careful with memory references - that may trap. If we are not, the behavior is undefined, so we may just - continue. */ - if (flag_non_call_exceptions && may_trap_p (dest)) - return; - - /* Even if the destination cannot trap, the source may. In this case we'd - need to handle updating the REG_EH_REGION note. */ - if (find_reg_note (insn, REG_EH_REGION, NULL_RTX)) - return; - - /* Make sure that the SET_SRC of this store insns can be assigned to - a register, or we will fail later on in replace_store_insn, which - assumes that we can do this. But sometimes the target machine has - oddities like MEM read-modify-write instruction. See for example - PR24257. */ - if (!can_assign_to_reg_p (SET_SRC (set))) - return; - - ptr = ldst_entry (dest); - if (!ptr->pattern_regs) - ptr->pattern_regs = extract_mentioned_regs (dest); - - /* Do not check for anticipatability if we either found one anticipatable - store already, or tested for one and found out that it was killed. */ - check_anticipatable = 0; - if (!ANTIC_STORE_LIST (ptr)) - check_anticipatable = 1; - else - { - tmp = XEXP (ANTIC_STORE_LIST (ptr), 0); - if (tmp != NULL_RTX - && BLOCK_FOR_INSN (tmp) != bb) - check_anticipatable = 1; - } - if (check_anticipatable) - { - if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before)) - tmp = NULL_RTX; - else - tmp = insn; - ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp, - ANTIC_STORE_LIST (ptr)); - } - - /* It is not necessary to check whether store is available if we did - it successfully before; if we failed before, do not bother to check - until we reach the insn that caused us to fail. */ - check_available = 0; - if (!AVAIL_STORE_LIST (ptr)) - check_available = 1; - else - { - tmp = XEXP (AVAIL_STORE_LIST (ptr), 0); - if (BLOCK_FOR_INSN (tmp) != bb) - check_available = 1; - } - if (check_available) - { - /* Check that we have already reached the insn at that the check - failed last time. */ - if (LAST_AVAIL_CHECK_FAILURE (ptr)) - { - for (tmp = BB_END (bb); - tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr); - tmp = PREV_INSN (tmp)) - continue; - if (tmp == insn) - check_available = 0; - } - else - check_available = store_killed_after (dest, ptr->pattern_regs, insn, - bb, regs_set_after, - &LAST_AVAIL_CHECK_FAILURE (ptr)); - } - if (!check_available) - AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr)); -} - -/* Find available and anticipatable stores. */ - -static int -compute_store_table (void) -{ - int ret; - basic_block bb; - unsigned regno; - rtx insn, pat, tmp; - int *last_set_in, *already_set; - struct ls_expr * ptr, **prev_next_ptr_ptr; - - max_gcse_regno = max_reg_num (); - - reg_set_in_block = sbitmap_vector_alloc (last_basic_block, - max_gcse_regno); - sbitmap_vector_zero (reg_set_in_block, last_basic_block); - pre_ldst_mems = 0; - pre_ldst_table = htab_create (13, pre_ldst_expr_hash, - pre_ldst_expr_eq, NULL); - last_set_in = XCNEWVEC (int, max_gcse_regno); - already_set = XNEWVEC (int, max_gcse_regno); - - /* Find all the stores we care about. */ - FOR_EACH_BB (bb) - { - /* First compute the registers set in this block. */ - regvec = last_set_in; - - FOR_BB_INSNS (bb, insn) - { - if (! INSN_P (insn)) - continue; - - if (CALL_P (insn)) - { - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) - { - last_set_in[regno] = INSN_UID (insn); - SET_BIT (reg_set_in_block[bb->index], regno); - } - } - - pat = PATTERN (insn); - compute_store_table_current_insn = insn; - note_stores (pat, reg_set_info, reg_set_in_block[bb->index]); - } - - /* Now find the stores. */ - memset (already_set, 0, sizeof (int) * max_gcse_regno); - regvec = already_set; - FOR_BB_INSNS (bb, insn) - { - if (! INSN_P (insn)) - continue; - - if (CALL_P (insn)) - { - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) - already_set[regno] = 1; - } - - pat = PATTERN (insn); - note_stores (pat, reg_set_info, NULL); - - /* Now that we've marked regs, look for stores. */ - find_moveable_store (insn, already_set, last_set_in); - - /* Unmark regs that are no longer set. */ - compute_store_table_current_insn = insn; - note_stores (pat, reg_clear_last_set, last_set_in); - if (CALL_P (insn)) - { - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno) - && last_set_in[regno] == INSN_UID (insn)) - last_set_in[regno] = 0; - } - } - -#ifdef ENABLE_CHECKING - /* last_set_in should now be all-zero. */ - for (regno = 0; regno < max_gcse_regno; regno++) - gcc_assert (!last_set_in[regno]); -#endif - - /* Clear temporary marks. */ - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) - { - LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX; - if (ANTIC_STORE_LIST (ptr) - && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX) - ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1); - } - } - - /* Remove the stores that are not available anywhere, as there will - be no opportunity to optimize them. */ - for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems; - ptr != NULL; - ptr = *prev_next_ptr_ptr) - { - if (!AVAIL_STORE_LIST (ptr)) - { - *prev_next_ptr_ptr = ptr->next; - htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index); - free_ldst_entry (ptr); - } - else - prev_next_ptr_ptr = &ptr->next; - } - - ret = enumerate_ldsts (); - - if (dump_file) - { - fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n"); - print_ldst_list (dump_file); - } - - free (last_set_in); - free (already_set); - return ret; -} - -/* Check to see if the load X is aliased with STORE_PATTERN. - AFTER is true if we are checking the case when STORE_PATTERN occurs - after the X. */ - -static bool -load_kills_store (const_rtx x, const_rtx store_pattern, int after) -{ - if (after) - return anti_dependence (x, store_pattern); - else - return true_dependence (store_pattern, GET_MODE (store_pattern), x, - rtx_addr_varies_p); -} - -/* Go through the entire insn X, looking for any loads which might alias - STORE_PATTERN. Return true if found. - AFTER is true if we are checking the case when STORE_PATTERN occurs - after the insn X. */ - -static bool -find_loads (const_rtx x, const_rtx store_pattern, int after) -{ - const char * fmt; - int i, j; - int ret = false; - - if (!x) - return false; - - if (GET_CODE (x) == SET) - x = SET_SRC (x); - - if (MEM_P (x)) - { - if (load_kills_store (x, store_pattern, after)) - return true; - } - - /* Recursively process the insn. */ - fmt = GET_RTX_FORMAT (GET_CODE (x)); - - for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--) - { - if (fmt[i] == 'e') - ret |= find_loads (XEXP (x, i), store_pattern, after); - else if (fmt[i] == 'E') - for (j = XVECLEN (x, i) - 1; j >= 0; j--) - ret |= find_loads (XVECEXP (x, i, j), store_pattern, after); - } - return ret; -} - -static inline bool -store_killed_in_pat (const_rtx x, const_rtx pat, int after) -{ - if (GET_CODE (pat) == SET) - { - rtx dest = SET_DEST (pat); - - if (GET_CODE (dest) == ZERO_EXTRACT) - dest = XEXP (dest, 0); - - /* Check for memory stores to aliased objects. */ - if (MEM_P (dest) - && !expr_equiv_p (dest, x)) - { - if (after) - { - if (output_dependence (dest, x)) - return true; - } - else - { - if (output_dependence (x, dest)) - return true; - } - } - } - - if (find_loads (pat, x, after)) - return true; - - return false; -} - -/* Check if INSN kills the store pattern X (is aliased with it). - AFTER is true if we are checking the case when store X occurs - after the insn. Return true if it does. */ - -static bool -store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after) -{ - const_rtx reg, base, note, pat; - - if (!INSN_P (insn)) - return false; - - if (CALL_P (insn)) - { - /* A normal or pure call might read from pattern, - but a const call will not. */ - if (! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn)) - return true; - - /* But even a const call reads its parameters. Check whether the - base of some of registers used in mem is stack pointer. */ - for (reg = x_regs; reg; reg = XEXP (reg, 1)) - { - base = find_base_term (XEXP (reg, 0)); - if (!base - || (GET_CODE (base) == ADDRESS - && GET_MODE (base) == Pmode - && XEXP (base, 0) == stack_pointer_rtx)) - return true; - } - - return false; - } - - pat = PATTERN (insn); - if (GET_CODE (pat) == SET) - { - if (store_killed_in_pat (x, pat, after)) - return true; - } - else if (GET_CODE (pat) == PARALLEL) - { - int i; - - for (i = 0; i < XVECLEN (pat, 0); i++) - if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after)) - return true; - } - else if (find_loads (PATTERN (insn), x, after)) - return true; - - /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory - location aliased with X, then this insn kills X. */ - note = find_reg_equal_equiv_note (insn); - if (! note) - return false; - note = XEXP (note, 0); - - /* However, if the note represents a must alias rather than a may - alias relationship, then it does not kill X. */ - if (expr_equiv_p (note, x)) - return false; - - /* See if there are any aliased loads in the note. */ - return find_loads (note, x, after); -} - -/* Returns true if the expression X is loaded or clobbered on or after INSN - within basic block BB. REGS_SET_AFTER is bitmap of registers set in - or after the insn. X_REGS is list of registers mentioned in X. If the store - is killed, return the last insn in that it occurs in FAIL_INSN. */ - -static bool -store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb, - int *regs_set_after, rtx *fail_insn) -{ - rtx last = BB_END (bb), act; - - if (!store_ops_ok (x_regs, regs_set_after)) - { - /* We do not know where it will happen. */ - if (fail_insn) - *fail_insn = NULL_RTX; - return true; - } - - /* Scan from the end, so that fail_insn is determined correctly. */ - for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act)) - if (store_killed_in_insn (x, x_regs, act, false)) - { - if (fail_insn) - *fail_insn = act; - return true; - } - - return false; -} - -/* Returns true if the expression X is loaded or clobbered on or before INSN - within basic block BB. X_REGS is list of registers mentioned in X. - REGS_SET_BEFORE is bitmap of registers set before or in this insn. */ -static bool -store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb, - int *regs_set_before) -{ - rtx first = BB_HEAD (bb); - - if (!store_ops_ok (x_regs, regs_set_before)) - return true; - - for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn)) - if (store_killed_in_insn (x, x_regs, insn, true)) - return true; - - return false; -} - -/* Fill in available, anticipatable, transparent and kill vectors in - STORE_DATA, based on lists of available and anticipatable stores. */ -static void -build_store_vectors (void) -{ - basic_block bb; - int *regs_set_in_block; - rtx insn, st; - struct ls_expr * ptr; - unsigned regno; - - /* Build the gen_vector. This is any store in the table which is not killed - by aliasing later in its block. */ - ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores); - sbitmap_vector_zero (ae_gen, last_basic_block); - - st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores); - sbitmap_vector_zero (st_antloc, last_basic_block); - - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) - { - for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1)) - { - insn = XEXP (st, 0); - bb = BLOCK_FOR_INSN (insn); - - /* If we've already seen an available expression in this block, - we can delete this one (It occurs earlier in the block). We'll - copy the SRC expression to an unused register in case there - are any side effects. */ - if (TEST_BIT (ae_gen[bb->index], ptr->index)) - { - rtx r = gen_reg_rtx (GET_MODE (ptr->pattern)); - if (dump_file) - fprintf (dump_file, "Removing redundant store:\n"); - replace_store_insn (r, XEXP (st, 0), bb, ptr); - continue; - } - SET_BIT (ae_gen[bb->index], ptr->index); - } - - for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1)) - { - insn = XEXP (st, 0); - bb = BLOCK_FOR_INSN (insn); - SET_BIT (st_antloc[bb->index], ptr->index); - } - } - - ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores); - sbitmap_vector_zero (ae_kill, last_basic_block); - - transp = sbitmap_vector_alloc (last_basic_block, num_stores); - sbitmap_vector_zero (transp, last_basic_block); - regs_set_in_block = XNEWVEC (int, max_gcse_regno); - - FOR_EACH_BB (bb) - { - for (regno = 0; regno < max_gcse_regno; regno++) - regs_set_in_block[regno] = TEST_BIT (reg_set_in_block[bb->index], regno); - - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) - { - if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb), - bb, regs_set_in_block, NULL)) - { - /* It should not be necessary to consider the expression - killed if it is both anticipatable and available. */ - if (!TEST_BIT (st_antloc[bb->index], ptr->index) - || !TEST_BIT (ae_gen[bb->index], ptr->index)) - SET_BIT (ae_kill[bb->index], ptr->index); - } - else - SET_BIT (transp[bb->index], ptr->index); - } - } - - free (regs_set_in_block); - - if (dump_file) - { - dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); - dump_sbitmap_vector (dump_file, "st_kill", "", ae_kill, last_basic_block); - dump_sbitmap_vector (dump_file, "Transpt", "", transp, last_basic_block); - dump_sbitmap_vector (dump_file, "st_avloc", "", ae_gen, last_basic_block); - } -} - -/* Insert an instruction at the beginning of a basic block, and update - the BB_HEAD if needed. */ - -static void -insert_insn_start_basic_block (rtx insn, basic_block bb) -{ - /* Insert at start of successor block. */ - rtx prev = PREV_INSN (BB_HEAD (bb)); - rtx before = BB_HEAD (bb); - while (before != 0) - { - if (! LABEL_P (before) - && !NOTE_INSN_BASIC_BLOCK_P (before)) - break; - prev = before; - if (prev == BB_END (bb)) - break; - before = NEXT_INSN (before); - } - - insn = emit_insn_after_noloc (insn, prev, bb); - - if (dump_file) - { - fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n", - bb->index); - print_inline_rtx (dump_file, insn, 6); - fprintf (dump_file, "\n"); - } -} - -/* This routine will insert a store on an edge. EXPR is the ldst entry for - the memory reference, and E is the edge to insert it on. Returns nonzero - if an edge insertion was performed. */ - -static int -insert_store (struct ls_expr * expr, edge e) -{ - rtx reg, insn; - basic_block bb; - edge tmp; - edge_iterator ei; - - /* We did all the deleted before this insert, so if we didn't delete a - store, then we haven't set the reaching reg yet either. */ - if (expr->reaching_reg == NULL_RTX) - return 0; - - if (e->flags & EDGE_FAKE) - return 0; - - reg = expr->reaching_reg; - insn = gen_move_insn (copy_rtx (expr->pattern), reg); - - /* If we are inserting this expression on ALL predecessor edges of a BB, - insert it at the start of the BB, and reset the insert bits on the other - edges so we don't try to insert it on the other edges. */ - bb = e->dest; - FOR_EACH_EDGE (tmp, ei, e->dest->preds) - if (!(tmp->flags & EDGE_FAKE)) - { - int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); - - gcc_assert (index != EDGE_INDEX_NO_EDGE); - if (! TEST_BIT (pre_insert_map[index], expr->index)) - break; - } - - /* If tmp is NULL, we found an insertion on every edge, blank the - insertion vector for these edges, and insert at the start of the BB. */ - if (!tmp && bb != EXIT_BLOCK_PTR) - { - FOR_EACH_EDGE (tmp, ei, e->dest->preds) - { - int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); - RESET_BIT (pre_insert_map[index], expr->index); - } - insert_insn_start_basic_block (insn, bb); - return 0; - } - - /* We can't put stores in the front of blocks pointed to by abnormal - edges since that may put a store where one didn't used to be. */ - gcc_assert (!(e->flags & EDGE_ABNORMAL)); - - insert_insn_on_edge (insn, e); - - if (dump_file) - { - fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n", - e->src->index, e->dest->index); - print_inline_rtx (dump_file, insn, 6); - fprintf (dump_file, "\n"); - } - - return 1; -} - -/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the - memory location in SMEXPR set in basic block BB. - - This could be rather expensive. */ - -static void -remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr) -{ - edge_iterator *stack, ei; - int sp; - edge act; - sbitmap visited = sbitmap_alloc (last_basic_block); - rtx last, insn, note; - rtx mem = smexpr->pattern; - - stack = XNEWVEC (edge_iterator, n_basic_blocks); - sp = 0; - ei = ei_start (bb->succs); - - sbitmap_zero (visited); - - act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL); - while (1) - { - if (!act) - { - if (!sp) - { - free (stack); - sbitmap_free (visited); - return; - } - act = ei_edge (stack[--sp]); - } - bb = act->dest; - - if (bb == EXIT_BLOCK_PTR - || TEST_BIT (visited, bb->index)) - { - if (!ei_end_p (ei)) - ei_next (&ei); - act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL; - continue; - } - SET_BIT (visited, bb->index); - - if (TEST_BIT (st_antloc[bb->index], smexpr->index)) - { - for (last = ANTIC_STORE_LIST (smexpr); - BLOCK_FOR_INSN (XEXP (last, 0)) != bb; - last = XEXP (last, 1)) - continue; - last = XEXP (last, 0); - } - else - last = NEXT_INSN (BB_END (bb)); - - for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn)) - if (INSN_P (insn)) - { - note = find_reg_equal_equiv_note (insn); - if (!note || !expr_equiv_p (XEXP (note, 0), mem)) - continue; - - if (dump_file) - fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", - INSN_UID (insn)); - remove_note (insn, note); - } - - if (!ei_end_p (ei)) - ei_next (&ei); - act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL; - - if (EDGE_COUNT (bb->succs) > 0) - { - if (act) - stack[sp++] = ei; - ei = ei_start (bb->succs); - act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL); - } - } -} - -/* This routine will replace a store with a SET to a specified register. */ - -static void -replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr) -{ - rtx insn, mem, note, set, ptr, pair; - - mem = smexpr->pattern; - insn = gen_move_insn (reg, SET_SRC (single_set (del))); - - for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1)) - if (XEXP (ptr, 0) == del) - { - XEXP (ptr, 0) = insn; - break; - } - - /* Move the notes from the deleted insn to its replacement, and patch - up the LIBCALL notes. */ - REG_NOTES (insn) = REG_NOTES (del); - - note = find_reg_note (insn, REG_RETVAL, NULL_RTX); - if (note) - { - pair = XEXP (note, 0); - note = find_reg_note (pair, REG_LIBCALL, NULL_RTX); - XEXP (note, 0) = insn; - } - note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); - if (note) - { - pair = XEXP (note, 0); - note = find_reg_note (pair, REG_RETVAL, NULL_RTX); - XEXP (note, 0) = insn; - } - - /* Emit the insn AFTER all the notes are transferred. - This is cheaper since we avoid df rescanning for the note change. */ - insn = emit_insn_after (insn, del); - - if (dump_file) - { - fprintf (dump_file, - "STORE_MOTION delete insn in BB %d:\n ", bb->index); - print_inline_rtx (dump_file, del, 6); - fprintf (dump_file, "\nSTORE MOTION replaced with insn:\n "); - print_inline_rtx (dump_file, insn, 6); - fprintf (dump_file, "\n"); - } - - delete_insn (del); - - /* Now we must handle REG_EQUAL notes whose contents is equal to the mem; - they are no longer accurate provided that they are reached by this - definition, so drop them. */ - for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn)) - if (INSN_P (insn)) - { - set = single_set (insn); - if (!set) - continue; - if (expr_equiv_p (SET_DEST (set), mem)) - return; - note = find_reg_equal_equiv_note (insn); - if (!note || !expr_equiv_p (XEXP (note, 0), mem)) - continue; - - if (dump_file) - fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", - INSN_UID (insn)); - remove_note (insn, note); - } - remove_reachable_equiv_notes (bb, smexpr); -} - - -/* Delete a store, but copy the value that would have been stored into - the reaching_reg for later storing. */ - -static void -delete_store (struct ls_expr * expr, basic_block bb) +static bool +gate_rtl_cprop (void) { - rtx reg, i, del; - - if (expr->reaching_reg == NULL_RTX) - expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern)); - - reg = expr->reaching_reg; - - for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1)) - { - del = XEXP (i, 0); - if (BLOCK_FOR_INSN (del) == bb) - { - /* We know there is only one since we deleted redundant - ones during the available computation. */ - replace_store_insn (reg, del, bb, expr); - break; - } - } + return optimize > 0 && flag_gcse + && !cfun->calls_setjmp + && dbg_cnt (cprop); } -/* Free memory used by store motion. */ - -static void -free_store_memory (void) +static unsigned int +execute_rtl_cprop (void) { - free_ldst_mems (); - - if (ae_gen) - sbitmap_vector_free (ae_gen); - if (ae_kill) - sbitmap_vector_free (ae_kill); - if (transp) - sbitmap_vector_free (transp); - if (st_antloc) - sbitmap_vector_free (st_antloc); - if (pre_insert_map) - sbitmap_vector_free (pre_insert_map); - if (pre_delete_map) - sbitmap_vector_free (pre_delete_map); - if (reg_set_in_block) - sbitmap_vector_free (reg_set_in_block); - - ae_gen = ae_kill = transp = st_antloc = NULL; - pre_insert_map = pre_delete_map = reg_set_in_block = NULL; + delete_unreachable_blocks (); + df_note_add_problem (); + df_set_flags (DF_LR_RUN_DCE); + df_analyze (); + flag_rerun_cse_after_global_opts |= one_cprop_pass (); + return 0; } -/* Perform store motion. Much like gcse, except we move expressions the - other way by looking at the flowgraph in reverse. */ - -static void -store_motion (void) +static bool +gate_rtl_pre (void) { - basic_block bb; - int x; - struct ls_expr * ptr; - int update_flow = 0; - - if (dump_file) - { - fprintf (dump_file, "before store motion\n"); - print_rtl (dump_file, get_insns ()); - } - - init_alias_analysis (); - - /* Find all the available and anticipatable stores. */ - num_stores = compute_store_table (); - if (num_stores == 0) - { - htab_delete (pre_ldst_table); - pre_ldst_table = NULL; - sbitmap_vector_free (reg_set_in_block); - end_alias_analysis (); - return; - } - - /* Now compute kill & transp vectors. */ - build_store_vectors (); - add_noreturn_fake_exit_edges (); - connect_infinite_loops_to_exit (); - - edge_list = pre_edge_rev_lcm (num_stores, transp, ae_gen, - st_antloc, ae_kill, &pre_insert_map, - &pre_delete_map); - - /* Now we want to insert the new stores which are going to be needed. */ - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) - { - /* If any of the edges we have above are abnormal, we can't move this - store. */ - for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--) - if (TEST_BIT (pre_insert_map[x], ptr->index) - && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL)) - break; - - if (x >= 0) - { - if (dump_file != NULL) - fprintf (dump_file, - "Can't replace store %d: abnormal edge from %d to %d\n", - ptr->index, INDEX_EDGE (edge_list, x)->src->index, - INDEX_EDGE (edge_list, x)->dest->index); - continue; - } - - /* Now we want to insert the new stores which are going to be needed. */ - - FOR_EACH_BB (bb) - if (TEST_BIT (pre_delete_map[bb->index], ptr->index)) - delete_store (ptr, bb); - - for (x = 0; x < NUM_EDGES (edge_list); x++) - if (TEST_BIT (pre_insert_map[x], ptr->index)) - update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x)); - } - - if (update_flow) - commit_edge_insertions (); - - free_store_memory (); - free_edge_list (edge_list); - remove_fake_exit_edges (); - end_alias_analysis (); + return optimize > 0 && flag_gcse + && !cfun->calls_setjmp + && optimize_function_for_speed_p (cfun) + && dbg_cnt (pre); } - -/* Entry point for jump bypassing optimization pass. */ - -static int -bypass_jumps (void) +static unsigned int +execute_rtl_pre (void) { - int changed; - - /* We do not construct an accurate cfg in functions which call - setjmp, so just punt to be safe. */ - if (current_function_calls_setjmp) - return 0; - - /* Identify the basic block information for this function, including - successors and predecessors. */ - max_gcse_regno = max_reg_num (); - - if (dump_file) - dump_flow_info (dump_file, dump_flags); - - /* Return if there's nothing to do, or it is too expensive. */ - if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 - || is_too_expensive (_ ("jump bypassing disabled"))) - return 0; - - gcc_obstack_init (&gcse_obstack); - bytes_used = 0; - - /* We need alias. */ - init_alias_analysis (); - - /* 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. - - 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 (); - - max_gcse_regno = max_reg_num (); - alloc_gcse_mem (); - changed = one_cprop_pass (MAX_GCSE_PASSES + 2, true, true); - free_gcse_mem (); - - if (dump_file) - { - fprintf (dump_file, "BYPASS of %s: %d basic blocks, ", - current_function_name (), n_basic_blocks); - fprintf (dump_file, "%d bytes\n\n", bytes_used); - } - - obstack_free (&gcse_obstack, NULL); - free_reg_set_mem (); - - /* We are finished with alias. */ - end_alias_analysis (); - - return changed; + delete_unreachable_blocks (); + df_note_add_problem (); + df_analyze (); + flag_rerun_cse_after_global_opts |= one_pre_gcse_pass (); + return 0; } -/* Return true if the graph is too expensive to optimize. PASS is the - optimization about to be performed. */ - -static bool -is_too_expensive (const char *pass) -{ - /* 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 as many - edges as blocks. But we do not want to punish small functions - which have a couple switch statements. Rather than simply - threshold the number of blocks, uses something with a more - graceful degradation. */ - if (n_edges > 20000 + n_basic_blocks * 4) - { - warning (OPT_Wdisabled_optimization, - "%s: %d basic blocks and %d edges/basic block", - pass, n_basic_blocks, n_edges / n_basic_blocks); - - return true; - } - - /* If allocating memory for the cprop bitmap would take up too much - storage it's better just to disable the optimization. */ - if ((n_basic_blocks - * SBITMAP_SET_SIZE (max_reg_num ()) - * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) - { - warning (OPT_Wdisabled_optimization, - "%s: %d basic blocks and %d registers", - pass, n_basic_blocks, max_reg_num ()); - - return true; - } - - return false; -} - static bool -gate_handle_jump_bypass (void) +gate_rtl_hoist (void) { - return optimize > 0 && flag_gcse; + return optimize > 0 && flag_gcse + && !cfun->calls_setjmp + /* It does not make sense to run code hoisting unless we are optimizing + for code size -- it rarely makes programs faster, and can make then + bigger if we did PRE (when optimizing for space, we don't run PRE). */ + && optimize_function_for_size_p (cfun) + && dbg_cnt (hoist); } -/* Perform jump bypassing and control flow optimizations. */ static unsigned int -rest_of_handle_jump_bypass (void) +execute_rtl_hoist (void) { delete_unreachable_blocks (); - if (bypass_jumps ()) - { - delete_trivially_dead_insns (get_insns (), max_reg_num ()); - rebuild_jump_labels (get_insns ()); - cleanup_cfg (0); - } + df_note_add_problem (); + df_analyze (); + flag_rerun_cse_after_global_opts |= one_code_hoisting_pass (); return 0; } -struct tree_opt_pass pass_jump_bypass = +struct rtl_opt_pass pass_rtl_cprop = { - "bypass", /* name */ - gate_handle_jump_bypass, /* gate */ - rest_of_handle_jump_bypass, /* execute */ + { + RTL_PASS, + "cprop", /* name */ + gate_rtl_cprop, /* gate */ + execute_rtl_cprop, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - TV_BYPASS, /* tv_id */ - 0, /* properties_required */ + TV_CPROP, /* tv_id */ + PROP_cfglayout, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ + TODO_df_finish | TODO_verify_rtl_sharing | TODO_dump_func | - TODO_ggc_collect | TODO_verify_flow, /* todo_flags_finish */ - 'G' /* letter */ + TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ + } }; - -static bool -gate_handle_gcse (void) -{ - return optimize > 0 && flag_gcse; -} - - -static unsigned int -rest_of_handle_gcse (void) +struct rtl_opt_pass pass_rtl_pre = { - int save_csb, save_cfj; - int tem2 = 0, tem; - tem = gcse_main (get_insns ()); - delete_trivially_dead_insns (get_insns (), max_reg_num ()); - rebuild_jump_labels (get_insns ()); - save_csb = flag_cse_skip_blocks; - save_cfj = flag_cse_follow_jumps; - flag_cse_skip_blocks = flag_cse_follow_jumps = 0; - - /* If -fexpensive-optimizations, re-run CSE to clean up things done - by gcse. */ - if (flag_expensive_optimizations) - { - timevar_push (TV_CSE); - tem2 = cse_main (get_insns (), max_reg_num ()); - df_finish_pass (false); - purge_all_dead_edges (); - delete_trivially_dead_insns (get_insns (), max_reg_num ()); - timevar_pop (TV_CSE); - cse_not_expected = !flag_rerun_cse_after_loop; - } - - /* If gcse or cse altered any jumps, rerun jump optimizations to clean - things up. */ - if (tem || tem2) - { - timevar_push (TV_JUMP); - rebuild_jump_labels (get_insns ()); - cleanup_cfg (0); - timevar_pop (TV_JUMP); - } - - flag_cse_skip_blocks = save_csb; - flag_cse_follow_jumps = save_cfj; - return 0; -} + { + RTL_PASS, + "pre", /* name */ + gate_rtl_pre, /* gate */ + execute_rtl_pre, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_PRE, /* tv_id */ + PROP_cfglayout, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_df_finish | TODO_verify_rtl_sharing | + TODO_dump_func | + TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ + } +}; -struct tree_opt_pass pass_gcse = +struct rtl_opt_pass pass_rtl_hoist = { - "gcse1", /* name */ - gate_handle_gcse, /* gate */ - rest_of_handle_gcse, /* execute */ + { + RTL_PASS, + "hoist", /* name */ + gate_rtl_hoist, /* gate */ + execute_rtl_hoist, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - TV_GCSE, /* tv_id */ - 0, /* properties_required */ + TV_HOIST, /* tv_id */ + PROP_cfglayout, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_df_finish | TODO_verify_rtl_sharing | TODO_dump_func | - TODO_verify_flow | TODO_ggc_collect, /* todo_flags_finish */ - 'G' /* letter */ + TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ + } }; - #include "gt-gcse.h"