CFGSimplificationPhase should not merge a block with itself
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 23 May 2017 18:49:15 +0000 (18:49 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 23 May 2017 18:49:15 +0000 (18:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=172508
<rdar://problem/28424006>

Reviewed by Keith Miller.

JSTests:

* stress/dont-crash-in-cfg-simplification.js: Added.
(bar):
(baz):
(foo):

Source/JavaScriptCore:

CFGSimplificationPhase can run into or create IR that ends up with a
block that has a Jump to itself, and no other predecessors. It should
gracefully handle such IR. Before this patch, it would not. The only criteria
for merging 'block' with 'targetBlock' used to be that 'targetBlock.predecessors.size() == 1'.
The code is written in such a way that if we merge a block with itself, we
will infinite loop until we run out of memory.

Merging a block with itself does not make sense for a few reasons. First,
we're joining the contents of two blocks. What is the definition of joining
a block with itself? I suppose we could simply unroll this self loop
one level, but that would not be wise because this self loop is by definition
unreachable unless it's the root block in the graph (which I think is
invalid IR since we'd never generate bytecode that would do this).

This patch employs an easy fix: we can't merge a block with itself.

* dfg/DFGCFGSimplificationPhase.cpp:
(JSC::DFG::CFGSimplificationPhase::canMergeBlocks):
(JSC::DFG::CFGSimplificationPhase::run):
(JSC::DFG::CFGSimplificationPhase::convertToJump):
(JSC::DFG::CFGSimplificationPhase::mergeBlocks):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@217287 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/stress/dont-crash-in-cfg-simplification.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp

index f849b74..c122837 100644 (file)
@@ -1,3 +1,16 @@
+2017-05-23  Saam Barati  <sbarati@apple.com>
+
+        CFGSimplificationPhase should not merge a block with itself
+        https://bugs.webkit.org/show_bug.cgi?id=172508
+        <rdar://problem/28424006>
+
+        Reviewed by Keith Miller.
+
+        * stress/dont-crash-in-cfg-simplification.js: Added.
+        (bar):
+        (baz):
+        (foo):
+
 2017-05-20  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [FTL] Support GetByVal with ArrayStorage and SlowPutArrayStorage
diff --git a/JSTests/stress/dont-crash-in-cfg-simplification.js b/JSTests/stress/dont-crash-in-cfg-simplification.js
new file mode 100644 (file)
index 0000000..c7687bf
--- /dev/null
@@ -0,0 +1,17 @@
+function bar() {}
+noInline(bar);
+
+function baz() { }
+
+function foo() {
+    if (typeof baz !== "undefined") {
+    } else {
+        // The test here is to make sure that we don't merge this basic block
+        // with itself. If we did, we'd infinite loop in the compiler and eventually
+        // crash due to OOM when growing a Vector.
+        while (true) bar();
+    }
+}
+noInline(foo);
+for (let i = 0; i < 10000; ++i)
+    foo();
index e15d9a1..3a1a7cb 100644 (file)
@@ -1,3 +1,33 @@
+2017-05-23  Saam Barati  <sbarati@apple.com>
+
+        CFGSimplificationPhase should not merge a block with itself
+        https://bugs.webkit.org/show_bug.cgi?id=172508
+        <rdar://problem/28424006>
+
+        Reviewed by Keith Miller.
+
+        CFGSimplificationPhase can run into or create IR that ends up with a
+        block that has a Jump to itself, and no other predecessors. It should
+        gracefully handle such IR. Before this patch, it would not. The only criteria
+        for merging 'block' with 'targetBlock' used to be that 'targetBlock.predecessors.size() == 1'.
+        The code is written in such a way that if we merge a block with itself, we
+        will infinite loop until we run out of memory.
+        
+        Merging a block with itself does not make sense for a few reasons. First,
+        we're joining the contents of two blocks. What is the definition of joining
+        a block with itself? I suppose we could simply unroll this self loop
+        one level, but that would not be wise because this self loop is by definition
+        unreachable unless it's the root block in the graph (which I think is
+        invalid IR since we'd never generate bytecode that would do this).
+        
+        This patch employs an easy fix: we can't merge a block with itself.
+
+        * dfg/DFGCFGSimplificationPhase.cpp:
+        (JSC::DFG::CFGSimplificationPhase::canMergeBlocks):
+        (JSC::DFG::CFGSimplificationPhase::run):
+        (JSC::DFG::CFGSimplificationPhase::convertToJump):
+        (JSC::DFG::CFGSimplificationPhase::mergeBlocks):
+
 2017-05-22  Brian Burg  <bburg@apple.com>
 
         Web Inspector: webkit reload policy should match default behavior
index 01e0cde..7c155ee 100644 (file)
@@ -43,6 +43,11 @@ public:
         : Phase(graph, "CFG simplification")
     {
     }
+
+    bool canMergeBlocks(BasicBlock* block, BasicBlock* targetBlock)
+    {
+        return targetBlock->predecessors.size() == 1 && targetBlock != block;
+    }
     
     bool run()
     {
@@ -61,11 +66,15 @@ public:
                 if (!block)
                     continue;
                 ASSERT(block->isReachable);
+
+                auto canMergeWithBlock = [&] (BasicBlock* targetBlock) {
+                    return canMergeBlocks(block, targetBlock);
+                };
             
                 switch (block->terminal()->op()) {
                 case Jump: {
                     // Successor with one predecessor -> merge.
-                    if (block->successor(0)->predecessors.size() == 1) {
+                    if (canMergeWithBlock(block->successor(0))) {
                         ASSERT(block->successor(0)->predecessors[0] == block);
                         if (extremeLogging)
                             m_graph.dump();
@@ -93,7 +102,7 @@ public:
                         bool condition = branchCondition(block->cfaBranchDirection);
                         BasicBlock* targetBlock = block->successorForCondition(condition);
                         BasicBlock* jettisonedBlock = block->successorForCondition(!condition);
-                        if (targetBlock->predecessors.size() == 1) {
+                        if (canMergeWithBlock(targetBlock)) {
                             if (extremeLogging)
                                 m_graph.dump();
                             m_graph.dethread();
@@ -177,7 +186,7 @@ public:
                                 jettisonedBlocks.append(successor);
                         }
                         
-                        if (targetBlock->predecessors.size() == 1) {
+                        if (canMergeWithBlock(targetBlock)) {
                             if (extremeLogging)
                                 m_graph.dump();
                             m_graph.dethread();
@@ -255,7 +264,7 @@ private:
     {
         ASSERT(targetBlock);
         ASSERT(targetBlock->isReachable);
-        if (targetBlock->predecessors.size() == 1) {
+        if (canMergeBlocks(block, targetBlock)) {
             m_graph.dethread();
             mergeBlocks(block, targetBlock, noBlocks());
         } else {
@@ -318,6 +327,7 @@ private:
         BasicBlock* firstBlock, BasicBlock* secondBlock,
         Vector<BasicBlock*, 1> jettisonedBlocks)
     {
+        RELEASE_ASSERT(canMergeBlocks(firstBlock, secondBlock));
         // This will add all of the nodes in secondBlock to firstBlock, but in so doing
         // it will also ensure that any GetLocals from the second block that refer to
         // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,