From patchwork Tue Aug 6 11:30:44 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xianmiao Qu X-Patchwork-Id: 1969430 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=linux.alibaba.com header.i=@linux.alibaba.com header.a=rsa-sha256 header.s=default header.b=uOHJ7yIA; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WdWP049x0z1ydt for ; Tue, 6 Aug 2024 21:32:04 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6A6D2385842A for ; Tue, 6 Aug 2024 11:32:02 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from out30-132.freemail.mail.aliyun.com (out30-132.freemail.mail.aliyun.com [115.124.30.132]) by sourceware.org (Postfix) with ESMTPS id 9EFDA385841E for ; Tue, 6 Aug 2024 11:31:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9EFDA385841E Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linux.alibaba.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linux.alibaba.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 9EFDA385841E Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=115.124.30.132 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722943870; cv=none; b=mxe8Aq+RYdwXpM4U69WLw9qj6X1SJti3KZX3iDaqO4QVdHL8getes36lUaG8cV4eSNyKvWBt5VioebIZFCfAjrpasv5XVgBd1ybopjqH7/mpcSkHLqx4oMLqokkip6i2qj789Q/SbNlek2y09mDnBjOplspNQOiSf+P6pkVxx/Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722943870; c=relaxed/simple; bh=A0biSzNMxMxf+kwtkFW1WUaRH+tACWuPkiZkM9qRo14=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=A9u6SW7lBf3vWvAd1UhryXv9wpkmMJ0a3JjKY0BrwiDAnZC9MOi0O1pW0rE3PqgPe1uF9ojrxzH/BS6THFVh5BXPAR4t96a3WZEe+cfVrdnEHJ/CsRF6tpQqcmBADL/hvqVVP/6fm4HJoSdliXjeUTRPNVfBD7uqsqBKFM2PJjw= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.alibaba.com; s=default; t=1722943866; h=From:To:Subject:Date:Message-Id:MIME-Version; bh=SBsnR6r6C7CQoVkz5GnpvMW8ld7HKjd58ruauRNJbhQ=; b=uOHJ7yIAmKKb+2lxFs9+cFbaS43afLKx1z/ZuftcCAnxxU9eRf5e5z/p9wj1vbwIoOD12UmLCBIVJP/YRQSR0MCummO9Pvde3EXjdpNXbODZFk8wkKoD0nxsZ8Ph6kAMbYNN+15iL5+n/750lx4XCp4adk72OHBHkqTQAvmL/nA= X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R251e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=maildocker-contentspam033037067109; MF=cooper.qu@linux.alibaba.com; NM=1; PH=DS; RN=3; SR=0; TI=SMTPD_---0WCFGQfG_1722943862; Received: from localhost(mailfrom:cooper.qu@linux.alibaba.com fp:SMTPD_---0WCFGQfG_1722943862) by smtp.aliyun-inc.com; Tue, 06 Aug 2024 19:31:03 +0800 From: Xianmiao Qu To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Cc: Xianmiao Qu Subject: [PATCH] genoutput: Accelerate the place_operands function. Date: Tue, 6 Aug 2024 19:30:44 +0800 Message-Id: <20240806113044.90204-1-cooper.qu@linux.alibaba.com> X-Mailer: git-send-email 2.32.1 (Apple Git-133) MIME-Version: 1.0 X-Spam-Status: No, score=-29.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, ENV_AND_HDR_SPF_MATCH, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, UNPARSEABLE_RELAY, USER_IN_DEF_DKIM_WL, USER_IN_DEF_SPF_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org With the increase in the number of modes and patterns for some backend architectures, the place_operands function becomes a bottleneck in the speed of genoutput, and may even become a bottleneck in the overall speed of building the GCC project. This patch aims to accelerate the place_operands function, the optimizations it includes are: 1. Use a hash table to store operand information, improving the lookup time for the first operand. 2. Move mode comparison to the beginning to avoid the scenarios of most strcmp. I tested the speed improvements for the following backends, Improvement Ratio x86_64 197.9% aarch64 954.5% riscv 2578.6% If the build machine is slow, then this improvement can save a lot of time. I tested the genoutput output for x86_64/aarch64/riscv backends, and there was no difference compared to before the optimization, so this shouldn't introduce any functional issues. --- gcc/genoutput.cc | 101 ++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 95 insertions(+), 6 deletions(-) diff --git a/gcc/genoutput.cc b/gcc/genoutput.cc index efd81766bb5b..456d96112cfb 100644 --- a/gcc/genoutput.cc +++ b/gcc/genoutput.cc @@ -112,6 +112,8 @@ static int next_operand_number = 1; struct operand_data { struct operand_data *next; + /* Point to the next member with the same hash value in the hash table. */ + struct operand_data *eq_next; int index; const char *predicate; const char *constraint; @@ -127,11 +129,12 @@ struct operand_data static struct operand_data null_operand = { - 0, 0, "", "", E_VOIDmode, 0, 0, 0, 0, 0 + 0, 0, 0, "", "", E_VOIDmode, 0, 0, 0, 0, 0 }; static struct operand_data *odata = &null_operand; static struct operand_data **odata_end = &null_operand.next; +static htab_t operand_data_table; /* Must match the constants in recog.h. */ @@ -180,6 +183,11 @@ static void place_operands (class data *); static void process_template (class data *, const char *); static void validate_insn_alternatives (class data *); static void validate_insn_operands (class data *); +static hashval_t hash_struct_operand_data (const void *); +static int eq_struct_operand_data (const void *, const void *); +static void insert_operand_data (struct operand_data *); +static struct operand_data *lookup_operand_data (struct operand_data *); +static void init_operand_data_table (void); class constraint_data { @@ -532,6 +540,13 @@ compare_operands (struct operand_data *d0, struct operand_data *d1) { const char *p0, *p1; + /* On one hand, comparing strings for predicate and constraint + is time-consuming, and on the other hand, the probability of + different modes is relatively high. Therefore, checking the mode + first can speed up the execution of the program. */ + if (d0->mode != d1->mode) + return 0; + p0 = d0->predicate; if (!p0) p0 = ""; @@ -550,9 +565,6 @@ compare_operands (struct operand_data *d0, struct operand_data *d1) if (strcmp (p0, p1) != 0) return 0; - if (d0->mode != d1->mode) - return 0; - if (d0->strict_low != d1->strict_low) return 0; @@ -577,9 +589,9 @@ place_operands (class data *d) return; } + od = lookup_operand_data (&d->operand[0]); /* Brute force substring search. */ - for (od = odata, i = 0; od; od = od->next, i = 0) - if (compare_operands (od, &d->operand[0])) + for (i = 0; od; od = od->eq_next, i = 0) { od2 = od->next; i = 1; @@ -605,6 +617,7 @@ place_operands (class data *d) *odata_end = od2; odata_end = &od2->next; od2->index = next_operand_number++; + insert_operand_data (od2); } *odata_end = NULL; return; @@ -1049,6 +1062,7 @@ main (int argc, const char **argv) progname = "genoutput"; init_insn_for_nothing (); + init_operand_data_table (); if (!init_rtx_reader_args (argc, argv)) return (FATAL_EXIT_CODE); @@ -1224,3 +1238,78 @@ mdep_constraint_len (const char *s, file_location loc, int opno) message_at (loc, "note: in operand %d", opno); return 1; /* safe */ } + +/* Helper to Hash a struct operand_data. */ + +static hashval_t +hash_struct_operand_data (const void *ptr) +{ + const struct operand_data *d = (const struct operand_data *) ptr; + const char *pred, *cons; + hashval_t hash; + + pred = d->predicate; + if (!pred) + pred = ""; + hash = htab_hash_string (pred); + + cons = d->constraint; + if (!cons) + cons = ""; + hash = iterative_hash (cons, strlen (cons), hash); + + hash = iterative_hash_object (d->mode, hash); + hash = iterative_hash_object (d->strict_low, hash); + hash = iterative_hash_object (d->eliminable, hash); + return hash; +} + +/* Equality function of the operand_data hash table. */ + +static int +eq_struct_operand_data (const void *p1, const void *p2) +{ + const struct operand_data *d1 = (const struct operand_data *) p1; + const struct operand_data *d2 = (const struct operand_data *) p2; + + return compare_operands (const_cast(d1), + const_cast(d2)); +} + +/* Insert the operand_data variable D into the hash table. + If an variable with the same hash value already exists in the hash table, + insert the element at the end of the linked list connected + through the eq_next member. */ + +static void +insert_operand_data (struct operand_data *d) +{ + void **slot = htab_find_slot (operand_data_table, d, INSERT); + if (*slot) + { + struct operand_data *last = (struct operand_data *) *slot; + while (last->eq_next) + last = last->eq_next; + last->eq_next = d; + } + else + *slot = d; +} + +/* Look up the operand_data D in the hash table. */ + +static struct operand_data * +lookup_operand_data (struct operand_data *d) +{ + return (struct operand_data *) htab_find (operand_data_table, d); +} + +/* Initializes the operand_data hash table. */ + +static void +init_operand_data_table (void) +{ + operand_data_table = htab_create_alloc (64, hash_struct_operand_data, + eq_struct_operand_data, 0, + xcalloc, free); +}