BackwardsGraph needs to consider back edges as the backward's root successor
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 29 Mar 2019 04:42:42 +0000 (04:42 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 29 Mar 2019 04:42:42 +0000 (04:42 +0000)
https://bugs.webkit.org/show_bug.cgi?id=195991

Reviewed by Filip Pizlo.

JSTests:

* stress/map-b3-licm-infinite-loop.js: Added.

Source/JavaScriptCore:

* b3/testb3.cpp:
(JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
(JSC::B3::run):

Source/WTF:

Previously, our backwards graph analysis was slightly wrong. The idea of
backwards graph is that the root of the graph has edges to terminals in
the original graph. And then the original directed edges in the graph are flipped.

However, we weren't considering loops as a form of terminality. For example,
we wouldn't consider an infinite loop as a terminal. So there were no edges
from the root to a node in the infinite loop. This lead us to make mistakes
when we used backwards dominators to compute control flow equivalence.

This is better understood in an example:

```
preheader:
while (1) {
    if (!isCell(v))
        continue;
    load structure ID
    if (cond)
       continue;
    return
}
```

In the previous version of this algorithm, the only edge from the backwards
root would be to the block containing the return. This would lead us to
believe that the loading of the structureID backwards dominates the preheader,
leading us to believe it's control flow equivalent to preheader. This is
obviously wrong, since we can loop forever if "v" isn't a cell.

The solution here is to treat any backedge in the graph as a "terminal" node.
Since a backedge implies the existence of a loop.

In the above example, the backwards root now has an edge to both blocks with
"continue". This prevents us from falsely claiming that the return is control
flow equivalent with the preheader.

This patch uses DFS spanning trees to compute back edges. An edge
u->v is a back edge when u is a descendent of v in the DFS spanning
tree of the Graph.

* WTF.xcodeproj/project.pbxproj:
* wtf/BackwardsGraph.h:
(WTF::BackwardsGraph::BackwardsGraph):
* wtf/SpanningTree.h: Added.
(SpanningTree::SpanningTree):
(SpanningTree::isDescendent):

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

JSTests/ChangeLog
JSTests/stress/map-b3-licm-infinite-loop.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/testb3.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BackwardsGraph.h
Source/WTF/wtf/SpanningTree.h [new file with mode: 0644]

index 552fbb9..40bbbdb 100644 (file)
@@ -1,3 +1,12 @@
+2019-03-28  Saam Barati  <sbarati@apple.com>
+
+        BackwardsGraph needs to consider back edges as the backward's root successor
+        https://bugs.webkit.org/show_bug.cgi?id=195991
+
+        Reviewed by Filip Pizlo.
+
+        * stress/map-b3-licm-infinite-loop.js: Added.
+
 2019-03-28  Tadeu Zagallo  <tzagallo@apple.com>
 
         CodeBlock::jettison() should disallow repatching its own calls
diff --git a/JSTests/stress/map-b3-licm-infinite-loop.js b/JSTests/stress/map-b3-licm-infinite-loop.js
new file mode 100644 (file)
index 0000000..828b2d5
--- /dev/null
@@ -0,0 +1,25 @@
+let count = 0;
+function foo() {
+    ++count;
+    if (count === 1000000)
+        throw new Error;
+}
+noInline(foo);
+
+function test() {
+    let map = new Map();
+
+    let count = 0;
+    for (let i = 1000000 % 0; ; ) {
+        if (!map.has(i)) {
+            map.set(i, i);
+        }
+        foo();
+    }
+
+    return map;
+}
+
+try {
+    test();
+} catch {}
index be69023..045d488 100644 (file)
@@ -1,3 +1,14 @@
+2019-03-28  Saam Barati  <sbarati@apple.com>
+
+        BackwardsGraph needs to consider back edges as the backward's root successor
+        https://bugs.webkit.org/show_bug.cgi?id=195991
+
+        Reviewed by Filip Pizlo.
+
+        * b3/testb3.cpp:
+        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
+        (JSC::B3::run):
+
 2019-03-28  Fujii Hironori  <Hironori.Fujii@sony.com>
 
         Opcode.h(159,27): warning: adding 'unsigned int' to a string does not append to the string [-Wstring-plus-int]
index 0e371bc..d5319f5 100644 (file)
@@ -16812,6 +16812,51 @@ void testReportUsedRegistersLateUseFollowedByEarlyDefDoesNotMarkUseAsDead()
     compileAndRun<void>(proc);
 }
 
+void testInfiniteLoopDoesntCauseBadHoisting()
+{
+    Procedure proc;
+    if (proc.optLevel() < 2)
+        return;
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* header = proc.addBlock();
+    BasicBlock* loadBlock = proc.addBlock();
+    BasicBlock* postLoadBlock = proc.addBlock();
+
+    Value* arg = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+    root->appendNewControlValue(proc, Jump, Origin(), header);
+
+    header->appendNewControlValue(
+        proc, Branch, Origin(),
+        header->appendNew<Value>(proc, Equal, Origin(),
+            arg,
+            header->appendNew<Const64Value>(proc, Origin(), 10)), header, loadBlock);
+
+    PatchpointValue* patchpoint = loadBlock->appendNew<PatchpointValue>(proc, Void, Origin());
+    patchpoint->effects = Effects::none();
+    patchpoint->effects.writesLocalState = true; // Don't DCE this.
+    patchpoint->setGenerator(
+        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
+            // This works because we don't have callee saves.
+            jit.emitFunctionEpilogue();
+            jit.ret();
+        });
+
+    Value* badLoad = loadBlock->appendNew<MemoryValue>(proc, Load, Int64, Origin(), arg, 0);
+
+    loadBlock->appendNewControlValue(
+        proc, Branch, Origin(),
+        loadBlock->appendNew<Value>(proc, Equal, Origin(),
+            badLoad,
+            loadBlock->appendNew<Const64Value>(proc, Origin(), 45)), header, postLoadBlock);
+
+    postLoadBlock->appendNewControlValue(proc, Return, Origin(), badLoad);
+
+    // The patchpoint early ret() works because we don't have callee saves.
+    auto code = compileProc(proc);
+    RELEASE_ASSERT(!proc.calleeSaveRegisterAtOffsetList().size()); 
+    invoke<void>(*code, static_cast<uint64_t>(55)); // Shouldn't crash dereferncing 55.
+}
+
 // Make sure the compiler does not try to optimize anything out.
 NEVER_INLINE double zero()
 {
@@ -18429,6 +18474,8 @@ void run(const char* filter)
 
     RUN(testLoopWithMultipleHeaderEdges());
 
+    RUN(testInfiniteLoopDoesntCauseBadHoisting());
+
     if (isX86()) {
         RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));
         RUN(testBranchBitAndImmFusion(Identity, Int64, 0xff, Air::BranchTest32, Air::Arg::Tmp));
index 5c577eb..4741f39 100644 (file)
@@ -1,3 +1,57 @@
+2019-03-28  Saam Barati  <sbarati@apple.com>
+
+        BackwardsGraph needs to consider back edges as the backward's root successor
+        https://bugs.webkit.org/show_bug.cgi?id=195991
+
+        Reviewed by Filip Pizlo.
+
+        Previously, our backwards graph analysis was slightly wrong. The idea of
+        backwards graph is that the root of the graph has edges to terminals in
+        the original graph. And then the original directed edges in the graph are flipped.
+        
+        However, we weren't considering loops as a form of terminality. For example,
+        we wouldn't consider an infinite loop as a terminal. So there were no edges
+        from the root to a node in the infinite loop. This lead us to make mistakes
+        when we used backwards dominators to compute control flow equivalence.
+        
+        This is better understood in an example:
+        
+        ```
+        preheader:
+        while (1) {
+            if (!isCell(v))
+                continue;
+            load structure ID
+            if (cond)
+               continue;
+            return
+        }
+        ```
+        
+        In the previous version of this algorithm, the only edge from the backwards
+        root would be to the block containing the return. This would lead us to
+        believe that the loading of the structureID backwards dominates the preheader,
+        leading us to believe it's control flow equivalent to preheader. This is
+        obviously wrong, since we can loop forever if "v" isn't a cell.
+        
+        The solution here is to treat any backedge in the graph as a "terminal" node.
+        Since a backedge implies the existence of a loop.
+        
+        In the above example, the backwards root now has an edge to both blocks with
+        "continue". This prevents us from falsely claiming that the return is control
+        flow equivalent with the preheader.
+        
+        This patch uses DFS spanning trees to compute back edges. An edge
+        u->v is a back edge when u is a descendent of v in the DFS spanning
+        tree of the Graph.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/BackwardsGraph.h:
+        (WTF::BackwardsGraph::BackwardsGraph):
+        * wtf/SpanningTree.h: Added.
+        (SpanningTree::SpanningTree):
+        (SpanningTree::isDescendent):
+
 2019-03-28  Tim Horton  <timothy_horton@apple.com>
 
         Un-fix the build
index f994941..6c0d951 100644 (file)
                70ECA60A1B02426800449739 /* AtomicStringImpl.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringImpl.cpp; sourceTree = "<group>"; };
                70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
                70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
+               79038E05224B05A7004C0738 /* SpanningTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpanningTree.h; sourceTree = "<group>"; };
                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
                793BFADD9CED44B8B9FBCA16 /* StdUnorderedMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdUnorderedMap.h; sourceTree = "<group>"; };
                795212021F42588800BD6421 /* SingleRootGraph.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SingleRootGraph.h; sourceTree = "<group>"; };
                                A8A4730C151A825B004123FF /* SizeLimits.cpp */,
                                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
                                A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
+                               79038E05224B05A7004C0738 /* SpanningTree.h */,
                                A8A4730D151A825B004123FF /* Spectrum.h */,
                                A8A4730E151A825B004123FF /* StackBounds.cpp */,
                                A8A4730F151A825B004123FF /* StackBounds.h */,
index ec49700..f4ba377 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -29,6 +29,7 @@
 #include <wtf/GraphNodeWorklist.h>
 #include <wtf/Noncopyable.h>
 #include <wtf/SingleRootGraph.h>
+#include <wtf/SpanningTree.h>
 #include <wtf/StdLibExtras.h>
 
 namespace WTF {
@@ -57,6 +58,23 @@ public:
             }
         };
 
+        {
+            // Loops are a form of terminality (you can loop forever). To have a loop, you need to
+            // have a back edge. An edge u->v is a back edge when u is a descendent of v in the
+            // DFS spanning tree of the Graph.
+            SpanningTree<Graph> spanningTree(graph);
+            for (unsigned i = 0; i < graph.numNodes(); ++i) {
+                if (typename Graph::Node node = graph.node(i)) {
+                    for (typename Graph::Node successor : graph.successors(node)) {
+                        if (spanningTree.isDescendent(node, successor)) {
+                            addRootSuccessor(node);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+
         for (unsigned i = 0; i < graph.numNodes(); ++i) {
             if (typename Graph::Node node = graph.node(i)) {
                 if (!graph.successors(node).size())
diff --git a/Source/WTF/wtf/SpanningTree.h b/Source/WTF/wtf/SpanningTree.h
new file mode 100644 (file)
index 0000000..882d763
--- /dev/null
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``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 APPLE INC. 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. 
+ */
+
+#pragma once
+
+#include <wtf/GraphNodeWorklist.h>
+
+template<typename Graph>
+class SpanningTree {
+public:
+    SpanningTree(Graph& graph)
+        : m_graph(graph)
+        , m_data(graph.template newMap<Data>())
+    {
+        ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
+        worklist.push(m_graph.root(), 0);
+    
+        size_t number = 0;
+
+        while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
+            typename Graph::Node block = item.node;
+            unsigned successorIndex = item.data;
+        
+            // We initially push with successorIndex = 0 regardless of whether or not we have any
+            // successors. This is so that we can assign our prenumber. Subsequently we get pushed
+            // with higher successorIndex values. We finally push successorIndex == # successors
+            // to calculate our post number.
+            ASSERT(!successorIndex || successorIndex <= m_graph.successors(block).size());
+
+            if (!successorIndex)
+                m_data[block].pre = number++;
+        
+            if (successorIndex < m_graph.successors(block).size()) {
+                unsigned nextSuccessorIndex = successorIndex + 1;
+                // We need to push this even if this is out of bounds so we can compute
+                // the post number.
+                worklist.forcePush(block, nextSuccessorIndex);
+
+                typename Graph::Node successorBlock = m_graph.successors(block)[successorIndex];
+                worklist.push(successorBlock, 0);
+            } else
+                m_data[block].post = number++;
+        }
+    }
+
+    // Returns true if a is a descendent of b.
+    // Note a is a descendent of b if they're equal.
+    bool isDescendent(typename Graph::Node a, typename Graph::Node b)
+    {
+        return m_data[b].pre <= m_data[a].pre
+            && m_data[b].post >= m_data[a].post;
+    }
+
+private:
+    struct Data {
+        size_t pre;
+        size_t post;
+    };
+
+    Graph& m_graph;
+    typename Graph::template Map<Data> m_data;
+};