/* Rematerialize pseudos values.
- Copyright (C) 2014-2016 Free Software Foundation, Inc.
+ Copyright (C) 2014-2019 Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
This file is part of GCC.
#include "df.h"
#include "insn-config.h"
#include "regs.h"
+#include "memmodel.h"
#include "ira.h"
#include "recog.h"
#include "lra.h"
{
/* Index of the candidates in all_cands. */
int index;
- /* The candidate insn. */
- rtx_insn *insn;
/* Insn pseudo regno for rematerialization. */
int regno;
+ /* The candidate insn. */
+ rtx_insn *insn;
/* Non-negative if a reload pseudo is in the insn instead of the
pseudo for rematerialization. */
int reload_regno;
/* Vector containing all candidates. */
static vec<cand_t> all_cands;
-/* Map: insn -> candidate representing it. It is null if the insn can
- not be used for rematerialization. */
+/* Map: insn -> candidate representing it. It is null if the insn cannot
+ be used for rematerialization. */
static cand_t *insn_to_cand;
+/* A secondary map, for candidates that involve two insns, where the
+ second one makes the equivalence. The candidate must not be used
+ before seeing this activation insn. */
+static cand_t *insn_to_cand_activation;
/* Map regno -> candidates can be used for the regno
rematerialization. */
/* Data about basic blocks used for the rematerialization
sub-pass. */
-struct remat_bb_data
+class remat_bb_data
{
+public:
/* Basic block about which the below data are. */
basic_block bb;
/* Registers changed in the basic block: */
};
/* Array for all BB data. Indexed by the corresponding BB index. */
-typedef struct remat_bb_data *remat_bb_data_t;
+typedef class remat_bb_data *remat_bb_data_t;
/* Basic blocks for data flow problems -- all bocks except the special
ones. */
\f
-/* Recursive hash function for RTL X. */
-static hashval_t
-rtx_hash (rtx x)
-{
- int i, j;
- enum rtx_code code;
- const char *fmt;
- hashval_t val = 0;
-
- if (x == 0)
- return val;
-
- code = GET_CODE (x);
- val += (int) code + 4095;
-
- /* Some RTL can be compared nonrecursively. */
- switch (code)
- {
- case REG:
- return val + REGNO (x);
-
- case LABEL_REF:
- return iterative_hash_object (XEXP (x, 0), val);
-
- case SYMBOL_REF:
- return iterative_hash_object (XSTR (x, 0), val);
-
- case SCRATCH:
- case CONST_DOUBLE:
- case CONST_INT:
- case CONST_VECTOR:
- return val;
-
- default:
- break;
- }
-
- /* Hash the elements. */
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- switch (fmt[i])
- {
- case 'w':
- val += XWINT (x, i);
- break;
-
- case 'n':
- case 'i':
- val += XINT (x, i);
- break;
-
- case 'V':
- case 'E':
- val += XVECLEN (x, i);
-
- for (j = 0; j < XVECLEN (x, i); j++)
- val += rtx_hash (XVECEXP (x, i, j));
- break;
-
- case 'e':
- val += rtx_hash (XEXP (x, i));
- break;
-
- case 'S':
- case 's':
- val += htab_hash_string (XSTR (x, i));
- break;
-
- case 'u':
- case '0':
- case 't':
- break;
-
- /* It is believed that rtx's at this level will never
- contain anything but integers and other rtx's, except for
- within LABEL_REFs and SYMBOL_REFs. */
- default:
- abort ();
- }
- }
- return val;
-}
-
-\f
-
/* Hash table for the candidates. Different insns (e.g. structurally
the same insns or even insns with different unused output regs) can
be represented by the same candidate in the table. */
\f
-/* Return true if X contains memory or some UNSPEC. We can not just
+/* Return true if X contains memory or some UNSPEC. We cannot just
check insn operands as memory or unspec might be not an operand
itself but contain an operand. Insn with memory access is not
profitable for rematerialization. Rematerialization of UNSPEC
return false;
}
-/* If INSN can not be used for rematerialization, return negative
+/* If INSN cannot be used for rematerialization, return negative
value. If INSN can be considered as a candidate for
rematerialization, return value which is the operand number of the
pseudo for which the insn can be used for rematerialization. Here
/* First find a pseudo which can be rematerialized. */
for (reg = id->regs; reg != NULL; reg = reg->next)
{
- /* True FRAME_POINTER_NEEDED might be because we can not follow
+ /* True FRAME_POINTER_NEEDED might be because we cannot follow
changing sp offsets, e.g. alloca is used. If the insn contains
- stack pointer in such case, we can not rematerialize it as we
- can not know sp offset at a rematerialization place. */
+ stack pointer in such case, we cannot rematerialize it as we
+ cannot know sp offset at a rematerialization place. */
if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
return -1;
else if (reg->type == OP_OUT && ! reg->subreg_p
if (reg->regno >= FIRST_PSEUDO_REGISTER
&& bitmap_bit_p (&subreg_regs, reg->regno))
return -1;
+
+ /* Don't allow hard registers to be rematerialized. */
+ if (reg->regno < FIRST_PSEUDO_REGISTER)
+ return -1;
}
if (found_reg == NULL)
return -1;
if (reg2->type == OP_OUT
&& reg->regno <= reg2->regno
&& (reg2->regno
- < (reg->regno
- + hard_regno_nregs[reg->regno][reg->biggest_mode])))
+ < (int) end_hard_regno (reg->biggest_mode, reg->regno)))
return -1;
}
+ /* Check hard coded insn registers. */
+ for (struct lra_insn_reg *reg = static_id->hard_regs;
+ reg != NULL;
+ reg = reg->next)
+ if (reg->type == OP_INOUT)
+ return -1;
+ else if (reg->type == OP_IN)
+ {
+ /* Check that there is no output hard reg as the input
+ one. */
+ for (struct lra_insn_reg *reg2 = static_id->hard_regs;
+ reg2 != NULL;
+ reg2 = reg2->next)
+ if (reg2->type == OP_OUT && reg->regno == reg2->regno)
+ return -1;
+ }
/* Find the rematerialization operand. */
int nop = static_id->n_operands;
for (int i = 0; i < nop; i++)
REGNO. Insert the candidate into the table and set up the
corresponding INSN_TO_CAND element. */
static void
-create_cand (rtx_insn *insn, int nop, int regno)
+create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
{
lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
rtx reg = *id->operand_loc[nop];
cand->next_regno_cand = regno_cands[cand->regno];
regno_cands[cand->regno] = cand;
}
+ if (activation)
+ insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
}
/* Create rematerialization candidates (inserting them into the
/* Create candidates. */
regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
+ if (NONDEBUG_INSN_P (insn))
{
- rtx set;
- int src_regno, dst_regno;
- rtx_insn *insn2;
lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
- int nop = operand_to_remat (insn);
- int regno = -1;
-
- if ((set = single_set (insn)) != NULL
- && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))
- && ((src_regno = REGNO (SET_SRC (set)))
- >= lra_constraint_new_regno_start)
- && (dst_regno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
- && reg_renumber[dst_regno] < 0
- && (insn2 = regno_potential_cand[src_regno].insn) != NULL
- && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
- /* It is an output reload insn after insn can be
- rematerialized (potential candidate). */
- create_cand (insn2, regno_potential_cand[src_regno].nop, dst_regno);
- if (nop < 0)
- goto fail;
- gcc_assert (REG_P (*id->operand_loc[nop]));
- regno = REGNO (*id->operand_loc[nop]);
- gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
- if (reg_renumber[regno] < 0)
- create_cand (insn, nop, regno);
- else
+ int keep_regno = -1;
+ rtx set = single_set (insn);
+ int nop;
+
+ /* See if this is an output reload for a previous insn. */
+ if (set != NULL
+ && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
+ {
+ rtx dstreg = SET_DEST (set);
+ int src_regno = REGNO (SET_SRC (set));
+ int dst_regno = REGNO (dstreg);
+ rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
+
+ if (insn2 != NULL
+ && dst_regno >= FIRST_PSEUDO_REGISTER
+ && reg_renumber[dst_regno] < 0
+ && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
+ {
+ create_cand (insn2, regno_potential_cand[src_regno].nop,
+ dst_regno, insn);
+ goto done;
+ }
+ }
+
+ nop = operand_to_remat (insn);
+ if (nop >= 0)
{
- regno_potential_cand[regno].insn = insn;
- regno_potential_cand[regno].nop = nop;
- goto fail;
+ gcc_assert (REG_P (*id->operand_loc[nop]));
+ int regno = REGNO (*id->operand_loc[nop]);
+ gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
+ /* If we're setting an unrenumbered pseudo, make a candidate immediately.
+ If it's an output reload register, save it for later; the code above
+ looks for output reload insns later on. */
+ if (reg_renumber[regno] < 0)
+ create_cand (insn, nop, regno);
+ else if (regno >= lra_constraint_new_regno_start)
+ {
+ regno_potential_cand[regno].insn = insn;
+ regno_potential_cand[regno].nop = nop;
+ keep_regno = regno;
+ }
}
- regno = -1;
- fail:
+
+ done:
for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
- if (reg->type != OP_IN && reg->regno != regno
+ if (reg->type != OP_IN && reg->regno != keep_regno
&& reg->regno >= FIRST_PSEUDO_REGISTER)
regno_potential_cand[reg->regno].insn = NULL;
}
basic_block bb;
remat_bb_data_t bb_info;
- remat_bb_data = XNEWVEC (struct remat_bb_data,
+ remat_bb_data = XNEWVEC (class remat_bb_data,
last_basic_block_for_fn (cfun));
FOR_ALL_BB_FN (bb, cfun)
{
FOR_EACH_BB_FN (bb, cfun)
FOR_BB_INSNS (bb, insn)
- if (INSN_P (insn))
+ if (NONDEBUG_INSN_P (insn))
set_bb_regs (bb, insn);
}
\f
-/* Return true if REGNO is an input operand of INSN. */
+/* Return true if REG overlaps an input operand of INSN. */
static bool
-input_regno_present_p (rtx_insn *insn, int regno)
+reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
{
int iter;
lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
struct lra_static_insn_data *static_id = id->insn_static_data;
- struct lra_insn_reg *reg;
-
+ unsigned regno = reg->regno;
+ int nregs;
+
+ if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
+ regno = reg_renumber[regno];
+ if (regno >= FIRST_PSEUDO_REGISTER)
+ nregs = 1;
+ else
+ nregs = hard_regno_nregs (regno, reg->biggest_mode);
+
+ struct lra_insn_reg *reg2;
+
for (iter = 0; iter < 2; iter++)
- for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
- reg != NULL;
- reg = reg->next)
- if (reg->type == OP_IN && reg->regno == regno)
- return true;
+ for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
+ reg2 != NULL;
+ reg2 = reg2->next)
+ {
+ if (reg2->type != OP_IN)
+ continue;
+ unsigned regno2 = reg2->regno;
+ int nregs2;
+
+ if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
+ regno2 = reg_renumber[regno2];
+ if (regno2 >= FIRST_PSEUDO_REGISTER)
+ nregs2 = 1;
+ else
+ nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
+
+ if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
+ || (regno + nregs - 1 >= regno2 && regno < regno2 + nregs2))
+ return true;
+ }
return false;
}
for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
reg != NULL;
reg = reg->next)
- if (reg->type == OP_IN && reg->regno <= FIRST_PSEUDO_REGISTER
+ if (reg->type == OP_IN && reg->regno < FIRST_PSEUDO_REGISTER
&& TEST_HARD_REG_BIT (call_used_reg_set, reg->regno))
return true;
return false;
{
basic_block bb;
bitmap gen_cands;
- bitmap_head gen_insns;
rtx_insn *insn;
- bitmap_initialize (&gen_insns, ®_obstack);
FOR_EACH_BB_FN (bb, cfun)
{
gen_cands = &get_remat_bb_data (bb)->gen_cands;
- bitmap_clear (&gen_insns);
+ auto_bitmap gen_insns (®_obstack);
FOR_BB_INSNS (bb, insn)
if (INSN_P (insn))
{
reg = reg->next)
if (reg->type != OP_IN
|| find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
- EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
+ EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
{
rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
&& dst_regno == cand->regno)
continue;
if (cand->regno == reg->regno
- || input_regno_present_p (insn2, reg->regno))
+ || reg_overlap_for_remat_p (reg, insn2))
{
bitmap_clear_bit (gen_cands, cand->index);
bitmap_set_bit (&temp_bitmap, uid);
}
if (CALL_P (insn))
- EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
+ EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
{
rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
bitmap_set_bit (&temp_bitmap, uid);
}
}
- bitmap_and_compl_into (&gen_insns, &temp_bitmap);
+ bitmap_and_compl_into (gen_insns, &temp_bitmap);
cand = insn_to_cand[INSN_UID (insn)];
if (cand != NULL)
{
bitmap_set_bit (gen_cands, cand->index);
- bitmap_set_bit (&gen_insns, INSN_UID (insn));
+ bitmap_set_bit (gen_insns, INSN_UID (insn));
}
}
}
- bitmap_clear (&gen_insns);
}
\f
/* Setup sp offset attribute to SP_OFFSET for all INSNS. */
static void
-change_sp_offset (rtx_insn *insns, HOST_WIDE_INT sp_offset)
+change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
{
for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
eliminate_regs_in_insn (insn, false, false, sp_offset);
int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
if (hard_regno >= 0)
- nregs = hard_regno_nregs[hard_regno][reg->biggest_mode];
+ nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
return hard_regno;
}
*loc = lra_create_new_reg (GET_MODE (*loc), *loc,
lra_get_allocno_class (regno),
"scratch pseudo copy");
- lra_register_new_scratch_op (remat_insn, i);
+ lra_register_new_scratch_op (remat_insn, i, id->icode);
}
}
static bool
do_remat (void)
{
+ unsigned regno;
rtx_insn *insn;
basic_block bb;
- bitmap_head avail_cands;
bool changed_p = false;
/* Living hard regs and hard registers of living pseudos. */
HARD_REG_SET live_hard_regs;
+ bitmap_iterator bi;
- bitmap_initialize (&avail_cands, ®_obstack);
+ auto_bitmap avail_cands (®_obstack);
+ auto_bitmap active_cands (®_obstack);
FOR_EACH_BB_FN (bb, cfun)
{
- REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_out (bb));
- bitmap_and (&avail_cands, &get_remat_bb_data (bb)->avin_cands,
+ CLEAR_HARD_REG_SET (live_hard_regs);
+ EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
+ {
+ int hard_regno = regno < FIRST_PSEUDO_REGISTER
+ ? regno
+ : reg_renumber[regno];
+ if (hard_regno >= 0)
+ SET_HARD_REG_BIT (live_hard_regs, hard_regno);
+ }
+ bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
&get_remat_bb_data (bb)->livein_cands);
+ /* Activating insns are always in the same block as their corresponding
+ remat insn, so at the start of a block the two bitsets are equal. */
+ bitmap_copy (active_cands, avail_cands);
FOR_BB_INSNS (bb, insn)
{
if (!NONDEBUG_INSN_P (insn))
for (cand = regno_cands[src_regno];
cand != NULL;
cand = cand->next_regno_cand)
- if (bitmap_bit_p (&avail_cands, cand->index))
+ if (bitmap_bit_p (avail_cands, cand->index)
+ && bitmap_bit_p (active_cands, cand->index))
break;
}
int i, hard_regno, nregs;
+ int dst_hard_regno, dst_nregs;
rtx_insn *remat_insn = NULL;
- HOST_WIDE_INT cand_sp_offset = 0;
+ poly_int64 cand_sp_offset = 0;
if (cand != NULL)
{
lra_insn_recog_data_t cand_id
gcc_assert (REG_P (saved_op));
int ignore_regno = REGNO (saved_op);
+ dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
+ ? dst_regno : reg_renumber[dst_regno];
+ gcc_assert (dst_hard_regno >= 0);
+ machine_mode mode = GET_MODE (SET_DEST (set));
+ dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
+
for (reg = cand_id->regs; reg != NULL; reg = reg->next)
if (reg->type != OP_IN && reg->regno != ignore_regno)
{
break;
if (i < nregs)
break;
+ /* Ensure the clobber also doesn't overlap dst_regno. */
+ if (hard_regno + nregs > dst_hard_regno
+ && hard_regno < dst_hard_regno + dst_nregs)
+ break;
}
if (reg == NULL)
for (reg = static_cand_id->hard_regs;
reg != NULL;
reg = reg->next)
- if (reg->type != OP_IN
- && TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
- break;
+ if (reg->type != OP_IN)
+ {
+ if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
+ break;
+ if (reg->regno >= dst_hard_regno
+ && reg->regno < dst_hard_regno + dst_nregs)
+ break;
+ }
}
if (reg == NULL)
reg = reg->next)
if (reg->type != OP_IN
|| find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
- EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
+ EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
{
cand = all_cands[cid];
&& dst_regno == cand->regno)
continue;
if (cand->regno == reg->regno
- || input_regno_present_p (cand->insn, reg->regno))
+ || reg_overlap_for_remat_p (reg, cand->insn))
bitmap_set_bit (&temp_bitmap, cand->index);
}
if (CALL_P (insn))
- EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
+ EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
{
cand = all_cands[cid];
bitmap_set_bit (&temp_bitmap, cand->index);
}
- bitmap_and_compl_into (&avail_cands, &temp_bitmap);
- if ((cand = insn_to_cand[INSN_UID (insn)]) != NULL)
- bitmap_set_bit (&avail_cands, cand->index);
-
+ bitmap_and_compl_into (avail_cands, &temp_bitmap);
+
+ /* Now see whether a candidate is made active or available
+ by this insn. */
+ cand = insn_to_cand_activation[INSN_UID (insn)];
+ if (cand)
+ bitmap_set_bit (active_cands, cand->index);
+
+ cand = insn_to_cand[INSN_UID (insn)];
+ if (cand != NULL)
+ {
+ bitmap_set_bit (avail_cands, cand->index);
+ if (cand->reload_regno == -1)
+ bitmap_set_bit (active_cands, cand->index);
+ else
+ bitmap_clear_bit (active_cands, cand->index);
+ }
+
if (remat_insn != NULL)
{
- HOST_WIDE_INT sp_offset_change = cand_sp_offset - id->sp_offset;
- if (sp_offset_change != 0)
+ poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
+ if (maybe_ne (sp_offset_change, 0))
change_sp_offset (remat_insn, sp_offset_change);
update_scratch_ops (remat_insn);
lra_process_new_insns (insn, remat_insn, NULL,
SET_HARD_REG_BIT (live_hard_regs, reg->regno);
}
}
- bitmap_clear (&avail_cands);
return changed_p;
}
lra_rematerialization_iter);
timevar_push (TV_LRA_REMAT);
insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
+ insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
regno_cands = XCNEWVEC (cand_t, max_regno);
all_cands.create (8000);
call_used_regs_arr_len = 0;
bitmap_clear (&all_blocks);
free (regno_cands);
free (insn_to_cand);
+ free (insn_to_cand_activation);
timevar_pop (TV_LRA_REMAT);
return result;
}
projects / thirdparty / gcc.git / blobdiff