1 files changed, 208 insertions, 275 deletions

diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
index c349da7fe3f8..16f92c4a775a 100644
--- a/scripts/kconfig/expr.c
+++ b/scripts/kconfig/expr.c
@@ -9,44 +9,69 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include <hash.h>
+#include <xalloc.h>
+#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);
 
-struct expr *expr_alloc_symbol(struct symbol *sym)
+/**
+ * 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.
+ * @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 = xcalloc(1, sizeof(*e));
-	e->type = E_SYMBOL;
-	e->left.sym = sym;
+	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;
+	e->val_is_valid = false;
+
+	hash_add(expr_hashtable, &e->node, hash);
+
 	return e;
 }
 
+struct expr *expr_alloc_symbol(struct symbol *sym)
+{
+	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)
@@ -63,76 +88,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;
 
 /*
@@ -145,16 +100,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;
 	}
 
@@ -170,7 +133,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);
@@ -242,9 +204,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
@@ -254,7 +217,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:
@@ -269,14 +232,10 @@ int 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:
@@ -291,11 +250,11 @@ int expr_eq(struct expr *e1, struct expr *e2)
 		printf(" ?\n");
 	}
 
-	return 0;
+	return false;
 }
 
 /*
- * 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
@@ -307,79 +266,39 @@ int 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:
@@ -397,7 +316,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)
@@ -440,6 +359,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);
@@ -461,7 +381,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)
@@ -558,38 +478,33 @@ 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;
 	}
 
 	/* *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);
 		if (tmp) {
-			expr_free(*ep1); expr_free(*ep2);
 			*ep1 = expr_alloc_symbol(&symbol_no);
 			*ep2 = tmp;
 			trans_count++;
@@ -598,7 +513,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++;
@@ -628,10 +542,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:
-			expr_eliminate_dups1(e->type, &e, &e);
+			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:
 			;
 		}
@@ -645,12 +564,34 @@ 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<B
+ *     !(A<B)     ->  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)
 {
-	struct expr *tmp;
-
 	if (!e)
 		return NULL;
 	switch (e->type) {
@@ -663,8 +604,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) {
@@ -672,21 +614,19 @@ struct expr *expr_transform(struct expr *e)
 		if (e->left.sym->type != S_BOOLEAN)
 			break;
 		if (e->right.sym == &symbol_no) {
-			e->type = E_NOT;
-			e->left.expr = expr_alloc_symbol(e->left.sym);
-			e->right.sym = NULL;
+			// A=n -> !A
+			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) {
-			e->type = E_SYMBOL;
-			e->right.sym = NULL;
+			// A=y -> A
+			e = expr_alloc_symbol(e->left.sym);
 			break;
 		}
 		break;
@@ -694,104 +634,71 @@ struct expr *expr_transform(struct expr *e)
 		if (e->left.sym->type != S_BOOLEAN)
 			break;
 		if (e->right.sym == &symbol_no) {
-			e->type = E_SYMBOL;
-			e->right.sym = NULL;
+			// A!=n -> A
+			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) {
-			e->type = E_NOT;
-			e->left.expr = expr_alloc_symbol(e->left.sym);
-			e->right.sym = NULL;
+			// A!=y -> !A
+			e = expr_alloc_one(E_NOT, e->left.expr);
 			break;
 		}
 		break;
 	case E_NOT:
 		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);
+			// !!A -> A
+			e = e->left.expr->left.expr;
 			break;
 		case E_EQUAL:
 		case E_UNEQUAL:
-			// !a='x' -> a!='x'
-			tmp = e->left.expr;
-			free(e);
-			e = tmp;
-			e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
+			// !(A=B) -> A!=B
+			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<='x' -> a>'x'
-			tmp = e->left.expr;
-			free(e);
-			e = tmp;
-			e->type = e->type == E_LEQ ? E_GTH : E_LTH;
+			// !(A<=B) -> A>B
+			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<'x' -> a>='x'
-			tmp = e->left.expr;
-			free(e);
-			e = tmp;
-			e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
+			// !(A<B) -> A>=B
+			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;
+			// !(A || B) -> !A && !B
+			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;
+			// !(A && B) -> !A || !B
+			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:
 			;
@@ -803,10 +710,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:
@@ -828,7 +735,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)
@@ -915,18 +822,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:
@@ -981,7 +888,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;
@@ -989,9 +896,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);
@@ -1055,6 +959,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)