Changeset 173279 in webkit


Ignore:
Timestamp:
Sep 4, 2014, 2:08:38 PM (11 years ago)
Author:
fpizlo@apple.com
Message:

Beef up the DFG's CFG analyses to include iterated dominance frontiers and more user-friendly BlockSets
​https://bugs.webkit.org/show_bug.cgi?id=136520

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

Add code to compute iterated dominance frontiers. This involves using BlockSet a lot, so
this patch also makes BlockSet a lot more user-friendly.

  • CMakeLists.txt:
  • JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • dfg/DFGBasicBlock.h:
  • dfg/DFGBlockSet.cpp: Added.

(JSC::DFG::BlockSet::dump):

  • dfg/DFGBlockSet.h:

(JSC::DFG::BlockSet::iterator::iterator):
(JSC::DFG::BlockSet::iterator::operator++):
(JSC::DFG::BlockSet::iterator::operator==):
(JSC::DFG::BlockSet::iterator::operator!=):
(JSC::DFG::BlockSet::Iterable::Iterable):
(JSC::DFG::BlockSet::Iterable::begin):
(JSC::DFG::BlockSet::Iterable::end):
(JSC::DFG::BlockSet::iterable):
(JSC::DFG::BlockAdder::BlockAdder):
(JSC::DFG::BlockAdder::operator()):

  • dfg/DFGBlockSetInlines.h: Added.

(JSC::DFG::BlockSet::iterator::operator*):

  • dfg/DFGDominators.cpp:

(JSC::DFG::Dominators::strictDominatorsOf):
(JSC::DFG::Dominators::dominatorsOf):
(JSC::DFG::Dominators::blocksStrictlyDominatedBy):
(JSC::DFG::Dominators::blocksDominatedBy):
(JSC::DFG::Dominators::dominanceFrontierOf):
(JSC::DFG::Dominators::iteratedDominanceFrontierOf):

  • dfg/DFGDominators.h:

(JSC::DFG::Dominators::forAllStrictDominatorsOf):
(JSC::DFG::Dominators::forAllDominatorsOf):
(JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy):
(JSC::DFG::Dominators::forAllBlocksDominatedBy):
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf):
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl):
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):

  • dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dumpBlockHeader):

  • dfg/DFGInvalidationPointInjectionPhase.cpp:

(JSC::DFG::InvalidationPointInjectionPhase::run):

Source/WTF:

Give BitVector a way to quickly find the next set (or unset) bit. Make BitVector equality
faster. Fix a minor closure goof in Spectrum.

  • wtf/BitVector.cpp:

(WTF::BitVector::equalsSlowCase):
(WTF::BitVector::equalsSlowCaseFast):
(WTF::BitVector::equalsSlowCaseSimple):

  • wtf/BitVector.h:

(WTF::BitVector::findBit):
(WTF::BitVector::findBitFast):
(WTF::BitVector::findBitSimple):
(WTF::BitVector::findBitInWord):

  • wtf/Spectrum.h:

(WTF::Spectrum::removeIf):

Location:
trunk/Source
Files:
2 added
14 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r173251 r173279  
    127127    dfg/DFGBinarySwitch.cpp
    128128    dfg/DFGBlockInsertionSet.cpp
     129    dfg/DFGBlockSet.cpp
    129130    dfg/DFGBlockWorklist.cpp
    130131    dfg/DFGByteCodeParser.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r173269 r173279  
     12014-09-03  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Beef up the DFG's CFG analyses to include iterated dominance frontiers and more user-friendly BlockSets
     4        https://bugs.webkit.org/show_bug.cgi?id=136520
     5
     6        Reviewed by Geoffrey Garen.
     7       
     8        Add code to compute iterated dominance frontiers. This involves using BlockSet a lot, so
     9        this patch also makes BlockSet a lot more user-friendly.
     10
     11        * CMakeLists.txt:
     12        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
     13        * JavaScriptCore.xcodeproj/project.pbxproj:
     14        * dfg/DFGBasicBlock.h:
     15        * dfg/DFGBlockSet.cpp: Added.
     16        (JSC::DFG::BlockSet::dump):
     17        * dfg/DFGBlockSet.h:
     18        (JSC::DFG::BlockSet::iterator::iterator):
     19        (JSC::DFG::BlockSet::iterator::operator++):
     20        (JSC::DFG::BlockSet::iterator::operator==):
     21        (JSC::DFG::BlockSet::iterator::operator!=):
     22        (JSC::DFG::BlockSet::Iterable::Iterable):
     23        (JSC::DFG::BlockSet::Iterable::begin):
     24        (JSC::DFG::BlockSet::Iterable::end):
     25        (JSC::DFG::BlockSet::iterable):
     26        (JSC::DFG::BlockAdder::BlockAdder):
     27        (JSC::DFG::BlockAdder::operator()):
     28        * dfg/DFGBlockSetInlines.h: Added.
     29        (JSC::DFG::BlockSet::iterator::operator*):
     30        * dfg/DFGDominators.cpp:
     31        (JSC::DFG::Dominators::strictDominatorsOf):
     32        (JSC::DFG::Dominators::dominatorsOf):
     33        (JSC::DFG::Dominators::blocksStrictlyDominatedBy):
     34        (JSC::DFG::Dominators::blocksDominatedBy):
     35        (JSC::DFG::Dominators::dominanceFrontierOf):
     36        (JSC::DFG::Dominators::iteratedDominanceFrontierOf):
     37        * dfg/DFGDominators.h:
     38        (JSC::DFG::Dominators::forAllStrictDominatorsOf):
     39        (JSC::DFG::Dominators::forAllDominatorsOf):
     40        (JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy):
     41        (JSC::DFG::Dominators::forAllBlocksDominatedBy):
     42        (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf):
     43        (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
     44        (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl):
     45        (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
     46        * dfg/DFGGraph.cpp:
     47        (JSC::DFG::Graph::dumpBlockHeader):
     48        * dfg/DFGInvalidationPointInjectionPhase.cpp:
     49        (JSC::DFG::InvalidationPointInjectionPhase::run):
     50
    1512014-09-04  Mark Lam  <mark.lam@apple.com>
    252

  • trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj

    r173198 r173279  
    373373    <ClCompile Include="..\dfg\DFGBinarySwitch.cpp" />
    374374    <ClCompile Include="..\dfg\DFGBlockInsertionSet.cpp" />
     375    <ClCompile Include="..\dfg\DFGBlockSet.cpp" />
    375376    <ClCompile Include="..\dfg\DFGBlockWorklist.cpp" />
    376377    <ClCompile Include="..\dfg\DFGByteCodeParser.cpp" />
    … …  
    9991000    <ClInclude Include="..\dfg\DFGBlockWorklist.h" />
    10001001    <ClInclude Include="..\dfg\DFGBlockSet.h" />
     1002    <ClInclude Include="..\dfg\DFGBlockSetInlines.h" />
    10011003    <ClInclude Include="..\dfg\DFGBranchDirection.h" />
    10021004    <ClInclude Include="..\dfg\DFGByteCodeParser.h" />

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

    r173251 r173279  
    482482                0FBE0F7616C1DB0F0082C5E8 /* DFGUnificationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FBE0F6F16C1DB010082C5E8 /* DFGUnificationPhase.cpp */; };
    483483                0FBE0F7716C1DB120082C5E8 /* DFGUnificationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FBE0F7016C1DB010082C5E8 /* DFGUnificationPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
     484                0FBF158C19B7A53100695DD0 /* DFGBlockSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FBF158A19B7A53100695DD0 /* DFGBlockSet.cpp */; };
     485                0FBF158D19B7A53100695DD0 /* DFGBlockSetInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FBF158B19B7A53100695DD0 /* DFGBlockSetInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
    484486                0FBFDD04196C92BF007A5BFA /* DFGPhantomRemovalPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FBFDD02196C92BF007A5BFA /* DFGPhantomRemovalPhase.cpp */; };
    485487                0FBFDD05196C92BF007A5BFA /* DFGPhantomRemovalPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FBFDD03196C92BF007A5BFA /* DFGPhantomRemovalPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    24062408                0FBE0F6F16C1DB010082C5E8 /* DFGUnificationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGUnificationPhase.cpp; path = dfg/DFGUnificationPhase.cpp; sourceTree = "<group>"; };
    24072409                0FBE0F7016C1DB010082C5E8 /* DFGUnificationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUnificationPhase.h; path = dfg/DFGUnificationPhase.h; sourceTree = "<group>"; };
     2410                0FBF158A19B7A53100695DD0 /* DFGBlockSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBlockSet.cpp; path = dfg/DFGBlockSet.cpp; sourceTree = "<group>"; };
     2411                0FBF158B19B7A53100695DD0 /* DFGBlockSetInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSetInlines.h; path = dfg/DFGBlockSetInlines.h; sourceTree = "<group>"; };
    24082412                0FBFDD02196C92BF007A5BFA /* DFGPhantomRemovalPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPhantomRemovalPhase.cpp; path = dfg/DFGPhantomRemovalPhase.cpp; sourceTree = "<group>"; };
    24092413                0FBFDD03196C92BF007A5BFA /* DFGPhantomRemovalPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPhantomRemovalPhase.h; path = dfg/DFGPhantomRemovalPhase.h; sourceTree = "<group>"; };
    … …  
    48274831                                0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */,
    48284832                                0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */,
     4833                                0FBF158A19B7A53100695DD0 /* DFGBlockSet.cpp */,
    48294834                                0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */,
     4835                                0FBF158B19B7A53100695DD0 /* DFGBlockSetInlines.h */,
    48304836                                0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */,
    48314837                                0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */,
    … …  
    59205926                                0F66E16C14DF3F1600B7B2E4 /* DFGEdge.h in Headers */,
    59215927                                A7D9A29617A0BC7400EE2618 /* DFGEdgeDominates.h in Headers */,
     5928                                0FBF158D19B7A53100695DD0 /* DFGBlockSetInlines.h in Headers */,
    59225929                                A7986D5717A0BB1E00A95DD0 /* DFGEdgeUsesStructure.h in Headers */,
    59235930                                0FBC0AE81496C7C700D4FBDD /* DFGExitProfile.h in Headers */,
    … …  
    74157422                                0FCEFACA1805E75500472CE4 /* InitializeLLVM.cpp in Sources */,
    74167423                                A513E5B7185B8BD3007E95AD /* InjectedScript.cpp in Sources */,
     7424                                0FBF158C19B7A53100695DD0 /* DFGBlockSet.cpp in Sources */,
    74177425                                A514B2C2185A684400F3C7CB /* InjectedScriptBase.cpp in Sources */,
    74187426                                A58E35911860DECF001F24FE /* InjectedScriptHost.cpp in Sources */,

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

    r173069 r173279  
    187187};
    188188
     189typedef Vector<BasicBlock*, 5> BlockList;
     190
    189191struct UnlinkedBlock {
    190192    BasicBlock* m_block;

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

    r173072 r173279  
    3333namespace JSC { namespace DFG {
    3434
     35class Graph;
     36
    3537class BlockSet {
    3638public:
    … …  
    5052    }
    5153   
     54    class iterator {
     55    public:
     56        iterator()
     57            : m_graph(nullptr)
     58            , m_set(nullptr)
     59            , m_index(0)
     60        {
     61        }
     62       
     63        iterator& operator++()
     64        {
     65            m_index = m_set->m_set.findBit(m_index + 1, true);
     66            return *this;
     67        }
     68       
     69        BasicBlock* operator*() const;
     70       
     71        bool operator==(const iterator& other) const
     72        {
     73            return m_index == other.m_index;
     74        }
     75       
     76        bool operator!=(const iterator& other) const
     77        {
     78            return !(*this == other);
     79        }
     80       
     81    private:
     82        friend class BlockSet;
     83       
     84        Graph* m_graph;
     85        const BlockSet* m_set;
     86        size_t m_index;
     87    };
     88   
     89    class Iterable {
     90    public:
     91        Iterable(Graph& graph, const BlockSet& set)
     92            : m_graph(graph)
     93            , m_set(set)
     94        {
     95        }
     96       
     97        iterator begin() const
     98        {
     99            iterator result;
     100            result.m_graph = &m_graph;
     101            result.m_set = &m_set;
     102            result.m_index = m_set.m_set.findBit(0, true);
     103            return result;
     104        }
     105       
     106        iterator end() const
     107        {
     108            iterator result;
     109            result.m_graph = &m_graph;
     110            result.m_set = &m_set;
     111            result.m_index = m_set.m_set.size();
     112            return result;
     113        }
     114       
     115    private:
     116        Graph& m_graph;
     117        const BlockSet& m_set;
     118    };
     119   
     120    Iterable iterable(Graph& graph) const
     121    {
     122        return Iterable(graph, *this);
     123    }
     124   
     125    void dump(PrintStream&) const;
     126   
    52127private:
    53128    BitVector m_set;
     129};
     130
     131class BlockAdder {
     132public:
     133    BlockAdder(BlockSet& set)
     134        : m_set(set)
     135    {
     136    }
     137   
     138    bool operator()(BasicBlock* block) const
     139    {
     140        return m_set.add(block);
     141    }
     142private:
     143    BlockSet& m_set;
    54144};
    55145

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

    r173072 r173279  
    401401}
    402402
     403BlockSet Dominators::strictDominatorsOf(BasicBlock* to) const
     404{
     405    BlockSet result;
     406    forAllStrictDominatorsOf(to, BlockAdder(result));
     407    return result;
     408}
     409
     410BlockSet Dominators::dominatorsOf(BasicBlock* to) const
     411{
     412    BlockSet result;
     413    forAllDominatorsOf(to, BlockAdder(result));
     414    return result;
     415}
     416
     417BlockSet Dominators::blocksStrictlyDominatedBy(BasicBlock* from) const
     418{
     419    BlockSet result;
     420    forAllBlocksStrictlyDominatedBy(from, BlockAdder(result));
     421    return result;
     422}
     423
     424BlockSet Dominators::blocksDominatedBy(BasicBlock* from) const
     425{
     426    BlockSet result;
     427    forAllBlocksDominatedBy(from, BlockAdder(result));
     428    return result;
     429}
     430
     431BlockSet Dominators::dominanceFrontierOf(BasicBlock* from) const
     432{
     433    BlockSet result;
     434    forAllBlocksInDominanceFrontierOfImpl(from, BlockAdder(result));
     435    return result;
     436}
     437
     438BlockSet Dominators::iteratedDominanceFrontierOf(const BlockList& from) const
     439{
     440    BlockSet result;
     441    forAllBlocksInIteratedDominanceFrontierOfImpl(from, BlockAdder(result));
     442    return result;
     443}
     444
    403445bool Dominators::naiveDominates(BasicBlock* from, BasicBlock* to) const
    404446{

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

    r173072 r173279  
    3232#include "DFGBasicBlock.h"
    3333#include "DFGBlockMap.h"
     34#include "DFGBlockSet.h"
    3435#include "DFGCommon.h"
    35 #include <wtf/FastBitVector.h>
    3636
    3737namespace JSC { namespace DFG {
    … …  
    5858    }
    5959   
     60    template<typename Functor>
     61    void forAllStrictDominatorsOf(BasicBlock* to, const Functor& functor) const
     62    {
     63        for (BasicBlock* block = m_data[to].idomParent; block; block = m_data[block].idomParent)
     64            functor(block);
     65    }
     66   
     67    template<typename Functor>
     68    void forAllDominatorsOf(BasicBlock* to, const Functor& functor) const
     69    {
     70        for (BasicBlock* block = to; block; block = m_data[block].idomParent)
     71            functor(block);
     72    }
     73   
     74    template<typename Functor>
     75    void forAllBlocksStrictlyDominatedBy(BasicBlock* from, const Functor& functor) const
     76    {
     77        Vector<BasicBlock*, 16> worklist;
     78        worklist.appendVector(m_data[from].idomKids);
     79        while (!worklist.isEmpty()) {
     80            BasicBlock* block = worklist.takeLast();
     81            functor(block);
     82            worklist.appendVector(m_data[block].idomKids);
     83        }
     84    }
     85   
     86    template<typename Functor>
     87    void forAllBlocksDominatedBy(BasicBlock* from, const Functor& functor) const
     88    {
     89        Vector<BasicBlock*, 16> worklist;
     90        worklist.append(from);
     91        while (!worklist.isEmpty()) {
     92            BasicBlock* block = worklist.takeLast();
     93            functor(block);
     94            worklist.appendVector(m_data[block].idomKids);
     95        }
     96    }
     97   
     98    BlockSet strictDominatorsOf(BasicBlock* to) const;
     99    BlockSet dominatorsOf(BasicBlock* to) const;
     100    BlockSet blocksStrictlyDominatedBy(BasicBlock* from) const;
     101    BlockSet blocksDominatedBy(BasicBlock* from) const;
     102   
     103    template<typename Functor>
     104    void forAllBlocksInDominanceFrontierOf(
     105        BasicBlock* from, const Functor& functor) const
     106    {
     107        BlockSet set;
     108        forAllBlocksInDominanceFrontierOfImpl(
     109            from,
     110            [&] (BasicBlock* block) {
     111                if (set.add(block))
     112                    functor(block);
     113            });
     114    }
     115   
     116    BlockSet dominanceFrontierOf(BasicBlock* from) const;
     117   
     118    template<typename Functor>
     119    void forAllBlocksInIteratedDominanceFrontierOf(
     120        const BlockList& from, const Functor& functor)
     121    {
     122        BlockSet set;
     123        forAllBlocksInIteratedDominanceFrontierOfImpl(
     124            from,
     125            [&] (BasicBlock* block) -> bool {
     126                if (!set.add(block))
     127                    return false;
     128                functor(block);
     129                return true;
     130            });
     131    }
     132   
     133    BlockSet iteratedDominanceFrontierOf(const BlockList& from) const;
     134   
    60135    void dump(PrintStream&) const;
    61136   
    62137private:
    63138    bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
     139   
     140    template<typename Functor>
     141    void forAllBlocksInDominanceFrontierOfImpl(
     142        BasicBlock* from, const Functor& functor) const
     143    {
     144        // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
     145        //     "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
     146        //     'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
     147        //     dominate 'to'."
     148        //
     149        // A useful corner case to remember: a block may be in its own dominance frontier if it has
     150        // a loop edge to itself, since it dominates itself and so it dominates its own immediate
     151        // predecessor, and a block never strictly dominates itself.
     152       
     153        forAllBlocksDominatedBy(
     154            from,
     155            [&] (BasicBlock* block) {
     156                for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
     157                    BasicBlock* to = block->successor(successorIndex);
     158                    if (!strictlyDominates(from, to))
     159                        functor(to);
     160                }
     161            });
     162    }
     163   
     164    template<typename Functor>
     165    void forAllBlocksInIteratedDominanceFrontierOfImpl(
     166        const BlockList& from, const Functor& functor) const
     167    {
     168        BlockList worklist = from;
     169        while (!worklist.isEmpty()) {
     170            BasicBlock* block = worklist.takeLast();
     171            forAllBlocksInDominanceFrontierOfImpl(
     172                block,
     173                [&] (BasicBlock* otherBlock) {
     174                    if (functor(otherBlock))
     175                        worklist.append(otherBlock);
     176                });
     177        }
     178    }
    64179   
    65180    struct BlockData {

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

    r173072 r173279  
    370370    out.print("\n");
    371371    if (m_dominators.isValid()) {
    372         out.print(prefix, "  Dominated by:");
    373         for (size_t i = 0; i < m_blocks.size(); ++i) {
    374             if (!this->block(i))
    375                 continue;
    376             if (!m_dominators.dominates(this->block(i), block))
    377                 continue;
    378             out.print(" #", i);
    379         }
    380         out.print("\n");
    381         out.print(prefix, "  Dominates:");
    382         for (size_t i = 0; i < m_blocks.size(); ++i) {
    383             if (!this->block(i))
    384                 continue;
    385             if (!m_dominators.dominates(block, this->block(i)))
    386                 continue;
    387             out.print(" #", i);
    388         }
    389         out.print("\n");
     372        out.print(prefix, "  Dominated by: ", m_dominators.dominatorsOf(block), "\n");
     373        out.print(prefix, "  Dominates: ", m_dominators.blocksDominatedBy(block), "\n");
     374        out.print(prefix, "  Dominance Frontier: ", m_dominators.dominanceFrontierOf(block), "\n");
     375        out.print(prefix, "  Iterated Dominance Frontier: ", m_dominators.iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
    390376    }
    391377    if (m_naturalLoops.isValid()) {

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

    r173072 r173279  
    11/*
    2  * Copyright (C) 2013 Apple Inc. All rights reserved.
     2 * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2929#if ENABLE(DFG_JIT)
    3030
    31 #include "DFGBlockSet.h"
     31#include "DFGBlockSetInlines.h"
    3232#include "DFGClobberize.h"
    3333#include "DFGGraph.h"
    … …  
    7070            m_insertionSet.execute(block);
    7171        }
    72        
    73         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
    74             BasicBlock* block = m_graph.block(blockIndex);
    7572
    76             if (!blocksThatNeedInvalidationPoints.contains(block))
    77                 continue;
    78            
     73        for (BasicBlock* block : blocksThatNeedInvalidationPoints.iterable(m_graph)) {
    7974            insertInvalidationCheck(0, block->at(0));
    8075            m_insertionSet.execute(block);

  • trunk/Source/WTF/ChangeLog

    r173271 r173279  
     12014-09-03  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Beef up the DFG's CFG analyses to include iterated dominance frontiers and more user-friendly BlockSets
     4        https://bugs.webkit.org/show_bug.cgi?id=136520
     5
     6        Reviewed by Geoffrey Garen.
     7       
     8        Give BitVector a way to quickly find the next set (or unset) bit. Make BitVector equality
     9        faster. Fix a minor closure goof in Spectrum.
     10
     11        * wtf/BitVector.cpp:
     12        (WTF::BitVector::equalsSlowCase):
     13        (WTF::BitVector::equalsSlowCaseFast):
     14        (WTF::BitVector::equalsSlowCaseSimple):
     15        * wtf/BitVector.h:
     16        (WTF::BitVector::findBit):
     17        (WTF::BitVector::findBitFast):
     18        (WTF::BitVector::findBitSimple):
     19        (WTF::BitVector::findBitInWord):
     20        * wtf/Spectrum.h:
     21        (WTF::Spectrum::removeIf):
     22
    1232014-09-04  Anders Carlsson  <andersca@apple.com>
    224

  • trunk/Source/WTF/wtf/BitVector.cpp

    r159039 r173279  
    184184bool BitVector::equalsSlowCase(const BitVector& other) const
    185185{
     186    bool result = equalsSlowCaseFast(other);
     187    ASSERT(result == equalsSlowCaseSimple(other));
     188    return result;
     189}
     190
     191bool BitVector::equalsSlowCaseFast(const BitVector& other) const
     192{
     193    if (isInline() != other.isInline())
     194        return equalsSlowCaseSimple(other);
     195   
     196    const OutOfLineBits* myBits = outOfLineBits();
     197    const OutOfLineBits* otherBits = other.outOfLineBits();
     198   
     199    size_t myNumWords = myBits->numWords();
     200    size_t otherNumWords = otherBits->numWords();
     201    size_t minNumWords;
     202    size_t maxNumWords;
     203   
     204    const OutOfLineBits* longerBits;
     205    if (myNumWords < otherNumWords) {
     206        minNumWords = myNumWords;
     207        maxNumWords = otherNumWords;
     208        longerBits = otherBits;
     209    } else {
     210        minNumWords = otherNumWords;
     211        maxNumWords = myNumWords;
     212        longerBits = myBits;
     213    }
     214   
     215    for (size_t i = minNumWords; i < maxNumWords; ++i) {
     216        if (longerBits->bits()[i])
     217            return false;
     218    }
     219   
     220    for (size_t i = minNumWords; i--;) {
     221        if (myBits->bits()[i] != otherBits->bits()[i])
     222            return false;
     223    }
     224
     225    return false;
     226}
     227
     228bool BitVector::equalsSlowCaseSimple(const BitVector& other) const
     229{
    186230    // This is really cheesy, but probably good enough for now.
    187231    for (unsigned i = std::max(size(), other.size()); i--;) {

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

    r173072 r173279  
    11/*
    2  * Copyright (C) 2011 Apple Inc. All rights reserved.
     2 * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2929#include <stdio.h>
    3030#include <wtf/Assertions.h>
     31#include <wtf/DataLog.h>
    3132#include <wtf/HashFunctions.h>
    3233#include <wtf/HashTraits.h>
    … …  
    216217    }
    217218   
     219    size_t findBit(size_t index, bool value) const
     220    {
     221        size_t result = findBitFast(index, value);
     222        if (!ASSERT_DISABLED) {
     223            size_t expectedResult = findBitSimple(index, value);
     224            if (result != expectedResult) {
     225                dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n");
     226                ASSERT_NOT_REACHED();
     227            }
     228        }
     229        return result;
     230    }
     231   
    218232    WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
    219233   
    … …  
    288302            return WTF::bitCount(static_cast<unsigned>(bits));
    289303        return WTF::bitCount(static_cast<uint64_t>(bits));
     304    }
     305   
     306    size_t findBitFast(size_t startIndex, bool value) const
     307    {
     308        if (isInline()) {
     309            size_t index = startIndex;
     310            findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value);
     311            return index;
     312        }
     313       
     314        const OutOfLineBits* bits = outOfLineBits();
     315       
     316        // value = true: casts to 1, then xors to 0, then negates to 0.
     317        // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits).
     318        uintptr_t skipValue = -(static_cast<uintptr_t>(value) ^ 1);
     319        size_t numWords = bits->numWords();
     320       
     321        size_t wordIndex = startIndex / bitsInPointer();
     322        size_t startIndexInWord = startIndex - wordIndex * bitsInPointer();
     323       
     324        while (wordIndex < numWords) {
     325            uintptr_t word = bits->bits()[wordIndex];
     326            if (word != skipValue) {
     327                size_t index = startIndexInWord;
     328                if (findBitInWord(word, index, bitsInPointer(), value))
     329                    return wordIndex * bitsInPointer() + index;
     330            }
     331           
     332            wordIndex++;
     333            startIndexInWord = 0;
     334        }
     335       
     336        return bits->numBits();
     337    }
     338   
     339    size_t findBitSimple(size_t index, bool value) const
     340    {
     341        while (index < size()) {
     342            if (get(index) == value)
     343                return index;
     344            index++;
     345        }
     346        return size();
     347    }
     348   
     349    static bool findBitInWord(uintptr_t word, size_t& index, size_t endIndex, bool value)
     350    {
     351        word >>= index;
     352       
     353        while (index < endIndex) {
     354            if ((word & 1) == static_cast<uintptr_t>(value))
     355                return true;
     356            index++;
     357            word >>= 1;
     358        }
     359
     360        index = endIndex;
     361        return false;
    290362    }
    291363   
    … …  
    325397   
    326398    WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const;
     399    bool equalsSlowCaseFast(const BitVector& other) const;
     400    bool equalsSlowCaseSimple(const BitVector& other) const;
    327401    WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const;
    328402   

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

    r173069 r173279  
    111111    void removeIf(const Functor& functor)
    112112    {
    113         m_map.removeIf([functor] (typename HashMap<T, CounterType>::KeyValuePairType& pair) {
     113        m_map.removeIf([&functor] (typename HashMap<T, CounterType>::KeyValuePairType& pair) {
    114114                return functor(KeyAndCount(pair.key, pair.value));
    115115            });
Note: See TracChangeset for help on using the changeset viewer.