// SPDX-License-Identifier: GPL-2.0/* * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> */ #include <ctype.h>#include <errno.h>#include <stdio.h>#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); /** * 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;	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){	return expr_lookup(type, ce, NULL);} struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2){	return expr_lookup(type, e1, e2);} struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2){	return expr_lookup(type, s1, s2);} struct expr *expr_alloc_and(struct expr *e1, struct expr *e2){	if (!e1)		return e2;	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;} struct expr *expr_alloc_or(struct expr *e1, struct expr *e2){	if (!e1)		return e2;	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;} static int trans_count; /* * expr_eliminate_eq() helper. * * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared * against all other leaves. Two equal leaves are both replaced with either 'y' * or 'n' as appropriate for 'type', to be eliminated later. */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) {		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) {		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;	} 	/* *ep1 and *ep2 are leaves. Compare them. */ 	if ((*ep1)->type == E_SYMBOL && (*ep2)->type == E_SYMBOL &&	    (*ep1)->left.sym == (*ep2)->left.sym &&	    ((*ep1)->left.sym == &symbol_yes || (*ep1)->left.sym == &symbol_no))		return;	if (!expr_eq(*ep1, *ep2))		return; 	/* *ep1 and *ep2 are equal leaves. Prepare them for elimination. */ 	trans_count++;	switch (type) {	case E_OR:		*ep1 = expr_alloc_symbol(&symbol_no);		*ep2 = expr_alloc_symbol(&symbol_no);		break;	case E_AND:		*ep1 = expr_alloc_symbol(&symbol_yes);		*ep2 = expr_alloc_symbol(&symbol_yes);		break;	default:		;	}} /* * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both. * Example reductions: * *	ep1: A && B           ->  ep1: y *	ep2: A && B && C      ->  ep2: C * *	ep1: A || B           ->  ep1: n *	ep2: A || B || C      ->  ep2: C * *	ep1: A && (B && FOO)  ->  ep1: FOO *	ep2: (BAR && B) && A  ->  ep2: BAR * *	ep1: A && (B || C)    ->  ep1: y *	ep2: (C || B) && A    ->  ep2: y * * Comparisons are done between all operands at the same "level" of && or ||. * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the * following operands will be compared: * *	- 'e1', 'e2 || e3', and 'e4 || e5', against each other *	- e2 against e3 *	- e4 against e5 * * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and * '(e1 && e2) && e3' are both a single level. * * See __expr_eliminate_eq() as well. */void expr_eliminate_eq(struct expr **ep1, struct expr **ep2){	if (!*ep1 || !*ep2)		return;	switch ((*ep1)->type) {	case E_OR:	case E_AND:		__expr_eliminate_eq((*ep1)->type, ep1, ep2);	default:		;	}	if ((*ep1)->type != (*ep2)->type) switch ((*ep2)->type) {	case E_OR:	case E_AND:		__expr_eliminate_eq((*ep2)->type, ep1, ep2);	default:		;	}	*ep1 = expr_eliminate_yn(*ep1);	*ep2 = expr_eliminate_yn(*ep2);} /* * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two * &&/|| expressions are considered equal if every operand in one expression * equals some operand in the other (operands do not need to appear in the same * order), recursively. */bool expr_eq(struct expr *e1, struct expr *e2){	int old_count;	bool res; 	/*	 * A NULL expr is taken to be yes, but there's also a different way to	 * represent yes. expr_is_yes() checks for either representation.	 */	if (!e1 || !e2)		return expr_is_yes(e1) && expr_is_yes(e2); 	if (e1->type != e2->type)		return false;	switch (e1->type) {	case E_EQUAL:	case E_GEQ:	case E_GTH:	case E_LEQ:	case E_LTH:	case E_UNEQUAL:		return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;	case E_SYMBOL:		return e1->left.sym == e2->left.sym;	case E_NOT:		return expr_eq(e1->left.expr, e2->left.expr);	case E_AND:	case E_OR:		old_count = trans_count;		expr_eliminate_eq(&e1, &e2);		res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&		       e1->left.sym == e2->left.sym);		trans_count = old_count;		return res;	case E_RANGE:	case E_NONE:		/* panic */;	} 	if (DEBUG_EXPR) {		expr_fprint(e1, stdout);		printf(" = ");		expr_fprint(e2, stdout);		printf(" ?\n");	} 	return false;} /* * Recursively performs the following simplifications (as well as the * corresponding simplifications with swapped operands): * *	expr && n  ->  n *	expr && y  ->  expr *	expr || n  ->  expr *	expr || y  ->  y * * Returns the optimized expression. */static struct expr *expr_eliminate_yn(struct expr *e){	struct expr *l, *r; 	if (e) switch (e->type) {	case E_AND:		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 (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:		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 (r->type == E_SYMBOL) {			if (r->left.sym == &symbol_no)				return l;			else if (r->left.sym == &symbol_yes)				return r;		}		break;	default:		;	}	return e;} /* * e1 || e2 -> ? */static struct expr *expr_join_or(struct expr *e1, struct expr *e2){	struct expr *tmp;	struct symbol *sym1, *sym2; 	if (expr_eq(e1, e2))		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)		return NULL;	if (e1->type == E_NOT) {		tmp = e1->left.expr;		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)			return NULL;		sym1 = tmp->left.sym;	} else		sym1 = e1->left.sym;	if (e2->type == E_NOT) {		if (e2->left.expr->type != E_SYMBOL)			return NULL;		sym2 = e2->left.expr->left.sym;	} else		sym2 = e2->left.sym;	if (sym1 != sym2)		return NULL;	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)		return NULL;	if (sym1->type == S_TRISTATE) {		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||		     (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {			// (a='y') || (a='m') -> (a!='n')			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);		}		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {			// (a='y') || (a='n') -> (a!='m')			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);		}		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&		    ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {			// (a='m') || (a='n') -> (a!='y')			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);		}	}	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);	} 	if (DEBUG_EXPR) {		printf("optimize (");		expr_fprint(e1, stdout);		printf(") || (");		expr_fprint(e2, stdout);		printf(")?\n");	}	return NULL;} static struct expr *expr_join_and(struct expr *e1, struct expr *e2){	struct expr *tmp;	struct symbol *sym1, *sym2; 	if (expr_eq(e1, e2))		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)		return NULL;	if (e1->type == E_NOT) {		tmp = e1->left.expr;		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)			return NULL;		sym1 = tmp->left.sym;	} else		sym1 = e1->left.sym;	if (e2->type == E_NOT) {		if (e2->left.expr->type != E_SYMBOL)			return NULL;		sym2 = e2->left.expr->left.sym;	} else		sym2 = e2->left.sym;	if (sym1 != sym2)		return NULL;	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)		return NULL; 	if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||	    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))		// (a) && (a='y') -> (a='y')		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))		// (a) && (a!='n') -> (a)		return expr_alloc_symbol(sym1); 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))		// (a) && (a!='m') -> (a='y')		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 	if (sym1->type == S_TRISTATE) {		if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'			sym2 = e1->right.sym;			if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)							     : expr_alloc_symbol(&symbol_no);		}		if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'			sym2 = e2->right.sym;			if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)							     : expr_alloc_symbol(&symbol_no);		}		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))			// (a!='y') && (a!='n') -> (a='m')			return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod); 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||			    (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))			// (a!='y') && (a!='m') -> (a='n')			return expr_alloc_comp(E_EQUAL, sym1, &symbol_no); 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&			   ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))			// (a!='m') && (a!='n') -> (a='m')			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 		if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||		    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||		    (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||		    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))			return NULL;	} 	if (DEBUG_EXPR) {		printf("optimize (");		expr_fprint(e1, stdout);		printf(") && (");		expr_fprint(e2, stdout);		printf(")?\n");	}	return NULL;} /* * expr_eliminate_dups() helper. * * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared * against all other leaves to look for simplifications. */static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2){	struct expr *tmp, *l, *r; 	/* Recurse down to leaves */ 	if ((*ep1)->type == type) {		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) {		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;	}

Lines 1–500 of 1213. Load more