yarv-diff:5
From: ko1 atdot.net
Date: 3 Jun 2005 22:33:11 -0000
Subject: [yarv-diff:5] r160 - in trunk: . benchmark rb test
Author: ko1
Date: 2005-06-04 07:33:10 +0900 (Sat, 04 Jun 2005)
New Revision: 160
Modified:
trunk/ChangeLog
trunk/benchmark/bmx_temp.rb
trunk/benchmark/run.rb
trunk/compile.c
trunk/compile.h
trunk/disasm.c
trunk/insns.def
trunk/rb/insns2vm.rb
trunk/test.rb
trunk/test/test_syn.rb
trunk/yarvcore.c
trunk/yarvcore.h
Log:
* compile.c, insns.def : optimize case/when statement
(dispatch on constant time)
* yarvcore.h, disasm.c, rb/insns2vm.rb : fixed for above
(CDHASH)
* test/test_syn.rb : add test for above
Modified: trunk/ChangeLog
===================================================================
--- trunk/ChangeLog 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/ChangeLog 2005-06-03 22:33:10 UTC (rev 160)
@@ -4,6 +4,17 @@
# from Mon, 03 May 2004 01:24:19 +0900
#
+2005-06-04(Sat) 07:31:21 +0900 Koichi Sasada <ko1 atdot.net>
+
+ * compile.c, insns.def : optimize case/when statement
+ (dispatch on constant time)
+
+ * yarvcore.h, disasm.c, rb/insns2vm.rb : fixed for above
+ (CDHASH)
+
+ * test/test_syn.rb : add test for above
+
+
2005-06-04(Sat) 03:41:29 +0900 Koichi Sasada <ko1 atdot.net>
* yarvcore.h, yarvcore.c : add some temporary variable test
Modified: trunk/benchmark/bmx_temp.rb
===================================================================
--- trunk/benchmark/bmx_temp.rb 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/benchmark/bmx_temp.rb 2005-06-03 22:33:10 UTC (rev 160)
@@ -1,8 +1,8 @@
i=0
-while i<500000
+while i<1000000
i+=1
- case :a
+ case :x
when :x
when :y
when :z
Modified: trunk/benchmark/run.rb
===================================================================
--- trunk/benchmark/run.rb 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/benchmark/run.rb 2005-06-03 22:33:10 UTC (rev 160)
@@ -6,7 +6,7 @@
require 'benchmark'
require 'rbconfig'
-$bench = false
+$bench = false #|| true
puts "ruby #{RUBY_VERSION} #{RUBY_PLATFORM}(#{RUBY_RELEASE_DATE})"
puts YARVCore::VERSION + " rev: #{YARVCore::REV} (#{YARVCore::DATE})"
Modified: trunk/compile.c
===================================================================
--- trunk/compile.c 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/compile.c 2005-06-03 22:33:10 UTC (rev 160)
@@ -627,6 +627,28 @@
}
iseq[pos+1+j] = lobj->position - (pos + len);
break;
+ case 'H':
+ /*
+ * [[obj, label], ...]
+ */
+ {
+ int i;
+ VALUE lits = ((NODE*)operands[j])->u1.value;
+ VALUE map = rb_hash_new();
+
+ for(i=0; i<RARRAY(lits)->len; i++){
+ int offset;
+ VALUE pair = RARRAY(lits)->ptr[i];
+ GetLabelVal(RARRAY(pair)->ptr[1], lobj);
+ if(lobj->set != Qtrue){
+ rb_bug("unknown label");
+ }
+ rb_hash_aset(map, RARRAY(pair)->ptr[0], INT2FIX(lobj->position - (pos + len)));
+ }
+ iseq[pos+1+j] = map;
+ rb_ary_push(iseqobj->iseq_mark_ary, map);
+ break;
+ }
case 'U': /* ulong */
iseq[pos+1+j] = FIX2INT(operands[j]);
break;
@@ -967,77 +989,6 @@
return iseqobj->local_size;
}
-static int get_temporary_variable_index(struct iseq_object *iseqobj){
- int idx;
- VALUE tvarary;
-
- tvarary = iseqobj->compile_data->temporary_variables;
- if(tvarary == 0){
- tvarary = iseqobj->compile_data->temporary_variables = rb_ary_new();
- }
-
- if(RARRAY(tvarary)->len == 0){
- int num = iseqobj->compile_data->temporary_variables_num ++;
- char tvarstr[0x10];
- int old_size = iseqobj->local_size;
- ID *old_tbl = iseqobj->local_tbl;
-
- /* new symbol name */
- snprintf(tvarstr, 0x10, "_$%d", num);
-
- /* add new symbol to local table */
- iseqobj->local_tbl = (ID*)ALLOC_N(ID*, old_size + 1);
- iseqobj->local_size += 1;
- MEMCPY(iseqobj->local_tbl, old_tbl, ID*, old_size);
- ruby_xfree(old_tbl);
- iseqobj->local_tbl[old_size] = rb_intern(tvarstr);
- idx = old_size;
- }
- else{
- idx = FIX2INT(rb_ary_pop(tvarary));
- }
-
- return idx;
-}
-
-static void release_temporary_variable_index(struct iseq_object *iseqobj, int idx){
- if(iseqobj->compile_data->temporary_variables){
- rb_ary_push(iseqobj->compile_data->temporary_variables, INT2FIX(idx));
- }
- else{
- rb_bug("release_temporary_local_variable error");
- }
-}
-
-static void get_temporary_variable_set_insn(struct iseq_object *iseqobj,
- VALUE seq, int line, int idx){
- int ls = iseqobj->local_size;
-
- if(iseqobj->parent_iseqobj){
- /* dvar */
- ADD_INSN2(seq, line, setdynamic, I2F(ls - idx), I2F(0));
- }
- else{
- /* lvar */
- ADD_INSN1(seq, line, setlocal, I2F(ls - idx - 2 /* block + svar */));
- }
-}
-
-static void set_temporary_variable_get_insn(struct iseq_object *iseqobj,
- VALUE seq, int line, int idx){
- int ls = iseqobj->local_size;
-
- if(iseqobj->parent_iseqobj){
- /* dvar */
- ADD_INSN2(seq, line, getdynamic, I2F(ls - idx), I2F(0));
- }
- else{
- /* lvar */
- ADD_INSN1(seq, line, getlocal, I2F(ls - idx - 2 /* block + svar */));
- }
-}
-
-
static VALUE compile_array(VALUE self, NODE *node_root, VALUE opt_p){
NODE *node = node_root;
VALUE obj, tmp, ret;
@@ -1067,6 +1018,20 @@
return ret;
}
+static VALUE case_when_optimizable_literal(NODE *node){
+ if(nd_type(node) == NODE_LIT){
+ VALUE v = node->nd_lit;
+ VALUE klass = CLASS_OF(v);
+
+ if(klass == rb_cString ||
+ klass == rb_cSymbol ||
+ rb_obj_is_kind_of(v, rb_cNumeric)){
+ return v;
+ }
+ }
+ return Qfalse;
+}
+
static VALUE make_masgn_lhs(VALUE self, NODE *node){
VALUE ret;
@@ -1314,10 +1279,102 @@
break;
}
case NODE_CASE:{
+#if 0
VALUE head = COMPILE("case base", node->nd_head);
NODE* vals;
NODE* val;
NODE* tempnode = node;
+ VALUE endlabel, elselabel;
+ VALUE body_seq, cond_seq;
+ VALUE special_literals = rb_ary_new();
+
+ node = node->nd_body;
+ type = nd_type(node);
+
+ if(type != NODE_WHEN){
+ COMPILE_ERROR(("NODE_CASE: unexpected node. must be NODE_WHEN, byt %s", node_name(type)));
+ }
+
+ ret = NEW_SEQ();
+ cond_seq = NEW_SEQ();
+ body_seq = NEW_SEQ();
+ endlabel = NEW_LABEL(nd_line(node));
+ elselabel = NEW_LABEL(nd_line(node));
+
+ ADD_SEQ (ret, head); /* case VAL */
+
+
+ while(type == NODE_WHEN){
+ l1 = NEW_LABEL(nd_line(node));
+ ADD_LABEL(body_seq, l1);
+ ADD_INSN (body_seq, nd_line(node), pop);
+ ADD_SEQ (body_seq, COMPILE_("when body", node->nd_body, poped));
+ ADD_INSNL(body_seq, nd_line(node), jump, endlabel);
+
+ vals = node->nd_head;
+ if(vals && nd_type(vals) == NODE_ARRAY){
+ while(vals){
+ VALUE lit;
+
+ val = vals->nd_head;
+
+ if((lit = case_when_optimizable_literal(val)) && special_literals){
+ rb_ary_push(special_literals, rb_ary_new3(2, lit, l1));
+ }
+ else{
+ special_literals = Qfalse;
+ }
+
+ ADD_SEQ (cond_seq, COMPILE("when cond", val));
+ ADD_INSN1(cond_seq, nd_line(node), topn, INT2FIX(1));
+ ADD_SEND (cond_seq, nd_line(node), ID2SYM(idEqq), INT2FIX(1));
+ ADD_INSNL(cond_seq, nd_line(node), if, l1);
+ vals = vals->nd_next;
+ }
+ }
+ else{
+ COMPILE_ERROR(("NODE_CASAE: must be NODE_ARRAY, but %s\n", node_name(nd_type(vals))));
+ }
+
+ node = node->nd_next;
+ if(!node){
+ break;
+ }
+ type = nd_type(node);
+ }
+ /* else */
+ if(node){
+ ADD_LABEL(cond_seq, elselabel);
+ ADD_INSN (cond_seq, nd_line(node), pop);
+ ADD_SEQ (cond_seq, COMPILE_("else", node, poped));
+ ADD_INSNL(cond_seq, nd_line(node), jump, endlabel);
+ }
+ else{
+ debugs("== else(implicit)\n");
+ ADD_LABEL(cond_seq, elselabel);
+ ADD_INSN (cond_seq, nd_line(tempnode), pop);
+ if(!poped){
+ ADD_INSN (cond_seq, nd_line(tempnode), putnil);
+ }
+ ADD_INSNL(cond_seq, nd_line(tempnode), jump, endlabel);
+ }
+
+ if(special_literals){
+ special_literals = (VALUE)NEW_WHILE(special_literals, 0, 0);
+ ADD_INSN2(ret, nd_line(tempnode), opt_case_dispatch,
+ special_literals, elselabel);
+ }
+
+ ADD_SEQ (ret, cond_seq);
+ ADD_SEQ (ret, body_seq);
+ ADD_LABEL(ret, endlabel);
+ break;
+
+#else
+ VALUE head = COMPILE("case base", node->nd_head);
+ NODE* vals;
+ NODE* val;
+ NODE* tempnode = node;
VALUE endlabel;
VALUE body_seq;
@@ -1345,15 +1402,6 @@
if(vals && nd_type(vals) == NODE_ARRAY){
while(vals){
val = vals->nd_head;
- /*
- u| obj
- | obj(dupped)
- | cond_val(self)
- -> # swap
- u| obj
- | cond_val(self)
- | obj(dupped)
- */
ADD_SEQ (ret, COMPILE("when cond", val));
ADD_INSN1(ret, nd_line(node), topn, INT2FIX(1));
ADD_SEND (ret, nd_line(node), ID2SYM(idEqq), INT2FIX(1));
@@ -1389,6 +1437,7 @@
ADD_SEQ (ret, body_seq);
ADD_LABEL(ret, endlabel);
break;
+#endif
}
case NODE_WHEN:{
NODE* vals;
@@ -3023,6 +3072,7 @@
#define TS_ID "I"
#define TS_GENTRY "G"
#define TS_IC "M"
+#define TS_CDHASH "H"
#define TS_VARIABLE "."
Modified: trunk/compile.h
===================================================================
--- trunk/compile.h 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/compile.h 2005-06-03 22:33:10 UTC (rev 160)
@@ -124,7 +124,7 @@
debugp_verbose_node("add_insn", seq))
/* add an instruction with label operand */
-#define ADD_INSNL(seq, line, insn, label) \
+#define ADD_INSNL(seq, line, insn, label) \
(rb_ary_push(seq, new_insn(BIN(insn), line, rb_ary_new3(1, label))), \
debugp_verbose_node("add_insnl", seq))
Modified: trunk/disasm.c
===================================================================
--- trunk/disasm.c 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/disasm.c 2005-06-03 22:33:10 UTC (rev 160)
@@ -83,6 +83,10 @@
case 'M':
ret = rb_str_new2("<ic>");
break;
+
+ case 'H':
+ ret = rb_str_new2("<cdhash>");
+ break;
default:
rb_bug("iseq_disasm: unknown operand type: %c", type);
Modified: trunk/insns.def
===================================================================
--- trunk/insns.def 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/insns.def 2005-06-03 22:33:10 UTC (rev 160)
@@ -1849,7 +1849,34 @@
ic->ic_value = val;
}
+/**
+ @c optimize
+ @e case dispatcher
+ @j case dispatcher
+ */
+DEFINE_INSN
+opt_case_dispatch
+(CDHASH hash, OFFSET else_offset)
+(..., VALUE key)
+()
+{
+ if(0){
+ /* if some === method is overrided */
+ }
+ else{
+ VALUE val;
+ if(st_lookup(RHASH(hash)->tbl, key, &val)){
+ JUMP(FIX2INT(val));
+ }
+ else{
+ JUMP(else_offset);
+ }
+ }
+}
+/** simple functions */
+
+
/**
@c optimize
@e optimized X+Y.
Modified: trunk/rb/insns2vm.rb
===================================================================
--- trunk/rb/insns2vm.rb 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/rb/insns2vm.rb 2005-06-03 22:33:10 UTC (rev 160)
@@ -625,6 +625,8 @@
"TS_IC"
when /^\.\.\./
"TS_VARIABLE"
+ when /^CDHASH/
+ "TS_CDHASH"
else
raise "unknown op type: #{op}"
end
Modified: trunk/test/test_syn.rb
===================================================================
--- trunk/test/test_syn.rb 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/test/test_syn.rb 2005-06-03 22:33:10 UTC (rev 160)
@@ -120,22 +120,60 @@
:ng_else
end
)
-
- ae %q(
- case Object.new
- when Object
- :ok
- end
- )
-
- ae %q(
- case Object
- when Object.new
- :ng
- else
- :ok
- end
- )
+ ae %q(
+ case Object.new
+ when Object
+ :ok
+ end
+ )
+ ae %q(
+ case Object
+ when Object.new
+ :ng
+ else
+ :ok
+ end
+ )
+ ae %q{
+ case 'test'
+ when 'tes'
+ :ng
+ when 'te'
+ :ng
+ else
+ :ok
+ end
+ }
+ ae %q{
+ case 'test'
+ when 'tes'
+ :ng
+ when 'te'
+ :ng
+ when 'test'
+ :ok
+ end
+ }
+ ae %q{
+ case 'test'
+ when 'tes'
+ :ng
+ when /te/
+ :ng
+ else
+ :ok
+ end
+ }
+ ae %q{
+ case 'test'
+ when 'tes'
+ :ng
+ when /test/
+ :ok
+ else
+ :ng
+ end
+ }
end
def test_when
Modified: trunk/test.rb
===================================================================
--- trunk/test.rb 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/test.rb 2005-06-03 22:33:10 UTC (rev 160)
@@ -9,14 +9,15 @@
###########################################################
$prog =<<'__EOP__'
-i=0
-while i<500000
- i+=1
- case :a
- when :x
- when :y
- when :z
- end
+case :z
+when :x
+ p :x
+when /x/
+ p :y
+when :z
+ p :z
+else
+ p :else
end
__END__
Modified: trunk/yarvcore.c
===================================================================
--- trunk/yarvcore.c 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/yarvcore.c 2005-06-03 22:33:10 UTC (rev 160)
@@ -316,7 +316,6 @@
MARK_UNLESS_NULL(iseqobj->compile_data->end_label);
MARK_UNLESS_NULL(iseqobj->compile_data->redo_label);
MARK_UNLESS_NULL(iseqobj->compile_data->err_info);
- MARK_UNLESS_NULL(iseqobj->compile_data->temporary_variables);
}
}
}
Modified: trunk/yarvcore.h
===================================================================
--- trunk/yarvcore.h 2005-06-03 18:43:02 UTC (rev 159)
+++ trunk/yarvcore.h 2005-06-03 22:33:10 UTC (rev 160)
@@ -102,13 +102,11 @@
VALUE end_label;
VALUE redo_label;
VALUE err_info;
- VALUE temporary_variables;
/* GC is not needed */
VALUE loopval_popped; /* used by NODE_BREAK */
VALUE in_ensure; /* used by NODE_RETURN */
int cached_const;
- int temporary_variables_num;
};
struct iseq_object{
@@ -321,6 +319,8 @@
#define ic_vmstat u3.cnt
typedef NODE * IC;
+typedef VALUE CDHASH;
+
#include "yarv.h"
#define YARV_METHOD_NODE NODE_ERRINFO
--
ML: yarv-diff quickml.atdot.net
Info: http://www.atdot.net/~ko1/quickml