https://github.com/mozilla/gecko-dev
Tip revision: 899c4da66f0c15117a7a744a2ce47765448f3993 authored by ffxbld on 11 March 2014, 00:25:43 UTC
Added FIREFOX_28_0_RELEASE FIREFOX_28_0_BUILD1 tag(s) for changeset 4095d6ad79b1. DONTBUILD CLOSED TREE a=release
Added FIREFOX_28_0_RELEASE FIREFOX_28_0_BUILD1 tag(s) for changeset 4095d6ad79b1. DONTBUILD CLOSED TREE a=release
Tip revision: 899c4da
jsanalyze.h
/* -*- 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/. */
/* Definitions for javascript analysis. */
#ifndef jsanalyze_h
#define jsanalyze_h
#include "jscompartment.h"
namespace js {
namespace analyze {
class LoopAnalysis;
class SlotValue;
class SSAValue;
class SSAUseChain;
/*
* 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;
};
};
/*
* 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_CALLARG:
case JSOP_GETLOCAL:
case JSOP_CALLLOCAL:
return true;
default:
return false;
}
}
static inline JSOp
ReverseCompareOp(JSOp op)
{
switch (op) {
case JSOP_GT:
return JSOP_LT;
case JSOP_GE:
return JSOP_LE;
case JSOP_LT:
return JSOP_GT;
case JSOP_LE:
return JSOP_GE;
case JSOP_EQ:
case JSOP_NE:
case JSOP_STRICTEQ:
case JSOP_STRICTNE:
return op;
default:
MOZ_ASSUME_UNREACHABLE("unrecognized op");
}
}
static inline JSOp
NegateCompareOp(JSOp op)
{
switch (op) {
case JSOP_GT:
return JSOP_LE;
case JSOP_GE:
return JSOP_LT;
case JSOP_LT:
return JSOP_GE;
case JSOP_LE:
return JSOP_GT;
case JSOP_EQ:
return JSOP_NE;
case JSOP_NE:
return JSOP_EQ;
case JSOP_STRICTNE:
return JSOP_STRICTEQ;
case JSOP_STRICTEQ:
return JSOP_STRICTNE;
default:
MOZ_ASSUME_UNREACHABLE("unrecognized op");
}
}
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;
}
/* Common representation of slots throughout analyses and the compiler. */
static inline uint32_t ThisSlot() {
return 0;
}
static inline uint32_t ArgSlot(uint32_t arg) {
return 1 + arg;
}
static inline uint32_t LocalSlot(JSScript *script, uint32_t local) {
return 1 + (script->function() ? script->function()->nargs : 0) + local;
}
static inline uint32_t TotalSlots(JSScript *script) {
return LocalSlot(script, 0) + script->nfixed;
}
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_CALLARG:
case JSOP_SETARG:
return ArgSlot(GET_SLOTNO(pc));
case JSOP_GETLOCAL:
case JSOP_CALLLOCAL:
case JSOP_SETLOCAL:
return LocalSlot(script, GET_SLOTNO(pc));
case JSOP_THIS:
return ThisSlot();
default:
MOZ_ASSUME_UNREACHABLE("Bad slot opcode");
}
}
/*
* 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) {}
};
struct NeedsArgsObjState;
/* Analysis information about a script. */
class ScriptAnalysis
{
friend class Bytecode;
JSScript *script_;
Bytecode **codeArray;
uint32_t numSlots;
uint32_t numPropertyReads_;
bool outOfMemory;
bool hadFailure;
bool *escapedSlots;
/* Which analyses have been performed. */
bool ranBytecode_;
bool ranSSA_;
bool ranLifetimes_;
#ifdef DEBUG
/* Whether the compartment was in debug mode when we performed the analysis. */
bool originalDebugMode_: 1;
#endif
/* --------- Bytecode analysis --------- */
bool usesScopeChain_:1;
bool localsAliasStack_:1;
bool canTrackVars:1;
bool hasLoops_:1;
bool hasTryFinally_:1;
bool argumentsContentsObserved_:1;
uint32_t numReturnSites_;
/* --------- Lifetime analysis --------- */
LifetimeVariable *lifetimes;
public:
ScriptAnalysis(JSScript *script) {
mozilla::PodZero(this);
this->script_ = script;
#ifdef DEBUG
this->originalDebugMode_ = script_->compartment()->debugMode();
#endif
}
bool ranBytecode() { return ranBytecode_; }
bool ranSSA() { return ranSSA_; }
bool ranLifetimes() { return ranLifetimes_; }
void analyzeBytecode(JSContext *cx);
void analyzeSSA(JSContext *cx);
void analyzeLifetimes(JSContext *cx);
bool OOM() const { return outOfMemory; }
bool failed() const { return hadFailure; }
/* Whether the script has a |finally| block. */
bool hasTryFinally() const { return hasTryFinally_; }
/* Number of property read opcodes in the script. */
uint32_t numPropertyReads() const { return numPropertyReads_; }
/* Whether there are NAME bytecodes which can access the frame's scope chain. */
bool usesScopeChain() const { return usesScopeChain_; }
uint32_t numReturnSites() const { return numReturnSites_; }
bool hasLoops() const { return hasLoops_; }
/*
* True if there are any LOCAL opcodes aliasing values on the stack (above
* script_->nfixed).
*/
bool localsAliasStack() { return localsAliasStack_; }
/* Accessors for bytecode information. */
Bytecode& getCode(uint32_t offset) {
JS_ASSERT(offset < script_->length());
JS_ASSERT(codeArray[offset]);
return *codeArray[offset];
}
Bytecode& getCode(const jsbytecode *pc) { return getCode(script_->pcToOffset(pc)); }
Bytecode* maybeCode(uint32_t offset) {
JS_ASSERT(offset < script_->length());
return codeArray[offset];
}
Bytecode* maybeCode(const jsbytecode *pc) { return maybeCode(script_->pcToOffset(pc)); }
bool jumpTarget(uint32_t offset) {
JS_ASSERT(offset < script_->length());
return codeArray[offset] && codeArray[offset]->jumpTarget;
}
bool jumpTarget(const jsbytecode *pc) { return jumpTarget(script_->pcToOffset(pc)); }
bool popGuaranteed(jsbytecode *pc) {
jsbytecode *next = pc + GetBytecodeLength(pc);
return JSOp(*next) == JSOP_POP && !jumpTarget(next);
}
inline const SSAValue &poppedValue(uint32_t offset, uint32_t which);
inline const SSAValue &poppedValue(const jsbytecode *pc, uint32_t which);
const SlotValue *newValues(uint32_t offset) {
JS_ASSERT(offset < script_->length());
return getCode(offset).newValues;
}
const SlotValue *newValues(const jsbytecode *pc) { return newValues(script_->pcToOffset(pc)); }
bool 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. May be invalid for some opcodes in
* scripts where localsAliasStack(). You have been warned!
*/
inline SSAUseChain *& useChain(const SSAValue &v);
/* For a JSOP_CALL* op, get the pc of the corresponding JSOP_CALL/NEW/etc. */
inline jsbytecode *getCallPC(jsbytecode *pc);
/* 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).
*/
bool 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.
*/
bool trackSlot(uint32_t slot) { return !slotEscapes(slot) && canTrackVars && slot < 1000; }
const LifetimeVariable & liveness(uint32_t slot) {
JS_ASSERT(script_->compartment()->activeAnalysis);
JS_ASSERT(!slotEscapes(slot));
return lifetimes[slot];
}
void printSSA(JSContext *cx);
void printTypes(JSContext *cx);
private:
void setOOM(JSContext *cx) {
if (!outOfMemory)
js_ReportOutOfMemory(cx);
outOfMemory = true;
hadFailure = true;
}
/* Bytecode helpers */
inline bool addJump(JSContext *cx, unsigned offset,
unsigned *currentOffset, unsigned *forwardJump, unsigned *forwardLoop,
unsigned stackDepth);
/* Lifetime helpers */
inline void addVariable(JSContext *cx, LifetimeVariable &var, unsigned offset,
LifetimeVariable **&saved, unsigned &savedCount);
inline void killVariable(JSContext *cx, LifetimeVariable &var, unsigned offset,
LifetimeVariable **&saved, unsigned &savedCount);
inline void extendVariable(JSContext *cx, LifetimeVariable &var, unsigned start, unsigned end);
inline void ensureVariable(LifetimeVariable &var, unsigned until);
/* 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;
};
/* SSA helpers */
bool makePhi(JSContext *cx, uint32_t slot, uint32_t offset, SSAValue *pv);
void insertPhi(JSContext *cx, SSAValue &phi, const SSAValue &v);
void mergeValue(JSContext *cx, uint32_t offset, const SSAValue &v, SlotValue *pv);
void checkPendingValue(JSContext *cx, const SSAValue &v, uint32_t slot,
Vector<SlotValue> *pending);
void checkBranchTarget(JSContext *cx, uint32_t targetOffset, Vector<uint32_t> &branchTargets,
SSAValueInfo *values, uint32_t stackDepth);
void checkExceptionTarget(JSContext *cx, uint32_t catchOffset,
Vector<uint32_t> &exceptionTargets);
void mergeBranchTarget(JSContext *cx, SSAValueInfo &value, uint32_t slot,
const Vector<uint32_t> &branchTargets, uint32_t currentOffset);
void mergeExceptionTarget(JSContext *cx, const SSAValue &value, uint32_t slot,
const Vector<uint32_t> &exceptionTargets);
void mergeAllExceptionTargets(JSContext *cx, SSAValueInfo *values,
const Vector<uint32_t> &exceptionTargets);
void freezeNewValues(JSContext *cx, uint32_t offset);
typedef Vector<SSAValue, 16> SeenVector;
bool needsArgsObj(JSContext *cx, SeenVector &seen, const SSAValue &v);
bool needsArgsObj(JSContext *cx, SeenVector &seen, SSAUseChain *use);
bool needsArgsObj(JSContext *cx);
public:
#ifdef DEBUG
void assertMatchingDebugMode();
#else
void assertMatchingDebugMode() { }
#endif
};
#ifdef DEBUG
void PrintBytecode(JSContext *cx, HandleScript script, jsbytecode *pc);
#endif
} /* 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 */
#endif /* jsanalyze_h */