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>

0 files changed, 0 insertions, 0 deletions