diff options
Diffstat (limited to 'js/src/jit/ScalarReplacement.cpp')
| -rw-r--r-- | js/src/jit/ScalarReplacement.cpp | 1350 |
1 files changed, 1350 insertions, 0 deletions
diff --git a/js/src/jit/ScalarReplacement.cpp b/js/src/jit/ScalarReplacement.cpp new file mode 100644 index 000000000..4614b2162 --- /dev/null +++ b/js/src/jit/ScalarReplacement.cpp @@ -0,0 +1,1350 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "jit/ScalarReplacement.h" + +#include "mozilla/Vector.h" + +#include "jit/IonAnalysis.h" +#include "jit/JitSpewer.h" +#include "jit/MIR.h" +#include "jit/MIRGenerator.h" +#include "jit/MIRGraph.h" +#include "vm/UnboxedObject.h" + +#include "jsobjinlines.h" + +namespace js { +namespace jit { + +template <typename MemoryView> +class EmulateStateOf +{ + private: + typedef typename MemoryView::BlockState BlockState; + + MIRGenerator* mir_; + MIRGraph& graph_; + + // Block state at the entrance of all basic blocks. + Vector<BlockState*, 8, SystemAllocPolicy> states_; + + public: + EmulateStateOf(MIRGenerator* mir, MIRGraph& graph) + : mir_(mir), + graph_(graph) + { + } + + bool run(MemoryView& view); +}; + +template <typename MemoryView> +bool +EmulateStateOf<MemoryView>::run(MemoryView& view) +{ + // Initialize the current block state of each block to an unknown state. + if (!states_.appendN(nullptr, graph_.numBlocks())) + return false; + + // Initialize the first block which needs to be traversed in RPO. + MBasicBlock* startBlock = view.startingBlock(); + if (!view.initStartingState(&states_[startBlock->id()])) + return false; + + // Iterate over each basic block which has a valid entry state, and merge + // the state in the successor blocks. + for (ReversePostorderIterator block = graph_.rpoBegin(startBlock); block != graph_.rpoEnd(); block++) { + if (mir_->shouldCancel(MemoryView::phaseName)) + return false; + + // Get the block state as the result of the merge of all predecessors + // which have already been visited in RPO. This means that backedges + // are not yet merged into the loop. + BlockState* state = states_[block->id()]; + if (!state) + continue; + view.setEntryBlockState(state); + + // Iterates over resume points, phi and instructions. + for (MNodeIterator iter(*block); iter; ) { + // Increment the iterator before visiting the instruction, as the + // visit function might discard itself from the basic block. + MNode* ins = *iter++; + if (ins->isDefinition()) + ins->toDefinition()->accept(&view); + else + view.visitResumePoint(ins->toResumePoint()); + if (view.oom()) + return false; + } + + // For each successor, merge the current state into the state of the + // successors. + for (size_t s = 0; s < block->numSuccessors(); s++) { + MBasicBlock* succ = block->getSuccessor(s); + if (!view.mergeIntoSuccessorState(*block, succ, &states_[succ->id()])) + return false; + } + } + + states_.clear(); + return true; +} + +static bool +IsObjectEscaped(MInstruction* ins, JSObject* objDefault = nullptr); + +// Returns False if the lambda is not escaped and if it is optimizable by +// ScalarReplacementOfObject. +static bool +IsLambdaEscaped(MLambda* lambda, JSObject* obj) +{ + JitSpewDef(JitSpew_Escape, "Check lambda\n", lambda); + JitSpewIndent spewIndent(JitSpew_Escape); + + // The scope chain is not escaped if none of the Lambdas which are + // capturing it are escaped. + for (MUseIterator i(lambda->usesBegin()); i != lambda->usesEnd(); i++) { + MNode* consumer = (*i)->consumer(); + if (!consumer->isDefinition()) { + // Cannot optimize if it is observable from fun.arguments or others. + if (!consumer->toResumePoint()->isRecoverableOperand(*i)) { + JitSpew(JitSpew_Escape, "Observable lambda cannot be recovered"); + return true; + } + continue; + } + + MDefinition* def = consumer->toDefinition(); + if (!def->isFunctionEnvironment()) { + JitSpewDef(JitSpew_Escape, "is escaped by\n", def); + return true; + } + + if (IsObjectEscaped(def->toInstruction(), obj)) { + JitSpewDef(JitSpew_Escape, "is indirectly escaped by\n", def); + return true; + } + } + JitSpew(JitSpew_Escape, "Lambda is not escaped"); + return false; +} + +// Returns False if the object is not escaped and if it is optimizable by +// ScalarReplacementOfObject. +// +// For the moment, this code is dumb as it only supports objects which are not +// changing shape, and which are known by TI at the object creation. +static bool +IsObjectEscaped(MInstruction* ins, JSObject* objDefault) +{ + MOZ_ASSERT(ins->type() == MIRType::Object); + MOZ_ASSERT(ins->isNewObject() || ins->isGuardShape() || ins->isCreateThisWithTemplate() || + ins->isNewCallObject() || ins->isFunctionEnvironment()); + + JitSpewDef(JitSpew_Escape, "Check object\n", ins); + JitSpewIndent spewIndent(JitSpew_Escape); + + JSObject* obj = objDefault; + if (!obj) + obj = MObjectState::templateObjectOf(ins); + + if (!obj) { + JitSpew(JitSpew_Escape, "No template object defined."); + return true; + } + + // Check if the object is escaped. If the object is not the first argument + // of either a known Store / Load, then we consider it as escaped. This is a + // cheap and conservative escape analysis. + for (MUseIterator i(ins->usesBegin()); i != ins->usesEnd(); i++) { + MNode* consumer = (*i)->consumer(); + if (!consumer->isDefinition()) { + // Cannot optimize if it is observable from fun.arguments or others. + if (!consumer->toResumePoint()->isRecoverableOperand(*i)) { + JitSpew(JitSpew_Escape, "Observable object cannot be recovered"); + return true; + } + continue; + } + + MDefinition* def = consumer->toDefinition(); + switch (def->op()) { + case MDefinition::Op_StoreFixedSlot: + case MDefinition::Op_LoadFixedSlot: + // Not escaped if it is the first argument. + if (def->indexOf(*i) == 0) + break; + + JitSpewDef(JitSpew_Escape, "is escaped by\n", def); + return true; + + case MDefinition::Op_LoadUnboxedScalar: + case MDefinition::Op_StoreUnboxedScalar: + case MDefinition::Op_LoadUnboxedObjectOrNull: + case MDefinition::Op_StoreUnboxedObjectOrNull: + case MDefinition::Op_LoadUnboxedString: + case MDefinition::Op_StoreUnboxedString: + // Not escaped if it is the first argument. + if (def->indexOf(*i) != 0) { + JitSpewDef(JitSpew_Escape, "is escaped by\n", def); + return true; + } + + if (!def->getOperand(1)->isConstant()) { + JitSpewDef(JitSpew_Escape, "is addressed with unknown index\n", def); + return true; + } + + break; + + case MDefinition::Op_PostWriteBarrier: + break; + + case MDefinition::Op_Slots: { +#ifdef DEBUG + // Assert that MSlots are only used by MStoreSlot and MLoadSlot. + MSlots* ins = def->toSlots(); + MOZ_ASSERT(ins->object() != 0); + for (MUseIterator i(ins->usesBegin()); i != ins->usesEnd(); i++) { + // toDefinition should normally never fail, since they don't get + // captured by resume points. + MDefinition* def = (*i)->consumer()->toDefinition(); + MOZ_ASSERT(def->op() == MDefinition::Op_StoreSlot || + def->op() == MDefinition::Op_LoadSlot); + } +#endif + break; + } + + case MDefinition::Op_GuardShape: { + MGuardShape* guard = def->toGuardShape(); + MOZ_ASSERT(!ins->isGuardShape()); + if (obj->maybeShape() != guard->shape()) { + JitSpewDef(JitSpew_Escape, "has a non-matching guard shape\n", guard); + return true; + } + if (IsObjectEscaped(def->toInstruction(), obj)) { + JitSpewDef(JitSpew_Escape, "is indirectly escaped by\n", def); + return true; + } + break; + } + + case MDefinition::Op_Lambda: { + MLambda* lambda = def->toLambda(); + if (IsLambdaEscaped(lambda, obj)) { + JitSpewDef(JitSpew_Escape, "is indirectly escaped by\n", lambda); + return true; + } + break; + } + + // This instruction is a no-op used to verify that scalar replacement + // is working as expected in jit-test. + case MDefinition::Op_AssertRecoveredOnBailout: + break; + + default: + JitSpewDef(JitSpew_Escape, "is escaped by\n", def); + return true; + } + } + + JitSpew(JitSpew_Escape, "Object is not escaped"); + return false; +} + +class ObjectMemoryView : public MDefinitionVisitorDefaultNoop +{ + public: + typedef MObjectState BlockState; + static const char* phaseName; + + private: + TempAllocator& alloc_; + MConstant* undefinedVal_; + MInstruction* obj_; + MBasicBlock* startBlock_; + BlockState* state_; + + // Used to improve the memory usage by sharing common modification. + const MResumePoint* lastResumePoint_; + + bool oom_; + + public: + ObjectMemoryView(TempAllocator& alloc, MInstruction* obj); + + MBasicBlock* startingBlock(); + bool initStartingState(BlockState** pState); + + void setEntryBlockState(BlockState* state); + bool mergeIntoSuccessorState(MBasicBlock* curr, MBasicBlock* succ, BlockState** pSuccState); + +#ifdef DEBUG + void assertSuccess(); +#else + void assertSuccess() {} +#endif + + bool oom() const { return oom_; } + + public: + void visitResumePoint(MResumePoint* rp); + void visitObjectState(MObjectState* ins); + void visitStoreFixedSlot(MStoreFixedSlot* ins); + void visitLoadFixedSlot(MLoadFixedSlot* ins); + void visitPostWriteBarrier(MPostWriteBarrier* ins); + void visitStoreSlot(MStoreSlot* ins); + void visitLoadSlot(MLoadSlot* ins); + void visitGuardShape(MGuardShape* ins); + void visitFunctionEnvironment(MFunctionEnvironment* ins); + void visitLambda(MLambda* ins); + void visitStoreUnboxedScalar(MStoreUnboxedScalar* ins); + void visitLoadUnboxedScalar(MLoadUnboxedScalar* ins); + void visitStoreUnboxedObjectOrNull(MStoreUnboxedObjectOrNull* ins); + void visitLoadUnboxedObjectOrNull(MLoadUnboxedObjectOrNull* ins); + void visitStoreUnboxedString(MStoreUnboxedString* ins); + void visitLoadUnboxedString(MLoadUnboxedString* ins); + + private: + void storeOffset(MInstruction* ins, size_t offset, MDefinition* value); + void loadOffset(MInstruction* ins, size_t offset); +}; + +const char* ObjectMemoryView::phaseName = "Scalar Replacement of Object"; + +ObjectMemoryView::ObjectMemoryView(TempAllocator& alloc, MInstruction* obj) + : alloc_(alloc), + obj_(obj), + startBlock_(obj->block()), + state_(nullptr), + lastResumePoint_(nullptr), + oom_(false) +{ + // Annotate snapshots RValue such that we recover the store first. + obj_->setIncompleteObject(); + + // Annotate the instruction such that we do not replace it by a + // Magic(JS_OPTIMIZED_OUT) in case of removed uses. + obj_->setImplicitlyUsedUnchecked(); +} + +MBasicBlock* +ObjectMemoryView::startingBlock() +{ + return startBlock_; +} + +bool +ObjectMemoryView::initStartingState(BlockState** pState) +{ + // Uninitialized slots have an "undefined" value. + undefinedVal_ = MConstant::New(alloc_, UndefinedValue()); + startBlock_->insertBefore(obj_, undefinedVal_); + + // Create a new block state and insert at it at the location of the new object. + BlockState* state = BlockState::New(alloc_, obj_); + if (!state) + return false; + + startBlock_->insertAfter(obj_, state); + + // Initialize the properties of the object state. + if (!state->initFromTemplateObject(alloc_, undefinedVal_)) + return false; + + // Hold out of resume point until it is visited. + state->setInWorklist(); + + *pState = state; + return true; +} + +void +ObjectMemoryView::setEntryBlockState(BlockState* state) +{ + state_ = state; +} + +bool +ObjectMemoryView::mergeIntoSuccessorState(MBasicBlock* curr, MBasicBlock* succ, + BlockState** pSuccState) +{ + BlockState* succState = *pSuccState; + + // When a block has no state yet, create an empty one for the + // successor. + if (!succState) { + // If the successor is not dominated then the object cannot flow + // in this basic block without a Phi. We know that no Phi exist + // in non-dominated successors as the conservative escaped + // analysis fails otherwise. Such condition can succeed if the + // successor is a join at the end of a if-block and the object + // only exists within the branch. + if (!startBlock_->dominates(succ)) + return true; + + // If there is only one predecessor, carry over the last state of the + // block to the successor. As the block state is immutable, if the + // current block has multiple successors, they will share the same entry + // state. + if (succ->numPredecessors() <= 1 || !state_->numSlots()) { + *pSuccState = state_; + return true; + } + + // If we have multiple predecessors, then we allocate one Phi node for + // each predecessor, and create a new block state which only has phi + // nodes. These would later be removed by the removal of redundant phi + // nodes. + succState = BlockState::Copy(alloc_, state_); + if (!succState) + return false; + + size_t numPreds = succ->numPredecessors(); + for (size_t slot = 0; slot < state_->numSlots(); slot++) { + MPhi* phi = MPhi::New(alloc_); + if (!phi->reserveLength(numPreds)) + return false; + + // Fill the input of the successors Phi with undefined + // values, and each block later fills the Phi inputs. + for (size_t p = 0; p < numPreds; p++) + phi->addInput(undefinedVal_); + + // Add Phi in the list of Phis of the basic block. + succ->addPhi(phi); + succState->setSlot(slot, phi); + } + + // Insert the newly created block state instruction at the beginning + // of the successor block, after all the phi nodes. Note that it + // would be captured by the entry resume point of the successor + // block. + succ->insertBefore(succ->safeInsertTop(), succState); + *pSuccState = succState; + } + + MOZ_ASSERT_IF(succ == startBlock_, startBlock_->isLoopHeader()); + if (succ->numPredecessors() > 1 && succState->numSlots() && succ != startBlock_) { + // We need to re-compute successorWithPhis as the previous EliminatePhis + // phase might have removed all the Phis from the successor block. + size_t currIndex; + MOZ_ASSERT(!succ->phisEmpty()); + if (curr->successorWithPhis()) { + MOZ_ASSERT(curr->successorWithPhis() == succ); + currIndex = curr->positionInPhiSuccessor(); + } else { + currIndex = succ->indexForPredecessor(curr); + curr->setSuccessorWithPhis(succ, currIndex); + } + MOZ_ASSERT(succ->getPredecessor(currIndex) == curr); + + // Copy the current slot states to the index of current block in all the + // Phi created during the first visit of the successor. + for (size_t slot = 0; slot < state_->numSlots(); slot++) { + MPhi* phi = succState->getSlot(slot)->toPhi(); + phi->replaceOperand(currIndex, state_->getSlot(slot)); + } + } + + return true; +} + +#ifdef DEBUG +void +ObjectMemoryView::assertSuccess() +{ + for (MUseIterator i(obj_->usesBegin()); i != obj_->usesEnd(); i++) { + MNode* ins = (*i)->consumer(); + MDefinition* def = nullptr; + + // Resume points have been replaced by the object state. + if (ins->isResumePoint() || (def = ins->toDefinition())->isRecoveredOnBailout()) { + MOZ_ASSERT(obj_->isIncompleteObject()); + continue; + } + + // The only remaining uses would be removed by DCE, which will also + // recover the object on bailouts. + MOZ_ASSERT(def->isSlots() || def->isLambda()); + MOZ_ASSERT(!def->hasDefUses()); + } +} +#endif + +void +ObjectMemoryView::visitResumePoint(MResumePoint* rp) +{ + // As long as the MObjectState is not yet seen next to the allocation, we do + // not patch the resume point to recover the side effects. + if (!state_->isInWorklist()) { + rp->addStore(alloc_, state_, lastResumePoint_); + lastResumePoint_ = rp; + } +} + +void +ObjectMemoryView::visitObjectState(MObjectState* ins) +{ + if (ins->isInWorklist()) + ins->setNotInWorklist(); +} + +void +ObjectMemoryView::visitStoreFixedSlot(MStoreFixedSlot* ins) +{ + // Skip stores made on other objects. + if (ins->object() != obj_) + return; + + // Clone the state and update the slot value. + if (state_->hasFixedSlot(ins->slot())) { + state_ = BlockState::Copy(alloc_, state_); + if (!state_) { + oom_ = true; + return; + } + + state_->setFixedSlot(ins->slot(), ins->value()); + ins->block()->insertBefore(ins->toInstruction(), state_); + } else { + // UnsafeSetReserveSlot can access baked-in slots which are guarded by + // conditions, which are not seen by the escape analysis. + MBail* bailout = MBail::New(alloc_, Bailout_Inevitable); + ins->block()->insertBefore(ins, bailout); + } + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitLoadFixedSlot(MLoadFixedSlot* ins) +{ + // Skip loads made on other objects. + if (ins->object() != obj_) + return; + + // Replace load by the slot value. + if (state_->hasFixedSlot(ins->slot())) { + ins->replaceAllUsesWith(state_->getFixedSlot(ins->slot())); + } else { + // UnsafeGetReserveSlot can access baked-in slots which are guarded by + // conditions, which are not seen by the escape analysis. + MBail* bailout = MBail::New(alloc_, Bailout_Inevitable); + ins->block()->insertBefore(ins, bailout); + ins->replaceAllUsesWith(undefinedVal_); + } + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitPostWriteBarrier(MPostWriteBarrier* ins) +{ + // Skip loads made on other objects. + if (ins->object() != obj_) + return; + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitStoreSlot(MStoreSlot* ins) +{ + // Skip stores made on other objects. + MSlots* slots = ins->slots()->toSlots(); + if (slots->object() != obj_) { + // Guard objects are replaced when they are visited. + MOZ_ASSERT(!slots->object()->isGuardShape() || slots->object()->toGuardShape()->object() != obj_); + return; + } + + // Clone the state and update the slot value. + if (state_->hasDynamicSlot(ins->slot())) { + state_ = BlockState::Copy(alloc_, state_); + if (!state_) { + oom_ = true; + return; + } + + state_->setDynamicSlot(ins->slot(), ins->value()); + ins->block()->insertBefore(ins->toInstruction(), state_); + } else { + // UnsafeSetReserveSlot can access baked-in slots which are guarded by + // conditions, which are not seen by the escape analysis. + MBail* bailout = MBail::New(alloc_, Bailout_Inevitable); + ins->block()->insertBefore(ins, bailout); + } + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitLoadSlot(MLoadSlot* ins) +{ + // Skip loads made on other objects. + MSlots* slots = ins->slots()->toSlots(); + if (slots->object() != obj_) { + // Guard objects are replaced when they are visited. + MOZ_ASSERT(!slots->object()->isGuardShape() || slots->object()->toGuardShape()->object() != obj_); + return; + } + + // Replace load by the slot value. + if (state_->hasDynamicSlot(ins->slot())) { + ins->replaceAllUsesWith(state_->getDynamicSlot(ins->slot())); + } else { + // UnsafeGetReserveSlot can access baked-in slots which are guarded by + // conditions, which are not seen by the escape analysis. + MBail* bailout = MBail::New(alloc_, Bailout_Inevitable); + ins->block()->insertBefore(ins, bailout); + ins->replaceAllUsesWith(undefinedVal_); + } + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitGuardShape(MGuardShape* ins) +{ + // Skip loads made on other objects. + if (ins->object() != obj_) + return; + + // Replace the shape guard by its object. + ins->replaceAllUsesWith(obj_); + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitFunctionEnvironment(MFunctionEnvironment* ins) +{ + // Skip function environment which are not aliases of the NewCallObject. + MDefinition* input = ins->input(); + if (!input->isLambda() || input->toLambda()->environmentChain() != obj_) + return; + + // Replace the function environment by the scope chain of the lambda. + ins->replaceAllUsesWith(obj_); + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitLambda(MLambda* ins) +{ + if (ins->environmentChain() != obj_) + return; + + // In order to recover the lambda we need to recover the scope chain, as the + // lambda is holding it. + ins->setIncompleteObject(); +} + +static size_t +GetOffsetOf(MDefinition* index, size_t width, int32_t baseOffset) +{ + int32_t idx = index->toConstant()->toInt32(); + MOZ_ASSERT(idx >= 0); + MOZ_ASSERT(baseOffset >= 0 && size_t(baseOffset) >= UnboxedPlainObject::offsetOfData()); + return idx * width + baseOffset - UnboxedPlainObject::offsetOfData(); +} + +static size_t +GetOffsetOf(MDefinition* index, Scalar::Type type, int32_t baseOffset) +{ + return GetOffsetOf(index, Scalar::byteSize(type), baseOffset); +} + +void +ObjectMemoryView::storeOffset(MInstruction* ins, size_t offset, MDefinition* value) +{ + // Clone the state and update the slot value. + MOZ_ASSERT(state_->hasOffset(offset)); + state_ = BlockState::Copy(alloc_, state_); + if (!state_) { + oom_ = true; + return; + } + + state_->setOffset(offset, value); + ins->block()->insertBefore(ins, state_); + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::loadOffset(MInstruction* ins, size_t offset) +{ + // Replace load by the slot value. + MOZ_ASSERT(state_->hasOffset(offset)); + ins->replaceAllUsesWith(state_->getOffset(offset)); + + // Remove original instruction. + ins->block()->discard(ins); +} + +void +ObjectMemoryView::visitStoreUnboxedScalar(MStoreUnboxedScalar* ins) +{ + // Skip stores made on other objects. + if (ins->elements() != obj_) + return; + + size_t offset = GetOffsetOf(ins->index(), ins->storageType(), ins->offsetAdjustment()); + storeOffset(ins, offset, ins->value()); +} + +void +ObjectMemoryView::visitLoadUnboxedScalar(MLoadUnboxedScalar* ins) +{ + // Skip loads made on other objects. + if (ins->elements() != obj_) + return; + + // Replace load by the slot value. + size_t offset = GetOffsetOf(ins->index(), ins->storageType(), ins->offsetAdjustment()); + loadOffset(ins, offset); +} + +void +ObjectMemoryView::visitStoreUnboxedObjectOrNull(MStoreUnboxedObjectOrNull* ins) +{ + // Skip stores made on other objects. + if (ins->elements() != obj_) + return; + + // Clone the state and update the slot value. + size_t offset = GetOffsetOf(ins->index(), sizeof(uintptr_t), ins->offsetAdjustment()); + storeOffset(ins, offset, ins->value()); +} + +void +ObjectMemoryView::visitLoadUnboxedObjectOrNull(MLoadUnboxedObjectOrNull* ins) +{ + // Skip loads made on other objects. + if (ins->elements() != obj_) + return; + + // Replace load by the slot value. + size_t offset = GetOffsetOf(ins->index(), sizeof(uintptr_t), ins->offsetAdjustment()); + loadOffset(ins, offset); +} + +void +ObjectMemoryView::visitStoreUnboxedString(MStoreUnboxedString* ins) +{ + // Skip stores made on other objects. + if (ins->elements() != obj_) + return; + + // Clone the state and update the slot value. + size_t offset = GetOffsetOf(ins->index(), sizeof(uintptr_t), ins->offsetAdjustment()); + storeOffset(ins, offset, ins->value()); +} + +void +ObjectMemoryView::visitLoadUnboxedString(MLoadUnboxedString* ins) +{ + // Skip loads made on other objects. + if (ins->elements() != obj_) + return; + + // Replace load by the slot value. + size_t offset = GetOffsetOf(ins->index(), sizeof(uintptr_t), ins->offsetAdjustment()); + loadOffset(ins, offset); +} + +static bool +IndexOf(MDefinition* ins, int32_t* res) +{ + MOZ_ASSERT(ins->isLoadElement() || ins->isStoreElement()); + MDefinition* indexDef = ins->getOperand(1); // ins->index(); + if (indexDef->isBoundsCheck()) + indexDef = indexDef->toBoundsCheck()->index(); + if (indexDef->isToInt32()) + indexDef = indexDef->toToInt32()->getOperand(0); + MConstant* indexDefConst = indexDef->maybeConstantValue(); + if (!indexDefConst || indexDefConst->type() != MIRType::Int32) + return false; + *res = indexDefConst->toInt32(); + return true; +} + +// Returns False if the elements is not escaped and if it is optimizable by +// ScalarReplacementOfArray. +static bool +IsElementEscaped(MElements* def, uint32_t arraySize) +{ + JitSpewDef(JitSpew_Escape, "Check elements\n", def); + JitSpewIndent spewIndent(JitSpew_Escape); + + for (MUseIterator i(def->usesBegin()); i != def->usesEnd(); i++) { + // The MIRType::Elements cannot be captured in a resume point as + // it does not represent a value allocation. + MDefinition* access = (*i)->consumer()->toDefinition(); + + switch (access->op()) { + case MDefinition::Op_LoadElement: { + MOZ_ASSERT(access->toLoadElement()->elements() == def); + + // If we need hole checks, then the array cannot be escaped + // as the array might refer to the prototype chain to look + // for properties, thus it might do additional side-effects + // which are not reflected by the alias set, is we are + // bailing on holes. + if (access->toLoadElement()->needsHoleCheck()) { + JitSpewDef(JitSpew_Escape, + "has a load element with a hole check\n", access); + return true; + } + + // If the index is not a constant then this index can alias + // all others. We do not handle this case. + int32_t index; + if (!IndexOf(access, &index)) { + JitSpewDef(JitSpew_Escape, + "has a load element with a non-trivial index\n", access); + return true; + } + if (index < 0 || arraySize <= uint32_t(index)) { + JitSpewDef(JitSpew_Escape, + "has a load element with an out-of-bound index\n", access); + return true; + } + break; + } + + case MDefinition::Op_StoreElement: { + MOZ_ASSERT(access->toStoreElement()->elements() == def); + + // If we need hole checks, then the array cannot be escaped + // as the array might refer to the prototype chain to look + // for properties, thus it might do additional side-effects + // which are not reflected by the alias set, is we are + // bailing on holes. + if (access->toStoreElement()->needsHoleCheck()) { + JitSpewDef(JitSpew_Escape, + "has a store element with a hole check\n", access); + return true; + } + + // If the index is not a constant then this index can alias + // all others. We do not handle this case. + int32_t index; + if (!IndexOf(access, &index)) { + JitSpewDef(JitSpew_Escape, "has a store element with a non-trivial index\n", access); + return true; + } + if (index < 0 || arraySize <= uint32_t(index)) { + JitSpewDef(JitSpew_Escape, "has a store element with an out-of-bound index\n", access); + return true; + } + + // We are not yet encoding magic hole constants in resume points. + if (access->toStoreElement()->value()->type() == MIRType::MagicHole) { + JitSpewDef(JitSpew_Escape, "has a store element with an magic-hole constant\n", access); + return true; + } + break; + } + + case MDefinition::Op_SetInitializedLength: + MOZ_ASSERT(access->toSetInitializedLength()->elements() == def); + break; + + case MDefinition::Op_InitializedLength: + MOZ_ASSERT(access->toInitializedLength()->elements() == def); + break; + + case MDefinition::Op_ArrayLength: + MOZ_ASSERT(access->toArrayLength()->elements() == def); + break; + + default: + JitSpewDef(JitSpew_Escape, "is escaped by\n", access); + return true; + } + } + JitSpew(JitSpew_Escape, "Elements is not escaped"); + return false; +} + +// Returns False if the array is not escaped and if it is optimizable by +// ScalarReplacementOfArray. +// +// For the moment, this code is dumb as it only supports arrays which are not +// changing length, with only access with known constants. +static bool +IsArrayEscaped(MInstruction* ins) +{ + MOZ_ASSERT(ins->type() == MIRType::Object); + MOZ_ASSERT(ins->isNewArray()); + uint32_t length = ins->toNewArray()->length(); + + JitSpewDef(JitSpew_Escape, "Check array\n", ins); + JitSpewIndent spewIndent(JitSpew_Escape); + + JSObject* obj = ins->toNewArray()->templateObject(); + if (!obj) { + JitSpew(JitSpew_Escape, "No template object defined."); + return true; + } + + if (obj->is<UnboxedArrayObject>()) { + JitSpew(JitSpew_Escape, "Template object is an unboxed plain object."); + return true; + } + + if (length >= 16) { + JitSpew(JitSpew_Escape, "Array has too many elements"); + return true; + } + + // Check if the object is escaped. If the object is not the first argument + // of either a known Store / Load, then we consider it as escaped. This is a + // cheap and conservative escape analysis. + for (MUseIterator i(ins->usesBegin()); i != ins->usesEnd(); i++) { + MNode* consumer = (*i)->consumer(); + if (!consumer->isDefinition()) { + // Cannot optimize if it is observable from fun.arguments or others. + if (!consumer->toResumePoint()->isRecoverableOperand(*i)) { + JitSpew(JitSpew_Escape, "Observable array cannot be recovered"); + return true; + } + continue; + } + + MDefinition* def = consumer->toDefinition(); + switch (def->op()) { + case MDefinition::Op_Elements: { + MElements *elem = def->toElements(); + MOZ_ASSERT(elem->object() == ins); + if (IsElementEscaped(elem, length)) { + JitSpewDef(JitSpew_Escape, "is indirectly escaped by\n", elem); + return true; + } + + break; + } + + // This instruction is a no-op used to verify that scalar replacement + // is working as expected in jit-test. + case MDefinition::Op_AssertRecoveredOnBailout: + break; + + default: + JitSpewDef(JitSpew_Escape, "is escaped by\n", def); + return true; + } + } + + JitSpew(JitSpew_Escape, "Array is not escaped"); + return false; +} + +// This class replaces every MStoreElement and MSetInitializedLength by an +// MArrayState which emulates the content of the array. All MLoadElement, +// MInitializedLength and MArrayLength are replaced by the corresponding value. +// +// In order to restore the value of the array correctly in case of bailouts, we +// replace all reference of the allocation by the MArrayState definition. +class ArrayMemoryView : public MDefinitionVisitorDefaultNoop +{ + public: + typedef MArrayState BlockState; + static const char* phaseName; + + private: + TempAllocator& alloc_; + MConstant* undefinedVal_; + MConstant* length_; + MInstruction* arr_; + MBasicBlock* startBlock_; + BlockState* state_; + + // Used to improve the memory usage by sharing common modification. + const MResumePoint* lastResumePoint_; + + bool oom_; + + public: + ArrayMemoryView(TempAllocator& alloc, MInstruction* arr); + + MBasicBlock* startingBlock(); + bool initStartingState(BlockState** pState); + + void setEntryBlockState(BlockState* state); + bool mergeIntoSuccessorState(MBasicBlock* curr, MBasicBlock* succ, BlockState** pSuccState); + +#ifdef DEBUG + void assertSuccess(); +#else + void assertSuccess() {} +#endif + + bool oom() const { return oom_; } + + private: + bool isArrayStateElements(MDefinition* elements); + void discardInstruction(MInstruction* ins, MDefinition* elements); + + public: + void visitResumePoint(MResumePoint* rp); + void visitArrayState(MArrayState* ins); + void visitStoreElement(MStoreElement* ins); + void visitLoadElement(MLoadElement* ins); + void visitSetInitializedLength(MSetInitializedLength* ins); + void visitInitializedLength(MInitializedLength* ins); + void visitArrayLength(MArrayLength* ins); +}; + +const char* ArrayMemoryView::phaseName = "Scalar Replacement of Array"; + +ArrayMemoryView::ArrayMemoryView(TempAllocator& alloc, MInstruction* arr) + : alloc_(alloc), + undefinedVal_(nullptr), + length_(nullptr), + arr_(arr), + startBlock_(arr->block()), + state_(nullptr), + lastResumePoint_(nullptr), + oom_(false) +{ + // Annotate snapshots RValue such that we recover the store first. + arr_->setIncompleteObject(); + + // Annotate the instruction such that we do not replace it by a + // Magic(JS_OPTIMIZED_OUT) in case of removed uses. + arr_->setImplicitlyUsedUnchecked(); +} + +MBasicBlock* +ArrayMemoryView::startingBlock() +{ + return startBlock_; +} + +bool +ArrayMemoryView::initStartingState(BlockState** pState) +{ + // Uninitialized elements have an "undefined" value. + undefinedVal_ = MConstant::New(alloc_, UndefinedValue()); + MConstant* initLength = MConstant::New(alloc_, Int32Value(0)); + arr_->block()->insertBefore(arr_, undefinedVal_); + arr_->block()->insertBefore(arr_, initLength); + + // Create a new block state and insert at it at the location of the new array. + BlockState* state = BlockState::New(alloc_, arr_, undefinedVal_, initLength); + if (!state) + return false; + + startBlock_->insertAfter(arr_, state); + + // Hold out of resume point until it is visited. + state->setInWorklist(); + + *pState = state; + return true; +} + +void +ArrayMemoryView::setEntryBlockState(BlockState* state) +{ + state_ = state; +} + +bool +ArrayMemoryView::mergeIntoSuccessorState(MBasicBlock* curr, MBasicBlock* succ, + BlockState** pSuccState) +{ + BlockState* succState = *pSuccState; + + // When a block has no state yet, create an empty one for the + // successor. + if (!succState) { + // If the successor is not dominated then the array cannot flow + // in this basic block without a Phi. We know that no Phi exist + // in non-dominated successors as the conservative escaped + // analysis fails otherwise. Such condition can succeed if the + // successor is a join at the end of a if-block and the array + // only exists within the branch. + if (!startBlock_->dominates(succ)) + return true; + + // If there is only one predecessor, carry over the last state of the + // block to the successor. As the block state is immutable, if the + // current block has multiple successors, they will share the same entry + // state. + if (succ->numPredecessors() <= 1 || !state_->numElements()) { + *pSuccState = state_; + return true; + } + + // If we have multiple predecessors, then we allocate one Phi node for + // each predecessor, and create a new block state which only has phi + // nodes. These would later be removed by the removal of redundant phi + // nodes. + succState = BlockState::Copy(alloc_, state_); + if (!succState) + return false; + + size_t numPreds = succ->numPredecessors(); + for (size_t index = 0; index < state_->numElements(); index++) { + MPhi* phi = MPhi::New(alloc_); + if (!phi->reserveLength(numPreds)) + return false; + + // Fill the input of the successors Phi with undefined + // values, and each block later fills the Phi inputs. + for (size_t p = 0; p < numPreds; p++) + phi->addInput(undefinedVal_); + + // Add Phi in the list of Phis of the basic block. + succ->addPhi(phi); + succState->setElement(index, phi); + } + + // Insert the newly created block state instruction at the beginning + // of the successor block, after all the phi nodes. Note that it + // would be captured by the entry resume point of the successor + // block. + succ->insertBefore(succ->safeInsertTop(), succState); + *pSuccState = succState; + } + + MOZ_ASSERT_IF(succ == startBlock_, startBlock_->isLoopHeader()); + if (succ->numPredecessors() > 1 && succState->numElements() && succ != startBlock_) { + // We need to re-compute successorWithPhis as the previous EliminatePhis + // phase might have removed all the Phis from the successor block. + size_t currIndex; + MOZ_ASSERT(!succ->phisEmpty()); + if (curr->successorWithPhis()) { + MOZ_ASSERT(curr->successorWithPhis() == succ); + currIndex = curr->positionInPhiSuccessor(); + } else { + currIndex = succ->indexForPredecessor(curr); + curr->setSuccessorWithPhis(succ, currIndex); + } + MOZ_ASSERT(succ->getPredecessor(currIndex) == curr); + + // Copy the current element states to the index of current block in all + // the Phi created during the first visit of the successor. + for (size_t index = 0; index < state_->numElements(); index++) { + MPhi* phi = succState->getElement(index)->toPhi(); + phi->replaceOperand(currIndex, state_->getElement(index)); + } + } + + return true; +} + +#ifdef DEBUG +void +ArrayMemoryView::assertSuccess() +{ + MOZ_ASSERT(!arr_->hasLiveDefUses()); +} +#endif + +void +ArrayMemoryView::visitResumePoint(MResumePoint* rp) +{ + // As long as the MArrayState is not yet seen next to the allocation, we do + // not patch the resume point to recover the side effects. + if (!state_->isInWorklist()) { + rp->addStore(alloc_, state_, lastResumePoint_); + lastResumePoint_ = rp; + } +} + +void +ArrayMemoryView::visitArrayState(MArrayState* ins) +{ + if (ins->isInWorklist()) + ins->setNotInWorklist(); +} + +bool +ArrayMemoryView::isArrayStateElements(MDefinition* elements) +{ + return elements->isElements() && elements->toElements()->object() == arr_; +} + +void +ArrayMemoryView::discardInstruction(MInstruction* ins, MDefinition* elements) +{ + MOZ_ASSERT(elements->isElements()); + ins->block()->discard(ins); + if (!elements->hasLiveDefUses()) + elements->block()->discard(elements->toInstruction()); +} + +void +ArrayMemoryView::visitStoreElement(MStoreElement* ins) +{ + // Skip other array objects. + MDefinition* elements = ins->elements(); + if (!isArrayStateElements(elements)) + return; + + // Register value of the setter in the state. + int32_t index; + MOZ_ALWAYS_TRUE(IndexOf(ins, &index)); + state_ = BlockState::Copy(alloc_, state_); + if (!state_) { + oom_ = true; + return; + } + + state_->setElement(index, ins->value()); + ins->block()->insertBefore(ins, state_); + + // Remove original instruction. + discardInstruction(ins, elements); +} + +void +ArrayMemoryView::visitLoadElement(MLoadElement* ins) +{ + // Skip other array objects. + MDefinition* elements = ins->elements(); + if (!isArrayStateElements(elements)) + return; + + // Replace by the value contained at the index. + int32_t index; + MOZ_ALWAYS_TRUE(IndexOf(ins, &index)); + ins->replaceAllUsesWith(state_->getElement(index)); + + // Remove original instruction. + discardInstruction(ins, elements); +} + +void +ArrayMemoryView::visitSetInitializedLength(MSetInitializedLength* ins) +{ + // Skip other array objects. + MDefinition* elements = ins->elements(); + if (!isArrayStateElements(elements)) + return; + + // Replace by the new initialized length. Note that the argument of + // MSetInitalizedLength is the last index and not the initialized length. + // To obtain the length, we need to add 1 to it, and thus we need to create + // a new constant that we register in the ArrayState. + state_ = BlockState::Copy(alloc_, state_); + if (!state_) { + oom_ = true; + return; + } + + int32_t initLengthValue = ins->index()->maybeConstantValue()->toInt32() + 1; + MConstant* initLength = MConstant::New(alloc_, Int32Value(initLengthValue)); + ins->block()->insertBefore(ins, initLength); + ins->block()->insertBefore(ins, state_); + state_->setInitializedLength(initLength); + + // Remove original instruction. + discardInstruction(ins, elements); +} + +void +ArrayMemoryView::visitInitializedLength(MInitializedLength* ins) +{ + // Skip other array objects. + MDefinition* elements = ins->elements(); + if (!isArrayStateElements(elements)) + return; + + // Replace by the value of the length. + ins->replaceAllUsesWith(state_->initializedLength()); + + // Remove original instruction. + discardInstruction(ins, elements); +} + +void +ArrayMemoryView::visitArrayLength(MArrayLength* ins) +{ + // Skip other array objects. + MDefinition* elements = ins->elements(); + if (!isArrayStateElements(elements)) + return; + + // Replace by the value of the length. + if (!length_) { + length_ = MConstant::New(alloc_, Int32Value(state_->numElements())); + arr_->block()->insertBefore(arr_, length_); + } + ins->replaceAllUsesWith(length_); + + // Remove original instruction. + discardInstruction(ins, elements); +} + +bool +ScalarReplacement(MIRGenerator* mir, MIRGraph& graph) +{ + EmulateStateOf<ObjectMemoryView> replaceObject(mir, graph); + EmulateStateOf<ArrayMemoryView> replaceArray(mir, graph); + bool addedPhi = false; + + for (ReversePostorderIterator block = graph.rpoBegin(); block != graph.rpoEnd(); block++) { + if (mir->shouldCancel("Scalar Replacement (main loop)")) + return false; + + for (MInstructionIterator ins = block->begin(); ins != block->end(); ins++) { + if ((ins->isNewObject() || ins->isCreateThisWithTemplate() || ins->isNewCallObject()) && + !IsObjectEscaped(*ins)) + { + ObjectMemoryView view(graph.alloc(), *ins); + if (!replaceObject.run(view)) + return false; + view.assertSuccess(); + addedPhi = true; + continue; + } + + if (ins->isNewArray() && !IsArrayEscaped(*ins)) { + ArrayMemoryView view(graph.alloc(), *ins); + if (!replaceArray.run(view)) + return false; + view.assertSuccess(); + addedPhi = true; + continue; + } + } + } + + if (addedPhi) { + // Phis added by Scalar Replacement are only redundant Phis which are + // not directly captured by any resume point but only by the MDefinition + // state. The conservative observability only focuses on Phis which are + // not used as resume points operands. + AssertExtendedGraphCoherency(graph); + if (!EliminatePhis(mir, graph, ConservativeObservability)) + return false; + } + + return true; +} + +} /* namespace jit */ +} /* namespace js */ |