From patchwork Sun Sep 8 12:43:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 13795448 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9F45515F3F3; Sun, 8 Sep 2024 12:44:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799445; cv=none; b=asfO3rCf52tidueGbt5O68/sJWIiZt0HITROg7NfM8TX43h5PkhCjer7jqj7SoIxsu3Fjp+biWQYq5Mgp7OvFYNGv8bdlRUjqGh3jmPkbsOQP7NADqywZLDwwUY+Zn5K+80XiUcTnB1WQUKtu3pqT4dHm2Ms99BHdy4tIOIRPQk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799445; c=relaxed/simple; bh=SBTEtiyEiAxysFHy1lrokIISQuJXKcwSNQZjCTO0YD4=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=gtHbg9Kdj8BWjGFhLMxMLGGdefqhPe5ttsLwnYykvKt+BY8XTYIlDMbwbNDJq8Q+spvkQaB9xonWYOwRxzKTwrb6SdZwlGN1aJRYROyjH9i8sHzLmpZtyEQ6U3pufpRJtgT+RSHmFnCun1i6hJdCsNynQ3+SWfw80WHFPEtbcRo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=cM2cxsWN; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="cM2cxsWN" Received: by smtp.kernel.org (Postfix) with ESMTPSA id E3AE7C4CEC3; Sun, 8 Sep 2024 12:44:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1725799445; bh=SBTEtiyEiAxysFHy1lrokIISQuJXKcwSNQZjCTO0YD4=; h=From:To:Cc:Subject:Date:From; b=cM2cxsWNoRdZ/wHMTeQVqrnIS5Xc0vPdEt3ePe52bgRLWu4FfMF/fsM5bwkj4C+7+ 9qNfPofIKKTsWmi9RxXbGcyJxCl+0+QtvQLcnciYx22jdYnA3vot1C98Fhf59oep7a idX/1++Ajto/BWnnH6h27fAd7nEXUewg9zM4D2EZdXSqVUa7ypexJkpqVEuK6pWNaw j0mzmQr4zpi0nH3sNvJzVKUxF4lAxn2UGOJuKkjY2wjLrfiCbH5PGya/TSKUJxNu+V 3YoNkFZDxUOBl5LuhKB1Ti4W4pRIxmVPYEgfdWnosMRoMGBU38OfLjz1f+SnsQb1Te Qzy6zxRjKG5yA== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Masahiro Yamada , Nathan Chancellor , Nicolas Schier Subject: [PATCH 1/6] scripts: move hash function from scripts/kconfig/ to scripts/include/ Date: Sun, 8 Sep 2024 21:43:16 +0900 Message-ID: <20240908124352.1828890-1-masahiroy@kernel.org> X-Mailer: git-send-email 2.43.0 Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 This function was originally added by commit 8af27e1dc4e4 ("fixdep: use hash table instead of a single array"). Move it to scripts/include/ so that other host programs can use it. Signed-off-by: Masahiro Yamada --- scripts/include/hash.h | 15 +++++++++++++++ scripts/kconfig/lkc.h | 1 - scripts/kconfig/symbol.c | 5 +++-- scripts/kconfig/util.c | 13 ++----------- 4 files changed, 20 insertions(+), 14 deletions(-) create mode 100644 scripts/include/hash.h diff --git a/scripts/include/hash.h b/scripts/include/hash.h new file mode 100644 index 000000000000..ce2bc43b308b --- /dev/null +++ b/scripts/include/hash.h @@ -0,0 +1,15 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef HASH_H +#define HASH_H + +static inline unsigned int hash_str(const char *s) +{ + /* fnv32 hash */ + unsigned int hash = 2166136261U; + + for (; *s; s++) + hash = (hash ^ *s) * 0x01000193; + return hash; +} + +#endif /* HASH_H */ diff --git a/scripts/kconfig/lkc.h b/scripts/kconfig/lkc.h index ddfb2b1cb737..b8ebc3094a23 100644 --- a/scripts/kconfig/lkc.h +++ b/scripts/kconfig/lkc.h @@ -51,7 +51,6 @@ static inline void xfwrite(const void *str, size_t len, size_t count, FILE *out) } /* util.c */ -unsigned int strhash(const char *s); const char *file_lookup(const char *name); /* lexer.l */ diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c index 6793f016af5e..6243f0143ecf 100644 --- a/scripts/kconfig/symbol.c +++ b/scripts/kconfig/symbol.c @@ -9,6 +9,7 @@ #include #include +#include #include #include "internal.h" #include "lkc.h" @@ -893,7 +894,7 @@ struct symbol *sym_lookup(const char *name, int flags) case 'n': return &symbol_no; } } - hash = strhash(name); + hash = hash_str(name); hash_for_each_possible(sym_hashtable, symbol, node, hash) { if (symbol->name && @@ -936,7 +937,7 @@ struct symbol *sym_find(const char *name) case 'n': return &symbol_no; } } - hash = strhash(name); + hash = hash_str(name); hash_for_each_possible(sym_hashtable, symbol, node, hash) { if (symbol->name && diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index 50698fff5b9d..5cdcee144b58 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -8,20 +8,11 @@ #include #include +#include #include #include #include "lkc.h" -unsigned int strhash(const char *s) -{ - /* fnv32 hash */ - unsigned int hash = 2166136261U; - - for (; *s; s++) - hash = (hash ^ *s) * 0x01000193; - return hash; -} - /* hash table of all parsed Kconfig files */ static HASHTABLE_DEFINE(file_hashtable, 1U << 11); @@ -35,7 +26,7 @@ const char *file_lookup(const char *name) { struct file *file; size_t len; - int hash = strhash(name); + int hash = hash_str(name); hash_for_each_possible(file_hashtable, file, node, hash) if (!strcmp(name, file->name)) From patchwork Sun Sep 8 12:43:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 13795449 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AA131165F01; Sun, 8 Sep 2024 12:44:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799446; cv=none; b=FxHoskSnqkZZpuQ25u3qyyZ7v8CiF+Sa0M/vjSIUjCFcWjhzw2xmiPw/is5VlfGNFKnYgaoRxmZ0LasYr2tXjq+CiuF77nQQQfpA4PAcBLXdTjkXNBhikqWiaWy5SZ68cCgP3qHIXonQwAnZEEOdCllujSR34pMyyLHmbY7Tiqo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799446; c=relaxed/simple; bh=4LXYQvQc2no5tWKFYWcwrQMNZ+2XmcVjWZzCRnlScNI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=rmMLO10xLRpRwU07lBd70Xdocl/fcnb+OZZk8J1zYzh2WniSRrH2zR65fyTUemclCkoLpI1IZpPHdUmkPYKs2lmpz+lMBSIdUR6cV7PspOc747lpKzwVcWzljwuwAzCQozesvBEX/7D42GWV3v7GWeE5cIXj5G44g7QGAgizA7k= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=fZmO1/BE; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="fZmO1/BE" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 9DA0CC4CEC9; Sun, 8 Sep 2024 12:44:05 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1725799446; bh=4LXYQvQc2no5tWKFYWcwrQMNZ+2XmcVjWZzCRnlScNI=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=fZmO1/BE2qkbCxp7GpGiDIuDYq53jg2qKNuQtGc3UGvrDlQoRQob/RMzaFtEBLVz6 kwpM1MhyHNmS4E+rFEnXJxWAhacLvAZxBLWvEbXSntkhb0kSGF2pNRyj1HhnXbmDz3 muy8tkebKt27E1CGMsK30HkzdYuRz4N5nfAoBl4kR5it+01CfzYCkxcoAfmK7JSrXo WKw6MvTDTHgPviQvsP/nT8uPFuSLR95Nywccq+UeTICST6Tc++smaxcA2OngovqqQI 6depTXoORos66g2uGo8oLUh3Ey5gKTmSQ7PDlj6cyzt90rFEengG+BTqXHCMGmCk1i iE1qbP6DKZEhQ== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Masahiro Yamada Subject: [PATCH 2/6] kconfig: change some expr_*() functions to bool Date: Sun, 8 Sep 2024 21:43:17 +0900 Message-ID: <20240908124352.1828890-2-masahiroy@kernel.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240908124352.1828890-1-masahiroy@kernel.org> References: <20240908124352.1828890-1-masahiroy@kernel.org> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 This clarifies the behavior of these functions. Signed-off-by: Masahiro Yamada --- scripts/kconfig/expr.c | 15 ++++++++------- scripts/kconfig/expr.h | 6 +++--- 2 files changed, 11 insertions(+), 10 deletions(-) diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index a16451347f63..d5dc682f7dc6 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -243,9 +243,10 @@ void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) * equals some operand in the other (operands do not need to appear in the same * order), recursively. */ -int expr_eq(struct expr *e1, struct expr *e2) +bool expr_eq(struct expr *e1, struct expr *e2) { - int res, old_count; + int old_count; + bool res; /* * A NULL expr is taken to be yes, but there's also a different way to @@ -255,7 +256,7 @@ int expr_eq(struct expr *e1, struct expr *e2) return expr_is_yes(e1) && expr_is_yes(e2); if (e1->type != e2->type) - return 0; + return false; switch (e1->type) { case E_EQUAL: case E_GEQ: @@ -292,7 +293,7 @@ int expr_eq(struct expr *e1, struct expr *e2) printf(" ?\n"); } - return 0; + return false; } /* @@ -804,10 +805,10 @@ struct expr *expr_transform(struct expr *e) return e; } -int expr_contains_symbol(struct expr *dep, struct symbol *sym) +bool expr_contains_symbol(struct expr *dep, struct symbol *sym) { if (!dep) - return 0; + return false; switch (dep->type) { case E_AND: @@ -829,7 +830,7 @@ int expr_contains_symbol(struct expr *dep, struct symbol *sym) default: ; } - return 0; + return false; } bool expr_depends_symbol(struct expr *dep, struct symbol *sym) diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h index c82d08bbd704..4ab7422ddbd8 100644 --- a/scripts/kconfig/expr.h +++ b/scripts/kconfig/expr.h @@ -278,11 +278,11 @@ struct expr *expr_alloc_or(struct expr *e1, struct expr *e2); struct expr *expr_copy(const struct expr *org); void expr_free(struct expr *e); void expr_eliminate_eq(struct expr **ep1, struct expr **ep2); -int expr_eq(struct expr *e1, struct expr *e2); +bool expr_eq(struct expr *e1, struct expr *e2); tristate expr_calc_value(struct expr *e); struct expr *expr_eliminate_dups(struct expr *e); struct expr *expr_transform(struct expr *e); -int expr_contains_symbol(struct expr *dep, struct symbol *sym); +bool expr_contains_symbol(struct expr *dep, struct symbol *sym); bool expr_depends_symbol(struct expr *dep, struct symbol *sym); struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym); @@ -292,7 +292,7 @@ void expr_gstr_print(const struct expr *e, struct gstr *gs); void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, tristate pr_type, const char *title); -static inline int expr_is_yes(const struct expr *e) +static inline bool expr_is_yes(const struct expr *e) { return !e || (e->type == E_SYMBOL && e->left.sym == &symbol_yes); } From patchwork Sun Sep 8 12:43:18 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 13795450 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1AE45166F03; Sun, 8 Sep 2024 12:44:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799448; cv=none; b=mYKejnxtfRoVWfYSw1KRDKTZ9B+6f0o+YWybNiQhaSRD/VUgPzSnroW9AdiQ2wSTMCYKze87N4lOjDaAgFoUKWNTykpILP+IEJXKMcne8VK9fwQqD9pC7zoFiE6XM8efXd6r8C6DoqX2KPdqokO0bdD/RhzyLRQJ0PIZ1jI2Xsk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799448; c=relaxed/simple; bh=jD1e4pYggDtDYf4yNsrFOPNi5Q/cX6VUdhkhhALj95Q=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=pDy9emuOPiMkov/mLp+NBzngZMdcMR4XnAukm+6sv/qVtcRNbtCOR1EVEL92cZydLKR43JwquKeyRPV5lJtfAPHnjQg4P8syoyjg/6pSgvvp6xzg15IU2nOE0kpYsR+7LRDgkXAK4tojSvH5dKNfXu/PZLSQrsdzq5KK0XE9jqs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=gks++DrI; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="gks++DrI" Received: by smtp.kernel.org (Postfix) with ESMTPSA id D4D47C4CEC8; Sun, 8 Sep 2024 12:44:06 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1725799447; bh=jD1e4pYggDtDYf4yNsrFOPNi5Q/cX6VUdhkhhALj95Q=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=gks++DrIKsZym/cRPSoMJnmI7qL44n2Z6TnNAUSAhSQBvmTvRGrZCVuWKWLjlewWZ J3L1+SLQ3rTuLUB8SYhKGVKOblZmM3zlPe7+4wtKVj6sLdLRfRaXLKrdGUc3BgLv0X aOpzc1qrDsSqXQSht3H+1RLs72+FePk8SgAIdwCOerFR4QUQEIvia3YphUkeZOxLeW 6fomkjpJAUeq6zMf9rENpQ/aJW9MmXQnWKIsPcz4hk7x0iqvmRc9kiOzLeQrUIpJ/E 2+5Tj5goznG8S2WWV3LO/LH0dWnAQ9ulsvgtES5M7YqDkCwNr/0HcCuM9bdcDOyjui 5N6Y8jRlRe6qQ== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Masahiro Yamada Subject: [PATCH 3/6] kconfig: add comments to expression transformations Date: Sun, 8 Sep 2024 21:43:18 +0900 Message-ID: <20240908124352.1828890-3-masahiroy@kernel.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240908124352.1828890-1-masahiroy@kernel.org> References: <20240908124352.1828890-1-masahiroy@kernel.org> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Provide explanations for complex transformations. Signed-off-by: Masahiro Yamada --- scripts/kconfig/expr.c | 43 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 37 insertions(+), 6 deletions(-) diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index d5dc682f7dc6..e83fe0c3d62f 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -442,6 +442,7 @@ static struct expr *expr_join_or(struct expr *e1, struct expr *e2) } } if (sym1->type == S_BOOLEAN) { + // a || !a -> y if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) return expr_alloc_symbol(&symbol_yes); @@ -647,6 +648,30 @@ struct expr *expr_eliminate_dups(struct expr *e) * Performs various simplifications involving logical operators and * comparisons. * + * For bool type: + * A=n -> !A + * A=m -> n + * A=y -> A + * A!=n -> A + * A!=m -> y + * A!=y -> !A + * + * For any type: + * !!A -> A + * !(A=B) -> A!=B + * !(A!=B) -> A=B + * !(A<=B) -> A>B + * !(A>=B) -> A A>=B + * !(A>B) -> A<=B + * !(A || B) -> !A && !B + * !(A && B) -> !A || !B + * + * For constant: + * !y -> n + * !m -> m + * !n -> y + * * Allocates and returns a new expression. */ struct expr *expr_transform(struct expr *e) @@ -674,12 +699,14 @@ struct expr *expr_transform(struct expr *e) if (e->left.sym->type != S_BOOLEAN) break; if (e->right.sym == &symbol_no) { + // A=n -> !A e->type = E_NOT; e->left.expr = expr_alloc_symbol(e->left.sym); e->right.sym = NULL; break; } if (e->right.sym == &symbol_mod) { + // A=m -> n printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); e->type = E_SYMBOL; e->left.sym = &symbol_no; @@ -687,6 +714,7 @@ struct expr *expr_transform(struct expr *e) break; } if (e->right.sym == &symbol_yes) { + // A=y -> A e->type = E_SYMBOL; e->right.sym = NULL; break; @@ -696,11 +724,13 @@ struct expr *expr_transform(struct expr *e) if (e->left.sym->type != S_BOOLEAN) break; if (e->right.sym == &symbol_no) { + // A!=n -> A e->type = E_SYMBOL; e->right.sym = NULL; break; } if (e->right.sym == &symbol_mod) { + // A!=m -> y printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); e->type = E_SYMBOL; e->left.sym = &symbol_yes; @@ -708,6 +738,7 @@ struct expr *expr_transform(struct expr *e) break; } if (e->right.sym == &symbol_yes) { + // A!=y -> !A e->type = E_NOT; e->left.expr = expr_alloc_symbol(e->left.sym); e->right.sym = NULL; @@ -717,7 +748,7 @@ struct expr *expr_transform(struct expr *e) case E_NOT: switch (e->left.expr->type) { case E_NOT: - // !!a -> a + // !!A -> A tmp = e->left.expr->left.expr; free(e->left.expr); free(e); @@ -726,7 +757,7 @@ struct expr *expr_transform(struct expr *e) break; case E_EQUAL: case E_UNEQUAL: - // !a='x' -> a!='x' + // !(A=B) -> A!=B tmp = e->left.expr; free(e); e = tmp; @@ -734,7 +765,7 @@ struct expr *expr_transform(struct expr *e) break; case E_LEQ: case E_GEQ: - // !a<='x' -> a>'x' + // !(A<=B) -> A>B tmp = e->left.expr; free(e); e = tmp; @@ -742,14 +773,14 @@ struct expr *expr_transform(struct expr *e) break; case E_LTH: case E_GTH: - // !a<'x' -> a>='x' + // !(A A>=B tmp = e->left.expr; free(e); e = tmp; e->type = e->type == E_LTH ? E_GEQ : E_LEQ; break; case E_OR: - // !(a || b) -> !a && !b + // !(A || B) -> !A && !B tmp = e->left.expr; e->type = E_AND; e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); @@ -758,7 +789,7 @@ struct expr *expr_transform(struct expr *e) e = expr_transform(e); break; case E_AND: - // !(a && b) -> !a || !b + // !(A && B) -> !A || !B tmp = e->left.expr; e->type = E_OR; e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); From patchwork Sun Sep 8 12:43:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 13795451 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 151D0158207; Sun, 8 Sep 2024 12:44:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799449; cv=none; b=ke6VhdKa/MWe+kBlRC4VQiUlpGsroskupoCTex2lHi8dpSWG8PmkuLYkGS5GNTcQH5DI/mIfpZbXuOwjaMDu5MvOwlldpWR8VlQ/JNkJ9T/KDOFOPU9Euw5m+ApuRC2dUvgFyF+0ZGfyqTms/9Rr+2Lj9w5/w+PYE4KFdCg0No0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799449; c=relaxed/simple; bh=kv+vHc8mbpg5KVF2uw90wNMXJvKCsvKQlGuPl3Mon4I=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Ise//PX4pgPpal3ZLCqr2+hqg2N4sj1ZBS1MIVszIZtg1zVChfiv0BYXIowPKKM3CglXVfds9u+C8GyN6uosV+d+l6WBDf3Q7wtMC3ZZdLSFgtSi7QMMkRyAoVVWvsQOhHB/y7JabI4TdafT2y8MvnyqrqmpMubek6Wpqaxz1hQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=fgGJ61pR; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="fgGJ61pR" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 18E10C4CEC9; Sun, 8 Sep 2024 12:44:07 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1725799448; bh=kv+vHc8mbpg5KVF2uw90wNMXJvKCsvKQlGuPl3Mon4I=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=fgGJ61pRJmS6lIcw3O0kM95yQDttE/WnfX6SXr+Yp4WM4UlCjKgQ/c4nj3qolGF80 LoypfmzV+zFSRCB0vJkZqfNjASuW0yMwovFJetwlbsDMjzvMLFK4g/rEyXb0Y/3xTG 647WK+j21Kvp/UQAsPQ87lk7BKcdm4nwtNmJgFTL6hnh08uj0r8ANaOkZYoGWL4Eks vocFWuQq9ho9c8/48J7Nxl48ejqPvGYV0NeZPyxUA9xmOSUpwB+iFZQP4KgkTlsfgn kCBzNcZO5SEme8nmazP4qM8pr4wBdrIcKm7BMeyHrRQne4ULizys7xtWxUvYV/n5Lq CRUaNLLy+RWFw== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Masahiro Yamada Subject: [PATCH 4/6] kconfig: refactor expr_eliminate_dups() Date: Sun, 8 Sep 2024 21:43:19 +0900 Message-ID: <20240908124352.1828890-4-masahiroy@kernel.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240908124352.1828890-1-masahiroy@kernel.org> References: <20240908124352.1828890-1-masahiroy@kernel.org> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Currently, expr_eliminate_dups() passes two identical pointers down to expr_eliminate_dups1(), which later skips processing identical leaves. This approach is somewhat tricky and, more importantly, it will not work with the refactoring made in the next commit. This commit slightly changes the recursion logic; it deduplicates both the left and right arms, and then passes them to expr_eliminate_dups1(). expr_eliminate_dups() should produce the same result. Signed-off-by: Masahiro Yamada --- scripts/kconfig/expr.c | 14 +++----------- 1 file changed, 3 insertions(+), 11 deletions(-) diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index e83fe0c3d62f..5b826d197f12 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -578,16 +578,6 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct /* *ep1 and *ep2 are leaves. Compare and process them. */ - if (*ep1 == *ep2) - return; - - switch ((*ep1)->type) { - case E_OR: case E_AND: - expr_eliminate_dups1((*ep1)->type, ep1, ep1); - default: - ; - } - switch (type) { case E_OR: tmp = expr_join_or(*ep1, *ep2); @@ -634,7 +624,9 @@ struct expr *expr_eliminate_dups(struct expr *e) trans_count = 0; switch (e->type) { case E_OR: case E_AND: - expr_eliminate_dups1(e->type, &e, &e); + e->left.expr = expr_eliminate_dups(e->left.expr); + e->right.expr = expr_eliminate_dups(e->right.expr); + expr_eliminate_dups1(e->type, &e->left.expr, &e->right.expr); default: ; } From patchwork Sun Sep 8 12:43:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 13795452 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 24A63167DB8; Sun, 8 Sep 2024 12:44:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799451; cv=none; b=H9HrJWU+5h0J5stZolSeSJo5/2RFSIGNDjviWMXgEABBGMHUVy8+8iLhkh2PSirc1+vJ9g/U6MEC12oD4QJ/xANtCxfKgivZ3vCSw5twJxZFuZtu81igfnnUsjEkny4g7gxFpjEeeUaTJhUO7cDvWvkNTxThkE9TjARXaqJ9zTU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799451; c=relaxed/simple; bh=eaDlb4JznD8YbuRoVtwHakqm/r/IqQrTYjV9cMcZ8sE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=dVedDcnXdh60MtE8mMKnDXGk9I/9PGxwR4dupcZ+z5l5Q+J27G/+iitGkOKGTG7XVRVwSbtgKoIjHHlsu984dtEgqVOPCP0OuN6lZWVPqtBmiqp2l8cHLWT9UWVYnlvCdSNh2td0LxvseK/TyEbqFyqiefGB+cyDczYO0aPpcN0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=g4XqvHTN; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="g4XqvHTN" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 730D1C4CEC9; Sun, 8 Sep 2024 12:44:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1725799450; bh=eaDlb4JznD8YbuRoVtwHakqm/r/IqQrTYjV9cMcZ8sE=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=g4XqvHTNzyQQEAGowR3ccYXasmdSvXFb2P27l/v59pCDTeHHYl2hhC9jSlh2XVTfw coYdBMWw2a5pknFYyncwMXA5IuyPUSAy43gwn0sHt6oJt4Fswg8XScGI+pB3q367MA V2eqp1TmU1lotPLedHpCrMFO6g+md4tmoeoMCA81zjJuyXPRukKTMKEUeWNNTIl5f+ 84ObEyadsj/9/fol7oIXQGmPWexFnkSN/4jp+K68cbvKxvU2T6LLrHLKmGafkQbnD3 CCZ3dVTJnt05wISRTBod9gsS8FLg0QQ1KT915T04iUCD/65VGbf/CQGTsmQ/mynPjU zEly+Z0pVtztA== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Masahiro Yamada , Nathan Chancellor , Nicolas Schier Subject: [PATCH 5/6] kconfig: use hash table to reuse expressions Date: Sun, 8 Sep 2024 21:43:20 +0900 Message-ID: <20240908124352.1828890-5-masahiroy@kernel.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240908124352.1828890-1-masahiroy@kernel.org> References: <20240908124352.1828890-1-masahiroy@kernel.org> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Currently, every expression in Kconfig files produces a new abstract syntax tree (AST), even if it is identical to a previously encountered one. Consider the following code: config FOO bool "FOO" depends on (A || B) && C config BAR bool "BAR" depends on (A || B) && C config BAZ bool "BAZ" depends on A || B The "depends on" lines are similar, but currently a separate AST is allocated for each one. The current data structure looks like this: FOO->dep ==> AND BAR->dep ==> AND BAZ->dep ==> OR / \ / \ / \ OR C OR C A B / \ / \ A B A B This is redundant; FOO->dep and BAR->dep have identical ASTs but different memory instances. We can optimize this; FOO->dep and BAR->dep can share the same AST, and BAZ->dep can reference its sub tree. The optimized data structure looks like this: FOO->dep, BAR->dep ==> AND / \ BAZ->dep ==> OR C / \ A B This commit introduces a hash table to keep track of allocated expressions. If an identical expression is found, it is reused. This does not necessarily result in memory savings, as menu_finalize() transforms expressions without freeing up stale ones. One further optimization that can be easily implemented is caching the expression's value. Once FOO's dependency, (A || B) && C, is calculated, it can be cached, eliminating the need to recalculate it for BAR. This commit also reverts commit e983b7b17ad1 ("kconfig/menu.c: fix multiple references to expressions in menu_add_prop()"). Signed-off-by: Masahiro Yamada --- scripts/include/hash.h | 13 ++ scripts/kconfig/expr.c | 381 +++++++++++++------------------------ scripts/kconfig/expr.h | 16 +- scripts/kconfig/internal.h | 4 + scripts/kconfig/menu.c | 33 +--- 5 files changed, 170 insertions(+), 277 deletions(-) diff --git a/scripts/include/hash.h b/scripts/include/hash.h index ce2bc43b308b..efa904368a62 100644 --- a/scripts/include/hash.h +++ b/scripts/include/hash.h @@ -12,4 +12,17 @@ static inline unsigned int hash_str(const char *s) return hash; } +/* simplified version of functions from include/linux/hash.h */ +#define GOLDEN_RATIO_32 0x61C88647 + +static inline unsigned int hash_32(unsigned int val) +{ + return 0x61C88647 * val; +} + +static inline unsigned int hash_ptr(const void *ptr) +{ + return hash_32((unsigned int)(unsigned long)ptr); +} + #endif /* HASH_H */ diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index 5b826d197f12..b7cfaf1a22e6 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -9,45 +9,68 @@ #include #include +#include #include +#include "internal.h" #include "lkc.h" #define DEBUG_EXPR 0 +HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE); + static struct expr *expr_eliminate_yn(struct expr *e); +/** + * expr_lookup - return the expression for the given type and sub-nodes + * This looks up an expression with the specified type and sub-nodes. If such + * an expression is found in the hash table, it is returned. Otherwise, a new + * expression node is allocated and added to the hash table. + * @type: expression type + * @l: left node + * @r: right node + * return: expression + */ +static struct expr *expr_lookup(enum expr_type type, void *l, void *r) +{ + struct expr *e; + int hash; + + hash = hash_32((unsigned int)type ^ hash_ptr(l) ^ hash_ptr(r)); + + hash_for_each_possible(expr_hashtable, e, node, hash) { + if (e->type == type && e->left._initdata == l && + e->right._initdata == r) + return e; + } + + e = xmalloc(sizeof(*e)); + e->type = type; + e->left._initdata = l; + e->right._initdata = r; + + hash_add(expr_hashtable, &e->node, hash); + + return e; +} + struct expr *expr_alloc_symbol(struct symbol *sym) { - struct expr *e = xcalloc(1, sizeof(*e)); - e->type = E_SYMBOL; - e->left.sym = sym; - return e; + return expr_lookup(E_SYMBOL, sym, NULL); } struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) { - struct expr *e = xcalloc(1, sizeof(*e)); - e->type = type; - e->left.expr = ce; - return e; + return expr_lookup(type, ce, NULL); } struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) { - struct expr *e = xcalloc(1, sizeof(*e)); - e->type = type; - e->left.expr = e1; - e->right.expr = e2; - return e; + return expr_lookup(type, e1, e2); } struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) { - struct expr *e = xcalloc(1, sizeof(*e)); - e->type = type; - e->left.sym = s1; - e->right.sym = s2; - return e; + return expr_lookup(type, s1, s2); } struct expr *expr_alloc_and(struct expr *e1, struct expr *e2) @@ -64,76 +87,6 @@ struct expr *expr_alloc_or(struct expr *e1, struct expr *e2) return e2 ? expr_alloc_two(E_OR, e1, e2) : e1; } -struct expr *expr_copy(const struct expr *org) -{ - struct expr *e; - - if (!org) - return NULL; - - e = xmalloc(sizeof(*org)); - memcpy(e, org, sizeof(*org)); - switch (org->type) { - case E_SYMBOL: - e->left = org->left; - break; - case E_NOT: - e->left.expr = expr_copy(org->left.expr); - break; - case E_EQUAL: - case E_GEQ: - case E_GTH: - case E_LEQ: - case E_LTH: - case E_UNEQUAL: - e->left.sym = org->left.sym; - e->right.sym = org->right.sym; - break; - case E_AND: - case E_OR: - e->left.expr = expr_copy(org->left.expr); - e->right.expr = expr_copy(org->right.expr); - break; - default: - fprintf(stderr, "can't copy type %d\n", e->type); - free(e); - e = NULL; - break; - } - - return e; -} - -void expr_free(struct expr *e) -{ - if (!e) - return; - - switch (e->type) { - case E_SYMBOL: - break; - case E_NOT: - expr_free(e->left.expr); - break; - case E_EQUAL: - case E_GEQ: - case E_GTH: - case E_LEQ: - case E_LTH: - case E_UNEQUAL: - break; - case E_OR: - case E_AND: - expr_free(e->left.expr); - expr_free(e->right.expr); - break; - default: - fprintf(stderr, "how to free type %d?\n", e->type); - break; - } - free(e); -} - static int trans_count; /* @@ -146,16 +99,24 @@ static int trans_count; */ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) { + struct expr *l, *r; + /* Recurse down to leaves */ if ((*ep1)->type == type) { - __expr_eliminate_eq(type, &(*ep1)->left.expr, ep2); - __expr_eliminate_eq(type, &(*ep1)->right.expr, ep2); + l = (*ep1)->left.expr; + r = (*ep1)->right.expr; + __expr_eliminate_eq(type, &l, ep2); + __expr_eliminate_eq(type, &r, ep2); + *ep1 = expr_alloc_two(type, l, r); return; } if ((*ep2)->type == type) { - __expr_eliminate_eq(type, ep1, &(*ep2)->left.expr); - __expr_eliminate_eq(type, ep1, &(*ep2)->right.expr); + l = (*ep2)->left.expr; + r = (*ep2)->right.expr; + __expr_eliminate_eq(type, ep1, &l); + __expr_eliminate_eq(type, ep1, &r); + *ep2 = expr_alloc_two(type, l, r); return; } @@ -171,7 +132,6 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e /* *ep1 and *ep2 are equal leaves. Prepare them for elimination. */ trans_count++; - expr_free(*ep1); expr_free(*ep2); switch (type) { case E_OR: *ep1 = expr_alloc_symbol(&symbol_no); @@ -271,14 +231,10 @@ bool expr_eq(struct expr *e1, struct expr *e2) return expr_eq(e1->left.expr, e2->left.expr); case E_AND: case E_OR: - e1 = expr_copy(e1); - e2 = expr_copy(e2); old_count = trans_count; expr_eliminate_eq(&e1, &e2); res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && e1->left.sym == e2->left.sym); - expr_free(e1); - expr_free(e2); trans_count = old_count; return res; case E_RANGE: @@ -297,7 +253,7 @@ bool expr_eq(struct expr *e1, struct expr *e2) } /* - * Recursively performs the following simplifications in-place (as well as the + * Recursively performs the following simplifications (as well as the * corresponding simplifications with swapped operands): * * expr && n -> n @@ -309,79 +265,39 @@ bool expr_eq(struct expr *e1, struct expr *e2) */ static struct expr *expr_eliminate_yn(struct expr *e) { - struct expr *tmp; + struct expr *l, *r; if (e) switch (e->type) { case E_AND: - e->left.expr = expr_eliminate_yn(e->left.expr); - e->right.expr = expr_eliminate_yn(e->right.expr); - if (e->left.expr->type == E_SYMBOL) { - if (e->left.expr->left.sym == &symbol_no) { - expr_free(e->left.expr); - expr_free(e->right.expr); - e->type = E_SYMBOL; - e->left.sym = &symbol_no; - e->right.expr = NULL; - return e; - } else if (e->left.expr->left.sym == &symbol_yes) { - free(e->left.expr); - tmp = e->right.expr; - *e = *(e->right.expr); - free(tmp); - return e; - } + l = expr_eliminate_yn(e->left.expr); + r = expr_eliminate_yn(e->right.expr); + if (l->type == E_SYMBOL) { + if (l->left.sym == &symbol_no) + return l; + else if (l->left.sym == &symbol_yes) + return r; } - if (e->right.expr->type == E_SYMBOL) { - if (e->right.expr->left.sym == &symbol_no) { - expr_free(e->left.expr); - expr_free(e->right.expr); - e->type = E_SYMBOL; - e->left.sym = &symbol_no; - e->right.expr = NULL; - return e; - } else if (e->right.expr->left.sym == &symbol_yes) { - free(e->right.expr); - tmp = e->left.expr; - *e = *(e->left.expr); - free(tmp); - return e; - } + if (r->type == E_SYMBOL) { + if (r->left.sym == &symbol_no) + return r; + else if (r->left.sym == &symbol_yes) + return l; } break; case E_OR: - e->left.expr = expr_eliminate_yn(e->left.expr); - e->right.expr = expr_eliminate_yn(e->right.expr); - if (e->left.expr->type == E_SYMBOL) { - if (e->left.expr->left.sym == &symbol_no) { - free(e->left.expr); - tmp = e->right.expr; - *e = *(e->right.expr); - free(tmp); - return e; - } else if (e->left.expr->left.sym == &symbol_yes) { - expr_free(e->left.expr); - expr_free(e->right.expr); - e->type = E_SYMBOL; - e->left.sym = &symbol_yes; - e->right.expr = NULL; - return e; - } + l = expr_eliminate_yn(e->left.expr); + r = expr_eliminate_yn(e->right.expr); + if (l->type == E_SYMBOL) { + if (l->left.sym == &symbol_no) + return r; + else if (l->left.sym == &symbol_yes) + return l; } - if (e->right.expr->type == E_SYMBOL) { - if (e->right.expr->left.sym == &symbol_no) { - free(e->right.expr); - tmp = e->left.expr; - *e = *(e->left.expr); - free(tmp); - return e; - } else if (e->right.expr->left.sym == &symbol_yes) { - expr_free(e->left.expr); - expr_free(e->right.expr); - e->type = E_SYMBOL; - e->left.sym = &symbol_yes; - e->right.expr = NULL; - return e; - } + if (r->type == E_SYMBOL) { + if (r->left.sym == &symbol_no) + return l; + else if (r->left.sym == &symbol_yes) + return r; } break; default: @@ -399,7 +315,7 @@ static struct expr *expr_join_or(struct expr *e1, struct expr *e2) struct symbol *sym1, *sym2; if (expr_eq(e1, e2)) - return expr_copy(e1); + return e1; if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) return NULL; if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) @@ -464,7 +380,7 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2) struct symbol *sym1, *sym2; if (expr_eq(e1, e2)) - return expr_copy(e1); + return e1; if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) return NULL; if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) @@ -561,18 +477,24 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2) */ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) { - struct expr *tmp; + struct expr *tmp, *l, *r; /* Recurse down to leaves */ if ((*ep1)->type == type) { - expr_eliminate_dups1(type, &(*ep1)->left.expr, ep2); - expr_eliminate_dups1(type, &(*ep1)->right.expr, ep2); + l = (*ep1)->left.expr; + r = (*ep1)->right.expr; + expr_eliminate_dups1(type, &l, ep2); + expr_eliminate_dups1(type, &r, ep2); + *ep1 = expr_alloc_two(type, l, r); return; } if ((*ep2)->type == type) { - expr_eliminate_dups1(type, ep1, &(*ep2)->left.expr); - expr_eliminate_dups1(type, ep1, &(*ep2)->right.expr); + l = (*ep2)->left.expr; + r = (*ep2)->right.expr; + expr_eliminate_dups1(type, ep1, &l); + expr_eliminate_dups1(type, ep1, &r); + *ep2 = expr_alloc_two(type, l, r); return; } @@ -582,7 +504,6 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct case E_OR: tmp = expr_join_or(*ep1, *ep2); if (tmp) { - expr_free(*ep1); expr_free(*ep2); *ep1 = expr_alloc_symbol(&symbol_no); *ep2 = tmp; trans_count++; @@ -591,7 +512,6 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct case E_AND: tmp = expr_join_and(*ep1, *ep2); if (tmp) { - expr_free(*ep1); expr_free(*ep2); *ep1 = expr_alloc_symbol(&symbol_yes); *ep2 = tmp; trans_count++; @@ -621,12 +541,15 @@ struct expr *expr_eliminate_dups(struct expr *e) oldcount = trans_count; do { + struct expr *l, *r; + trans_count = 0; switch (e->type) { case E_OR: case E_AND: - e->left.expr = expr_eliminate_dups(e->left.expr); - e->right.expr = expr_eliminate_dups(e->right.expr); - expr_eliminate_dups1(e->type, &e->left.expr, &e->right.expr); + l = expr_eliminate_dups(e->left.expr); + r = expr_eliminate_dups(e->right.expr); + expr_eliminate_dups1(e->type, &l, &r); + e = expr_alloc_two(e->type, l, r); default: ; } @@ -668,8 +591,6 @@ struct expr *expr_eliminate_dups(struct expr *e) */ struct expr *expr_transform(struct expr *e) { - struct expr *tmp; - if (!e) return NULL; switch (e->type) { @@ -682,8 +603,9 @@ struct expr *expr_transform(struct expr *e) case E_SYMBOL: break; default: - e->left.expr = expr_transform(e->left.expr); - e->right.expr = expr_transform(e->right.expr); + e = expr_alloc_two(e->type, + expr_transform(e->left.expr), + expr_transform(e->right.expr)); } switch (e->type) { @@ -692,23 +614,18 @@ struct expr *expr_transform(struct expr *e) break; if (e->right.sym == &symbol_no) { // A=n -> !A - e->type = E_NOT; - e->left.expr = expr_alloc_symbol(e->left.sym); - e->right.sym = NULL; + e = expr_alloc_one(E_NOT, expr_alloc_symbol(e->left.sym)); break; } if (e->right.sym == &symbol_mod) { // A=m -> n printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); - e->type = E_SYMBOL; - e->left.sym = &symbol_no; - e->right.sym = NULL; + e = expr_alloc_symbol(&symbol_no); break; } if (e->right.sym == &symbol_yes) { // A=y -> A - e->type = E_SYMBOL; - e->right.sym = NULL; + e = expr_alloc_symbol(e->left.sym); break; } break; @@ -717,23 +634,18 @@ struct expr *expr_transform(struct expr *e) break; if (e->right.sym == &symbol_no) { // A!=n -> A - e->type = E_SYMBOL; - e->right.sym = NULL; + e = expr_alloc_symbol(e->left.sym); break; } if (e->right.sym == &symbol_mod) { // A!=m -> y printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); - e->type = E_SYMBOL; - e->left.sym = &symbol_yes; - e->right.sym = NULL; + e = expr_alloc_symbol(&symbol_yes); break; } if (e->right.sym == &symbol_yes) { // A!=y -> !A - e->type = E_NOT; - e->left.expr = expr_alloc_symbol(e->left.sym); - e->right.sym = NULL; + e = expr_alloc_one(E_NOT, e->left.expr); break; } break; @@ -741,82 +653,51 @@ struct expr *expr_transform(struct expr *e) switch (e->left.expr->type) { case E_NOT: // !!A -> A - tmp = e->left.expr->left.expr; - free(e->left.expr); - free(e); - e = tmp; - e = expr_transform(e); + e = e->left.expr->left.expr; break; case E_EQUAL: case E_UNEQUAL: // !(A=B) -> A!=B - tmp = e->left.expr; - free(e); - e = tmp; - e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; + e = expr_alloc_comp(e->left.expr->type == E_EQUAL ? E_UNEQUAL : E_EQUAL, + e->left.expr->left.sym, + e->left.expr->right.sym); break; case E_LEQ: case E_GEQ: // !(A<=B) -> A>B - tmp = e->left.expr; - free(e); - e = tmp; - e->type = e->type == E_LEQ ? E_GTH : E_LTH; + e = expr_alloc_comp(e->left.expr->type == E_LEQ ? E_GTH : E_LTH, + e->left.expr->left.sym, + e->left.expr->right.sym); break; case E_LTH: case E_GTH: // !(A A>=B - tmp = e->left.expr; - free(e); - e = tmp; - e->type = e->type == E_LTH ? E_GEQ : E_LEQ; + e = expr_alloc_comp(e->left.expr->type == E_LTH ? E_GEQ : E_LEQ, + e->left.expr->left.sym, + e->left.expr->right.sym); break; case E_OR: // !(A || B) -> !A && !B - tmp = e->left.expr; - e->type = E_AND; - e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); - tmp->type = E_NOT; - tmp->right.expr = NULL; + e = expr_alloc_and(expr_alloc_one(E_NOT, e->left.expr->left.expr), + expr_alloc_one(E_NOT, e->left.expr->right.expr)); e = expr_transform(e); break; case E_AND: // !(A && B) -> !A || !B - tmp = e->left.expr; - e->type = E_OR; - e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); - tmp->type = E_NOT; - tmp->right.expr = NULL; + e = expr_alloc_or(expr_alloc_one(E_NOT, e->left.expr->left.expr), + expr_alloc_one(E_NOT, e->left.expr->right.expr)); e = expr_transform(e); break; case E_SYMBOL: - if (e->left.expr->left.sym == &symbol_yes) { + if (e->left.expr->left.sym == &symbol_yes) // !'y' -> 'n' - tmp = e->left.expr; - free(e); - e = tmp; - e->type = E_SYMBOL; - e->left.sym = &symbol_no; - break; - } - if (e->left.expr->left.sym == &symbol_mod) { + e = expr_alloc_symbol(&symbol_no); + else if (e->left.expr->left.sym == &symbol_mod) // !'m' -> 'm' - tmp = e->left.expr; - free(e); - e = tmp; - e->type = E_SYMBOL; - e->left.sym = &symbol_mod; - break; - } - if (e->left.expr->left.sym == &symbol_no) { + e = expr_alloc_symbol(&symbol_mod); + else if (e->left.expr->left.sym == &symbol_no) // !'n' -> 'y' - tmp = e->left.expr; - free(e); - e = tmp; - e->type = E_SYMBOL; - e->left.sym = &symbol_yes; - break; - } + e = expr_alloc_symbol(&symbol_yes); break; default: ; @@ -940,18 +821,18 @@ struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symb case E_EQUAL: if (type == E_EQUAL) { if (sym == &symbol_yes) - return expr_copy(e); + return e; if (sym == &symbol_mod) return expr_alloc_symbol(&symbol_no); if (sym == &symbol_no) - return expr_alloc_one(E_NOT, expr_copy(e)); + return expr_alloc_one(E_NOT, e); } else { if (sym == &symbol_yes) - return expr_alloc_one(E_NOT, expr_copy(e)); + return expr_alloc_one(E_NOT, e); if (sym == &symbol_mod) return expr_alloc_symbol(&symbol_yes); if (sym == &symbol_no) - return expr_copy(e); + return e; } break; case E_SYMBOL: diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h index 4ab7422ddbd8..a398b2b2dbe0 100644 --- a/scripts/kconfig/expr.h +++ b/scripts/kconfig/expr.h @@ -29,11 +29,21 @@ enum expr_type { }; union expr_data { - struct expr *expr; - struct symbol *sym; + struct expr * const expr; + struct symbol * const sym; + void *_initdata; }; +/** + * struct expr - expression + * + * @node: link node for the hash table + * @type: expressoin type + * @left: left node + * @right: right node + */ struct expr { + struct hlist_node node; enum expr_type type; union expr_data left, right; }; @@ -275,8 +285,6 @@ struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2); struct expr *expr_alloc_and(struct expr *e1, struct expr *e2); struct expr *expr_alloc_or(struct expr *e1, struct expr *e2); -struct expr *expr_copy(const struct expr *org); -void expr_free(struct expr *e); void expr_eliminate_eq(struct expr **ep1, struct expr **ep2); bool expr_eq(struct expr *e1, struct expr *e2); tristate expr_calc_value(struct expr *e); diff --git a/scripts/kconfig/internal.h b/scripts/kconfig/internal.h index 02106eb7815e..84c2ea0389fd 100644 --- a/scripts/kconfig/internal.h +++ b/scripts/kconfig/internal.h @@ -11,6 +11,10 @@ extern HASHTABLE_DECLARE(sym_hashtable, SYMBOL_HASHSIZE); #define for_all_symbols(sym) \ hash_for_each(sym_hashtable, sym, node) +#define EXPR_HASHSIZE (1U << 14) + +extern HASHTABLE_DECLARE(expr_hashtable, EXPR_HASHSIZE); + struct menu; extern struct menu *current_menu, *current_entry; diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c index f61327fabead..4addd33749bb 100644 --- a/scripts/kconfig/menu.c +++ b/scripts/kconfig/menu.c @@ -107,12 +107,13 @@ static struct expr *rewrite_m(struct expr *e) switch (e->type) { case E_NOT: - e->left.expr = rewrite_m(e->left.expr); + e = expr_alloc_one(E_NOT, rewrite_m(e->left.expr)); break; case E_OR: case E_AND: - e->left.expr = rewrite_m(e->left.expr); - e->right.expr = rewrite_m(e->right.expr); + e = expr_alloc_two(e->type, + rewrite_m(e->left.expr), + rewrite_m(e->right.expr)); break; case E_SYMBOL: /* change 'm' into 'm' && MODULES */ @@ -192,21 +193,11 @@ struct property *menu_add_prompt(enum prop_type type, const char *prompt, struct menu *menu = current_entry; while ((menu = menu->parent) != NULL) { - struct expr *dup_expr; if (!menu->visibility) continue; - /* - * Do not add a reference to the menu's visibility - * expression but use a copy of it. Otherwise the - * expression reduction functions will modify - * expressions that have multiple references which - * can cause unwanted side effects. - */ - dup_expr = expr_copy(menu->visibility); - prop->visible.expr = expr_alloc_and(prop->visible.expr, - dup_expr); + menu->visibility); } } @@ -322,7 +313,7 @@ static void _menu_finalize(struct menu *parent, bool inside_choice) */ basedep = rewrite_m(menu->dep); basedep = expr_transform(basedep); - basedep = expr_alloc_and(expr_copy(parent->dep), basedep); + basedep = expr_alloc_and(parent->dep, basedep); basedep = expr_eliminate_dups(basedep); menu->dep = basedep; @@ -366,7 +357,7 @@ static void _menu_finalize(struct menu *parent, bool inside_choice) */ dep = rewrite_m(prop->visible.expr); dep = expr_transform(dep); - dep = expr_alloc_and(expr_copy(basedep), dep); + dep = expr_alloc_and(basedep, dep); dep = expr_eliminate_dups(dep); prop->visible.expr = dep; @@ -377,11 +368,11 @@ static void _menu_finalize(struct menu *parent, bool inside_choice) if (prop->type == P_SELECT) { struct symbol *es = prop_get_symbol(prop); es->rev_dep.expr = expr_alloc_or(es->rev_dep.expr, - expr_alloc_and(expr_alloc_symbol(menu->sym), expr_copy(dep))); + expr_alloc_and(expr_alloc_symbol(menu->sym), dep)); } else if (prop->type == P_IMPLY) { struct symbol *es = prop_get_symbol(prop); es->implied.expr = expr_alloc_or(es->implied.expr, - expr_alloc_and(expr_alloc_symbol(menu->sym), expr_copy(dep))); + expr_alloc_and(expr_alloc_symbol(menu->sym), dep)); } } } @@ -441,22 +432,18 @@ static void _menu_finalize(struct menu *parent, bool inside_choice) */ dep = expr_trans_compare(dep, E_UNEQUAL, &symbol_no); dep = expr_eliminate_dups(expr_transform(dep)); - dep2 = expr_copy(basedep); + dep2 = basedep; expr_eliminate_eq(&dep, &dep2); - expr_free(dep); if (!expr_is_yes(dep2)) { /* Not superset, quit */ - expr_free(dep2); break; } /* Superset, put in submenu */ - expr_free(dep2); next: _menu_finalize(menu, false); menu->parent = parent; last_menu = menu; } - expr_free(basedep); if (last_menu) { parent->list = parent->next; parent->next = last_menu->next; From patchwork Sun Sep 8 12:43:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 13795453 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7F20316849C; Sun, 8 Sep 2024 12:44:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799452; cv=none; b=VXWgu6ntcdSkNWhMQv1TVAY0QCOcCe43aes4hk5fUGn9hAyGYnLzbmFL7Qav0ijtRmBKOTHjTyRMn1rqUgIiaxaC/SoKmi/L925qEy5CuA68R/REGbIqM3r4QmkkHtnpmRzQr/1KC8ZFYsNGb1sYD41rvTA1RD5Cv/gNWVLYBWY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725799452; c=relaxed/simple; bh=frpqPefFBN64WOqQqEzY881Z9/lRotv+26+9hJ0KYc4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=mZrcLjCCg8kwc/0xnFLadRDS/FsQOSeWEzH6Xzp5lwPVTcL53jdpdqnPr3xoxTTGyWSbb6QKWCewbCXPgFcOmfk0Dsb3Mm8hRvaUrFR9RMb1o1I5tnG2Xq7TNl4PY6jHYLRuipAYjSOMywhwctbbvIAR9Vx5fNx3L1lN35IPGo0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=q4dJJvK+; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="q4dJJvK+" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 3673BC4CEC8; Sun, 8 Sep 2024 12:44:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1725799452; bh=frpqPefFBN64WOqQqEzY881Z9/lRotv+26+9hJ0KYc4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=q4dJJvK+oGGaSp8r1ejylQoqHkC/rhLtpgeMP/SSG8hhKpyeYga/fW+UOOuolDvky byT7M8oUkFkgTVpAw4ndfRFUcxdqyCQ+EoMhW3lonoaD2XPkYcMrkHiFyeaxI5Uasj OVkvku+6lSn2myNMlEfnJOP1amn0sXoj+7DwYUea3Y3rZ1xuPc0/05OXD2j0/xAnT8 d/8VZAb2GwdCoJWLXUHq83tTuKiJXtMjt2AqUaoUfPMU1jeO4I9oua8s6mJFyORdgm UDD9gZmSS3MiNj9BTQzMMSQKJfG2bUsPf7VI90wTe9M3S8qQ/T9oOgQImC/j3B53Mg mCQEduQTuX6hw== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Masahiro Yamada Subject: [PATCH 6/6] kconfig: cache expression values Date: Sun, 8 Sep 2024 21:43:21 +0900 Message-ID: <20240908124352.1828890-6-masahiroy@kernel.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240908124352.1828890-1-masahiroy@kernel.org> References: <20240908124352.1828890-1-masahiroy@kernel.org> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Cache expression values to avoid recalculating them repeatedly. Signed-off-by: Masahiro Yamada --- scripts/kconfig/confdata.c | 2 ++ scripts/kconfig/expr.c | 36 +++++++++++++++++++++++++++++++----- scripts/kconfig/expr.h | 4 ++++ scripts/kconfig/internal.h | 2 ++ scripts/kconfig/symbol.c | 1 + 5 files changed, 40 insertions(+), 5 deletions(-) diff --git a/scripts/kconfig/confdata.c b/scripts/kconfig/confdata.c index d8849dfb06db..4286d5e7f95d 100644 --- a/scripts/kconfig/confdata.c +++ b/scripts/kconfig/confdata.c @@ -396,6 +396,8 @@ int conf_read_simple(const char *name, int def) } } + expr_invalidate_all(); + while (getline_stripped(&line, &line_asize, in) != -1) { struct menu *choice; diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index b7cfaf1a22e6..78738ef412de 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -21,7 +21,7 @@ HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE); static struct expr *expr_eliminate_yn(struct expr *e); /** - * expr_lookup - return the expression for the given type and sub-nodes + * expr_lookup - return the expression with the given type and sub-nodes * This looks up an expression with the specified type and sub-nodes. If such * an expression is found in the hash table, it is returned. Otherwise, a new * expression node is allocated and added to the hash table. @@ -887,7 +887,7 @@ static enum string_value_kind expr_parse_string(const char *str, ? kind : k_string; } -tristate expr_calc_value(struct expr *e) +static tristate __expr_calc_value(struct expr *e) { tristate val1, val2; const char *str1, *str2; @@ -895,9 +895,6 @@ tristate expr_calc_value(struct expr *e) union string_value lval = {}, rval = {}; int res; - if (!e) - return yes; - switch (e->type) { case E_SYMBOL: sym_calc_value(e->left.sym); @@ -961,6 +958,35 @@ tristate expr_calc_value(struct expr *e) } } +/** + * expr_calc_value - return the tristate value of the given expression + * @e: expression + * return: tristate value of the expression + */ +tristate expr_calc_value(struct expr *e) +{ + if (!e) + return yes; + + if (!e->val_is_valid) { + e->val = __expr_calc_value(e); + e->val_is_valid = true; + } + + return e->val; +} + +/** + * expr_invalidate_all - invalidate all cached expression values + */ +void expr_invalidate_all(void) +{ + struct expr *e; + + hash_for_each(expr_hashtable, e, node) + e->val_is_valid = false; +} + static int expr_compare_type(enum expr_type t1, enum expr_type t2) { if (t1 == t2) diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h index a398b2b2dbe0..21578dcd4292 100644 --- a/scripts/kconfig/expr.h +++ b/scripts/kconfig/expr.h @@ -39,12 +39,16 @@ union expr_data { * * @node: link node for the hash table * @type: expressoin type + * @val: calculated tristate value + * @val_is_valid: indicate whether the value is valid * @left: left node * @right: right node */ struct expr { struct hlist_node node; enum expr_type type; + tristate val; + bool val_is_valid; union expr_data left, right; }; diff --git a/scripts/kconfig/internal.h b/scripts/kconfig/internal.h index 84c2ea0389fd..d0ffce2dfbba 100644 --- a/scripts/kconfig/internal.h +++ b/scripts/kconfig/internal.h @@ -15,6 +15,8 @@ extern HASHTABLE_DECLARE(sym_hashtable, SYMBOL_HASHSIZE); extern HASHTABLE_DECLARE(expr_hashtable, EXPR_HASHSIZE); +void expr_invalidate_all(void); + struct menu; extern struct menu *current_menu, *current_entry; diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c index 6243f0143ecf..a3af93aaaf32 100644 --- a/scripts/kconfig/symbol.c +++ b/scripts/kconfig/symbol.c @@ -519,6 +519,7 @@ void sym_clear_all_valid(void) for_all_symbols(sym) sym->flags &= ~SYMBOL_VALID; + expr_invalidate_all(); conf_set_changed(true); sym_calc_value(modules_sym); }