From 47316d294571673a8dbf1e9e435893e2660f46a8 Mon Sep 17 00:00:00 2001 From: "Arnold D. Robbins" 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