--- /dev/null
+/*
+ * Copyright (C) 2013, 2014 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 "DFGInPlaceAbstractState.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "CodeBlock.h"
+#include "DFGBasicBlock.h"
+#include "GetByIdStatus.h"
+#include "JSCInlines.h"
+#include "PutByIdStatus.h"
+#include "StringObject.h"
+
+namespace JSC { namespace DFG {
+
+InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
+ : m_graph(graph)
+ , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
+ , m_block(0)
+{
+}
+
+InPlaceAbstractState::~InPlaceAbstractState() { }
+
+void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
+{
+ ASSERT(!m_block);
+
+ ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
+ ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
+ ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
+
+ for (size_t i = 0; i < basicBlock->size(); i++)
+ forNode(basicBlock->at(i)).clear();
+
+ m_variables = basicBlock->valuesAtHead;
+ m_haveStructures = false;
+ for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
+ if (m_variables.argument(i).hasClobberableState()) {
+ m_haveStructures = true;
+ break;
+ }
+ }
+ for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
+ if (m_variables.local(i).hasClobberableState()) {
+ m_haveStructures = true;
+ break;
+ }
+ }
+
+ if (m_graph.m_form == SSA) {
+ HashMap<Node*, AbstractValue>::iterator iter = basicBlock->ssa->valuesAtHead.begin();
+ HashMap<Node*, AbstractValue>::iterator end = basicBlock->ssa->valuesAtHead.end();
+ for (; iter != end; ++iter) {
+ forNode(iter->key) = iter->value;
+ if (iter->value.hasClobberableState())
+ m_haveStructures = true;
+ }
+ }
+
+ basicBlock->cfaShouldRevisit = false;
+ basicBlock->cfaHasVisited = true;
+ m_block = basicBlock;
+ m_isValid = true;
+ m_foundConstants = false;
+ m_branchDirection = InvalidBranchDirection;
+}
+
+static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
+{
+ values.clear();
+
+ HashSet<Node*>::iterator iter = live.begin();
+ HashSet<Node*>::iterator end = live.end();
+ for (; iter != end; ++iter)
+ values.add(*iter, AbstractValue());
+}
+
+void InPlaceAbstractState::initialize()
+{
+ BasicBlock* root = m_graph.block(0);
+ root->cfaShouldRevisit = true;
+ root->cfaHasVisited = false;
+ root->cfaFoundConstants = false;
+ for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
+ root->valuesAtTail.argument(i).clear();
+ if (m_graph.m_form == SSA) {
+ root->valuesAtHead.argument(i).makeHeapTop();
+ continue;
+ }
+
+ Node* node = root->variablesAtHead.argument(i);
+ ASSERT(node->op() == SetArgument);
+ if (!node->variableAccessData()->shouldUnboxIfPossible()) {
+ root->valuesAtHead.argument(i).makeHeapTop();
+ continue;
+ }
+
+ SpeculatedType prediction =
+ node->variableAccessData()->argumentAwarePrediction();
+ if (isInt32Speculation(prediction))
+ root->valuesAtHead.argument(i).setType(SpecInt32);
+ else if (isBooleanSpeculation(prediction))
+ root->valuesAtHead.argument(i).setType(SpecBoolean);
+ else if (isCellSpeculation(prediction))
+ root->valuesAtHead.argument(i).setType(SpecCell);
+ else
+ root->valuesAtHead.argument(i).makeHeapTop();
+ }
+ for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
+ Node* node = root->variablesAtHead.local(i);
+ if (node && node->variableAccessData()->isCaptured())
+ root->valuesAtHead.local(i).makeHeapTop();
+ else
+ root->valuesAtHead.local(i).clear();
+ root->valuesAtTail.local(i).clear();
+ }
+ for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ ASSERT(block->isReachable);
+ block->cfaShouldRevisit = false;
+ block->cfaHasVisited = false;
+ block->cfaFoundConstants = false;
+ for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
+ block->valuesAtHead.argument(i).clear();
+ block->valuesAtTail.argument(i).clear();
+ }
+ for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
+ block->valuesAtHead.local(i).clear();
+ block->valuesAtTail.local(i).clear();
+ }
+ if (m_graph.m_form == SSA)
+ continue;
+ if (!block->isOSRTarget)
+ continue;
+ if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
+ continue;
+ for (size_t i = 0; i < m_graph.m_mustHandleAbstractValues.size(); ++i) {
+ int operand = m_graph.m_mustHandleAbstractValues.operandForIndex(i);
+ Node* node = block->variablesAtHead.operand(operand);
+ if (!node)
+ continue;
+ AbstractValue value = m_graph.m_mustHandleAbstractValues[i];
+ AbstractValue& abstractValue = block->valuesAtHead.operand(operand);
+ VariableAccessData* variable = node->variableAccessData();
+ FlushFormat format = variable->flushFormat();
+ abstractValue.merge(value);
+ abstractValue.fixTypeForRepresentation(resultFor(format));
+ }
+ block->cfaShouldRevisit = true;
+ }
+ if (m_graph.m_form == SSA) {
+ for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
+ setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
+ }
+ }
+}
+
+bool InPlaceAbstractState::endBasicBlock(MergeMode mergeMode)
+{
+ ASSERT(m_block);
+
+ BasicBlock* block = m_block; // Save the block for successor merging.
+
+ block->cfaFoundConstants = m_foundConstants;
+ block->cfaDidFinish = m_isValid;
+ block->cfaBranchDirection = m_branchDirection;
+
+ if (!m_isValid) {
+ reset();
+ return false;
+ }
+
+ bool changed = false;
+
+ if (mergeMode != DontMerge || !ASSERT_DISABLED) {
+ switch (m_graph.m_form) {
+ case ThreadedCPS: {
+ for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
+ AbstractValue& destination = block->valuesAtTail.argument(argument);
+ changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
+ }
+
+ for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
+ AbstractValue& destination = block->valuesAtTail.local(local);
+ changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
+ }
+ break;
+ }
+
+ case SSA: {
+ for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
+ changed |= block->valuesAtTail[i].merge(m_variables[i]);
+
+ HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
+ HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
+ for (; iter != end; ++iter) {
+ Node* node = *iter;
+ changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
+ }
+ break;
+ }
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+ }
+
+ ASSERT(mergeMode != DontMerge || !changed);
+
+ reset();
+
+ if (mergeMode != MergeToSuccessors)
+ return changed;
+
+ return mergeToSuccessors(block);
+}
+
+void InPlaceAbstractState::reset()
+{
+ m_block = 0;
+ m_isValid = false;
+ m_branchDirection = InvalidBranchDirection;
+}
+
+bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
+{
+ if (!node)
+ return false;
+
+ AbstractValue source;
+
+ if (node->variableAccessData()->isCaptured()) {
+ // If it's captured then we know that whatever value was stored into the variable last is the
+ // one we care about. This is true even if the variable at tail is dead, which might happen if
+ // the last thing we did to the variable was a GetLocal and then ended up not using the
+ // GetLocal's result.
+
+ source = inVariable;
+ } else {
+ switch (node->op()) {
+ case Phi:
+ case SetArgument:
+ case PhantomLocal:
+ case Flush:
+ // The block transfers the value from head to tail.
+ source = inVariable;
+ break;
+
+ case GetLocal:
+ // The block refines the value with additional speculations.
+ source = forNode(node);
+ break;
+
+ case SetLocal:
+ // The block sets the variable, and potentially refines it, both
+ // before and after setting it.
+ source = forNode(node->child1());
+ if (node->variableAccessData()->flushFormat() == FlushedDouble)
+ RELEASE_ASSERT(!(source.m_type & ~SpecFullDouble));
+ break;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ break;
+ }
+ }
+
+ if (destination == source) {
+ // Abstract execution did not change the output value of the variable, for this
+ // basic block, on this iteration.
+ return false;
+ }
+
+ // Abstract execution reached a new conclusion about the speculations reached about
+ // this variable after execution of this basic block. Update the state, and return
+ // true to indicate that the fixpoint must go on!
+ destination = source;
+ return true;
+}
+
+bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
+{
+ ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
+ ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
+
+ bool changed = false;
+
+ switch (m_graph.m_form) {
+ case ThreadedCPS: {
+ for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
+ AbstractValue& destination = to->valuesAtHead.argument(argument);
+ changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
+ }
+
+ for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
+ AbstractValue& destination = to->valuesAtHead.local(local);
+ changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
+ }
+ break;
+ }
+
+ case SSA: {
+ for (size_t i = from->valuesAtTail.size(); i--;)
+ changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
+
+ HashSet<Node*>::iterator iter = to->ssa->liveAtHead.begin();
+ HashSet<Node*>::iterator end = to->ssa->liveAtHead.end();
+ for (; iter != end; ++iter) {
+ Node* node = *iter;
+ changed |= to->ssa->valuesAtHead.find(node)->value.merge(
+ from->ssa->valuesAtTail.find(node)->value);
+ }
+ break;
+ }
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ break;
+ }
+
+ if (!to->cfaHasVisited)
+ changed = true;
+
+ to->cfaShouldRevisit |= changed;
+
+ return changed;
+}
+
+inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
+{
+ Node* terminal = basicBlock->last();
+
+ ASSERT(terminal->isTerminal());
+
+ switch (terminal->op()) {
+ case Jump: {
+ ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
+ return merge(basicBlock, terminal->targetBlock());
+ }
+
+ case Branch: {
+ ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
+ bool changed = false;
+ if (basicBlock->cfaBranchDirection != TakeFalse)
+ changed |= merge(basicBlock, terminal->branchData()->taken.block);
+ if (basicBlock->cfaBranchDirection != TakeTrue)
+ changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
+ return changed;
+ }
+
+ case Switch: {
+ // FIXME: It would be cool to be sparse conditional for Switch's. Currently
+ // we're not. However I somehow doubt that this will ever be a big deal.
+ ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
+ SwitchData* data = terminal->switchData();
+ bool changed = merge(basicBlock, data->fallThrough.block);
+ for (unsigned i = data->cases.size(); i--;)
+ changed |= merge(basicBlock, data->cases[i].target.block);
+ return changed;
+ }
+
+ case Return:
+ case Unreachable:
+ ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
+ return false;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ return false;
+ }
+}
+
+inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
+{
+ if (!destinationNode)
+ return false;
+
+ ASSERT_UNUSED(sourceNode, sourceNode);
+
+ // FIXME: We could do some sparse conditional propagation here!
+
+ return destination.merge(source);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
projects / apple / javascriptcore.git / blobdiff