/* Post reload partially redundant load elimination
- Copyright (C) 2004-2014 Free Software Foundation, Inc.
+ Copyright (C) 2004-2020 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "diagnostic-core.h"
-
-#include "hash-table.h"
+#include "backend.h"
+#include "target.h"
#include "rtl.h"
#include "tree.h"
+#include "predict.h"
+#include "df.h"
+#include "memmodel.h"
#include "tm_p.h"
-#include "regs.h"
-#include "hard-reg-set.h"
-#include "flags.h"
#include "insn-config.h"
+#include "emit-rtl.h"
#include "recog.h"
-#include "basic-block.h"
-#include "function.h"
+
+#include "cfgrtl.h"
+#include "profile.h"
#include "expr.h"
-#include "except.h"
-#include "intl.h"
-#include "obstack.h"
-#include "hashtab.h"
-#include "params.h"
-#include "target.h"
#include "tree-pass.h"
#include "dbgcnt.h"
+#include "intl.h"
+#include "gcse-common.h"
+#include "gcse.h"
+#include "regs.h"
+#include "function-abi.h"
/* The following code implements gcse after reload, the purpose of this
pass is to cleanup redundant loads generated by reload and other
/* The same hash for this entry. */
hashval_t hash;
+ /* Index in the transparent bitmaps. */
+ unsigned int bitmap_index;
+
/* List of available occurrence in basic blocks in the function. */
struct occr *avail_occr;
};
/* Hashtable helpers. */
-struct expr_hasher : typed_noop_remove <expr>
+struct expr_hasher : nofree_ptr_hash <expr>
{
- typedef expr value_type;
- typedef expr compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const expr *);
+ static inline bool equal (const expr *, const expr *);
};
here, we just return the cached hash value. */
inline hashval_t
-expr_hasher::hash (const value_type *exp)
+expr_hasher::hash (const expr *exp)
{
return exp->hash;
}
Return nonzero if exp1 is equivalent to exp2. */
inline bool
-expr_hasher::equal (const value_type *exp1, const compare_type *exp2)
+expr_hasher::equal (const expr *exp1, const expr *exp2)
{
int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
block, have no gaps, and only apply to real insns. */
static int *uid_cuid;
#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
+
+/* Bitmap of blocks which have memory stores. */
+static bitmap modify_mem_list_set;
+
+/* Bitmap of blocks which have calls. */
+static bitmap blocks_with_calls;
+
+/* Vector indexed by block # with a list of all the insns that
+ modify memory within the block. */
+static vec<rtx_insn *> *modify_mem_list;
+
+/* Vector indexed by block # with a canonicalized list of insns
+ that modify memory in the block. */
+static vec<modify_pair> *canon_modify_mem_list;
+
+/* Vector of simple bitmaps indexed by block number. Each component sbitmap
+ indicates which expressions are transparent through the block. */
+static sbitmap *transp;
\f
/* Helpers for memory allocation/freeing. */
static rtx get_avail_load_store_reg (rtx_insn *);
static bool bb_has_well_behaved_predecessors (basic_block);
-static struct occr* get_bb_avail_insn (basic_block, struct occr *);
+static struct occr* get_bb_avail_insn (basic_block, struct occr *, int);
static void hash_scan_set (rtx_insn *);
static void compute_hash_table (void);
modifies_mem_obstack_bottom =
(struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
sizeof (struct modifies_mem));
+
+ blocks_with_calls = BITMAP_ALLOC (NULL);
+ modify_mem_list_set = BITMAP_ALLOC (NULL);
+
+ modify_mem_list = (vec_rtx_heap *) xcalloc (last_basic_block_for_fn (cfun),
+ sizeof (vec_rtx_heap));
+ canon_modify_mem_list
+ = (vec_modify_pair_heap *) xcalloc (last_basic_block_for_fn (cfun),
+ sizeof (vec_modify_pair_heap));
}
/* Free memory allocated by alloc_mem. */
obstack_free (&unoccr_obstack, NULL);
obstack_free (&modifies_mem_obstack, NULL);
+ unsigned i;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
+ {
+ modify_mem_list[i].release ();
+ canon_modify_mem_list[i].release ();
+ }
+
+ BITMAP_FREE (blocks_with_calls);
+ BITMAP_FREE (modify_mem_list_set);
free (reg_avail_info);
+ free (modify_mem_list);
+ free (canon_modify_mem_list);
}
\f
int do_not_record_p;
hashval_t hash;
struct expr *cur_expr, **slot;
- struct occr *avail_occr, *last_occr = NULL;
+ struct occr *avail_occr;
hash = hash_expr (x, &do_not_record_p);
slot = expr_table->find_slot_with_hash (cur_expr, hash, INSERT);
if (! (*slot))
- /* The expression isn't found, so insert it. */
- *slot = cur_expr;
+ {
+ /* The expression isn't found, so insert it. */
+ *slot = cur_expr;
+
+ /* Anytime we add an entry to the table, record the index
+ of the new entry. The bitmap index starts counting
+ at zero. */
+ cur_expr->bitmap_index = expr_table->elements () - 1;
+ }
else
{
/* The expression is already in the table, so roll back the
cur_expr = *slot;
}
- /* Search for another occurrence in the same basic block. */
+ /* Search for another occurrence in the same basic block. We insert
+ insns blockwise from start to end, so keep appending to the
+ start of the list so we have to check only a single element. */
avail_occr = cur_expr->avail_occr;
- while (avail_occr
- && BLOCK_FOR_INSN (avail_occr->insn) != BLOCK_FOR_INSN (insn))
- {
- /* If an occurrence isn't found, save a pointer to the end of
- the list. */
- last_occr = avail_occr;
- avail_occr = avail_occr->next;
- }
-
- if (avail_occr)
- /* Found another instance of the expression in the same basic block.
- Prefer this occurrence to the currently recorded one. We want
- the last one in the block and the block is scanned from start
- to end. */
+ if (avail_occr
+ && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
avail_occr->insn = insn;
else
{
/* First occurrence of this expression in this basic block. */
avail_occr = (struct occr *) obstack_alloc (&occr_obstack,
sizeof (struct occr));
-
- /* First occurrence of this expression in any block? */
- if (cur_expr->avail_occr == NULL)
- cur_expr->avail_occr = avail_occr;
- else
- last_occr->next = avail_occr;
-
avail_occr->insn = insn;
- avail_occr->next = NULL;
+ avail_occr->next = cur_expr->avail_occr;
avail_occr->deleted_p = 0;
+ cur_expr->avail_occr = avail_occr;
}
}
\f
(long) expr_table->size (),
(long) expr_table->elements (),
expr_table->collisions ());
- if (expr_table->elements () > 0)
+ if (!expr_table->is_empty ())
{
fprintf (file, "\n\ntable entries:\n");
expr_table->traverse <FILE *, dump_expr_hash_table_entry> (file);
unsigned int regno, end_regno;
regno = REGNO (x);
- end_regno = END_HARD_REGNO (x);
+ end_regno = END_REGNO (x);
do
if (reg_avail_info[regno] > cuid)
return true;
It will set mems_conflict_p to nonzero if there may be a
conflict between X and SETTER. */
mems_conflict_p = 0;
- note_stores (PATTERN (setter), find_mem_conflicts, x);
+ note_stores (setter, find_mem_conflicts, x);
if (mems_conflict_p)
return 1;
unsigned int regno, end_regno;
regno = REGNO (reg);
- end_regno = END_HARD_REGNO (reg);
+ end_regno = END_REGNO (reg);
do
reg_avail_info[regno] = INSN_CUID (insn);
while (++regno < end_regno);
list_entry->insn = insn;
list_entry->next = modifies_mem_list;
modifies_mem_list = list_entry;
+
+ record_last_mem_set_info_common (insn, modify_mem_list,
+ canon_modify_mem_list,
+ modify_mem_list_set,
+ blocks_with_calls);
}
/* Called from compute_hash_table via note_stores to handle one
rtx note;
/* Find all stores and record them. */
- note_stores (PATTERN (insn), record_last_set_info, insn);
+ note_stores (insn, record_last_set_info, insn);
/* Also record autoincremented REGs for this insn as changed. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (CALL_P (insn))
{
unsigned int regno;
- rtx link, x;
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_regno (insn, regno);
- for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
- if (GET_CODE (XEXP (link, 0)) == CLOBBER)
- {
- x = XEXP (XEXP (link, 0), 0);
- if (REG_P (x))
- {
- gcc_assert (HARD_REGISTER_P (x));
- record_last_reg_set_info (insn, x);
- }
- }
-
if (! RTL_CONST_OR_PURE_CALL_P (insn))
record_last_mem_set_info (insn);
}
static bool
reg_killed_on_edge (rtx reg, edge e)
{
- rtx insn;
+ rtx_insn *insn;
for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn) && reg_set_p (reg, insn))
static bool
reg_used_on_edge (rtx reg, edge e)
{
- rtx insn;
+ rtx_insn *insn;
for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
FOR_EACH_EDGE (pred, ei, bb->preds)
{
- if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
+ /* commit_one_edge_insertion refuses to insert on abnormal edges even if
+ the source has only one successor so EDGE_CRITICAL_P is too weak. */
+ if ((pred->flags & EDGE_ABNORMAL) && !single_pred_p (pred->dest))
return false;
if ((pred->flags & EDGE_ABNORMAL_CALL) && cfun->has_nonlocal_label)
/* Search for the occurrences of expression in BB. */
static struct occr*
-get_bb_avail_insn (basic_block bb, struct occr *occr)
+get_bb_avail_insn (basic_block bb, struct occr *orig_occr, int bitmap_index)
{
+ struct occr *occr = orig_occr;
+
for (; occr != NULL; occr = occr->next)
if (BLOCK_FOR_INSN (occr->insn) == bb)
return occr;
+
+ /* If we could not find an occurrence in BB, see if BB
+ has a single predecessor with an occurrence that is
+ transparent through BB. */
+ if (transp
+ && single_pred_p (bb)
+ && bitmap_bit_p (transp[bb->index], bitmap_index)
+ && (occr = get_bb_avail_insn (single_pred (bb), orig_occr, bitmap_index)))
+ {
+ rtx avail_reg = get_avail_load_store_reg (occr->insn);
+ if (!reg_set_between_p (avail_reg,
+ PREV_INSN (BB_HEAD (bb)),
+ NEXT_INSN (BB_END (bb)))
+ && !reg_killed_on_edge (avail_reg, single_pred_edge (bb)))
+ return occr;
+ }
+
return NULL;
}
+/* This helper is called via htab_traverse. */
+int
+compute_expr_transp (expr **slot, FILE *dump_file ATTRIBUTE_UNUSED)
+{
+ struct expr *expr = *slot;
+
+ compute_transp (expr->expr, expr->bitmap_index, transp,
+ blocks_with_calls, modify_mem_list_set,
+ canon_modify_mem_list);
+ return 1;
+}
+
/* This handles the case where several stores feed a partially redundant
load. It checks if the redundancy elimination is possible and if it's
worth it.
struct unoccr *occr, *avail_occrs = NULL;
struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
int npred_ok = 0;
- gcov_type ok_count = 0; /* Redundant load execution count. */
- gcov_type critical_count = 0; /* Execution count of critical edges. */
+ profile_count ok_count = profile_count::zero ();
+ /* Redundant load execution count. */
+ profile_count critical_count = profile_count::zero ();
+ /* Execution count of critical edges. */
edge_iterator ei;
bool critical_edge_split = false;
/* The execution count of the loads to be added to make the
load fully redundant. */
- gcov_type not_ok_count = 0;
+ profile_count not_ok_count = profile_count::zero ();
basic_block pred_bb;
pat = PATTERN (insn);
avail_insn = NULL;
avail_reg = NULL_RTX;
pred_bb = pred->src;
- next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
- for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
- a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
+ for (a_occr = get_bb_avail_insn (pred_bb,
+ expr->avail_occr,
+ expr->bitmap_index);
+ a_occr;
+ a_occr = get_bb_avail_insn (pred_bb,
+ a_occr->next,
+ expr->bitmap_index))
{
/* Check if the loaded register is not used. */
avail_insn = a_occr->insn;
/* Make sure we can generate a move from register avail_reg to
dest. */
- extract_insn (gen_move_insn (copy_rtx (dest),
- copy_rtx (avail_reg)));
- if (! constrain_operands (1)
+ rtx_insn *move = gen_move_insn (copy_rtx (dest),
+ copy_rtx (avail_reg));
+ extract_insn (move);
+ if (! constrain_operands (1, get_preferred_alternatives (insn,
+ pred_bb))
|| reg_killed_on_edge (avail_reg, pred)
|| reg_used_on_edge (dest, pred))
{
avail_insn = NULL;
continue;
}
+ next_pred_bb_end = NEXT_INSN (BB_END (BLOCK_FOR_INSN (avail_insn)));
if (!reg_set_between_p (avail_reg, avail_insn, next_pred_bb_end))
/* AVAIL_INSN remains non-null. */
break;
avail_insn = NULL;
}
- if (EDGE_CRITICAL_P (pred))
- critical_count += pred->count;
+ if (EDGE_CRITICAL_P (pred) && pred->count ().initialized_p ())
+ critical_count += pred->count ();
if (avail_insn != NULL_RTX)
{
npred_ok++;
- ok_count += pred->count;
+ if (pred->count ().initialized_p ())
+ ok_count = ok_count + pred->count ();
if (! set_noop_p (PATTERN (gen_move_insn (copy_rtx (dest),
copy_rtx (avail_reg)))))
{
/* Adding a load on a critical edge will cause a split. */
if (EDGE_CRITICAL_P (pred))
critical_edge_split = true;
- not_ok_count += pred->count;
+ if (pred->count ().initialized_p ())
+ not_ok_count = not_ok_count + pred->count ();
unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
sizeof (struct unoccr));
unoccr->insn = NULL;
|| (optimize_bb_for_size_p (bb) && npred_ok > 1)
/* If we don't have profile information we cannot tell if splitting
a critical edge is profitable or not so don't do it. */
- || ((! profile_info || ! flag_branch_probabilities
+ || ((!profile_info || profile_status_for_fn (cfun) != PROFILE_READ
|| targetm.cannot_modify_jumps_p ())
&& critical_edge_split))
goto cleanup;
/* Check if it's worth applying the partial redundancy elimination. */
- if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
+ if (ok_count.to_gcov_type ()
+ < param_gcse_after_reload_partial_fraction * not_ok_count.to_gcov_type ())
goto cleanup;
- if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
+
+ gcov_type threshold;
+#if (GCC_VERSION >= 5000)
+ if (__builtin_mul_overflow (param_gcse_after_reload_critical_fraction,
+ critical_count.to_gcov_type (), &threshold))
+ threshold = profile_count::max_count;
+#else
+ threshold
+ = (param_gcse_after_reload_critical_fraction
+ * critical_count.to_gcov_type ());
+#endif
+
+ if (ok_count.to_gcov_type () < threshold)
goto cleanup;
/* Generate moves to the loaded register from where
/* Delete the insn if it is not available in this block and mark it
for deletion if it is available. If insn is available it may help
discover additional redundancies, so mark it for later deletion. */
- for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
+ for (a_occr = get_bb_avail_insn (bb, expr->avail_occr, expr->bitmap_index);
a_occr && (a_occr->insn != insn);
- a_occr = get_bb_avail_insn (bb, a_occr->next))
+ a_occr = get_bb_avail_insn (bb, a_occr->next, expr->bitmap_index))
;
if (!a_occr)
static void
gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
{
+ /* Disable computing transparentness if it is too expensive. */
+ bool do_transp
+ = !gcse_or_cprop_is_too_expensive (_("using simple load CSE after register "
+ "allocation"));
memset (&stats, 0, sizeof (stats));
if (dump_file)
dump_hash_table (dump_file);
- if (expr_table->elements () > 0)
+ if (!expr_table->is_empty ())
{
+ /* Knowing which MEMs are transparent through a block can signifiantly
+ increase the number of redundant loads found. So compute transparency
+ information for each memory expression in the hash table. */
+ df_analyze ();
+ if (do_transp)
+ {
+ /* This cannot be part of the normal allocation routine because
+ we have to know the number of elements in the hash table. */
+ transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
+ expr_table->elements ());
+ bitmap_vector_ones (transp, last_basic_block_for_fn (cfun));
+ expr_table->traverse <FILE *, compute_expr_transp> (dump_file);
+ }
+ else
+ transp = NULL;
eliminate_partially_redundant_loads ();
delete_redundant_insns ();
+ if (do_transp)
+ sbitmap_vector_free (transp);
if (dump_file)
{
projects / gcc.git / blobdiff