Changeset 203921 in webkit


Ignore:
Timestamp:
Jul 29, 2016 1:58:35 PM (8 years ago)
Author:
benjamin@webkit.org
Message:

[JSC] Use the same data structures for DFG and Air Liveness Analysis
​https://bugs.webkit.org/show_bug.cgi?id=160346

Reviewed by Geoffrey Garen.

In Air, we minimized memory accesses during liveness analysis
with a couple of tricks:
-Use a single Sparse Set ADT for the live value of each block.
-Manipulate compact positive indices instead of hashing values.

This patch brings the same ideas to DFG.

This patch still uses the same fixpoint algorithms.
The reason is Edge's KillStatus used by other phases. We cannot
use a block-boundary liveness algorithm and update KillStatus
simultaneously. It's something I'll probably revisit at some point.

  • dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::AbstractInterpreter<AbstractStateType>::forAllValues):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::dump):

  • dfg/DFGBasicBlock.h:
  • dfg/DFGGraph.h:

(JSC::DFG::Graph::maxNodeCount):
(JSC::DFG::Graph::nodeAt):

  • dfg/DFGInPlaceAbstractState.cpp:

(JSC::DFG::setLiveValues):
(JSC::DFG::InPlaceAbstractState::endBasicBlock):

  • dfg/DFGLivenessAnalysisPhase.cpp:

(JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
(JSC::DFG::LivenessAnalysisPhase::run):
(JSC::DFG::LivenessAnalysisPhase::processBlock):
(JSC::DFG::LivenessAnalysisPhase::addChildUse):
(JSC::DFG::LivenessAnalysisPhase::process): Deleted.

Location:
trunk/Source/JavaScriptCore
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r203897 r203921  
     12016-07-29  Benjamin Poulain  <benjamin@webkit.org>
     2
     3        [JSC] Use the same data structures for DFG and Air Liveness Analysis
     4        https://bugs.webkit.org/show_bug.cgi?id=160346
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        In Air, we minimized memory accesses during liveness analysis
     9        with a couple of tricks:
     10        -Use a single Sparse Set ADT for the live value of each block.
     11        -Manipulate compact positive indices instead of hashing values.
     12
     13        This patch brings the same ideas to DFG.
     14
     15        This patch still uses the same fixpoint algorithms.
     16        The reason is Edge's KillStatus used by other phases. We cannot
     17        use a block-boundary liveness algorithm and update KillStatus
     18        simultaneously. It's something I'll probably revisit at some point.
     19
     20        * dfg/DFGAbstractInterpreterInlines.h:
     21        (JSC::DFG::AbstractInterpreter<AbstractStateType>::forAllValues):
     22        (JSC::DFG::AbstractInterpreter<AbstractStateType>::dump):
     23        * dfg/DFGBasicBlock.h:
     24        * dfg/DFGGraph.h:
     25        (JSC::DFG::Graph::maxNodeCount):
     26        (JSC::DFG::Graph::nodeAt):
     27        * dfg/DFGInPlaceAbstractState.cpp:
     28        (JSC::DFG::setLiveValues):
     29        (JSC::DFG::InPlaceAbstractState::endBasicBlock):
     30        * dfg/DFGLivenessAnalysisPhase.cpp:
     31        (JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
     32        (JSC::DFG::LivenessAnalysisPhase::run):
     33        (JSC::DFG::LivenessAnalysisPhase::processBlock):
     34        (JSC::DFG::LivenessAnalysisPhase::addChildUse):
     35        (JSC::DFG::LivenessAnalysisPhase::process): Deleted.
     36
    1372016-07-29  Yusuke Suzuki  <utatane.tea@gmail.com>
    238

  • trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h

    r203895 r203921  
    29642964        functor(forNode(m_state.block()->at(i)));
    29652965    if (m_graph.m_form == SSA) {
    2966         HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
    2967         HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtHead.end();
    2968         for (; iter != end; ++iter)
    2969             functor(forNode(*iter));
     2966        for (Node* node : m_state.block()->ssa->liveAtHead)
     2967            functor(forNode(node));
    29702968    }
    29712969    for (size_t i = m_state.variables().numberOfArguments(); i--;)
    … …  
    30253023    HashSet<Node*> seen;
    30263024    if (m_graph.m_form == SSA) {
    3027         HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
    3028         HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtHead.end();
    3029         for (; iter != end; ++iter) {
    3030             Node* node = *iter;
     3025        for (Node* node : m_state.block()->ssa->liveAtHead) {
    30313026            seen.add(node);
    30323027            AbstractValue& value = forNode(node);
    … …  
    30453040    }
    30463041    if (m_graph.m_form == SSA) {
    3047         HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtTail.begin();
    3048         HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtTail.end();
    3049         for (; iter != end; ++iter) {
    3050             Node* node = *iter;
     3042        for (Node* node : m_state.block()->ssa->liveAtTail) {
    30513043            if (seen.contains(node))
    30523044                continue;

  • trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h

    r203802 r203921  
    250250        AvailabilityMap availabilityAtHead;
    251251        AvailabilityMap availabilityAtTail;
    252        
    253         bool liveAtTailIsDirty { false };
    254         HashSet<Node*> liveAtTail;
    255         HashSet<Node*> liveAtHead;
     252
     253        Vector<Node*> liveAtHead;
     254        Vector<Node*> liveAtTail;
    256255        struct NodeAbstractValuePair {
    257256            Node* node;

  • trunk/Source/JavaScriptCore/dfg/DFGGraph.h

    r203808 r203921  
    196196    }
    197197    void deleteNode(Node*);
     198    unsigned maxNodeCount() const { return m_nodes.size(); }
     199    Node* nodeAt(unsigned index) const { return m_nodes[index]; }
    198200
    199201    void dethread();

  • trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp

    r200034 r203921  
    7575}
    7676
    77 static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
     77static void setLiveValues(HashMap<Node*, AbstractValue>& values, const Vector<Node*>& liveNodes)
    7878{
    7979    values.clear();
    80    
    81     HashSet<Node*>::iterator iter = live.begin();
    82     HashSet<Node*>::iterator end = live.end();
    83     for (; iter != end; ++iter)
    84         values.add(*iter, AbstractValue());
    85 }
    86 
    87 static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, HashSet<Node*>& live)
     80    for (Node* node : liveNodes)
     81        values.add(node, AbstractValue());
     82}
     83
     84static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, const Vector<Node*>& live)
    8885{
    8986    values.resize(0);
    … …  
    204201            changed |= block->valuesAtTail[i].merge(m_variables[i]);
    205202
    206         HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
    207         HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
    208         for (; iter != end; ++iter) {
    209             Node* node = *iter;
     203        for (Node* node : block->ssa->liveAtTail) {
    210204            changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
    211205        }

  • trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp

    r198364 r203921  
    11/*
    2  * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
     2 * Copyright (C) 2013, 2015-2016 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3030
    3131#include "DFGBasicBlockInlines.h"
     32#include "DFGBlockMapInlines.h"
    3233#include "DFGGraph.h"
    3334#include "DFGInsertionSet.h"
    3435#include "DFGPhase.h"
    3536#include "JSCInlines.h"
     37#include <wtf/BitVector.h>
     38#include <wtf/IndexSparseSet.h>
    3639
    3740namespace JSC { namespace DFG {
    … …  
    4144    LivenessAnalysisPhase(Graph& graph)
    4245        : Phase(graph, "liveness analysis")
    43     {
    44     }
    45    
     46        , m_dirtyBlocks(m_graph.numBlocks())
     47        , m_liveAtHead(m_graph)
     48        , m_liveAtTail(m_graph)
     49        , m_workset(graph.maxNodeCount() - 1)
     50    {
     51    }
     52
    4653    bool run()
    4754    {
    48         ASSERT(m_graph.m_form == SSA);
    49        
    50         // Liveness is a backwards analysis; the roots are the blocks that
    51         // end in a terminal (Return/Throw/ThrowReferenceError). For now, we
    52         // use a fixpoint formulation since liveness is a rapid analysis with
    53         // convergence guaranteed after O(connectivity).
    54        
    55         // Start by assuming that everything is dead.
    56         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
     55        // Start with all valid block dirty.
     56        BlockIndex numBlock = m_graph.numBlocks();
     57        m_dirtyBlocks.ensureSize(numBlock);
     58        for (BlockIndex blockIndex = 0; blockIndex < numBlock; ++blockIndex) {
     59            if (m_graph.block(blockIndex))
     60                m_dirtyBlocks.quickSet(blockIndex);
     61        }
     62
     63        // Fixpoint until we do not add any new live values at tail.
     64        bool changed;
     65        do {
     66            changed = false;
     67
     68            for (BlockIndex blockIndex = numBlock; blockIndex--;) {
     69                if (!m_dirtyBlocks.quickClear(blockIndex))
     70                    continue;
     71
     72                changed |= processBlock(blockIndex);
     73            }
     74        } while (changed);
     75
     76        // Update the per-block node list for live and tail.
     77        for (BlockIndex blockIndex = numBlock; blockIndex--;) {
    5778            BasicBlock* block = m_graph.block(blockIndex);
    5879            if (!block)
    5980                continue;
    60             block->ssa->liveAtTailIsDirty = true;
    61             block->ssa->liveAtHead.clear();
    62             block->ssa->liveAtTail.clear();
    63         }
    64        
    65         do {
    66             m_changed = false;
    67             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
    68                 process(blockIndex);
    69         } while (m_changed);
    70        
    71         if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) {
    72             DFG_CRASH(
    73                 m_graph, nullptr,
    74                 toCString(
    75                     "Bad liveness analysis result: live at root is not empty: ",
    76                     nodeListDump(m_graph.block(0)->ssa->liveAtHead)).data());
    77         }
    78        
     81
     82            {
     83                const auto& liveAtHeadIndices = m_liveAtHead[blockIndex];
     84                Vector<Node*>& liveAtHead = block->ssa->liveAtHead;
     85                liveAtHead.resize(0);
     86                liveAtHead.reserveCapacity(liveAtHeadIndices.size());
     87                for (unsigned index : liveAtHeadIndices)
     88                    liveAtHead.uncheckedAppend(m_graph.nodeAt(index));
     89            }
     90            {
     91                const auto& liveAtTailIndices = m_liveAtTail[blockIndex];
     92                Vector<Node*>& liveAtTail = block->ssa->liveAtTail;
     93                liveAtTail.resize(0);
     94                liveAtTail.reserveCapacity(liveAtTailIndices.size());
     95                for (unsigned index : m_liveAtTail[blockIndex])
     96                    liveAtTail.uncheckedAppend(m_graph.nodeAt(index));
     97            }
     98        }
     99
    79100        return true;
    80101    }
    81102
    82103private:
    83     void process(BlockIndex blockIndex)
     104    bool processBlock(BlockIndex blockIndex)
    84105    {
    85106        BasicBlock* block = m_graph.block(blockIndex);
    86         if (!block)
    87             return;
    88 
    89         if (!block->ssa->liveAtTailIsDirty)
    90             return;
    91         block->ssa->liveAtTailIsDirty = false;
    92 
    93         m_live = block->ssa->liveAtTail;
     107        ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty.");
     108
     109        m_workset.clear();
     110        for (unsigned index : m_liveAtTail[blockIndex])
     111            m_workset.add(index);
     112
    94113        for (unsigned nodeIndex = block->size(); nodeIndex--;) {
    95114            Node* node = block->at(nodeIndex);
    96            
     115
    97116            // Given an Upsilon:
    98117            //
    … …  
    115134            switch (node->op()) {
    116135            case Upsilon: {
     136                ASSERT_WITH_MESSAGE(!m_workset.contains(node->index()), "Upsilon should not be used as defs by other nodes.");
     137
    117138                Node* phi = node->phi();
    118                 m_live.remove(phi);
    119                 m_live.remove(node);
    120                 m_live.add(node->child1().node());
     139                m_workset.remove(phi->index());
     140                m_workset.add(node->child1()->index());
    121141                break;
    122142            }
    123                
    124143            case Phi: {
    125144                break;
    126145            }
    127                
    128146            default:
    129                 m_live.remove(node);
     147                m_workset.remove(node->index());
    130148                DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse);
    131149                break;
    132150            }
    133151        }
    134        
    135         for (Node* node : m_live) {
    136             if (!block->ssa->liveAtHead.contains(node)) {
    137                 m_changed = true;
    138                 for (unsigned i = block->predecessors.size(); i--;) {
    139                     BasicBlock* predecessor = block->predecessors[i];
    140                     if (predecessor->ssa->liveAtTail.add(node).isNewEntry)
    141                         predecessor->ssa->liveAtTailIsDirty = true;
     152
     153        // Update live at head.
     154        auto& liveAtHead = m_liveAtHead[blockIndex];
     155        if (m_workset.size() == liveAtHead.size())
     156            return false;
     157
     158        for (unsigned liveIndexAtHead : liveAtHead)
     159            m_workset.remove(liveIndexAtHead);
     160        ASSERT(!m_workset.isEmpty());
     161
     162        liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
     163        for (unsigned newValue : m_workset)
     164            liveAtHead.uncheckedAppend(newValue);
     165
     166        bool changedPredecessor = false;
     167        for (BasicBlock* predecessor : block->predecessors) {
     168            auto& liveAtTail = m_liveAtTail[predecessor];
     169            for (unsigned newValue : m_workset) {
     170                if (liveAtTail.add(newValue)) {
     171                    if (!m_dirtyBlocks.quickSet(predecessor->index))
     172                        changedPredecessor = true;
    142173                }
    143174            }
    144175        }
    145         block->ssa->liveAtHead = WTFMove(m_live);
    146     }
    147    
    148     void addChildUse(Node*, Edge& edge)
    149     {
    150         addChildUse(edge);
    151     }
    152    
    153     void addChildUse(Edge& edge)
    154     {
    155         edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill);
    156     }
    157    
    158     bool m_changed;
    159     HashSet<Node*> m_live;
     176        return changedPredecessor;
     177    }
     178
     179    ALWAYS_INLINE void addChildUse(Node*, Edge& edge)
     180    {
     181        bool newEntry = m_workset.add(edge->index());
     182        edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
     183    }
     184
     185    // Blocks with new live values at tail.
     186    BitVector m_dirtyBlocks;
     187
     188    // Live values per block edge.
     189    BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead;
     190    BlockMap<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_liveAtTail;
     191
     192    // Single sparse set allocated once and used by every basic block.
     193    IndexSparseSet<UnsafeVectorOverflow> m_workset;
    160194};
    161195
Note: See TracChangeset for help on using the changeset viewer.