Add compile-time "range-check" infrastructure to sparse

13 files changed, 120 insertions, 18 deletions

diff --git a/check.c b/check.c
index 3160bc0..01f9eea 100644
--- a/check.c
+++ b/check.c
@@ -113,11 +113,20 @@ static void check_cast_instruction(struct instruction *insn)
 	}
 }
 
+static void check_range_instruction(struct instruction *insn)
+{
+	warning(insn->bb->pos, "value out of range");
+}
+
 static void check_one_instruction(struct instruction *insn)
 {
 	switch (insn->opcode) {
 	case OP_CAST: case OP_SCAST:
-		check_cast_instruction(insn);
+		if (verbose)
+			check_cast_instruction(insn);
+		break;
+	case OP_RANGE:
+		check_range_instruction(insn);
 		break;
 	default:
 		break;
@@ -155,8 +164,7 @@ static void check_context(struct entrypoint *ep)
 		} END_FOR_EACH_PTR(pseudo);
 	}
 
-	if (verbose)
-		check_instructions(ep);
+	check_instructions(ep);
 
 	check_bb_context(ep, ep->entry->bb, sym->ctype.in_context, sym->ctype.out_context);
 }
diff --git a/evaluate.c b/evaluate.c
index 63f7d1a..1de810b 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -2560,9 +2560,14 @@ struct symbol *evaluate_statement(struct statement *stmt)
 	case STMT_ASM:
 		evaluate_asm_statement(stmt);
 		return NULL;
-	case STMT_INTERNAL:
+	case STMT_CONTEXT:
 		evaluate_expression(stmt->expression);
 		return NULL;
+	case STMT_RANGE:
+		evaluate_expression(stmt->range_expression);
+		evaluate_expression(stmt->range_low);
+		evaluate_expression(stmt->range_high);
+		return NULL;
 	}
 	return NULL;
 }
diff --git a/example.c b/example.c
index f6a9c5d..538bc9a 100644
--- a/example.c
+++ b/example.c
@@ -80,6 +80,8 @@ static const char* opcodes[] = {
 	[OP_PHI] = "phi",
 	[OP_PHISOURCE] = "phisrc",
 	[OP_CAST] = "cast",
+	[OP_SCAST] = "scast",
+	[OP_FPCAST] = "fpcast",
 	[OP_PTRCAST] = "ptrcast",
 	[OP_CALL] = "call",
 	[OP_VANEXT] = "va_next",
@@ -1438,7 +1440,7 @@ static void generate_one_insn(struct instruction *insn, struct bb_state *state)
 		generate_compare(state, insn);
 		break;
 
-	case OP_CAST: case OP_PTRCAST:
+	case OP_CAST: case OP_SCAST: case OP_FPCAST: case OP_PTRCAST:
 		generate_cast(state, insn);
 		break;
 
diff --git a/expand.c b/expand.c
index 3b9adb8..33f5f0a 100644
--- a/expand.c
+++ b/expand.c
@@ -1054,9 +1054,14 @@ static int expand_statement(struct statement *stmt)
 	case STMT_ASM:
 		/* FIXME! Do the asm parameter evaluation! */
 		break;
-	case STMT_INTERNAL:
+	case STMT_CONTEXT:
 		expand_expression(stmt->expression);
 		break;
+	case STMT_RANGE:
+		expand_expression(stmt->range_expression);
+		expand_expression(stmt->range_low);
+		expand_expression(stmt->range_high);
+		break;
 	}
 	return SIDE_EFFECTS;
 }
diff --git a/ident-list.h b/ident-list.h
index c414d2c..8e94961 100644
--- a/ident-list.h
+++ b/ident-list.h
@@ -66,6 +66,7 @@ __IDENT(__PRETTY_FUNCTION___ident, "__PRETTY_FUNCTION__", 0);
 
 /* Sparse commands */
 IDENT_RESERVED(__context__);
+IDENT_RESERVED(__range__);
 
 #undef __IDENT
 #undef IDENT
diff --git a/inline.c b/inline.c
index 8b145c7..552ddb2 100644
--- a/inline.c
+++ b/inline.c
@@ -294,7 +294,7 @@ static struct statement *copy_one_statement(struct statement *stmt)
 	switch(stmt->type) {
 	case STMT_NONE:
 		break;
-	case STMT_INTERNAL:
+	case STMT_CONTEXT:
 	case STMT_EXPRESSION: {
 		struct expression *expr = copy_expression(stmt->expression);
 		if (expr == stmt->expression)
@@ -303,6 +303,14 @@ static struct statement *copy_one_statement(struct statement *stmt)
 		stmt->expression = expr;
 		break;
 	}
+	case STMT_RANGE: {
+		struct expression *expr = copy_expression(stmt->range_expression);
+		if (expr == stmt->expression)
+			break;
+		stmt = dup_statement(stmt);
+		stmt->range_expression = expr;
+		break;
+	}
 	case STMT_COMPOUND: {
 		struct statement *new = alloc_statement(stmt->pos, STMT_COMPOUND);
 		copy_statement(stmt, new);
diff --git a/linearize.c b/linearize.c
index e891a0e..7a4affb 100644
--- a/linearize.c
+++ b/linearize.c
@@ -231,6 +231,7 @@ static const char* opcodes[] = {
 
 	/* Sparse tagging (line numbers, context, whatever) */
 	[OP_CONTEXT] = "context",
+	[OP_RANGE] = "range-check",
 };
 
 static char *show_asm_constraints(char *buf, const char *sep, struct asm_constraint_list *list)
@@ -429,6 +430,9 @@ const char *show_instruction(struct instruction *insn)
 	case OP_CONTEXT:
 		buf += sprintf(buf, "%d", insn->increment);
 		break;
+	case OP_RANGE:
+		buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
+		break;
 	case OP_NOP:
 		buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
 		break;
@@ -1599,7 +1603,7 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct state
 	return pseudo;
 }
 
-pseudo_t linearize_internal(struct entrypoint *ep, struct statement *stmt)
+pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
 {
 	struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
 	struct expression *expr = stmt->expression;
@@ -1613,6 +1617,17 @@ pseudo_t linearize_internal(struct entrypoint *ep, struct statement *stmt)
 	return VOID;
 }
 
+pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
+{
+	struct instruction *insn = alloc_instruction(OP_RANGE, 0);
+
+	use_pseudo(linearize_expression(ep, stmt->range_expression), &insn->src1);
+	use_pseudo(linearize_expression(ep, stmt->range_low), &insn->src2);
+	use_pseudo(linearize_expression(ep, stmt->range_high), &insn->src3);
+	add_one_insn(ep, insn);
+	return VOID;
+}
+
 ALLOCATOR(asm_rules, "asm rules");
 ALLOCATOR(asm_constraint, "asm constraints");
 
@@ -1756,8 +1771,11 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 	case STMT_NONE:
 		break;
 
-	case STMT_INTERNAL:
-		return linearize_internal(ep, stmt);
+	case STMT_CONTEXT:
+		return linearize_context(ep, stmt);
+
+	case STMT_RANGE:
+		return linearize_range(ep, stmt);
 
 	case STMT_EXPRESSION:
 		return linearize_expression(ep, stmt->expression);
diff --git a/linearize.h b/linearize.h
index 7c29fba..32636c1 100644
--- a/linearize.h
+++ b/linearize.h
@@ -195,6 +195,7 @@ enum opcode {
 
 	/* Sparse tagging (line numbers, context, whatever) */
 	OP_CONTEXT,
+	OP_RANGE,
 };
 
 struct basic_block_list;
diff --git a/liveness.c b/liveness.c
index 31dc757..c1387fe 100644
--- a/liveness.c
+++ b/liveness.c
@@ -138,6 +138,10 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		asm_liveness(bb, insn, def, use);
 		break;
 
+	case OP_RANGE:
+		USES(src1); USES(src2); USES(src3);
+		break;
+
 	case OP_BADOP:
 	case OP_INVOKE:
 	case OP_UNWIND:
diff --git a/parse.c b/parse.c
index 3063adb..10d77c9 100644
--- a/parse.c
+++ b/parse.c
@@ -1276,10 +1276,19 @@ default_statement:
 			return parse_asm(token->next, stmt);
 		}
 		if (token->ident == &__context___ident) {
-			stmt->type = STMT_INTERNAL;
+			stmt->type = STMT_CONTEXT;
 			token = parse_expression(token->next, &stmt->expression);
 			return expect(token, ';', "at end of statement");
 		}
+		if (token->ident == &__range___ident) {
+			stmt->type = STMT_RANGE;
+			token = assignment_expression(token->next, &stmt->range_expression);
+			token = expect(token, ',', "after range expression");
+			token = assignment_expression(token, &stmt->range_low);
+			token = expect(token, ',', "after low range");
+			token = assignment_expression(token, &stmt->range_high);
+			return expect(token, ';', "after range statement");
+		}
 		if (match_op(token->next, ':')) {
 			stmt->type = STMT_LABEL;
 			stmt->label_identifier = label_symbol(token);
diff --git a/parse.h b/parse.h
index e37825b..7a8aceb 100644
--- a/parse.h
+++ b/parse.h
@@ -23,7 +23,8 @@ enum statement_type {
 	STMT_LABEL,
 	STMT_GOTO,
 	STMT_ASM,
-	STMT_INTERNAL,
+	STMT_CONTEXT,
+	STMT_RANGE,
 };
 
 struct statement {
@@ -98,6 +99,11 @@ struct statement {
 			struct expression_list *asm_inputs;
 			struct expression_list *asm_clobbers;
 		};
+		struct /* range */ {
+			struct expression *range_expression;
+			struct expression *range_low;
+			struct expression *range_high;
+		};
 	};
 };
 
diff --git a/show-parse.c b/show-parse.c
index 695a1be..0a75a09 100644
--- a/show-parse.c
+++ b/show-parse.c
@@ -561,11 +561,18 @@ int show_statement(struct statement *stmt)
 	case STMT_ASM:
 		printf("\tasm( .... )\n");
 		break;
-	case STMT_INTERNAL: {
+	case STMT_CONTEXT: {
 		int val = show_expression(stmt->expression);
-		printf("\tINTERNAL( %d )\n", val);
+		printf("\tcontext( %d )\n", val);
 		break;
 	}
+	case STMT_RANGE: {
+		int val = show_expression(stmt->range_expression);
+		int low = show_expression(stmt->range_low);
+		int high = show_expression(stmt->range_high);
+		printf("\trange( %d %d-%d)\n", val, low, high); 
+		break;
+	}	
 	}
 	return 0;
 }
diff --git a/simplify.c b/simplify.c
index 8f9d814..96ad80e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -188,10 +188,18 @@ void kill_instruction(struct instruction *insn)
 		repeat_phase |= REPEAT_CSE;
 		return;
 
-	 case OP_SYMADDR:
-	 	insn->bb = NULL;
-	 	repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
-	 	return;
+	case OP_SYMADDR:
+		insn->bb = NULL;
+		repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
+		return;
+
+	case OP_RANGE:
+		insn->bb = NULL;
+		repeat_phase |= REPEAT_CSE;
+		kill_use(&insn->src1);
+		kill_use(&insn->src2);
+		kill_use(&insn->src3);
+		return;
 	}
 }
 
@@ -631,6 +639,24 @@ static int simplify_select(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_range(struct instruction *insn)
+{
+	pseudo_t src1, src2, src3;
+
+	src1 = insn->src1;
+	src2 = insn->src2;
+	src3 = insn->src3;
+	if (src2->type != PSEUDO_VAL || src2->type != PSEUDO_VAL)
+		return 0;
+	if (src1->type == PSEUDO_VAL) {
+		if (src1->value >= src2->value && src1->value <= src3->value) {
+			kill_instruction(insn);
+			return REPEAT_CSE;
+		}
+	}
+	return 0;
+}
+
 /*
  * Simplify "set_ne/eq $0 + br"
  */
@@ -802,6 +828,8 @@ int simplify_instruction(struct instruction *insn)
 		return simplify_branch(insn);
 	case OP_SWITCH:
 		return simplify_switch(insn);
+	case OP_RANGE:
+		return simplify_range(insn);
 	}
 	return 0;
 }