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

Changeset 244122 in webkit


Ignore:
Timestamp:
Apr 10, 2019, 10:11:02 AM (7 years ago)
Author:
Alan Coon
Message:

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

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

Legend:

Unmodified
Added
Removed

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

    r243577 r244122  
     12019-04-09  Alan Coon  <alancoon@apple.com>
     2
     3        Cherry-pick r243639. rdar://problem/49725710
     4
     5    BackwardsGraph needs to consider back edges as the backward's root successor
     6    https://bugs.webkit.org/show_bug.cgi?id=195991
     7   
     8    Reviewed by Filip Pizlo.
     9   
     10    JSTests:
     11   
     12    * stress/map-b3-licm-infinite-loop.js: Added.
     13   
     14    Source/JavaScriptCore:
     15   
     16    * b3/testb3.cpp:
     17    (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     18    (JSC::B3::run):
     19   
     20    Source/WTF:
     21   
     22    Previously, our backwards graph analysis was slightly wrong. The idea of
     23    backwards graph is that the root of the graph has edges to terminals in
     24    the original graph. And then the original directed edges in the graph are flipped.
     25           
     26    However, we weren't considering loops as a form of terminality. For example,
     27    we wouldn't consider an infinite loop as a terminal. So there were no edges
     28    from the root to a node in the infinite loop. This lead us to make mistakes
     29    when we used backwards dominators to compute control flow equivalence.
     30           
     31    This is better understood in an example:
     32           
     33    ```
     34    preheader:
     35    while (1) {
     36        if (!isCell(v))
     37            continue;
     38        load structure ID
     39        if (cond)
     40           continue;
     41        return
     42    }
     43    ```
     44           
     45    In the previous version of this algorithm, the only edge from the backwards
     46    root would be to the block containing the return. This would lead us to
     47    believe that the loading of the structureID backwards dominates the preheader,
     48    leading us to believe it's control flow equivalent to preheader. This is
     49    obviously wrong, since we can loop forever if "v" isn't a cell.
     50           
     51    The solution here is to treat any backedge in the graph as a "terminal" node.
     52    Since a backedge implies the existence of a loop.
     53           
     54    In the above example, the backwards root now has an edge to both blocks with
     55    "continue". This prevents us from falsely claiming that the return is control
     56    flow equivalent with the preheader.
     57           
     58    This patch uses DFS spanning trees to compute back edges. An edge
     59    u->v is a back edge when u is a descendent of v in the DFS spanning
     60    tree of the Graph.
     61   
     62    * WTF.xcodeproj/project.pbxproj:
     63    * wtf/BackwardsGraph.h:
     64    (WTF::BackwardsGraph::BackwardsGraph):
     65    * wtf/SpanningTree.h: Added.
     66    (SpanningTree::SpanningTree):
     67    (SpanningTree::isDescendent):
     68   
     69   
     70   
     71    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     72
     73    2019-03-28  Saam Barati  <sbarati@apple.com>
     74
     75            BackwardsGraph needs to consider back edges as the backward's root successor
     76            https://bugs.webkit.org/show_bug.cgi?id=195991
     77
     78            Reviewed by Filip Pizlo.
     79
     80            * stress/map-b3-licm-infinite-loop.js: Added.
     81
    1822019-03-27  Alan Coon  <alancoon@apple.com>
    283

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

    r243577 r244122  
     12019-04-09  Alan Coon  <alancoon@apple.com>
     2
     3        Cherry-pick r243639. rdar://problem/49725710
     4
     5    BackwardsGraph needs to consider back edges as the backward's root successor
     6    https://bugs.webkit.org/show_bug.cgi?id=195991
     7   
     8    Reviewed by Filip Pizlo.
     9   
     10    JSTests:
     11   
     12    * stress/map-b3-licm-infinite-loop.js: Added.
     13   
     14    Source/JavaScriptCore:
     15   
     16    * b3/testb3.cpp:
     17    (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     18    (JSC::B3::run):
     19   
     20    Source/WTF:
     21   
     22    Previously, our backwards graph analysis was slightly wrong. The idea of
     23    backwards graph is that the root of the graph has edges to terminals in
     24    the original graph. And then the original directed edges in the graph are flipped.
     25           
     26    However, we weren't considering loops as a form of terminality. For example,
     27    we wouldn't consider an infinite loop as a terminal. So there were no edges
     28    from the root to a node in the infinite loop. This lead us to make mistakes
     29    when we used backwards dominators to compute control flow equivalence.
     30           
     31    This is better understood in an example:
     32           
     33    ```
     34    preheader:
     35    while (1) {
     36        if (!isCell(v))
     37            continue;
     38        load structure ID
     39        if (cond)
     40           continue;
     41        return
     42    }
     43    ```
     44           
     45    In the previous version of this algorithm, the only edge from the backwards
     46    root would be to the block containing the return. This would lead us to
     47    believe that the loading of the structureID backwards dominates the preheader,
     48    leading us to believe it's control flow equivalent to preheader. This is
     49    obviously wrong, since we can loop forever if "v" isn't a cell.
     50           
     51    The solution here is to treat any backedge in the graph as a "terminal" node.
     52    Since a backedge implies the existence of a loop.
     53           
     54    In the above example, the backwards root now has an edge to both blocks with
     55    "continue". This prevents us from falsely claiming that the return is control
     56    flow equivalent with the preheader.
     57           
     58    This patch uses DFS spanning trees to compute back edges. An edge
     59    u->v is a back edge when u is a descendent of v in the DFS spanning
     60    tree of the Graph.
     61   
     62    * WTF.xcodeproj/project.pbxproj:
     63    * wtf/BackwardsGraph.h:
     64    (WTF::BackwardsGraph::BackwardsGraph):
     65    * wtf/SpanningTree.h: Added.
     66    (SpanningTree::SpanningTree):
     67    (SpanningTree::isDescendent):
     68   
     69   
     70   
     71    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243639 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     72
     73    2019-03-28  Saam Barati  <sbarati@apple.com>
     74
     75            BackwardsGraph needs to consider back edges as the backward's root successor
     76            https://bugs.webkit.org/show_bug.cgi?id=195991
     77
     78            Reviewed by Filip Pizlo.
     79
     80            * b3/testb3.cpp:
     81            (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     82            (JSC::B3::run):
     83
    1842019-03-27  Alan Coon  <alancoon@apple.com>
    285

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

    r242857 r244122  
    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-branch/Source/WTF/ChangeLog

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

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

    r239278 r244122  
    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-branch/Source/WTF/wtf/BackwardsGraph.h

    r237099 r244122  
    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.