compile optimized case dispatch for nil/true/false

nil/true/false are special literals just like floats, integers,
literal strings, and symbols.  Optimize when statements with
them by using a jump table, too.

target 0: a (ruby 2.3.0dev (2015-12-08 trunk 52928) [x86_64-linux]) at "/home/ew/rrrr/b/ruby"
target 1: b (ruby 2.3.0dev (2015-12-08 master 52928) [x86_64-linux]) at "/home/ew/ruby/b/ruby"

benchmark results:
minimum results in each 5 measurements.
Execution time (sec)
name	a	b
loop_whileloop2	0.102	0.103
vm2_case_lit*	1.657	0.549

Speedup ratio: compare with the result of `a' (greater is better)
name	b
loop_whileloop2	0.988
vm2_case_lit*	3.017

* benchmark/bm_vm2_case_lit.rb: new benchmark
* compile.c (case_when_optimizable_literal): add nil/true/false
* insns.def (opt_case_dispatch): ditto
* vm.c (vm_redefinition_check_flag): ditto
* vm.c (vm_init_redefined_flag): ditto
* vm_core.h: ditto
* object.c (InitVM_Object): define === explicitly for nil/true/false
* test/ruby/test_case.rb (test_deoptimize_nil): new test
* test/ruby/test_optimization.rb (test_opt_case_dispatch): update
  (test_eqq): new test
  [ruby-core:71923] [Feature #11769]
  Original patch by Aaron Patterson <tenderlove@ruby-lang.org>

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

9 files changed, 91 insertions, 1 deletions

diff --git a/ChangeLog b/ChangeLog
index fe9b6e6c74..880fcabd47 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+Tue Dec  8 10:40:21 2015  Eric Wong  <e@80x24.org>
+
+	* benchmark/bm_vm2_case_lit.rb: new benchmark
+	* compile.c (case_when_optimizable_literal): add nil/true/false
+	* insns.def (opt_case_dispatch): ditto
+	* vm.c (vm_redefinition_check_flag): ditto
+	* vm.c (vm_init_redefined_flag): ditto
+	* vm_core.h: ditto
+	* object.c (InitVM_Object): define === explicitly for nil/true/false
+	* test/ruby/test_case.rb (test_deoptimize_nil): new test
+	* test/ruby/test_optimization.rb (test_opt_case_dispatch): update
+	  (test_eqq): new test
+	  [ruby-core:71923] [Feature #11769]
+	  Original patch by Aaron Patterson <tenderlove@ruby-lang.org>
+
 Tue Dec  8 10:19:02 2015  Jake Worth  <jakeworth82@gmail.com>
 
 	* lib/optparse.rb: fix double word typo in the document.
diff --git a/benchmark/bm_vm2_case_lit.rb b/benchmark/bm_vm2_case_lit.rb
new file mode 100644
index 0000000000..c62b294e0e
--- /dev/null
+++ b/benchmark/bm_vm2_case_lit.rb
@@ -0,0 +1,19 @@
+i = 0
+@ret = [ "foo", true, false, :sym, 6, nil, 0.1, 0xffffffffffffffff ]
+def foo(i)
+  @ret[i % @ret.size]
+end
+
+while i<6_000_000 # while loop 2
+  case foo(i)
+  when "foo" then :foo
+  when true then true
+  when false then false
+  when :sym then :sym
+  when 6 then :fix
+  when nil then nil
+  when 0.1 then :float
+  when 0xffffffffffffffff then :big
+  end
+  i += 1
+end
diff --git a/compile.c b/compile.c
index 9be8fd57c8..abb5306759 100644
--- a/compile.c
+++ b/compile.c
@@ -2919,6 +2919,12 @@ case_when_optimizable_literal(NODE * node)
 	}
 	break;
       }
+      case NODE_NIL:
+	return Qnil;
+      case NODE_TRUE:
+	return Qtrue;
+      case NODE_FALSE:
+	return Qfalse;
       case NODE_STR:
 	return node->nd_lit = rb_fstring(node->nd_lit);
     }
diff --git a/insns.def b/insns.def
index c8088919c5..3c4d98073b 100644
--- a/insns.def
+++ b/insns.def
@@ -1264,6 +1264,9 @@ opt_case_dispatch
 	    key = FIXABLE(ival) ? LONG2FIX((long)ival) : rb_dbl2big(ival);
 	}
       }
+      case T_TRUE:
+      case T_FALSE:
+      case T_NIL:
       case T_SYMBOL: /* fall through */
       case T_FIXNUM:
       case T_BIGNUM:
@@ -1273,6 +1276,9 @@ opt_case_dispatch
 				   FIXNUM_REDEFINED_OP_FLAG |
 				   FLOAT_REDEFINED_OP_FLAG |
 				   BIGNUM_REDEFINED_OP_FLAG |
+				   NIL_REDEFINED_OP_FLAG    |
+				   TRUE_REDEFINED_OP_FLAG   |
+				   FALSE_REDEFINED_OP_FLAG  |
 				   STRING_REDEFINED_OP_FLAG)) {
 	    st_data_t val;
 	    if (st_lookup(RHASH_TBL_RAW(hash), key, &val)) {
diff --git a/object.c b/object.c
index ff2db0b45a..d339ff94b2 100644
--- a/object.c
+++ b/object.c
@@ -3468,6 +3468,7 @@ InitVM_Object(void)
     rb_define_method(rb_cNilClass, "&", false_and, 1);
     rb_define_method(rb_cNilClass, "|", false_or, 1);
     rb_define_method(rb_cNilClass, "^", false_xor, 1);
+    rb_define_method(rb_cNilClass, "===", rb_equal, 1);
 
     rb_define_method(rb_cNilClass, "nil?", rb_true, 0);
     rb_undef_alloc_func(rb_cNilClass);
@@ -3553,6 +3554,7 @@ InitVM_Object(void)
     rb_define_method(rb_cTrueClass, "&", true_and, 1);
     rb_define_method(rb_cTrueClass, "|", true_or, 1);
     rb_define_method(rb_cTrueClass, "^", true_xor, 1);
+    rb_define_method(rb_cTrueClass, "===", rb_equal, 1);
     rb_undef_alloc_func(rb_cTrueClass);
     rb_undef_method(CLASS_OF(rb_cTrueClass), "new");
     /*
@@ -3566,6 +3568,7 @@ InitVM_Object(void)
     rb_define_method(rb_cFalseClass, "&", false_and, 1);
     rb_define_method(rb_cFalseClass, "|", false_or, 1);
     rb_define_method(rb_cFalseClass, "^", false_xor, 1);
+    rb_define_method(rb_cFalseClass, "===", rb_equal, 1);
     rb_undef_alloc_func(rb_cFalseClass);
     rb_undef_method(CLASS_OF(rb_cFalseClass), "new");
     /*
diff --git a/test/ruby/test_case.rb b/test/ruby/test_case.rb
index f20d1dfd7e..b9f8ab264d 100644
--- a/test/ruby/test_case.rb
+++ b/test/ruby/test_case.rb
@@ -121,4 +121,25 @@ class TestCase < Test::Unit::TestCase
       end
     }
   end
+
+  module NilEqq
+    refine NilClass do
+      def === other
+        false
+      end
+    end
+  end
+
+  class NilEqqClass
+    using NilEqq
+
+    def eqq(a)
+      case a; when nil then nil; else :not_nil; end
+    end
+  end
+
+
+  def test_deoptimize_nil
+    assert_equal :not_nil, NilEqqClass.new.eqq(nil)
+  end
 end
diff --git a/test/ruby/test_optimization.rb b/test/ruby/test_optimization.rb
index 23c522612f..1c50044f7f 100644
--- a/test/ruby/test_optimization.rb
+++ b/test/ruby/test_optimization.rb
@@ -313,8 +313,11 @@ class TestRubyOptimization < Test::Unit::TestCase
     code = <<-EOF
       case foo
       when "foo" then :foo
+      when true then true
+      when false then false
       when :sym then :sym
       when 6 then :fix
+      when nil then nil
       when 0.1 then :float
       when 0xffffffffffffffff then :big
       else
@@ -323,8 +326,11 @@ class TestRubyOptimization < Test::Unit::TestCase
     EOF
     check = {
       'foo' => :foo,
+      true => true,
+      false => false,
       :sym => :sym,
       6 => :fix,
+      nil => nil,
       0.1 => :float,
       0xffffffffffffffff => :big,
     }
@@ -349,4 +355,11 @@ class TestRubyOptimization < Test::Unit::TestCase
       end;
     end
   end
+
+  def test_eqq
+    [ nil, true, false, 0.1, :sym, 'str', 0xffffffffffffffff ].each do |v|
+      k = v.class.to_s
+      assert_redefine_method(k, '===', "assert_equal(#{v.inspect} === 0, 0)")
+    end
+  end
 end
diff --git a/vm.c b/vm.c
index 71e9eacaf1..be9c7b2f93 100644
--- a/vm.c
+++ b/vm.c
@@ -1373,6 +1373,9 @@ vm_redefinition_check_flag(VALUE klass)
     if (klass == rb_cSymbol) return SYMBOL_REDEFINED_OP_FLAG;
     if (klass == rb_cTime)   return TIME_REDEFINED_OP_FLAG;
     if (klass == rb_cRegexp) return REGEXP_REDEFINED_OP_FLAG;
+    if (klass == rb_cNilClass) return NIL_REDEFINED_OP_FLAG;
+    if (klass == rb_cTrueClass) return TRUE_REDEFINED_OP_FLAG;
+    if (klass == rb_cFalseClass) return FALSE_REDEFINED_OP_FLAG;
     return 0;
 }
 
@@ -1437,7 +1440,8 @@ vm_init_redefined_flag(void)
     OP(DIV, DIV), (C(Fixnum), C(Float));
     OP(MOD, MOD), (C(Fixnum), C(Float));
     OP(Eq, EQ), (C(Fixnum), C(Float), C(String));
-    OP(Eqq, EQQ), (C(Fixnum), C(Bignum), C(Float), C(Symbol), C(String));
+    OP(Eqq, EQQ), (C(Fixnum), C(Bignum), C(Float), C(Symbol), C(String),
+		   C(NilClass), C(TrueClass), C(FalseClass));
     OP(LT, LT), (C(Fixnum), C(Float));
     OP(LE, LE), (C(Fixnum), C(Float));
     OP(GT, GT), (C(Fixnum), C(Float));
diff --git a/vm_core.h b/vm_core.h
index 2343e1154d..aecbe613d8 100644
--- a/vm_core.h
+++ b/vm_core.h
@@ -545,6 +545,9 @@ typedef struct rb_vm_struct {
 #define SYMBOL_REDEFINED_OP_FLAG (1 << 6)
 #define TIME_REDEFINED_OP_FLAG   (1 << 7)
 #define REGEXP_REDEFINED_OP_FLAG (1 << 8)
+#define NIL_REDEFINED_OP_FLAG    (1 << 9)
+#define TRUE_REDEFINED_OP_FLAG   (1 << 10)
+#define FALSE_REDEFINED_OP_FLAG  (1 << 11)
 
 #define BASIC_OP_UNREDEFINED_P(op, klass) (LIKELY((GET_VM()->redefined_flag[(op)]&(klass)) == 0))