--- /dev/null
+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
+
projects / packages / gawk.git / blobdiff