From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x436.google.com (mail-wr1-x436.google.com [IPv6:2a00:1450:4864:20::436]) by sourceware.org (Postfix) with ESMTPS id 952603857404 for ; Thu, 28 Apr 2022 18:35:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 952603857404 Received: by mail-wr1-x436.google.com with SMTP id k2so7910086wrd.5 for ; Thu, 28 Apr 2022 11:35:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=bZRqD9xNrSZiTJPueOIeLXrA6+UBhtDjc0a/hl5mRRs=; b=tbgl7jbz9Lv3qVrTA+PEOt5raYNot+zy+IlwUHo66sBNSgtZIPpA/sVeo+uFDjyqMs EewQuQzIl1wKiQv5FrBYsmJpVTrLGaekesFHRTnsqV4L+zvudmM30aDEeUanRr6Qc+Ut ZcSyET/MT+DAHbA3ouUyu5r/4H/y3RNvgr80F66O7oaoGYWxv+gFLsITHfXdan/sVkZg CS/3LLuiIQrkNBy5UCY3MGbkkuRK4p/4ioIqW4X/LTln1VvSOiK9FRyBzOcG9N5LLy+0 uVnhLJ8TeDIpZeDxDCS6/jvXZQkVP9MCeLVMKC18fh2I0HAsHShCbW1sXoHwkH4PSs/V uwpg== X-Gm-Message-State: AOAM5329GctpMe0hpTUZ3dV9hjjzsNO2fZhnRkxmoacrmzJVCuA2VphD chTJvgx3doSI2AGtG0H1puc= X-Google-Smtp-Source: ABdhPJxK7TjVjtSKLCLU65wGksmBPfaoSAGvfp4ChKjVC2mm7UL4DqAX5+BjKRbiFHqIKILnQQskQg== X-Received: by 2002:a05:6000:1789:b0:20a:9fbc:b1b5 with SMTP id e9-20020a056000178900b0020a9fbcb1b5mr27263263wrg.581.1651170911148; Thu, 28 Apr 2022 11:35:11 -0700 (PDT) Received: from nz.home (host81-147-8-147.range81-147.btcentralplus.com. [81.147.8.147]) by smtp.gmail.com with ESMTPSA id j24-20020adfa558000000b0020ae9eafef9sm460029wrb.92.2022.04.28.11.35.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 28 Apr 2022 11:35:10 -0700 (PDT) Received: by nz.home (Postfix, from userid 1000) id CACA72FE61D04; Thu, 28 Apr 2022 19:35:09 +0100 (BST) From: Sergei Trofimovich To: binutils@sourceware.org Cc: Sergei Trofimovich Subject: [binutils-2.38 backport][PATCH] M68K: avoid quadratic slowdlow in label alignment check Date: Thu, 28 Apr 2022 19:35:03 +0100 Message-Id: <20220428183503.938467-1-slyich@gmail.com> X-Mailer: git-send-email 2.35.3 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, 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: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 28 Apr 2022 18:35:14 -0000 From: Sergei Trofimovich 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. (cherry picked from commit c641fe0dcb886dc1b8a235ab2b236275ee46510a) --- 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)); } } 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.3