/* Global constant/copy propagation for RTL.
- Copyright (C) 1997-2014 Free Software Foundation, Inc.
+ Copyright (C) 1997-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "tm.h"
#include "diagnostic-core.h"
#include "toplev.h"
-
#include "rtl.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
#include "tm_p.h"
#include "regs.h"
#include "flags.h"
#include "insn-config.h"
#include "recog.h"
-#include "basic-block.h"
+#include "predict.h"
#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfgrtl.h"
+#include "cfganal.h"
+#include "lcm.h"
+#include "cfgcleanup.h"
+#include "basic-block.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "except.h"
#include "params.h"
+#include "alloc-pool.h"
#include "cselib.h"
#include "intl.h"
#include "obstack.h"
#include "tree-pass.h"
-#include "hashtab.h"
#include "df.h"
#include "dbgcnt.h"
#include "target.h"
There is one per basic block. If a pattern appears more than once the
last appearance is used. */
-struct occr
+struct cprop_occr
{
/* Next occurrence of this expression. */
- struct occr *next;
+ struct cprop_occr *next;
/* The insn that computes the expression. */
rtx_insn *insn;
};
-typedef struct occr *occr_t;
+typedef struct cprop_occr *occr_t;
/* Hash table entry for assignment expressions. */
-struct expr
+struct cprop_expr
{
/* The expression (DEST := SRC). */
rtx dest;
/* Index in the available expression bitmaps. */
int bitmap_index;
/* Next entry with the same hash. */
- struct expr *next_same_hash;
+ struct cprop_expr *next_same_hash;
/* List of available occurrence in basic blocks in the function.
An "available occurrence" is one that is the last occurrence in the
basic block and whose operands are not modified by following statements
in the basic block [including this insn]. */
- struct occr *avail_occr;
+ struct cprop_occr *avail_occr;
};
/* Hash table for copy propagation expressions.
{
/* The table itself.
This is an array of `set_hash_table_size' elements. */
- struct expr **table;
+ struct cprop_expr **table;
/* Size of the hash table, in elements. */
unsigned int size;
{
bool found = false;
unsigned int hash;
- struct expr *cur_expr, *last_expr = NULL;
- struct occr *cur_occr;
+ struct cprop_expr *cur_expr, *last_expr = NULL;
+ struct cprop_occr *cur_occr;
hash = hash_mod (REGNO (dest), table->size);
if (! found)
{
- cur_expr = GOBNEW (struct expr);
- bytes_used += sizeof (struct expr);
+ cur_expr = GOBNEW (struct cprop_expr);
+ bytes_used += sizeof (struct cprop_expr);
if (table->table[hash] == NULL)
/* This is the first pattern that hashed to this index. */
table->table[hash] = cur_expr;
else
{
/* First occurrence of this expression in this basic block. */
- cur_occr = GOBNEW (struct occr);
- bytes_used += sizeof (struct occr);
+ cur_occr = GOBNEW (struct cprop_occr);
+ bytes_used += sizeof (struct cprop_occr);
cur_occr->insn = insn;
cur_occr->next = cur_expr->avail_occr;
cur_expr->avail_occr = cur_occr;
return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
}
+/* Determine whether the rtx X should be treated as a register that can
+ be propagated. Any pseudo-register is fine. */
+
+static bool
+cprop_reg_p (const_rtx x)
+{
+ return REG_P (x) && !HARD_REGISTER_P (x);
+}
+
/* Scan SET present in INSN and add an entry to the hash TABLE.
IMPLICIT is true if it's an implicit set, false otherwise. */
rtx src = SET_SRC (set);
rtx dest = SET_DEST (set);
- if (REG_P (dest)
- && ! HARD_REGISTER_P (dest)
+ if (cprop_reg_p (dest)
&& reg_available_p (dest, insn)
&& can_copy_p (GET_MODE (dest)))
{
&& REG_NOTE_KIND (note) == REG_EQUAL
&& !REG_P (src)
&& cprop_constant_p (XEXP (note, 0)))
- src = XEXP (note, 0), set = gen_rtx_SET (VOIDmode, dest, src);
+ src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
/* Record sets for constant/copy propagation. */
- if ((REG_P (src)
+ if ((cprop_reg_p (src)
&& src != dest
- && ! HARD_REGISTER_P (src)
&& reg_available_p (src, insn))
|| cprop_constant_p (src))
insert_set_in_table (dest, src, insn, table, implicit);
{
int i;
/* Flattened out table, so it's printed in proper order. */
- struct expr **flat_table;
+ struct cprop_expr **flat_table;
unsigned int *hash_val;
- struct expr *expr;
+ struct cprop_expr *expr;
- flat_table = XCNEWVEC (struct expr *, table->n_elems);
+ flat_table = XCNEWVEC (struct cprop_expr *, table->n_elems);
hash_val = XNEWVEC (unsigned int, table->n_elems);
for (i = 0; i < (int) table->size; i++)
Making it an odd number is simplest for now.
??? Later take some measurements. */
table->size |= 1;
- n = table->size * sizeof (struct expr *);
- table->table = XNEWVAR (struct expr *, n);
+ n = table->size * sizeof (struct cprop_expr *);
+ table->table = XNEWVAR (struct cprop_expr *, n);
}
/* Free things allocated by alloc_hash_table. */
{
/* Initialize count of number of entries in hash table. */
table->n_elems = 0;
- memset (table->table, 0, table->size * sizeof (struct expr *));
+ memset (table->table, 0, table->size * sizeof (struct cprop_expr *));
compute_hash_table_work (table);
}
/* Lookup REGNO in the set TABLE. The result is a pointer to the
table entry, or NULL if not found. */
-static struct expr *
+static struct cprop_expr *
lookup_set (unsigned int regno, struct hash_table_d *table)
{
unsigned int hash = hash_mod (regno, table->size);
- struct expr *expr;
+ struct cprop_expr *expr;
expr = table->table[hash];
/* Return the next entry for REGNO in list EXPR. */
-static struct expr *
-next_set (unsigned int regno, struct expr *expr)
+static struct cprop_expr *
+next_set (unsigned int regno, struct cprop_expr *expr)
{
do
expr = expr->next_same_hash;
for (i = 0; i < table->size; i++)
{
- struct expr *expr;
+ struct cprop_expr *expr;
for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
{
int indx = expr->bitmap_index;
df_ref def;
- struct occr *occr;
+ struct cprop_occr *occr;
/* For each definition of the destination pseudo-reg, the expression
is killed in the block where the definition is. */
int success = 0;
rtx set = single_set (insn);
+ bool check_rtx_costs = true;
+ bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
+ int old_cost = set ? set_rtx_cost (set, speed) : 0;
+
+ if ((note != 0
+ && REG_NOTE_KIND (note) == REG_EQUAL
+ && (GET_CODE (XEXP (note, 0)) == CONST
+ || CONSTANT_P (XEXP (note, 0))))
+ || (set && CONSTANT_P (SET_SRC (set))))
+ check_rtx_costs = false;
+
/* Usually we substitute easy stuff, so we won't copy everything.
We however need to take care to not duplicate non-trivial CONST
expressions. */
to = copy_rtx (to);
validate_replace_src_group (from, to, insn);
+
+ /* If TO is a constant, check the cost of the set after propagation
+ to the cost of the set before the propagation. If the cost is
+ higher, then do not replace FROM with TO. */
+
+ if (check_rtx_costs
+ && CONSTANT_P (to)
+ && (set_rtx_cost (set, speed) > old_cost))
+ {
+ cancel_changes (0);
+ return false;
+ }
+
+
if (num_changes_pending () && apply_change_group ())
success = 1;
return success;
}
-/* Find a set of REGNOs that are available on entry to INSN's block. Return
- NULL no such set is found. */
+/* Find a set of REGNOs that are available on entry to INSN's block. If found,
+ SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
+ set with a constant source. If not found the corresponding entry is set to
+ NULL. */
-static struct expr *
-find_avail_set (int regno, rtx_insn *insn)
+static void
+find_avail_set (int regno, rtx_insn *insn, struct cprop_expr *set_ret[2])
{
- /* SET1 contains the last set found that can be returned to the caller for
- use in a substitution. */
- struct expr *set1 = 0;
+ set_ret[0] = set_ret[1] = NULL;
/* Loops are not possible here. To get a loop we would need two sets
available at the start of the block containing INSN. i.e. we would
while (1)
{
rtx src;
- struct expr *set = lookup_set (regno, &set_hash_table);
+ struct cprop_expr *set = lookup_set (regno, &set_hash_table);
/* Find a set that is available at the start of the block
which contains INSN. */
If the source operand changed, we may still use it for the next
iteration of this loop, but we may not use it for substitutions. */
- if (cprop_constant_p (src) || reg_not_set_p (src, insn))
- set1 = set;
+ if (cprop_constant_p (src))
+ set_ret[1] = set;
+ else if (reg_not_set_p (src, insn))
+ set_ret[0] = set;
/* If the source of the set is anything except a register, then
we have reached the end of the copy chain. */
and see if we have an available copy into SRC. */
regno = REGNO (src);
}
-
- /* SET1 holds the last set that was available and anticipatable at
- INSN. */
- return set1;
}
/* Subroutine of cprop_insn that tries to propagate constants into
remove_note (jump, note);
}
-#ifdef HAVE_cc0
/* Delete the cc0 setter. */
- if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
+ if (HAVE_cc0 && setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
delete_insn (setcc);
-#endif
global_const_prop_count++;
if (dump_file != NULL)
int changed = 0, changed_this_round;
rtx note;
-retry:
- changed_this_round = 0;
- reg_use_count = 0;
- note_uses (&PATTERN (insn), find_used_regs, NULL);
-
- /* We may win even when propagating constants into notes. */
- note = find_reg_equal_equiv_note (insn);
- if (note)
- find_used_regs (&XEXP (note, 0), NULL);
-
- for (i = 0; i < reg_use_count; i++)
+ do
{
- rtx reg_used = reg_use_table[i];
- unsigned int regno = REGNO (reg_used);
- rtx src;
- struct expr *set;
+ changed_this_round = 0;
+ reg_use_count = 0;
+ note_uses (&PATTERN (insn), find_used_regs, NULL);
- /* If the register has already been set in this block, there's
- nothing we can do. */
- if (! reg_not_set_p (reg_used, insn))
- continue;
+ /* We may win even when propagating constants into notes. */
+ note = find_reg_equal_equiv_note (insn);
+ if (note)
+ find_used_regs (&XEXP (note, 0), NULL);
- /* Find an assignment that sets reg_used and is available
- at the start of the block. */
- set = find_avail_set (regno, insn);
- if (! set)
- continue;
+ for (i = 0; i < reg_use_count; i++)
+ {
+ rtx reg_used = reg_use_table[i];
+ unsigned int regno = REGNO (reg_used);
+ rtx src_cst = NULL, src_reg = NULL;
+ struct cprop_expr *set[2];
- src = set->src;
+ /* If the register has already been set in this block, there's
+ nothing we can do. */
+ if (! reg_not_set_p (reg_used, insn))
+ continue;
- /* Constant propagation. */
- if (cprop_constant_p (src))
- {
- if (constprop_register (reg_used, src, insn))
+ /* Find an assignment that sets reg_used and is available
+ at the start of the block. */
+ find_avail_set (regno, insn, set);
+ if (set[0])
+ src_reg = set[0]->src;
+ if (set[1])
+ src_cst = set[1]->src;
+
+ /* Constant propagation. */
+ if (src_cst && cprop_constant_p (src_cst)
+ && constprop_register (reg_used, src_cst, insn))
{
changed_this_round = changed = 1;
global_const_prop_count++;
"GLOBAL CONST-PROP: Replacing reg %d in ", regno);
fprintf (dump_file, "insn %d with constant ",
INSN_UID (insn));
- print_rtl (dump_file, src);
+ print_rtl (dump_file, src_cst);
fprintf (dump_file, "\n");
}
- if (INSN_DELETED_P (insn))
+ if (insn->deleted ())
return 1;
}
- }
- else if (REG_P (src)
- && REGNO (src) >= FIRST_PSEUDO_REGISTER
- && REGNO (src) != regno)
- {
- if (try_replace_reg (reg_used, src, insn))
+ /* Copy propagation. */
+ else if (src_reg && cprop_reg_p (src_reg)
+ && REGNO (src_reg) != regno
+ && try_replace_reg (reg_used, src_reg, insn))
{
changed_this_round = changed = 1;
global_copy_prop_count++;
fprintf (dump_file,
"GLOBAL COPY-PROP: Replacing reg %d in insn %d",
regno, INSN_UID (insn));
- fprintf (dump_file, " with reg %d\n", REGNO (src));
+ fprintf (dump_file, " with reg %d\n", REGNO (src_reg));
}
/* The original insn setting reg_used may or may not now be
and made things worse. */
}
}
-
- /* If try_replace_reg simplified the insn, the regs found
- by find_used_regs may not be valid anymore. Start over. */
- if (changed_this_round)
- goto retry;
}
+ /* If try_replace_reg simplified the insn, the regs found by find_used_regs
+ may not be valid anymore. Start over. */
+ while (changed_this_round);
if (changed && DEBUG_INSN_P (insn))
return 0;
/* Rule out USE instructions and ASM statements as we don't want to
change the hard registers mentioned. */
if (REG_P (x)
- && (REGNO (x) >= FIRST_PSEUDO_REGISTER
+ && (cprop_reg_p (x)
|| (GET_CODE (PATTERN (insn)) != USE
&& asm_noperands (PATTERN (insn)) < 0)))
{
if (cprop_constant_p (this_rtx))
newcnst = this_rtx;
- if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
+ if (cprop_reg_p (this_rtx)
/* Don't copy propagate if it has attached REG_EQUIV note.
At this point this only function parameters should have
REG_EQUIV notes and if the argument slot is used somewhere
break;
}
}
- if (INSN_DELETED_P (insn))
+ if (insn->deleted ())
break;
}
while (i < reg_use_count);
static bool
implicit_set_cond_p (const_rtx cond)
{
- enum machine_mode mode;
+ machine_mode mode;
rtx cst;
/* COND must be either an EQ or NE comparison. */
if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
return false;
- /* The first operand of COND must be a pseudo-reg. */
- if (! REG_P (XEXP (cond, 0))
- || HARD_REGISTER_P (XEXP (cond, 0)))
+ /* The first operand of COND must be a register we can propagate. */
+ if (!cprop_reg_p (XEXP (cond, 0)))
return false;
/* The second operand of COND must be a suitable constant. */
(implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
}
- new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
- XEXP (cond, 1));
+ new_rtx = gen_rtx_SET (XEXP (cond, 0), XEXP (cond, 1));
implicit_sets[dest->index] = new_rtx;
if (dump_file)
{
block BB. Return NULL if no such set is found. Based heavily upon
find_avail_set. */
-static struct expr *
+static struct cprop_expr *
find_bypass_set (int regno, int bb)
{
- struct expr *result = 0;
+ struct cprop_expr *result = 0;
for (;;)
{
rtx src;
- struct expr *set = lookup_set (regno, &set_hash_table);
+ struct cprop_expr *set = lookup_set (regno, &set_hash_table);
while (set)
{
static bool
reg_killed_on_edge (const_rtx reg, const_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))
rtx reg_used = reg_use_table[i];
unsigned int regno = REGNO (reg_used);
basic_block dest, old_dest;
- struct expr *set;
+ struct cprop_expr *set;
rtx src, new_rtx;
set = find_bypass_set (regno, e->src->index);
/* ??? 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, or deleted the insn. */
- if (! NOTE_P (insn) && ! INSN_DELETED_P (insn))
+ if (! NOTE_P (insn) && ! insn->deleted ())
mark_oprs_set (insn);
}
}