/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- * vim: set ts=8 sts=2 et sw=2 tw=80: * 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/TypeAnalysis.h" #include "jit/MIRGenerator.h" #include "jit/MIRGraph.h" #include "vm/BytecodeUtil-inl.h" using namespace js; using namespace js::jit; using mozilla::DebugOnly; 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 { const MIRGenerator* mir; MIRGraph& graph; Vector 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; } [[nodiscard]] bool propagateAllPhiSpecializations(); bool respecialize(MPhi* phi, MIRType type); bool propagateSpecialization(MPhi* phi); bool specializePhis(); bool specializeOsrOnlyPhis(); void replaceRedundantPhi(MPhi* phi); bool adjustPhiInputs(MPhi* phi); bool adjustInputs(MDefinition* def); bool insertConversions(); bool checkFloatCoherency(); bool graphContainsFloat32(); bool markPhiConsumers(); bool markPhiProducers(); bool specializeValidFloatOps(); bool tryEmitFloatOperations(); bool propagateUnbox(); bool shouldSpecializeOsrPhis() const; MIRType guessPhiType(MPhi* phi) const; public: TypeAnalyzer(const MIRGenerator* mir, MIRGraph& graph) : mir(mir), graph(graph) {} bool analyze(); }; } /* anonymous namespace */ bool TypeAnalyzer::shouldSpecializeOsrPhis() const { // [SMDOC] OSR Phi Type Specialization // // Without special handling for OSR phis, we end up with unspecialized phis // (MIRType::Value) in the loop (pre)header and other blocks, resulting in // unnecessary boxing and unboxing in the loop body. // // To fix this, phi type specialization needs special code to deal with the // OSR entry block. Recall that OSR results in the following basic block // structure: // // +------------------+ +-----------------+ // | Code before loop | | OSR entry block | // +------------------+ +-----------------+ // | | // | | // | +---------------+ | // +---------> | OSR preheader | <---------+ // +---------------+ // | // V // +---------------+ // | Loop header |<-----+ // +---------------+ | // | | // ... | // | | // +---------------+ | // | Loop backedge |------+ // +---------------+ // // OSR phi specialization happens in three steps: // // (1) Specialize phis but ignore MOsrValue phi inputs. In other words, // pretend the OSR entry block doesn't exist. See guessPhiType. // // (2) Once phi specialization is done, look at the types of loop header phis // and add these types to the corresponding preheader phis. This way, the // types of the preheader phis are based on the code before the loop and // the code in the loop body. These are exactly the types we expect for // the OSR Values. See the last part of TypeAnalyzer::specializePhis. // // (3) For type-specialized preheader phis, add guard/unbox instructions to // the OSR entry block to guard the incoming Value indeed has this type. // This happens in: // // * TypeAnalyzer::adjustPhiInputs: adds a fallible unbox for values that // can be unboxed. // // * TypeAnalyzer::replaceRedundantPhi: adds a type guard for values that // can't be unboxed (null/undefined/magic Values). if (!graph.osrBlock()) { return false; } return !mir->outerInfo().hadSpeculativePhiBailout(); } // Try to specialize this phi based on its non-cyclic inputs. MIRType TypeAnalyzer::guessPhiType(MPhi* phi) const { #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::MagicHole || in->type() == MIRType::MagicIsConstructing) { if (magicType == MIRType::None) { magicType = in->type(); } MOZ_ASSERT(magicType == in->type()); } } #endif MIRType type = MIRType::None; bool convertibleToFloat32 = false; bool hasOSRValueInput = false; DebugOnly hasSpecializableInput = false; for (size_t i = 0, e = phi->numOperands(); i < e; i++) { MDefinition* in = phi->getOperand(i); if (in->isPhi()) { hasSpecializableInput = 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; } } // See shouldSpecializeOsrPhis comment. This is the first step mentioned // there. if (shouldSpecializeOsrPhis() && in->isOsrValue()) { hasOSRValueInput = true; hasSpecializableInput = true; continue; } if (type == MIRType::None) { type = in->type(); if (in->canProduceFloat32() && !mir->outerInfo().hadSpeculativePhiBailout()) { convertibleToFloat32 = true; } continue; } if (type == in->type()) { convertibleToFloat32 = convertibleToFloat32 && in->canProduceFloat32(); } else { 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 (IsTypeRepresentableAsDouble(type) && IsTypeRepresentableAsDouble(in->type())) { // Specialize phis with int32 and double operands as double. type = MIRType::Double; convertibleToFloat32 = convertibleToFloat32 && in->canProduceFloat32(); } else { return MIRType::Value; } } } if (hasOSRValueInput && type == MIRType::Float32) { // TODO(post-Warp): simplify float32 handling in this function or (better) // make the float32 analysis a stand-alone optimization pass instead of // complicating type analysis. See bug 1655773. type = MIRType::Double; } MOZ_ASSERT_IF(type == MIRType::None, hasSpecializableInput); 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) { MOZ_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 it can't be specialized as float32, specialize // as double. MIRType type = phi->type(); if (type == MIRType::Float32 && !use->canProduceFloat32()) { type = MIRType::Double; } if (!respecialize(use, 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 (IsTypeRepresentableAsDouble(use->type()) && IsTypeRepresentableAsDouble(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::propagateAllPhiSpecializations() { while (!phiWorklist_.empty()) { if (mir->shouldCancel("Specialize Phis (worklist)")) { return false; } MPhi* phi = popPhi(); if (!propagateSpecialization(phi)) { return false; } } return true; } // If branch pruning removes the path from the entry block to the OSR // preheader, we may have phis (or chains of phis) with no operands // other than OsrValues. These phis will still have MIRType::None. // Since we don't have any information about them, we specialize them // as MIRType::Value. bool TypeAnalyzer::specializeOsrOnlyPhis() { MOZ_ASSERT(graph.osrBlock()); MOZ_ASSERT(graph.osrPreHeaderBlock()->numPredecessors() == 1); for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); block++) { if (mir->shouldCancel("Specialize osr-only phis (main loop)")) { return false; } for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) { if (mir->shouldCancel("Specialize osr-only phis (inner loop)")) { return false; } if (phi->type() == MIRType::None) { phi->specialize(MIRType::Value); } } } return true; } bool TypeAnalyzer::specializePhis() { 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++) { if (mir->shouldCancel("Specialize Phis (inner loop)")) { return false; } MIRType type = guessPhiType(*phi); 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. continue; } if (!propagateSpecialization(*phi)) { return false; } } } if (!propagateAllPhiSpecializations()) { return false; } if (shouldSpecializeOsrPhis()) { // See shouldSpecializeOsrPhis comment. This is the second step, propagating // loop header phi types to preheader phis. MBasicBlock* preHeader = graph.osrPreHeaderBlock(); MBasicBlock* header = preHeader->getSingleSuccessor(); if (preHeader->numPredecessors() == 1) { MOZ_ASSERT(preHeader->getPredecessor(0) == graph.osrBlock()); // Branch pruning has removed the path from the entry block // to the preheader. Specialize any phis with no non-osr inputs. if (!specializeOsrOnlyPhis()) { return false; } } else if (header->isLoopHeader()) { for (MPhiIterator phi(header->phisBegin()); phi != header->phisEnd(); phi++) { MPhi* preHeaderPhi = phi->getOperand(0)->toPhi(); MOZ_ASSERT(preHeaderPhi->block() == preHeader); if (preHeaderPhi->type() == MIRType::Value) { // Already includes everything. continue; } MIRType loopType = phi->type(); if (!respecialize(preHeaderPhi, loopType)) { return false; } } if (!propagateAllPhiSpecializations()) { return false; } } else { // Edge case: there is no backedge in this loop. This can happen // if the header is a 'pending' loop header when control flow in // the loop body is terminated unconditionally, or if a block // that dominates the backedge unconditionally bails out. In // this case the header only has the preheader as predecessor // and we don't need to do anything. MOZ_ASSERT(header->numPredecessors() == 1); } } MOZ_ASSERT(phiWorklist_.empty()); return true; } bool TypeAnalyzer::adjustPhiInputs(MPhi* phi) { MIRType phiType = phi->type(); MOZ_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 numbers, and was specialized to floating point type. 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()); continue; } if (!alloc().ensureBallast()) { return false; } MBasicBlock* predecessor = phi->block()->getPredecessor(i); MInstruction* replacement; if (IsFloatingPointType(phiType) && IsTypeRepresentableAsDouble(in->type())) { // Convert number operands to |phiType|. if (phiType == MIRType::Double) { replacement = MToDouble::New(alloc(), in); } else { MOZ_ASSERT(phiType == MIRType::Float32); 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) { auto* box = MBox::New(alloc(), in); predecessor->insertAtEnd(box); in = box; } // Be optimistic and insert unboxes when the operand is a value. if (phiType == MIRType::Float32) { // Float32 is unboxed as Double, then converted. auto* unbox = MUnbox::New(alloc(), in, MIRType::Double, MUnbox::Fallible); unbox->setBailoutKind(BailoutKind::SpeculativePhi); predecessor->insertAtEnd(unbox); replacement = MToFloat32::New(alloc(), unbox); } else { replacement = MUnbox::New(alloc(), in, phiType, MUnbox::Fallible); replacement->setBailoutKind(BailoutKind::SpeculativePhi); } } MOZ_ASSERT(replacement->type() == phiType); predecessor->insertAtEnd(replacement); phi->replaceOperand(i, replacement); } return true; } // 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; } // The input is being explicitly unboxed, so sneak past and grab the // original box. Don't bother optimizing if magic values are involved. if (in->isUnbox()) { MDefinition* unboxInput = in->toUnbox()->input(); if (!IsMagicType(unboxInput->type()) && phi->typeIncludes(unboxInput)) { in = in->toUnbox()->input(); } } if (in->type() != MIRType::Value) { if (!alloc().ensureBallast()) { return false; } MBasicBlock* pred = phi->block()->getPredecessor(i); in = BoxAt(alloc(), pred->lastIns(), in); } phi->replaceOperand(i, in); } return true; } bool TypeAnalyzer::adjustInputs(MDefinition* def) { // Definitions such as MPhi have no type policy. if (!def->isInstruction()) { return true; } MInstruction* ins = def->toInstruction(); const TypePolicy* policy = ins->typePolicy(); if (policy && !policy->adjustInputs(alloc(), ins)) { 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::MagicOptimizedOut: v = MagicValue(JS_OPTIMIZED_OUT); break; case MIRType::MagicUninitializedLexical: v = MagicValue(JS_UNINITIALIZED_LEXICAL); break; case MIRType::MagicIsConstructing: v = MagicValue(JS_IS_CONSTRUCTING); break; case MIRType::MagicHole: default: MOZ_CRASH("unexpected type"); } MConstant* c = MConstant::New(alloc(), v); // The instruction pass will insert the box block->insertBefore(*(block->begin()), c); phi->justReplaceAllUsesWith(c); if (shouldSpecializeOsrPhis()) { // See shouldSpecializeOsrPhis comment. This is part of the third step, // guard the incoming MOsrValue is of this type. for (uint32_t i = 0; i < phi->numOperands(); i++) { MDefinition* def = phi->getOperand(i); if (def->type() != phi->type()) { MOZ_ASSERT(def->isOsrValue() || def->isPhi()); MOZ_ASSERT(def->type() == MIRType::Value); MGuardValue* guard = MGuardValue::New(alloc(), def, v); guard->setBailoutKind(BailoutKind::SpeculativePhi); def->block()->insertBefore(def->block()->lastIns(), guard); } } } } 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 iter(block->phisBegin()), end(block->phisEnd()); iter != end;) { MPhi* phi = *iter++; if (IsNullOrUndefined(phi->type()) || IsMagicType(phi->type())) { // We can replace this phi with a constant. if (!alloc().ensureBallast()) { return false; } replaceRedundantPhi(phi); block->discardPhi(phi); } else { if (!adjustPhiInputs(phi)) { return false; } } } // AdjustInputs can add/remove/mutate instructions before and after the // current instruction. Only increment the iterator after it is finished. for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) { if (!alloc().ensureBallast()) { return false; } if (!adjustInputs(*iter)) { return false; } } } return true; } /* clang-format off */ // // 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. // /* clang-format on */ bool TypeAnalyzer::markPhiConsumers() { MOZ_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) { MOZ_ASSERT(!phi->isInWorklist()); bool canConsumeFloat32 = !phi->isImplicitlyUsed(); 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(); MOZ_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() { MOZ_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) { MOZ_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(); MOZ_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; } if (!alloc().ensureBallast()) { return false; } // 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) { for (MDefinitionIterator def(*block); def; def++) { if (mir->shouldCancel( "Ensure Float32 commutativity - Graph contains Float32")) { return false; } if (def->type() == MIRType::Float32) { return true; } } } return false; } bool TypeAnalyzer::tryEmitFloatOperations() { // Asm.js uses the ahead of time type checks to specialize operations, no need // to check them again at this point. if (mir->compilingWasm()) { 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; } // WarpBuilder skips over code that can't be reached except through // a catch block. Locals and arguments may be observable in such // code after bailing out, so we can't rely on seeing all uses. if (graph.hasTryBlock()) { 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(); MOZ_ASSERT(consumer->isConsistentFloat32Use(use.use())); } } } #endif return true; } static bool HappensBefore(const MDefinition* earlier, const MDefinition* later) { MOZ_ASSERT(earlier->block() == later->block()); for (auto* ins : *earlier->block()) { if (ins == earlier) { return true; } if (ins == later) { return false; } } MOZ_CRASH("earlier and later are instructions in the block"); } // Propagate type information from dominating unbox instructions. // // This optimization applies for example for self-hosted String.prototype // functions. // // Example: // ``` // String.prototype.id = function() { // // Strict mode to avoid ToObject on primitive this-values. // "use strict"; // // // Template string to apply ToString on the this-value. // return `${this}`; // }; // // function f(s) { // // Assume |s| is a string value. // return s.id(); // } // ``` // // Compiles into: (Graph after Scalar Replacement) // // ┌───────────────────────────────────────────────────────────────────────────┐ // │ Block 0 │ // │ resumepoint 1 0 2 2 │ // │ 0 parameter THIS_SLOT Value │ // │ 1 parameter 0 Value │ // │ 2 constant undefined Undefined │ // │ 3 start │ // │ 4 checkoverrecursed │ // │ 5 unbox parameter1 to String (fallible) String │ // │ 6 constant object 1d908053e088 (String) Object │ // │ 7 guardshape constant6:Object Object │ // │ 8 slots guardshape7:Object Slots │ // │ 9 loaddynamicslot slots8:Slots (slot 53) Value │ // │ 10 constant 0x0 Int32 │ // │ 11 unbox loaddynamicslot9 to Object (fallible) Object │ // │ 12 nurseryobject Object │ // │ 13 guardspecificfunction unbox11:Object nurseryobject12:Object Object │ // │ 14 goto block1 │ // └──────────────────────────────────┬────────────────────────────────────────┘ // │ // ┌──────────────────────────────────▼────────────────────────────────────────┐ // │ Block 1 │ // │ ((0)) resumepoint 15 1 15 15 | 1 13 1 0 2 2 │ // │ 15 constant undefined Undefined │ // │ 16 tostring parameter1:Value String │ // │ 18 goto block2 │ // └──────────────────────────────────┬────────────────────────────────────────┘ // │ // ┌──────────────▼──────────────┐ // │ Block 2 │ // │ resumepoint 16 1 0 2 2 │ // │ 19 return tostring16:String │ // └─────────────────────────────┘ // // The Unbox instruction is used as a type guard. The ToString instruction // doesn't use the type information from the preceding Unbox instruction and // therefore has to assume its operand can be any value. // // When instead propagating the type information from the preceding Unbox // instruction, this graph is constructed after the "Apply types" phase: // // ┌───────────────────────────────────────────────────────────────────────────┐ // │ Block 0 │ // │ resumepoint 1 0 2 2 │ // │ 0 parameter THIS_SLOT Value │ // │ 1 parameter 0 Value │ // │ 2 constant undefined Undefined │ // │ 3 start │ // │ 4 checkoverrecursed │ // │ 5 unbox parameter1 to String (fallible) String │ // │ 6 constant object 1d908053e088 (String) Object │ // │ 7 guardshape constant6:Object Object │ // │ 8 slots guardshape7:Object Slots │ // │ 9 loaddynamicslot slots8:Slots (slot 53) Value │ // │ 10 constant 0x0 Int32 │ // │ 11 unbox loaddynamicslot9 to Object (fallible) Object │ // │ 12 nurseryobject Object │ // │ 13 guardspecificfunction unbox11:Object nurseryobject12:Object Object │ // │ 14 goto block1 │ // └──────────────────────────────────┬────────────────────────────────────────┘ // │ // ┌──────────────────────────────────▼────────────────────────────────────────┐ // │ Block 1 │ // │ ((0)) resumepoint 15 1 15 15 | 1 13 1 0 2 2 │ // │ 15 constant undefined Undefined │ // │ 20 unbox parameter1 to String (fallible) String │ // │ 16 tostring parameter1:Value String │ // │ 18 goto block2 │ // └──────────────────────────────────┬────────────────────────────────────────┘ // │ // ┌──────────────▼─────────────────────┐ // │ Block 2 │ // │ resumepoint 16 1 0 2 2 │ // │ 21 box tostring16:String Value │ // │ 19 return box21:Value │ // └────────────────────────────────────┘ // // GVN will later merge both Unbox instructions and fold away the ToString // instruction, so we get this final graph: // // ┌───────────────────────────────────────────────────────────────────────────┐ // │ Block 0 │ // │ resumepoint 1 0 2 2 │ // │ 0 parameter THIS_SLOT Value │ // │ 1 parameter 0 Value │ // │ 2 constant undefined Undefined │ // │ 3 start │ // │ 4 checkoverrecursed │ // │ 5 unbox parameter1 to String (fallible) String │ // │ 6 constant object 1d908053e088 (String) Object │ // │ 7 guardshape constant6:Object Object │ // │ 8 slots guardshape7:Object Slots │ // │ 22 loaddynamicslotandunbox slots8:Slots (slot 53) Object │ // │ 11 nurseryobject Object │ // │ 12 guardspecificfunction load22:Object nurseryobject11:Object Object │ // │ 13 goto block1 │ // └──────────────────────────────────┬────────────────────────────────────────┘ // │ // ┌──────────────────────────────────▼────────────────────────────────────────┐ // │ Block 1 │ // │ ((0)) resumepoint 2 1 2 2 | 1 12 1 0 2 2 │ // │ 14 goto block2 │ // └──────────────────────────────────┬────────────────────────────────────────┘ // │ // ┌──────────────▼─────────────────────┐ // │ Block 2 │ // │ resumepoint 5 1 0 2 2 │ // │ 15 return parameter1:Value │ // └────────────────────────────────────┘ // bool TypeAnalyzer::propagateUnbox() { // Visit the blocks in post-order, so that the type information of the closest // unbox operation is used. for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); block++) { if (mir->shouldCancel("Propagate Unbox")) { return false; } // Iterate over all instructions to look for unbox instructions. for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) { if (!iter->isUnbox()) { continue; } auto* unbox = iter->toUnbox(); auto* input = unbox->input(); // Ignore unbox operations on typed values. if (input->type() != MIRType::Value) { continue; } // Ignore unbox to floating point types, because propagating boxed Int32 // values as Double can lead to repeated bailouts when later instructions // expect Int32 inputs. if (IsFloatingPointType(unbox->type())) { continue; } // Inspect other uses of |input| to propagate the unboxed type information // from |unbox|. for (auto uses = input->usesBegin(); uses != input->usesEnd();) { auto* use = *uses++; // Ignore resume points. if (!use->consumer()->isDefinition()) { continue; } auto* def = use->consumer()->toDefinition(); // Ignore any unbox operations, including the current |unbox|. if (def->isUnbox()) { continue; } // Ignore phi nodes, because we don't yet support them. if (def->isPhi()) { continue; } // The unbox operation needs to happen before the other use, otherwise // we can't propagate the type information. if (unbox->block() == def->block()) { if (!HappensBefore(unbox, def)) { continue; } } else { if (!unbox->block()->dominates(def->block())) { continue; } } // Replace the use with |unbox|, so that GVN knows about the actual // value type and can more easily fold unnecessary operations. If the // instruction actually needs a boxed input, the BoxPolicy type policy // will simply unwrap the unbox instruction. use->replaceProducer(unbox); // The uses in the MIR graph no longer reflect the uses in the bytecode, // so we have to mark |input| as implicitly used. input->setImplicitlyUsedUnchecked(); } } } return true; } bool TypeAnalyzer::analyze() { if (!tryEmitFloatOperations()) { return false; } if (!specializePhis()) { return false; } if (!propagateUnbox()) { return false; } if (!insertConversions()) { return false; } if (!checkFloatCoherency()) { return false; } return true; } bool jit::ApplyTypeInformation(const MIRGenerator* mir, MIRGraph& graph) { TypeAnalyzer analyzer(mir, graph); if (!analyzer.analyze()) { return false; } return true; }