kconfig: cache expression values

Cache expression values to avoid recalculating them repeatedly.

Signed-off-by: Masahiro Yamada <[email protected]>

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.

Conside

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 <[email protected]>

show more ...

kbuild: move some helper headers from scripts/kconfig/ to scripts/include/

Move array_size.h, hashtable.h, list.h, list_types.h from scripts/kconfig/
to scripts/include/.

These headers will be usef

kbuild: move some helper headers from scripts/kconfig/ to scripts/include/

Move array_size.h, hashtable.h, list.h, list_types.h from scripts/kconfig/
to scripts/include/.

These headers will be useful for other host programs.

Remove scripts/mod/list.h.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: use generic macros to implement symbol hashtable

Use helper macros in hashtable.h for generic hashtable implementation.

We can git rid of the hash head index of for_all_symbols().

Signed-

kconfig: use generic macros to implement symbol hashtable

Use helper macros in hashtable.h for generic hashtable implementation.

We can git rid of the hash head index of for_all_symbols().

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove zconf_curname() and zconf_lineno()

Now zconf_curname() and zconf_lineno() are so simple that they just
return cur_filename, cur_lineno, respectively.

Remove these functions, and the

kconfig: remove zconf_curname() and zconf_lineno()

Now zconf_curname() and zconf_lineno() are so simple that they just
return cur_filename, cur_lineno, respectively.

Remove these functions, and then use cur_filename and cur_lineno
directly.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: split menu.c out of parser.y

Compile menu.c as an independent compilation unit.

Signed-off-by: Masahiro Yamada <[email protected]>