Manage AST NODEs out of GC

NODEs in AST are no longer objects managed by GC.  This change will
remove the restriction imposed by the GC.  For example, a NODE can use
more than five words (this is my primary purpose; we want to store the
position data for each NODE, for coverage library), or even a NODE can
have variable length (some kinds of NODEs have unused fields).
To do this, however, we need more work, since Ripper still uses T_NODE
objects managed by the GC.

The life time of NODEs is more obvious than other kinds of objects; they
are created at parsing, and they become disused immediately after
compilation.  This change releases all NODEs by a few `xfree`s after
compilation, so performance will be improved a bit.  In extreme example,
`eval("x=1;" * 10000000)` runs much faster (40 sec. -> 7.8 sec. on my
machine).

The most important part of this change is `ast_t` struct, which has
three contents: (1) NODE buffer (malloc'ed memory), (2) a reference to
the root NODE, and (3) an array that contains objects that must be
marked during parsing (such as literal objects).  Some functions that
had received `NODE*` arguments, must now receive `ast_t*`.

* node.c, node.h: defines `ast_t` struct and related operations.
* gc.c, internal.h: defines `imemo_ast`.
* parse.y: makes `parser_params` struct have a reference to `ast_t`.
  Instead of `rb_node_newnode`, use `rb_ast_newnode` to create a NODE.
* iseq.c, load.c, ruby.c, template/prelude.c.tmpl: modifies some
  functions to handle `ast_t*` instead of `NODE*`.
* test/ruby/test_gc.rb: ad-hoc fix for a failed test.  The test assumes
  GC eden is increased at startup by NODE object creation.  However,
  this change now create no NODE object, so GC eden is not necessarily
  increased.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@60485 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

10 files changed, 250 insertions, 68 deletions

diff --git a/gc.c b/gc.c
index 4ba06c2952..48053b66c5 100644
--- a/gc.c
+++ b/gc.c
@@ -434,6 +434,7 @@ typedef struct RVALUE {
 	    const rb_iseq_t iseq;
 	    rb_env_t env;
 	    struct rb_imemo_alloc_struct alloc;
+	    ast_t ast;
 	} imemo;
 	struct {
 	    struct RBasic basic;
@@ -2359,6 +2360,9 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
 	  case imemo_alloc:
 	    xfree(RANY(obj)->as.imemo.alloc.ptr);
 	    break;
+	  case imemo_ast:
+	    rb_ast_free(&RANY(obj)->as.imemo.ast);
+	    break;
 	  default:
 	    break;
 	}
@@ -4540,6 +4544,9 @@ gc_mark_imemo(rb_objspace_t *objspace, VALUE obj)
 	    } while ((m = m->next) != NULL);
 	}
 	return;
+      case imemo_ast:
+	rb_ast_mark(&RANY(obj)->as.imemo.ast);
+	return;
 #if VM_CHECK_MODE > 0
       default:
 	VM_UNREACHABLE(gc_mark_imemo);
diff --git a/internal.h b/internal.h
index fb1f64bb9e..ad29434c7c 100644
--- a/internal.h
+++ b/internal.h
@@ -844,7 +844,8 @@ enum imemo_type {
     imemo_memo       = 5,
     imemo_ment       = 6,
     imemo_iseq       = 7,
-    imemo_alloc      = 8
+    imemo_alloc      = 8,
+    imemo_ast        = 9
 };
 #define IMEMO_MASK   0x0f
 
diff --git a/iseq.c b/iseq.c
index 6047d0017d..0de58c4086 100644
--- a/iseq.c
+++ b/iseq.c
@@ -641,9 +641,9 @@ rb_iseq_compile_with_option(VALUE src, VALUE file, VALUE realpath, VALUE line, c
 #else
 # define INITIALIZED /* volatile */
 #endif
-    NODE *(*parse)(VALUE vparser, VALUE fname, VALUE file, int start);
+    ast_t *(*parse)(VALUE vparser, VALUE fname, VALUE file, int start);
     int ln;
-    NODE *INITIALIZED node;
+    ast_t *INITIALIZED ast;
 
     /* safe results first */
     make_compile_option(&option, opt);
@@ -659,18 +659,20 @@ rb_iseq_compile_with_option(VALUE src, VALUE file, VALUE realpath, VALUE line, c
     {
 	const VALUE parser = rb_parser_new();
 	rb_parser_set_context(parser, base_block, FALSE);
-	node = (*parse)(parser, file, src, ln);
+	ast = (*parse)(parser, file, src, ln);
     }
 
-    if (!node) {
+    if (!ast->root) {
+	rb_ast_dispose(ast);
 	rb_exc_raise(th->ec->errinfo);
     }
     else {
 	INITIALIZED VALUE label = parent ?
 	    parent->body->location.label :
 	    rb_fstring_cstr("<compiled>");
-	iseq = rb_iseq_new_with_opt(node, label, file, realpath, line,
+	iseq = rb_iseq_new_with_opt(ast->root, label, file, realpath, line,
 				    parent, type, &option);
+	rb_ast_dispose(ast);
     }
 
     return iseq;
@@ -851,8 +853,8 @@ static VALUE
 iseqw_s_compile_file(int argc, VALUE *argv, VALUE self)
 {
     VALUE file, line = INT2FIX(1), opt = Qnil;
-    VALUE parser, f, exc = Qnil;
-    const NODE *node;
+    VALUE parser, f, exc = Qnil, ret;
+    ast_t *ast;
     rb_compile_option_t option;
     int i;
 
@@ -869,18 +871,23 @@ iseqw_s_compile_file(int argc, VALUE *argv, VALUE self)
 
     parser = rb_parser_new();
     rb_parser_set_context(parser, NULL, FALSE);
-    node = rb_parser_compile_file_path(parser, file, f, NUM2INT(line));
-    if (!node) exc = GET_EC()->errinfo;
+    ast = rb_parser_compile_file_path(parser, file, f, NUM2INT(line));
+    if (!ast->root) exc = GET_EC()->errinfo;
 
     rb_io_close(f);
-    if (!node) rb_exc_raise(exc);
+    if (!ast->root) {
+	rb_ast_dispose(ast);
+	rb_exc_raise(exc);
+    }
 
     make_compile_option(&option, opt);
 
-    return iseqw_new(rb_iseq_new_with_opt(node, rb_fstring_cstr("<main>"),
-					  file,
-					  rb_realpath_internal(Qnil, file, 1),
-					  line, NULL, ISEQ_TYPE_TOP, &option));
+    ret = iseqw_new(rb_iseq_new_with_opt(ast->root, rb_fstring_cstr("<main>"),
+					 file,
+					 rb_realpath_internal(Qnil, file, 1),
+					 line, NULL, ISEQ_TYPE_TOP, &option));
+    rb_ast_dispose(ast);
+    return ret;
 }
 
 /*
diff --git a/load.c b/load.c
index db09c3384e..8b12c4d64c 100644
--- a/load.c
+++ b/load.c
@@ -602,7 +602,7 @@ rb_load_internal0(rb_thread_t *th, VALUE fname, int wrap)
     EC_PUSH_TAG(th->ec);
     state = EXEC_TAG();
     if (state == TAG_NONE) {
-	NODE *node;
+	ast_t *ast;
 	const rb_iseq_t *iseq;
 
 	if ((iseq = rb_iseq_load_iseq(fname)) != NULL) {
@@ -611,9 +611,10 @@ rb_load_internal0(rb_thread_t *th, VALUE fname, int wrap)
 	else {
 	    VALUE parser = rb_parser_new();
 	    rb_parser_set_context(parser, NULL, FALSE);
-	    node = (NODE *)rb_parser_load_file(parser, fname);
-	    iseq = rb_iseq_new_top(node, rb_fstring_cstr("<top (required)>"),
+	    ast = (ast_t *)rb_parser_load_file(parser, fname);
+	    iseq = rb_iseq_new_top(ast->root, rb_fstring_cstr("<top (required)>"),
 			    fname, rb_realpath_internal(Qnil, fname, 1), NULL);
+	    rb_ast_dispose(ast);
 	}
 	rb_iseq_eval(iseq);
     }
diff --git a/node.c b/node.c
index f6011d585d..d9c115ba3c 100644
--- a/node.c
+++ b/node.c
@@ -1211,3 +1211,107 @@ rb_gc_mark_node(NODE *obj)
     }
     return 0;
 }
+
+typedef struct node_buffer_elem_struct {
+    struct node_buffer_elem_struct *next;
+    NODE buf[1];
+} node_buffer_elem_t;
+
+typedef struct node_buffer_struct {
+    long idx, len;
+    node_buffer_elem_t *head;
+    node_buffer_elem_t body;
+} node_buffer_t;
+
+node_buffer_t *
+rb_node_buffer_new()
+{
+    node_buffer_t *nb = xmalloc(sizeof(node_buffer_t) + 16 * sizeof(NODE));
+    nb->idx = 0;
+    nb->len = 16;
+    nb->head = &nb->body;
+    nb->head->next = NULL;
+    return nb;
+}
+
+void
+rb_node_buffer_free(node_buffer_t *nb)
+{
+    node_buffer_elem_t *nbe = nb->head;
+
+    while (nbe != &nb->body) {
+	void *buf = nbe;
+	nbe = nbe->next;
+	xfree(buf);
+    }
+    xfree(nb);
+}
+
+NODE *
+rb_ast_newnode(ast_t *ast)
+{
+    node_buffer_t *nb = ast->node_buffer;
+    if (nb->idx >= nb->len) {
+	long n = nb->len * 2;
+	node_buffer_elem_t *nbe;
+	nbe = xmalloc(sizeof(node_buffer_elem_t) + n * sizeof(NODE));
+	nb->idx = 0;
+	nb->len = n;
+	nbe->next = nb->head;
+	nb->head = nbe;
+    }
+    return &nb->head->buf[nb->idx++];
+}
+
+void
+rb_ast_delete_node(ast_t *ast, NODE *n)
+{
+    (void)ast;
+    (void)n;
+    /* should we implement freelist? */
+}
+
+ast_t *
+rb_ast_new(void)
+{
+    return (ast_t *)rb_imemo_new(imemo_ast, 0, (VALUE)rb_node_buffer_new(), rb_ary_tmp_new(0), 0);
+}
+
+void
+rb_ast_mark(ast_t *ast)
+{
+    if (ast->node_buffer) rb_gc_mark(ast->mark_ary);
+}
+
+void
+rb_ast_free(ast_t *ast)
+{
+    if (ast->node_buffer) rb_node_buffer_free(ast->node_buffer);
+    ast->node_buffer = 0;
+    ast->root = 0;
+    ast->mark_ary = 0;
+}
+
+void
+rb_ast_dispose(ast_t *ast)
+{
+    rb_ast_free(ast);
+    rb_gc_writebarrier_remember((VALUE)ast);
+}
+
+void
+rb_ast_add_mark_object(ast_t *ast, VALUE obj)
+{
+    rb_ary_push(ast->mark_ary, obj);
+}
+
+void
+rb_ast_delete_mark_object(ast_t *ast, VALUE obj)
+{
+    long i;
+    for (i = 0; i < RARRAY_LEN(ast->mark_ary); i++) {
+	if (obj == RARRAY_AREF(ast->mark_ary, i)) {
+	    RARRAY_ASET(ast->mark_ary, i, Qnil);
+	}
+    }
+}
diff --git a/node.h b/node.h
index 2fb0d53875..23b2bb11f8 100644
--- a/node.h
+++ b/node.h
@@ -439,6 +439,24 @@ typedef struct RNode {
 
 RUBY_SYMBOL_EXPORT_BEGIN
 
+typedef struct node_buffer_struct node_buffer_t;
+/* T_IMEMO/ast */
+typedef struct ast_struct {
+    VALUE flags;
+    VALUE reserved1;
+    NODE *root;
+    node_buffer_t *node_buffer;
+    VALUE mark_ary;
+} ast_t;
+ast_t *rb_ast_new();
+void rb_ast_mark(ast_t*);
+void rb_ast_dispose(ast_t*);
+void rb_ast_free(ast_t*);
+void rb_ast_add_mark_object(ast_t*, VALUE);
+void rb_ast_delete_mark_object(ast_t*, VALUE);
+NODE *rb_ast_newnode(ast_t*);
+void rb_ast_delete_node(ast_t*, NODE *n);
+
 VALUE rb_parser_new(void);
 VALUE rb_parser_end_seen_p(VALUE);
 VALUE rb_parser_encoding(VALUE);
@@ -447,15 +465,15 @@ VALUE rb_parser_set_yydebug(VALUE, VALUE);
 VALUE rb_parser_dump_tree(NODE *node, int comment);
 void rb_parser_set_options(VALUE, int, int, int, int);
 
-NODE *rb_parser_compile_cstr(VALUE, const char*, const char*, int, int);
-NODE *rb_parser_compile_string(VALUE, const char*, VALUE, int);
-NODE *rb_parser_compile_file(VALUE, const char*, VALUE, int);
-NODE *rb_parser_compile_string_path(VALUE vparser, VALUE fname, VALUE src, int line);
-NODE *rb_parser_compile_file_path(VALUE vparser, VALUE fname, VALUE input, int line);
+ast_t *rb_parser_compile_cstr(VALUE, const char*, const char*, int, int);
+ast_t *rb_parser_compile_string(VALUE, const char*, VALUE, int);
+ast_t *rb_parser_compile_file(VALUE, const char*, VALUE, int);
+ast_t *rb_parser_compile_string_path(VALUE vparser, VALUE fname, VALUE src, int line);
+ast_t *rb_parser_compile_file_path(VALUE vparser, VALUE fname, VALUE input, int line);
 
-NODE *rb_compile_cstr(const char*, const char*, int, int);
-NODE *rb_compile_string(const char*, VALUE, int);
-NODE *rb_compile_file(const char*, VALUE, int);
+ast_t *rb_compile_cstr(const char*, const char*, int, int);
+ast_t *rb_compile_string(const char*, VALUE, int);
+ast_t *rb_compile_file(const char*, VALUE, int);
 
 void rb_node_init(NODE *n, enum node_type type, VALUE a0, VALUE a1, VALUE a2);
 NODE *rb_node_newnode(enum node_type,VALUE,VALUE,VALUE);
diff --git a/parse.y b/parse.y
index 082365dac2..cb3849e28e 100644
--- a/parse.y
+++ b/parse.y
@@ -239,6 +239,7 @@ struct parser_params {
     unsigned int do_chomp: 1;
     unsigned int do_split: 1;
 
+    ast_t *ast;
     NODE *eval_tree_begin;
     NODE *eval_tree;
     VALUE error_buffer;
@@ -338,15 +339,27 @@ parser_set_line(NODE *n, int l)
 }
 
 static inline void
-rb_discard_node(NODE *n)
+rb_discard_node_gen(struct parser_params *parser, NODE *n)
 {
+#ifndef RIPPER
+    rb_ast_delete_node(parser->ast, n);
+#else
     rb_gc_force_recycle((VALUE)n);
+#endif
 }
-
-#define add_mark_object(obj) (void)(obj)
+#define rb_discard_node(n) rb_discard_node_gen(parser, (n))
 
 #ifndef RIPPER
 static inline void
+add_mark_object_gen(struct parser_params *parser, VALUE obj)
+{
+    if (!SPECIAL_CONST_P(obj)) {
+	rb_ast_add_mark_object(parser->ast, obj);
+    }
+}
+#define add_mark_object(obj) add_mark_object_gen(parser, (obj))
+
+static inline void
 set_line_body(NODE *body, int line)
 {
     if (!body) return;
@@ -575,6 +588,8 @@ static NODE *parser_heredoc_dedent(struct parser_params*,NODE*);
 #else  /* RIPPER */
 #define NODE_RIPPER NODE_CDECL
 
+#define add_mark_object(obj) (void)(obj)
+
 static inline VALUE
 ripper_new_yylval(ID a, VALUE b, VALUE c)
 {
@@ -2850,6 +2865,7 @@ primary		: literal
 				break;
 			    }
 			}
+			add_mark_object((VALUE)rb_imemo_alloc_new((VALUE)tbl, 0, 0, 0));
 			scope = NEW_NODE(NODE_SCOPE, tbl, $8, args);
 			nd_set_column(scope, @1.first_column);
 			tbl[0] = 1; tbl[1] = id;
@@ -5573,52 +5589,55 @@ lex_getline(struct parser_params *parser)
 static const rb_data_type_t parser_data_type;
 
 #ifndef RIPPER
-static NODE*
+static ast_t*
 parser_compile_string(VALUE vparser, VALUE fname, VALUE s, int line)
 {
     struct parser_params *parser;
-    NODE *node;
+    ast_t *ast;
 
     TypedData_Get_Struct(vparser, struct parser_params, &parser_data_type, parser);
+    parser->ast = ast = rb_ast_new();
+
     lex_gets = lex_get_str;
     lex_gets_ptr = 0;
     lex_input = rb_str_new_frozen(s);
     lex_pbeg = lex_p = lex_pend = 0;
 
-    node = yycompile(parser, fname, line);
+    ast->root = yycompile(parser, fname, line);
+    parser->ast = 0;
     RB_GC_GUARD(vparser); /* prohibit tail call optimization */
 
-    return node;
+    return ast;
 }
 
-NODE*
+ast_t*
 rb_compile_string(const char *f, VALUE s, int line)
 {
     must_be_ascii_compatible(s);
     return parser_compile_string(rb_parser_new(), rb_filesystem_str_new_cstr(f), s, line);
 }
 
-NODE*
+ast_t*
 rb_parser_compile_string(VALUE vparser, const char *f, VALUE s, int line)
 {
     return rb_parser_compile_string_path(vparser, rb_filesystem_str_new_cstr(f), s, line);
 }
 
-NODE*
+ast_t*
 rb_parser_compile_string_path(VALUE vparser, VALUE f, VALUE s, int line)
 {
     must_be_ascii_compatible(s);
     return parser_compile_string(vparser, f, s, line);
 }
 
-NODE*
+ast_t*
 rb_compile_cstr(const char *f, const char *s, int len, int line)
 {
     VALUE str = rb_str_new(s, len);
     return parser_compile_string(rb_parser_new(), rb_filesystem_str_new_cstr(f), str, line);
 }
 
-NODE*
+ast_t*
 rb_parser_compile_cstr(VALUE vparser, const char *f, const char *s, int len, int line)
 {
     VALUE str = rb_str_new(s, len);
@@ -5633,7 +5652,7 @@ lex_io_gets(struct parser_params *parser, VALUE io)
     return rb_io_gets_internal(io);
 }
 
-NODE*
+ast_t*
 rb_compile_file(const char *f, VALUE file, int start)
 {
     VALUE vparser = rb_parser_new();
@@ -5641,27 +5660,30 @@ rb_compile_file(const char *f, VALUE file, int start)
     return rb_parser_compile_file(vparser, f, file, start);
 }
 
-NODE*
+ast_t*
 rb_parser_compile_file(VALUE vparser, const char *f, VALUE file, int start)
 {
     return rb_parser_compile_file_path(vparser, rb_filesystem_str_new_cstr(f), file, start);
 }
 
-NODE*
+ast_t*
 rb_parser_compile_file_path(VALUE vparser, VALUE fname, VALUE file, int start)
 {
     struct parser_params *parser;
-    NODE *node;
+    ast_t *ast;
 
     TypedData_Get_Struct(vparser, struct parser_params, &parser_data_type, parser);
+    parser->ast = ast = rb_ast_new();
+
     lex_gets = lex_io_gets;
     lex_input = file;
     lex_pbeg = lex_p = lex_pend = 0;
 
-    node = yycompile(parser, fname, start);
+    ast->root = yycompile(parser, fname, start);
+    parser->ast = 0;
     RB_GC_GUARD(vparser); /* prohibit tail call optimization */
 
-    return node;
+    return ast;
 }
 #endif  /* !RIPPER */
 
@@ -6160,8 +6182,11 @@ parser_regx_options(struct parser_params *parser)
 }
 
 static void
-dispose_string(VALUE str)
+dispose_string(struct parser_params *parser, VALUE str)
 {
+#ifndef RIPPER
+    rb_ast_delete_mark_object(parser->ast, str);
+#endif
     rb_str_free(str);
     rb_gc_force_recycle(str);
 }
@@ -6639,7 +6664,7 @@ parser_heredoc_restore(struct parser_params *parser, NODE *here)
     lex_p = lex_pbeg + here->nd_nth;
     heredoc_end = ruby_sourceline;
     ruby_sourceline = nd_line(here);
-    dispose_string(here->nd_lit);
+    dispose_string(parser, here->nd_lit);
     rb_discard_node(here);
     token_flush(parser);
 }
@@ -6925,7 +6950,7 @@ parser_here_document(struct parser_params *parser, NODE *here)
 	    }
 	    if (nextc() == -1) {
 		if (str) {
-		    dispose_string(str);
+		    dispose_string(parser, str);
 		    str = 0;
 		}
 		goto error;
@@ -8800,7 +8825,10 @@ yylex(YYSTYPE *lval, YYLTYPE *yylloc, struct parser_params *parser)
 static NODE*
 node_newnode(struct parser_params *parser, enum node_type type, VALUE a0, VALUE a1, VALUE a2)
 {
-    NODE *n = (rb_node_newnode)(type, a0, a1, a2);
+    NODE *n = rb_ast_newnode(parser->ast);
+
+    rb_node_init(n, type, a0, a1, a2);
+
     nd_set_line(n, ruby_sourceline);
     /* mark not cared column to -1 */
     nd_set_column(n, -1);
@@ -10590,6 +10618,7 @@ new_args_tail_gen(struct parser_params *parser, NODE *k, ID kr, ID b, int column
     NODE *node;
 
     args = ZALLOC(struct rb_args_info);
+    add_mark_object((VALUE)rb_imemo_alloc_new((VALUE)args, 0, 0, 0));
     node = NEW_NODE(NODE_ARGS, 0, 0, args);
     nd_set_column(node, column);
     if (parser->error_p) return node;
@@ -10959,6 +10988,9 @@ local_tbl_gen(struct parser_params *parser)
     }
     if (--j < cnt) REALLOC_N(buf, ID, (cnt = j) + 1);
     buf[0] = cnt;
+
+    add_mark_object((VALUE)rb_imemo_alloc_new((VALUE)buf, 0, 0, 0));
+
     return buf;
 }
 #endif
@@ -11350,18 +11382,16 @@ parser_mark(void *ptr)
 {
     struct parser_params *parser = (struct parser_params*)ptr;
 
-    rb_gc_mark((VALUE)lex_strterm);
     rb_gc_mark(lex_input);
     rb_gc_mark(lex_lastline);
     rb_gc_mark(lex_nextline);
     rb_gc_mark(ruby_sourcefile_string);
 #ifndef RIPPER
-    rb_gc_mark((VALUE)ruby_eval_tree_begin);
-    rb_gc_mark((VALUE)ruby_eval_tree);
     rb_gc_mark(ruby_debug_lines);
     rb_gc_mark(parser->compile_option);
     rb_gc_mark(parser->error_buffer);
 #else
+    rb_gc_mark((VALUE)lex_strterm);
     rb_gc_mark(parser->delayed);
     rb_gc_mark(parser->value);
     rb_gc_mark(parser->result);
diff --git a/ruby.c b/ruby.c
index 94464ab2b9..75f2837d23 100644
--- a/ruby.c
+++ b/ruby.c
@@ -177,7 +177,7 @@ cmdline_options_init(ruby_cmdline_options_t *opt)
     return opt;
 }
 
-static NODE *load_file(VALUE parser, VALUE fname, VALUE f, int script,
+static ast_t *load_file(VALUE parser, VALUE fname, VALUE f, int script,
 		       ruby_cmdline_options_t *opt);
 static VALUE open_load_file(VALUE fname_v, int *xflag);
 static void forbid_setid(const char *, const ruby_cmdline_options_t *);
@@ -1461,7 +1461,7 @@ rb_f_chomp(int argc, VALUE *argv)
 static VALUE
 process_options(int argc, char **argv, ruby_cmdline_options_t *opt)
 {
-    NODE *tree = 0;
+    ast_t *ast = 0;
     VALUE parser;
     VALUE script_name;
     const rb_iseq_t *iseq;
@@ -1674,12 +1674,12 @@ process_options(int argc, char **argv, ruby_cmdline_options_t *opt)
         ruby_set_script_name(progname);
 	rb_parser_set_options(parser, opt->do_print, opt->do_loop,
 			      opt->do_line, opt->do_split);
-	tree = rb_parser_compile_string(parser, opt->script, opt->e_script, 1);
+	ast = rb_parser_compile_string(parser, opt->script, opt->e_script, 1);
     }
     else {
 	VALUE f;
 	f = open_load_file(script_name, &opt->xflag);
-	tree = load_file(parser, opt->script_name, f, 1, opt);
+	ast = load_file(parser, opt->script_name, f, 1, opt);
     }
     ruby_set_script_name(opt->script_name);
     if (dump & DUMP_BIT(yydebug)) {
@@ -1704,7 +1704,10 @@ process_options(int argc, char **argv, ruby_cmdline_options_t *opt)
 	rb_enc_set_default_internal(Qnil);
     rb_stdio_set_default_encoding();
 
-    if (!tree) return Qfalse;
+    if (!ast->root) {
+	rb_ast_dispose(ast);
+	return Qfalse;
+    }
 
     process_sflag(&opt->sflag);
     opt->xflag = 0;
@@ -1723,10 +1726,13 @@ process_options(int argc, char **argv, ruby_cmdline_options_t *opt)
     }
 
     if (dump & (DUMP_BIT(parsetree)|DUMP_BIT(parsetree_with_comment))) {
-	rb_io_write(rb_stdout, rb_parser_dump_tree(tree, dump & DUMP_BIT(parsetree_with_comment)));
+	rb_io_write(rb_stdout, rb_parser_dump_tree(ast->root, dump & DUMP_BIT(parsetree_with_comment)));
 	rb_io_flush(rb_stdout);
 	dump &= ~DUMP_BIT(parsetree)&~DUMP_BIT(parsetree_with_comment);
-	if (!dump) return Qtrue;
+	if (!dump) {
+	    rb_ast_dispose(ast);
+	    return Qtrue;
+	}
     }
 
     {
@@ -1740,7 +1746,8 @@ process_options(int argc, char **argv, ruby_cmdline_options_t *opt)
 #endif
 	}
 	base_block = toplevel_context(toplevel_binding);
-	iseq = rb_iseq_new_main(tree, opt->script_name, path, vm_block_iseq(base_block));
+	iseq = rb_iseq_new_main(ast->root, opt->script_name, path, vm_block_iseq(base_block));
+	rb_ast_dispose(ast);
     }
 
     if (dump & DUMP_BIT(insns)) {
@@ -1790,7 +1797,7 @@ load_file_internal(VALUE argp_v)
     ruby_cmdline_options_t *opt = argp->opt;
     VALUE f = argp->f;
     int line_start = 1;
-    NODE *tree = 0;
+    ast_t *ast = 0;
     rb_encoding *enc;
     ID set_encoding;
 
@@ -1894,7 +1901,7 @@ load_file_internal(VALUE argp_v)
 	return (VALUE)rb_parser_compile_string_path(parser, orig_fname, f, line_start);
     }
     rb_funcall(f, set_encoding, 2, rb_enc_from_encoding(enc), rb_str_new_cstr("-"));
-    tree = rb_parser_compile_file_path(parser, orig_fname, f, line_start);
+    ast = rb_parser_compile_file_path(parser, orig_fname, f, line_start);
     rb_funcall(f, set_encoding, 1, rb_parser_encoding(parser));
     if (script && rb_parser_end_seen_p(parser)) {
 	/*
@@ -1912,7 +1919,7 @@ load_file_internal(VALUE argp_v)
 	rb_define_global_const("DATA", f);
 	argp->f = Qnil;
     }
-    return (VALUE)tree;
+    return (VALUE)ast;
 }
 
 static VALUE
@@ -2004,7 +2011,7 @@ restore_load_file(VALUE arg)
     return Qnil;
 }
 
-static NODE *
+static ast_t *
 load_file(VALUE parser, VALUE fname, VALUE f, int script, ruby_cmdline_options_t *opt)
 {
     struct load_file_arg arg;
@@ -2013,8 +2020,8 @@ load_file(VALUE parser, VALUE fname, VALUE f, int script, ruby_cmdline_options_t
     arg.script = script;
     arg.opt = opt;
     arg.f = f;
-    return (NODE *)rb_ensure(load_file_internal, (VALUE)&arg,
-			     restore_load_file, (VALUE)&arg);
+    return (ast_t *)rb_ensure(load_file_internal, (VALUE)&arg,
+			      restore_load_file, (VALUE)&arg);
 }
 
 void *
diff --git a/template/prelude.c.tmpl b/template/prelude.c.tmpl
index 873146fc39..b791c14ae4 100644
--- a/template/prelude.c.tmpl
+++ b/template/prelude.c.tmpl
@@ -121,10 +121,14 @@ prelude_eval(VALUE code, VALUE name, int line)
 	FALSE, /* int debug_frozen_string_literal; */
     };
 
-    NODE *node = rb_parser_compile_string_path(rb_parser_new(), name, code, line);
-    if (!node) rb_exc_raise(rb_errinfo());
-    rb_iseq_eval(rb_iseq_new_with_opt(node, name, name, Qnil, INT2FIX(line),
+    ast_t *ast = rb_parser_compile_string_path(rb_parser_new(), name, code, line);
+    if (!ast->root) {
+	rb_ast_dispose(ast);
+	rb_exc_raise(rb_errinfo());
+    }
+    rb_iseq_eval(rb_iseq_new_with_opt(ast->root, name, name, Qnil, INT2FIX(line),
 				      NULL, ISEQ_TYPE_TOP, &optimization));
+    rb_ast_dispose(ast);
 }
 % end
 
diff --git a/test/ruby/test_gc.rb b/test/ruby/test_gc.rb
index 67fd40a51e..7a6309b6a3 100644
--- a/test/ruby/test_gc.rb
+++ b/test/ruby/test_gc.rb
@@ -290,6 +290,9 @@ class TestGc < Test::Unit::TestCase
     base_length = GC.stat[:heap_eden_pages]
     (base_length * 500).times{ 'a' }
     GC.start
+    base_length = GC.stat[:heap_eden_pages]
+    (base_length * 500).times{ 'a' }
+    GC.start
     assert_in_epsilon base_length, (v = GC.stat[:heap_eden_pages]), 1/8r,
            "invalid heap expanding (base_length: #{base_length}, GC.stat[:heap_eden_pages]: #{v})"