From 3133bed5d0327e8a9cd0a601b7ecdb9de4fc825d Mon Sep 17 00:00:00 2001 From: "Vladimir N. Makarov" Date: Sun, 23 Feb 2020 16:20:05 -0500 Subject: [PATCH] Changing cost propagation and ordering colorable bucket heuristics for PR93564. 2020-02-23 Vladimir Makarov PR rtl-optimization/93564 * ira-color.c (struct update_cost_queue_elem): New member start. (queue_update_cost, get_next_update_cost): Add new arg start. (allocnos_conflict_p): New function. (update_costs_from_allocno): Add new arg conflict_cost_update_p. Add checking conflicts with allocnos_conflict_p. (update_costs_from_prefs, restore_costs_from_copies): Adjust update_costs_from_allocno calls. (update_conflict_hard_regno_costs): Add checking conflicts with allocnos_conflict_p. Adjust calls of queue_update_cost and get_next_update_cost. (assign_hard_reg): Adjust calls of queue_update_cost. Add debugging print. (bucket_allocno_compare_func): Restore previous version. --- gcc/ChangeLog | 17 ++++++++++ gcc/ira-color.c | 97 +++++++++++++++++++++++++++++++++++++-------------------- 2 files changed, 81 insertions(+), 33 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cea52f0..b3b9d92 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,20 @@ +2020-02-23 Vladimir Makarov + + PR rtl-optimization/93564 + * ira-color.c (struct update_cost_queue_elem): New member start. + (queue_update_cost, get_next_update_cost): Add new arg start. + (allocnos_conflict_p): New function. + (update_costs_from_allocno): Add new arg conflict_cost_update_p. + Add checking conflicts with allocnos_conflict_p. + (update_costs_from_prefs, restore_costs_from_copies): Adjust + update_costs_from_allocno calls. + (update_conflict_hard_regno_costs): Add checking conflicts with + allocnos_conflict_p. Adjust calls of queue_update_cost and + get_next_update_cost. + (assign_hard_reg): Adjust calls of queue_update_cost. Add + debugging print. + (bucket_allocno_compare_func): Restore previous version. + 2020-02-21 John David Anglin * gcc/config/pa/pa.c (pa_function_value): Fix check for word and diff --git a/gcc/ira-color.c b/gcc/ira-color.c index 0bcc804..0ffdd19 100644 --- a/gcc/ira-color.c +++ b/gcc/ira-color.c @@ -1199,6 +1199,10 @@ struct update_cost_queue_elem connecting this allocno to the one being allocated. */ int divisor; + /* Allocno from which we started chaining costs of connected + allocnos. */ + ira_allocno_t start; + /* Allocno from which we are chaining costs of connected allocnos. It is used not go back in graph of allocnos connected by copies. */ @@ -1258,10 +1262,11 @@ start_update_cost (void) update_cost_queue = NULL; } -/* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless +/* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless ALLOCNO is already in the queue, or has NO_REGS class. */ static inline void -queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor) +queue_update_cost (ira_allocno_t allocno, ira_allocno_t start, + ira_allocno_t from, int divisor) { struct update_cost_queue_elem *elem; @@ -1270,6 +1275,7 @@ queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor) && ALLOCNO_CLASS (allocno) != NO_REGS) { elem->check = update_cost_check; + elem->start = start; elem->from = from; elem->divisor = divisor; elem->next = NULL; @@ -1282,10 +1288,11 @@ queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor) } /* Try to remove the first element from update_cost_queue. Return - false if the queue was empty, otherwise make (*ALLOCNO, *FROM, - *DIVISOR) describe the removed element. */ + false if the queue was empty, otherwise make (*ALLOCNO, *START, + *FROM, *DIVISOR) describe the removed element. */ static inline bool -get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor) +get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start, + ira_allocno_t *from, int *divisor) { struct update_cost_queue_elem *elem; @@ -1294,6 +1301,7 @@ get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor) *allocno = update_cost_queue; elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)]; + *start = elem->start; *from = elem->from; *divisor = elem->divisor; update_cost_queue = elem->next; @@ -1325,18 +1333,41 @@ update_allocno_cost (ira_allocno_t allocno, int hard_regno, return true; } +/* Return TRUE if allocnos A1 and A2 conflicts. Here we are + interesting only in conflicts of allocnos with intersected allocno + classes. */ +static bool +allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2) +{ + ira_object_t obj, conflict_obj; + ira_object_conflict_iterator oci; + int word, nwords = ALLOCNO_NUM_OBJECTS (a1); + + for (word = 0; word < nwords; word++) + { + obj = ALLOCNO_OBJECT (a1, word); + /* Take preferences of conflicting allocnos into account. */ + FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) + if (OBJECT_ALLOCNO (conflict_obj) == a2) + return true; + } + return false; +} + /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected by copies to ALLOCNO to increase chances to remove some copies as - the result of subsequent assignment. Record cost updates if - RECORD_P is true. */ + the result of subsequent assignment. Update conflict costs only + for true CONFLICT_COST_UPDATE_P. Record cost updates if RECORD_P is + true. */ static void update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, - int divisor, bool decr_p, bool record_p) + int divisor, bool decr_p, bool record_p, + bool conflict_cost_update_p) { int cost, update_cost, update_conflict_cost; machine_mode mode; enum reg_class rclass, aclass; - ira_allocno_t another_allocno, from = NULL; + ira_allocno_t another_allocno, start = allocno, from = NULL; ira_copy_t cp, next_cp; rclass = REGNO_REG_CLASS (hard_regno); @@ -1359,7 +1390,8 @@ update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, else gcc_unreachable (); - if (another_allocno == from) + if (another_allocno == from + || allocnos_conflict_p (another_allocno, start)) continue; aclass = ALLOCNO_CLASS (another_allocno); @@ -1384,7 +1416,8 @@ update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, if (decr_p) cost = -cost; - update_conflict_cost = update_cost = cp->freq * cost / divisor; + update_cost = cp->freq * cost / divisor; + update_conflict_cost = conflict_cost_update_p ? update_cost : 0; if (ALLOCNO_COLOR_DATA (another_allocno) != NULL && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno @@ -1399,7 +1432,8 @@ update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, if (! update_allocno_cost (another_allocno, hard_regno, update_cost, update_conflict_cost)) continue; - queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR); + queue_update_cost (another_allocno, start, allocno, + divisor * COST_HOP_DIVISOR); if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL) ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records = get_update_cost_record (hard_regno, divisor, @@ -1407,7 +1441,7 @@ update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, ->update_cost_records); } } - while (get_next_update_cost (&allocno, &from, &divisor)); + while (get_next_update_cost (&allocno, &start, &from, &divisor)); } /* Decrease preferred ALLOCNO hard register costs and costs of @@ -1420,7 +1454,7 @@ update_costs_from_prefs (ira_allocno_t allocno) start_update_cost (); for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref) update_costs_from_allocno (allocno, pref->hard_regno, - COST_HOP_DIVISOR, true, true); + COST_HOP_DIVISOR, true, true, false); } /* Update (decrease if DECR_P) the cost of allocnos connected to @@ -1435,7 +1469,7 @@ update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p) hard_regno = ALLOCNO_HARD_REGNO (allocno); ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS); start_update_cost (); - update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p); + update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p, true); } /* Update conflict_allocno_hard_prefs of allocnos conflicting with @@ -1485,7 +1519,7 @@ restore_costs_from_copies (ira_allocno_t allocno) start_update_cost (); for (curr = records; curr != NULL; curr = curr->next) update_costs_from_allocno (allocno, curr->hard_regno, - curr->divisor, true, false); + curr->divisor, true, false, true); free_update_cost_record_list (records); ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL; } @@ -1503,10 +1537,10 @@ update_conflict_hard_regno_costs (int *costs, enum reg_class aclass, int *conflict_costs; bool cont_p; enum reg_class another_aclass; - ira_allocno_t allocno, another_allocno, from; + ira_allocno_t allocno, another_allocno, start, from; ira_copy_t cp, next_cp; - while (get_next_update_cost (&allocno, &from, &divisor)) + while (get_next_update_cost (&allocno, &start, &from, &divisor)) for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) { if (cp->first == allocno) @@ -1522,7 +1556,8 @@ update_conflict_hard_regno_costs (int *costs, enum reg_class aclass, else gcc_unreachable (); - if (another_allocno == from) + if (another_allocno == from + || allocnos_conflict_p (another_allocno, start)) continue; another_aclass = ALLOCNO_CLASS (another_allocno); @@ -1568,7 +1603,7 @@ update_conflict_hard_regno_costs (int *costs, enum reg_class aclass, * COST_HOP_DIVISOR * COST_HOP_DIVISOR * COST_HOP_DIVISOR)) - queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR); + queue_update_cost (another_allocno, start, from, divisor * COST_HOP_DIVISOR); } } @@ -1837,8 +1872,7 @@ assign_hard_reg (ira_allocno_t a, bool retry_p) continue; full_costs[j] -= conflict_costs[k]; } - queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR); - + queue_update_cost (conflict_a, conflict_a, NULL, COST_HOP_DIVISOR); } } } @@ -1852,7 +1886,7 @@ assign_hard_reg (ira_allocno_t a, bool retry_p) if (! retry_p) { start_update_cost (); - queue_update_cost (a, NULL, COST_HOP_DIVISOR); + queue_update_cost (a, a, NULL, COST_HOP_DIVISOR); update_conflict_hard_regno_costs (full_costs, aclass, false); } min_cost = min_full_cost = INT_MAX; @@ -1897,6 +1931,8 @@ assign_hard_reg (ira_allocno_t a, bool retry_p) best_hard_regno = hard_regno; ira_assert (hard_regno >= 0); } + if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) + fprintf (ira_dump_file, "(%d=%d,%d) ", hard_regno, cost, full_cost); } if (min_full_cost > mem_cost /* Do not spill static chain pointer pseudo when non-local goto @@ -2259,16 +2295,6 @@ bucket_allocno_compare_func (const void *v1p, const void *v2p) ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno; int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2); - /* Push allocnos with minimal hard_reg_prefs first. */ - pref1 = ALLOCNO_COLOR_DATA (a1)->hard_reg_prefs; - pref2 = ALLOCNO_COLOR_DATA (a2)->hard_reg_prefs; - if ((diff = pref1 - pref2) != 0) - return diff; - /* Push allocnos with minimal conflict_allocno_hard_prefs first. */ - pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs; - pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs; - if ((diff = pref1 - pref2) != 0) - return diff; freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq; freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq; if ((diff = freq1 - freq2) != 0) @@ -2294,6 +2320,11 @@ bucket_allocno_compare_func (const void *v1p, const void *v2p) a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num; if ((diff = a2_num - a1_num) != 0) return diff; + /* Push allocnos with minimal conflict_allocno_hard_prefs first. */ + pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs; + pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs; + if ((diff = pref1 - pref2) != 0) + return diff; return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1); } -- 2.7.4