michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- michael@0: * vim: set ts=8 sts=4 et sw=4 tw=99: michael@0: * This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: #include "mozilla/DebugOnly.h" michael@0: #include "mozilla/MathAlgorithms.h" michael@0: #include "mozilla/PodOperations.h" michael@0: michael@0: #include "jscntxt.h" michael@0: #include "jscompartment.h" michael@0: michael@0: #include "vm/Opcodes.h" michael@0: michael@0: #include "jsinferinlines.h" michael@0: #include "jsobjinlines.h" michael@0: #include "jsopcodeinlines.h" michael@0: michael@0: using mozilla::DebugOnly; michael@0: using mozilla::PodCopy; michael@0: using mozilla::PodZero; michael@0: using mozilla::FloorLog2; michael@0: michael@0: namespace js { michael@0: namespace analyze { michael@0: class LoopAnalysis; michael@0: } // namespace analyze michael@0: } // namespace js michael@0: michael@0: namespace mozilla { michael@0: michael@0: template <> struct IsPod : TrueType {}; michael@0: template <> struct IsPod : TrueType {}; michael@0: template <> struct IsPod : TrueType {}; michael@0: template <> struct IsPod : TrueType {}; michael@0: template <> struct IsPod : TrueType {}; michael@0: michael@0: } /* namespace mozilla */ michael@0: michael@0: namespace js { michael@0: namespace analyze { michael@0: michael@0: /* michael@0: * There are three analyses we can perform on a JSScript, outlined below. michael@0: * The results of all three are stored in ScriptAnalysis, but the analyses michael@0: * themselves can be performed separately. Along with type inference results, michael@0: * per-script analysis results are tied to the per-compartment analysis pool michael@0: * and are freed on every garbage collection. michael@0: * michael@0: * - Basic bytecode analysis. For each bytecode, determine the stack depth at michael@0: * that point and control flow information needed for compilation. Also does michael@0: * a defined-variables analysis to look for local variables which have uses michael@0: * before definitions. michael@0: * michael@0: * - Lifetime analysis. Makes a backwards pass over the script to approximate michael@0: * the regions where each variable is live, avoiding a full fixpointing michael@0: * live-variables pass. This is based on the algorithm described in: michael@0: * michael@0: * "Quality and Speed in Linear-scan Register Allocation" michael@0: * Traub et. al. michael@0: * PLDI, 1998 michael@0: * michael@0: * - SSA analysis of the script's variables and stack values. For each stack michael@0: * value popped and non-escaping local variable or argument read, determines michael@0: * which push(es) or write(s) produced that value. michael@0: * michael@0: * Intermediate type inference results are additionally stored here. The above michael@0: * analyses are independent from type inference. michael@0: */ michael@0: michael@0: /* Information about a bytecode instruction. */ michael@0: class Bytecode michael@0: { michael@0: friend class ScriptAnalysis; michael@0: michael@0: public: michael@0: Bytecode() { mozilla::PodZero(this); } michael@0: michael@0: /* --------- Bytecode analysis --------- */ michael@0: michael@0: /* Whether there are any incoming jumps to this instruction. */ michael@0: bool jumpTarget : 1; michael@0: michael@0: /* Whether there is fallthrough to this instruction from a non-branching instruction. */ michael@0: bool fallthrough : 1; michael@0: michael@0: /* Whether this instruction is the fall through point of a conditional jump. */ michael@0: bool jumpFallthrough : 1; michael@0: michael@0: /* michael@0: * Whether this instruction must always execute, unless the script throws michael@0: * an exception which it does not later catch. michael@0: */ michael@0: bool unconditional : 1; michael@0: michael@0: /* Whether this instruction has been analyzed to get its output defines and stack. */ michael@0: bool analyzed : 1; michael@0: michael@0: /* Whether this is a catch/finally entry point. */ michael@0: bool exceptionEntry : 1; michael@0: michael@0: /* Stack depth before this opcode. */ michael@0: uint32_t stackDepth; michael@0: michael@0: private: michael@0: michael@0: /* If this is a JSOP_LOOPHEAD or JSOP_LOOPENTRY, information about the loop. */ michael@0: LoopAnalysis *loop; michael@0: michael@0: /* --------- SSA analysis --------- */ michael@0: michael@0: /* Generated location of each value popped by this bytecode. */ michael@0: SSAValue *poppedValues; michael@0: michael@0: /* Points where values pushed or written by this bytecode are popped. */ michael@0: SSAUseChain **pushedUses; michael@0: michael@0: union { michael@0: /* michael@0: * If this is a join point (implies jumpTarget), any slots at this michael@0: * point which can have a different values than at the immediate michael@0: * predecessor in the bytecode. Array is terminated by an entry with michael@0: * a zero slot. michael@0: */ michael@0: SlotValue *newValues; michael@0: michael@0: /* michael@0: * Vector used during SSA analysis to store values in need of merging michael@0: * at this point. If this has incoming forward jumps and we have not michael@0: * yet reached this point, stores values for entries on the stack and michael@0: * for variables which have changed since the branch. If this is a loop michael@0: * head and we haven't reached the back edge yet, stores loop phi nodes michael@0: * for variables and entries live at the head of the loop. michael@0: */ michael@0: Vector *pendingValues; michael@0: }; michael@0: }; michael@0: michael@0: /* michael@0: * Information about the lifetime of a local or argument. These form a linked michael@0: * list describing successive intervals in the program where the variable's michael@0: * value may be live. At points in the script not in one of these segments michael@0: * (points in a 'lifetime hole'), the variable is dead and registers containing michael@0: * its type/payload can be discarded without needing to be synced. michael@0: */ michael@0: struct Lifetime michael@0: { michael@0: /* michael@0: * Start and end offsets of this lifetime. The variable is live at the michael@0: * beginning of every bytecode in this (inclusive) range. michael@0: */ michael@0: uint32_t start; michael@0: uint32_t end; michael@0: michael@0: /* michael@0: * In a loop body, endpoint to extend this lifetime with if the variable is michael@0: * live in the next iteration. michael@0: */ michael@0: uint32_t savedEnd; michael@0: michael@0: /* michael@0: * The start of this lifetime is a bytecode writing the variable. Each michael@0: * write to a variable is associated with a lifetime. michael@0: */ michael@0: bool write; michael@0: michael@0: /* Next lifetime. The variable is dead from this->end to next->start. */ michael@0: Lifetime *next; michael@0: michael@0: Lifetime(uint32_t offset, uint32_t savedEnd, Lifetime *next) michael@0: : start(offset), end(offset), savedEnd(savedEnd), michael@0: write(false), next(next) michael@0: {} michael@0: }; michael@0: michael@0: /* Basic information for a loop. */ michael@0: class LoopAnalysis michael@0: { michael@0: public: michael@0: /* Any loop this one is nested in. */ michael@0: LoopAnalysis *parent; michael@0: michael@0: /* Offset of the head of the loop. */ michael@0: uint32_t head; michael@0: michael@0: /* michael@0: * Offset of the unique jump going to the head of the loop. The code michael@0: * between the head and the backedge forms the loop body. michael@0: */ michael@0: uint32_t backedge; michael@0: }; michael@0: michael@0: /* Current lifetime information for a variable. */ michael@0: struct LifetimeVariable michael@0: { michael@0: /* If the variable is currently live, the lifetime segment. */ michael@0: Lifetime *lifetime; michael@0: michael@0: /* If the variable is currently dead, the next live segment. */ michael@0: Lifetime *saved; michael@0: michael@0: /* Jump preceding the basic block which killed this variable. */ michael@0: uint32_t savedEnd : 31; michael@0: michael@0: /* If the variable needs to be kept alive until lifetime->start. */ michael@0: bool ensured : 1; michael@0: michael@0: /* Whether this variable is live at offset. */ michael@0: Lifetime * live(uint32_t offset) const { michael@0: if (lifetime && lifetime->end >= offset) michael@0: return lifetime; michael@0: Lifetime *segment = lifetime ? lifetime : saved; michael@0: while (segment && segment->start <= offset) { michael@0: if (segment->end >= offset) michael@0: return segment; michael@0: segment = segment->next; michael@0: } michael@0: return nullptr; michael@0: } michael@0: michael@0: /* michael@0: * Get the offset of the first write to the variable in an inclusive range, michael@0: * UINT32_MAX if the variable is not written in the range. michael@0: */ michael@0: uint32_t firstWrite(uint32_t start, uint32_t end) const { michael@0: Lifetime *segment = lifetime ? lifetime : saved; michael@0: while (segment && segment->start <= end) { michael@0: if (segment->start >= start && segment->write) michael@0: return segment->start; michael@0: segment = segment->next; michael@0: } michael@0: return UINT32_MAX; michael@0: } michael@0: uint32_t firstWrite(LoopAnalysis *loop) const { michael@0: return firstWrite(loop->head, loop->backedge); michael@0: } michael@0: michael@0: /* michael@0: * If the variable is only written once in the body of a loop, offset of michael@0: * that write. UINT32_MAX otherwise. michael@0: */ michael@0: uint32_t onlyWrite(LoopAnalysis *loop) const { michael@0: uint32_t offset = UINT32_MAX; michael@0: Lifetime *segment = lifetime ? lifetime : saved; michael@0: while (segment && segment->start <= loop->backedge) { michael@0: if (segment->start >= loop->head && segment->write) { michael@0: if (offset != UINT32_MAX) michael@0: return UINT32_MAX; michael@0: offset = segment->start; michael@0: } michael@0: segment = segment->next; michael@0: } michael@0: return offset; michael@0: } michael@0: michael@0: #ifdef DEBUG michael@0: void print() const; michael@0: #endif michael@0: }; michael@0: michael@0: struct SSAPhiNode; michael@0: michael@0: /* michael@0: * Representation of values on stack or in slots at each point in the script. michael@0: * Values are independent from the bytecode position, and mean the same thing michael@0: * everywhere in the script. SSA values are immutable, except for contents of michael@0: * the values and types in an SSAPhiNode. michael@0: */ michael@0: class SSAValue michael@0: { michael@0: friend class ScriptAnalysis; michael@0: michael@0: public: michael@0: enum Kind { michael@0: EMPTY = 0, /* Invalid entry. */ michael@0: PUSHED = 1, /* Value pushed by some bytecode. */ michael@0: VAR = 2, /* Initial or written value to some argument or local. */ michael@0: PHI = 3 /* Selector for one of several values. */ michael@0: }; michael@0: michael@0: Kind kind() const { michael@0: JS_ASSERT(u.pushed.kind == u.var.kind && u.pushed.kind == u.phi.kind); michael@0: michael@0: /* Use a bitmask because MSVC wants to use -1 for PHI nodes. */ michael@0: return (Kind) (u.pushed.kind & 0x3); michael@0: } michael@0: michael@0: bool operator==(const SSAValue &o) const { michael@0: return !memcmp(this, &o, sizeof(SSAValue)); michael@0: } michael@0: michael@0: /* Accessors for values pushed by a bytecode within this script. */ michael@0: michael@0: uint32_t pushedOffset() const { michael@0: JS_ASSERT(kind() == PUSHED); michael@0: return u.pushed.offset; michael@0: } michael@0: michael@0: uint32_t pushedIndex() const { michael@0: JS_ASSERT(kind() == PUSHED); michael@0: return u.pushed.index; michael@0: } michael@0: michael@0: /* Accessors for initial and written values of arguments and (undefined) locals. */ michael@0: michael@0: bool varInitial() const { michael@0: JS_ASSERT(kind() == VAR); michael@0: return u.var.initial; michael@0: } michael@0: michael@0: uint32_t varSlot() const { michael@0: JS_ASSERT(kind() == VAR); michael@0: return u.var.slot; michael@0: } michael@0: michael@0: uint32_t varOffset() const { michael@0: JS_ASSERT(!varInitial()); michael@0: return u.var.offset; michael@0: } michael@0: michael@0: /* Accessors for phi nodes. */ michael@0: michael@0: uint32_t phiSlot() const; michael@0: uint32_t phiLength() const; michael@0: const SSAValue &phiValue(uint32_t i) const; michael@0: michael@0: /* Offset at which this phi node was created. */ michael@0: uint32_t phiOffset() const { michael@0: JS_ASSERT(kind() == PHI); michael@0: return u.phi.offset; michael@0: } michael@0: michael@0: SSAPhiNode *phiNode() const { michael@0: JS_ASSERT(kind() == PHI); michael@0: return u.phi.node; michael@0: } michael@0: michael@0: /* Other accessors. */ michael@0: michael@0: #ifdef DEBUG michael@0: void print() const; michael@0: #endif michael@0: michael@0: void clear() { michael@0: mozilla::PodZero(this); michael@0: JS_ASSERT(kind() == EMPTY); michael@0: } michael@0: michael@0: void initPushed(uint32_t offset, uint32_t index) { michael@0: clear(); michael@0: u.pushed.kind = PUSHED; michael@0: u.pushed.offset = offset; michael@0: u.pushed.index = index; michael@0: } michael@0: michael@0: static SSAValue PushedValue(uint32_t offset, uint32_t index) { michael@0: SSAValue v; michael@0: v.initPushed(offset, index); michael@0: return v; michael@0: } michael@0: michael@0: void initInitial(uint32_t slot) { michael@0: clear(); michael@0: u.var.kind = VAR; michael@0: u.var.initial = true; michael@0: u.var.slot = slot; michael@0: } michael@0: michael@0: void initWritten(uint32_t slot, uint32_t offset) { michael@0: clear(); michael@0: u.var.kind = VAR; michael@0: u.var.initial = false; michael@0: u.var.slot = slot; michael@0: u.var.offset = offset; michael@0: } michael@0: michael@0: static SSAValue WrittenVar(uint32_t slot, uint32_t offset) { michael@0: SSAValue v; michael@0: v.initWritten(slot, offset); michael@0: return v; michael@0: } michael@0: michael@0: void initPhi(uint32_t offset, SSAPhiNode *node) { michael@0: clear(); michael@0: u.phi.kind = PHI; michael@0: u.phi.offset = offset; michael@0: u.phi.node = node; michael@0: } michael@0: michael@0: static SSAValue PhiValue(uint32_t offset, SSAPhiNode *node) { michael@0: SSAValue v; michael@0: v.initPhi(offset, node); michael@0: return v; michael@0: } michael@0: michael@0: private: michael@0: union { michael@0: struct { michael@0: Kind kind : 2; michael@0: uint32_t offset : 30; michael@0: uint32_t index; michael@0: } pushed; michael@0: struct { michael@0: Kind kind : 2; michael@0: bool initial : 1; michael@0: uint32_t slot : 29; michael@0: uint32_t offset; michael@0: } var; michael@0: struct { michael@0: Kind kind : 2; michael@0: uint32_t offset : 30; michael@0: SSAPhiNode *node; michael@0: } phi; michael@0: } u; michael@0: }; michael@0: michael@0: /* michael@0: * Mutable component of a phi node, with the possible values of the phi michael@0: * and the possible types of the node as determined by type inference. michael@0: * When phi nodes are copied around, any updates to the original will michael@0: * be seen by all copies made. michael@0: */ michael@0: struct SSAPhiNode michael@0: { michael@0: uint32_t slot; michael@0: uint32_t length; michael@0: SSAValue *options; michael@0: SSAUseChain *uses; michael@0: SSAPhiNode() { mozilla::PodZero(this); } michael@0: }; michael@0: michael@0: inline uint32_t michael@0: SSAValue::phiSlot() const michael@0: { michael@0: return u.phi.node->slot; michael@0: } michael@0: michael@0: inline uint32_t michael@0: SSAValue::phiLength() const michael@0: { michael@0: JS_ASSERT(kind() == PHI); michael@0: return u.phi.node->length; michael@0: } michael@0: michael@0: inline const SSAValue & michael@0: SSAValue::phiValue(uint32_t i) const michael@0: { michael@0: JS_ASSERT(kind() == PHI && i < phiLength()); michael@0: return u.phi.node->options[i]; michael@0: } michael@0: michael@0: class SSAUseChain michael@0: { michael@0: public: michael@0: bool popped : 1; michael@0: uint32_t offset : 31; michael@0: /* FIXME: Assert that only the proper arm of this union is accessed. */ michael@0: union { michael@0: uint32_t which; michael@0: SSAPhiNode *phi; michael@0: } u; michael@0: SSAUseChain *next; michael@0: michael@0: SSAUseChain() { mozilla::PodZero(this); } michael@0: }; michael@0: michael@0: class SlotValue michael@0: { michael@0: public: michael@0: uint32_t slot; michael@0: SSAValue value; michael@0: SlotValue(uint32_t slot, const SSAValue &value) : slot(slot), value(value) {} michael@0: }; michael@0: michael@0: ///////////////////////////////////////////////////////////////////// michael@0: // Bytecode michael@0: ///////////////////////////////////////////////////////////////////// michael@0: michael@0: #ifdef DEBUG michael@0: void michael@0: PrintBytecode(JSContext *cx, HandleScript script, jsbytecode *pc) michael@0: { michael@0: fprintf(stderr, "#%u:", script->id()); michael@0: Sprinter sprinter(cx); michael@0: if (!sprinter.init()) michael@0: return; michael@0: js_Disassemble1(cx, script, pc, script->pcToOffset(pc), true, &sprinter); michael@0: fprintf(stderr, "%s", sprinter.string()); michael@0: } michael@0: #endif michael@0: michael@0: /* michael@0: * For opcodes which assign to a local variable or argument, track an extra def michael@0: * during SSA analysis for the value's use chain and assigned type. michael@0: */ michael@0: static inline bool michael@0: ExtendedDef(jsbytecode *pc) michael@0: { michael@0: switch ((JSOp)*pc) { michael@0: case JSOP_SETARG: michael@0: case JSOP_SETLOCAL: michael@0: return true; michael@0: default: michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: /* michael@0: * For opcodes which access local variables or arguments, we track an extra michael@0: * use during SSA analysis for the value of the variable before/after the op. michael@0: */ michael@0: static inline bool michael@0: ExtendedUse(jsbytecode *pc) michael@0: { michael@0: if (ExtendedDef(pc)) michael@0: return true; michael@0: switch ((JSOp)*pc) { michael@0: case JSOP_GETARG: michael@0: case JSOP_GETLOCAL: michael@0: return true; michael@0: default: michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: static inline unsigned michael@0: FollowBranch(JSContext *cx, JSScript *script, unsigned offset) michael@0: { michael@0: /* michael@0: * Get the target offset of a branch. For GOTO opcodes implementing michael@0: * 'continue' statements, short circuit any artificial backwards jump michael@0: * inserted by the emitter. michael@0: */ michael@0: jsbytecode *pc = script->offsetToPC(offset); michael@0: unsigned targetOffset = offset + GET_JUMP_OFFSET(pc); michael@0: if (targetOffset < offset) { michael@0: jsbytecode *target = script->offsetToPC(targetOffset); michael@0: JSOp nop = JSOp(*target); michael@0: if (nop == JSOP_GOTO) michael@0: return targetOffset + GET_JUMP_OFFSET(target); michael@0: } michael@0: return targetOffset; michael@0: } michael@0: michael@0: static inline uint32_t StackSlot(JSScript *script, uint32_t index) { michael@0: return TotalSlots(script) + index; michael@0: } michael@0: michael@0: static inline uint32_t GetBytecodeSlot(JSScript *script, jsbytecode *pc) michael@0: { michael@0: switch (JSOp(*pc)) { michael@0: michael@0: case JSOP_GETARG: michael@0: case JSOP_SETARG: michael@0: return ArgSlot(GET_ARGNO(pc)); michael@0: michael@0: case JSOP_GETLOCAL: michael@0: case JSOP_SETLOCAL: michael@0: return LocalSlot(script, GET_LOCALNO(pc)); michael@0: michael@0: case JSOP_THIS: michael@0: return ThisSlot(); michael@0: michael@0: default: michael@0: MOZ_ASSUME_UNREACHABLE("Bad slot opcode"); michael@0: } michael@0: } michael@0: michael@0: ///////////////////////////////////////////////////////////////////// michael@0: // Bytecode Analysis michael@0: ///////////////////////////////////////////////////////////////////// michael@0: michael@0: inline bool michael@0: ScriptAnalysis::addJump(JSContext *cx, unsigned offset, michael@0: unsigned *currentOffset, unsigned *forwardJump, unsigned *forwardLoop, michael@0: unsigned stackDepth) michael@0: { michael@0: JS_ASSERT(offset < script_->length()); michael@0: michael@0: Bytecode *&code = codeArray[offset]; michael@0: if (!code) { michael@0: code = cx->typeLifoAlloc().new_(); michael@0: if (!code) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: code->stackDepth = stackDepth; michael@0: } michael@0: JS_ASSERT(code->stackDepth == stackDepth); michael@0: michael@0: code->jumpTarget = true; michael@0: michael@0: if (offset < *currentOffset) { michael@0: if (!code->analyzed) { michael@0: /* michael@0: * Backedge in a while/for loop, whose body has not been analyzed michael@0: * due to a lack of fallthrough at the loop head. Roll back the michael@0: * offset to analyze the body. michael@0: */ michael@0: if (*forwardJump == 0) michael@0: *forwardJump = *currentOffset; michael@0: if (*forwardLoop == 0) michael@0: *forwardLoop = *currentOffset; michael@0: *currentOffset = offset; michael@0: } michael@0: } else if (offset > *forwardJump) { michael@0: *forwardJump = offset; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: inline bool michael@0: ScriptAnalysis::jumpTarget(uint32_t offset) michael@0: { michael@0: JS_ASSERT(offset < script_->length()); michael@0: return codeArray[offset] && codeArray[offset]->jumpTarget; michael@0: } michael@0: michael@0: inline bool michael@0: ScriptAnalysis::jumpTarget(const jsbytecode *pc) michael@0: { michael@0: return jumpTarget(script_->pcToOffset(pc)); michael@0: } michael@0: michael@0: inline const SSAValue & michael@0: ScriptAnalysis::poppedValue(uint32_t offset, uint32_t which) michael@0: { michael@0: JS_ASSERT(which < GetUseCount(script_, offset) + michael@0: (ExtendedUse(script_->offsetToPC(offset)) ? 1 : 0)); michael@0: return getCode(offset).poppedValues[which]; michael@0: } michael@0: michael@0: inline const SSAValue & michael@0: ScriptAnalysis::poppedValue(const jsbytecode *pc, uint32_t which) michael@0: { michael@0: return poppedValue(script_->pcToOffset(pc), which); michael@0: } michael@0: michael@0: inline const SlotValue * michael@0: ScriptAnalysis::newValues(uint32_t offset) michael@0: { michael@0: JS_ASSERT(offset < script_->length()); michael@0: return getCode(offset).newValues; michael@0: } michael@0: michael@0: inline const SlotValue * michael@0: ScriptAnalysis::newValues(const jsbytecode *pc) michael@0: { michael@0: return newValues(script_->pcToOffset(pc)); michael@0: } michael@0: michael@0: inline bool michael@0: ScriptAnalysis::trackUseChain(const SSAValue &v) michael@0: { michael@0: JS_ASSERT_IF(v.kind() == SSAValue::VAR, trackSlot(v.varSlot())); michael@0: return v.kind() != SSAValue::EMPTY && michael@0: (v.kind() != SSAValue::VAR || !v.varInitial()); michael@0: } michael@0: michael@0: /* michael@0: * Get the use chain for an SSA value. michael@0: */ michael@0: inline SSAUseChain *& michael@0: ScriptAnalysis::useChain(const SSAValue &v) michael@0: { michael@0: JS_ASSERT(trackUseChain(v)); michael@0: if (v.kind() == SSAValue::PUSHED) michael@0: return getCode(v.pushedOffset()).pushedUses[v.pushedIndex()]; michael@0: if (v.kind() == SSAValue::VAR) michael@0: return getCode(v.varOffset()).pushedUses[GetDefCount(script_, v.varOffset())]; michael@0: return v.phiNode()->uses; michael@0: } michael@0: michael@0: /* For a JSOP_CALL* op, get the pc of the corresponding JSOP_CALL/NEW/etc. */ michael@0: inline jsbytecode * michael@0: ScriptAnalysis::getCallPC(jsbytecode *pc) michael@0: { michael@0: SSAUseChain *uses = useChain(SSAValue::PushedValue(script_->pcToOffset(pc), 0)); michael@0: JS_ASSERT(uses && uses->popped); michael@0: JS_ASSERT(js_CodeSpec[script_->code()[uses->offset]].format & JOF_INVOKE); michael@0: return script_->offsetToPC(uses->offset); michael@0: } michael@0: michael@0: /* Accessors for local variable information. */ michael@0: michael@0: /* michael@0: * Escaping slots include all slots that can be accessed in ways other than michael@0: * through the corresponding LOCAL/ARG opcode. This includes all closed michael@0: * slots in the script, all slots in scripts which use eval or are in debug michael@0: * mode, and slots which are aliased by NAME or similar opcodes in the michael@0: * containing script (which does not imply the variable is closed). michael@0: */ michael@0: inline bool michael@0: ScriptAnalysis::slotEscapes(uint32_t slot) michael@0: { michael@0: JS_ASSERT(script_->compartment()->activeAnalysis); michael@0: if (slot >= numSlots) michael@0: return true; michael@0: return escapedSlots[slot]; michael@0: } michael@0: michael@0: /* michael@0: * Whether we distinguish different writes of this variable while doing michael@0: * SSA analysis. Escaping locals can be written in other scripts, and the michael@0: * presence of NAME opcodes which could alias local variables or arguments michael@0: * keeps us from tracking variable values at each point. michael@0: */ michael@0: inline bool michael@0: ScriptAnalysis::trackSlot(uint32_t slot) michael@0: { michael@0: return !slotEscapes(slot) && canTrackVars && slot < 1000; michael@0: } michael@0: michael@0: inline const LifetimeVariable & michael@0: ScriptAnalysis::liveness(uint32_t slot) michael@0: { michael@0: JS_ASSERT(script_->compartment()->activeAnalysis); michael@0: JS_ASSERT(!slotEscapes(slot)); michael@0: return lifetimes[slot]; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::analyzeBytecode(JSContext *cx) michael@0: { michael@0: JS_ASSERT(cx->compartment()->activeAnalysis); michael@0: JS_ASSERT(!codeArray); michael@0: michael@0: LifoAlloc &alloc = cx->typeLifoAlloc(); michael@0: michael@0: numSlots = TotalSlots(script_); michael@0: michael@0: unsigned length = script_->length(); michael@0: codeArray = alloc.newArray(length); michael@0: escapedSlots = alloc.newArray(numSlots); michael@0: michael@0: if (!codeArray || !escapedSlots) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: PodZero(codeArray, length); michael@0: michael@0: /* michael@0: * Populate arg and local slots which can escape and be accessed in ways michael@0: * other than through ARG* and LOCAL* opcodes (though arguments can still michael@0: * be indirectly read but not written through 'arguments' properties). michael@0: * All escaping locals are treated as having possible use-before-defs. michael@0: * Conservatively use 'argumentsHasVarBinding' instead of 'needsArgsObj' michael@0: * (needsArgsObj requires SSA which requires escapedSlots). Lastly, the michael@0: * debugger can access any local at any time. Even though debugger michael@0: * reads/writes are monitored by the DebugScopeProxy, this monitoring michael@0: * updates the flow-insensitive type sets, so we cannot use SSA. michael@0: */ michael@0: michael@0: PodZero(escapedSlots, numSlots); michael@0: michael@0: bool allVarsAliased = script_->compartment()->debugMode(); michael@0: bool allArgsAliased = allVarsAliased || script_->argumentsHasVarBinding(); michael@0: michael@0: RootedScript script(cx, script_); michael@0: for (BindingIter bi(script); bi; bi++) { michael@0: if (bi->kind() == Binding::ARGUMENT) michael@0: escapedSlots[ArgSlot(bi.frameIndex())] = allArgsAliased || bi->aliased(); michael@0: else michael@0: escapedSlots[LocalSlot(script_, bi.frameIndex())] = allVarsAliased || bi->aliased(); michael@0: } michael@0: michael@0: canTrackVars = true; michael@0: michael@0: /* michael@0: * If we are in the middle of one or more jumps, the offset of the highest michael@0: * target jumping over this bytecode. Includes implicit jumps from michael@0: * try/catch/finally blocks. michael@0: */ michael@0: unsigned forwardJump = 0; michael@0: michael@0: /* If we are in the middle of a loop, the offset of the highest backedge. */ michael@0: unsigned forwardLoop = 0; michael@0: michael@0: /* michael@0: * If we are in the middle of a try block, the offset of the highest michael@0: * catch/finally/enditer. michael@0: */ michael@0: unsigned forwardCatch = 0; michael@0: michael@0: /* Fill in stack depth and definitions at initial bytecode. */ michael@0: Bytecode *startcode = alloc.new_(); michael@0: if (!startcode) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: startcode->stackDepth = 0; michael@0: codeArray[0] = startcode; michael@0: michael@0: unsigned offset, nextOffset = 0; michael@0: while (nextOffset < length) { michael@0: offset = nextOffset; michael@0: michael@0: JS_ASSERT(forwardCatch <= forwardJump); michael@0: michael@0: /* Check if the current forward jump/try-block has finished. */ michael@0: if (forwardJump && forwardJump == offset) michael@0: forwardJump = 0; michael@0: if (forwardCatch && forwardCatch == offset) michael@0: forwardCatch = 0; michael@0: michael@0: Bytecode *code = maybeCode(offset); michael@0: jsbytecode *pc = script_->offsetToPC(offset); michael@0: michael@0: JSOp op = (JSOp)*pc; michael@0: JS_ASSERT(op < JSOP_LIMIT); michael@0: michael@0: /* Immediate successor of this bytecode. */ michael@0: unsigned successorOffset = offset + GetBytecodeLength(pc); michael@0: michael@0: /* michael@0: * Next bytecode to analyze. This is either the successor, or is an michael@0: * earlier bytecode if this bytecode has a loop backedge. michael@0: */ michael@0: nextOffset = successorOffset; michael@0: michael@0: if (!code) { michael@0: /* Haven't found a path by which this bytecode is reachable. */ michael@0: continue; michael@0: } michael@0: michael@0: /* michael@0: * Update info about bytecodes inside loops, which may have been michael@0: * analyzed before the backedge was seen. michael@0: */ michael@0: if (forwardLoop) { michael@0: if (forwardLoop <= offset) michael@0: forwardLoop = 0; michael@0: } michael@0: michael@0: if (code->analyzed) { michael@0: /* No need to reanalyze, see Bytecode::mergeDefines. */ michael@0: continue; michael@0: } michael@0: michael@0: code->analyzed = true; michael@0: michael@0: if (script_->hasBreakpointsAt(pc)) michael@0: canTrackVars = false; michael@0: michael@0: unsigned stackDepth = code->stackDepth; michael@0: michael@0: if (!forwardJump) michael@0: code->unconditional = true; michael@0: michael@0: unsigned nuses = GetUseCount(script_, offset); michael@0: unsigned ndefs = GetDefCount(script_, offset); michael@0: michael@0: JS_ASSERT(stackDepth >= nuses); michael@0: stackDepth -= nuses; michael@0: stackDepth += ndefs; michael@0: michael@0: switch (op) { michael@0: michael@0: case JSOP_DEFFUN: michael@0: case JSOP_DEFVAR: michael@0: case JSOP_DEFCONST: michael@0: case JSOP_SETCONST: michael@0: canTrackVars = false; michael@0: break; michael@0: michael@0: case JSOP_EVAL: michael@0: case JSOP_SPREADEVAL: michael@0: case JSOP_ENTERWITH: michael@0: canTrackVars = false; michael@0: break; michael@0: michael@0: case JSOP_TABLESWITCH: { michael@0: unsigned defaultOffset = offset + GET_JUMP_OFFSET(pc); michael@0: jsbytecode *pc2 = pc + JUMP_OFFSET_LEN; michael@0: int32_t low = GET_JUMP_OFFSET(pc2); michael@0: pc2 += JUMP_OFFSET_LEN; michael@0: int32_t high = GET_JUMP_OFFSET(pc2); michael@0: pc2 += JUMP_OFFSET_LEN; michael@0: michael@0: if (!addJump(cx, defaultOffset, &nextOffset, &forwardJump, &forwardLoop, stackDepth)) michael@0: return false; michael@0: michael@0: for (int32_t i = low; i <= high; i++) { michael@0: unsigned targetOffset = offset + GET_JUMP_OFFSET(pc2); michael@0: if (targetOffset != offset) { michael@0: if (!addJump(cx, targetOffset, &nextOffset, &forwardJump, &forwardLoop, stackDepth)) michael@0: return false; michael@0: } michael@0: pc2 += JUMP_OFFSET_LEN; michael@0: } michael@0: break; michael@0: } michael@0: michael@0: case JSOP_TRY: { michael@0: /* michael@0: * Everything between a try and corresponding catch or finally is conditional. michael@0: * Note that there is no problem with code which is skipped by a thrown michael@0: * exception but is not caught by a later handler in the same function: michael@0: * no more code will execute, and it does not matter what is defined. michael@0: */ michael@0: JSTryNote *tn = script_->trynotes()->vector; michael@0: JSTryNote *tnlimit = tn + script_->trynotes()->length; michael@0: for (; tn < tnlimit; tn++) { michael@0: unsigned startOffset = script_->mainOffset() + tn->start; michael@0: if (startOffset == offset + 1) { michael@0: unsigned catchOffset = startOffset + tn->length; michael@0: michael@0: /* This will overestimate try block code, for multiple catch/finally. */ michael@0: if (catchOffset > forwardCatch) michael@0: forwardCatch = catchOffset; michael@0: michael@0: if (tn->kind != JSTRY_ITER && tn->kind != JSTRY_LOOP) { michael@0: if (!addJump(cx, catchOffset, &nextOffset, &forwardJump, &forwardLoop, stackDepth)) michael@0: return false; michael@0: getCode(catchOffset).exceptionEntry = true; michael@0: } michael@0: } michael@0: } michael@0: break; michael@0: } michael@0: michael@0: case JSOP_GETLOCAL: michael@0: case JSOP_SETLOCAL: michael@0: JS_ASSERT(GET_LOCALNO(pc) < script_->nfixed()); michael@0: break; michael@0: michael@0: default: michael@0: break; michael@0: } michael@0: michael@0: bool jump = IsJumpOpcode(op); michael@0: michael@0: /* Check basic jump opcodes, which may or may not have a fallthrough. */ michael@0: if (jump) { michael@0: /* Case instructions do not push the lvalue back when branching. */ michael@0: unsigned newStackDepth = stackDepth; michael@0: if (op == JSOP_CASE) michael@0: newStackDepth--; michael@0: michael@0: unsigned targetOffset = offset + GET_JUMP_OFFSET(pc); michael@0: if (!addJump(cx, targetOffset, &nextOffset, &forwardJump, &forwardLoop, newStackDepth)) michael@0: return false; michael@0: } michael@0: michael@0: /* Handle any fallthrough from this opcode. */ michael@0: if (BytecodeFallsThrough(op)) { michael@0: JS_ASSERT(successorOffset < script_->length()); michael@0: michael@0: Bytecode *&nextcode = codeArray[successorOffset]; michael@0: michael@0: if (!nextcode) { michael@0: nextcode = alloc.new_(); michael@0: if (!nextcode) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: nextcode->stackDepth = stackDepth; michael@0: } michael@0: JS_ASSERT(nextcode->stackDepth == stackDepth); michael@0: michael@0: if (jump) michael@0: nextcode->jumpFallthrough = true; michael@0: michael@0: /* Treat the fallthrough of a branch instruction as a jump target. */ michael@0: if (jump) michael@0: nextcode->jumpTarget = true; michael@0: else michael@0: nextcode->fallthrough = true; michael@0: } michael@0: } michael@0: michael@0: JS_ASSERT(forwardJump == 0 && forwardLoop == 0 && forwardCatch == 0); michael@0: michael@0: /* michael@0: * Always ensure that a script's arguments usage has been analyzed before michael@0: * entering the script. This allows the functionPrologue to ensure that michael@0: * arguments are always created eagerly which simplifies interp logic. michael@0: */ michael@0: if (!script_->analyzedArgsUsage()) { michael@0: if (!analyzeLifetimes(cx)) michael@0: return false; michael@0: if (!analyzeSSA(cx)) michael@0: return false; michael@0: michael@0: /* michael@0: * Now that we have full SSA information for the script, analyze whether michael@0: * we can avoid creating the arguments object. michael@0: */ michael@0: script_->setNeedsArgsObj(needsArgsObj(cx)); michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: ///////////////////////////////////////////////////////////////////// michael@0: // Lifetime Analysis michael@0: ///////////////////////////////////////////////////////////////////// michael@0: michael@0: bool michael@0: ScriptAnalysis::analyzeLifetimes(JSContext *cx) michael@0: { michael@0: JS_ASSERT(cx->compartment()->activeAnalysis); michael@0: JS_ASSERT(codeArray); michael@0: JS_ASSERT(!lifetimes); michael@0: michael@0: LifoAlloc &alloc = cx->typeLifoAlloc(); michael@0: michael@0: lifetimes = alloc.newArray(numSlots); michael@0: if (!lifetimes) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: PodZero(lifetimes, numSlots); michael@0: michael@0: /* michael@0: * Variables which are currently dead. On forward branches to locations michael@0: * where these are live, they need to be marked as live. michael@0: */ michael@0: LifetimeVariable **saved = cx->pod_calloc(numSlots); michael@0: if (!saved) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: unsigned savedCount = 0; michael@0: michael@0: LoopAnalysis *loop = nullptr; michael@0: michael@0: uint32_t offset = script_->length() - 1; michael@0: while (offset < script_->length()) { michael@0: Bytecode *code = maybeCode(offset); michael@0: if (!code) { michael@0: offset--; michael@0: continue; michael@0: } michael@0: michael@0: jsbytecode *pc = script_->offsetToPC(offset); michael@0: michael@0: JSOp op = (JSOp) *pc; michael@0: michael@0: if (op == JSOP_LOOPHEAD && code->loop) { michael@0: /* michael@0: * This is the head of a loop, we need to go and make sure that any michael@0: * variables live at the head are live at the backedge and points prior. michael@0: * For each such variable, look for the last lifetime segment in the body michael@0: * and extend it to the end of the loop. michael@0: */ michael@0: JS_ASSERT(loop == code->loop); michael@0: unsigned backedge = code->loop->backedge; michael@0: for (unsigned i = 0; i < numSlots; i++) { michael@0: if (lifetimes[i].lifetime) { michael@0: if (!extendVariable(cx, lifetimes[i], offset, backedge)) michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: loop = loop->parent; michael@0: JS_ASSERT_IF(loop, loop->head < offset); michael@0: } michael@0: michael@0: if (code->exceptionEntry) { michael@0: DebugOnly found = false; michael@0: JSTryNote *tn = script_->trynotes()->vector; michael@0: JSTryNote *tnlimit = tn + script_->trynotes()->length; michael@0: for (; tn < tnlimit; tn++) { michael@0: unsigned startOffset = script_->mainOffset() + tn->start; michael@0: if (startOffset + tn->length == offset) { michael@0: /* michael@0: * Extend all live variables at exception entry to the start of michael@0: * the try block. michael@0: */ michael@0: for (unsigned i = 0; i < numSlots; i++) { michael@0: if (lifetimes[i].lifetime) michael@0: ensureVariable(lifetimes[i], startOffset - 1); michael@0: } michael@0: michael@0: found = true; michael@0: break; michael@0: } michael@0: } michael@0: JS_ASSERT(found); michael@0: } michael@0: michael@0: switch (op) { michael@0: case JSOP_GETARG: michael@0: case JSOP_GETLOCAL: michael@0: case JSOP_THIS: { michael@0: uint32_t slot = GetBytecodeSlot(script_, pc); michael@0: if (!slotEscapes(slot)) { michael@0: if (!addVariable(cx, lifetimes[slot], offset, saved, savedCount)) michael@0: return false; michael@0: } michael@0: break; michael@0: } michael@0: michael@0: case JSOP_SETARG: michael@0: case JSOP_SETLOCAL: { michael@0: uint32_t slot = GetBytecodeSlot(script_, pc); michael@0: if (!slotEscapes(slot)) { michael@0: if (!killVariable(cx, lifetimes[slot], offset, saved, savedCount)) michael@0: return false; michael@0: } michael@0: break; michael@0: } michael@0: michael@0: case JSOP_TABLESWITCH: michael@0: /* Restore all saved variables. :FIXME: maybe do this precisely. */ michael@0: for (unsigned i = 0; i < savedCount; i++) { michael@0: LifetimeVariable &var = *saved[i]; michael@0: uint32_t savedEnd = var.savedEnd; michael@0: var.lifetime = alloc.new_(offset, savedEnd, var.saved); michael@0: if (!var.lifetime) { michael@0: js_free(saved); michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: var.saved = nullptr; michael@0: saved[i--] = saved[--savedCount]; michael@0: } michael@0: savedCount = 0; michael@0: break; michael@0: michael@0: case JSOP_TRY: michael@0: for (unsigned i = 0; i < numSlots; i++) { michael@0: LifetimeVariable &var = lifetimes[i]; michael@0: if (var.ensured) { michael@0: JS_ASSERT(var.lifetime); michael@0: if (var.lifetime->start == offset) michael@0: var.ensured = false; michael@0: } michael@0: } michael@0: break; michael@0: michael@0: case JSOP_LOOPENTRY: michael@0: getCode(offset).loop = loop; michael@0: break; michael@0: michael@0: default:; michael@0: } michael@0: michael@0: if (IsJumpOpcode(op)) { michael@0: /* michael@0: * Forward jumps need to pull in all variables which are live at michael@0: * their target offset --- the variables live before the jump are michael@0: * the union of those live at the fallthrough and at the target. michael@0: */ michael@0: uint32_t targetOffset = FollowBranch(cx, script_, offset); michael@0: michael@0: if (targetOffset < offset) { michael@0: /* This is a loop back edge, no lifetime to pull in yet. */ michael@0: michael@0: #ifdef DEBUG michael@0: JSOp nop = JSOp(script_->code()[targetOffset]); michael@0: JS_ASSERT(nop == JSOP_LOOPHEAD); michael@0: #endif michael@0: michael@0: LoopAnalysis *nloop = alloc.new_(); michael@0: if (!nloop) { michael@0: js_free(saved); michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: PodZero(nloop); michael@0: michael@0: nloop->parent = loop; michael@0: loop = nloop; michael@0: michael@0: getCode(targetOffset).loop = loop; michael@0: loop->head = targetOffset; michael@0: loop->backedge = offset; michael@0: michael@0: /* michael@0: * Find the entry jump, which will be a GOTO for 'for' or michael@0: * 'while' loops or a fallthrough for 'do while' loops. michael@0: */ michael@0: uint32_t entry = targetOffset; michael@0: if (entry) { michael@0: do { michael@0: entry--; michael@0: } while (!maybeCode(entry)); michael@0: michael@0: jsbytecode *entrypc = script_->offsetToPC(entry); michael@0: michael@0: if (JSOp(*entrypc) == JSOP_GOTO) michael@0: entry += GET_JUMP_OFFSET(entrypc); michael@0: else michael@0: entry = targetOffset; michael@0: } else { michael@0: /* Do-while loop at the start of the script. */ michael@0: entry = targetOffset; michael@0: } michael@0: JS_ASSERT(script_->code()[entry] == JSOP_LOOPHEAD || michael@0: script_->code()[entry] == JSOP_LOOPENTRY); michael@0: } else { michael@0: for (unsigned i = 0; i < savedCount; i++) { michael@0: LifetimeVariable &var = *saved[i]; michael@0: JS_ASSERT(!var.lifetime && var.saved); michael@0: if (var.live(targetOffset)) { michael@0: /* michael@0: * Jumping to a place where this variable is live. Make a new michael@0: * lifetime segment for the variable. michael@0: */ michael@0: uint32_t savedEnd = var.savedEnd; michael@0: var.lifetime = alloc.new_(offset, savedEnd, var.saved); michael@0: if (!var.lifetime) { michael@0: js_free(saved); michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: var.saved = nullptr; michael@0: saved[i--] = saved[--savedCount]; michael@0: } else if (loop && !var.savedEnd) { michael@0: /* michael@0: * This jump precedes the basic block which killed the variable, michael@0: * remember it and use it for the end of the next lifetime michael@0: * segment should the variable become live again. This is needed michael@0: * for loops, as if we wrap liveness around the loop the isLive michael@0: * test below may have given the wrong answer. michael@0: */ michael@0: var.savedEnd = offset; michael@0: } michael@0: } michael@0: } michael@0: } michael@0: michael@0: offset--; michael@0: } michael@0: michael@0: js_free(saved); michael@0: michael@0: return true; michael@0: } michael@0: michael@0: #ifdef DEBUG michael@0: void michael@0: LifetimeVariable::print() const michael@0: { michael@0: Lifetime *segment = lifetime ? lifetime : saved; michael@0: while (segment) { michael@0: printf(" (%u,%u)", segment->start, segment->end); michael@0: segment = segment->next; michael@0: } michael@0: printf("\n"); michael@0: } michael@0: #endif /* DEBUG */ michael@0: michael@0: inline bool michael@0: ScriptAnalysis::addVariable(JSContext *cx, LifetimeVariable &var, unsigned offset, michael@0: LifetimeVariable **&saved, unsigned &savedCount) michael@0: { michael@0: if (var.lifetime) { michael@0: if (var.ensured) michael@0: return true; michael@0: michael@0: JS_ASSERT(offset < var.lifetime->start); michael@0: var.lifetime->start = offset; michael@0: } else { michael@0: if (var.saved) { michael@0: /* Remove from the list of saved entries. */ michael@0: for (unsigned i = 0; i < savedCount; i++) { michael@0: if (saved[i] == &var) { michael@0: JS_ASSERT(savedCount); michael@0: saved[i--] = saved[--savedCount]; michael@0: break; michael@0: } michael@0: } michael@0: } michael@0: uint32_t savedEnd = var.savedEnd; michael@0: var.lifetime = cx->typeLifoAlloc().new_(offset, savedEnd, var.saved); michael@0: if (!var.lifetime) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: var.saved = nullptr; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: inline bool michael@0: ScriptAnalysis::killVariable(JSContext *cx, LifetimeVariable &var, unsigned offset, michael@0: LifetimeVariable **&saved, unsigned &savedCount) michael@0: { michael@0: if (!var.lifetime) { michael@0: /* Make a point lifetime indicating the write. */ michael@0: uint32_t savedEnd = var.savedEnd; michael@0: Lifetime *lifetime = cx->typeLifoAlloc().new_(offset, savedEnd, var.saved); michael@0: if (!lifetime) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: if (!var.saved) michael@0: saved[savedCount++] = &var; michael@0: var.saved = lifetime; michael@0: var.saved->write = true; michael@0: var.savedEnd = 0; michael@0: return true; michael@0: } michael@0: michael@0: JS_ASSERT_IF(!var.ensured, offset < var.lifetime->start); michael@0: unsigned start = var.lifetime->start; michael@0: michael@0: /* michael@0: * The variable is considered to be live at the bytecode which kills it michael@0: * (just not at earlier bytecodes). This behavior is needed by downstream michael@0: * register allocation (see FrameState::bestEvictReg). michael@0: */ michael@0: var.lifetime->start = offset; michael@0: var.lifetime->write = true; michael@0: michael@0: if (var.ensured) { michael@0: /* michael@0: * The variable is live even before the write, due to an enclosing try michael@0: * block. We need to split the lifetime to indicate there was a write. michael@0: * We set the new interval's savedEnd to 0, since it will always be michael@0: * adjacent to the old interval, so it never needs to be extended. michael@0: */ michael@0: var.lifetime = cx->typeLifoAlloc().new_(start, 0, var.lifetime); michael@0: if (!var.lifetime) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: var.lifetime->end = offset; michael@0: } else { michael@0: var.saved = var.lifetime; michael@0: var.savedEnd = 0; michael@0: var.lifetime = nullptr; michael@0: michael@0: saved[savedCount++] = &var; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: inline bool michael@0: ScriptAnalysis::extendVariable(JSContext *cx, LifetimeVariable &var, michael@0: unsigned start, unsigned end) michael@0: { michael@0: JS_ASSERT(var.lifetime); michael@0: if (var.ensured) { michael@0: /* michael@0: * If we are still ensured to be live, the try block must scope over michael@0: * the loop, in which case the variable is already guaranteed to be michael@0: * live for the entire loop. michael@0: */ michael@0: JS_ASSERT(var.lifetime->start < start); michael@0: return true; michael@0: } michael@0: michael@0: var.lifetime->start = start; michael@0: michael@0: /* michael@0: * Consider this code: michael@0: * michael@0: * while (...) { (#1) michael@0: * use x; (#2) michael@0: * ... michael@0: * x = ...; (#3) michael@0: * ... michael@0: * } (#4) michael@0: * michael@0: * Just before analyzing the while statement, there would be a live range michael@0: * from #1..#2 and a "point range" at #3. The job of extendVariable is to michael@0: * create a new live range from #3..#4. michael@0: * michael@0: * However, more extensions may be required if the definition of x is michael@0: * conditional. Consider the following. michael@0: * michael@0: * while (...) { (#1) michael@0: * use x; (#2) michael@0: * ... michael@0: * if (...) (#5) michael@0: * x = ...; (#3) michael@0: * ... michael@0: * } (#4) michael@0: * michael@0: * Assume that x is not used after the loop. Then, before extendVariable is michael@0: * run, the live ranges would be the same as before (#1..#2 and #3..#3). We michael@0: * still need to create a range from #3..#4. But, since the assignment at #3 michael@0: * may never run, we also need to create a range from #2..#3. This is done michael@0: * as follows. michael@0: * michael@0: * Each time we create a Lifetime, we store the start of the most recently michael@0: * seen sequence of conditional code in the Lifetime's savedEnd field. So, michael@0: * when creating the Lifetime at #2, we set the Lifetime's savedEnd to michael@0: * #5. (The start of the most recent conditional is cached in each michael@0: * variable's savedEnd field.) Consequently, extendVariable is able to michael@0: * create a new interval from #2..#5 using the savedEnd field of the michael@0: * existing #1..#2 interval. michael@0: */ michael@0: michael@0: Lifetime *segment = var.lifetime; michael@0: while (segment && segment->start < end) { michael@0: uint32_t savedEnd = segment->savedEnd; michael@0: if (!segment->next || segment->next->start >= end) { michael@0: /* michael@0: * savedEnd is only set for variables killed in the middle of the michael@0: * loop. Make a tail segment connecting the last use with the michael@0: * back edge. michael@0: */ michael@0: if (segment->end >= end) { michael@0: /* Variable known to be live after the loop finishes. */ michael@0: break; michael@0: } michael@0: savedEnd = end; michael@0: } michael@0: JS_ASSERT(savedEnd <= end); michael@0: if (savedEnd > segment->end) { michael@0: Lifetime *tail = cx->typeLifoAlloc().new_(savedEnd, 0, segment->next); michael@0: if (!tail) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: tail->start = segment->end; michael@0: michael@0: /* michael@0: * Clear the segment's saved end, but preserve in the tail if this michael@0: * is the last segment in the loop and the variable is killed in an michael@0: * outer loop before the backedge. michael@0: */ michael@0: if (segment->savedEnd > end) { michael@0: JS_ASSERT(savedEnd == end); michael@0: tail->savedEnd = segment->savedEnd; michael@0: } michael@0: segment->savedEnd = 0; michael@0: michael@0: segment->next = tail; michael@0: segment = tail->next; michael@0: } else { michael@0: JS_ASSERT(segment->savedEnd == 0); michael@0: segment = segment->next; michael@0: } michael@0: } michael@0: return true; michael@0: } michael@0: michael@0: inline void michael@0: ScriptAnalysis::ensureVariable(LifetimeVariable &var, unsigned until) michael@0: { michael@0: JS_ASSERT(var.lifetime); michael@0: michael@0: /* michael@0: * If we are already ensured, the current range we are trying to ensure michael@0: * should already be included. michael@0: */ michael@0: if (var.ensured) { michael@0: JS_ASSERT(var.lifetime->start <= until); michael@0: return; michael@0: } michael@0: michael@0: JS_ASSERT(until < var.lifetime->start); michael@0: var.lifetime->start = until; michael@0: var.ensured = true; michael@0: } michael@0: michael@0: ///////////////////////////////////////////////////////////////////// michael@0: // SSA Analysis michael@0: ///////////////////////////////////////////////////////////////////// michael@0: michael@0: /* Current value for a variable or stack value, as tracked during SSA. */ michael@0: struct SSAValueInfo michael@0: { michael@0: SSAValue v; michael@0: michael@0: /* michael@0: * Sizes of branchTargets the last time this slot was written. Branches less michael@0: * than this threshold do not need to be inspected if the slot is written michael@0: * again, as they will already reflect the slot's value at the branch. michael@0: */ michael@0: int32_t branchSize; michael@0: }; michael@0: michael@0: bool michael@0: ScriptAnalysis::analyzeSSA(JSContext *cx) michael@0: { michael@0: JS_ASSERT(cx->compartment()->activeAnalysis); michael@0: JS_ASSERT(codeArray); michael@0: JS_ASSERT(lifetimes); michael@0: michael@0: LifoAlloc &alloc = cx->typeLifoAlloc(); michael@0: unsigned maxDepth = script_->nslots() - script_->nfixed(); michael@0: michael@0: /* michael@0: * Current value of each variable and stack value. Empty for missing or michael@0: * untracked entries, i.e. escaping locals and arguments. michael@0: */ michael@0: SSAValueInfo *values = cx->pod_calloc(numSlots + maxDepth); michael@0: if (!values) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: struct FreeSSAValues { michael@0: SSAValueInfo *values; michael@0: FreeSSAValues(SSAValueInfo *values) : values(values) {} michael@0: ~FreeSSAValues() { js_free(values); } michael@0: } free(values); michael@0: michael@0: SSAValueInfo *stack = values + numSlots; michael@0: uint32_t stackDepth = 0; michael@0: michael@0: for (uint32_t slot = ArgSlot(0); slot < numSlots; slot++) { michael@0: if (trackSlot(slot)) michael@0: values[slot].v.initInitial(slot); michael@0: } michael@0: michael@0: /* michael@0: * All target offsets for forward jumps we have seen (including ones whose michael@0: * target we have advanced past). We lazily add pending entries at these michael@0: * targets for the original value of variables modified before the branch michael@0: * rejoins. michael@0: */ michael@0: Vector branchTargets(cx); michael@0: michael@0: /* michael@0: * Subset of branchTargets which are exception handlers at future offsets. michael@0: * Any new value of a variable modified before the target is reached is a michael@0: * potential value at that target, along with the lazy original value. michael@0: */ michael@0: Vector exceptionTargets(cx); michael@0: michael@0: uint32_t offset = 0; michael@0: while (offset < script_->length()) { michael@0: jsbytecode *pc = script_->offsetToPC(offset); michael@0: JSOp op = (JSOp)*pc; michael@0: michael@0: uint32_t successorOffset = offset + GetBytecodeLength(pc); michael@0: michael@0: Bytecode *code = maybeCode(pc); michael@0: if (!code) { michael@0: offset = successorOffset; michael@0: continue; michael@0: } michael@0: michael@0: if (code->exceptionEntry) { michael@0: /* Remove from exception targets list, which reflects only future targets. */ michael@0: for (size_t i = 0; i < exceptionTargets.length(); i++) { michael@0: if (exceptionTargets[i] == offset) { michael@0: exceptionTargets[i] = exceptionTargets.back(); michael@0: exceptionTargets.popBack(); michael@0: break; michael@0: } michael@0: } michael@0: } michael@0: michael@0: if (code->stackDepth > stackDepth) michael@0: PodZero(stack + stackDepth, code->stackDepth - stackDepth); michael@0: stackDepth = code->stackDepth; michael@0: michael@0: if (op == JSOP_LOOPHEAD && code->loop) { michael@0: /* michael@0: * Make sure there is a pending value array for phi nodes at the michael@0: * loop head. We won't be able to clear these until we reach the michael@0: * loop's back edge. michael@0: * michael@0: * We need phi nodes for all variables which might be modified michael@0: * during the loop. This ensures that in the loop body we have michael@0: * already updated state to reflect possible changes that happen michael@0: * before the back edge, and don't need to go back and fix things michael@0: * up when we *do* get to the back edge. This could be made lazier. michael@0: * michael@0: * We don't make phi nodes for values on the stack at the head of michael@0: * the loop. These may be popped during the loop (i.e. for ITER michael@0: * loops), but in such cases the original value is pushed back. michael@0: */ michael@0: Vector *&pending = code->pendingValues; michael@0: if (!pending) { michael@0: pending = cx->new_< Vector >(cx); michael@0: if (!pending) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: /* michael@0: * Make phi nodes and update state for slots which are already in michael@0: * pending from previous branches to the loop head, and which are michael@0: * modified in the body of the loop. michael@0: */ michael@0: for (unsigned i = 0; i < pending->length(); i++) { michael@0: SlotValue &v = (*pending)[i]; michael@0: if (v.slot < numSlots && liveness(v.slot).firstWrite(code->loop) != UINT32_MAX) { michael@0: if (v.value.kind() != SSAValue::PHI || v.value.phiOffset() != offset) { michael@0: JS_ASSERT(v.value.phiOffset() < offset); michael@0: SSAValue ov = v.value; michael@0: if (!makePhi(cx, v.slot, offset, &ov)) michael@0: return false; michael@0: if (!insertPhi(cx, ov, v.value)) michael@0: return false; michael@0: v.value = ov; michael@0: } michael@0: } michael@0: if (code->fallthrough || code->jumpFallthrough) { michael@0: if (!mergeValue(cx, offset, values[v.slot].v, &v)) michael@0: return false; michael@0: } michael@0: if (!mergeBranchTarget(cx, values[v.slot], v.slot, branchTargets, offset - 1)) michael@0: return false; michael@0: values[v.slot].v = v.value; michael@0: } michael@0: michael@0: /* michael@0: * Make phi nodes for all other slots which might be modified michael@0: * during the loop. This ensures that in the loop body we have michael@0: * already updated state to reflect possible changes that happen michael@0: * before the back edge, and don't need to go back and fix things michael@0: * up when we *do* get to the back edge. This could be made lazier. michael@0: */ michael@0: for (uint32_t slot = ArgSlot(0); slot < numSlots + stackDepth; slot++) { michael@0: if (slot >= numSlots || !trackSlot(slot)) michael@0: continue; michael@0: if (liveness(slot).firstWrite(code->loop) == UINT32_MAX) michael@0: continue; michael@0: if (values[slot].v.kind() == SSAValue::PHI && values[slot].v.phiOffset() == offset) { michael@0: /* There is already a pending entry for this slot. */ michael@0: continue; michael@0: } michael@0: SSAValue ov; michael@0: if (!makePhi(cx, slot, offset, &ov)) michael@0: return false; michael@0: if (code->fallthrough || code->jumpFallthrough) { michael@0: if (!insertPhi(cx, ov, values[slot].v)) michael@0: return false; michael@0: } michael@0: if (!mergeBranchTarget(cx, values[slot], slot, branchTargets, offset - 1)) michael@0: return false; michael@0: values[slot].v = ov; michael@0: if (!pending->append(SlotValue(slot, ov))) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: } michael@0: } else if (code->pendingValues) { michael@0: /* michael@0: * New values at this point from a previous jump to this bytecode. michael@0: * If there is fallthrough from the previous instruction, merge michael@0: * with the current state and create phi nodes where necessary, michael@0: * otherwise replace current values with the new values. michael@0: * michael@0: * Catch blocks are artifically treated as having fallthrough, so michael@0: * that values written inside the block but not subsequently michael@0: * overwritten are picked up. michael@0: */ michael@0: bool exception = getCode(offset).exceptionEntry; michael@0: Vector *pending = code->pendingValues; michael@0: for (unsigned i = 0; i < pending->length(); i++) { michael@0: SlotValue &v = (*pending)[i]; michael@0: if (code->fallthrough || code->jumpFallthrough || michael@0: (exception && values[v.slot].v.kind() != SSAValue::EMPTY)) { michael@0: if (!mergeValue(cx, offset, values[v.slot].v, &v)) michael@0: return false; michael@0: } michael@0: if (!mergeBranchTarget(cx, values[v.slot], v.slot, branchTargets, offset)) michael@0: return false; michael@0: values[v.slot].v = v.value; michael@0: } michael@0: if (!freezeNewValues(cx, offset)) michael@0: return false; michael@0: } michael@0: michael@0: unsigned nuses = GetUseCount(script_, offset); michael@0: unsigned ndefs = GetDefCount(script_, offset); michael@0: JS_ASSERT(stackDepth >= nuses); michael@0: michael@0: unsigned xuses = ExtendedUse(pc) ? nuses + 1 : nuses; michael@0: michael@0: if (xuses) { michael@0: code->poppedValues = alloc.newArray(xuses); michael@0: if (!code->poppedValues) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: for (unsigned i = 0; i < nuses; i++) { michael@0: SSAValue &v = stack[stackDepth - 1 - i].v; michael@0: code->poppedValues[i] = v; michael@0: v.clear(); michael@0: } michael@0: if (xuses > nuses) { michael@0: /* michael@0: * For SETLOCAL, etc. opcodes, add an extra popped value michael@0: * holding the value of the local before the op. michael@0: */ michael@0: uint32_t slot = GetBytecodeSlot(script_, pc); michael@0: if (trackSlot(slot)) michael@0: code->poppedValues[nuses] = values[slot].v; michael@0: else michael@0: code->poppedValues[nuses].clear(); michael@0: } michael@0: michael@0: if (xuses) { michael@0: SSAUseChain *useChains = alloc.newArray(xuses); michael@0: if (!useChains) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: PodZero(useChains, xuses); michael@0: for (unsigned i = 0; i < xuses; i++) { michael@0: const SSAValue &v = code->poppedValues[i]; michael@0: if (trackUseChain(v)) { michael@0: SSAUseChain *&uses = useChain(v); michael@0: useChains[i].popped = true; michael@0: useChains[i].offset = offset; michael@0: useChains[i].u.which = i; michael@0: useChains[i].next = uses; michael@0: uses = &useChains[i]; michael@0: } michael@0: } michael@0: } michael@0: } michael@0: michael@0: stackDepth -= nuses; michael@0: michael@0: for (unsigned i = 0; i < ndefs; i++) michael@0: stack[stackDepth + i].v.initPushed(offset, i); michael@0: michael@0: unsigned xdefs = ExtendedDef(pc) ? ndefs + 1 : ndefs; michael@0: if (xdefs) { michael@0: code->pushedUses = alloc.newArray(xdefs); michael@0: if (!code->pushedUses) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: PodZero(code->pushedUses, xdefs); michael@0: } michael@0: michael@0: stackDepth += ndefs; michael@0: michael@0: if (op == JSOP_SETARG || op == JSOP_SETLOCAL) { michael@0: uint32_t slot = GetBytecodeSlot(script_, pc); michael@0: if (trackSlot(slot)) { michael@0: if (!mergeBranchTarget(cx, values[slot], slot, branchTargets, offset)) michael@0: return false; michael@0: if (!mergeExceptionTarget(cx, values[slot].v, slot, exceptionTargets)) michael@0: return false; michael@0: values[slot].v.initWritten(slot, offset); michael@0: } michael@0: } michael@0: michael@0: switch (op) { michael@0: case JSOP_GETARG: michael@0: case JSOP_GETLOCAL: { michael@0: uint32_t slot = GetBytecodeSlot(script_, pc); michael@0: if (trackSlot(slot)) { michael@0: /* michael@0: * Propagate the current value of the local to the pushed value, michael@0: * and remember it with an extended use on the opcode. michael@0: */ michael@0: stack[stackDepth - 1].v = code->poppedValues[0] = values[slot].v; michael@0: } michael@0: break; michael@0: } michael@0: michael@0: /* Short circuit ops which push back one of their operands. */ michael@0: michael@0: case JSOP_MOREITER: michael@0: stack[stackDepth - 2].v = code->poppedValues[0]; michael@0: break; michael@0: michael@0: case JSOP_MUTATEPROTO: michael@0: case JSOP_INITPROP: michael@0: case JSOP_INITPROP_GETTER: michael@0: case JSOP_INITPROP_SETTER: michael@0: stack[stackDepth - 1].v = code->poppedValues[1]; michael@0: break; michael@0: michael@0: case JSOP_SPREAD: michael@0: case JSOP_INITELEM_INC: michael@0: stack[stackDepth - 2].v = code->poppedValues[2]; michael@0: break; michael@0: michael@0: case JSOP_INITELEM_ARRAY: michael@0: stack[stackDepth - 1].v = code->poppedValues[1]; michael@0: break; michael@0: michael@0: case JSOP_INITELEM: michael@0: case JSOP_INITELEM_GETTER: michael@0: case JSOP_INITELEM_SETTER: michael@0: stack[stackDepth - 1].v = code->poppedValues[2]; michael@0: break; michael@0: michael@0: case JSOP_DUP: michael@0: stack[stackDepth - 1].v = stack[stackDepth - 2].v = code->poppedValues[0]; michael@0: break; michael@0: michael@0: case JSOP_DUP2: michael@0: stack[stackDepth - 1].v = stack[stackDepth - 3].v = code->poppedValues[0]; michael@0: stack[stackDepth - 2].v = stack[stackDepth - 4].v = code->poppedValues[1]; michael@0: break; michael@0: michael@0: case JSOP_DUPAT: { michael@0: unsigned pickedDepth = GET_UINT24 (pc); michael@0: JS_ASSERT(pickedDepth < stackDepth - 1); michael@0: stack[stackDepth - 1].v = stack[stackDepth - 2 - pickedDepth].v; michael@0: break; michael@0: } michael@0: michael@0: case JSOP_SWAP: michael@0: /* Swap is like pick 1. */ michael@0: case JSOP_PICK: { michael@0: unsigned pickedDepth = (op == JSOP_SWAP ? 1 : pc[1]); michael@0: stack[stackDepth - 1].v = code->poppedValues[pickedDepth]; michael@0: for (unsigned i = 0; i < pickedDepth; i++) michael@0: stack[stackDepth - 2 - i].v = code->poppedValues[i]; michael@0: break; michael@0: } michael@0: michael@0: /* michael@0: * Switch and try blocks preserve the stack between the original op michael@0: * and all case statements or exception/finally handlers. michael@0: */ michael@0: michael@0: case JSOP_TABLESWITCH: { michael@0: unsigned defaultOffset = offset + GET_JUMP_OFFSET(pc); michael@0: jsbytecode *pc2 = pc + JUMP_OFFSET_LEN; michael@0: int32_t low = GET_JUMP_OFFSET(pc2); michael@0: pc2 += JUMP_OFFSET_LEN; michael@0: int32_t high = GET_JUMP_OFFSET(pc2); michael@0: pc2 += JUMP_OFFSET_LEN; michael@0: michael@0: for (int32_t i = low; i <= high; i++) { michael@0: unsigned targetOffset = offset + GET_JUMP_OFFSET(pc2); michael@0: if (targetOffset != offset) { michael@0: if (!checkBranchTarget(cx, targetOffset, branchTargets, values, stackDepth)) michael@0: return false; michael@0: } michael@0: pc2 += JUMP_OFFSET_LEN; michael@0: } michael@0: michael@0: if (!checkBranchTarget(cx, defaultOffset, branchTargets, values, stackDepth)) michael@0: return false; michael@0: break; michael@0: } michael@0: michael@0: case JSOP_TRY: { michael@0: JSTryNote *tn = script_->trynotes()->vector; michael@0: JSTryNote *tnlimit = tn + script_->trynotes()->length; michael@0: for (; tn < tnlimit; tn++) { michael@0: unsigned startOffset = script_->mainOffset() + tn->start; michael@0: if (startOffset == offset + 1) { michael@0: unsigned catchOffset = startOffset + tn->length; michael@0: michael@0: if (tn->kind != JSTRY_ITER && tn->kind != JSTRY_LOOP) { michael@0: if (!checkBranchTarget(cx, catchOffset, branchTargets, values, stackDepth)) michael@0: return false; michael@0: if (!checkExceptionTarget(cx, catchOffset, exceptionTargets)) michael@0: return false; michael@0: } michael@0: } michael@0: } michael@0: break; michael@0: } michael@0: michael@0: case JSOP_THROW: michael@0: case JSOP_RETURN: michael@0: case JSOP_RETRVAL: michael@0: if (!mergeAllExceptionTargets(cx, values, exceptionTargets)) michael@0: return false; michael@0: break; michael@0: michael@0: default:; michael@0: } michael@0: michael@0: if (IsJumpOpcode(op)) { michael@0: unsigned targetOffset = FollowBranch(cx, script_, offset); michael@0: if (!checkBranchTarget(cx, targetOffset, branchTargets, values, stackDepth)) michael@0: return false; michael@0: michael@0: /* michael@0: * If this is a back edge, we're done with the loop and can freeze michael@0: * the phi values at the head now. michael@0: */ michael@0: if (targetOffset < offset) { michael@0: if (!freezeNewValues(cx, targetOffset)) michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: offset = successorOffset; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: /* Get a phi node's capacity for a given length. */ michael@0: static inline unsigned michael@0: PhiNodeCapacity(unsigned length) michael@0: { michael@0: if (length <= 4) michael@0: return 4; michael@0: michael@0: return 1 << (FloorLog2(length - 1) + 1); michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::makePhi(JSContext *cx, uint32_t slot, uint32_t offset, SSAValue *pv) michael@0: { michael@0: SSAPhiNode *node = cx->typeLifoAlloc().new_(); michael@0: SSAValue *options = cx->typeLifoAlloc().newArray(PhiNodeCapacity(0)); michael@0: if (!node || !options) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: node->slot = slot; michael@0: node->options = options; michael@0: pv->initPhi(offset, node); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::insertPhi(JSContext *cx, SSAValue &phi, const SSAValue &v) michael@0: { michael@0: JS_ASSERT(phi.kind() == SSAValue::PHI); michael@0: SSAPhiNode *node = phi.phiNode(); michael@0: michael@0: /* michael@0: * Filter dupes inserted into small nodes to keep things clean and avoid michael@0: * extra type constraints, but don't bother on large phi nodes to avoid michael@0: * quadratic behavior. michael@0: */ michael@0: if (node->length <= 8) { michael@0: for (unsigned i = 0; i < node->length; i++) { michael@0: if (v == node->options[i]) michael@0: return true; michael@0: } michael@0: } michael@0: michael@0: if (trackUseChain(v)) { michael@0: SSAUseChain *&uses = useChain(v); michael@0: michael@0: SSAUseChain *use = cx->typeLifoAlloc().new_(); michael@0: if (!use) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: use->popped = false; michael@0: use->offset = phi.phiOffset(); michael@0: use->u.phi = node; michael@0: use->next = uses; michael@0: uses = use; michael@0: } michael@0: michael@0: if (node->length < PhiNodeCapacity(node->length)) { michael@0: node->options[node->length++] = v; michael@0: return true; michael@0: } michael@0: michael@0: SSAValue *newOptions = michael@0: cx->typeLifoAlloc().newArray(PhiNodeCapacity(node->length + 1)); michael@0: if (!newOptions) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: PodCopy(newOptions, node->options, node->length); michael@0: node->options = newOptions; michael@0: node->options[node->length++] = v; michael@0: michael@0: return true; michael@0: } michael@0: michael@0: inline bool michael@0: ScriptAnalysis::mergeValue(JSContext *cx, uint32_t offset, const SSAValue &v, SlotValue *pv) michael@0: { michael@0: /* Make sure that v is accounted for in the pending value or phi value at pv. */ michael@0: JS_ASSERT(v.kind() != SSAValue::EMPTY && pv->value.kind() != SSAValue::EMPTY); michael@0: michael@0: if (v == pv->value) michael@0: return true; michael@0: michael@0: if (pv->value.kind() != SSAValue::PHI || pv->value.phiOffset() < offset) { michael@0: SSAValue ov = pv->value; michael@0: return makePhi(cx, pv->slot, offset, &pv->value) michael@0: && insertPhi(cx, pv->value, v) michael@0: && insertPhi(cx, pv->value, ov); michael@0: } michael@0: michael@0: JS_ASSERT(pv->value.phiOffset() == offset); michael@0: return insertPhi(cx, pv->value, v); michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::checkPendingValue(JSContext *cx, const SSAValue &v, uint32_t slot, michael@0: Vector *pending) michael@0: { michael@0: JS_ASSERT(v.kind() != SSAValue::EMPTY); michael@0: michael@0: for (unsigned i = 0; i < pending->length(); i++) { michael@0: if ((*pending)[i].slot == slot) michael@0: return true; michael@0: } michael@0: michael@0: if (!pending->append(SlotValue(slot, v))) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::checkBranchTarget(JSContext *cx, uint32_t targetOffset, michael@0: Vector &branchTargets, michael@0: SSAValueInfo *values, uint32_t stackDepth) michael@0: { michael@0: unsigned targetDepth = getCode(targetOffset).stackDepth; michael@0: JS_ASSERT(targetDepth <= stackDepth); michael@0: michael@0: /* michael@0: * If there is already an active branch to target, make sure its pending michael@0: * values reflect any changes made since the first branch. Otherwise, add a michael@0: * new pending branch and determine its pending values lazily. michael@0: */ michael@0: Vector *&pending = getCode(targetOffset).pendingValues; michael@0: if (pending) { michael@0: for (unsigned i = 0; i < pending->length(); i++) { michael@0: SlotValue &v = (*pending)[i]; michael@0: if (!mergeValue(cx, targetOffset, values[v.slot].v, &v)) michael@0: return false; michael@0: } michael@0: } else { michael@0: pending = cx->new_< Vector >(cx); michael@0: if (!pending || !branchTargets.append(targetOffset)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: /* michael@0: * Make sure there is a pending entry for each value on the stack. michael@0: * The number of stack entries at join points is usually zero, and michael@0: * we don't want to look at the active branches while popping and michael@0: * pushing values in each opcode. michael@0: */ michael@0: for (unsigned i = 0; i < targetDepth; i++) { michael@0: uint32_t slot = StackSlot(script_, i); michael@0: if (!checkPendingValue(cx, values[slot].v, slot, pending)) michael@0: return false; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::checkExceptionTarget(JSContext *cx, uint32_t catchOffset, michael@0: Vector &exceptionTargets) michael@0: { michael@0: JS_ASSERT(getCode(catchOffset).exceptionEntry); michael@0: michael@0: /* michael@0: * The catch offset will already be in the branch targets, just check michael@0: * whether this is already a known exception target. michael@0: */ michael@0: for (unsigned i = 0; i < exceptionTargets.length(); i++) { michael@0: if (exceptionTargets[i] == catchOffset) michael@0: return true; michael@0: } michael@0: if (!exceptionTargets.append(catchOffset)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::mergeBranchTarget(JSContext *cx, SSAValueInfo &value, uint32_t slot, michael@0: const Vector &branchTargets, uint32_t currentOffset) michael@0: { michael@0: if (slot >= numSlots) { michael@0: /* michael@0: * There is no need to lazily check that there are pending values at michael@0: * branch targets for slots on the stack, these are added to pending michael@0: * eagerly. michael@0: */ michael@0: return true; michael@0: } michael@0: michael@0: JS_ASSERT(trackSlot(slot)); michael@0: michael@0: /* michael@0: * Before changing the value of a variable, make sure the old value is michael@0: * marked at the target of any branches jumping over the current opcode. michael@0: * Only look at new branch targets which have appeared since the last time michael@0: * the variable was written. michael@0: */ michael@0: for (int i = branchTargets.length() - 1; i >= value.branchSize; i--) { michael@0: if (branchTargets[i] <= currentOffset) michael@0: continue; michael@0: michael@0: const Bytecode &code = getCode(branchTargets[i]); michael@0: michael@0: Vector *pending = code.pendingValues; michael@0: if (!checkPendingValue(cx, value.v, slot, pending)) michael@0: return false; michael@0: } michael@0: michael@0: value.branchSize = branchTargets.length(); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::mergeExceptionTarget(JSContext *cx, const SSAValue &value, uint32_t slot, michael@0: const Vector &exceptionTargets) michael@0: { michael@0: JS_ASSERT(trackSlot(slot)); michael@0: michael@0: /* michael@0: * Update the value at exception targets with the value of a variable michael@0: * before it is overwritten. Unlike mergeBranchTarget, this is done whether michael@0: * or not the overwritten value is the value of the variable at the michael@0: * original branch. Values for a variable which are written after the michael@0: * try block starts and overwritten before it is finished can still be michael@0: * seen at exception handlers via exception paths. michael@0: */ michael@0: for (unsigned i = 0; i < exceptionTargets.length(); i++) { michael@0: unsigned offset = exceptionTargets[i]; michael@0: Vector *pending = getCode(offset).pendingValues; michael@0: michael@0: bool duplicate = false; michael@0: for (unsigned i = 0; i < pending->length(); i++) { michael@0: if ((*pending)[i].slot == slot) { michael@0: duplicate = true; michael@0: SlotValue &v = (*pending)[i]; michael@0: if (!mergeValue(cx, offset, value, &v)) michael@0: return false; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (!duplicate && !pending->append(SlotValue(slot, value))) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::mergeAllExceptionTargets(JSContext *cx, SSAValueInfo *values, michael@0: const Vector &exceptionTargets) michael@0: { michael@0: for (unsigned i = 0; i < exceptionTargets.length(); i++) { michael@0: Vector *pending = getCode(exceptionTargets[i]).pendingValues; michael@0: for (unsigned i = 0; i < pending->length(); i++) { michael@0: const SlotValue &v = (*pending)[i]; michael@0: if (trackSlot(v.slot)) { michael@0: if (!mergeExceptionTarget(cx, values[v.slot].v, v.slot, exceptionTargets)) michael@0: return false; michael@0: } michael@0: } michael@0: } michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::freezeNewValues(JSContext *cx, uint32_t offset) michael@0: { michael@0: Bytecode &code = getCode(offset); michael@0: michael@0: Vector *pending = code.pendingValues; michael@0: code.pendingValues = nullptr; michael@0: michael@0: unsigned count = pending->length(); michael@0: if (count == 0) { michael@0: js_delete(pending); michael@0: return true; michael@0: } michael@0: michael@0: code.newValues = cx->typeLifoAlloc().newArray(count + 1); michael@0: if (!code.newValues) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: michael@0: for (unsigned i = 0; i < count; i++) michael@0: code.newValues[i] = (*pending)[i]; michael@0: code.newValues[count].slot = 0; michael@0: code.newValues[count].value.clear(); michael@0: michael@0: js_delete(pending); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::needsArgsObj(JSContext *cx, SeenVector &seen, const SSAValue &v) michael@0: { michael@0: /* michael@0: * trackUseChain is false for initial values of variables, which michael@0: * cannot hold the script's arguments object. michael@0: */ michael@0: if (!trackUseChain(v)) michael@0: return false; michael@0: michael@0: for (unsigned i = 0; i < seen.length(); i++) { michael@0: if (v == seen[i]) michael@0: return false; michael@0: } michael@0: if (!seen.append(v)) michael@0: return true; michael@0: michael@0: SSAUseChain *use = useChain(v); michael@0: while (use) { michael@0: if (needsArgsObj(cx, seen, use)) michael@0: return true; michael@0: use = use->next; michael@0: } michael@0: michael@0: return false; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::needsArgsObj(JSContext *cx, SeenVector &seen, SSAUseChain *use) michael@0: { michael@0: if (!use->popped) michael@0: return needsArgsObj(cx, seen, SSAValue::PhiValue(use->offset, use->u.phi)); michael@0: michael@0: jsbytecode *pc = script_->offsetToPC(use->offset); michael@0: JSOp op = JSOp(*pc); michael@0: michael@0: if (op == JSOP_POP || op == JSOP_POPN) michael@0: return false; michael@0: michael@0: /* We can read the frame's arguments directly for f.apply(x, arguments). */ michael@0: if (op == JSOP_FUNAPPLY && GET_ARGC(pc) == 2 && use->u.which == 0) { michael@0: argumentsContentsObserved_ = true; michael@0: return false; michael@0: } michael@0: michael@0: /* arguments[i] can read fp->canonicalActualArg(i) directly. */ michael@0: if (op == JSOP_GETELEM && use->u.which == 1) { michael@0: argumentsContentsObserved_ = true; michael@0: return false; michael@0: } michael@0: michael@0: /* arguments.length length can read fp->numActualArgs() directly. */ michael@0: if (op == JSOP_LENGTH) michael@0: return false; michael@0: michael@0: /* Allow assignments to non-closed locals (but not arguments). */ michael@0: michael@0: if (op == JSOP_SETLOCAL) { michael@0: uint32_t slot = GetBytecodeSlot(script_, pc); michael@0: if (!trackSlot(slot)) michael@0: return true; michael@0: return needsArgsObj(cx, seen, SSAValue::PushedValue(use->offset, 0)) || michael@0: needsArgsObj(cx, seen, SSAValue::WrittenVar(slot, use->offset)); michael@0: } michael@0: michael@0: if (op == JSOP_GETLOCAL) michael@0: return needsArgsObj(cx, seen, SSAValue::PushedValue(use->offset, 0)); michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: ScriptAnalysis::needsArgsObj(JSContext *cx) michael@0: { michael@0: JS_ASSERT(script_->argumentsHasVarBinding()); michael@0: michael@0: /* michael@0: * Always construct arguments objects when in debug mode and for generator michael@0: * scripts (generators can be suspended when speculation fails). michael@0: * michael@0: * FIXME: Don't build arguments for ES6 generator expressions. michael@0: */ michael@0: if (cx->compartment()->debugMode() || script_->isGenerator()) michael@0: return true; michael@0: michael@0: /* michael@0: * If the script has dynamic name accesses which could reach 'arguments', michael@0: * the parser will already have checked to ensure there are no explicit michael@0: * uses of 'arguments' in the function. If there are such uses, the script michael@0: * will be marked as definitely needing an arguments object. michael@0: * michael@0: * New accesses on 'arguments' can occur through 'eval' or the debugger michael@0: * statement. In the former case, we will dynamically detect the use and michael@0: * mark the arguments optimization as having failed. michael@0: */ michael@0: if (script_->bindingsAccessedDynamically()) michael@0: return false; michael@0: michael@0: unsigned pcOff = script_->pcToOffset(script_->argumentsBytecode()); michael@0: michael@0: SeenVector seen(cx); michael@0: if (needsArgsObj(cx, seen, SSAValue::PushedValue(pcOff, 0))) michael@0: return true; michael@0: michael@0: /* michael@0: * If a script explicitly accesses the contents of 'arguments', and has michael@0: * formals which may be stored as part of a call object, don't use lazy michael@0: * arguments. The compiler can then assume that accesses through michael@0: * arguments[i] will be on unaliased variables. michael@0: */ michael@0: if (script_->funHasAnyAliasedFormal() && argumentsContentsObserved_) michael@0: return true; michael@0: michael@0: return false; michael@0: } michael@0: michael@0: #ifdef DEBUG michael@0: michael@0: void michael@0: ScriptAnalysis::printSSA(JSContext *cx) michael@0: { michael@0: types::AutoEnterAnalysis enter(cx); michael@0: michael@0: printf("\n"); michael@0: michael@0: RootedScript script(cx, script_); michael@0: for (unsigned offset = 0; offset < script_->length(); offset++) { michael@0: Bytecode *code = maybeCode(offset); michael@0: if (!code) michael@0: continue; michael@0: michael@0: jsbytecode *pc = script_->offsetToPC(offset); michael@0: michael@0: PrintBytecode(cx, script, pc); michael@0: michael@0: SlotValue *newv = code->newValues; michael@0: if (newv) { michael@0: while (newv->slot) { michael@0: if (newv->value.kind() != SSAValue::PHI || newv->value.phiOffset() != offset) { michael@0: newv++; michael@0: continue; michael@0: } michael@0: printf(" phi "); michael@0: newv->value.print(); michael@0: printf(" ["); michael@0: for (unsigned i = 0; i < newv->value.phiLength(); i++) { michael@0: if (i) michael@0: printf(","); michael@0: newv->value.phiValue(i).print(); michael@0: } michael@0: printf("]\n"); michael@0: newv++; michael@0: } michael@0: } michael@0: michael@0: unsigned nuses = GetUseCount(script_, offset); michael@0: unsigned xuses = ExtendedUse(pc) ? nuses + 1 : nuses; michael@0: michael@0: for (unsigned i = 0; i < xuses; i++) { michael@0: printf(" popped%d: ", i); michael@0: code->poppedValues[i].print(); michael@0: printf("\n"); michael@0: } michael@0: } michael@0: michael@0: printf("\n"); michael@0: } michael@0: michael@0: void michael@0: SSAValue::print() const michael@0: { michael@0: switch (kind()) { michael@0: michael@0: case EMPTY: michael@0: printf("empty"); michael@0: break; michael@0: michael@0: case PUSHED: michael@0: printf("pushed:%05u#%u", pushedOffset(), pushedIndex()); michael@0: break; michael@0: michael@0: case VAR: michael@0: if (varInitial()) michael@0: printf("initial:%u", varSlot()); michael@0: else michael@0: printf("write:%05u", varOffset()); michael@0: break; michael@0: michael@0: case PHI: michael@0: printf("phi:%05u#%u", phiOffset(), phiSlot()); michael@0: break; michael@0: michael@0: default: michael@0: MOZ_ASSUME_UNREACHABLE("Bad kind"); michael@0: } michael@0: } michael@0: michael@0: void michael@0: ScriptAnalysis::assertMatchingDebugMode() michael@0: { michael@0: JS_ASSERT(!!script_->compartment()->debugMode() == !!originalDebugMode_); michael@0: } michael@0: michael@0: void michael@0: ScriptAnalysis::assertMatchingStackDepthAtOffset(uint32_t offset, uint32_t stackDepth) { michael@0: JS_ASSERT_IF(maybeCode(offset), getCode(offset).stackDepth == stackDepth); michael@0: } michael@0: michael@0: #endif /* DEBUG */ michael@0: michael@0: } // namespace analyze michael@0: } // namespace js