From patchwork Thu Jan 6 14:46:22 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 49621 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 027F4385840C for ; Thu, 6 Jan 2022 14:47:36 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 027F4385840C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1641480456; bh=zH0a1SgL7JDqZkXnSXkPEf3tAkCscYScSmQcB05MepA=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=ZMriCs3BBLJLD9EQihnZtUdbu4U5TYY+TFR+rZqUTAZ1JoUEVbKtzvc7UC/4Myp9T h4mM5lpFgTVZho4QDAdxqAvrIdS9lRITv60d/gWg8UTqghTnwOf7TxmwSUEartnk5C prH58cKGl1X/flLvc5EzMlFMYlLClT9wJIZN+lME= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id A1AB93858023 for ; Thu, 6 Jan 2022 14:46:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A1AB93858023 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 565AA13D5; Thu, 6 Jan 2022 06:46:24 -0800 (PST) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.88]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id D2DE73F5A1; Thu, 6 Jan 2022 06:46:23 -0800 (PST) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, vmakarov@redhat.com, richard.sandiford@arm.com Subject: [PATCH 1/6] ira: Add a ira_loop_border_costs class References: Date: Thu, 06 Jan 2022 14:46:22 +0000 In-Reply-To: (Richard Sandiford's message of "Thu, 06 Jan 2022 14:45:45 +0000") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, SCC_5_SHORT_WORD_LINES, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The final index into (ira_)memory_move_cost is 1 for loads and 0 for stores. Thus the combination: entry_freq * memory_cost[1] + exit_freq * memory_cost[0] is the cost of loading a register on entry to a loop and storing it back on exit from the loop. This is the cost to use if the register is successfully allocated within the loop but is spilled in the parent loop. Similarly: entry_freq * memory_cost[0] + exit_freq * memory_cost[1] is the cost of storing a register on entry to the loop and restoring it on exit from the loop. This is the cost to use if the register is spilled within the loop but is successfully allocated in the parent loop. The patch adds a helper class for calculating these values and mechanically replaces the existing instances. There is no attempt to editorialise the choice between using “spill inside” and “spill outside” costs. (I think one of them is the wrong way round, but a later patch deals with that.) No functional change intended. gcc/ PR rtl-optimization/98782 * ira-int.h (ira_loop_border_costs): New class. * ira-color.c (ira_loop_border_costs::ira_loop_border_costs): New constructor. (calculate_allocno_spill_cost): Use ira_loop_border_costs. (color_pass): Likewise. (move_spill_restore): Likewise. --- gcc/ira-color.c | 76 +++++++++++++++++++------------------------------ gcc/ira-int.h | 56 ++++++++++++++++++++++++++++++++++++ 2 files changed, 86 insertions(+), 46 deletions(-) diff --git a/gcc/ira-color.c b/gcc/ira-color.c index e0b4e490043..66c11710b97 100644 --- a/gcc/ira-color.c +++ b/gcc/ira-color.c @@ -2567,13 +2567,23 @@ ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) return REG_FREQ_FROM_EDGE_FREQ (freq); } +/* Construct an object that describes the boundary between A and its + parent allocno. */ +ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a) + : m_mode (ALLOCNO_MODE (a)), + m_class (ALLOCNO_CLASS (a)), + m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a), + ALLOCNO_REGNO (a), false)), + m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a), + ALLOCNO_REGNO (a), true)) +{ +} + /* Calculate and return the cost of putting allocno A into memory. */ static int calculate_allocno_spill_cost (ira_allocno_t a) { int regno, cost; - machine_mode mode; - enum reg_class rclass; ira_allocno_t parent_allocno; ira_loop_tree_node_t parent_node, loop_node; @@ -2586,24 +2596,12 @@ calculate_allocno_spill_cost (ira_allocno_t a) return cost; if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL) return cost; - mode = ALLOCNO_MODE (a); - rclass = ALLOCNO_CLASS (a); + ira_loop_border_costs border_costs (a); if (ALLOCNO_HARD_REGNO (parent_allocno) < 0) - cost -= (ira_memory_move_cost[mode][rclass][0] - * ira_loop_edge_freq (loop_node, regno, true) - + ira_memory_move_cost[mode][rclass][1] - * ira_loop_edge_freq (loop_node, regno, false)); + cost -= border_costs.spill_outside_loop_cost (); else - { - ira_init_register_move_cost_if_necessary (mode); - cost += ((ira_memory_move_cost[mode][rclass][1] - * ira_loop_edge_freq (loop_node, regno, true) - + ira_memory_move_cost[mode][rclass][0] - * ira_loop_edge_freq (loop_node, regno, false)) - - (ira_register_move_cost[mode][rclass][rclass] - * (ira_loop_edge_freq (loop_node, regno, false) - + ira_loop_edge_freq (loop_node, regno, true)))); - } + cost += (border_costs.spill_inside_loop_cost () + - border_costs.move_between_loops_cost ()); return cost; } @@ -3342,7 +3340,7 @@ static void color_pass (ira_loop_tree_node_t loop_tree_node) { int regno, hard_regno, index = -1, n; - int cost, exit_freq, enter_freq; + int cost; unsigned int j; bitmap_iterator bi; machine_mode mode; @@ -3466,8 +3464,6 @@ color_pass (ira_loop_tree_node_t loop_tree_node) } continue; } - exit_freq = ira_loop_edge_freq (subloop_node, regno, true); - enter_freq = ira_loop_edge_freq (subloop_node, regno, false); ira_assert (regno < ira_reg_equiv_len); if (ira_equiv_no_lvalue_p (regno)) { @@ -3483,16 +3479,16 @@ color_pass (ira_loop_tree_node_t loop_tree_node) } else if (hard_regno < 0) { + ira_loop_border_costs border_costs (subloop_allocno); ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno) - -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq) - + (ira_memory_move_cost[mode][rclass][0] * exit_freq)); + -= border_costs.spill_outside_loop_cost (); } else { + ira_loop_border_costs border_costs (subloop_allocno); aclass = ALLOCNO_CLASS (subloop_allocno); ira_init_register_move_cost_if_necessary (mode); - cost = (ira_register_move_cost[mode][rclass][rclass] - * (exit_freq + enter_freq)); + cost = border_costs.move_between_loops_cost (); ira_allocate_and_set_or_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass, ALLOCNO_UPDATED_CLASS_COST (subloop_allocno), @@ -3508,8 +3504,7 @@ color_pass (ira_loop_tree_node_t loop_tree_node) ALLOCNO_UPDATED_CLASS_COST (subloop_allocno) = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index]; ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno) - += (ira_memory_move_cost[mode][rclass][0] * enter_freq - + ira_memory_move_cost[mode][rclass][1] * exit_freq); + += border_costs.spill_inside_loop_cost (); } } } @@ -3550,7 +3545,6 @@ move_spill_restore (void) { int cost, regno, hard_regno, hard_regno2, index; bool changed_p; - int enter_freq, exit_freq; machine_mode mode; enum reg_class rclass; ira_allocno_t a, parent_allocno, subloop_allocno; @@ -3605,38 +3599,28 @@ move_spill_restore (void) - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL ? ALLOCNO_CLASS_COST (subloop_allocno) : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])); - exit_freq = ira_loop_edge_freq (subloop_node, regno, true); - enter_freq = ira_loop_edge_freq (subloop_node, regno, false); + ira_loop_border_costs border_costs (subloop_allocno); if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0) - cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq - + ira_memory_move_cost[mode][rclass][1] * enter_freq); + cost -= border_costs.spill_outside_loop_cost (); else { - cost - += (ira_memory_move_cost[mode][rclass][0] * exit_freq - + ira_memory_move_cost[mode][rclass][1] * enter_freq); + cost += border_costs.spill_outside_loop_cost (); if (hard_regno2 != hard_regno) - cost -= (ira_register_move_cost[mode][rclass][rclass] - * (exit_freq + enter_freq)); + cost -= border_costs.move_between_loops_cost (); } } if ((parent = loop_node->parent) != NULL && (parent_allocno = parent->regno_allocno_map[regno]) != NULL) { ira_assert (rclass == ALLOCNO_CLASS (parent_allocno)); - exit_freq = ira_loop_edge_freq (loop_node, regno, true); - enter_freq = ira_loop_edge_freq (loop_node, regno, false); + ira_loop_border_costs border_costs (a); if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0) - cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq - + ira_memory_move_cost[mode][rclass][1] * enter_freq); + cost -= border_costs.spill_outside_loop_cost (); else { - cost - += (ira_memory_move_cost[mode][rclass][1] * exit_freq - + ira_memory_move_cost[mode][rclass][0] * enter_freq); + cost += border_costs.spill_inside_loop_cost (); if (hard_regno2 != hard_regno) - cost -= (ira_register_move_cost[mode][rclass][rclass] - * (exit_freq + enter_freq)); + cost -= border_costs.move_between_loops_cost (); } } if (cost < 0) diff --git a/gcc/ira-int.h b/gcc/ira-int.h index 59d2872cac3..b32c80d4c9e 100644 --- a/gcc/ira-int.h +++ b/gcc/ira-int.h @@ -1539,4 +1539,60 @@ ira_need_caller_save_p (ira_allocno_t a, unsigned int regno) ALLOCNO_MODE (a), regno); } +/* Represents the boundary between an allocno in one loop and its parent + allocno in the enclosing loop. It is usually possible to change a + register's allocation on this boundary; the class provides routines + for calculating the cost of such changes. */ +class ira_loop_border_costs +{ +public: + ira_loop_border_costs (ira_allocno_t); + + int move_between_loops_cost () const; + int spill_outside_loop_cost () const; + int spill_inside_loop_cost () const; + +private: + /* The mode and class of the child allocno. */ + machine_mode m_mode; + reg_class m_class; + + /* Sums the frequencies of the entry edges and the exit edges. */ + int m_entry_freq, m_exit_freq; +}; + +/* Return the cost of storing the register on entry to the loop and + loading it back on exit from the loop. This is the cost to use if + the register is spilled within the loop but is successfully allocated + in the parent loop. */ +inline int +ira_loop_border_costs::spill_inside_loop_cost () const +{ + return (m_entry_freq * ira_memory_move_cost[m_mode][m_class][0] + + m_exit_freq * ira_memory_move_cost[m_mode][m_class][1]); +} + +/* Return the cost of loading the register on entry to the loop and + storing it back on exit from the loop. This is the cost to use if + the register is successfully allocated within the loop but is spilled + in the parent loop. */ +inline int +ira_loop_border_costs::spill_outside_loop_cost () const +{ + return (m_entry_freq * ira_memory_move_cost[m_mode][m_class][1] + + m_exit_freq * ira_memory_move_cost[m_mode][m_class][0]); +} + +/* Return the cost of moving the pseudo register between different hard + registers on entry and exit from the loop. This is the cost to use + if the register is successfully allocated within both this loop and + the parent loop, but the allocations for the loops differ. */ +inline int +ira_loop_border_costs::move_between_loops_cost () const +{ + ira_init_register_move_cost_if_necessary (m_mode); + auto move_cost = ira_register_move_cost[m_mode][m_class][m_class]; + return move_cost * (m_entry_freq + m_exit_freq); +} + #endif /* GCC_IRA_INT_H */