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

Changeset 244016 in webkit


Ignore:
Timestamp:
Apr 8, 2019, 5:39:54 AM (7 years ago)
Author:
Carlos Garcia Campos
Message:

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):

Location:
releases/WebKitGTK/webkit-2.24
Files:
2 added
7 edited

Legend:

Unmodified
Added
Removed

  • releases/WebKitGTK/webkit-2.24/JSTests/ChangeLog

    r244010 r244016  
     12019-03-28  Saam Barati  <sbarati@apple.com>
     2
     3        BackwardsGraph needs to consider back edges as the backward's root successor
     4        https://bugs.webkit.org/show_bug.cgi?id=195991
     5
     6        Reviewed by Filip Pizlo.
     7
     8        * stress/map-b3-licm-infinite-loop.js: Added.
     9
    1102019-03-21  Mark Lam  <mark.lam@apple.com>
    211

  • releases/WebKitGTK/webkit-2.24/Source/JavaScriptCore/ChangeLog

    r244010 r244016  
     12019-03-28  Saam Barati  <sbarati@apple.com>
     2
     3        BackwardsGraph needs to consider back edges as the backward's root successor
     4        https://bugs.webkit.org/show_bug.cgi?id=195991
     5
     6        Reviewed by Filip Pizlo.
     7
     8        * b3/testb3.cpp:
     9        (JSC::B3::testInfiniteLoopDoesntCauseBadHoisting):
     10        (JSC::B3::run):
     11
    1122019-03-21  Mark Lam  <mark.lam@apple.com>
    213

  • releases/WebKitGTK/webkit-2.24/Source/JavaScriptCore/b3/testb3.cpp

    r242866 r244016  
    1660816608
    1660916609    compileAndRun<void>(proc);
     16610}
     16611
     16612void testInfiniteLoopDoesntCauseBadHoisting()
     16613{
     16614    Procedure proc;
     16615    if (proc.optLevel() < 2)
     16616        return;
     16617    BasicBlock* root = proc.addBlock();
     16618    BasicBlock* header = proc.addBlock();
     16619    BasicBlock* loadBlock = proc.addBlock();
     16620    BasicBlock* postLoadBlock = proc.addBlock();
     16621
     16622    Value* arg = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     16623    root->appendNewControlValue(proc, Jump, Origin(), header);
     16624
     16625    header->appendNewControlValue(
     16626        proc, Branch, Origin(),
     16627        header->appendNew<Value>(proc, Equal, Origin(),
     16628            arg,
     16629            header->appendNew<Const64Value>(proc, Origin(), 10)), header, loadBlock);
     16630
     16631    PatchpointValue* patchpoint = loadBlock->appendNew<PatchpointValue>(proc, Void, Origin());
     16632    patchpoint->effects = Effects::none();
     16633    patchpoint->effects.writesLocalState = true; // Don't DCE this.
     16634    patchpoint->setGenerator(
     16635        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
     16636            // This works because we don't have callee saves.
     16637            jit.emitFunctionEpilogue();
     16638            jit.ret();
     16639        });
     16640
     16641    Value* badLoad = loadBlock->appendNew<MemoryValue>(proc, Load, Int64, Origin(), arg, 0);
     16642
     16643    loadBlock->appendNewControlValue(
     16644        proc, Branch, Origin(),
     16645        loadBlock->appendNew<Value>(proc, Equal, Origin(),
     16646            badLoad,
     16647            loadBlock->appendNew<Const64Value>(proc, Origin(), 45)), header, postLoadBlock);
     16648
     16649    postLoadBlock->appendNewControlValue(proc, Return, Origin(), badLoad);
     16650
     16651    // The patchpoint early ret() works because we don't have callee saves.
     16652    auto code = compileProc(proc);
     16653    RELEASE_ASSERT(!proc.calleeSaveRegisterAtOffsetList().size());
     16654    invoke<void>(*code, static_cast<uint64_t>(55)); // Shouldn't crash dereferncing 55.
    1661016655}
    1661116656
    … …  
    1821218257    RUN(testLoopWithMultipleHeaderEdges());
    1821318258
     18259    RUN(testInfiniteLoopDoesntCauseBadHoisting());
     18260
    1821418261    if (isX86()) {
    1821518262        RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));

  • releases/WebKitGTK/webkit-2.24/Source/WTF/ChangeLog

    r242545 r244016  
     12019-03-28  Saam Barati  <sbarati@apple.com>
     2
     3        BackwardsGraph needs to consider back edges as the backward's root successor
     4        https://bugs.webkit.org/show_bug.cgi?id=195991
     5
     6        Reviewed by Filip Pizlo.
     7
     8        Previously, our backwards graph analysis was slightly wrong. The idea of
     9        backwards graph is that the root of the graph has edges to terminals in
     10        the original graph. And then the original directed edges in the graph are flipped.
     11       
     12        However, we weren't considering loops as a form of terminality. For example,
     13        we wouldn't consider an infinite loop as a terminal. So there were no edges
     14        from the root to a node in the infinite loop. This lead us to make mistakes
     15        when we used backwards dominators to compute control flow equivalence.
     16       
     17        This is better understood in an example:
     18       
     19        ```
     20        preheader:
     21        while (1) {
     22            if (!isCell(v))
     23                continue;
     24            load structure ID
     25            if (cond)
     26               continue;
     27            return
     28        }
     29        ```
     30       
     31        In the previous version of this algorithm, the only edge from the backwards
     32        root would be to the block containing the return. This would lead us to
     33        believe that the loading of the structureID backwards dominates the preheader,
     34        leading us to believe it's control flow equivalent to preheader. This is
     35        obviously wrong, since we can loop forever if "v" isn't a cell.
     36       
     37        The solution here is to treat any backedge in the graph as a "terminal" node.
     38        Since a backedge implies the existence of a loop.
     39       
     40        In the above example, the backwards root now has an edge to both blocks with
     41        "continue". This prevents us from falsely claiming that the return is control
     42        flow equivalent with the preheader.
     43       
     44        This patch uses DFS spanning trees to compute back edges. An edge
     45        u->v is a back edge when u is a descendent of v in the DFS spanning
     46        tree of the Graph.
     47
     48        * WTF.xcodeproj/project.pbxproj:
     49        * wtf/BackwardsGraph.h:
     50        (WTF::BackwardsGraph::BackwardsGraph):
     51        * wtf/SpanningTree.h: Added.
     52        (SpanningTree::SpanningTree):
     53        (SpanningTree::isDescendent):
     54
    1552019-03-04  Michael Catanzaro  <mcatanzaro@igalia.com>
    256

  • releases/WebKitGTK/webkit-2.24/Source/WTF/WTF.xcodeproj/project.pbxproj

    r242540 r244016  
    397397                70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
    398398                70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
     399                79038E05224B05A7004C0738 /* SpanningTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpanningTree.h; sourceTree = "<group>"; };
    399400                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
    400401                793BFADD9CED44B8B9FBCA16 /* StdUnorderedMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdUnorderedMap.h; sourceTree = "<group>"; };
    … …  
    11181119                                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
    11191120                                A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
     1121                                79038E05224B05A7004C0738 /* SpanningTree.h */,
    11201122                                A8A4730D151A825B004123FF /* Spectrum.h */,
    11211123                                A8A4730E151A825B004123FF /* StackBounds.cpp */,

  • releases/WebKitGTK/webkit-2.24/Source/WTF/wtf/BackwardsGraph.h

    r237099 r244016  
    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) {

  • releases/WebKitGTK/webkit-2.24/Source/WTF/wtf/CMakeLists.txt

    r242540 r244016  
    207207    SmallPtrSet.h
    208208    SoftLinking.h
     209    SpanningTree.h
    209210    Spectrum.h
    210211    StackBounds.h
Note: See TracChangeset for help on using the changeset viewer.