The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

  * vim: set ts=8 sts=4 et sw=4 tw=99:

  * This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #include "mozilla/DebugOnly.h"

 #include "mozilla/MathAlgorithms.h"

 #include "mozilla/PodOperations.h"

 #include "jscntxt.h"

 #include "jscompartment.h"

 #include "vm/Opcodes.h"

 #include "jsinferinlines.h"

 #include "jsobjinlines.h"

 #include "jsopcodeinlines.h"

 using mozilla::DebugOnly;

 using mozilla::PodCopy;

 using mozilla::PodZero;

 using mozilla::FloorLog2;

 namespace js {

 namespace analyze {

 class LoopAnalysis;

 } // namespace analyze

 } // namespace js

 namespace mozilla {

 template <> struct IsPod<js::analyze::LifetimeVariable> : TrueType {};

 template <> struct IsPod<js::analyze::LoopAnalysis>     : TrueType {};

 template <> struct IsPod<js::analyze::SlotValue>        : TrueType {};

 template <> struct IsPod<js::analyze::SSAValue>         : TrueType {};

 template <> struct IsPod<js::analyze::SSAUseChain>      : TrueType {};

 } /* namespace mozilla */

 namespace js {

 namespace analyze {

 /*

  * There are three analyses we can perform on a JSScript, outlined below.

  * The results of all three are stored in ScriptAnalysis, but the analyses

  * themselves can be performed separately. Along with type inference results,

  * per-script analysis results are tied to the per-compartment analysis pool

  * and are freed on every garbage collection.

  *

  * - Basic bytecode analysis. For each bytecode, determine the stack depth at

  * that point and control flow information needed for compilation. Also does

  * a defined-variables analysis to look for local variables which have uses

  * before definitions.

  *

  * - Lifetime analysis. Makes a backwards pass over the script to approximate

  * the regions where each variable is live, avoiding a full fixpointing

  * live-variables pass. This is based on the algorithm described in:

  *

  *     "Quality and Speed in Linear-scan Register Allocation"

  *     Traub et. al.

  *     PLDI, 1998

  *

  * - SSA analysis of the script's variables and stack values. For each stack

  * value popped and non-escaping local variable or argument read, determines

  * which push(es) or write(s) produced that value.

  *

  * Intermediate type inference results are additionally stored here. The above

  * analyses are independent from type inference.

  */

 /* Information about a bytecode instruction. */

 class Bytecode

 {

     friend class ScriptAnalysis;

   public:

     Bytecode() { mozilla::PodZero(this); }

     /* --------- Bytecode analysis --------- */

     /* Whether there are any incoming jumps to this instruction. */

     bool jumpTarget : 1;

     /* Whether there is fallthrough to this instruction from a non-branching instruction. */

     bool fallthrough : 1;

     /* Whether this instruction is the fall through point of a conditional jump. */

     bool jumpFallthrough : 1;

     /*

      * Whether this instruction must always execute, unless the script throws

      * an exception which it does not later catch.

      */

     bool unconditional : 1;

     /* Whether this instruction has been analyzed to get its output defines and stack. */

     bool analyzed : 1;

     /* Whether this is a catch/finally entry point. */

     bool exceptionEntry : 1;

     /* Stack depth before this opcode. */

     uint32_t stackDepth;

   private:

     /* If this is a JSOP_LOOPHEAD or JSOP_LOOPENTRY, information about the loop. */

     LoopAnalysis *loop;

     /* --------- SSA analysis --------- */

     /* Generated location of each value popped by this bytecode. */

     SSAValue *poppedValues;

     /* Points where values pushed or written by this bytecode are popped. */

     SSAUseChain **pushedUses;

     union {

         /*

          * If this is a join point (implies jumpTarget), any slots at this

          * point which can have a different values than at the immediate

          * predecessor in the bytecode. Array is terminated by an entry with

          * a zero slot.

          */

         SlotValue *newValues;

         /*

          * Vector used during SSA analysis to store values in need of merging

          * at this point. If this has incoming forward jumps and we have not

          * yet reached this point, stores values for entries on the stack and

          * for variables which have changed since the branch. If this is a loop

          * head and we haven't reached the back edge yet, stores loop phi nodes

          * for variables and entries live at the head of the loop.

          */

         Vector<SlotValue> *pendingValues;

     };

 };

 /*

  * Information about the lifetime of a local or argument. These form a linked

  * list describing successive intervals in the program where the variable's

  * value may be live. At points in the script not in one of these segments

  * (points in a 'lifetime hole'), the variable is dead and registers containing

  * its type/payload can be discarded without needing to be synced.

  */

 struct Lifetime

 {

     /*

      * Start and end offsets of this lifetime. The variable is live at the

      * beginning of every bytecode in this (inclusive) range.

      */

     uint32_t start;

     uint32_t end;

     /*

      * In a loop body, endpoint to extend this lifetime with if the variable is

      * live in the next iteration.

      */

     uint32_t savedEnd;

     /*

      * The start of this lifetime is a bytecode writing the variable. Each

      * write to a variable is associated with a lifetime.

      */

     bool write;

     /* Next lifetime. The variable is dead from this->end to next->start. */

     Lifetime *next;

     Lifetime(uint32_t offset, uint32_t savedEnd, Lifetime *next)

         : start(offset), end(offset), savedEnd(savedEnd),

           write(false), next(next)

     {}

 };

 /* Basic information for a loop. */

 class LoopAnalysis

 {

   public:

     /* Any loop this one is nested in. */

     LoopAnalysis *parent;

     /* Offset of the head of the loop. */

     uint32_t head;

     /*

      * Offset of the unique jump going to the head of the loop. The code

      * between the head and the backedge forms the loop body.

      */

     uint32_t backedge;

 };

 /* Current lifetime information for a variable. */

 struct LifetimeVariable

 {

     /* If the variable is currently live, the lifetime segment. */

     Lifetime *lifetime;

     /* If the variable is currently dead, the next live segment. */

     Lifetime *saved;

     /* Jump preceding the basic block which killed this variable. */

     uint32_t savedEnd : 31;

     /* If the variable needs to be kept alive until lifetime->start. */

     bool ensured : 1;

     /* Whether this variable is live at offset. */

     Lifetime * live(uint32_t offset) const {

         if (lifetime && lifetime->end >= offset)

             return lifetime;

         Lifetime *segment = lifetime ? lifetime : saved;

         while (segment && segment->start <= offset) {

             if (segment->end >= offset)

                 return segment;

             segment = segment->next;

         }

         return nullptr;

     }

     /*

      * Get the offset of the first write to the variable in an inclusive range,

      * UINT32_MAX if the variable is not written in the range.

      */

     uint32_t firstWrite(uint32_t start, uint32_t end) const {

         Lifetime *segment = lifetime ? lifetime : saved;

         while (segment && segment->start <= end) {

             if (segment->start >= start && segment->write)

                 return segment->start;

             segment = segment->next;

         }

         return UINT32_MAX;

     }

     uint32_t firstWrite(LoopAnalysis *loop) const {

         return firstWrite(loop->head, loop->backedge);

     }

     /*

      * If the variable is only written once in the body of a loop, offset of

      * that write. UINT32_MAX otherwise.

      */

     uint32_t onlyWrite(LoopAnalysis *loop) const {

         uint32_t offset = UINT32_MAX;

         Lifetime *segment = lifetime ? lifetime : saved;

         while (segment && segment->start <= loop->backedge) {

             if (segment->start >= loop->head && segment->write) {

                 if (offset != UINT32_MAX)

                     return UINT32_MAX;

                 offset = segment->start;

             }

             segment = segment->next;

         }

         return offset;

     }

 #ifdef DEBUG

     void print() const;

 #endif

 };

 struct SSAPhiNode;

 /*

  * Representation of values on stack or in slots at each point in the script.

  * Values are independent from the bytecode position, and mean the same thing

  * everywhere in the script. SSA values are immutable, except for contents of

  * the values and types in an SSAPhiNode.

  */

 class SSAValue

 {

     friend class ScriptAnalysis;

   public:

     enum Kind {

         EMPTY  = 0, /* Invalid entry. */

         PUSHED = 1, /* Value pushed by some bytecode. */

         VAR    = 2, /* Initial or written value to some argument or local. */

         PHI    = 3  /* Selector for one of several values. */

     };

     Kind kind() const {

         JS_ASSERT(u.pushed.kind == u.var.kind && u.pushed.kind == u.phi.kind);

         /* Use a bitmask because MSVC wants to use -1 for PHI nodes. */

         return (Kind) (u.pushed.kind & 0x3);

     }

     bool operator==(const SSAValue &o) const {

         return !memcmp(this, &o, sizeof(SSAValue));

     }

     /* Accessors for values pushed by a bytecode within this script. */

     uint32_t pushedOffset() const {

         JS_ASSERT(kind() == PUSHED);

         return u.pushed.offset;

     }

     uint32_t pushedIndex() const {

         JS_ASSERT(kind() == PUSHED);

         return u.pushed.index;

     }

     /* Accessors for initial and written values of arguments and (undefined) locals. */

     bool varInitial() const {

         JS_ASSERT(kind() == VAR);

         return u.var.initial;

     }

     uint32_t varSlot() const {

         JS_ASSERT(kind() == VAR);

         return u.var.slot;

     }

     uint32_t varOffset() const {

         JS_ASSERT(!varInitial());

         return u.var.offset;

     }

     /* Accessors for phi nodes. */

     uint32_t phiSlot() const;

     uint32_t phiLength() const;

     const SSAValue &phiValue(uint32_t i) const;

     /* Offset at which this phi node was created. */

     uint32_t phiOffset() const {

         JS_ASSERT(kind() == PHI);

         return u.phi.offset;

     }

     SSAPhiNode *phiNode() const {

         JS_ASSERT(kind() == PHI);

         return u.phi.node;

     }

     /* Other accessors. */

 #ifdef DEBUG

     void print() const;

 #endif

     void clear() {

         mozilla::PodZero(this);

         JS_ASSERT(kind() == EMPTY);

     }

     void initPushed(uint32_t offset, uint32_t index) {

         clear();

         u.pushed.kind = PUSHED;

         u.pushed.offset = offset;

         u.pushed.index = index;

     }

     static SSAValue PushedValue(uint32_t offset, uint32_t index) {

         SSAValue v;

         v.initPushed(offset, index);

         return v;

     }

     void initInitial(uint32_t slot) {

         clear();

         u.var.kind = VAR;

         u.var.initial = true;

         u.var.slot = slot;

     }

     void initWritten(uint32_t slot, uint32_t offset) {

         clear();

         u.var.kind = VAR;

         u.var.initial = false;

         u.var.slot = slot;

         u.var.offset = offset;

     }

     static SSAValue WrittenVar(uint32_t slot, uint32_t offset) {

         SSAValue v;

         v.initWritten(slot, offset);

         return v;

     }

     void initPhi(uint32_t offset, SSAPhiNode *node) {

         clear();

         u.phi.kind = PHI;

         u.phi.offset = offset;

         u.phi.node = node;

     }

     static SSAValue PhiValue(uint32_t offset, SSAPhiNode *node) {

         SSAValue v;

         v.initPhi(offset, node);

         return v;

     }

   private:

     union {

         struct {

             Kind kind : 2;

             uint32_t offset : 30;

             uint32_t index;

         } pushed;

         struct {

             Kind kind : 2;

             bool initial : 1;

             uint32_t slot : 29;

             uint32_t offset;

         } var;

         struct {

             Kind kind : 2;

             uint32_t offset : 30;

             SSAPhiNode *node;

         } phi;

     } u;

 };

 /*

  * Mutable component of a phi node, with the possible values of the phi

  * and the possible types of the node as determined by type inference.

  * When phi nodes are copied around, any updates to the original will

  * be seen by all copies made.

  */

 struct SSAPhiNode

 {

     uint32_t slot;

     uint32_t length;

     SSAValue *options;

     SSAUseChain *uses;

     SSAPhiNode() { mozilla::PodZero(this); }

 };

 inline uint32_t

 SSAValue::phiSlot() const

 {

     return u.phi.node->slot;

 }

 inline uint32_t

 SSAValue::phiLength() const

 {

     JS_ASSERT(kind() == PHI);

     return u.phi.node->length;

 }

 inline const SSAValue &

 SSAValue::phiValue(uint32_t i) const

 {

     JS_ASSERT(kind() == PHI && i < phiLength());

     return u.phi.node->options[i];

 }

 class SSAUseChain

 {

   public:

     bool popped : 1;

     uint32_t offset : 31;

     /* FIXME: Assert that only the proper arm of this union is accessed. */

     union {

         uint32_t which;

         SSAPhiNode *phi;

     } u;

     SSAUseChain *next;

     SSAUseChain() { mozilla::PodZero(this); }

 };

 class SlotValue

 {

   public:

     uint32_t slot;

     SSAValue value;

     SlotValue(uint32_t slot, const SSAValue &value) : slot(slot), value(value) {}

 };

 /////////////////////////////////////////////////////////////////////

 // Bytecode

 /////////////////////////////////////////////////////////////////////

 #ifdef DEBUG

 void

 PrintBytecode(JSContext *cx, HandleScript script, jsbytecode *pc)

 {

     fprintf(stderr, "#%u:", script->id());

     Sprinter sprinter(cx);

     if (!sprinter.init())

         return;

     js_Disassemble1(cx, script, pc, script->pcToOffset(pc), true, &sprinter);

     fprintf(stderr, "%s", sprinter.string());

 }

 #endif

 /*

  * For opcodes which assign to a local variable or argument, track an extra def

  * during SSA analysis for the value's use chain and assigned type.

  */

 static inline bool

 ExtendedDef(jsbytecode *pc)

 {

     switch ((JSOp)*pc) {

       case JSOP_SETARG:

       case JSOP_SETLOCAL:

         return true;

       default:

         return false;

     }

 }

 /*

  * For opcodes which access local variables or arguments, we track an extra

  * use during SSA analysis for the value of the variable before/after the op.

  */

 static inline bool

 ExtendedUse(jsbytecode *pc)

 {

     if (ExtendedDef(pc))

         return true;

     switch ((JSOp)*pc) {

       case JSOP_GETARG:

       case JSOP_GETLOCAL:

         return true;

       default:

         return false;

     }

 }

 static inline unsigned

 FollowBranch(JSContext *cx, JSScript *script, unsigned offset)

 {

     /*

      * Get the target offset of a branch. For GOTO opcodes implementing

      * 'continue' statements, short circuit any artificial backwards jump

      * inserted by the emitter.

      */

     jsbytecode *pc = script->offsetToPC(offset);

     unsigned targetOffset = offset + GET_JUMP_OFFSET(pc);

     if (targetOffset < offset) {

         jsbytecode *target = script->offsetToPC(targetOffset);

         JSOp nop = JSOp(*target);

         if (nop == JSOP_GOTO)

             return targetOffset + GET_JUMP_OFFSET(target);

     }

     return targetOffset;

 }

 static inline uint32_t StackSlot(JSScript *script, uint32_t index) {

     return TotalSlots(script) + index;

 }

 static inline uint32_t GetBytecodeSlot(JSScript *script, jsbytecode *pc)

 {

     switch (JSOp(*pc)) {

       case JSOP_GETARG:

       case JSOP_SETARG:

         return ArgSlot(GET_ARGNO(pc));

       case JSOP_GETLOCAL:

       case JSOP_SETLOCAL:

         return LocalSlot(script, GET_LOCALNO(pc));

       case JSOP_THIS:

         return ThisSlot();

       default:

         MOZ_ASSUME_UNREACHABLE("Bad slot opcode");

     }

 }

 /////////////////////////////////////////////////////////////////////

 // Bytecode Analysis

 /////////////////////////////////////////////////////////////////////

 inline bool

 ScriptAnalysis::addJump(JSContext *cx, unsigned offset,

                         unsigned *currentOffset, unsigned *forwardJump, unsigned *forwardLoop,

                         unsigned stackDepth)

 {

     JS_ASSERT(offset < script_->length());

     Bytecode *&code = codeArray[offset];

     if (!code) {

         code = cx->typeLifoAlloc().new_<Bytecode>();

         if (!code) {

             js_ReportOutOfMemory(cx);

             return false;

         }

         code->stackDepth = stackDepth;

     }

     JS_ASSERT(code->stackDepth == stackDepth);

     code->jumpTarget = true;

     if (offset < *currentOffset) {

         if (!code->analyzed) {

             /*

              * Backedge in a while/for loop, whose body has not been analyzed

              * due to a lack of fallthrough at the loop head. Roll back the

              * offset to analyze the body.

              */

             if (*forwardJump == 0)

                 *forwardJump = *currentOffset;

             if (*forwardLoop == 0)

                 *forwardLoop = *currentOffset;

             *currentOffset = offset;

         }

     } else if (offset > *forwardJump) {

         *forwardJump = offset;

     }

     return true;

 }

 inline bool

 ScriptAnalysis::jumpTarget(uint32_t offset)

 {

     JS_ASSERT(offset < script_->length());

     return codeArray[offset] && codeArray[offset]->jumpTarget;

 }

 inline bool

 ScriptAnalysis::jumpTarget(const jsbytecode *pc)

 {

     return jumpTarget(script_->pcToOffset(pc));

 }

 inline const SSAValue &

 ScriptAnalysis::poppedValue(uint32_t offset, uint32_t which)

 {

     JS_ASSERT(which < GetUseCount(script_, offset) +

               (ExtendedUse(script_->offsetToPC(offset)) ? 1 : 0));

     return getCode(offset).poppedValues[which];

 }

 inline const SSAValue &

 ScriptAnalysis::poppedValue(const jsbytecode *pc, uint32_t which)

 {

     return poppedValue(script_->pcToOffset(pc), which);

 }

 inline const SlotValue *

 ScriptAnalysis::newValues(uint32_t offset)

 {

     JS_ASSERT(offset < script_->length());

     return getCode(offset).newValues;

 }

 inline const SlotValue *

 ScriptAnalysis::newValues(const jsbytecode *pc)

 {

     return newValues(script_->pcToOffset(pc));

 }

 inline bool

 ScriptAnalysis::trackUseChain(const SSAValue &v)

 {

     JS_ASSERT_IF(v.kind() == SSAValue::VAR, trackSlot(v.varSlot()));

     return v.kind() != SSAValue::EMPTY &&

         (v.kind() != SSAValue::VAR || !v.varInitial());

 }

 /*

  * Get the use chain for an SSA value.

  */

 inline SSAUseChain *&

 ScriptAnalysis::useChain(const SSAValue &v)

 {

     JS_ASSERT(trackUseChain(v));

     if (v.kind() == SSAValue::PUSHED)

         return getCode(v.pushedOffset()).pushedUses[v.pushedIndex()];

     if (v.kind() == SSAValue::VAR)

         return getCode(v.varOffset()).pushedUses[GetDefCount(script_, v.varOffset())];

     return v.phiNode()->uses;

 }

 /* For a JSOP_CALL* op, get the pc of the corresponding JSOP_CALL/NEW/etc. */

 inline jsbytecode *

 ScriptAnalysis::getCallPC(jsbytecode *pc)

 {

     SSAUseChain *uses = useChain(SSAValue::PushedValue(script_->pcToOffset(pc), 0));

     JS_ASSERT(uses && uses->popped);

     JS_ASSERT(js_CodeSpec[script_->code()[uses->offset]].format & JOF_INVOKE);

     return script_->offsetToPC(uses->offset);

 }

 /* Accessors for local variable information. */

 /*

  * Escaping slots include all slots that can be accessed in ways other than

  * through the corresponding LOCAL/ARG opcode. This includes all closed

  * slots in the script, all slots in scripts which use eval or are in debug

  * mode, and slots which are aliased by NAME or similar opcodes in the

  * containing script (which does not imply the variable is closed).

  */

 inline bool

 ScriptAnalysis::slotEscapes(uint32_t slot)

 {

     JS_ASSERT(script_->compartment()->activeAnalysis);

     if (slot >= numSlots)

         return true;

     return escapedSlots[slot];

 }

 /*

  * Whether we distinguish different writes of this variable while doing

  * SSA analysis. Escaping locals can be written in other scripts, and the

  * presence of NAME opcodes which could alias local variables or arguments

  * keeps us from tracking variable values at each point.

  */

 inline bool

 ScriptAnalysis::trackSlot(uint32_t slot)

 {

     return !slotEscapes(slot) && canTrackVars && slot < 1000;

 }

 inline const LifetimeVariable &

 ScriptAnalysis::liveness(uint32_t slot)

 {

     JS_ASSERT(script_->compartment()->activeAnalysis);

     JS_ASSERT(!slotEscapes(slot));

     return lifetimes[slot];

 }

 bool

 ScriptAnalysis::analyzeBytecode(JSContext *cx)

 {

     JS_ASSERT(cx->compartment()->activeAnalysis);

     JS_ASSERT(!codeArray);

     LifoAlloc &alloc = cx->typeLifoAlloc();

     numSlots = TotalSlots(script_);

     unsigned length = script_->length();

     codeArray = alloc.newArray<Bytecode*>(length);

     escapedSlots = alloc.newArray<bool>(numSlots);

     if (!codeArray || !escapedSlots) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     PodZero(codeArray, length);

     /*

      * Populate arg and local slots which can escape and be accessed in ways

      * other than through ARG* and LOCAL* opcodes (though arguments can still

      * be indirectly read but not written through 'arguments' properties).

      * All escaping locals are treated as having possible use-before-defs.

      * Conservatively use 'argumentsHasVarBinding' instead of 'needsArgsObj'

      * (needsArgsObj requires SSA which requires escapedSlots). Lastly, the

      * debugger can access any local at any time. Even though debugger

      * reads/writes are monitored by the DebugScopeProxy, this monitoring

      * updates the flow-insensitive type sets, so we cannot use SSA.

      */

     PodZero(escapedSlots, numSlots);

     bool allVarsAliased = script_->compartment()->debugMode();

     bool allArgsAliased = allVarsAliased || script_->argumentsHasVarBinding();

     RootedScript script(cx, script_);

     for (BindingIter bi(script); bi; bi++) {

         if (bi->kind() == Binding::ARGUMENT)

             escapedSlots[ArgSlot(bi.frameIndex())] = allArgsAliased || bi->aliased();

         else

             escapedSlots[LocalSlot(script_, bi.frameIndex())] = allVarsAliased || bi->aliased();

     }

     canTrackVars = true;

     /*

      * If we are in the middle of one or more jumps, the offset of the highest

      * target jumping over this bytecode.  Includes implicit jumps from

      * try/catch/finally blocks.

      */

     unsigned forwardJump = 0;

     /* If we are in the middle of a loop, the offset of the highest backedge. */

     unsigned forwardLoop = 0;

     /*

      * If we are in the middle of a try block, the offset of the highest

      * catch/finally/enditer.

      */

     unsigned forwardCatch = 0;

     /* Fill in stack depth and definitions at initial bytecode. */

     Bytecode *startcode = alloc.new_<Bytecode>();

     if (!startcode) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     startcode->stackDepth = 0;

     codeArray[0] = startcode;

     unsigned offset, nextOffset = 0;

     while (nextOffset < length) {

         offset = nextOffset;

         JS_ASSERT(forwardCatch <= forwardJump);

         /* Check if the current forward jump/try-block has finished. */

         if (forwardJump && forwardJump == offset)

             forwardJump = 0;

         if (forwardCatch && forwardCatch == offset)

             forwardCatch = 0;

         Bytecode *code = maybeCode(offset);

         jsbytecode *pc = script_->offsetToPC(offset);

         JSOp op = (JSOp)*pc;

         JS_ASSERT(op < JSOP_LIMIT);

         /* Immediate successor of this bytecode. */

         unsigned successorOffset = offset + GetBytecodeLength(pc);

         /*

          * Next bytecode to analyze.  This is either the successor, or is an

          * earlier bytecode if this bytecode has a loop backedge.

          */

         nextOffset = successorOffset;

         if (!code) {

             /* Haven't found a path by which this bytecode is reachable. */

             continue;

         }

         /*

          * Update info about bytecodes inside loops, which may have been

          * analyzed before the backedge was seen.

          */

         if (forwardLoop) {

             if (forwardLoop <= offset)

                 forwardLoop = 0;

         }

         if (code->analyzed) {

             /* No need to reanalyze, see Bytecode::mergeDefines. */

             continue;

         }

         code->analyzed = true;

         if (script_->hasBreakpointsAt(pc))

             canTrackVars = false;

         unsigned stackDepth = code->stackDepth;

         if (!forwardJump)

             code->unconditional = true;

         unsigned nuses = GetUseCount(script_, offset);

         unsigned ndefs = GetDefCount(script_, offset);

         JS_ASSERT(stackDepth >= nuses);

         stackDepth -= nuses;

         stackDepth += ndefs;

         switch (op) {

           case JSOP_DEFFUN:

           case JSOP_DEFVAR:

           case JSOP_DEFCONST:

           case JSOP_SETCONST:

             canTrackVars = false;

             break;

           case JSOP_EVAL:

           case JSOP_SPREADEVAL:

           case JSOP_ENTERWITH:

             canTrackVars = false;

             break;

           case JSOP_TABLESWITCH: {

             unsigned defaultOffset = offset + GET_JUMP_OFFSET(pc);

             jsbytecode *pc2 = pc + JUMP_OFFSET_LEN;

             int32_t low = GET_JUMP_OFFSET(pc2);

             pc2 += JUMP_OFFSET_LEN;

             int32_t high = GET_JUMP_OFFSET(pc2);

             pc2 += JUMP_OFFSET_LEN;

             if (!addJump(cx, defaultOffset, &nextOffset, &forwardJump, &forwardLoop, stackDepth))

                 return false;

             for (int32_t i = low; i <= high; i++) {

                 unsigned targetOffset = offset + GET_JUMP_OFFSET(pc2);

                 if (targetOffset != offset) {

                     if (!addJump(cx, targetOffset, &nextOffset, &forwardJump, &forwardLoop, stackDepth))

                         return false;

                 }

                 pc2 += JUMP_OFFSET_LEN;

             }

             break;

           }

           case JSOP_TRY: {

             /*

              * Everything between a try and corresponding catch or finally is conditional.

              * Note that there is no problem with code which is skipped by a thrown

              * exception but is not caught by a later handler in the same function:

              * no more code will execute, and it does not matter what is defined.

              */

             JSTryNote *tn = script_->trynotes()->vector;

             JSTryNote *tnlimit = tn + script_->trynotes()->length;

             for (; tn < tnlimit; tn++) {

                 unsigned startOffset = script_->mainOffset() + tn->start;

                 if (startOffset == offset + 1) {

                     unsigned catchOffset = startOffset + tn->length;

                     /* This will overestimate try block code, for multiple catch/finally. */

                     if (catchOffset > forwardCatch)

                         forwardCatch = catchOffset;

                     if (tn->kind != JSTRY_ITER && tn->kind != JSTRY_LOOP) {

                         if (!addJump(cx, catchOffset, &nextOffset, &forwardJump, &forwardLoop, stackDepth))

                             return false;

                         getCode(catchOffset).exceptionEntry = true;

                     }

                 }

             }

             break;

           }

           case JSOP_GETLOCAL:

           case JSOP_SETLOCAL:

             JS_ASSERT(GET_LOCALNO(pc) < script_->nfixed());

             break;

           default:

             break;

         }

         bool jump = IsJumpOpcode(op);

         /* Check basic jump opcodes, which may or may not have a fallthrough. */

         if (jump) {

             /* Case instructions do not push the lvalue back when branching. */

             unsigned newStackDepth = stackDepth;

             if (op == JSOP_CASE)

                 newStackDepth--;

             unsigned targetOffset = offset + GET_JUMP_OFFSET(pc);

             if (!addJump(cx, targetOffset, &nextOffset, &forwardJump, &forwardLoop, newStackDepth))

                 return false;

         }

         /* Handle any fallthrough from this opcode. */

         if (BytecodeFallsThrough(op)) {

             JS_ASSERT(successorOffset < script_->length());

             Bytecode *&nextcode = codeArray[successorOffset];

             if (!nextcode) {

                 nextcode = alloc.new_<Bytecode>();

                 if (!nextcode) {

                     js_ReportOutOfMemory(cx);

                     return false;

                 }

                 nextcode->stackDepth = stackDepth;

             }

             JS_ASSERT(nextcode->stackDepth == stackDepth);

             if (jump)

                 nextcode->jumpFallthrough = true;

             /* Treat the fallthrough of a branch instruction as a jump target. */

             if (jump)

                 nextcode->jumpTarget = true;

             else

                 nextcode->fallthrough = true;

         }

     }

     JS_ASSERT(forwardJump == 0 && forwardLoop == 0 && forwardCatch == 0);

     /*

      * Always ensure that a script's arguments usage has been analyzed before

      * entering the script. This allows the functionPrologue to ensure that

      * arguments are always created eagerly which simplifies interp logic.

      */

     if (!script_->analyzedArgsUsage()) {

         if (!analyzeLifetimes(cx))

             return false;

         if (!analyzeSSA(cx))

             return false;

         /*

          * Now that we have full SSA information for the script, analyze whether

          * we can avoid creating the arguments object.

          */

         script_->setNeedsArgsObj(needsArgsObj(cx));

     }

     return true;

 }

 /////////////////////////////////////////////////////////////////////

 // Lifetime Analysis

 /////////////////////////////////////////////////////////////////////

 bool

 ScriptAnalysis::analyzeLifetimes(JSContext *cx)

 {

     JS_ASSERT(cx->compartment()->activeAnalysis);

     JS_ASSERT(codeArray);

     JS_ASSERT(!lifetimes);

     LifoAlloc &alloc = cx->typeLifoAlloc();

     lifetimes = alloc.newArray<LifetimeVariable>(numSlots);

     if (!lifetimes) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     PodZero(lifetimes, numSlots);

     /*

      * Variables which are currently dead. On forward branches to locations

      * where these are live, they need to be marked as live.

      */

     LifetimeVariable **saved = cx->pod_calloc<LifetimeVariable*>(numSlots);

     if (!saved) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     unsigned savedCount = 0;

     LoopAnalysis *loop = nullptr;

     uint32_t offset = script_->length() - 1;

     while (offset < script_->length()) {

         Bytecode *code = maybeCode(offset);

         if (!code) {

             offset--;

             continue;

         }

         jsbytecode *pc = script_->offsetToPC(offset);

         JSOp op = (JSOp) *pc;

         if (op == JSOP_LOOPHEAD && code->loop) {

             /*

              * This is the head of a loop, we need to go and make sure that any

              * variables live at the head are live at the backedge and points prior.

              * For each such variable, look for the last lifetime segment in the body

              * and extend it to the end of the loop.

              */

             JS_ASSERT(loop == code->loop);

             unsigned backedge = code->loop->backedge;

             for (unsigned i = 0; i < numSlots; i++) {

                 if (lifetimes[i].lifetime) {

                     if (!extendVariable(cx, lifetimes[i], offset, backedge))

                         return false;

                 }

             }

             loop = loop->parent;

             JS_ASSERT_IF(loop, loop->head < offset);

         }

         if (code->exceptionEntry) {

             DebugOnly<bool> found = false;

             JSTryNote *tn = script_->trynotes()->vector;

             JSTryNote *tnlimit = tn + script_->trynotes()->length;

             for (; tn < tnlimit; tn++) {

                 unsigned startOffset = script_->mainOffset() + tn->start;

                 if (startOffset + tn->length == offset) {

                     /*

                      * Extend all live variables at exception entry to the start of

                      * the try block.

                      */

                     for (unsigned i = 0; i < numSlots; i++) {

                         if (lifetimes[i].lifetime)

                             ensureVariable(lifetimes[i], startOffset - 1);

                     }

                     found = true;

                     break;

                 }

             }

             JS_ASSERT(found);

         }

         switch (op) {

           case JSOP_GETARG:

           case JSOP_GETLOCAL:

           case JSOP_THIS: {

             uint32_t slot = GetBytecodeSlot(script_, pc);

             if (!slotEscapes(slot)) {

                 if (!addVariable(cx, lifetimes[slot], offset, saved, savedCount))

                     return false;

             }

             break;

           }

           case JSOP_SETARG:

           case JSOP_SETLOCAL: {

             uint32_t slot = GetBytecodeSlot(script_, pc);

             if (!slotEscapes(slot)) {

                 if (!killVariable(cx, lifetimes[slot], offset, saved, savedCount))

                     return false;

             }

             break;

           }

           case JSOP_TABLESWITCH:

             /* Restore all saved variables. :FIXME: maybe do this precisely. */

             for (unsigned i = 0; i < savedCount; i++) {

                 LifetimeVariable &var = *saved[i];

                 uint32_t savedEnd = var.savedEnd;

                 var.lifetime = alloc.new_<Lifetime>(offset, savedEnd, var.saved);

                 if (!var.lifetime) {

                     js_free(saved);

                     js_ReportOutOfMemory(cx);

                     return false;

                 }

                 var.saved = nullptr;

                 saved[i--] = saved[--savedCount];

             }

             savedCount = 0;

             break;

           case JSOP_TRY:

             for (unsigned i = 0; i < numSlots; i++) {

                 LifetimeVariable &var = lifetimes[i];

                 if (var.ensured) {

                     JS_ASSERT(var.lifetime);

                     if (var.lifetime->start == offset)

                         var.ensured = false;

                 }

             }

             break;

           case JSOP_LOOPENTRY:

             getCode(offset).loop = loop;

             break;

           default:;

         }

         if (IsJumpOpcode(op)) {

             /*

              * Forward jumps need to pull in all variables which are live at

              * their target offset --- the variables live before the jump are

              * the union of those live at the fallthrough and at the target.

              */

             uint32_t targetOffset = FollowBranch(cx, script_, offset);

             if (targetOffset < offset) {

                 /* This is a loop back edge, no lifetime to pull in yet. */

 #ifdef DEBUG

                 JSOp nop = JSOp(script_->code()[targetOffset]);

                 JS_ASSERT(nop == JSOP_LOOPHEAD);

 #endif

                 LoopAnalysis *nloop = alloc.new_<LoopAnalysis>();

                 if (!nloop) {

                     js_free(saved);

                     js_ReportOutOfMemory(cx);

                     return false;

                 }

                 PodZero(nloop);

                 nloop->parent = loop;

                 loop = nloop;

                 getCode(targetOffset).loop = loop;

                 loop->head = targetOffset;

                 loop->backedge = offset;

                 /*

                  * Find the entry jump, which will be a GOTO for 'for' or

                  * 'while' loops or a fallthrough for 'do while' loops.

                  */

                 uint32_t entry = targetOffset;

                 if (entry) {

                     do {

                         entry--;

                     } while (!maybeCode(entry));

                     jsbytecode *entrypc = script_->offsetToPC(entry);

                     if (JSOp(*entrypc) == JSOP_GOTO)

                         entry += GET_JUMP_OFFSET(entrypc);

                     else

                         entry = targetOffset;

                 } else {

                     /* Do-while loop at the start of the script. */

                     entry = targetOffset;

                 }

                 JS_ASSERT(script_->code()[entry] == JSOP_LOOPHEAD ||

                           script_->code()[entry] == JSOP_LOOPENTRY);

             } else {

                 for (unsigned i = 0; i < savedCount; i++) {

                     LifetimeVariable &var = *saved[i];

                     JS_ASSERT(!var.lifetime && var.saved);

                     if (var.live(targetOffset)) {

                         /*

                          * Jumping to a place where this variable is live. Make a new

                          * lifetime segment for the variable.

                          */

                         uint32_t savedEnd = var.savedEnd;

                         var.lifetime = alloc.new_<Lifetime>(offset, savedEnd, var.saved);

                         if (!var.lifetime) {

                             js_free(saved);

                             js_ReportOutOfMemory(cx);

                             return false;

                         }

                         var.saved = nullptr;

                         saved[i--] = saved[--savedCount];

                     } else if (loop && !var.savedEnd) {

                         /*

                          * This jump precedes the basic block which killed the variable,

                          * remember it and use it for the end of the next lifetime

                          * segment should the variable become live again. This is needed

                          * for loops, as if we wrap liveness around the loop the isLive

                          * test below may have given the wrong answer.

                          */

                         var.savedEnd = offset;

                     }

                 }

             }

         }

         offset--;

     }

     js_free(saved);

     return true;

 }

 #ifdef DEBUG

 void

 LifetimeVariable::print() const

 {

     Lifetime *segment = lifetime ? lifetime : saved;

     while (segment) {

         printf(" (%u,%u)", segment->start, segment->end);

         segment = segment->next;

     }

     printf("\n");

 }

 #endif /* DEBUG */

 inline bool

 ScriptAnalysis::addVariable(JSContext *cx, LifetimeVariable &var, unsigned offset,

                             LifetimeVariable **&saved, unsigned &savedCount)

 {

     if (var.lifetime) {

         if (var.ensured)

             return true;

         JS_ASSERT(offset < var.lifetime->start);

         var.lifetime->start = offset;

     } else {

         if (var.saved) {

             /* Remove from the list of saved entries. */

             for (unsigned i = 0; i < savedCount; i++) {

                 if (saved[i] == &var) {

                     JS_ASSERT(savedCount);

                     saved[i--] = saved[--savedCount];

                     break;

                 }

             }

         }

         uint32_t savedEnd = var.savedEnd;

         var.lifetime = cx->typeLifoAlloc().new_<Lifetime>(offset, savedEnd, var.saved);

         if (!var.lifetime) {

             js_ReportOutOfMemory(cx);

             return false;

         }

         var.saved = nullptr;

     }

     return true;

 }

 inline bool

 ScriptAnalysis::killVariable(JSContext *cx, LifetimeVariable &var, unsigned offset,

                              LifetimeVariable **&saved, unsigned &savedCount)

 {

     if (!var.lifetime) {

         /* Make a point lifetime indicating the write. */

         uint32_t savedEnd = var.savedEnd;

         Lifetime *lifetime = cx->typeLifoAlloc().new_<Lifetime>(offset, savedEnd, var.saved);

         if (!lifetime) {

             js_ReportOutOfMemory(cx);

             return false;

         }

         if (!var.saved)

             saved[savedCount++] = &var;

         var.saved = lifetime;

         var.saved->write = true;

         var.savedEnd = 0;

         return true;

     }

     JS_ASSERT_IF(!var.ensured, offset < var.lifetime->start);

     unsigned start = var.lifetime->start;

     /*

      * The variable is considered to be live at the bytecode which kills it

      * (just not at earlier bytecodes). This behavior is needed by downstream

      * register allocation (see FrameState::bestEvictReg).

      */

     var.lifetime->start = offset;

     var.lifetime->write = true;

     if (var.ensured) {

         /*

          * The variable is live even before the write, due to an enclosing try

          * block. We need to split the lifetime to indicate there was a write.

          * We set the new interval's savedEnd to 0, since it will always be

          * adjacent to the old interval, so it never needs to be extended.

          */

         var.lifetime = cx->typeLifoAlloc().new_<Lifetime>(start, 0, var.lifetime);

         if (!var.lifetime) {

             js_ReportOutOfMemory(cx);

             return false;

         }

         var.lifetime->end = offset;

     } else {

         var.saved = var.lifetime;

         var.savedEnd = 0;

         var.lifetime = nullptr;

         saved[savedCount++] = &var;

     }

     return true;

 }

 inline bool

 ScriptAnalysis::extendVariable(JSContext *cx, LifetimeVariable &var,

                                unsigned start, unsigned end)

 {

     JS_ASSERT(var.lifetime);

     if (var.ensured) {

         /*

          * If we are still ensured to be live, the try block must scope over

          * the loop, in which case the variable is already guaranteed to be

          * live for the entire loop.

          */

         JS_ASSERT(var.lifetime->start < start);

         return true;

     }

     var.lifetime->start = start;

     /*

      * Consider this code:

      *

      *   while (...) { (#1)

      *       use x;    (#2)

      *       ...

      *       x = ...;  (#3)

      *       ...

      *   }             (#4)

      *

      * Just before analyzing the while statement, there would be a live range

      * from #1..#2 and a "point range" at #3. The job of extendVariable is to

      * create a new live range from #3..#4.

      *

      * However, more extensions may be required if the definition of x is

      * conditional. Consider the following.

      *

      *   while (...) {     (#1)

      *       use x;        (#2)

      *       ...

      *       if (...)      (#5)

      *           x = ...;  (#3)

      *       ...

      *   }                 (#4)

      *

      * Assume that x is not used after the loop. Then, before extendVariable is

      * run, the live ranges would be the same as before (#1..#2 and #3..#3). We

      * still need to create a range from #3..#4. But, since the assignment at #3

      * may never run, we also need to create a range from #2..#3. This is done

      * as follows.

      *

      * Each time we create a Lifetime, we store the start of the most recently

      * seen sequence of conditional code in the Lifetime's savedEnd field. So,

      * when creating the Lifetime at #2, we set the Lifetime's savedEnd to

      * #5. (The start of the most recent conditional is cached in each

      * variable's savedEnd field.) Consequently, extendVariable is able to

      * create a new interval from #2..#5 using the savedEnd field of the

      * existing #1..#2 interval.

      */

     Lifetime *segment = var.lifetime;

     while (segment && segment->start < end) {

         uint32_t savedEnd = segment->savedEnd;

         if (!segment->next || segment->next->start >= end) {

             /*

              * savedEnd is only set for variables killed in the middle of the

              * loop. Make a tail segment connecting the last use with the

              * back edge.

              */

             if (segment->end >= end) {

                 /* Variable known to be live after the loop finishes. */

                 break;

             }

             savedEnd = end;

         }

         JS_ASSERT(savedEnd <= end);

         if (savedEnd > segment->end) {

             Lifetime *tail = cx->typeLifoAlloc().new_<Lifetime>(savedEnd, 0, segment->next);

             if (!tail) {

                 js_ReportOutOfMemory(cx);

                 return false;

             }

             tail->start = segment->end;

             /*

              * Clear the segment's saved end, but preserve in the tail if this

              * is the last segment in the loop and the variable is killed in an

              * outer loop before the backedge.

              */

             if (segment->savedEnd > end) {

                 JS_ASSERT(savedEnd == end);

                 tail->savedEnd = segment->savedEnd;

             }

             segment->savedEnd = 0;

             segment->next = tail;

             segment = tail->next;

         } else {

             JS_ASSERT(segment->savedEnd == 0);

             segment = segment->next;

         }

     }

     return true;

 }

 inline void

 ScriptAnalysis::ensureVariable(LifetimeVariable &var, unsigned until)

 {

     JS_ASSERT(var.lifetime);

     /*

      * If we are already ensured, the current range we are trying to ensure

      * should already be included.

      */

     if (var.ensured) {

         JS_ASSERT(var.lifetime->start <= until);

         return;

     }

     JS_ASSERT(until < var.lifetime->start);

     var.lifetime->start = until;

     var.ensured = true;

 }

 /////////////////////////////////////////////////////////////////////

 // SSA Analysis

 /////////////////////////////////////////////////////////////////////

 /* Current value for a variable or stack value, as tracked during SSA. */

 struct SSAValueInfo

 {

     SSAValue v;

     /*

      * Sizes of branchTargets the last time this slot was written. Branches less

      * than this threshold do not need to be inspected if the slot is written

      * again, as they will already reflect the slot's value at the branch.

      */

     int32_t branchSize;

 };

 bool

 ScriptAnalysis::analyzeSSA(JSContext *cx)

 {

     JS_ASSERT(cx->compartment()->activeAnalysis);

     JS_ASSERT(codeArray);

     JS_ASSERT(lifetimes);

     LifoAlloc &alloc = cx->typeLifoAlloc();

     unsigned maxDepth = script_->nslots() - script_->nfixed();

     /*

      * Current value of each variable and stack value. Empty for missing or

      * untracked entries, i.e. escaping locals and arguments.

      */

     SSAValueInfo *values = cx->pod_calloc<SSAValueInfo>(numSlots + maxDepth);

     if (!values) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     struct FreeSSAValues {

         SSAValueInfo *values;

         FreeSSAValues(SSAValueInfo *values) : values(values) {}

         ~FreeSSAValues() { js_free(values); }

     } free(values);

     SSAValueInfo *stack = values + numSlots;

     uint32_t stackDepth = 0;

     for (uint32_t slot = ArgSlot(0); slot < numSlots; slot++) {

         if (trackSlot(slot))

             values[slot].v.initInitial(slot);

     }

     /*

      * All target offsets for forward jumps we have seen (including ones whose

      * target we have advanced past). We lazily add pending entries at these

      * targets for the original value of variables modified before the branch

      * rejoins.

      */

     Vector<uint32_t> branchTargets(cx);

     /*

      * Subset of branchTargets which are exception handlers at future offsets.

      * Any new value of a variable modified before the target is reached is a

      * potential value at that target, along with the lazy original value.

      */

     Vector<uint32_t> exceptionTargets(cx);

     uint32_t offset = 0;

     while (offset < script_->length()) {

         jsbytecode *pc = script_->offsetToPC(offset);

         JSOp op = (JSOp)*pc;

         uint32_t successorOffset = offset + GetBytecodeLength(pc);

         Bytecode *code = maybeCode(pc);

         if (!code) {

             offset = successorOffset;

             continue;

         }

         if (code->exceptionEntry) {

             /* Remove from exception targets list, which reflects only future targets. */

             for (size_t i = 0; i < exceptionTargets.length(); i++) {

                 if (exceptionTargets[i] == offset) {

                     exceptionTargets[i] = exceptionTargets.back();

                     exceptionTargets.popBack();

                     break;

                 }

             }

         }

         if (code->stackDepth > stackDepth)

             PodZero(stack + stackDepth, code->stackDepth - stackDepth);

         stackDepth = code->stackDepth;

         if (op == JSOP_LOOPHEAD && code->loop) {

             /*

              * Make sure there is a pending value array for phi nodes at the

              * loop head. We won't be able to clear these until we reach the

              * loop's back edge.

              *

              * We need phi nodes for all variables which might be modified

              * during the loop. This ensures that in the loop body we have

              * already updated state to reflect possible changes that happen

              * before the back edge, and don't need to go back and fix things

              * up when we *do* get to the back edge. This could be made lazier.

              *

              * We don't make phi nodes for values on the stack at the head of

              * the loop. These may be popped during the loop (i.e. for ITER

              * loops), but in such cases the original value is pushed back.

              */

             Vector<SlotValue> *&pending = code->pendingValues;

             if (!pending) {

                 pending = cx->new_< Vector<SlotValue> >(cx);

                 if (!pending) {

                     js_ReportOutOfMemory(cx);

                     return false;

                 }

             }

             /*

              * Make phi nodes and update state for slots which are already in

              * pending from previous branches to the loop head, and which are

              * modified in the body of the loop.

              */

             for (unsigned i = 0; i < pending->length(); i++) {

                 SlotValue &v = (*pending)[i];

                 if (v.slot < numSlots && liveness(v.slot).firstWrite(code->loop) != UINT32_MAX) {

                     if (v.value.kind() != SSAValue::PHI || v.value.phiOffset() != offset) {

                         JS_ASSERT(v.value.phiOffset() < offset);

                         SSAValue ov = v.value;

                         if (!makePhi(cx, v.slot, offset, &ov))

                             return false;

                         if (!insertPhi(cx, ov, v.value))

                             return false;

                         v.value = ov;

                     }

                 }

                 if (code->fallthrough || code->jumpFallthrough) {

                     if (!mergeValue(cx, offset, values[v.slot].v, &v))

                         return false;

                 }

                 if (!mergeBranchTarget(cx, values[v.slot], v.slot, branchTargets, offset - 1))

                     return false;

                 values[v.slot].v = v.value;

             }

             /*

              * Make phi nodes for all other slots which might be modified

              * during the loop. This ensures that in the loop body we have

              * already updated state to reflect possible changes that happen

              * before the back edge, and don't need to go back and fix things

              * up when we *do* get to the back edge. This could be made lazier.

              */

             for (uint32_t slot = ArgSlot(0); slot < numSlots + stackDepth; slot++) {

                 if (slot >= numSlots || !trackSlot(slot))

                     continue;

                 if (liveness(slot).firstWrite(code->loop) == UINT32_MAX)

                     continue;

                 if (values[slot].v.kind() == SSAValue::PHI && values[slot].v.phiOffset() == offset) {

                     /* There is already a pending entry for this slot. */

                     continue;

                 }

                 SSAValue ov;

                 if (!makePhi(cx, slot, offset, &ov))

                     return false;

                 if (code->fallthrough || code->jumpFallthrough) {

                     if (!insertPhi(cx, ov, values[slot].v))

                         return false;

                 }

                 if (!mergeBranchTarget(cx, values[slot], slot, branchTargets, offset - 1))

                     return false;

                 values[slot].v = ov;

                 if (!pending->append(SlotValue(slot, ov))) {

                     js_ReportOutOfMemory(cx);

                     return false;

                 }

             }

         } else if (code->pendingValues) {

             /*

              * New values at this point from a previous jump to this bytecode.

              * If there is fallthrough from the previous instruction, merge

              * with the current state and create phi nodes where necessary,

              * otherwise replace current values with the new values.

              *

              * Catch blocks are artifically treated as having fallthrough, so

              * that values written inside the block but not subsequently

              * overwritten are picked up.

              */

             bool exception = getCode(offset).exceptionEntry;

             Vector<SlotValue> *pending = code->pendingValues;

             for (unsigned i = 0; i < pending->length(); i++) {

                 SlotValue &v = (*pending)[i];

                 if (code->fallthrough || code->jumpFallthrough ||

                     (exception && values[v.slot].v.kind() != SSAValue::EMPTY)) {

                     if (!mergeValue(cx, offset, values[v.slot].v, &v))

                         return false;

                 }

                 if (!mergeBranchTarget(cx, values[v.slot], v.slot, branchTargets, offset))

                     return false;

                 values[v.slot].v = v.value;

             }

             if (!freezeNewValues(cx, offset))

                 return false;

         }

         unsigned nuses = GetUseCount(script_, offset);

         unsigned ndefs = GetDefCount(script_, offset);

         JS_ASSERT(stackDepth >= nuses);

         unsigned xuses = ExtendedUse(pc) ? nuses + 1 : nuses;

         if (xuses) {

             code->poppedValues = alloc.newArray<SSAValue>(xuses);

             if (!code->poppedValues) {

                 js_ReportOutOfMemory(cx);

                 return false;

             }

             for (unsigned i = 0; i < nuses; i++) {

                 SSAValue &v = stack[stackDepth - 1 - i].v;

                 code->poppedValues[i] = v;

                 v.clear();

             }

             if (xuses > nuses) {

                 /*

                  * For SETLOCAL, etc. opcodes, add an extra popped value

                  * holding the value of the local before the op.

                  */

                 uint32_t slot = GetBytecodeSlot(script_, pc);

                 if (trackSlot(slot))

                     code->poppedValues[nuses] = values[slot].v;

                 else

                     code->poppedValues[nuses].clear();

             }

             if (xuses) {

                 SSAUseChain *useChains = alloc.newArray<SSAUseChain>(xuses);

                 if (!useChains) {

                     js_ReportOutOfMemory(cx);

                     return false;

                 }

                 PodZero(useChains, xuses);

                 for (unsigned i = 0; i < xuses; i++) {

                     const SSAValue &v = code->poppedValues[i];

                     if (trackUseChain(v)) {

                         SSAUseChain *&uses = useChain(v);

                         useChains[i].popped = true;

                         useChains[i].offset = offset;

                         useChains[i].u.which = i;

                         useChains[i].next = uses;

                         uses = &useChains[i];

                     }

                 }

             }

         }

         stackDepth -= nuses;

         for (unsigned i = 0; i < ndefs; i++)

             stack[stackDepth + i].v.initPushed(offset, i);

         unsigned xdefs = ExtendedDef(pc) ? ndefs + 1 : ndefs;

         if (xdefs) {

             code->pushedUses = alloc.newArray<SSAUseChain *>(xdefs);

             if (!code->pushedUses) {

                 js_ReportOutOfMemory(cx);

                 return false;

             }

             PodZero(code->pushedUses, xdefs);

         }

         stackDepth += ndefs;

         if (op == JSOP_SETARG || op == JSOP_SETLOCAL) {

             uint32_t slot = GetBytecodeSlot(script_, pc);

             if (trackSlot(slot)) {

                 if (!mergeBranchTarget(cx, values[slot], slot, branchTargets, offset))

                     return false;

                 if (!mergeExceptionTarget(cx, values[slot].v, slot, exceptionTargets))

                     return false;

                 values[slot].v.initWritten(slot, offset);

             }

         }

         switch (op) {

           case JSOP_GETARG:

           case JSOP_GETLOCAL: {

             uint32_t slot = GetBytecodeSlot(script_, pc);

             if (trackSlot(slot)) {

                 /*

                  * Propagate the current value of the local to the pushed value,

                  * and remember it with an extended use on the opcode.

                  */

                 stack[stackDepth - 1].v = code->poppedValues[0] = values[slot].v;

             }

             break;

           }

           /* Short circuit ops which push back one of their operands. */

           case JSOP_MOREITER:

             stack[stackDepth - 2].v = code->poppedValues[0];

             break;

           case JSOP_MUTATEPROTO:

           case JSOP_INITPROP:

           case JSOP_INITPROP_GETTER:

           case JSOP_INITPROP_SETTER:

             stack[stackDepth - 1].v = code->poppedValues[1];

             break;

           case JSOP_SPREAD:

           case JSOP_INITELEM_INC:

             stack[stackDepth - 2].v = code->poppedValues[2];

             break;

           case JSOP_INITELEM_ARRAY:

             stack[stackDepth - 1].v = code->poppedValues[1];

             break;

           case JSOP_INITELEM:

           case JSOP_INITELEM_GETTER:

           case JSOP_INITELEM_SETTER:

             stack[stackDepth - 1].v = code->poppedValues[2];

             break;

           case JSOP_DUP:

             stack[stackDepth - 1].v = stack[stackDepth - 2].v = code->poppedValues[0];

             break;

           case JSOP_DUP2:

             stack[stackDepth - 1].v = stack[stackDepth - 3].v = code->poppedValues[0];

             stack[stackDepth - 2].v = stack[stackDepth - 4].v = code->poppedValues[1];

             break;

           case JSOP_DUPAT: {

             unsigned pickedDepth = GET_UINT24 (pc);

             JS_ASSERT(pickedDepth < stackDepth - 1);

             stack[stackDepth - 1].v = stack[stackDepth - 2 - pickedDepth].v;

             break;

           }

           case JSOP_SWAP:

             /* Swap is like pick 1. */

           case JSOP_PICK: {

             unsigned pickedDepth = (op == JSOP_SWAP ? 1 : pc[1]);

             stack[stackDepth - 1].v = code->poppedValues[pickedDepth];

             for (unsigned i = 0; i < pickedDepth; i++)

                 stack[stackDepth - 2 - i].v = code->poppedValues[i];

             break;

           }

           /*

            * Switch and try blocks preserve the stack between the original op

            * and all case statements or exception/finally handlers.

            */

           case JSOP_TABLESWITCH: {

             unsigned defaultOffset = offset + GET_JUMP_OFFSET(pc);

             jsbytecode *pc2 = pc + JUMP_OFFSET_LEN;

             int32_t low = GET_JUMP_OFFSET(pc2);

             pc2 += JUMP_OFFSET_LEN;

             int32_t high = GET_JUMP_OFFSET(pc2);

             pc2 += JUMP_OFFSET_LEN;

             for (int32_t i = low; i <= high; i++) {

                 unsigned targetOffset = offset + GET_JUMP_OFFSET(pc2);

                 if (targetOffset != offset) {

                     if (!checkBranchTarget(cx, targetOffset, branchTargets, values, stackDepth))

                         return false;

                 }

                 pc2 += JUMP_OFFSET_LEN;

             }

             if (!checkBranchTarget(cx, defaultOffset, branchTargets, values, stackDepth))

                 return false;

             break;

           }

           case JSOP_TRY: {

             JSTryNote *tn = script_->trynotes()->vector;

             JSTryNote *tnlimit = tn + script_->trynotes()->length;

             for (; tn < tnlimit; tn++) {

                 unsigned startOffset = script_->mainOffset() + tn->start;

                 if (startOffset == offset + 1) {

                     unsigned catchOffset = startOffset + tn->length;

                     if (tn->kind != JSTRY_ITER && tn->kind != JSTRY_LOOP) {

                         if (!checkBranchTarget(cx, catchOffset, branchTargets, values, stackDepth))

                             return false;

                         if (!checkExceptionTarget(cx, catchOffset, exceptionTargets))

                             return false;

                     }

                 }

             }

             break;

           }

           case JSOP_THROW:

           case JSOP_RETURN:

           case JSOP_RETRVAL:

             if (!mergeAllExceptionTargets(cx, values, exceptionTargets))

                 return false;

             break;

           default:;

         }

         if (IsJumpOpcode(op)) {

             unsigned targetOffset = FollowBranch(cx, script_, offset);

             if (!checkBranchTarget(cx, targetOffset, branchTargets, values, stackDepth))

                 return false;

             /*

              * If this is a back edge, we're done with the loop and can freeze

              * the phi values at the head now.

              */

             if (targetOffset < offset) {

                 if (!freezeNewValues(cx, targetOffset))

                     return false;

             }

         }

         offset = successorOffset;

     }

     return true;

 }

 /* Get a phi node's capacity for a given length. */

 static inline unsigned

 PhiNodeCapacity(unsigned length)

 {

     if (length <= 4)

         return 4;

     return 1 << (FloorLog2(length - 1) + 1);

 }

 bool

 ScriptAnalysis::makePhi(JSContext *cx, uint32_t slot, uint32_t offset, SSAValue *pv)

 {

     SSAPhiNode *node = cx->typeLifoAlloc().new_<SSAPhiNode>();

     SSAValue *options = cx->typeLifoAlloc().newArray<SSAValue>(PhiNodeCapacity(0));

     if (!node || !options) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     node->slot = slot;

     node->options = options;

     pv->initPhi(offset, node);

     return true;

 }

 bool

 ScriptAnalysis::insertPhi(JSContext *cx, SSAValue &phi, const SSAValue &v)

 {

     JS_ASSERT(phi.kind() == SSAValue::PHI);

     SSAPhiNode *node = phi.phiNode();

     /*

      * Filter dupes inserted into small nodes to keep things clean and avoid

      * extra type constraints, but don't bother on large phi nodes to avoid

      * quadratic behavior.

      */

     if (node->length <= 8) {

         for (unsigned i = 0; i < node->length; i++) {

             if (v == node->options[i])

                 return true;

         }

     }

     if (trackUseChain(v)) {

         SSAUseChain *&uses = useChain(v);

         SSAUseChain *use = cx->typeLifoAlloc().new_<SSAUseChain>();

         if (!use) {

             js_ReportOutOfMemory(cx);

             return false;

         }

         use->popped = false;

         use->offset = phi.phiOffset();

         use->u.phi = node;

         use->next = uses;

         uses = use;

     }

     if (node->length < PhiNodeCapacity(node->length)) {

         node->options[node->length++] = v;

         return true;

     }

     SSAValue *newOptions =

         cx->typeLifoAlloc().newArray<SSAValue>(PhiNodeCapacity(node->length + 1));

     if (!newOptions) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     PodCopy(newOptions, node->options, node->length);

     node->options = newOptions;

     node->options[node->length++] = v;

     return true;

 }

 inline bool

 ScriptAnalysis::mergeValue(JSContext *cx, uint32_t offset, const SSAValue &v, SlotValue *pv)

 {

     /* Make sure that v is accounted for in the pending value or phi value at pv. */

     JS_ASSERT(v.kind() != SSAValue::EMPTY && pv->value.kind() != SSAValue::EMPTY);

     if (v == pv->value)

         return true;

     if (pv->value.kind() != SSAValue::PHI || pv->value.phiOffset() < offset) {

         SSAValue ov = pv->value;

         return makePhi(cx, pv->slot, offset, &pv->value)

             && insertPhi(cx, pv->value, v)

             && insertPhi(cx, pv->value, ov);

     }

     JS_ASSERT(pv->value.phiOffset() == offset);

     return insertPhi(cx, pv->value, v);

 }

 bool

 ScriptAnalysis::checkPendingValue(JSContext *cx, const SSAValue &v, uint32_t slot,

                                   Vector<SlotValue> *pending)

 {

     JS_ASSERT(v.kind() != SSAValue::EMPTY);

     for (unsigned i = 0; i < pending->length(); i++) {

         if ((*pending)[i].slot == slot)

             return true;

     }

     if (!pending->append(SlotValue(slot, v))) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     return true;

 }

 bool

 ScriptAnalysis::checkBranchTarget(JSContext *cx, uint32_t targetOffset,

                                   Vector<uint32_t> &branchTargets,

                                   SSAValueInfo *values, uint32_t stackDepth)

 {

     unsigned targetDepth = getCode(targetOffset).stackDepth;

     JS_ASSERT(targetDepth <= stackDepth);

     /*

      * If there is already an active branch to target, make sure its pending

      * values reflect any changes made since the first branch. Otherwise, add a

      * new pending branch and determine its pending values lazily.

      */

     Vector<SlotValue> *&pending = getCode(targetOffset).pendingValues;

     if (pending) {

         for (unsigned i = 0; i < pending->length(); i++) {

             SlotValue &v = (*pending)[i];

             if (!mergeValue(cx, targetOffset, values[v.slot].v, &v))

                 return false;

         }

     } else {

         pending = cx->new_< Vector<SlotValue> >(cx);

         if (!pending || !branchTargets.append(targetOffset)) {

             js_ReportOutOfMemory(cx);

             return false;

         }

     }

     /*

      * Make sure there is a pending entry for each value on the stack.

      * The number of stack entries at join points is usually zero, and

      * we don't want to look at the active branches while popping and

      * pushing values in each opcode.

      */

     for (unsigned i = 0; i < targetDepth; i++) {

         uint32_t slot = StackSlot(script_, i);

         if (!checkPendingValue(cx, values[slot].v, slot, pending))

             return false;

     }

     return true;

 }

 bool

 ScriptAnalysis::checkExceptionTarget(JSContext *cx, uint32_t catchOffset,

                                      Vector<uint32_t> &exceptionTargets)

 {

     JS_ASSERT(getCode(catchOffset).exceptionEntry);

     /*

      * The catch offset will already be in the branch targets, just check

      * whether this is already a known exception target.

      */

     for (unsigned i = 0; i < exceptionTargets.length(); i++) {

         if (exceptionTargets[i] == catchOffset)

             return true;

     }

     if (!exceptionTargets.append(catchOffset)) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     return true;

 }

 bool

 ScriptAnalysis::mergeBranchTarget(JSContext *cx, SSAValueInfo &value, uint32_t slot,

                                   const Vector<uint32_t> &branchTargets, uint32_t currentOffset)

 {

     if (slot >= numSlots) {

         /*

          * There is no need to lazily check that there are pending values at

          * branch targets for slots on the stack, these are added to pending

          * eagerly.

          */

         return true;

     }

     JS_ASSERT(trackSlot(slot));

     /*

      * Before changing the value of a variable, make sure the old value is

      * marked at the target of any branches jumping over the current opcode.

      * Only look at new branch targets which have appeared since the last time

      * the variable was written.

      */

     for (int i = branchTargets.length() - 1; i >= value.branchSize; i--) {

         if (branchTargets[i] <= currentOffset)

             continue;

         const Bytecode &code = getCode(branchTargets[i]);

         Vector<SlotValue> *pending = code.pendingValues;

         if (!checkPendingValue(cx, value.v, slot, pending))

             return false;

     }

     value.branchSize = branchTargets.length();

     return true;

 }

 bool

 ScriptAnalysis::mergeExceptionTarget(JSContext *cx, const SSAValue &value, uint32_t slot,

                                      const Vector<uint32_t> &exceptionTargets)

 {

     JS_ASSERT(trackSlot(slot));

     /*

      * Update the value at exception targets with the value of a variable

      * before it is overwritten. Unlike mergeBranchTarget, this is done whether

      * or not the overwritten value is the value of the variable at the

      * original branch. Values for a variable which are written after the

      * try block starts and overwritten before it is finished can still be

      * seen at exception handlers via exception paths.

      */

     for (unsigned i = 0; i < exceptionTargets.length(); i++) {

         unsigned offset = exceptionTargets[i];

         Vector<SlotValue> *pending = getCode(offset).pendingValues;

         bool duplicate = false;

         for (unsigned i = 0; i < pending->length(); i++) {

             if ((*pending)[i].slot == slot) {

                 duplicate = true;

                 SlotValue &v = (*pending)[i];

                 if (!mergeValue(cx, offset, value, &v))

                     return false;

                 break;

             }

         }

         if (!duplicate && !pending->append(SlotValue(slot, value))) {

             js_ReportOutOfMemory(cx);

             return false;

         }

     }

     return true;

 }

 bool

 ScriptAnalysis::mergeAllExceptionTargets(JSContext *cx, SSAValueInfo *values,

                                          const Vector<uint32_t> &exceptionTargets)

 {

     for (unsigned i = 0; i < exceptionTargets.length(); i++) {

         Vector<SlotValue> *pending = getCode(exceptionTargets[i]).pendingValues;

         for (unsigned i = 0; i < pending->length(); i++) {

             const SlotValue &v = (*pending)[i];

             if (trackSlot(v.slot)) {

                 if (!mergeExceptionTarget(cx, values[v.slot].v, v.slot, exceptionTargets))

                     return false;

             }

         }

     }

     return true;

 }

 bool

 ScriptAnalysis::freezeNewValues(JSContext *cx, uint32_t offset)

 {

     Bytecode &code = getCode(offset);

     Vector<SlotValue> *pending = code.pendingValues;

     code.pendingValues = nullptr;

     unsigned count = pending->length();

     if (count == 0) {

         js_delete(pending);

         return true;

     }

     code.newValues = cx->typeLifoAlloc().newArray<SlotValue>(count + 1);

     if (!code.newValues) {

         js_ReportOutOfMemory(cx);

         return false;

     }

     for (unsigned i = 0; i < count; i++)

         code.newValues[i] = (*pending)[i];

     code.newValues[count].slot = 0;

     code.newValues[count].value.clear();

     js_delete(pending);

     return true;

 }

 bool

 ScriptAnalysis::needsArgsObj(JSContext *cx, SeenVector &seen, const SSAValue &v)

 {

     /*

      * trackUseChain is false for initial values of variables, which

      * cannot hold the script's arguments object.

      */

     if (!trackUseChain(v))

         return false;

     for (unsigned i = 0; i < seen.length(); i++) {

         if (v == seen[i])

             return false;

     }

     if (!seen.append(v))

         return true;

     SSAUseChain *use = useChain(v);

     while (use) {

         if (needsArgsObj(cx, seen, use))

             return true;

         use = use->next;

     }

     return false;

 }

 bool

 ScriptAnalysis::needsArgsObj(JSContext *cx, SeenVector &seen, SSAUseChain *use)

 {

     if (!use->popped)

         return needsArgsObj(cx, seen, SSAValue::PhiValue(use->offset, use->u.phi));

     jsbytecode *pc = script_->offsetToPC(use->offset);

     JSOp op = JSOp(*pc);

     if (op == JSOP_POP || op == JSOP_POPN)

         return false;

     /* We can read the frame's arguments directly for f.apply(x, arguments). */

     if (op == JSOP_FUNAPPLY && GET_ARGC(pc) == 2 && use->u.which == 0) {

         argumentsContentsObserved_ = true;

         return false;

     }

     /* arguments[i] can read fp->canonicalActualArg(i) directly. */

     if (op == JSOP_GETELEM && use->u.which == 1) {

         argumentsContentsObserved_ = true;

         return false;

     }

     /* arguments.length length can read fp->numActualArgs() directly. */

     if (op == JSOP_LENGTH)

         return false;

     /* Allow assignments to non-closed locals (but not arguments). */

     if (op == JSOP_SETLOCAL) {

         uint32_t slot = GetBytecodeSlot(script_, pc);

         if (!trackSlot(slot))

             return true;

         return needsArgsObj(cx, seen, SSAValue::PushedValue(use->offset, 0)) ||

                needsArgsObj(cx, seen, SSAValue::WrittenVar(slot, use->offset));

     }

     if (op == JSOP_GETLOCAL)

         return needsArgsObj(cx, seen, SSAValue::PushedValue(use->offset, 0));

     return true;

 }

 bool

 ScriptAnalysis::needsArgsObj(JSContext *cx)

 {

     JS_ASSERT(script_->argumentsHasVarBinding());

     /*

      * Always construct arguments objects when in debug mode and for generator

      * scripts (generators can be suspended when speculation fails).

      *

      * FIXME: Don't build arguments for ES6 generator expressions.

      */

     if (cx->compartment()->debugMode() || script_->isGenerator())

         return true;

     /*

      * If the script has dynamic name accesses which could reach 'arguments',

      * the parser will already have checked to ensure there are no explicit

      * uses of 'arguments' in the function. If there are such uses, the script

      * will be marked as definitely needing an arguments object.

      *

      * New accesses on 'arguments' can occur through 'eval' or the debugger

      * statement. In the former case, we will dynamically detect the use and

      * mark the arguments optimization as having failed.

      */

     if (script_->bindingsAccessedDynamically())

         return false;

     unsigned pcOff = script_->pcToOffset(script_->argumentsBytecode());

     SeenVector seen(cx);

     if (needsArgsObj(cx, seen, SSAValue::PushedValue(pcOff, 0)))

         return true;

     /*

      * If a script explicitly accesses the contents of 'arguments', and has

      * formals which may be stored as part of a call object, don't use lazy

      * arguments. The compiler can then assume that accesses through

      * arguments[i] will be on unaliased variables.

      */

     if (script_->funHasAnyAliasedFormal() && argumentsContentsObserved_)

         return true;

     return false;

 }

 #ifdef DEBUG

 void

 ScriptAnalysis::printSSA(JSContext *cx)

 {

     types::AutoEnterAnalysis enter(cx);

     printf("\n");

     RootedScript script(cx, script_);

     for (unsigned offset = 0; offset < script_->length(); offset++) {

         Bytecode *code = maybeCode(offset);

         if (!code)

             continue;

         jsbytecode *pc = script_->offsetToPC(offset);

         PrintBytecode(cx, script, pc);

         SlotValue *newv = code->newValues;

         if (newv) {

             while (newv->slot) {

                 if (newv->value.kind() != SSAValue::PHI || newv->value.phiOffset() != offset) {

                     newv++;

                     continue;

                 }

                 printf("  phi ");

                 newv->value.print();

                 printf(" [");

                 for (unsigned i = 0; i < newv->value.phiLength(); i++) {

                     if (i)

                         printf(",");

                     newv->value.phiValue(i).print();

                 }

                 printf("]\n");

                 newv++;

             }

         }

         unsigned nuses = GetUseCount(script_, offset);

         unsigned xuses = ExtendedUse(pc) ? nuses + 1 : nuses;

         for (unsigned i = 0; i < xuses; i++) {

             printf("  popped%d: ", i);

             code->poppedValues[i].print();

             printf("\n");

         }

     }

     printf("\n");

 }

 void

 SSAValue::print() const

 {

     switch (kind()) {

       case EMPTY:

         printf("empty");

         break;

       case PUSHED:

         printf("pushed:%05u#%u", pushedOffset(), pushedIndex());

         break;

       case VAR:

         if (varInitial())

             printf("initial:%u", varSlot());

         else

             printf("write:%05u", varOffset());

         break;

       case PHI:

         printf("phi:%05u#%u", phiOffset(), phiSlot());

         break;

       default:

         MOZ_ASSUME_UNREACHABLE("Bad kind");

     }

 }

 void

 ScriptAnalysis::assertMatchingDebugMode()

 {

     JS_ASSERT(!!script_->compartment()->debugMode() == !!originalDebugMode_);

 }

 void

 ScriptAnalysis::assertMatchingStackDepthAtOffset(uint32_t offset, uint32_t stackDepth) {

     JS_ASSERT_IF(maybeCode(offset), getCode(offset).stackDepth == stackDepth);

 }

 #endif  /* DEBUG */

 } // namespace analyze

 } // namespace js