Ignore:
Timestamp:
Jul 29, 2016, 1:58:35 PM (9 years ago)
Author:
[email protected]
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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.