[PATCH 0/2] simplify for-statement & make struct statement smaller

[PATCH 0/2] simplify for-statement & make struct statement smaller

[Luc Van Oostenryck]

The goal of this two patches series is to make struct statement
smaller via a slight change in how for-statement's AST is build. 

On a 64bit machine the size of the struct, which was 80, is now
a round 64 bytes, 20% thus (but admittingly, the effect on the
total memory is quite small since statements represent less than
2% of the total memory used).

Note: this series is part of a larger effort to decrease the amount
      of memory used by sparse.


Luc Van Oostenryck (2):
  avoid some struct symbol member for for-statements
  make for-loop statement simpler

 ast-inspect.c  |  2 --
 compile-i386.c |  3 ---
 dissect.c      |  2 --
 evaluate.c     |  2 --
 expand.c       |  1 -
 inline.c       |  3 ---
 linearize.c    |  8 --------
 parse.c        | 30 +++++++++++++++++++++++-------
 parse.h        |  2 --
 show-parse.c   |  3 ---
 10 files changed, 23 insertions(+), 33 deletions(-)

-- 
2.13.0

      statements:   125292,   10023360,   10059776,  99.64%,    80.00
           total:  5725865,  563383738,  566362112,  99.47%,    98.39

      statements:   126693,    8108352,    8126464,  99.78%,    64.00
           total:  5891718,  430096434,  431620096,  99.65%,    73.00

[PATCH 1/2] avoid some struct symbol member for for-statements

[Luc Van Oostenryck]

The for-statement needs a lot of fields in struct statement, much
more than any other statement. This is due to the complexity of
the for-statement.

The possibility in C99 to declare variables in the initialization
part of the statement add yet another field to hold the declared
symbols. However, these symbols doesn't need a lis of their own,
they can simply be put in the list of a STMT_DECLARATION used
as the 'pre-' statement of a classic for-statement.

Merge the symbols list with the pre-statement.

Note: The motivation for this change is to make struct statement
      smaller. The change also make further processing slightly
      simpler since we don't have to process the declaration
      separately.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 compile-i386.c |  1 -
 dissect.c      |  1 -
 evaluate.c     |  1 -
 inline.c       |  2 --
 linearize.c    |  6 ------
 parse.c        | 22 +++++++++++++++-------
 parse.h        |  1 -
 show-parse.c   |  1 -
 8 files changed, 15 insertions(+), 20 deletions(-)

diff --git a/compile-i386.c b/compile-i386.c
index 24e408baa..de252c8f9 100644
--- a/compile-i386.c
+++ b/compile-i386.c
@@ -1926,7 +1926,6 @@ static void emit_loop(struct statement *stmt)
 	loop_continue = new_label();
 	loopstk_push(loop_continue, loop_bottom);
 
-	x86_symbol_decl(stmt->iterator_syms);
 	x86_statement(pre_statement);
 	if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
 		loop_top = new_label();
diff --git a/dissect.c b/dissect.c
index 5f067eb4c..9f823980d 100644
--- a/dissect.c
+++ b/dissect.c
@@ -494,7 +494,6 @@ static struct symbol *do_statement(usage_t mode, struct statement *stmt)
 	}
 
 	break; case STMT_ITERATOR:
-		do_sym_list(stmt->iterator_syms);
 		do_statement(U_VOID, stmt->iterator_pre_statement);
 		do_expression(U_R_VAL, stmt->iterator_pre_condition);
 		do_statement(U_VOID, stmt->iterator_post_statement);
diff --git a/evaluate.c b/evaluate.c
index cf3cf244d..e5b3b5904 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -3279,7 +3279,6 @@ static void evaluate_if_statement(struct statement *stmt)
 
 static void evaluate_iterator(struct statement *stmt)
 {
-	evaluate_symbol_list(stmt->iterator_syms);
 	evaluate_conditional(stmt->iterator_pre_condition, 1);
 	evaluate_conditional(stmt->iterator_post_condition,1);
 	evaluate_statement(stmt->iterator_pre_statement);
diff --git a/inline.c b/inline.c
index a3002c6bd..dec07a25c 100644
--- a/inline.c
+++ b/inline.c
@@ -421,8 +421,6 @@ static struct statement *copy_one_statement(struct statement *stmt)
 		stmt = dup_statement(stmt);
 		stmt->iterator_break = copy_symbol(stmt->pos, stmt->iterator_break);
 		stmt->iterator_continue = copy_symbol(stmt->pos, stmt->iterator_continue);
-		stmt->iterator_syms = copy_symbol_list(stmt->iterator_syms);
-
 		stmt->iterator_pre_statement = copy_one_statement(stmt->iterator_pre_statement);
 		stmt->iterator_pre_condition = copy_expression(stmt->iterator_pre_condition);
 
diff --git a/linearize.c b/linearize.c
index 7313e72d8..6d0695a18 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2000,12 +2000,6 @@ static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt
 	struct statement  *post_statement = stmt->iterator_post_statement;
 	struct expression *post_condition = stmt->iterator_post_condition;
 	struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
-	struct symbol *sym;
-
-	FOR_EACH_PTR(stmt->iterator_syms, sym) {
-		linearize_one_symbol(ep, sym);
-	} END_FOR_EACH_PTR(sym);
-	concat_symbol_list(stmt->iterator_syms, &ep->syms);
 	linearize_statement(ep, pre_statement);
 
 	loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
diff --git a/parse.c b/parse.c
index 214547904..e063dae99 100644
--- a/parse.c
+++ b/parse.c
@@ -2282,36 +2282,44 @@ static void validate_for_loop_decl(struct symbol *sym)
 
 static struct token *parse_for_statement(struct token *token, struct statement *stmt)
 {
-	struct symbol_list *syms;
-	struct expression *e1, *e2, *e3;
+	struct expression *e2, *e3;
 	struct statement *iterator;
+	struct statement *pre = NULL;
 
-	start_iterator(stmt);
 	token = expect(token->next, '(', "after 'for'");
 
-	syms = NULL;
-	e1 = NULL;
 	/* C99 variable declaration? */
 	if (lookup_type(token)) {
+		struct symbol_list *syms = NULL;
+		struct position pos = token->pos;
+		start_symbol_scope();
 		token = external_declaration(token, &syms, validate_for_loop_decl);
+		pre = alloc_statement(pos, STMT_DECLARATION);
+		pre->declaration = syms;
 	} else {
+		struct expression *e1 = NULL;
 		token = parse_expression(token, &e1);
 		token = expect(token, ';', "in 'for'");
+		pre = make_statement(e1);
 	}
+
+	start_iterator(stmt);
 	token = parse_expression(token, &e2);
 	token = expect(token, ';', "in 'for'");
 	token = parse_expression(token, &e3);
 	token = expect(token, ')', "in 'for'");
 	token = statement(token, &iterator);
 
-	stmt->iterator_syms = syms;
-	stmt->iterator_pre_statement = make_statement(e1);
+	stmt->iterator_pre_statement = pre;
 	stmt->iterator_pre_condition = e2;
 	stmt->iterator_post_statement = make_statement(e3);
 	stmt->iterator_post_condition = NULL;
 	stmt->iterator_statement = iterator;
 	end_iterator(stmt);
 
+	if (pre && pre->type == STMT_DECLARATION)
+		end_symbol_scope();
+
 	return token;
 }
 
diff --git a/parse.h b/parse.h
index 26227a387..e01497096 100644
--- a/parse.h
+++ b/parse.h
@@ -88,7 +88,6 @@ struct statement {
 		struct /* iterator_struct */ {
 			struct symbol *iterator_break;
 			struct symbol *iterator_continue;
-			struct symbol_list *iterator_syms;
 			struct statement  *iterator_pre_statement;
 			struct expression *iterator_pre_condition;
 
diff --git a/show-parse.c b/show-parse.c
index 5e3e13165..6801a68e2 100644
--- a/show-parse.c
+++ b/show-parse.c
@@ -633,7 +633,6 @@ int show_statement(struct statement *stmt)
 		struct expression *post_condition = stmt->iterator_post_condition;
 		int val, loop_top = 0, loop_bottom = 0;
 
-		show_symbol_decl(stmt->iterator_syms);
 		show_statement(pre_statement);
 		if (pre_condition) {
 			if (pre_condition->type == EXPR_VALUE) {
-- 
2.13.0

[PATCH 2/2] make for-loop statement simpler

[Luc Van Oostenryck]

The for-statement needs a lot of fields in struct statement, much
more than any other statement. This is due to the complexity of
the for-statement.

However part of this complexity can be removed by processing the
'pre-' statement separately from the loop. This is equivalent to
transform a single-statement for-loop like:
	for (pre; cond; post)
		body
into a compound statement like:
	pre;
	for (;cond; post)
		body;

Note: The motivation for this change is to make struct statement
      smaller. The change also make further processing slightly
      simpler since we don't have to process the 'pre-' statement
      separately.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ast-inspect.c  |  2 --
 compile-i386.c |  2 --
 dissect.c      |  1 -
 evaluate.c     |  1 -
 expand.c       |  1 -
 inline.c       |  1 -
 linearize.c    |  2 --
 parse.c        | 10 +++++++++-
 parse.h        |  1 -
 show-parse.c   |  2 --
 10 files changed, 9 insertions(+), 14 deletions(-)

diff --git a/ast-inspect.c b/ast-inspect.c
index 24d4a4a65..e25e9d097 100644
--- a/ast-inspect.c
+++ b/ast-inspect.c
@@ -59,8 +59,6 @@ void inspect_statement(AstNode *node)
 		case STMT_ITERATOR:
 			ast_append_child(node, "break:", stmt->iterator_break, inspect_symbol);
 			ast_append_child(node, "continue:", stmt->iterator_continue, inspect_symbol);
-			ast_append_child(node, "pre_statement:", stmt->iterator_pre_statement,
-					 inspect_statement);
 			ast_append_child(node, "statement:", stmt->iterator_statement,
 					 inspect_statement);
 			ast_append_child(node, "post_statement:", stmt->iterator_post_statement,
diff --git a/compile-i386.c b/compile-i386.c
index de252c8f9..c5e2309ce 100644
--- a/compile-i386.c
+++ b/compile-i386.c
@@ -1913,7 +1913,6 @@ static int loopstk_continue(void)
 
 static void emit_loop(struct statement *stmt)
 {
-	struct statement  *pre_statement = stmt->iterator_pre_statement;
 	struct expression *pre_condition = stmt->iterator_pre_condition;
 	struct statement  *statement = stmt->iterator_statement;
 	struct statement  *post_statement = stmt->iterator_post_statement;
@@ -1926,7 +1925,6 @@ static void emit_loop(struct statement *stmt)
 	loop_continue = new_label();
 	loopstk_push(loop_continue, loop_bottom);
 
-	x86_statement(pre_statement);
 	if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
 		loop_top = new_label();
 		emit_label(loop_top, "loop top");
diff --git a/dissect.c b/dissect.c
index 9f823980d..fb3ae9167 100644
--- a/dissect.c
+++ b/dissect.c
@@ -494,7 +494,6 @@ static struct symbol *do_statement(usage_t mode, struct statement *stmt)
 	}
 
 	break; case STMT_ITERATOR:
-		do_statement(U_VOID, stmt->iterator_pre_statement);
 		do_expression(U_R_VAL, stmt->iterator_pre_condition);
 		do_statement(U_VOID, stmt->iterator_post_statement);
 		do_statement(U_VOID, stmt->iterator_statement);
diff --git a/evaluate.c b/evaluate.c
index e5b3b5904..a2e356f0b 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -3281,7 +3281,6 @@ static void evaluate_iterator(struct statement *stmt)
 {
 	evaluate_conditional(stmt->iterator_pre_condition, 1);
 	evaluate_conditional(stmt->iterator_post_condition,1);
-	evaluate_statement(stmt->iterator_pre_statement);
 	evaluate_statement(stmt->iterator_statement);
 	evaluate_statement(stmt->iterator_post_statement);
 }
diff --git a/expand.c b/expand.c
index 5f908c971..27df8baf9 100644
--- a/expand.c
+++ b/expand.c
@@ -1180,7 +1180,6 @@ static int expand_statement(struct statement *stmt)
 	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 SIDE_EFFECTS;
diff --git a/inline.c b/inline.c
index dec07a25c..a5ae22c2b 100644
--- a/inline.c
+++ b/inline.c
@@ -421,7 +421,6 @@ static struct statement *copy_one_statement(struct statement *stmt)
 		stmt = dup_statement(stmt);
 		stmt->iterator_break = copy_symbol(stmt->pos, stmt->iterator_break);
 		stmt->iterator_continue = copy_symbol(stmt->pos, stmt->iterator_continue);
-		stmt->iterator_pre_statement = copy_one_statement(stmt->iterator_pre_statement);
 		stmt->iterator_pre_condition = copy_expression(stmt->iterator_pre_condition);
 
 		stmt->iterator_statement = copy_one_statement(stmt->iterator_statement);
diff --git a/linearize.c b/linearize.c
index 6d0695a18..f0057bec0 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1994,13 +1994,11 @@ static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
 
 static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt)
 {
-	struct statement  *pre_statement = stmt->iterator_pre_statement;
 	struct expression *pre_condition = stmt->iterator_pre_condition;
 	struct statement  *statement = stmt->iterator_statement;
 	struct statement  *post_statement = stmt->iterator_post_statement;
 	struct expression *post_condition = stmt->iterator_post_condition;
 	struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
-	linearize_statement(ep, pre_statement);
 
 	loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
 	loop_continue = alloc_basic_block(ep, stmt->pos);
diff --git a/parse.c b/parse.c
index e063dae99..ea8e3de19 100644
--- a/parse.c
+++ b/parse.c
@@ -2284,6 +2284,7 @@ static struct token *parse_for_statement(struct token *token, struct statement *
 {
 	struct expression *e2, *e3;
 	struct statement *iterator;
+	struct statement *compound;
 	struct statement *pre = NULL;
 
 	token = expect(token->next, '(', "after 'for'");
@@ -2303,6 +2304,14 @@ static struct token *parse_for_statement(struct token *token, struct statement *
 		pre = make_statement(e1);
 	}
 
+	if (pre) {
+		compound = stmt;
+		compound->type = STMT_COMPOUND;
+		stmt = alloc_statement(token->pos, STMT_ITERATOR);
+		add_statement(&compound->stmts, pre);
+		add_statement(&compound->stmts, stmt);
+	}
+
 	start_iterator(stmt);
 	token = parse_expression(token, &e2);
 	token = expect(token, ';', "in 'for'");
@@ -2310,7 +2319,6 @@ static struct token *parse_for_statement(struct token *token, struct statement *
 	token = expect(token, ')', "in 'for'");
 	token = statement(token, &iterator);
 
-	stmt->iterator_pre_statement = pre;
 	stmt->iterator_pre_condition = e2;
 	stmt->iterator_post_statement = make_statement(e3);
 	stmt->iterator_post_condition = NULL;
diff --git a/parse.h b/parse.h
index e01497096..5220f3af0 100644
--- a/parse.h
+++ b/parse.h
@@ -88,7 +88,6 @@ struct statement {
 		struct /* iterator_struct */ {
 			struct symbol *iterator_break;
 			struct symbol *iterator_continue;
-			struct statement  *iterator_pre_statement;
 			struct expression *iterator_pre_condition;
 
 			struct statement  *iterator_statement;
diff --git a/show-parse.c b/show-parse.c
index 6801a68e2..cbd93b21c 100644
--- a/show-parse.c
+++ b/show-parse.c
@@ -626,14 +626,12 @@ int show_statement(struct statement *stmt)
 		break;
 
 	case STMT_ITERATOR: {
-		struct statement  *pre_statement = stmt->iterator_pre_statement;
 		struct expression *pre_condition = stmt->iterator_pre_condition;
 		struct statement  *statement = stmt->iterator_statement;
 		struct statement  *post_statement = stmt->iterator_post_statement;
 		struct expression *post_condition = stmt->iterator_post_condition;
 		int val, loop_top = 0, loop_bottom = 0;
 
-		show_statement(pre_statement);
 		if (pre_condition) {
 			if (pre_condition->type == EXPR_VALUE) {
 				if (!pre_condition->value) {
-- 
2.13.0

Re: [PATCH 2/2] make for-loop statement simpler

[Christopher Li]

On Wed, Jun 28, 2017 at 1:49 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The for-statement needs a lot of fields in struct statement, much
> more than any other statement. This is due to the complexity of
> the for-statement.
>
> However part of this complexity can be removed by processing the
> 'pre-' statement separately from the loop. This is equivalent to
> transform a single-statement for-loop like:
>         for (pre; cond; post)
>                 body
> into a compound statement like:
>         pre;
>         for (;cond; post)
>                 body;

Notice that the two are not exactly the same.

quote 6.8.5 3"The declaration part of a for statement shall only
declare identifiers for
objects having storage class auto or register."

However sparse already validate the for statement declaration in function
"validate_for_loop_decl()" so I think it is fine.

Chris

Re: [PATCH 2/2] make for-loop statement simpler

[Luc Van Oostenryck]

On Wed, Jun 28, 2017 at 05:18:18PM -0700, Christopher Li wrote:
> On Wed, Jun 28, 2017 at 1:49 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > The for-statement needs a lot of fields in struct statement, much
> > more than any other statement. This is due to the complexity of
> > the for-statement.
> >
> > However part of this complexity can be removed by processing the
> > 'pre-' statement separately from the loop. This is equivalent to
> > transform a single-statement for-loop like:
> >         for (pre; cond; post)
> >                 body
> > into a compound statement like:
> >         pre;
> >         for (;cond; post)
> >                 body;
> 
> Notice that the two are not exactly the same.
> 
> quote 6.8.5 3"The declaration part of a for statement shall only
> declare identifiers for
> objects having storage class auto or register."
> 
> However sparse already validate the for statement declaration in function
> "validate_for_loop_decl()" so I think it is fine.

Yes, and the patch take care of the scope too.

-- Luc

Re: [PATCH 2/2] make for-loop statement simpler

[Bernd Petrovitsch]

On Thu, 2017-06-29 at 05:18 +0200, Luc Van Oostenryck wrote:
> On Wed, Jun 28, 2017 at 05:18:18PM -0700, Christopher Li wrote:
> > On Wed, Jun 28, 2017 at 1:49 PM, Luc Van Oostenryck
> > <luc.vanoostenryck@gmail.com> wrote:
> > > The for-statement needs a lot of fields in struct statement, much
> > > more than any other statement. This is due to the complexity of
> > > the for-statement.
> > > 
> > > However part of this complexity can be removed by processing the
> > > 'pre-' statement separately from the loop. This is equivalent to
> > > transform a single-statement for-loop like:
> > >         for (pre; cond; post)
> > >                 body
> > > into a compound statement like:
> > >         pre;
> > >         for (;cond; post)
> > >                 body;
> > 
> > Notice that the two are not exactly the same.
[...]
> Yes, and the patch take care of the scope too.
Just update the explanation to
----  snip  ----
transform a single-statement for-loop like:
        for (pre; cond; post)
                body
into a compound statement like:
{
        pre;
        for (;cond; post)
                body;
}
----  snip  ----
which makes it identical.

MfG,
	Bernd
-- 
Bernd Petrovitsch                  Email : bernd@petrovitsch.priv.at
                     LUGA : http://www.luga.at