js/src/jit/ScalarReplacement.cpp
author Brian Hackett <bhackett1024@gmail.com>
Fri, 06 Feb 2015 09:13:29 -0700
changeset 227824 6bfcb81d3716bfcdcd0045d0fb80153159513a83
parent 226945 7b4c0588cba87c37523adbad6f46710d95c74ace
child 230996 2a0481539f3828b5d99a651c830f4f332f37cf34
permissions -rw-r--r--
Bug 1129226 - Refactor ObjectGroup class and accessors, r=jandem.

/* -*- 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"

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());
        }

        // 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;
}

// 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 = nullptr)
{
    MOZ_ASSERT(ins->type() == MIRType_Object);
    MOZ_ASSERT(ins->isNewObject() || ins->isGuardShape() || ins->isCreateThisWithTemplate() ||
               ins->isNewCallObject() || ins->isFunctionEnvironment());

    JSObject *obj = nullptr;
    if (ins->isNewObject())
        obj = ins->toNewObject()->templateObject();
    else if (ins->isCreateThisWithTemplate())
        obj = ins->toCreateThisWithTemplate()->templateObject();
    else if (ins->isNewCallObject())
        obj = ins->toNewCallObject()->templateObject();
    else
        obj = objDefault;

    // Don't optimize unboxed objects, which aren't handled by MObjectState.
    if (obj->is<UnboxedPlainObject>())
        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)) {
                JitSpewDef(JitSpew_Escape, "Observable object cannot be recovered\n", ins);
                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, "Object ", ins);
            JitSpewDef(JitSpew_Escape, "  is escaped by\n", def);
            return true;

          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->lastProperty() != guard->shape()) {
                JitSpewDef(JitSpew_Escape, "Object ", ins);
                JitSpewDef(JitSpew_Escape, "  has a non-matching guard shape\n", guard);
                return true;
            }
            if (IsObjectEscaped(def->toInstruction(), obj))
                return true;
            break;
          }

          case MDefinition::Op_Lambda: {
            MLambda *lambda = def->toLambda();
            // 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)) {
                        JitSpewDef(JitSpew_Escape, "Observable object cannot be recovered\n", ins);
                        return true;
                    }
                    continue;
                }

                MDefinition *def = consumer->toDefinition();
                if (!def->isFunctionEnvironment() || IsObjectEscaped(def->toInstruction(), obj)) {
                    JitSpewDef(JitSpew_Escape, "Object ", ins);
                    JitSpewDef(JitSpew_Escape, "  is escaped through a lambda by\n", def);
                    return true;
                }
            }

            break;
          }

          default:
            JitSpewDef(JitSpew_Escape, "Object ", ins);
            JitSpewDef(JitSpew_Escape, "  is escaped by\n", def);
            return true;
        }
    }

    JitSpewDef(JitSpew_Escape, "Object is not escaped\n", ins);
    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_;

  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

  public:
    void visitResumePoint(MResumePoint *rp);
    void visitObjectState(MObjectState *ins);
    void visitStoreFixedSlot(MStoreFixedSlot *ins);
    void visitLoadFixedSlot(MLoadFixedSlot *ins);
    void visitStoreSlot(MStoreSlot *ins);
    void visitLoadSlot(MLoadSlot *ins);
    void visitGuardShape(MGuardShape *ins);
    void visitFunctionEnvironment(MFunctionEnvironment *ins);
    void visitLambda(MLambda *ins);
};

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)
{
    // 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_, undefinedVal_);
    startBlock_->insertAfter(obj_, state);

    // 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_);
        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.
    state_ = BlockState::Copy(alloc_, state_);
    state_->setFixedSlot(ins->slot(), ins->value());
    ins->block()->insertBefore(ins->toInstruction(), state_);

    // 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.
    ins->replaceAllUsesWith(state_->getFixedSlot(ins->slot()));

    // 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()->obj() != obj_);
        return;
    }

    // Clone the state and update the slot value.
    state_ = BlockState::Copy(alloc_, state_);
    state_->setDynamicSlot(ins->slot(), ins->value());
    ins->block()->insertBefore(ins->toInstruction(), state_);

    // 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()->obj() != obj_);
        return;
    }

    // Replace load by the slot value.
    ins->replaceAllUsesWith(state_->getDynamicSlot(ins->slot()));

    // Remove original instruction.
    ins->block()->discard(ins);
}

void
ObjectMemoryView::visitGuardShape(MGuardShape *ins)
{
    // Skip loads made on other objects.
    if (ins->obj() != 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()->scopeChain() != 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->scopeChain() != obj_)
        return;

    // In order to recover the lambda we need to recover the scope chain, as the
    // lambda is holding it.
    ins->setIncompleteObject();
}

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);
    if (!indexDef->isConstantValue())
        return false;

    Value index = indexDef->constantValue();
    if (!index.isInt32())
        return false;
    *res = index.toInt32();
    return true;
}

// 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 count = ins->toNewArray()->count();

    // The array is probably too large to be represented efficiently with
    // MArrayState, and we do not want to make huge allocations during bailouts.
    if (ins->toNewArray()->allocatingBehaviour() == NewArray_Unallocating) {
        JitSpewDef(JitSpew_Escape, "Array is not allocated\n", ins);
        return true;
    }

    if (count >= 16) {
        JitSpewDef(JitSpew_Escape, "Array has too many elements\n", ins);
        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)) {
                JitSpewDef(JitSpew_Escape, "Observable array cannot be recovered\n", ins);
                return true;
            }
            continue;
        }

        MDefinition *def = consumer->toDefinition();
        switch (def->op()) {
          case MDefinition::Op_Elements: {
            MOZ_ASSERT(def->toElements()->object() == ins);
            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, "Array ", ins);
                        JitSpewDef(JitSpew_Escape,
                                   "  has a load element which needs 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, "Array ", ins);
                        JitSpewDef(JitSpew_Escape,
                                   "  has a load element with a non-trivial index\n", access);
                        return true;
                    }
                    if (index < 0 || count <= uint32_t(index)) {
                        JitSpewDef(JitSpew_Escape, "Array ", ins);
                        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())
                        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, "Array ", ins);
                        JitSpewDef(JitSpew_Escape, "  has a store element with a non-trivial index\n", access);
                        return true;
                    }
                    if (index < 0 || count <= uint32_t(index)) {
                        JitSpewDef(JitSpew_Escape, "Array ", ins);
                        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, "Array ", ins);
                        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, "Array's element ", ins);
                    JitSpewDef(JitSpew_Escape, "  is escaped by\n", def);
                    return true;
                }
            }

            break;
          }

          default:
            JitSpewDef(JitSpew_Escape, "Array ", ins);
            JitSpewDef(JitSpew_Escape, "  is escaped by\n", def);
            return true;
        }
    }

    JitSpewDef(JitSpew_Escape, "Array is not escaped\n", ins);
    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_;

  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

  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)
{
    // 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);
    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_);
        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_);
    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_);
    int32_t initLengthValue = ins->index()->constantValue().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 */