[PATCH] M68K: avoid quadratic slowdlow in label alignment check

[PATCH] M68K: avoid quadratic slowdlow in label alignment check

[Sergei Trofimovich]

From: Sergei Trofimovich <siarheit@google.com>

Before the change tc-m68k maintained a list of seen labels.
Alignment check traversed label list to resolve symbol to label.
This caused quadratic slowdown as each symbol was checked against
each label. Worst affected files are the ones built with debugging
enabled as DWARF generates many labels.

The change embeds auxiliary label information right into symbol using
TC_SYMFIELD_TYPE.

Before the change test from PR 29058 did not finish in 10 minutes. After
the change it finishes in 2 seconds.

gas/ChangeLog:

	PR 29058
	* config/tc-m68k.h (TC_SYMFIELD_TYPE): define as m68k_tc_sy.
	* config/tc-m68k.c (m68k_frob_label): Use TC_SYMFIELD_TYPE to
	store label information.
---
 gas/config/tc-m68k.c | 43 +++++++++----------------------------------
 gas/config/tc-m68k.h | 17 +++++++++++++++++
 2 files changed, 26 insertions(+), 34 deletions(-)

diff --git a/gas/config/tc-m68k.c b/gas/config/tc-m68k.c
index 6184f6bf91b..9afa2448482 100644
--- a/gas/config/tc-m68k.c
+++ b/gas/config/tc-m68k.c
@@ -107,25 +107,9 @@ static int m68k_rel32_from_cmdline;
    displacement.  */
 static enum m68k_size m68k_index_width_default = SIZE_LONG;
 
-/* We want to warn if any text labels are misaligned.  In order to get
-   the right line number, we need to record the line number for each
-   label.  */
-struct label_line
-{
-  struct label_line *next;
-  symbolS *label;
-  const char *file;
-  unsigned int line;
-  int text;
-};
-
-/* The list of labels.  */
-
-static struct label_line *labels;
-
 /* The current label.  */
 
-static struct label_line *current_label;
+static struct m68k_tc_sy *current_label;
 
 /* Pointer to list holding the opcodes sorted by name.  */
 static struct m68k_opcode const ** m68k_sorted_opcodes;
@@ -4697,14 +4681,11 @@ md_begin (void)
 void
 m68k_frob_label (symbolS *sym)
 {
-  struct label_line *n;
+  struct m68k_tc_sy *n;
 
-  n = XNEW (struct label_line);
-  n->next = labels;
-  n->label = sym;
+  n = symbol_get_tc (sym);
   n->file = as_where (&n->line);
   n->text = 0;
-  labels = n;
   current_label = n;
 
   dwarf2_emit_label (sym);
@@ -4733,19 +4714,13 @@ m68k_frob_symbol (symbolS *sym)
     }
   else if ((S_GET_VALUE (sym) & 1) != 0)
     {
-      struct label_line *l;
+      struct m68k_tc_sy *l;
+      l = symbol_get_tc (sym);
 
-      for (l = labels; l != NULL; l = l->next)
-	{
-	  if (l->label == sym)
-	    {
-	      if (l->text)
-		as_warn_where (l->file, l->line,
-			       _("text label `%s' aligned to odd boundary"),
-			       S_GET_NAME (sym));
-	      break;
-	    }
-	}
+      if (l->text)
+        as_warn_where (l->file, l->line,
+		       _("text label `%s' aligned to odd boundary"),
+		       S_GET_NAME (sym));
     }
 }
 \f
diff --git a/gas/config/tc-m68k.h b/gas/config/tc-m68k.h
index 5039db8f9db..4ab62b16b1a 100644
--- a/gas/config/tc-m68k.h
+++ b/gas/config/tc-m68k.h
@@ -18,6 +18,9 @@
    Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
    02110-1301, USA.  */
 
+#ifndef TC_M68K_H
+#define TC_M68K_H
+
 #define TC_M68K 1
 
 struct fix;
@@ -139,3 +142,17 @@ struct broken_word;
   tc_m68k_check_adjusted_broken_word ((offsetT) (new_offset), (brokw))
 extern void tc_m68k_check_adjusted_broken_word (offsetT,
 						struct broken_word *);
+
+/* We want to warn if any text labels are misaligned.  In order to get
+   the right line number, we need to record the line number for each
+   label.  */
+struct m68k_tc_sy
+{
+  const char *file;
+  unsigned int line;
+  int text;
+};
+
+#define TC_SYMFIELD_TYPE struct m68k_tc_sy
+
+#endif /* TC_M68K_H */
-- 
2.35.1

Re: [PATCH] M68K: avoid quadratic slowdlow in label alignment check

[Alan Modra]

On Thu, Apr 14, 2022 at 09:01:58AM +0100, Sergei Trofimovich via Binutils wrote:
> From: Sergei Trofimovich <siarheit@google.com>
> 
> Before the change tc-m68k maintained a list of seen labels.
> Alignment check traversed label list to resolve symbol to label.
> This caused quadratic slowdown as each symbol was checked against
> each label. Worst affected files are the ones built with debugging
> enabled as DWARF generates many labels.
> 
> The change embeds auxiliary label information right into symbol using
> TC_SYMFIELD_TYPE.
> 
> Before the change test from PR 29058 did not finish in 10 minutes. After
> the change it finishes in 2 seconds.
> 
> gas/ChangeLog:
> 
> 	PR 29058
> 	* config/tc-m68k.h (TC_SYMFIELD_TYPE): define as m68k_tc_sy.
> 	* config/tc-m68k.c (m68k_frob_label): Use TC_SYMFIELD_TYPE to
> 	store label information.

Looks good to commit, thanks!

-- 
Alan Modra
Australia Development Lab, IBM

Re: [PATCH] M68K: avoid quadratic slowdlow in label alignment check

[Sergei Trofimovich]

On Thu, 14 Apr 2022 19:30:20 +0930
Alan Modra <amodra@gmail.com> wrote:

> On Thu, Apr 14, 2022 at 09:01:58AM +0100, Sergei Trofimovich via Binutils wrote:
> > From: Sergei Trofimovich <siarheit@google.com>
> > 
> > Before the change tc-m68k maintained a list of seen labels.
> > Alignment check traversed label list to resolve symbol to label.
> > This caused quadratic slowdown as each symbol was checked against
> > each label. Worst affected files are the ones built with debugging
> > enabled as DWARF generates many labels.
> > 
> > The change embeds auxiliary label information right into symbol using
> > TC_SYMFIELD_TYPE.
> > 
> > Before the change test from PR 29058 did not finish in 10 minutes. After
> > the change it finishes in 2 seconds.
> > 
> > gas/ChangeLog:
> > 
> > 	PR 29058
> > 	* config/tc-m68k.h (TC_SYMFIELD_TYPE): define as m68k_tc_sy.
> > 	* config/tc-m68k.c (m68k_frob_label): Use TC_SYMFIELD_TYPE to
> > 	store label information.  
> 
> Looks good to commit, thanks!

Thank you! Pushed to master as:
    https://sourceware.org/git/?p=binutils-gdb.git;a=commitdiff;h=c641fe0dcb88

Would it be reasonable to backport it to binutils-.2.28 branch?
Suggested by John Paul Adrian Glaubitz as a Debian maintainer.

I can do it if it's ok. 'git cherry-pick -x c641fe0dcb88' works
as is and passes m68k tests.

-- 

  Sergei