/* Global common subexpression elimination/Partial redundancy elimination
and global constant/copy propagation for GNU compiler.
Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
- 2006, 2007, 2008 Free Software Foundation, Inc.
+ 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
This file is part of GCC.
- a store to the same address as a load does not kill the load if the
source of the store is also the destination of the load. Handling this
allows more load motion, particularly out of loops.
- - ability to realloc sbitmap vectors would allow one initial computation
- of reg_set_in_block with only subsequent additions, rather than
- recomputing it for each pass
*/
We perform the following steps:
- 1) Compute basic block information.
+ 1) Compute table of places where registers are set.
- 2) Compute table of places where registers are set.
+ 2) Perform copy/constant propagation.
- 3) Perform copy/constant propagation.
-
- 4) Perform global cse using lazy code motion if not optimizing
+ 3) Perform global cse using lazy code motion if not optimizing
for size, or code hoisting if we are.
- 5) Perform another pass of copy/constant propagation.
+ 4) Perform another pass of copy/constant propagation. Try to bypass
+ conditional jumps if the condition can be computed from a value of
+ an incoming edge.
+
+ 5) Perform store motion.
Two passes of copy/constant propagation are done because the first one
enables more GCSE and the second one helps to clean up the copies that
(set (pseudo-reg) (expression)).
Function want_to_gcse_p says what these are.
+ In addition, expressions in REG_EQUAL notes are candidates for GXSE-ing.
+ This allows PRE to hoist expressions that are expressed in multiple insns,
+ such as comprex address calculations (e.g. for PIC code, or loads with a
+ high part and as lowe part).
+
PRE handles moving invariant expressions out of loops (by treating them as
partially redundant).
It was found doing copy propagation between each pass enables further
substitutions.
+ This study was done before expressions in REG_EQUAL notes were added as
+ candidate expressions for optimization, and before the GIMPLE optimizers
+ were added. Probably, multiple passes is even less efficient now than
+ at the time when the study was conducted.
+
PRE is quite expensive in complicated functions because the DFA can take
- a while to converge. Hence we only perform one pass. The parameter
- max-gcse-passes can be modified if one wants to experiment.
+ a while to converge. Hence we only perform one pass.
**********************
\f
/* GCSE global vars. */
-/* Note whether or not we should run jump optimization after gcse. We
- want to do this for two cases.
-
- * If we changed any jumps via cprop.
-
- * If we added any labels via edge splitting. */
-static int run_jump_opt_after_gcse;
+/* Set to non-zero if CSE should run after all GCSE optimizations are done. */
+int flag_rerun_cse_after_global_opts;
/* An obstack for our working variables. */
static struct obstack gcse_obstack;
/* Copy propagation hash table. */
static struct hash_table set_hash_table;
-/* Mapping of uids to cuids.
- Only real insns get cuids. */
-static int *uid_cuid;
-
-/* Highest UID in UID_CUID. */
-static int max_uid;
-
-/* Get the cuid of an insn. */
-#ifdef ENABLE_CHECKING
-#define INSN_CUID(INSN) \
- (gcc_assert (INSN_UID (INSN) <= max_uid), uid_cuid[INSN_UID (INSN)])
-#else
-#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
-#endif
-
-/* Number of cuids. */
-static int max_cuid;
-
-/* Maximum register number in function prior to doing gcse + 1.
- Registers created during this pass have regno >= max_gcse_regno.
- This is named with "gcse" to not collide with global of same name. */
-static unsigned int max_gcse_regno;
-
-/* Table of registers that are modified.
-
- For each register, each element is a list of places where the pseudo-reg
- is set.
-
- For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
- requires knowledge of which blocks kill which regs [and thus could use
- a bitmap instead of the lists `reg_set_table' uses].
-
- `reg_set_table' and could be turned into an array of bitmaps (num-bbs x
- num-regs) [however perhaps it may be useful to keep the data as is]. One
- advantage of recording things this way is that `reg_set_table' is fairly
- sparse with respect to pseudo regs but for hard regs could be fairly dense
- [relatively speaking]. And recording sets of pseudo-regs in lists speeds
- up functions like compute_transp since in the case of pseudo-regs we only
- need to iterate over the number of times a pseudo-reg is set, not over the
- number of basic blocks [clearly there is a bit of a slow down in the cases
- where a pseudo is set more than once in a block, however it is believed
- that the net effect is to speed things up]. This isn't done for hard-regs
- because recording call-clobbered hard-regs in `reg_set_table' at each
- function call can consume a fair bit of memory, and iterating over
- hard-regs stored this way in compute_transp will be more expensive. */
-
-typedef struct reg_set
-{
- /* The next setting of this register. */
- struct reg_set *next;
- /* The index of the block where it was set. */
- int bb_index;
-} reg_set;
-
-static reg_set **reg_set_table;
-
-/* Size of `reg_set_table'.
- The table starts out at max_gcse_regno + slop, and is enlarged as
- necessary. */
-static int reg_set_table_size;
-
-/* Amount to grow `reg_set_table' by when it's full. */
-#define REG_SET_TABLE_SLOP 100
-
/* This is a list of expressions which are MEMs and will be used by load
or store motion.
Load motion tracks MEMs which aren't killed by
the start of the basic block. */
static regset reg_set_bitmap;
-/* For each block, a bitmap of registers set in the block.
- This is used by compute_transp.
- It is computed during hash table computation and not by compute_sets
- as it includes registers added since the last pass (or between cprop and
- gcse) and it's currently not easy to realloc sbitmap vectors. */
-static sbitmap *reg_set_in_block;
-
/* Array, indexed by basic block number for a list of insns which modify
memory within that block. */
static rtx * modify_mem_list;
static int global_copy_prop_count;
\f
/* For available exprs */
-static sbitmap *ae_kill, *ae_gen;
+static sbitmap *ae_kill;
\f
static void compute_can_copy (void);
static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
-static void *grealloc (void *, size_t);
static void *gcse_alloc (unsigned long);
static void alloc_gcse_mem (void);
static void free_gcse_mem (void);
-static void alloc_reg_set_mem (int);
-static void free_reg_set_mem (void);
-static void record_one_set (int, rtx);
-static void record_set_info (rtx, const_rtx, void *);
-static void compute_sets (void);
static void hash_scan_insn (rtx, struct hash_table *);
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 (const_rtx);
static int oprs_unchanged_p (const_rtx, const_rtx, int);
static int oprs_anticipatable_p (const_rtx, const_rtx);
static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
static int load_killed_in_block_p (const_basic_block, int, const_rtx, int);
static void canon_list_insert (rtx, const_rtx, void *);
-static int cprop_insn (rtx, int);
-static int cprop (int);
+static int cprop_insn (rtx);
static void find_implicit_sets (void);
-static int one_cprop_pass (int, bool, bool);
-static bool constprop_register (rtx, rtx, rtx, bool);
+static int one_cprop_pass (void);
+static bool constprop_register (rtx, rtx, rtx);
static struct expr *find_bypass_set (int, int);
static bool reg_killed_on_edge (const_rtx, const_edge);
static int bypass_block (basic_block, rtx, rtx);
static void pre_insert_copies (void);
static int pre_delete (void);
static int pre_gcse (void);
-static int one_pre_gcse_pass (int);
+static int one_pre_gcse_pass (void);
static void add_label_notes (rtx, rtx);
static void alloc_code_hoist_mem (int, int);
static void free_code_hoist_mem (void);
static void compute_code_hoist_vbeinout (void);
static void compute_code_hoist_data (void);
static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *);
-static void hoist_code (void);
+static int hoist_code (void);
static int one_code_hoisting_pass (void);
static rtx process_insert_insn (struct expr *);
static int pre_edge_insert (struct edge_list *, struct expr **);
static void free_ldst_mems (void);
static void print_ldst_list (FILE *);
static struct ls_expr * find_rtx_in_ldst (rtx);
-static int enumerate_ldsts (void);
static inline struct ls_expr * first_ls_expr (void);
static inline struct ls_expr * next_ls_expr (struct ls_expr *);
static int simple_mem (const_rtx);
static void compute_ld_motion_mems (void);
static void trim_ld_motion_mems (void);
static void update_ld_motion_stores (struct expr *);
-static void reg_set_info (rtx, const_rtx, void *);
-static void reg_clear_last_set (rtx, const_rtx, void *);
-static bool store_ops_ok (const_rtx, int *);
-static rtx extract_mentioned_regs (rtx);
-static rtx extract_mentioned_regs_helper (rtx, rtx);
-static void find_moveable_store (rtx, int *, int *);
-static int compute_store_table (void);
-static bool load_kills_store (const_rtx, const_rtx, int);
-static bool find_loads (const_rtx, const_rtx, int);
-static bool store_killed_in_insn (const_rtx, const_rtx, const_rtx, int);
-static bool store_killed_after (const_rtx, const_rtx, const_rtx, const_basic_block, int *, rtx *);
-static bool store_killed_before (const_rtx, const_rtx, const_rtx, const_basic_block, int *);
-static void build_store_vectors (void);
-static void insert_insn_start_basic_block (rtx, basic_block);
-static int insert_store (struct ls_expr *, edge);
-static void remove_reachable_equiv_notes (basic_block, struct ls_expr *);
-static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *);
-static void delete_store (struct ls_expr *, basic_block);
-static void free_store_memory (void);
-static void store_motion (void);
static void free_insn_expr_list_list (rtx *);
static void clear_modify_mem_tables (void);
static void free_modify_mem_tables (void);
static rtx gcse_emit_move_after (rtx, rtx, rtx);
static void local_cprop_find_used_regs (rtx *, void *);
-static bool do_local_cprop (rtx, rtx, bool);
-static void local_cprop_pass (bool);
+static bool do_local_cprop (rtx, rtx);
+static int local_cprop_pass (void);
static bool is_too_expensive (const char *);
#define GNEW(T) ((T *) gmalloc (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)))
\f
-
-/* Entry point for global common subexpression elimination.
- F is the first instruction in the function. Return nonzero if a
- change is mode. */
-
-static int
-gcse_main (rtx f ATTRIBUTE_UNUSED)
-{
- int changed, pass;
- /* Bytes used at start of pass. */
- int initial_bytes_used;
- /* Maximum number of bytes used by a pass. */
- int max_pass_bytes;
- /* Point to release obstack data from for each pass. */
- char *gcse_obstack_bottom;
-
- /* We do not construct an accurate cfg in functions which call
- setjmp, so just punt to be safe. */
- if (cfun->calls_setjmp)
- return 0;
-
- /* Assume that we do not need to run jump optimizations after gcse. */
- run_jump_opt_after_gcse = 0;
-
- /* Identify the basic block information for this function, including
- successors and predecessors. */
- max_gcse_regno = max_reg_num ();
-
- df_note_add_problem ();
- df_analyze ();
-
- if (dump_file)
- dump_flow_info (dump_file, dump_flags);
-
- /* Return if there's nothing to do, or it is too expensive. */
- if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
- || is_too_expensive (_("GCSE disabled")))
- return 0;
-
- gcc_obstack_init (&gcse_obstack);
- bytes_used = 0;
-
- /* We need alias. */
- init_alias_analysis ();
- /* Record where pseudo-registers are set. This data is kept accurate
- during each pass. ??? We could also record hard-reg information here
- [since it's unchanging], however it is currently done during hash table
- computation.
-
- It may be tempting to compute MEM set information here too, but MEM sets
- will be subject to code motion one day and thus we need to compute
- information about memory sets when we build the hash tables. */
-
- alloc_reg_set_mem (max_gcse_regno);
- compute_sets ();
-
- pass = 0;
- initial_bytes_used = bytes_used;
- max_pass_bytes = 0;
- gcse_obstack_bottom = GOBNEWVAR (char, 1);
- changed = 1;
- while (changed && pass < MAX_GCSE_PASSES)
- {
- changed = 0;
- if (dump_file)
- fprintf (dump_file, "GCSE pass %d\n\n", pass + 1);
-
- /* Initialize bytes_used to the space for the pred/succ lists,
- and the reg_set_table data. */
- bytes_used = initial_bytes_used;
-
- /* Each pass may create new registers, so recalculate each time. */
- max_gcse_regno = max_reg_num ();
-
- alloc_gcse_mem ();
-
- /* Don't allow constant propagation to modify jumps
- during this pass. */
- if (dbg_cnt (cprop1))
- {
- timevar_push (TV_CPROP1);
- changed = one_cprop_pass (pass + 1, false, false);
- timevar_pop (TV_CPROP1);
- }
-
- if (optimize_function_for_speed_p (cfun))
- {
- timevar_push (TV_PRE);
- changed |= one_pre_gcse_pass (pass + 1);
- /* We may have just created new basic blocks. Release and
- recompute various things which are sized on the number of
- basic blocks. */
- if (changed)
- {
- free_modify_mem_tables ();
- modify_mem_list = 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 ();
- run_jump_opt_after_gcse = 1;
- timevar_pop (TV_PRE);
- }
-
- if (max_pass_bytes < bytes_used)
- max_pass_bytes = bytes_used;
-
- /* Free up memory, then reallocate for code hoisting. We can
- not re-use the existing allocated memory because the tables
- will not have info for the insns or registers created by
- partial redundancy elimination. */
- free_gcse_mem ();
-
- /* It does not make sense to run code hoisting unless we are optimizing
- for code size -- it rarely makes programs faster, and can make
- them bigger if we did partial redundancy elimination (when optimizing
- for space, we don't run the partial redundancy algorithms). */
- if (optimize_function_for_size_p (cfun))
- {
- timevar_push (TV_HOIST);
- max_gcse_regno = max_reg_num ();
- alloc_gcse_mem ();
- changed |= one_code_hoisting_pass ();
- free_gcse_mem ();
-
- if (max_pass_bytes < bytes_used)
- max_pass_bytes = bytes_used;
- timevar_pop (TV_HOIST);
- }
-
- if (dump_file)
- {
- fprintf (dump_file, "\n");
- fflush (dump_file);
- }
-
- obstack_free (&gcse_obstack, gcse_obstack_bottom);
- pass++;
- }
-
- /* Do one last pass of copy propagation, including cprop into
- conditional jumps. */
-
- if (dbg_cnt (cprop2))
- {
- max_gcse_regno = max_reg_num ();
- alloc_gcse_mem ();
-
- /* This time, go ahead and allow cprop to alter jumps. */
- timevar_push (TV_CPROP2);
- one_cprop_pass (pass + 1, true, true);
- timevar_pop (TV_CPROP2);
- free_gcse_mem ();
- }
-
- if (dump_file)
- {
- fprintf (dump_file, "GCSE of %s: %d basic blocks, ",
- current_function_name (), n_basic_blocks);
- fprintf (dump_file, "%d pass%s, %d bytes\n\n",
- pass, pass > 1 ? "es" : "", max_pass_bytes);
- }
-
- obstack_free (&gcse_obstack, NULL);
- free_reg_set_mem ();
-
- /* We are finished with alias. */
- end_alias_analysis ();
-
- if (optimize_function_for_speed_p (cfun) && flag_gcse_sm)
- {
- timevar_push (TV_LSM);
- store_motion ();
- timevar_pop (TV_LSM);
- }
-
- /* Record where pseudo-registers are set. */
- return run_jump_opt_after_gcse;
-}
-\f
/* Misc. utilities. */
/* Nonzero for each mode that supports (set (reg) (reg)).
return can_copy[mode] != 0;
}
+
\f
/* Cover function to xmalloc to record bytes allocated. */
return xcalloc (nelem, elsize);
}
-/* Cover function to xrealloc.
- We don't record the additional size since we don't know it.
- It won't affect memory usage stats much anyway. */
-
-static void *
-grealloc (void *ptr, size_t size)
-{
- return xrealloc (ptr, size);
-}
-
/* Cover function to obstack_alloc. */
static void *
return obstack_alloc (&gcse_obstack, size);
}
-/* Allocate memory for the cuid mapping array,
- and reg/memory set tracking tables.
-
+/* Allocate memory for the reg/memory set tracking tables.
This is called at the start of each pass. */
static void
alloc_gcse_mem (void)
{
- int i;
- basic_block bb;
- rtx insn;
-
- /* Find the largest UID and create a mapping from UIDs to CUIDs.
- CUIDs are like UIDs except they increase monotonically, have no gaps,
- and only apply to real insns.
- (Actually, there are gaps, for insn that are not inside a basic block.
- but we should never see those anyway, so this is OK.) */
-
- max_uid = get_max_uid ();
- uid_cuid = 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;
-
/* Allocate vars to track sets of regs. */
reg_set_bitmap = BITMAP_ALLOC (NULL);
- /* Allocate vars to track sets of regs, memory per block. */
- reg_set_in_block = sbitmap_vector_alloc (last_basic_block, max_gcse_regno);
/* Allocate array to keep a list of insns which modify memory in each
basic block. */
modify_mem_list = GCNEWVEC (rtx, last_basic_block);
static void
free_gcse_mem (void)
{
- free (uid_cuid);
-
- BITMAP_FREE (reg_set_bitmap);
-
- sbitmap_vector_free (reg_set_in_block);
free_modify_mem_tables ();
BITMAP_FREE (modify_mem_list_set);
BITMAP_FREE (blocks_with_calls);
}
}
\f
-/* Register set information.
-
- `reg_set_table' records where each register is set or otherwise
- modified. */
-
-static struct obstack reg_set_obstack;
-
-static void
-alloc_reg_set_mem (int n_regs)
-{
- reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
- reg_set_table = GCNEWVEC (struct reg_set *, reg_set_table_size);
-
- gcc_obstack_init (®_set_obstack);
-}
-
-static void
-free_reg_set_mem (void)
-{
- free (reg_set_table);
- obstack_free (®_set_obstack, NULL);
-}
-
-/* Record REGNO in the reg_set table. */
-
-static void
-record_one_set (int regno, rtx insn)
-{
- /* Allocate a new reg_set element and link it onto the list. */
- struct reg_set *new_reg_info;
-
- /* If the table isn't big enough, enlarge it. */
- if (regno >= reg_set_table_size)
- {
- int new_size = regno + REG_SET_TABLE_SLOP;
-
- reg_set_table = 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 = XOBNEW (®_set_obstack, struct reg_set);
- bytes_used += sizeof (struct reg_set);
- new_reg_info->bb_index = BLOCK_NUM (insn);
- new_reg_info->next = reg_set_table[regno];
- reg_set_table[regno] = new_reg_info;
-}
-
-/* Called from compute_sets via note_stores to handle one SET or CLOBBER in
- an insn. The DATA is really the instruction in which the SET is
- occurring. */
-
-static void
-record_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
-{
- rtx record_set_insn = (rtx) data;
-
- if (REG_P (dest) && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
- record_one_set (REGNO (dest), record_set_insn);
-}
-
-/* Scan the function and record each set of each pseudo-register.
-
- This is called once, at the start of the gcse pass. See the comments for
- `reg_set_table' for further documentation. */
-
-static void
-compute_sets (void)
-{
- basic_block bb;
- rtx insn;
-
- FOR_EACH_BB (bb)
- FOR_BB_INSNS (bb, insn)
- if (INSN_P (insn))
- note_stores (PATTERN (insn), record_set_info, insn);
-}
-\f
/* Hash table support. */
struct reg_avail_info
return 0;
default:
- return can_assign_to_reg_p (x);
+ return can_assign_to_reg_without_clobbers_p (x);
}
}
-/* Used internally by can_assign_to_reg_p. */
+/* Used internally by can_assign_to_reg_without_clobbers_p. */
static GTY(()) rtx test_insn;
-/* Return true if we can assign X to a pseudo register. */
+/* Return true if we can assign X to a pseudo register such that the
+ resulting insn does not result in clobbering a hard register as a
+ side-effect.
+ This function is typically used by code motion passes, to verify
+ that it is safe to insert an insn without worrying about clobbering
+ maybe live hard regs. */
-static bool
-can_assign_to_reg_p (rtx x)
+bool
+can_assign_to_reg_without_clobbers_p (rtx x)
{
int num_clobbers = 0;
int icode;
if (info->last_bb != current_bb)
return 1;
if (avail_p)
- return info->last_set < INSN_CUID (insn);
+ return info->last_set < DF_INSN_LUID (insn);
else
- return info->first_set >= INSN_CUID (insn);
+ return info->first_set >= DF_INSN_LUID (insn);
}
case MEM:
- if (load_killed_in_block_p (current_bb, INSN_CUID (insn),
+ if (load_killed_in_block_p (current_bb, DF_INSN_LUID (insn),
x, avail_p))
return 0;
else
}
/* Return nonzero if the expression in X (a memory reference) is killed
- in block BB before or after the insn with the CUID in UID_LIMIT.
+ in block BB before or after the insn with the LUID in UID_LIMIT.
AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
before UID_LIMIT.
rtx setter;
/* Ignore entries in the list that do not apply. */
if ((avail_p
- && INSN_CUID (XEXP (list_entry, 0)) < uid_limit)
+ && DF_INSN_LUID (XEXP (list_entry, 0)) < uid_limit)
|| (! avail_p
- && INSN_CUID (XEXP (list_entry, 0)) > uid_limit))
+ && DF_INSN_LUID (XEXP (list_entry, 0)) > uid_limit))
{
list_entry = XEXP (list_entry, 1);
continue;
/* First occurrence of this expression in this basic block. */
cur_occr = GOBNEW (struct occr);
bytes_used += sizeof (struct occr);
-
- cur_occr->insn = insn;
- cur_occr->next = cur_expr->avail_occr;
- cur_occr->deleted_p = 0;
- cur_expr->avail_occr = cur_occr;
+ cur_occr->insn = insn;
+ cur_occr->next = cur_expr->avail_occr;
+ cur_occr->deleted_p = 0;
+ cur_expr->avail_occr = cur_occr;
}
}
&& ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
return true;
- return CONSTANT_P (x);
+ /* Since X might be inserted more than once we have to take care that it
+ is sharable. */
+ return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
}
/* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
is set and is used to compute "availability".
last_bb records the block for which first_set and last_set are
- valid, as a quick test to invalidate them.
-
- reg_set_in_block records whether the register is set in the block
- and is used to compute "transparency". */
+ valid, as a quick test to invalidate them. */
static void
record_last_reg_set_info (rtx insn, int regno)
{
struct reg_avail_info *info = ®_avail_info[regno];
- int cuid = INSN_CUID (insn);
+ int luid = DF_INSN_LUID (insn);
- info->last_set = cuid;
+ info->last_set = luid;
if (info->last_bb != current_bb)
{
info->last_bb = current_bb;
- info->first_set = cuid;
- SET_BIT (reg_set_in_block[current_bb->index], regno);
+ info->first_set = luid;
}
}
static void
compute_hash_table_work (struct hash_table *table)
{
- unsigned int i;
-
- /* While we compute the hash table we also compute a bit array of which
- registers are set in which blocks.
- ??? This isn't needed during const/copy propagation, but it's cheap to
- compute. Later. */
- sbitmap_vector_zero (reg_set_in_block, last_basic_block);
+ int i;
/* re-Cache any INSN_LIST nodes we have allocated. */
clear_modify_mem_tables ();
/* Some working arrays used to track first and last set in each block. */
- reg_avail_info = GNEWVEC (struct reg_avail_info, max_gcse_regno);
+ reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
- for (i = 0; i < max_gcse_regno; ++i)
+ for (i = 0; i < max_reg_num (); ++i)
reg_avail_info[i].last_bb = NULL;
FOR_EACH_BB (current_bb)
unsigned int regno;
/* First pass over the instructions records information used to
- determine when registers and memory are first and last set.
- ??? hard-reg reg_set_in_block computation
- could be moved to compute_sets since they currently don't change. */
-
+ determine when registers and memory are first and last set. */
FOR_BB_INSNS (current_bb, insn)
{
if (! INSN_P (insn))
case MEM:
if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
- INSN_CUID (insn), x, 0))
+ DF_INSN_LUID (insn), x, 0))
return 0;
else
return oprs_not_set_p (XEXP (x, 0), insn);
compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p)
{
int i, j;
- basic_block bb;
enum rtx_code code;
- reg_set *r;
const char *fmt;
/* repeat is used to turn tail-recursion into iteration since GCC
case REG:
if (set_p)
{
- if (REGNO (x) < FIRST_PSEUDO_REGISTER)
- {
- FOR_EACH_BB (bb)
- if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
- SET_BIT (bmap[bb->index], indx);
- }
- else
- {
- for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
- SET_BIT (bmap[r->bb_index], indx);
- }
+ df_ref def;
+ for (def = DF_REG_DEF_CHAIN (REGNO (x));
+ def;
+ def = DF_REF_NEXT_REG (def))
+ SET_BIT (bmap[DF_REF_BB (def)->index], indx);
}
else
{
- if (REGNO (x) < FIRST_PSEUDO_REGISTER)
- {
- FOR_EACH_BB (bb)
- if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
- RESET_BIT (bmap[bb->index], indx);
- }
- else
- {
- for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
- RESET_BIT (bmap[r->bb_index], indx);
- }
+ df_ref def;
+ for (def = DF_REG_DEF_CHAIN (REGNO (x));
+ def;
+ def = DF_REF_NEXT_REG (def))
+ RESET_BIT (bmap[DF_REF_BB (def)->index], indx);
}
return;
dest_addr = XEXP (list_entry, 0);
if (canon_true_dependence (dest, GET_MODE (dest), dest_addr,
- x, rtx_addr_varies_p))
+ x, NULL_RTX, rtx_addr_varies_p))
{
if (set_p)
SET_BIT (bmap[bb_index], indx);
delete_insn (setcc);
#endif
- run_jump_opt_after_gcse = 1;
-
global_const_prop_count++;
if (dump_file != NULL)
{
}
static bool
-constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps)
+constprop_register (rtx insn, rtx from, rtx to)
{
rtx sset;
/* Check for reg or cc0 setting instructions followed by
conditional branch instructions first. */
- if (alter_jumps
- && (sset = single_set (insn)) != NULL
+ if ((sset = single_set (insn)) != NULL
&& NEXT_INSN (insn)
&& any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
{
Right now the insn in question must look like
(set (pc) (if_then_else ...)) */
- else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
+ else if (any_condjump_p (insn) && onlyjump_p (insn))
return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
return 0;
}
The result is nonzero if a change was made. */
static int
-cprop_insn (rtx insn, int alter_jumps)
+cprop_insn (rtx insn)
{
struct reg_use *reg_used;
int changed = 0;
rtx pat, src;
struct expr *set;
- /* Ignore registers created by GCSE.
- We do this because ... */
- if (regno >= max_gcse_regno)
- continue;
-
/* If the register has already been set in this block, there's
nothing we can do. */
if (! oprs_not_set_p (reg_used->reg_rtx, insn))
/* Constant propagation. */
if (gcse_constant_p (src))
{
- if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
+ if (constprop_register (insn, reg_used->reg_rtx, src))
{
changed = 1;
global_const_prop_count++;
find_used_regs (xptr, data);
}
-/* Try to perform local const/copy propagation on X in INSN.
- If ALTER_JUMPS is false, changing jump insns is not allowed. */
+/* Try to perform local const/copy propagation on X in INSN. */
static bool
-do_local_cprop (rtx x, rtx insn, bool alter_jumps)
+do_local_cprop (rtx x, rtx insn)
{
rtx newreg = NULL, newcnst = NULL;
|| ! MEM_P (XEXP (note, 0))))
newreg = this_rtx;
}
- if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
+ if (newcnst && constprop_register (insn, x, newcnst))
{
if (dump_file != NULL)
{
return false;
}
-/* 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. */
+/* Do local const/copy propagation (i.e. within each basic block). */
-static void
-local_cprop_pass (bool alter_jumps)
+static int
+local_cprop_pass (void)
{
basic_block bb;
rtx insn;
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))
+ if (do_local_cprop (reg_used->reg_rtx, insn))
{
changed = true;
break;
cselib_finish ();
- /* Global analysis may get into infinite loops for unreachable blocks. */
- if (changed && alter_jumps)
- {
- delete_unreachable_blocks ();
- free_reg_set_mem ();
- alloc_reg_set_mem (max_reg_num ());
- compute_sets ();
- }
-}
-
-/* Forward propagate copies. This includes copies and constants. Return
- nonzero if a change was made. */
-
-static int
-cprop (int alter_jumps)
-{
- int changed;
- basic_block bb;
- rtx insn;
-
- /* Note we start at block 1. */
- if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
- {
- if (dump_file != NULL)
- fprintf (dump_file, "\n");
- return 0;
- }
-
- changed = 0;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
- {
- /* Reset tables used to keep track of what's still valid [since the
- start of the block]. */
- reset_opr_set_tables ();
-
- FOR_BB_INSNS (bb, insn)
- if (INSN_P (insn))
- {
- changed |= cprop_insn (insn, alter_jumps);
-
- /* Keep track of everything modified by this insn. */
- /* ??? Need to be careful w.r.t. mods done to INSN. Don't
- call mark_oprs_set if we turned the insn into a NOTE. */
- if (! NOTE_P (insn))
- mark_oprs_set (insn);
- }
- }
-
- if (dump_file != NULL)
- fprintf (dump_file, "\n");
-
return changed;
}
following "if (x == 2)", the then branch may be optimized as though the
conditional performed an "explicit set", in this example, "x = 2". This
function records the set patterns that are implicit at the start of each
- basic block. */
+ basic block.
+
+ FIXME: This would be more effective if critical edges are pre-split. As
+ it is now, we can't record implicit sets for blocks that have
+ critical successor edges. This results in missed optimizations
+ and in more (unnecessary) work in cfgcleanup.c:thread_jump(). */
static void
find_implicit_sets (void)
dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
: FALLTHRU_EDGE (bb)->dest;
- if (dest && single_pred_p (dest)
+ if (dest
+ /* Record nothing for a critical edge. */
+ && single_pred_p (dest)
&& dest != EXIT_BLOCK_PTR)
{
new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
fprintf (dump_file, "Found %d implicit sets\n", count);
}
-/* Perform one copy/constant propagation pass.
- PASS is the pass count. If CPROP_JUMPS is true, perform constant
- propagation into conditional jumps. If BYPASS_JUMPS is true,
- perform conditional jump bypassing optimizations. */
-
-static int
-one_cprop_pass (int pass, bool cprop_jumps, bool bypass_jumps)
-{
- int changed = 0;
-
- global_const_prop_count = local_const_prop_count = 0;
- global_copy_prop_count = local_copy_prop_count = 0;
-
- if (cprop_jumps)
- local_cprop_pass (cprop_jumps);
-
- /* Determine implicit sets. */
- implicit_sets = XCNEWVEC (rtx, last_basic_block);
- find_implicit_sets ();
-
- alloc_hash_table (max_cuid, &set_hash_table, 1);
- compute_hash_table (&set_hash_table);
-
- /* Free implicit_sets before peak usage. */
- free (implicit_sets);
- implicit_sets = NULL;
-
- if (dump_file)
- dump_hash_table (dump_file, "SET", &set_hash_table);
- if (set_hash_table.n_elems > 0)
- {
- alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
- compute_cprop_data ();
- changed = cprop (cprop_jumps);
- if (bypass_jumps)
- changed |= bypass_conditional_jumps ();
- free_cprop_mem ();
- }
-
- free_hash_table (&set_hash_table);
-
- if (dump_file)
- {
- fprintf (dump_file, "CPROP of %s, pass %d: %d bytes needed, ",
- current_function_name (), pass, bytes_used);
- fprintf (dump_file, "%d local const props, %d local copy props, ",
- local_const_prop_count, local_copy_prop_count);
- fprintf (dump_file, "%d global const props, %d global copy props\n\n",
- global_const_prop_count, global_copy_prop_count);
- }
- /* Global analysis may get into infinite loops for unreachable blocks. */
- if (changed && cprop_jumps)
- delete_unreachable_blocks ();
-
- return changed;
-}
-\f
/* Bypass conditional jumps. */
/* The value of last_basic_block at the beginning of the jump_bypass
struct expr *set;
rtx src, new_rtx;
- if (regno >= max_gcse_regno)
- continue;
-
set = find_bypass_set (regno, e->src->index);
if (! set)
/* Contains the edge_list returned by pre_edge_lcm. */
static struct edge_list *edge_list;
-/* Redundant insns. */
-static sbitmap pre_redundant_insns;
-
/* Allocate vars used for PRE analysis. */
static void
while (1)
{
if (INSN_P (pat))
- {
- add_label_notes (PATTERN (pat), new_insn);
- note_stores (PATTERN (pat), record_set_info, pat);
- }
+ add_label_notes (PATTERN (pat), new_insn);
if (pat == pat_end)
break;
pat = NEXT_INSN (pat);
if (dump_file)
{
- fprintf (dump_file, "PRE/HOIST: edge (%d,%d), ",
+ fprintf (dump_file, "PRE: edge (%d,%d), ",
bb->index,
INDEX_EDGE_SUCC_BB (edge_list, e)->index);
fprintf (dump_file, "copy expression %d\n",
{
new_insn = gen_move_insn (old_reg, reg);
new_insn = emit_insn_after (new_insn, insn);
-
- /* Keep register set table up to date. */
- record_one_set (regno, insn);
}
else
{
new_insn = gen_move_insn (reg, old_reg);
new_insn = emit_insn_after (new_insn, insn);
-
- /* Keep register set table up to date. */
- record_one_set (regno, new_insn);
}
}
else /* This is possible only in case of a store to memory. */
new_insn = emit_insn_before (new_insn, insn);
else
new_insn = emit_insn_after (new_insn, insn);
-
- /* Keep register set table up to date. */
- record_one_set (regno, new_insn);
}
gcse_create_count++;
continue;
/* Don't handle this one if it's a redundant one. */
- if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
+ if (INSN_DELETED_P (insn))
continue;
/* Or if the expression doesn't reach the deleted one. */
gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
delete_insn (insn);
occr->deleted_p = 1;
- SET_BIT (pre_redundant_insns, INSN_CUID (insn));
changed = 1;
gcse_subst_count++;
for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
index_map[expr->bitmap_index] = expr;
- /* Reset bitmap used to track which insns are redundant. */
- pre_redundant_insns = sbitmap_alloc (max_cuid);
- sbitmap_zero (pre_redundant_insns);
-
/* Delete the redundant insns first so that
- we know what register to use for the new insns and for the other
ones with reaching expressions
}
free (index_map);
- sbitmap_free (pre_redundant_insns);
return changed;
}
Return nonzero if a change was made. */
static int
-one_pre_gcse_pass (int pass)
+one_pre_gcse_pass (void)
{
int changed = 0;
gcse_subst_count = 0;
gcse_create_count = 0;
- alloc_hash_table (max_cuid, &expr_hash_table, 0);
- add_noreturn_fake_exit_edges ();
- if (flag_gcse_lm)
- compute_ld_motion_mems ();
-
- compute_hash_table (&expr_hash_table);
+ /* Return if there's nothing to do, or it is too expensive. */
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
+ || is_too_expensive (_("PRE disabled")))
+ return 0;
+
+ /* We need alias. */
+ init_alias_analysis ();
+
+ bytes_used = 0;
+ gcc_obstack_init (&gcse_obstack);
+ alloc_gcse_mem ();
+
+ alloc_hash_table (get_max_uid (), &expr_hash_table, 0);
+ add_noreturn_fake_exit_edges ();
+ if (flag_gcse_lm)
+ compute_ld_motion_mems ();
+
+ compute_hash_table (&expr_hash_table);
trim_ld_motion_mems ();
if (dump_file)
dump_hash_table (dump_file, "Expression", &expr_hash_table);
remove_fake_exit_edges ();
free_hash_table (&expr_hash_table);
+ free_gcse_mem ();
+ obstack_free (&gcse_obstack, NULL);
+
+ /* We are finished with alias. */
+ end_alias_analysis ();
+
if (dump_file)
{
- fprintf (dump_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
- current_function_name (), pass, bytes_used);
+ fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
+ current_function_name (), n_basic_blocks, bytes_used);
fprintf (dump_file, "%d substs, %d insns created\n",
gcse_subst_count, gcse_create_count);
}
\f
/* Actually perform code hoisting. */
-static void
+static int
hoist_code (void)
{
basic_block bb, dominated;
unsigned int i,j;
struct expr **index_map;
struct expr *expr;
+ int changed = 0;
sbitmap_vector_zero (hoist_exprs, last_basic_block);
gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
delete_insn (insn);
occr->deleted_p = 1;
+ changed = 1;
+ gcse_subst_count++;
+
if (!insn_inserted_p)
{
insert_insn_end_basic_block (index_map[i], bb, 0);
}
free (index_map);
+
+ return changed;
}
/* Top level routine to perform one code hoisting (aka unification) pass
{
int changed = 0;
- alloc_hash_table (max_cuid, &expr_hash_table, 0);
+ gcse_subst_count = 0;
+ gcse_create_count = 0;
+
+ /* Return if there's nothing to do, or it is too expensive. */
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
+ || is_too_expensive (_("GCSE disabled")))
+ return 0;
+
+ /* We need alias. */
+ init_alias_analysis ();
+
+ bytes_used = 0;
+ gcc_obstack_init (&gcse_obstack);
+ alloc_gcse_mem ();
+
+ alloc_hash_table (get_max_uid (), &expr_hash_table, 0);
compute_hash_table (&expr_hash_table);
if (dump_file)
dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
{
alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
compute_code_hoist_data ();
- hoist_code ();
+ changed = hoist_code ();
free_code_hoist_mem ();
}
free_hash_table (&expr_hash_table);
+ free_gcse_mem ();
+ obstack_free (&gcse_obstack, NULL);
+
+ /* We are finished with alias. */
+ end_alias_analysis ();
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ",
+ current_function_name (), n_basic_blocks, bytes_used);
+ fprintf (dump_file, "%d substs, %d insns created\n",
+ gcse_subst_count, gcse_create_count);
+ }
return changed;
}
return (struct ls_expr *) *slot;
}
-/* Assign each element of the list of mems a monotonically increasing value. */
-
-static int
-enumerate_ldsts (void)
-{
- struct ls_expr * ptr;
- int n = 0;
-
- for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
- ptr->index = n++;
-
- return n;
-}
-
/* Return first item in the list. */
static inline struct ls_expr *
&& GET_CODE (src) != ASM_OPERANDS
/* Check for REG manually since want_to_gcse_p
returns 0 for all REGs. */
- && can_assign_to_reg_p (src))
+ && can_assign_to_reg_without_clobbers_p (src))
ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
else
ptr->invalid = 1;
fprintf (dump_file, "\n");
}
- copy = gen_move_insn ( reg, copy_rtx (SET_SRC (pat)));
+ copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
new_rtx = emit_insn_before (copy, insn);
- record_one_set (REGNO (reg), new_rtx);
SET_SRC (pat) = reg;
df_insn_rescan (insn);
}
}
\f
-/* Store motion code. */
-
-#define ANTIC_STORE_LIST(x) ((x)->loads)
-#define AVAIL_STORE_LIST(x) ((x)->stores)
-#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
-
-/* This is used to communicate the target bitvector we want to use in the
- reg_set_info routine when called via the note_stores mechanism. */
-static int * regvec;
-
-/* And current insn, for the same routine. */
-static rtx compute_store_table_current_insn;
-
-/* Used in computing the reverse edge graph bit vectors. */
-static sbitmap * st_antloc;
-
-/* Global holding the number of store expressions we are dealing with. */
-static int num_stores;
-
-/* Checks to set if we need to mark a register set. Called from
- note_stores. */
+/* Return true if the graph is too expensive to optimize. PASS is the
+ optimization about to be performed. */
-static void
-reg_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
- void *data)
+static bool
+is_too_expensive (const char *pass)
{
- sbitmap bb_reg = (sbitmap) data;
+ /* Trying to perform global optimizations on flow graphs which have
+ a high connectivity will take a long time and is unlikely to be
+ particularly useful.
- if (GET_CODE (dest) == SUBREG)
- dest = SUBREG_REG (dest);
+ In normal circumstances a cfg should have about twice as many
+ edges as blocks. But we do not want to punish small functions
+ which have a couple switch statements. Rather than simply
+ threshold the number of blocks, uses something with a more
+ graceful degradation. */
+ if (n_edges > 20000 + n_basic_blocks * 4)
+ {
+ warning (OPT_Wdisabled_optimization,
+ "%s: %d basic blocks and %d edges/basic block",
+ pass, n_basic_blocks, n_edges / n_basic_blocks);
- if (REG_P (dest))
+ return true;
+ }
+
+ /* If allocating memory for the cprop bitmap would take up too much
+ storage it's better just to disable the optimization. */
+ if ((n_basic_blocks
+ * SBITMAP_SET_SIZE (max_reg_num ())
+ * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
{
- regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
- if (bb_reg)
- SET_BIT (bb_reg, REGNO (dest));
+ warning (OPT_Wdisabled_optimization,
+ "%s: %d basic blocks and %d registers",
+ pass, n_basic_blocks, max_reg_num ());
+
+ return true;
}
+
+ return false;
}
-/* Clear any mark that says that this insn sets dest. Called from
- note_stores. */
+\f
+/* Main function for the CPROP pass. */
-static void
-reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
- void *data)
+static int
+one_cprop_pass (void)
{
- int *dead_vec = (int *) data;
-
- if (GET_CODE (dest) == SUBREG)
- dest = SUBREG_REG (dest);
+ int changed = 0;
- if (REG_P (dest) &&
- dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn))
- dead_vec[REGNO (dest)] = 0;
-}
+ /* Return if there's nothing to do, or it is too expensive. */
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
+ || is_too_expensive (_ ("const/copy propagation disabled")))
+ return 0;
-/* Return zero if some of the registers in list X are killed
- due to set of registers in bitmap REGS_SET. */
+ global_const_prop_count = local_const_prop_count = 0;
+ global_copy_prop_count = local_copy_prop_count = 0;
-static bool
-store_ops_ok (const_rtx x, int *regs_set)
-{
- const_rtx reg;
+ bytes_used = 0;
+ gcc_obstack_init (&gcse_obstack);
+ alloc_gcse_mem ();
- for (; x; x = XEXP (x, 1))
+ /* Do a local const/copy propagation pass first. The global pass
+ only handles global opportunities.
+ If the local pass changes something, remove any unreachable blocks
+ because the CPROP global dataflow analysis may get into infinite
+ loops for CFGs with unreachable blocks.
+
+ FIXME: This local pass should not be necessary after CSE (but for
+ some reason it still is). It is also (proven) not necessary
+ to run the local pass right after FWPWOP.
+
+ FIXME: The global analysis would not get into infinite loops if it
+ would use the DF solver (via df_simple_dataflow) instead of
+ the solver implemented in this file. */
+ if (local_cprop_pass ())
{
- reg = XEXP (x, 0);
- if (regs_set[REGNO(reg)])
- return false;
+ delete_unreachable_blocks ();
+ df_analyze ();
}
- return true;
-}
-
-/* Returns a list of registers mentioned in X. */
-static rtx
-extract_mentioned_regs (rtx x)
-{
- return extract_mentioned_regs_helper (x, NULL_RTX);
-}
-
-/* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
- registers. */
-static rtx
-extract_mentioned_regs_helper (rtx x, rtx accum)
-{
- int i;
- enum rtx_code code;
- const char * fmt;
+ /* Determine implicit sets. */
+ implicit_sets = XCNEWVEC (rtx, last_basic_block);
+ find_implicit_sets ();
- /* Repeat is used to turn tail-recursion into iteration. */
- repeat:
+ alloc_hash_table (get_max_uid (), &set_hash_table, 1);
+ compute_hash_table (&set_hash_table);
- if (x == 0)
- return accum;
+ /* Free implicit_sets before peak usage. */
+ free (implicit_sets);
+ implicit_sets = NULL;
- code = GET_CODE (x);
- switch (code)
+ if (dump_file)
+ dump_hash_table (dump_file, "SET", &set_hash_table);
+ if (set_hash_table.n_elems > 0)
{
- case REG:
- return alloc_EXPR_LIST (0, x, accum);
+ basic_block bb;
+ rtx insn;
- case MEM:
- x = XEXP (x, 0);
- goto repeat;
+ alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
+ compute_cprop_data ();
- case PRE_DEC:
- case PRE_INC:
- case PRE_MODIFY:
- case POST_DEC:
- case POST_INC:
- case POST_MODIFY:
- /* We do not run this function with arguments having side effects. */
- gcc_unreachable ();
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
+ {
+ /* Reset tables used to keep track of what's still valid [since
+ the start of the block]. */
+ reset_opr_set_tables ();
- case PC:
- case CC0: /*FIXME*/
- case CONST:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST_FIXED:
- case CONST_VECTOR:
- case SYMBOL_REF:
- case LABEL_REF:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- return accum;
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn))
+ {
+ changed |= cprop_insn (insn);
+
+ /* Keep track of everything modified by this insn. */
+ /* ??? Need to be careful w.r.t. mods done to INSN.
+ Don't call mark_oprs_set if we turned the
+ insn into a NOTE. */
+ if (! NOTE_P (insn))
+ mark_oprs_set (insn);
+ }
+ }
- default:
- break;
+ changed |= bypass_conditional_jumps ();
+ free_cprop_mem ();
}
- i = GET_RTX_LENGTH (code) - 1;
- fmt = GET_RTX_FORMAT (code);
+ free_hash_table (&set_hash_table);
+ free_gcse_mem ();
+ obstack_free (&gcse_obstack, NULL);
- for (; i >= 0; i--)
+ if (dump_file)
{
- if (fmt[i] == 'e')
- {
- rtx tem = XEXP (x, i);
-
- /* If we are about to do the last recursive call
- needed at this level, change it into iteration. */
- if (i == 0)
- {
- x = tem;
- goto repeat;
- }
-
- accum = extract_mentioned_regs_helper (tem, accum);
- }
- else if (fmt[i] == 'E')
- {
- int j;
-
- for (j = 0; j < XVECLEN (x, i); j++)
- accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
- }
+ fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
+ current_function_name (), n_basic_blocks, bytes_used);
+ fprintf (dump_file, "%d local const props, %d local copy props, ",
+ local_const_prop_count, local_copy_prop_count);
+ fprintf (dump_file, "%d global const props, %d global copy props\n\n",
+ global_const_prop_count, global_copy_prop_count);
}
- return accum;
+ return changed;
}
-/* Determine whether INSN is MEM store pattern that we will consider moving.
- REGS_SET_BEFORE is bitmap of registers set before (and including) the
- current insn, REGS_SET_AFTER is bitmap of registers set after (and
- including) the insn in this basic block. We must be passing through BB from
- head to end, as we are using this fact to speed things up.
-
- The results are stored this way:
-
- -- the first anticipatable expression is added into ANTIC_STORE_LIST
- -- if the processed expression is not anticipatable, NULL_RTX is added
- there instead, so that we can use it as indicator that no further
- expression of this type may be anticipatable
- -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
- consequently, all of them but this head are dead and may be deleted.
- -- if the expression is not available, the insn due to that it fails to be
- available is stored in reaching_reg.
+\f
+/* All the passes implemented in this file. Each pass has its
+ own gate and execute function, and at the end of the file a
+ pass definition for passes.c.
- The things are complicated a bit by fact that there already may be stores
- to the same MEM from other blocks; also caller must take care of the
- necessary cleanup of the temporary markers after end of the basic block.
- */
+ We do not construct an accurate cfg in functions which call
+ setjmp, so none of these passes runs if the function calls
+ setjmp.
+ FIXME: Should just handle setjmp via REG_SETJMP notes. */
-static void
-find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
+static bool
+gate_rtl_cprop (void)
{
- struct ls_expr * ptr;
- rtx dest, set, tmp;
- int check_anticipatable, check_available;
- basic_block bb = BLOCK_FOR_INSN (insn);
-
- set = single_set (insn);
- if (!set)
- return;
-
- dest = SET_DEST (set);
-
- if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
- || GET_MODE (dest) == BLKmode)
- return;
+ return optimize > 0 && flag_gcse
+ && !cfun->calls_setjmp
+ && dbg_cnt (cprop);
+}
- if (side_effects_p (dest))
- return;
+static unsigned int
+execute_rtl_cprop (void)
+{
+ delete_unreachable_blocks ();
+ df_note_add_problem ();
+ df_set_flags (DF_LR_RUN_DCE);
+ df_analyze ();
+ flag_rerun_cse_after_global_opts |= one_cprop_pass ();
+ return 0;
+}
- /* If we are handling exceptions, we must be careful with memory references
- that may trap. If we are not, the behavior is undefined, so we may just
- continue. */
- if (flag_non_call_exceptions && may_trap_p (dest))
- return;
+static bool
+gate_rtl_pre (void)
+{
+ return optimize > 0 && flag_gcse
+ && !cfun->calls_setjmp
+ && optimize_function_for_speed_p (cfun)
+ && dbg_cnt (pre);
+}
- /* Even if the destination cannot trap, the source may. In this case we'd
- need to handle updating the REG_EH_REGION note. */
- if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
- return;
+static unsigned int
+execute_rtl_pre (void)
+{
+ delete_unreachable_blocks ();
+ df_note_add_problem ();
+ df_analyze ();
+ flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
+ return 0;
+}
- /* 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;
+static bool
+gate_rtl_hoist (void)
+{
+ return optimize > 0 && flag_gcse
+ && !cfun->calls_setjmp
+ /* It does not make sense to run code hoisting unless we are optimizing
+ for code size -- it rarely makes programs faster, and can make then
+ bigger if we did PRE (when optimizing for space, we don't run PRE). */
+ && optimize_function_for_size_p (cfun)
+ && dbg_cnt (hoist);
+}
- ptr = ldst_entry (dest);
- if (!ptr->pattern_regs)
- ptr->pattern_regs = extract_mentioned_regs (dest);
+static unsigned int
+execute_rtl_hoist (void)
+{
+ delete_unreachable_blocks ();
+ df_note_add_problem ();
+ df_analyze ();
+ flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
+ return 0;
+}
- /* Do not check for anticipatability if we either found one anticipatable
- store already, or tested for one and found out that it was killed. */
- check_anticipatable = 0;
- if (!ANTIC_STORE_LIST (ptr))
- check_anticipatable = 1;
- else
- {
- tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
- if (tmp != NULL_RTX
- && BLOCK_FOR_INSN (tmp) != bb)
- check_anticipatable = 1;
- }
- if (check_anticipatable)
- {
- if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
- tmp = NULL_RTX;
- else
- tmp = insn;
- ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
- ANTIC_STORE_LIST (ptr));
- }
-
- /* It is not necessary to check whether store is available if we did
- it successfully before; if we failed before, do not bother to check
- until we reach the insn that caused us to fail. */
- check_available = 0;
- if (!AVAIL_STORE_LIST (ptr))
- check_available = 1;
- else
- {
- tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
- if (BLOCK_FOR_INSN (tmp) != bb)
- check_available = 1;
- }
- if (check_available)
- {
- /* Check that we have already reached the insn at that the check
- failed last time. */
- if (LAST_AVAIL_CHECK_FAILURE (ptr))
- {
- for (tmp = BB_END (bb);
- tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
- tmp = PREV_INSN (tmp))
- continue;
- if (tmp == insn)
- check_available = 0;
- }
- else
- check_available = store_killed_after (dest, ptr->pattern_regs, insn,
- bb, regs_set_after,
- &LAST_AVAIL_CHECK_FAILURE (ptr));
- }
- if (!check_available)
- AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
-}
-
-/* Find available and anticipatable stores. */
-
-static int
-compute_store_table (void)
-{
- int ret;
- basic_block bb;
- unsigned regno;
- rtx insn, pat, tmp;
- int *last_set_in, *already_set;
- struct ls_expr * ptr, **prev_next_ptr_ptr;
-
- max_gcse_regno = max_reg_num ();
-
- reg_set_in_block = sbitmap_vector_alloc (last_basic_block,
- max_gcse_regno);
- sbitmap_vector_zero (reg_set_in_block, last_basic_block);
- pre_ldst_mems = 0;
- pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
- pre_ldst_expr_eq, NULL);
- last_set_in = XCNEWVEC (int, max_gcse_regno);
- already_set = XNEWVEC (int, max_gcse_regno);
-
- /* Find all the stores we care about. */
- FOR_EACH_BB (bb)
- {
- /* First compute the registers set in this block. */
- regvec = last_set_in;
-
- FOR_BB_INSNS (bb, insn)
- {
- if (! INSN_P (insn))
- continue;
-
- if (CALL_P (insn))
- {
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
- {
- last_set_in[regno] = INSN_UID (insn);
- SET_BIT (reg_set_in_block[bb->index], regno);
- }
- }
-
- pat = PATTERN (insn);
- compute_store_table_current_insn = insn;
- note_stores (pat, reg_set_info, reg_set_in_block[bb->index]);
- }
-
- /* Now find the stores. */
- memset (already_set, 0, sizeof (int) * max_gcse_regno);
- regvec = already_set;
- FOR_BB_INSNS (bb, insn)
- {
- if (! INSN_P (insn))
- continue;
-
- if (CALL_P (insn))
- {
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
- already_set[regno] = 1;
- }
-
- pat = PATTERN (insn);
- note_stores (pat, reg_set_info, NULL);
-
- /* Now that we've marked regs, look for stores. */
- find_moveable_store (insn, already_set, last_set_in);
-
- /* Unmark regs that are no longer set. */
- compute_store_table_current_insn = insn;
- note_stores (pat, reg_clear_last_set, last_set_in);
- if (CALL_P (insn))
- {
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
- && last_set_in[regno] == INSN_UID (insn))
- last_set_in[regno] = 0;
- }
- }
-
-#ifdef ENABLE_CHECKING
- /* last_set_in should now be all-zero. */
- for (regno = 0; regno < max_gcse_regno; regno++)
- gcc_assert (!last_set_in[regno]);
-#endif
-
- /* Clear temporary marks. */
- for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
- {
- LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
- if (ANTIC_STORE_LIST (ptr)
- && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
- ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
- }
- }
-
- /* Remove the stores that are not available anywhere, as there will
- be no opportunity to optimize them. */
- for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
- ptr != NULL;
- ptr = *prev_next_ptr_ptr)
- {
- if (!AVAIL_STORE_LIST (ptr))
- {
- *prev_next_ptr_ptr = ptr->next;
- htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
- free_ldst_entry (ptr);
- }
- else
- prev_next_ptr_ptr = &ptr->next;
- }
-
- ret = enumerate_ldsts ();
-
- if (dump_file)
- {
- fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n");
- print_ldst_list (dump_file);
- }
-
- free (last_set_in);
- free (already_set);
- return ret;
-}
-
-/* Check to see if the load X is aliased with STORE_PATTERN.
- AFTER is true if we are checking the case when STORE_PATTERN occurs
- after the X. */
-
-static bool
-load_kills_store (const_rtx x, const_rtx store_pattern, int after)
-{
- if (after)
- return anti_dependence (x, store_pattern);
- else
- return true_dependence (store_pattern, GET_MODE (store_pattern), x,
- rtx_addr_varies_p);
-}
-
-/* Go through the entire insn X, looking for any loads which might alias
- STORE_PATTERN. Return true if found.
- AFTER is true if we are checking the case when STORE_PATTERN occurs
- after the insn X. */
-
-static bool
-find_loads (const_rtx x, const_rtx store_pattern, int after)
-{
- const char * fmt;
- int i, j;
- int ret = false;
-
- if (!x)
- return false;
-
- if (GET_CODE (x) == SET)
- x = SET_SRC (x);
-
- if (MEM_P (x))
- {
- if (load_kills_store (x, store_pattern, after))
- return true;
- }
-
- /* Recursively process the insn. */
- fmt = GET_RTX_FORMAT (GET_CODE (x));
-
- for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
- {
- if (fmt[i] == 'e')
- ret |= find_loads (XEXP (x, i), store_pattern, after);
- else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
- }
- return ret;
-}
-
-static inline bool
-store_killed_in_pat (const_rtx x, const_rtx pat, int after)
-{
- if (GET_CODE (pat) == SET)
- {
- rtx dest = SET_DEST (pat);
-
- if (GET_CODE (dest) == ZERO_EXTRACT)
- dest = XEXP (dest, 0);
-
- /* Check for memory stores to aliased objects. */
- if (MEM_P (dest)
- && !expr_equiv_p (dest, x))
- {
- if (after)
- {
- if (output_dependence (dest, x))
- return true;
- }
- else
- {
- if (output_dependence (x, dest))
- return true;
- }
- }
- }
-
- if (find_loads (pat, x, after))
- return true;
-
- return false;
-}
-
-/* Check if INSN kills the store pattern X (is aliased with it).
- AFTER is true if we are checking the case when store X occurs
- after the insn. Return true if it does. */
-
-static bool
-store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
-{
- const_rtx reg, base, note, pat;
-
- if (!INSN_P (insn))
- return false;
-
- if (CALL_P (insn))
- {
- /* A normal or pure call might read from pattern,
- but a const call will not. */
- if (!RTL_CONST_CALL_P (insn))
- return true;
-
- /* But even a const call reads its parameters. Check whether the
- base of some of registers used in mem is stack pointer. */
- for (reg = x_regs; reg; reg = XEXP (reg, 1))
- {
- base = find_base_term (XEXP (reg, 0));
- if (!base
- || (GET_CODE (base) == ADDRESS
- && GET_MODE (base) == Pmode
- && XEXP (base, 0) == stack_pointer_rtx))
- return true;
- }
-
- return false;
- }
-
- pat = PATTERN (insn);
- if (GET_CODE (pat) == SET)
- {
- if (store_killed_in_pat (x, pat, after))
- return true;
- }
- else if (GET_CODE (pat) == PARALLEL)
- {
- int i;
-
- for (i = 0; i < XVECLEN (pat, 0); i++)
- if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
- return true;
- }
- else if (find_loads (PATTERN (insn), x, after))
- return true;
-
- /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
- location aliased with X, then this insn kills X. */
- note = find_reg_equal_equiv_note (insn);
- if (! note)
- return false;
- note = XEXP (note, 0);
-
- /* However, if the note represents a must alias rather than a may
- alias relationship, then it does not kill X. */
- if (expr_equiv_p (note, x))
- return false;
-
- /* See if there are any aliased loads in the note. */
- return find_loads (note, x, after);
-}
-
-/* Returns true if the expression X is loaded or clobbered on or after INSN
- within basic block BB. REGS_SET_AFTER is bitmap of registers set in
- or after the insn. X_REGS is list of registers mentioned in X. If the store
- is killed, return the last insn in that it occurs in FAIL_INSN. */
-
-static bool
-store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
- int *regs_set_after, rtx *fail_insn)
-{
- rtx last = BB_END (bb), act;
-
- if (!store_ops_ok (x_regs, regs_set_after))
- {
- /* We do not know where it will happen. */
- if (fail_insn)
- *fail_insn = NULL_RTX;
- return true;
- }
-
- /* Scan from the end, so that fail_insn is determined correctly. */
- for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
- if (store_killed_in_insn (x, x_regs, act, false))
- {
- if (fail_insn)
- *fail_insn = act;
- return true;
- }
-
- return false;
-}
-
-/* Returns true if the expression X is loaded or clobbered on or before INSN
- within basic block BB. X_REGS is list of registers mentioned in X.
- REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
-static bool
-store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
- int *regs_set_before)
-{
- rtx first = BB_HEAD (bb);
-
- if (!store_ops_ok (x_regs, regs_set_before))
- return true;
-
- for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
- if (store_killed_in_insn (x, x_regs, insn, true))
- return true;
-
- return false;
-}
-
-/* Fill in available, anticipatable, transparent and kill vectors in
- STORE_DATA, based on lists of available and anticipatable stores. */
-static void
-build_store_vectors (void)
-{
- basic_block bb;
- int *regs_set_in_block;
- rtx insn, st;
- struct ls_expr * ptr;
- unsigned regno;
-
- /* Build the gen_vector. This is any store in the table which is not killed
- by aliasing later in its block. */
- ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores);
- sbitmap_vector_zero (ae_gen, last_basic_block);
-
- st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
- sbitmap_vector_zero (st_antloc, last_basic_block);
-
- for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
- {
- for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
- {
- insn = XEXP (st, 0);
- bb = BLOCK_FOR_INSN (insn);
-
- /* If we've already seen an available expression in this block,
- we can delete this one (It occurs earlier in the block). We'll
- copy the SRC expression to an unused register in case there
- are any side effects. */
- if (TEST_BIT (ae_gen[bb->index], ptr->index))
- {
- rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
- if (dump_file)
- fprintf (dump_file, "Removing redundant store:\n");
- replace_store_insn (r, XEXP (st, 0), bb, ptr);
- continue;
- }
- SET_BIT (ae_gen[bb->index], ptr->index);
- }
-
- for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
- {
- insn = XEXP (st, 0);
- bb = BLOCK_FOR_INSN (insn);
- SET_BIT (st_antloc[bb->index], ptr->index);
- }
- }
-
- ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
- sbitmap_vector_zero (ae_kill, last_basic_block);
-
- transp = sbitmap_vector_alloc (last_basic_block, num_stores);
- sbitmap_vector_zero (transp, last_basic_block);
- regs_set_in_block = XNEWVEC (int, max_gcse_regno);
-
- FOR_EACH_BB (bb)
- {
- for (regno = 0; regno < max_gcse_regno; regno++)
- regs_set_in_block[regno] = TEST_BIT (reg_set_in_block[bb->index], regno);
-
- for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
- {
- if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
- bb, regs_set_in_block, NULL))
- {
- /* It should not be necessary to consider the expression
- killed if it is both anticipatable and available. */
- if (!TEST_BIT (st_antloc[bb->index], ptr->index)
- || !TEST_BIT (ae_gen[bb->index], ptr->index))
- SET_BIT (ae_kill[bb->index], ptr->index);
- }
- else
- SET_BIT (transp[bb->index], ptr->index);
- }
- }
-
- free (regs_set_in_block);
-
- if (dump_file)
- {
- dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
- dump_sbitmap_vector (dump_file, "st_kill", "", ae_kill, last_basic_block);
- dump_sbitmap_vector (dump_file, "Transpt", "", transp, last_basic_block);
- dump_sbitmap_vector (dump_file, "st_avloc", "", ae_gen, last_basic_block);
- }
-}
-
-/* Insert an instruction at the beginning of a basic block, and update
- the BB_HEAD if needed. */
-
-static void
-insert_insn_start_basic_block (rtx insn, basic_block bb)
-{
- /* Insert at start of successor block. */
- rtx prev = PREV_INSN (BB_HEAD (bb));
- rtx before = BB_HEAD (bb);
- while (before != 0)
- {
- if (! LABEL_P (before)
- && !NOTE_INSN_BASIC_BLOCK_P (before))
- break;
- prev = before;
- if (prev == BB_END (bb))
- break;
- before = NEXT_INSN (before);
- }
-
- insn = emit_insn_after_noloc (insn, prev, bb);
-
- if (dump_file)
- {
- fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
- bb->index);
- print_inline_rtx (dump_file, insn, 6);
- fprintf (dump_file, "\n");
- }
-}
-
-/* This routine will insert a store on an edge. EXPR is the ldst entry for
- the memory reference, and E is the edge to insert it on. Returns nonzero
- if an edge insertion was performed. */
-
-static int
-insert_store (struct ls_expr * expr, edge e)
-{
- rtx reg, insn;
- basic_block bb;
- edge tmp;
- edge_iterator ei;
-
- /* We did all the deleted before this insert, so if we didn't delete a
- store, then we haven't set the reaching reg yet either. */
- if (expr->reaching_reg == NULL_RTX)
- return 0;
-
- if (e->flags & EDGE_FAKE)
- return 0;
-
- reg = expr->reaching_reg;
- insn = gen_move_insn (copy_rtx (expr->pattern), reg);
-
- /* If we are inserting this expression on ALL predecessor edges of a BB,
- insert it at the start of the BB, and reset the insert bits on the other
- edges so we don't try to insert it on the other edges. */
- bb = e->dest;
- FOR_EACH_EDGE (tmp, ei, e->dest->preds)
- if (!(tmp->flags & EDGE_FAKE))
- {
- int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
-
- gcc_assert (index != EDGE_INDEX_NO_EDGE);
- if (! TEST_BIT (pre_insert_map[index], expr->index))
- break;
- }
-
- /* If tmp is NULL, we found an insertion on every edge, blank the
- insertion vector for these edges, and insert at the start of the BB. */
- if (!tmp && bb != EXIT_BLOCK_PTR)
- {
- FOR_EACH_EDGE (tmp, ei, e->dest->preds)
- {
- int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
- RESET_BIT (pre_insert_map[index], expr->index);
- }
- insert_insn_start_basic_block (insn, bb);
- return 0;
- }
-
- /* We can't put stores in the front of blocks pointed to by abnormal
- edges since that may put a store where one didn't used to be. */
- gcc_assert (!(e->flags & EDGE_ABNORMAL));
-
- insert_insn_on_edge (insn, e);
-
- if (dump_file)
- {
- fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
- e->src->index, e->dest->index);
- print_inline_rtx (dump_file, insn, 6);
- fprintf (dump_file, "\n");
- }
-
- return 1;
-}
-
-/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
- memory location in SMEXPR set in basic block BB.
-
- This could be rather expensive. */
-
-static void
-remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
-{
- edge_iterator *stack, ei;
- int sp;
- edge act;
- sbitmap visited = sbitmap_alloc (last_basic_block);
- rtx last, insn, note;
- rtx mem = smexpr->pattern;
-
- stack = XNEWVEC (edge_iterator, n_basic_blocks);
- sp = 0;
- ei = ei_start (bb->succs);
-
- sbitmap_zero (visited);
-
- act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
- while (1)
- {
- if (!act)
- {
- if (!sp)
- {
- free (stack);
- sbitmap_free (visited);
- return;
- }
- act = ei_edge (stack[--sp]);
- }
- bb = act->dest;
-
- if (bb == EXIT_BLOCK_PTR
- || TEST_BIT (visited, bb->index))
- {
- if (!ei_end_p (ei))
- ei_next (&ei);
- act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
- continue;
- }
- SET_BIT (visited, bb->index);
-
- if (TEST_BIT (st_antloc[bb->index], smexpr->index))
- {
- for (last = ANTIC_STORE_LIST (smexpr);
- BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
- last = XEXP (last, 1))
- continue;
- last = XEXP (last, 0);
- }
- else
- last = NEXT_INSN (BB_END (bb));
-
- for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- {
- note = find_reg_equal_equiv_note (insn);
- if (!note || !expr_equiv_p (XEXP (note, 0), mem))
- continue;
-
- if (dump_file)
- fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
- INSN_UID (insn));
- remove_note (insn, note);
- }
-
- if (!ei_end_p (ei))
- ei_next (&ei);
- act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
-
- if (EDGE_COUNT (bb->succs) > 0)
- {
- if (act)
- stack[sp++] = ei;
- ei = ei_start (bb->succs);
- act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
- }
- }
-}
-
-/* This routine will replace a store with a SET to a specified register. */
-
-static void
-replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr)
-{
- rtx insn, mem, note, set, ptr;
-
- mem = smexpr->pattern;
- insn = gen_move_insn (reg, SET_SRC (single_set (del)));
-
- for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1))
- if (XEXP (ptr, 0) == del)
- {
- XEXP (ptr, 0) = insn;
- break;
- }
-
- /* Move the notes from the deleted insn to its replacement. */
- REG_NOTES (insn) = REG_NOTES (del);
-
- /* Emit the insn AFTER all the notes are transferred.
- This is cheaper since we avoid df rescanning for the note change. */
- insn = emit_insn_after (insn, del);
-
- if (dump_file)
- {
- fprintf (dump_file,
- "STORE_MOTION delete insn in BB %d:\n ", bb->index);
- print_inline_rtx (dump_file, del, 6);
- fprintf (dump_file, "\nSTORE MOTION replaced with insn:\n ");
- print_inline_rtx (dump_file, insn, 6);
- fprintf (dump_file, "\n");
- }
-
- delete_insn (del);
-
- /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
- they are no longer accurate provided that they are reached by this
- definition, so drop them. */
- for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- {
- set = single_set (insn);
- if (!set)
- continue;
- if (expr_equiv_p (SET_DEST (set), mem))
- return;
- note = find_reg_equal_equiv_note (insn);
- if (!note || !expr_equiv_p (XEXP (note, 0), mem))
- continue;
-
- if (dump_file)
- fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
- INSN_UID (insn));
- remove_note (insn, note);
- }
- remove_reachable_equiv_notes (bb, smexpr);
-}
-
-
-/* Delete a store, but copy the value that would have been stored into
- the reaching_reg for later storing. */
-
-static void
-delete_store (struct ls_expr * expr, basic_block bb)
-{
- rtx reg, i, del;
-
- if (expr->reaching_reg == NULL_RTX)
- expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
-
- reg = expr->reaching_reg;
-
- for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
- {
- del = XEXP (i, 0);
- if (BLOCK_FOR_INSN (del) == bb)
- {
- /* We know there is only one since we deleted redundant
- ones during the available computation. */
- replace_store_insn (reg, del, bb, expr);
- break;
- }
- }
-}
-
-/* Free memory used by store motion. */
-
-static void
-free_store_memory (void)
-{
- free_ldst_mems ();
-
- if (ae_gen)
- sbitmap_vector_free (ae_gen);
- if (ae_kill)
- sbitmap_vector_free (ae_kill);
- if (transp)
- sbitmap_vector_free (transp);
- if (st_antloc)
- sbitmap_vector_free (st_antloc);
- if (pre_insert_map)
- sbitmap_vector_free (pre_insert_map);
- if (pre_delete_map)
- sbitmap_vector_free (pre_delete_map);
- if (reg_set_in_block)
- sbitmap_vector_free (reg_set_in_block);
-
- ae_gen = ae_kill = transp = st_antloc = NULL;
- pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
-}
-
-/* Perform store motion. Much like gcse, except we move expressions the
- other way by looking at the flowgraph in reverse. */
-
-static void
-store_motion (void)
-{
- basic_block bb;
- int x;
- struct ls_expr * ptr;
- int update_flow = 0;
-
- if (dump_file)
- {
- fprintf (dump_file, "before store motion\n");
- print_rtl (dump_file, get_insns ());
- }
-
- init_alias_analysis ();
-
- /* Find all the available and anticipatable stores. */
- num_stores = compute_store_table ();
- if (num_stores == 0)
- {
- htab_delete (pre_ldst_table);
- pre_ldst_table = NULL;
- sbitmap_vector_free (reg_set_in_block);
- end_alias_analysis ();
- return;
- }
-
- /* Now compute kill & transp vectors. */
- build_store_vectors ();
- add_noreturn_fake_exit_edges ();
- connect_infinite_loops_to_exit ();
-
- edge_list = pre_edge_rev_lcm (num_stores, transp, ae_gen,
- st_antloc, ae_kill, &pre_insert_map,
- &pre_delete_map);
-
- /* Now we want to insert the new stores which are going to be needed. */
- for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
- {
- /* If any of the edges we have above are abnormal, we can't move this
- store. */
- for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
- if (TEST_BIT (pre_insert_map[x], ptr->index)
- && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
- break;
-
- if (x >= 0)
- {
- if (dump_file != NULL)
- fprintf (dump_file,
- "Can't replace store %d: abnormal edge from %d to %d\n",
- ptr->index, INDEX_EDGE (edge_list, x)->src->index,
- INDEX_EDGE (edge_list, x)->dest->index);
- continue;
- }
-
- /* Now we want to insert the new stores which are going to be needed. */
-
- FOR_EACH_BB (bb)
- if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
- delete_store (ptr, bb);
-
- for (x = 0; x < NUM_EDGES (edge_list); x++)
- if (TEST_BIT (pre_insert_map[x], ptr->index))
- update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
- }
-
- if (update_flow)
- commit_edge_insertions ();
-
- free_store_memory ();
- free_edge_list (edge_list);
- remove_fake_exit_edges ();
- end_alias_analysis ();
-}
-
-\f
-/* Entry point for jump bypassing optimization pass. */
-
-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 (cfun->calls_setjmp)
- return 0;
-
- /* Identify the basic block information for this function, including
- successors and predecessors. */
- max_gcse_regno = max_reg_num ();
-
- if (dump_file)
- dump_flow_info (dump_file, dump_flags);
-
- /* Return if there's nothing to do, or it is too expensive. */
- if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
- || is_too_expensive (_ ("jump bypassing disabled")))
- return 0;
-
- gcc_obstack_init (&gcse_obstack);
- bytes_used = 0;
-
- /* We need alias. */
- init_alias_analysis ();
-
- /* Record where pseudo-registers are set. This data is kept accurate
- during each pass. ??? We could also record hard-reg information here
- [since it's unchanging], however it is currently done during hash table
- computation.
-
- It may be tempting to compute MEM set information here too, but MEM sets
- will be subject to code motion one day and thus we need to compute
- information about memory sets when we build the hash tables. */
-
- alloc_reg_set_mem (max_gcse_regno);
- compute_sets ();
-
- max_gcse_regno = max_reg_num ();
- alloc_gcse_mem ();
- changed = one_cprop_pass (MAX_GCSE_PASSES + 2, true, true);
- free_gcse_mem ();
-
- if (dump_file)
- {
- fprintf (dump_file, "BYPASS of %s: %d basic blocks, ",
- current_function_name (), n_basic_blocks);
- fprintf (dump_file, "%d bytes\n\n", bytes_used);
- }
-
- obstack_free (&gcse_obstack, NULL);
- free_reg_set_mem ();
-
- /* We are finished with alias. */
- end_alias_analysis ();
-
- return changed;
-}
-
-/* Return true if the graph is too expensive to optimize. PASS is the
- optimization about to be performed. */
-
-static bool
-is_too_expensive (const char *pass)
-{
- /* Trying to perform global optimizations on flow graphs which have
- a high connectivity will take a long time and is unlikely to be
- particularly useful.
-
- In normal circumstances a cfg should have about twice as many
- edges as blocks. But we do not want to punish small functions
- which have a couple switch statements. Rather than simply
- threshold the number of blocks, uses something with a more
- graceful degradation. */
- if (n_edges > 20000 + n_basic_blocks * 4)
- {
- warning (OPT_Wdisabled_optimization,
- "%s: %d basic blocks and %d edges/basic block",
- pass, n_basic_blocks, n_edges / n_basic_blocks);
-
- return true;
- }
-
- /* If allocating memory for the cprop bitmap would take up too much
- storage it's better just to disable the optimization. */
- if ((n_basic_blocks
- * SBITMAP_SET_SIZE (max_reg_num ())
- * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
- {
- warning (OPT_Wdisabled_optimization,
- "%s: %d basic blocks and %d registers",
- pass, n_basic_blocks, max_reg_num ());
-
- return true;
- }
-
- return false;
-}
-\f
-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 =
+struct rtl_opt_pass pass_rtl_cprop =
{
{
RTL_PASS,
- "bypass", /* name */
- gate_handle_jump_bypass, /* gate */
- rest_of_handle_jump_bypass, /* execute */
+ "cprop", /* name */
+ gate_rtl_cprop, /* gate */
+ execute_rtl_cprop, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- TV_BYPASS, /* tv_id */
- 0, /* properties_required */
+ TV_CPROP, /* tv_id */
+ PROP_cfglayout, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
+ TODO_df_finish | TODO_verify_rtl_sharing |
TODO_dump_func |
- TODO_ggc_collect | TODO_verify_flow /* todo_flags_finish */
+ TODO_verify_flow | TODO_ggc_collect /* 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)
+struct rtl_opt_pass pass_rtl_pre =
{
- int save_csb, save_cfj;
- int tem2 = 0, tem;
- tem = gcse_main (get_insns ());
- delete_trivially_dead_insns (get_insns (), max_reg_num ());
- rebuild_jump_labels (get_insns ());
- save_csb = flag_cse_skip_blocks;
- save_cfj = flag_cse_follow_jumps;
- flag_cse_skip_blocks = flag_cse_follow_jumps = 0;
-
- /* If -fexpensive-optimizations, re-run CSE to clean up things done
- by gcse. */
- if (flag_expensive_optimizations)
- {
- timevar_push (TV_CSE);
- tem2 = cse_main (get_insns (), max_reg_num ());
- df_finish_pass (false);
- purge_all_dead_edges ();
- delete_trivially_dead_insns (get_insns (), max_reg_num ());
- timevar_pop (TV_CSE);
- cse_not_expected = !flag_rerun_cse_after_loop;
- }
-
- /* If gcse or cse altered any jumps, rerun jump optimizations to clean
- things up. */
- if (tem || tem2 == 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;
-}
+ {
+ RTL_PASS,
+ "pre", /* name */
+ gate_rtl_pre, /* gate */
+ execute_rtl_pre, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_PRE, /* tv_id */
+ PROP_cfglayout, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish | TODO_verify_rtl_sharing |
+ TODO_dump_func |
+ TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
+ }
+};
-struct rtl_opt_pass pass_gcse =
+struct rtl_opt_pass pass_rtl_hoist =
{
{
RTL_PASS,
- "gcse1", /* name */
- gate_handle_gcse, /* gate */
- rest_of_handle_gcse, /* execute */
+ "hoist", /* name */
+ gate_rtl_hoist, /* gate */
+ execute_rtl_hoist, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- TV_GCSE, /* tv_id */
- 0, /* properties_required */
+ TV_HOIST, /* tv_id */
+ PROP_cfglayout, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
}
};
-
#include "gt-gcse.h"