new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-08.js
@@ -0,0 +1,7 @@
+
+function foo(x,n) {
+ for (var i = -5; i < n; i++) {
+ x[i] = 10;
+ }
+}
+foo([1,2,3,4,5],5);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-09.js
@@ -0,0 +1,11 @@
+
+function foo(x, y) {
+ for (var i = 0; i < x.length; i++) {
+ x[i];
+ if (i < 20)
+ y[i + 1] = 0;
+ }
+}
+
+var q = Array(1,2,3,4,5);
+foo(q, []);
--- a/js/src/jsanalyze.cpp
+++ b/js/src/jsanalyze.cpp
@@ -715,16 +715,88 @@ Script::analyze(JSContext *cx, JSScript
}
}
JS_ASSERT(!failed());
JS_ASSERT(forwardJump == 0 && forwardCatch == 0);
}
/////////////////////////////////////////////////////////////////////
+// Stack Analysis
+/////////////////////////////////////////////////////////////////////
+
+bool
+StackAnalysis::analyze(JSArenaPool &pool, JSScript *script,
+ uint32 start, uint32 length, Script *analysis)
+{
+ this->script = script;
+ this->start = start;
+ this->length = length;
+
+ poppedArray = ArenaArray<PoppedValue*>(pool, length);
+ if (!poppedArray)
+ return false;
+ PodZero(poppedArray, length);
+
+ PoppedValue *stack = ArenaArray<PoppedValue>(pool, script->nslots - script->nfixed);
+ if (!stack)
+ return false;
+
+ unsigned depth = analysis->getCode(start).stackDepth;
+ for (unsigned i = 0; i < depth; i++)
+ stack[i].reset();
+
+ unsigned offset = start;
+ while (offset < start + length) {
+ jsbytecode *pc = script->code + offset;
+ uint32 successorOffset = offset + GetBytecodeLength(pc);
+
+ Bytecode *code = analysis->maybeCode(pc);
+ if (!code) {
+ offset = successorOffset;
+ continue;
+ }
+
+ for (unsigned i = depth; i < code->stackDepth; i++)
+ stack[i].reset();
+ depth = code->stackDepth;
+
+ if (code->jumpTarget) {
+ for (unsigned i = 0; i < depth; i++)
+ stack[i].reset();
+ }
+
+ unsigned nuses = GetUseCount(script, offset);
+ unsigned ndefs = GetDefCount(script, offset);
+
+ if (nuses) {
+ PoppedValue *popped = ArenaArray<PoppedValue>(pool, nuses);
+ if (!popped)
+ return false;
+ for (unsigned i = 0; i < nuses; i++)
+ popped[i] = stack[depth - 1 - i];
+ poppedArray[offset - start] = popped;
+ }
+
+ for (unsigned i = 0; i < ndefs; i++) {
+ PoppedValue &value = stack[depth - nuses + i];
+ value.offset = offset;
+ value.which = i;
+ }
+
+ depth -= nuses;
+ depth += ndefs;
+
+ offset = successorOffset;
+ }
+
+ return true;
+}
+
+/////////////////////////////////////////////////////////////////////
// Live Range Analysis
/////////////////////////////////////////////////////////////////////
LifetimeScript::LifetimeScript()
{
PodZero(this);
}
@@ -1120,372 +1192,10 @@ LifetimeScript::extendVariable(JSContext
return false;
tail->start = segment->end;
tail->loopTail = true;
segment->next = tail;
return true;
}
-/* Whether pc is a loop test operand accessing a variable modified by the loop. */
-bool
-LifetimeScript::loopVariableAccess(LifetimeLoop *loop, jsbytecode *pc)
-{
- unsigned nargs = script->fun ? script->fun->nargs : 0;
- switch (JSOp(*pc)) {
- case JSOP_GETLOCAL:
- case JSOP_INCLOCAL:
- case JSOP_DECLOCAL:
- case JSOP_LOCALINC:
- case JSOP_LOCALDEC:
- if (analysis->localEscapes(GET_SLOTNO(pc)))
- return false;
- return firstWrite(2 + nargs + GET_SLOTNO(pc), loop) != uint32(-1);
- case JSOP_GETARG:
- case JSOP_INCARG:
- case JSOP_DECARG:
- case JSOP_ARGINC:
- case JSOP_ARGDEC:
- if (analysis->argEscapes(GET_SLOTNO(pc)))
- return false;
- return firstWrite(2 + GET_SLOTNO(pc), loop) != uint32(-1);
- default:
- return false;
- }
-}
-
-/*
- * Get any slot/constant accessed by a loop test operand, in terms of its value
- * at the start of the next loop iteration.
- */
-bool
-LifetimeScript::getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp)
-{
- *slotp = LifetimeLoop::UNASSIGNED;
- *constantp = 0;
-
- /*
- * If the pc is modifying a variable and the value tested is its earlier value
- * (e.g. 'x++ < n'), we need to account for the modification --- at the start
- * of the next iteration, the value compared will have been 'x - 1'.
- * Note that we don't need to worry about other accesses to the variable
- * in the condition like 'x++ < x', as loop tests where both operands are
- * modified by the loop are rejected.
- */
-
- JSOp op = JSOp(*pc);
- switch (op) {
-
- case JSOP_GETLOCAL:
- case JSOP_INCLOCAL:
- case JSOP_DECLOCAL:
- case JSOP_LOCALINC:
- case JSOP_LOCALDEC: {
- uint32 local = GET_SLOTNO(pc);
- if (analysis->localEscapes(local))
- return false;
- *slotp = 2 + (script->fun ? script->fun->nargs : 0) + local; /* :XXX: factor out */
- if (op == JSOP_LOCALINC)
- *constantp = -1;
- else if (op == JSOP_LOCALDEC)
- *constantp = 1;
- return true;
- }
-
- case JSOP_GETARG:
- case JSOP_INCARG:
- case JSOP_DECARG:
- case JSOP_ARGINC:
- case JSOP_ARGDEC: {
- uint32 arg = GET_SLOTNO(pc);
- if (analysis->argEscapes(GET_SLOTNO(pc)))
- return false;
- *slotp = 2 + arg; /* :XXX: factor out */
- if (op == JSOP_ARGINC)
- *constantp = -1;
- else if (op == JSOP_ARGDEC)
- *constantp = 1;
- return true;
- }
-
- case JSOP_ZERO:
- *constantp = 0;
- return true;
-
- case JSOP_ONE:
- *constantp = 1;
- return true;
-
- case JSOP_UINT16:
- *constantp = (int32_t) GET_UINT16(pc);
- return true;
-
- case JSOP_UINT24:
- *constantp = (int32_t) GET_UINT24(pc);
- return true;
-
- case JSOP_INT8:
- *constantp = GET_INT8(pc);
- return true;
-
- case JSOP_INT32:
- /*
- * Don't allow big constants out of the range of an object's max
- * nslots, to avoid integer overflow.
- */
- *constantp = GET_INT32(pc);
- if (*constantp >= JSObject::NSLOTS_LIMIT || *constantp <= -JSObject::NSLOTS_LIMIT)
- return false;
- return true;
-
- default:
- return false;
- }
-}
-
-void
-LifetimeScript::analyzeLoopTest(LifetimeLoop *loop)
-{
- /*
- * Try to pick out loop tests like 'A cmp B', where A and B are locals/args
- * or constants, and at most one is modified in the body of the loop.
- * :TODO: bug 618692 once more general loop invariant code motion is in
- * place, this needs to be more robust. Also, LoopState::checkHoistedBounds
- * depends on the test not storing anything between the entry and backedge,
- * and also needs to be more robust.
- */
-
- /* Don't handle do-while loops. */
- if (loop->entry == loop->head)
- return;
-
- /* Don't handle loops with branching inside their condition. */
- if (loop->entry < loop->lastBlock)
- return;
-
- /*
- * Only handle loops with four opcodes between the entry and backedge:
- * get/inc/dec lhs, get/inc/dec rhs, compare, jump to head
- */
- jsbytecode *backedge = script->code + loop->backedge;
-
- jsbytecode *one = script->code + loop->entry;
- if (one == backedge)
- return;
- jsbytecode *two = one + GetBytecodeLength(one);
- if (two == backedge)
- return;
- jsbytecode *three = two + GetBytecodeLength(two);
- if (three == backedge)
- return;
- if (three + GetBytecodeLength(three) != backedge || JSOp(*backedge) != JSOP_IFNE)
- return;
-
- /* Only handle inequalities in the compare condition. */
- JSOp cmpop = JSOp(*three);
- switch (cmpop) {
- case JSOP_GT:
- case JSOP_GE:
- case JSOP_LT:
- case JSOP_LE:
- break;
- default:
- return;
- }
-
- /* Reverse the condition if the LHS is not modified by the loop. */
- if (!loopVariableAccess(loop, one)) {
- jsbytecode *tmp = one;
- one = two;
- two = tmp;
- cmpop = ReverseCompareOp(cmpop);
- }
-
- /* Only handle comparisons where the RHS is not modified by the loop. */
- if (loopVariableAccess(loop, two))
- return;
-
- uint32 lhs;
- int32 lhsConstant;
- if (!getLoopTestAccess(one, &lhs, &lhsConstant))
- return;
-
- uint32 rhs;
- int32 rhsConstant;
- if (!getLoopTestAccess(two, &rhs, &rhsConstant))
- return;
-
- if (lhs == LifetimeLoop::UNASSIGNED)
- return;
-
- /* Passed all filters, this is a loop test we can capture. */
-
- loop->testLHS = lhs;
- loop->testRHS = rhs;
- loop->testConstant = rhsConstant - lhsConstant;
-
- switch (cmpop) {
- case JSOP_GT:
- loop->testConstant++; /* x > y ==> x >= y + 1 */
- /* FALLTHROUGH */
- case JSOP_GE:
- loop->testLessEqual = false;
- break;
-
- case JSOP_LT:
- loop->testConstant--; /* x < y ==> x <= y - 1 */
- case JSOP_LE:
- loop->testLessEqual = true;
- break;
-
- default:
- JS_NOT_REACHED("Bad op");
- return;
- }
-}
-
-bool
-LifetimeScript::analyzeLoopIncrements(JSContext *cx, LifetimeLoop *loop)
-{
- /*
- * Find locals and arguments which are used in exactly one inc/dec operation in every
- * iteration of the loop (we only match against the last basic block, but could
- * also handle the first basic block).
- */
-
- Vector<LifetimeLoop::Increment> increments(cx);
-
- unsigned nargs = script->fun ? script->fun->nargs : 0;
- for (unsigned i = 0; i < nargs; i++) {
- if (analysis->argEscapes(i))
- continue;
-
- uint32 offset = onlyWrite(2 + i, loop);
- if (offset == uint32(-1) || offset < loop->lastBlock)
- continue;
-
- JSOp op = JSOp(script->code[offset]);
- if (op == JSOP_SETARG)
- continue;
-
- LifetimeLoop::Increment inc;
- inc.slot = 2 + i; /* :XXX: factor out */
- inc.offset = offset;
- if (!increments.append(inc))
- return false;
- }
-
- for (unsigned i = 0; i < script->nfixed; i++) {
- if (analysis->localEscapes(i))
- continue;
-
- uint32 offset = onlyWrite(2 + nargs + i, loop);
- if (offset == uint32(-1) || offset < loop->lastBlock)
- continue;
-
- JSOp op = JSOp(script->code[offset]);
- if (op == JSOP_SETLOCAL || op == JSOP_SETLOCALPOP)
- continue;
-
- LifetimeLoop::Increment inc;
- inc.slot = 2 + (script->fun ? script->fun->nargs : 0) + i; /* :XXX: factor out */
- inc.offset = offset;
- if (!increments.append(inc))
- return false;
- }
-
- loop->increments = ArenaArray<LifetimeLoop::Increment>(pool, increments.length());
- if (!loop->increments)
- return false;
- loop->nIncrements = increments.length();
-
- for (unsigned i = 0; i < increments.length(); i++)
- loop->increments[i] = increments[i];
-
- return true;
-}
-
-bool
-LifetimeScript::analyzeLoopModset(JSContext *cx, LifetimeLoop *loop)
-{
- Vector<types::TypeObject *> growArrays(cx);
-
- /*
- * To figure out modsets, we need to know the type sets on the stack at
- * each point. These were generated when running inference on the script,
- * but are no longer retained and we need to reconstruct them here.
- */
-
- types::TypeSet **stack = ArenaArray<types::TypeSet*>(pool, script->nslots);
- if (!stack)
- return false;
-
- unsigned offset = loop->head;
- unsigned stackDepth = 0;
-
- while (offset < loop->backedge) {
- jsbytecode *pc = script->code + offset;
- unsigned successorOffset = offset + GetBytecodeLength(pc);
-
- analyze::Bytecode *opinfo = analysis->maybeCode(offset);
- if (!opinfo) {
- offset = successorOffset;
- continue;
- }
-
- if (opinfo->stackDepth > stackDepth) {
- unsigned ndefs = opinfo->stackDepth - stackDepth;
- memset(&stack[stackDepth], 0, ndefs * sizeof(types::TypeSet*));
- }
- stackDepth = opinfo->stackDepth;
-
- switch (JSOp(*pc)) {
-
- case JSOP_SETHOLE: {
- types::TypeSet *types = stack[opinfo->stackDepth - 3];
- if (types && !types->unknown()) {
- unsigned count = types->getObjectCount();
- for (unsigned i = 0; i < count; i++) {
- types::TypeObject *object = types->getObject(i);
- if (object) {
- bool found = false;
- for (unsigned i = 0; !found && i < growArrays.length(); i++) {
- if (growArrays[i] == object)
- found = true;
- }
- if (!found && !growArrays.append(object))
- return false;
- }
- }
- } else {
- loop->unknownModset = true;
- }
- break;
- }
-
- default:
- break;
- }
-
- unsigned nuses = analyze::GetUseCount(script, offset);
- unsigned ndefs = analyze::GetDefCount(script, offset);
- memset(&stack[stackDepth - nuses], 0, ndefs * sizeof(types::TypeSet*));
- stackDepth = stackDepth - nuses + ndefs;
-
- for (unsigned i = 0; i < ndefs; i++)
- stack[stackDepth - ndefs + i] = script->types->pushed(offset, i);
-
- offset = successorOffset;
- }
-
- loop->growArrays = ArenaArray<types::TypeObject*>(pool, growArrays.length());
- if (!loop->growArrays)
- return false;
- loop->nGrowArrays = growArrays.length();
-
- for (unsigned i = 0; i < growArrays.length(); i++)
- loop->growArrays[i] = growArrays[i];
-
- return true;
-}
-
} /* namespace analyze */
} /* namespace js */
--- a/js/src/jsanalyze.h
+++ b/js/src/jsanalyze.h
@@ -322,16 +322,48 @@ struct UntrapOpcode
~UntrapOpcode()
{
if (trap)
*pc = JSOP_TRAP;
}
};
/*
+ * Analysis over a range of bytecode to determine where each popped value was
+ * originally pushed.
+ */
+struct StackAnalysis
+{
+ /* For values whose pushed location is not known. */
+ static const uint32 UNKNOWN_PUSHED = uint32(-1);
+
+ struct PoppedValue {
+ uint32 offset;
+ uint32 which;
+ void reset() { offset = UNKNOWN_PUSHED; which = 0; }
+ };
+
+ PoppedValue **poppedArray;
+ uint32 start;
+ uint32 length;
+
+ JSScript *script;
+
+ bool analyze(JSArenaPool &pool, JSScript *script, uint32 start, uint32 length,
+ Script *analysis);
+
+ const PoppedValue &popped(uint32 offset, uint32 which) {
+ return poppedArray[offset - start][which];
+ }
+ const PoppedValue &popped(jsbytecode *pc, uint32 which) {
+ return popped(pc - script->code, which);
+ }
+};
+
+/*
* Lifetime analysis. The goal of this analysis is to make a single backwards pass
* over a script to approximate the regions where each variable is live, without
* doing 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
@@ -396,58 +428,23 @@ struct LifetimeLoop
* Start of the last basic block in the loop, excluding the initial jump to
* entry. All code between lastBlock and the backedge runs in every
* iteration, and if entry >= lastBlock all code between entry and the
* backedge runs when the loop is initially entered.
*/
uint32 lastBlock;
/*
- * Any inequality known to hold at the head of the loop. This has the
- * form 'lhs <= rhs + constant' or 'lhs >= rhs + constant', depending on
- * lessEqual. The lhs may be modified within the loop body (the test is
- * invalid afterwards), and the rhs is invariant. This information is only
- * valid if the LHS/RHS are known integers.
- */
- enum { UNASSIGNED = uint32(-1) };
- uint32 testLHS;
- uint32 testRHS;
- int32 testConstant;
- bool testLessEqual;
-
- /*
- * A variable which will be incremented or decremented exactly once in each
- * iteration of the loop. The offset of the operation is indicated, which
- * may or may not run after the initial entry into the loop.
- */
- struct Increment {
- uint32 slot;
- uint32 offset;
- };
- Increment *increments;
- uint32 nIncrements;
-
- /* It is unknown which arrays grow or which objects are modified in this loop. */
- bool unknownModset;
-
- /*
* This loop contains safe points in its body which the interpreter might
* join at directly.
*/
bool hasSafePoints;
/* This loop has calls or inner loops. */
bool hasCallsLoops;
-
- /*
- * Arrays which might grow during this loop. This is a guess, and may
- * underapproximate the actual set of such arrays.
- */
- types::TypeObject **growArrays;
- uint32 nGrowArrays;
};
/* Lifetime and register information for a bytecode. */
struct LifetimeBytecode
{
/* If this is a loop head, information about the loop. */
LifetimeLoop *loop;
@@ -585,30 +582,19 @@ class LifetimeScript
return lifetimes[slot].nonDecreasing(script, loop);
}
uint32 onlyWrite(uint32 slot, LifetimeLoop *loop) {
JS_ASSERT(slot < nLifetimes);
return lifetimes[slot].onlyWrite(loop);
}
- /*
- * Note: loop analysis depends on the function not having had indirect
- * modification of its arguments. Clients must watch for this.
- */
- void analyzeLoopTest(LifetimeLoop *loop);
- bool analyzeLoopIncrements(JSContext *cx, LifetimeLoop *loop);
- bool analyzeLoopModset(JSContext *cx, LifetimeLoop *loop);
-
private:
inline bool addVariable(JSContext *cx, LifetimeVariable &var, unsigned offset);
inline bool killVariable(JSContext *cx, LifetimeVariable &var, unsigned offset);
inline bool extendVariable(JSContext *cx, LifetimeVariable &var, unsigned start, unsigned end);
-
- bool loopVariableAccess(LifetimeLoop *loop, jsbytecode *pc);
- bool getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp);
};
} /* namespace analyze */
} /* namespace js */
#endif // jsanalyze_h___
--- a/js/src/jsinfer.h
+++ b/js/src/jsinfer.h
@@ -455,17 +455,20 @@ enum {
* Whether all the properties of this object are unknown. When this object
* appears in a type set, nothing can be assumed about its contents,
* including whether the .proto field is correct. This is needed to handle
* mutable __proto__, which requires us to unify all type objects with
* unknown properties in type sets (see SetProto).
*/
OBJECT_FLAG_UNKNOWN_MASK = uint32(-1),
- /* Whether any objects this represents are not dense arrays. */
+ /*
+ * Whether any objects this represents are not dense arrays. This also
+ * includes dense arrays whose length property does not fit in an int32.
+ */
OBJECT_FLAG_NON_DENSE_ARRAY = 1 << 0,
/* Whether any objects this represents are not packed arrays. */
OBJECT_FLAG_NON_PACKED_ARRAY = 1 << 1,
/* Whether any objects this represents have had their .arguments accessed. */
OBJECT_FLAG_UNINLINEABLE = 1 << 2,
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -423,20 +423,26 @@ JSObject::getArrayLength() const
return (uint32)(size_t) getPrivate();
}
inline bool
JSObject::setArrayLength(JSContext *cx, uint32 length)
{
JS_ASSERT(isArray());
- if (length > INT32_MAX &&
- !cx->addTypePropertyId(getType(), ATOM_TO_JSID(cx->runtime->atomState.lengthAtom),
- js::types::TYPE_DOUBLE)) {
- return false;
+ if (length > INT32_MAX) {
+ /*
+ * Mark the type of this object as possibly not a dense array, per the
+ * requirements of OBJECT_FLAG_NON_DENSE_ARRAY.
+ */
+ if (!cx->markTypeArrayNotPacked(getType(), true))
+ return false;
+ jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
+ if (!cx->addTypePropertyId(getType(), lengthId, js::types::TYPE_DOUBLE))
+ return false;
}
setPrivate((void*) length);
return true;
}
inline void
JSObject::setDenseArrayLength(uint32 length)
--- a/js/src/methodjit/Compiler.cpp
+++ b/js/src/methodjit/Compiler.cpp
@@ -4354,23 +4354,36 @@ mjit::Compiler::jsop_length()
masm.urshift32(Imm32(JSString::LENGTH_SHIFT), str);
frame.pop();
frame.pushTypedPayload(JSVAL_TYPE_INT32, str);
}
return true;
}
/*
- * Check if we are accessing the 'length' property of a known dense array
- * which must fit in an int32.
+ * Check if this is an array we can make a loop invariant entry for.
+ * This will fail for objects which are not definitely dense arrays.
+ */
+ if (loop && loop->generatingInvariants()) {
+ FrameEntry *fe = loop->invariantLength(top);
+ if (fe) {
+ frame.pop();
+ frame.pushTemporary(fe);
+ return true;
+ }
+ }
+
+ /*
+ * Check if we are accessing the 'length' property of a known dense array.
+ * Note that if the types are known to indicate dense arrays, their lengths
+ * must fit in an int32.
*/
types::TypeSet *types = frame.extra(top).types;
types::ObjectKind kind = types ? types->getKnownObjectKind(cx) : types::OBJECT_UNKNOWN;
- if ((kind == types::OBJECT_DENSE_ARRAY || kind == types::OBJECT_PACKED_ARRAY) &&
- knownPushedType(0) == JSVAL_TYPE_INT32) {
+ if ((kind == types::OBJECT_DENSE_ARRAY || kind == types::OBJECT_PACKED_ARRAY)) {
bool isObject = top->isTypeKnown();
if (!isObject) {
Jump notObject = frame.testObject(Assembler::NotEqual, top);
stubcc.linkExit(notObject, Uses(1));
stubcc.leave();
OOL_STUBCALL(stubs::Length);
}
RegisterID reg = frame.tempRegForData(top);
@@ -5407,17 +5420,17 @@ mjit::Compiler::jsop_this()
stubcc.linkExit(notObj, Uses(1));
stubcc.leave();
OOL_STUBCALL(stubs::This);
stubcc.rejoin(Changes(1));
}
// Now we know that |this| is an object.
frame.pop();
- frame.learnThisIsObject();
+ frame.learnThisIsObject(type != JSVAL_TYPE_OBJECT);
frame.pushThis();
}
JS_ASSERT(thisFe->isType(JSVAL_TYPE_OBJECT));
}
}
bool
@@ -6578,38 +6591,43 @@ mjit::Compiler::finishLoop(jsbytecode *h
RegisterAllocation *alloc = a->liveness.getCode(head).allocation;
JaegerSpew(JSpew_Regalloc, "loop allocation at %u:", head - script->code);
frame.dumpAllocation(alloc);
}
#endif
loop->entryJump().linkTo(masm.label(), &masm);
+ jsbytecode *oldPC = PC;
+
+ PC = entryTarget;
{
REJOIN_SITE(stubs::MissedBoundsCheckEntry);
OOL_STUBCALL(stubs::MissedBoundsCheckEntry);
if (loop->generatingInvariants()) {
/*
* To do the initial load of the invariants, jump to the invariant
* restore point after the call just emitted. :XXX: fix hackiness.
*/
if (oomInVector)
return false;
Label label = callSites[callSites.length() - 1].loopJumpLabel;
stubcc.linkExitDirect(masm.jump(), label);
}
stubcc.crossJump(stubcc.masm.jump(), masm.label());
}
+ PC = oldPC;
frame.prepareForJump(entryTarget, masm, true);
if (!jumpInScript(masm.jump(), entryTarget))
return false;
+ PC = head;
if (!a->analysis.getCode(head).safePoint) {
/*
* Emit a stub into the OOL path which loads registers from a synced state
* and jumps to the loop head, for rejoining from the interpreter.
*/
LoopEntry entry;
entry.pcOffset = head - script->code;
@@ -6626,16 +6644,17 @@ mjit::Compiler::finishLoop(jsbytecode *h
autoRejoinHead.oolRejoin(stubcc.masm.label());
frame.prepareForJump(head, stubcc.masm, true);
if (!stubcc.jumpInScript(stubcc.masm.jump(), head))
return false;
loopEntries.append(entry);
}
+ PC = oldPC;
/* Write out loads and tests of loop invariants at all calls in the loop body. */
loop->flushLoop(stubcc);
LoopState *nloop = loop->outer;
cx->delete_(loop);
loop = nloop;
frame.setLoop(loop);
--- a/js/src/methodjit/FrameEntry.h
+++ b/js/src/methodjit/FrameEntry.h
@@ -55,17 +55,17 @@ class FrameEntry
friend class FrameState;
friend class ImmutableSync;
public:
/* Accessors for entries which are known constants. */
bool isConstant() const {
- if (isCopy() || isInvariant())
+ if (isCopy())
return false;
return data.isConstant();
}
const jsval_layout &getConstant() const {
JS_ASSERT(isConstant());
return v_;
}
@@ -151,32 +151,19 @@ class FrameEntry
const FrameEntry *backing() const {
return isCopy() ? copyOf() : this;
}
bool hasSameBacking(const FrameEntry *other) const {
return backing() == other->backing();
}
- /*
- * Accessors for entries which are copies of analysis temporaries. All
- * temporaries are invariant, so these behave more like constants than like
- * copies of mutable entries.
- */
-
- bool isInvariant() const { return !!invariant_; }
-
- FrameEntry *invariant() {
- JS_ASSERT(isInvariant());
- return invariant_;
- }
-
private:
void setType(JSValueType type_) {
- JS_ASSERT(!isCopy() && !isInvariant());
+ JS_ASSERT(!isCopy());
type.setConstant();
#if defined JS_NUNBOX32
v_.s.tag = JSVAL_TYPE_TO_TAG(type_);
#elif defined JS_PUNBOX64
v_.asBits &= JSVAL_PAYLOAD_MASK;
v_.asBits |= JSVAL_TYPE_TO_SHIFTED_TAG(type_);
#endif
knownType = type_;
@@ -186,17 +173,16 @@ class FrameEntry
clear();
index_ = index;
tracked = true;
}
void clear() {
copied = false;
copy = NULL;
- invariant_ = NULL;
}
uint32 trackerIndex() {
return index_;
}
/*
* Marks the FE as unsynced & invalid.
@@ -237,76 +223,71 @@ class FrameEntry
void setCopied() {
JS_ASSERT(!isCopy());
copied = true;
}
FrameEntry *copyOf() const {
JS_ASSERT(isCopy());
- JS_ASSERT(copy < this);
+ JS_ASSERT_IF(!copy->temporary, copy < this);
return copy;
}
void setNotCopied() {
copied = false;
}
/*
* Set copy index.
*/
void setCopyOf(FrameEntry *fe) {
JS_ASSERT(!isCopied());
copy = fe;
- invariant_ = NULL;
if (fe) {
type.invalidate();
data.invalidate();
}
}
- void setInvariant(FrameEntry *fe) {
- JS_ASSERT(!isCopied());
- copy = NULL;
- invariant_ = fe;
- type.invalidate();
- data.invalidate();
- }
-
inline bool isTracked() const {
return tracked;
}
inline void untrack() {
tracked = false;
}
inline bool dataInRegister(AnyRegisterID reg) const {
- JS_ASSERT(!copy && !invariant_);
+ JS_ASSERT(!copy);
return reg.isReg()
? (data.inRegister() && data.reg() == reg.reg())
: (data.inFPRegister() && data.fpreg() == reg.fpreg());
}
private:
JSValueType knownType;
jsval_layout v_;
RematInfo type;
RematInfo data;
uint32 index_;
- FrameEntry *invariant_;
FrameEntry *copy;
bool copied;
bool tracked;
bool inlined;
+ bool temporary;
/*
* Offset of the last loop in which this entry was written or had a loop
* register assigned.
*/
uint32 lastLoop;
+
+#if JS_BITS_PER_WORD == 32
+ void *padding;
+#endif
};
} /* namespace mjit */
} /* namespace js */
#endif /* jsjaeger_valueinfo_h__ */
--- a/js/src/methodjit/FrameState-inl.h
+++ b/js/src/methodjit/FrameState-inl.h
@@ -613,23 +613,23 @@ FrameState::tempRegForData(FrameEntry *f
masm.loadPayload(addressOf(fe), reg);
return reg;
}
}
inline bool
FrameState::shouldAvoidTypeRemat(FrameEntry *fe)
{
- return !fe->isCopy() && !fe->isInvariant() && fe->type.inMemory();
+ return !fe->isCopy() && fe->type.inMemory();
}
inline bool
FrameState::shouldAvoidDataRemat(FrameEntry *fe)
{
- return !fe->isCopy() && !fe->isInvariant() && fe->data.inMemory();
+ return !fe->isCopy() && fe->data.inMemory();
}
inline void
FrameState::ensureFeSynced(const FrameEntry *fe, Assembler &masm) const
{
Address to = addressOf(fe);
const FrameEntry *backing = fe;
if (fe->isCopy())
@@ -1111,17 +1111,17 @@ FrameState::unpinKilledReg(RegisterID re
{
regstate(reg).unpinUnsafe();
a->freeRegs.putReg(reg);
}
inline void
FrameState::forgetAllRegs(FrameEntry *fe)
{
- if (fe->isCopy() || fe->isInvariant())
+ if (fe->isCopy())
return;
if (fe->type.inRegister())
forgetReg(fe->type.reg());
if (fe->data.inRegister())
forgetReg(fe->data.reg());
if (fe->data.inFPRegister())
forgetReg(fe->data.fpreg());
}
@@ -1218,23 +1218,30 @@ FrameState::pushCallee()
inline void
FrameState::pushThis()
{
FrameEntry *fe = getThis();
pushCopyOf(indexOfFe(fe));
}
+inline void
+FrameState::pushTemporary(FrameEntry *fe)
+{
+ JS_ASSERT(isTemporary(fe));
+ pushCopyOf(indexOfFe(fe));
+}
+
void
-FrameState::learnThisIsObject()
+FrameState::learnThisIsObject(bool unsync)
{
// This is safe, albeit hacky. This is only called from the compiler,
// and only on the first use of |this| inside a basic block. Thus,
// there are no copies of |this| anywhere.
- learnType(this_, JSVAL_TYPE_OBJECT);
+ learnType(this_, JSVAL_TYPE_OBJECT, unsync);
}
inline void
FrameState::leaveBlock(uint32 n)
{
popn(n);
}
@@ -1302,18 +1309,17 @@ FrameState::loadDouble(RegisterID t, Reg
loadDouble(fe, fpreg, masm);
#endif
}
inline bool
FrameState::tryFastDoubleLoad(FrameEntry *fe, FPRegisterID fpReg, Assembler &masm) const
{
#ifdef JS_CPU_X86
- if (!fe->isCopy() && !fe->isInvariant() &&
- fe->type.inRegister() && fe->data.inRegister()) {
+ if (!fe->isCopy() && fe->type.inRegister() && fe->data.inRegister()) {
masm.fastLoadDouble(fe->data.reg(), fe->type.reg(), fpReg);
return true;
}
#endif
return false;
}
inline void
--- a/js/src/methodjit/FrameState.cpp
+++ b/js/src/methodjit/FrameState.cpp
@@ -1328,26 +1328,23 @@ FrameState::assertValidRegisterState() c
for (uint32 i = 0; i < a->tracker.nentries; i++) {
FrameEntry *fe = a->tracker[i];
if (deadEntry(fe))
continue;
JS_ASSERT(i == fe->trackerIndex());
if (fe->isCopy()) {
+ JS_ASSERT_IF(!fe->copyOf()->temporary, fe > fe->copyOf());
JS_ASSERT(fe->trackerIndex() > fe->copyOf()->trackerIndex());
- JS_ASSERT(fe > fe->copyOf());
JS_ASSERT(!deadEntry(fe->copyOf()));
JS_ASSERT(fe->copyOf()->isCopied());
continue;
}
- if (fe->isInvariant())
- continue;
-
if (fe->type.inRegister()) {
checkedFreeRegs.takeReg(fe->type.reg());
JS_ASSERT(regstate(fe->type.reg()).fe() == fe);
}
if (fe->data.inRegister()) {
checkedFreeRegs.takeReg(fe->data.reg());
JS_ASSERT(regstate(fe->data.reg()).fe() == fe);
}
@@ -1531,17 +1528,17 @@ FrameState::sync(Assembler &masm, Uses u
if ((!fe->type.synced() && backing->type.inMemory()) ||
(!fe->data.synced() && backing->data.inMemory())) {
syncFancy(masm, avail, fe, bottom);
return;
}
#endif
}
- bool copy = fe->isCopy() || fe->isInvariant();
+ bool copy = fe->isCopy();
/* If a part still needs syncing, it is either a copy or constant. */
#if defined JS_PUNBOX64
/* All register-backed FEs have been entirely synced up-front. */
if (copy || (!fe->type.inRegister() && !fe->data.inRegister()))
ensureFeSynced(fe, masm);
#elif defined JS_NUNBOX32
/* All components held in registers have been already synced. */
@@ -1621,17 +1618,17 @@ FrameState::syncAndKill(Registers kill,
maxvisits--;
if (deadEntry(fe, ignore.nuses))
continue;
syncFe(fe);
- if (fe->isCopy() || fe->isInvariant())
+ if (fe->isCopy())
continue;
/* Forget registers. */
if (fe->data.inRegister() && !regstate(fe->data.reg()).isPinned()) {
forgetReg(fe->data.reg());
fe->data.setMemory();
}
if (fe->data.inFPRegister() && !regstate(fe->data.fpreg()).isPinned()) {
@@ -2066,35 +2063,32 @@ FrameState::ensureDouble(FrameEntry *fe)
void
FrameState::ensureInMemoryDoubles(Assembler &masm)
{
JS_ASSERT(!a->parent);
for (uint32 i = 0; i < a->tracker.nentries; i++) {
FrameEntry *fe = a->tracker[i];
if (!deadEntry(fe) && fe->isType(JSVAL_TYPE_DOUBLE) &&
- !fe->isCopy() && !fe->isInvariant() && !fe->isConstant()) {
+ !fe->isCopy() && !fe->isConstant()) {
masm.ensureInMemoryDouble(addressOf(fe));
}
}
}
void
FrameState::pushCopyOf(uint32 index)
{
FrameEntry *backing = entryFor(index);
FrameEntry *fe = rawPush();
fe->resetUnsynced();
if (backing->isConstant()) {
fe->setConstant(Jsvalify(backing->getValue()));
} else {
- if (backing->isTypeKnown())
- fe->setType(backing->getKnownType());
- else
- fe->type.invalidate();
+ fe->type.invalidate();
fe->data.invalidate();
if (backing->isCopy()) {
backing = backing->copyOf();
fe->setCopyOf(backing);
} else {
fe->setCopyOf(backing);
backing->setCopied();
}
@@ -2104,16 +2098,19 @@ FrameState::pushCopyOf(uint32 index)
if (fe->trackerIndex() < backing->trackerIndex())
swapInTracker(fe, backing);
}
}
FrameEntry *
FrameState::walkTrackerForUncopy(FrameEntry *original)
{
+ /* Temporary entries are immutable and should never be uncopied. */
+ JS_ASSERT(!isTemporary(original));
+
uint32 firstCopy = InvalidIndex;
FrameEntry *bestFe = NULL;
uint32 ncopies = 0;
for (uint32 i = original->trackerIndex() + 1; i < a->tracker.nentries; i++) {
FrameEntry *fe = a->tracker[i];
if (deadEntry(fe))
continue;
if (fe->isCopy() && fe->copyOf() == original) {
@@ -2377,16 +2374,18 @@ FrameState::forgetEntry(FrameEntry *fe)
if (fe >= spBase && fe < sp)
a->extraArray[fe - spBase].reset();
}
void
FrameState::storeTop(FrameEntry *target, JSValueType type, bool popGuaranteed)
{
+ JS_ASSERT(!isTemporary(target));
+
/* Detect something like (x = x) which is a no-op. */
FrameEntry *top = peek(-1);
if (top->isCopy() && top->copyOf() == target) {
JS_ASSERT(target->isCopied());
return;
}
/* Completely invalidate the local variable. */
@@ -3040,16 +3039,17 @@ FrameState::maybeUnpinReg(MaybeRegisterI
uint32
FrameState::allocTemporary()
{
if (temporariesTop == temporaries + TEMPORARY_LIMIT)
return uint32(-1);
FrameEntry *fe = temporariesTop++;
fe->lastLoop = 0;
+ fe->temporary = true;
return fe - temporaries;
}
void
FrameState::clearTemporaries()
{
for (FrameEntry *fe = temporaries; fe < temporariesTop; fe++) {
if (!fe->isTracked())
--- a/js/src/methodjit/FrameState.h
+++ b/js/src/methodjit/FrameState.h
@@ -361,22 +361,25 @@ class FrameState
inline void leaveBlock(uint32 n);
// Pushes a copy of a slot (formal argument, local variable, or stack slot)
// onto the operation stack.
void pushLocal(uint32 n, JSValueType knownType);
void pushArg(uint32 n, JSValueType knownType);
void pushCallee();
void pushThis();
- inline void learnThisIsObject();
+ void pushTemporary(FrameEntry *fe);
+ inline void learnThisIsObject(bool unsync = true);
inline FrameEntry *getStack(uint32 slot);
inline FrameEntry *getLocal(uint32 slot);
inline FrameEntry *getArg(uint32 slot);
+ inline FrameEntry *getOrTrack(uint32 index);
+
/*
* Allocates a temporary register for a FrameEntry's type. The register
* can be spilled or clobbered by the frame. The compiler may only operate
* on it temporarily, and must take care not to clobber it.
*/
inline RegisterID tempRegForType(FrameEntry *fe);
/*
@@ -910,17 +913,16 @@ class FrameState
inline void ensureDataSynced(const FrameEntry *fe, Assembler &masm) const;
/* Guarantee sync, even if register allocation is required, and set sync. */
inline void syncFe(FrameEntry *fe);
inline void syncType(FrameEntry *fe);
inline void syncData(FrameEntry *fe);
inline void syncAndForgetFe(FrameEntry *fe);
- inline FrameEntry *getOrTrack(uint32 index);
inline FrameEntry *getCallee();
inline FrameEntry *getThis();
inline void forgetAllRegs(FrameEntry *fe);
inline void swapInTracker(FrameEntry *lhs, FrameEntry *rhs);
void pushCopyOf(uint32 index);
#if defined JS_NUNBOX32
void syncFancy(Assembler &masm, Registers avail, FrameEntry *resumeAt,
FrameEntry *bottom) const;
--- a/js/src/methodjit/LoopState.cpp
+++ b/js/src/methodjit/LoopState.cpp
@@ -48,58 +48,70 @@ using namespace js::analyze;
LoopState::LoopState(JSContext *cx, JSScript *script,
mjit::Compiler *cc, FrameState *frame,
Script *analysis, LifetimeScript *liveness)
: cx(cx), script(script), cc(*cc), frame(*frame), analysis(analysis), liveness(liveness),
lifetime(NULL), alloc(NULL), loopRegs(0), skipAnalysis(false),
loopJoins(CompilerAllocPolicy(cx, *cc)),
loopPatches(CompilerAllocPolicy(cx, *cc)),
restoreInvariantCalls(CompilerAllocPolicy(cx, *cc)),
- hoistedBoundsChecks(CompilerAllocPolicy(cx, *cc)),
- invariantArraySlots(CompilerAllocPolicy(cx, *cc)),
- outer(NULL), PC(NULL)
+ invariantEntries(CompilerAllocPolicy(cx, *cc)),
+ outer(NULL), PC(NULL),
+ testLHS(UNASSIGNED), testRHS(UNASSIGNED),
+ testConstant(0), testLessEqual(false), testLength(false),
+ increments(CompilerAllocPolicy(cx, *cc)), unknownModset(false),
+ growArrays(CompilerAllocPolicy(cx, *cc)),
+ modifiedProperties(CompilerAllocPolicy(cx, *cc))
{
JS_ASSERT(cx->typeInferenceEnabled());
}
bool
LoopState::init(jsbytecode *head, Jump entry, jsbytecode *entryTarget)
{
this->lifetime = liveness->getCode(head).loop;
JS_ASSERT(lifetime &&
lifetime->head == uint32(head - script->code) &&
lifetime->entry == uint32(entryTarget - script->code));
this->entry = entry;
- liveness->analyzeLoopTest(lifetime);
- if (!liveness->analyzeLoopIncrements(cx, lifetime))
- return false;
- if (!liveness->analyzeLoopModset(cx, lifetime))
+ if (!stack.analyze(liveness->pool, script, lifetime->head,
+ lifetime->backedge - lifetime->head + 1, analysis)) {
return false;
-
- if (lifetime->testLHS != LifetimeLoop::UNASSIGNED) {
- JaegerSpew(JSpew_Analysis, "loop test at %u: %s %s %s + %d\n", lifetime->head,
- frame.entryName(lifetime->testLHS),
- lifetime->testLessEqual ? "<=" : ">=",
- (lifetime->testRHS == LifetimeLoop::UNASSIGNED)
- ? ""
- : frame.entryName(lifetime->testRHS),
- lifetime->testConstant);
}
- for (unsigned i = 0; i < lifetime->nIncrements; i++) {
- JaegerSpew(JSpew_Analysis, "loop increment at %u for %s: %u\n", lifetime->head,
- frame.entryName(lifetime->increments[i].slot),
- lifetime->increments[i].offset);
+ analyzeLoopTest();
+ analyzeLoopIncrements();
+ analyzeModset();
+
+ if (testLHS != UNASSIGNED) {
+ JaegerSpew(JSpew_Analysis, "loop test at %u: %s %s%s %s + %d\n", lifetime->head,
+ frame.entryName(testLHS),
+ testLessEqual ? "<=" : ">=",
+ testLength ? " length" : "",
+ (testRHS == UNASSIGNED) ? "" : frame.entryName(testRHS),
+ testConstant);
}
- for (unsigned i = 0; i < lifetime->nGrowArrays; i++) {
+ for (unsigned i = 0; i < increments.length(); i++) {
+ JaegerSpew(JSpew_Analysis, "loop increment at %u for %s: %u\n", lifetime->head,
+ frame.entryName(increments[i].slot),
+ increments[i].offset);
+ }
+
+ for (unsigned i = 0; i < growArrays.length(); i++) {
JaegerSpew(JSpew_Analysis, "loop grow array at %u: %s\n", lifetime->head,
- lifetime->growArrays[i]->name());
+ growArrays[i]->name());
+ }
+
+ for (unsigned i = 0; i < modifiedProperties.length(); i++) {
+ JaegerSpew(JSpew_Analysis, "loop modified property at %u: %s %s\n", lifetime->head,
+ modifiedProperties[i].object->name(),
+ types::TypeIdString(modifiedProperties[i].id));
}
RegisterAllocation *&alloc = liveness->getCode(head).allocation;
JS_ASSERT(!alloc);
alloc = ArenaNew<RegisterAllocation>(liveness->pool, true);
if (!alloc)
return false;
@@ -254,61 +266,92 @@ LoopState::loopInvariantEntry(const Fram
bool
LoopState::addHoistedCheck(uint32 arraySlot, uint32 valueSlot, int32 constant)
{
/*
* Check to see if this bounds check either implies or is implied by an
* existing hoisted check.
*/
- for (unsigned i = 0; i < hoistedBoundsChecks.length(); i++) {
- HoistedBoundsCheck &check = hoistedBoundsChecks[i];
- if (check.arraySlot == arraySlot && check.valueSlot == valueSlot) {
- if (check.constant < constant)
- check.constant = constant;
+ for (unsigned i = 0; i < invariantEntries.length(); i++) {
+ InvariantEntry &entry = invariantEntries[i];
+ if (entry.kind == InvariantEntry::BOUNDS_CHECK &&
+ entry.u.check.arraySlot == arraySlot &&
+ entry.u.check.valueSlot == valueSlot) {
+ if (entry.u.check.constant < constant)
+ entry.u.check.constant = constant;
return true;
}
}
/*
* Maintain an invariant that for any array with a hoisted bounds check,
* we also have a loop invariant slot to hold the array's slots pointer.
* The compiler gets invariant array slots only for accesses with a hoisted
* bounds check, so this makes invariantSlots infallible.
*/
bool hasInvariantSlots = false;
- for (unsigned i = 0; !hasInvariantSlots && i < invariantArraySlots.length(); i++) {
- if (invariantArraySlots[i].arraySlot == arraySlot)
+ for (unsigned i = 0; !hasInvariantSlots && i < invariantEntries.length(); i++) {
+ InvariantEntry &entry = invariantEntries[i];
+ if (entry.kind == InvariantEntry::INVARIANT_SLOTS &&
+ entry.u.array.arraySlot == arraySlot) {
hasInvariantSlots = true;
+ }
}
if (!hasInvariantSlots) {
uint32 which = frame.allocTemporary();
if (which == uint32(-1))
return false;
FrameEntry *fe = frame.getTemporary(which);
JaegerSpew(JSpew_Analysis, "Using %s for loop invariant slots of %s\n",
frame.entryName(fe), frame.entryName(arraySlot));
- InvariantArraySlots slots;
- slots.arraySlot = arraySlot;
- slots.temporary = which;
- invariantArraySlots.append(slots);
+ InvariantEntry entry;
+ entry.kind = InvariantEntry::INVARIANT_SLOTS;
+ entry.u.array.arraySlot = arraySlot;
+ entry.u.array.temporary = which;
+ invariantEntries.append(entry);
}
- HoistedBoundsCheck check;
- check.arraySlot = arraySlot;
- check.valueSlot = valueSlot;
- check.constant = constant;
- hoistedBoundsChecks.append(check);
+ InvariantEntry entry;
+ entry.kind = InvariantEntry::BOUNDS_CHECK;
+ entry.u.check.arraySlot = arraySlot;
+ entry.u.check.valueSlot = valueSlot;
+ entry.u.check.constant = constant;
+ invariantEntries.append(entry);
return true;
}
void
+LoopState::addNegativeCheck(uint32 valueSlot, int32 constant)
+{
+ /*
+ * Check to see if this check either implies or is implied by an
+ * existing negative check.
+ */
+ for (unsigned i = 0; i < invariantEntries.length(); i++) {
+ InvariantEntry &entry = invariantEntries[i];
+ if (entry.kind == InvariantEntry::NEGATIVE_CHECK &&
+ entry.u.check.valueSlot == valueSlot) {
+ if (entry.u.check.constant > constant)
+ entry.u.check.constant = constant;
+ return;
+ }
+ }
+
+ InvariantEntry entry;
+ entry.kind = InvariantEntry::NEGATIVE_CHECK;
+ entry.u.check.valueSlot = valueSlot;
+ entry.u.check.constant = constant;
+ invariantEntries.append(entry);
+}
+
+void
LoopState::setLoopReg(AnyRegisterID reg, FrameEntry *fe)
{
JS_ASSERT(alloc->loop(reg));
loopRegs.takeReg(reg);
uint32 slot = frame.indexOfFe(fe);
JaegerSpew(JSpew_Regalloc, "allocating loop register %s for %s\n",
reg.name(), frame.entryName(fe));
@@ -372,23 +415,22 @@ LoopState::hoistArrayLengthCheck(const F
}
/*
* Check for an overlap with the arrays we think might grow in this loop.
* This information is only a guess; if we don't think the array can grow
* but it actually can, we will probably recompile after the hoisted
* bounds check fails.
*/
- if (lifetime->nGrowArrays) {
- types::TypeObject **growArrays = lifetime->growArrays;
+ if (!growArrays.empty()) {
unsigned count = objTypes->getObjectCount();
for (unsigned i = 0; i < count; i++) {
types::TypeObject *object = objTypes->getObject(i);
if (object) {
- for (unsigned j = 0; j < lifetime->nGrowArrays; j++) {
+ for (unsigned j = 0; j < growArrays.length(); j++) {
if (object == growArrays[j]) {
JaegerSpew(JSpew_Analysis, "Object might grow inside loop\n");
return false;
}
}
}
}
}
@@ -403,127 +445,667 @@ LoopState::hoistArrayLengthCheck(const F
if (loopInvariantEntry(index)) {
/* Hoist checks on x[y] accesses when y is loop invariant. */
JaegerSpew(JSpew_Analysis, "Hoisted as initlen > %s\n", frame.entryName(index));
return addHoistedCheck(frame.indexOfFe(obj), frame.indexOfFe(index), 0);
}
- if (frame.indexOfFe(index) == lifetime->testLHS && lifetime->testLessEqual) {
+ if (frame.indexOfFe(index) == testLHS && testLessEqual) {
/*
* If the access is of the form x[y] where we know that y <= z + n at
* the head of the loop, hoist the check as initlen < z + n provided
* that y has not been modified since the head of the loop.
*/
- uint32 rhs = lifetime->testRHS;
- int32 constant = lifetime->testConstant;
+ uint32 rhs = testRHS;
/*
* If the LHS can decrease in the loop, it could become negative and
* underflow the array.
*/
- if (!liveness->nonDecreasing(lifetime->testLHS, lifetime)) {
+ if (!liveness->nonDecreasing(testLHS, lifetime)) {
JaegerSpew(JSpew_Analysis, "Index may decrease in future iterations\n");
return false;
}
- uint32 write = liveness->firstWrite(lifetime->testLHS, lifetime);
- JS_ASSERT(write != LifetimeLoop::UNASSIGNED);
+ uint32 write = liveness->firstWrite(testLHS, lifetime);
+ JS_ASSERT(write != UNASSIGNED);
if (write < uint32(PC - script->code)) {
JaegerSpew(JSpew_Analysis, "Index previously modified in loop\n");
return false;
}
- if (rhs != LifetimeLoop::UNASSIGNED) {
- /*
- * The index will be a known int or will have been guarded as an int,
- * but the branch test substitution is only valid if it is comparing
- * integers.
- */
+ if (rhs != UNASSIGNED) {
types::TypeSet *types = cc.getTypeSet(rhs);
- if (types->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
- JaegerSpew(JSpew_Analysis, "Branch test may not be on integer\n");
+ if (!types) {
+ JaegerSpew(JSpew_Analysis, "Unknown type of branch test\n");
return false;
}
+ if (testLength) {
+ FrameEntry *rhsFE = frame.getOrTrack(rhs);
+ FrameEntry *lengthEntry = invariantLength(rhsFE);
+ if (!lengthEntry) {
+ JaegerSpew(JSpew_Analysis, "Could not get invariant entry for length\n");
+ return false;
+ }
+ rhs = frame.indexOfFe(lengthEntry);
+ } else {
+ /*
+ * The index will be a known int or will have been guarded as an int,
+ * but the branch test substitution is only valid if it is comparing
+ * integers.
+ */
+ if (types->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
+ JaegerSpew(JSpew_Analysis, "Branch test may not be on integer\n");
+ return false;
+ }
+ }
}
+ /*
+ * Check that the LHS is nonnegative every time we rejoin the loop.
+ * This is only really necessary on initial loop entry. Note that this
+ * test is not sensitive to changes to the LHS between when we make
+ * the test and the start of the next iteration, as we've ensured the
+ * LHS is nondecreasing within the body of the loop.
+ */
+
+ JaegerSpew(JSpew_Analysis, "Nonnegative check %s + %d >= 0\n",
+ frame.entryName(testLHS), 0);
+
+ addNegativeCheck(testLHS, 0);
+
JaegerSpew(JSpew_Analysis, "Hoisted as initlen > %s + %d\n",
- (rhs == LifetimeLoop::UNASSIGNED) ? "" : frame.entryName(rhs),
- constant);
+ (rhs == UNASSIGNED) ? "" : frame.entryName(rhs),
+ testConstant);
- return addHoistedCheck(frame.indexOfFe(obj), rhs, constant);
+ return addHoistedCheck(frame.indexOfFe(obj), rhs, testConstant);
}
JaegerSpew(JSpew_Analysis, "No match found\n");
return false;
}
FrameEntry *
LoopState::invariantSlots(const FrameEntry *obj)
{
obj = obj->backing();
uint32 slot = frame.indexOfFe(obj);
- for (unsigned i = 0; i < invariantArraySlots.length(); i++) {
- if (invariantArraySlots[i].arraySlot == slot)
- return frame.getTemporary(invariantArraySlots[i].temporary);
+ for (unsigned i = 0; i < invariantEntries.length(); i++) {
+ InvariantEntry &entry = invariantEntries[i];
+ if (entry.kind == InvariantEntry::INVARIANT_SLOTS &&
+ entry.u.array.arraySlot == slot) {
+ return frame.getTemporary(entry.u.array.temporary);
+ }
}
/* addHoistedCheck should have ensured there is an entry for the slots. */
JS_NOT_REACHED("Missing invariant slots");
return NULL;
}
+FrameEntry *
+LoopState::invariantLength(const FrameEntry *obj)
+{
+ obj = obj->backing();
+ uint32 slot = frame.indexOfFe(obj);
+
+ for (unsigned i = 0; i < invariantEntries.length(); i++) {
+ InvariantEntry &entry = invariantEntries[i];
+ if (entry.kind == InvariantEntry::INVARIANT_LENGTH &&
+ entry.u.array.arraySlot == slot) {
+ FrameEntry *fe = frame.getTemporary(entry.u.array.temporary);
+ frame.learnType(fe, JSVAL_TYPE_INT32, false);
+ return fe;
+ }
+ }
+
+ if (!loopInvariantEntry(obj))
+ return NULL;
+
+ /* Make sure this is a dense array whose length fits in an int32. */
+ types::TypeSet *types = cc.getTypeSet(slot);
+ types::ObjectKind kind = types ? types->getKnownObjectKind(cx) : types::OBJECT_UNKNOWN;
+ if (kind != types::OBJECT_DENSE_ARRAY && kind != types::OBJECT_PACKED_ARRAY)
+ return NULL;
+
+ /*
+ * Don't make 'length' loop invariant if the loop might directly write
+ * to the elements of any of the accessed arrays. This could invoke an
+ * inline path which updates the length.
+ */
+ for (unsigned i = 0; i < types->getObjectCount(); i++) {
+ types::TypeObject *object = types->getObject(i);
+ if (!object)
+ continue;
+ if (object->unknownProperties() || hasModifiedProperty(object, JSID_VOID))
+ return NULL;
+ }
+ types->addFreeze(cx);
+
+ uint32 which = frame.allocTemporary();
+ if (which == uint32(-1))
+ return NULL;
+ FrameEntry *fe = frame.getTemporary(which);
+ frame.learnType(fe, JSVAL_TYPE_INT32, false);
+
+ JaegerSpew(JSpew_Analysis, "Using %s for loop invariant length of %s\n",
+ frame.entryName(fe), frame.entryName(slot));
+
+ InvariantEntry entry;
+ entry.kind = InvariantEntry::INVARIANT_LENGTH;
+ entry.u.array.arraySlot = slot;
+ entry.u.array.temporary = which;
+ invariantEntries.append(entry);
+
+ return fe;
+}
+
void
LoopState::restoreInvariants(Assembler &masm, Vector<Jump> *jumps)
{
/*
* Restore all invariants in memory when entering the loop or after any
* scripted or C++ call, and check that all hoisted conditions. Care should
* be taken not to clobber the return register or callee-saved registers,
* which may still be live after some calls.
*/
Registers regs(Registers::TempRegs);
regs.takeReg(Registers::ReturnReg);
- for (unsigned i = 0; i < invariantArraySlots.length(); i++) {
- const InvariantArraySlots &entry = invariantArraySlots[i];
- FrameEntry *fe = frame.getTemporary(entry.temporary);
+ RegisterID T0 = regs.takeAnyReg().reg();
+ RegisterID T1 = regs.takeAnyReg().reg();
+
+ for (unsigned i = 0; i < invariantEntries.length(); i++) {
+ const InvariantEntry &entry = invariantEntries[i];
+ switch (entry.kind) {
+
+ case InvariantEntry::BOUNDS_CHECK: {
+ /*
+ * Hoisted bounds checks always have preceding invariant slots
+ * in the invariant list, so don't recheck this is an object.
+ */
+ masm.loadPayload(frame.addressOf(entry.u.check.arraySlot), T0);
+ masm.load32(Address(T0, offsetof(JSObject, initializedLength)), T0);
+
+ if (entry.u.check.valueSlot != uint32(-1)) {
+ masm.loadPayload(frame.addressOf(entry.u.check.valueSlot), T1);
+ if (entry.u.check.constant != 0) {
+ Jump overflow = masm.branchAdd32(Assembler::Overflow,
+ Imm32(entry.u.check.constant), T1);
+ jumps->append(overflow);
+ }
+ Jump j = masm.branch32(Assembler::BelowOrEqual, T0, T1);
+ jumps->append(j);
+ } else {
+ Jump j = masm.branch32(Assembler::BelowOrEqual, T0,
+ Imm32(entry.u.check.constant));
+ jumps->append(j);
+ }
+ break;
+ }
+
+ case InvariantEntry::NEGATIVE_CHECK: {
+ masm.loadPayload(frame.addressOf(entry.u.check.valueSlot), T0);
+ if (entry.u.check.constant != 0) {
+ Jump overflow = masm.branchAdd32(Assembler::Overflow,
+ Imm32(entry.u.check.constant), T0);
+ jumps->append(overflow);
+ }
+ Jump j = masm.branch32(Assembler::LessThan, T0, Imm32(0));
+ jumps->append(j);
+ break;
+ }
+
+ case InvariantEntry::INVARIANT_SLOTS:
+ case InvariantEntry::INVARIANT_LENGTH: {
+ /* Make sure this is an object before trying to access its slots or length. */
+ uint32 array = entry.u.array.arraySlot;
+ if (cc.getTypeSet(array)->getKnownTypeTag(cx) != JSVAL_TYPE_OBJECT) {
+ Jump notObject = masm.testObject(Assembler::NotEqual, frame.addressOf(array));
+ jumps->append(notObject);
+ }
+ masm.loadPayload(frame.addressOf(array), T0);
+
+ uint32 offset = (entry.kind == InvariantEntry::INVARIANT_SLOTS)
+ ? JSObject::offsetOfSlots()
+ : offsetof(JSObject, privateData);
+
+ masm.loadPtr(Address(T0, offset), T0);
+ masm.storePtr(T0, frame.addressOf(frame.getTemporary(entry.u.array.temporary)));
+ break;
+ }
+
+ default:
+ JS_NOT_REACHED("Bad invariant kind");
+ }
+ }
+}
+
+/* Loop analysis methods. */
+
+/* :XXX: factor out into more common code. */
+static inline uint32 localSlot(JSScript *script, uint32 local) {
+ return 2 + (script->fun ? script->fun->nargs : 0) + local;
+}
+static inline uint32 argSlot(uint32 arg) {
+ return 2 + arg;
+}
+static inline uint32 thisSlot() {
+ return 1;
+}
+
+/* Whether pc is a loop test operand accessing a variable modified by the loop. */
+bool
+LoopState::loopVariableAccess(jsbytecode *pc)
+{
+ switch (JSOp(*pc)) {
+ case JSOP_GETLOCAL:
+ case JSOP_INCLOCAL:
+ case JSOP_DECLOCAL:
+ case JSOP_LOCALINC:
+ case JSOP_LOCALDEC:
+ if (analysis->localEscapes(GET_SLOTNO(pc)))
+ return false;
+ return liveness->firstWrite(localSlot(script, GET_SLOTNO(pc)), lifetime) != uint32(-1);
+ case JSOP_GETARG:
+ case JSOP_INCARG:
+ case JSOP_DECARG:
+ case JSOP_ARGINC:
+ case JSOP_ARGDEC:
+ if (analysis->argEscapes(GET_SLOTNO(pc)))
+ return false;
+ return liveness->firstWrite(argSlot(GET_SLOTNO(pc)), lifetime) != uint32(-1);
+ default:
+ return false;
+ }
+}
+
+/*
+ * Get any slot/constant accessed by a loop test operand, in terms of its value
+ * at the start of the next loop iteration.
+ */
+bool
+LoopState::getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp)
+{
+ *slotp = UNASSIGNED;
+ *constantp = 0;
- Address array = frame.addressOf(entry.arraySlot);
- Address address = frame.addressOf(fe);
+ /*
+ * If the pc is modifying a variable and the value tested is its earlier value
+ * (e.g. 'x++ < n'), we need to account for the modification --- at the start
+ * of the next iteration, the value compared will have been 'x - 1'.
+ * Note that we don't need to worry about other accesses to the variable
+ * in the condition like 'x++ < x', as loop tests where both operands are
+ * modified by the loop are rejected.
+ */
+
+ JSOp op = JSOp(*pc);
+ switch (op) {
+
+ case JSOP_GETLOCAL:
+ case JSOP_INCLOCAL:
+ case JSOP_DECLOCAL:
+ case JSOP_LOCALINC:
+ case JSOP_LOCALDEC: {
+ uint32 local = GET_SLOTNO(pc);
+ if (analysis->localEscapes(local))
+ return false;
+ *slotp = localSlot(script, local);
+ if (op == JSOP_LOCALINC)
+ *constantp = -1;
+ else if (op == JSOP_LOCALDEC)
+ *constantp = 1;
+ return true;
+ }
+
+ case JSOP_GETARG:
+ case JSOP_INCARG:
+ case JSOP_DECARG:
+ case JSOP_ARGINC:
+ case JSOP_ARGDEC: {
+ uint32 arg = GET_SLOTNO(pc);
+ if (analysis->argEscapes(arg))
+ return false;
+ *slotp = argSlot(arg);
+ if (op == JSOP_ARGINC)
+ *constantp = -1;
+ else if (op == JSOP_ARGDEC)
+ *constantp = 1;
+ return true;
+ }
+
+ case JSOP_ZERO:
+ *constantp = 0;
+ return true;
+
+ case JSOP_ONE:
+ *constantp = 1;
+ return true;
+
+ case JSOP_UINT16:
+ *constantp = (int32_t) GET_UINT16(pc);
+ return true;
+
+ case JSOP_UINT24:
+ *constantp = (int32_t) GET_UINT24(pc);
+ return true;
- RegisterID reg = regs.takeAnyReg().reg();
- masm.loadPayload(array, reg);
- masm.loadPtr(Address(reg, JSObject::offsetOfSlots()), reg);
- masm.storePtr(reg, address);
- regs.putReg(reg);
+ case JSOP_INT8:
+ *constantp = GET_INT8(pc);
+ return true;
+
+ case JSOP_INT32:
+ /*
+ * Don't allow big constants out of the range of an object's max
+ * nslots, to avoid integer overflow.
+ */
+ *constantp = GET_INT32(pc);
+ if (*constantp >= JSObject::NSLOTS_LIMIT || *constantp <= -JSObject::NSLOTS_LIMIT)
+ return false;
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+void
+LoopState::analyzeLoopTest()
+{
+ /* Don't handle do-while loops. */
+ if (lifetime->entry == lifetime->head)
+ return;
+
+ /* Don't handle loops with branching inside their condition. */
+ if (lifetime->entry < lifetime->lastBlock)
+ return;
+
+ /* Get the test performed before branching. */
+ jsbytecode *backedge = script->code + lifetime->backedge;
+ if (JSOp(*backedge) != JSOP_IFNE)
+ return;
+ StackAnalysis::PoppedValue test = stack.popped(backedge, 0);
+ if (test.offset == StackAnalysis::UNKNOWN_PUSHED)
+ return;
+ JSOp cmpop = JSOp(script->code[test.offset]);
+ switch (cmpop) {
+ case JSOP_GT:
+ case JSOP_GE:
+ case JSOP_LT:
+ case JSOP_LE:
+ break;
+ default:
+ return;
+ }
+
+ StackAnalysis::PoppedValue poppedOne = stack.popped(test.offset, 1);
+ StackAnalysis::PoppedValue poppedTwo = stack.popped(test.offset, 0);
+
+ if (poppedOne.offset == StackAnalysis::UNKNOWN_PUSHED ||
+ poppedTwo.offset == StackAnalysis::UNKNOWN_PUSHED) {
+ return;
+ }
+
+ jsbytecode *one = script->code + poppedOne.offset;
+ jsbytecode *two = script->code + poppedTwo.offset;
+
+ /* Reverse the condition if the RHS is modified by the loop. */
+ if (loopVariableAccess(two)) {
+ jsbytecode *tmp = one;
+ one = two;
+ two = tmp;
+ cmpop = ReverseCompareOp(cmpop);
}
- for (unsigned i = 0; i < hoistedBoundsChecks.length(); i++) {
- /* Testing: initializedLength(array) > value + constant; */
- const HoistedBoundsCheck &check = hoistedBoundsChecks[i];
+ /* Don't handle comparisons where both the LHS and RHS are modified in the loop. */
+ if (loopVariableAccess(two))
+ return;
+
+ uint32 lhs;
+ int32 lhsConstant;
+ if (!getLoopTestAccess(one, &lhs, &lhsConstant))
+ return;
+
+ uint32 rhs = UNASSIGNED;
+ int32 rhsConstant = 0;
+ bool rhsLength = false;
- RegisterID initlen = regs.takeAnyReg().reg();
- masm.loadPayload(frame.addressOf(check.arraySlot), initlen);
- masm.load32(Address(initlen, offsetof(JSObject, initializedLength)), initlen);
+ if (JSOp(*two) == JSOP_LENGTH) {
+ /* Handle 'this.length' or 'x.length' for loop invariant 'x'. */
+ StackAnalysis::PoppedValue array = stack.popped(two, 0);
+ if (array.offset == StackAnalysis::UNKNOWN_PUSHED)
+ return;
+ jsbytecode *arraypc = script->code + array.offset;
+ if (loopVariableAccess(arraypc))
+ return;
+ switch (JSOp(*arraypc)) {
+ case JSOP_GETLOCAL: {
+ uint32 local = GET_SLOTNO(arraypc);
+ if (analysis->localEscapes(local))
+ return;
+ rhs = localSlot(script, local);
+ break;
+ }
+ case JSOP_GETARG: {
+ uint32 arg = GET_SLOTNO(arraypc);
+ if (analysis->argEscapes(arg))
+ return;
+ rhs = argSlot(arg);
+ break;
+ }
+ case JSOP_THIS:
+ rhs = thisSlot();
+ break;
+ default:
+ return;
+ }
+ rhsLength = true;
+ } else {
+ if (!getLoopTestAccess(two, &rhs, &rhsConstant))
+ return;
+ }
+
+ if (lhs == UNASSIGNED)
+ return;
+
+ /* Passed all filters, this is a loop test we can capture. */
+
+ this->testLHS = lhs;
+ this->testRHS = rhs;
+ this->testConstant = rhsConstant - lhsConstant;
+ this->testLength = rhsLength;
+
+ switch (cmpop) {
+ case JSOP_GT:
+ this->testConstant++; /* x > y ==> x >= y + 1 */
+ /* FALLTHROUGH */
+ case JSOP_GE:
+ this->testLessEqual = false;
+ break;
- if (check.valueSlot != uint32(-1)) {
- RegisterID value = regs.takeAnyReg().reg();
- masm.loadPayload(frame.addressOf(check.valueSlot), value);
- if (check.constant != 0) {
- Jump overflow = masm.branchAdd32(Assembler::Overflow,
- Imm32(check.constant), value);
- jumps->append(overflow);
- }
- Jump j = masm.branch32(Assembler::BelowOrEqual, initlen, value);
- jumps->append(j);
- regs.putReg(value);
- } else {
- Jump j = masm.branch32(Assembler::BelowOrEqual, initlen, Imm32(check.constant));
- jumps->append(j);
+ case JSOP_LT:
+ this->testConstant--; /* x < y ==> x <= y - 1 */
+ case JSOP_LE:
+ this->testLessEqual = true;
+ break;
+
+ default:
+ JS_NOT_REACHED("Bad op");
+ return;
+ }
+}
+
+void
+LoopState::analyzeLoopIncrements()
+{
+ /*
+ * Find locals and arguments which are used in exactly one inc/dec operation in every
+ * iteration of the loop (we only match against the last basic block, but could
+ * also handle the first basic block).
+ */
+
+ unsigned nargs = script->fun ? script->fun->nargs : 0;
+ for (unsigned i = 0; i < nargs; i++) {
+ if (analysis->argEscapes(i))
+ continue;
+
+ uint32 offset = liveness->onlyWrite(argSlot(i), lifetime);
+ if (offset == uint32(-1) || offset < lifetime->lastBlock)
+ continue;
+
+ JSOp op = JSOp(script->code[offset]);
+ if (op == JSOP_SETARG)
+ continue;
+
+ Increment inc;
+ inc.slot = argSlot(i);
+ inc.offset = offset;
+ increments.append(inc);
+ }
+
+ for (unsigned i = 0; i < script->nfixed; i++) {
+ if (analysis->localEscapes(i))
+ continue;
+
+ uint32 offset = liveness->onlyWrite(localSlot(script, i), lifetime);
+ if (offset == uint32(-1) || offset < lifetime->lastBlock)
+ continue;
+
+ JSOp op = JSOp(script->code[offset]);
+ if (op == JSOP_SETLOCAL || op == JSOP_SETLOCALPOP)
+ continue;
+
+ Increment inc;
+ inc.slot = localSlot(script, i);
+ inc.offset = offset;
+ increments.append(inc);
+ }
+}
+
+void
+LoopState::analyzeModset()
+{
+ /* :XXX: Currently only doing this for arrays modified in the loop. */
+
+ unsigned offset = lifetime->head;
+ while (offset < lifetime->backedge) {
+ jsbytecode *pc = script->code + offset;
+ uint32 successorOffset = offset + GetBytecodeLength(pc);
+
+ analyze::Bytecode *opinfo = analysis->maybeCode(offset);
+ if (!opinfo) {
+ offset = successorOffset;
+ continue;
}
- regs.putReg(initlen);
+ JSOp op = JSOp(*pc);
+ switch (op) {
+
+ case JSOP_SETHOLE:
+ case JSOP_SETELEM: {
+ types::TypeSet *objTypes = poppedTypes(pc, 2);
+ types::TypeSet *elemTypes = poppedTypes(pc, 1);
+
+ /*
+ * Mark the modset as unknown if the index might be non-integer,
+ * we don't want to consider the SETELEM PIC here.
+ */
+ if (!objTypes || objTypes->unknown() || !elemTypes ||
+ elemTypes->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
+ unknownModset = true;
+ return;
+ }
+
+ objTypes->addFreeze(cx);
+ for (unsigned i = 0; i < objTypes->getObjectCount(); i++) {
+ types::TypeObject *object = objTypes->getObject(i);
+ if (!object)
+ continue;
+ if (!addModifiedProperty(object, JSID_VOID))
+ return;
+ if (op == JSOP_SETHOLE && !addGrowArray(object))
+ return;
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+
+ offset = successorOffset;
}
}
+
+bool
+LoopState::addGrowArray(types::TypeObject *object)
+{
+ static const uint32 MAX_SIZE = 10;
+ for (unsigned i = 0; i < growArrays.length(); i++) {
+ if (growArrays[i] == object)
+ return true;
+ }
+ if (growArrays.length() >= MAX_SIZE) {
+ unknownModset = true;
+ return false;
+ }
+ growArrays.append(object);
+
+ return true;
+}
+
+bool
+LoopState::addModifiedProperty(types::TypeObject *object, jsid id)
+{
+ static const uint32 MAX_SIZE = 20;
+ for (unsigned i = 0; i < modifiedProperties.length(); i++) {
+ if (modifiedProperties[i].object == object && modifiedProperties[i].id == id)
+ return true;
+ }
+ if (modifiedProperties.length() >= MAX_SIZE) {
+ unknownModset = true;
+ return false;
+ }
+
+ ModifiedProperty property;
+ property.object = object;
+ property.id = id;
+ modifiedProperties.append(property);
+
+ return true;
+}
+
+bool
+LoopState::hasGrowArray(types::TypeObject *object)
+{
+ if (unknownModset)
+ return true;
+ for (unsigned i = 0; i < growArrays.length(); i++) {
+ if (growArrays[i] == object)
+ return true;
+ }
+ return false;
+}
+
+bool
+LoopState::hasModifiedProperty(types::TypeObject *object, jsid id)
+{
+ if (unknownModset)
+ return true;
+ for (unsigned i = 0; i < modifiedProperties.length(); i++) {
+ if (modifiedProperties[i].object == object && modifiedProperties[i].id == id)
+ return true;
+ }
+ return false;
+}
+
+inline types::TypeSet *
+LoopState::poppedTypes(jsbytecode *pc, unsigned which)
+{
+ StackAnalysis::PoppedValue value = stack.popped(pc, which);
+ if (value.offset == StackAnalysis::UNKNOWN_PUSHED)
+ return NULL;
+ return script->types->pushed(value.offset, value.which);
+}
--- a/js/src/methodjit/LoopState.h
+++ b/js/src/methodjit/LoopState.h
@@ -139,43 +139,54 @@ class LoopState : public MacroAssemblerT
/* Index into Compiler's callSites or rejoinSites */
unsigned patchIndex;
bool patchCall;
};
Vector<RestoreInvariantCall> restoreInvariantCalls;
/*
- * Array bounds check hoisted out of the loop. This is a check that needs
- * to be performed, expressed in terms of the state at the loop head.
+ * Aggregate structure for all loop invariant code and hoisted checks we
+ * can perform. These are all stored in the same vector as they may depend
+ * on each other and we need to emit code restoring them in order.
*/
- struct HoistedBoundsCheck
- {
- /* initializedLength(array) > value + constant */
- uint32 arraySlot;
- uint32 valueSlot;
- int32 constant;
+ struct InvariantEntry {
+ enum {
+ /*
+ * initializedLength(array) > value + constant.
+ * Unsigned comparison, so will fail if value + constant < 0
+ */
+ BOUNDS_CHECK,
+
+ /* value + constant >= 0 */
+ NEGATIVE_CHECK,
+
+ INVARIANT_SLOTS,
+ INVARIANT_LENGTH
+ } kind;
+ union {
+ struct {
+ uint32 arraySlot;
+ uint32 valueSlot;
+ int32 constant;
+ } check;
+ struct {
+ uint32 arraySlot;
+ uint32 temporary;
+ } array;
+ } u;
+ InvariantEntry() { PodZero(this); }
};
- Vector<HoistedBoundsCheck, 4, CompilerAllocPolicy> hoistedBoundsChecks;
+ Vector<InvariantEntry, 4, CompilerAllocPolicy> invariantEntries;
bool loopInvariantEntry(const FrameEntry *fe);
bool addHoistedCheck(uint32 arraySlot, uint32 valueSlot, int32 constant);
+ void addNegativeCheck(uint32 valueSlot, int32 constant);
- /*
- * Track analysis temporaries in the frame state which hold slots pointers
- * for arrays throughout the loop.
- */
- struct InvariantArraySlots
- {
- uint32 arraySlot;
- uint32 temporary;
- };
- Vector<InvariantArraySlots, 4, CompilerAllocPolicy> invariantArraySlots;
-
- bool hasInvariants() { return !hoistedBoundsChecks.empty() || !invariantArraySlots.empty(); }
+ bool hasInvariants() { return !invariantEntries.empty(); }
void restoreInvariants(Assembler &masm, Vector<Jump> *jumps);
public:
/* Outer loop to this one, in case of loop nesting. */
LoopState *outer;
/* Current bytecode for compilation. */
@@ -219,14 +230,82 @@ class LoopState : public MacroAssemblerT
void addJoin(unsigned index, bool script);
void clearLoopRegisters();
void flushLoop(StubCompiler &stubcc);
bool hoistArrayLengthCheck(const FrameEntry *obj, const FrameEntry *id);
FrameEntry *invariantSlots(const FrameEntry *obj);
+ FrameEntry *invariantLength(const FrameEntry *obj);
+
+ private:
+ /* Analysis information for the loop. */
+
+ /* Stack information at points within this loop. */
+ analyze::StackAnalysis stack;
+
+ /*
+ * Any inequality known to hold at the head of the loop. This has the
+ * form 'lhs <= rhs + constant' or 'lhs >= rhs + constant', depending on
+ * lessEqual. The lhs may be modified within the loop body (the test is
+ * invalid afterwards), and the rhs is invariant. This information is only
+ * valid if the LHS/RHS are known integers.
+ */
+ enum { UNASSIGNED = uint32(-1) };
+ uint32 testLHS;
+ uint32 testRHS;
+ int32 testConstant;
+ bool testLessEqual;
+
+ /*
+ * The rhs in the test is testRHS.length; for the test to be valid, the
+ * length must not be directly modified within the loop.
+ */
+ bool testLength;
+
+ /*
+ * A variable which will be incremented or decremented exactly once in each
+ * iteration of the loop. The offset of the operation is indicated, which
+ * may or may not run after the initial entry into the loop.
+ */
+ struct Increment {
+ uint32 slot;
+ uint32 offset;
+ };
+ Vector<Increment, 4, CompilerAllocPolicy> increments;
+
+ /* It is unknown which arrays grow or which objects are modified in this loop. */
+ bool unknownModset;
+
+ /*
+ * Arrays which might grow during this loop. This is a guess, and may
+ * underapproximate the actual set of such arrays.
+ */
+ Vector<types::TypeObject *, 4, CompilerAllocPolicy> growArrays;
+
+ /* Properties which might be modified during this loop. */
+ struct ModifiedProperty {
+ types::TypeObject *object;
+ jsid id;
+ };
+ Vector<ModifiedProperty, 4, CompilerAllocPolicy> modifiedProperties;
+
+ void analyzeLoopTest();
+ void analyzeLoopIncrements();
+ void analyzeModset();
+
+ bool loopVariableAccess(jsbytecode *pc);
+ bool getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp);
+
+ bool addGrowArray(types::TypeObject *object);
+ bool addModifiedProperty(types::TypeObject *object, jsid id);
+
+ bool hasGrowArray(types::TypeObject *object);
+ bool hasModifiedProperty(types::TypeObject *object, jsid id);
+
+ inline types::TypeSet *poppedTypes(jsbytecode *pc, unsigned which);
};
} /* namespace mjit */
} /* namespace js */
#endif /* jsjaeger_loopstate_h__ */