diff mbox series

[03/12] mode-switching: Avoid quadractic list operation

Message ID mptlebc82c9.fsf@arm.com
State New
Headers show
Series Tweaks and extensions to the mode-switching pass | expand

Commit Message

Richard Sandiford Nov. 5, 2023, 6:47 p.m. UTC 
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(-)

Comments

Jeff Law Nov. 7, 2023, 12:47 a.m. UTC | #1 
On 11/5/23 11:47, Richard Sandiford wrote:
> 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.
OK
jeff
diff mbox series

Patch

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 &regs_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);