gawk-4.2.1-001-remove-the-tail-recursion-optimization.patch

   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.
   5
   6 ---
   7  awk.h                |  4 ----
   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
  18
  19 diff --git a/awk.h b/awk.h
  20 index 3b351c2..36e71f2 100644
  21 --- a/awk.h
  22 +++ b/awk.h
  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
  28
  29  /* Node_var: */
  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
  34
  35 -/* Op_func_call */
  36 -#define tail_call      d.dl
  37 -
  38  /* Op_subscript */
  39  #define sub_count       d.dl
  40
  41 diff --git a/awkgram.y b/awkgram.y
  42 index ad830a5..caed09e 100644
  43 --- a/awkgram.y
  44 +++ b/awkgram.y
  45 @@ -993,20 +993,9 @@ non_compound_stmt
  46                         $$ = list_create($1);
  47                         (void) list_prepend($$, instruction(Op_push_i));
  48                         $$->nexti->memory = dupnode(Nnull_string);
  49 -               } else {
  50 -                       if (do_optimize
  51 -                               && $3->lasti->opcode == Op_func_call
  52 -                               && strcmp($3->lasti->func_name, in_function) == 0
  53 -                       ) {
  54 -                               /* Do tail recursion optimization. Tail
  55 -                                * call without a return value is recognized
  56 -                                * in mk_function().
  57 -                                */
  58 -                               ($3->lasti + 1)->tail_call = true;
  59 -                       }
  60 -
  61 +               } else
  62                         $$ = list_append($3, $1);
  63 -               }
  64 +
  65                 $$ = add_pending_comment($$);
  66           }
  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);
  71
  72 -       if (do_optimize && def->lasti->opcode == Op_pop) {
  73 -               /* tail call which does not return any value. */
  74 -
  75 -               INSTRUCTION *t;
  76 -
  77 -               for (t = def->nexti; t->nexti != def->lasti; t = t->nexti)
  78 -                       ;
  79 -               if (t->opcode == Op_func_call
  80 -                   && strcmp(t->func_name, thisfunc->vname) == 0)
  81 -                       (t + 1)->tail_call = true;
  82 -       }
  83 -
  84         /* add any pre-function comment to start of action for profile.c  */
  85
  86         if (function_comment != NULL) {
  87 diff --git a/eval.c b/eval.c
  88 index 6ece236..34ba174 100644
  89 --- a/eval.c
  90 +++ b/eval.c
  91 @@ -674,7 +674,7 @@ void
  92  dump_fcall_stack(FILE *fp)
  93  {
  94         NODE *f, *func;
  95 -       long i = 0, j, k = 0;
  96 +       long i = 0, k = 0;
  97
  98         if (fcall_count == 0)
  99                 return;
 100 @@ -682,15 +682,13 @@ dump_fcall_stack(FILE *fp)
 101
 102         /* current frame */
 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);
 107
 108         /* outer frames except main */
 109         for (i = 1; i < fcall_count; i++) {
 110                 f = fcall_list[i];
 111                 func = f->func_node;
 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);
 115         }
 116
 117         fprintf(fp, "\t# %3ld. -- main --\n", k);
 118 @@ -1242,38 +1240,16 @@ setup_frame(INSTRUCTION *pc)
 119         NODE *m, *f, *fp;
 120         NODE **sp = NULL;
 121         int pcount, arg_count, i, j;
 122 -       bool tail_optimize = false;
 123
 124         f = pc->func_body;
 125         pcount = f->param_cnt;
 126         fp = f->fparms;
 127         arg_count = (pc + 1)->expr_count;
 128
 129 -       /* tail recursion optimization */
 130 -       tail_optimize =  ((pc + 1)->tail_call && do_optimize
 131 -                               && ! do_debug && ! do_profile);
 132 -
 133 -       if (tail_optimize) {
 134 -               /* free local vars of calling frame */
 135 -
 136 -               NODE *func;
 137 -               int n;
 138 -
 139 -               func = frame_ptr->func_node;
 140 -               for (n = func->param_cnt, sp = frame_ptr->stack; n > 0; n--) {
 141 -                       r = *sp++;
 142 -                       if (r->type == Node_var)     /* local variable */
 143 -                               DEREF(r->var_value);
 144 -                       else if (r->type == Node_var_array)     /* local array */
 145 -                               assoc_clear(r);
 146 -               }
 147 -               sp = frame_ptr->stack;
 148 -
 149 -       } else if (pcount > 0) {
 150 +       if (pcount > 0) {
 151                 ezalloc(sp, NODE **, pcount * sizeof(NODE *), "setup_frame");
 152         }
 153
 154 -
 155         /* check for extra args */
 156         if (arg_count > pcount) {
 157                 warning(
 158 @@ -1287,13 +1263,9 @@ setup_frame(INSTRUCTION *pc)
 159         }
 160
 161         for (i = 0, j = arg_count - 1; i < pcount; i++, j--) {
 162 -               if (tail_optimize)
 163 -                       r = sp[i];
 164 -               else {
 165 -                       getnode(r);
 166 -                       memset(r, 0, sizeof(NODE));
 167 -                       sp[i] = r;
 168 -               }
 169 +               getnode(r);
 170 +               memset(r, 0, sizeof(NODE));
 171 +               sp[i] = r;
 172
 173                 if (i >= arg_count) {
 174                         /* local variable */
 175 @@ -1348,11 +1320,6 @@ setup_frame(INSTRUCTION *pc)
 176
 177         stack_adj(-arg_count);  /* adjust stack pointer */
 178
 179 -       if (tail_optimize) {
 180 -               frame_ptr->num_tail_calls++;
 181 -               return f->code_ptr;
 182 -       }
 183 -
 184         if (pc->opcode == Op_indirect_func_call) {
 185                 r = POP();      /* indirect var */
 186                 DEREF(r);
 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 */
 194
 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;
 201
 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 = \
 208         synerr1.ok \
 209         synerr2.awk \
 210         synerr2.ok \
 211 +       tailrecurse.awk \
 212 +       tailrecurse.ok \
 213         testext.ok \
 214         time.awk \
 215         time.ok \
 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 = \
 230         synerr1.ok \
 231         synerr2.awk \
 232         synerr2.ok \
 233 +       tailrecurse.awk \
 234 +       tailrecurse.ok \
 235         testext.ok \
 236         time.awk \
 237         time.ok \
 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 _$@
 250
 251 +tailrecurse:
 252 +       @echo $@
 253 +       @AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 254 +       @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 255 +
 256  uninit2:
 257         @echo $@
 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
 261 --- a/test/Maketests
 262 +++ b/test/Maketests
 263 @@ -1002,6 +1002,11 @@ synerr2:
 264         @AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 265         @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 266
 267 +tailrecurse:
 268 +       @echo $@
 269 +       @AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 270 +       @-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 271 +
 272  uninit2:
 273         @echo $@
 274         @AWKPATH="$(srcdir)" $(AWK) -f $@.awk  --lint >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 275 diff --git a/test/tailrecurse.awk b/test/tailrecurse.awk
 276 new file mode 100644
 277 index 0000000..b287d16
 278 --- /dev/null
 279 +++ b/test/tailrecurse.awk
 280 @@ -0,0 +1,15 @@
 281 +BEGIN {
 282 +       abc(2)
 283 +}
 284 +
 285 +
 286 +function abc(c, A, B)
 287 +{
 288 +       print "abc(" c ", " length(A) ")"
 289 +       if (! c--) {
 290 +               return
 291 +       }
 292 +       B[""]
 293 +       print length(B)
 294 +       return abc(c, B)
 295 +}
 296 diff --git a/test/tailrecurse.ok b/test/tailrecurse.ok
 297 new file mode 100644
 298 index 0000000..73ce1ed
 299 --- /dev/null
 300 +++ b/test/tailrecurse.ok
 301 @@ -0,0 +1,5 @@
 302 +abc(2, 0)
 303 +1
 304 +abc(1, 1)
 305 +1
 306 +abc(0, 1)
 307 --
 308 2.14.4
 309