1 From 47316d294571673a8dbf1e9e435893e2660f46a8 Mon Sep 17 00:00:00 2001
2 From: "Arnold D. Robbins" <arnold@skeeve.com>
3 Date: Mon, 26 Mar 2018 10:45:01 +0300
4 Subject: [PATCH] Remove the tail recursion optimization.
8 awkgram.y | 27 ++-------------------------
9 eval.c | 49 +++++++------------------------------------------
10 test/Makefile.am | 4 +++-
11 test/Makefile.in | 9 ++++++++-
12 test/Maketests | 5 +++++
13 test/tailrecurse.awk | 15 +++++++++++++++
14 test/tailrecurse.ok | 5 +++++
15 8 files changed, 45 insertions(+), 73 deletions(-)
16 create mode 100644 test/tailrecurse.awk
17 create mode 100644 test/tailrecurse.ok
19 diff --git a/awk.h b/awk.h
20 index 3b351c2..36e71f2 100644
23 @@ -527,7 +527,6 @@ typedef struct exp_node {
24 #define func_node sub.nodep.x.extra
25 #define prev_frame_size sub.nodep.reflags
26 #define reti sub.nodep.l.li
27 -#define num_tail_calls sub.nodep.cnt
30 #define var_value lnode
31 @@ -862,9 +861,6 @@ typedef struct exp_instruction {
32 /* Op_func_call, Op_func */
33 #define func_body x.xn
36 -#define tail_call d.dl
39 #define sub_count d.dl
41 diff --git a/awkgram.y b/awkgram.y
42 index ad830a5..caed09e 100644
45 @@ -993,20 +993,9 @@ non_compound_stmt
47 (void) list_prepend($$, instruction(Op_push_i));
48 $$->nexti->memory = dupnode(Nnull_string);
51 - && $3->lasti->opcode == Op_func_call
52 - && strcmp($3->lasti->func_name, in_function) == 0
54 - /* Do tail recursion optimization. Tail
55 - * call without a return value is recognized
58 - ($3->lasti + 1)->tail_call = true;
62 $$ = list_append($3, $1);
65 $$ = add_pending_comment($$);
67 | simple_stmt statement_term
68 @@ -4736,18 +4725,6 @@ mk_function(INSTRUCTION *fi, INSTRUCTION *def)
69 thisfunc = fi->func_body;
70 assert(thisfunc != NULL);
72 - if (do_optimize && def->lasti->opcode == Op_pop) {
73 - /* tail call which does not return any value. */
77 - for (t = def->nexti; t->nexti != def->lasti; t = t->nexti)
79 - if (t->opcode == Op_func_call
80 - && strcmp(t->func_name, thisfunc->vname) == 0)
81 - (t + 1)->tail_call = true;
84 /* add any pre-function comment to start of action for profile.c */
86 if (function_comment != NULL) {
87 diff --git a/eval.c b/eval.c
88 index 6ece236..34ba174 100644
91 @@ -674,7 +674,7 @@ void
92 dump_fcall_stack(FILE *fp)
95 - long i = 0, j, k = 0;
100 @@ -682,15 +682,13 @@ dump_fcall_stack(FILE *fp)
103 func = frame_ptr->func_node;
104 - for (j = 0; j <= frame_ptr->num_tail_calls; j++)
105 - fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
106 + fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
108 /* outer frames except main */
109 for (i = 1; i < fcall_count; i++) {
112 - for (j = 0; j <= f->num_tail_calls; j++)
113 - fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
114 + fprintf(fp, "\t# %3ld. %s\n", k++, func->vname);
117 fprintf(fp, "\t# %3ld. -- main --\n", k);
118 @@ -1242,38 +1240,16 @@ setup_frame(INSTRUCTION *pc)
121 int pcount, arg_count, i, j;
122 - bool tail_optimize = false;
125 pcount = f->param_cnt;
127 arg_count = (pc + 1)->expr_count;
129 - /* tail recursion optimization */
130 - tail_optimize = ((pc + 1)->tail_call && do_optimize
131 - && ! do_debug && ! do_profile);
133 - if (tail_optimize) {
134 - /* free local vars of calling frame */
139 - func = frame_ptr->func_node;
140 - for (n = func->param_cnt, sp = frame_ptr->stack; n > 0; n--) {
142 - if (r->type == Node_var) /* local variable */
143 - DEREF(r->var_value);
144 - else if (r->type == Node_var_array) /* local array */
147 - sp = frame_ptr->stack;
149 - } else if (pcount > 0) {
151 ezalloc(sp, NODE **, pcount * sizeof(NODE *), "setup_frame");
155 /* check for extra args */
156 if (arg_count > pcount) {
158 @@ -1287,13 +1263,9 @@ setup_frame(INSTRUCTION *pc)
161 for (i = 0, j = arg_count - 1; i < pcount; i++, j--) {
166 - memset(r, 0, sizeof(NODE));
170 + memset(r, 0, sizeof(NODE));
173 if (i >= arg_count) {
175 @@ -1348,11 +1320,6 @@ setup_frame(INSTRUCTION *pc)
177 stack_adj(-arg_count); /* adjust stack pointer */
179 - if (tail_optimize) {
180 - frame_ptr->num_tail_calls++;
181 - return f->code_ptr;
184 if (pc->opcode == Op_indirect_func_call) {
185 r = POP(); /* indirect var */
187 @@ -1372,7 +1339,6 @@ setup_frame(INSTRUCTION *pc)
188 frame_ptr->stack = sp;
189 frame_ptr->prev_frame_size = (stack_ptr - stack_bottom); /* size of the previous stack frame */
190 frame_ptr->func_node = f;
191 - frame_ptr->num_tail_calls = 0;
192 frame_ptr->vname = NULL;
193 frame_ptr->reti = pc; /* on return execute pc->nexti */
195 @@ -1774,7 +1740,6 @@ init_interpret()
196 frame_ptr->type = Node_frame;
197 frame_ptr->stack = NULL;
198 frame_ptr->func_node = NULL; /* in main */
199 - frame_ptr->num_tail_calls = 0;
200 frame_ptr->vname = NULL;
202 /* initialize true and false nodes */
203 diff --git a/test/Makefile.am b/test/Makefile.am
204 index bf1dbd3..40e25b2 100644
205 --- a/test/Makefile.am
206 +++ b/test/Makefile.am
207 @@ -1134,6 +1134,8 @@ EXTRA_DIST = \
216 @@ -1253,7 +1255,7 @@ BASIC_TESTS = \
217 sigpipe1 sortempty sortglos splitargv splitarr \
218 splitdef splitvar splitwht status-close strcat1 strnum1 strnum2 strtod \
219 subamp subback subi18n subsepnm subslash substr swaplns synerr1 synerr2 \
220 - tradanch tweakfld \
221 + tailrecurse tradanch tweakfld \
222 uninit2 uninit3 uninit4 uninit5 uninitialized unterm uparrfs uplus \
223 wideidx wideidx2 widesub widesub2 widesub3 widesub4 wjposer1 \
224 zero2 zeroe0 zeroflag
225 diff --git a/test/Makefile.in b/test/Makefile.in
226 index f96151b..74405f8 100644
227 --- a/test/Makefile.in
228 +++ b/test/Makefile.in
229 @@ -1392,6 +1392,8 @@ EXTRA_DIST = \
238 @@ -1510,7 +1512,7 @@ BASIC_TESTS = \
239 sigpipe1 sortempty sortglos splitargv splitarr \
240 splitdef splitvar splitwht status-close strcat1 strnum1 strnum2 strtod \
241 subamp subback subi18n subsepnm subslash substr swaplns synerr1 synerr2 \
242 - tradanch tweakfld \
243 + tailrecurse tradanch tweakfld \
244 uninit2 uninit3 uninit4 uninit5 uninitialized unterm uparrfs uplus \
245 wideidx wideidx2 widesub widesub2 widesub3 widesub4 wjposer1 \
246 zero2 zeroe0 zeroflag
247 @@ -3919,6 +3921,11 @@ synerr2:
248 @AWKPATH="$(srcdir)" $(AWK) -f $@.awk >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
249 @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
253 + @AWKPATH="$(srcdir)" $(AWK) -f $@.awk >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
254 + @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
258 @AWKPATH="$(srcdir)" $(AWK) -f $@.awk --lint >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
259 diff --git a/test/Maketests b/test/Maketests
260 index e449dd3..4a90e3e 100644
263 @@ -1002,6 +1002,11 @@ synerr2:
264 @AWKPATH="$(srcdir)" $(AWK) -f $@.awk >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
265 @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
269 + @AWKPATH="$(srcdir)" $(AWK) -f $@.awk >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
270 + @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
274 @AWKPATH="$(srcdir)" $(AWK) -f $@.awk --lint >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
275 diff --git a/test/tailrecurse.awk b/test/tailrecurse.awk
277 index 0000000..b287d16
279 +++ b/test/tailrecurse.awk
286 +function abc(c, A, B)
288 + print "abc(" c ", " length(A) ")"
296 diff --git a/test/tailrecurse.ok b/test/tailrecurse.ok
298 index 0000000..73ce1ed
300 +++ b/test/tailrecurse.ok