/* Post reload partially redundant load elimination
- Copyright (C) 2004, 2005
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2017 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "toplev.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 "real.h"
#include "insn-config.h"
+#include "emit-rtl.h"
#include "recog.h"
-#include "basic-block.h"
-#include "output.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 "gcse-common.h"
/* The following code implements gcse after reload, the purpose of this
pass is to cleanup redundant loads generated by reload and other
type 'struct expr', and for each expression there is a single linked
list of occurrences. */
-/* The table itself. */
-static htab_t expr_table;
-
/* Expression elements in the hash table. */
struct expr
{
/* 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 : nofree_ptr_hash <expr>
+{
+ static inline hashval_t hash (const expr *);
+ static inline bool equal (const expr *, const expr *);
+};
+
+
+/* Hash expression X.
+ DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
+ or if the expression contains something we don't want to insert in the
+ table. */
+
+static hashval_t
+hash_expr (rtx x, int *do_not_record_p)
+{
+ *do_not_record_p = 0;
+ return hash_rtx (x, GET_MODE (x), do_not_record_p,
+ NULL, /*have_reg_qty=*/false);
+}
+
+/* Callback for hashtab.
+ Return the hash value for expression EXP. We don't actually hash
+ here, we just return the cached hash value. */
+
+inline hashval_t
+expr_hasher::hash (const expr *exp)
+{
+ return exp->hash;
+}
+
+/* Callback for hashtab.
+ Return nonzero if exp1 is equivalent to exp2. */
+
+inline bool
+expr_hasher::equal (const expr *exp1, const expr *exp2)
+{
+ int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
+
+ gcc_assert (!equiv_p || exp1->hash == exp2->hash);
+ return equiv_p;
+}
+
+/* The table itself. */
+static hash_table<expr_hasher> *expr_table;
+\f
+
static struct obstack expr_obstack;
/* Occurrence of an expression.
/* Next occurrence of this expression. */
struct occr *next;
/* The insn that computes the expression. */
- rtx insn;
+ rtx_insn *insn;
/* Nonzero if this [anticipatable] occurrence has been deleted. */
char deleted_p;
};
{
struct unoccr *next;
edge pred;
- rtx insn;
+ rtx_insn *insn;
};
static struct obstack unoccr_obstack;
/* A list of insns that may modify memory within the current basic block. */
struct modifies_mem
{
- rtx insn;
+ rtx_insn *insn;
struct modifies_mem *next;
};
static struct modifies_mem *modifies_mem_list;
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 void free_mem (void);
/* Support for hash table construction and transformations. */
-static bool oprs_unchanged_p (rtx, rtx, bool);
-static void record_last_reg_set_info (rtx, int);
-static void record_last_mem_set_info (rtx);
-static void record_last_set_info (rtx, rtx, void *);
-static void record_opr_changes (rtx);
-
-static void find_mem_conflicts (rtx, rtx, void *);
+static bool oprs_unchanged_p (rtx, rtx_insn *, bool);
+static void record_last_reg_set_info (rtx_insn *, rtx);
+static void record_last_reg_set_info_regno (rtx_insn *, int);
+static void record_last_mem_set_info (rtx_insn *);
+static void record_last_set_info (rtx, const_rtx, void *);
+static void record_opr_changes (rtx_insn *);
+
+static void find_mem_conflicts (rtx, const_rtx, void *);
static int load_killed_in_block_p (int, rtx, bool);
static void reset_opr_set_tables (void);
/* Hash table support. */
static hashval_t hash_expr (rtx, int *);
-static hashval_t hash_expr_for_htab (const void *);
-static int expr_equiv_p (const void *, const void *);
-static void insert_expr_in_table (rtx, rtx);
+static void insert_expr_in_table (rtx, rtx_insn *);
static struct expr *lookup_expr_in_table (rtx);
-static int dump_hash_table_entry (void **, void *);
static void dump_hash_table (FILE *);
/* Helpers for eliminate_partially_redundant_load. */
static bool reg_killed_on_edge (rtx, edge);
static bool reg_used_on_edge (rtx, edge);
-static rtx reg_set_between_after_reload_p (rtx, rtx, rtx);
-static rtx reg_used_between_after_reload_p (rtx, rtx, rtx);
-static rtx get_avail_load_store_reg (rtx);
+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 void hash_scan_set (rtx);
+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);
/* The work horses of this pass. */
static void eliminate_partially_redundant_load (basic_block,
- rtx,
+ rtx_insn *,
struct expr *);
static void eliminate_partially_redundant_loads (void);
\f
{
int i;
basic_block bb;
- rtx insn;
+ rtx_insn *insn;
/* Find the largest UID and create a mapping from UIDs to CUIDs. */
- uid_cuid = xcalloc (get_max_uid () + 1, sizeof (int));
- i = 0;
- FOR_EACH_BB (bb)
+ uid_cuid = XCNEWVEC (int, get_max_uid () + 1);
+ i = 1;
+ FOR_EACH_BB_FN (bb, cfun)
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
make the hash table too small, but unnecessarily making it too large
also doesn't help. The i/4 is a gcse.c relic, and seems like a
reasonable choice. */
- expr_table = htab_create (MAX (i / 4, 13),
- hash_expr_for_htab, expr_equiv_p, NULL);
+ expr_table = new hash_table<expr_hasher> (MAX (i / 4, 13));
/* We allocate everything on obstacks because we often can roll back
the whole obstack to some point. Freeing obstacks is very fast. */
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. */
{
free (uid_cuid);
- htab_delete (expr_table);
+ delete expr_table;
+ expr_table = NULL;
obstack_free (&expr_obstack, NULL);
obstack_free (&occr_obstack, NULL);
obstack_free (&unoccr_obstack, NULL);
obstack_free (&modifies_mem_obstack, NULL);
- free (reg_avail_info);
-}
-\f
-
-/* Hash expression X.
- DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
- or if the expression contains something we don't want to insert in the
- table. */
-
-static hashval_t
-hash_expr (rtx x, int *do_not_record_p)
-{
- *do_not_record_p = 0;
- return hash_rtx (x, GET_MODE (x), do_not_record_p,
- NULL, /*have_reg_qty=*/false);
-}
-
-/* Callback for hashtab.
- Return the hash value for expression EXP. We don't actually hash
- here, we just return the cached hash value. */
-
-static hashval_t
-hash_expr_for_htab (const void *expp)
-{
- struct expr *exp = (struct expr *) expp;
- return exp->hash;
-}
-
-/* Callback for hashtab.
- Return nonzero if exp1 is equivalent to exp2. */
+ 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 ();
+ }
-static int
-expr_equiv_p (const void *exp1p, const void *exp2p)
-{
- struct expr *exp1 = (struct expr *) exp1p;
- struct expr *exp2 = (struct expr *) exp2p;
- int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
-
- gcc_assert (!equiv_p || exp1->hash == exp2->hash);
- return equiv_p;
+ 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
basic block. */
static void
-insert_expr_in_table (rtx x, rtx insn)
+insert_expr_in_table (rtx x, rtx_insn *insn)
{
int do_not_record_p;
hashval_t hash;
cur_expr->hash = hash;
cur_expr->avail_occr = NULL;
- slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr,
- hash, INSERT);
-
+ 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
/* Search for another occurrence in the same basic block. */
avail_occr = cur_expr->avail_occr;
- while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
+ 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. */
tmp_expr->hash = hash;
tmp_expr->avail_occr = NULL;
- slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr,
- hash, INSERT);
+ slot = expr_table->find_slot_with_hash (tmp_expr, hash, INSERT);
obstack_free (&expr_obstack, tmp_expr);
if (!slot)
expression hash table to FILE. */
/* This helper is called via htab_traverse. */
-static int
-dump_hash_table_entry (void **slot, void *filep)
+int
+dump_expr_hash_table_entry (expr **slot, FILE *file)
{
- struct expr *expr = (struct expr *) *slot;
- FILE *file = (FILE *) filep;
+ struct expr *exprs = *slot;
struct occr *occr;
fprintf (file, "expr: ");
- print_rtl (file, expr->expr);
- fprintf (file,"\nhashcode: %u\n", expr->hash);
- fprintf (file,"list of occurences:\n");
- occr = expr->avail_occr;
+ print_rtl (file, exprs->expr);
+ fprintf (file,"\nhashcode: %u\n", exprs->hash);
+ fprintf (file,"list of occurrences:\n");
+ occr = exprs->avail_occr;
while (occr)
{
- rtx insn = occr->insn;
+ rtx_insn *insn = occr->insn;
print_rtl_single (file, insn);
fprintf (file, "\n");
occr = occr->next;
{
fprintf (file, "\n\nexpression hash table\n");
fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
- (long) htab_size (expr_table),
- (long) htab_elements (expr_table),
- htab_collisions (expr_table));
- if (htab_elements (expr_table) > 0)
+ (long) expr_table->size (),
+ (long) expr_table->elements (),
+ expr_table->collisions ());
+ if (expr_table->elements () > 0)
{
fprintf (file, "\n\ntable entries:\n");
- htab_traverse (expr_table, dump_hash_table_entry, file);
+ expr_table->traverse <FILE *, dump_expr_hash_table_entry> (file);
}
fprintf (file, "\n");
}
\f
+/* Return true if register X is recorded as being set by an instruction
+ whose CUID is greater than the one given. */
+
+static bool
+reg_changed_after_insn_p (rtx x, int cuid)
+{
+ unsigned int regno, end_regno;
+
+ regno = REGNO (x);
+ end_regno = END_REGNO (x);
+ do
+ if (reg_avail_info[regno] > cuid)
+ return true;
+ while (++regno < end_regno);
+ return false;
+}
/* Return nonzero if the operands of expression X are unchanged
1) from the start of INSN's basic block up to but not including INSN
2) from INSN to the end of INSN's basic block if AFTER_INSN is true. */
static bool
-oprs_unchanged_p (rtx x, rtx insn, bool after_insn)
+oprs_unchanged_p (rtx x, rtx_insn *insn, bool after_insn)
{
int i, j;
enum rtx_code code;
/* We are called after register allocation. */
gcc_assert (REGNO (x) < FIRST_PSEUDO_REGISTER);
if (after_insn)
- /* If the last CUID setting the insn is less than the CUID of
- INSN, then reg X is not changed in or after INSN. */
- return reg_avail_info[REGNO (x)] < INSN_CUID (insn);
+ return !reg_changed_after_insn_p (x, INSN_CUID (insn) - 1);
else
- /* Reg X is not set before INSN in the current basic block if
- we have not yet recorded the CUID of an insn that touches
- the reg. */
- return reg_avail_info[REGNO (x)] == 0;
+ return !reg_changed_after_insn_p (x, 0);
case MEM:
if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn))
case PC:
case CC0: /*FIXME*/
case CONST:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST_VECTOR:
+ CASE_CONST_ANY:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
to a nonzero value. */
static void
-find_mem_conflicts (rtx dest, rtx setter ATTRIBUTE_UNUSED,
+find_mem_conflicts (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
void *data)
{
rtx mem_op = (rtx) data;
if (! MEM_P (dest))
return;
- if (true_dependence (dest, GET_MODE (dest), mem_op,
- rtx_addr_varies_p))
+ if (true_dependence (dest, GET_MODE (dest), mem_op))
mems_conflict_p = 1;
}
\f
while (list_entry)
{
- rtx setter = list_entry->insn;
+ rtx_insn *setter = list_entry->insn;
/* Ignore entries in the list that do not apply. */
if ((after_insn
/* Record register first/last/block set information for REGNO in INSN. */
static inline void
-record_last_reg_set_info (rtx insn, int regno)
+record_last_reg_set_info (rtx_insn *insn, rtx reg)
+{
+ unsigned int regno, end_regno;
+
+ regno = REGNO (reg);
+ end_regno = END_REGNO (reg);
+ do
+ reg_avail_info[regno] = INSN_CUID (insn);
+ while (++regno < end_regno);
+}
+
+static inline void
+record_last_reg_set_info_regno (rtx_insn *insn, int regno)
{
reg_avail_info[regno] = INSN_CUID (insn);
}
a CALL_INSN). We merely need to record which insns modify memory. */
static void
-record_last_mem_set_info (rtx insn)
+record_last_mem_set_info (rtx_insn *insn)
{
struct modifies_mem *list_entry;
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
the SET is taking place. */
static void
-record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
+record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
{
- rtx last_set_insn = (rtx) data;
+ rtx_insn *last_set_insn = (rtx_insn *) data;
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (REG_P (dest))
- record_last_reg_set_info (last_set_insn, REGNO (dest));
- else if (MEM_P (dest)
- /* Ignore pushes, they clobber nothing. */
- && ! push_operand (dest, GET_MODE (dest)))
- record_last_mem_set_info (last_set_insn);
+ record_last_reg_set_info (last_set_insn, dest);
+ else if (MEM_P (dest))
+ {
+ /* Ignore pushes, they don't clobber memory. They may still
+ clobber the stack pointer though. Some targets do argument
+ pushes without adding REG_INC notes. See e.g. PR25196,
+ where a pushsi2 on i386 doesn't have REG_INC notes. Note
+ such changes here too. */
+ if (! push_operand (dest, GET_MODE (dest)))
+ record_last_mem_set_info (last_set_insn);
+ else
+ record_last_reg_set_info_regno (last_set_insn, STACK_POINTER_REGNUM);
+ }
}
This data is used by oprs_unchanged_p. */
static void
-record_opr_changes (rtx insn)
+record_opr_changes (rtx_insn *insn)
{
rtx note;
/* Also record autoincremented REGs for this insn as changed. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_INC)
- record_last_reg_set_info (insn, REGNO (XEXP (note, 0)));
+ record_last_reg_set_info (insn, XEXP (note, 0));
/* Finally, if this is a call, record all call clobbers. */
if (CALL_P (insn))
{
unsigned int regno;
-
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
- record_last_reg_set_info (insn, regno);
-
- if (! CONST_OR_PURE_CALL_P (insn))
+ rtx link, x;
+ hard_reg_set_iterator hrsi;
+ EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 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);
}
}
After reload we are interested in loads/stores only. */
static void
-hash_scan_set (rtx insn)
+hash_scan_set (rtx_insn *insn)
{
rtx pat = PATTERN (insn);
rtx src = SET_SRC (pat);
can_copy_p (GET_MODE (dest))
/* Is SET_SRC something we want to gcse? */
&& general_operand (src, GET_MODE (src))
+#ifdef STACK_REGS
+ /* Never consider insns touching the register stack. It may
+ create situations that reg-stack cannot handle (e.g. a stack
+ register live across an abnormal edge). */
+ && (REGNO (dest) < FIRST_STACK_REG || REGNO (dest) > LAST_STACK_REG)
+#endif
/* An expression is not available if its operands are
subsequently modified, including this insn. */
&& oprs_unchanged_p (src, insn, true))
can_copy_p (GET_MODE (src))
/* Is SET_DEST something we want to gcse? */
&& general_operand (dest, GET_MODE (dest))
+#ifdef STACK_REGS
+ /* As above for STACK_REGS. */
+ && (REGNO (src) < FIRST_STACK_REG || REGNO (src) > LAST_STACK_REG)
+#endif
&& ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
/* Check if the memory expression is killed after insn. */
&& ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
{
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- rtx insn;
+ rtx_insn *insn;
/* First pass over the instructions records information used to
determine when registers and memory are last set.
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)))
return false;
}
\f
-
-/* Return the insn that sets register REG or clobbers it in between
- FROM_INSN and TO_INSN (exclusive of those two).
- Just like reg_set_between but for hard registers and not pseudos. */
-
-static rtx
-reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
-{
- rtx insn;
-
- /* We are called after register allocation. */
- gcc_assert (REG_P (reg) && REGNO (reg) < FIRST_PSEUDO_REGISTER);
-
- if (from_insn == to_insn)
- return NULL_RTX;
-
- for (insn = NEXT_INSN (from_insn);
- insn != to_insn;
- insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- {
- if (set_of (reg, insn) != NULL_RTX)
- return insn;
- if ((CALL_P (insn)
- && call_used_regs[REGNO (reg)])
- || find_reg_fusage (insn, CLOBBER, reg))
- return insn;
-
- if (FIND_REG_INC_NOTE (insn, reg))
- return insn;
- }
-
- return NULL_RTX;
-}
-
-/* Return the insn that uses register REG in between FROM_INSN and TO_INSN
- (exclusive of those two). Similar to reg_used_between but for hard
- registers and not pseudos. */
-
-static rtx
-reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
-{
- rtx insn;
-
- /* We are called after register allocation. */
- gcc_assert (REG_P (reg) && REGNO (reg) < FIRST_PSEUDO_REGISTER);
-
- if (from_insn == to_insn)
- return NULL_RTX;
-
- for (insn = NEXT_INSN (from_insn);
- insn != to_insn;
- insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- {
- if (reg_overlap_mentioned_p (reg, PATTERN (insn))
- || (CALL_P (insn)
- && call_used_regs[REGNO (reg)])
- || find_reg_fusage (insn, USE, reg)
- || find_reg_fusage (insn, CLOBBER, reg))
- return insn;
-
- if (FIND_REG_INC_NOTE (insn, reg))
- return insn;
- }
-
- return NULL_RTX;
-}
-
-/* Return true if REG is used, set, or killed between the beginning of
- basic block BB and UP_TO_INSN. Caches the result in reg_avail_info. */
-
-static bool
-reg_set_or_used_since_bb_start (rtx reg, basic_block bb, rtx up_to_insn)
-{
- rtx insn, start = PREV_INSN (BB_HEAD (bb));
-
- if (reg_avail_info[REGNO (reg)] != 0)
- return true;
-
- insn = reg_used_between_after_reload_p (reg, start, up_to_insn);
- if (! insn)
- insn = reg_set_between_after_reload_p (reg, start, up_to_insn);
-
- if (insn)
- reg_avail_info[REGNO (reg)] = INSN_CUID (insn);
-
- return insn != NULL_RTX;
-}
-
/* Return the loaded/stored register of a load/store instruction. */
static rtx
-get_avail_load_store_reg (rtx insn)
+get_avail_load_store_reg (rtx_insn *insn)
{
if (REG_P (SET_DEST (PATTERN (insn))))
/* A load. */
- return SET_DEST(PATTERN(insn));
+ return SET_DEST (PATTERN (insn));
else
{
/* A store. */
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)
return false;
- if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
+ if (tablejump_p (BB_END (pred->src), NULL, NULL))
return false;
}
return true;
/* 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 (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.
a redundancy is also worth doing, assuming it is possible. */
static void
-eliminate_partially_redundant_load (basic_block bb, rtx insn,
+eliminate_partially_redundant_load (basic_block bb, rtx_insn *insn,
struct expr *expr)
{
edge pred;
- rtx avail_insn = NULL_RTX;
+ rtx_insn *avail_insn = NULL;
rtx avail_reg;
rtx dest, pat;
struct occr *a_occr;
/* Check that the loaded register is not used, set, or killed from the
beginning of the block. */
- if (reg_set_or_used_since_bb_start (dest, bb, insn))
+ if (reg_changed_after_insn_p (dest, 0)
+ || reg_used_between_p (dest, PREV_INSN (BB_HEAD (bb)), insn))
return;
/* Check potential for replacing load with copy for predecessors. */
FOR_EACH_EDGE (pred, ei, bb->preds)
{
- rtx next_pred_bb_end;
+ rtx_insn *next_pred_bb_end;
- avail_insn = NULL_RTX;
+ 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;
avail_reg = get_avail_load_store_reg (avail_insn);
gcc_assert (avail_reg);
-
+
/* 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;
}
- if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
- next_pred_bb_end))
+ 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;
else
else /* Its a dead move no need to generate. */
continue;
occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
- sizeof (struct occr));
+ sizeof (struct unoccr));
occr->insn = avail_insn;
occr->pred = pred;
occr->next = avail_occrs;
}
else
{
- /* Adding a load on a critical edge will cuase a split. */
+ /* 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;
unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
sizeof (struct unoccr));
- unoccr->insn = NULL_RTX;
+ unoccr->insn = NULL;
unoccr->pred = pred;
unoccr->next = unavail_occrs;
unavail_occrs = unoccr;
if (/* No load can be replaced by copy. */
npred_ok == 0
- /* Prevent exploding the code. */
- || (optimize_size && npred_ok > 1)
- /* If we don't have profile information we cannot tell if splitting
+ /* Prevent exploding the code. */
+ || (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
|| targetm.cannot_modify_jumps_p ())
/* 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
eliminate_partially_redundant_loads (void)
{
- rtx insn;
+ rtx_insn *insn;
basic_block bb;
/* Note we start at block 1. */
- if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+ if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
return;
FOR_BB_BETWEEN (bb,
- ENTRY_BLOCK_PTR->next_bb->next_bb,
- EXIT_BLOCK_PTR,
+ ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
+ EXIT_BLOCK_PTR_FOR_FN (cfun),
next_bb)
{
/* Don't try anything on basic blocks with strange predecessors. */
continue;
/* Do not try anything on cold basic blocks. */
- if (probably_cold_bb_p (bb))
+ if (optimize_bb_for_size_p (bb))
continue;
/* Reset the table of things changed since the start of the current
/* Are the operands unchanged since the start of the
block? */
&& oprs_unchanged_p (src, insn, false)
- && !(flag_non_call_exceptions && may_trap_p (src))
+ && !(cfun->can_throw_non_call_exceptions && may_trap_p (src))
&& !side_effects_p (src)
/* Is the expression recorded? */
&& (expr = lookup_expr_in_table (src)) != NULL)
marked for later deletion. */
/* This helper is called via htab_traverse. */
-static int
-delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
+int
+delete_redundant_insns_1 (expr **slot, void *data ATTRIBUTE_UNUSED)
{
- struct expr *expr = (struct expr *) *slot;
+ struct expr *exprs = *slot;
struct occr *occr;
- for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
+ for (occr = exprs->avail_occr; occr != NULL; occr = occr->next)
{
- if (occr->deleted_p)
+ if (occr->deleted_p && dbg_cnt (gcse2_delete))
{
delete_insn (occr->insn);
stats.insns_deleted++;
static void
delete_redundant_insns (void)
{
- htab_traverse (expr_table, delete_redundant_insns_1, NULL);
+ expr_table->traverse <void *, delete_redundant_insns_1> (NULL);
if (dump_file)
fprintf (dump_file, "\n");
}
/* Main entry point of the GCSE after reload - clean some redundant loads
due to spilling. */
-void
+static void
gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
{
memset (&stats, 0, sizeof (stats));
- /* Allocate ememory for this pass.
+ /* Allocate memory for this pass.
Also computes and initializes the insns' CUIDs. */
alloc_mem ();
if (dump_file)
dump_hash_table (dump_file);
- if (htab_elements (expr_table) > 0)
+ if (expr_table->elements () > 0)
{
+ /* 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 ();
+ /* This can not 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);
eliminate_partially_redundant_loads ();
delete_redundant_insns ();
+ sbitmap_vector_free (transp);
if (dump_file)
{
fprintf (dump_file, "insns deleted: %d\n", stats.insns_deleted);
fprintf (dump_file, "\n\n");
}
+
+ statistics_counter_event (cfun, "copies inserted",
+ stats.copies_inserted);
+ statistics_counter_event (cfun, "moves inserted",
+ stats.moves_inserted);
+ statistics_counter_event (cfun, "insns deleted",
+ stats.insns_deleted);
}
-
+
/* We are finished with alias. */
end_alias_analysis ();
free_mem ();
}
+\f
+
+static unsigned int
+rest_of_handle_gcse2 (void)
+{
+ gcse_after_reload_main (get_insns ());
+ rebuild_jump_labels (get_insns ());
+ return 0;
+}
+
+namespace {
+
+const pass_data pass_data_gcse2 =
+{
+ RTL_PASS, /* type */
+ "gcse2", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_GCSE_AFTER_RELOAD, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_gcse2 : public rtl_opt_pass
+{
+public:
+ pass_gcse2 (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_gcse2, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *fun)
+ {
+ return (optimize > 0 && flag_gcse_after_reload
+ && optimize_function_for_speed_p (fun));
+ }
+
+ virtual unsigned int execute (function *) { return rest_of_handle_gcse2 (); }
+
+}; // class pass_gcse2
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_gcse2 (gcc::context *ctxt)
+{
+ return new pass_gcse2 (ctxt);
+}
projects / thirdparty / gcc.git / blobdiff