1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/IonAnalysis.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,2474 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jit/IonAnalysis.h"
1.11 +
1.12 +#include "jsanalyze.h"
1.13 +
1.14 +#include "jit/BaselineInspector.h"
1.15 +#include "jit/BaselineJIT.h"
1.16 +#include "jit/Ion.h"
1.17 +#include "jit/IonBuilder.h"
1.18 +#include "jit/IonOptimizationLevels.h"
1.19 +#include "jit/LIR.h"
1.20 +#include "jit/Lowering.h"
1.21 +#include "jit/MIRGraph.h"
1.22 +
1.23 +#include "jsinferinlines.h"
1.24 +#include "jsobjinlines.h"
1.25 +#include "jsopcodeinlines.h"
1.26 +
1.27 +using namespace js;
1.28 +using namespace js::jit;
1.29 +
1.30 +using mozilla::DebugOnly;
1.31 +
1.32 +// A critical edge is an edge which is neither its successor's only predecessor
1.33 +// nor its predecessor's only successor. Critical edges must be split to
1.34 +// prevent copy-insertion and code motion from affecting other edges.
1.35 +bool
1.36 +jit::SplitCriticalEdges(MIRGraph &graph)
1.37 +{
1.38 + for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
1.39 + if (block->numSuccessors() < 2)
1.40 + continue;
1.41 + for (size_t i = 0; i < block->numSuccessors(); i++) {
1.42 + MBasicBlock *target = block->getSuccessor(i);
1.43 + if (target->numPredecessors() < 2)
1.44 + continue;
1.45 +
1.46 + // Create a new block inheriting from the predecessor.
1.47 + MBasicBlock *split = MBasicBlock::NewSplitEdge(graph, block->info(), *block);
1.48 + if (!split)
1.49 + return false;
1.50 + split->setLoopDepth(block->loopDepth());
1.51 + graph.insertBlockAfter(*block, split);
1.52 + split->end(MGoto::New(graph.alloc(), target));
1.53 +
1.54 + block->replaceSuccessor(i, split);
1.55 + target->replacePredecessor(*block, split);
1.56 + }
1.57 + }
1.58 + return true;
1.59 +}
1.60 +
1.61 +// Operands to a resume point which are dead at the point of the resume can be
1.62 +// replaced with undefined values. This analysis supports limited detection of
1.63 +// dead operands, pruning those which are defined in the resume point's basic
1.64 +// block and have no uses outside the block or at points later than the resume
1.65 +// point.
1.66 +//
1.67 +// This is intended to ensure that extra resume points within a basic block
1.68 +// will not artificially extend the lifetimes of any SSA values. This could
1.69 +// otherwise occur if the new resume point captured a value which is created
1.70 +// between the old and new resume point and is dead at the new resume point.
1.71 +bool
1.72 +jit::EliminateDeadResumePointOperands(MIRGenerator *mir, MIRGraph &graph)
1.73 +{
1.74 + // If we are compiling try blocks, locals and arguments may be observable
1.75 + // from catch or finally blocks (which Ion does not compile). For now just
1.76 + // disable the pass in this case.
1.77 + if (graph.hasTryBlock())
1.78 + return true;
1.79 +
1.80 + for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
1.81 + if (mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)"))
1.82 + return false;
1.83 +
1.84 + // The logic below can get confused on infinite loops.
1.85 + if (block->isLoopHeader() && block->backedge() == *block)
1.86 + continue;
1.87 +
1.88 + for (MInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
1.89 + // No benefit to replacing constant operands with other constants.
1.90 + if (ins->isConstant())
1.91 + continue;
1.92 +
1.93 + // Scanning uses does not give us sufficient information to tell
1.94 + // where instructions that are involved in box/unbox operations or
1.95 + // parameter passing might be live. Rewriting uses of these terms
1.96 + // in resume points may affect the interpreter's behavior. Rather
1.97 + // than doing a more sophisticated analysis, just ignore these.
1.98 + if (ins->isUnbox() || ins->isParameter() || ins->isTypeBarrier() || ins->isComputeThis())
1.99 + continue;
1.100 +
1.101 + // If the instruction's behavior has been constant folded into a
1.102 + // separate instruction, we can't determine precisely where the
1.103 + // instruction becomes dead and can't eliminate its uses.
1.104 + if (ins->isImplicitlyUsed())
1.105 + continue;
1.106 +
1.107 + // Check if this instruction's result is only used within the
1.108 + // current block, and keep track of its last use in a definition
1.109 + // (not resume point). This requires the instructions in the block
1.110 + // to be numbered, ensured by running this immediately after alias
1.111 + // analysis.
1.112 + uint32_t maxDefinition = 0;
1.113 + for (MUseDefIterator uses(*ins); uses; uses++) {
1.114 + if (uses.def()->block() != *block ||
1.115 + uses.def()->isBox() ||
1.116 + uses.def()->isPhi())
1.117 + {
1.118 + maxDefinition = UINT32_MAX;
1.119 + break;
1.120 + }
1.121 + maxDefinition = Max(maxDefinition, uses.def()->id());
1.122 + }
1.123 + if (maxDefinition == UINT32_MAX)
1.124 + continue;
1.125 +
1.126 + // Walk the uses a second time, removing any in resume points after
1.127 + // the last use in a definition.
1.128 + for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd(); ) {
1.129 + if (uses->consumer()->isDefinition()) {
1.130 + uses++;
1.131 + continue;
1.132 + }
1.133 + MResumePoint *mrp = uses->consumer()->toResumePoint();
1.134 + if (mrp->block() != *block ||
1.135 + !mrp->instruction() ||
1.136 + mrp->instruction() == *ins ||
1.137 + mrp->instruction()->id() <= maxDefinition)
1.138 + {
1.139 + uses++;
1.140 + continue;
1.141 + }
1.142 +
1.143 + // The operand is an uneliminable slot. This currently
1.144 + // includes argument slots in non-strict scripts (due to being
1.145 + // observable via Function.arguments).
1.146 + if (!block->info().canOptimizeOutSlot(uses->index())) {
1.147 + uses++;
1.148 + continue;
1.149 + }
1.150 +
1.151 + // Store an optimized out magic value in place of all dead
1.152 + // resume point operands. Making any such substitution can in
1.153 + // general alter the interpreter's behavior, even though the
1.154 + // code is dead, as the interpreter will still execute opcodes
1.155 + // whose effects cannot be observed. If the undefined value
1.156 + // were to flow to, say, a dead property access the
1.157 + // interpreter could throw an exception; we avoid this problem
1.158 + // by removing dead operands before removing dead code.
1.159 + MConstant *constant = MConstant::New(graph.alloc(), MagicValue(JS_OPTIMIZED_OUT));
1.160 + block->insertBefore(*(block->begin()), constant);
1.161 + uses = mrp->replaceOperand(uses, constant);
1.162 + }
1.163 + }
1.164 + }
1.165 +
1.166 + return true;
1.167 +}
1.168 +
1.169 +// Instructions are useless if they are unused and have no side effects.
1.170 +// This pass eliminates useless instructions.
1.171 +// The graph itself is unchanged.
1.172 +bool
1.173 +jit::EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph)
1.174 +{
1.175 + // Traverse in postorder so that we hit uses before definitions.
1.176 + // Traverse instruction list backwards for the same reason.
1.177 + for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
1.178 + if (mir->shouldCancel("Eliminate Dead Code (main loop)"))
1.179 + return false;
1.180 +
1.181 + // Remove unused instructions.
1.182 + for (MInstructionReverseIterator inst = block->rbegin(); inst != block->rend(); ) {
1.183 + if (!inst->isEffectful() && !inst->resumePoint() &&
1.184 + !inst->hasUses() && !inst->isGuard() &&
1.185 + !inst->isControlInstruction()) {
1.186 + inst = block->discardAt(inst);
1.187 + } else {
1.188 + inst++;
1.189 + }
1.190 + }
1.191 + }
1.192 +
1.193 + return true;
1.194 +}
1.195 +
1.196 +static inline bool
1.197 +IsPhiObservable(MPhi *phi, Observability observe)
1.198 +{
1.199 + // If the phi has uses which are not reflected in SSA, then behavior in the
1.200 + // interpreter may be affected by removing the phi.
1.201 + if (phi->isImplicitlyUsed())
1.202 + return true;
1.203 +
1.204 + // Check for uses of this phi node outside of other phi nodes.
1.205 + // Note that, initially, we skip reading resume points, which we
1.206 + // don't count as actual uses. If the only uses are resume points,
1.207 + // then the SSA name is never consumed by the program. However,
1.208 + // after optimizations have been performed, it's possible that the
1.209 + // actual uses in the program have been (incorrectly) optimized
1.210 + // away, so we must be more conservative and consider resume
1.211 + // points as well.
1.212 + switch (observe) {
1.213 + case AggressiveObservability:
1.214 + for (MUseDefIterator iter(phi); iter; iter++) {
1.215 + if (!iter.def()->isPhi())
1.216 + return true;
1.217 + }
1.218 + break;
1.219 +
1.220 + case ConservativeObservability:
1.221 + for (MUseIterator iter(phi->usesBegin()); iter != phi->usesEnd(); iter++) {
1.222 + if (!iter->consumer()->isDefinition() ||
1.223 + !iter->consumer()->toDefinition()->isPhi())
1.224 + return true;
1.225 + }
1.226 + break;
1.227 + }
1.228 +
1.229 + uint32_t slot = phi->slot();
1.230 + CompileInfo &info = phi->block()->info();
1.231 + JSFunction *fun = info.funMaybeLazy();
1.232 +
1.233 + // If the Phi is of the |this| value, it must always be observable.
1.234 + if (fun && slot == info.thisSlot())
1.235 + return true;
1.236 +
1.237 + // If the function may need an arguments object, then make sure to
1.238 + // preserve the scope chain, because it may be needed to construct the
1.239 + // arguments object during bailout. If we've already created an arguments
1.240 + // object (or got one via OSR), preserve that as well.
1.241 + if (fun && info.hasArguments() &&
1.242 + (slot == info.scopeChainSlot() || slot == info.argsObjSlot()))
1.243 + {
1.244 + return true;
1.245 + }
1.246 +
1.247 + // The Phi is an uneliminable slot. Currently this includes argument slots
1.248 + // in non-strict scripts (due to being observable via Function.arguments).
1.249 + if (fun && !info.canOptimizeOutSlot(slot))
1.250 + return true;
1.251 +
1.252 + return false;
1.253 +}
1.254 +
1.255 +// Handles cases like:
1.256 +// x is phi(a, x) --> a
1.257 +// x is phi(a, a) --> a
1.258 +static inline MDefinition *
1.259 +IsPhiRedundant(MPhi *phi)
1.260 +{
1.261 + MDefinition *first = phi->operandIfRedundant();
1.262 + if (first == nullptr)
1.263 + return nullptr;
1.264 +
1.265 + // Propagate the ImplicitlyUsed flag if |phi| is replaced with another phi.
1.266 + if (phi->isImplicitlyUsed())
1.267 + first->setImplicitlyUsedUnchecked();
1.268 +
1.269 + return first;
1.270 +}
1.271 +
1.272 +bool
1.273 +jit::EliminatePhis(MIRGenerator *mir, MIRGraph &graph,
1.274 + Observability observe)
1.275 +{
1.276 + // Eliminates redundant or unobservable phis from the graph. A
1.277 + // redundant phi is something like b = phi(a, a) or b = phi(a, b),
1.278 + // both of which can be replaced with a. An unobservable phi is
1.279 + // one that whose value is never used in the program.
1.280 + //
1.281 + // Note that we must be careful not to eliminate phis representing
1.282 + // values that the interpreter will require later. When the graph
1.283 + // is first constructed, we can be more aggressive, because there
1.284 + // is a greater correspondence between the CFG and the bytecode.
1.285 + // After optimizations such as GVN have been performed, however,
1.286 + // the bytecode and CFG may not correspond as closely to one
1.287 + // another. In that case, we must be more conservative. The flag
1.288 + // |conservativeObservability| is used to indicate that eliminate
1.289 + // phis is being run after some optimizations have been performed,
1.290 + // and thus we should use more conservative rules about
1.291 + // observability. The particular danger is that we can optimize
1.292 + // away uses of a phi because we think they are not executable,
1.293 + // but the foundation for that assumption is false TI information
1.294 + // that will eventually be invalidated. Therefore, if
1.295 + // |conservativeObservability| is set, we will consider any use
1.296 + // from a resume point to be observable. Otherwise, we demand a
1.297 + // use from an actual instruction.
1.298 +
1.299 + Vector<MPhi *, 16, SystemAllocPolicy> worklist;
1.300 +
1.301 + // Add all observable phis to a worklist. We use the "in worklist" bit to
1.302 + // mean "this phi is live".
1.303 + for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
1.304 + if (mir->shouldCancel("Eliminate Phis (populate loop)"))
1.305 + return false;
1.306 +
1.307 + MPhiIterator iter = block->phisBegin();
1.308 + while (iter != block->phisEnd()) {
1.309 + // Flag all as unused, only observable phis would be marked as used
1.310 + // when processed by the work list.
1.311 + iter->setUnused();
1.312 +
1.313 + // If the phi is redundant, remove it here.
1.314 + if (MDefinition *redundant = IsPhiRedundant(*iter)) {
1.315 + iter->replaceAllUsesWith(redundant);
1.316 + iter = block->discardPhiAt(iter);
1.317 + continue;
1.318 + }
1.319 +
1.320 + // Enqueue observable Phis.
1.321 + if (IsPhiObservable(*iter, observe)) {
1.322 + iter->setInWorklist();
1.323 + if (!worklist.append(*iter))
1.324 + return false;
1.325 + }
1.326 + iter++;
1.327 + }
1.328 + }
1.329 +
1.330 + // Iteratively mark all phis reachable from live phis.
1.331 + while (!worklist.empty()) {
1.332 + if (mir->shouldCancel("Eliminate Phis (worklist)"))
1.333 + return false;
1.334 +
1.335 + MPhi *phi = worklist.popCopy();
1.336 + JS_ASSERT(phi->isUnused());
1.337 + phi->setNotInWorklist();
1.338 +
1.339 + // The removal of Phis can produce newly redundant phis.
1.340 + if (MDefinition *redundant = IsPhiRedundant(phi)) {
1.341 + // Add to the worklist the used phis which are impacted.
1.342 + for (MUseDefIterator it(phi); it; it++) {
1.343 + if (it.def()->isPhi()) {
1.344 + MPhi *use = it.def()->toPhi();
1.345 + if (!use->isUnused()) {
1.346 + use->setUnusedUnchecked();
1.347 + use->setInWorklist();
1.348 + if (!worklist.append(use))
1.349 + return false;
1.350 + }
1.351 + }
1.352 + }
1.353 + phi->replaceAllUsesWith(redundant);
1.354 + } else {
1.355 + // Otherwise flag them as used.
1.356 + phi->setNotUnused();
1.357 + }
1.358 +
1.359 + // The current phi is/was used, so all its operands are used.
1.360 + for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
1.361 + MDefinition *in = phi->getOperand(i);
1.362 + if (!in->isPhi() || !in->isUnused() || in->isInWorklist())
1.363 + continue;
1.364 + in->setInWorklist();
1.365 + if (!worklist.append(in->toPhi()))
1.366 + return false;
1.367 + }
1.368 + }
1.369 +
1.370 + // Sweep dead phis.
1.371 + for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
1.372 + MPhiIterator iter = block->phisBegin();
1.373 + while (iter != block->phisEnd()) {
1.374 + if (iter->isUnused())
1.375 + iter = block->discardPhiAt(iter);
1.376 + else
1.377 + iter++;
1.378 + }
1.379 + }
1.380 +
1.381 + return true;
1.382 +}
1.383 +
1.384 +namespace {
1.385 +
1.386 +// The type analysis algorithm inserts conversions and box/unbox instructions
1.387 +// to make the IR graph well-typed for future passes.
1.388 +//
1.389 +// Phi adjustment: If a phi's inputs are all the same type, the phi is
1.390 +// specialized to return that type.
1.391 +//
1.392 +// Input adjustment: Each input is asked to apply conversion operations to its
1.393 +// inputs. This may include Box, Unbox, or other instruction-specific type
1.394 +// conversion operations.
1.395 +//
1.396 +class TypeAnalyzer
1.397 +{
1.398 + MIRGenerator *mir;
1.399 + MIRGraph &graph;
1.400 + Vector<MPhi *, 0, SystemAllocPolicy> phiWorklist_;
1.401 +
1.402 + TempAllocator &alloc() const {
1.403 + return graph.alloc();
1.404 + }
1.405 +
1.406 + bool addPhiToWorklist(MPhi *phi) {
1.407 + if (phi->isInWorklist())
1.408 + return true;
1.409 + if (!phiWorklist_.append(phi))
1.410 + return false;
1.411 + phi->setInWorklist();
1.412 + return true;
1.413 + }
1.414 + MPhi *popPhi() {
1.415 + MPhi *phi = phiWorklist_.popCopy();
1.416 + phi->setNotInWorklist();
1.417 + return phi;
1.418 + }
1.419 +
1.420 + bool respecialize(MPhi *phi, MIRType type);
1.421 + bool propagateSpecialization(MPhi *phi);
1.422 + bool specializePhis();
1.423 + void replaceRedundantPhi(MPhi *phi);
1.424 + void adjustPhiInputs(MPhi *phi);
1.425 + bool adjustInputs(MDefinition *def);
1.426 + bool insertConversions();
1.427 +
1.428 + bool checkFloatCoherency();
1.429 + bool graphContainsFloat32();
1.430 + bool markPhiConsumers();
1.431 + bool markPhiProducers();
1.432 + bool specializeValidFloatOps();
1.433 + bool tryEmitFloatOperations();
1.434 +
1.435 + public:
1.436 + TypeAnalyzer(MIRGenerator *mir, MIRGraph &graph)
1.437 + : mir(mir), graph(graph)
1.438 + { }
1.439 +
1.440 + bool analyze();
1.441 +};
1.442 +
1.443 +} /* anonymous namespace */
1.444 +
1.445 +// Try to specialize this phi based on its non-cyclic inputs.
1.446 +static MIRType
1.447 +GuessPhiType(MPhi *phi, bool *hasInputsWithEmptyTypes)
1.448 +{
1.449 +#ifdef DEBUG
1.450 + // Check that different magic constants aren't flowing together. Ignore
1.451 + // JS_OPTIMIZED_OUT, since an operand could be legitimately optimized
1.452 + // away.
1.453 + MIRType magicType = MIRType_None;
1.454 + for (size_t i = 0; i < phi->numOperands(); i++) {
1.455 + MDefinition *in = phi->getOperand(i);
1.456 + if (in->type() == MIRType_MagicOptimizedArguments ||
1.457 + in->type() == MIRType_MagicHole ||
1.458 + in->type() == MIRType_MagicIsConstructing)
1.459 + {
1.460 + if (magicType == MIRType_None)
1.461 + magicType = in->type();
1.462 + MOZ_ASSERT(magicType == in->type());
1.463 + }
1.464 + }
1.465 +#endif
1.466 +
1.467 + *hasInputsWithEmptyTypes = false;
1.468 +
1.469 + MIRType type = MIRType_None;
1.470 + bool convertibleToFloat32 = false;
1.471 + bool hasPhiInputs = false;
1.472 + for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
1.473 + MDefinition *in = phi->getOperand(i);
1.474 + if (in->isPhi()) {
1.475 + hasPhiInputs = true;
1.476 + if (!in->toPhi()->triedToSpecialize())
1.477 + continue;
1.478 + if (in->type() == MIRType_None) {
1.479 + // The operand is a phi we tried to specialize, but we were
1.480 + // unable to guess its type. propagateSpecialization will
1.481 + // propagate the type to this phi when it becomes known.
1.482 + continue;
1.483 + }
1.484 + }
1.485 +
1.486 + // Ignore operands which we've never observed.
1.487 + if (in->resultTypeSet() && in->resultTypeSet()->empty()) {
1.488 + *hasInputsWithEmptyTypes = true;
1.489 + continue;
1.490 + }
1.491 +
1.492 + if (type == MIRType_None) {
1.493 + type = in->type();
1.494 + if (in->canProduceFloat32())
1.495 + convertibleToFloat32 = true;
1.496 + continue;
1.497 + }
1.498 + if (type != in->type()) {
1.499 + if (convertibleToFloat32 && in->type() == MIRType_Float32) {
1.500 + // If we only saw definitions that can be converted into Float32 before and
1.501 + // encounter a Float32 value, promote previous values to Float32
1.502 + type = MIRType_Float32;
1.503 + } else if (IsNumberType(type) && IsNumberType(in->type())) {
1.504 + // Specialize phis with int32 and double operands as double.
1.505 + type = MIRType_Double;
1.506 + convertibleToFloat32 &= in->canProduceFloat32();
1.507 + } else {
1.508 + return MIRType_Value;
1.509 + }
1.510 + }
1.511 + }
1.512 +
1.513 + if (type == MIRType_None && !hasPhiInputs) {
1.514 + // All inputs are non-phis with empty typesets. Use MIRType_Value
1.515 + // in this case, as it's impossible to get better type information.
1.516 + JS_ASSERT(*hasInputsWithEmptyTypes);
1.517 + type = MIRType_Value;
1.518 + }
1.519 +
1.520 + return type;
1.521 +}
1.522 +
1.523 +bool
1.524 +TypeAnalyzer::respecialize(MPhi *phi, MIRType type)
1.525 +{
1.526 + if (phi->type() == type)
1.527 + return true;
1.528 + phi->specialize(type);
1.529 + return addPhiToWorklist(phi);
1.530 +}
1.531 +
1.532 +bool
1.533 +TypeAnalyzer::propagateSpecialization(MPhi *phi)
1.534 +{
1.535 + JS_ASSERT(phi->type() != MIRType_None);
1.536 +
1.537 + // Verify that this specialization matches any phis depending on it.
1.538 + for (MUseDefIterator iter(phi); iter; iter++) {
1.539 + if (!iter.def()->isPhi())
1.540 + continue;
1.541 + MPhi *use = iter.def()->toPhi();
1.542 + if (!use->triedToSpecialize())
1.543 + continue;
1.544 + if (use->type() == MIRType_None) {
1.545 + // We tried to specialize this phi, but were unable to guess its
1.546 + // type. Now that we know the type of one of its operands, we can
1.547 + // specialize it.
1.548 + if (!respecialize(use, phi->type()))
1.549 + return false;
1.550 + continue;
1.551 + }
1.552 + if (use->type() != phi->type()) {
1.553 + // Specialize phis with int32 that can be converted to float and float operands as floats.
1.554 + if ((use->type() == MIRType_Int32 && use->canProduceFloat32() && phi->type() == MIRType_Float32) ||
1.555 + (phi->type() == MIRType_Int32 && phi->canProduceFloat32() && use->type() == MIRType_Float32))
1.556 + {
1.557 + if (!respecialize(use, MIRType_Float32))
1.558 + return false;
1.559 + continue;
1.560 + }
1.561 +
1.562 + // Specialize phis with int32 and double operands as double.
1.563 + if (IsNumberType(use->type()) && IsNumberType(phi->type())) {
1.564 + if (!respecialize(use, MIRType_Double))
1.565 + return false;
1.566 + continue;
1.567 + }
1.568 +
1.569 + // This phi in our use chain can now no longer be specialized.
1.570 + if (!respecialize(use, MIRType_Value))
1.571 + return false;
1.572 + }
1.573 + }
1.574 +
1.575 + return true;
1.576 +}
1.577 +
1.578 +bool
1.579 +TypeAnalyzer::specializePhis()
1.580 +{
1.581 + Vector<MPhi *, 0, SystemAllocPolicy> phisWithEmptyInputTypes;
1.582 +
1.583 + for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); block++) {
1.584 + if (mir->shouldCancel("Specialize Phis (main loop)"))
1.585 + return false;
1.586 +
1.587 + for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
1.588 + bool hasInputsWithEmptyTypes;
1.589 + MIRType type = GuessPhiType(*phi, &hasInputsWithEmptyTypes);
1.590 + phi->specialize(type);
1.591 + if (type == MIRType_None) {
1.592 + // We tried to guess the type but failed because all operands are
1.593 + // phis we still have to visit. Set the triedToSpecialize flag but
1.594 + // don't propagate the type to other phis, propagateSpecialization
1.595 + // will do that once we know the type of one of the operands.
1.596 +
1.597 + // Edge case: when this phi has a non-phi input with an empty
1.598 + // typeset, it's possible for two phis to have a cyclic
1.599 + // dependency and they will both have MIRType_None. Specialize
1.600 + // such phis to MIRType_Value later on.
1.601 + if (hasInputsWithEmptyTypes && !phisWithEmptyInputTypes.append(*phi))
1.602 + return false;
1.603 + continue;
1.604 + }
1.605 + if (!propagateSpecialization(*phi))
1.606 + return false;
1.607 + }
1.608 + }
1.609 +
1.610 + do {
1.611 + while (!phiWorklist_.empty()) {
1.612 + if (mir->shouldCancel("Specialize Phis (worklist)"))
1.613 + return false;
1.614 +
1.615 + MPhi *phi = popPhi();
1.616 + if (!propagateSpecialization(phi))
1.617 + return false;
1.618 + }
1.619 +
1.620 + // When two phis have a cyclic dependency and inputs that have an empty
1.621 + // typeset (which are ignored by GuessPhiType), we may still have to
1.622 + // specialize these to MIRType_Value.
1.623 + while (!phisWithEmptyInputTypes.empty()) {
1.624 + if (mir->shouldCancel("Specialize Phis (phisWithEmptyInputTypes)"))
1.625 + return false;
1.626 +
1.627 + MPhi *phi = phisWithEmptyInputTypes.popCopy();
1.628 + if (phi->type() == MIRType_None) {
1.629 + phi->specialize(MIRType_Value);
1.630 + if (!propagateSpecialization(phi))
1.631 + return false;
1.632 + }
1.633 + }
1.634 + } while (!phiWorklist_.empty());
1.635 +
1.636 + return true;
1.637 +}
1.638 +
1.639 +void
1.640 +TypeAnalyzer::adjustPhiInputs(MPhi *phi)
1.641 +{
1.642 + MIRType phiType = phi->type();
1.643 + JS_ASSERT(phiType != MIRType_None);
1.644 +
1.645 + // If we specialized a type that's not Value, there are 3 cases:
1.646 + // 1. Every input is of that type.
1.647 + // 2. Every observed input is of that type (i.e., some inputs haven't been executed yet).
1.648 + // 3. Inputs were doubles and int32s, and was specialized to double.
1.649 + if (phiType != MIRType_Value) {
1.650 + for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
1.651 + MDefinition *in = phi->getOperand(i);
1.652 + if (in->type() == phiType)
1.653 + continue;
1.654 +
1.655 + if (in->isBox() && in->toBox()->input()->type() == phiType) {
1.656 + phi->replaceOperand(i, in->toBox()->input());
1.657 + } else {
1.658 + MInstruction *replacement;
1.659 +
1.660 + if (phiType == MIRType_Double && IsFloatType(in->type())) {
1.661 + // Convert int32 operands to double.
1.662 + replacement = MToDouble::New(alloc(), in);
1.663 + } else if (phiType == MIRType_Float32) {
1.664 + if (in->type() == MIRType_Int32 || in->type() == MIRType_Double) {
1.665 + replacement = MToFloat32::New(alloc(), in);
1.666 + } else {
1.667 + // See comment below
1.668 + if (in->type() != MIRType_Value) {
1.669 + MBox *box = MBox::New(alloc(), in);
1.670 + in->block()->insertBefore(in->block()->lastIns(), box);
1.671 + in = box;
1.672 + }
1.673 +
1.674 + MUnbox *unbox = MUnbox::New(alloc(), in, MIRType_Double, MUnbox::Fallible);
1.675 + in->block()->insertBefore(in->block()->lastIns(), unbox);
1.676 + replacement = MToFloat32::New(alloc(), in);
1.677 + }
1.678 + } else {
1.679 + // If we know this branch will fail to convert to phiType,
1.680 + // insert a box that'll immediately fail in the fallible unbox
1.681 + // below.
1.682 + if (in->type() != MIRType_Value) {
1.683 + MBox *box = MBox::New(alloc(), in);
1.684 + in->block()->insertBefore(in->block()->lastIns(), box);
1.685 + in = box;
1.686 + }
1.687 +
1.688 + // Be optimistic and insert unboxes when the operand is a
1.689 + // value.
1.690 + replacement = MUnbox::New(alloc(), in, phiType, MUnbox::Fallible);
1.691 + }
1.692 +
1.693 + in->block()->insertBefore(in->block()->lastIns(), replacement);
1.694 + phi->replaceOperand(i, replacement);
1.695 + }
1.696 + }
1.697 +
1.698 + return;
1.699 + }
1.700 +
1.701 + // Box every typed input.
1.702 + for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
1.703 + MDefinition *in = phi->getOperand(i);
1.704 + if (in->type() == MIRType_Value)
1.705 + continue;
1.706 +
1.707 + if (in->isUnbox() && phi->typeIncludes(in->toUnbox()->input())) {
1.708 + // The input is being explicitly unboxed, so sneak past and grab
1.709 + // the original box.
1.710 + phi->replaceOperand(i, in->toUnbox()->input());
1.711 + } else {
1.712 + MDefinition *box = BoxInputsPolicy::alwaysBoxAt(alloc(), in->block()->lastIns(), in);
1.713 + phi->replaceOperand(i, box);
1.714 + }
1.715 + }
1.716 +}
1.717 +
1.718 +bool
1.719 +TypeAnalyzer::adjustInputs(MDefinition *def)
1.720 +{
1.721 + TypePolicy *policy = def->typePolicy();
1.722 + if (policy && !policy->adjustInputs(alloc(), def->toInstruction()))
1.723 + return false;
1.724 + return true;
1.725 +}
1.726 +
1.727 +void
1.728 +TypeAnalyzer::replaceRedundantPhi(MPhi *phi)
1.729 +{
1.730 + MBasicBlock *block = phi->block();
1.731 + js::Value v;
1.732 + switch (phi->type()) {
1.733 + case MIRType_Undefined:
1.734 + v = UndefinedValue();
1.735 + break;
1.736 + case MIRType_Null:
1.737 + v = NullValue();
1.738 + break;
1.739 + case MIRType_MagicOptimizedArguments:
1.740 + v = MagicValue(JS_OPTIMIZED_ARGUMENTS);
1.741 + break;
1.742 + case MIRType_MagicOptimizedOut:
1.743 + v = MagicValue(JS_OPTIMIZED_OUT);
1.744 + break;
1.745 + default:
1.746 + MOZ_ASSUME_UNREACHABLE("unexpected type");
1.747 + }
1.748 + MConstant *c = MConstant::New(alloc(), v);
1.749 + // The instruction pass will insert the box
1.750 + block->insertBefore(*(block->begin()), c);
1.751 + phi->replaceAllUsesWith(c);
1.752 +}
1.753 +
1.754 +bool
1.755 +TypeAnalyzer::insertConversions()
1.756 +{
1.757 + // Instructions are processed in reverse postorder: all uses are defs are
1.758 + // seen before uses. This ensures that output adjustment (which may rewrite
1.759 + // inputs of uses) does not conflict with input adjustment.
1.760 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
1.761 + if (mir->shouldCancel("Insert Conversions"))
1.762 + return false;
1.763 +
1.764 + for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd();) {
1.765 + if (phi->type() == MIRType_Undefined ||
1.766 + phi->type() == MIRType_Null ||
1.767 + phi->type() == MIRType_MagicOptimizedArguments ||
1.768 + phi->type() == MIRType_MagicOptimizedOut)
1.769 + {
1.770 + replaceRedundantPhi(*phi);
1.771 + phi = block->discardPhiAt(phi);
1.772 + } else {
1.773 + adjustPhiInputs(*phi);
1.774 + phi++;
1.775 + }
1.776 + }
1.777 + for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
1.778 + if (!adjustInputs(*iter))
1.779 + return false;
1.780 + }
1.781 + }
1.782 + return true;
1.783 +}
1.784 +
1.785 +// This function tries to emit Float32 specialized operations whenever it's possible.
1.786 +// MIR nodes are flagged as:
1.787 +// - Producers, when they can create Float32 that might need to be coerced into a Double.
1.788 +// Loads in Float32 arrays and conversions to Float32 are producers.
1.789 +// - Consumers, when they can have Float32 as inputs and validate a legal use of a Float32.
1.790 +// Stores in Float32 arrays and conversions to Float32 are consumers.
1.791 +// - Float32 commutative, when using the Float32 instruction instead of the Double instruction
1.792 +// does not result in a compound loss of precision. This is the case for +, -, /, * with 2
1.793 +// operands, for instance. However, an addition with 3 operands is not commutative anymore,
1.794 +// so an intermediate coercion is needed.
1.795 +// Except for phis, all these flags are known after Ion building, so they cannot change during
1.796 +// the process.
1.797 +//
1.798 +// The idea behind the algorithm is easy: whenever we can prove that a commutative operation
1.799 +// has only producers as inputs and consumers as uses, we can specialize the operation as a
1.800 +// float32 operation. Otherwise, we have to convert all float32 inputs to doubles. Even
1.801 +// if a lot of conversions are produced, GVN will take care of eliminating the redundant ones.
1.802 +//
1.803 +// Phis have a special status. Phis need to be flagged as producers or consumers as they can
1.804 +// be inputs or outputs of commutative instructions. Fortunately, producers and consumers
1.805 +// properties are such that we can deduce the property using all non phis inputs first (which form
1.806 +// an initial phi graph) and then propagate all properties from one phi to another using a
1.807 +// fixed point algorithm. The algorithm is ensured to terminate as each iteration has less or as
1.808 +// many flagged phis as the previous iteration (so the worst steady state case is all phis being
1.809 +// flagged as false).
1.810 +//
1.811 +// In a nutshell, the algorithm applies three passes:
1.812 +// 1 - Determine which phis are consumers. Each phi gets an initial value by making a global AND on
1.813 +// all its non-phi inputs. Then each phi propagates its value to other phis. If after propagation,
1.814 +// the flag value changed, we have to reapply the algorithm on all phi operands, as a phi is a
1.815 +// consumer if all of its uses are consumers.
1.816 +// 2 - Determine which phis are producers. It's the same algorithm, except that we have to reapply
1.817 +// the algorithm on all phi uses, as a phi is a producer if all of its operands are producers.
1.818 +// 3 - Go through all commutative operations and ensure their inputs are all producers and their
1.819 +// uses are all consumers.
1.820 +bool
1.821 +TypeAnalyzer::markPhiConsumers()
1.822 +{
1.823 + JS_ASSERT(phiWorklist_.empty());
1.824 +
1.825 + // Iterate in postorder so worklist is initialized to RPO.
1.826 + for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); ++block) {
1.827 + if (mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Initial state"))
1.828 + return false;
1.829 +
1.830 + for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) {
1.831 + JS_ASSERT(!phi->isInWorklist());
1.832 + bool canConsumeFloat32 = true;
1.833 + for (MUseDefIterator use(*phi); canConsumeFloat32 && use; use++) {
1.834 + MDefinition *usedef = use.def();
1.835 + canConsumeFloat32 &= usedef->isPhi() || usedef->canConsumeFloat32(use.use());
1.836 + }
1.837 + phi->setCanConsumeFloat32(canConsumeFloat32);
1.838 + if (canConsumeFloat32 && !addPhiToWorklist(*phi))
1.839 + return false;
1.840 + }
1.841 + }
1.842 +
1.843 + while (!phiWorklist_.empty()) {
1.844 + if (mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Fixed point"))
1.845 + return false;
1.846 +
1.847 + MPhi *phi = popPhi();
1.848 + JS_ASSERT(phi->canConsumeFloat32(nullptr /* unused */));
1.849 +
1.850 + bool validConsumer = true;
1.851 + for (MUseDefIterator use(phi); use; use++) {
1.852 + MDefinition *def = use.def();
1.853 + if (def->isPhi() && !def->canConsumeFloat32(use.use())) {
1.854 + validConsumer = false;
1.855 + break;
1.856 + }
1.857 + }
1.858 +
1.859 + if (validConsumer)
1.860 + continue;
1.861 +
1.862 + // Propagate invalidated phis
1.863 + phi->setCanConsumeFloat32(false);
1.864 + for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
1.865 + MDefinition *input = phi->getOperand(i);
1.866 + if (input->isPhi() && !input->isInWorklist() && input->canConsumeFloat32(nullptr /* unused */))
1.867 + {
1.868 + if (!addPhiToWorklist(input->toPhi()))
1.869 + return false;
1.870 + }
1.871 + }
1.872 + }
1.873 + return true;
1.874 +}
1.875 +
1.876 +bool
1.877 +TypeAnalyzer::markPhiProducers()
1.878 +{
1.879 + JS_ASSERT(phiWorklist_.empty());
1.880 +
1.881 + // Iterate in reverse postorder so worklist is initialized to PO.
1.882 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
1.883 + if (mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - initial state"))
1.884 + return false;
1.885 +
1.886 + for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) {
1.887 + JS_ASSERT(!phi->isInWorklist());
1.888 + bool canProduceFloat32 = true;
1.889 + for (size_t i = 0, e = phi->numOperands(); canProduceFloat32 && i < e; ++i) {
1.890 + MDefinition *input = phi->getOperand(i);
1.891 + canProduceFloat32 &= input->isPhi() || input->canProduceFloat32();
1.892 + }
1.893 + phi->setCanProduceFloat32(canProduceFloat32);
1.894 + if (canProduceFloat32 && !addPhiToWorklist(*phi))
1.895 + return false;
1.896 + }
1.897 + }
1.898 +
1.899 + while (!phiWorklist_.empty()) {
1.900 + if (mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - Fixed point"))
1.901 + return false;
1.902 +
1.903 + MPhi *phi = popPhi();
1.904 + JS_ASSERT(phi->canProduceFloat32());
1.905 +
1.906 + bool validProducer = true;
1.907 + for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
1.908 + MDefinition *input = phi->getOperand(i);
1.909 + if (input->isPhi() && !input->canProduceFloat32()) {
1.910 + validProducer = false;
1.911 + break;
1.912 + }
1.913 + }
1.914 +
1.915 + if (validProducer)
1.916 + continue;
1.917 +
1.918 + // Propagate invalidated phis
1.919 + phi->setCanProduceFloat32(false);
1.920 + for (MUseDefIterator use(phi); use; use++) {
1.921 + MDefinition *def = use.def();
1.922 + if (def->isPhi() && !def->isInWorklist() && def->canProduceFloat32())
1.923 + {
1.924 + if (!addPhiToWorklist(def->toPhi()))
1.925 + return false;
1.926 + }
1.927 + }
1.928 + }
1.929 + return true;
1.930 +}
1.931 +
1.932 +bool
1.933 +TypeAnalyzer::specializeValidFloatOps()
1.934 +{
1.935 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
1.936 + if (mir->shouldCancel("Ensure Float32 commutativity - Instructions"))
1.937 + return false;
1.938 +
1.939 + for (MInstructionIterator ins(block->begin()); ins != block->end(); ++ins) {
1.940 + if (!ins->isFloat32Commutative())
1.941 + continue;
1.942 +
1.943 + if (ins->type() == MIRType_Float32)
1.944 + continue;
1.945 +
1.946 + // This call will try to specialize the instruction iff all uses are consumers and
1.947 + // all inputs are producers.
1.948 + ins->trySpecializeFloat32(alloc());
1.949 + }
1.950 + }
1.951 + return true;
1.952 +}
1.953 +
1.954 +bool
1.955 +TypeAnalyzer::graphContainsFloat32()
1.956 +{
1.957 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
1.958 + if (mir->shouldCancel("Ensure Float32 commutativity - Graph contains Float32"))
1.959 + return false;
1.960 +
1.961 + for (MDefinitionIterator def(*block); def; def++) {
1.962 + if (def->type() == MIRType_Float32)
1.963 + return true;
1.964 + }
1.965 + }
1.966 + return false;
1.967 +}
1.968 +
1.969 +bool
1.970 +TypeAnalyzer::tryEmitFloatOperations()
1.971 +{
1.972 + // Backends that currently don't know how to generate Float32 specialized instructions
1.973 + // shouldn't run this pass and just let all instructions as specialized for Double.
1.974 + if (!LIRGenerator::allowFloat32Optimizations())
1.975 + return true;
1.976 +
1.977 + // Asm.js uses the ahead of time type checks to specialize operations, no need to check
1.978 + // them again at this point.
1.979 + if (mir->compilingAsmJS())
1.980 + return true;
1.981 +
1.982 + // Check ahead of time that there is at least one definition typed as Float32, otherwise we
1.983 + // don't need this pass.
1.984 + if (!graphContainsFloat32())
1.985 + return true;
1.986 +
1.987 + if (!markPhiConsumers())
1.988 + return false;
1.989 + if (!markPhiProducers())
1.990 + return false;
1.991 + if (!specializeValidFloatOps())
1.992 + return false;
1.993 + return true;
1.994 +}
1.995 +
1.996 +bool
1.997 +TypeAnalyzer::checkFloatCoherency()
1.998 +{
1.999 +#ifdef DEBUG
1.1000 + // Asserts that all Float32 instructions are flowing into Float32 consumers or specialized
1.1001 + // operations
1.1002 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) {
1.1003 + if (mir->shouldCancel("Check Float32 coherency"))
1.1004 + return false;
1.1005 +
1.1006 + for (MDefinitionIterator def(*block); def; def++) {
1.1007 + if (def->type() != MIRType_Float32)
1.1008 + continue;
1.1009 +
1.1010 + for (MUseDefIterator use(*def); use; use++) {
1.1011 + MDefinition *consumer = use.def();
1.1012 + JS_ASSERT(consumer->isConsistentFloat32Use(use.use()));
1.1013 + }
1.1014 + }
1.1015 + }
1.1016 +#endif
1.1017 + return true;
1.1018 +}
1.1019 +
1.1020 +bool
1.1021 +TypeAnalyzer::analyze()
1.1022 +{
1.1023 + if (!tryEmitFloatOperations())
1.1024 + return false;
1.1025 + if (!specializePhis())
1.1026 + return false;
1.1027 + if (!insertConversions())
1.1028 + return false;
1.1029 + if (!checkFloatCoherency())
1.1030 + return false;
1.1031 + return true;
1.1032 +}
1.1033 +
1.1034 +bool
1.1035 +jit::ApplyTypeInformation(MIRGenerator *mir, MIRGraph &graph)
1.1036 +{
1.1037 + TypeAnalyzer analyzer(mir, graph);
1.1038 +
1.1039 + if (!analyzer.analyze())
1.1040 + return false;
1.1041 +
1.1042 + return true;
1.1043 +}
1.1044 +
1.1045 +bool
1.1046 +jit::MakeMRegExpHoistable(MIRGraph &graph)
1.1047 +{
1.1048 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
1.1049 + for (MDefinitionIterator iter(*block); iter; iter++) {
1.1050 + if (!iter->isRegExp())
1.1051 + continue;
1.1052 +
1.1053 + MRegExp *regexp = iter->toRegExp();
1.1054 +
1.1055 + // Test if MRegExp is hoistable by looking at all uses.
1.1056 + bool hoistable = true;
1.1057 + for (MUseIterator i = regexp->usesBegin(); i != regexp->usesEnd(); i++) {
1.1058 + // Ignore resume points. At this point all uses are listed.
1.1059 + // No DCE or GVN or something has happened.
1.1060 + if (i->consumer()->isResumePoint())
1.1061 + continue;
1.1062 +
1.1063 + JS_ASSERT(i->consumer()->isDefinition());
1.1064 +
1.1065 + // All MRegExp* MIR's don't adjust the regexp.
1.1066 + MDefinition *use = i->consumer()->toDefinition();
1.1067 + if (use->isRegExpReplace())
1.1068 + continue;
1.1069 + if (use->isRegExpExec())
1.1070 + continue;
1.1071 + if (use->isRegExpTest())
1.1072 + continue;
1.1073 +
1.1074 + hoistable = false;
1.1075 + break;
1.1076 + }
1.1077 +
1.1078 + if (!hoistable)
1.1079 + continue;
1.1080 +
1.1081 + // Make MRegExp hoistable
1.1082 + regexp->setMovable();
1.1083 +
1.1084 + // That would be incorrect for global/sticky, because lastIndex could be wrong.
1.1085 + // Therefore setting the lastIndex to 0. That is faster than a not movable regexp.
1.1086 + RegExpObject *source = regexp->source();
1.1087 + if (source->sticky() || source->global()) {
1.1088 + JS_ASSERT(regexp->mustClone());
1.1089 + MConstant *zero = MConstant::New(graph.alloc(), Int32Value(0));
1.1090 + regexp->block()->insertAfter(regexp, zero);
1.1091 +
1.1092 + MStoreFixedSlot *lastIndex =
1.1093 + MStoreFixedSlot::New(graph.alloc(), regexp, RegExpObject::lastIndexSlot(), zero);
1.1094 + regexp->block()->insertAfter(zero, lastIndex);
1.1095 + }
1.1096 + }
1.1097 + }
1.1098 +
1.1099 + return true;
1.1100 +}
1.1101 +
1.1102 +bool
1.1103 +jit::RenumberBlocks(MIRGraph &graph)
1.1104 +{
1.1105 + size_t id = 0;
1.1106 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++)
1.1107 + block->setId(id++);
1.1108 +
1.1109 + return true;
1.1110 +}
1.1111 +
1.1112 +// A Simple, Fast Dominance Algorithm by Cooper et al.
1.1113 +// Modified to support empty intersections for OSR, and in RPO.
1.1114 +static MBasicBlock *
1.1115 +IntersectDominators(MBasicBlock *block1, MBasicBlock *block2)
1.1116 +{
1.1117 + MBasicBlock *finger1 = block1;
1.1118 + MBasicBlock *finger2 = block2;
1.1119 +
1.1120 + JS_ASSERT(finger1);
1.1121 + JS_ASSERT(finger2);
1.1122 +
1.1123 + // In the original paper, the block ID comparisons are on the postorder index.
1.1124 + // This implementation iterates in RPO, so the comparisons are reversed.
1.1125 +
1.1126 + // For this function to be called, the block must have multiple predecessors.
1.1127 + // If a finger is then found to be self-dominating, it must therefore be
1.1128 + // reachable from multiple roots through non-intersecting control flow.
1.1129 + // nullptr is returned in this case, to denote an empty intersection.
1.1130 +
1.1131 + while (finger1->id() != finger2->id()) {
1.1132 + while (finger1->id() > finger2->id()) {
1.1133 + MBasicBlock *idom = finger1->immediateDominator();
1.1134 + if (idom == finger1)
1.1135 + return nullptr; // Empty intersection.
1.1136 + finger1 = idom;
1.1137 + }
1.1138 +
1.1139 + while (finger2->id() > finger1->id()) {
1.1140 + MBasicBlock *idom = finger2->immediateDominator();
1.1141 + if (idom == finger2)
1.1142 + return nullptr; // Empty intersection.
1.1143 + finger2 = idom;
1.1144 + }
1.1145 + }
1.1146 + return finger1;
1.1147 +}
1.1148 +
1.1149 +static void
1.1150 +ComputeImmediateDominators(MIRGraph &graph)
1.1151 +{
1.1152 + // The default start block is a root and therefore only self-dominates.
1.1153 + MBasicBlock *startBlock = *graph.begin();
1.1154 + startBlock->setImmediateDominator(startBlock);
1.1155 +
1.1156 + // Any OSR block is a root and therefore only self-dominates.
1.1157 + MBasicBlock *osrBlock = graph.osrBlock();
1.1158 + if (osrBlock)
1.1159 + osrBlock->setImmediateDominator(osrBlock);
1.1160 +
1.1161 + bool changed = true;
1.1162 +
1.1163 + while (changed) {
1.1164 + changed = false;
1.1165 +
1.1166 + ReversePostorderIterator block = graph.rpoBegin();
1.1167 +
1.1168 + // For each block in RPO, intersect all dominators.
1.1169 + for (; block != graph.rpoEnd(); block++) {
1.1170 + // If a node has once been found to have no exclusive dominator,
1.1171 + // it will never have an exclusive dominator, so it may be skipped.
1.1172 + if (block->immediateDominator() == *block)
1.1173 + continue;
1.1174 +
1.1175 + MBasicBlock *newIdom = block->getPredecessor(0);
1.1176 +
1.1177 + // Find the first common dominator.
1.1178 + for (size_t i = 1; i < block->numPredecessors(); i++) {
1.1179 + MBasicBlock *pred = block->getPredecessor(i);
1.1180 + if (pred->immediateDominator() == nullptr)
1.1181 + continue;
1.1182 +
1.1183 + newIdom = IntersectDominators(pred, newIdom);
1.1184 +
1.1185 + // If there is no common dominator, the block self-dominates.
1.1186 + if (newIdom == nullptr) {
1.1187 + block->setImmediateDominator(*block);
1.1188 + changed = true;
1.1189 + break;
1.1190 + }
1.1191 + }
1.1192 +
1.1193 + if (newIdom && block->immediateDominator() != newIdom) {
1.1194 + block->setImmediateDominator(newIdom);
1.1195 + changed = true;
1.1196 + }
1.1197 + }
1.1198 + }
1.1199 +
1.1200 +#ifdef DEBUG
1.1201 + // Assert that all blocks have dominator information.
1.1202 + for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
1.1203 + JS_ASSERT(block->immediateDominator() != nullptr);
1.1204 + }
1.1205 +#endif
1.1206 +}
1.1207 +
1.1208 +bool
1.1209 +jit::BuildDominatorTree(MIRGraph &graph)
1.1210 +{
1.1211 + ComputeImmediateDominators(graph);
1.1212 +
1.1213 + // Traversing through the graph in post-order means that every use
1.1214 + // of a definition is visited before the def itself. Since a def
1.1215 + // dominates its uses, by the time we reach a particular
1.1216 + // block, we have processed all of its dominated children, so
1.1217 + // block->numDominated() is accurate.
1.1218 + for (PostorderIterator i(graph.poBegin()); i != graph.poEnd(); i++) {
1.1219 + MBasicBlock *child = *i;
1.1220 + MBasicBlock *parent = child->immediateDominator();
1.1221 +
1.1222 + // If the block only self-dominates, it has no definite parent.
1.1223 + if (child == parent)
1.1224 + continue;
1.1225 +
1.1226 + if (!parent->addImmediatelyDominatedBlock(child))
1.1227 + return false;
1.1228 +
1.1229 + // An additional +1 for the child block.
1.1230 + parent->addNumDominated(child->numDominated() + 1);
1.1231 + }
1.1232 +
1.1233 +#ifdef DEBUG
1.1234 + // If compiling with OSR, many blocks will self-dominate.
1.1235 + // Without OSR, there is only one root block which dominates all.
1.1236 + if (!graph.osrBlock())
1.1237 + JS_ASSERT(graph.begin()->numDominated() == graph.numBlocks() - 1);
1.1238 +#endif
1.1239 + // Now, iterate through the dominator tree and annotate every
1.1240 + // block with its index in the pre-order traversal of the
1.1241 + // dominator tree.
1.1242 + Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(graph.alloc());
1.1243 +
1.1244 + // The index of the current block in the CFG traversal.
1.1245 + size_t index = 0;
1.1246 +
1.1247 + // Add all self-dominating blocks to the worklist.
1.1248 + // This includes all roots. Order does not matter.
1.1249 + for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
1.1250 + MBasicBlock *block = *i;
1.1251 + if (block->immediateDominator() == block) {
1.1252 + if (!worklist.append(block))
1.1253 + return false;
1.1254 + }
1.1255 + }
1.1256 + // Starting from each self-dominating block, traverse the CFG in pre-order.
1.1257 + while (!worklist.empty()) {
1.1258 + MBasicBlock *block = worklist.popCopy();
1.1259 + block->setDomIndex(index);
1.1260 +
1.1261 + if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
1.1262 + block->immediatelyDominatedBlocksEnd())) {
1.1263 + return false;
1.1264 + }
1.1265 + index++;
1.1266 + }
1.1267 +
1.1268 + return true;
1.1269 +}
1.1270 +
1.1271 +bool
1.1272 +jit::BuildPhiReverseMapping(MIRGraph &graph)
1.1273 +{
1.1274 + // Build a mapping such that given a basic block, whose successor has one or
1.1275 + // more phis, we can find our specific input to that phi. To make this fast
1.1276 + // mapping work we rely on a specific property of our structured control
1.1277 + // flow graph: For a block with phis, its predecessors each have only one
1.1278 + // successor with phis. Consider each case:
1.1279 + // * Blocks with less than two predecessors cannot have phis.
1.1280 + // * Breaks. A break always has exactly one successor, and the break
1.1281 + // catch block has exactly one predecessor for each break, as
1.1282 + // well as a final predecessor for the actual loop exit.
1.1283 + // * Continues. A continue always has exactly one successor, and the
1.1284 + // continue catch block has exactly one predecessor for each
1.1285 + // continue, as well as a final predecessor for the actual
1.1286 + // loop continuation. The continue itself has exactly one
1.1287 + // successor.
1.1288 + // * An if. Each branch as exactly one predecessor.
1.1289 + // * A switch. Each branch has exactly one predecessor.
1.1290 + // * Loop tail. A new block is always created for the exit, and if a
1.1291 + // break statement is present, the exit block will forward
1.1292 + // directly to the break block.
1.1293 + for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
1.1294 + if (block->numPredecessors() < 2) {
1.1295 + JS_ASSERT(block->phisEmpty());
1.1296 + continue;
1.1297 + }
1.1298 +
1.1299 + // Assert on the above.
1.1300 + for (size_t j = 0; j < block->numPredecessors(); j++) {
1.1301 + MBasicBlock *pred = block->getPredecessor(j);
1.1302 +
1.1303 +#ifdef DEBUG
1.1304 + size_t numSuccessorsWithPhis = 0;
1.1305 + for (size_t k = 0; k < pred->numSuccessors(); k++) {
1.1306 + MBasicBlock *successor = pred->getSuccessor(k);
1.1307 + if (!successor->phisEmpty())
1.1308 + numSuccessorsWithPhis++;
1.1309 + }
1.1310 + JS_ASSERT(numSuccessorsWithPhis <= 1);
1.1311 +#endif
1.1312 +
1.1313 + pred->setSuccessorWithPhis(*block, j);
1.1314 + }
1.1315 + }
1.1316 +
1.1317 + return true;
1.1318 +}
1.1319 +
1.1320 +#ifdef DEBUG
1.1321 +static bool
1.1322 +CheckSuccessorImpliesPredecessor(MBasicBlock *A, MBasicBlock *B)
1.1323 +{
1.1324 + // Assuming B = succ(A), verify A = pred(B).
1.1325 + for (size_t i = 0; i < B->numPredecessors(); i++) {
1.1326 + if (A == B->getPredecessor(i))
1.1327 + return true;
1.1328 + }
1.1329 + return false;
1.1330 +}
1.1331 +
1.1332 +static bool
1.1333 +CheckPredecessorImpliesSuccessor(MBasicBlock *A, MBasicBlock *B)
1.1334 +{
1.1335 + // Assuming B = pred(A), verify A = succ(B).
1.1336 + for (size_t i = 0; i < B->numSuccessors(); i++) {
1.1337 + if (A == B->getSuccessor(i))
1.1338 + return true;
1.1339 + }
1.1340 + return false;
1.1341 +}
1.1342 +
1.1343 +static bool
1.1344 +CheckOperandImpliesUse(MNode *n, MDefinition *operand)
1.1345 +{
1.1346 + for (MUseIterator i = operand->usesBegin(); i != operand->usesEnd(); i++) {
1.1347 + if (i->consumer() == n)
1.1348 + return true;
1.1349 + }
1.1350 + return false;
1.1351 +}
1.1352 +
1.1353 +static bool
1.1354 +CheckUseImpliesOperand(MDefinition *def, MUse *use)
1.1355 +{
1.1356 + return use->consumer()->getOperand(use->index()) == def;
1.1357 +}
1.1358 +#endif // DEBUG
1.1359 +
1.1360 +void
1.1361 +jit::AssertBasicGraphCoherency(MIRGraph &graph)
1.1362 +{
1.1363 +#ifdef DEBUG
1.1364 + JS_ASSERT(graph.entryBlock()->numPredecessors() == 0);
1.1365 + JS_ASSERT(graph.entryBlock()->phisEmpty());
1.1366 + JS_ASSERT(!graph.entryBlock()->unreachable());
1.1367 +
1.1368 + if (MBasicBlock *osrBlock = graph.osrBlock()) {
1.1369 + JS_ASSERT(osrBlock->numPredecessors() == 0);
1.1370 + JS_ASSERT(osrBlock->phisEmpty());
1.1371 + JS_ASSERT(osrBlock != graph.entryBlock());
1.1372 + JS_ASSERT(!osrBlock->unreachable());
1.1373 + }
1.1374 +
1.1375 + if (MResumePoint *resumePoint = graph.entryResumePoint())
1.1376 + JS_ASSERT(resumePoint->block() == graph.entryBlock());
1.1377 +
1.1378 + // Assert successor and predecessor list coherency.
1.1379 + uint32_t count = 0;
1.1380 + for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
1.1381 + count++;
1.1382 +
1.1383 + JS_ASSERT(&block->graph() == &graph);
1.1384 +
1.1385 + for (size_t i = 0; i < block->numSuccessors(); i++)
1.1386 + JS_ASSERT(CheckSuccessorImpliesPredecessor(*block, block->getSuccessor(i)));
1.1387 +
1.1388 + for (size_t i = 0; i < block->numPredecessors(); i++)
1.1389 + JS_ASSERT(CheckPredecessorImpliesSuccessor(*block, block->getPredecessor(i)));
1.1390 +
1.1391 + // Assert that use chains are valid for this instruction.
1.1392 + for (MDefinitionIterator iter(*block); iter; iter++) {
1.1393 + for (uint32_t i = 0, e = iter->numOperands(); i < e; i++)
1.1394 + JS_ASSERT(CheckOperandImpliesUse(*iter, iter->getOperand(i)));
1.1395 + }
1.1396 + for (MResumePointIterator iter(block->resumePointsBegin()); iter != block->resumePointsEnd(); iter++) {
1.1397 + for (uint32_t i = 0, e = iter->numOperands(); i < e; i++) {
1.1398 + if (iter->getUseFor(i)->hasProducer())
1.1399 + JS_ASSERT(CheckOperandImpliesUse(*iter, iter->getOperand(i)));
1.1400 + }
1.1401 + }
1.1402 + for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
1.1403 + JS_ASSERT(phi->numOperands() == block->numPredecessors());
1.1404 + }
1.1405 + for (MDefinitionIterator iter(*block); iter; iter++) {
1.1406 + JS_ASSERT(iter->block() == *block);
1.1407 + for (MUseIterator i(iter->usesBegin()); i != iter->usesEnd(); i++)
1.1408 + JS_ASSERT(CheckUseImpliesOperand(*iter, *i));
1.1409 +
1.1410 + if (iter->isInstruction()) {
1.1411 + if (MResumePoint *resume = iter->toInstruction()->resumePoint()) {
1.1412 + if (MInstruction *ins = resume->instruction())
1.1413 + JS_ASSERT(ins->block() == iter->block());
1.1414 + }
1.1415 + }
1.1416 + }
1.1417 + }
1.1418 +
1.1419 + JS_ASSERT(graph.numBlocks() == count);
1.1420 +#endif
1.1421 +}
1.1422 +
1.1423 +#ifdef DEBUG
1.1424 +static void
1.1425 +AssertReversePostOrder(MIRGraph &graph)
1.1426 +{
1.1427 + // Check that every block is visited after all its predecessors (except backedges).
1.1428 + for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
1.1429 + JS_ASSERT(!block->isMarked());
1.1430 +
1.1431 + for (size_t i = 0; i < block->numPredecessors(); i++) {
1.1432 + MBasicBlock *pred = block->getPredecessor(i);
1.1433 + JS_ASSERT_IF(!pred->isLoopBackedge(), pred->isMarked());
1.1434 + }
1.1435 +
1.1436 + block->mark();
1.1437 + }
1.1438 +
1.1439 + graph.unmarkBlocks();
1.1440 +}
1.1441 +#endif
1.1442 +
1.1443 +void
1.1444 +jit::AssertGraphCoherency(MIRGraph &graph)
1.1445 +{
1.1446 +#ifdef DEBUG
1.1447 + if (!js_JitOptions.checkGraphConsistency)
1.1448 + return;
1.1449 + AssertBasicGraphCoherency(graph);
1.1450 + AssertReversePostOrder(graph);
1.1451 +#endif
1.1452 +}
1.1453 +
1.1454 +void
1.1455 +jit::AssertExtendedGraphCoherency(MIRGraph &graph)
1.1456 +{
1.1457 + // Checks the basic GraphCoherency but also other conditions that
1.1458 + // do not hold immediately (such as the fact that critical edges
1.1459 + // are split)
1.1460 +
1.1461 +#ifdef DEBUG
1.1462 + if (!js_JitOptions.checkGraphConsistency)
1.1463 + return;
1.1464 + AssertGraphCoherency(graph);
1.1465 +
1.1466 + uint32_t idx = 0;
1.1467 + for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
1.1468 + JS_ASSERT(block->id() == idx++);
1.1469 +
1.1470 + // No critical edges:
1.1471 + if (block->numSuccessors() > 1)
1.1472 + for (size_t i = 0; i < block->numSuccessors(); i++)
1.1473 + JS_ASSERT(block->getSuccessor(i)->numPredecessors() == 1);
1.1474 +
1.1475 + if (block->isLoopHeader()) {
1.1476 + JS_ASSERT(block->numPredecessors() == 2);
1.1477 + MBasicBlock *backedge = block->getPredecessor(1);
1.1478 + JS_ASSERT(backedge->id() >= block->id());
1.1479 + JS_ASSERT(backedge->numSuccessors() == 1);
1.1480 + JS_ASSERT(backedge->getSuccessor(0) == *block);
1.1481 + }
1.1482 +
1.1483 + if (!block->phisEmpty()) {
1.1484 + for (size_t i = 0; i < block->numPredecessors(); i++) {
1.1485 + MBasicBlock *pred = block->getPredecessor(i);
1.1486 + JS_ASSERT(pred->successorWithPhis() == *block);
1.1487 + JS_ASSERT(pred->positionInPhiSuccessor() == i);
1.1488 + }
1.1489 + }
1.1490 +
1.1491 + uint32_t successorWithPhis = 0;
1.1492 + for (size_t i = 0; i < block->numSuccessors(); i++)
1.1493 + if (!block->getSuccessor(i)->phisEmpty())
1.1494 + successorWithPhis++;
1.1495 +
1.1496 + JS_ASSERT(successorWithPhis <= 1);
1.1497 + JS_ASSERT_IF(successorWithPhis, block->successorWithPhis() != nullptr);
1.1498 +
1.1499 + // I'd like to assert this, but it's not necc. true. Sometimes we set this
1.1500 + // flag to non-nullptr just because a successor has multiple preds, even if it
1.1501 + // does not actually have any phis.
1.1502 + //
1.1503 + // JS_ASSERT_IF(!successorWithPhis, block->successorWithPhis() == nullptr);
1.1504 + }
1.1505 +#endif
1.1506 +}
1.1507 +
1.1508 +
1.1509 +struct BoundsCheckInfo
1.1510 +{
1.1511 + MBoundsCheck *check;
1.1512 + uint32_t validUntil;
1.1513 +};
1.1514 +
1.1515 +typedef HashMap<uint32_t,
1.1516 + BoundsCheckInfo,
1.1517 + DefaultHasher<uint32_t>,
1.1518 + IonAllocPolicy> BoundsCheckMap;
1.1519 +
1.1520 +// Compute a hash for bounds checks which ignores constant offsets in the index.
1.1521 +static HashNumber
1.1522 +BoundsCheckHashIgnoreOffset(MBoundsCheck *check)
1.1523 +{
1.1524 + SimpleLinearSum indexSum = ExtractLinearSum(check->index());
1.1525 + uintptr_t index = indexSum.term ? uintptr_t(indexSum.term) : 0;
1.1526 + uintptr_t length = uintptr_t(check->length());
1.1527 + return index ^ length;
1.1528 +}
1.1529 +
1.1530 +static MBoundsCheck *
1.1531 +FindDominatingBoundsCheck(BoundsCheckMap &checks, MBoundsCheck *check, size_t index)
1.1532 +{
1.1533 + // See the comment in ValueNumberer::findDominatingDef.
1.1534 + HashNumber hash = BoundsCheckHashIgnoreOffset(check);
1.1535 + BoundsCheckMap::Ptr p = checks.lookup(hash);
1.1536 + if (!p || index > p->value().validUntil) {
1.1537 + // We didn't find a dominating bounds check.
1.1538 + BoundsCheckInfo info;
1.1539 + info.check = check;
1.1540 + info.validUntil = index + check->block()->numDominated();
1.1541 +
1.1542 + if(!checks.put(hash, info))
1.1543 + return nullptr;
1.1544 +
1.1545 + return check;
1.1546 + }
1.1547 +
1.1548 + return p->value().check;
1.1549 +}
1.1550 +
1.1551 +// Extract a linear sum from ins, if possible (otherwise giving the sum 'ins + 0').
1.1552 +SimpleLinearSum
1.1553 +jit::ExtractLinearSum(MDefinition *ins)
1.1554 +{
1.1555 + if (ins->isBeta())
1.1556 + ins = ins->getOperand(0);
1.1557 +
1.1558 + if (ins->type() != MIRType_Int32)
1.1559 + return SimpleLinearSum(ins, 0);
1.1560 +
1.1561 + if (ins->isConstant()) {
1.1562 + const Value &v = ins->toConstant()->value();
1.1563 + JS_ASSERT(v.isInt32());
1.1564 + return SimpleLinearSum(nullptr, v.toInt32());
1.1565 + } else if (ins->isAdd() || ins->isSub()) {
1.1566 + MDefinition *lhs = ins->getOperand(0);
1.1567 + MDefinition *rhs = ins->getOperand(1);
1.1568 + if (lhs->type() == MIRType_Int32 && rhs->type() == MIRType_Int32) {
1.1569 + SimpleLinearSum lsum = ExtractLinearSum(lhs);
1.1570 + SimpleLinearSum rsum = ExtractLinearSum(rhs);
1.1571 +
1.1572 + if (lsum.term && rsum.term)
1.1573 + return SimpleLinearSum(ins, 0);
1.1574 +
1.1575 + // Check if this is of the form <SUM> + n, n + <SUM> or <SUM> - n.
1.1576 + if (ins->isAdd()) {
1.1577 + int32_t constant;
1.1578 + if (!SafeAdd(lsum.constant, rsum.constant, &constant))
1.1579 + return SimpleLinearSum(ins, 0);
1.1580 + return SimpleLinearSum(lsum.term ? lsum.term : rsum.term, constant);
1.1581 + } else if (lsum.term) {
1.1582 + int32_t constant;
1.1583 + if (!SafeSub(lsum.constant, rsum.constant, &constant))
1.1584 + return SimpleLinearSum(ins, 0);
1.1585 + return SimpleLinearSum(lsum.term, constant);
1.1586 + }
1.1587 + }
1.1588 + }
1.1589 +
1.1590 + return SimpleLinearSum(ins, 0);
1.1591 +}
1.1592 +
1.1593 +// Extract a linear inequality holding when a boolean test goes in the
1.1594 +// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).
1.1595 +bool
1.1596 +jit::ExtractLinearInequality(MTest *test, BranchDirection direction,
1.1597 + SimpleLinearSum *plhs, MDefinition **prhs, bool *plessEqual)
1.1598 +{
1.1599 + if (!test->getOperand(0)->isCompare())
1.1600 + return false;
1.1601 +
1.1602 + MCompare *compare = test->getOperand(0)->toCompare();
1.1603 +
1.1604 + MDefinition *lhs = compare->getOperand(0);
1.1605 + MDefinition *rhs = compare->getOperand(1);
1.1606 +
1.1607 + // TODO: optimize Compare_UInt32
1.1608 + if (!compare->isInt32Comparison())
1.1609 + return false;
1.1610 +
1.1611 + JS_ASSERT(lhs->type() == MIRType_Int32);
1.1612 + JS_ASSERT(rhs->type() == MIRType_Int32);
1.1613 +
1.1614 + JSOp jsop = compare->jsop();
1.1615 + if (direction == FALSE_BRANCH)
1.1616 + jsop = NegateCompareOp(jsop);
1.1617 +
1.1618 + SimpleLinearSum lsum = ExtractLinearSum(lhs);
1.1619 + SimpleLinearSum rsum = ExtractLinearSum(rhs);
1.1620 +
1.1621 + if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant))
1.1622 + return false;
1.1623 +
1.1624 + // Normalize operations to use <= or >=.
1.1625 + switch (jsop) {
1.1626 + case JSOP_LE:
1.1627 + *plessEqual = true;
1.1628 + break;
1.1629 + case JSOP_LT:
1.1630 + /* x < y ==> x + 1 <= y */
1.1631 + if (!SafeAdd(lsum.constant, 1, &lsum.constant))
1.1632 + return false;
1.1633 + *plessEqual = true;
1.1634 + break;
1.1635 + case JSOP_GE:
1.1636 + *plessEqual = false;
1.1637 + break;
1.1638 + case JSOP_GT:
1.1639 + /* x > y ==> x - 1 >= y */
1.1640 + if (!SafeSub(lsum.constant, 1, &lsum.constant))
1.1641 + return false;
1.1642 + *plessEqual = false;
1.1643 + break;
1.1644 + default:
1.1645 + return false;
1.1646 + }
1.1647 +
1.1648 + *plhs = lsum;
1.1649 + *prhs = rsum.term;
1.1650 +
1.1651 + return true;
1.1652 +}
1.1653 +
1.1654 +static bool
1.1655 +TryEliminateBoundsCheck(BoundsCheckMap &checks, size_t blockIndex, MBoundsCheck *dominated, bool *eliminated)
1.1656 +{
1.1657 + JS_ASSERT(!*eliminated);
1.1658 +
1.1659 + // Replace all uses of the bounds check with the actual index.
1.1660 + // This is (a) necessary, because we can coalesce two different
1.1661 + // bounds checks and would otherwise use the wrong index and
1.1662 + // (b) helps register allocation. Note that this is safe since
1.1663 + // no other pass after bounds check elimination moves instructions.
1.1664 + dominated->replaceAllUsesWith(dominated->index());
1.1665 +
1.1666 + if (!dominated->isMovable())
1.1667 + return true;
1.1668 +
1.1669 + MBoundsCheck *dominating = FindDominatingBoundsCheck(checks, dominated, blockIndex);
1.1670 + if (!dominating)
1.1671 + return false;
1.1672 +
1.1673 + if (dominating == dominated) {
1.1674 + // We didn't find a dominating bounds check.
1.1675 + return true;
1.1676 + }
1.1677 +
1.1678 + // We found two bounds checks with the same hash number, but we still have
1.1679 + // to make sure the lengths and index terms are equal.
1.1680 + if (dominating->length() != dominated->length())
1.1681 + return true;
1.1682 +
1.1683 + SimpleLinearSum sumA = ExtractLinearSum(dominating->index());
1.1684 + SimpleLinearSum sumB = ExtractLinearSum(dominated->index());
1.1685 +
1.1686 + // Both terms should be nullptr or the same definition.
1.1687 + if (sumA.term != sumB.term)
1.1688 + return true;
1.1689 +
1.1690 + // This bounds check is redundant.
1.1691 + *eliminated = true;
1.1692 +
1.1693 + // Normalize the ranges according to the constant offsets in the two indexes.
1.1694 + int32_t minimumA, maximumA, minimumB, maximumB;
1.1695 + if (!SafeAdd(sumA.constant, dominating->minimum(), &minimumA) ||
1.1696 + !SafeAdd(sumA.constant, dominating->maximum(), &maximumA) ||
1.1697 + !SafeAdd(sumB.constant, dominated->minimum(), &minimumB) ||
1.1698 + !SafeAdd(sumB.constant, dominated->maximum(), &maximumB))
1.1699 + {
1.1700 + return false;
1.1701 + }
1.1702 +
1.1703 + // Update the dominating check to cover both ranges, denormalizing the
1.1704 + // result per the constant offset in the index.
1.1705 + int32_t newMinimum, newMaximum;
1.1706 + if (!SafeSub(Min(minimumA, minimumB), sumA.constant, &newMinimum) ||
1.1707 + !SafeSub(Max(maximumA, maximumB), sumA.constant, &newMaximum))
1.1708 + {
1.1709 + return false;
1.1710 + }
1.1711 +
1.1712 + dominating->setMinimum(newMinimum);
1.1713 + dominating->setMaximum(newMaximum);
1.1714 + return true;
1.1715 +}
1.1716 +
1.1717 +static void
1.1718 +TryEliminateTypeBarrierFromTest(MTypeBarrier *barrier, bool filtersNull, bool filtersUndefined,
1.1719 + MTest *test, BranchDirection direction, bool *eliminated)
1.1720 +{
1.1721 + JS_ASSERT(filtersNull || filtersUndefined);
1.1722 +
1.1723 + // Watch for code patterns similar to 'if (x.f) { ... = x.f }'. If x.f
1.1724 + // is either an object or null/undefined, there will be a type barrier on
1.1725 + // the latter read as the null/undefined value is never realized there.
1.1726 + // The type barrier can be eliminated, however, by looking at tests
1.1727 + // performed on the result of the first operation that filter out all
1.1728 + // types that have been seen in the first access but not the second.
1.1729 +
1.1730 + // A test 'if (x.f)' filters both null and undefined.
1.1731 +
1.1732 + // Disregard the possible unbox added before the Typebarrier for checking.
1.1733 + MDefinition *input = barrier->input();
1.1734 + MUnbox *inputUnbox = nullptr;
1.1735 + if (input->isUnbox() && input->toUnbox()->mode() != MUnbox::Fallible) {
1.1736 + inputUnbox = input->toUnbox();
1.1737 + input = inputUnbox->input();
1.1738 + }
1.1739 +
1.1740 + MDefinition *subject = nullptr;
1.1741 + bool removeUndefined;
1.1742 + bool removeNull;
1.1743 + test->filtersUndefinedOrNull(direction == TRUE_BRANCH, &subject, &removeUndefined, &removeNull);
1.1744 +
1.1745 + // The Test doesn't filter undefined nor null.
1.1746 + if (!subject)
1.1747 + return;
1.1748 +
1.1749 + // Make sure the subject equals the input to the TypeBarrier.
1.1750 + if (subject != input)
1.1751 + return;
1.1752 +
1.1753 + // When the TypeBarrier filters undefined, the test must at least also do,
1.1754 + // this, before the TypeBarrier can get removed.
1.1755 + if (!removeUndefined && filtersUndefined)
1.1756 + return;
1.1757 +
1.1758 + // When the TypeBarrier filters null, the test must at least also do,
1.1759 + // this, before the TypeBarrier can get removed.
1.1760 + if (!removeNull && filtersNull)
1.1761 + return;
1.1762 +
1.1763 + // Eliminate the TypeBarrier. The possible TypeBarrier unboxing is kept,
1.1764 + // but made infallible.
1.1765 + *eliminated = true;
1.1766 + if (inputUnbox)
1.1767 + inputUnbox->makeInfallible();
1.1768 + barrier->replaceAllUsesWith(barrier->input());
1.1769 +}
1.1770 +
1.1771 +static bool
1.1772 +TryEliminateTypeBarrier(MTypeBarrier *barrier, bool *eliminated)
1.1773 +{
1.1774 + JS_ASSERT(!*eliminated);
1.1775 +
1.1776 + const types::TemporaryTypeSet *barrierTypes = barrier->resultTypeSet();
1.1777 + const types::TemporaryTypeSet *inputTypes = barrier->input()->resultTypeSet();
1.1778 +
1.1779 + // Disregard the possible unbox added before the Typebarrier.
1.1780 + if (barrier->input()->isUnbox() && barrier->input()->toUnbox()->mode() != MUnbox::Fallible)
1.1781 + inputTypes = barrier->input()->toUnbox()->input()->resultTypeSet();
1.1782 +
1.1783 + if (!barrierTypes || !inputTypes)
1.1784 + return true;
1.1785 +
1.1786 + bool filtersNull = barrierTypes->filtersType(inputTypes, types::Type::NullType());
1.1787 + bool filtersUndefined = barrierTypes->filtersType(inputTypes, types::Type::UndefinedType());
1.1788 +
1.1789 + if (!filtersNull && !filtersUndefined)
1.1790 + return true;
1.1791 +
1.1792 + MBasicBlock *block = barrier->block();
1.1793 + while (true) {
1.1794 + BranchDirection direction;
1.1795 + MTest *test = block->immediateDominatorBranch(&direction);
1.1796 +
1.1797 + if (test) {
1.1798 + TryEliminateTypeBarrierFromTest(barrier, filtersNull, filtersUndefined,
1.1799 + test, direction, eliminated);
1.1800 + }
1.1801 +
1.1802 + MBasicBlock *previous = block->immediateDominator();
1.1803 + if (previous == block)
1.1804 + break;
1.1805 + block = previous;
1.1806 + }
1.1807 +
1.1808 + return true;
1.1809 +}
1.1810 +
1.1811 +// Eliminate checks which are redundant given each other or other instructions.
1.1812 +//
1.1813 +// A type barrier is considered redundant if all missing types have been tested
1.1814 +// for by earlier control instructions.
1.1815 +//
1.1816 +// A bounds check is considered redundant if it's dominated by another bounds
1.1817 +// check with the same length and the indexes differ by only a constant amount.
1.1818 +// In this case we eliminate the redundant bounds check and update the other one
1.1819 +// to cover the ranges of both checks.
1.1820 +//
1.1821 +// Bounds checks are added to a hash map and since the hash function ignores
1.1822 +// differences in constant offset, this offers a fast way to find redundant
1.1823 +// checks.
1.1824 +bool
1.1825 +jit::EliminateRedundantChecks(MIRGraph &graph)
1.1826 +{
1.1827 + BoundsCheckMap checks(graph.alloc());
1.1828 +
1.1829 + if (!checks.init())
1.1830 + return false;
1.1831 +
1.1832 + // Stack for pre-order CFG traversal.
1.1833 + Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(graph.alloc());
1.1834 +
1.1835 + // The index of the current block in the CFG traversal.
1.1836 + size_t index = 0;
1.1837 +
1.1838 + // Add all self-dominating blocks to the worklist.
1.1839 + // This includes all roots. Order does not matter.
1.1840 + for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
1.1841 + MBasicBlock *block = *i;
1.1842 + if (block->immediateDominator() == block) {
1.1843 + if (!worklist.append(block))
1.1844 + return false;
1.1845 + }
1.1846 + }
1.1847 +
1.1848 + // Starting from each self-dominating block, traverse the CFG in pre-order.
1.1849 + while (!worklist.empty()) {
1.1850 + MBasicBlock *block = worklist.popCopy();
1.1851 +
1.1852 + // Add all immediate dominators to the front of the worklist.
1.1853 + if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
1.1854 + block->immediatelyDominatedBlocksEnd())) {
1.1855 + return false;
1.1856 + }
1.1857 +
1.1858 + for (MDefinitionIterator iter(block); iter; ) {
1.1859 + bool eliminated = false;
1.1860 +
1.1861 + if (iter->isBoundsCheck()) {
1.1862 + if (!TryEliminateBoundsCheck(checks, index, iter->toBoundsCheck(), &eliminated))
1.1863 + return false;
1.1864 + } else if (iter->isTypeBarrier()) {
1.1865 + if (!TryEliminateTypeBarrier(iter->toTypeBarrier(), &eliminated))
1.1866 + return false;
1.1867 + } else if (iter->isConvertElementsToDoubles()) {
1.1868 + // Now that code motion passes have finished, replace any
1.1869 + // ConvertElementsToDoubles with the actual elements.
1.1870 + MConvertElementsToDoubles *ins = iter->toConvertElementsToDoubles();
1.1871 + ins->replaceAllUsesWith(ins->elements());
1.1872 + }
1.1873 +
1.1874 + if (eliminated)
1.1875 + iter = block->discardDefAt(iter);
1.1876 + else
1.1877 + iter++;
1.1878 + }
1.1879 + index++;
1.1880 + }
1.1881 +
1.1882 + JS_ASSERT(index == graph.numBlocks());
1.1883 + return true;
1.1884 +}
1.1885 +
1.1886 +// If the given block contains a goto and nothing interesting before that,
1.1887 +// return the goto. Return nullptr otherwise.
1.1888 +static LGoto *
1.1889 +FindLeadingGoto(LBlock *bb)
1.1890 +{
1.1891 + for (LInstructionIterator ins(bb->begin()); ins != bb->end(); ins++) {
1.1892 + // Ignore labels.
1.1893 + if (ins->isLabel())
1.1894 + continue;
1.1895 + // If we have a goto, we're good to go.
1.1896 + if (ins->isGoto())
1.1897 + return ins->toGoto();
1.1898 + break;
1.1899 + }
1.1900 + return nullptr;
1.1901 +}
1.1902 +
1.1903 +// Eliminate blocks containing nothing interesting besides gotos. These are
1.1904 +// often created by optimizer, which splits all critical edges. If these
1.1905 +// splits end up being unused after optimization and register allocation,
1.1906 +// fold them back away to avoid unnecessary branching.
1.1907 +bool
1.1908 +jit::UnsplitEdges(LIRGraph *lir)
1.1909 +{
1.1910 + for (size_t i = 0; i < lir->numBlocks(); i++) {
1.1911 + LBlock *bb = lir->getBlock(i);
1.1912 + MBasicBlock *mirBlock = bb->mir();
1.1913 +
1.1914 + // Renumber the MIR blocks as we go, since we may remove some.
1.1915 + mirBlock->setId(i);
1.1916 +
1.1917 + // Register allocation is done by this point, so we don't need the phis
1.1918 + // anymore. Clear them to avoid needed to keep them current as we edit
1.1919 + // the CFG.
1.1920 + bb->clearPhis();
1.1921 + mirBlock->discardAllPhis();
1.1922 +
1.1923 + // First make sure the MIR block looks sane. Some of these checks may be
1.1924 + // over-conservative, but we're attempting to keep everything in MIR
1.1925 + // current as we modify the LIR, so only proceed if the MIR is simple.
1.1926 + if (mirBlock->numPredecessors() == 0 || mirBlock->numSuccessors() != 1 ||
1.1927 + !mirBlock->begin()->isGoto())
1.1928 + {
1.1929 + continue;
1.1930 + }
1.1931 +
1.1932 + // The MIR block is empty, but check the LIR block too (in case the
1.1933 + // register allocator inserted spill code there, or whatever).
1.1934 + LGoto *theGoto = FindLeadingGoto(bb);
1.1935 + if (!theGoto)
1.1936 + continue;
1.1937 + MBasicBlock *target = theGoto->target();
1.1938 + if (target == mirBlock || target != mirBlock->getSuccessor(0))
1.1939 + continue;
1.1940 +
1.1941 + // If we haven't yet cleared the phis for the successor, do so now so
1.1942 + // that the CFG manipulation routines don't trip over them.
1.1943 + if (!target->phisEmpty()) {
1.1944 + target->discardAllPhis();
1.1945 + target->lir()->clearPhis();
1.1946 + }
1.1947 +
1.1948 + // Edit the CFG to remove lir/mirBlock and reconnect all its edges.
1.1949 + for (size_t j = 0; j < mirBlock->numPredecessors(); j++) {
1.1950 + MBasicBlock *mirPred = mirBlock->getPredecessor(j);
1.1951 +
1.1952 + for (size_t k = 0; k < mirPred->numSuccessors(); k++) {
1.1953 + if (mirPred->getSuccessor(k) == mirBlock) {
1.1954 + mirPred->replaceSuccessor(k, target);
1.1955 + if (!target->addPredecessorWithoutPhis(mirPred))
1.1956 + return false;
1.1957 + }
1.1958 + }
1.1959 +
1.1960 + LInstruction *predTerm = *mirPred->lir()->rbegin();
1.1961 + for (size_t k = 0; k < predTerm->numSuccessors(); k++) {
1.1962 + if (predTerm->getSuccessor(k) == mirBlock)
1.1963 + predTerm->setSuccessor(k, target);
1.1964 + }
1.1965 + }
1.1966 + target->removePredecessor(mirBlock);
1.1967 +
1.1968 + // Zap the block.
1.1969 + lir->removeBlock(i);
1.1970 + lir->mir().removeBlock(mirBlock);
1.1971 + --i;
1.1972 + }
1.1973 +
1.1974 + return true;
1.1975 +}
1.1976 +
1.1977 +bool
1.1978 +LinearSum::multiply(int32_t scale)
1.1979 +{
1.1980 + for (size_t i = 0; i < terms_.length(); i++) {
1.1981 + if (!SafeMul(scale, terms_[i].scale, &terms_[i].scale))
1.1982 + return false;
1.1983 + }
1.1984 + return SafeMul(scale, constant_, &constant_);
1.1985 +}
1.1986 +
1.1987 +bool
1.1988 +LinearSum::add(const LinearSum &other)
1.1989 +{
1.1990 + for (size_t i = 0; i < other.terms_.length(); i++) {
1.1991 + if (!add(other.terms_[i].term, other.terms_[i].scale))
1.1992 + return false;
1.1993 + }
1.1994 + return add(other.constant_);
1.1995 +}
1.1996 +
1.1997 +bool
1.1998 +LinearSum::add(MDefinition *term, int32_t scale)
1.1999 +{
1.2000 + JS_ASSERT(term);
1.2001 +
1.2002 + if (scale == 0)
1.2003 + return true;
1.2004 +
1.2005 + if (term->isConstant()) {
1.2006 + int32_t constant = term->toConstant()->value().toInt32();
1.2007 + if (!SafeMul(constant, scale, &constant))
1.2008 + return false;
1.2009 + return add(constant);
1.2010 + }
1.2011 +
1.2012 + for (size_t i = 0; i < terms_.length(); i++) {
1.2013 + if (term == terms_[i].term) {
1.2014 + if (!SafeAdd(scale, terms_[i].scale, &terms_[i].scale))
1.2015 + return false;
1.2016 + if (terms_[i].scale == 0) {
1.2017 + terms_[i] = terms_.back();
1.2018 + terms_.popBack();
1.2019 + }
1.2020 + return true;
1.2021 + }
1.2022 + }
1.2023 +
1.2024 + terms_.append(LinearTerm(term, scale));
1.2025 + return true;
1.2026 +}
1.2027 +
1.2028 +bool
1.2029 +LinearSum::add(int32_t constant)
1.2030 +{
1.2031 + return SafeAdd(constant, constant_, &constant_);
1.2032 +}
1.2033 +
1.2034 +void
1.2035 +LinearSum::print(Sprinter &sp) const
1.2036 +{
1.2037 + for (size_t i = 0; i < terms_.length(); i++) {
1.2038 + int32_t scale = terms_[i].scale;
1.2039 + int32_t id = terms_[i].term->id();
1.2040 + JS_ASSERT(scale);
1.2041 + if (scale > 0) {
1.2042 + if (i)
1.2043 + sp.printf("+");
1.2044 + if (scale == 1)
1.2045 + sp.printf("#%d", id);
1.2046 + else
1.2047 + sp.printf("%d*#%d", scale, id);
1.2048 + } else if (scale == -1) {
1.2049 + sp.printf("-#%d", id);
1.2050 + } else {
1.2051 + sp.printf("%d*#%d", scale, id);
1.2052 + }
1.2053 + }
1.2054 + if (constant_ > 0)
1.2055 + sp.printf("+%d", constant_);
1.2056 + else if (constant_ < 0)
1.2057 + sp.printf("%d", constant_);
1.2058 +}
1.2059 +
1.2060 +void
1.2061 +LinearSum::dump(FILE *fp) const
1.2062 +{
1.2063 + Sprinter sp(GetIonContext()->cx);
1.2064 + sp.init();
1.2065 + print(sp);
1.2066 + fprintf(fp, "%s\n", sp.string());
1.2067 +}
1.2068 +
1.2069 +void
1.2070 +LinearSum::dump() const
1.2071 +{
1.2072 + dump(stderr);
1.2073 +}
1.2074 +
1.2075 +static bool
1.2076 +AnalyzePoppedThis(JSContext *cx, types::TypeObject *type,
1.2077 + MDefinition *thisValue, MInstruction *ins, bool definitelyExecuted,
1.2078 + HandleObject baseobj,
1.2079 + Vector<types::TypeNewScript::Initializer> *initializerList,
1.2080 + Vector<PropertyName *> *accessedProperties,
1.2081 + bool *phandled)
1.2082 +{
1.2083 + // Determine the effect that a use of the |this| value when calling |new|
1.2084 + // on a script has on the properties definitely held by the new object.
1.2085 +
1.2086 + if (ins->isCallSetProperty()) {
1.2087 + MCallSetProperty *setprop = ins->toCallSetProperty();
1.2088 +
1.2089 + if (setprop->object() != thisValue)
1.2090 + return true;
1.2091 +
1.2092 + // Don't use GetAtomId here, we need to watch for SETPROP on
1.2093 + // integer properties and bail out. We can't mark the aggregate
1.2094 + // JSID_VOID type property as being in a definite slot.
1.2095 + if (setprop->name() == cx->names().prototype ||
1.2096 + setprop->name() == cx->names().proto ||
1.2097 + setprop->name() == cx->names().constructor)
1.2098 + {
1.2099 + return true;
1.2100 + }
1.2101 +
1.2102 + // Ignore assignments to properties that were already written to.
1.2103 + if (baseobj->nativeLookup(cx, NameToId(setprop->name()))) {
1.2104 + *phandled = true;
1.2105 + return true;
1.2106 + }
1.2107 +
1.2108 + // Don't add definite properties for properties that were already
1.2109 + // read in the constructor.
1.2110 + for (size_t i = 0; i < accessedProperties->length(); i++) {
1.2111 + if ((*accessedProperties)[i] == setprop->name())
1.2112 + return true;
1.2113 + }
1.2114 +
1.2115 + // Don't add definite properties to an object which won't fit in its
1.2116 + // fixed slots.
1.2117 + if (GetGCKindSlots(gc::GetGCObjectKind(baseobj->slotSpan() + 1)) <= baseobj->slotSpan())
1.2118 + return true;
1.2119 +
1.2120 + // Assignments to new properties must always execute.
1.2121 + if (!definitelyExecuted)
1.2122 + return true;
1.2123 +
1.2124 + RootedId id(cx, NameToId(setprop->name()));
1.2125 + if (!types::AddClearDefiniteGetterSetterForPrototypeChain(cx, type, id)) {
1.2126 + // The prototype chain already contains a getter/setter for this
1.2127 + // property, or type information is too imprecise.
1.2128 + return true;
1.2129 + }
1.2130 +
1.2131 + DebugOnly<unsigned> slotSpan = baseobj->slotSpan();
1.2132 + if (!DefineNativeProperty(cx, baseobj, id, UndefinedHandleValue, nullptr, nullptr,
1.2133 + JSPROP_ENUMERATE))
1.2134 + {
1.2135 + return false;
1.2136 + }
1.2137 + JS_ASSERT(baseobj->slotSpan() != slotSpan);
1.2138 + JS_ASSERT(!baseobj->inDictionaryMode());
1.2139 +
1.2140 + Vector<MResumePoint *> callerResumePoints(cx);
1.2141 + MBasicBlock *block = ins->block();
1.2142 + for (MResumePoint *rp = block->callerResumePoint();
1.2143 + rp;
1.2144 + block = rp->block(), rp = block->callerResumePoint())
1.2145 + {
1.2146 + JSScript *script = rp->block()->info().script();
1.2147 + if (!types::AddClearDefiniteFunctionUsesInScript(cx, type, script, block->info().script()))
1.2148 + return true;
1.2149 + if (!callerResumePoints.append(rp))
1.2150 + return false;
1.2151 + }
1.2152 +
1.2153 + for (int i = callerResumePoints.length() - 1; i >= 0; i--) {
1.2154 + MResumePoint *rp = callerResumePoints[i];
1.2155 + JSScript *script = rp->block()->info().script();
1.2156 + types::TypeNewScript::Initializer entry(types::TypeNewScript::Initializer::SETPROP_FRAME,
1.2157 + script->pcToOffset(rp->pc()));
1.2158 + if (!initializerList->append(entry))
1.2159 + return false;
1.2160 + }
1.2161 +
1.2162 + JSScript *script = ins->block()->info().script();
1.2163 + types::TypeNewScript::Initializer entry(types::TypeNewScript::Initializer::SETPROP,
1.2164 + script->pcToOffset(setprop->resumePoint()->pc()));
1.2165 + if (!initializerList->append(entry))
1.2166 + return false;
1.2167 +
1.2168 + *phandled = true;
1.2169 + return true;
1.2170 + }
1.2171 +
1.2172 + if (ins->isCallGetProperty()) {
1.2173 + MCallGetProperty *get = ins->toCallGetProperty();
1.2174 +
1.2175 + /*
1.2176 + * Properties can be read from the 'this' object if the following hold:
1.2177 + *
1.2178 + * - The read is not on a getter along the prototype chain, which
1.2179 + * could cause 'this' to escape.
1.2180 + *
1.2181 + * - The accessed property is either already a definite property or
1.2182 + * is not later added as one. Since the definite properties are
1.2183 + * added to the object at the point of its creation, reading a
1.2184 + * definite property before it is assigned could incorrectly hit.
1.2185 + */
1.2186 + RootedId id(cx, NameToId(get->name()));
1.2187 + if (!baseobj->nativeLookup(cx, id) && !accessedProperties->append(get->name()))
1.2188 + return false;
1.2189 +
1.2190 + if (!types::AddClearDefiniteGetterSetterForPrototypeChain(cx, type, id)) {
1.2191 + // The |this| value can escape if any property reads it does go
1.2192 + // through a getter.
1.2193 + return true;
1.2194 + }
1.2195 +
1.2196 + *phandled = true;
1.2197 + return true;
1.2198 + }
1.2199 +
1.2200 + if (ins->isPostWriteBarrier()) {
1.2201 + *phandled = true;
1.2202 + return true;
1.2203 + }
1.2204 +
1.2205 + return true;
1.2206 +}
1.2207 +
1.2208 +static int
1.2209 +CmpInstructions(const void *a, const void *b)
1.2210 +{
1.2211 + return (*static_cast<MInstruction * const *>(a))->id() -
1.2212 + (*static_cast<MInstruction * const *>(b))->id();
1.2213 +}
1.2214 +
1.2215 +bool
1.2216 +jit::AnalyzeNewScriptProperties(JSContext *cx, JSFunction *fun,
1.2217 + types::TypeObject *type, HandleObject baseobj,
1.2218 + Vector<types::TypeNewScript::Initializer> *initializerList)
1.2219 +{
1.2220 + JS_ASSERT(cx->compartment()->activeAnalysis);
1.2221 +
1.2222 + // When invoking 'new' on the specified script, try to find some properties
1.2223 + // which will definitely be added to the created object before it has a
1.2224 + // chance to escape and be accessed elsewhere.
1.2225 +
1.2226 + RootedScript script(cx, fun->getOrCreateScript(cx));
1.2227 + if (!script)
1.2228 + return false;
1.2229 +
1.2230 + if (!jit::IsIonEnabled(cx) || !jit::IsBaselineEnabled(cx) ||
1.2231 + !script->compileAndGo() || !script->canBaselineCompile())
1.2232 + {
1.2233 + return true;
1.2234 + }
1.2235 +
1.2236 + static const uint32_t MAX_SCRIPT_SIZE = 2000;
1.2237 + if (script->length() > MAX_SCRIPT_SIZE)
1.2238 + return true;
1.2239 +
1.2240 + Vector<PropertyName *> accessedProperties(cx);
1.2241 +
1.2242 + LifoAlloc alloc(types::TypeZone::TYPE_LIFO_ALLOC_PRIMARY_CHUNK_SIZE);
1.2243 +
1.2244 + TempAllocator temp(&alloc);
1.2245 + IonContext ictx(cx, &temp);
1.2246 +
1.2247 + if (!cx->compartment()->ensureJitCompartmentExists(cx))
1.2248 + return false;
1.2249 +
1.2250 + if (!script->hasBaselineScript()) {
1.2251 + MethodStatus status = BaselineCompile(cx, script);
1.2252 + if (status == Method_Error)
1.2253 + return false;
1.2254 + if (status != Method_Compiled)
1.2255 + return true;
1.2256 + }
1.2257 +
1.2258 + types::TypeScript::SetThis(cx, script, types::Type::ObjectType(type));
1.2259 +
1.2260 + MIRGraph graph(&temp);
1.2261 + CompileInfo info(script, fun,
1.2262 + /* osrPc = */ nullptr, /* constructing = */ false,
1.2263 + DefinitePropertiesAnalysis,
1.2264 + script->needsArgsObj());
1.2265 +
1.2266 + AutoTempAllocatorRooter root(cx, &temp);
1.2267 +
1.2268 + const OptimizationInfo *optimizationInfo = js_IonOptimizations.get(Optimization_Normal);
1.2269 +
1.2270 + types::CompilerConstraintList *constraints = types::NewCompilerConstraintList(temp);
1.2271 + if (!constraints) {
1.2272 + js_ReportOutOfMemory(cx);
1.2273 + return false;
1.2274 + }
1.2275 +
1.2276 + BaselineInspector inspector(script);
1.2277 + const JitCompileOptions options(cx);
1.2278 +
1.2279 + IonBuilder builder(cx, CompileCompartment::get(cx->compartment()), options, &temp, &graph, constraints,
1.2280 + &inspector, &info, optimizationInfo, /* baselineFrame = */ nullptr);
1.2281 +
1.2282 + if (!builder.build()) {
1.2283 + if (builder.abortReason() == AbortReason_Alloc)
1.2284 + return false;
1.2285 + return true;
1.2286 + }
1.2287 +
1.2288 + types::FinishDefinitePropertiesAnalysis(cx, constraints);
1.2289 +
1.2290 + if (!SplitCriticalEdges(graph))
1.2291 + return false;
1.2292 +
1.2293 + if (!RenumberBlocks(graph))
1.2294 + return false;
1.2295 +
1.2296 + if (!BuildDominatorTree(graph))
1.2297 + return false;
1.2298 +
1.2299 + if (!EliminatePhis(&builder, graph, AggressiveObservability))
1.2300 + return false;
1.2301 +
1.2302 + MDefinition *thisValue = graph.begin()->getSlot(info.thisSlot());
1.2303 +
1.2304 + // Get a list of instructions using the |this| value in the order they
1.2305 + // appear in the graph.
1.2306 + Vector<MInstruction *> instructions(cx);
1.2307 +
1.2308 + for (MUseDefIterator uses(thisValue); uses; uses++) {
1.2309 + MDefinition *use = uses.def();
1.2310 +
1.2311 + // Don't track |this| through assignments to phis.
1.2312 + if (!use->isInstruction())
1.2313 + return true;
1.2314 +
1.2315 + if (!instructions.append(use->toInstruction()))
1.2316 + return false;
1.2317 + }
1.2318 +
1.2319 + // Sort the instructions to visit in increasing order.
1.2320 + qsort(instructions.begin(), instructions.length(),
1.2321 + sizeof(MInstruction *), CmpInstructions);
1.2322 +
1.2323 + // Find all exit blocks in the graph.
1.2324 + Vector<MBasicBlock *> exitBlocks(cx);
1.2325 + for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
1.2326 + if (!block->numSuccessors() && !exitBlocks.append(*block))
1.2327 + return false;
1.2328 + }
1.2329 +
1.2330 + for (size_t i = 0; i < instructions.length(); i++) {
1.2331 + MInstruction *ins = instructions[i];
1.2332 +
1.2333 + // Track whether the use of |this| is in unconditional code, i.e.
1.2334 + // the block dominates all graph exits.
1.2335 + bool definitelyExecuted = true;
1.2336 + for (size_t i = 0; i < exitBlocks.length(); i++) {
1.2337 + for (MBasicBlock *exit = exitBlocks[i];
1.2338 + exit != ins->block();
1.2339 + exit = exit->immediateDominator())
1.2340 + {
1.2341 + if (exit == exit->immediateDominator()) {
1.2342 + definitelyExecuted = false;
1.2343 + break;
1.2344 + }
1.2345 + }
1.2346 + }
1.2347 +
1.2348 + // Also check to see if the instruction is inside a loop body. Even if
1.2349 + // an access will always execute in the script, if it executes multiple
1.2350 + // times then we can get confused when rolling back objects while
1.2351 + // clearing the new script information.
1.2352 + if (ins->block()->loopDepth() != 0)
1.2353 + definitelyExecuted = false;
1.2354 +
1.2355 + bool handled = false;
1.2356 + if (!AnalyzePoppedThis(cx, type, thisValue, ins, definitelyExecuted,
1.2357 + baseobj, initializerList, &accessedProperties, &handled))
1.2358 + {
1.2359 + return false;
1.2360 + }
1.2361 + if (!handled)
1.2362 + return true;
1.2363 + }
1.2364 +
1.2365 + return true;
1.2366 +}
1.2367 +
1.2368 +static bool
1.2369 +ArgumentsUseCanBeLazy(JSContext *cx, JSScript *script, MInstruction *ins, size_t index)
1.2370 +{
1.2371 + // We can read the frame's arguments directly for f.apply(x, arguments).
1.2372 + if (ins->isCall()) {
1.2373 + if (*ins->toCall()->resumePoint()->pc() == JSOP_FUNAPPLY &&
1.2374 + ins->toCall()->numActualArgs() == 2 &&
1.2375 + index == MCall::IndexOfArgument(1))
1.2376 + {
1.2377 + return true;
1.2378 + }
1.2379 + }
1.2380 +
1.2381 + // arguments[i] can read fp->canonicalActualArg(i) directly.
1.2382 + if (ins->isCallGetElement() && index == 0)
1.2383 + return true;
1.2384 +
1.2385 + // arguments.length length can read fp->numActualArgs() directly.
1.2386 + if (ins->isCallGetProperty() && index == 0 && ins->toCallGetProperty()->name() == cx->names().length)
1.2387 + return true;
1.2388 +
1.2389 + return false;
1.2390 +}
1.2391 +
1.2392 +bool
1.2393 +jit::AnalyzeArgumentsUsage(JSContext *cx, JSScript *scriptArg)
1.2394 +{
1.2395 + RootedScript script(cx, scriptArg);
1.2396 + types::AutoEnterAnalysis enter(cx);
1.2397 +
1.2398 + JS_ASSERT(!script->analyzedArgsUsage());
1.2399 +
1.2400 + // Treat the script as needing an arguments object until we determine it
1.2401 + // does not need one. This both allows us to easily see where the arguments
1.2402 + // object can escape through assignments to the function's named arguments,
1.2403 + // and also simplifies handling of early returns.
1.2404 + script->setNeedsArgsObj(true);
1.2405 +
1.2406 + if (!jit::IsIonEnabled(cx) || !script->compileAndGo())
1.2407 + return true;
1.2408 +
1.2409 + static const uint32_t MAX_SCRIPT_SIZE = 10000;
1.2410 + if (script->length() > MAX_SCRIPT_SIZE)
1.2411 + return true;
1.2412 +
1.2413 + if (!script->ensureHasTypes(cx))
1.2414 + return false;
1.2415 +
1.2416 + LifoAlloc alloc(types::TypeZone::TYPE_LIFO_ALLOC_PRIMARY_CHUNK_SIZE);
1.2417 +
1.2418 + TempAllocator temp(&alloc);
1.2419 + IonContext ictx(cx, &temp);
1.2420 +
1.2421 + if (!cx->compartment()->ensureJitCompartmentExists(cx))
1.2422 + return false;
1.2423 +
1.2424 + MIRGraph graph(&temp);
1.2425 + CompileInfo info(script, script->functionNonDelazifying(),
1.2426 + /* osrPc = */ nullptr, /* constructing = */ false,
1.2427 + ArgumentsUsageAnalysis,
1.2428 + /* needsArgsObj = */ true);
1.2429 +
1.2430 + AutoTempAllocatorRooter root(cx, &temp);
1.2431 +
1.2432 + const OptimizationInfo *optimizationInfo = js_IonOptimizations.get(Optimization_Normal);
1.2433 +
1.2434 + types::CompilerConstraintList *constraints = types::NewCompilerConstraintList(temp);
1.2435 + if (!constraints)
1.2436 + return false;
1.2437 +
1.2438 + BaselineInspector inspector(script);
1.2439 + const JitCompileOptions options(cx);
1.2440 +
1.2441 + IonBuilder builder(nullptr, CompileCompartment::get(cx->compartment()), options, &temp, &graph, constraints,
1.2442 + &inspector, &info, optimizationInfo, /* baselineFrame = */ nullptr);
1.2443 +
1.2444 + if (!builder.build()) {
1.2445 + if (builder.abortReason() == AbortReason_Alloc)
1.2446 + return false;
1.2447 + return true;
1.2448 + }
1.2449 +
1.2450 + if (!SplitCriticalEdges(graph))
1.2451 + return false;
1.2452 +
1.2453 + if (!RenumberBlocks(graph))
1.2454 + return false;
1.2455 +
1.2456 + if (!BuildDominatorTree(graph))
1.2457 + return false;
1.2458 +
1.2459 + if (!EliminatePhis(&builder, graph, AggressiveObservability))
1.2460 + return false;
1.2461 +
1.2462 + MDefinition *argumentsValue = graph.begin()->getSlot(info.argsObjSlot());
1.2463 +
1.2464 + for (MUseDefIterator uses(argumentsValue); uses; uses++) {
1.2465 + MDefinition *use = uses.def();
1.2466 +
1.2467 + // Don't track |arguments| through assignments to phis.
1.2468 + if (!use->isInstruction())
1.2469 + return true;
1.2470 +
1.2471 + if (!ArgumentsUseCanBeLazy(cx, script, use->toInstruction(), uses.index()))
1.2472 + return true;
1.2473 + }
1.2474 +
1.2475 + script->setNeedsArgsObj(false);
1.2476 + return true;
1.2477 +}
