[hydrogen] optimize switch with string clauses

test/mjsunit/switch.js

 // Copyright 2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
 //       with the distribution.
 //     * Neither the name of Google Inc. nor the names of its
 //       contributors may be used to endorse or promote products derived
 //       from this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
+// Flags: --allow-natives-syntax
+
 function f0() {
   switch (0) {
     // switch deliberately left empty
   }
 }
 
 f0();  // no errors
 
 function f1(x) {
   switch (x) {
@@ skipping 81 matching lines @@
   }
   return x;
 }
 
 
 assertEquals(3, f4(0), "fallthrough-switch.0");
 assertEquals(3, f4(1), "fallthrough-switch.1");
 assertEquals(3, f4(2), "fallthrough-switch.2");
 assertEquals(5, f4(3), "fallthrough-switch.3");
 
+function f4_string(tag, x) {
+  switch(tag) {
+    case 'zero':
+      x++;
+    case 'two':
+      x++;
+  }
+  return x;
+}
+
+// Symbols
+assertEquals(2, f4_string('zero', 0), "fallthrough-string-switch.0");
+assertEquals(1, f4_string('one', 1), "fallthrough-string-switch.1");
+assertEquals(3, f4_string('two', 2), "fallthrough-string-switch.2");
+
+// Strings
+assertEquals(2, f4_string('_zero'.slice(1), 0), "fallthrough-string-switch.3");
+assertEquals(1, f4_string('_one'.slice(1), 1), "fallthrough-string-switch.4");
+assertEquals(3, f4_string('_two'.slice(1), 2), "fallthrough-string-switch.5");
+
+// Oddball
+assertEquals(3, f4_string(null, 3), "fallthrough-string-switch.6");
+
+// Test for regression
+function regress_string(value) {
+  var json = 1;
+  switch (typeof value) {
+    case 'object':
+      break;
+
+    default:
+
+  }
+  return json;
+};
+assertEquals(1, regress_string('object'), 'regression-string');
 
 function f5(x) {
   switch(x) {
      case -2: return true;
      case -1: return false;
      case 0: return true;
      case 2: return false;
      default: return 42;
   }
 }
@@ skipping 141 matching lines @@
          "    }\n" +
          "  }\n" +
          "  return res;\n" +
          "})";
   return eval(res);
 }
 var verylong_size = 1000;
 var verylong = makeVeryLong(verylong_size);
 
 assertEquals(verylong_size * 2 + 1, verylong());
+
+//
+// Test suite below aims to cover all possible combinations of following:
+//
+//  clauses  |   tags   |   type feedback   |  optimization
+// =========================================================
+//  strings  |  symbol  |     all           |      on
+//  smis     |  string  |     target        |      off
+//  mixed    |  oddball |     non-target    |
+//           |  smis    |     none          |
+//           |  heapnum |                   |
+// =========================================================
+

[fschneider, 2011/11/17 10:05:32]

Global unique id for each generated test case needed:

var test_id = 0;

+// Function-with-switch generator
+var clause_values = {
+  string: ['abc', 'def', 'ghi', 'jkl'],
+  smi: [1, 2, 3, 4],
+  mixed: ['abc', 1, 'def', 2, 'ghi', 3, 'jkl', 4]
+};
+
+function switch_gen(clause_type, feedback, optimize) {
+  var values = clause_values[clause_type];
+
+  function opt(fn) {
+    if (feedback === 'all') {
+      values.forEach(fn);
+    } else if (Array.isArray(feedback)) {
+      // Non-target
+      values.filter(function(v) {
+        return feedback.indexOf(v) === -1;
+      }).forEach(fn);
+    } else if (feedback !== undefined) {
+      // Target
+      fn(feedback);
+    } else {
+      // None
+    }
+
+    if (optimize) %OptimizeFunctionOnNextCall(fn);
+
+    return fn;
+  };
+
+  return opt(new Function(
+      'tag',
+      'switch(tag) {' +

[fschneider, 2011/11/17 10:05:32]

Here we need some kind of unique id so that the compilation cache does not
return a previous version of the unoptimized code and spoils our type feedback:

'"' + (test_id++) + '"; switch(tag) {' +

+      values.map(function(value) {
+        return 'case ' + JSON.stringify(value) + ': return' +
+               JSON.stringify('ok-' + value);
+      }).join(';') +
+      '}'
+  ));
+};
+
+function test_switch(clause_type, test_type, feedback, optimize) {
+  var pairs = [],
+      fn = switch_gen(clause_type, feedback, optimize);
+
+  if (Array.isArray(test_type)) {
+    pairs = test_type.map(function(v) {
+      return {
+        value: v,
+        expected: 'ok-' + v
+      };
+    });
+  } else if (test_type === 'symbols') {
+    pairs = clause_values.string.map(function(v) {
+      return {
+        value: v,
+        expected: clause_type !== 'smi' ? 'ok-' + v : undefined
+      };
+    });
+  } else if (test_type === 'strings') {
+    pairs = clause_values.string.map(function(v) {
+      return {
+        value: ('%%' + v).slice(2),
+        expected: clause_type !== 'smi' ? 'ok-' + v : undefined
+      };
+    });
+  } else if (test_type === 'oddball') {
+    pairs = [
+      { value: null, expected: undefined },
+      { value: NaN, expected: undefined },
+      { value: undefined, expected: undefined }
+    ];
+  } else if (test_type === 'smi') {
+    pairs = clause_values.smi.map(function(v) {
+      return {
+        value: v,
+        expected: clause_type !== 'string' ? 'ok-' + v : undefined
+      };
+    });
+  } else if (test_type === 'heapnum') {
+    pairs = clause_values.smi.map(function(v) {
+      return {
+        value: ((v * 17)/16) - ((v*17)%16/16),
+        expected: clause_type !== 'string' ? 'ok-' + v : undefined
+      };
+    });
+  }
+
+  pairs.forEach(function(pair) {
+    assertEquals(fn(pair.value), pair.expected);
+  });
+};
+
+// test_switch(clause_type, test_type, feedback, optimize);
+
+function test_switches(opt) {
+  var test_types = ['symbols', 'strings', 'oddball', 'smi', 'heapnum'];
+
+  function test(clause_type) {
+    var values = clause_values[clause_type];
+
+    test_types.forEach(function(test_type) {
+      test_switch(clause_type, test_type, 'all', opt);
+      test_switch(clause_type, test_type, 'none', opt);
+
+      // Targeting specific clause feedback
+      values.forEach(function(value) {
+        test_switch(clause_type, test_type, [value], value, opt);
+        test_switch(clause_type, test_type, value, value, opt);
+      });
+    });
+  };
+
+  test('string');
+  test('smi');
+  test('mixed');
+};
+
+test_switches(false);
+test_switches(true);