/* Partial redundancy elimination / Hoisting for RTL.
- Copyright (C) 1997-2015 Free Software Foundation, Inc.
+ Copyright (C) 1997-2021 Free Software Foundation, Inc.
This file is part of GCC.
#include "tree.h"
#include "predict.h"
#include "df.h"
+#include "memmodel.h"
#include "tm_p.h"
#include "insn-config.h"
+#include "print-rtl.h"
#include "regs.h"
#include "ira.h"
#include "recog.h"
#include "lcm.h"
#include "cfgcleanup.h"
#include "expr.h"
-#include "params.h"
#include "intl.h"
#include "tree-pass.h"
#include "dbgcnt.h"
#include "gcse.h"
#include "gcse-common.h"
+#include "function-abi.h"
/* We support GCSE via Partial Redundancy Elimination. PRE optimizations
are a superset of those done by classic GCSE.
to keep register pressure under control.
A value of "0" removes restrictions on how far the expression can
travel. */
- int max_distance;
+ HOST_WIDE_INT max_distance;
};
/* Occurrence of an expression.
struct gcse_expr * expr; /* Gcse expression reference for LM. */
rtx pattern; /* Pattern of this mem. */
rtx pattern_regs; /* List of registers mentioned by the mem. */
- rtx_insn_list *loads; /* INSN list of loads seen. */
- rtx_insn_list *stores; /* INSN list of stores seen. */
+ vec<rtx_insn *> stores; /* INSN list of stores seen. */
struct ls_expr * next; /* Next in the list. */
int invalid; /* Invalid for some reason. */
int index; /* If it maps to a bitmap index. */
static int oprs_anticipatable_p (const_rtx, const rtx_insn *);
static int oprs_available_p (const_rtx, const rtx_insn *);
static void insert_expr_in_table (rtx, machine_mode, rtx_insn *, int, int,
- int, struct gcse_hash_table_d *);
+ HOST_WIDE_INT, struct gcse_hash_table_d *);
static unsigned int hash_expr (const_rtx, machine_mode, int *, int);
static void record_last_reg_set_info (rtx_insn *, int);
static void record_last_mem_set_info (rtx_insn *);
static void free_code_hoist_mem (void);
static void compute_code_hoist_vbeinout (void);
static void compute_code_hoist_data (void);
-static int should_hoist_expr_to_dom (basic_block, struct gcse_expr *, basic_block,
- sbitmap, int, int *, enum reg_class,
+static int should_hoist_expr_to_dom (basic_block, struct gcse_expr *,
+ basic_block,
+ sbitmap, HOST_WIDE_INT, int *,
+ enum reg_class,
int *, bitmap, rtx_insn *);
static int hoist_code (void);
static enum reg_class get_regno_pressure_class (int regno, int *nregs);
static void update_ld_motion_stores (struct gcse_expr *);
static void clear_modify_mem_tables (void);
static void free_modify_mem_tables (void);
-static bool is_too_expensive (const char *);
#define GNEW(T) ((T *) gmalloc (sizeof (T)))
#define GCNEW(T) ((T *) gcalloc (1, sizeof (T)))
GCSE. */
static int
-want_to_gcse_p (rtx x, machine_mode mode, int *max_distance_ptr)
+want_to_gcse_p (rtx x, machine_mode mode, HOST_WIDE_INT *max_distance_ptr)
{
#ifdef STACK_REGS
/* On register stack architectures, don't GCSE constants from the
/* PRE doesn't implement max_distance restriction. */
{
int cost;
- int max_distance;
+ HOST_WIDE_INT max_distance;
gcc_assert (!optimize_function_for_speed_p (cfun)
&& optimize_function_for_size_p (cfun));
cost = set_src_cost (x, mode, 0);
- if (cost < COSTS_N_INSNS (GCSE_UNRESTRICTED_COST))
+ if (cost < COSTS_N_INSNS (param_gcse_unrestricted_cost))
{
- max_distance = (GCSE_COST_DISTANCE_RATIO * cost) / 10;
+ max_distance
+ = ((HOST_WIDE_INT)param_gcse_cost_distance_ratio * cost) / 10;
if (max_distance == 0)
return 0;
*max_distance_ptr = max_distance;
}
- return can_assign_to_reg_without_clobbers_p (x);
+ return can_assign_to_reg_without_clobbers_p (x, mode);
}
}
static GTY(()) rtx_insn *test_insn;
-/* 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.
+/* Return true if we can assign X to a pseudo register of mode MODE
+ such that the resulting insn does not result in clobbering a hard
+ register as a side-effect.
Additionally, if the target requires it, check that the resulting insn
can be copied. If it cannot, this means that X is special and probably
maybe live hard regs. */
bool
-can_assign_to_reg_without_clobbers_p (rtx x)
+can_assign_to_reg_without_clobbers_p (rtx x, machine_mode mode)
{
int num_clobbers = 0;
int icode;
bool can_assign = false;
/* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
- if (general_operand (x, GET_MODE (x)))
+ if (general_operand (x, mode))
return 1;
else if (GET_MODE (x) == VOIDmode)
return 0;
/* Now make an insn like the one we would make when GCSE'ing and see if
valid. */
- PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
+ PUT_MODE (SET_DEST (PATTERN (test_insn)), mode);
SET_SRC (PATTERN (test_insn)) = x;
icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
return 0;
case PC:
- case CC0: /*FIXME*/
case CONST:
CASE_CONST_ANY:
case SYMBOL_REF:
note_stores to examine each hunk of memory that is modified. */
mci.mem = x;
mci.conflict = false;
- note_stores (PATTERN (setter), mems_conflict_for_gcse_p, &mci);
+ note_stores (setter, mems_conflict_for_gcse_p, &mci);
if (mci.conflict)
return 1;
}
static void
insert_expr_in_table (rtx x, machine_mode mode, rtx_insn *insn,
int antic_p,
- int avail_p, int max_distance, struct gcse_hash_table_d *table)
+ int avail_p, HOST_WIDE_INT max_distance,
+ struct gcse_hash_table_d *table)
{
int found, do_not_record_p;
unsigned int hash;
cur_expr = table->table[hash];
found = 0;
- while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
+ while (cur_expr && (found = expr_equiv_p (cur_expr->expr, x)) == 0)
{
/* If the expression isn't found, save a pointer to the end of
the list. */
else if (REG_P (dest))
{
unsigned int regno = REGNO (dest);
- int max_distance = 0;
+ HOST_WIDE_INT max_distance = 0;
/* See if a REG_EQUAL note shows this equivalent to a simpler expression.
else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
{
unsigned int regno = REGNO (src);
- int max_distance = 0;
+ HOST_WIDE_INT max_distance = 0;
/* Only record sets of pseudo-regs in the hash table. */
if (regno >= FIRST_PSEUDO_REGISTER
if (flat_table[i] != 0)
{
expr = flat_table[i];
- fprintf (file, "Index %d (hash value %d; max distance %d)\n ",
+ fprintf (file, "Index %d (hash value %d; max distance "
+ HOST_WIDE_INT_PRINT_DEC ")\n ",
expr->bitmap_index, hash_val[i], expr->max_distance);
print_rtl (file, expr->expr);
fprintf (file, "\n");
if (CALL_P (insn))
{
hard_reg_set_iterator hrsi;
- EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
- 0, regno, hrsi)
+
+ /* We don't track modes of hard registers, so we need
+ to be conservative and assume that partial kills
+ are full kills. */
+ HARD_REG_SET callee_clobbers
+ = insn_callee_abi (insn).full_and_partial_reg_clobbers ();
+ EXECUTE_IF_SET_IN_HARD_REG_SET (callee_clobbers, 0, regno, hrsi)
record_last_reg_set_info (insn, regno);
- if (! RTL_CONST_OR_PURE_CALL_P (insn))
+ if (! RTL_CONST_OR_PURE_CALL_P (insn)
+ || RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
+ || can_throw_external (insn))
record_last_mem_set_info (insn);
}
- note_stores (PATTERN (insn), record_last_set_info, insn);
+ note_stores (insn, record_last_set_info, insn);
}
/* The next pass builds the hash table. */
static void
prune_expressions (bool pre_p)
{
- sbitmap prune_exprs;
struct gcse_expr *expr;
unsigned int ui;
basic_block bb;
- prune_exprs = sbitmap_alloc (expr_hash_table.n_elems);
+ auto_sbitmap prune_exprs (expr_hash_table.n_elems);
bitmap_clear (prune_exprs);
for (ui = 0; ui < expr_hash_table.size; ui++)
{
continue;
}
- if (!pre_p && MEM_P (expr->expr))
+ if (!pre_p && contains_mem_rtx_p (expr->expr))
/* Note memory references that can be clobbered by a call.
We do not split abnormal edges in hoisting, so would
a memory reference get hoisted along an abnormal edge,
constant memory references can be hoisted along abnormal
edges. */
{
- if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
- continue;
+ rtx x = expr->expr;
+
+ /* Common cases where we might find the MEM which may allow us
+ to avoid pruning the expression. */
+ while (GET_CODE (x) == ZERO_EXTEND || GET_CODE (x) == SIGN_EXTEND)
+ x = XEXP (x, 0);
+
+ /* If we found the MEM, go ahead and look at it to see if it has
+ properties that allow us to avoid pruning its expression out
+ of the tables. */
+ if (MEM_P (x))
+ {
+ if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
+ continue;
- if (MEM_READONLY_P (expr->expr)
- && !MEM_VOLATILE_P (expr->expr)
- && MEM_NOTRAP_P (expr->expr))
- /* Constant memory reference, e.g., a PIC address. */
- continue;
+ if (MEM_READONLY_P (x)
+ && !MEM_VOLATILE_P (x)
+ && MEM_NOTRAP_P (x))
+ /* Constant memory reference, e.g., a PIC address. */
+ continue;
+ }
/* ??? Optimally, we would use interprocedural alias
analysis to determine if this mem is actually killed
break;
}
}
-
- sbitmap_free (prune_exprs);
}
/* It may be necessary to insert a large number of insns on edges to
prune_insertions_deletions (int n_elems)
{
sbitmap_iterator sbi;
- sbitmap prune_exprs;
/* We always use I to iterate over blocks/edges and J to iterate over
expressions. */
/* Set of expressions which require too many insertions relative to
the number of deletions achieved. We will prune these out of the
insertion/deletion sets. */
- prune_exprs = sbitmap_alloc (n_elems);
+ auto_sbitmap prune_exprs (n_elems);
bitmap_clear (prune_exprs);
/* Iterate over the edges counting the number of times each expression
PRUNE_EXPRS. */
for (j = 0; j < (unsigned) n_elems; j++)
if (deletions[j]
- && ((unsigned) insertions[j] / deletions[j]) > MAX_GCSE_INSERTION_RATIO)
+ && (insertions[j] / deletions[j]) > param_max_gcse_insertion_ratio)
bitmap_set_bit (prune_exprs, j);
/* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */
bitmap_clear_bit (pre_delete_map[i], j);
}
- sbitmap_free (prune_exprs);
free (insertions);
free (deletions);
}
return rval;
}
\f
-/* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */
+/* Generate RTL to copy an EXP to REG and return it. */
-static rtx_insn *
-process_insert_insn (struct gcse_expr *expr)
+rtx_insn *
+prepare_copy_insn (rtx reg, rtx exp)
{
- rtx reg = expr->reaching_reg;
- /* Copy the expression to make sure we don't have any sharing issues. */
- rtx exp = copy_rtx (expr->expr);
rtx_insn *pat;
start_sequence ();
return pat;
}
+/* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */
+
+static rtx_insn *
+process_insert_insn (struct gcse_expr *expr)
+{
+ rtx reg = expr->reaching_reg;
+ /* Copy the expression to make sure we don't have any sharing issues. */
+ rtx exp = copy_rtx (expr->expr);
+
+ return prepare_copy_insn (reg, exp);
+}
+
/* Add EXPR to the end of basic block BB.
This is used by both the PRE and code hoisting. */
while (NEXT_INSN (pat_end) != NULL_RTX)
pat_end = NEXT_INSN (pat_end);
- /* If the last insn is a jump, insert EXPR in front [taking care to
- handle cc0, etc. properly]. Similarly we need to care trapping
- instructions in presence of non-call exceptions. */
+ /* If the last insn is a jump, insert EXPR in front. Similarly we need to
+ take care of trapping instructions in presence of non-call exceptions. */
if (JUMP_P (insn)
|| (NONJUMP_INSN_P (insn)
&& (!single_succ_p (bb)
|| single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
{
- /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
- if cc0 isn't set. */
- if (HAVE_cc0)
- {
- rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
- if (note)
- insn = safe_as_a <rtx_insn *> (XEXP (note, 0));
- else
- {
- rtx_insn *maybe_cc0_setter = prev_nonnote_insn (insn);
- if (maybe_cc0_setter
- && INSN_P (maybe_cc0_setter)
- && sets_cc0_p (PATTERN (maybe_cc0_setter)))
- insn = maybe_cc0_setter;
- }
- }
-
- /* FIXME: What if something in cc0/jump uses value set in new insn? */
+ /* FIXME: What if something in jump uses value set in new insn? */
new_insn = emit_insn_before_noloc (pat, insn, bb);
}
s.insn = insn;
s.nsets = 0;
- note_stores (pattern, record_set_data, &s);
+ note_pattern_stores (pattern, record_set_data, &s);
/* Considered invariant insns have exactly one set. */
gcc_assert (s.nsets == 1);
/* Return if there's nothing to do, or it is too expensive. */
if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
- || is_too_expensive (_("PRE disabled")))
+ || gcse_or_cprop_is_too_expensive (_("PRE disabled")))
return 0;
/* We need alias. */
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, LABEL_REF_LABEL (x));
+ add_reg_note (insn, REG_LABEL_OPERAND, label_ref_label (x));
- if (LABEL_P (LABEL_REF_LABEL (x)))
- LABEL_NUSES (LABEL_REF_LABEL (x))++;
+ if (LABEL_P (label_ref_label (x)))
+ LABEL_NUSES (label_ref_label (x))++;
return;
}
static int
should_hoist_expr_to_dom (basic_block expr_bb, struct gcse_expr *expr,
- basic_block bb, sbitmap visited, int distance,
+ basic_block bb, sbitmap visited,
+ HOST_WIDE_INT distance,
int *bb_size, enum reg_class pressure_class,
int *nregs, bitmap hoisted_bbs, rtx_insn *from)
{
hoist_code (void)
{
basic_block bb, dominated;
- vec<basic_block> dom_tree_walk;
unsigned int dom_tree_walk_index;
- vec<basic_block> domby;
unsigned int i, j, k;
struct gcse_expr **index_map;
struct gcse_expr *expr;
if (flag_ira_hoist_pressure)
hoisted_bbs = BITMAP_ALLOC (NULL);
- dom_tree_walk = get_all_dominated_blocks (CDI_DOMINATORS,
- ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
+ auto_vec<basic_block> dom_tree_walk
+ = get_all_dominated_blocks (CDI_DOMINATORS,
+ ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
/* Walk over each basic block looking for potentially hoistable
expressions, nothing gets hoisted from the entry block. */
FOR_EACH_VEC_ELT (dom_tree_walk, dom_tree_walk_index, bb)
{
- domby = get_dominated_to_depth (CDI_DOMINATORS, bb, MAX_HOIST_DEPTH);
+ auto_vec<basic_block> domby
+ = get_dominated_to_depth (CDI_DOMINATORS, bb, param_max_hoist_depth);
if (domby.length () == 0)
continue;
computes the expression. */
FOR_EACH_VEC_ELT (domby, j, dominated)
{
- int max_distance;
+ HOST_WIDE_INT max_distance;
/* Ignore self dominance. */
if (bb == dominated)
bitmap_clear (from_bbs);
}
}
- domby.release ();
}
- dom_tree_walk.release ();
BITMAP_FREE (from_bbs);
if (flag_ira_hoist_pressure)
BITMAP_FREE (hoisted_bbs);
/* Return if there's nothing to do, or it is too expensive. */
if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
- || is_too_expensive (_("GCSE disabled")))
+ || gcse_or_cprop_is_too_expensive (_("GCSE disabled")))
return 0;
doing_code_hoisting_p = true;
ptr->expr = NULL;
ptr->pattern = x;
ptr->pattern_regs = NULL_RTX;
- ptr->loads = NULL;
- ptr->stores = NULL;
+ ptr->stores.create (0);
ptr->reaching_reg = NULL_RTX;
ptr->invalid = 0;
ptr->index = 0;
static void
free_ldst_entry (struct ls_expr * ptr)
{
- free_INSN_LIST_list (& ptr->loads);
- free_INSN_LIST_list (& ptr->stores);
+ ptr->stores.release ();
free (ptr);
}
print_rtl (file, ptr->pattern);
- fprintf (file, "\n Loads : ");
-
- if (ptr->loads)
- print_rtl (file, ptr->loads);
- else
- fprintf (file, "(nil)");
-
fprintf (file, "\n Stores : ");
-
- if (ptr->stores)
- print_rtl (file, ptr->stores);
- else
- fprintf (file, "(nil)");
+ print_rtx_insn_vec (file, ptr->stores);
fprintf (file, "\n\n");
}
{
rtx src = SET_SRC (PATTERN (insn));
rtx dest = SET_DEST (PATTERN (insn));
- rtx note = find_reg_equal_equiv_note (insn);
- rtx src_eq;
- /* Check for a simple LOAD... */
+ /* Check for a simple load. */
if (MEM_P (src) && simple_mem (src))
{
ptr = ldst_entry (src);
- if (REG_P (dest))
- ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
- else
+ if (!REG_P (dest))
ptr->invalid = 1;
}
else
invalidate_any_buried_refs (src);
}
- if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
- src_eq = XEXP (note, 0);
- else
- src_eq = NULL_RTX;
-
- if (src_eq != NULL_RTX
+ /* Check for a simple load through a REG_EQUAL note. */
+ rtx note = find_reg_equal_equiv_note (insn), src_eq;
+ if (note
+ && REG_NOTE_KIND (note) == REG_EQUAL
+ && (src_eq = XEXP (note, 0))
&& !(MEM_P (src_eq) && simple_mem (src_eq)))
invalidate_any_buried_refs (src_eq);
if (MEM_P (dest) && simple_mem (dest))
{
ptr = ldst_entry (dest);
-
+ machine_mode src_mode = GET_MODE (src);
if (! MEM_P (src)
&& GET_CODE (src) != ASM_OPERANDS
/* Check for REG manually since want_to_gcse_p
returns 0 for all REGs. */
- && can_assign_to_reg_without_clobbers_p (src))
- ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
+ && can_assign_to_reg_without_clobbers_p (src,
+ src_mode))
+ ptr->stores.safe_push (insn);
else
ptr->invalid = 1;
}
}
else
- invalidate_any_buried_refs (PATTERN (insn));
+ {
+ /* Invalidate all MEMs in the pattern and... */
+ invalidate_any_buried_refs (PATTERN (insn));
+
+ /* ...in REG_EQUAL notes for PARALLELs with single SET. */
+ rtx note = find_reg_equal_equiv_note (insn), src_eq;
+ if (note
+ && REG_NOTE_KIND (note) == REG_EQUAL
+ && (src_eq = XEXP (note, 0)))
+ invalidate_any_buried_refs (src_eq);
+ }
}
}
}
where reg is the reaching reg used in the load. We checked in
compute_ld_motion_mems that we can replace (set mem expr) with
(set reg expr) in that insn. */
- rtx list = mem_ptr->stores;
-
- for ( ; list != NULL_RTX; list = XEXP (list, 1))
+ rtx_insn *insn;
+ unsigned int i;
+ FOR_EACH_VEC_ELT_REVERSE (mem_ptr->stores, i, insn)
{
- rtx_insn *insn = as_a <rtx_insn *> (XEXP (list, 0));
rtx pat = PATTERN (insn);
rtx src = SET_SRC (pat);
rtx reg = expr->reaching_reg;
/* 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)
+bool
+gcse_or_cprop_is_too_expensive (const char *pass)
{
+ unsigned HOST_WIDE_INT memory_request
+ = ((unsigned HOST_WIDE_INT)n_basic_blocks_for_fn (cfun)
+ * SBITMAP_SET_SIZE (max_reg_num ()) * sizeof (SBITMAP_ELT_TYPE));
+
/* 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 allocating memory for the dataflow bitmaps would take up too much
storage it's better just to disable the optimization. */
- if ((n_basic_blocks_for_fn (cfun)
- * SBITMAP_SET_SIZE (max_reg_num ())
- * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
+ if (memory_request / 1024 > (unsigned HOST_WIDE_INT)param_max_gcse_memory)
{
warning (OPT_Wdisabled_optimization,
- "%s: %d basic blocks and %d registers",
- pass, n_basic_blocks_for_fn (cfun), max_reg_num ());
+ "%s: %d basic blocks and %d registers; "
+ "increase %<--param max-gcse-memory%> above %wu",
+ pass, n_basic_blocks_for_fn (cfun), max_reg_num (),
+ memory_request / 1024);
return true;
}