kconfig: use hash table to reuse expressions

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. This will be
addressed later.

One 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 <masahiroy@kernel.org>

1 files changed, 10 insertions, 23 deletions

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;