Split tree evaluation into two phases: the first phase

does type evaluation, the second one does value evaluation and inline expansion. This has the advantage that by the time we do value evaluation and inline expansion, we have traversed the tree fully once, which allows us to take advantage of function-global information, ie we know whether symbols have ever been accessed etc.
author: Linus Torvalds <torvalds@home.osdl.org> 2003-07-09 02:57:13 -0700
committer: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-04-07 21:00:56 -0700
commit: 8d121d51b6f88e90d166af84d098c6e3af066a87 (patch)
tree: 46a807115ba29f029fe2370808a459aa243075d6
parent: 06231a22afbbad21dcf7523fbf7ed4beb356cd19 (diff)
download: sparse-dev-8d121d51b6f88e90d166af84d098c6e3af066a87.tar.gz
8 files changed, 649 insertions, 233 deletions
diff --git a/Makefile b/Makefile
index 0444e8a9..1098f778 100644
--- a/Makefile
+++ b/Makefile
@@ -8,7 +8,7 @@ PROGRAMS=test-lexing test-parsing obfuscate check
 LIB_H=    token.h parse.h lib.h symbol.h scope.h expression.h target.h
 
 LIB_OBJS= parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
-	  expression.o show-parse.o evaluate.o inline.o
+	  expression.o show-parse.o evaluate.o expand.o inline.o
 
 LIB_FILE= sparse.a
 LIBS=$(LIB_FILE)
diff --git a/check.c b/check.c
index aae7b78c..70fa4f91 100644
--- a/check.c
+++ b/check.c
@@ -94,6 +94,7 @@ static void clean_up_symbol(struct symbol *sym, void *_parent, int flags)
 {
 	check_duplicates(sym);
 	evaluate_symbol(sym);
+	expand_symbol(sym);
 }
 
 int main(int argc, char **argv)
diff --git a/evaluate.c b/evaluate.c
index b0aa888f..6cccc68c 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -34,9 +34,6 @@ static struct symbol *evaluate_symbol_expression(struct expression *expr)
 
 	if (!sym) {
 		if (preprocessing) {
-			warn(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
-			expr->type = EXPR_VALUE;
-			expr->value = 0;
 			expr->ctype = &int_ctype;
 			return &int_ctype;
 		}
@@ -57,16 +54,6 @@ static struct symbol *evaluate_symbol_expression(struct expression *expr)
 	/* The type of a symbol is the symbol itself! */
 	expr->ctype = sym;
 
-	/* Const symbol with a constant initializer? */
-	if (sym->ctype.modifiers & MOD_CONST) {
-		struct expression *value = sym->initializer;
-		if (value && value->type == EXPR_VALUE) {
-			expr->type = EXPR_VALUE;
-			expr->value = value->value;
-			return sym;
-		}
-	}
-
 	/* enum's can be turned into plain values */
 	if (sym->type != SYM_ENUM) {
 		struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
@@ -137,54 +124,12 @@ static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right)
 	return ctype_integer(mod);
 }
 
-static struct symbol * cast_value(struct expression *expr, struct symbol *newtype,
-			struct expression *old, struct symbol *oldtype)
-{
-	int old_size = oldtype->bit_size;
-	int new_size = newtype->bit_size;
-	long long value, mask, ormask, andmask;
-	int is_signed;
-
-	// FIXME! We don't handle FP casts of constant values yet
-	if (newtype->ctype.base_type == &fp_type)
-		return NULL;
-	if (oldtype->ctype.base_type == &fp_type)
-		return NULL;
-
-	// For pointers and integers, we can just move the value around
-	expr->type = EXPR_VALUE;
-	if (old_size == new_size) {
-		expr->value = old->value;
-		return newtype;
-	}
-
-	// expand it to the full "long long" value
-	is_signed = !(oldtype->ctype.modifiers & MOD_UNSIGNED);
-	mask = 1ULL << (old_size-1);
-	value = old->value;
-	if (!(value & mask))
-		is_signed = 0;
-	andmask = mask | (mask-1);
-	ormask = ~andmask;
-	if (!is_signed)
-		ormask = 0;
-	value = (value & andmask) | ormask;
-
-	// Truncate it to the new size
-	mask = 1ULL << (new_size-1);
-	mask = mask | (mask-1);
-	expr->value = value & mask;
-	return newtype;
-}
-
 static struct expression * cast_to(struct expression *old, struct symbol *type)
 {
 	struct expression *expr = alloc_expression(old->pos, EXPR_CAST);
 	expr->ctype = type;
 	expr->cast_type = type;
 	expr->cast_expression = old;
-	if (old->type == EXPR_VALUE)
-		cast_value(expr, type, old, old->ctype);
 	return expr;
 }
 
@@ -235,69 +180,11 @@ static struct symbol * compatible_integer_binop(struct expression *expr, struct
 	return NULL;
 }
 
-static int check_shift_count(struct expression *expr, struct symbol *ctype, unsigned int count)
-{
-	if (count >= ctype->bit_size) {
-		warn(expr->pos, "shift too big for type");
-		count &= ctype->bit_size-1;
-	}
-	return count;
-}
-
-/*
- * CAREFUL! We need to get the size and sign of the
- * result right!
- */
-static void simplify_int_binop(struct expression *expr, struct symbol *ctype)
-{
-	struct expression *left = expr->left, *right = expr->right;
-	unsigned long long v, l, r, mask;
-	signed long long s, sl, sr;
-	int is_signed, shift;
-
-	if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
-		return;
-	l = left->value; r = right->value;
-	is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
-	mask = 1ULL << (ctype->bit_size-1);
-	sl = l; sr = r;
-	if (is_signed && (sl & mask))
-		sl |= ~(mask-1);
-	if (is_signed && (sr & mask))
-		sr |= ~(mask-1);
-	
-	switch (expr->op) {
-	case '+':		v = l + r; s = v; break;
-	case '-':		v = l - r; s = v; break;
-	case '&':		v = l & r; s = v; break;
-	case '|':		v = l | r; s = v; break;
-	case '^':		v = l ^ r; s = v; break;
-	case '*':		v = l * r; s = sl * sr; break;
-	case '/':		if (!r) return; v = l / r; s = sl / sr; break;
-	case '%':		if (!r) return; v = l % r; s = sl % sr; break;
-	case SPECIAL_LEFTSHIFT: shift = check_shift_count(expr, ctype, r); v = l << shift; s = v; break; 
-	case SPECIAL_RIGHTSHIFT:shift = check_shift_count(expr, ctype, r); v = l >> shift; s = sl >> shift; break;
-	case '<':		v = l < r; s = sl < sr; break;
-	case '>':		v = l > r; s = sl > sr; break;
-	case SPECIAL_LTE:	v = l <= r; s = sl <= sr; break;
-	case SPECIAL_GTE:	v = l >= r; s = sl >= sr; break;
-	case SPECIAL_EQUAL:	v = l == r; s = v; break;
-	case SPECIAL_NOTEQUAL:	v = l != r; s = v; break;
-	default: return;
-	}
-	if (is_signed)
-		v = s;
-	mask = mask | (mask-1);
-	expr->value = v & mask;
-	expr->type = EXPR_VALUE;
-}
-
 static struct symbol *evaluate_int_binop(struct expression *expr)
 {
 	struct symbol *ctype = compatible_integer_binop(expr, &expr->left, &expr->right);
 	if (ctype) {
 		expr->ctype = ctype;
-		simplify_int_binop(expr, ctype);
 		return ctype;
 	}
 	return bad_expr_type(expr);
@@ -382,12 +269,10 @@ static struct symbol *evaluate_ptr_add(struct expression *expr, struct expressio
 		mul->ctype = size_t_ctype;
 		mul->left = i;
 		mul->right = val;
-		simplify_int_binop(mul, size_t_ctype);
 
 		/* Leave 'add->op' as 'expr->op' - either '+' or '-' */
 		add->left = ptr;
 		add->right = mul;
-		simplify_int_binop(add, ctype);
 	}
 
 	expr->ctype = ctype;	
@@ -410,7 +295,7 @@ static struct symbol *evaluate_add(struct expression *expr)
 }
 
 #define MOD_SIZE (MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
-#define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE | MOD_SIGNED | MOD_UNSIGNED)
+#define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE | MOD_SIGNED | MOD_UNSIGNED | MOD_ASSIGNED)
 
 static const char * type_difference(struct symbol *target, struct symbol *source,
 	unsigned long target_mod_ignore, unsigned long source_mod_ignore)
@@ -591,44 +476,11 @@ static struct symbol *evaluate_sub(struct expression *expr)
 
 static struct symbol *evaluate_logical(struct expression *expr)
 {
-	struct expression *left = expr->left;
-	struct expression *right;
-
-	if (!evaluate_expression(left))
+	if (!evaluate_expression(expr->left))
 		return NULL;
-
-	/* Do immediate short-circuiting ... */
-	if (left->type == EXPR_VALUE) {
-		if (expr->op == SPECIAL_LOGICAL_AND) {
-			if (!left->value) {
-				expr->type = EXPR_VALUE;
-				expr->value = 0;
-				expr->ctype = &bool_ctype;
-				return &bool_ctype;
-			}
-		} else {
-			if (left->value) {
-				expr->type = EXPR_VALUE;
-				expr->value = 1;
-				expr->ctype = &bool_ctype;
-				return &bool_ctype;
-			}
-		}
-	}
-
-	right = expr->right;
-	if (!evaluate_expression(right))
+	if (!evaluate_expression(expr->right))
 		return NULL;
 	expr->ctype = &bool_ctype;
-	if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
-		/*
-		 * We know the left value doesn't matter, since
-		 * otherwise we would have short-circuited it..
-		 */
-		expr->type = EXPR_VALUE;
-		expr->value = right->value;
-	}
-
 	return &bool_ctype;
 }
 
@@ -682,7 +534,6 @@ static struct symbol *evaluate_compare(struct expression *expr)
 
 	ctype = compatible_integer_binop(expr, &expr->left, &expr->right);
 	if (ctype) {
-		simplify_int_binop(expr, ctype);
 		expr->ctype = &bool_ctype;
 		return &bool_ctype;
 	}
@@ -711,7 +562,7 @@ static int is_null_ptr(struct expression *expr)
 }
 
 /*
- * FIXME!! This shoul ddo casts, array degeneration etc..
+ * FIXME!! This should do casts, array degeneration etc..
  */
 static struct symbol *compatible_ptr_type(struct expression *left, struct expression *right)
 {
@@ -767,12 +618,6 @@ static struct symbol * evaluate_conditional(struct expression *expr)
 		}
 	}
 
-	/* Simplify conditional expression.. */
-	if (cond->type == EXPR_VALUE) {
-		if (!cond->value)
-			true = false;
-		*expr = *true;
-	}
 	expr->ctype = ctype;
 	return ctype;
 }
@@ -886,6 +731,9 @@ static struct symbol *evaluate_assignment(struct expression *expr)
 	if (!compatible_assignment_types(expr, ltype, &expr->right, rtype, "assignment"))
 		return 0;
 
+	if (ltype->type == SYM_NODE)
+		ltype->ctype.modifiers |= MOD_ASSIGNED;
+
 	expr->ctype = ltype;
 	return ltype;
 }
@@ -960,27 +808,6 @@ static struct symbol *evaluate_dereference(struct expression *expr)
 	return sym;
 }
 
-static void simplify_preop(struct expression *expr)
-{
-	struct expression *op = expr->unop;
-	unsigned long long v, mask;
-
-	if (op->type != EXPR_VALUE)
-		return;
-	v = op->value;
-	switch (expr->op) {
-	case '+': break;
-	case '-': v = -v; break;
-	case '!': v = !v; break;
-	case '~': v = ~v; break;
-	default: return;
-	}
-	mask = 1ULL << (expr->ctype->bit_size-1);
-	mask = mask | (mask-1);
-	expr->value = v & mask;
-	expr->type = EXPR_VALUE;
-}
-
 /*
  * Unary post-ops: x++ and x--
  */
@@ -1029,7 +856,6 @@ static struct symbol *evaluate_preop(struct expression *expr)
 		break;
 	}
 	expr->ctype = ctype;
-	simplify_preop(expr);
 	return &bool_ctype;
 }
 
@@ -1083,7 +909,6 @@ static struct expression *evaluate_offset(struct expression *expr, unsigned long
 	add->right->ctype = &int_ctype;
 	add->right->value = offset;
 
-	simplify_int_binop(add, &ptr_ctype);
 	return add;
 }
 
@@ -1384,10 +1209,6 @@ static struct symbol *evaluate_cast(struct expression *expr)
 	}
 
 	evaluate_expression(target);
-
-	/* Simplify normal integer casts.. */
-	if (target->type == EXPR_VALUE)
-		cast_value(expr, ctype, target, target->ctype);
 	return ctype;
 }
 
@@ -1404,8 +1225,8 @@ static int evaluate_symbol_call(struct expression *expr)
 	if (fn->type != EXPR_PREOP)
 		return 0;
 
-	if (ctype->evaluate)
-		return ctype->evaluate(expr);
+	if (ctype->op && ctype->op->evaluate)
+		return ctype->op->evaluate(expr);
 
 	/*
 	 * FIXME!! We should really expand the inline functions.
@@ -1444,6 +1265,10 @@ static struct symbol *evaluate_call(struct expression *expr)
 		if (evaluate_symbol_call(expr))
 			return expr->ctype;
 	}
+	if (sym->type == SYM_NODE) {
+		if (evaluate_symbol_call(expr))
+			return expr->ctype;
+	}
 	if (ctype->type != SYM_FN) {
 		warn(expr->pos, "not a function");
 		return NULL;
@@ -1654,20 +1479,6 @@ static void evaluate_if_statement(struct statement *stmt)
 	if (!ctype)
 		return;
 
-	/* Simplify constant conditionals without even evaluating the false side */
-	if (expr->type == EXPR_VALUE) {
-		struct statement *simple;
-		simple = expr->value ? stmt->if_true : stmt->if_false;
-
-		/* Nothing? */
-		if (!simple) {
-			stmt->type = STMT_NONE;
-			return;
-		}
-		evaluate_statement(simple);
-		*stmt = *simple;
-		return;
-	}
 	evaluate_statement(stmt->if_true);
 	evaluate_statement(stmt->if_false);
 }
@@ -1724,26 +1535,3 @@ struct symbol *evaluate_statement(struct statement *stmt)
 	}
 	return NULL;
 }
-
-long long get_expression_value(struct expression *expr)
-{
-	long long value, mask;
-	struct symbol *ctype;
-
-	ctype = evaluate_expression(expr);
-	if (!ctype || expr->type != EXPR_VALUE) {
-		warn(expr->pos, "bad constant expression");
-		return 0;
-	}
-
-	value = expr->value;
-	mask = 1ULL << (ctype->bit_size-1);
-
-	if (value & mask) {
-		while (ctype->type != SYM_BASETYPE)
-			ctype = ctype->ctype.base_type;
-		if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
-			value = value | mask | ~(mask-1);
-	}
-	return value;
-}
diff --git a/expand.c b/expand.c
new file mode 100644
index 00000000..7842c026
--- /dev/null
+++ b/expand.c
@@ -0,0 +1,609 @@
+/*
+ * sparse/expand.c
+ *
+ * Copyright (C) 2003 Transmeta Corp.
+ *
+ *  Licensed under the Open Software License version 1.1
+ *
+ * expand constant expressions.
+ */
+#include <stdlib.h>
+#include <stdarg.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <limits.h>
+
+#include "lib.h"
+#include "parse.h"
+#include "token.h"
+#include "symbol.h"
+#include "target.h"
+#include "expression.h"
+
+static void expand_expression(struct expression *);
+static void expand_statement(struct statement *);
+
+static void expand_symbol_expression(struct expression *expr)
+{
+	struct symbol *sym = expr->symbol;
+
+	/*
+	 * The preprocessor can cause unknown symbols to be generated
+	 */
+	if (!sym) {
+		warn(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
+		expr->type = EXPR_VALUE;
+		expr->value = 0;
+		return;
+	}
+}
+
+static void cast_value(struct expression *expr, struct symbol *newtype,
+			struct expression *old, struct symbol *oldtype)
+{
+	int old_size = oldtype->bit_size;
+	int new_size = newtype->bit_size;
+	long long value, mask, ormask, andmask;
+	int is_signed;
+
+	// FIXME! We don't handle FP casts of constant values yet
+	if (newtype->ctype.base_type == &fp_type)
+		return;
+	if (oldtype->ctype.base_type == &fp_type)
+		return;
+
+	// For pointers and integers, we can just move the value around
+	expr->type = EXPR_VALUE;
+	if (old_size == new_size) {
+		expr->value = old->value;
+		return;
+	}
+
+	// expand it to the full "long long" value
+	is_signed = !(oldtype->ctype.modifiers & MOD_UNSIGNED);
+	mask = 1ULL << (old_size-1);
+	value = old->value;
+	if (!(value & mask))
+		is_signed = 0;
+	andmask = mask | (mask-1);
+	ormask = ~andmask;
+	if (!is_signed)
+		ormask = 0;
+	value = (value & andmask) | ormask;
+
+	// Truncate it to the new size
+	mask = 1ULL << (new_size-1);
+	mask = mask | (mask-1);
+	expr->value = value & mask;
+}
+
+static int check_shift_count(struct expression *expr, struct symbol *ctype, unsigned int count)
+{
+	if (count >= ctype->bit_size) {
+		warn(expr->pos, "shift too big for type");
+		count &= ctype->bit_size-1;
+	}
+	return count;
+}
+
+/*
+ * CAREFUL! We need to get the size and sign of the
+ * result right!
+ */
+static void simplify_int_binop(struct expression *expr, struct symbol *ctype)
+{
+	struct expression *left = expr->left, *right = expr->right;
+	unsigned long long v, l, r, mask;
+	signed long long s, sl, sr;
+	int is_signed, shift;
+
+	if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
+		return;
+	l = left->value; r = right->value;
+	is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
+	mask = 1ULL << (ctype->bit_size-1);
+	sl = l; sr = r;
+	if (is_signed && (sl & mask))
+		sl |= ~(mask-1);
+	if (is_signed && (sr & mask))
+		sr |= ~(mask-1);
+	
+	switch (expr->op) {
+	case '+':		v = l + r; s = v; break;
+	case '-':		v = l - r; s = v; break;
+	case '&':		v = l & r; s = v; break;
+	case '|':		v = l | r; s = v; break;
+	case '^':		v = l ^ r; s = v; break;
+	case '*':		v = l * r; s = sl * sr; break;
+	case '/':		if (!r) return; v = l / r; s = sl / sr; break;
+	case '%':		if (!r) return; v = l % r; s = sl % sr; break;
+	case SPECIAL_LEFTSHIFT: shift = check_shift_count(expr, ctype, r); v = l << shift; s = v; break; 
+	case SPECIAL_RIGHTSHIFT:shift = check_shift_count(expr, ctype, r); v = l >> shift; s = sl >> shift; break;
+	case '<':		v = l < r; s = sl < sr; break;
+	case '>':		v = l > r; s = sl > sr; break;
+	case SPECIAL_LTE:	v = l <= r; s = sl <= sr; break;
+	case SPECIAL_GTE:	v = l >= r; s = sl >= sr; break;
+	case SPECIAL_EQUAL:	v = l == r; s = v; break;
+	case SPECIAL_NOTEQUAL:	v = l != r; s = v; break;
+	default: return;
+	}
+	if (is_signed)
+		v = s;
+	mask = mask | (mask-1);
+	expr->value = v & mask;
+	expr->type = EXPR_VALUE;
+}
+
+static void expand_int_binop(struct expression *expr)
+{
+	simplify_int_binop(expr, expr->ctype);
+}
+
+static void expand_logical(struct expression *expr)
+{
+	struct expression *left = expr->left;
+	struct expression *right;
+
+	/* Do immediate short-circuiting ... */
+	expand_expression(left);
+	if (left->type == EXPR_VALUE) {
+		if (expr->op == SPECIAL_LOGICAL_AND) {
+			if (!left->value) {
+				expr->type = EXPR_VALUE;
+				expr->value = 0;
+				return;
+			}
+		} else {
+			if (left->value) {
+				expr->type = EXPR_VALUE;
+				expr->value = 1;
+				return;
+			}
+		}
+	}
+
+	right = expr->right;
+	expand_expression(right);
+	if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
+		/*
+		 * We know the left value doesn't matter, since
+		 * otherwise we would have short-circuited it..
+		 */
+		expr->type = EXPR_VALUE;
+		expr->value = right->value;
+	}
+}
+
+static void expand_binop(struct expression *expr)
+{
+	expand_int_binop(expr);
+}
+
+static void expand_comma(struct expression *expr)
+{
+	if (expr->left->type == EXPR_VALUE)
+		*expr = *expr->right;
+}
+
+static void expand_compare(struct expression *expr)
+{
+	simplify_int_binop(expr, expr->ctype);
+}
+
+static void expand_conditional(struct expression *expr)
+{
+	struct expression *cond = expr->conditional;
+
+	if (cond->type == EXPR_VALUE) {
+		struct expression *true, *false;
+
+		true = expr->cond_true ? : cond;
+		false = expr->cond_false;
+
+		if (!cond->value)
+			true = false;
+		*expr = *true;
+	}
+}
+		
+static void expand_assignment(struct expression *expr)
+{
+}
+
+static void expand_addressof(struct expression *expr)
+{
+}
+
+static void expand_dereference(struct expression *expr)
+{
+	struct expression *unop = expr->unop;
+	if (unop->type == EXPR_SYMBOL) {
+		struct symbol *sym = unop->symbol;
+
+		if (sym->ctype.modifiers & MOD_NODEREF)
+			warn(expr->pos, "dereference of '%s'", show_ident(sym->ident));
+
+		/* Const symbol with a constant initializer? */
+		if (!(sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE))) {
+			struct expression *value = sym->initializer;
+			if (value) {
+				if (value->type == EXPR_VALUE) {
+					expr->type = EXPR_VALUE;
+					expr->value = value->value;
+				}
+			}
+		}
+	}
+}
+
+static void simplify_preop(struct expression *expr)
+{
+	struct expression *op = expr->unop;
+	unsigned long long v, mask;
+
+	if (op->type != EXPR_VALUE)
+		return;
+	v = op->value;
+	switch (expr->op) {
+	case '+': break;
+	case '-': v = -v; break;
+	case '!': v = !v; break;
+	case '~': v = ~v; break;
+	default: return;
+	}
+	mask = 1ULL << (expr->ctype->bit_size-1);
+	mask = mask | (mask-1);
+	expr->value = v & mask;
+	expr->type = EXPR_VALUE;
+}
+
+/*
+ * Unary post-ops: x++ and x--
+ */
+static void expand_postop(struct expression *expr)
+{
+}
+
+static void expand_preop(struct expression *expr)
+{
+	switch (expr->op) {
+	case '*':
+		expand_dereference(expr);
+		return;
+
+	case '&':
+		expand_addressof(expr);
+		return;
+
+	case SPECIAL_INCREMENT:
+	case SPECIAL_DECREMENT:
+		/*
+		 * From a type evaluation standpoint the pre-ops are
+		 * the same as the postops
+		 */
+		expand_postop(expr);
+		return;
+
+	default:
+		break;
+	}
+	simplify_preop(expr);
+}
+
+static void expand_arguments(struct expression_list *head)
+{
+	struct expression *expr;
+
+	FOR_EACH_PTR (head, expr) {
+		expand_expression(expr);
+	} END_FOR_EACH_PTR;
+}
+
+static void expand_cast(struct expression *expr)
+{
+	struct expression *target = expr->cast_expression;
+
+	expand_expression(target);
+
+	/* Simplify normal integer casts.. */
+	if (target->type == EXPR_VALUE)
+		cast_value(expr, expr->ctype, target, target->ctype);
+}
+
+/*
+ * expand a call expression with a symbol. This
+ * should expand inline functions, and expand
+ * builtins.
+ */
+static void expand_symbol_call(struct expression *expr)
+{
+	struct expression *fn = expr->fn;
+	struct symbol *ctype = fn->ctype;
+
+	if (fn->type != EXPR_PREOP)
+		return;
+
+	if (ctype->op && ctype->op->expand) {
+		ctype->op->expand(expr);
+		return;
+	}
+
+	if (ctype->ctype.modifiers & MOD_INLINE)
+		inline_function(expr, ctype);
+}
+
+static void expand_call(struct expression *expr)
+{
+	struct symbol *sym;
+	struct expression *fn = expr->fn;
+
+	sym = fn->ctype;
+	expand_arguments(expr->args);
+	if (sym->type == SYM_NODE)
+		expand_symbol_call(expr);
+}
+
+static void expand_expression_list(struct expression_list *list)
+{
+	struct expression *expr;
+
+	FOR_EACH_PTR(list, expr) {
+		expand_expression(expr);
+	} END_FOR_EACH_PTR;
+}
+
+static void expand_expression(struct expression *expr)
+{
+	if (!expr)
+		return;
+	if (!expr->ctype)
+		return;
+
+	switch (expr->type) {
+	case EXPR_VALUE:
+		return;
+	case EXPR_STRING:
+		return;
+	case EXPR_SYMBOL:
+		expand_symbol_expression(expr);
+		return;
+	case EXPR_BINOP:
+		expand_expression(expr->left);
+		expand_expression(expr->right);
+		expand_binop(expr);
+		return;
+
+	case EXPR_LOGICAL:
+		expand_logical(expr);
+		return;
+
+	case EXPR_COMMA:
+		expand_expression(expr->left);
+		expand_expression(expr->right);
+		expand_comma(expr);
+		return;
+
+	case EXPR_COMPARE:
+		expand_expression(expr->left);
+		expand_expression(expr->right);
+		expand_compare(expr);
+		return;
+
+	case EXPR_ASSIGNMENT:
+		expand_expression(expr->left);
+		expand_expression(expr->right);
+		expand_assignment(expr);
+		return;
+
+	case EXPR_PREOP:
+		expand_expression(expr->unop);
+		expand_preop(expr);
+		return;
+
+	case EXPR_POSTOP:
+		expand_expression(expr->unop);
+		expand_postop(expr);
+		return;
+
+	case EXPR_CAST:
+		expand_cast(expr);
+		return;
+
+	case EXPR_CALL:
+		expand_call(expr);
+		return;
+
+	case EXPR_DEREF:
+		return;
+
+	case EXPR_BITFIELD:
+		expand_expression(expr->address);
+		return;
+
+	case EXPR_CONDITIONAL:
+		expand_expression(expr->conditional);
+		expand_expression(expr->cond_false);
+		expand_expression(expr->cond_true);
+		expand_conditional(expr);
+		return;
+
+	case EXPR_STATEMENT:
+		expand_statement(expr->statement);
+		return;
+
+	case EXPR_LABEL:
+		return;
+
+	case EXPR_INITIALIZER:
+		expand_expression_list(expr->expr_list);
+		return;
+
+	case EXPR_IDENTIFIER:
+		return;
+
+	case EXPR_INDEX:
+		return;
+
+	case EXPR_POS:
+		expand_expression(expr->init_expr);
+		return;
+
+	case EXPR_SIZEOF:
+		warn(expr->pos, "internal front-end error: sizeof in expansion?");
+		return;
+	}
+	return;
+}
+
+
+static void expand_one_statement(struct statement *stmt, void *unused, int flags)
+{
+	expand_statement(stmt);
+}
+
+void expand_symbol(struct symbol *sym)
+{
+	struct symbol *base_type;
+
+	if (!sym)
+		return;
+	base_type = sym->ctype.base_type;
+	if (!base_type)
+		return;
+
+	expand_expression(sym->initializer);
+	/* expand the body of the symbol */
+	if (base_type->type == SYM_FN) {
+		if (base_type->stmt)
+			expand_statement(base_type->stmt);
+	}
+}
+
+static void expand_one_symbol(struct symbol *sym, void *unused, int flags)
+{
+	expand_symbol(sym);
+}
+
+static void expand_return_expression(struct statement *stmt)
+{
+	expand_expression(stmt->expression);
+}
+
+static void expand_if_statement(struct statement *stmt)
+{
+	struct expression *expr = stmt->if_conditional;
+
+	if (!expr || !expr->ctype)
+		return;
+
+	expand_expression(expr);
+
+	/* Simplify constant conditionals without even evaluating the false side */
+	if (expr->type == EXPR_VALUE) {
+		struct statement *simple;
+		simple = expr->value ? stmt->if_true : stmt->if_false;
+
+		/* Nothing? */
+		if (!simple) {
+			stmt->type = STMT_NONE;
+			return;
+		}
+		expand_statement(simple);
+		*stmt = *simple;
+		return;
+	}
+	expand_statement(stmt->if_true);
+	expand_statement(stmt->if_false);
+}
+
+static void expand_statement(struct statement *stmt)
+{
+	if (!stmt)
+		return;
+
+	switch (stmt->type) {
+	case STMT_RETURN:
+		expand_return_expression(stmt);
+		return;
+
+	case STMT_EXPRESSION:
+		expand_expression(stmt->expression);
+		return;
+
+	case STMT_COMPOUND: {
+		symbol_iterate(stmt->syms, expand_one_symbol, NULL);
+		expand_symbol(stmt->ret);
+		statement_iterate(stmt->stmts, expand_one_statement, NULL);
+		return;
+	}
+
+	case STMT_IF:
+		expand_if_statement(stmt);
+		return;
+
+	case STMT_ITERATOR:
+		expand_expression(stmt->iterator_pre_condition);
+		expand_expression(stmt->iterator_post_condition);
+		expand_statement(stmt->iterator_pre_statement);
+		expand_statement(stmt->iterator_statement);
+		expand_statement(stmt->iterator_post_statement);
+		return;
+
+	case STMT_SWITCH:
+		expand_expression(stmt->switch_expression);
+		expand_statement(stmt->switch_statement);
+		return;
+
+	case STMT_CASE:
+		expand_expression(stmt->case_expression);
+		expand_expression(stmt->case_to);
+		expand_statement(stmt->case_statement);
+		return;
+
+	case STMT_LABEL:
+		expand_statement(stmt->label_statement);
+		return;
+
+	case STMT_GOTO:
+		expand_expression(stmt->goto_expression);
+		return;
+
+	case STMT_NONE:
+		break;
+	case STMT_ASM:
+		/* FIXME! Do the asm parameter evaluation! */
+		break;
+	}
+}
+
+long long get_expression_value(struct expression *expr)
+{
+	long long value, mask;
+	struct symbol *ctype;
+
+	ctype = evaluate_expression(expr);
+	if (!ctype) {
+		warn(expr->pos, "bad constant expression type");
+		return 0;
+	}
+	expand_expression(expr);
+	if (expr->type != EXPR_VALUE) {
+		warn(expr->pos, "bad constant expression");
+		return 0;
+	}
+
+	value = expr->value;
+	mask = 1ULL << (ctype->bit_size-1);
+
+	if (value & mask) {
+		while (ctype->type != SYM_BASETYPE)
+			ctype = ctype->ctype.base_type;
+		if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
+			value = value | mask | ~(mask-1);
+	}
+	return value;
+}
diff --git a/expression.h b/expression.h
index 8a5ea3b5..a9245caf 100644
--- a/expression.h
+++ b/expression.h
@@ -125,6 +125,8 @@ extern struct symbol *evaluate_symbol(struct symbol *sym);
 extern struct symbol *evaluate_statement(struct statement *stmt);
 extern struct symbol *evaluate_expression(struct expression *);
 
+extern void expand_symbol(struct symbol *);
+
 static inline struct expression *alloc_expression(struct position pos, int type)
 {
 	struct expression *expr = __alloc_expression(0);
diff --git a/symbol.c b/symbol.c
index ebe46009..fac4de9c 100644
--- a/symbol.c
+++ b/symbol.c
@@ -332,6 +332,12 @@ static struct symbol *create_symbol(int stream, const char *name, int type, int
 
 static int evaluate_constant_p(struct expression *expr)
 {
+	expr->ctype = &int_ctype;
+	return 1;
+}
+
+static void expand_constant_p(struct expression *expr)
+{
 	struct expression *arg;
 	struct expression_list *arglist = expr->args;
 	int value = 1;
@@ -341,10 +347,8 @@ static int evaluate_constant_p(struct expression *expr)
 			value = 0;
 	} END_FOR_EACH_PTR;
 
-	expr->ctype = &int_ctype;
 	expr->type = EXPR_VALUE;
 	expr->value = value;
-	return 1;
 }
 
 /*
@@ -358,7 +362,7 @@ struct sym_init {
 	const char *name;
 	struct symbol *base_type;
 	unsigned int modifiers;
-	int (*evaluate)(struct expression *);
+	struct symbol_op *op;
 } symbol_init_table[] = {
 	/* Storage class */
 	{ "auto",	NULL,		MOD_AUTO },
@@ -420,11 +424,16 @@ struct sym_init {
 	{ NULL,		NULL,		0 }
 };
 
+struct symbol_op constant_p_op = {
+	.evaluate = evaluate_constant_p,
+	.expand = expand_constant_p
+};
+
 /*
  * Builtin functions
  */
 struct sym_init eval_init_table[] = {
-	{ "__builtin_constant_p", &int_type, MOD_TOPLEVEL, evaluate_constant_p },
+	{ "__builtin_constant_p", &int_type, MOD_TOPLEVEL, &constant_p_op },
 
 	{ NULL,		NULL,		0 }
 };
@@ -545,7 +554,7 @@ void init_symbols(void)
 		sym = create_symbol(stream, ptr->name, SYM_NODE, NS_SYMBOL);
 		sym->ctype.base_type = ptr->base_type;
 		sym->ctype.modifiers = ptr->modifiers;
-		sym->evaluate = ptr->evaluate;
+		sym->op = ptr->op;
 	}
 
 	ptr_ctype.type = SYM_PTR;
diff --git a/symbol.h b/symbol.h
index 40f0b838..408e36cf 100644
--- a/symbol.h
+++ b/symbol.h
@@ -56,6 +56,11 @@ struct ctype {
 	struct symbol *base_type;
 };
 
+struct symbol_op {
+	int (*evaluate)(struct expression *);
+	void (*expand)(struct expression *);
+};	
+
 struct symbol {
 	enum namespace namespace:8;
 	enum type type:8;
@@ -66,7 +71,7 @@ struct symbol {
 	struct symbol	*replace;	/* What is this symbol shadowed by in copy-expression */
 	struct scope	*scope;
 	struct symbol	*same_symbol;
-	int (*evaluate)(struct expression *);
+	struct symbol_op *op;
 
 	struct /* preprocessor_sym */ {
 		struct token *expansion;
@@ -127,6 +132,7 @@ struct symbol {
 #define MOD_TOPLEVEL	0x800000	// scoping..
 
 #define MOD_LABEL	0x1000000
+#define MOD_ASSIGNED	0x2000000
 
 /* Basic types */
 extern struct symbol	void_type,
diff --git a/test-parsing.c b/test-parsing.c
index c9ee16d3..f63be073 100644
--- a/test-parsing.c
+++ b/test-parsing.c
@@ -70,6 +70,7 @@ static void handle_switch(char *arg)
 static void clean_up_symbol(struct symbol *sym, void *_parent, int flags)
 {
 	evaluate_symbol(sym);
+	expand_symbol(sym);
 }
 
 int main(int argc, char **argv)
@@ -112,7 +113,7 @@ int main(int argc, char **argv)
 	// Parse the resulting C code
 	translation_unit(token, &used_list);
 
-	// Do type evaluation and simplify
+	// Do type evaluation and simplification
 	symbol_iterate(used_list, clean_up_symbol, NULL);
 
 #if 1
author	Linus Torvalds <torvalds@home.osdl.org>	2003-07-09 02:57:13 -0700
committer	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-04-07 21:00:56 -0700
commit	8d121d51b6f88e90d166af84d098c6e3af066a87 (patch)
tree	46a807115ba29f029fe2370808a459aa243075d6
parent	06231a22afbbad21dcf7523fbf7ed4beb356cd19 (diff)
download	sparse-dev-8d121d51b6f88e90d166af84d098c6e3af066a87.tar.gz