Google Git
Sign in
cobalt / cobalt / 4fe09471d0134f1d49ad5034a1c8867d6f9f4551 / . / src / third_party / mozjs / js / src / jit / IonBuilder.cpp
blob: c5ee14744fa078d5fddf1c9713240521c7a39feb [file] [log] [blame]
/* -*- 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 "jit/IonBuilder.h"
#include "mozilla/DebugOnly.h"
#include "builtin/Eval.h"
#include "frontend/SourceNotes.h"
#include "jit/BaselineInspector.h"
#include "jit/Ion.h"
#include "jit/IonAnalysis.h"
#include "jit/IonAnalysis.h"
#include "jit/IonSpewer.h"
#include "jit/Lowering.h"
#include "jit/MIRGraph.h"
#include "CompileInfo-inl.h"
#include "ExecutionModeInlines.h"
#include "jsanalyzeinlines.h"
#include "jsscriptinlines.h"
#include "jstypedarrayinlines.h"
#ifdef JS_THREADSAFE
#if defined(STARBOARD)
#include "starboard/client_porting/pr_starboard/pr_starboard.h"
#else
# include "prthread.h"
#endif // defined(STARBOARD)
#endif
using namespace js;
using namespace js::jit;
using mozilla::DebugOnly;
IonBuilder::IonBuilder(JSContext *cx, TempAllocator *temp, MIRGraph *graph,
BaselineInspector *inspector, CompileInfo *info, BaselineFrame *baselineFrame,
size_t inliningDepth, uint32_t loopDepth)
: MIRGenerator(cx->compartment(), temp, graph, info),
backgroundCodegen_(NULL),
recompileInfo(cx->compartment()->types.compiledInfo),
cx(cx),
baselineFrame_(baselineFrame),
abortReason_(AbortReason_Disable),
loopDepth_(loopDepth),
callerResumePoint_(NULL),
callerBuilder_(NULL),
inspector(inspector),
inliningDepth_(inliningDepth),
numLoopRestarts_(0),
failedBoundsCheck_(info->script()->failedBoundsCheck),
failedShapeGuard_(info->script()->failedShapeGuard),
nonStringIteration_(false),
lazyArguments_(NULL),
inlineCallInfo_(NULL)
{
script_.init(info->script());
pc = info->startPC();
}
void
IonBuilder::clearForBackEnd()
{
cx = NULL;
baselineFrame_ = NULL;
}
bool
IonBuilder::abort(const char *message, ...)
{
// Don't call PCToLineNumber in release builds.
#ifdef DEBUG
va_list ap;
va_start(ap, message);
abortFmt(message, ap);
va_end(ap);
IonSpew(IonSpew_Abort, "aborted @ %s:%d", script()->filename(), PCToLineNumber(script(), pc));
#endif
return false;
}
void
IonBuilder::spew(const char *message)
{
// Don't call PCToLineNumber in release builds.
#ifdef DEBUG
IonSpew(IonSpew_MIR, "%s @ %s:%d", message, script()->filename(), PCToLineNumber(script(), pc));
#endif
}
static inline int32_t
GetJumpOffset(jsbytecode *pc)
{
JS_ASSERT(js_CodeSpec[JSOp(*pc)].type() == JOF_JUMP);
return GET_JUMP_OFFSET(pc);
}
IonBuilder::CFGState
IonBuilder::CFGState::If(jsbytecode *join, MBasicBlock *ifFalse)
{
CFGState state;
state.state = IF_TRUE;
state.stopAt = join;
state.branch.ifFalse = ifFalse;
return state;
}
IonBuilder::CFGState
IonBuilder::CFGState::IfElse(jsbytecode *trueEnd, jsbytecode *falseEnd, MBasicBlock *ifFalse)
{
CFGState state;
// If the end of the false path is the same as the start of the
// false path, then the "else" block is empty and we can devolve
// this to the IF_TRUE case. We handle this here because there is
// still an extra GOTO on the true path and we want stopAt to point
// there, whereas the IF_TRUE case does not have the GOTO.
state.state = (falseEnd == ifFalse->pc())
? IF_TRUE_EMPTY_ELSE
: IF_ELSE_TRUE;
state.stopAt = trueEnd;
state.branch.falseEnd = falseEnd;
state.branch.ifFalse = ifFalse;
return state;
}
IonBuilder::CFGState
IonBuilder::CFGState::AndOr(jsbytecode *join, MBasicBlock *joinStart)
{
CFGState state;
state.state = AND_OR;
state.stopAt = join;
state.branch.ifFalse = joinStart;
return state;
}
IonBuilder::CFGState
IonBuilder::CFGState::TableSwitch(jsbytecode *exitpc, MTableSwitch *ins)
{
CFGState state;
state.state = TABLE_SWITCH;
state.stopAt = exitpc;
state.tableswitch.exitpc = exitpc;
state.tableswitch.breaks = NULL;
state.tableswitch.ins = ins;
state.tableswitch.currentBlock = 0;
return state;
}
JSFunction *
IonBuilder::getSingleCallTarget(types::StackTypeSet *calleeTypes)
{
if (!calleeTypes)
return NULL;
JSObject *obj = calleeTypes->getSingleton();
if (!obj || !obj->is<JSFunction>())
return NULL;
return &obj->as<JSFunction>();
}
bool
IonBuilder::getPolyCallTargets(types::StackTypeSet *calleeTypes,
AutoObjectVector &targets,
uint32_t maxTargets,
bool *gotLambda)
{
JS_ASSERT(targets.length() == 0);
JS_ASSERT(gotLambda);
*gotLambda = false;
if (!calleeTypes)
return true;
if (calleeTypes->baseFlags() != 0)
return true;
unsigned objCount = calleeTypes->getObjectCount();
if (objCount == 0 || objCount > maxTargets)
return true;
if (!targets.reserve(objCount))
return false;
for(unsigned i = 0; i < objCount; i++) {
JSObject *obj = calleeTypes->getSingleObject(i);
if (obj) {
if (!obj->is<JSFunction>()) {
targets.clear();
return true;
}
if (obj->as<JSFunction>().isInterpreted() &&
!obj->as<JSFunction>().getOrCreateScript(cx))
{
return false;
}
DebugOnly<bool> appendOk = targets.append(obj);
JS_ASSERT(appendOk);
} else {
/* Temporarily disable heavyweight-function inlining. */
targets.clear();
return true;
#if 0
types::TypeObject *typeObj = calleeTypes->getTypeObject(i);
JS_ASSERT(typeObj);
if (!typeObj->isFunction() || !typeObj->interpretedFunction) {
targets.clear();
return true;
}
if (!typeObj->interpretedFunction->getOrCreateScript(cx))
return false;
DebugOnly<bool> appendOk = targets.append(typeObj->interpretedFunction);
JS_ASSERT(appendOk);
*gotLambda = true;
#endif
}
}
// For now, only inline "singleton" lambda calls
if (*gotLambda && targets.length() > 1)
targets.clear();
return true;
}
bool
IonBuilder::canEnterInlinedFunction(JSFunction *target)
{
RootedScript targetScript(cx, target->nonLazyScript());
if (!targetScript->ensureRanAnalysis(cx))
return false;
if (!targetScript->analysis()->ionInlineable())
return false;
if (targetScript->needsArgsObj())
return false;
if (!targetScript->compileAndGo)
return false;
types::TypeObject *targetType = target->getType(cx);
if (!targetType || targetType->unknownProperties())
return false;
return true;
}
bool
IonBuilder::canInlineTarget(JSFunction *target)
{
if (!target->isInterpreted()) {
IonSpew(IonSpew_Inlining, "Cannot inline due to non-interpreted");
return false;
}
if (target->getParent() != &script()->global()) {
IonSpew(IonSpew_Inlining, "Cannot inline due to scope mismatch");
return false;
}
RootedScript inlineScript(cx, target->nonLazyScript());
ExecutionMode executionMode = info().executionMode();
if (!CanIonCompile(inlineScript, executionMode)) {
IonSpew(IonSpew_Inlining, "%s:%d Cannot inline due to disable Ion compilation",
inlineScript->filename(), inlineScript->lineno);
return false;
}
// Don't inline functions which don't have baseline scripts compiled for them.
if (executionMode == SequentialExecution && !inlineScript->hasBaselineScript()) {
IonSpew(IonSpew_Inlining, "%s:%d Cannot inline target with no baseline jitcode",
inlineScript->filename(), inlineScript->lineno);
return false;
}
// Allow inlining of recursive calls, but only one level deep.
IonBuilder *builder = callerBuilder_;
while (builder) {
if (builder->script() == inlineScript) {
IonSpew(IonSpew_Inlining, "%s:%d Not inlining recursive call",
inlineScript->filename(), inlineScript->lineno);
return false;
}
builder = builder->callerBuilder_;
}
if (!canEnterInlinedFunction(target)) {
IonSpew(IonSpew_Inlining, "%s:%d Cannot inline due to oracle veto %d",
inlineScript->filename(), inlineScript->lineno,
script()->lineno);
return false;
}
return true;
}
void
IonBuilder::popCfgStack()
{
if (cfgStack_.back().isLoop())
loops_.popBack();
if (cfgStack_.back().state == CFGState::LABEL)
labels_.popBack();
cfgStack_.popBack();
}
void
IonBuilder::analyzeNewLoopTypes(MBasicBlock *entry, jsbytecode *start, jsbytecode *end)
{
// The phi inputs at the loop head only reflect types for variables that
// were present at the start of the loop. If the variable changes to a new
// type within the loop body, and that type is carried around to the loop
// head, then we need to know about the new type up front.
//
// Since SSA information hasn't been constructed for the loop body yet, we
// need a separate analysis to pick out the types that might flow around
// the loop header. This is a best-effort analysis that may either over-
// or under-approximate the set of such types.
//
// Over-approximating the types may lead to inefficient generated code, and
// under-approximating the types will cause the loop body to be analyzed
// multiple times as the correct types are deduced (see finishLoop).
jsbytecode *last = NULL, *earlier = NULL;
for (jsbytecode *pc = start; pc != end; earlier = last, last = pc, pc += GetBytecodeLength(pc)) {
uint32_t slot;
if (*pc == JSOP_SETLOCAL)
slot = info().localSlot(GET_SLOTNO(pc));
else if (*pc == JSOP_SETARG)
slot = info().argSlotUnchecked(GET_SLOTNO(pc));
else
continue;
if (slot >= info().firstStackSlot())
continue;
if (!script()->analysis()->maybeCode(pc))
continue;
MPhi *phi = entry->getSlot(slot)->toPhi();
if (*last == JSOP_POS)
last = earlier;
if (js_CodeSpec[*last].format & JOF_TYPESET) {
types::StackTypeSet *typeSet = types::TypeScript::BytecodeTypes(script(), last);
if (!typeSet->empty()) {
MIRType type = MIRTypeFromValueType(typeSet->getKnownTypeTag());
phi->addBackedgeType(type, typeSet);
}
} else if (*last == JSOP_GETLOCAL || *last == JSOP_GETARG) {
uint32_t slot = (*last == JSOP_GETLOCAL)
? info().localSlot(GET_SLOTNO(last))
: info().argSlotUnchecked(GET_SLOTNO(last));
if (slot < info().firstStackSlot()) {
MPhi *otherPhi = entry->getSlot(slot)->toPhi();
if (otherPhi->hasBackedgeType())
phi->addBackedgeType(otherPhi->type(), otherPhi->resultTypeSet());
}
} else {
MIRType type = MIRType_None;
switch (*last) {
case JSOP_VOID:
case JSOP_UNDEFINED:
type = MIRType_Undefined;
break;
case JSOP_NULL:
type = MIRType_Null;
break;
case JSOP_ZERO:
case JSOP_ONE:
case JSOP_INT8:
case JSOP_INT32:
case JSOP_UINT16:
case JSOP_UINT24:
case JSOP_BITAND:
case JSOP_BITOR:
case JSOP_BITXOR:
case JSOP_BITNOT:
case JSOP_RSH:
case JSOP_LSH:
case JSOP_URSH:
type = MIRType_Int32;
break;
case JSOP_FALSE:
case JSOP_TRUE:
case JSOP_EQ:
case JSOP_NE:
case JSOP_LT:
case JSOP_LE:
case JSOP_GT:
case JSOP_GE:
case JSOP_NOT:
case JSOP_STRICTEQ:
case JSOP_STRICTNE:
case JSOP_IN:
case JSOP_INSTANCEOF:
type = MIRType_Boolean;
break;
case JSOP_DOUBLE:
type = MIRType_Double;
break;
case JSOP_STRING:
case JSOP_TYPEOF:
case JSOP_TYPEOFEXPR:
case JSOP_ITERNEXT:
type = MIRType_String;
break;
case JSOP_ADD:
case JSOP_SUB:
case JSOP_MUL:
case JSOP_DIV:
case JSOP_MOD:
case JSOP_NEG:
type = inspector->expectedResultType(last);
default:
break;
}
if (type != MIRType_None)
phi->addBackedgeType(type, NULL);
}
}
}
bool
IonBuilder::pushLoop(CFGState::State initial, jsbytecode *stopAt, MBasicBlock *entry, bool osr,
jsbytecode *loopHead, jsbytecode *initialPc,
jsbytecode *bodyStart, jsbytecode *bodyEnd, jsbytecode *exitpc,
jsbytecode *continuepc)
{
if (!continuepc)
continuepc = entry->pc();
ControlFlowInfo loop(cfgStack_.length(), continuepc);
if (!loops_.append(loop))
return false;
CFGState state;
state.state = initial;
state.stopAt = stopAt;
state.loop.bodyStart = bodyStart;
state.loop.bodyEnd = bodyEnd;
state.loop.exitpc = exitpc;
state.loop.continuepc = continuepc;
state.loop.entry = entry;
state.loop.osr = osr;
state.loop.successor = NULL;
state.loop.breaks = NULL;
state.loop.continues = NULL;
state.loop.initialState = initial;
state.loop.initialPc = initialPc;
state.loop.initialStopAt = stopAt;
state.loop.loopHead = loopHead;
return cfgStack_.append(state);
}
bool
IonBuilder::build()
{
if (!script()->ensureHasBytecodeTypeMap(cx))
return false;
setCurrentAndSpecializePhis(newBlock(pc));
if (!current)
return false;
IonSpew(IonSpew_Scripts, "Analyzing script %s:%d (%p) (usecount=%d)",
script()->filename(), script()->lineno, (void *)script(), (int)script()->getUseCount());
if (!graph().addScript(script()))
return false;
if (!initParameters())
return false;
// Initialize local variables.
for (uint32_t i = 0; i < info().nlocals(); i++) {
MConstant *undef = MConstant::New(UndefinedValue());
current->add(undef);
current->initSlot(info().localSlot(i), undef);
}
// Initialize something for the scope chain. We can bail out before the
// start instruction, but the snapshot is encoded *at* the start
// instruction, which means generating any code that could load into
// registers is illegal.
{
MInstruction *scope = MConstant::New(UndefinedValue());
current->add(scope);
current->initSlot(info().scopeChainSlot(), scope);
}
// Initialize the arguments object slot to undefined if necessary.
if (info().hasArguments()) {
MInstruction *argsObj = MConstant::New(UndefinedValue());
current->add(argsObj);
current->initSlot(info().argsObjSlot(), argsObj);
}
// Emit the start instruction, so we can begin real instructions.
current->makeStart(MStart::New(MStart::StartType_Default));
if (instrumentedProfiling())
current->add(MFunctionBoundary::New(script(), MFunctionBoundary::Enter));
// Parameters have been checked to correspond to the typeset, now we unbox
// what we can in an infallible manner.
rewriteParameters();
// It's safe to start emitting actual IR, so now build the scope chain.
if (!initScopeChain())
return false;
if (info().needsArgsObj() && !initArgumentsObject())
return false;
// Guard against over-recursion.
MCheckOverRecursed *check = new MCheckOverRecursed;
current->add(check);
check->setResumePoint(current->entryResumePoint());
// Prevent |this| from being DCE'd: necessary for constructors.
if (info().fun())
current->getSlot(info().thisSlot())->setGuard();
// The type analysis phase attempts to insert unbox operations near
// definitions of values. It also attempts to replace uses in resume points
// with the narrower, unboxed variants. However, we must prevent this
// replacement from happening on values in the entry snapshot. Otherwise we
// could get this:
//
// v0 = MParameter(0)
// v1 = MParameter(1)
// -- ResumePoint(v2, v3)
// v2 = Unbox(v0, INT32)
// v3 = Unbox(v1, INT32)
//
// So we attach the initial resume point to each parameter, which the type
// analysis explicitly checks (this is the same mechanism used for
// effectful operations).
for (uint32_t i = 0; i < info().endArgSlot(); i++) {
MInstruction *ins = current->getEntrySlot(i)->toInstruction();
if (ins->type() == MIRType_Value)
ins->setResumePoint(current->entryResumePoint());
}
// lazyArguments should never be accessed in |argsObjAliasesFormals| scripts.
if (info().hasArguments() && !info().argsObjAliasesFormals()) {
lazyArguments_ = MConstant::New(MagicValue(JS_OPTIMIZED_ARGUMENTS));
current->add(lazyArguments_);
}
if (!traverseBytecode())
return false;
if (!processIterators())
return false;
types::TypeScript::AddFreezeConstraints(cx, script());
JS_ASSERT(loopDepth_ == 0);
abortReason_ = AbortReason_NoAbort;
return true;
}
bool
IonBuilder::processIterators()
{
// Find phis that must directly hold an iterator live.
Vector<MPhi *, 0, SystemAllocPolicy> worklist;
for (size_t i = 0; i < iterators_.length(); i++) {
MInstruction *ins = iterators_[i];
for (MUseDefIterator iter(ins); iter; iter++) {
if (iter.def()->isPhi()) {
if (!worklist.append(iter.def()->toPhi()))
return false;
}
}
}
// Propagate the iterator and live status of phis to all other connected
// phis.
while (!worklist.empty()) {
MPhi *phi = worklist.popCopy();
phi->setIterator();
phi->setFoldedUnchecked();
for (MUseDefIterator iter(phi); iter; iter++) {
if (iter.def()->isPhi()) {
MPhi *other = iter.def()->toPhi();
if (!other->isIterator() && !worklist.append(other))
return false;
}
}
}
return true;
}
bool
IonBuilder::buildInline(IonBuilder *callerBuilder, MResumePoint *callerResumePoint,
CallInfo &callInfo)
{
inlineCallInfo_ = &callInfo;
if (!script()->ensureHasBytecodeTypeMap(cx))
return false;
IonSpew(IonSpew_Scripts, "Inlining script %s:%d (%p)",
script()->filename(), script()->lineno, (void *)script());
if (!graph().addScript(script()))
return false;
callerBuilder_ = callerBuilder;
callerResumePoint_ = callerResumePoint;
if (callerBuilder->failedBoundsCheck_)
failedBoundsCheck_ = true;
if (callerBuilder->failedShapeGuard_)
failedShapeGuard_ = true;
// Generate single entrance block.
setCurrentAndSpecializePhis(newBlock(pc));
if (!current)
return false;
current->setCallerResumePoint(callerResumePoint);
// Connect the entrance block to the last block in the caller's graph.
MBasicBlock *predecessor = callerBuilder->current;
JS_ASSERT(predecessor == callerResumePoint->block());
// All further instructions generated in from this scope should be
// considered as part of the function that we're inlining. We also need to
// keep track of the inlining depth because all scripts inlined on the same
// level contiguously have only one Inline_Exit node.
if (instrumentedProfiling())
predecessor->add(MFunctionBoundary::New(script(),
MFunctionBoundary::Inline_Enter,
inliningDepth_));
predecessor->end(MGoto::New(current));
if (!current->addPredecessorWithoutPhis(predecessor))
return false;
// Initialize scope chain slot to Undefined. It's set later by |initScopeChain|.
{
MInstruction *scope = MConstant::New(UndefinedValue());
current->add(scope);
current->initSlot(info().scopeChainSlot(), scope);
}
// Initialize |arguments| slot.
if (info().hasArguments()) {
MInstruction *argsObj = MConstant::New(UndefinedValue());
current->add(argsObj);
current->initSlot(info().argsObjSlot(), argsObj);
}
// Initialize |this| slot.
current->initSlot(info().thisSlot(), callInfo.thisArg());
IonSpew(IonSpew_Inlining, "Initializing %u arg slots", info().nargs());
// NB: Ion does not inline functions which |needsArgsObj|. So using argSlot()
// instead of argSlotUnchecked() below is OK
JS_ASSERT(!info().needsArgsObj());
// Initialize actually set arguments.
uint32_t existing_args = Min<uint32_t>(callInfo.argc(), info().nargs());
for (size_t i = 0; i < existing_args; ++i) {
MDefinition *arg = callInfo.getArg(i);
current->initSlot(info().argSlot(i), arg);
}
// Pass Undefined for missing arguments
for (size_t i = callInfo.argc(); i < info().nargs(); ++i) {
MConstant *arg = MConstant::New(UndefinedValue());
current->add(arg);
current->initSlot(info().argSlot(i), arg);
}
// Initialize the scope chain now that args are initialized.
if (!initScopeChain(callInfo.fun()))
return false;
IonSpew(IonSpew_Inlining, "Initializing %u local slots", info().nlocals());
// Initialize local variables.
for (uint32_t i = 0; i < info().nlocals(); i++) {
MConstant *undef = MConstant::New(UndefinedValue());
current->add(undef);
current->initSlot(info().localSlot(i), undef);
}
IonSpew(IonSpew_Inlining, "Inline entry block MResumePoint %p, %u operands",
(void *) current->entryResumePoint(), current->entryResumePoint()->numOperands());
// +2 for the scope chain and |this|, maybe another +1 for arguments object slot.
JS_ASSERT(current->entryResumePoint()->numOperands() == info().totalSlots());
if (script_->argumentsHasVarBinding()) {
lazyArguments_ = MConstant::New(MagicValue(JS_OPTIMIZED_ARGUMENTS));
current->add(lazyArguments_);
}
if (!traverseBytecode())
return false;
types::TypeScript::AddFreezeConstraints(cx, script());
return true;
}
void
IonBuilder::rewriteParameter(uint32_t slotIdx, MDefinition *param, int32_t argIndex)
{
JS_ASSERT(param->isParameter() || param->isGetArgumentsObjectArg());
// Find the original (not cloned) type set for the MParameter, as we
// will be adding constraints to it.
types::StackTypeSet *types;
if (argIndex == MParameter::THIS_SLOT)
types = types::TypeScript::ThisTypes(script());
else
types = types::TypeScript::ArgTypes(script(), argIndex);
JSValueType definiteType = types->getKnownTypeTag();
if (definiteType == JSVAL_TYPE_UNKNOWN)
return;
MInstruction *actual = NULL;
switch (definiteType) {
case JSVAL_TYPE_UNDEFINED:
param->setFoldedUnchecked();
actual = MConstant::New(UndefinedValue());
break;
case JSVAL_TYPE_NULL:
param->setFoldedUnchecked();
actual = MConstant::New(NullValue());
break;
default:
actual = MUnbox::New(param, MIRTypeFromValueType(definiteType), MUnbox::Infallible);
break;
}
// Careful! We leave the original MParameter in the entry resume point. The
// arguments still need to be checked unless proven otherwise at the call
// site, and these checks can bailout. We can end up:
// v0 = Parameter(0)
// v1 = Unbox(v0, INT32)
// -- ResumePoint(v0)
//
// As usual, it would be invalid for v1 to be captured in the initial
// resume point, rather than v0.
current->add(actual);
current->rewriteSlot(slotIdx, actual);
}
// Apply Type Inference information to parameters early on, unboxing them if
// they have a definitive type. The actual guards will be emitted by the code
// generator, explicitly, as part of the function prologue.
void
IonBuilder::rewriteParameters()
{
JS_ASSERT(info().scopeChainSlot() == 0);
if (!info().fun())
return;
for (uint32_t i = info().startArgSlot(); i < info().endArgSlot(); i++) {
MDefinition *param = current->getSlot(i);
rewriteParameter(i, param, param->toParameter()->index());
}
}
bool
IonBuilder::initParameters()
{
if (!info().fun())
return true;
MParameter *param = MParameter::New(MParameter::THIS_SLOT,
cloneTypeSet(types::TypeScript::ThisTypes(script())));
current->add(param);
current->initSlot(info().thisSlot(), param);
for (uint32_t i = 0; i < info().nargs(); i++) {
param = MParameter::New(i, cloneTypeSet(types::TypeScript::ArgTypes(script(), i)));
current->add(param);
current->initSlot(info().argSlotUnchecked(i), param);
}
return true;
}
bool
IonBuilder::initScopeChain(MDefinition *callee)
{
MInstruction *scope = NULL;
// If the script doesn't use the scopechain, then it's already initialized
// from earlier. However, always make a scope chain when |needsArgsObj| is true
// for the script, since arguments object construction requires the scope chain
// to be passed in.
if (!info().needsArgsObj() && !script()->analysis()->usesScopeChain())
return true;
// The scope chain is only tracked in scripts that have NAME opcodes which
// will try to access the scope. For other scripts, the scope instructions
// will be held live by resume points and code will still be generated for
// them, so just use a constant undefined value.
if (!script()->compileAndGo)
return abort("non-CNG global scripts are not supported");
if (JSFunction *fun = info().fun()) {
if (!callee) {
MCallee *calleeIns = MCallee::New();
current->add(calleeIns);
callee = calleeIns;
}
scope = MFunctionEnvironment::New(callee);
current->add(scope);
// This reproduce what is done in CallObject::createForFunction
if (fun->isHeavyweight()) {
if (fun->isNamedLambda()) {
scope = createDeclEnvObject(callee, scope);
if (!scope)
return false;
}
scope = createCallObject(callee, scope);
if (!scope)
return false;
}
} else {
scope = MConstant::New(ObjectValue(script()->global()));
current->add(scope);
}
current->setScopeChain(scope);
return true;
}
bool
IonBuilder::initArgumentsObject()
{
IonSpew(IonSpew_MIR, "%s:%d - Emitting code to initialize arguments object! block=%p",
script()->filename(), script()->lineno, current);
JS_ASSERT(info().needsArgsObj());
MCreateArgumentsObject *argsObj = MCreateArgumentsObject::New(current->scopeChain());
current->add(argsObj);
current->setArgumentsObject(argsObj);
return true;
}
bool
IonBuilder::addOsrValueTypeBarrier(uint32_t slot, MInstruction **def_,
MIRType type, types::StackTypeSet *typeSet)
{
MInstruction *&def = *def_;
MBasicBlock *osrBlock = def->block();
// Clear bogus type information added in newOsrPreheader().
def->setResultType(MIRType_Value);
def->setResultTypeSet(NULL);
if (typeSet && !typeSet->unknown()) {
MInstruction *barrier = MTypeBarrier::New(def, typeSet);
osrBlock->insertBefore(osrBlock->lastIns(), barrier);
osrBlock->rewriteSlot(slot, barrier);
def = barrier;
} else if (type == MIRType_Null ||
type == MIRType_Undefined ||
type == MIRType_Magic)
{
// No unbox instruction will be added below, so check the type by
// adding a type barrier for a singleton type set.
types::Type ntype = types::Type::PrimitiveType(ValueTypeFromMIRType(type));
typeSet = GetIonContext()->temp->lifoAlloc()->new_<types::StackTypeSet>(ntype);
if (!typeSet)
return false;
MInstruction *barrier = MTypeBarrier::New(def, typeSet);
osrBlock->insertBefore(osrBlock->lastIns(), barrier);
osrBlock->rewriteSlot(slot, barrier);
def = barrier;
}
switch (type) {
case MIRType_Boolean:
case MIRType_Int32:
case MIRType_Double:
case MIRType_String:
case MIRType_Object:
{
MUnbox *unbox = MUnbox::New(def, type, MUnbox::Fallible);
osrBlock->insertBefore(osrBlock->lastIns(), unbox);
osrBlock->rewriteSlot(slot, unbox);
def = unbox;
break;
}
case MIRType_Null:
{
MConstant *c = MConstant::New(NullValue());
osrBlock->insertBefore(osrBlock->lastIns(), c);
osrBlock->rewriteSlot(slot, c);
def = c;
break;
}
case MIRType_Undefined:
{
MConstant *c = MConstant::New(UndefinedValue());
osrBlock->insertBefore(osrBlock->lastIns(), c);
osrBlock->rewriteSlot(slot, c);
def = c;
break;
}
case MIRType_Magic:
JS_ASSERT(lazyArguments_);
osrBlock->rewriteSlot(slot, lazyArguments_);
def = lazyArguments_;
break;
default:
break;
}
JS_ASSERT(def == osrBlock->getSlot(slot));
return true;
}
bool
IonBuilder::maybeAddOsrTypeBarriers()
{
if (!info().osrPc())
return true;
// The loop has successfully been processed, and the loop header phis
// have their final type. Add unboxes and type barriers in the OSR
// block to check that the values have the appropriate type, and update
// the types in the preheader.
MBasicBlock *osrBlock = graph().osrBlock();
MBasicBlock *preheader = osrBlock->getSuccessor(0);
MBasicBlock *header = preheader->getSuccessor(0);
static const size_t OSR_PHI_POSITION = 1;
JS_ASSERT(preheader->getPredecessor(OSR_PHI_POSITION) == osrBlock);
MPhiIterator headerPhi = header->phisBegin();
while (headerPhi != header->phisEnd() && headerPhi->slot() < info().startArgSlot())
headerPhi++;
for (uint32_t i = info().startArgSlot(); i < osrBlock->stackDepth(); i++, headerPhi++) {
MInstruction *def = osrBlock->getSlot(i)->toOsrValue();
JS_ASSERT(headerPhi->slot() == i);
MPhi *preheaderPhi = preheader->getSlot(i)->toPhi();
MIRType type = headerPhi->type();
types::StackTypeSet *typeSet = headerPhi->resultTypeSet();
if (!addOsrValueTypeBarrier(i, &def, type, typeSet))
return false;
preheaderPhi->replaceOperand(OSR_PHI_POSITION, def);
preheaderPhi->setResultType(type);
preheaderPhi->setResultTypeSet(typeSet);
}
return true;
}
// We try to build a control-flow graph in the order that it would be built as
// if traversing the AST. This leads to a nice ordering and lets us build SSA
// in one pass, since the bytecode is structured.
//
// We traverse the bytecode iteratively, maintaining a current basic block.
// Each basic block has a mapping of local slots to instructions, as well as a
// stack depth. As we encounter instructions we mutate this mapping in the
// current block.
//
// Things get interesting when we encounter a control structure. This can be
// either an IFEQ, downward GOTO, or a decompiler hint stashed away in source
// notes. Once we encounter such an opcode, we recover the structure of the
// control flow (its branches and bounds), and push it on a stack.
//
// As we continue traversing the bytecode, we look for points that would
// terminate the topmost control flow path pushed on the stack. These are:
// (1) The bounds of the current structure (end of a loop or join/edge of a
// branch).
// (2) A "return", "break", or "continue" statement.
//
// For (1), we expect that there is a current block in the progress of being
// built, and we complete the necessary edges in the CFG. For (2), we expect
// that there is no active block.
//
// For normal diamond join points, we construct Phi nodes as we add
// predecessors. For loops, care must be taken to propagate Phi nodes back
// through uses in the loop body.
bool
IonBuilder::traverseBytecode()
{
for (;;) {
JS_ASSERT(pc < info().limitPC());
for (;;) {
if (!temp().ensureBallast())
return false;
// Check if we've hit an expected join point or edge in the bytecode.
// Leaving one control structure could place us at the edge of another,
// thus |while| instead of |if| so we don't skip any opcodes.
if (!cfgStack_.empty() && cfgStack_.back().stopAt == pc) {
ControlStatus status = processCfgStack();
if (status == ControlStatus_Error)
return false;
if (status == ControlStatus_Abort)
return abort("Aborted while processing control flow");
if (!current)
return maybeAddOsrTypeBarriers();
continue;
}
// Some opcodes need to be handled early because they affect control
// flow, terminating the current basic block and/or instructing the
// traversal algorithm to continue from a new pc.
//
// (1) If the opcode does not affect control flow, then the opcode
// is inspected and transformed to IR. This is the process_opcode
// label.
// (2) A loop could be detected via a forward GOTO. In this case,
// we don't want to process the GOTO, but the following
// instruction.
// (3) A RETURN, STOP, BREAK, or CONTINUE may require processing the
// CFG stack to terminate open branches.
//
// Similar to above, snooping control flow could land us at another
// control flow point, so we iterate until it's time to inspect a real
// opcode.
ControlStatus status;
if ((status = snoopControlFlow(JSOp(*pc))) == ControlStatus_None)
break;
if (status == ControlStatus_Error)
return false;
if (!current)
return maybeAddOsrTypeBarriers();
}
// Nothing in inspectOpcode() is allowed to advance the pc.
JSOp op = JSOp(*pc);
if (!inspectOpcode(op))
return false;
pc += js_CodeSpec[op].length;
#ifdef TRACK_SNAPSHOTS
current->updateTrackedPc(pc);
#endif
}
return maybeAddOsrTypeBarriers();
}
IonBuilder::ControlStatus
IonBuilder::snoopControlFlow(JSOp op)
{
switch (op) {
case JSOP_NOP:
return maybeLoop(op, info().getNote(cx, pc));
case JSOP_POP:
return maybeLoop(op, info().getNote(cx, pc));
case JSOP_RETURN:
case JSOP_STOP:
return processReturn(op);
case JSOP_THROW:
return processThrow();
case JSOP_GOTO:
{
jssrcnote *sn = info().getNote(cx, pc);
switch (sn ? SN_TYPE(sn) : SRC_NULL) {
case SRC_BREAK:
case SRC_BREAK2LABEL:
return processBreak(op, sn);
case SRC_CONTINUE:
return processContinue(op);
case SRC_SWITCHBREAK:
return processSwitchBreak(op);
case SRC_WHILE:
case SRC_FOR_IN:
// while (cond) { }
return whileOrForInLoop(sn);
default:
// Hard assert for now - make an error later.
JS_NOT_REACHED("unknown goto case");
break;
}
break;
}
case JSOP_TABLESWITCH:
return tableSwitch(op, info().getNote(cx, pc));
case JSOP_IFNE:
// We should never reach an IFNE, it's a stopAt point, which will
// trigger closing the loop.
JS_NOT_REACHED("we should never reach an ifne!");
return ControlStatus_Error;
default:
break;
}
return ControlStatus_None;
}
bool
IonBuilder::inspectOpcode(JSOp op)
{
switch (op) {
case JSOP_NOP:
case JSOP_LINENO:
case JSOP_LOOPENTRY:
return true;
case JSOP_LABEL:
return jsop_label();
case JSOP_UNDEFINED:
return pushConstant(UndefinedValue());
case JSOP_IFEQ:
return jsop_ifeq(JSOP_IFEQ);
case JSOP_CONDSWITCH:
return jsop_condswitch();
case JSOP_BITNOT:
return jsop_bitnot();
case JSOP_BITAND:
case JSOP_BITOR:
case JSOP_BITXOR:
case JSOP_LSH:
case JSOP_RSH:
case JSOP_URSH:
return jsop_bitop(op);
case JSOP_ADD:
case JSOP_SUB:
case JSOP_MUL:
case JSOP_DIV:
case JSOP_MOD:
return jsop_binary(op);
case JSOP_POS:
return jsop_pos();
case JSOP_NEG:
return jsop_neg();
case JSOP_AND:
case JSOP_OR:
return jsop_andor(op);
case JSOP_DEFVAR:
case JSOP_DEFCONST:
return jsop_defvar(GET_UINT32_INDEX(pc));
case JSOP_DEFFUN:
return jsop_deffun(GET_UINT32_INDEX(pc));
case JSOP_EQ:
case JSOP_NE:
case JSOP_STRICTEQ:
case JSOP_STRICTNE:
case JSOP_LT:
case JSOP_LE:
case JSOP_GT:
case JSOP_GE:
return jsop_compare(op);
case JSOP_DOUBLE:
return pushConstant(info().getConst(pc));
case JSOP_STRING:
return pushConstant(StringValue(info().getAtom(pc)));
case JSOP_ZERO:
return pushConstant(Int32Value(0));
case JSOP_ONE:
return pushConstant(Int32Value(1));
case JSOP_NULL:
return pushConstant(NullValue());
case JSOP_VOID:
current->pop();
return pushConstant(UndefinedValue());
case JSOP_HOLE:
return pushConstant(MagicValue(JS_ELEMENTS_HOLE));
case JSOP_FALSE:
return pushConstant(BooleanValue(false));
case JSOP_TRUE:
return pushConstant(BooleanValue(true));
case JSOP_ARGUMENTS:
return jsop_arguments();
case JSOP_RUNONCE:
return jsop_runonce();
case JSOP_REST:
return jsop_rest();
case JSOP_NOTEARG:
return jsop_notearg();
case JSOP_GETARG:
case JSOP_CALLARG:
if (info().argsObjAliasesFormals()) {
MGetArgumentsObjectArg *getArg = MGetArgumentsObjectArg::New(current->argumentsObject(),
GET_SLOTNO(pc));
current->add(getArg);
current->push(getArg);
} else {
current->pushArg(GET_SLOTNO(pc));
}
return true;
case JSOP_SETARG:
// To handle this case, we should spill the arguments to the space where
// actual arguments are stored. The tricky part is that if we add a MIR
// to wrap the spilling action, we don't want the spilling to be
// captured by the GETARG and by the resume point, only by
// MGetArgument.
if (info().argsObjAliasesFormals()) {
current->add(MSetArgumentsObjectArg::New(current->argumentsObject(), GET_SLOTNO(pc),
current->peek(-1)));
} else {
// TODO: if hasArguments() is true, and the script has a JSOP_SETARG, then
// convert all arg accesses to go through the arguments object.
if (info().hasArguments())
return abort("NYI: arguments & setarg.");
current->setArg(GET_SLOTNO(pc));
}
return true;
case JSOP_GETLOCAL:
case JSOP_CALLLOCAL:
current->pushLocal(GET_SLOTNO(pc));
return true;
case JSOP_SETLOCAL:
current->setLocal(GET_SLOTNO(pc));
return true;
case JSOP_POP:
current->pop();
// POP opcodes frequently appear where values are killed, e.g. after
// SET* opcodes. Place a resume point afterwards to avoid capturing
// the dead value in later snapshots, except in places where that
// resume point is obviously unnecessary.
if (pc[JSOP_POP_LENGTH] == JSOP_POP)
return true;
return maybeInsertResume();
case JSOP_POPN:
for (uint32_t i = 0, n = GET_UINT16(pc); i < n; i++)
current->pop();
return true;
case JSOP_NEWINIT:
{
if (GET_UINT8(pc) == JSProto_Array)
return jsop_newarray(0);
RootedObject baseObj(cx, NULL);
return jsop_newobject(baseObj);
}
case JSOP_NEWARRAY:
return jsop_newarray(GET_UINT24(pc));
case JSOP_NEWOBJECT:
{
RootedObject baseObj(cx, info().getObject(pc));
return jsop_newobject(baseObj);
}
case JSOP_INITELEM:
return jsop_initelem();
case JSOP_INITELEM_ARRAY:
return jsop_initelem_array();
case JSOP_INITPROP:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
return jsop_initprop(name);
}
case JSOP_ENDINIT:
return true;
case JSOP_FUNCALL:
return jsop_funcall(GET_ARGC(pc));
case JSOP_FUNAPPLY:
return jsop_funapply(GET_ARGC(pc));
case JSOP_CALL:
case JSOP_NEW:
return jsop_call(GET_ARGC(pc), (JSOp)*pc == JSOP_NEW);
case JSOP_EVAL:
return jsop_eval(GET_ARGC(pc));
case JSOP_INT8:
return pushConstant(Int32Value(GET_INT8(pc)));
case JSOP_UINT16:
return pushConstant(Int32Value(GET_UINT16(pc)));
case JSOP_GETGNAME:
case JSOP_CALLGNAME:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
RootedObject obj(cx, &script()->global());
bool succeeded;
if (!getStaticName(obj, name, &succeeded))
return false;
return succeeded || jsop_getname(name);
}
case JSOP_BINDGNAME:
return pushConstant(ObjectValue(script()->global()));
case JSOP_SETGNAME:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
RootedObject obj(cx, &script()->global());
return setStaticName(obj, name);
}
case JSOP_NAME:
case JSOP_CALLNAME:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
return jsop_getname(name);
}
case JSOP_GETINTRINSIC:
case JSOP_CALLINTRINSIC:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
return jsop_intrinsic(name);
}
case JSOP_BINDNAME:
return jsop_bindname(info().getName(pc));
case JSOP_DUP:
current->pushSlot(current->stackDepth() - 1);
return true;
case JSOP_DUP2:
return jsop_dup2();
case JSOP_SWAP:
current->swapAt(-1);
return true;
case JSOP_PICK:
current->pick(-GET_INT8(pc));
return true;
case JSOP_GETALIASEDVAR:
case JSOP_CALLALIASEDVAR:
return jsop_getaliasedvar(ScopeCoordinate(pc));
case JSOP_SETALIASEDVAR:
return jsop_setaliasedvar(ScopeCoordinate(pc));
case JSOP_UINT24:
return pushConstant(Int32Value(GET_UINT24(pc)));
case JSOP_INT32:
return pushConstant(Int32Value(GET_INT32(pc)));
case JSOP_LOOPHEAD:
// JSOP_LOOPHEAD is handled when processing the loop header.
JS_NOT_REACHED("JSOP_LOOPHEAD outside loop");
return true;
case JSOP_GETELEM:
case JSOP_CALLELEM:
return jsop_getelem();
case JSOP_SETELEM:
return jsop_setelem();
case JSOP_LENGTH:
return jsop_length();
case JSOP_NOT:
return jsop_not();
case JSOP_THIS:
return jsop_this();
case JSOP_CALLEE:
{
MDefinition *callee;
if (inliningDepth_ == 0) {
MInstruction *calleeIns = MCallee::New();
current->add(calleeIns);
callee = calleeIns;
} else {
callee = inlineCallInfo_->fun();
}
current->push(callee);
return true;
}
case JSOP_GETPROP:
case JSOP_CALLPROP:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
return jsop_getprop(name);
}
case JSOP_SETPROP:
case JSOP_SETNAME:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
return jsop_setprop(name);
}
case JSOP_DELPROP:
{
RootedPropertyName name(cx, info().getAtom(pc)->asPropertyName());
return jsop_delprop(name);
}
case JSOP_REGEXP:
return jsop_regexp(info().getRegExp(pc));
case JSOP_OBJECT:
return jsop_object(info().getObject(pc));
case JSOP_TYPEOF:
case JSOP_TYPEOFEXPR:
return jsop_typeof();
case JSOP_TOID:
return jsop_toid();
case JSOP_LAMBDA:
return jsop_lambda(info().getFunction(pc));
case JSOP_ITER:
return jsop_iter(GET_INT8(pc));
case JSOP_ITERNEXT:
return jsop_iternext();
case JSOP_MOREITER:
return jsop_itermore();
case JSOP_ENDITER:
return jsop_iterend();
case JSOP_IN:
return jsop_in();
case JSOP_INSTANCEOF:
return jsop_instanceof();
default:
#ifdef DEBUG
return abort("Unsupported opcode: %s (line %d)", js_CodeName[op], info().lineno(cx, pc));
#else
return abort("Unsupported opcode: %d (line %d)", op, info().lineno(cx, pc));
#endif
}
}
// Given that the current control flow structure has ended forcefully,
// via a return, break, or continue (rather than joining), propagate the
// termination up. For example, a return nested 5 loops deep may terminate
// every outer loop at once, if there are no intervening conditionals:
//
// for (...) {
// for (...) {
// return x;
// }
// }
//
// If |current| is NULL when this function returns, then there is no more
// control flow to be processed.
IonBuilder::ControlStatus
IonBuilder::processControlEnd()
{
JS_ASSERT(!current);
if (cfgStack_.empty()) {
// If there is no more control flow to process, then this is the
// last return in the function.
return ControlStatus_Ended;
}
return processCfgStack();
}
// Processes the top of the CFG stack. This is used from two places:
// (1) processControlEnd(), whereby a break, continue, or return may interrupt
// an in-progress CFG structure before reaching its actual termination
// point in the bytecode.
// (2) traverseBytecode(), whereby we reach the last instruction in a CFG
// structure.
IonBuilder::ControlStatus
IonBuilder::processCfgStack()
{
ControlStatus status = processCfgEntry(cfgStack_.back());
// If this terminated a CFG structure, act like processControlEnd() and
// keep propagating upward.
while (status == ControlStatus_Ended) {
popCfgStack();
if (cfgStack_.empty())
return status;
status = processCfgEntry(cfgStack_.back());
}
// If some join took place, the current structure is finished.
if (status == ControlStatus_Joined)
popCfgStack();
return status;
}
IonBuilder::ControlStatus
IonBuilder::processCfgEntry(CFGState &state)
{
switch (state.state) {
case CFGState::IF_TRUE:
case CFGState::IF_TRUE_EMPTY_ELSE:
return processIfEnd(state);
case CFGState::IF_ELSE_TRUE:
return processIfElseTrueEnd(state);
case CFGState::IF_ELSE_FALSE:
return processIfElseFalseEnd(state);
case CFGState::DO_WHILE_LOOP_BODY:
return processDoWhileBodyEnd(state);
case CFGState::DO_WHILE_LOOP_COND:
return processDoWhileCondEnd(state);
case CFGState::WHILE_LOOP_COND:
return processWhileCondEnd(state);
case CFGState::WHILE_LOOP_BODY:
return processWhileBodyEnd(state);
case CFGState::FOR_LOOP_COND:
return processForCondEnd(state);
case CFGState::FOR_LOOP_BODY:
return processForBodyEnd(state);
case CFGState::FOR_LOOP_UPDATE:
return processForUpdateEnd(state);
case CFGState::TABLE_SWITCH:
return processNextTableSwitchCase(state);
case CFGState::COND_SWITCH_CASE:
return processCondSwitchCase(state);
case CFGState::COND_SWITCH_BODY:
return processCondSwitchBody(state);
case CFGState::AND_OR:
return processAndOrEnd(state);
case CFGState::LABEL:
return processLabelEnd(state);
default:
JS_NOT_REACHED("unknown cfgstate");
}
return ControlStatus_Error;
}
IonBuilder::ControlStatus
IonBuilder::processIfEnd(CFGState &state)
{
if (current) {
// Here, the false block is the join point. Create an edge from the
// current block to the false block. Note that a RETURN opcode
// could have already ended the block.
current->end(MGoto::New(state.branch.ifFalse));
if (!state.branch.ifFalse->addPredecessor(current))
return ControlStatus_Error;
}
setCurrentAndSpecializePhis(state.branch.ifFalse);
graph().moveBlockToEnd(current);
pc = current->pc();
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::processIfElseTrueEnd(CFGState &state)
{
// We've reached the end of the true branch of an if-else. Don't
// create an edge yet, just transition to parsing the false branch.
state.state = CFGState::IF_ELSE_FALSE;
state.branch.ifTrue = current;
state.stopAt = state.branch.falseEnd;
pc = state.branch.ifFalse->pc();
setCurrentAndSpecializePhis(state.branch.ifFalse);
graph().moveBlockToEnd(current);
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processIfElseFalseEnd(CFGState &state)
{
// Update the state to have the latest block from the false path.
state.branch.ifFalse = current;
// To create the join node, we need an incoming edge that has not been
// terminated yet.
MBasicBlock *pred = state.branch.ifTrue
? state.branch.ifTrue
: state.branch.ifFalse;
MBasicBlock *other = (pred == state.branch.ifTrue) ? state.branch.ifFalse : state.branch.ifTrue;
if (!pred)
return ControlStatus_Ended;
// Create a new block to represent the join.
MBasicBlock *join = newBlock(pred, state.branch.falseEnd);
if (!join)
return ControlStatus_Error;
// Create edges from the true and false blocks as needed.
pred->end(MGoto::New(join));
if (other) {
other->end(MGoto::New(join));
if (!join->addPredecessor(other))
return ControlStatus_Error;
}
// Ignore unreachable remainder of false block if existent.
setCurrentAndSpecializePhis(join);
pc = current->pc();
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::processBrokenLoop(CFGState &state)
{
JS_ASSERT(!current);
JS_ASSERT(loopDepth_);
loopDepth_--;
// A broken loop is not a real loop (it has no header or backedge), so
// reset the loop depth.
for (MBasicBlockIterator i(graph().begin(state.loop.entry)); i != graph().end(); i++) {
if (i->loopDepth() > loopDepth_)
i->setLoopDepth(i->loopDepth() - 1);
}
// If the loop started with a condition (while/for) then even if the
// structure never actually loops, the condition itself can still fail and
// thus we must resume at the successor, if one exists.
setCurrentAndSpecializePhis(state.loop.successor);
if (current) {
JS_ASSERT(current->loopDepth() == loopDepth_);
graph().moveBlockToEnd(current);
}
// Join the breaks together and continue parsing.
if (state.loop.breaks) {
MBasicBlock *block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc);
if (!block)
return ControlStatus_Error;
if (current) {
current->end(MGoto::New(block));
if (!block->addPredecessor(current))
return ControlStatus_Error;
}
setCurrentAndSpecializePhis(block);
}
// If the loop is not gated on a condition, and has only returns, we'll
// reach this case. For example:
// do { ... return; } while ();
if (!current)
return ControlStatus_Ended;
// Otherwise, the loop is gated on a condition and/or has breaks so keep
// parsing at the successor.
pc = current->pc();
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::finishLoop(CFGState &state, MBasicBlock *successor)
{
JS_ASSERT(current);
JS_ASSERT(loopDepth_);
loopDepth_--;
JS_ASSERT_IF(successor, successor->loopDepth() == loopDepth_);
// Compute phis in the loop header and propagate them throughout the loop,
// including the successor.
AbortReason r = state.loop.entry->setBackedge(current);
if (r == AbortReason_Alloc)
return ControlStatus_Error;
if (r == AbortReason_Disable) {
// If there are types for variables on the backedge that were not
// present at the original loop header, then uses of the variables'
// phis may have generated incorrect nodes. The new types have been
// incorporated into the header phis, so remove all blocks for the
// loop body and restart with the new types.
return restartLoop(state);
}
if (successor) {
graph().moveBlockToEnd(successor);
successor->inheritPhis(state.loop.entry);
}
if (state.loop.breaks) {
// Propagate phis placed in the header to individual break exit points.
DeferredEdge *edge = state.loop.breaks;
while (edge) {
edge->block->inheritPhis(state.loop.entry);
edge = edge->next;
}
// Create a catch block to join all break exits.
MBasicBlock *block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc);
if (!block)
return ControlStatus_Error;
if (successor) {
// Finally, create an unconditional edge from the successor to the
// catch block.
successor->end(MGoto::New(block));
if (!block->addPredecessor(successor))
return ControlStatus_Error;
}
successor = block;
}
setCurrentAndSpecializePhis(successor);
// An infinite loop (for (;;) { }) will not have a successor.
if (!current)
return ControlStatus_Ended;
pc = current->pc();
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::restartLoop(CFGState state)
{
spew("New types at loop header, restarting loop body");
if (js_IonOptions.limitScriptSize) {
if (++numLoopRestarts_ >= MAX_LOOP_RESTARTS)
return ControlStatus_Abort;
}
MBasicBlock *header = state.loop.entry;
// Remove all blocks in the loop body other than the header, which has phis
// of the appropriate type and incoming edges to preserve.
graph().removeBlocksAfter(header);
// Remove all instructions from the header itself, and all resume points
// except the entry resume point.
header->discardAllInstructions();
header->discardAllResumePoints(/* discardEntry = */ false);
header->setStackDepth(header->getPredecessor(0)->stackDepth());
popCfgStack();
loopDepth_++;
if (!pushLoop(state.loop.initialState, state.loop.initialStopAt, header, state.loop.osr,
state.loop.loopHead, state.loop.initialPc,
state.loop.bodyStart, state.loop.bodyEnd,
state.loop.exitpc, state.loop.continuepc))
{
return ControlStatus_Error;
}
CFGState &nstate = cfgStack_.back();
nstate.loop.condpc = state.loop.condpc;
nstate.loop.updatepc = state.loop.updatepc;
nstate.loop.updateEnd = state.loop.updateEnd;
// Don't specializePhis(), as the header has been visited before and the
// phis have already had their type set.
setCurrent(header);
if (!jsop_loophead(nstate.loop.loopHead))
return ControlStatus_Error;
pc = nstate.loop.initialPc;
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processDoWhileBodyEnd(CFGState &state)
{
if (!processDeferredContinues(state))
return ControlStatus_Error;
// No current means control flow cannot reach the condition, so this will
// never loop.
if (!current)
return processBrokenLoop(state);
MBasicBlock *header = newBlock(current, state.loop.updatepc);
if (!header)
return ControlStatus_Error;
current->end(MGoto::New(header));
state.state = CFGState::DO_WHILE_LOOP_COND;
state.stopAt = state.loop.updateEnd;
pc = state.loop.updatepc;
setCurrentAndSpecializePhis(header);
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processDoWhileCondEnd(CFGState &state)
{
JS_ASSERT(JSOp(*pc) == JSOP_IFNE);
// We're guaranteed a |current|, it's impossible to break or return from
// inside the conditional expression.
JS_ASSERT(current);
// Pop the last value, and create the successor block.
MDefinition *vins = current->pop();
MBasicBlock *successor = newBlock(current, GetNextPc(pc), loopDepth_ - 1);
if (!successor)
return ControlStatus_Error;
// Create the test instruction and end the current block.
MTest *test = MTest::New(vins, state.loop.entry, successor);
current->end(test);
return finishLoop(state, successor);
}
IonBuilder::ControlStatus
IonBuilder::processWhileCondEnd(CFGState &state)
{
JS_ASSERT(JSOp(*pc) == JSOP_IFNE);
// Balance the stack past the IFNE.
MDefinition *ins = current->pop();
// Create the body and successor blocks.
MBasicBlock *body = newBlock(current, state.loop.bodyStart);
state.loop.successor = newBlock(current, state.loop.exitpc, loopDepth_ - 1);
if (!body || !state.loop.successor)
return ControlStatus_Error;
MTest *test = MTest::New(ins, body, state.loop.successor);
current->end(test);
state.state = CFGState::WHILE_LOOP_BODY;
state.stopAt = state.loop.bodyEnd;
pc = state.loop.bodyStart;
setCurrentAndSpecializePhis(body);
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processWhileBodyEnd(CFGState &state)
{
if (!processDeferredContinues(state))
return ControlStatus_Error;
if (!current)
return processBrokenLoop(state);
current->end(MGoto::New(state.loop.entry));
return finishLoop(state, state.loop.successor);
}
IonBuilder::ControlStatus
IonBuilder::processForCondEnd(CFGState &state)
{
JS_ASSERT(JSOp(*pc) == JSOP_IFNE);
// Balance the stack past the IFNE.
MDefinition *ins = current->pop();
// Create the body and successor blocks.
MBasicBlock *body = newBlock(current, state.loop.bodyStart);
state.loop.successor = newBlock(current, state.loop.exitpc, loopDepth_ - 1);
if (!body || !state.loop.successor)
return ControlStatus_Error;
MTest *test = MTest::New(ins, body, state.loop.successor);
current->end(test);
state.state = CFGState::FOR_LOOP_BODY;
state.stopAt = state.loop.bodyEnd;
pc = state.loop.bodyStart;
setCurrentAndSpecializePhis(body);
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processForBodyEnd(CFGState &state)
{
if (!processDeferredContinues(state))
return ControlStatus_Error;
// If there is no updatepc, just go right to processing what would be the
// end of the update clause. Otherwise, |current| might be NULL; if this is
// the case, the udpate is unreachable anyway.
if (!state.loop.updatepc || !current)
return processForUpdateEnd(state);
pc = state.loop.updatepc;
state.state = CFGState::FOR_LOOP_UPDATE;
state.stopAt = state.loop.updateEnd;
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processForUpdateEnd(CFGState &state)
{
// If there is no current, we couldn't reach the loop edge and there was no
// update clause.
if (!current)
return processBrokenLoop(state);
current->end(MGoto::New(state.loop.entry));
return finishLoop(state, state.loop.successor);
}
IonBuilder::DeferredEdge *
IonBuilder::filterDeadDeferredEdges(DeferredEdge *edge)
{
DeferredEdge *head = edge, *prev = NULL;
while (edge) {
if (edge->block->isDead()) {
if (prev)
prev->next = edge->next;
else
head = edge->next;
} else {
prev = edge;
}
edge = edge->next;
}
// There must be at least one deferred edge from a block that was not
// deleted; blocks are deleted when restarting processing of a loop, and
// the final version of the loop body will have edges from live blocks.
JS_ASSERT(head);
return head;
}
bool
IonBuilder::processDeferredContinues(CFGState &state)
{
// If there are any continues for this loop, and there is an update block,
// then we need to create a new basic block to house the update.
if (state.loop.continues) {
DeferredEdge *edge = filterDeadDeferredEdges(state.loop.continues);
MBasicBlock *update = newBlock(edge->block, loops_.back().continuepc);
if (!update)
return false;
if (current) {
current->end(MGoto::New(update));
if (!update->addPredecessor(current))
return ControlStatus_Error;
}
// No need to use addPredecessor for first edge,
// because it is already predecessor.
edge->block->end(MGoto::New(update));
edge = edge->next;
// Remaining edges
while (edge) {
edge->block->end(MGoto::New(update));
if (!update->addPredecessor(edge->block))
return ControlStatus_Error;
edge = edge->next;
}
state.loop.continues = NULL;
setCurrentAndSpecializePhis(update);
}
return true;
}
MBasicBlock *
IonBuilder::createBreakCatchBlock(DeferredEdge *edge, jsbytecode *pc)
{
edge = filterDeadDeferredEdges(edge);
// Create block, using the first break statement as predecessor
MBasicBlock *successor = newBlock(edge->block, pc);
if (!successor)
return NULL;
// No need to use addPredecessor for first edge,
// because it is already predecessor.
edge->block->end(MGoto::New(successor));
edge = edge->next;
// Finish up remaining breaks.
while (edge) {
edge->block->end(MGoto::New(successor));
if (!successor->addPredecessor(edge->block))
return NULL;
edge = edge->next;
}
return successor;
}
IonBuilder::ControlStatus
IonBuilder::processNextTableSwitchCase(CFGState &state)
{
JS_ASSERT(state.state == CFGState::TABLE_SWITCH);
state.tableswitch.currentBlock++;
// Test if there are still unprocessed successors (cases/default)
if (state.tableswitch.currentBlock >= state.tableswitch.ins->numBlocks())
return processSwitchEnd(state.tableswitch.breaks, state.tableswitch.exitpc);
// Get the next successor
MBasicBlock *successor = state.tableswitch.ins->getBlock(state.tableswitch.currentBlock);
// Add current block as predecessor if available.
// This means the previous case didn't have a break statement.
// So flow will continue in this block.
if (current) {
current->end(MGoto::New(successor));
successor->addPredecessor(current);
}
// Insert successor after the current block, to maintain RPO.
graph().moveBlockToEnd(successor);
// If this is the last successor the block should stop at the end of the tableswitch
// Else it should stop at the start of the next successor
if (state.tableswitch.currentBlock+1 < state.tableswitch.ins->numBlocks())
state.stopAt = state.tableswitch.ins->getBlock(state.tableswitch.currentBlock+1)->pc();
else
state.stopAt = state.tableswitch.exitpc;
setCurrentAndSpecializePhis(successor);
pc = current->pc();
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processAndOrEnd(CFGState &state)
{
// We just processed the RHS of an && or || expression.
// Now jump to the join point (the false block).
current->end(MGoto::New(state.branch.ifFalse));
if (!state.branch.ifFalse->addPredecessor(current))
return ControlStatus_Error;
setCurrentAndSpecializePhis(state.branch.ifFalse);
graph().moveBlockToEnd(current);
pc = current->pc();
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::processLabelEnd(CFGState &state)
{
JS_ASSERT(state.state == CFGState::LABEL);
// If there are no breaks and no current, controlflow is terminated.
if (!state.label.breaks && !current)
return ControlStatus_Ended;
// If there are no breaks to this label, there's nothing to do.
if (!state.label.breaks)
return ControlStatus_Joined;
MBasicBlock *successor = createBreakCatchBlock(state.label.breaks, state.stopAt);
if (!successor)
return ControlStatus_Error;
if (current) {
current->end(MGoto::New(successor));
successor->addPredecessor(current);
}
pc = state.stopAt;
setCurrentAndSpecializePhis(successor);
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::processBreak(JSOp op, jssrcnote *sn)
{
JS_ASSERT(op == JSOP_GOTO);
JS_ASSERT(SN_TYPE(sn) == SRC_BREAK ||
SN_TYPE(sn) == SRC_BREAK2LABEL);
// Find the break target.
jsbytecode *target = pc + GetJumpOffset(pc);
DebugOnly<bool> found = false;
if (SN_TYPE(sn) == SRC_BREAK2LABEL) {
for (size_t i = labels_.length() - 1; i < labels_.length(); i--) {
CFGState &cfg = cfgStack_[labels_[i].cfgEntry];
JS_ASSERT(cfg.state == CFGState::LABEL);
if (cfg.stopAt == target) {
cfg.label.breaks = new DeferredEdge(current, cfg.label.breaks);
found = true;
break;
}
}
} else {
for (size_t i = loops_.length() - 1; i < loops_.length(); i--) {
CFGState &cfg = cfgStack_[loops_[i].cfgEntry];
JS_ASSERT(cfg.isLoop());
if (cfg.loop.exitpc == target) {
cfg.loop.breaks = new DeferredEdge(current, cfg.loop.breaks);
found = true;
break;
}
}
}
JS_ASSERT(found);
setCurrent(NULL);
pc += js_CodeSpec[op].length;
return processControlEnd();
}
static inline jsbytecode *
EffectiveContinue(jsbytecode *pc)
{
if (JSOp(*pc) == JSOP_GOTO)
return pc + GetJumpOffset(pc);
return pc;
}
IonBuilder::ControlStatus
IonBuilder::processContinue(JSOp op)
{
JS_ASSERT(op == JSOP_GOTO);
// Find the target loop.
CFGState *found = NULL;
jsbytecode *target = pc + GetJumpOffset(pc);
for (size_t i = loops_.length() - 1; i < loops_.length(); i--) {
if (loops_[i].continuepc == target ||
EffectiveContinue(loops_[i].continuepc) == target)
{
found = &cfgStack_[loops_[i].cfgEntry];
break;
}
}
// There must always be a valid target loop structure. If not, there's
// probably an off-by-something error in which pc we track.
JS_ASSERT(found);
CFGState &state = *found;
state.loop.continues = new DeferredEdge(current, state.loop.continues);
setCurrent(NULL);
pc += js_CodeSpec[op].length;
return processControlEnd();
}
IonBuilder::ControlStatus
IonBuilder::processSwitchBreak(JSOp op)
{
JS_ASSERT(op == JSOP_GOTO);
// Find the target switch.
CFGState *found = NULL;
jsbytecode *target = pc + GetJumpOffset(pc);
for (size_t i = switches_.length() - 1; i < switches_.length(); i--) {
if (switches_[i].continuepc == target) {
found = &cfgStack_[switches_[i].cfgEntry];
break;
}
}
// There must always be a valid target loop structure. If not, there's
// probably an off-by-something error in which pc we track.
JS_ASSERT(found);
CFGState &state = *found;
DeferredEdge **breaks = NULL;
switch (state.state) {
case CFGState::TABLE_SWITCH:
breaks = &state.tableswitch.breaks;
break;
case CFGState::COND_SWITCH_BODY:
breaks = &state.condswitch.breaks;
break;
default:
JS_NOT_REACHED("Unexpected switch state.");
return ControlStatus_Error;
}
*breaks = new DeferredEdge(current, *breaks);
setCurrent(NULL);
pc += js_CodeSpec[op].length;
return processControlEnd();
}
IonBuilder::ControlStatus
IonBuilder::processSwitchEnd(DeferredEdge *breaks, jsbytecode *exitpc)
{
// No break statements, no current.
// This means that control flow is cut-off from this point
// (e.g. all cases have return statements).
if (!breaks && !current)
return ControlStatus_Ended;
// Create successor block.
// If there are breaks, create block with breaks as predecessor
// Else create a block with current as predecessor
MBasicBlock *successor = NULL;
if (breaks)
successor = createBreakCatchBlock(breaks, exitpc);
else
successor = newBlock(current, exitpc);
if (!successor)
return ControlStatus_Ended;
// If there is current, the current block flows into this one.
// So current is also a predecessor to this block
if (current) {
current->end(MGoto::New(successor));
if (breaks)
successor->addPredecessor(current);
}
pc = exitpc;
setCurrentAndSpecializePhis(successor);
return ControlStatus_Joined;
}
IonBuilder::ControlStatus
IonBuilder::maybeLoop(JSOp op, jssrcnote *sn)
{
// This function looks at the opcode and source note and tries to
// determine the structure of the loop. For some opcodes, like
// POP/NOP which are not explicitly control flow, this source note is
// optional. For opcodes with control flow, like GOTO, an unrecognized
// or not-present source note is a compilation failure.
switch (op) {
case JSOP_POP:
// for (init; ; update?) ...
if (sn && SN_TYPE(sn) == SRC_FOR) {
current->pop();
return forLoop(op, sn);
}
break;
case JSOP_NOP:
if (sn) {
// do { } while (cond)
if (SN_TYPE(sn) == SRC_WHILE)
return doWhileLoop(op, sn);
// Build a mapping such that given a basic block, whose successor
// has a phi
// for (; ; update?)
if (SN_TYPE(sn) == SRC_FOR)
return forLoop(op, sn);
}
break;
default:
JS_NOT_REACHED("unexpected opcode");
return ControlStatus_Error;
}
return ControlStatus_None;
}
void
IonBuilder::assertValidLoopHeadOp(jsbytecode *pc)
{
#ifdef DEBUG
JS_ASSERT(JSOp(*pc) == JSOP_LOOPHEAD);
// Make sure this is the next opcode after the loop header,
// unless the for loop is unconditional.
CFGState &state = cfgStack_.back();
JS_ASSERT_IF((JSOp)*(state.loop.entry->pc()) == JSOP_GOTO,
GetNextPc(state.loop.entry->pc()) == pc);
// do-while loops have a source note.
jssrcnote *sn = info().getNote(cx, pc);
if (sn) {
jsbytecode *ifne = pc + js_GetSrcNoteOffset(sn, 0);
jsbytecode *expected_ifne;
switch (state.state) {
case CFGState::DO_WHILE_LOOP_BODY:
expected_ifne = state.loop.updateEnd;
break;
default:
JS_NOT_REACHED("JSOP_LOOPHEAD unexpected source note");
return;
}
// Make sure this loop goes to the same ifne as the loop header's
// source notes or GOTO.
JS_ASSERT(ifne == expected_ifne);
} else {
JS_ASSERT(state.state != CFGState::DO_WHILE_LOOP_BODY);
}
#endif
}
IonBuilder::ControlStatus
IonBuilder::doWhileLoop(JSOp op, jssrcnote *sn)
{
// do { } while() loops have the following structure:
// NOP ; SRC_WHILE (offset to COND)
// LOOPHEAD ; SRC_WHILE (offset to IFNE)
// LOOPENTRY
// ... ; body
// ...
// COND ; start of condition
// ...
// IFNE -> ; goes to LOOPHEAD
int condition_offset = js_GetSrcNoteOffset(sn, 0);
jsbytecode *conditionpc = pc + condition_offset;
jssrcnote *sn2 = info().getNote(cx, pc+1);
int offset = js_GetSrcNoteOffset(sn2, 0);
jsbytecode *ifne = pc + offset + 1;
JS_ASSERT(ifne > pc);
// Verify that the IFNE goes back to a loophead op.
jsbytecode *loopHead = GetNextPc(pc);
JS_ASSERT(JSOp(*loopHead) == JSOP_LOOPHEAD);
JS_ASSERT(loopHead == ifne + GetJumpOffset(ifne));
jsbytecode *loopEntry = GetNextPc(loopHead);
bool osr = info().hasOsrAt(loopEntry);
if (osr) {
MBasicBlock *preheader = newOsrPreheader(current, loopEntry);
if (!preheader)
return ControlStatus_Error;
current->end(MGoto::New(preheader));
setCurrentAndSpecializePhis(preheader);
}
MBasicBlock *header = newPendingLoopHeader(current, pc, osr);
if (!header)
return ControlStatus_Error;
current->end(MGoto::New(header));
jsbytecode *loophead = GetNextPc(pc);
jsbytecode *bodyStart = GetNextPc(loophead);
jsbytecode *bodyEnd = conditionpc;
jsbytecode *exitpc = GetNextPc(ifne);
analyzeNewLoopTypes(header, bodyStart, exitpc);
if (!pushLoop(CFGState::DO_WHILE_LOOP_BODY, conditionpc, header, osr,
loopHead, bodyStart, bodyStart, bodyEnd, exitpc, conditionpc))
{
return ControlStatus_Error;
}
CFGState &state = cfgStack_.back();
state.loop.updatepc = conditionpc;
state.loop.updateEnd = ifne;
setCurrentAndSpecializePhis(header);
if (!jsop_loophead(loophead))
return ControlStatus_Error;
pc = bodyStart;
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::whileOrForInLoop(jssrcnote *sn)
{
// while (cond) { } loops have the following structure:
// GOTO cond ; SRC_WHILE (offset to IFNE)
// LOOPHEAD
// ...
// cond:
// LOOPENTRY
// ...
// IFNE ; goes to LOOPHEAD
// for (x in y) { } loops are similar; the cond will be a MOREITER.
JS_ASSERT(SN_TYPE(sn) == SRC_FOR_IN || SN_TYPE(sn) == SRC_WHILE);
int ifneOffset = js_GetSrcNoteOffset(sn, 0);
jsbytecode *ifne = pc + ifneOffset;
JS_ASSERT(ifne > pc);
// Verify that the IFNE goes back to a loophead op.
JS_ASSERT(JSOp(*GetNextPc(pc)) == JSOP_LOOPHEAD);
JS_ASSERT(GetNextPc(pc) == ifne + GetJumpOffset(ifne));
jsbytecode *loopEntry = pc + GetJumpOffset(pc);
bool osr = info().hasOsrAt(loopEntry);
if (osr) {
MBasicBlock *preheader = newOsrPreheader(current, loopEntry);
if (!preheader)
return ControlStatus_Error;
current->end(MGoto::New(preheader));
setCurrentAndSpecializePhis(preheader);
}
MBasicBlock *header = newPendingLoopHeader(current, pc, osr);
if (!header)
return ControlStatus_Error;
current->end(MGoto::New(header));
// Skip past the JSOP_LOOPHEAD for the body start.
jsbytecode *loopHead = GetNextPc(pc);
jsbytecode *bodyStart = GetNextPc(loopHead);
jsbytecode *bodyEnd = pc + GetJumpOffset(pc);
jsbytecode *exitpc = GetNextPc(ifne);
analyzeNewLoopTypes(header, bodyStart, exitpc);
if (!pushLoop(CFGState::WHILE_LOOP_COND, ifne, header, osr,
loopHead, bodyEnd, bodyStart, bodyEnd, exitpc))
{
return ControlStatus_Error;
}
// Parse the condition first.
setCurrentAndSpecializePhis(header);
if (!jsop_loophead(loopHead))
return ControlStatus_Error;
pc = bodyEnd;
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::forLoop(JSOp op, jssrcnote *sn)
{
// Skip the NOP or POP.
JS_ASSERT(op == JSOP_POP || op == JSOP_NOP);
pc = GetNextPc(pc);
jsbytecode *condpc = pc + js_GetSrcNoteOffset(sn, 0);
jsbytecode *updatepc = pc + js_GetSrcNoteOffset(sn, 1);
jsbytecode *ifne = pc + js_GetSrcNoteOffset(sn, 2);
jsbytecode *exitpc = GetNextPc(ifne);
// for loops have the following structures:
//
// NOP or POP
// [GOTO cond | NOP]
// LOOPHEAD
// body:
// ; [body]
// [increment:]
// ; [increment]
// [cond:]
// LOOPENTRY
// GOTO body
//
// If there is a condition (condpc != ifne), this acts similar to a while
// loop otherwise, it acts like a do-while loop.
jsbytecode *bodyStart = pc;
jsbytecode *bodyEnd = updatepc;
jsbytecode *loopEntry = condpc;
if (condpc != ifne) {
JS_ASSERT(JSOp(*bodyStart) == JSOP_GOTO);
JS_ASSERT(bodyStart + GetJumpOffset(bodyStart) == condpc);
bodyStart = GetNextPc(bodyStart);
} else {
// No loop condition, such as for(j = 0; ; j++)
if (op != JSOP_NOP) {
// If the loop starts with POP, we have to skip a NOP.
JS_ASSERT(JSOp(*bodyStart) == JSOP_NOP);
bodyStart = GetNextPc(bodyStart);
}
loopEntry = GetNextPc(bodyStart);
}
jsbytecode *loopHead = bodyStart;
JS_ASSERT(JSOp(*bodyStart) == JSOP_LOOPHEAD);
JS_ASSERT(ifne + GetJumpOffset(ifne) == bodyStart);
bodyStart = GetNextPc(bodyStart);
bool osr = info().hasOsrAt(loopEntry);
if (osr) {
MBasicBlock *preheader = newOsrPreheader(current, loopEntry);
if (!preheader)
return ControlStatus_Error;
current->end(MGoto::New(preheader));
setCurrentAndSpecializePhis(preheader);
}
MBasicBlock *header = newPendingLoopHeader(current, pc, osr);
if (!header)
return ControlStatus_Error;
current->end(MGoto::New(header));
// If there is no condition, we immediately parse the body. Otherwise, we
// parse the condition.
jsbytecode *stopAt;
CFGState::State initial;
if (condpc != ifne) {
pc = condpc;
stopAt = ifne;
initial = CFGState::FOR_LOOP_COND;
} else {
pc = bodyStart;
stopAt = bodyEnd;
initial = CFGState::FOR_LOOP_BODY;
}
analyzeNewLoopTypes(header, bodyStart, exitpc);
if (!pushLoop(initial, stopAt, header, osr,
loopHead, pc, bodyStart, bodyEnd, exitpc, updatepc))
{
return ControlStatus_Error;
}
CFGState &state = cfgStack_.back();
state.loop.condpc = (condpc != ifne) ? condpc : NULL;
state.loop.updatepc = (updatepc != condpc) ? updatepc : NULL;
if (state.loop.updatepc)
state.loop.updateEnd = condpc;
setCurrentAndSpecializePhis(header);
if (!jsop_loophead(loopHead))
return ControlStatus_Error;
return ControlStatus_Jumped;
}
int
IonBuilder::CmpSuccessors(const void *a, const void *b)
{
const MBasicBlock *a0 = * (MBasicBlock * const *)a;
const MBasicBlock *b0 = * (MBasicBlock * const *)b;
if (a0->pc() == b0->pc())
return 0;
return (a0->pc() > b0->pc()) ? 1 : -1;
}
IonBuilder::ControlStatus
IonBuilder::tableSwitch(JSOp op, jssrcnote *sn)
{
// TableSwitch op contains the following data
// (length between data is JUMP_OFFSET_LEN)
//
// 0: Offset of default case
// 1: Lowest number in tableswitch
// 2: Highest number in tableswitch
// 3: Offset of case low
// 4: Offset of case low+1
// .: ...
// .: Offset of case high
JS_ASSERT(op == JSOP_TABLESWITCH);
JS_ASSERT(SN_TYPE(sn) == SRC_TABLESWITCH);
// Pop input.
MDefinition *ins = current->pop();
// Get the default and exit pc
jsbytecode *exitpc = pc + js_GetSrcNoteOffset(sn, 0);
jsbytecode *defaultpc = pc + GET_JUMP_OFFSET(pc);
JS_ASSERT(defaultpc > pc && defaultpc <= exitpc);
// Get the low and high from the tableswitch
jsbytecode *pc2 = pc;
pc2 += JUMP_OFFSET_LEN;
int low = GET_JUMP_OFFSET(pc2);
pc2 += JUMP_OFFSET_LEN;
int high = GET_JUMP_OFFSET(pc2);
pc2 += JUMP_OFFSET_LEN;
// Create MIR instruction
MTableSwitch *tableswitch = MTableSwitch::New(ins, low, high);
// Create default case
MBasicBlock *defaultcase = newBlock(current, defaultpc);
if (!defaultcase)
return ControlStatus_Error;
tableswitch->addDefault(defaultcase);
tableswitch->addBlock(defaultcase);
// Create cases
jsbytecode *casepc = NULL;
for (int i = 0; i < high-low+1; i++) {
casepc = pc + GET_JUMP_OFFSET(pc2);
JS_ASSERT(casepc >= pc && casepc <= exitpc);
MBasicBlock *caseblock = newBlock(current, casepc);
if (!caseblock)
return ControlStatus_Error;
// If the casepc equals the current pc, it is not a written case,
// but a filled gap. That way we can use a tableswitch instead of
// condswitch, even if not all numbers are consecutive.
// In that case this block goes to the default case
if (casepc == pc) {
caseblock->end(MGoto::New(defaultcase));
defaultcase->addPredecessor(caseblock);
}
tableswitch->addCase(caseblock);
// If this is an actual case (not filled gap),
// add this block to the list that still needs to get processed
if (casepc != pc)
tableswitch->addBlock(caseblock);
pc2 += JUMP_OFFSET_LEN;
}
// Move defaultcase to the end, to maintain RPO.
graph().moveBlockToEnd(defaultcase);
JS_ASSERT(tableswitch->numCases() == (uint32_t)(high - low + 1));
JS_ASSERT(tableswitch->numSuccessors() > 0);
// Sort the list of blocks that still needs to get processed by pc
qsort(tableswitch->blocks(), tableswitch->numBlocks(),
sizeof(MBasicBlock*), CmpSuccessors);
// Create info
ControlFlowInfo switchinfo(cfgStack_.length(), exitpc);
if (!switches_.append(switchinfo))
return ControlStatus_Error;
// Use a state to retrieve some information
CFGState state = CFGState::TableSwitch(exitpc, tableswitch);
// Save the MIR instruction as last instruction of this block.
current->end(tableswitch);
// If there is only one successor the block should stop at the end of the switch
// Else it should stop at the start of the next successor
if (tableswitch->numBlocks() > 1)
state.stopAt = tableswitch->getBlock(1)->pc();
setCurrentAndSpecializePhis(tableswitch->getBlock(0));
if (!cfgStack_.append(state))
return ControlStatus_Error;
pc = current->pc();
return ControlStatus_Jumped;
}
bool
IonBuilder::jsop_label()
{
JS_ASSERT(JSOp(*pc) == JSOP_LABEL);
jsbytecode *endpc = pc + GET_JUMP_OFFSET(pc);
JS_ASSERT(endpc > pc);
ControlFlowInfo label(cfgStack_.length(), endpc);
if (!labels_.append(label))
return false;
return cfgStack_.append(CFGState::Label(endpc));
}
bool
IonBuilder::jsop_condswitch()
{
// CondSwitch op looks as follows:
// condswitch [length +exit_pc; first case offset +next-case ]
// {
// {
// ... any code ...
// case (+jump) [pcdelta offset +next-case]
// }+
// default (+jump)
// ... jump targets ...
// }
//
// The default case is always emitted even if there is no default case in
// the source. The last case statement pcdelta source note might have a 0
// offset on the last case (not all the time).
//
// A conditional evaluate the condition of each case and compare it to the
// switch value with a strict equality. Cases conditions are iterated
// linearly until one is matching. If one case succeeds, the flow jumps into
// the corresponding body block. The body block might alias others and
// might continue in the next body block if the body is not terminated with
// a break.
//
// Algorithm:
// 1/ Loop over the case chain to reach the default target
// & Estimate the number of uniq bodies.
// 2/ Generate code for all cases (see processCondSwitchCase).
// 3/ Generate code for all bodies (see processCondSwitchBody).
JS_ASSERT(JSOp(*pc) == JSOP_CONDSWITCH);
jssrcnote *sn = info().getNote(cx, pc);
JS_ASSERT(SN_TYPE(sn) == SRC_CONDSWITCH);
// Get the exit pc
jsbytecode *exitpc = pc + js_GetSrcNoteOffset(sn, 0);
jsbytecode *firstCase = pc + js_GetSrcNoteOffset(sn, 1);
// Iterate all cases in the conditional switch.
// - Stop at the default case. (always emitted after the last case)
// - Estimate the number of uniq bodies. This estimation might be off by 1
// if the default body alias a case body.
jsbytecode *curCase = firstCase;
jsbytecode *lastTarget = GetJumpOffset(curCase) + curCase;
size_t nbBodies = 2; // default target and the first body.
JS_ASSERT(pc < curCase && curCase <= exitpc);
while (JSOp(*curCase) == JSOP_CASE) {
// Fetch the next case.
jssrcnote *caseSn = info().getNote(cx, curCase);
JS_ASSERT(caseSn && SN_TYPE(caseSn) == SRC_NEXTCASE);
ptrdiff_t off = js_GetSrcNoteOffset(caseSn, 0);
curCase = off ? curCase + off : GetNextPc(curCase);
JS_ASSERT(pc < curCase && curCase <= exitpc);
// Count non-aliased cases.
jsbytecode *curTarget = GetJumpOffset(curCase) + curCase;
if (lastTarget < curTarget)
nbBodies++;
lastTarget = curTarget;
}
// The current case now be the default case which jump to the body of the
// default case, which might be behind the last target.
JS_ASSERT(JSOp(*curCase) == JSOP_DEFAULT);
jsbytecode *defaultTarget = GetJumpOffset(curCase) + curCase;
JS_ASSERT(curCase < defaultTarget && defaultTarget <= exitpc);
// Allocate the current graph state.
CFGState state = CFGState::CondSwitch(exitpc, defaultTarget);
if (!state.condswitch.bodies || !state.condswitch.bodies->init(nbBodies))
return ControlStatus_Error;
// We loop on case conditions with processCondSwitchCase.
JS_ASSERT(JSOp(*firstCase) == JSOP_CASE);
state.stopAt = firstCase;
state.state = CFGState::COND_SWITCH_CASE;
return cfgStack_.append(state);
}
IonBuilder::CFGState
IonBuilder::CFGState::CondSwitch(jsbytecode *exitpc, jsbytecode *defaultTarget)
{
CFGState state;
state.state = COND_SWITCH_CASE;
state.stopAt = NULL;
state.condswitch.bodies = (FixedList<MBasicBlock *> *)GetIonContext()->temp->allocate(
sizeof(FixedList<MBasicBlock *>));
state.condswitch.currentIdx = 0;
state.condswitch.defaultTarget = defaultTarget;
state.condswitch.defaultIdx = uint32_t(-1);
state.condswitch.exitpc = exitpc;
state.condswitch.breaks = NULL;
return state;
}
IonBuilder::CFGState
IonBuilder::CFGState::Label(jsbytecode *exitpc)
{
CFGState state;
state.state = LABEL;
state.stopAt = exitpc;
state.label.breaks = NULL;
return state;
}
IonBuilder::ControlStatus
IonBuilder::processCondSwitchCase(CFGState &state)
{
JS_ASSERT(state.state == CFGState::COND_SWITCH_CASE);
JS_ASSERT(!state.condswitch.breaks);
JS_ASSERT(current);
JS_ASSERT(JSOp(*pc) == JSOP_CASE);
FixedList<MBasicBlock *> &bodies = *state.condswitch.bodies;
jsbytecode *defaultTarget = state.condswitch.defaultTarget;
uint32_t &currentIdx = state.condswitch.currentIdx;
jsbytecode *lastTarget = currentIdx ? bodies[currentIdx - 1]->pc() : NULL;
// Fetch the following case in which we will continue.
jssrcnote *sn = info().getNote(cx, pc);
ptrdiff_t off = js_GetSrcNoteOffset(sn, 0);
jsbytecode *casePc = off ? pc + off : GetNextPc(pc);
bool caseIsDefault = JSOp(*casePc) == JSOP_DEFAULT;
JS_ASSERT(JSOp(*casePc) == JSOP_CASE || caseIsDefault);
// Allocate the block of the matching case.
bool bodyIsNew = false;
MBasicBlock *bodyBlock = NULL;
jsbytecode *bodyTarget = pc + GetJumpOffset(pc);
if (lastTarget < bodyTarget) {
// If the default body is in the middle or aliasing the current target.
if (lastTarget < defaultTarget && defaultTarget <= bodyTarget) {
JS_ASSERT(state.condswitch.defaultIdx == uint32_t(-1));
state.condswitch.defaultIdx = currentIdx;
bodies[currentIdx] = NULL;
// If the default body does not alias any and it would be allocated
// later and stored in the defaultIdx location.
if (defaultTarget < bodyTarget)
currentIdx++;
}
bodyIsNew = true;
// Pop switch and case operands.
bodyBlock = newBlockPopN(current, bodyTarget, 2);
bodies[currentIdx++] = bodyBlock;
} else {
// This body alias the previous one.
JS_ASSERT(lastTarget == bodyTarget);
JS_ASSERT(currentIdx > 0);
bodyBlock = bodies[currentIdx - 1];
}
if (!bodyBlock)
return ControlStatus_Error;
lastTarget = bodyTarget;
// Allocate the block of the non-matching case. This can either be a normal
// case or the default case.
bool caseIsNew = false;
MBasicBlock *caseBlock = NULL;
if (!caseIsDefault) {
caseIsNew = true;
// Pop the case operand.
caseBlock = newBlockPopN(current, GetNextPc(pc), 1);
} else {
// The non-matching case is the default case, which jump directly to its
// body. Skip the creation of a default case block and directly create
// the default body if it does not alias any previous body.
if (state.condswitch.defaultIdx == uint32_t(-1)) {
// The default target is the last target.
JS_ASSERT(lastTarget < defaultTarget);
state.condswitch.defaultIdx = currentIdx++;
caseIsNew = true;
} else if (bodies[state.condswitch.defaultIdx] == NULL) {
// The default target is in the middle and it does not alias any
// case target.
JS_ASSERT(defaultTarget < lastTarget);
caseIsNew = true;
} else {
// The default target is in the middle and it alias a case target.
JS_ASSERT(defaultTarget <= lastTarget);
caseBlock = bodies[state.condswitch.defaultIdx];
}
// Allocate and register the default body.
if (caseIsNew) {
// Pop the case & switch operands.
caseBlock = newBlockPopN(current, defaultTarget, 2);
bodies[state.condswitch.defaultIdx] = caseBlock;
}
}
if (!caseBlock)
return ControlStatus_Error;
// Terminate the last case condition block by emitting the code
// corresponding to JSOP_CASE bytecode.
if (bodyBlock != caseBlock) {
MDefinition *caseOperand = current->pop();
MDefinition *switchOperand = current->peek(-1);
MCompare *cmpResult = MCompare::New(switchOperand, caseOperand, JSOP_STRICTEQ);
cmpResult->infer(cx, inspector, pc);
JS_ASSERT(!cmpResult->isEffectful());
current->add(cmpResult);
current->end(MTest::New(cmpResult, bodyBlock, caseBlock));
// Add last case as predecessor of the body if the body is aliasing
// the previous case body.
if (!bodyIsNew && !bodyBlock->addPredecessorPopN(current, 1))
return ControlStatus_Error;
// Add last case as predecessor of the non-matching case if the
// non-matching case is an aliased default case. We need to pop the
// switch operand as we skip the default case block and use the default
// body block directly.
JS_ASSERT_IF(!caseIsNew, caseIsDefault);
if (!caseIsNew && !caseBlock->addPredecessorPopN(current, 1))
return ControlStatus_Error;
} else {
// The default case alias the last case body.
JS_ASSERT(caseIsDefault);
current->pop(); // Case operand
current->pop(); // Switch operand
current->end(MGoto::New(bodyBlock));
if (!bodyIsNew && !bodyBlock->addPredecessor(current))
return ControlStatus_Error;
}
if (caseIsDefault) {
// The last case condition is finished. Loop in processCondSwitchBody,
// with potential stops in processSwitchBreak. Check that the bodies
// fixed list is over-estimate by at most 1, and shrink the size such as
// length can be used as an upper bound while iterating bodies.
JS_ASSERT(currentIdx == bodies.length() || currentIdx + 1 == bodies.length());
bodies.shrink(bodies.length() - currentIdx);
// Handle break statements in processSwitchBreak while processing
// bodies.
ControlFlowInfo breakInfo(cfgStack_.length() - 1, state.condswitch.exitpc);
if (!switches_.append(breakInfo))
return ControlStatus_Error;
// Jump into the first body.
currentIdx = 0;
setCurrent(NULL);
state.state = CFGState::COND_SWITCH_BODY;
return processCondSwitchBody(state);
}
// Continue until the case condition.
setCurrentAndSpecializePhis(caseBlock);
pc = current->pc();
state.stopAt = casePc;
return ControlStatus_Jumped;
}
IonBuilder::ControlStatus
IonBuilder::processCondSwitchBody(CFGState &state)
{
JS_ASSERT(state.state == CFGState::COND_SWITCH_BODY);
JS_ASSERT(pc <= state.condswitch.exitpc);
FixedList<MBasicBlock *> &bodies = *state.condswitch.bodies;
uint32_t &currentIdx = state.condswitch.currentIdx;
JS_ASSERT(currentIdx <= bodies.length());
if (currentIdx == bodies.length()) {
JS_ASSERT_IF(current, pc == state.condswitch.exitpc);
return processSwitchEnd(state.condswitch.breaks, state.condswitch.exitpc);
}
// Get the next body
MBasicBlock *nextBody = bodies[currentIdx++];
JS_ASSERT_IF(current, pc == nextBody->pc());
// Fix the reverse post-order iteration.
graph().moveBlockToEnd(nextBody);
// The last body continue into the new one.
if (current) {
current->end(MGoto::New(nextBody));
nextBody->addPredecessor(current);
}
// Continue in the next body.
setCurrentAndSpecializePhis(nextBody);
pc = current->pc();
if (currentIdx < bodies.length())
state.stopAt = bodies[currentIdx]->pc();
else
state.stopAt = state.condswitch.exitpc;
return ControlStatus_Jumped;
}
bool
IonBuilder::jsop_andor(JSOp op)
{
JS_ASSERT(op == JSOP_AND || op == JSOP_OR);
jsbytecode *rhsStart = pc + js_CodeSpec[op].length;
jsbytecode *joinStart = pc + GetJumpOffset(pc);
JS_ASSERT(joinStart > pc);
// We have to leave the LHS on the stack.
MDefinition *lhs = current->peek(-1);