- Revision
- 243639
- Author
- [email protected]
- Date
- 2019-03-28 21:42:42 -0700 (Thu, 28 Mar 2019)
Log Message
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.
JSTests:
* stress/map-b3-licm-infinite-loop.js: Added.
Source/_javascript_Core:
* 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):
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (243638 => 243639)
--- trunk/JSTests/ChangeLog 2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/JSTests/ChangeLog 2019-03-29 04:42:42 UTC (rev 243639)
@@ -1,3 +1,12 @@
+2019-03-28 Saam Barati <[email protected]>
+
+ 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 <[email protected]>
CodeBlock::jettison() should disallow repatching its own calls
Added: trunk/JSTests/stress/map-b3-licm-infinite-loop.js (0 => 243639)
--- trunk/JSTests/stress/map-b3-licm-infinite-loop.js (rev 0)
+++ trunk/JSTests/stress/map-b3-licm-infinite-loop.js 2019-03-29 04:42:42 UTC (rev 243639)
@@ -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 {}
Modified: trunk/Source/_javascript_Core/ChangeLog (243638 => 243639)
--- trunk/Source/_javascript_Core/ChangeLog 2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/_javascript_Core/ChangeLog 2019-03-29 04:42:42 UTC (rev 243639)
@@ -1,3 +1,14 @@
+2019-03-28 Saam Barati <[email protected]>
+
+ 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 <[email protected]>
Opcode.h(159,27): warning: adding 'unsigned int' to a string does not append to the string [-Wstring-plus-int]
Modified: trunk/Source/_javascript_Core/b3/testb3.cpp (243638 => 243639)
--- trunk/Source/_javascript_Core/b3/testb3.cpp 2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/_javascript_Core/b3/testb3.cpp 2019-03-29 04:42:42 UTC (rev 243639)
@@ -16812,6 +16812,51 @@
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 @@
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));
Modified: trunk/Source/WTF/ChangeLog (243638 => 243639)
--- trunk/Source/WTF/ChangeLog 2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/WTF/ChangeLog 2019-03-29 04:42:42 UTC (rev 243639)
@@ -1,3 +1,57 @@
+2019-03-28 Saam Barati <[email protected]>
+
+ 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 <[email protected]>
Un-fix the build
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (243638 => 243639)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2019-03-29 04:42:42 UTC (rev 243639)
@@ -398,6 +398,7 @@
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>"; };
@@ -1126,6 +1127,7 @@
A8A4730C151A825B004123FF /* SizeLimits.cpp */,
7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
+ 79038E05224B05A7004C0738 /* SpanningTree.h */,
A8A4730D151A825B004123FF /* Spectrum.h */,
A8A4730E151A825B004123FF /* StackBounds.cpp */,
A8A4730F151A825B004123FF /* StackBounds.h */,
Modified: trunk/Source/WTF/wtf/BackwardsGraph.h (243638 => 243639)
--- trunk/Source/WTF/wtf/BackwardsGraph.h 2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/WTF/wtf/BackwardsGraph.h 2019-03-29 04:42:42 UTC (rev 243639)
@@ -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 @@
}
};
+ {
+ // 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())
Added: trunk/Source/WTF/wtf/SpanningTree.h (0 => 243639)
--- trunk/Source/WTF/wtf/SpanningTree.h (rev 0)
+++ trunk/Source/WTF/wtf/SpanningTree.h 2019-03-29 04:42:42 UTC (rev 243639)
@@ -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;
+};
