| /* |
| * Copyright (C) 2012 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "DFGStructureCheckHoistingPhase.h" |
| |
| #if ENABLE(DFG_JIT) |
| |
| #include "DFGBasicBlock.h" |
| #include "DFGGraph.h" |
| #include "DFGInsertionSet.h" |
| #include "DFGPhase.h" |
| #include "DFGVariableAccessDataDump.h" |
| #include <wtf/HashMap.h> |
| |
| namespace JSC { namespace DFG { |
| |
| enum CheckBallot { VoteOther, VoteStructureCheck }; |
| |
| class StructureCheckHoistingPhase : public Phase { |
| public: |
| StructureCheckHoistingPhase(Graph& graph) |
| : Phase(graph, "structure check hoisting") |
| { |
| } |
| |
| bool run() |
| { |
| for (unsigned i = m_graph.m_variableAccessData.size(); i--;) { |
| VariableAccessData* variable = &m_graph.m_variableAccessData[i]; |
| if (!variable->isRoot()) |
| continue; |
| variable->clearVotes(); |
| } |
| |
| // Identify the set of variables that are always subject to the same structure |
| // checks. For now, only consider monomorphic structure checks (one structure). |
| |
| for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { |
| BasicBlock* block = m_graph.m_blocks[blockIndex].get(); |
| if (!block) |
| continue; |
| for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { |
| NodeIndex nodeIndex = block->at(indexInBlock); |
| Node& node = m_graph[nodeIndex]; |
| if (!node.shouldGenerate()) |
| continue; |
| switch (node.op()) { |
| case CheckStructure: |
| case StructureTransitionWatchpoint: { |
| Node& child = m_graph[node.child1()]; |
| if (child.op() != GetLocal) |
| break; |
| VariableAccessData* variable = child.variableAccessData(); |
| variable->vote(VoteStructureCheck); |
| if (variable->isCaptured() || variable->structureCheckHoistingFailed()) |
| break; |
| if (!isCellSpeculation(variable->prediction())) |
| break; |
| noticeStructureCheck(variable, node.structureSet()); |
| break; |
| } |
| |
| case ForwardCheckStructure: |
| case ForwardStructureTransitionWatchpoint: |
| // We currently rely on the fact that we're the only ones who would |
| // insert this node. |
| ASSERT_NOT_REACHED(); |
| break; |
| |
| case GetByOffset: |
| case PutByOffset: |
| case PutStructure: |
| case AllocatePropertyStorage: |
| case ReallocatePropertyStorage: |
| case GetButterfly: |
| case GetByVal: |
| case PutByVal: |
| case PutByValAlias: |
| case GetArrayLength: |
| case CheckArray: |
| case GetIndexedPropertyStorage: |
| case Phantom: |
| // Don't count these uses. |
| break; |
| |
| case ArrayifyToStructure: |
| case Arrayify: |
| if (node.arrayMode().conversion() == Array::RageConvert) { |
| // Rage conversion changes structures. We should avoid tying to do |
| // any kind of hoisting when rage conversion is in play. |
| Node& child = m_graph[node.child1()]; |
| if (child.op() != GetLocal) |
| break; |
| VariableAccessData* variable = child.variableAccessData(); |
| variable->vote(VoteOther); |
| if (variable->isCaptured() || variable->structureCheckHoistingFailed()) |
| break; |
| if (!isCellSpeculation(variable->prediction())) |
| break; |
| noticeStructureCheck(variable, 0); |
| } |
| break; |
| |
| case SetLocal: { |
| // Find all uses of the source of the SetLocal. If any of them are a |
| // kind of CheckStructure, then we should notice them to ensure that |
| // we're not hoisting a check that would contravene checks that are |
| // already being performed. |
| VariableAccessData* variable = node.variableAccessData(); |
| if (variable->isCaptured() || variable->structureCheckHoistingFailed()) |
| break; |
| if (!isCellSpeculation(variable->prediction())) |
| break; |
| NodeIndex source = node.child1().index(); |
| for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) { |
| NodeIndex subNodeIndex = block->at(subIndexInBlock); |
| Node& subNode = m_graph[subNodeIndex]; |
| if (!subNode.shouldGenerate()) |
| continue; |
| switch (subNode.op()) { |
| case CheckStructure: { |
| if (subNode.child1().index() != source) |
| break; |
| |
| noticeStructureCheck(variable, subNode.structureSet()); |
| break; |
| } |
| case StructureTransitionWatchpoint: { |
| if (subNode.child1().index() != source) |
| break; |
| |
| noticeStructureCheck(variable, subNode.structure()); |
| break; |
| } |
| default: |
| break; |
| } |
| } |
| |
| m_graph.vote(node, VoteOther); |
| break; |
| } |
| case GarbageValue: |
| break; |
| |
| default: |
| m_graph.vote(node, VoteOther); |
| break; |
| } |
| } |
| } |
| |
| // Disable structure hoisting on variables that appear to mostly be used in |
| // contexts where it doesn't make sense. |
| |
| for (unsigned i = m_graph.m_variableAccessData.size(); i--;) { |
| VariableAccessData* variable = &m_graph.m_variableAccessData[i]; |
| if (!variable->isRoot()) |
| continue; |
| if (variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting()) |
| continue; |
| HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); |
| if (iter == m_map.end()) |
| continue; |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLog( |
| "Zeroing the structure to hoist for ", VariableAccessDataDump(m_graph, variable), |
| " because the ratio is ", variable->voteRatio(), ".\n"); |
| #endif |
| iter->value.m_structure = 0; |
| } |
| |
| // Disable structure check hoisting for variables that cross the OSR entry that |
| // we're currently taking, and where the value currently does not have the |
| // structure we want. |
| |
| for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { |
| BasicBlock* block = m_graph.m_blocks[blockIndex].get(); |
| if (!block) |
| continue; |
| ASSERT(block->isReachable); |
| if (!block->isOSRTarget) |
| continue; |
| if (block->bytecodeBegin != m_graph.m_osrEntryBytecodeIndex) |
| continue; |
| for (size_t i = 0; i < m_graph.m_mustHandleValues.size(); ++i) { |
| int operand = m_graph.m_mustHandleValues.operandForIndex(i); |
| NodeIndex nodeIndex = block->variablesAtHead.operand(operand); |
| if (nodeIndex == NoNode) |
| continue; |
| VariableAccessData* variable = m_graph[nodeIndex].variableAccessData(); |
| HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); |
| if (iter == m_map.end()) |
| continue; |
| if (!iter->value.m_structure) |
| continue; |
| JSValue value = m_graph.m_mustHandleValues[i]; |
| if (!value || !value.isCell()) { |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLog( |
| "Zeroing the structure to hoist for ", VariableAccessDataDump(m_graph, variable), |
| " because the OSR entry value is not a cell: ", value, ".\n"); |
| #endif |
| iter->value.m_structure = 0; |
| continue; |
| } |
| if (value.asCell()->structure() != iter->value.m_structure) { |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLog( |
| "Zeroing the structure to hoist for ", VariableAccessDataDump(m_graph, variable), |
| " because the OSR entry value has structure ", |
| RawPointer(value.asCell()->structure()), " and we wanted ", |
| RawPointer(iter->value.m_structure), ".\n"); |
| #endif |
| iter->value.m_structure = 0; |
| continue; |
| } |
| } |
| } |
| |
| bool changed = false; |
| |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| for (HashMap<VariableAccessData*, CheckData>::iterator it = m_map.begin(); |
| it != m_map.end(); ++it) { |
| if (!it->value.m_structure) { |
| dataLog( |
| "Not hoisting checks for ", VariableAccessDataDump(m_graph, it->key), |
| " because of heuristics.\n"); |
| continue; |
| } |
| dataLog("Hoisting checks for ", VariableAccessDataDump(m_graph, it->key), "\n"); |
| } |
| #endif // DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| |
| // Place CheckStructure's at SetLocal sites. |
| |
| InsertionSet<NodeIndex> insertionSet; |
| for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { |
| BasicBlock* block = m_graph.m_blocks[blockIndex].get(); |
| if (!block) |
| continue; |
| for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { |
| NodeIndex nodeIndex = block->at(indexInBlock); |
| Node& node = m_graph[nodeIndex]; |
| // Be careful not to use 'node' after appending to the graph. In those switch |
| // cases where we need to append, we first carefully extract everything we need |
| // from the node, before doing any appending. |
| if (!node.shouldGenerate()) |
| continue; |
| switch (node.op()) { |
| case SetArgument: { |
| ASSERT(!blockIndex); |
| // Insert a GetLocal and a CheckStructure immediately following this |
| // SetArgument, if the variable was a candidate for structure hoisting. |
| // If the basic block previously only had the SetArgument as its |
| // variable-at-tail, then replace it with this GetLocal. |
| VariableAccessData* variable = node.variableAccessData(); |
| HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); |
| if (iter == m_map.end()) |
| break; |
| if (!iter->value.m_structure) |
| break; |
| |
| node.ref(); |
| |
| CodeOrigin codeOrigin = node.codeOrigin; |
| |
| Node getLocal(GetLocal, codeOrigin, OpInfo(variable), nodeIndex); |
| getLocal.predict(variable->prediction()); |
| getLocal.ref(); |
| NodeIndex getLocalIndex = m_graph.size(); |
| m_graph.append(getLocal); |
| insertionSet.append(indexInBlock + 1, getLocalIndex); |
| |
| Node checkStructure(CheckStructure, codeOrigin, OpInfo(m_graph.addStructureSet(iter->value.m_structure)), getLocalIndex); |
| checkStructure.ref(); |
| NodeIndex checkStructureIndex = m_graph.size(); |
| m_graph.append(checkStructure); |
| insertionSet.append(indexInBlock + 1, checkStructureIndex); |
| |
| if (block->variablesAtTail.operand(variable->local()) == nodeIndex) |
| block->variablesAtTail.operand(variable->local()) = getLocalIndex; |
| |
| m_graph.substituteGetLocal(*block, indexInBlock, variable, getLocalIndex); |
| |
| changed = true; |
| break; |
| } |
| |
| case SetLocal: { |
| VariableAccessData* variable = node.variableAccessData(); |
| HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); |
| if (iter == m_map.end()) |
| break; |
| if (!iter->value.m_structure) |
| break; |
| |
| // First insert a dead SetLocal to tell OSR that the child's value should |
| // be dropped into this bytecode variable if the CheckStructure decides |
| // to exit. |
| |
| CodeOrigin codeOrigin = node.codeOrigin; |
| NodeIndex child1 = node.child1().index(); |
| |
| Node setLocal(SetLocal, codeOrigin, OpInfo(variable), child1); |
| NodeIndex setLocalIndex = m_graph.size(); |
| m_graph.append(setLocal); |
| insertionSet.append(indexInBlock, setLocalIndex); |
| m_graph[child1].ref(); |
| // Use a ForwardCheckStructure to indicate that we should exit to the |
| // next bytecode instruction rather than reexecuting the current one. |
| Node checkStructure(ForwardCheckStructure, codeOrigin, OpInfo(m_graph.addStructureSet(iter->value.m_structure)), child1); |
| checkStructure.ref(); |
| NodeIndex checkStructureIndex = m_graph.size(); |
| m_graph.append(checkStructure); |
| insertionSet.append(indexInBlock, checkStructureIndex); |
| changed = true; |
| break; |
| } |
| |
| default: |
| break; |
| } |
| } |
| insertionSet.execute(*block); |
| } |
| |
| return changed; |
| } |
| |
| private: |
| void noticeStructureCheck(VariableAccessData* variable, Structure* structure) |
| { |
| HashMap<VariableAccessData*, CheckData>::AddResult result = |
| m_map.add(variable, CheckData(structure)); |
| if (result.isNewEntry) |
| return; |
| if (result.iterator->value.m_structure == structure) |
| return; |
| result.iterator->value.m_structure = 0; |
| } |
| |
| void noticeStructureCheck(VariableAccessData* variable, const StructureSet& set) |
| { |
| if (set.size() != 1) { |
| noticeStructureCheck(variable, 0); |
| return; |
| } |
| noticeStructureCheck(variable, set.singletonStructure()); |
| } |
| |
| struct CheckData { |
| Structure* m_structure; |
| |
| CheckData() |
| : m_structure(0) |
| { |
| } |
| |
| CheckData(Structure* structure) |
| : m_structure(structure) |
| { |
| } |
| }; |
| |
| HashMap<VariableAccessData*, CheckData> m_map; |
| }; |
| |
| bool performStructureCheckHoisting(Graph& graph) |
| { |
| SamplingRegion samplingRegion("DFG Structure Check Hoisting Phase"); |
| return runPhase<StructureCheckHoistingPhase>(graph); |
| } |
| |
| } } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
| |
| |
