Attachment 342494 Details for Bug 184829 – patch

[patch] patch

c-backup.diff (text/plain), 10.20 KB, created by Saam Barati on 2018-06-11 17:53:32 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Saam Barati

Created: 2018-06-11 17:53:32 PDT

Size: 10.20 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 232735)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,24 @@
>+2018-06-11  Saam Barati  <sbarati@apple.com>
>+
>+        The NaturalLoops algorithm only works when the list of blocks in a loop is de-duplicated
>+        https://bugs.webkit.org/show_bug.cgi?id=184829
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        This patch codifies that a BasicBlock's list of predecessors is de-duplicated.
>+        In B3/Air, this just meant writing a validation rule. In DFG, this meant
>+        ensuring this property when building up the predecessors list, and also adding
>+        a validation rule. The NaturalLoops algorithm relies on this property.
>+
>+        * b3/B3Validate.cpp:
>+        * b3/air/AirValidate.cpp:
>+        * b3/testb3.cpp:
>+        (JSC::B3::testLoopWithMultipleHeaderEdges):
>+        (JSC::B3::run):
>+        * dfg/DFGGraph.cpp:
>+        (JSC::DFG::Graph::handleSuccessor):
>+        * dfg/DFGValidate.cpp:
>+
> 2018-06-11  Mark Lam  <mark.lam@apple.com>
> 
>         Add support for webkit-test-runner jscOptions in DumpRenderTree and WebKitTestRunner.
>Index: Source/JavaScriptCore/b3/B3Validate.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3Validate.cpp	(revision 232668)
>+++ Source/JavaScriptCore/b3/B3Validate.cpp	(working copy)
>@@ -536,6 +536,14 @@ public:
> 
>         for (Variable* variable : m_procedure.variables())
>             VALIDATE(variable->type() != Void, ("At ", *variable));
>+
>+        for (BasicBlock* block : m_procedure) {
>+            // We expect the predecessor list to be de-duplicated.
>+            HashSet<BasicBlock*> predecessors;
>+            for (BasicBlock* predecessor : block->predecessors())
>+                predecessors.add(predecessor);
>+            VALIDATE(block->numPredecessors() == predecessors.size(), ("At ", *block));
>+        }
>     }
> 
> private:
>Index: Source/JavaScriptCore/b3/testb3.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/testb3.cpp	(revision 232668)
>+++ Source/JavaScriptCore/b3/testb3.cpp	(working copy)
>@@ -10830,6 +10830,49 @@ void testChillModImms32(int32_t numerato
>     CHECK(compileAndRun<int32_t>(proc, numerator, denominator) == chillMod(numerator, denominator));
> }
> 
>+void testLoopWithMultipleHeaderEdges()
>+{
>+    Procedure proc;
>+    BasicBlock* root = proc.addBlock();
>+    BasicBlock* innerHeader = proc.addBlock();
>+    BasicBlock* innerEnd = proc.addBlock();
>+    BasicBlock* outerHeader = proc.addBlock();
>+    BasicBlock* outerEnd = proc.addBlock();
>+    BasicBlock* end = proc.addBlock();
>+
>+    auto* ne42 = outerHeader->appendNew<Value>(
>+        proc, NotEqual, Origin(),
>+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
>+        root->appendNew<ConstPtrValue>(proc, Origin(), 42));
>+    outerHeader->appendNewControlValue(
>+        proc, Branch, Origin(),
>+        ne42,
>+        FrequentedBlock(innerHeader), FrequentedBlock(outerEnd));
>+    outerEnd->appendNewControlValue(
>+        proc, Branch, Origin(),
>+        root->appendNew<Value>(
>+            proc, Trunc, Origin(),
>+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)),
>+        FrequentedBlock(outerHeader), FrequentedBlock(end));
>+
>+    SwitchValue* switchValue = innerHeader->appendNew<SwitchValue>(
>+        proc, Origin(), root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1));
>+    switchValue->setFallThrough(FrequentedBlock(innerEnd));
>+    for (unsigned i = 0; i < 20; ++i) {
>+        switchValue->appendCase(SwitchCase(i, FrequentedBlock(innerHeader)));
>+    }
>+
>+    root->appendNewControlValue(proc, Jump, Origin(), FrequentedBlock(outerHeader));
>+
>+    innerEnd->appendNewControlValue(proc, Jump, Origin(), FrequentedBlock(outerEnd));
>+    end->appendNewControlValue(
>+        proc, Return, Origin(),
>+        end->appendNew<Const32Value>(proc, Origin(), 5678));
>+
>+    auto code = compileProc(proc); // This shouldn't crash in computing NaturalLoops.
>+    CHECK(invoke<int32_t>(*code, 0, 12345) == 5678);
>+}
>+
> void testSwitch(unsigned degree, unsigned gap = 1)
> {
>     Procedure proc;
>@@ -17803,6 +17846,8 @@ void run(const char* filter)
>     RUN(testShuffleDoesntTrashCalleeSaves());
>     RUN(testDemotePatchpointTerminal());
> 
>+    RUN(testLoopWithMultipleHeaderEdges());
>+
>     if (isX86()) {
>         RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));
>         RUN(testBranchBitAndImmFusion(Identity, Int64, 0xff, Air::BranchTest32, Air::Arg::Tmp));
>Index: Source/JavaScriptCore/b3/air/AirValidate.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/air/AirValidate.cpp	(revision 232668)
>+++ Source/JavaScriptCore/b3/air/AirValidate.cpp	(working copy)
>@@ -112,6 +112,14 @@ public:
>             for (BasicBlock* successor : block->successorBlocks())
>                 VALIDATE(validBlocks.contains(successor), ("In ", *block));
>         }
>+
>+        for (BasicBlock* block : m_code) {
>+            // We expect the predecessor list to be de-duplicated.
>+            HashSet<BasicBlock*> predecessors;
>+            for (BasicBlock* predecessor : block->predecessors())
>+                predecessors.add(predecessor);
>+            VALIDATE(block->numPredecessors() == predecessors.size(), ("At ", *block));
>+        }
>     }
> 
> private:
>Index: Source/JavaScriptCore/dfg/DFGGraph.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGGraph.cpp	(revision 232668)
>+++ Source/JavaScriptCore/dfg/DFGGraph.cpp	(working copy)
>@@ -656,7 +656,8 @@ void Graph::handleSuccessor(Vector<Basic
>         worklist.append(successor);
>     }
>     
>-    successor->predecessors.append(block);
>+    if (!successor->predecessors.contains(block))
>+        successor->predecessors.append(block);
> }
> 
> void Graph::determineReachability()
>Index: Source/JavaScriptCore/dfg/DFGValidate.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGValidate.cpp	(revision 232668)
>+++ Source/JavaScriptCore/dfg/DFGValidate.cpp	(working copy)
>@@ -415,6 +415,14 @@ public:
>                 });
>             }
>         }
>+
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            // We expect the predecessor list to be de-duplicated.
>+            HashSet<BasicBlock*> predecessors;
>+            for (BasicBlock* predecessor : block->predecessors)
>+                predecessors.add(predecessor);
>+            VALIDATE((block), predecessors.size() == block->predecessors.size());
>+        }
>     }
>     
> private:
>Index: Source/WTF/ChangeLog
>===================================================================
>--- Source/WTF/ChangeLog	(revision 232668)
>+++ Source/WTF/ChangeLog	(working copy)
>@@ -1,3 +1,22 @@
>+2018-06-11  Saam Barati  <sbarati@apple.com>
>+
>+        The NaturalLoops algorithm only works when the list of blocks in a loop is de-duplicated
>+        https://bugs.webkit.org/show_bug.cgi?id=184829
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        This patch switches NaturalLoops to walking over a block's predecessors
>+        instead of successors when building the initial list of loops and their
>+        headers. The algorithm broke down when we had a footer block with multiple
>+        control flow edges pointing to the same header. This made the loop data
>+        structure contain multiple entries for the same basic block. The algorithm
>+        breaks down when we end up in this state, since it means our way of detecting
>+        what loop is more inner is broken, since that check uses a loop's size.
>+
>+        * wtf/NaturalLoops.h:
>+        (WTF::NaturalLoop::addBlock):
>+        (WTF::NaturalLoops::NaturalLoops):
>+
> 2018-06-09  Dan Bernstein  <mitz@apple.com>
> 
>         [Xcode] Clean up and modernize some build setting definitions
>Index: Source/WTF/wtf/NaturalLoops.h
>===================================================================
>--- Source/WTF/wtf/NaturalLoops.h	(revision 232668)
>+++ Source/WTF/wtf/NaturalLoops.h	(working copy)
>@@ -94,7 +94,11 @@ private:
>     template<typename>
>     friend class NaturalLoops;
>     
>-    void addBlock(typename Graph::Node block) { m_body.append(block); }
>+    void addBlock(typename Graph::Node block)
>+    {
>+        ASSERT(!m_body.contains(block)); // The NaturalLoops algorithm relies on blocks being unique in this vector.
>+        m_body.append(block);
>+    }
> 
>     Graph* m_graph;
>     typename Graph::Node m_header;
>@@ -130,26 +134,28 @@ public:
>         m_loops.shrink(0);
>     
>         for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
>-            typename Graph::Node block = graph.node(blockIndex);
>-            if (!block)
>+            typename Graph::Node header = graph.node(blockIndex);
>+            if (!header)
>                 continue;
>         
>-            for (unsigned i = graph.successors(block).size(); i--;) {
>-                typename Graph::Node successor = graph.successors(block)[i];
>-                if (!dominators.dominates(successor, block))
>+            for (unsigned i = graph.predecessors(header).size(); i--;) {
>+                typename Graph::Node footer = graph.predecessors(header)[i];
>+                if (!dominators.dominates(header, footer))
>                     continue;
>+                // At this point, we've proven 'header' is actually a loop header and
>+                // that 'footer' is a loop footer.
>                 bool found = false;
>                 for (unsigned j = m_loops.size(); j--;) {
>-                    if (m_loops[j].header() == successor) {
>-                        m_loops[j].addBlock(block);
>+                    if (m_loops[j].header() == header) {
>+                        m_loops[j].addBlock(footer);
>                         found = true;
>                         break;
>                     }
>                 }
>                 if (found)
>                     continue;
>-                NaturalLoop<Graph> loop(graph, successor, m_loops.size());
>-                loop.addBlock(block);
>+                NaturalLoop<Graph> loop(graph, header, m_loops.size());
>+                loop.addBlock(footer);
>                 m_loops.append(loop);
>             }
>         }

Actions: View | Formatted Diff | Diff

Attachments on bug 184829: 342340 | 342341 | 342413 | 342494 | 342504