⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 244639 in webkit


Ignore:
Timestamp:
Apr 24, 2019, 11:42:40 PM (7 years ago)
Author:
bshafiei@apple.com
Message:

Cherry-pick r244122. rdar://problem/50132675

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/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

git-svn-id: ​https://svn.webkit.org/repository/webkit/branches/safari-607-branch@244122 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Location:
branches/safari-607.2.6.0-branch
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed

  • branches/safari-607.2.6.0-branch/JSTests/ChangeLog

    r244625 r244639  
     12019-04-24  Babak Shafiei  <bshafiei@apple.com>
     2
     3        Cherry-pick r244122. rdar://problem/50132675
     4
     5    Cherry-pick r243639. rdar://problem/49725710
     6   
     7        BackwardsGraph needs to consider back edges as the backward's root successor
     8        https://bugs.webkit.org/show_bug.cgi?id=195991
     9   
     10        Reviewed by Filip Pizlo.
     11   
     12        JSTests:
     13   
     14        * stress/map-b3-licm-infinite-loop.js: Added.
     15   
     16        Source/JavaScriptCore:
     17   
     18        * b3/testb3.cpp:
     19        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     20        (JSC::B3::run):
     21   
     22        Source/WTF:
     23   
     24        Previously, our backwards graph analysis was slightly wrong. The idea of
     25        backwards graph is that the root of the graph has edges to terminals in
     26        the original graph. And then the original directed edges in the graph are flipped.
     27   
     28        However, we weren't considering loops as a form of terminality. For example,
     29        we wouldn't consider an infinite loop as a terminal. So there were no edges
     30        from the root to a node in the infinite loop. This lead us to make mistakes
     31        when we used backwards dominators to compute control flow equivalence.
     32   
     33        This is better understood in an example:
     34   
     35        ```
     36        preheader:
     37        while (1) {
     38            if (!isCell(v))
     39                continue;
     40            load structure ID
     41            if (cond)
     42               continue;
     43            return
     44        }
     45        ```
     46   
     47        In the previous version of this algorithm, the only edge from the backwards
     48        root would be to the block containing the return. This would lead us to
     49        believe that the loading of the structureID backwards dominates the preheader,
     50        leading us to believe it's control flow equivalent to preheader. This is
     51        obviously wrong, since we can loop forever if "v" isn't a cell.
     52   
     53        The solution here is to treat any backedge in the graph as a "terminal" node.
     54        Since a backedge implies the existence of a loop.
     55   
     56        In the above example, the backwards root now has an edge to both blocks with
     57        "continue". This prevents us from falsely claiming that the return is control
     58        flow equivalent with the preheader.
     59   
     60        This patch uses DFS spanning trees to compute back edges. An edge
     61        u->v is a back edge when u is a descendent of v in the DFS spanning
     62        tree of the Graph.
     63   
     64        * WTF.xcodeproj/project.pbxproj:
     65        * wtf/BackwardsGraph.h:
     66        (WTF::BackwardsGraph::BackwardsGraph):
     67        * wtf/SpanningTree.h: Added.
     68        (SpanningTree::SpanningTree):
     69        (SpanningTree::isDescendent):
     70   
     71        git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     72   
     73    git-svn-id: https://svn.webkit.org/repository/webkit/branches/safari-607-branch@244122 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     74
     75    2019-04-09  Alan Coon  <alancoon@apple.com>
     76
     77            Cherry-pick r243639. rdar://problem/49725710
     78
     79        BackwardsGraph needs to consider back edges as the backward's root successor
     80        https://bugs.webkit.org/show_bug.cgi?id=195991
     81
     82        Reviewed by Filip Pizlo.
     83
     84        JSTests:
     85
     86        * stress/map-b3-licm-infinite-loop.js: Added.
     87
     88        Source/JavaScriptCore:
     89
     90        * b3/testb3.cpp:
     91        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     92        (JSC::B3::run):
     93
     94        Source/WTF:
     95
     96        Previously, our backwards graph analysis was slightly wrong. The idea of
     97        backwards graph is that the root of the graph has edges to terminals in
     98        the original graph. And then the original directed edges in the graph are flipped.
     99
     100        However, we weren't considering loops as a form of terminality. For example,
     101        we wouldn't consider an infinite loop as a terminal. So there were no edges
     102        from the root to a node in the infinite loop. This lead us to make mistakes
     103        when we used backwards dominators to compute control flow equivalence.
     104
     105        This is better understood in an example:
     106
     107        ```
     108        preheader:
     109        while (1) {
     110            if (!isCell(v))
     111                continue;
     112            load structure ID
     113            if (cond)
     114               continue;
     115            return
     116        }
     117        ```
     118
     119        In the previous version of this algorithm, the only edge from the backwards
     120        root would be to the block containing the return. This would lead us to
     121        believe that the loading of the structureID backwards dominates the preheader,
     122        leading us to believe it's control flow equivalent to preheader. This is
     123        obviously wrong, since we can loop forever if "v" isn't a cell.
     124
     125        The solution here is to treat any backedge in the graph as a "terminal" node.
     126        Since a backedge implies the existence of a loop.
     127
     128        In the above example, the backwards root now has an edge to both blocks with
     129        "continue". This prevents us from falsely claiming that the return is control
     130        flow equivalent with the preheader.
     131
     132        This patch uses DFS spanning trees to compute back edges. An edge
     133        u->v is a back edge when u is a descendent of v in the DFS spanning
     134        tree of the Graph.
     135
     136        * WTF.xcodeproj/project.pbxproj:
     137        * wtf/BackwardsGraph.h:
     138        (WTF::BackwardsGraph::BackwardsGraph):
     139        * wtf/SpanningTree.h: Added.
     140        (SpanningTree::SpanningTree):
     141        (SpanningTree::isDescendent):
     142
     143
     144
     145        git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     146
     147        2019-03-28  Saam Barati  <sbarati@apple.com>
     148
     149                BackwardsGraph needs to consider back edges as the backward's root successor
     150                https://bugs.webkit.org/show_bug.cgi?id=195991
     151
     152                Reviewed by Filip Pizlo.
     153
     154                * stress/map-b3-licm-infinite-loop.js: Added.
     155
    11562019-04-24  Alan Coon  <alancoon@apple.com>
    2157

  • branches/safari-607.2.6.0-branch/Source/JavaScriptCore/ChangeLog

    r244637 r244639  
     12019-04-24  Babak Shafiei  <bshafiei@apple.com>
     2
     3        Cherry-pick r244122. rdar://problem/50132675
     4
     5    Cherry-pick r243639. rdar://problem/49725710
     6   
     7        BackwardsGraph needs to consider back edges as the backward's root successor
     8        https://bugs.webkit.org/show_bug.cgi?id=195991
     9   
     10        Reviewed by Filip Pizlo.
     11   
     12        JSTests:
     13   
     14        * stress/map-b3-licm-infinite-loop.js: Added.
     15   
     16        Source/JavaScriptCore:
     17   
     18        * b3/testb3.cpp:
     19        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     20        (JSC::B3::run):
     21   
     22        Source/WTF:
     23   
     24        Previously, our backwards graph analysis was slightly wrong. The idea of
     25        backwards graph is that the root of the graph has edges to terminals in
     26        the original graph. And then the original directed edges in the graph are flipped.
     27   
     28        However, we weren't considering loops as a form of terminality. For example,
     29        we wouldn't consider an infinite loop as a terminal. So there were no edges
     30        from the root to a node in the infinite loop. This lead us to make mistakes
     31        when we used backwards dominators to compute control flow equivalence.
     32   
     33        This is better understood in an example:
     34   
     35        ```
     36        preheader:
     37        while (1) {
     38            if (!isCell(v))
     39                continue;
     40            load structure ID
     41            if (cond)
     42               continue;
     43            return
     44        }
     45        ```
     46   
     47        In the previous version of this algorithm, the only edge from the backwards
     48        root would be to the block containing the return. This would lead us to
     49        believe that the loading of the structureID backwards dominates the preheader,
     50        leading us to believe it's control flow equivalent to preheader. This is
     51        obviously wrong, since we can loop forever if "v" isn't a cell.
     52   
     53        The solution here is to treat any backedge in the graph as a "terminal" node.
     54        Since a backedge implies the existence of a loop.
     55   
     56        In the above example, the backwards root now has an edge to both blocks with
     57        "continue". This prevents us from falsely claiming that the return is control
     58        flow equivalent with the preheader.
     59   
     60        This patch uses DFS spanning trees to compute back edges. An edge
     61        u->v is a back edge when u is a descendent of v in the DFS spanning
     62        tree of the Graph.
     63   
     64        * WTF.xcodeproj/project.pbxproj:
     65        * wtf/BackwardsGraph.h:
     66        (WTF::BackwardsGraph::BackwardsGraph):
     67        * wtf/SpanningTree.h: Added.
     68        (SpanningTree::SpanningTree):
     69        (SpanningTree::isDescendent):
     70   
     71        git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     72   
     73    git-svn-id: https://svn.webkit.org/repository/webkit/branches/safari-607-branch@244122 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     74
     75    2019-04-09  Alan Coon  <alancoon@apple.com>
     76
     77            Cherry-pick r243639. rdar://problem/49725710
     78
     79        BackwardsGraph needs to consider back edges as the backward's root successor
     80        https://bugs.webkit.org/show_bug.cgi?id=195991
     81
     82        Reviewed by Filip Pizlo.
     83
     84        JSTests:
     85
     86        * stress/map-b3-licm-infinite-loop.js: Added.
     87
     88        Source/JavaScriptCore:
     89
     90        * b3/testb3.cpp:
     91        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     92        (JSC::B3::run):
     93
     94        Source/WTF:
     95
     96        Previously, our backwards graph analysis was slightly wrong. The idea of
     97        backwards graph is that the root of the graph has edges to terminals in
     98        the original graph. And then the original directed edges in the graph are flipped.
     99
     100        However, we weren't considering loops as a form of terminality. For example,
     101        we wouldn't consider an infinite loop as a terminal. So there were no edges
     102        from the root to a node in the infinite loop. This lead us to make mistakes
     103        when we used backwards dominators to compute control flow equivalence.
     104
     105        This is better understood in an example:
     106
     107        ```
     108        preheader:
     109        while (1) {
     110            if (!isCell(v))
     111                continue;
     112            load structure ID
     113            if (cond)
     114               continue;
     115            return
     116        }
     117        ```
     118
     119        In the previous version of this algorithm, the only edge from the backwards
     120        root would be to the block containing the return. This would lead us to
     121        believe that the loading of the structureID backwards dominates the preheader,
     122        leading us to believe it's control flow equivalent to preheader. This is
     123        obviously wrong, since we can loop forever if "v" isn't a cell.
     124
     125        The solution here is to treat any backedge in the graph as a "terminal" node.
     126        Since a backedge implies the existence of a loop.
     127
     128        In the above example, the backwards root now has an edge to both blocks with
     129        "continue". This prevents us from falsely claiming that the return is control
     130        flow equivalent with the preheader.
     131
     132        This patch uses DFS spanning trees to compute back edges. An edge
     133        u->v is a back edge when u is a descendent of v in the DFS spanning
     134        tree of the Graph.
     135
     136        * WTF.xcodeproj/project.pbxproj:
     137        * wtf/BackwardsGraph.h:
     138        (WTF::BackwardsGraph::BackwardsGraph):
     139        * wtf/SpanningTree.h: Added.
     140        (SpanningTree::SpanningTree):
     141        (SpanningTree::isDescendent):
     142
     143
     144
     145        git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     146
     147        2019-03-28  Saam Barati  <sbarati@apple.com>
     148
     149                BackwardsGraph needs to consider back edges as the backward's root successor
     150                https://bugs.webkit.org/show_bug.cgi?id=195991
     151
     152                Reviewed by Filip Pizlo.
     153
     154                * b3/testb3.cpp:
     155                (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     156                (JSC::B3::run):
     157
    11582019-04-24  Babak Shafiei  <bshafiei@apple.com>
    2159

  • branches/safari-607.2.6.0-branch/Source/JavaScriptCore/b3/testb3.cpp

    r244625 r244639  
    1632616326
    1632716327    compileAndRun<void>(proc);
     16328}
     16329
     16330void testInfiniteLoopDoesntCauseBadHoisting()
     16331{
     16332    Procedure proc;
     16333    if (proc.optLevel() < 2)
     16334        return;
     16335    BasicBlock* root = proc.addBlock();
     16336    BasicBlock* header = proc.addBlock();
     16337    BasicBlock* loadBlock = proc.addBlock();
     16338    BasicBlock* postLoadBlock = proc.addBlock();
     16339
     16340    Value* arg = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     16341    root->appendNewControlValue(proc, Jump, Origin(), header);
     16342
     16343    header->appendNewControlValue(
     16344        proc, Branch, Origin(),
     16345        header->appendNew<Value>(proc, Equal, Origin(),
     16346            arg,
     16347            header->appendNew<Const64Value>(proc, Origin(), 10)), header, loadBlock);
     16348
     16349    PatchpointValue* patchpoint = loadBlock->appendNew<PatchpointValue>(proc, Void, Origin());
     16350    patchpoint->effects = Effects::none();
     16351    patchpoint->effects.writesLocalState = true; // Don't DCE this.
     16352    patchpoint->setGenerator(
     16353        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
     16354            // This works because we don't have callee saves.
     16355            jit.emitFunctionEpilogue();
     16356            jit.ret();
     16357        });
     16358
     16359    Value* badLoad = loadBlock->appendNew<MemoryValue>(proc, Load, Int64, Origin(), arg, 0);
     16360
     16361    loadBlock->appendNewControlValue(
     16362        proc, Branch, Origin(),
     16363        loadBlock->appendNew<Value>(proc, Equal, Origin(),
     16364            badLoad,
     16365            loadBlock->appendNew<Const64Value>(proc, Origin(), 45)), header, postLoadBlock);
     16366
     16367    postLoadBlock->appendNewControlValue(proc, Return, Origin(), badLoad);
     16368
     16369    // The patchpoint early ret() works because we don't have callee saves.
     16370    auto code = compileProc(proc);
     16371    RELEASE_ASSERT(!proc.calleeSaveRegisterAtOffsetList().size());
     16372    invoke<void>(*code, static_cast<uint64_t>(55)); // Shouldn't crash dereferncing 55.
    1632816373}
    1632916374
    … …  
    1789917944    RUN(testLoopWithMultipleHeaderEdges());
    1790017945
     17946    RUN(testInfiniteLoopDoesntCauseBadHoisting());
     17947
    1790117948    if (isX86()) {
    1790217949        RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));

  • branches/safari-607.2.6.0-branch/Source/WTF/ChangeLog

    r244625 r244639  
     12019-04-24  Babak Shafiei  <bshafiei@apple.com>
     2
     3        Cherry-pick r244122. rdar://problem/50132675
     4
     5    Cherry-pick r243639. rdar://problem/49725710
     6   
     7        BackwardsGraph needs to consider back edges as the backward's root successor
     8        https://bugs.webkit.org/show_bug.cgi?id=195991
     9   
     10        Reviewed by Filip Pizlo.
     11   
     12        JSTests:
     13   
     14        * stress/map-b3-licm-infinite-loop.js: Added.
     15   
     16        Source/JavaScriptCore:
     17   
     18        * b3/testb3.cpp:
     19        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     20        (JSC::B3::run):
     21   
     22        Source/WTF:
     23   
     24        Previously, our backwards graph analysis was slightly wrong. The idea of
     25        backwards graph is that the root of the graph has edges to terminals in
     26        the original graph. And then the original directed edges in the graph are flipped.
     27   
     28        However, we weren't considering loops as a form of terminality. For example,
     29        we wouldn't consider an infinite loop as a terminal. So there were no edges
     30        from the root to a node in the infinite loop. This lead us to make mistakes
     31        when we used backwards dominators to compute control flow equivalence.
     32   
     33        This is better understood in an example:
     34   
     35        ```
     36        preheader:
     37        while (1) {
     38            if (!isCell(v))
     39                continue;
     40            load structure ID
     41            if (cond)
     42               continue;
     43            return
     44        }
     45        ```
     46   
     47        In the previous version of this algorithm, the only edge from the backwards
     48        root would be to the block containing the return. This would lead us to
     49        believe that the loading of the structureID backwards dominates the preheader,
     50        leading us to believe it's control flow equivalent to preheader. This is
     51        obviously wrong, since we can loop forever if "v" isn't a cell.
     52   
     53        The solution here is to treat any backedge in the graph as a "terminal" node.
     54        Since a backedge implies the existence of a loop.
     55   
     56        In the above example, the backwards root now has an edge to both blocks with
     57        "continue". This prevents us from falsely claiming that the return is control
     58        flow equivalent with the preheader.
     59   
     60        This patch uses DFS spanning trees to compute back edges. An edge
     61        u->v is a back edge when u is a descendent of v in the DFS spanning
     62        tree of the Graph.
     63   
     64        * WTF.xcodeproj/project.pbxproj:
     65        * wtf/BackwardsGraph.h:
     66        (WTF::BackwardsGraph::BackwardsGraph):
     67        * wtf/SpanningTree.h: Added.
     68        (SpanningTree::SpanningTree):
     69        (SpanningTree::isDescendent):
     70   
     71        git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     72   
     73    git-svn-id: https://svn.webkit.org/repository/webkit/branches/safari-607-branch@244122 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     74
     75    2019-04-09  Alan Coon  <alancoon@apple.com>
     76
     77            Cherry-pick r243639. rdar://problem/49725710
     78
     79        BackwardsGraph needs to consider back edges as the backward's root successor
     80        https://bugs.webkit.org/show_bug.cgi?id=195991
     81
     82        Reviewed by Filip Pizlo.
     83
     84        JSTests:
     85
     86        * stress/map-b3-licm-infinite-loop.js: Added.
     87
     88        Source/JavaScriptCore:
     89
     90        * b3/testb3.cpp:
     91        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     92        (JSC::B3::run):
     93
     94        Source/WTF:
     95
     96        Previously, our backwards graph analysis was slightly wrong. The idea of
     97        backwards graph is that the root of the graph has edges to terminals in
     98        the original graph. And then the original directed edges in the graph are flipped.
     99
     100        However, we weren't considering loops as a form of terminality. For example,
     101        we wouldn't consider an infinite loop as a terminal. So there were no edges
     102        from the root to a node in the infinite loop. This lead us to make mistakes
     103        when we used backwards dominators to compute control flow equivalence.
     104
     105        This is better understood in an example:
     106
     107        ```
     108        preheader:
     109        while (1) {
     110            if (!isCell(v))
     111                continue;
     112            load structure ID
     113            if (cond)
     114               continue;
     115            return
     116        }
     117        ```
     118
     119        In the previous version of this algorithm, the only edge from the backwards
     120        root would be to the block containing the return. This would lead us to
     121        believe that the loading of the structureID backwards dominates the preheader,
     122        leading us to believe it's control flow equivalent to preheader. This is
     123        obviously wrong, since we can loop forever if "v" isn't a cell.
     124
     125        The solution here is to treat any backedge in the graph as a "terminal" node.
     126        Since a backedge implies the existence of a loop.
     127
     128        In the above example, the backwards root now has an edge to both blocks with
     129        "continue". This prevents us from falsely claiming that the return is control
     130        flow equivalent with the preheader.
     131
     132        This patch uses DFS spanning trees to compute back edges. An edge
     133        u->v is a back edge when u is a descendent of v in the DFS spanning
     134        tree of the Graph.
     135
     136        * WTF.xcodeproj/project.pbxproj:
     137        * wtf/BackwardsGraph.h:
     138        (WTF::BackwardsGraph::BackwardsGraph):
     139        * wtf/SpanningTree.h: Added.
     140        (SpanningTree::SpanningTree):
     141        (SpanningTree::isDescendent):
     142
     143
     144
     145        git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     146
     147        2019-03-28  Saam Barati  <sbarati@apple.com>
     148
     149                BackwardsGraph needs to consider back edges as the backward's root successor
     150                https://bugs.webkit.org/show_bug.cgi?id=195991
     151
     152                Reviewed by Filip Pizlo.
     153
     154                Previously, our backwards graph analysis was slightly wrong. The idea of
     155                backwards graph is that the root of the graph has edges to terminals in
     156                the original graph. And then the original directed edges in the graph are flipped.
     157
     158                However, we weren't considering loops as a form of terminality. For example,
     159                we wouldn't consider an infinite loop as a terminal. So there were no edges
     160                from the root to a node in the infinite loop. This lead us to make mistakes
     161                when we used backwards dominators to compute control flow equivalence.
     162
     163                This is better understood in an example:
     164
     165                ```
     166                preheader:
     167                while (1) {
     168                    if (!isCell(v))
     169                        continue;
     170                    load structure ID
     171                    if (cond)
     172                       continue;
     173                    return
     174                }
     175                ```
     176
     177                In the previous version of this algorithm, the only edge from the backwards
     178                root would be to the block containing the return. This would lead us to
     179                believe that the loading of the structureID backwards dominates the preheader,
     180                leading us to believe it's control flow equivalent to preheader. This is
     181                obviously wrong, since we can loop forever if "v" isn't a cell.
     182
     183                The solution here is to treat any backedge in the graph as a "terminal" node.
     184                Since a backedge implies the existence of a loop.
     185
     186                In the above example, the backwards root now has an edge to both blocks with
     187                "continue". This prevents us from falsely claiming that the return is control
     188                flow equivalent with the preheader.
     189
     190                This patch uses DFS spanning trees to compute back edges. An edge
     191                u->v is a back edge when u is a descendent of v in the DFS spanning
     192                tree of the Graph.
     193
     194                * WTF.xcodeproj/project.pbxproj:
     195                * wtf/BackwardsGraph.h:
     196                (WTF::BackwardsGraph::BackwardsGraph):
     197                * wtf/SpanningTree.h: Added.
     198                (SpanningTree::SpanningTree):
     199                (SpanningTree::isDescendent):
     200
    12012019-04-24  Alan Coon  <alancoon@apple.com>
    2202

  • branches/safari-607.2.6.0-branch/Source/WTF/WTF.xcodeproj/project.pbxproj

    r244625 r244639  
    389389                70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
    390390                70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
     391                79038E05224B05A7004C0738 /* SpanningTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpanningTree.h; sourceTree = "<group>"; };
    391392                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
    392393                793BFADD9CED44B8B9FBCA16 /* StdUnorderedMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdUnorderedMap.h; sourceTree = "<group>"; };
    … …  
    10781079                                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
    10791080                                A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
     1081                                79038E05224B05A7004C0738 /* SpanningTree.h */,
    10801082                                A8A4730D151A825B004123FF /* Spectrum.h */,
    10811083                                A8A4730E151A825B004123FF /* StackBounds.cpp */,

  • branches/safari-607.2.6.0-branch/Source/WTF/wtf/BackwardsGraph.h

    r244625 r244639  
    11/*
    2  * Copyright (C) 2016 Apple Inc. All rights reserved.
     2 * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3030#include <wtf/Noncopyable.h>
    3131#include <wtf/SingleRootGraph.h>
     32#include <wtf/SpanningTree.h>
    3233#include <wtf/StdLibExtras.h>
    3334
    … …  
    5758            }
    5859        };
     60
     61        {
     62            // Loops are a form of terminality (you can loop forever). To have a loop, you need to
     63            // have a back edge. An edge u->v is a back edge when u is a descendent of v in the
     64            // DFS spanning tree of the Graph.
     65            SpanningTree<Graph> spanningTree(graph);
     66            for (unsigned i = 0; i < graph.numNodes(); ++i) {
     67                if (typename Graph::Node node = graph.node(i)) {
     68                    for (typename Graph::Node successor : graph.successors(node)) {
     69                        if (spanningTree.isDescendent(node, successor)) {
     70                            addRootSuccessor(node);
     71                            break;
     72                        }
     73                    }
     74                }
     75            }
     76        }
    5977
    6078        for (unsigned i = 0; i < graph.numNodes(); ++i) {
Note: See TracChangeset for help on using the changeset viewer.