The Tor Browser: comparison js/src/jit/IonAnalysis.cpp

--1:000000000000
+:09fbdcac6e49
+/* -*- 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/IonAnalysis.h"
+#include "jsanalyze.h"
+#include "jit/BaselineInspector.h"
+#include "jit/BaselineJIT.h"
+#include "jit/Ion.h"
+#include "jit/IonBuilder.h"
+#include "jit/IonOptimizationLevels.h"
+#include "jit/LIR.h"
+#include "jit/Lowering.h"
+#include "jit/MIRGraph.h"
+#include "jsinferinlines.h"
+#include "jsobjinlines.h"
+#include "jsopcodeinlines.h"
+using namespace js;
+using namespace js::jit;
+using mozilla::DebugOnly;
+// A critical edge is an edge which is neither its successor's only predecessor
+// nor its predecessor's only successor. Critical edges must be split to
+// prevent copy-insertion and code motion from affecting other edges.
+bool
+jit::SplitCriticalEdges(MIRGraph &graph)
+{
+for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+if (block->numSuccessors() < 2)
+continue;
+for (size_t i = 0; i < block->numSuccessors(); i++) {
+MBasicBlock *target = block->getSuccessor(i);
+if (target->numPredecessors() < 2)
+continue;
+// Create a new block inheriting from the predecessor.
+MBasicBlock *split = MBasicBlock::NewSplitEdge(graph, block->info(), *block);
+if (!split)
+return false;
+split->setLoopDepth(block->loopDepth());
+graph.insertBlockAfter(*block, split);
+split->end(MGoto::New(graph.alloc(), target));
+block->replaceSuccessor(i, split);
+target->replacePredecessor(*block, split);
+}
+}
+return true;
+}
+// Operands to a resume point which are dead at the point of the resume can be
+// replaced with undefined values. This analysis supports limited detection of
+// dead operands, pruning those which are defined in the resume point's basic
+// block and have no uses outside the block or at points later than the resume
+// point.
+//
+// This is intended to ensure that extra resume points within a basic block
+// will not artificially extend the lifetimes of any SSA values. This could
+// otherwise occur if the new resume point captured a value which is created
+// between the old and new resume point and is dead at the new resume point.
+bool
+jit::EliminateDeadResumePointOperands(MIRGenerator *mir, MIRGraph &graph)
+{
+// If we are compiling try blocks, locals and arguments may be observable
+// from catch or finally blocks (which Ion does not compile). For now just
+// disable the pass in this case.
+if (graph.hasTryBlock())
+return true;
+for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
+if (mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)"))
+return false;
+// The logic below can get confused on infinite loops.
+if (block->isLoopHeader() && block->backedge() == *block)
+continue;
+for (MInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
+// No benefit to replacing constant operands with other constants.
+if (ins->isConstant())
+continue;
+// Scanning uses does not give us sufficient information to tell
+// where instructions that are involved in box/unbox operations or
+// parameter passing might be live. Rewriting uses of these terms
+// in resume points may affect the interpreter's behavior. Rather
+// than doing a more sophisticated analysis, just ignore these.
+if (ins->isUnbox() || ins->isParameter() || ins->isTypeBarrier() || ins->isComputeThis())
+continue;
+// If the instruction's behavior has been constant folded into a
+// separate instruction, we can't determine precisely where the
+// instruction becomes dead and can't eliminate its uses.
+if (ins->isImplicitlyUsed())
+continue;
+// Check if this instruction's result is only used within the
+// current block, and keep track of its last use in a definition
+// (not resume point). This requires the instructions in the block
+// to be numbered, ensured by running this immediately after alias
+// analysis.
+uint32_t maxDefinition = 0;
+for (MUseDefIterator uses(*ins); uses; uses++) {
+if (uses.def()->block() != *block ||
+uses.def()->isBox() ||
+uses.def()->isPhi())
+{
+maxDefinition = UINT32_MAX;
+break;
+}
+maxDefinition = Max(maxDefinition, uses.def()->id());
+}
+if (maxDefinition == UINT32_MAX)
+continue;
+// Walk the uses a second time, removing any in resume points after
+// the last use in a definition.
+for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd(); ) {
+if (uses->consumer()->isDefinition()) {
+uses++;
+continue;
+}
+MResumePoint *mrp = uses->consumer()->toResumePoint();
+if (mrp->block() != *block ||
+!mrp->instruction() ||
+mrp->instruction() == *ins ||
+mrp->instruction()->id() <= maxDefinition)
+{
+uses++;
+continue;
+}
+// The operand is an uneliminable slot. This currently
+// includes argument slots in non-strict scripts (due to being
+// observable via Function.arguments).
+if (!block->info().canOptimizeOutSlot(uses->index())) {
+uses++;
+continue;
+}
+// Store an optimized out magic value in place of all dead
+// resume point operands. Making any such substitution can in
+// general alter the interpreter's behavior, even though the
+// code is dead, as the interpreter will still execute opcodes
+// whose effects cannot be observed. If the undefined value
+// were to flow to, say, a dead property access the
+// interpreter could throw an exception; we avoid this problem
+// by removing dead operands before removing dead code.
+MConstant *constant = MConstant::New(graph.alloc(), MagicValue(JS_OPTIMIZED_OUT));
+block->insertBefore(*(block->begin()), constant);
+uses = mrp->replaceOperand(uses, constant);
+}
+}
+}
+return true;
+}
+// Instructions are useless if they are unused and have no side effects.
+// This pass eliminates useless instructions.
+// The graph itself is unchanged.
+bool
+jit::EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph)
+{
+// Traverse in postorder so that we hit uses before definitions.
+// Traverse instruction list backwards for the same reason.
+for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
+if (mir->shouldCancel("Eliminate Dead Code (main loop)"))
+return false;
+// Remove unused instructions.
+for (MInstructionReverseIterator inst = block->rbegin(); inst != block->rend(); ) {
+if (!inst->isEffectful() && !inst->resumePoint() &&
+!inst->hasUses() && !inst->isGuard() &&
+!inst->isControlInstruction()) {
+inst = block->discardAt(inst);
+} else {
+inst++;
+}
+}
+}
+return true;
+}
+static inline bool
+IsPhiObservable(MPhi *phi, Observability observe)
+{
+// If the phi has uses which are not reflected in SSA, then behavior in the
+// interpreter may be affected by removing the phi.
+if (phi->isImplicitlyUsed())
+return true;
+// Check for uses of this phi node outside of other phi nodes.
+// Note that, initially, we skip reading resume points, which we
+// don't count as actual uses. If the only uses are resume points,
+// then the SSA name is never consumed by the program.  However,
+// after optimizations have been performed, it's possible that the
+// actual uses in the program have been (incorrectly) optimized
+// away, so we must be more conservative and consider resume
+// points as well.
+switch (observe) {
+case AggressiveObservability:
+for (MUseDefIterator iter(phi); iter; iter++) {
+if (!iter.def()->isPhi())
+return true;
+}
+break;
+case ConservativeObservability:
+for (MUseIterator iter(phi->usesBegin()); iter != phi->usesEnd(); iter++) {
+if (!iter->consumer()->isDefinition() ||
+!iter->consumer()->toDefinition()->isPhi())
+return true;
+}
+break;
+}
+uint32_t slot = phi->slot();
+CompileInfo &info = phi->block()->info();
+JSFunction *fun = info.funMaybeLazy();
+// If the Phi is of the |this| value, it must always be observable.
+if (fun && slot == info.thisSlot())
+return true;
+// If the function may need an arguments object, then make sure to
+// preserve the scope chain, because it may be needed to construct the
+// arguments object during bailout. If we've already created an arguments
+// object (or got one via OSR), preserve that as well.
+if (fun && info.hasArguments() &&
+(slot == info.scopeChainSlot() || slot == info.argsObjSlot()))
+{
+return true;
+}
+// The Phi is an uneliminable slot. Currently this includes argument slots
+// in non-strict scripts (due to being observable via Function.arguments).
+if (fun && !info.canOptimizeOutSlot(slot))
+return true;
+return false;
+}
+// Handles cases like:
+//    x is phi(a, x) --> a
+//    x is phi(a, a) --> a
+static inline MDefinition *
+IsPhiRedundant(MPhi *phi)
+{
+MDefinition *first = phi->operandIfRedundant();
+if (first == nullptr)
+return nullptr;
+// Propagate the ImplicitlyUsed flag if |phi| is replaced with another phi.
+if (phi->isImplicitlyUsed())
+first->setImplicitlyUsedUnchecked();
+return first;
+}
+bool
+jit::EliminatePhis(MIRGenerator *mir, MIRGraph &graph,
+Observability observe)
+{
+// Eliminates redundant or unobservable phis from the graph.  A
+// redundant phi is something like b = phi(a, a) or b = phi(a, b),
+// both of which can be replaced with a.  An unobservable phi is
+// one that whose value is never used in the program.
+//
+// Note that we must be careful not to eliminate phis representing
+// values that the interpreter will require later.  When the graph
+// is first constructed, we can be more aggressive, because there
+// is a greater correspondence between the CFG and the bytecode.
+// After optimizations such as GVN have been performed, however,
+// the bytecode and CFG may not correspond as closely to one
+// another.  In that case, we must be more conservative.  The flag
+// |conservativeObservability| is used to indicate that eliminate
+// phis is being run after some optimizations have been performed,
+// and thus we should use more conservative rules about
+// observability.  The particular danger is that we can optimize
+// away uses of a phi because we think they are not executable,
+// but the foundation for that assumption is false TI information
+// that will eventually be invalidated.  Therefore, if
+// |conservativeObservability| is set, we will consider any use
+// from a resume point to be observable.  Otherwise, we demand a
+// use from an actual instruction.
+Vector<MPhi *, 16, SystemAllocPolicy> worklist;
+// Add all observable phis to a worklist. We use the "in worklist" bit to
+// mean "this phi is live".
+for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
+if (mir->shouldCancel("Eliminate Phis (populate loop)"))
+return false;
+MPhiIterator iter = block->phisBegin();
+while (iter != block->phisEnd()) {
+// Flag all as unused, only observable phis would be marked as used
+// when processed by the work list.
+iter->setUnused();
+// If the phi is redundant, remove it here.
+if (MDefinition *redundant = IsPhiRedundant(*iter)) {
+iter->replaceAllUsesWith(redundant);
+iter = block->discardPhiAt(iter);
+continue;
+}
+// Enqueue observable Phis.
+if (IsPhiObservable(*iter, observe)) {
+iter->setInWorklist();
+if (!worklist.append(*iter))
+return false;
+}
+iter++;
+}
+}
+// Iteratively mark all phis reachable from live phis.
+while (!worklist.empty()) {
+if (mir->shouldCancel("Eliminate Phis (worklist)"))
+return false;
+MPhi *phi = worklist.popCopy();
+JS_ASSERT(phi->isUnused());
+phi->setNotInWorklist();
+// The removal of Phis can produce newly redundant phis.
+if (MDefinition *redundant = IsPhiRedundant(phi)) {
+// Add to the worklist the used phis which are impacted.
+for (MUseDefIterator it(phi); it; it++) {
+if (it.def()->isPhi()) {
+MPhi *use = it.def()->toPhi();
+if (!use->isUnused()) {
+use->setUnusedUnchecked();
+use->setInWorklist();
+if (!worklist.append(use))
+return false;
+}
+}
+}
+phi->replaceAllUsesWith(redundant);
+} else {
+// Otherwise flag them as used.
+phi->setNotUnused();
+}
+// The current phi is/was used, so all its operands are used.
+for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
+MDefinition *in = phi->getOperand(i);
+if (!in->isPhi() || !in->isUnused() || in->isInWorklist())
+continue;
+in->setInWorklist();
+if (!worklist.append(in->toPhi()))
+return false;
+}
+}
+// Sweep dead phis.
+for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
+MPhiIterator iter = block->phisBegin();
+while (iter != block->phisEnd()) {
+if (iter->isUnused())
+iter = block->discardPhiAt(iter);
+else
+iter++;
+}
+}
+return true;
+}
+namespace {
+// The type analysis algorithm inserts conversions and box/unbox instructions
+// to make the IR graph well-typed for future passes.
+//
+// Phi adjustment: If a phi's inputs are all the same type, the phi is
+// specialized to return that type.
+//
+// Input adjustment: Each input is asked to apply conversion operations to its
+// inputs. This may include Box, Unbox, or other instruction-specific type
+// conversion operations.
+//
+class TypeAnalyzer
+{
+MIRGenerator *mir;
+MIRGraph &graph;
+Vector<MPhi *, 0, SystemAllocPolicy> phiWorklist_;
+TempAllocator &alloc() const {
+return graph.alloc();
+}
+bool addPhiToWorklist(MPhi *phi) {
+if (phi->isInWorklist())
+return true;
+if (!phiWorklist_.append(phi))
+return false;
+phi->setInWorklist();
+return true;
+}
+MPhi *popPhi() {
+MPhi *phi = phiWorklist_.popCopy();
+phi->setNotInWorklist();
+return phi;
+}
+bool respecialize(MPhi *phi, MIRType type);
+bool propagateSpecialization(MPhi *phi);
+bool specializePhis();
+void replaceRedundantPhi(MPhi *phi);
+void adjustPhiInputs(MPhi *phi);
+bool adjustInputs(MDefinition *def);
+bool insertConversions();
+bool checkFloatCoherency();
+bool graphContainsFloat32();
+bool markPhiConsumers();
+bool markPhiProducers();
+bool specializeValidFloatOps();
+bool tryEmitFloatOperations();
+public:
+TypeAnalyzer(MIRGenerator *mir, MIRGraph &graph)
+: mir(mir), graph(graph)
+{ }
+bool analyze();
+};
+} /* anonymous namespace */
+// Try to specialize this phi based on its non-cyclic inputs.
+static MIRType
+GuessPhiType(MPhi *phi, bool *hasInputsWithEmptyTypes)
+{
+#ifdef DEBUG
+// Check that different magic constants aren't flowing together. Ignore
+// JS_OPTIMIZED_OUT, since an operand could be legitimately optimized
+// away.
+MIRType magicType = MIRType_None;
+for (size_t i = 0; i < phi->numOperands(); i++) {
+MDefinition *in = phi->getOperand(i);
+if (in->type() == MIRType_MagicOptimizedArguments ||
+in->type() == MIRType_MagicHole ||
+in->type() == MIRType_MagicIsConstructing)
+{
+if (magicType == MIRType_None)
+magicType = in->type();
+MOZ_ASSERT(magicType == in->type());
+}
+}
+#endif
+*hasInputsWithEmptyTypes = false;
+MIRType type = MIRType_None;
+bool convertibleToFloat32 = false;
+bool hasPhiInputs = false;
+for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
+MDefinition *in = phi->getOperand(i);
+if (in->isPhi()) {
+hasPhiInputs = true;
+if (!in->toPhi()->triedToSpecialize())
+continue;
+if (in->type() == MIRType_None) {
+// The operand is a phi we tried to specialize, but we were
+// unable to guess its type. propagateSpecialization will
+// propagate the type to this phi when it becomes known.
+continue;
+}
+}
+// Ignore operands which we've never observed.
+if (in->resultTypeSet() && in->resultTypeSet()->empty()) {
+*hasInputsWithEmptyTypes = true;
+continue;
+}
+if (type == MIRType_None) {
+type = in->type();
+if (in->canProduceFloat32())
+convertibleToFloat32 = true;
+continue;
+}
+if (type != in->type()) {
+if (convertibleToFloat32 && in->type() == MIRType_Float32) {
+// If we only saw definitions that can be converted into Float32 before and
+// encounter a Float32 value, promote previous values to Float32
+type = MIRType_Float32;
+} else if (IsNumberType(type) && IsNumberType(in->type())) {
+// Specialize phis with int32 and double operands as double.
+type = MIRType_Double;
+convertibleToFloat32 &= in->canProduceFloat32();
+} else {
+return MIRType_Value;
+}
+}
+}
+if (type == MIRType_None && !hasPhiInputs) {
+// All inputs are non-phis with empty typesets. Use MIRType_Value
+// in this case, as it's impossible to get better type information.
+JS_ASSERT(*hasInputsWithEmptyTypes);
+type = MIRType_Value;
+}
+return type;
+}
+bool
+TypeAnalyzer::respecialize(MPhi *phi, MIRType type)
+{
+if (phi->type() == type)
+return true;
+phi->specialize(type);
+return addPhiToWorklist(phi);
+}
+bool
+TypeAnalyzer::propagateSpecialization(MPhi *phi)
+{
+JS_ASSERT(phi->type() != MIRType_None);
+// Verify that this specialization matches any phis depending on it.
+for (MUseDefIterator iter(phi); iter; iter++) {
+if (!iter.def()->isPhi())
+continue;
+MPhi *use = iter.def()->toPhi();
+if (!use->triedToSpecialize())
+continue;
+if (use->type() == MIRType_None) {
+// We tried to specialize this phi, but were unable to guess its
+// type. Now that we know the type of one of its operands, we can
+// specialize it.
+if (!respecialize(use, phi->type()))
+return false;
+continue;
+}
+if (use->type() != phi->type()) {
+// Specialize phis with int32 that can be converted to float and float operands as floats.
+if ((use->type() == MIRType_Int32 && use->canProduceFloat32() && phi->type() == MIRType_Float32) ||
+(phi->type() == MIRType_Int32 && phi->canProduceFloat32() && use->type() == MIRType_Float32))
+{
+if (!respecialize(use, MIRType_Float32))
+return false;
+continue;
+}
+// Specialize phis with int32 and double operands as double.
+if (IsNumberType(use->type()) && IsNumberType(phi->type())) {
+if (!respecialize(use, MIRType_Double))
+return false;
+continue;
+}
+// This phi in our use chain can now no longer be specialized.
+if (!respecialize(use, MIRType_Value))
+return false;
+}
+}
+return true;
+}
+bool
+TypeAnalyzer::specializePhis()
+{
+Vector<MPhi *, 0, SystemAllocPolicy> phisWithEmptyInputTypes;
+for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); block++) {
+if (mir->shouldCancel("Specialize Phis (main loop)"))
+return false;
+for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
+bool hasInputsWithEmptyTypes;
+MIRType type = GuessPhiType(*phi, &hasInputsWithEmptyTypes);
+phi->specialize(type);
+if (type == MIRType_None) {
+// We tried to guess the type but failed because all operands are
+// phis we still have to visit. Set the triedToSpecialize flag but
+// don't propagate the type to other phis, propagateSpecialization
+// will do that once we know the type of one of the operands.
+// Edge case: when this phi has a non-phi input with an empty
+// typeset, it's possible for two phis to have a cyclic
+// dependency and they will both have MIRType_None. Specialize
+// such phis to MIRType_Value later on.
+if (hasInputsWithEmptyTypes && !phisWithEmptyInputTypes.append(*phi))
+return false;
+continue;
+}
+if (!propagateSpecialization(*phi))
+return false;
+}
+}
+do {
+while (!phiWorklist_.empty()) {
+if (mir->shouldCancel("Specialize Phis (worklist)"))
+return false;
+MPhi *phi = popPhi();
+if (!propagateSpecialization(phi))
+return false;
+}
+// When two phis have a cyclic dependency and inputs that have an empty
+// typeset (which are ignored by GuessPhiType), we may still have to
+// specialize these to MIRType_Value.
+while (!phisWithEmptyInputTypes.empty()) {
+if (mir->shouldCancel("Specialize Phis (phisWithEmptyInputTypes)"))
+return false;
+MPhi *phi = phisWithEmptyInputTypes.popCopy();
+if (phi->type() == MIRType_None) {
+phi->specialize(MIRType_Value);
+if (!propagateSpecialization(phi))
+return false;
+}
+}
+} while (!phiWorklist_.empty());
+return true;
+}
+void
+TypeAnalyzer::adjustPhiInputs(MPhi *phi)
+{
+MIRType phiType = phi->type();
+JS_ASSERT(phiType != MIRType_None);
+// If we specialized a type that's not Value, there are 3 cases:
+// 1. Every input is of that type.
+// 2. Every observed input is of that type (i.e., some inputs haven't been executed yet).
+// 3. Inputs were doubles and int32s, and was specialized to double.
+if (phiType != MIRType_Value) {
+for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
+MDefinition *in = phi->getOperand(i);
+if (in->type() == phiType)
+continue;
+if (in->isBox() && in->toBox()->input()->type() == phiType) {
+phi->replaceOperand(i, in->toBox()->input());
+} else {
+MInstruction *replacement;
+if (phiType == MIRType_Double && IsFloatType(in->type())) {
+// Convert int32 operands to double.
+replacement = MToDouble::New(alloc(), in);
+} else if (phiType == MIRType_Float32) {
+if (in->type() == MIRType_Int32 || in->type() == MIRType_Double) {
+replacement = MToFloat32::New(alloc(), in);
+} else {
+// See comment below
+if (in->type() != MIRType_Value) {
+MBox *box = MBox::New(alloc(), in);
+in->block()->insertBefore(in->block()->lastIns(), box);
+in = box;
+}
+MUnbox *unbox = MUnbox::New(alloc(), in, MIRType_Double, MUnbox::Fallible);
+in->block()->insertBefore(in->block()->lastIns(), unbox);
+replacement = MToFloat32::New(alloc(), in);
+}
+} else {
+// If we know this branch will fail to convert to phiType,
+// insert a box that'll immediately fail in the fallible unbox
+// below.
+if (in->type() != MIRType_Value) {
+MBox *box = MBox::New(alloc(), in);
+in->block()->insertBefore(in->block()->lastIns(), box);
+in = box;
+}
+// Be optimistic and insert unboxes when the operand is a
+// value.
+replacement = MUnbox::New(alloc(), in, phiType, MUnbox::Fallible);
+}
+in->block()->insertBefore(in->block()->lastIns(), replacement);
+phi->replaceOperand(i, replacement);
+}
+}
+return;
+}
+// Box every typed input.
+for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
+MDefinition *in = phi->getOperand(i);
+if (in->type() == MIRType_Value)
+continue;
+if (in->isUnbox() && phi->typeIncludes(in->toUnbox()->input())) {
+// The input is being explicitly unboxed, so sneak past and grab
+// the original box.
+phi->replaceOperand(i, in->toUnbox()->input());
+} else {
+MDefinition *box = BoxInputsPolicy::alwaysBoxAt(alloc(), in->block()->lastIns(), in);
+phi->replaceOperand(i, box);
+}
+}
+}
+bool
+TypeAnalyzer::adjustInputs(MDefinition *def)
+{
+TypePolicy *policy = def->typePolicy();
+if (policy && !policy->adjustInputs(alloc(), def->toInstruction()))
+return false;
+return true;
+}
+void
+TypeAnalyzer::replaceRedundantPhi(MPhi *phi)
+{
+MBasicBlock *block = phi->block();
+js::Value v;
+switch (phi->type()) {
+case MIRType_Undefined:
+v = UndefinedValue();
+break;
+case MIRType_Null:
+v = NullValue();
+break;
+case MIRType_MagicOptimizedArguments:
+v = MagicValue(JS_OPTIMIZED_ARGUMENTS);
+break;
+case MIRType_MagicOptimizedOut:
+v = MagicValue(JS_OPTIMIZED_OUT);
+break;
+default:
+MOZ_ASSUME_UNREACHABLE("unexpected type");
+}
+MConstant *c = MConstant::New(alloc(), v);
+// The instruction pass will insert the box
+block->insertBefore(*(block->begin()), c);
+phi->replaceAllUsesWith(c);
+}
+bool
+TypeAnalyzer::insertConversions()
+{
+// Instructions are processed in reverse postorder: all uses are defs are
+// seen before uses. This ensures that output adjustment (which may rewrite
+// inputs of uses) does not conflict with input adjustment.
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
+if (mir->shouldCancel("Insert Conversions"))
+return false;
+for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd();) {
+if (phi->type() == MIRType_Undefined ||
+phi->type() == MIRType_Null ||
+phi->type() == MIRType_MagicOptimizedArguments ||
+phi->type() == MIRType_MagicOptimizedOut)
+{
+replaceRedundantPhi(*phi);
+phi = block->discardPhiAt(phi);
+} else {
+adjustPhiInputs(*phi);
+phi++;
+}
+}
+for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
+if (!adjustInputs(*iter))
+return false;
+}
+}
+return true;
+}
+// This function tries to emit Float32 specialized operations whenever it's possible.
+// MIR nodes are flagged as:
+// - Producers, when they can create Float32 that might need to be coerced into a Double.
+//   Loads in Float32 arrays and conversions to Float32 are producers.
+// - Consumers, when they can have Float32 as inputs and validate a legal use of a Float32.
+//   Stores in Float32 arrays and conversions to Float32 are consumers.
+// - Float32 commutative, when using the Float32 instruction instead of the Double instruction
+//   does not result in a compound loss of precision. This is the case for +, -, /, * with 2
+//   operands, for instance. However, an addition with 3 operands is not commutative anymore,
+//   so an intermediate coercion is needed.
+// Except for phis, all these flags are known after Ion building, so they cannot change during
+// the process.
+//
+// The idea behind the algorithm is easy: whenever we can prove that a commutative operation
+// has only producers as inputs and consumers as uses, we can specialize the operation as a
+// float32 operation. Otherwise, we have to convert all float32 inputs to doubles. Even
+// if a lot of conversions are produced, GVN will take care of eliminating the redundant ones.
+//
+// Phis have a special status. Phis need to be flagged as producers or consumers as they can
+// be inputs or outputs of commutative instructions. Fortunately, producers and consumers
+// properties are such that we can deduce the property using all non phis inputs first (which form
+// an initial phi graph) and then propagate all properties from one phi to another using a
+// fixed point algorithm. The algorithm is ensured to terminate as each iteration has less or as
+// many flagged phis as the previous iteration (so the worst steady state case is all phis being
+// flagged as false).
+//
+// In a nutshell, the algorithm applies three passes:
+// 1 - Determine which phis are consumers. Each phi gets an initial value by making a global AND on
+// all its non-phi inputs. Then each phi propagates its value to other phis. If after propagation,
+// the flag value changed, we have to reapply the algorithm on all phi operands, as a phi is a
+// consumer if all of its uses are consumers.
+// 2 - Determine which phis are producers. It's the same algorithm, except that we have to reapply
+// the algorithm on all phi uses, as a phi is a producer if all of its operands are producers.
+// 3 - Go through all commutative operations and ensure their inputs are all producers and their
+// uses are all consumers.
+bool
+TypeAnalyzer::markPhiConsumers()
+{
+JS_ASSERT(phiWorklist_.empty());
+// Iterate in postorder so worklist is initialized to RPO.
+for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); ++block) {
+if (mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Initial state"))
+return false;
+for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) {
+JS_ASSERT(!phi->isInWorklist());
+bool canConsumeFloat32 = true;
+for (MUseDefIterator use(*phi); canConsumeFloat32 && use; use++) {
+MDefinition *usedef = use.def();
+canConsumeFloat32 &= usedef->isPhi() || usedef->canConsumeFloat32(use.use());
+}
+phi->setCanConsumeFloat32(canConsumeFloat32);
+if (canConsumeFloat32 && !addPhiToWorklist(*phi))
+return false;
+}
+}
+while (!phiWorklist_.empty()) {
+if (mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Fixed point"))
+return false;
+MPhi *phi = popPhi();
+JS_ASSERT(phi->canConsumeFloat32(nullptr /* unused */));
+bool validConsumer = true;
+for (MUseDefIterator use(phi); use; use++) {
+MDefinition *def = use.def();
+if (def->isPhi() && !def->canConsumeFloat32(use.use())) {
+validConsumer = false;
+break;
+}
+}
+if (validConsumer)
+continue;
+// Propagate invalidated phis
+phi->setCanConsumeFloat32(false);
+for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
+MDefinition *input = phi->getOperand(i);
+if (input->isPhi() && !input->isInWorklist() && input->canConsumeFloat32(nullptr /* unused */))
+{
+if (!addPhiToWorklist(input->toPhi()))
+return false;
+}
+}
+}
+return true;
+}
+bool
+TypeAnalyzer::markPhiProducers()
+{
+JS_ASSERT(phiWorklist_.empty());
+// Iterate in reverse postorder so worklist is initialized to PO.
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
+if (mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - initial state"))
+return false;
+for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) {
+JS_ASSERT(!phi->isInWorklist());
+bool canProduceFloat32 = true;
+for (size_t i = 0, e = phi->numOperands(); canProduceFloat32 && i < e; ++i) {
+MDefinition *input = phi->getOperand(i);
+canProduceFloat32 &= input->isPhi() || input->canProduceFloat32();
+}
+phi->setCanProduceFloat32(canProduceFloat32);
+if (canProduceFloat32 && !addPhiToWorklist(*phi))
+return false;
+}
+}
+while (!phiWorklist_.empty()) {
+if (mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - Fixed point"))
+return false;
+MPhi *phi = popPhi();
+JS_ASSERT(phi->canProduceFloat32());
+bool validProducer = true;
+for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
+MDefinition *input = phi->getOperand(i);
+if (input->isPhi() && !input->canProduceFloat32()) {
+validProducer = false;
+break;
+}
+}
+if (validProducer)
+continue;
+// Propagate invalidated phis
+phi->setCanProduceFloat32(false);
+for (MUseDefIterator use(phi); use; use++) {
+MDefinition *def = use.def();
+if (def->isPhi() && !def->isInWorklist() && def->canProduceFloat32())
+{
+if (!addPhiToWorklist(def->toPhi()))
+return false;
+}
+}
+}
+return true;
+}
+bool
+TypeAnalyzer::specializeValidFloatOps()
+{
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
+if (mir->shouldCancel("Ensure Float32 commutativity - Instructions"))
+return false;
+for (MInstructionIterator ins(block->begin()); ins != block->end(); ++ins) {
+if (!ins->isFloat32Commutative())
+continue;
+if (ins->type() == MIRType_Float32)
+continue;
+// This call will try to specialize the instruction iff all uses are consumers and
+// all inputs are producers.
+ins->trySpecializeFloat32(alloc());
+}
+}
+return true;
+}
+bool
+TypeAnalyzer::graphContainsFloat32()
+{
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
+if (mir->shouldCancel("Ensure Float32 commutativity - Graph contains Float32"))
+return false;
+for (MDefinitionIterator def(*block); def; def++) {
+if (def->type() == MIRType_Float32)
+return true;
+}
+}
+return false;
+}
+bool
+TypeAnalyzer::tryEmitFloatOperations()
+{
+// Backends that currently don't know how to generate Float32 specialized instructions
+// shouldn't run this pass and just let all instructions as specialized for Double.
+if (!LIRGenerator::allowFloat32Optimizations())
+return true;
+// Asm.js uses the ahead of time type checks to specialize operations, no need to check
+// them again at this point.
+if (mir->compilingAsmJS())
+return true;
+// Check ahead of time that there is at least one definition typed as Float32, otherwise we
+// don't need this pass.
+if (!graphContainsFloat32())
+return true;
+if (!markPhiConsumers())
+return false;
+if (!markPhiProducers())
+return false;
+if (!specializeValidFloatOps())
+return false;
+return true;
+}
+bool
+TypeAnalyzer::checkFloatCoherency()
+{
+#ifdef DEBUG
+// Asserts that all Float32 instructions are flowing into Float32 consumers or specialized
+// operations
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
+if (mir->shouldCancel("Check Float32 coherency"))
+return false;
+for (MDefinitionIterator def(*block); def; def++) {
+if (def->type() != MIRType_Float32)
+continue;
+for (MUseDefIterator use(*def); use; use++) {
+MDefinition *consumer = use.def();
+JS_ASSERT(consumer->isConsistentFloat32Use(use.use()));
+}
+}
+}
+#endif
+return true;
+}
+bool
+TypeAnalyzer::analyze()
+{
+if (!tryEmitFloatOperations())
+return false;
+if (!specializePhis())
+return false;
+if (!insertConversions())
+return false;
+if (!checkFloatCoherency())
+return false;
+return true;
+}
+bool
+jit::ApplyTypeInformation(MIRGenerator *mir, MIRGraph &graph)
+{
+TypeAnalyzer analyzer(mir, graph);
+if (!analyzer.analyze())
+return false;
+return true;
+}
+bool
+jit::MakeMRegExpHoistable(MIRGraph &graph)
+{
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
+for (MDefinitionIterator iter(*block); iter; iter++) {
+if (!iter->isRegExp())
+continue;
+MRegExp *regexp = iter->toRegExp();
+// Test if MRegExp is hoistable by looking at all uses.
+bool hoistable = true;
+for (MUseIterator i = regexp->usesBegin(); i != regexp->usesEnd(); i++) {
+// Ignore resume points. At this point all uses are listed.
+// No DCE or GVN or something has happened.
+if (i->consumer()->isResumePoint())
+continue;
+JS_ASSERT(i->consumer()->isDefinition());
+// All MRegExp* MIR's don't adjust the regexp.
+MDefinition *use = i->consumer()->toDefinition();
+if (use->isRegExpReplace())
+continue;
+if (use->isRegExpExec())
+continue;
+if (use->isRegExpTest())
+continue;
+hoistable = false;
+break;
+}
+if (!hoistable)
+continue;
+// Make MRegExp hoistable
+regexp->setMovable();
+// That would be incorrect for global/sticky, because lastIndex could be wrong.
+// Therefore setting the lastIndex to 0. That is faster than a not movable regexp.
+RegExpObject *source = regexp->source();
+if (source->sticky() || source->global()) {
+JS_ASSERT(regexp->mustClone());
+MConstant *zero = MConstant::New(graph.alloc(), Int32Value(0));
+regexp->block()->insertAfter(regexp, zero);
+MStoreFixedSlot *lastIndex =
+MStoreFixedSlot::New(graph.alloc(), regexp, RegExpObject::lastIndexSlot(), zero);
+regexp->block()->insertAfter(zero, lastIndex);
+}
+}
+}
+return true;
+}
+bool
+jit::RenumberBlocks(MIRGraph &graph)
+{
+size_t id = 0;
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++)
+block->setId(id++);
+return true;
+}
+// A Simple, Fast Dominance Algorithm by Cooper et al.
+// Modified to support empty intersections for OSR, and in RPO.
+static MBasicBlock *
+IntersectDominators(MBasicBlock *block1, MBasicBlock *block2)
+{
+MBasicBlock *finger1 = block1;
+MBasicBlock *finger2 = block2;
+JS_ASSERT(finger1);
+JS_ASSERT(finger2);
+// In the original paper, the block ID comparisons are on the postorder index.
+// This implementation iterates in RPO, so the comparisons are reversed.
+// For this function to be called, the block must have multiple predecessors.
+// If a finger is then found to be self-dominating, it must therefore be
+// reachable from multiple roots through non-intersecting control flow.
+// nullptr is returned in this case, to denote an empty intersection.
+while (finger1->id() != finger2->id()) {
+while (finger1->id() > finger2->id()) {
+MBasicBlock *idom = finger1->immediateDominator();
+if (idom == finger1)
+return nullptr; // Empty intersection.
+finger1 = idom;
+}
+while (finger2->id() > finger1->id()) {
+MBasicBlock *idom = finger2->immediateDominator();
+if (idom == finger2)
+return nullptr; // Empty intersection.
+finger2 = idom;
+}
+}
+return finger1;
+}
+static void
+ComputeImmediateDominators(MIRGraph &graph)
+{
+// The default start block is a root and therefore only self-dominates.
+MBasicBlock *startBlock = *graph.begin();
+startBlock->setImmediateDominator(startBlock);
+// Any OSR block is a root and therefore only self-dominates.
+MBasicBlock *osrBlock = graph.osrBlock();
+if (osrBlock)
+osrBlock->setImmediateDominator(osrBlock);
+bool changed = true;
+while (changed) {
+changed = false;
+ReversePostorderIterator block = graph.rpoBegin();
+// For each block in RPO, intersect all dominators.
+for (; block != graph.rpoEnd(); block++) {
+// If a node has once been found to have no exclusive dominator,
+// it will never have an exclusive dominator, so it may be skipped.
+if (block->immediateDominator() == *block)
+continue;
+MBasicBlock *newIdom = block->getPredecessor(0);
+// Find the first common dominator.
+for (size_t i = 1; i < block->numPredecessors(); i++) {
+MBasicBlock *pred = block->getPredecessor(i);
+if (pred->immediateDominator() == nullptr)
+continue;
+newIdom = IntersectDominators(pred, newIdom);
+// If there is no common dominator, the block self-dominates.
+if (newIdom == nullptr) {
+block->setImmediateDominator(*block);
+changed = true;
+break;
+}
+}
+if (newIdom && block->immediateDominator() != newIdom) {
+block->setImmediateDominator(newIdom);
+changed = true;
+}
+}
+}
+#ifdef DEBUG
+// Assert that all blocks have dominator information.
+for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+JS_ASSERT(block->immediateDominator() != nullptr);
+}
+#endif
+}
+bool
+jit::BuildDominatorTree(MIRGraph &graph)
+{
+ComputeImmediateDominators(graph);
+// Traversing through the graph in post-order means that every use
+// of a definition is visited before the def itself. Since a def
+// dominates its uses, by the time we reach a particular
+// block, we have processed all of its dominated children, so
+// block->numDominated() is accurate.
+for (PostorderIterator i(graph.poBegin()); i != graph.poEnd(); i++) {
+MBasicBlock *child = *i;
+MBasicBlock *parent = child->immediateDominator();
+// If the block only self-dominates, it has no definite parent.
+if (child == parent)
+continue;
+if (!parent->addImmediatelyDominatedBlock(child))
+return false;
+// An additional +1 for the child block.
+parent->addNumDominated(child->numDominated() + 1);
+}
+#ifdef DEBUG
+// If compiling with OSR, many blocks will self-dominate.
+// Without OSR, there is only one root block which dominates all.
+if (!graph.osrBlock())
+JS_ASSERT(graph.begin()->numDominated() == graph.numBlocks() - 1);
+#endif
+// Now, iterate through the dominator tree and annotate every
+// block with its index in the pre-order traversal of the
+// dominator tree.
+Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(graph.alloc());
+// The index of the current block in the CFG traversal.
+size_t index = 0;
+// Add all self-dominating blocks to the worklist.
+// This includes all roots. Order does not matter.
+for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
+MBasicBlock *block = *i;
+if (block->immediateDominator() == block) {
+if (!worklist.append(block))
+return false;
+}
+}
+// Starting from each self-dominating block, traverse the CFG in pre-order.
+while (!worklist.empty()) {
+MBasicBlock *block = worklist.popCopy();
+block->setDomIndex(index);
+if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
+block->immediatelyDominatedBlocksEnd())) {
+return false;
+}
+index++;
+}
+return true;
+}
+bool
+jit::BuildPhiReverseMapping(MIRGraph &graph)
+{
+// Build a mapping such that given a basic block, whose successor has one or
+// more phis, we can find our specific input to that phi. To make this fast
+// mapping work we rely on a specific property of our structured control
+// flow graph: For a block with phis, its predecessors each have only one
+// successor with phis. Consider each case:
+//   * Blocks with less than two predecessors cannot have phis.
+//   * Breaks. A break always has exactly one successor, and the break
+//             catch block has exactly one predecessor for each break, as
+//             well as a final predecessor for the actual loop exit.
+//   * Continues. A continue always has exactly one successor, and the
+//             continue catch block has exactly one predecessor for each
+//             continue, as well as a final predecessor for the actual
+//             loop continuation. The continue itself has exactly one
+//             successor.
+//   * An if. Each branch as exactly one predecessor.
+//   * A switch. Each branch has exactly one predecessor.
+//   * Loop tail. A new block is always created for the exit, and if a
+//             break statement is present, the exit block will forward
+//             directly to the break block.
+for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+if (block->numPredecessors() < 2) {
+JS_ASSERT(block->phisEmpty());
+continue;
+}
+// Assert on the above.
+for (size_t j = 0; j < block->numPredecessors(); j++) {
+MBasicBlock *pred = block->getPredecessor(j);
+#ifdef DEBUG
+size_t numSuccessorsWithPhis = 0;
+for (size_t k = 0; k < pred->numSuccessors(); k++) {
+MBasicBlock *successor = pred->getSuccessor(k);
+if (!successor->phisEmpty())
+numSuccessorsWithPhis++;
+}
+JS_ASSERT(numSuccessorsWithPhis <= 1);
+#endif
+pred->setSuccessorWithPhis(*block, j);
+}
+}
+return true;
+}
+#ifdef DEBUG
+static bool
+CheckSuccessorImpliesPredecessor(MBasicBlock *A, MBasicBlock *B)
+{
+// Assuming B = succ(A), verify A = pred(B).
+for (size_t i = 0; i < B->numPredecessors(); i++) {
+if (A == B->getPredecessor(i))
+return true;
+}
+return false;
+}
+static bool
+CheckPredecessorImpliesSuccessor(MBasicBlock *A, MBasicBlock *B)
+{
+// Assuming B = pred(A), verify A = succ(B).
+for (size_t i = 0; i < B->numSuccessors(); i++) {
+if (A == B->getSuccessor(i))
+return true;
+}
+return false;
+}
+static bool
+CheckOperandImpliesUse(MNode *n, MDefinition *operand)
+{
+for (MUseIterator i = operand->usesBegin(); i != operand->usesEnd(); i++) {
+if (i->consumer() == n)
+return true;
+}
+return false;
+}
+static bool
+CheckUseImpliesOperand(MDefinition *def, MUse *use)
+{
+return use->consumer()->getOperand(use->index()) == def;
+}
+#endif // DEBUG
+void
+jit::AssertBasicGraphCoherency(MIRGraph &graph)
+{
+#ifdef DEBUG
+JS_ASSERT(graph.entryBlock()->numPredecessors() == 0);
+JS_ASSERT(graph.entryBlock()->phisEmpty());
+JS_ASSERT(!graph.entryBlock()->unreachable());
+if (MBasicBlock *osrBlock = graph.osrBlock()) {
+JS_ASSERT(osrBlock->numPredecessors() == 0);
+JS_ASSERT(osrBlock->phisEmpty());
+JS_ASSERT(osrBlock != graph.entryBlock());
+JS_ASSERT(!osrBlock->unreachable());
+}
+if (MResumePoint *resumePoint = graph.entryResumePoint())
+JS_ASSERT(resumePoint->block() == graph.entryBlock());
+// Assert successor and predecessor list coherency.
+uint32_t count = 0;
+for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+count++;
+JS_ASSERT(&block->graph() == &graph);
+for (size_t i = 0; i < block->numSuccessors(); i++)
+JS_ASSERT(CheckSuccessorImpliesPredecessor(*block, block->getSuccessor(i)));
+for (size_t i = 0; i < block->numPredecessors(); i++)
+JS_ASSERT(CheckPredecessorImpliesSuccessor(*block, block->getPredecessor(i)));
+// Assert that use chains are valid for this instruction.
+for (MDefinitionIterator iter(*block); iter; iter++) {
+for (uint32_t i = 0, e = iter->numOperands(); i < e; i++)
+JS_ASSERT(CheckOperandImpliesUse(*iter, iter->getOperand(i)));
+}
+for (MResumePointIterator iter(block->resumePointsBegin()); iter != block->resumePointsEnd(); iter++) {
+for (uint32_t i = 0, e = iter->numOperands(); i < e; i++) {
+if (iter->getUseFor(i)->hasProducer())
+JS_ASSERT(CheckOperandImpliesUse(*iter, iter->getOperand(i)));
+}
+}
+for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
+JS_ASSERT(phi->numOperands() == block->numPredecessors());
+}
+for (MDefinitionIterator iter(*block); iter; iter++) {
+JS_ASSERT(iter->block() == *block);
+for (MUseIterator i(iter->usesBegin()); i != iter->usesEnd(); i++)
+JS_ASSERT(CheckUseImpliesOperand(*iter, *i));
+if (iter->isInstruction()) {
+if (MResumePoint *resume = iter->toInstruction()->resumePoint()) {
+if (MInstruction *ins = resume->instruction())
+JS_ASSERT(ins->block() == iter->block());
+}
+}
+}
+}
+JS_ASSERT(graph.numBlocks() == count);
+#endif
+}
+#ifdef DEBUG
+static void
+AssertReversePostOrder(MIRGraph &graph)
+{
+// Check that every block is visited after all its predecessors (except backedges).
+for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
+JS_ASSERT(!block->isMarked());
+for (size_t i = 0; i < block->numPredecessors(); i++) {
+MBasicBlock *pred = block->getPredecessor(i);
+JS_ASSERT_IF(!pred->isLoopBackedge(), pred->isMarked());
+}
+block->mark();
+}
+graph.unmarkBlocks();
+}
+#endif
+void
+jit::AssertGraphCoherency(MIRGraph &graph)
+{
+#ifdef DEBUG
+if (!js_JitOptions.checkGraphConsistency)
+return;
+AssertBasicGraphCoherency(graph);
+AssertReversePostOrder(graph);
+#endif
+}
+void
+jit::AssertExtendedGraphCoherency(MIRGraph &graph)
+{
+// Checks the basic GraphCoherency but also other conditions that
+// do not hold immediately (such as the fact that critical edges
+// are split)
+#ifdef DEBUG
+if (!js_JitOptions.checkGraphConsistency)
+return;
+AssertGraphCoherency(graph);
+uint32_t idx = 0;
+for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+JS_ASSERT(block->id() == idx++);
+// No critical edges:
+if (block->numSuccessors() > 1)
+for (size_t i = 0; i < block->numSuccessors(); i++)
+JS_ASSERT(block->getSuccessor(i)->numPredecessors() == 1);
+if (block->isLoopHeader()) {
+JS_ASSERT(block->numPredecessors() == 2);
+MBasicBlock *backedge = block->getPredecessor(1);
+JS_ASSERT(backedge->id() >= block->id());
+JS_ASSERT(backedge->numSuccessors() == 1);
+JS_ASSERT(backedge->getSuccessor(0) == *block);
+}
+if (!block->phisEmpty()) {
+for (size_t i = 0; i < block->numPredecessors(); i++) {
+MBasicBlock *pred = block->getPredecessor(i);
+JS_ASSERT(pred->successorWithPhis() == *block);
+JS_ASSERT(pred->positionInPhiSuccessor() == i);
+}
+}
+uint32_t successorWithPhis = 0;
+for (size_t i = 0; i < block->numSuccessors(); i++)
+if (!block->getSuccessor(i)->phisEmpty())
+successorWithPhis++;
+JS_ASSERT(successorWithPhis <= 1);
+JS_ASSERT_IF(successorWithPhis, block->successorWithPhis() != nullptr);
+// I'd like to assert this, but it's not necc. true.  Sometimes we set this
+// flag to non-nullptr just because a successor has multiple preds, even if it
+// does not actually have any phis.
+//
+// JS_ASSERT_IF(!successorWithPhis, block->successorWithPhis() == nullptr);
+}
+#endif
+}
+struct BoundsCheckInfo
+{
+MBoundsCheck *check;
+uint32_t validUntil;
+};
+typedef HashMap<uint32_t,
+BoundsCheckInfo,
+DefaultHasher<uint32_t>,
+IonAllocPolicy> BoundsCheckMap;
+// Compute a hash for bounds checks which ignores constant offsets in the index.
+static HashNumber
+BoundsCheckHashIgnoreOffset(MBoundsCheck *check)
+{
+SimpleLinearSum indexSum = ExtractLinearSum(check->index());
+uintptr_t index = indexSum.term ? uintptr_t(indexSum.term) : 0;
+uintptr_t length = uintptr_t(check->length());
+return index ^ length;
+}
+static MBoundsCheck *
+FindDominatingBoundsCheck(BoundsCheckMap &checks, MBoundsCheck *check, size_t index)
+{
+// See the comment in ValueNumberer::findDominatingDef.
+HashNumber hash = BoundsCheckHashIgnoreOffset(check);
+BoundsCheckMap::Ptr p = checks.lookup(hash);
+if (!p || index > p->value().validUntil) {
+// We didn't find a dominating bounds check.
+BoundsCheckInfo info;
+info.check = check;
+info.validUntil = index + check->block()->numDominated();
+if(!checks.put(hash, info))
+return nullptr;
+return check;
+}
+return p->value().check;
+}
+// Extract a linear sum from ins, if possible (otherwise giving the sum 'ins + 0').
+SimpleLinearSum
+jit::ExtractLinearSum(MDefinition *ins)
+{
+if (ins->isBeta())
+ins = ins->getOperand(0);
+if (ins->type() != MIRType_Int32)
+return SimpleLinearSum(ins, 0);
+if (ins->isConstant()) {
+const Value &v = ins->toConstant()->value();
+JS_ASSERT(v.isInt32());
+return SimpleLinearSum(nullptr, v.toInt32());
+} else if (ins->isAdd() || ins->isSub()) {
+MDefinition *lhs = ins->getOperand(0);
+MDefinition *rhs = ins->getOperand(1);
+if (lhs->type() == MIRType_Int32 && rhs->type() == MIRType_Int32) {
+SimpleLinearSum lsum = ExtractLinearSum(lhs);
+SimpleLinearSum rsum = ExtractLinearSum(rhs);
+if (lsum.term && rsum.term)
+return SimpleLinearSum(ins, 0);
+// Check if this is of the form <SUM> + n, n + <SUM> or <SUM> - n.
+if (ins->isAdd()) {
+int32_t constant;
+if (!SafeAdd(lsum.constant, rsum.constant, &constant))
+return SimpleLinearSum(ins, 0);
+return SimpleLinearSum(lsum.term ? lsum.term : rsum.term, constant);
+} else if (lsum.term) {
+int32_t constant;
+if (!SafeSub(lsum.constant, rsum.constant, &constant))
+return SimpleLinearSum(ins, 0);
+return SimpleLinearSum(lsum.term, constant);
+}
+}
+}
+return SimpleLinearSum(ins, 0);
+}
+// Extract a linear inequality holding when a boolean test goes in the
+// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).
+bool
+jit::ExtractLinearInequality(MTest *test, BranchDirection direction,
+SimpleLinearSum *plhs, MDefinition **prhs, bool *plessEqual)
+{
+if (!test->getOperand(0)->isCompare())
+return false;
+MCompare *compare = test->getOperand(0)->toCompare();
+MDefinition *lhs = compare->getOperand(0);
+MDefinition *rhs = compare->getOperand(1);
+// TODO: optimize Compare_UInt32
+if (!compare->isInt32Comparison())
+return false;
+JS_ASSERT(lhs->type() == MIRType_Int32);
+JS_ASSERT(rhs->type() == MIRType_Int32);
+JSOp jsop = compare->jsop();
+if (direction == FALSE_BRANCH)
+jsop = NegateCompareOp(jsop);
+SimpleLinearSum lsum = ExtractLinearSum(lhs);
+SimpleLinearSum rsum = ExtractLinearSum(rhs);
+if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant))
+return false;
+// Normalize operations to use <= or >=.
+switch (jsop) {
+case JSOP_LE:
+*plessEqual = true;
+break;
+case JSOP_LT:
+/* x < y ==> x + 1 <= y */
+if (!SafeAdd(lsum.constant, 1, &lsum.constant))
+return false;
+*plessEqual = true;
+break;
+case JSOP_GE:
+*plessEqual = false;
+break;
+case JSOP_GT:
+/* x > y ==> x - 1 >= y */
+if (!SafeSub(lsum.constant, 1, &lsum.constant))
+return false;
+*plessEqual = false;
+break;
+default:
+return false;
+}
+*plhs = lsum;
+*prhs = rsum.term;
+return true;
+}
+static bool
+TryEliminateBoundsCheck(BoundsCheckMap &checks, size_t blockIndex, MBoundsCheck *dominated, bool *eliminated)
+{
+JS_ASSERT(!*eliminated);
+// Replace all uses of the bounds check with the actual index.
+// This is (a) necessary, because we can coalesce two different
+// bounds checks and would otherwise use the wrong index and
+// (b) helps register allocation. Note that this is safe since
+// no other pass after bounds check elimination moves instructions.
+dominated->replaceAllUsesWith(dominated->index());
+if (!dominated->isMovable())
+return true;
+MBoundsCheck *dominating = FindDominatingBoundsCheck(checks, dominated, blockIndex);
+if (!dominating)
+return false;
+if (dominating == dominated) {
+// We didn't find a dominating bounds check.
+return true;
+}
+// We found two bounds checks with the same hash number, but we still have
+// to make sure the lengths and index terms are equal.
+if (dominating->length() != dominated->length())
+return true;
+SimpleLinearSum sumA = ExtractLinearSum(dominating->index());
+SimpleLinearSum sumB = ExtractLinearSum(dominated->index());
+// Both terms should be nullptr or the same definition.
+if (sumA.term != sumB.term)
+return true;
+// This bounds check is redundant.
+*eliminated = true;
+// Normalize the ranges according to the constant offsets in the two indexes.
+int32_t minimumA, maximumA, minimumB, maximumB;
+if (!SafeAdd(sumA.constant, dominating->minimum(), &minimumA) ||
+!SafeAdd(sumA.constant, dominating->maximum(), &maximumA) ||
+!SafeAdd(sumB.constant, dominated->minimum(), &minimumB) ||
+!SafeAdd(sumB.constant, dominated->maximum(), &maximumB))
+{
+return false;
+}
+// Update the dominating check to cover both ranges, denormalizing the
+// result per the constant offset in the index.
+int32_t newMinimum, newMaximum;
+if (!SafeSub(Min(minimumA, minimumB), sumA.constant, &newMinimum) ||
+!SafeSub(Max(maximumA, maximumB), sumA.constant, &newMaximum))
+{
+return false;
+}
+dominating->setMinimum(newMinimum);
+dominating->setMaximum(newMaximum);
+return true;
+}
+static void
+TryEliminateTypeBarrierFromTest(MTypeBarrier *barrier, bool filtersNull, bool filtersUndefined,
+MTest *test, BranchDirection direction, bool *eliminated)
+{
+JS_ASSERT(filtersNull || filtersUndefined);
+// Watch for code patterns similar to 'if (x.f) { ... = x.f }'.  If x.f
+// is either an object or null/undefined, there will be a type barrier on
+// the latter read as the null/undefined value is never realized there.
+// The type barrier can be eliminated, however, by looking at tests
+// performed on the result of the first operation that filter out all
+// types that have been seen in the first access but not the second.
+// A test 'if (x.f)' filters both null and undefined.
+// Disregard the possible unbox added before the Typebarrier for checking.
+MDefinition *input = barrier->input();
+MUnbox *inputUnbox = nullptr;
+if (input->isUnbox() && input->toUnbox()->mode() != MUnbox::Fallible) {
+inputUnbox = input->toUnbox();
+input = inputUnbox->input();
+}
+MDefinition *subject = nullptr;
+bool removeUndefined;
+bool removeNull;
+test->filtersUndefinedOrNull(direction == TRUE_BRANCH, &subject, &removeUndefined, &removeNull);
+// The Test doesn't filter undefined nor null.
+if (!subject)
+return;
+// Make sure the subject equals the input to the TypeBarrier.
+if (subject != input)
+return;
+// When the TypeBarrier filters undefined, the test must at least also do,
+// this, before the TypeBarrier can get removed.
+if (!removeUndefined && filtersUndefined)
+return;
+// When the TypeBarrier filters null, the test must at least also do,
+// this, before the TypeBarrier can get removed.
+if (!removeNull && filtersNull)
+return;
+// Eliminate the TypeBarrier. The possible TypeBarrier unboxing is kept,
+// but made infallible.
+*eliminated = true;
+if (inputUnbox)
+inputUnbox->makeInfallible();
+barrier->replaceAllUsesWith(barrier->input());
+}
+static bool
+TryEliminateTypeBarrier(MTypeBarrier *barrier, bool *eliminated)
+{
+JS_ASSERT(!*eliminated);
+const types::TemporaryTypeSet *barrierTypes = barrier->resultTypeSet();
+const types::TemporaryTypeSet *inputTypes = barrier->input()->resultTypeSet();
+// Disregard the possible unbox added before the Typebarrier.
+if (barrier->input()->isUnbox() && barrier->input()->toUnbox()->mode() != MUnbox::Fallible)
+inputTypes = barrier->input()->toUnbox()->input()->resultTypeSet();
+if (!barrierTypes || !inputTypes)
+return true;
+bool filtersNull = barrierTypes->filtersType(inputTypes, types::Type::NullType());
+bool filtersUndefined = barrierTypes->filtersType(inputTypes, types::Type::UndefinedType());
+if (!filtersNull && !filtersUndefined)
+return true;
+MBasicBlock *block = barrier->block();
+while (true) {
+BranchDirection direction;
+MTest *test = block->immediateDominatorBranch(&direction);
+if (test) {
+TryEliminateTypeBarrierFromTest(barrier, filtersNull, filtersUndefined,
+test, direction, eliminated);
+}
+MBasicBlock *previous = block->immediateDominator();
+if (previous == block)
+break;
+block = previous;
+}
+return true;
+}
+// Eliminate checks which are redundant given each other or other instructions.
+//
+// A type barrier is considered redundant if all missing types have been tested
+// for by earlier control instructions.
+//
+// A bounds check is considered redundant if it's dominated by another bounds
+// check with the same length and the indexes differ by only a constant amount.
+// In this case we eliminate the redundant bounds check and update the other one
+// to cover the ranges of both checks.
+//
+// Bounds checks are added to a hash map and since the hash function ignores
+// differences in constant offset, this offers a fast way to find redundant
+// checks.
+bool
+jit::EliminateRedundantChecks(MIRGraph &graph)
+{
+BoundsCheckMap checks(graph.alloc());
+if (!checks.init())
+return false;
+// Stack for pre-order CFG traversal.
+Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(graph.alloc());
+// The index of the current block in the CFG traversal.
+size_t index = 0;
+// Add all self-dominating blocks to the worklist.
+// This includes all roots. Order does not matter.
+for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
+MBasicBlock *block = *i;
+if (block->immediateDominator() == block) {
+if (!worklist.append(block))
+return false;
+}
+}
+// Starting from each self-dominating block, traverse the CFG in pre-order.
+while (!worklist.empty()) {
+MBasicBlock *block = worklist.popCopy();
+// Add all immediate dominators to the front of the worklist.
+if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
+block->immediatelyDominatedBlocksEnd())) {
+return false;
+}
+for (MDefinitionIterator iter(block); iter; ) {
+bool eliminated = false;
+if (iter->isBoundsCheck()) {
+if (!TryEliminateBoundsCheck(checks, index, iter->toBoundsCheck(), &eliminated))
+return false;
+} else if (iter->isTypeBarrier()) {
+if (!TryEliminateTypeBarrier(iter->toTypeBarrier(), &eliminated))
+return false;
+} else if (iter->isConvertElementsToDoubles()) {
+// Now that code motion passes have finished, replace any
+// ConvertElementsToDoubles with the actual elements.
+MConvertElementsToDoubles *ins = iter->toConvertElementsToDoubles();
+ins->replaceAllUsesWith(ins->elements());
+}
+if (eliminated)
+iter = block->discardDefAt(iter);
+else
+iter++;
+}
+index++;
+}
+JS_ASSERT(index == graph.numBlocks());
+return true;
+}
+// If the given block contains a goto and nothing interesting before that,
+// return the goto. Return nullptr otherwise.
+static LGoto *
+FindLeadingGoto(LBlock *bb)
+{
+for (LInstructionIterator ins(bb->begin()); ins != bb->end(); ins++) {
+// Ignore labels.
+if (ins->isLabel())
+continue;
+// If we have a goto, we're good to go.
+if (ins->isGoto())
+return ins->toGoto();
+break;
+}
+return nullptr;
+}
+// Eliminate blocks containing nothing interesting besides gotos. These are
+// often created by optimizer, which splits all critical edges. If these
+// splits end up being unused after optimization and register allocation,
+// fold them back away to avoid unnecessary branching.
+bool
+jit::UnsplitEdges(LIRGraph *lir)
+{
+for (size_t i = 0; i < lir->numBlocks(); i++) {
+LBlock *bb = lir->getBlock(i);
+MBasicBlock *mirBlock = bb->mir();
+// Renumber the MIR blocks as we go, since we may remove some.
+mirBlock->setId(i);
+// Register allocation is done by this point, so we don't need the phis
+// anymore. Clear them to avoid needed to keep them current as we edit
+// the CFG.
+bb->clearPhis();
+mirBlock->discardAllPhis();
+// First make sure the MIR block looks sane. Some of these checks may be
+// over-conservative, but we're attempting to keep everything in MIR
+// current as we modify the LIR, so only proceed if the MIR is simple.
+if (mirBlock->numPredecessors() == 0 || mirBlock->numSuccessors() != 1 ||
+!mirBlock->begin()->isGoto())
+{
+continue;
+}
+// The MIR block is empty, but check the LIR block too (in case the
+// register allocator inserted spill code there, or whatever).
+LGoto *theGoto = FindLeadingGoto(bb);
+if (!theGoto)
+continue;
+MBasicBlock *target = theGoto->target();
+if (target == mirBlock || target != mirBlock->getSuccessor(0))
+continue;
+// If we haven't yet cleared the phis for the successor, do so now so
+// that the CFG manipulation routines don't trip over them.
+if (!target->phisEmpty()) {
+target->discardAllPhis();
+target->lir()->clearPhis();
+}
+// Edit the CFG to remove lir/mirBlock and reconnect all its edges.
+for (size_t j = 0; j < mirBlock->numPredecessors(); j++) {
+MBasicBlock *mirPred = mirBlock->getPredecessor(j);
+for (size_t k = 0; k < mirPred->numSuccessors(); k++) {
+if (mirPred->getSuccessor(k) == mirBlock) {
+mirPred->replaceSuccessor(k, target);
+if (!target->addPredecessorWithoutPhis(mirPred))
+return false;
+}
+}
+LInstruction *predTerm = *mirPred->lir()->rbegin();
+for (size_t k = 0; k < predTerm->numSuccessors(); k++) {
+if (predTerm->getSuccessor(k) == mirBlock)
+predTerm->setSuccessor(k, target);
+}
+}
+target->removePredecessor(mirBlock);
+// Zap the block.
+lir->removeBlock(i);
+lir->mir().removeBlock(mirBlock);
+--i;
+}
+return true;
+}
+bool
+LinearSum::multiply(int32_t scale)
+{
+for (size_t i = 0; i < terms_.length(); i++) {
+if (!SafeMul(scale, terms_[i].scale, &terms_[i].scale))
+return false;
+}
+return SafeMul(scale, constant_, &constant_);
+}
+bool
+LinearSum::add(const LinearSum &other)
+{
+for (size_t i = 0; i < other.terms_.length(); i++) {
+if (!add(other.terms_[i].term, other.terms_[i].scale))
+return false;
+}
+return add(other.constant_);
+}
+bool
+LinearSum::add(MDefinition *term, int32_t scale)
+{
+JS_ASSERT(term);
+if (scale == 0)
+return true;
+if (term->isConstant()) {
+int32_t constant = term->toConstant()->value().toInt32();
+if (!SafeMul(constant, scale, &constant))
+return false;
+return add(constant);
+}
+for (size_t i = 0; i < terms_.length(); i++) {
+if (term == terms_[i].term) {
+if (!SafeAdd(scale, terms_[i].scale, &terms_[i].scale))
+return false;
+if (terms_[i].scale == 0) {
+terms_[i] = terms_.back();
+terms_.popBack();
+}
+return true;
+}
+}
+terms_.append(LinearTerm(term, scale));
+return true;
+}
+bool
+LinearSum::add(int32_t constant)
+{
+return SafeAdd(constant, constant_, &constant_);
+}
+void
+LinearSum::print(Sprinter &sp) const
+{
+for (size_t i = 0; i < terms_.length(); i++) {
+int32_t scale = terms_[i].scale;
+int32_t id = terms_[i].term->id();
+JS_ASSERT(scale);
+if (scale > 0) {
+if (i)
+sp.printf("+");
+if (scale == 1)
+sp.printf("#%d", id);
+else
+sp.printf("%d*#%d", scale, id);
+} else if (scale == -1) {
+sp.printf("-#%d", id);
+} else {
+sp.printf("%d*#%d", scale, id);
+}
+}
+if (constant_ > 0)
+sp.printf("+%d", constant_);
+else if (constant_ < 0)
+sp.printf("%d", constant_);
+}
+void
+LinearSum::dump(FILE *fp) const
+{
+Sprinter sp(GetIonContext()->cx);
+sp.init();
+print(sp);
+fprintf(fp, "%s\n", sp.string());
+}
+void
+LinearSum::dump() const
+{
+dump(stderr);
+}
+static bool
+AnalyzePoppedThis(JSContext *cx, types::TypeObject *type,
+MDefinition *thisValue, MInstruction *ins, bool definitelyExecuted,
+HandleObject baseobj,
+Vector<types::TypeNewScript::Initializer> *initializerList,
+Vector<PropertyName *> *accessedProperties,
+bool *phandled)
+{
+// Determine the effect that a use of the |this| value when calling |new|
+// on a script has on the properties definitely held by the new object.
+if (ins->isCallSetProperty()) {
+MCallSetProperty *setprop = ins->toCallSetProperty();
+if (setprop->object() != thisValue)
+return true;
+// Don't use GetAtomId here, we need to watch for SETPROP on
+// integer properties and bail out. We can't mark the aggregate
+// JSID_VOID type property as being in a definite slot.
+if (setprop->name() == cx->names().prototype ||
+setprop->name() == cx->names().proto ||
+setprop->name() == cx->names().constructor)
+{
+return true;
+}
+// Ignore assignments to properties that were already written to.
+if (baseobj->nativeLookup(cx, NameToId(setprop->name()))) {
+*phandled = true;
+return true;
+}
+// Don't add definite properties for properties that were already
+// read in the constructor.
+for (size_t i = 0; i < accessedProperties->length(); i++) {
+if ((*accessedProperties)[i] == setprop->name())
+return true;
+}
+// Don't add definite properties to an object which won't fit in its
+// fixed slots.
+if (GetGCKindSlots(gc::GetGCObjectKind(baseobj->slotSpan() + 1)) <= baseobj->slotSpan())
+return true;
+// Assignments to new properties must always execute.
+if (!definitelyExecuted)
+return true;
+RootedId id(cx, NameToId(setprop->name()));
+if (!types::AddClearDefiniteGetterSetterForPrototypeChain(cx, type, id)) {
+// The prototype chain already contains a getter/setter for this
+// property, or type information is too imprecise.
+return true;
+}
+DebugOnly<unsigned> slotSpan = baseobj->slotSpan();
+if (!DefineNativeProperty(cx, baseobj, id, UndefinedHandleValue, nullptr, nullptr,
+JSPROP_ENUMERATE))
+{
+return false;
+}
+JS_ASSERT(baseobj->slotSpan() != slotSpan);
+JS_ASSERT(!baseobj->inDictionaryMode());
+Vector<MResumePoint *> callerResumePoints(cx);
+MBasicBlock *block = ins->block();
+for (MResumePoint *rp = block->callerResumePoint();
+rp;
+block = rp->block(), rp = block->callerResumePoint())
+{
+JSScript *script = rp->block()->info().script();
+if (!types::AddClearDefiniteFunctionUsesInScript(cx, type, script, block->info().script()))
+return true;
+if (!callerResumePoints.append(rp))
+return false;
+}
+for (int i = callerResumePoints.length() - 1; i >= 0; i--) {
+MResumePoint *rp = callerResumePoints[i];
+JSScript *script = rp->block()->info().script();
+types::TypeNewScript::Initializer entry(types::TypeNewScript::Initializer::SETPROP_FRAME,
+script->pcToOffset(rp->pc()));
+if (!initializerList->append(entry))
+return false;
+}
+JSScript *script = ins->block()->info().script();
+types::TypeNewScript::Initializer entry(types::TypeNewScript::Initializer::SETPROP,
+script->pcToOffset(setprop->resumePoint()->pc()));
+if (!initializerList->append(entry))
+return false;
+*phandled = true;
+return true;
+}
+if (ins->isCallGetProperty()) {
+MCallGetProperty *get = ins->toCallGetProperty();
+/*
+* Properties can be read from the 'this' object if the following hold:
+*
+* - The read is not on a getter along the prototype chain, which
+*   could cause 'this' to escape.
+*
+* - The accessed property is either already a definite property or
+*   is not later added as one. Since the definite properties are
+*   added to the object at the point of its creation, reading a
+*   definite property before it is assigned could incorrectly hit.
+*/
+RootedId id(cx, NameToId(get->name()));
+if (!baseobj->nativeLookup(cx, id) && !accessedProperties->append(get->name()))
+return false;
+if (!types::AddClearDefiniteGetterSetterForPrototypeChain(cx, type, id)) {
+// The |this| value can escape if any property reads it does go
+// through a getter.
+return true;
+}
+*phandled = true;
+return true;
+}
+if (ins->isPostWriteBarrier()) {
+*phandled = true;
+return true;
+}
+return true;
+}
+static int
+CmpInstructions(const void *a, const void *b)
+{
+return (*static_cast<MInstruction * const *>(a))->id() -
+(*static_cast<MInstruction * const *>(b))->id();
+}
+bool
+jit::AnalyzeNewScriptProperties(JSContext *cx, JSFunction *fun,
+types::TypeObject *type, HandleObject baseobj,
+Vector<types::TypeNewScript::Initializer> *initializerList)
+{
+JS_ASSERT(cx->compartment()->activeAnalysis);
+// When invoking 'new' on the specified script, try to find some properties
+// which will definitely be added to the created object before it has a
+// chance to escape and be accessed elsewhere.
+RootedScript script(cx, fun->getOrCreateScript(cx));
+if (!script)
+return false;
+if (!jit::IsIonEnabled(cx) || !jit::IsBaselineEnabled(cx) ||
+!script->compileAndGo() || !script->canBaselineCompile())
+{
+return true;
+}
+static const uint32_t MAX_SCRIPT_SIZE = 2000;
+if (script->length() > MAX_SCRIPT_SIZE)
+return true;
+Vector<PropertyName *> accessedProperties(cx);
+LifoAlloc alloc(types::TypeZone::TYPE_LIFO_ALLOC_PRIMARY_CHUNK_SIZE);
+TempAllocator temp(&alloc);
+IonContext ictx(cx, &temp);
+if (!cx->compartment()->ensureJitCompartmentExists(cx))
+return false;
+if (!script->hasBaselineScript()) {
+MethodStatus status = BaselineCompile(cx, script);
+if (status == Method_Error)
+return false;
+if (status != Method_Compiled)
+return true;
+}
+types::TypeScript::SetThis(cx, script, types::Type::ObjectType(type));
+MIRGraph graph(&temp);
+CompileInfo info(script, fun,
+/* osrPc = */ nullptr, /* constructing = */ false,
+DefinitePropertiesAnalysis,
+script->needsArgsObj());
+AutoTempAllocatorRooter root(cx, &temp);
+const OptimizationInfo *optimizationInfo = js_IonOptimizations.get(Optimization_Normal);
+types::CompilerConstraintList *constraints = types::NewCompilerConstraintList(temp);
+if (!constraints) {
+js_ReportOutOfMemory(cx);
+return false;
+}
+BaselineInspector inspector(script);
+const JitCompileOptions options(cx);
+IonBuilder builder(cx, CompileCompartment::get(cx->compartment()), options, &temp, &graph, constraints,
+&inspector, &info, optimizationInfo, /* baselineFrame = */ nullptr);
+if (!builder.build()) {
+if (builder.abortReason() == AbortReason_Alloc)
+return false;
+return true;
+}
+types::FinishDefinitePropertiesAnalysis(cx, constraints);
+if (!SplitCriticalEdges(graph))
+return false;
+if (!RenumberBlocks(graph))
+return false;
+if (!BuildDominatorTree(graph))
+return false;
+if (!EliminatePhis(&builder, graph, AggressiveObservability))
+return false;
+MDefinition *thisValue = graph.begin()->getSlot(info.thisSlot());
+// Get a list of instructions using the |this| value in the order they
+// appear in the graph.
+Vector<MInstruction *> instructions(cx);
+for (MUseDefIterator uses(thisValue); uses; uses++) {
+MDefinition *use = uses.def();
+// Don't track |this| through assignments to phis.
+if (!use->isInstruction())
+return true;
+if (!instructions.append(use->toInstruction()))
+return false;
+}
+// Sort the instructions to visit in increasing order.
+qsort(instructions.begin(), instructions.length(),
+sizeof(MInstruction *), CmpInstructions);
+// Find all exit blocks in the graph.
+Vector<MBasicBlock *> exitBlocks(cx);
+for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+if (!block->numSuccessors() && !exitBlocks.append(*block))
+return false;
+}
+for (size_t i = 0; i < instructions.length(); i++) {
+MInstruction *ins = instructions[i];
+// Track whether the use of |this| is in unconditional code, i.e.
+// the block dominates all graph exits.
+bool definitelyExecuted = true;
+for (size_t i = 0; i < exitBlocks.length(); i++) {
+for (MBasicBlock *exit = exitBlocks[i];
+exit != ins->block();
+exit = exit->immediateDominator())
+{
+if (exit == exit->immediateDominator()) {
+definitelyExecuted = false;
+break;
+}
+}
+}
+// Also check to see if the instruction is inside a loop body. Even if
+// an access will always execute in the script, if it executes multiple
+// times then we can get confused when rolling back objects while
+// clearing the new script information.
+if (ins->block()->loopDepth() != 0)
+definitelyExecuted = false;
+bool handled = false;
+if (!AnalyzePoppedThis(cx, type, thisValue, ins, definitelyExecuted,
+baseobj, initializerList, &accessedProperties, &handled))
+{
+return false;
+}
+if (!handled)
+return true;
+}
+return true;
+}
+static bool
+ArgumentsUseCanBeLazy(JSContext *cx, JSScript *script, MInstruction *ins, size_t index)
+{
+// We can read the frame's arguments directly for f.apply(x, arguments).
+if (ins->isCall()) {
+if (*ins->toCall()->resumePoint()->pc() == JSOP_FUNAPPLY &&
+ins->toCall()->numActualArgs() == 2 &&
+index == MCall::IndexOfArgument(1))
+{
+return true;
+}
+}
+// arguments[i] can read fp->canonicalActualArg(i) directly.
+if (ins->isCallGetElement() && index == 0)
+return true;
+// arguments.length length can read fp->numActualArgs() directly.
+if (ins->isCallGetProperty() && index == 0 && ins->toCallGetProperty()->name() == cx->names().length)
+return true;
+return false;
+}
+bool
+jit::AnalyzeArgumentsUsage(JSContext *cx, JSScript *scriptArg)
+{
+RootedScript script(cx, scriptArg);
+types::AutoEnterAnalysis enter(cx);
+JS_ASSERT(!script->analyzedArgsUsage());
+// Treat the script as needing an arguments object until we determine it
+// does not need one. This both allows us to easily see where the arguments
+// object can escape through assignments to the function's named arguments,
+// and also simplifies handling of early returns.
+script->setNeedsArgsObj(true);
+if (!jit::IsIonEnabled(cx) || !script->compileAndGo())
+return true;
+static const uint32_t MAX_SCRIPT_SIZE = 10000;
+if (script->length() > MAX_SCRIPT_SIZE)
+return true;
+if (!script->ensureHasTypes(cx))
+return false;
+LifoAlloc alloc(types::TypeZone::TYPE_LIFO_ALLOC_PRIMARY_CHUNK_SIZE);
+TempAllocator temp(&alloc);
+IonContext ictx(cx, &temp);
+if (!cx->compartment()->ensureJitCompartmentExists(cx))
+return false;
+MIRGraph graph(&temp);
+CompileInfo info(script, script->functionNonDelazifying(),
+/* osrPc = */ nullptr, /* constructing = */ false,
+ArgumentsUsageAnalysis,
+/* needsArgsObj = */ true);
+AutoTempAllocatorRooter root(cx, &temp);
+const OptimizationInfo *optimizationInfo = js_IonOptimizations.get(Optimization_Normal);
+types::CompilerConstraintList *constraints = types::NewCompilerConstraintList(temp);
+if (!constraints)
+return false;
+BaselineInspector inspector(script);
+const JitCompileOptions options(cx);
+IonBuilder builder(nullptr, CompileCompartment::get(cx->compartment()), options, &temp, &graph, constraints,
+&inspector, &info, optimizationInfo, /* baselineFrame = */ nullptr);
+if (!builder.build()) {
+if (builder.abortReason() == AbortReason_Alloc)
+return false;
+return true;
+}
+if (!SplitCriticalEdges(graph))
+return false;
+if (!RenumberBlocks(graph))
+return false;
+if (!BuildDominatorTree(graph))
+return false;
+if (!EliminatePhis(&builder, graph, AggressiveObservability))
+return false;
+MDefinition *argumentsValue = graph.begin()->getSlot(info.argsObjSlot());
+for (MUseDefIterator uses(argumentsValue); uses; uses++) {
+MDefinition *use = uses.def();
+// Don't track |arguments| through assignments to phis.
+if (!use->isInstruction())
+return true;
+if (!ArgumentsUseCanBeLazy(cx, script, use->toInstruction(), uses.index()))
+return true;
+}
+script->setNeedsArgsObj(false);
+return true;
+}

The Tor Browser / file comparison

comparison: js/src/jit/IonAnalysis.cpp

js/src/jit/IonAnalysis.cpp