From 47316d294571673a8dbf1e9e435893e2660f46a8 Mon Sep 17 00:00:00 2001
From: "Arnold D. Robbins" <arnold@skeeve.com>
Date: Mon, 26 Mar 2018 10:45:01 +0300
Subject: [PATCH] Remove the tail recursion optimization.

---
 awk.h                |  4 ----
 awkgram.y            | 27 ++-------------------------
 eval.c               | 49 +++++++------------------------------------------
 test/Makefile.am     |  4 +++-
 test/Makefile.in     |  9 ++++++++-
 test/Maketests       |  5 +++++
 test/tailrecurse.awk | 15 +++++++++++++++
 test/tailrecurse.ok  |  5 +++++
 8 files changed, 45 insertions(+), 73 deletions(-)
 create mode 100644 test/tailrecurse.awk
 create mode 100644 test/tailrecurse.ok

diff --git a/awk.h b/awk.h
index 3b351c2..36e71f2 100644
--- a/awk.h
+++ b/awk.h
@@ -527,7 +527,6 @@ typedef struct exp_node {
 #define func_node    sub.nodep.x.extra
 #define prev_frame_size	sub.nodep.reflags
 #define reti         sub.nodep.l.li
-#define num_tail_calls    sub.nodep.cnt
 
 /* Node_var: */
 #define var_value    lnode
@@ -862,9 +861,6 @@ typedef struct exp_instruction {
 /* Op_func_call, Op_func */
 #define func_body       x.xn
 
-/* Op_func_call */
-#define tail_call	d.dl
-
 /* Op_subscript */
 #define sub_count       d.dl
 
diff --git a/awkgram.y b/awkgram.y
index ad830a5..caed09e 100644
--- a/awkgram.y
+++ b/awkgram.y
@@ -993,20 +993,9 @@ non_compound_stmt
 			$$ = list_create($1);
 			(void) list_prepend($$, instruction(Op_push_i));
 			$$->nexti->memory = dupnode(Nnull_string);
-		} else {
-			if (do_optimize
-				&& $3->lasti->opcode == Op_func_call
-				&& strcmp($3->lasti->func_name, in_function) == 0
-			) {
-				/* Do tail recursion optimization. Tail
-				 * call without a return value is recognized
-				 * in mk_function().
-				 */
-				($3->lasti + 1)->tail_call = true;
-			}
-
+		} else
 			$$ = list_append($3, $1);
-		}
+
 		$$ = add_pending_comment($$);
 	  }
 	| simple_stmt statement_term
@@ -4736,18 +4725,6 @@ mk_function(INSTRUCTION *fi, INSTRUCTION *def)
 	thisfunc = fi->func_body;
 	assert(thisfunc != NULL);
 
-	if (do_optimize && def->lasti->opcode == Op_pop) {
-		/* tail call which does not return any value. */
-
-		INSTRUCTION *t;
-
-		for (t = def->nexti; t->nexti != def->lasti; t = t->nexti)
-			;
-		if (t->opcode == Op_func_call
-		    && strcmp(t->func_name, thisfunc->vname) == 0)
-			(t + 1)->tail_call = true;
-	}
-
 	/* add any pre-function comment to start of action for profile.c  */
 
 	if (function_comment != NULL) {
diff --git a/eval.c b/eval.c
index 6ece236..34ba174 100644
--- a/eval.c
+++ b/eval.c
@@ -674,7 +674,7 @@ void
 dump_fcall_stack(FILE *fp)
 {
 	NODE *f, *func;
-	long i = 0, j, k = 0;
+	long i = 0, k = 0;
 
 	if (fcall_count == 0)
 		return;
@@ -682,15 +682,13 @@ dump_fcall_stack(FILE *fp)
 
 	/* current frame */
 	func = frame_ptr->func_node;
-	for (j = 0; j <= frame_ptr->num_tail_calls; j++)
-		fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
+	fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
 
 	/* outer frames except main */
 	for (i = 1; i < fcall_count; i++) {
 		f = fcall_list[i];
 		func = f->func_node;
-		for (j = 0; j <= f->num_tail_calls; j++)
-			fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
+		fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
 	}
 
 	fprintf(fp, "\t# %3ld. -- main --\n", k);
@@ -1242,38 +1240,16 @@ setup_frame(INSTRUCTION *pc)
 	NODE *m, *f, *fp;
 	NODE **sp = NULL;
 	int pcount, arg_count, i, j;
-	bool tail_optimize = false;
 
 	f = pc->func_body;
 	pcount = f->param_cnt;
 	fp = f->fparms;
 	arg_count = (pc + 1)->expr_count;
 
-	/* tail recursion optimization */
-	tail_optimize =  ((pc + 1)->tail_call && do_optimize
-				&& ! do_debug && ! do_profile);
-
-	if (tail_optimize) {
-		/* free local vars of calling frame */
-
-		NODE *func;
-		int n;
-
-		func = frame_ptr->func_node;
-		for (n = func->param_cnt, sp = frame_ptr->stack; n > 0; n--) {
-			r = *sp++;
-			if (r->type == Node_var)     /* local variable */
-				DEREF(r->var_value);
-			else if (r->type == Node_var_array)     /* local array */
-				assoc_clear(r);
-		}
-		sp = frame_ptr->stack;
-
-	} else if (pcount > 0) {
+	if (pcount > 0) {
 		ezalloc(sp, NODE **, pcount * sizeof(NODE *), "setup_frame");
 	}
 
-
 	/* check for extra args */
 	if (arg_count > pcount) {
 		warning(
@@ -1287,13 +1263,9 @@ setup_frame(INSTRUCTION *pc)
 	}
 
 	for (i = 0, j = arg_count - 1; i < pcount; i++, j--) {
-		if (tail_optimize)
-			r = sp[i];
-		else {
-			getnode(r);
-			memset(r, 0, sizeof(NODE));
-			sp[i] = r;
-		}
+		getnode(r);
+		memset(r, 0, sizeof(NODE));
+		sp[i] = r;
 
 		if (i >= arg_count) {
 			/* local variable */
@@ -1348,11 +1320,6 @@ setup_frame(INSTRUCTION *pc)
 
 	stack_adj(-arg_count);	/* adjust stack pointer */
 
-	if (tail_optimize) {
-		frame_ptr->num_tail_calls++;
-		return f->code_ptr;
-	}
-
 	if (pc->opcode == Op_indirect_func_call) {
 		r = POP();	/* indirect var */
 		DEREF(r);
@@ -1372,7 +1339,6 @@ setup_frame(INSTRUCTION *pc)
 	frame_ptr->stack = sp;
 	frame_ptr->prev_frame_size = (stack_ptr - stack_bottom); /* size of the previous stack frame */
 	frame_ptr->func_node = f;
-	frame_ptr->num_tail_calls = 0;
 	frame_ptr->vname = NULL;
 	frame_ptr->reti = pc; /* on return execute pc->nexti */
 
@@ -1774,7 +1740,6 @@ init_interpret()
 	frame_ptr->type = Node_frame;
 	frame_ptr->stack = NULL;
 	frame_ptr->func_node = NULL;	/* in main */
-	frame_ptr->num_tail_calls = 0;
 	frame_ptr->vname = NULL;
 
 	/* initialize true and false nodes */
diff --git a/test/Makefile.am b/test/Makefile.am
index bf1dbd3..40e25b2 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -1134,6 +1134,8 @@ EXTRA_DIST = \
 	synerr1.ok \
 	synerr2.awk \
 	synerr2.ok \
+	tailrecurse.awk \
+	tailrecurse.ok \
 	testext.ok \
 	time.awk \
 	time.ok \
@@ -1253,7 +1255,7 @@ BASIC_TESTS = \
 	sigpipe1 sortempty sortglos splitargv splitarr \
 	splitdef splitvar splitwht status-close strcat1 strnum1 strnum2 strtod \
 	subamp subback subi18n subsepnm subslash substr swaplns synerr1 synerr2 \
-	tradanch tweakfld \
+	tailrecurse tradanch tweakfld \
 	uninit2 uninit3 uninit4 uninit5 uninitialized unterm uparrfs uplus \
 	wideidx wideidx2 widesub widesub2 widesub3 widesub4 wjposer1 \
 	zero2 zeroe0 zeroflag
diff --git a/test/Makefile.in b/test/Makefile.in
index f96151b..74405f8 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -1392,6 +1392,8 @@ EXTRA_DIST = \
 	synerr1.ok \
 	synerr2.awk \
 	synerr2.ok \
+	tailrecurse.awk \
+	tailrecurse.ok \
 	testext.ok \
 	time.awk \
 	time.ok \
@@ -1510,7 +1512,7 @@ BASIC_TESTS = \
 	sigpipe1 sortempty sortglos splitargv splitarr \
 	splitdef splitvar splitwht status-close strcat1 strnum1 strnum2 strtod \
 	subamp subback subi18n subsepnm subslash substr swaplns synerr1 synerr2 \
-	tradanch tweakfld \
+	tailrecurse tradanch tweakfld \
 	uninit2 uninit3 uninit4 uninit5 uninitialized unterm uparrfs uplus \
 	wideidx wideidx2 widesub widesub2 widesub3 widesub4 wjposer1 \
 	zero2 zeroe0 zeroflag
@@ -3919,6 +3921,11 @@ synerr2:
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 
+tailrecurse:
+	@echo $@
+	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
+	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
+
 uninit2:
 	@echo $@
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  --lint >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
diff --git a/test/Maketests b/test/Maketests
index e449dd3..4a90e3e 100644
--- a/test/Maketests
+++ b/test/Maketests
@@ -1002,6 +1002,11 @@ synerr2:
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 
+tailrecurse:
+	@echo $@
+	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
+	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
+
 uninit2:
 	@echo $@
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  --lint >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
diff --git a/test/tailrecurse.awk b/test/tailrecurse.awk
new file mode 100644
index 0000000..b287d16
--- /dev/null
+++ b/test/tailrecurse.awk
@@ -0,0 +1,15 @@
+BEGIN {
+	abc(2)
+}
+
+
+function abc(c, A, B)
+{
+	print "abc(" c ", " length(A) ")"
+	if (! c--) {
+		return 
+	}
+	B[""]
+	print length(B)
+	return abc(c, B)
+}
diff --git a/test/tailrecurse.ok b/test/tailrecurse.ok
new file mode 100644
index 0000000..73ce1ed
--- /dev/null
+++ b/test/tailrecurse.ok
@@ -0,0 +1,5 @@
+abc(2, 0)
+1
+abc(1, 1)
+1
+abc(0, 1)
-- 
2.14.4

