JIT fixnum cases (with a value span <= 32) as a tableswitch

... instead of falling back to lookupswitch
jruby · Jan 9, 2017 · 3a0e1ee · 3a0e1ee
1 parent fa9060d
commit 3a0e1ee
Show file tree

Hide file tree

Showing 2 changed files with 61 additions and 4 deletions.
diff --git a/core/src/main/java/org/jruby/ir/targets/JVMVisitor.java b/core/src/main/java/org/jruby/ir/targets/JVMVisitor.java
@@ -848,6 +848,11 @@ public void BreakInstr(BreakInstr breakInstr) {
 
     }
 
+    // max (case) values span that generates a tableswitch instruction
+    //   case 0, 2, 4, 8, 16, 32 still generates a tableswitch (filling in holes)
+    //   case 0, 10, 100 fallbacks to generating a lookupswitch
+    private static final int MAX_TABLE_SWITCH_SIZE = 32 + 1;
+
     public void BSwitchInstr(BSwitchInstr bswitchinstr) {
         visit(bswitchinstr.getCaseOperand());
         jvmAdapter().dup();
@@ -860,17 +865,34 @@ public void BSwitchInstr(BSwitchInstr bswitchinstr) {
         Label[] targets = bswitchinstr.getTargets();
         org.objectweb.asm.Label[] jvmTargets = new org.objectweb.asm.Label[targets.length];
         for (int i = 0; i < targets.length; i++) jvmTargets[i] = getJVMLabel(targets[i]);
-
+        org.objectweb.asm.Label defaultTarget = getJVMLabel(bswitchinstr.getElseTarget());
         // if jump table is all contiguous values, use a tableswitch
         int[] jumps = bswitchinstr.getJumps(); // always ordered e.g. [2, 3, 4]
 
         int low = jumps[0]; // 2
         int high = jumps[jumps.length - 1]; // 4
         int span = high - low + 1;
         if (span == jumps.length) { // perfectly compact - no "holes"
-            jvmAdapter().tableswitch(low, high, getJVMLabel(bswitchinstr.getElseTarget()), jvmTargets);
-        } else {
-            jvmAdapter().lookupswitch(getJVMLabel(bswitchinstr.getElseTarget()), bswitchinstr.getJumps(), jvmTargets);
+            jvmAdapter().tableswitch(low, high, defaultTarget, jvmTargets);
+        }
+        else if (span <= MAX_TABLE_SWITCH_SIZE) { // an imperfect switch
+            org.objectweb.asm.Label[] realTargets = jvmTargets;
+            jvmTargets = new org.objectweb.asm.Label[span];
+            jvmTargets[0] = realTargets[0]; int p = jumps[0] + 1; int t = 1;
+            for ( int i = 1; i < jumps.length; i++ ) {
+                int cj = jumps[i];
+                if (cj == p) {
+                    jvmTargets[t++] = realTargets[i]; p = cj + 1;
+                }
+                else { // fill in holes with cases to jump to else part
+                    while (cj > p++) jvmTargets[t++] = defaultTarget;
+                    jvmTargets[t++] = realTargets[i];
+                }
+            }
+            jvmAdapter().tableswitch(low, high, defaultTarget, jvmTargets);
+        }
+        else {
+            jvmAdapter().lookupswitch(defaultTarget, bswitchinstr.getJumps(), jvmTargets);
         }
         jvmAdapter().label(notFixnum);
         jvmAdapter().pop();

diff --git a/test/jruby/test_case.rb b/test/jruby/test_case.rb
@@ -104,6 +104,41 @@ def case_24(*args)
     end
   end
 
+  def test_big_case_with_holes
+    params = [0, 1, 2, 4, 5, 10, 11, 18, 19, 20, 21, 22, -1,  -2]
+    expect = [1, 0, 3, 5, 4,  9, 10, 17, 18, 21, 20, 21, nil, -3]
+    assert_equal expect, params.map { |p| case_01359_21(p) }
+  end
+
+  def case_01359_21(p)
+    case p + 1
+      when 0 then nil
+      when 1 then 1
+      when 3 then 3
+      when 5 then 5
+      when 9 then 9
+      when 21
+        return 21
+      else p - 1
+    end
+  end
+
+  def test_multi_case_with_holes
+    params = [  0, 1, 2, 3, 4, 5, 8, 9, 10, 12, 13, 14, 15, 16, 17]
+    expect = [nil, 0, 1, 3, 1, 5, 1, 9, 10, 12, 13, 14, 15,  2, 17]
+    assert_equal expect, params.map { |p| case_2481632(p) }
+  end
+
+  def case_2481632(p)
+    case p % 100
+      when 0 then nil
+      when 1 then 0
+      when 2, 4, 8 then 1
+      when 16, 32 then 2
+      else p % 31
+    end
+  end
+
   def test_case_no_match_returns_nil
     x = case nil
     when String then "HEH1"