Changeset 195422 in webkit

Timestamp:

Jan 21, 2016 2:56:21 PM (8 years ago)

Author:

benjamin@webkit.org

Message:

[JSC] foldPathConstants() makes invalid assumptions with Switch
​https://bugs.webkit.org/show_bug.cgi?id=153324

Reviewed by Filip Pizlo.

If a Switch() has two cases pointing to the same basic block, foldPathConstants()
was adding two override for that block with two different constants.
If the block with the Switch dominates the target, both override were equally valid
and we were assuming any of the constants as the value in the target block.

See testSwitchTargettingSameBlockFoldPathConstant() for an example that breaks.

This patch adds checks to ignore any block that is reached more than
once by the control value.

• b3/B3FoldPathConstants.cpp:
• b3/B3Generate.cpp:

(JSC::B3::generateToAir):

• b3/testb3.cpp:

(JSC::B3::testSwitchTargettingSameBlock):
(JSC::B3::testSwitchTargettingSameBlockFoldPathConstant):
(JSC::B3::run):

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• b3/B3FoldPathConstants.cpp (modified) (3 diffs)
• b3/B3Generate.cpp (modified) (1 diff)
• b3/testb3.cpp (modified) (2 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-01-21  Benjamin Poulain  <benjamin@webkit.org>
+
+        [JSC] foldPathConstants() makes invalid assumptions with Switch
+        https://bugs.webkit.org/show_bug.cgi?id=153324
+
+        Reviewed by Filip Pizlo.
+
+        If a Switch() has two cases pointing to the same basic block, foldPathConstants()
+        was adding two override for that block with two different constants.
+        If the block with the Switch dominates the target, both override were equally valid
+        and we were assuming any of the constants as the value in the target block.
+
+        See testSwitchTargettingSameBlockFoldPathConstant() for an example that breaks.
+
+        This patch adds checks to ignore any block that is reached more than
+        once by the control value.
+
+        * b3/B3FoldPathConstants.cpp:
+        * b3/B3Generate.cpp:
+        (JSC::B3::generateToAir):
+        * b3/testb3.cpp:
+        (JSC::B3::testSwitchTargettingSameBlock):
+        (JSC::B3::testSwitchTargettingSameBlockFoldPathConstant):
+        (JSC::B3::run):
+
 2016-01-21  Filip Pizlo  <fpizlo@apple.com>
 

trunk/Source/JavaScriptCore/b3/B3FoldPathConstants.cpp

@@ -91 +91 @@
             switch (branch->opcode()) {
             case Branch:
+                if (branch->successorBlock(0) == branch->successorBlock(1))
+                    continue;
                 addOverride(
                     block, branch->child(0),
@@ -98 +100 @@
                     Override::constant(branch->successorBlock(1), 0));
                 break;
-            case Switch:
+            case Switch: {
+                HashMap<BasicBlock*, unsigned> targetUses;
+                for (const SwitchCase& switchCase : *branch->as<SwitchValue>())
+                    targetUses.add(switchCase.targetBlock(), 0).iterator->value++;
+
                 for (const SwitchCase& switchCase : *branch->as<SwitchValue>()) {
+                    if (targetUses.find(switchCase.targetBlock())->value != 1)
+                        continue;
+
                     addOverride(
                         block, branch->child(0),
@@ -105 +114 @@
                 }
                 break;
+            }
             default:
                 break;

trunk/Source/JavaScriptCore/b3/B3Generate.cpp

@@ -92 +92 @@
     if (optLevel >= 1) {
         reduceStrength(procedure);
-        
+
         // FIXME: Add more optimizations here.
         // https://bugs.webkit.org/show_bug.cgi?id=150507

trunk/Source/JavaScriptCore/b3/testb3.cpp

@@ -8428 +8428 @@
     CHECK(!invoke<int32_t>(*code, degree * gap, 42, 11));
     CHECK(!invoke<int32_t>(*code, degree * gap + 1, 42, 11));
+}
+
+void testSwitchTargettingSameBlock()
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    BasicBlock* terminate = proc.addBlock();
+    terminate->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        terminate->appendNew<Const32Value>(proc, Origin(), 5));
+
+    SwitchValue* switchValue = root->appendNew<SwitchValue>(
+        proc, Origin(),
+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+        FrequentedBlock(terminate));
+
+    BasicBlock* otherTarget = proc.addBlock();
+    otherTarget->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        otherTarget->appendNew<Const32Value>(proc, Origin(), 42));
+    switchValue->appendCase(SwitchCase(3, FrequentedBlock(otherTarget)));
+    switchValue->appendCase(SwitchCase(13, FrequentedBlock(otherTarget)));
+
+    auto code = compile(proc);
+
+    for (unsigned i = 0; i < 20; ++i) {
+        int32_t expected = (i == 3 || i == 13) ? 42 : 5;
+        CHECK(invoke<int32_t>(*code, i) == expected);
+    }
+}
+
+void testSwitchTargettingSameBlockFoldPathConstant()
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    BasicBlock* terminate = proc.addBlock();
+    terminate->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        terminate->appendNew<Const32Value>(proc, Origin(), 42));
+
+    Value* argument = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+    SwitchValue* switchValue = root->appendNew<SwitchValue>(
+        proc, Origin(),
+        argument,
+        FrequentedBlock(terminate));
+
+    BasicBlock* otherTarget = proc.addBlock();
+    otherTarget->appendNew<ControlValue>(
+        proc, Return, Origin(), argument);
+    switchValue->appendCase(SwitchCase(3, FrequentedBlock(otherTarget)));
+    switchValue->appendCase(SwitchCase(13, FrequentedBlock(otherTarget)));
+
+    auto code = compile(proc);
+
+    for (unsigned i = 0; i < 20; ++i) {
+        int32_t expected = (i == 3 || i == 13) ? i : 42;
+        CHECK(invoke<int32_t>(*code, i) == expected);
+    }
 }
 
@@ -10385 +10445 @@
     RUN(testSwitchChillDiv(100, 1));
     RUN(testSwitchChillDiv(100, 100));
+
+    RUN(testSwitchTargettingSameBlock());
+    RUN(testSwitchTargettingSameBlockFoldPathConstant());
 
     RUN(testTrunc(0));