Diff
Modified: branches/safari-607-branch/JSTests/ChangeLog (244121 => 244122)
--- branches/safari-607-branch/JSTests/ChangeLog 2019-04-10 17:10:59 UTC (rev 244121)
+++ branches/safari-607-branch/JSTests/ChangeLog 2019-04-10 17:11:02 UTC (rev 244122)
@@ -1,3 +1,84 @@
+2019-04-09 Alan Coon <[email protected]>
+
+ Cherry-pick r243639. rdar://problem/49725710
+
+ 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):
+
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 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-27 Alan Coon <[email protected]>
Cherry-pick r243280. rdar://problem/49308036
Added: branches/safari-607-branch/JSTests/stress/map-b3-licm-infinite-loop.js (0 => 244122)
--- branches/safari-607-branch/JSTests/stress/map-b3-licm-infinite-loop.js (rev 0)
+++ branches/safari-607-branch/JSTests/stress/map-b3-licm-infinite-loop.js 2019-04-10 17:11:02 UTC (rev 244122)
@@ -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: branches/safari-607-branch/Source/_javascript_Core/ChangeLog (244121 => 244122)
--- branches/safari-607-branch/Source/_javascript_Core/ChangeLog 2019-04-10 17:10:59 UTC (rev 244121)
+++ branches/safari-607-branch/Source/_javascript_Core/ChangeLog 2019-04-10 17:11:02 UTC (rev 244122)
@@ -1,3 +1,86 @@
+2019-04-09 Alan Coon <[email protected]>
+
+ Cherry-pick r243639. rdar://problem/49725710
+
+ 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):
+
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 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-27 Alan Coon <[email protected]>
Cherry-pick r243280. rdar://problem/49308036
Modified: branches/safari-607-branch/Source/_javascript_Core/b3/testb3.cpp (244121 => 244122)
--- branches/safari-607-branch/Source/_javascript_Core/b3/testb3.cpp 2019-04-10 17:10:59 UTC (rev 244121)
+++ branches/safari-607-branch/Source/_javascript_Core/b3/testb3.cpp 2019-04-10 17:11:02 UTC (rev 244122)
@@ -16327,6 +16327,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()
{
@@ -17898,6 +17943,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: branches/safari-607-branch/Source/WTF/ChangeLog (244121 => 244122)
--- branches/safari-607-branch/Source/WTF/ChangeLog 2019-04-10 17:10:59 UTC (rev 244121)
+++ branches/safari-607-branch/Source/WTF/ChangeLog 2019-04-10 17:11:02 UTC (rev 244122)
@@ -1,3 +1,129 @@
+2019-04-09 Alan Coon <[email protected]>
+
+ Cherry-pick r243639. rdar://problem/49725710
+
+ 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):
+
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 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-02-28 Andy Estes <[email protected]>
[watchOS] Disable Parental Controls content filtering
Modified: branches/safari-607-branch/Source/WTF/WTF.xcodeproj/project.pbxproj (244121 => 244122)
--- branches/safari-607-branch/Source/WTF/WTF.xcodeproj/project.pbxproj 2019-04-10 17:10:59 UTC (rev 244121)
+++ branches/safari-607-branch/Source/WTF/WTF.xcodeproj/project.pbxproj 2019-04-10 17:11:02 UTC (rev 244122)
@@ -388,6 +388,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>"; };
@@ -1077,6 +1078,7 @@
A8A4730C151A825B004123FF /* SizeLimits.cpp */,
7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
+ 79038E05224B05A7004C0738 /* SpanningTree.h */,
A8A4730D151A825B004123FF /* Spectrum.h */,
A8A4730E151A825B004123FF /* StackBounds.cpp */,
A8A4730F151A825B004123FF /* StackBounds.h */,
Modified: branches/safari-607-branch/Source/WTF/wtf/BackwardsGraph.h (244121 => 244122)
--- branches/safari-607-branch/Source/WTF/wtf/BackwardsGraph.h 2019-04-10 17:10:59 UTC (rev 244121)
+++ branches/safari-607-branch/Source/WTF/wtf/BackwardsGraph.h 2019-04-10 17:11:02 UTC (rev 244122)
@@ -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: branches/safari-607-branch/Source/WTF/wtf/SpanningTree.h (0 => 244122)
--- branches/safari-607-branch/Source/WTF/wtf/SpanningTree.h (rev 0)
+++ branches/safari-607-branch/Source/WTF/wtf/SpanningTree.h 2019-04-10 17:11:02 UTC (rev 244122)
@@ -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;
+};
