X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgcse.c;h=ee2d31e0a42df54a0c6288a95318debe8ceb55a6;hb=77fa068f2e71f42bc5b3bd797ad672af8ebc90eb;hp=67f8053e9c811167dc487ff3daf58cc121bff0c6;hpb=476d094d7713bdd77be9c7863518b69342c7a4b4;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/gcse.c b/gcc/gcse.c index 67f8053e9c8..ee2d31e0a42 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -1,13 +1,13 @@ /* 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 - Free Software Foundation, Inc. + Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, + 2006, 2007, 2008 Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -16,9 +16,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ /* TODO - reordering of memory allocation and freeing to be more space efficient @@ -169,6 +168,10 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "intl.h" #include "obstack.h" #include "timevar.h" +#include "tree-pass.h" +#include "hashtab.h" +#include "df.h" +#include "dbgcnt.h" /* Propagate flow information through back edges and thus enable PRE's moving loop invariant calculations out of loops. @@ -264,25 +267,11 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA the result of the expression is copied to a new register, and the redundant expression is deleted by replacing it with this new register. Classic GCSE doesn't have this problem as much as it computes the reaching defs of - each register in each block and thus can try to use an existing register. - - ********************** - - A fair bit of simplicity is created by creating small functions for simple - tasks, even when the function is only called in one place. This may - measurably slow things down [or may not] by creating more function call - overhead than is necessary. The source is laid out so that it's trivial - to make the affected functions inline so that one can measure what speed - up, if any, can be achieved, and maybe later when things settle things can - be rearranged. - - Help stamp out big monolithic functions! */ + each register in each block and thus can try to use an existing + register. */ /* GCSE global vars. */ -/* -dG dump file. */ -static FILE *gcse_file; - /* Note whether or not we should run jump optimization after gcse. We want to do this for two cases. @@ -291,13 +280,6 @@ static FILE *gcse_file; * If we added any labels via edge splitting. */ static int run_jump_opt_after_gcse; -/* Bitmaps are normally not included in debugging dumps. - However it's useful to be able to print them from GDB. - We could create special functions for this, but it's simpler to - just allow passing stderr to the dump_foo fns. Since stderr can - be a macro, we store a copy here. */ -static FILE *debug_stderr; - /* An obstack for our working variables. */ static struct obstack gcse_obstack; @@ -398,12 +380,6 @@ static int max_uid; /* 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. */ @@ -436,8 +412,8 @@ typedef struct reg_set { /* The next setting of this register. */ struct reg_set *next; - /* The insn where it was set. */ - rtx insn; + /* The index of the block where it was set. */ + int bb_index; } reg_set; static reg_set **reg_set_table; @@ -481,6 +457,9 @@ static rtx *implicit_sets; /* Head of the list of load/store memory refs. */ static struct ls_expr * pre_ldst_mems = NULL; +/* Hashtable for the load/store memory refs. */ +static htab_t pre_ldst_table = NULL; + /* Bitmap containing one bit for each register in the program. Used when performing GCSE to track which registers have been set since the start of the basic block. */ @@ -500,7 +479,10 @@ static bitmap modify_mem_list_set; /* This array parallels modify_mem_list, but is kept canonicalized. */ static rtx * canon_modify_mem_list; -static bitmap canon_modify_mem_list_set; + +/* Bitmap indexed by block numbers to record which blocks contain + function calls. */ +static bitmap blocks_with_calls; /* Various variables for statistics gathering. */ @@ -515,62 +497,47 @@ static int gcse_subst_count; static int gcse_create_count; /* Number of local constants propagated. */ static int local_const_prop_count; -/* Number of local copys propagated. */ +/* Number of local copies propagated. */ static int local_copy_prop_count; /* Number of global constants propagated. */ static int global_const_prop_count; -/* Number of global copys propagated. */ +/* Number of global copies propagated. */ static int global_copy_prop_count; /* For available exprs */ static sbitmap *ae_kill, *ae_gen; - -/* Objects of this type are passed around by the null-pointer check - removal routines. */ -struct null_pointer_info -{ - /* The basic block being processed. */ - basic_block current_block; - /* The first register to be handled in this pass. */ - unsigned int min_reg; - /* One greater than the last register to be handled in this pass. */ - unsigned int max_reg; - sbitmap *nonnull_local; - sbitmap *nonnull_killed; -}; 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 (rtx); +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 replace_one_set (int, rtx, rtx); -static void record_set_info (rtx, rtx, void *); -static void compute_sets (rtx); -static void hash_scan_insn (rtx, struct hash_table *, int); +static void record_set_info (rtx, const_rtx, void *); +static void compute_sets (void); +static void hash_scan_insn (rtx, struct hash_table *); 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 int want_to_gcse_p (rtx); static bool can_assign_to_reg_p (rtx); -static bool gcse_constant_p (rtx); -static int oprs_unchanged_p (rtx, rtx, int); -static int oprs_anticipatable_p (rtx, rtx); -static int oprs_available_p (rtx, 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 *); -static unsigned int hash_expr (rtx, enum machine_mode, int *, int); +static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int); static unsigned int hash_set (int, int); -static int expr_equiv_p (rtx, rtx); +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, rtx, void *); +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 *); @@ -579,14 +546,14 @@ static void dump_hash_table (FILE *, const char *, struct hash_table *); static struct expr *lookup_set (unsigned int, struct hash_table *); static struct expr *next_set (unsigned int, struct expr *); static void reset_opr_set_tables (void); -static int oprs_not_set_p (rtx, rtx); +static int oprs_not_set_p (const_rtx, const_rtx); static void mark_call (rtx); static void mark_set (rtx, rtx); static void mark_clobber (rtx, rtx); static void mark_oprs_set (rtx); static void alloc_cprop_mem (int, int); static void free_cprop_mem (void); -static void compute_transp (rtx, int, sbitmap *, int); +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 *); @@ -595,16 +562,16 @@ static void find_used_regs (rtx *, void *); static int try_replace_reg (rtx, rtx, rtx); static struct expr *find_avail_set (int, rtx); static int cprop_jump (basic_block, rtx, rtx, rtx, rtx); -static void mems_conflict_for_gcse_p (rtx, rtx, void *); -static int load_killed_in_block_p (basic_block, int, rtx, int); -static void canon_list_insert (rtx, rtx, void *); +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 void find_implicit_sets (void); -static int one_cprop_pass (int, int, int); -static bool constprop_register (rtx, rtx, rtx, int); +static int one_cprop_pass (int, bool, bool); +static bool constprop_register (rtx, rtx, rtx, bool); static struct expr *find_bypass_set (int, int); -static bool reg_killed_on_edge (rtx, edge); +static bool reg_killed_on_edge (const_rtx, const_edge); static int bypass_block (basic_block, rtx, rtx); static int bypass_conditional_jumps (void); static void alloc_pre_mem (int, int); @@ -612,7 +579,7 @@ static void free_pre_mem (void); static void compute_pre_data (void); static int pre_expr_reaches_here_p (basic_block, struct expr *, basic_block); -static void insert_insn_end_bb (struct expr *, basic_block, int); +static void insert_insn_end_basic_block (struct expr *, basic_block, int); static void pre_insert_copy_insn (struct expr *, rtx); static void pre_insert_copies (void); static int pre_delete (void); @@ -638,25 +605,25 @@ 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 (rtx); +static int simple_mem (const_rtx); 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, rtx, void *); -static void reg_clear_last_set (rtx, rtx, void *); -static bool store_ops_ok (rtx, int *); +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 (rtx, rtx, int); -static bool find_loads (rtx, rtx, int); -static bool store_killed_in_insn (rtx, rtx, rtx, int); -static bool store_killed_after (rtx, rtx, rtx, basic_block, int *, rtx *); -static bool store_killed_before (rtx, rtx, rtx, basic_block, int *); +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_bb (rtx, basic_block); +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 *); @@ -668,18 +635,31 @@ 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, int, rtx*); -static bool adjust_libcall_notes (rtx, rtx, rtx, rtx*); -static void local_cprop_pass (int); +static bool do_local_cprop (rtx, rtx, bool); +static void local_cprop_pass (bool); static bool is_too_expensive (const char *); + +#define GNEW(T) ((T *) gmalloc (sizeof (T))) +#define GCNEW(T) ((T *) gcalloc (1, sizeof (T))) + +#define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N))) +#define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T))) +#define GRESIZEVEC(T, P, N) ((T *) grealloc ((void *) (P), sizeof (T) * (N))) + +#define GNEWVAR(T, S) ((T *) gmalloc ((S))) +#define GCNEWVAR(T, S) ((T *) gcalloc (1, (S))) +#define GRESIZEVAR(T, P, S) ((T *) grealloc ((P), (S))) + +#define GOBNEW(T) ((T *) gcse_alloc (sizeof (T))) +#define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S))) /* Entry point for global common subexpression elimination. F is the first instruction in the function. Return nonzero if a change is mode. */ -int -gcse_main (rtx f, FILE *file) +static int +gcse_main (rtx f ATTRIBUTE_UNUSED) { int changed, pass; /* Bytes used at start of pass. */ @@ -691,25 +671,25 @@ gcse_main (rtx f, FILE *file) /* We do not construct an accurate cfg in functions which call setjmp, so just punt to be safe. */ - if (current_function_calls_setjmp) + if (cfun->calls_setjmp) return 0; /* Assume that we do not need to run jump optimizations after gcse. */ run_jump_opt_after_gcse = 0; - /* For calling dump_foo fns from gdb. */ - debug_stderr = stderr; - gcse_file = file; - /* Identify the basic block information for this function, including successors and predecessors. */ max_gcse_regno = max_reg_num (); - if (file) - dump_flow_info (file); + 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 <= 1 || is_too_expensive (_("GCSE disabled"))) + if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 + || is_too_expensive (_("GCSE disabled"))) return 0; gcc_obstack_init (&gcse_obstack); @@ -727,18 +707,18 @@ gcse_main (rtx f, FILE *file) information about memory sets when we build the hash tables. */ alloc_reg_set_mem (max_gcse_regno); - compute_sets (f); + compute_sets (); pass = 0; initial_bytes_used = bytes_used; max_pass_bytes = 0; - gcse_obstack_bottom = gcse_alloc (1); + gcse_obstack_bottom = GOBNEWVAR (char, 1); changed = 1; while (changed && pass < MAX_GCSE_PASSES) { changed = 0; - if (file) - fprintf (file, "GCSE pass %d\n\n", pass + 1); + 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. */ @@ -747,17 +727,18 @@ gcse_main (rtx f, FILE *file) /* Each pass may create new registers, so recalculate each time. */ max_gcse_regno = max_reg_num (); - alloc_gcse_mem (f); + alloc_gcse_mem (); /* Don't allow constant propagation to modify jumps during this pass. */ - timevar_push (TV_CPROP1); - changed = one_cprop_pass (pass + 1, 0, 0); - timevar_pop (TV_CPROP1); + if (dbg_cnt (cprop1)) + { + timevar_push (TV_CPROP1); + changed = one_cprop_pass (pass + 1, false, false); + timevar_pop (TV_CPROP1); + } - if (optimize_size) - /* Do nothing. */ ; - else + if (optimize_function_for_speed_p (cfun)) { timevar_push (TV_PRE); changed |= one_pre_gcse_pass (pass + 1); @@ -767,12 +748,12 @@ gcse_main (rtx f, FILE *file) 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)); + modify_mem_list = GCNEWVEC (rtx, last_basic_block); + canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block); } free_reg_set_mem (); alloc_reg_set_mem (max_reg_num ()); - compute_sets (f); + compute_sets (); run_jump_opt_after_gcse = 1; timevar_pop (TV_PRE); } @@ -790,11 +771,11 @@ gcse_main (rtx f, FILE *file) 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) + if (optimize_function_for_size_p (cfun)) { timevar_push (TV_HOIST); max_gcse_regno = max_reg_num (); - alloc_gcse_mem (f); + alloc_gcse_mem (); changed |= one_code_hoisting_pass (); free_gcse_mem (); @@ -803,10 +784,10 @@ gcse_main (rtx f, FILE *file) timevar_pop (TV_HOIST); } - if (file) + if (dump_file) { - fprintf (file, "\n"); - fflush (file); + fprintf (dump_file, "\n"); + fflush (dump_file); } obstack_free (&gcse_obstack, gcse_obstack_bottom); @@ -816,19 +797,23 @@ gcse_main (rtx f, FILE *file) /* Do one last pass of copy propagation, including cprop into conditional jumps. */ - max_gcse_regno = max_reg_num (); - alloc_gcse_mem (f); - /* This time, go ahead and allow cprop to alter jumps. */ - timevar_push (TV_CPROP2); - one_cprop_pass (pass + 1, 1, 0); - timevar_pop (TV_CPROP2); - free_gcse_mem (); + if (dbg_cnt (cprop2)) + { + max_gcse_regno = max_reg_num (); + alloc_gcse_mem (); - if (file) + /* 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 (file, "GCSE of %s: %d basic blocks, ", + fprintf (dump_file, "GCSE of %s: %d basic blocks, ", current_function_name (), n_basic_blocks); - fprintf (file, "%d pass%s, %d bytes\n\n", + fprintf (dump_file, "%d pass%s, %d bytes\n\n", pass, pass > 1 ? "es" : "", max_pass_bytes); } @@ -837,9 +822,8 @@ gcse_main (rtx f, FILE *file) /* We are finished with alias. */ end_alias_analysis (); - allocate_reg_info (max_reg_num (), FALSE, FALSE); - if (!optimize_size && flag_gcse_sm) + if (optimize_function_for_speed_p (cfun) && flag_gcse_sm) { timevar_push (TV_LSM); store_motion (); @@ -946,44 +930,43 @@ gcse_alloc (unsigned long size) This is called at the start of each pass. */ static void -alloc_gcse_mem (rtx f) +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. */ + 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)); - for (insn = f, i = 0; insn; insn = NEXT_INSN (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. */ + uid_cuid = GCNEWVEC (int, max_uid + 1); + 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; + } max_cuid = i; - cuid_insn = gcalloc (max_cuid + 1, sizeof (rtx)); - for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) - if (INSN_P (insn)) - CUID_INSN (i++) = insn; /* Allocate vars to track sets of regs. */ - reg_set_bitmap = BITMAP_XMALLOC (); + 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_set = BITMAP_XMALLOC (); - canon_modify_mem_list_set = BITMAP_XMALLOC (); + 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); } /* Free memory allocated by alloc_gcse_mem. */ @@ -992,14 +975,13 @@ static void free_gcse_mem (void) { free (uid_cuid); - free (cuid_insn); - BITMAP_XFREE (reg_set_bitmap); + BITMAP_FREE (reg_set_bitmap); sbitmap_vector_free (reg_set_in_block); free_modify_mem_tables (); - BITMAP_XFREE (modify_mem_list_set); - BITMAP_XFREE (canon_modify_mem_list_set); + BITMAP_FREE (modify_mem_list_set); + BITMAP_FREE (blocks_with_calls); } /* Compute the local properties of each recorded expression. @@ -1106,7 +1088,7 @@ 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 *)); + reg_set_table = GCNEWVEC (struct reg_set *, reg_set_table_size); gcc_obstack_init (®_set_obstack); } @@ -1118,24 +1100,6 @@ free_reg_set_mem (void) obstack_free (®_set_obstack, NULL); } -/* An OLD_INSN that used to set REGNO was replaced by NEW_INSN. - Update the corresponding `reg_set_table' entry accordingly. - We assume that NEW_INSN is not already recorded in reg_set_table[regno]. */ - -static void -replace_one_set (int regno, rtx old_insn, rtx new_insn) -{ - struct reg_set *reg_info; - if (regno >= reg_set_table_size) - return; - for (reg_info = reg_set_table[regno]; reg_info; reg_info = reg_info->next) - if (reg_info->insn == old_insn) - { - reg_info->insn = new_insn; - break; - } -} - /* Record REGNO in the reg_set table. */ static void @@ -1149,16 +1113,15 @@ record_one_set (int regno, rtx insn) { int new_size = regno + REG_SET_TABLE_SLOP; - reg_set_table = grealloc (reg_set_table, - new_size * sizeof (struct reg_set *)); + reg_set_table = GRESIZEVEC (struct reg_set *, reg_set_table, new_size); 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)); + new_reg_info = XOBNEW (®_set_obstack, struct reg_set); bytes_used += sizeof (struct reg_set); - new_reg_info->insn = insn; + new_reg_info->bb_index = BLOCK_NUM (insn); new_reg_info->next = reg_set_table[regno]; reg_set_table[regno] = new_reg_info; } @@ -1168,7 +1131,7 @@ record_one_set (int regno, rtx insn) occurring. */ static void -record_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data) +record_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) { rtx record_set_insn = (rtx) data; @@ -1182,13 +1145,15 @@ record_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data) `reg_set_table' for further documentation. */ static void -compute_sets (rtx f) +compute_sets (void) { + basic_block bb; rtx insn; - for (insn = f; insn != 0; insn = NEXT_INSN (insn)) - if (INSN_P (insn)) - note_stores (PATTERN (insn), record_set_info, 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. */ @@ -1210,12 +1175,21 @@ static basic_block current_bb; static int want_to_gcse_p (rtx x) { +#ifdef STACK_REGS + /* On register stack architectures, don't GCSE constants from the + constant pool, as the benefits are often swamped by the overhead + of shuffling the register stack between basic blocks. */ + if (IS_STACK_MODE (GET_MODE (x))) + x = avoid_constant_pool_reference (x); +#endif + switch (GET_CODE (x)) { case REG: case SUBREG: case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case CONST_VECTOR: case CALL: return 0; @@ -1268,7 +1242,7 @@ can_assign_to_reg_p (rtx x) or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */ static int -oprs_unchanged_p (rtx x, rtx insn, int avail_p) +oprs_unchanged_p (const_rtx x, const_rtx insn, int avail_p) { int i, j; enum rtx_code code; @@ -1312,6 +1286,7 @@ oprs_unchanged_p (rtx x, rtx insn, int avail_p) case CONST: case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case CONST_VECTOR: case SYMBOL_REF: case LABEL_REF: @@ -1354,14 +1329,14 @@ static int gcse_mems_conflict_p; load_killed_in_block_p. A memory reference for a load instruction, mems_conflict_for_gcse_p will see if a memory store conflicts with this memory load. */ -static rtx gcse_mem_operand; +static const_rtx gcse_mem_operand; /* DEST is the output of an instruction. If it is a memory reference, and possibly conflicts with the load found in gcse_mem_operand, then set gcse_mems_conflict_p to a nonzero value. */ static void -mems_conflict_for_gcse_p (rtx dest, rtx setter ATTRIBUTE_UNUSED, +mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) { while (GET_CODE (dest) == SUBREG @@ -1399,9 +1374,14 @@ mems_conflict_for_gcse_p (rtx dest, rtx setter ATTRIBUTE_UNUSED, AVAIL_P to 0. */ static int -load_killed_in_block_p (basic_block bb, int uid_limit, rtx x, int avail_p) +load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x, int avail_p) { rtx list_entry = modify_mem_list[bb->index]; + + /* If this is a readonly then we aren't going to be changing it. */ + if (MEM_READONLY_P (x)) + return 0; + while (list_entry) { rtx setter; @@ -1442,7 +1422,7 @@ load_killed_in_block_p (basic_block bb, int uid_limit, rtx x, int avail_p) the start of INSN's basic block up to but not including INSN. */ static int -oprs_anticipatable_p (rtx x, rtx insn) +oprs_anticipatable_p (const_rtx x, const_rtx insn) { return oprs_unchanged_p (x, insn, 0); } @@ -1451,7 +1431,7 @@ oprs_anticipatable_p (rtx x, rtx insn) INSN to the end of INSN's basic block. */ static int -oprs_available_p (rtx x, rtx insn) +oprs_available_p (const_rtx x, const_rtx insn) { return oprs_unchanged_p (x, insn, 1); } @@ -1464,7 +1444,7 @@ oprs_available_p (rtx x, rtx insn) the current size of the hash table to be probed. */ static unsigned int -hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p, +hash_expr (const_rtx x, enum machine_mode mode, int *do_not_record_p, int hash_table_size) { unsigned int hash; @@ -1495,7 +1475,7 @@ hash_set (int regno, int hash_table_size) /* Return nonzero if exp1 is equivalent to exp2. */ static int -expr_equiv_p (rtx x, rtx y) +expr_equiv_p (const_rtx x, const_rtx y) { return exp_equiv_p (x, y, 0, true); } @@ -1518,7 +1498,6 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, unsigned int hash; struct expr *cur_expr, *last_expr = NULL; struct occr *antic_occr, *avail_occr; - struct occr *last_occr = NULL; hash = hash_expr (x, mode, &do_not_record_p, table->size); @@ -1541,7 +1520,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. */ @@ -1563,14 +1542,8 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, { antic_occr = cur_expr->antic_occr; - /* Search for another occurrence in the same basic block. */ - while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn)) - { - /* If an occurrence isn't found, save a pointer to the end of - the list. */ - last_occr = antic_occr; - antic_occr = antic_occr->next; - } + if (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn)) + antic_occr = NULL; if (antic_occr) /* Found another instance of the expression in the same basic block. @@ -1580,17 +1553,12 @@ 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); - /* First occurrence of this expression in any block? */ - if (cur_expr->antic_occr == NULL) - cur_expr->antic_occr = antic_occr; - else - last_occr->next = antic_occr; - antic_occr->insn = insn; - antic_occr->next = NULL; + antic_occr->next = cur_expr->antic_occr; antic_occr->deleted_p = 0; + cur_expr->antic_occr = antic_occr; } } @@ -1598,36 +1566,23 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, { avail_occr = cur_expr->avail_occr; - /* Search for another occurrence in the same basic block. */ - while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn)) + if (avail_occr && BLOCK_NUM (avail_occr->insn) == BLOCK_NUM (insn)) { - /* If an occurrence isn't found, save a pointer to the end of - the list. */ - last_occr = avail_occr; - avail_occr = avail_occr->next; + /* Found another instance of the expression in the same basic block. + Prefer this occurrence to the currently recorded one. We want + the last one in the block and the block is scanned from start + to end. */ + avail_occr->insn = insn; } - - if (avail_occr) - /* Found another instance of the expression in the same basic block. - Prefer this occurrence to the currently recorded one. We want - the last one in the block and the block is scanned from start - to end. */ - avail_occr->insn = insn; 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); - - /* First occurrence of this expression in any block? */ - if (cur_expr->avail_occr == NULL) - cur_expr->avail_occr = avail_occr; - else - last_occr->next = avail_occr; - avail_occr->insn = insn; - avail_occr->next = NULL; + avail_occr->next = cur_expr->avail_occr; avail_occr->deleted_p = 0; + cur_expr->avail_occr = avail_occr; } } } @@ -1643,7 +1598,7 @@ insert_set_in_table (rtx x, rtx insn, struct hash_table *table) int found; unsigned int hash; struct expr *cur_expr, *last_expr = NULL; - struct occr *cur_occr, *last_occr = NULL; + struct occr *cur_occr; gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x))); @@ -1662,7 +1617,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. */ @@ -1684,35 +1639,24 @@ insert_set_in_table (rtx x, rtx insn, struct hash_table *table) /* Now record the occurrence. */ cur_occr = cur_expr->avail_occr; - /* Search for another occurrence in the same basic block. */ - while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn)) + if (cur_occr && BLOCK_NUM (cur_occr->insn) == BLOCK_NUM (insn)) { - /* If an occurrence isn't found, save a pointer to the end of - the list. */ - last_occr = cur_occr; - cur_occr = cur_occr->next; + /* Found another instance of the expression in the same basic block. + Prefer this occurrence to the currently recorded one. We want + the last one in the block and the block is scanned from start + to end. */ + cur_occr->insn = insn; } - - if (cur_occr) - /* Found another instance of the expression in the same basic block. - Prefer this occurrence to the currently recorded one. We want the - last one in the block and the block is scanned from start to end. */ - cur_occr->insn = insn; 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); - /* First occurrence of this expression in any block? */ - if (cur_expr->avail_occr == NULL) - cur_expr->avail_occr = cur_occr; - else - last_occr->next = cur_occr; - - cur_occr->insn = insn; - cur_occr->next = NULL; - cur_occr->deleted_p = 0; + cur_occr->insn = insn; + cur_occr->next = cur_expr->avail_occr; + cur_occr->deleted_p = 0; + cur_expr->avail_occr = cur_occr; } } @@ -1720,7 +1664,7 @@ insert_set_in_table (rtx x, rtx insn, struct hash_table *table) the purposes of GCSE's constant propagation. */ static bool -gcse_constant_p (rtx x) +gcse_constant_p (const_rtx x) { /* Consider a COMPARE of two integers constant. */ if (GET_CODE (x) == COMPARE @@ -1758,10 +1702,28 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) unsigned int regno = REGNO (dest); rtx tmp; - /* If this is a single set and we are doing constant propagation, - see if a REG_NOTE shows this equivalent to a constant. */ - if (table->set_p && (note = find_reg_equal_equiv_note (insn)) != 0 - && gcse_constant_p (XEXP (note, 0))) + /* 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. + + 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)))) src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src); /* Only record sets of pseudo-regs in the hash table. */ @@ -1782,13 +1744,15 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) REG_EQUIV notes and if the argument slot is used somewhere explicitly, it means address of parameter has been taken, so we should not extend the lifetime of the pseudo. */ - && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0 - || ! MEM_P (XEXP (note, 0)))) + && (note == NULL_RTX || ! MEM_P (XEXP (note, 0)))) { /* An expression is not anticipatable if its operands are modified before this insn or if this is not the only SET in - this insn. */ - int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn); + this insn. The latter condition does not have to mean that + SRC itself is not anticipatable, but we just will not be + able to handle code motion of insns with multiple sets. */ + int antic_p = oprs_anticipatable_p (src, insn) + && !multiple_sets (insn); /* An expression is not available if its operands are subsequently modified, including this insn. It's also not available if this is a branch, because we can't insert @@ -1811,8 +1775,9 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table *table) modified. Here we want to search from INSN+1 on, but oprs_available_p searches from INSN on. */ && (insn == BB_END (BLOCK_FOR_INSN (insn)) - || ((tmp = next_nonnote_insn (insn)) != NULL_RTX - && oprs_available_p (pat, tmp)))) + || (tmp = next_nonnote_insn (insn)) == NULL_RTX + || BLOCK_FOR_INSN (tmp) != BLOCK_FOR_INSN (insn) + || oprs_available_p (pat, tmp))) insert_set_in_table (pat, insn, table); } /* In case of store we want to consider the memory value as available in @@ -1883,19 +1848,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 *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. */ @@ -1929,8 +1889,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) @@ -1993,7 +1953,7 @@ record_last_reg_set_info (rtx insn, int regno) taken off pairwise. */ static void -canon_list_insert (rtx dest ATTRIBUTE_UNUSED, rtx unused1 ATTRIBUTE_UNUSED, +canon_list_insert (rtx dest ATTRIBUTE_UNUSED, const_rtx unused1 ATTRIBUTE_UNUSED, void * v_insn) { rtx dest_addr, insn; @@ -2020,7 +1980,6 @@ canon_list_insert (rtx dest ATTRIBUTE_UNUSED, rtx unused1 ATTRIBUTE_UNUSED, alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]); canon_modify_mem_list[bb] = alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]); - bitmap_set_bit (canon_modify_mem_list_set, bb); } /* Record memory modification information for INSN. We do not actually care @@ -2044,7 +2003,7 @@ record_last_mem_set_info (rtx insn) need to insert a pair of items, as canon_list_insert does. */ canon_modify_mem_list[bb] = alloc_INSN_LIST (insn, canon_modify_mem_list[bb]); - bitmap_set_bit (canon_modify_mem_list_set, bb); + bitmap_set_bit (blocks_with_calls, bb); } else note_stores (PATTERN (insn), canon_list_insert, (void*) insn); @@ -2055,7 +2014,7 @@ record_last_mem_set_info (rtx insn) the SET is taking place. */ static void -record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data) +record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) { rtx last_set_insn = (rtx) data; @@ -2100,7 +2059,7 @@ compute_hash_table_work (struct hash_table *table) /* 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_gcse_regno); for (i = 0; i < max_gcse_regno; ++i) reg_avail_info[i].last_bb = NULL; @@ -2109,16 +2068,13 @@ compute_hash_table_work (struct hash_table *table) { 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. */ - for (insn = BB_HEAD (current_bb); - insn && insn != NEXT_INSN (BB_END (current_bb)); - insn = NEXT_INSN (insn)) + FOR_BB_INSNS (current_bb, insn) { if (! INSN_P (insn)) continue; @@ -2142,20 +2098,9 @@ compute_hash_table_work (struct hash_table *table) BB_HEAD (current_bb), table); /* The next pass builds the hash table. */ - - for (insn = BB_HEAD (current_bb), in_libcall_block = 0; - insn && insn != NEXT_INSN (BB_END (current_bb)); - insn = NEXT_INSN (insn)) + 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); @@ -2182,7 +2127,7 @@ 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; } @@ -2268,17 +2213,13 @@ clear_modify_mem_tables (void) EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi) { free_INSN_LIST_list (modify_mem_list + i); - } - bitmap_clear (modify_mem_list_set); - - EXECUTE_IF_SET_IN_BITMAP (canon_modify_mem_list_set, 0, i, bi) - { free_insn_expr_list_list (canon_modify_mem_list + i); } - bitmap_clear (canon_modify_mem_list_set); + bitmap_clear (modify_mem_list_set); + bitmap_clear (blocks_with_calls); } -/* Release memory used by modify_mem_list_set and canon_modify_mem_list_set. */ +/* Release memory used by modify_mem_list_set. */ static void free_modify_mem_tables (void) @@ -2310,7 +2251,7 @@ reset_opr_set_tables (void) INSN's basic block. */ static int -oprs_not_set_p (rtx x, rtx insn) +oprs_not_set_p (const_rtx x, const_rtx insn) { int i, j; enum rtx_code code; @@ -2327,6 +2268,7 @@ oprs_not_set_p (rtx x, rtx insn) case CONST: case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case CONST_VECTOR: case SYMBOL_REF: case LABEL_REF: @@ -2375,7 +2317,7 @@ oprs_not_set_p (rtx x, 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); } @@ -2488,7 +2430,7 @@ free_cprop_mem (void) bit in BMAP. */ static void -compute_transp (rtx x, int indx, sbitmap *bmap, int set_p) +compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p) { int i, j; basic_block bb; @@ -2518,7 +2460,7 @@ compute_transp (rtx x, int indx, sbitmap *bmap, int set_p) else { for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next) - SET_BIT (bmap[BLOCK_NUM (r->insn)], indx); + SET_BIT (bmap[r->bb_index], indx); } } else @@ -2532,47 +2474,59 @@ compute_transp (rtx x, int indx, sbitmap *bmap, int set_p) else { for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next) - RESET_BIT (bmap[BLOCK_NUM (r->insn)], indx); + RESET_BIT (bmap[r->bb_index], indx); } } return; case MEM: - FOR_EACH_BB (bb) + if (! MEM_READONLY_P (x)) { - rtx list_entry = canon_modify_mem_list[bb->index]; + bitmap_iterator bi; + unsigned bb_index; - while (list_entry) + /* First handle all the blocks with calls. We don't need to + do any list walking for them. */ + EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi) { - rtx dest, dest_addr; + if (set_p) + SET_BIT (bmap[bb_index], indx); + else + RESET_BIT (bmap[bb_index], indx); + } - if (CALL_P (XEXP (list_entry, 0))) - { - if (set_p) - SET_BIT (bmap[bb->index], indx); - else - RESET_BIT (bmap[bb->index], indx); - break; - } - /* LIST_ENTRY must be an INSN of some kind that sets memory. - Examine each hunk of memory that is modified. */ + /* Now iterate over the blocks which have memory modifications + but which do not have any calls. */ + EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, + blocks_with_calls, + 0, bb_index, bi) + { + rtx list_entry = canon_modify_mem_list[bb_index]; + + while (list_entry) + { + rtx dest, dest_addr; - dest = XEXP (list_entry, 0); - list_entry = XEXP (list_entry, 1); - dest_addr = XEXP (list_entry, 0); + /* LIST_ENTRY must be an INSN of some kind that sets memory. + Examine each hunk of memory that is modified. */ - if (canon_true_dependence (dest, GET_MODE (dest), dest_addr, - x, rtx_addr_varies_p)) - { - if (set_p) - SET_BIT (bmap[bb->index], indx); - else - RESET_BIT (bmap[bb->index], indx); - break; - } - list_entry = XEXP (list_entry, 1); - } + dest = XEXP (list_entry, 0); + list_entry = XEXP (list_entry, 1); + dest_addr = XEXP (list_entry, 0); + + if (canon_true_dependence (dest, GET_MODE (dest), dest_addr, + x, rtx_addr_varies_p)) + { + if (set_p) + SET_BIT (bmap[bb_index], indx); + else + RESET_BIT (bmap[bb_index], indx); + break; + } + list_entry = XEXP (list_entry, 1); + } + } } x = XEXP (x, 0); @@ -2583,6 +2537,7 @@ compute_transp (rtx x, int indx, sbitmap *bmap, int set_p) case CONST: case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case CONST_VECTOR: case SYMBOL_REF: case LABEL_REF: @@ -2703,6 +2658,11 @@ try_replace_reg (rtx from, rtx to, rtx insn) int success = 0; rtx set = single_set (insn); + /* Usually we substitute easy stuff, so we won't copy everything. + We however need to take care to not duplicate non-trivial CONST + expressions. */ + to = copy_rtx (to); + validate_replace_src_group (from, to, insn); if (num_changes_pending () && apply_change_group ()) success = 1; @@ -2716,11 +2676,12 @@ try_replace_reg (rtx from, rtx to, rtx insn) validate_change (insn, &SET_SRC (set), src, 0); } - /* If there is already a NOTE, update the expression in it with our - replacement. */ - if (note != 0) - XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), from, to); - + /* If there is already a REG_EQUAL note, update the expression in it + 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, + 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 @@ -2736,7 +2697,8 @@ try_replace_reg (rtx from, rtx to, rtx insn) have a note, and have no special SET, add a REG_EQUAL note to not lose information. */ if (!success && note == 0 && set != 0 - && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT) + && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT + && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART) note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src)); } @@ -2744,7 +2706,7 @@ try_replace_reg (rtx from, rtx to, rtx insn) We don't allow that. Remove that note. This code ought not to happen, because previous code ought to synthesize reg-reg move, but be on the safe side. */ - if (note && REG_P (XEXP (note, 0))) + if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0))) remove_note (insn, note); return success; @@ -2827,7 +2789,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); @@ -2859,22 +2821,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 @@ -2885,20 +2847,14 @@ 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; } /* Remove REG_EQUAL note after simplification. */ if (note_src) remove_note (jump, note); - - /* If this has turned into an unconditional jump, - then put a barrier after it so that the unreachable - code will be deleted. */ - if (GET_CODE (SET_SRC (set)) == LABEL_REF) - emit_barrier_after (jump); } #ifdef HAVE_cc0 @@ -2910,21 +2866,39 @@ cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) run_jump_opt_after_gcse = 1; global_const_prop_count++; - if (gcse_file != NULL) + if (dump_file != NULL) { - fprintf (gcse_file, + fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ", REGNO (from), INSN_UID (jump)); - print_rtl (gcse_file, src); - fprintf (gcse_file, "\n"); + print_rtl (dump_file, src); + fprintf (dump_file, "\n"); } purge_dead_edges (bb); + /* 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_rtx != pc_rtx && simplejump_p (jump)) + { + edge e; + edge_iterator ei; + + for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ei_next (&ei)) + if (e->dest != EXIT_BLOCK_PTR + && BB_HEAD (e->dest) == JUMP_LABEL (jump)) + { + e->flags |= EDGE_FALLTHRU; + break; + } + delete_insn (jump); + } + return 1; } static bool -constprop_register (rtx insn, rtx from, rtx to, int alter_jumps) +constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps) { rtx sset; @@ -3015,12 +2989,12 @@ cprop_insn (rtx insn, int alter_jumps) { changed = 1; global_const_prop_count++; - if (gcse_file != NULL) + if (dump_file != NULL) { - fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno); - fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn)); - print_rtl (gcse_file, src); - fprintf (gcse_file, "\n"); + fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno); + fprintf (dump_file, "insn %d with constant ", INSN_UID (insn)); + print_rtl (dump_file, src); + fprintf (dump_file, "\n"); } if (INSN_DELETED_P (insn)) return 1; @@ -3034,11 +3008,11 @@ cprop_insn (rtx insn, int alter_jumps) { changed = 1; global_copy_prop_count++; - if (gcse_file != NULL) + if (dump_file != NULL) { - fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d", + fprintf (dump_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d", regno, INSN_UID (insn)); - fprintf (gcse_file, " with reg %d\n", REGNO (src)); + fprintf (dump_file, " with reg %d\n", REGNO (src)); } /* The original insn setting reg_used may or may not now be @@ -3098,11 +3072,11 @@ 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. + If ALTER_JUMPS is false, changing jump insns is not allowed. */ static bool -do_local_cprop (rtx x, rtx insn, int alter_jumps, rtx *libcall_sp) +do_local_cprop (rtx x, rtx insn, bool alter_jumps) { rtx newreg = NULL, newcnst = NULL; @@ -3123,10 +3097,6 @@ do_local_cprop (rtx x, rtx insn, int 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 @@ -3141,37 +3111,26 @@ do_local_cprop (rtx x, rtx insn, int alter_jumps, rtx *libcall_sp) } if (newcnst && constprop_register (insn, x, newcnst, alter_jumps)) { - /* 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_EUAQL 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 (gcse_file != NULL) + if (dump_file != NULL) { - fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ", + fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ", REGNO (x)); - fprintf (gcse_file, "insn %d with constant ", + fprintf (dump_file, "insn %d with constant ", INSN_UID (insn)); - print_rtl (gcse_file, newcnst); - fprintf (gcse_file, "\n"); + print_rtl (dump_file, newcnst); + fprintf (dump_file, "\n"); } local_const_prop_count++; return true; } else if (newreg && newreg != x && try_replace_reg (x, newreg, insn)) { - adjust_libcall_notes (x, newreg, insn, libcall_sp); - if (gcse_file != NULL) + if (dump_file != NULL) { - fprintf (gcse_file, + fprintf (dump_file, "LOCAL COPY-PROP: Replacing reg %d in insn %d", REGNO (x), INSN_UID (insn)); - fprintf (gcse_file, " with reg %d\n", REGNO (newreg)); + fprintf (dump_file, " with reg %d\n", REGNO (newreg)); } local_copy_prop_count++; return true; @@ -3180,102 +3139,64 @@ do_local_cprop (rtx x, rtx insn, int 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); - insn = end; - } - return true; -} - -#define MAX_NESTED_LIBCALLS 9 +/* 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 (int alter_jumps) +local_cprop_pass (bool alter_jumps) { + 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 (insn = get_insns (); insn; insn = NEXT_INSN (insn)) + FOR_EACH_BB (bb) { - if (INSN_P (insn)) + FOR_BB_INSNS (bb, 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); - do + if (INSN_P (insn)) { - reg_use_count = 0; - note_uses (&PATTERN (insn), local_cprop_find_used_regs, NULL); - if (note) - local_cprop_find_used_regs (&XEXP (note, 0), NULL); - - 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)) - { - changed = true; + rtx note = find_reg_equal_equiv_note (insn); + do + { + reg_use_count = 0; + note_uses (&PATTERN (insn), local_cprop_find_used_regs, + NULL); + if (note) + local_cprop_find_used_regs (&XEXP (note, 0), NULL); + + 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)) + { + changed = true; + break; + } + } + if (INSN_DELETED_P (insn)) break; - } - if (INSN_DELETED_P (insn)) - break; + } + while (reg_use_count); } - while (reg_use_count); + cselib_process_insn (insn); } - cselib_process_insn (insn); + + /* Forget everything at the end of a basic block. */ + cselib_clear_table (); } + 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 (get_insns ()); + compute_sets (); } } @@ -3292,8 +3213,8 @@ cprop (int alter_jumps) /* Note we start at block 1. */ if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) { - if (gcse_file != NULL) - fprintf (gcse_file, "\n"); + if (dump_file != NULL) + fprintf (dump_file, "\n"); return 0; } @@ -3304,9 +3225,7 @@ cprop (int alter_jumps) start of the block]. */ reset_opr_set_tables (); - for (insn = BB_HEAD (bb); - insn != NULL && insn != NEXT_INSN (BB_END (bb)); - insn = NEXT_INSN (insn)) + FOR_BB_INSNS (bb, insn) if (INSN_P (insn)) { changed |= cprop_insn (insn, alter_jumps); @@ -3319,8 +3238,8 @@ cprop (int alter_jumps) } } - if (gcse_file != NULL) - fprintf (gcse_file, "\n"); + if (dump_file != NULL) + fprintf (dump_file, "\n"); return changed; } @@ -3332,7 +3251,7 @@ cprop (int alter_jumps) settle for the condition variable in the jump instruction being integral. We prefer to be able to record the value of a user variable, rather than the value of a temporary used in a condition. This could be solved by - recording the value of *every* register scaned by canonicalize_condition, + recording the value of *every* register scanned by canonicalize_condition, but this would require some code reorganization. */ rtx @@ -3345,10 +3264,10 @@ fis_get_condition (rtx jump) it. COND is either an EQ or NE comparison. */ static bool -implicit_set_cond_p (rtx cond) +implicit_set_cond_p (const_rtx cond) { - enum machine_mode mode = GET_MODE (XEXP (cond, 0)); - rtx cst = XEXP (cond, 1); + const enum machine_mode mode = GET_MODE (XEXP (cond, 0)); + const_rtx cst = XEXP (cond, 1); /* We can't perform this optimization if either operand might be or might contain a signed zero. */ @@ -3385,7 +3304,7 @@ find_implicit_sets (void) { basic_block bb, dest; unsigned int count; - rtx cond, new; + rtx cond, new_rtx; count = 0; FOR_EACH_BB (bb) @@ -3403,25 +3322,25 @@ find_implicit_sets (void) dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest; - if (dest && EDGE_COUNT (dest->preds) == 1 + if (dest && 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; - if (gcse_file) + implicit_sets[dest->index] = new_rtx; + if (dump_file) { - fprintf(gcse_file, "Implicit set of reg %d in ", + fprintf(dump_file, "Implicit set of reg %d in ", REGNO (XEXP (cond, 0))); - fprintf(gcse_file, "basic block %d\n", dest->index); + fprintf(dump_file, "basic block %d\n", dest->index); } count++; } } } - if (gcse_file) - fprintf (gcse_file, "Found %d implicit sets\n", count); + if (dump_file) + fprintf (dump_file, "Found %d implicit sets\n", count); } /* Perform one copy/constant propagation pass. @@ -3430,17 +3349,18 @@ find_implicit_sets (void) perform conditional jump bypassing optimizations. */ static int -one_cprop_pass (int pass, int cprop_jumps, int bypass_jumps) +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; - local_cprop_pass (cprop_jumps); + if (cprop_jumps) + local_cprop_pass (cprop_jumps); /* Determine implicit sets. */ - implicit_sets = xcalloc (last_basic_block, sizeof (rtx)); + implicit_sets = XCNEWVEC (rtx, last_basic_block); find_implicit_sets (); alloc_hash_table (max_cuid, &set_hash_table, 1); @@ -3450,8 +3370,8 @@ one_cprop_pass (int pass, int cprop_jumps, int bypass_jumps) free (implicit_sets); implicit_sets = NULL; - if (gcse_file) - dump_hash_table (gcse_file, "SET", &set_hash_table); + 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); @@ -3464,13 +3384,13 @@ one_cprop_pass (int pass, int cprop_jumps, int bypass_jumps) free_hash_table (&set_hash_table); - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, ", + fprintf (dump_file, "CPROP of %s, pass %d: %d bytes needed, ", current_function_name (), pass, bytes_used); - fprintf (gcse_file, "%d local const props, %d local copy props\n\n", + fprintf (dump_file, "%d local const props, %d local copy props, ", local_const_prop_count, local_copy_prop_count); - fprintf (gcse_file, "%d global const props, %d global copy props\n\n", + 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. */ @@ -3535,7 +3455,7 @@ find_bypass_set (int regno, int bb) valid prior to commit_edge_insertions. */ static bool -reg_killed_on_edge (rtx reg, edge e) +reg_killed_on_edge (const_rtx reg, const_edge e) { rtx insn; @@ -3617,7 +3537,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; + rtx src, new_rtx; if (regno >= max_gcse_regno) continue; @@ -3638,7 +3558,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 @@ -3646,23 +3566,18 @@ 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) { - edge_iterator ei2; - - dest = BLOCK_FOR_INSN (XEXP (new, 0)); + dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0)); /* Don't bypass edges containing instructions. */ - FOR_EACH_EDGE (edest, ei2, bb->succs) - if (edest->dest == dest && edest->insns.r) - { - dest = NULL; - break; - } + edest = find_edge (bb, dest); + if (edest && edest->insns.r) + dest = NULL; } else dest = NULL; @@ -3671,18 +3586,9 @@ bypass_block (basic_block bb, rtx setcc, rtx jump) branch. We would end up emitting the instruction on "both" edges. */ - if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))) - { - edge e2; - edge_iterator ei2; - - FOR_EACH_EDGE (e2, ei2, e->src->succs) - if (e2->dest == dest) - { - dest = NULL; - break; - } - } + if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc))) + && find_edge (e->src, dest)) + dest = NULL; old_dest = e->dest; if (dest != NULL @@ -3700,13 +3606,13 @@ bypass_block (basic_block bb, rtx setcc, rtx jump) insert_insn_on_edge (copy_insn (pat), e); } - if (gcse_file != NULL) + if (dump_file != NULL) { - fprintf (gcse_file, "JUMP-BYPASS: Proved reg %d " + fprintf (dump_file, "JUMP-BYPASS: Proved reg %d " "in jump_insn %d equals constant ", regno, INSN_UID (jump)); - print_rtl (gcse_file, SET_SRC (set->expr)); - fprintf (gcse_file, "\nBypass edge from %d->%d to %d\n", + print_rtl (dump_file, SET_SRC (set->expr)); + fprintf (dump_file, "\nBypass edge from %d->%d to %d\n", e->src->index, old_dest->index, dest->index); } change = 1; @@ -3748,12 +3654,10 @@ bypass_conditional_jumps (void) EXIT_BLOCK_PTR, next_bb) { /* Check for more than one predecessor. */ - if (EDGE_COUNT (bb->preds) > 1) + if (!single_pred_p (bb)) { setcc = NULL_RTX; - for (insn = BB_HEAD (bb); - insn != NULL && insn != NEXT_INSN (BB_END (bb)); - insn = NEXT_INSN (insn)) + FOR_BB_INSNS (bb, insn) if (NONJUMP_INSN_P (insn)) { if (setcc) @@ -3782,7 +3686,7 @@ bypass_conditional_jumps (void) /* If we bypassed any register setting insns, we inserted a copy on the redirected edge. These need to be committed. */ if (changed) - commit_edge_insertions(); + commit_edge_insertions (); return changed; } @@ -3913,7 +3817,7 @@ compute_pre_data (void) sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]); } - edge_list = pre_edge_lcm (gcse_file, expr_hash_table.n_elems, transp, comp, antloc, + edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc, ae_kill, &pre_insert_map, &pre_delete_map); sbitmap_vector_free (antloc); antloc = NULL; @@ -3987,7 +3891,7 @@ static int pre_expr_reaches_here_p (basic_block occr_bb, struct expr *expr, basic_block bb) { int rval; - char *visited = xcalloc (last_basic_block, 1); + char *visited = XCNEWVEC (char, last_basic_block); rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited); @@ -4041,7 +3945,7 @@ process_insert_insn (struct expr *expr) no sense for code hoisting. */ static void -insert_insn_end_bb (struct expr *expr, basic_block bb, int pre) +insert_insn_end_basic_block (struct expr *expr, basic_block bb, int pre) { rtx insn = BB_END (bb); rtx new_insn; @@ -4062,8 +3966,8 @@ insert_insn_end_bb (struct expr *expr, basic_block bb, int pre) if (JUMP_P (insn) || (NONJUMP_INSN_P (insn) - && (EDGE_COUNT (bb->succs) > 1 - || EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))) + && (!single_succ_p (bb) + || single_succ_edge (bb)->flags & EDGE_ABNORMAL))) { #ifdef HAVE_cc0 rtx note; @@ -4098,13 +4002,14 @@ insert_insn_end_bb (struct expr *expr, basic_block bb, int pre) } #endif /* FIXME: What if something in cc0/jump uses value set in new insn? */ - new_insn = emit_insn_before_noloc (pat, insn); + new_insn = emit_insn_before_noloc (pat, insn, bb); } /* Likewise if the last insn is a call, as will happen in the presence of exception handling. */ else if (CALL_P (insn) - && (EDGE_COUNT (bb->succs) > 1 || EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL)) + && (!single_succ_p (bb) + || single_succ_edge (bb)->flags & EDGE_ABNORMAL)) { /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers, we search backward and place the instructions before the first @@ -4136,10 +4041,10 @@ insert_insn_end_bb (struct expr *expr, basic_block bb, int pre) || NOTE_INSN_BASIC_BLOCK_P (insn)) insn = NEXT_INSN (insn); - new_insn = emit_insn_before_noloc (pat, insn); + new_insn = emit_insn_before_noloc (pat, insn, bb); } else - new_insn = emit_insn_after_noloc (pat, insn); + new_insn = emit_insn_after_noloc (pat, insn, bb); while (1) { @@ -4155,11 +4060,11 @@ insert_insn_end_bb (struct expr *expr, basic_block bb, int pre) gcse_create_count++; - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, ", + fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ", bb->index, INSN_UID (new_insn)); - fprintf (gcse_file, "copying expression %d to reg %d\n", + fprintf (dump_file, "copying expression %d to reg %d\n", expr->bitmap_index, regno); } } @@ -4202,7 +4107,7 @@ pre_edge_insert (struct edge_list *edge_list, struct expr **index_map) if (! occr->deleted_p) continue; - /* Insert this expression on this edge if if it would + /* Insert this expression on this edge if it would reach the deleted occurrence in BB. */ if (!TEST_BIT (inserted[e], j)) { @@ -4217,19 +4122,19 @@ pre_edge_insert (struct edge_list *edge_list, struct expr **index_map) now. */ if (eg->flags & EDGE_ABNORMAL) - insert_insn_end_bb (index_map[j], bb, 0); + insert_insn_end_basic_block (index_map[j], bb, 0); else { insn = process_insert_insn (index_map[j]); insert_insn_on_edge (insn, eg); } - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "PRE/HOIST: edge (%d,%d), ", + fprintf (dump_file, "PRE/HOIST: edge (%d,%d), ", bb->index, INDEX_EDGE_SUCC_BB (edge_list, e)->index); - fprintf (gcse_file, "copy expression %d\n", + fprintf (dump_file, "copy expression %d\n", expr->bitmap_index); } @@ -4269,7 +4174,7 @@ pre_insert_copy_insn (struct expr *expr, rtx insn) int regno = REGNO (reg); int indx = expr->bitmap_index; rtx pat = PATTERN (insn); - rtx set, new_insn; + rtx set, first_set, new_insn; rtx old_reg; int i; @@ -4283,17 +4188,29 @@ pre_insert_copy_insn (struct expr *expr, rtx insn) case PARALLEL: /* Search through the parallel looking for the set whose source was the expression that we're interested in. */ + first_set = NULL_RTX; set = NULL_RTX; for (i = 0; i < XVECLEN (pat, 0); i++) { rtx x = XVECEXP (pat, 0, i); - if (GET_CODE (x) == SET - && expr_equiv_p (SET_SRC (x), expr->expr)) + if (GET_CODE (x) == SET) { - set = x; - break; + /* If the source was a REG_EQUAL or REG_EQUIV note, we + may not find an equivalent expression, but in this + case the PARALLEL will have a single set. */ + if (first_set == NULL_RTX) + first_set = x; + if (expr_equiv_p (SET_SRC (x), expr->expr)) + { + set = x; + break; + } } } + + gcc_assert (first_set); + if (set == NULL_RTX) + set = first_set; break; default: @@ -4310,7 +4227,6 @@ pre_insert_copy_insn (struct expr *expr, rtx insn) new_insn = emit_insn_after (new_insn, insn); /* Keep register set table up to date. */ - replace_one_set (REGNO (old_reg), insn, new_insn); record_one_set (regno, insn); } else @@ -4339,8 +4255,8 @@ pre_insert_copy_insn (struct expr *expr, rtx insn) gcse_create_count++; - if (gcse_file) - fprintf (gcse_file, + if (dump_file) + fprintf (dump_file, "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n", BLOCK_NUM (insn), INSN_UID (new_insn), indx, INSN_UID (insn), regno); @@ -4418,7 +4334,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; @@ -4426,20 +4342,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. @@ -4476,14 +4392,14 @@ pre_delete (void) /* We only delete insns that have a single_set. */ if (TEST_BIT (pre_delete_map[bb->index], indx) - && (set = single_set (insn)) != 0) + && (set = single_set (insn)) != 0 + && dbg_cnt (pre_insn)) { /* Create a pseudo-reg to store the result of reaching expressions into. Get the mode for the new pseudo from the mode of the original destination pseudo. */ if (expr->reaching_reg == NULL) - expr->reaching_reg - = gen_reg_rtx (GET_MODE (SET_DEST (set))); + 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); @@ -4492,12 +4408,12 @@ pre_delete (void) changed = 1; gcse_subst_count++; - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, + fprintf (dump_file, "PRE: redundant insn %d (expression %d) in ", INSN_UID (insn), indx); - fprintf (gcse_file, "bb %d, reaching reg is %d\n", + fprintf (dump_file, "bb %d, reaching reg is %d\n", bb->index, REGNO (expr->reaching_reg)); } } @@ -4538,7 +4454,7 @@ pre_gcse (void) /* Compute a mapping from expression number (`bitmap_index') to hash table entry. */ - index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *)); + index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems); for (i = 0; i < expr_hash_table.size; i++) for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) index_map[expr->bitmap_index] = expr; @@ -4553,7 +4469,6 @@ pre_gcse (void) - we know which insns are redundant when we go to create copies */ changed = pre_delete (); - did_insert = pre_edge_insert (edge_list, index_map); /* In other places with reaching expressions, copy the expression to the @@ -4589,8 +4504,8 @@ one_pre_gcse_pass (int pass) compute_hash_table (&expr_hash_table); trim_ld_motion_mems (); - if (gcse_file) - dump_hash_table (gcse_file, "Expression", &expr_hash_table); + if (dump_file) + dump_hash_table (dump_file, "Expression", &expr_hash_table); if (expr_hash_table.n_elems > 0) { @@ -4605,28 +4520,26 @@ one_pre_gcse_pass (int pass) remove_fake_exit_edges (); free_hash_table (&expr_hash_table); - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ", + fprintf (dump_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ", current_function_name (), pass, bytes_used); - fprintf (gcse_file, "%d substs, %d insns created\n", + fprintf (dump_file, "%d substs, %d insns created\n", gcse_subst_count, gcse_create_count); } return changed; } -/* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN. - If notes are added to an insn which references a CODE_LABEL, the - LABEL_NUSES count is incremented. We have to add REG_LABEL notes, - because the following loop optimization pass requires them. */ - -/* ??? This is very similar to the loop.c add_label_notes function. We - could probably share code here. */ +/* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them + to INSN. If such notes are added to an insn which references a + CODE_LABEL, the LABEL_NUSES count is incremented. We have to add + that note, because the following loop optimization pass requires + them. */ /* ??? If there was a jump optimization pass after gcse and before loop, then we would not need to do this here, because jump would add the - necessary REG_LABEL notes. */ + necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */ static void add_label_notes (rtx x, rtx insn) @@ -4643,10 +4556,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). */ - REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0), - REG_NOTES (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)); + add_reg_note (insn, REG_LABEL_OPERAND, XEXP (x, 0)); + if (LABEL_P (XEXP (x, 0))) LABEL_NUSES (XEXP (x, 0))++; + return; } @@ -4684,7 +4602,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))) @@ -4779,17 +4697,21 @@ compute_code_hoist_vbeinout (void) the convergence. */ FOR_EACH_BB_REVERSE (bb) { - changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index], - hoist_vbeout[bb->index], transp[bb->index]); if (bb->next_bb != EXIT_BLOCK_PTR) - sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index); + sbitmap_intersection_of_succs (hoist_vbeout[bb->index], + hoist_vbein, bb->index); + + changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], + antloc[bb->index], + hoist_vbeout[bb->index], + transp[bb->index]); } passes++; } - if (gcse_file) - fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes); + if (dump_file) + fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes); } /* Top level routine to do the dataflow analysis needed by code hoisting. */ @@ -4801,8 +4723,8 @@ compute_code_hoist_data (void) compute_transpout (); compute_code_hoist_vbeinout (); calculate_dominance_info (CDI_DOMINATORS); - if (gcse_file) - fprintf (gcse_file, "\n"); + if (dump_file) + fprintf (dump_file, "\n"); } /* Determine if the expression identified by EXPR_INDEX would @@ -4829,7 +4751,7 @@ hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, if (visited == NULL) { visited_allocated_locally = 1; - visited = xcalloc (last_basic_block, 1); + visited = XCNEWVEC (char, last_basic_block); } FOR_EACH_EDGE (pred, ei, bb->preds) @@ -4870,8 +4792,7 @@ static void hoist_code (void) { basic_block bb, dominated; - basic_block *domby; - unsigned int domby_len; + VEC (basic_block, heap) *domby; unsigned int i,j; struct expr **index_map; struct expr *expr; @@ -4881,7 +4802,7 @@ hoist_code (void) /* Compute a mapping from expression number (`bitmap_index') to hash table entry. */ - index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *)); + index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems); for (i = 0; i < expr_hash_table.size; i++) for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) index_map[expr->bitmap_index] = expr; @@ -4893,7 +4814,7 @@ hoist_code (void) int found = 0; int insn_inserted_p; - domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby); + domby = get_dominated_by (CDI_DOMINATORS, bb); /* Examine each expression that is very busy at the exit of this block. These are the potentially hoistable expressions. */ for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++) @@ -4906,9 +4827,8 @@ hoist_code (void) /* We've found a potentially hoistable expression, now we look at every block BB dominates to see if it computes the expression. */ - for (j = 0; j < domby_len; j++) + for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) { - dominated = domby[j]; /* Ignore self dominance. */ if (bb == dominated) continue; @@ -4947,8 +4867,8 @@ hoist_code (void) /* If we found nothing to hoist, then quit now. */ if (! found) { - free (domby); - continue; + VEC_free (basic_block, heap, domby); + continue; } /* Loop over all the hoistable expressions. */ @@ -4959,14 +4879,13 @@ hoist_code (void) insn_inserted_p = 0; /* These tests should be the same as the tests above. */ - if (TEST_BIT (hoist_vbeout[bb->index], i)) + if (TEST_BIT (hoist_exprs[bb->index], i)) { /* We've found a potentially hoistable expression, now we look at every block BB dominates to see if it computes the expression. */ - for (j = 0; j < domby_len; j++) + for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) { - dominated = domby[j]; /* Ignore self dominance. */ if (bb == dominated) continue; @@ -5003,21 +4922,21 @@ 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; if (!insn_inserted_p) { - insert_insn_end_bb (index_map[i], bb, 0); + insert_insn_end_basic_block (index_map[i], bb, 0); insn_inserted_p = 1; } } } } } - free (domby); + VEC_free (basic_block, heap, domby); } free (index_map); @@ -5034,8 +4953,8 @@ one_code_hoisting_pass (void) alloc_hash_table (max_cuid, &expr_hash_table, 0); compute_hash_table (&expr_hash_table); - if (gcse_file) - dump_hash_table (gcse_file, "Code Hosting Expressions", &expr_hash_table); + if (dump_file) + dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table); if (expr_hash_table.n_elems > 0) { @@ -5075,6 +4994,22 @@ one_code_hoisting_pass (void) load towards the exit, and we end up with no loads or stores of 'i' in the loop. */ +static hashval_t +pre_ldst_expr_hash (const void *p) +{ + int do_not_record_p = 0; + 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 *const ptr1 = (const struct ls_expr *) p1, + *const ptr2 = (const struct ls_expr *) p2; + return expr_equiv_p (ptr1->pattern, ptr2->pattern); +} + /* This will search the ldst list for a matching expression. If it doesn't find one, we create one and initialize it. */ @@ -5084,15 +5019,18 @@ ldst_entry (rtx x) int do_not_record_p = 0; struct ls_expr * ptr; unsigned int hash; + void **slot; + struct ls_expr e; hash = hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, /*have_reg_qty=*/false); - for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) - if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x)) - return ptr; + e.pattern = x; + slot = htab_find_slot_with_hash (pre_ldst_table, &e, hash, INSERT); + if (*slot) + return (struct ls_expr *)*slot; - ptr = xmalloc (sizeof (struct ls_expr)); + ptr = XNEW (struct ls_expr); ptr->next = pre_ldst_mems; ptr->expr = NULL; @@ -5105,6 +5043,7 @@ ldst_entry (rtx x) ptr->index = 0; ptr->hash_index = hash; pre_ldst_mems = ptr; + *slot = ptr; return ptr; } @@ -5125,6 +5064,10 @@ free_ldst_entry (struct ls_expr * ptr) static void free_ldst_mems (void) { + if (pre_ldst_table) + htab_delete (pre_ldst_table); + pre_ldst_table = NULL; + while (pre_ldst_mems) { struct ls_expr * tmp = pre_ldst_mems; @@ -5146,7 +5089,7 @@ print_ldst_list (FILE * file) fprintf (file, "LDST list: \n"); - for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr)) + for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) { fprintf (file, " Pattern (%3d): ", ptr->index); @@ -5177,13 +5120,15 @@ print_ldst_list (FILE * file) static struct ls_expr * find_rtx_in_ldst (rtx x) { - struct ls_expr * ptr; - - for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) - if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid) - return ptr; - - return NULL; + struct ls_expr e; + void **slot; + if (!pre_ldst_table) + return NULL; + e.pattern = x; + slot = htab_find_slot (pre_ldst_table, &e, NO_INSERT); + if (!slot || ((struct ls_expr *)*slot)->invalid) + return NULL; + return (struct ls_expr *) *slot; } /* Assign each element of the list of mems a monotonically increasing value. */ @@ -5223,7 +5168,7 @@ next_ls_expr (struct ls_expr * ptr) ld_motion list, otherwise we let the usual aliasing take care of it. */ static int -simple_mem (rtx x) +simple_mem (const_rtx x) { if (! MEM_P (x)) return 0; @@ -5304,12 +5249,12 @@ compute_ld_motion_mems (void) rtx insn; pre_ldst_mems = NULL; + pre_ldst_table = htab_create (13, pre_ldst_expr_hash, + pre_ldst_expr_eq, NULL); FOR_EACH_BB (bb) { - for (insn = BB_HEAD (bb); - insn && insn != NEXT_INSN (BB_END (bb)); - insn = NEXT_INSN (insn)) + FOR_BB_INSNS (bb, insn) { if (INSN_P (insn)) { @@ -5396,14 +5341,15 @@ trim_ld_motion_mems (void) else { *last = ptr->next; + htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index); free_ldst_entry (ptr); ptr = * last; } } /* Show the world what we've found. */ - if (gcse_file && pre_ldst_mems != NULL) - print_ldst_list (gcse_file); + if (dump_file && pre_ldst_mems != NULL) + print_ldst_list (dump_file); } /* This routine will take an expression which we are replacing with @@ -5436,25 +5382,26 @@ 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) continue; - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "PRE: store updated with reaching reg "); - print_rtl (gcse_file, expr->reaching_reg); - fprintf (gcse_file, ":\n "); - print_inline_rtx (gcse_file, insn, 8); - fprintf (gcse_file, "\n"); + fprintf (dump_file, "PRE: store updated with reaching reg "); + print_rtl (dump_file, expr->reaching_reg); + fprintf (dump_file, ":\n "); + print_inline_rtx (dump_file, insn, 8); + 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); + new_rtx = emit_insn_before (copy, insn); + record_one_set (REGNO (reg), new_rtx); SET_SRC (pat) = reg; + df_insn_rescan (insn); /* un-recognize this pattern since it's probably different now. */ INSN_CODE (insn) = -1; @@ -5486,10 +5433,10 @@ static int num_stores; note_stores. */ static void -reg_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, +reg_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) { - sbitmap bb_reg = data; + sbitmap bb_reg = (sbitmap) data; if (GET_CODE (dest) == SUBREG) dest = SUBREG_REG (dest); @@ -5506,10 +5453,10 @@ reg_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, note_stores. */ static void -reg_clear_last_set (rtx dest, rtx setter ATTRIBUTE_UNUSED, +reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) { - int *dead_vec = data; + int *dead_vec = (int *) data; if (GET_CODE (dest) == SUBREG) dest = SUBREG_REG (dest); @@ -5523,9 +5470,9 @@ reg_clear_last_set (rtx dest, rtx setter ATTRIBUTE_UNUSED, due to set of registers in bitmap REGS_SET. */ static bool -store_ops_ok (rtx x, int *regs_set) +store_ops_ok (const_rtx x, int *regs_set) { - rtx reg; + const_rtx reg; for (; x; x = XEXP (x, 1)) { @@ -5571,8 +5518,10 @@ extract_mentioned_regs_helper (rtx x, rtx accum) 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 (); @@ -5581,6 +5530,7 @@ extract_mentioned_regs_helper (rtx x, rtx accum) case CONST: case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case CONST_VECTOR: case SYMBOL_REF: case LABEL_REF: @@ -5677,6 +5627,14 @@ find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after) 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); @@ -5755,8 +5713,10 @@ compute_store_table (void) max_gcse_regno); sbitmap_vector_zero (reg_set_in_block, last_basic_block); pre_ldst_mems = 0; - last_set_in = xcalloc (max_gcse_regno, sizeof (int)); - already_set = xmalloc (sizeof (int) * max_gcse_regno); + 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) @@ -5764,9 +5724,7 @@ compute_store_table (void) /* First compute the registers set in this block. */ regvec = last_set_in; - for (insn = BB_HEAD (bb); - insn != NEXT_INSN (BB_END (bb)); - insn = NEXT_INSN (insn)) + FOR_BB_INSNS (bb, insn) { if (! INSN_P (insn)) continue; @@ -5789,9 +5747,7 @@ compute_store_table (void) /* Now find the stores. */ memset (already_set, 0, sizeof (int) * max_gcse_regno); regvec = already_set; - for (insn = BB_HEAD (bb); - insn != NEXT_INSN (BB_END (bb)); - insn = NEXT_INSN (insn)) + FOR_BB_INSNS (bb, insn) { if (! INSN_P (insn)) continue; @@ -5846,6 +5802,7 @@ compute_store_table (void) 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 @@ -5854,10 +5811,10 @@ compute_store_table (void) ret = enumerate_ldsts (); - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n"); - print_ldst_list (gcse_file); + fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n"); + print_ldst_list (dump_file); } free (last_set_in); @@ -5870,7 +5827,7 @@ compute_store_table (void) after the X. */ static bool -load_kills_store (rtx x, rtx store_pattern, int after) +load_kills_store (const_rtx x, const_rtx store_pattern, int after) { if (after) return anti_dependence (x, store_pattern); @@ -5885,7 +5842,7 @@ load_kills_store (rtx x, rtx store_pattern, int after) after the insn X. */ static bool -find_loads (rtx x, rtx store_pattern, int after) +find_loads (const_rtx x, const_rtx store_pattern, int after) { const char * fmt; int i, j; @@ -5917,14 +5874,47 @@ find_loads (rtx x, rtx store_pattern, int 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 it does. */ + after the insn. Return true if it does. */ static bool -store_killed_in_insn (rtx x, rtx x_regs, rtx insn, int after) +store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after) { - rtx reg, base, note; + const_rtx reg, base, note, pat; if (!INSN_P (insn)) return false; @@ -5933,7 +5923,7 @@ store_killed_in_insn (rtx x, rtx x_regs, rtx insn, int after) { /* 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)) + if (!RTL_CONST_CALL_P (insn)) return true; /* But even a const call reads its parameters. Check whether the @@ -5951,32 +5941,20 @@ store_killed_in_insn (rtx x, rtx x_regs, rtx insn, int after) return false; } - if (GET_CODE (PATTERN (insn)) == SET) + pat = PATTERN (insn); + if (GET_CODE (pat) == SET) { - rtx pat = PATTERN (insn); - 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 (SET_SRC (pat), x, after)) + 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; @@ -6002,7 +5980,7 @@ store_killed_in_insn (rtx x, rtx x_regs, rtx insn, int after) is killed, return the last insn in that it occurs in FAIL_INSN. */ static bool -store_killed_after (rtx x, rtx x_regs, rtx insn, basic_block bb, +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; @@ -6031,7 +6009,7 @@ store_killed_after (rtx x, rtx x_regs, rtx insn, basic_block bb, 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 (rtx x, rtx x_regs, rtx insn, basic_block bb, +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); @@ -6078,9 +6056,9 @@ build_store_vectors (void) are any side effects. */ if (TEST_BIT (ae_gen[bb->index], ptr->index)) { - rtx r = gen_reg_rtx (GET_MODE (ptr->pattern)); - if (gcse_file) - fprintf (gcse_file, "Removing redundant store:\n"); + rtx r = gen_reg_rtx_and_attrs (ptr->pattern); + if (dump_file) + fprintf (dump_file, "Removing redundant store:\n"); replace_store_insn (r, XEXP (st, 0), bb, ptr); continue; } @@ -6100,7 +6078,7 @@ build_store_vectors (void) transp = sbitmap_vector_alloc (last_basic_block, num_stores); sbitmap_vector_zero (transp, last_basic_block); - regs_set_in_block = xmalloc (sizeof (int) * max_gcse_regno); + regs_set_in_block = XNEWVEC (int, max_gcse_regno); FOR_EACH_BB (bb) { @@ -6125,12 +6103,12 @@ build_store_vectors (void) free (regs_set_in_block); - if (gcse_file) + if (dump_file) { - dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block); - dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block); - dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block); - dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, last_basic_block); + 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); } } @@ -6138,7 +6116,7 @@ build_store_vectors (void) the BB_HEAD if needed. */ static void -insert_insn_start_bb (rtx insn, basic_block bb) +insert_insn_start_basic_block (rtx insn, basic_block bb) { /* Insert at start of successor block. */ rtx prev = PREV_INSN (BB_HEAD (bb)); @@ -6146,8 +6124,7 @@ insert_insn_start_bb (rtx insn, basic_block bb) while (before != 0) { if (! LABEL_P (before) - && (! NOTE_P (before) - || NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK)) + && !NOTE_INSN_BASIC_BLOCK_P (before)) break; prev = before; if (prev == BB_END (bb)) @@ -6155,14 +6132,14 @@ insert_insn_start_bb (rtx insn, basic_block bb) before = NEXT_INSN (before); } - insn = emit_insn_after_noloc (insn, prev); + insn = emit_insn_after_noloc (insn, prev, bb); - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n", + fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n", bb->index); - print_inline_rtx (gcse_file, insn, 6); - fprintf (gcse_file, "\n"); + print_inline_rtx (dump_file, insn, 6); + fprintf (dump_file, "\n"); } } @@ -6212,7 +6189,7 @@ insert_store (struct ls_expr * expr, edge e) int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); RESET_BIT (pre_insert_map[index], expr->index); } - insert_insn_start_bb (insn, bb); + insert_insn_start_basic_block (insn, bb); return 0; } @@ -6222,12 +6199,12 @@ insert_store (struct ls_expr * expr, edge e) insert_insn_on_edge (insn, e); - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "STORE_MOTION insert insn on edge (%d, %d):\n", + fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n", e->src->index, e->dest->index); - print_inline_rtx (gcse_file, insn, 6); - fprintf (gcse_file, "\n"); + print_inline_rtx (dump_file, insn, 6); + fprintf (dump_file, "\n"); } return 1; @@ -6248,7 +6225,7 @@ remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr) rtx last, insn, note; rtx mem = smexpr->pattern; - stack = xmalloc (sizeof (edge_iterator) * n_basic_blocks); + stack = XNEWVEC (edge_iterator, n_basic_blocks); sp = 0; ei = ei_start (bb->succs); @@ -6297,8 +6274,8 @@ remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr) if (!note || !expr_equiv_p (XEXP (note, 0), mem)) continue; - if (gcse_file) - fprintf (gcse_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", + if (dump_file) + fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", INSN_UID (insn)); remove_note (insn, note); } @@ -6322,21 +6299,10 @@ remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr) static void replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr) { - rtx insn, mem, note, set, ptr, pair; + rtx insn, mem, note, set, ptr; mem = smexpr->pattern; insn = gen_move_insn (reg, SET_SRC (single_set (del))); - insn = emit_insn_after (insn, del); - - if (gcse_file) - { - fprintf (gcse_file, - "STORE_MOTION delete insn in BB %d:\n ", bb->index); - print_inline_rtx (gcse_file, del, 6); - fprintf (gcse_file, "\nSTORE MOTION replaced with insn:\n "); - print_inline_rtx (gcse_file, insn, 6); - fprintf (gcse_file, "\n"); - } for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1)) if (XEXP (ptr, 0) == del) @@ -6345,23 +6311,21 @@ replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr) break; } - /* Move the notes from the deleted insn to its replacement, and patch - up the LIBCALL notes. */ + /* Move the notes from the deleted insn to its replacement. */ 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) + /* 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) { - pair = XEXP (note, 0); - note = find_reg_note (pair, REG_RETVAL, NULL_RTX); - XEXP (note, 0) = insn; + 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); @@ -6381,8 +6345,8 @@ replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr) if (!note || !expr_equiv_p (XEXP (note, 0), mem)) continue; - if (gcse_file) - fprintf (gcse_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", + if (dump_file) + fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", INSN_UID (insn)); remove_note (insn, note); } @@ -6399,7 +6363,7 @@ delete_store (struct ls_expr * expr, basic_block bb) rtx reg, i, del; if (expr->reaching_reg == NULL_RTX) - expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern)); + expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern); reg = expr->reaching_reg; @@ -6453,10 +6417,10 @@ store_motion (void) struct ls_expr * ptr; int update_flow = 0; - if (gcse_file) + if (dump_file) { - fprintf (gcse_file, "before store motion\n"); - print_rtl (gcse_file, get_insns ()); + fprintf (dump_file, "before store motion\n"); + print_rtl (dump_file, get_insns ()); } init_alias_analysis (); @@ -6465,6 +6429,8 @@ store_motion (void) 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; @@ -6475,7 +6441,7 @@ store_motion (void) add_noreturn_fake_exit_edges (); connect_infinite_loops_to_exit (); - edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen, + edge_list = pre_edge_rev_lcm (num_stores, transp, ae_gen, st_antloc, ae_kill, &pre_insert_map, &pre_delete_map); @@ -6491,8 +6457,8 @@ store_motion (void) if (x >= 0) { - if (gcse_file != NULL) - fprintf (gcse_file, + 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); @@ -6522,29 +6488,26 @@ store_motion (void) /* Entry point for jump bypassing optimization pass. */ -int -bypass_jumps (FILE *file) +static int +bypass_jumps (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) + if (cfun->calls_setjmp) return 0; - /* For calling dump_foo fns from gdb. */ - debug_stderr = stderr; - gcse_file = file; - /* Identify the basic block information for this function, including successors and predecessors. */ max_gcse_regno = max_reg_num (); - if (file) - dump_flow_info (file); + 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 <= 1 || is_too_expensive (_ ("jump bypassing disabled"))) + if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 + || is_too_expensive (_ ("jump bypassing disabled"))) return 0; gcc_obstack_init (&gcse_obstack); @@ -6563,18 +6526,18 @@ bypass_jumps (FILE *file) information about memory sets when we build the hash tables. */ alloc_reg_set_mem (max_gcse_regno); - compute_sets (get_insns ()); + compute_sets (); max_gcse_regno = max_reg_num (); - alloc_gcse_mem (get_insns ()); - changed = one_cprop_pass (MAX_GCSE_PASSES + 2, 1, 1); + alloc_gcse_mem (); + changed = one_cprop_pass (MAX_GCSE_PASSES + 2, true, true); free_gcse_mem (); - if (file) + if (dump_file) { - fprintf (file, "BYPASS of %s: %d basic blocks, ", + fprintf (dump_file, "BYPASS of %s: %d basic blocks, ", current_function_name (), n_basic_blocks); - fprintf (file, "%d bytes\n\n", bytes_used); + fprintf (dump_file, "%d bytes\n\n", bytes_used); } obstack_free (&gcse_obstack, NULL); @@ -6582,7 +6545,6 @@ bypass_jumps (FILE *file) /* We are finished with alias. */ end_alias_analysis (); - allocate_reg_info (max_reg_num (), FALSE, FALSE); return changed; } @@ -6604,9 +6566,9 @@ is_too_expensive (const char *pass) graceful degradation. */ if (n_edges > 20000 + n_basic_blocks * 4) { - if (warn_disabled_optimization) - warning ("%s: %d basic blocks and %d edges/basic block", - pass, n_basic_blocks, n_edges / n_basic_blocks); + warning (OPT_Wdisabled_optimization, + "%s: %d basic blocks and %d edges/basic block", + pass, n_basic_blocks, n_edges / n_basic_blocks); return true; } @@ -6617,14 +6579,128 @@ is_too_expensive (const char *pass) * SBITMAP_SET_SIZE (max_reg_num ()) * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) { - if (warn_disabled_optimization) - warning ("%s: %d basic blocks and %d registers", - pass, n_basic_blocks, max_reg_num ()); + 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) +{ + return optimize > 0 && flag_gcse + && dbg_cnt (jump_bypass); +} + +/* Perform jump bypassing and control flow optimizations. */ +static unsigned int +rest_of_handle_jump_bypass (void) +{ + delete_unreachable_blocks (); + if (bypass_jumps ()) + { + delete_trivially_dead_insns (get_insns (), max_reg_num ()); + rebuild_jump_labels (get_insns ()); + cleanup_cfg (0); + } + return 0; +} + +struct rtl_opt_pass pass_jump_bypass = +{ + { + RTL_PASS, + "bypass", /* name */ + gate_handle_jump_bypass, /* gate */ + rest_of_handle_jump_bypass, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_BYPASS, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | + TODO_ggc_collect | TODO_verify_flow /* todo_flags_finish */ + } +}; + + +static bool +gate_handle_gcse (void) +{ + return optimize > 0 && flag_gcse + && dbg_cnt (gcse); +} + + +static unsigned int +rest_of_handle_gcse (void) +{ + 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 == 2) + { + timevar_push (TV_JUMP); + rebuild_jump_labels (get_insns ()); + cleanup_cfg (0); + timevar_pop (TV_JUMP); + } + else if (tem2 == 1) + cleanup_cfg (0); + + flag_cse_skip_blocks = save_csb; + flag_cse_follow_jumps = save_cfj; + return 0; +} + +struct rtl_opt_pass pass_gcse = +{ + { + RTL_PASS, + "gcse1", /* name */ + gate_handle_gcse, /* gate */ + rest_of_handle_gcse, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_GCSE, /* tv_id */ + 0, /* 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 */ + } +}; + #include "gt-gcse.h"