From: Robin Dapp <[email protected]>
This patch adds dependent-filter support to lra. As with register
filters, this is the part that ensures correctness, while the later
ira patch improves register allocation.
As dependent filters can be expensive, the patch adds a hash-table
cache that is integrated into lra_get_dependent_filter.
In order to keep track of dependent filters during pseudo phases, the
patch adds a vector of them to lra_reg. It is filled after reloading
and queried in find_hard_regno_for_1 so we can fold it into
conflict_set.
gcc/ChangeLog:
* lra-assigns.cc (find_hard_regno_for_1): Query dependent
filter of current pseudo.
* lra-constraints.cc (struct dependent_filter_cache_hasher): New
hasher.
(lra_init_dependent_filter_cache): New function.
(lra_finish_dependent_filter_cache): Ditto.
(lra_reset_dependent_filters): Ditto.
(lra_get_dependent_filter): New function to query (and add)
a dependent filter from/to the cache.
(lra_add_dependent_filter): New function to add a dependent
filter to an lra_reg.
(get_dependent_filter): New function to get a dependent filter
from a constraint.
(process_dependent_filters): New function to get all dependent
filters from the current insn's constraints.
(process_alt_operands): Initialize dependent-filter regset.
(curr_insn_transform): Fill lra_reg dependent filters.
* lra-int.h (struct dependent_filter): Declare.
(struct dependent_filter_entry): Ditto.
(lra_init_dependent_filter_cache): Ditto.
(lra_finish_dependent_filter_cache): Ditto.
* lra.cc (initialize_lra_reg_info_element): New function.
(finish_reg_info): Release dependent-filter vector.
(lra_init_once): Init hash table.
(lra_finish_once): Clear hash table.
* lra.h (lra_reset_dependent_filters): Declare.
---
gcc/lra-assigns.cc | 23 +++++
gcc/lra-constraints.cc | 221 +++++++++++++++++++++++++++++++++++++++++
gcc/lra-int.h | 22 ++++
gcc/lra.cc | 8 +-
gcc/lra.h | 3 +
5 files changed, 276 insertions(+), 1 deletion(-)
diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
index ddc685ecdfa..193ba49f54c 100644
--- a/gcc/lra-assigns.cc
+++ b/gcc/lra-assigns.cc
@@ -629,6 +629,29 @@ find_hard_regno_for_1 (int regno, int *cost, int
try_only_hard_regno,
lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
}
}
+
+ /* If a reference/partner pseudo already has a hardreg, restrict this one
+ to what the filter permits. */
+ if (!lra_reg_info[regno].dependent_filters.is_empty ())
+ {
+ unsigned int i;
+ dependent_filter *filter;
+ FOR_EACH_VEC_ELT (lra_reg_info[regno].dependent_filters, i, filter)
+ {
+ int partner_regno = live_pseudos_reg_renumber[filter->partner_regno];
+ if (partner_regno < 0)
+ partner_regno = reg_renumber[filter->partner_regno];
+ if (partner_regno < 0)
+ continue;
+
+ const HARD_REG_SET *allowed
+ = lra_get_dependent_filter (filter->id, filter->mode,
+ (unsigned int) partner_regno,
+ filter->partner_mode, filter->is_ref);
+ conflict_set |= ~*allowed;
+ }
+ }
+
/* Make sure that all registers in a multi-word pseudo belong to the
required class. */
conflict_set |= ~reg_class_contents[rclass];
diff --git a/gcc/lra-constraints.cc b/gcc/lra-constraints.cc
index d6056cf7acc..1471119cd58 100644
--- a/gcc/lra-constraints.cc
+++ b/gcc/lra-constraints.cc
@@ -2182,6 +2182,219 @@ print_curr_insn_alt (int alt_number)
}
}
+struct dependent_filter_cache_hasher
+ : free_ptr_hash <dependent_filter_entry>
+{
+ static inline hashval_t hash (const dependent_filter_entry *e)
+ {
+ hashval_t h = (hashval_t) e->id;
+ h = iterative_hash_hashval_t ((hashval_t) e->mode, h);
+ h = iterative_hash_hashval_t ((hashval_t) e->partner_mode, h);
+ h = iterative_hash_hashval_t (e->partner_regno, h);
+ h = iterative_hash_hashval_t ((hashval_t) e->is_ref, h);
+ return h;
+ }
+ static inline bool equal (const dependent_filter_entry *a,
+ const dependent_filter_entry *b)
+ {
+ return (a->id == b->id && a->mode == b->mode
+ && a->partner_mode == b->partner_mode
+ && a->partner_regno == b->partner_regno
+ && a->is_ref == b->is_ref);
+ }
+};
+
+static hash_table<dependent_filter_cache_hasher> *dependent_filter_htab;
+
+/* Allocate the dependent-filter cache. */
+
+void
+lra_init_dependent_filter_cache (void)
+{
+ gcc_assert (!dependent_filter_htab);
+ dependent_filter_htab = new hash_table<dependent_filter_cache_hasher> (16);
+}
+
+/* Release the dependent-filter cache. */
+
+void
+lra_finish_dependent_filter_cache (void)
+{
+ delete dependent_filter_htab;
+ dependent_filter_htab = nullptr;
+}
+
+/* Reset the dependent-filter cache. */
+
+void
+lra_reset_dependent_filters (void)
+{
+ if (dependent_filter_htab)
+ dependent_filter_htab->empty ();
+}
+
+/* Return the set of hardregs allowed by dependent filter ID for an operand
+ of mode MODE when the referenced operand has PARTNER_REGNO in
+ PARTNER_MODE. That is when IS_REF is false. If it is true, the roles are
+ reversed and PARTNER_REGNO as well as PARTNER_MODE refer to the dependent
+ operand.
+
+ We fill the set for all hardregs and add the resulting regset to
+ a hash table if it doesn't already exist in it. */
+
+const HARD_REG_SET *
+lra_get_dependent_filter (int id, machine_mode mode,
+ unsigned int partner_regno,
+ machine_mode partner_mode, bool is_ref)
+{
+ dependent_filter_entry key;
+ key.id = id;
+ key.mode = mode;
+ key.partner_mode = partner_mode;
+ key.partner_regno = partner_regno;
+ key.is_ref = is_ref;
+
+ dependent_filter_entry **slot
+ = dependent_filter_htab->find_slot (&key, INSERT);
+ if (*slot)
+ return &(*slot)->allowed;
+
+ auto *e = XCNEW (dependent_filter_entry);
+ e->id = id;
+ e->mode = mode;
+ e->partner_mode = partner_mode;
+ e->partner_regno = partner_regno;
+ e->is_ref = is_ref;
+
+ /* ??? Should we restrict ourselves to a register class here? */
+ for (unsigned regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
+ {
+ bool ok;
+ if (is_ref)
+ ok = eval_dependent_filter (id, partner_regno, partner_mode,
+ regno, mode);
+ else
+ ok = eval_dependent_filter (id, regno, mode,
+ partner_regno, partner_mode);
+ if (ok)
+ SET_HARD_REG_BIT (e->allowed, regno);
+ }
+ *slot = e;
+ return &e->allowed;
+}
+
+/* Add the dependent filter ID to REGNO's dependent filters with
+ referenced PARTNER_REGNO and PARTNER_MODE if IS_REF is false.
+ If IS_REF is true, the roles are reversed. We need both
+ directions in case the referenced op is assigned a hardreg first. */
+
+void
+lra_add_dependent_filter (int regno, int id, machine_mode mode,
+ int partner_regno, machine_mode partner_mode,
+ bool is_ref)
+{
+ /* Only meaningful for pseudo partners. */
+ if (partner_regno < FIRST_PSEUDO_REGISTER)
+ return;
+
+ vec<dependent_filter> &filters = lra_reg_info[regno].dependent_filters;
+ unsigned int i;
+ dependent_filter *filter;
+
+ /* If this filter already exists, do nothing. */
+ FOR_EACH_VEC_ELT (filters, i, filter)
+ if (filter->id == id
+ && filter->partner_regno == (unsigned int) partner_regno
+ && filter->mode == mode && filter->partner_mode == partner_mode
+ && filter->is_ref == is_ref)
+ return;
+
+ /* Otherwise, create a new filter. */
+ dependent_filter new_filter;
+ new_filter.id = id;
+ new_filter.mode = mode;
+ new_filter.partner_mode = partner_mode;
+ new_filter.partner_regno = (unsigned int) partner_regno;
+ new_filter.is_ref = is_ref;
+ filters.safe_push (new_filter);
+}
+
+/* Return the set of hardregs for the constraint CN in MODE,
+ allowed by its dependent filter.
+ If there is no dependent filter or the involved registers are no
+ hardregs, return NULL. */
+
+static const HARD_REG_SET *
+get_dependent_filter (constraint_num cn, machine_mode mode)
+{
+ int id = get_dependent_filter_id (cn);
+ if (id < 0)
+ return nullptr;
+
+ gcc_assert (reg_class_for_constraint (cn) != NO_REGS);
+
+ int ref_opno = get_dependent_filter_ref (id);
+ gcc_assert (ref_opno >= 0 && ref_opno < curr_static_id->n_operands);
+
+ rtx ref_op = *curr_id->operand_loc[ref_opno];
+ if (!REG_P (ref_op))
+ return nullptr;
+ unsigned int ref_regno = REGNO (ref_op);
+ if (ref_regno >= FIRST_PSEUDO_REGISTER)
+ {
+ int ref_hard_regno = reg_renumber[ref_regno];
+ if (ref_hard_regno < 0)
+ return nullptr;
+ ref_regno = (unsigned int) ref_hard_regno;
+ }
+
+ return lra_get_dependent_filter (id, mode, ref_regno, GET_MODE (ref_op),
+ false);
+}
+
+/* Go through all operands and their constraints, looking for a dependent
+ filter. If we find one, add it to the respective reg_info's
+ dependent-filter list. After assigning a hardreg to either the dependent
+ or the referenced op, this allows us to filter the other's regset. */
+
+static void
+process_dependent_filters (void)
+{
+ int n_operands = curr_static_id->n_operands;
+ for (int i = 0; i < n_operands; i++)
+ {
+ rtx op = *curr_id->operand_loc[i];
+ if (!REG_P (op) || HARD_REGISTER_P (op))
+ continue;
+ const char *constraint
+ = curr_static_id->operand_alternative
+ [goal_alt_number * n_operands + i].constraint;
+ for (const char *p = constraint;
+ *p && *p != ',' && *p != '#';
+ p += CONSTRAINT_LEN (*p, p))
+ {
+ enum constraint_num cn = lookup_constraint (p);
+ int id = get_dependent_filter_id (cn);
+ if (id < 0)
+ continue;
+ if (reg_class_for_constraint (cn) == NO_REGS)
+ continue;
+ int ref_opno = get_dependent_filter_ref (id);
+ if (ref_opno < 0 || ref_opno >= n_operands)
+ continue;
+ rtx ref_op = *curr_id->operand_loc[ref_opno];
+ if (!REG_P (ref_op) || HARD_REGISTER_P (ref_op))
+ continue;
+ machine_mode mode = curr_operand_mode[i];
+ lra_add_dependent_filter (REGNO (op), id, mode,
+ REGNO (ref_op), GET_MODE (ref_op),
+ false);
+ lra_add_dependent_filter (REGNO (ref_op), id, GET_MODE (ref_op),
+ REGNO (op), mode, true);
+ }
+ }
+}
+
/* Major function to choose the current insn alternative and what
operands should be reloaded and how. If ONLY_ALTERNATIVE is not
negative we should consider only this alternative. Return false if
@@ -2364,6 +2577,7 @@ process_alt_operands (int only_alternative)
win = did_match = winreg = offmemok = constmemok = false;
badop = true;
+ const HARD_REG_SET *cl_dep_filter = nullptr;
early_clobber_p = false;
p = curr_static_id->operand_alternative[opalt_num].constraint;
@@ -2650,6 +2864,7 @@ process_alt_operands (int only_alternative)
if (cl != NO_REGS)
{
cl_filter = get_register_filter (cn);
+ cl_dep_filter = get_dependent_filter (cn, mode);
goto reg;
}
break;
@@ -2731,6 +2946,8 @@ process_alt_operands (int only_alternative)
this_alternative_set |= reg_class_contents[cl];
if (cl_filter)
this_alternative_exclude_start_hard_regs |= ~*cl_filter;
+ if (cl_dep_filter)
+ this_alternative_exclude_start_hard_regs |= ~*cl_dep_filter;
if (costly_p)
{
this_costly_alternative
@@ -5070,6 +5287,10 @@ curr_insn_transform (bool check_only_p)
REGNO (op), regno);
}
}
+
+ /* After the dust has settled, collect and attach dependent filters. */
+ process_dependent_filters ();
+
if (before != NULL_RTX || after != NULL_RTX
|| max_regno_before != max_reg_num ())
change_p = true;
diff --git a/gcc/lra-int.h b/gcc/lra-int.h
index 7da359ec2e2..b043bab6380 100644
--- a/gcc/lra-int.h
+++ b/gcc/lra-int.h
@@ -30,6 +30,26 @@ along with GCC; see the file COPYING3. If not see
typedef struct lra_live_range *lra_live_range_t;
+struct dependent_filter
+{
+ int id;
+ machine_mode mode;
+ unsigned int partner_regno;
+ machine_mode partner_mode;
+ bool is_ref;
+};
+
+/* Cache entry that extends dependent_filter with the precomputed set of
+ allowed hardregs. */
+
+struct dependent_filter_entry : dependent_filter
+{
+ HARD_REG_SET allowed;
+};
+
+extern void lra_init_dependent_filter_cache (void);
+extern void lra_finish_dependent_filter_cache (void);
+
/* The structure describes program points where a given pseudo lives.
The live ranges can be used to find conflicts with other pseudos.
If the live ranges of two pseudos are intersected, the pseudos are
@@ -113,6 +133,8 @@ public:
/* This member is set up in lra-lives.cc for subsequent
assignments. */
lra_copy_t copies;
+ /* Dependent filters for this reg. */
+ vec<dependent_filter> dependent_filters;
};
/* References to the common info about each register. */
diff --git a/gcc/lra.cc b/gcc/lra.cc
index f0871d3faf7..10391df582a 100644
--- a/gcc/lra.cc
+++ b/gcc/lra.cc
@@ -1373,6 +1373,7 @@ initialize_lra_reg_info_element (int i)
lra_reg_info[i].val = get_new_reg_value ();
lra_reg_info[i].offset = 0;
lra_reg_info[i].copies = NULL;
+ lra_reg_info[i].dependent_filters = vNULL;
}
/* Initialize common reg info and copies. */
@@ -1398,7 +1399,10 @@ finish_reg_info (void)
int i;
for (i = 0; i < reg_info_size; i++)
- bitmap_clear (&lra_reg_info[i].insn_bitmap);
+ {
+ bitmap_clear (&lra_reg_info[i].insn_bitmap);
+ lra_reg_info[i].dependent_filters.release ();
+ }
free (lra_reg_info);
reg_info_size = 0;
}
@@ -2698,6 +2702,7 @@ void
lra_init_once (void)
{
init_insn_code_data_once ();
+ lra_init_dependent_filter_cache ();
}
/* Called once per compiler to finish LRA data which are initialize
@@ -2706,4 +2711,5 @@ void
lra_finish_once (void)
{
finish_insn_code_data_once ();
+ lra_finish_dependent_filter_cache ();
}
diff --git a/gcc/lra.h b/gcc/lra.h
index f7f10dfeae6..08ea6091e67 100644
--- a/gcc/lra.h
+++ b/gcc/lra.h
@@ -38,5 +38,8 @@ extern rtx lra_eliminate_regs (rtx, machine_mode, rtx);
extern void lra (FILE *, int);
extern void lra_init_once (void);
extern void lra_finish_once (void);
+extern const HARD_REG_SET *lra_get_dependent_filter
+ (int, machine_mode, unsigned int, machine_mode, bool);
+extern void lra_reset_dependent_filters ();
#endif /* GCC_LRA_H */
--
2.53.0
