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

Changeset 243639 in webkit


Ignore:
Timestamp:
Mar 28, 2019, 9:42:42 PM (7 years ago)
Author:
sbarati@apple.com
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:
trunk
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r243626 r243639  
     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-28  Tadeu Zagallo  <tzagallo@apple.com>
    211

  • trunk/Source/JavaScriptCore/ChangeLog

    r243633 r243639  
     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-28  Fujii Hironori  <Hironori.Fujii@sony.com>
    213

  • trunk/Source/JavaScriptCore/b3/testb3.cpp

    r243065 r243639  
    1681116811
    1681216812    compileAndRun<void>(proc);
     16813}
     16814
     16815void testInfiniteLoopDoesntCauseBadHoisting()
     16816{
     16817    Procedure proc;
     16818    if (proc.optLevel() < 2)
     16819        return;
     16820    BasicBlock* root = proc.addBlock();
     16821    BasicBlock* header = proc.addBlock();
     16822    BasicBlock* loadBlock = proc.addBlock();
     16823    BasicBlock* postLoadBlock = proc.addBlock();
     16824
     16825    Value* arg = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     16826    root->appendNewControlValue(proc, Jump, Origin(), header);
     16827
     16828    header->appendNewControlValue(
     16829        proc, Branch, Origin(),
     16830        header->appendNew<Value>(proc, Equal, Origin(),
     16831            arg,
     16832            header->appendNew<Const64Value>(proc, Origin(), 10)), header, loadBlock);
     16833
     16834    PatchpointValue* patchpoint = loadBlock->appendNew<PatchpointValue>(proc, Void, Origin());
     16835    patchpoint->effects = Effects::none();
     16836    patchpoint->effects.writesLocalState = true; // Don't DCE this.
     16837    patchpoint->setGenerator(
     16838        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
     16839            // This works because we don't have callee saves.
     16840            jit.emitFunctionEpilogue();
     16841            jit.ret();
     16842        });
     16843
     16844    Value* badLoad = loadBlock->appendNew<MemoryValue>(proc, Load, Int64, Origin(), arg, 0);
     16845
     16846    loadBlock->appendNewControlValue(
     16847        proc, Branch, Origin(),
     16848        loadBlock->appendNew<Value>(proc, Equal, Origin(),
     16849            badLoad,
     16850            loadBlock->appendNew<Const64Value>(proc, Origin(), 45)), header, postLoadBlock);
     16851
     16852    postLoadBlock->appendNewControlValue(proc, Return, Origin(), badLoad);
     16853
     16854    // The patchpoint early ret() works because we don't have callee saves.
     16855    auto code = compileProc(proc);
     16856    RELEASE_ASSERT(!proc.calleeSaveRegisterAtOffsetList().size());
     16857    invoke<void>(*code, static_cast<uint64_t>(55)); // Shouldn't crash dereferncing 55.
    1681316858}
    1681416859
    … …  
    1843018475    RUN(testLoopWithMultipleHeaderEdges());
    1843118476
     18477    RUN(testInfiniteLoopDoesntCauseBadHoisting());
     18478
    1843218479    if (isX86()) {
    1843318480        RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));

  • trunk/Source/WTF/ChangeLog

    r243619 r243639  
     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-28  Tim Horton  <timothy_horton@apple.com>
    256

  • trunk/Source/WTF/WTF.xcodeproj/project.pbxproj

    r243254 r243639  
    399399                70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
    400400                70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
     401                79038E05224B05A7004C0738 /* SpanningTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpanningTree.h; sourceTree = "<group>"; };
    401402                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
    402403                793BFADD9CED44B8B9FBCA16 /* StdUnorderedMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdUnorderedMap.h; sourceTree = "<group>"; };
    … …  
    11271128                                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
    11281129                                A30D412D1F0DE13F00B71954 /* SoftLinking.h */,
     1130                                79038E05224B05A7004C0738 /* SpanningTree.h */,
    11291131                                A8A4730D151A825B004123FF /* Spectrum.h */,
    11301132                                A8A4730E151A825B004123FF /* StackBounds.cpp */,

  • trunk/Source/WTF/wtf/BackwardsGraph.h

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