From: Richard Sandiford <richard.sandiford@arm.com>
To: gcc-patches@gcc.gnu.org
Cc: jlaw@ventanamicro.com
Subject: [PATCH 03/12] mode-switching: Avoid quadractic list operation
Date: Sun, 05 Nov 2023 18:47:02 +0000 [thread overview]
Message-ID: <mptlebc82c9.fsf@arm.com> (raw)
In-Reply-To: <mpt34xk9gza.fsf@arm.com> (Richard Sandiford's message of "Sun, 05 Nov 2023 18:45:29 +0000")
add_seginfo chained insn information to the end of a list
by starting at the head of the list. This patch avoids the
quadraticness by keeping track of the tail pointer.
gcc/
* mode-switching.cc (add_seginfo): Replace head pointer with
a pointer to the tail pointer.
(optimize_mode_switching): Update calls accordingly.
---
gcc/mode-switching.cc | 24 ++++++++----------------
1 file changed, 8 insertions(+), 16 deletions(-)
diff --git a/gcc/mode-switching.cc b/gcc/mode-switching.cc
index 8577069bde1..bebe89d5fd2 100644
--- a/gcc/mode-switching.cc
+++ b/gcc/mode-switching.cc
@@ -162,23 +162,14 @@ new_seginfo (int mode, rtx_insn *insn, const HARD_REG_SET ®s_live)
}
/* Add a seginfo element to the end of a list.
- HEAD is a pointer to the list beginning.
+ TAIL is a pointer to the list's null terminator.
INFO is the structure to be linked in. */
static void
-add_seginfo (struct bb_info *head, struct seginfo *info)
+add_seginfo (struct seginfo ***tail_ptr, struct seginfo *info)
{
- struct seginfo *ptr;
-
- if (head->seginfo == NULL)
- head->seginfo = info;
- else
- {
- ptr = head->seginfo;
- while (ptr->next != NULL)
- ptr = ptr->next;
- ptr->next = info;
- }
+ **tail_ptr = info;
+ *tail_ptr = &info->next;
}
/* Record in LIVE that register REG died. */
@@ -574,6 +565,7 @@ optimize_mode_switching (void)
Also compute the initial transparency settings. */
FOR_EACH_BB_FN (bb, cfun)
{
+ struct seginfo **tail_ptr = &info[bb->index].seginfo;
struct seginfo *ptr;
int last_mode = no_mode;
bool any_set_required = false;
@@ -599,7 +591,7 @@ optimize_mode_switching (void)
if (ins_pos != BB_END (bb))
ins_pos = NEXT_INSN (ins_pos);
ptr = new_seginfo (no_mode, ins_pos, live_now);
- add_seginfo (info + bb->index, ptr);
+ add_seginfo (&tail_ptr, ptr);
for (i = 0; i < no_mode; i++)
clear_mode_bit (transp[bb->index], j, i);
}
@@ -617,7 +609,7 @@ optimize_mode_switching (void)
any_set_required = true;
last_mode = mode;
ptr = new_seginfo (mode, insn, live_now);
- add_seginfo (info + bb->index, ptr);
+ add_seginfo (&tail_ptr, ptr);
for (i = 0; i < no_mode; i++)
clear_mode_bit (transp[bb->index], j, i);
}
@@ -646,7 +638,7 @@ optimize_mode_switching (void)
if (!any_set_required)
{
ptr = new_seginfo (no_mode, BB_END (bb), live_now);
- add_seginfo (info + bb->index, ptr);
+ add_seginfo (&tail_ptr, ptr);
if (last_mode != no_mode)
for (i = 0; i < no_mode; i++)
clear_mode_bit (transp[bb->index], j, i);
--
2.25.1
next prev parent reply other threads:[~2023-11-05 18:47 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-05 18:45 [PATCH 00/12] Tweaks and extensions to the mode-switching pass Richard Sandiford
2023-11-05 18:46 ` [PATCH 01/12] mode-switching: Tweak the macro/hook documentation Richard Sandiford
2023-11-07 0:10 ` Jeff Law
2023-11-05 18:46 ` [PATCH 02/12] mode-switching: Add note problem Richard Sandiford
2023-11-07 0:11 ` Jeff Law
2023-11-05 18:47 ` Richard Sandiford [this message]
2023-11-07 0:47 ` [PATCH 03/12] mode-switching: Avoid quadractic list operation Jeff Law
2023-11-05 18:47 ` [PATCH 04/12] mode-switching: Fix the mode passed to the emit hook Richard Sandiford
2023-11-07 0:51 ` Jeff Law
2023-11-05 18:47 ` [PATCH 05/12] mode-switching: Simplify recording of transparency Richard Sandiford
2023-11-07 0:52 ` Jeff Law
2023-11-05 18:48 ` [PATCH 06/12] mode-switching: Tweak entry/exit handling Richard Sandiford
2023-11-07 1:01 ` Jeff Law
2023-11-05 18:48 ` [PATCH 07/12] mode-switching: Allow targets to set the mode for EH handlers Richard Sandiford
2023-11-07 1:07 ` Jeff Law
2023-11-08 0:15 ` Richard Sandiford
2023-11-08 2:24 ` Jeff Law
2023-11-05 18:48 ` [PATCH 08/12] mode-switching: Pass set of live registers to the needed hook Richard Sandiford
2023-11-07 1:11 ` Jeff Law
2023-11-05 18:49 ` [PATCH 09/12] mode-switching: Pass the set of live registers to the after hook Richard Sandiford
2023-11-07 1:12 ` Jeff Law
2023-11-05 18:49 ` [PATCH 10/12] mode-switching: Use 1-based edge aux fields Richard Sandiford
2023-11-07 2:53 ` Jeff Law
2023-11-08 0:35 ` Richard Sandiford
2023-11-08 2:22 ` Jeff Law
2023-11-11 15:51 ` Richard Sandiford
2023-11-11 16:19 ` Jeff Law
2023-11-05 18:50 ` [PATCH 11/12] mode-switching: Add a target-configurable confluence operator Richard Sandiford
2023-11-07 3:04 ` Jeff Law
2023-11-11 15:54 ` Richard Sandiford
2023-11-11 16:19 ` Jeff Law
2023-11-11 17:29 ` Richard Sandiford
2023-11-05 18:50 ` [PATCH 12/12] mode-switching: Add a backprop hook Richard Sandiford
2023-11-10 1:18 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=mptlebc82c9.fsf@arm.com \
--to=richard.sandiford@arm.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jlaw@ventanamicro.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).