Changeset 95389 in webkit


Ignore:
Timestamp:
Sep 17, 2011 8:47:04 PM (13 years ago)
Author:
fpizlo@apple.com
Message:

DFG JIT does not have full block-local CSE
​https://bugs.webkit.org/show_bug.cgi?id=68316

Reviewed by Oliver Hunt.

This adds block-local CSE to the DFG. CSE runs in the propagator just after
type propagation. It is part of the propagator itself because it needs to
use the propagator's internal data structures to determine which operations
may have side effects. Because it changes the live-ranges of nodes, the
virtual register allocator had to be moved into the propagator so that it
runs after CSE. To ensure that the back-end knows to keep the inputs to
any eliminated node alive for OSR, a new node type, Phantom, was introduced.
It is a no-op but prolonges the live-range of its inputs.

This is an 80% speed-up on imaging-gaussian-blur, and a 10% speed-up on
Kraken.

  • JavaScriptCore.xcodeproj/project.pbxproj:
  • dfg/DFGAliasTracker.h: Removed.
  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::parse):

  • dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):

  • dfg/DFGGraph.h:

(JSC::DFG::MethodCheckData::operator==):
(JSC::DFG::MethodCheckData::operator!=):

  • dfg/DFGNode.h:

(JSC::DFG::Node::hasVirtualRegister):
(JSC::DFG::Node::setRefCount):

  • dfg/DFGPropagator.cpp:

(JSC::DFG::Propagator::Propagator):
(JSC::DFG::Propagator::fixpoint):
(JSC::DFG::Propagator::propagateNode):
(JSC::DFG::Propagator::canonicalize):
(JSC::DFG::Propagator::computeStartIndex):
(JSC::DFG::Propagator::startIndex):
(JSC::DFG::Propagator::pureCSE):
(JSC::DFG::Propagator::globalVarLoadElimination):
(JSC::DFG::Propagator::getByValLoadElimination):
(JSC::DFG::Propagator::getMethodLoadElimination):
(JSC::DFG::Propagator::performSubstitution):
(JSC::DFG::Propagator::setReplacement):
(JSC::DFG::Propagator::performNodeCSE):
(JSC::DFG::Propagator::performBlockCSE):
(JSC::DFG::Propagator::localCSE):
(JSC::DFG::Propagator::allocateVirtualRegisters):
(JSC::DFG::propagate):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::compile):

Location:
trunk/Source/JavaScriptCore
Files:
1 deleted
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r95388 r95389  
     12011-09-17  Filip Pizlo  <fpizlo@apple.com>
     2
     3        DFG JIT does not have full block-local CSE
     4        https://bugs.webkit.org/show_bug.cgi?id=68316
     5
     6        Reviewed by Oliver Hunt.
     7       
     8        This adds block-local CSE to the DFG. CSE runs in the propagator just after
     9        type propagation. It is part of the propagator itself because it needs to
     10        use the propagator's internal data structures to determine which operations
     11        may have side effects. Because it changes the live-ranges of nodes, the
     12        virtual register allocator had to be moved into the propagator so that it
     13        runs after CSE. To ensure that the back-end knows to keep the inputs to
     14        any eliminated node alive for OSR, a new node type, Phantom, was introduced.
     15        It is a no-op but prolonges the live-range of its inputs.
     16       
     17        This is an 80% speed-up on imaging-gaussian-blur, and a 10% speed-up on
     18        Kraken.
     19       
     20        * JavaScriptCore.xcodeproj/project.pbxproj:
     21        * dfg/DFGAliasTracker.h: Removed.
     22        * dfg/DFGByteCodeParser.cpp:
     23        (JSC::DFG::ByteCodeParser::parseBlock):
     24        (JSC::DFG::ByteCodeParser::parse):
     25        * dfg/DFGGraph.cpp:
     26        (JSC::DFG::Graph::dump):
     27        * dfg/DFGGraph.h:
     28        (JSC::DFG::MethodCheckData::operator==):
     29        (JSC::DFG::MethodCheckData::operator!=):
     30        * dfg/DFGNode.h:
     31        (JSC::DFG::Node::hasVirtualRegister):
     32        (JSC::DFG::Node::setRefCount):
     33        * dfg/DFGPropagator.cpp:
     34        (JSC::DFG::Propagator::Propagator):
     35        (JSC::DFG::Propagator::fixpoint):
     36        (JSC::DFG::Propagator::propagateNode):
     37        (JSC::DFG::Propagator::canonicalize):
     38        (JSC::DFG::Propagator::computeStartIndex):
     39        (JSC::DFG::Propagator::startIndex):
     40        (JSC::DFG::Propagator::pureCSE):
     41        (JSC::DFG::Propagator::globalVarLoadElimination):
     42        (JSC::DFG::Propagator::getByValLoadElimination):
     43        (JSC::DFG::Propagator::getMethodLoadElimination):
     44        (JSC::DFG::Propagator::performSubstitution):
     45        (JSC::DFG::Propagator::setReplacement):
     46        (JSC::DFG::Propagator::performNodeCSE):
     47        (JSC::DFG::Propagator::performBlockCSE):
     48        (JSC::DFG::Propagator::localCSE):
     49        (JSC::DFG::Propagator::allocateVirtualRegisters):
     50        (JSC::DFG::propagate):
     51        * dfg/DFGSpeculativeJIT.cpp:
     52        (JSC::DFG::SpeculativeJIT::compile):
     53
    1542011-09-16  Filip Pizlo  <fpizlo@apple.com>
    255

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

    r95331 r95389  
    360360                86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */ = {isa = PBXBuildFile; fileRef = 86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */; };
    361361                86ECA3FA132DF25A002B2AD7 /* DFGScoreBoard.h in Headers */ = {isa = PBXBuildFile; fileRef = 86ECA3F9132DF25A002B2AD7 /* DFGScoreBoard.h */; };
    362                 86ECA4F1132EAA6D002B2AD7 /* DFGAliasTracker.h in Headers */ = {isa = PBXBuildFile; fileRef = 86ECA4F0132EAA6D002B2AD7 /* DFGAliasTracker.h */; };
    363362                86F38859121130CA007A7CE3 /* AtomicStringHash.h in Headers */ = {isa = PBXBuildFile; fileRef = 86F38858121130CA007A7CE3 /* AtomicStringHash.h */; settings = {ATTRIBUTES = (Private, ); }; };
    364363                90213E3D123A40C200D422F3 /* MemoryStatistics.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 90213E3B123A40C200D422F3 /* MemoryStatistics.cpp */; };
    … …  
    11121111                86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNode.h; path = dfg/DFGNode.h; sourceTree = "<group>"; };
    11131112                86ECA3F9132DF25A002B2AD7 /* DFGScoreBoard.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGScoreBoard.h; path = dfg/DFGScoreBoard.h; sourceTree = "<group>"; };
    1114                 86ECA4F0132EAA6D002B2AD7 /* DFGAliasTracker.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAliasTracker.h; path = dfg/DFGAliasTracker.h; sourceTree = "<group>"; };
    11151113                86F38858121130CA007A7CE3 /* AtomicStringHash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AtomicStringHash.h; path = text/AtomicStringHash.h; sourceTree = "<group>"; };
    11161114                90213E3B123A40C200D422F3 /* MemoryStatistics.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MemoryStatistics.cpp; sourceTree = "<group>"; };
    … …  
    22362234                                0FD3C82214115D0E00FD81CB /* DFGDriver.h */,
    22372235                                0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
    2238                                 86ECA4F0132EAA6D002B2AD7 /* DFGAliasTracker.h */,
    22392236                                86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
    22402237                                86EC9DB51328DF82002B2AD7 /* DFGByteCodeParser.h */,
    … …  
    24942491                                5135FAF212D26ACE003C083B /* Decoder.h in Headers */,
    24952492                                BC18C3FC0E16F5CD00B34460 /* Deque.h in Headers */,
    2496                                 86ECA4F1132EAA6D002B2AD7 /* DFGAliasTracker.h in Headers */,
    24972493                                86EC9DC51328DF82002B2AD7 /* DFGByteCodeParser.h in Headers */,
    24982494                                86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,

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

    r95310 r95389  
    2929#if ENABLE(DFG_JIT)
    3030
    31 #include "DFGAliasTracker.h"
    3231#include "DFGCapabilities.h"
    33 #include "DFGScoreBoard.h"
    3432#include "CodeBlock.h"
    3533#include <wtf/MathExtras.h>
    … …  
    636634            m_constants[i] = ConstantRecord();
    637635    }
    638 
    639     AliasTracker aliases(m_graph);
    640636
    641637    Interpreter* interpreter = m_globalData->interpreter;
    … …  
    951947            weaklyPredictInt32(property);
    952948
    953             NodeIndex getByVal = addToGraph(GetByVal, OpInfo(0), OpInfo(PredictNone), base, property, aliases.lookupGetByVal(base, property));
     949            NodeIndex getByVal = addToGraph(GetByVal, OpInfo(0), OpInfo(PredictNone), base, property);
    954950            set(currentInstruction[1].u.operand, getByVal);
    955951            stronglyPredict(getByVal);
    956             aliases.recordGetByVal(getByVal);
    957952
    958953            NEXT_OPCODE(op_get_by_val);
    … …  
    966961            weaklyPredictInt32(property);
    967962
    968             NodeIndex aliasedGet = aliases.lookupGetByVal(base, property);
    969             NodeIndex putByVal = addToGraph(aliasedGet != NoNode ? PutByValAlias : PutByVal, base, property, value);
    970             aliases.recordPutByVal(putByVal);
     963            addToGraph(PutByVal, base, property, value);
    971964
    972965            NEXT_OPCODE(op_put_by_val);
    … …  
    999992                methodCheckData.prototype = methodCall.cachedPrototype.get();
    1000993                m_graph.m_methodCheckData.append(methodCheckData);
    1001                
    1002                 aliases.recordGetMethod(checkMethod);
    1003994            } else {
    1004995                NodeIndex getMethod = addToGraph(GetMethod, OpInfo(identifier), OpInfo(PredictNone), base);
    1005996                set(getInstruction[1].u.operand, getMethod);
    1006997                stronglyPredict(getMethod);
    1007                 aliases.recordGetMethod(getMethod);
    1008998            }
    1009999           
    … …  
    10191009            set(currentInstruction[1].u.operand, getById);
    10201010            stronglyPredict(getById);
    1021             aliases.recordGetById(getById);
    10221011
    10231012            NEXT_OPCODE(op_get_by_id);
    … …  
    10301019            bool direct = currentInstruction[8].u.operand;
    10311020
    1032             if (direct) {
    1033                 NodeIndex putByIdDirect = addToGraph(PutByIdDirect, OpInfo(identifier), base, value);
    1034                 aliases.recordPutByIdDirect(putByIdDirect);
    1035             } else {
    1036                 NodeIndex putById = addToGraph(PutById, OpInfo(identifier), base, value);
    1037                 aliases.recordPutById(putById);
    1038             }
     1021            if (direct)
     1022                addToGraph(PutByIdDirect, OpInfo(identifier), base, value);
     1023            else
     1024                addToGraph(PutById, OpInfo(identifier), base, value);
    10391025
    10401026            NEXT_OPCODE(op_put_by_id);
    … …  
    12531239            }
    12541240           
    1255             NodeIndex call = addCall(interpreter, currentInstruction, Call);
    1256             aliases.recordCall(call);
     1241            addCall(interpreter, currentInstruction, Call);
    12571242            NEXT_OPCODE(op_call);
    12581243        }
    12591244           
    12601245        case op_construct: {
    1261             NodeIndex construct = addCall(interpreter, currentInstruction, Construct);
    1262             aliases.recordConstruct(construct);
     1246            addCall(interpreter, currentInstruction, Construct);
    12631247            NEXT_OPCODE(op_construct);
    12641248        }
    … …  
    12721256            NodeIndex resolve = addToGraph(Resolve, OpInfo(identifier));
    12731257            set(currentInstruction[1].u.operand, resolve);
    1274             aliases.recordResolve(resolve);
    12751258
    12761259            NEXT_OPCODE(op_resolve);
    … …  
    12821265            NodeIndex resolve = addToGraph(currentInstruction[3].u.operand ? ResolveBaseStrictPut : ResolveBase, OpInfo(identifier));
    12831266            set(currentInstruction[1].u.operand, resolve);
    1284             aliases.recordResolve(resolve);
    12851267
    12861268            NEXT_OPCODE(op_resolve_base);
    … …  
    13861368}
    13871369
    1388 void ByteCodeParser::allocateVirtualRegisters()
    1389 {
    1390     ScoreBoard scoreBoard(m_graph, m_preservedVars);
    1391     unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
    1392     for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
    1393         Node& node = m_graph[i];
    1394        
    1395         if (!node.shouldGenerate())
    1396             continue;
    1397        
    1398         // GetLocal nodes are effectively phi nodes in the graph, referencing
    1399         // results from prior blocks.
    1400         if (node.op != GetLocal) {
    1401             // First, call use on all of the current node's children, then
    1402             // allocate a VirtualRegister for this node. We do so in this
    1403             // order so that if a child is on its last use, and a
    1404             // VirtualRegister is freed, then it may be reused for node.
    1405             if (node.op & NodeHasVarArgs) {
    1406                 for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
    1407                     scoreBoard.use(m_graph.m_varArgChildren[childIdx]);
    1408             } else {
    1409                 scoreBoard.use(node.child1());
    1410                 scoreBoard.use(node.child2());
    1411                 scoreBoard.use(node.child3());
    1412             }
    1413         }
    1414 
    1415         if (!node.hasResult())
    1416             continue;
    1417 
    1418         node.setVirtualRegister(scoreBoard.allocate());
    1419         // 'mustGenerate' nodes have their useCount artificially elevated,
    1420         // call use now to account for this.
    1421         if (node.mustGenerate())
    1422             scoreBoard.use(i);
    1423     }
    1424 
    1425     // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
    1426     // for the function (and checked for on entry). Since we perform a new and
    1427     // different allocation of temporaries, more registers may now be required.
    1428     unsigned calleeRegisters = scoreBoard.allocatedCount() + m_preservedVars + m_parameterSlots;
    1429     if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
    1430         m_codeBlock->m_numCalleeRegisters = calleeRegisters;
    1431 }
    1432 
    14331370bool ByteCodeParser::parse()
    14341371{
    … …  
    14621399    processPhiStack<LocalPhiStack>();
    14631400    processPhiStack<ArgumentPhiStack>();
    1464 
    1465     allocateVirtualRegisters();
     1401   
     1402    m_graph.m_preservedVars = m_preservedVars;
     1403    m_graph.m_parameterSlots = m_parameterSlots;
    14661404
    14671405#if ENABLE(DFG_DEBUG_VERBOSE)

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

    r95273 r95389  
    7878    //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
    7979    printf("% 4d:%s<%c%u:", (int)nodeIndex, skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
    80     if (node.hasResult() && !skipped)
     80    if (node.hasResult() && !skipped && node.hasVirtualRegister())
    8181        printf("%u", node.virtualRegister());
    8282    else

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

    r95310 r95389  
    6565    JSObject* function;
    6666    JSObject* prototype;
     67   
     68    bool operator==(const MethodCheckData& other) const
     69    {
     70        if (structure != other.structure)
     71            return false;
     72        if (prototypeStructure != other.prototypeStructure)
     73            return false;
     74        if (function != other.function)
     75            return false;
     76        if (prototype != other.prototype)
     77            return false;
     78        return true;
     79    }
     80   
     81    bool operator!=(const MethodCheckData& other) const
     82    {
     83        return !(*this == other);
     84    }
    6785};
    6886
    … …  
    282300    Vector<NodeIndex, 16> m_varArgChildren;
    283301    Vector<MethodCheckData> m_methodCheckData;
     302    unsigned m_preservedVars;
     303    unsigned m_parameterSlots;
    284304private:
    285305   

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

    r95310 r95389  
    108108// Entries in the NodeType enum (below) are composed of an id, a result type (possibly none)
    109109// and some additional informative flags (must generate, is constant, etc).
    110 #define NodeIdMask          0xFFF
    111 #define NodeResultMask     0xF000
    112 #define NodeMustGenerate  0x10000 // set on nodes that have side effects, and may not trivially be removed by DCE.
    113 #define NodeIsConstant    0x20000
    114 #define NodeIsJump        0x40000
    115 #define NodeIsBranch      0x80000
    116 #define NodeIsTerminal   0x100000
    117 #define NodeHasVarArgs   0x200000
     110#define NodeIdMask           0xFFF
     111#define NodeResultMask      0xF000
     112#define NodeMustGenerate   0x10000 // set on nodes that have side effects, and may not trivially be removed by DCE.
     113#define NodeIsConstant     0x20000
     114#define NodeIsJump         0x40000
     115#define NodeIsBranch       0x80000
     116#define NodeIsTerminal    0x100000
     117#define NodeHasVarArgs    0x200000
     118#define NodeClobbersWorld 0x400000
     119#define NodeMightClobber  0x800000
    118120
    119121// These values record the result type of the node (as checked by NodeResultMask, above), 0 for no result.
    … …  
    132134    macro(GetLocal, NodeResultJS) \
    133135    macro(SetLocal, 0) \
     136    macro(Phantom, NodeMustGenerate) \
    134137    macro(Phi, 0) \
    135138    \
    … …  
    160163    \
    161164    /* Add of values may either be arithmetic, or result in string concatenation. */\
    162     macro(ValueAdd, NodeResultJS | NodeMustGenerate) \
     165    macro(ValueAdd, NodeResultJS | NodeMustGenerate | NodeMightClobber) \
    163166    \
    164167    /* Property access. */\
    … …  
    167170    /* this must be the directly subsequent property put. */\
    168171    macro(GetByVal, NodeResultJS | NodeMustGenerate) \
    169     macro(PutByVal, NodeMustGenerate) \
    170     macro(PutByValAlias, NodeMustGenerate) \
    171     macro(GetById, NodeResultJS | NodeMustGenerate) \
    172     macro(PutById, NodeMustGenerate) \
    173     macro(PutByIdDirect, NodeMustGenerate) \
     172    macro(PutByVal, NodeMustGenerate | NodeClobbersWorld) \
     173    macro(PutByValAlias, NodeMustGenerate | NodeClobbersWorld) \
     174    macro(GetById, NodeResultJS | NodeMustGenerate | NodeClobbersWorld) \
     175    macro(PutById, NodeMustGenerate | NodeClobbersWorld) \
     176    macro(PutByIdDirect, NodeMustGenerate | NodeClobbersWorld) \
    174177    macro(GetMethod, NodeResultJS | NodeMustGenerate) \
    175178    macro(CheckMethod, NodeResultJS | NodeMustGenerate) \
    176179    macro(GetGlobalVar, NodeResultJS | NodeMustGenerate) \
    177     macro(PutGlobalVar, NodeMustGenerate) \
     180    macro(PutGlobalVar, NodeMustGenerate | NodeClobbersWorld) \
    178181    \
    179182    /* Nodes for comparison operations. */\
    180     macro(CompareLess, NodeResultBoolean | NodeMustGenerate) \
    181     macro(CompareLessEq, NodeResultBoolean | NodeMustGenerate) \
    182     macro(CompareGreater, NodeResultBoolean | NodeMustGenerate) \
    183     macro(CompareGreaterEq, NodeResultBoolean | NodeMustGenerate) \
    184     macro(CompareEq, NodeResultBoolean | NodeMustGenerate) \
     183    macro(CompareLess, NodeResultBoolean | NodeMustGenerate | NodeMightClobber) \
     184    macro(CompareLessEq, NodeResultBoolean | NodeMustGenerate | NodeMightClobber) \
     185    macro(CompareGreater, NodeResultBoolean | NodeMustGenerate | NodeMightClobber) \
     186    macro(CompareGreaterEq, NodeResultBoolean | NodeMustGenerate | NodeMightClobber) \
     187    macro(CompareEq, NodeResultBoolean | NodeMustGenerate | NodeMightClobber) \
    185188    macro(CompareStrictEq, NodeResultBoolean) \
    186189    \
    187190    /* Calls. */\
    188     macro(Call, NodeResultJS | NodeMustGenerate | NodeHasVarArgs) \
    189     macro(Construct, NodeResultJS | NodeMustGenerate | NodeHasVarArgs) \
     191    macro(Call, NodeResultJS | NodeMustGenerate | NodeHasVarArgs | NodeClobbersWorld) \
     192    macro(Construct, NodeResultJS | NodeMustGenerate | NodeHasVarArgs | NodeClobbersWorld) \
    190193    \
    191194    /* Resolve nodes. */\
    192     macro(Resolve, NodeResultJS | NodeMustGenerate) \
    193     macro(ResolveBase, NodeResultJS | NodeMustGenerate) \
    194     macro(ResolveBaseStrictPut, NodeResultJS | NodeMustGenerate) \
     195    macro(Resolve, NodeResultJS | NodeMustGenerate | NodeClobbersWorld) \
     196    macro(ResolveBase, NodeResultJS | NodeMustGenerate | NodeClobbersWorld) \
     197    macro(ResolveBaseStrictPut, NodeResultJS | NodeMustGenerate | NodeClobbersWorld) \
    195198    \
    196199    /* Nodes for misc operations. */\
    197     macro(Breakpoint, NodeMustGenerate) \
     200    macro(Breakpoint, NodeMustGenerate | NodeClobbersWorld) \
    198201    macro(CheckHasInstance, NodeMustGenerate) \
    199202    macro(InstanceOf, NodeResultBoolean) \
    200     macro(LogicalNot, NodeResultBoolean) \
     203    macro(LogicalNot, NodeResultBoolean | NodeMightClobber) \
    201204    \
    202205    /* Block terminals. */\
    … …  
    211214    FOR_EACH_DFG_OP(DFG_OP_ENUM)
    212215#undef DFG_OP_ENUM
     216    LastNodeId
    213217};
    214218
    … …  
    485489    }
    486490   
     491    bool hasVirtualRegister()
     492    {
     493        return m_virtualRegister != InvalidVirtualRegister;
     494    }
     495   
    487496    VirtualRegister virtualRegister()
    488497    {
    … …  
    518527    {
    519528        return mustGenerate() ? m_refCount - 1 : m_refCount;
     529    }
     530   
     531    void setRefCount(unsigned refCount)
     532    {
     533        m_refCount = refCount;
    520534    }
    521535   

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

    r95310 r95389  
    3030
    3131#include "DFGGraph.h"
     32#include "DFGScoreBoard.h"
     33#include <wtf/FixedArray.h>
    3234
    3335namespace JSC { namespace DFG {
    … …  
    5961        m_variableUses.initializeSimilarTo(m_graph.predictions());
    6062       
     63        // Replacements are used to implement local common subexpression elimination.
     64        m_replacements.resize(m_graph.size());
     65       
    6166        for (unsigned i = 0; i < m_graph.size(); ++i) {
    6267            m_predictions[i] = PredictNone;
    6368            m_uses[i] = PredictNone;
    64         }
     69            m_replacements[i] = NoNode;
     70        }
     71       
     72        for (unsigned i = 0; i < LastNodeId; ++i)
     73            m_lastSeen[i] = NoNode;
    6574    }
    6675   
    … …  
    8897       
    8998        fixup();
     99       
     100#if ENABLE(DFG_DEBUG_VERBOSE)
     101        printf("Graph after propagation fixup:\n");
     102        m_graph.dump(m_codeBlock);
     103#endif
     104
     105        localCSE();
     106
     107#if ENABLE(DFG_DEBUG_VERBOSE)
     108        printf("Graph after CSE:\n");
     109        m_graph.dump(m_codeBlock);
     110#endif
     111
     112        allocateVirtualRegisters();
     113
     114#if ENABLE(DFG_DEBUG_VERBOSE)
     115        printf("Graph after virtual register allocation:\n");
     116        m_graph.dump(m_codeBlock);
     117#endif
    90118    }
    91119   
    … …  
    302330            break;
    303331           
     332        // This gets ignored because it doesn't do anything.
     333        case Phantom:
     334            break;
     335           
    304336        default:
    305337            ASSERT_NOT_REACHED();
    … …  
    411443    }
    412444   
     445    NodeIndex canonicalize(NodeIndex nodeIndex)
     446    {
     447        if (nodeIndex == NoNode)
     448            return NoNode;
     449       
     450        if (m_graph[nodeIndex].op == ValueToNumber)
     451            nodeIndex = m_graph[nodeIndex].child1();
     452       
     453        if (m_graph[nodeIndex].op == ValueToInt32)
     454            nodeIndex = m_graph[nodeIndex].child1();
     455       
     456        return nodeIndex;
     457    }
     458   
     459    // Computes where the search for a candidate for CSE should start. Don't call
     460    // this directly; call startIndex() instead as it does logging in debug mode.
     461    NodeIndex computeStartIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
     462    {
     463        const unsigned limit = 300;
     464       
     465        NodeIndex start = m_start;
     466        if (m_compileIndex - start > limit)
     467            start = m_compileIndex - limit;
     468       
     469        ASSERT(start >= m_start);
     470       
     471        NodeIndex child = canonicalize(child1);
     472        if (child == NoNode)
     473            return start;
     474       
     475        if (start < child)
     476            start = child;
     477       
     478        child = canonicalize(child2);
     479        if (child == NoNode)
     480            return start;
     481       
     482        if (start < child)
     483            start = child;
     484       
     485        child = canonicalize(child3);
     486        if (child == NoNode)
     487            return start;
     488       
     489        if (start < child)
     490            start = child;
     491       
     492        return start;
     493    }
     494   
     495    NodeIndex startIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
     496    {
     497        NodeIndex result = computeStartIndexForChildren(child1, child2, child3);
     498#if ENABLE(DFG_DEBUG_VERBOSE)
     499        printf("  lookback %u: ", result);
     500#endif
     501        return result;
     502    }
     503   
     504    NodeIndex startIndex()
     505    {
     506        Node& node = m_graph[m_compileIndex];
     507        return startIndexForChildren(node.child1(), node.child2(), node.child3());
     508    }
     509   
     510    NodeIndex endIndexForPureCSE()
     511    {
     512        NodeIndex result = m_lastSeen[m_graph[m_compileIndex].op & NodeIdMask];
     513        if (result == NoNode)
     514            result = 0;
     515        else
     516            result++;
     517        ASSERT(result <= m_compileIndex);
     518#if ENABLE(DFG_DEBUG_VERBOSE)
     519        printf("  limit %u: ", result);
     520#endif
     521        return result;
     522    }
     523   
     524    NodeIndex pureCSE(Node& node)
     525    {
     526        NodeIndex child1 = canonicalize(node.child1());
     527        NodeIndex child2 = canonicalize(node.child2());
     528        NodeIndex child3 = canonicalize(node.child3());
     529       
     530        NodeIndex start = startIndex();
     531        for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
     532            Node& otherNode = m_graph[index];
     533            if (node.op != otherNode.op)
     534                continue;
     535           
     536            NodeIndex otherChild = canonicalize(otherNode.child1());
     537            if (otherChild == NoNode)
     538                return index;
     539            if (otherChild != child1)
     540                continue;
     541           
     542            otherChild = canonicalize(otherNode.child2());
     543            if (otherChild == NoNode)
     544                return index;
     545            if (otherChild != child2)
     546                continue;
     547           
     548            otherChild = canonicalize(otherNode.child3());
     549            if (otherChild == NoNode)
     550                return index;
     551            if (otherChild != child3)
     552                continue;
     553           
     554            return index;
     555        }
     556        return NoNode;
     557    }
     558   
     559    bool isPredictedNumerical(Node& node)
     560    {
     561        PredictedType left = m_predictions[node.child1()];
     562        PredictedType right = m_predictions[node.child2()];
     563        return isStrongPrediction(left) && isStrongPrediction(right)
     564            && isNumberPrediction(left) && isNumberPrediction(right);
     565    }
     566   
     567    bool logicalNotIsPure(Node& node)
     568    {
     569        PredictedType prediction = m_predictions[node.child1()];
     570        return isBooleanPrediction(prediction) || !isStrongPrediction(prediction);
     571    }
     572   
     573    bool clobbersWorld(NodeIndex nodeIndex)
     574    {
     575        Node& node = m_graph[nodeIndex];
     576        if (node.op & NodeClobbersWorld)
     577            return true;
     578        if (!(node.op & NodeMightClobber))
     579            return false;
     580        switch (node.op) {
     581        case ValueAdd:
     582        case CompareLess:
     583        case CompareLessEq:
     584        case CompareGreater:
     585        case CompareGreaterEq:
     586        case CompareEq:
     587            return !isPredictedNumerical(node);
     588        case LogicalNot:
     589            return !logicalNotIsPure(node);
     590        default:
     591            ASSERT_NOT_REACHED();
     592            return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
     593        }
     594    }
     595   
     596    NodeIndex globalVarLoadElimination(unsigned varNumber)
     597    {
     598        NodeIndex start = startIndex();
     599        for (NodeIndex index = m_compileIndex; index-- > start;) {
     600            Node& node = m_graph[index];
     601            switch (node.op) {
     602            case GetGlobalVar:
     603                if (node.varNumber() == varNumber)
     604                    return index;
     605                break;
     606            case PutGlobalVar:
     607                if (node.varNumber() == varNumber)
     608                    return node.child1();
     609                break;
     610            default:
     611                break;
     612            }
     613            if (clobbersWorld(index))
     614                break;
     615        }
     616        return NoNode;
     617    }
     618   
     619    NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
     620    {
     621        NodeIndex start = startIndexForChildren(child1, child2);
     622        for (NodeIndex index = m_compileIndex; index-- > start;) {
     623            Node& node = m_graph[index];
     624            switch (node.op) {
     625            case GetByVal:
     626                if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
     627                    return index;
     628                break;
     629            case PutByVal:
     630                if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
     631                    return node.child3();
     632                break;
     633            default:
     634                break;
     635            }
     636            if (clobbersWorld(index))
     637                break;
     638        }
     639        return NoNode;
     640    }
     641   
     642    NodeIndex getMethodLoadElimination(const MethodCheckData& methodCheckData, unsigned identifierNumber, NodeIndex child1)
     643    {
     644        NodeIndex start = startIndex();
     645        for (NodeIndex index = m_compileIndex; index-- > start;) {
     646            Node& node = m_graph[index];
     647            if (node.op == CheckMethod
     648                && node.child1() == child1
     649                && node.identifierNumber() == identifierNumber
     650                && m_graph.m_methodCheckData[node.methodCheckDataIndex()] == methodCheckData)
     651                return index;
     652            if (clobbersWorld(index))
     653                break;
     654        }
     655        return NoNode;
     656    }
     657   
     658    void performSubstitution(NodeIndex& child)
     659    {
     660        // Check if this operand is actually unused.
     661        if (child == NoNode)
     662            return;
     663       
     664        // Check if there is any replacement.
     665        NodeIndex replacement = m_replacements[child];
     666        if (replacement == NoNode)
     667            return;
     668       
     669        child = replacement;
     670       
     671        // There is definitely a replacement. Assert that the replacement does not
     672        // have a replacement.
     673        ASSERT(m_replacements[child] == NoNode);
     674       
     675        m_graph[child].ref();
     676    }
     677   
     678    void setReplacement(NodeIndex replacement)
     679    {
     680        if (replacement == NoNode)
     681            return;
     682       
     683        // Be safe. Don't try to perform replacements if the predictions don't
     684        // agree.
     685        if (m_predictions[m_compileIndex] != m_predictions[replacement])
     686            return;
     687       
     688#if ENABLE(DFG_DEBUG_VERBOSE)
     689        printf("   Replacing @%u -> @%u", m_compileIndex, replacement);
     690#endif
     691       
     692        Node& node = m_graph[m_compileIndex];
     693        node.op = Phantom;
     694        node.setRefCount(1);
     695       
     696        // At this point we will eliminate all references to this node.
     697        m_replacements[m_compileIndex] = replacement;
     698    }
     699   
     700    void performNodeCSE(Node& node)
     701    {
     702        if (node.op & NodeHasVarArgs) {
     703            for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
     704                performSubstitution(m_graph.m_varArgChildren[childIdx]);
     705        } else {
     706            performSubstitution(node.children.fixed.child1);
     707            performSubstitution(node.children.fixed.child2);
     708            performSubstitution(node.children.fixed.child3);
     709        }
     710       
     711        if (!node.shouldGenerate())
     712            return;
     713       
     714#if ENABLE(DFG_DEBUG_VERBOSE)
     715        printf("   %s[%u]: ", Graph::opName(m_graph[m_compileIndex].op), m_compileIndex);
     716#endif
     717
     718        switch (node.op) {
     719       
     720        // Handle the pure nodes. These nodes never have any side-effects.
     721        case BitAnd:
     722        case BitOr:
     723        case BitXor:
     724        case BitRShift:
     725        case BitLShift:
     726        case BitURShift:
     727        case ArithAdd:
     728        case ArithSub:
     729        case ArithMul:
     730        case ArithMod:
     731        case ArithDiv:
     732        case ArithAbs:
     733            setReplacement(pureCSE(node));
     734            break;
     735           
     736        // Handle nodes that are conditionally pure: these are pure, and can
     737        // be CSE'd, so long as the prediction is the one we want.
     738        case ValueAdd:
     739        case CompareLess:
     740        case CompareLessEq:
     741        case CompareGreater:
     742        case CompareGreaterEq:
     743        case CompareEq: {
     744            if (isPredictedNumerical(node)) {
     745                NodeIndex replacementIndex = pureCSE(node);
     746                if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex]))
     747                    setReplacement(replacementIndex);
     748            }
     749            break;
     750        }
     751           
     752        case LogicalNot: {
     753            if (logicalNotIsPure(node)) {
     754                NodeIndex replacementIndex = pureCSE(node);
     755                if (replacementIndex != NoNode && logicalNotIsPure(m_graph[replacementIndex]))
     756                    setReplacement(replacementIndex);
     757            }
     758            break;
     759        }
     760           
     761        // Finally handle heap accesses. These are not quite pure, but we can still
     762        // optimize them provided that some subtle conditions are met.
     763        case GetGlobalVar:
     764            setReplacement(globalVarLoadElimination(node.varNumber()));
     765            break;
     766           
     767        case GetByVal:
     768            setReplacement(getByValLoadElimination(node.child1(), node.child2()));
     769            break;
     770           
     771        case PutByVal:
     772            if (getByValLoadElimination(node.child1(), node.child2()) != NoNode)
     773                node.op = PutByValAlias;
     774            break;
     775           
     776        case CheckMethod:
     777            setReplacement(getMethodLoadElimination(m_graph.m_methodCheckData[node.methodCheckDataIndex()], node.identifierNumber(), node.child1()));
     778            break;
     779           
     780        default:
     781            // do nothing.
     782            break;
     783        }
     784       
     785        m_lastSeen[node.op & NodeIdMask] = m_compileIndex;
     786#if ENABLE(DFG_DEBUG_VERBOSE)
     787        printf("\n");
     788#endif
     789    }
     790   
     791    void performBlockCSE(BasicBlock& block)
     792    {
     793        m_start = block.begin;
     794        NodeIndex end = block.end;
     795        for (m_compileIndex = m_start; m_compileIndex < end; ++m_compileIndex)
     796            performNodeCSE(m_graph[m_compileIndex]);
     797    }
     798   
     799    void localCSE()
     800    {
     801#if ENABLE(DFG_DEBUG_VERBOSE)
     802        printf("Performing local CSE:");
     803#endif
     804        for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
     805            performBlockCSE(*m_graph.m_blocks[block]);
     806    }
     807   
     808    void allocateVirtualRegisters()
     809    {
     810        ScoreBoard scoreBoard(m_graph, m_graph.m_preservedVars);
     811        unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
     812        for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
     813            Node& node = m_graph[i];
     814       
     815            if (!node.shouldGenerate())
     816                continue;
     817       
     818            // GetLocal nodes are effectively phi nodes in the graph, referencing
     819            // results from prior blocks.
     820            if (node.op != GetLocal) {
     821                // First, call use on all of the current node's children, then
     822                // allocate a VirtualRegister for this node. We do so in this
     823                // order so that if a child is on its last use, and a
     824                // VirtualRegister is freed, then it may be reused for node.
     825                if (node.op & NodeHasVarArgs) {
     826                    for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
     827                        scoreBoard.use(m_graph.m_varArgChildren[childIdx]);
     828                } else {
     829                    scoreBoard.use(node.child1());
     830                    scoreBoard.use(node.child2());
     831                    scoreBoard.use(node.child3());
     832                }
     833            }
     834
     835            if (!node.hasResult())
     836                continue;
     837
     838            node.setVirtualRegister(scoreBoard.allocate());
     839            // 'mustGenerate' nodes have their useCount artificially elevated,
     840            // call use now to account for this.
     841            if (node.mustGenerate())
     842                scoreBoard.use(i);
     843        }
     844
     845        // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
     846        // for the function (and checked for on entry). Since we perform a new and
     847        // different allocation of temporaries, more registers may now be required.
     848        unsigned calleeRegisters = scoreBoard.allocatedCount() + m_graph.m_preservedVars + m_graph.m_parameterSlots;
     849        if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
     850            m_codeBlock->m_numCalleeRegisters = calleeRegisters;
     851    }
     852   
    413853    Graph& m_graph;
    414854    JSGlobalData& m_globalData;
    … …  
    416856    CodeBlock* m_profiledBlock;
    417857   
     858    NodeIndex m_start;
    418859    NodeIndex m_compileIndex;
    419860   
    … …  
    428869   
    429870    bool m_changed;
     871
     872    Vector<NodeIndex, 16> m_replacements;
     873    FixedArray<NodeIndex, LastNodeId> m_lastSeen;
    430874};
    431875
    … …  
    439883    propagator.fixpoint();
    440884   
    441 #if ENABLE(DFG_DEBUG_VERBOSE)
    442     graph.dump(codeBlock);
    443 #endif
    444885}
    445886

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

    r95310 r95389  
    11581158
    11591159    case GetByVal: {
    1160         NodeIndex alias = node.child3();
    1161         if (alias != NoNode) {
    1162             // FIXME: result should be able to reuse child1, child2. Should have an 'UnusedOperand' type.
    1163             JSValueOperand aliasedValue(this, node.child3());
    1164             GPRTemporary result(this, aliasedValue);
    1165             m_jit.move(aliasedValue.gpr(), result.gpr());
    1166             jsValueResult(result.gpr(), m_compileIndex);
    1167             break;
    1168         }
    1169 
     1160        ASSERT(node.child3() == NoNode);
    11701161        SpeculateCellOperand base(this, node.child1());
    11711162        SpeculateStrictInt32Operand property(this, node.child2());
    … …  
    15971588        break;
    15981589    }
     1590       
     1591    case Phantom:
     1592        // This is a no-op.
     1593        noResult(m_compileIndex);
     1594        break;
    15991595    }
    16001596   
Note: See TracChangeset for help on using the changeset viewer.