summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorJulian Wachter <julian.wachter@student.kit.edu>2022-02-21 18:59:31 +0100
committerJulian Wachter <julian.wachter@student.kit.edu>2022-06-30 11:13:09 +0200
commitc96dbce2850786d0f3741417491765fbca3ffe01 (patch)
treea9277a6405169abb3e9a29a0c1561505aa1416fc
parent8e965bdb79129548d5b986284399a0f21d5f5b0e (diff)
Give up and spill all callee-saves if too many are spilled
If we detect that >= half of our callee-saved registers are spilled, we opt to not materialize them. This effectively reverts our spilling decisions and lets us start from scratch again. We then spill all callee-saved registers right at the start, lowering the register pressure in the rest of the function significantly. Later optimization passes eliminate `spill-reload` combinations that aren't needed, so this will not introduce useless spills.
-rw-r--r--ir/be/bespillbelady.c85
-rw-r--r--ir/be/bespillutil.c5
-rw-r--r--ir/be/bespillutil.h9
3 files changed, 96 insertions, 3 deletions
diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c
index 120a431..709b079 100644
--- a/ir/be/bespillbelady.c
+++ b/ir/be/bespillbelady.c
@@ -79,6 +79,9 @@ static bool improve_known_preds = true;
(see bespill.h be_get_reload_costs_no_weight) */
static int remat_bonus = 10;
+static bool has_given_up = false;
+static bool can_give_up = true;
+
static const lc_opt_table_entry_t options[] = {
LC_OPT_ENT_BOOL ("movespills", "try to move spills out of loops", &move_spills),
LC_OPT_ENT_BOOL ("respectloopdepth", "outermost loop cutting", &respectloopdepth),
@@ -867,6 +870,38 @@ static void fix_block_borders(ir_node *block, void *data)
}
}
+static void give_up_based_on_callee_save_pressure(ir_graph* irg) {
+ int spill_count = 0;
+ int total_count = 0;
+ DB((dbg, DBG_FIX, "\nShould we give up based on callee-saved spill status?\n"));
+
+ ir_node *start = get_irg_start(irg);
+ foreach_out_edge(start, edge) {
+ if (!is_Proj(edge->src) || arch_irn_is_ignore(edge->src)) {
+ continue;
+ }
+ const arch_register_req_t *req = arch_get_irn_register_req(edge->src);
+ if (req->limited == NULL) {
+ continue;
+ }
+ total_count++;
+
+ if (was_spilled(senv, edge->src)) {
+ const char *register_name = arch_get_irn_register(edge->src)->name;
+ DB((dbg, DBG_FIX, " %+F is spilled (%3s)\n", edge->src, register_name));
+ spill_count++;
+ }
+ }
+
+ DB((dbg, DBG_FIX, " %d out of %d are spilled\n", spill_count, total_count));
+ if (spill_count >= total_count / 2) {
+ DB((dbg, DBG_FIX, " Giving up\n"));
+ has_given_up = true;
+ } else {
+ DB((dbg, DBG_FIX, " Carrying on as ratio is acceptable\n"));
+ }
+}
+
static void be_spill_belady(ir_graph *irg, const arch_register_class_t *rcls,
const regalloc_if_t *regif)
{
@@ -897,6 +932,25 @@ static void be_spill_belady(ir_graph *irg, const arch_register_class_t *rcls,
stat_ev_tim_pop("belady_time_init");
stat_ev_tim_push();
+
+ // We gave up, just spill every callee-saved register
+ if (has_given_up) {
+ DB((dbg, DBG_FIX, "We have given up, spilling all callee-saves\n"));
+ ir_node *start = get_irg_start(irg);
+ foreach_out_edge(start, edge) {
+ if (!is_Proj(edge->src) || arch_irn_is_ignore(edge->src)) {
+ continue;
+ }
+ const arch_register_req_t *req = arch_get_irn_register_req(edge->src);
+ if (req->limited == NULL) {
+ continue;
+ }
+ be_add_spill(senv, edge->src, start);
+ const char *register_name = arch_get_irn_register(edge->src)->name;
+ DB((dbg, DBG_FIX, " spill %+F (%3s)\n", edge->src, register_name));
+ }
+ }
+
/* walk blocks in reverse postorder */
for (size_t i = ARR_LEN(blocklist); i-- > 0; ) {
process_block(blocklist[i]);
@@ -912,8 +966,17 @@ static void be_spill_belady(ir_graph *irg, const arch_register_class_t *rcls,
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
- /* Insert spill/reload nodes into the graph and fix usages */
- be_insert_spills_reloads(senv);
+ if (can_give_up) {
+ give_up_based_on_callee_save_pressure(irg);
+ }
+
+ // Only spill if we haven't given up, as we will retry in that case
+ if (!has_given_up || !can_give_up) {
+ /* Insert spill/reload nodes into the graph and fix usages */
+ be_insert_spills_reloads(senv);
+ } else {
+ DB((dbg, DBG_FIX, "Skipping spill materialization as we have given up and will try again\n"));
+ }
/* clean up */
be_delete_spill_env(senv);
@@ -923,6 +986,22 @@ static void be_spill_belady(ir_graph *irg, const arch_register_class_t *rcls,
obstack_free(&obst, NULL);
}
+static void be_spill_belady_wrapper(ir_graph *irg, const arch_register_class_t *rcls,
+ const regalloc_if_t *regif)
+{
+ // First try, we can still give up :^)
+ can_give_up = true;
+ has_given_up = false;
+ be_spill_belady(irg, rcls, regif);
+
+ // Second try, but this time failure is not an option
+ if (has_given_up) {
+ DB((dbg, DBG_FIX, "\nTrying again but spilling all callee-saves from the start\n\n"));
+ can_give_up = false;
+ be_spill_belady(irg, rcls, regif);
+ }
+}
+
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady)
void be_init_spillbelady(void)
{
@@ -930,6 +1009,6 @@ void be_init_spillbelady(void)
lc_opt_entry_t *belady_group = lc_opt_get_grp(be_grp, "belady");
lc_opt_add_table(belady_group, options);
- be_register_spiller("belady", be_spill_belady);
+ be_register_spiller("belady", be_spill_belady_wrapper);
FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady");
}
diff --git a/ir/be/bespillutil.c b/ir/be/bespillutil.c
index 5c1d11b..ba79e29 100644
--- a/ir/be/bespillutil.c
+++ b/ir/be/bespillutil.c
@@ -124,6 +124,11 @@ void be_delete_spill_env(spill_env_t *env)
free(env);
}
+bool was_spilled(spill_env_t* senv, ir_node* to_check) {
+ spill_info_t *info = ir_nodehashmap_get(spill_info_t, &senv->spillmap, to_check);
+ return info != NULL;
+}
+
void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *after)
{
assert(!arch_irn_is(skip_Proj_const(to_spill), dont_spill));
diff --git a/ir/be/bespillutil.h b/ir/be/bespillutil.h
index ad321e0..37cf776 100644
--- a/ir/be/bespillutil.h
+++ b/ir/be/bespillutil.h
@@ -40,6 +40,15 @@ ir_node *be_get_end_of_block_insertion_point(const ir_node *block);
void be_add_spill(spill_env_t *senv, ir_node *to_spill, ir_node *after);
/**
+ * Checks whether a given node is spilled.
+ *
+ * @param senv The spill environment
+ * @param to_check The node to check
+ * @return True if the node was spilled
+ */
+bool was_spilled(spill_env_t* senv, ir_node* to_check);
+
+/**
* Inserts a new entry into the list of reloads to place (the real nodes will
* be created when be_insert_spills_reloads is run). You don't have to
* explicitly create spill nodes, they will be created automatically after