<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[243639] trunk</title>
</head>
<body>

<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }
#msg dl a { font-weight: bold}
#msg dl a:link    { color:#fc3; }
#msg dl a:active  { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/243639">243639</a></dd>
<dt>Author</dt> <dd>sbarati@apple.com</dd>
<dt>Date</dt> <dd>2019-03-28 21:42:42 -0700 (Thu, 28 Mar 2019)</dd>
</dl>

<h3>Log Message</h3>
<pre>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/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):</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkJSTestsChangeLog">trunk/JSTests/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3cpp">trunk/Source/JavaScriptCore/b3/testb3.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfBackwardsGraphh">trunk/Source/WTF/wtf/BackwardsGraph.h</a></li>
</ul>

<h3>Added Paths</h3>
<ul>
<li><a href="#trunkJSTestsstressmapb3licminfiniteloopjs">trunk/JSTests/stress/map-b3-licm-infinite-loop.js</a></li>
<li><a href="#trunkSourceWTFwtfSpanningTreeh">trunk/Source/WTF/wtf/SpanningTree.h</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkJSTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/JSTests/ChangeLog (243638 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/ChangeLog  2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/JSTests/ChangeLog     2019-03-29 04:42:42 UTC (rev 243639)
</span><span class="lines">@@ -1,3 +1,12 @@
</span><ins>+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.
+
</ins><span class="cx"> 2019-03-28  Tadeu Zagallo  <tzagallo@apple.com>
</span><span class="cx"> 
</span><span class="cx">         CodeBlock::jettison() should disallow repatching its own calls
</span></span></pre></div>
<a id="trunkJSTestsstressmapb3licminfiniteloopjs"></a>
<div class="addfile"><h4>Added: trunk/JSTests/stress/map-b3-licm-infinite-loop.js (0 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -0,0 +1,25 @@
</span><ins>+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 {}
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (243638 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog    2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/JavaScriptCore/ChangeLog       2019-03-29 04:42:42 UTC (rev 243639)
</span><span class="lines">@@ -1,3 +1,14 @@
</span><ins>+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):
+
</ins><span class="cx"> 2019-03-28  Fujii Hironori  <Hironori.Fujii@sony.com>
</span><span class="cx"> 
</span><span class="cx">         Opcode.h(159,27): warning: adding 'unsigned int' to a string does not append to the string [-Wstring-plus-int]
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3.cpp (243638 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3.cpp        2019-03-29 02:34:56 UTC (rev 243638)
+++ trunk/Source/JavaScriptCore/b3/testb3.cpp   2019-03-29 04:42:42 UTC (rev 243639)
</span><span class="lines">@@ -16812,6 +16812,51 @@
</span><span class="cx">     compileAndRun<void>(proc);
</span><span class="cx"> }
</span><span class="cx"> 
</span><ins>+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.
+}
+
</ins><span class="cx"> // Make sure the compiler does not try to optimize anything out.
</span><span class="cx"> NEVER_INLINE double zero()
</span><span class="cx"> {
</span><span class="lines">@@ -18429,6 +18474,8 @@
</span><span class="cx"> 
</span><span class="cx">     RUN(testLoopWithMultipleHeaderEdges());
</span><span class="cx"> 
</span><ins>+    RUN(testInfiniteLoopDoesntCauseBadHoisting());
+
</ins><span class="cx">     if (isX86()) {
</span><span class="cx">         RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));
</span><span class="cx">         RUN(testBranchBitAndImmFusion(Identity, Int64, 0xff, Air::BranchTest32, Air::Arg::Tmp));
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (243638 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,3 +1,57 @@
</span><ins>+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):
+
</ins><span class="cx"> 2019-03-28  Tim Horton  <timothy_horton@apple.com>
</span><span class="cx"> 
</span><span class="cx">         Un-fix the build
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (243638 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -398,6 +398,7 @@
</span><span class="cx">          70ECA60A1B02426800449739 /* AtomicStringImpl.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringImpl.cpp; sourceTree = "<group>"; };
</span><span class="cx">          70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
</span><span class="cx">          70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
</span><ins>+               79038E05224B05A7004C0738 /* SpanningTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpanningTree.h; sourceTree = "<group>"; };
</ins><span class="cx">           7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
</span><span class="cx">          793BFADD9CED44B8B9FBCA16 /* StdUnorderedMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdUnorderedMap.h; sourceTree = "<group>"; };
</span><span class="cx">          795212021F42588800BD6421 /* SingleRootGraph.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SingleRootGraph.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -1126,6 +1127,7 @@
</span><span class="cx">                          A8A4730C151A825B004123FF /* SizeLimits.cpp */,
</span><span class="cx">                          7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
</span><span class="cx">                          A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
</span><ins>+                               79038E05224B05A7004C0738 /* SpanningTree.h */,
</ins><span class="cx">                           A8A4730D151A825B004123FF /* Spectrum.h */,
</span><span class="cx">                          A8A4730E151A825B004123FF /* StackBounds.cpp */,
</span><span class="cx">                          A8A4730F151A825B004123FF /* StackBounds.h */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfBackwardsGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/BackwardsGraph.h (243638 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2016 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
</ins><span class="cx">  *
</span><span class="cx">  * Redistribution and use in source and binary forms, with or without
</span><span class="cx">  * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> #include <wtf/GraphNodeWorklist.h>
</span><span class="cx"> #include <wtf/Noncopyable.h>
</span><span class="cx"> #include <wtf/SingleRootGraph.h>
</span><ins>+#include <wtf/SpanningTree.h>
</ins><span class="cx"> #include <wtf/StdLibExtras.h>
</span><span class="cx"> 
</span><span class="cx"> namespace WTF {
</span><span class="lines">@@ -57,6 +58,23 @@
</span><span class="cx">             }
</span><span class="cx">         };
</span><span class="cx"> 
</span><ins>+        {
+            // 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;
+                        }
+                    }
+                }
+            }
+        }
+
</ins><span class="cx">         for (unsigned i = 0; i < graph.numNodes(); ++i) {
</span><span class="cx">             if (typename Graph::Node node = graph.node(i)) {
</span><span class="cx">                 if (!graph.successors(node).size())
</span></span></pre></div>
<a id="trunkSourceWTFwtfSpanningTreeh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/SpanningTree.h (0 => 243639)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/SpanningTree.h                              (rev 0)
+++ trunk/Source/WTF/wtf/SpanningTree.h 2019-03-29 04:42:42 UTC (rev 243639)
</span><span class="lines">@@ -0,0 +1,84 @@
</span><ins>+/*
+ * 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;
+};
</ins></span></pre>
</div>
</div>

</body>
</html>