Last Comment Bug 719541 - IonMonkey: bounds check hoisting/consolidation
: IonMonkey: bounds check hoisting/consolidation
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
: -- normal (vote)
: ---
Assigned To: Brian Hackett (:bhackett)
:
Mentors:
Depends on: 720169
Blocks: 703132
  Show dependency treegraph
 
Reported: 2012-01-19 12:10 PST by Brian Hackett (:bhackett)
Modified: 2012-01-26 15:59 PST (History)
4 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
consolidation (66106b3ac316) (23.06 KB, patch)
2012-01-19 17:27 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (66106b3ac316) (36.56 KB, patch)
2012-01-21 16:58 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (66106b3ac316) (48.83 KB, patch)
2012-01-22 13:14 PST, Brian Hackett (:bhackett)
dvander: review+
Details | Diff | Splinter Review

Description Brian Hackett (:bhackett) 2012-01-19 12:10:51 PST
JM+TI has analyses to hoist bounds checks, which are important for good loop perf and should get ported to IonMonkey.  Redundant bounds checks should also be consolidated, e.g. code like:

x = a[0];
y = a[1];
z = a[2];

Should only have a single bounds check.  This sort of access pattern is common in e.g. library code with unrolled loops, which JM+TI does poorly at (bug 703132).
Comment 1 Brian Hackett (:bhackett) 2012-01-19 17:27:52 PST
Created attachment 590063 [details] [diff] [review]
consolidation (66106b3ac316)

Working patch to consolidate bounds checks which differ by only a constant factor, modifies GVN a bit to allow elimination of MIR nodes which are not exactly equivalent.  This is reviewable but leaving as a WIP for now as hoisting will need some of the infrastructure added here (and hoisting is the more important of the two optimizations).
Comment 2 Brian Hackett (:bhackett) 2012-01-21 16:58:04 PST
Created attachment 590523 [details] [diff] [review]
patch (66106b3ac316)

Basic bounds check consolidation and hoisting.  This still needs some more work to handle linear equalities between variables (while (x++ < n) { a[y++] }), which is important for v8-crypto, but that can wait for another bug.
Comment 3 Brian Hackett (:bhackett) 2012-01-21 17:32:52 PST
Comment on attachment 590523 [details] [diff] [review]
patch (66106b3ac316)

Oh, forgot to deal with underflows here, this will need some more work.
Comment 4 Brian Hackett (:bhackett) 2012-01-22 13:14:02 PST
Created attachment 590582 [details] [diff] [review]
patch (66106b3ac316)

Patch with lower bounds checks (and better tests).
Comment 5 Brian Hackett (:bhackett) 2012-01-23 16:18:26 PST
High level overview and example for bounds check hoisting.  The details are commented in tryHoistBoundsCheck, and I'll add this as a comment in the final push.

Given a bounds check within a loop which is not loop invariant, we would like to compute loop invariant bounds checks which imply that the inner check will succeed.  These invariant checks can then be added to the preheader, and the inner check eliminated.

Example:

for (i = v; i < n; i++)
  x[i] = 0;

There are two constraints captured by the bounds check here: i >= 0, and i < length(x).  'i' is not loop invariant, but we can still hoist these checks:

- At the point of the check, it is known that i < n.  Given this, if n <= length(x) then i < length(x), and since n and length(x) are loop invariant the former condition can be hoisted and the i < length(x) check removed.

- i is only incremented within the loop, so if its initial value is >= 0 then all its values within the loop will also be >= 0.  The lower bounds check can be hoisted as v >= 0.

tryHoistBoundsCheck encodes this logic.  Given a bounds check B and a test T in the loop dominating that bounds check, where B and T share a non-invariant term lhs, a new check C is computed such that T && C imply B.
Comment 6 David Anderson [:dvander] 2012-01-25 20:08:39 PST
Comment on attachment 590582 [details] [diff] [review]
patch (66106b3ac316)

Review of attachment 590582 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/CodeGenerator.cpp
@@ +778,5 @@
> +    JS_ASSERT(max >= min);
> +
> +    Register temp = ToRegister(lir->getTemp(0));
> +    if (lir->index()->isConstant()) {
> +        int32 nmin, nmax, index = ToInt32(lir->index());

This declaration would be a little clearer if "index" was on its own line.

::: js/src/ion/LICM.cpp
@@ +66,5 @@
> +        if (lhs->type() == MIRType_Int32 && rhs->type() == MIRType_Int32) {
> +            LinearSum lsum = ExtractLinearSum(lhs);
> +            LinearSum rsum = ExtractLinearSum(rhs);
> +
> +            // We should have constant folded already.  XXX Did we?

Remove XXX (fwiw, we constant fold during GVN, which is optional for LICM)

@@ +71,5 @@
> +            JS_ASSERT(lsum.term || rsum.term);
> +            if (lsum.term && rsum.term)
> +                return LinearSum(ins, 0);
> +
> +            if (ins->isAdd()) {

This code deserves a brief comment explaining which patterns it's trying to fold.

@@ +100,5 @@
> +
> +    MDefinition *lhs = compare->getOperand(0);
> +    MDefinition *rhs = compare->getOperand(1);
> +
> +    if (lhs->type() != MIRType_Int32 || rhs->type() != MIRType_Int32)

It's better to say: compare->specialization() == MIRType_Int32, then you're guaranteed both are int32.

@@ +113,5 @@
> +
> +    if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant))
> +        return false;
> +
> +    switch (jsop) {

Please add a comment here explaining that this code does some normalization to make further areas simpler.

@@ +304,5 @@
> +    // handle dependencies on loop invariant instructions.
> +    InstructionQueue hoistedChecks;
> +    for (size_t i = 0; i < boundsChecks.length(); i++) {
> +        MBoundsCheck *ins = boundsChecks[i]->toBoundsCheck();
> +        if (isLoopInvariant(ins) || !isInLoop(ins))

The first check *might* not be needed; the loop earlier only added bounds checks that were not loop invariant.

@@ +308,5 @@
> +        if (isLoopInvariant(ins) || !isInLoop(ins))
> +            continue;
> +
> +        MBasicBlock *block = ins->block();
> +        while (true) {

Could you add a short comment explaining what this loop is looking for?

@@ +460,5 @@
> +    // Ensure the lhs is a phi node from the start of the loop body.
> +    if (!lhs.term || !lhs.term->isPhi() || lhs.term->block() != header_)
> +        return;
> +
> +    LinearSum index = ExtractLinearSum(ins->index());

Could you add a comment saying something like: "Check to see if the conditional's left term matches the index in the bounds check."

@@ +469,5 @@
> +        return;
> +
> +    // At the point of the access, it is known that lhs + lhsN <= rhs, and the
> +    // bounds check is that lhs + indexN + maximum < length. To ensure the
> +    // bounds check check holds then, we need to ensure that:

"check check"

@@ +488,5 @@
> +    // variable at loop entry and the variable's value never decreases in the
> +    // loop body, it will hold throughout the loop.
> +
> +    uint32 slot = lhs.term->toPhi()->slot();
> +    MDefinition *initialIndex = preLoop_->getSlot(slot);

This should be:
   uint32 position = preLoop_->positionInPhiSuccessor();
   MDefinition *initialIndex = lhs.term->toPhi->getOperand(position);

(this pattern appears elsewhere too, if you wanted you could make it prettier by adding a getOperandFrom(MBasicBlock *) in MPhi).

@@ +490,5 @@
> +
> +    uint32 slot = lhs.term->toPhi()->slot();
> +    MDefinition *initialIndex = preLoop_->getSlot(slot);
> +    while (initialIndex->isCopy())
> +        initialIndex = initialIndex->getOperand(0);

Then this code can go away. It's a bug if copies appear past type analysis.

@@ +534,5 @@
> +    while (!worklist.empty()) {
> +        MDefinition *def = worklist.popCopy();
> +        bool duplicate = false;
> +        for (size_t i = 0; i < seen.length() && !duplicate; i++) {
> +            if (seen[i] == def)

I'd prefer to set/check a MIR flag instead of having this loop. InWorklist is in-use when this is called, but it should be easy to add a new bit (MIR_FLAG_LIST in MIR.h).

@@ +560,5 @@
> +            }
> +            continue;
> +        }
> +
> +        if (def->isAdd()) {

Does this need to test def->toAdd()->specialization() == MIRType_Int32?

::: js/src/ion/LICM.h
@@ +80,5 @@
> +
> +// Extract a linear inequality holding when a boolean test goes in the
> +// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).
> +bool
> +ExtractLinearInequality(MTest *test, bool direction,

This direction boolean should be a JSOp or enum for clarity.

@@ +144,5 @@
> +    // State for hoisting bounds checks. Even if the terms involved in a bounds
> +    // check are not loop invariant, we analyze the tests and increments done
> +    // in the loop to try to find a stronger condition which can be hoisted.
> +
> +    void tryHoistBoundsCheck(MBoundsCheck *ins, MTest *test, bool direction,

Same here.

::: js/src/ion/Lowering.cpp
@@ +836,5 @@
>  bool
>  LIRGenerator::visitBoundsCheck(MBoundsCheck *ins)
>  {
> +    LInstruction *check;
> +    if (ins->minimum() || ins->maximum()) {

Could this test be replaced with something like: isRange()?

::: js/src/ion/MIR.h
@@ +378,5 @@
>  
> +    // Mark this instruction as having replaced all uses of ins, as during GVN,
> +    // returning false if the replacement should not be performed. For use when
> +    // GVN eliminates instructions which are not equivalent to one another.
> +    virtual bool updateForReplacement(MDefinition *ins) { return true; }

Local style is: {
    return true;
}

::: js/src/ion/MIRGraph.cpp
@@ +919,5 @@
> +    if (dom != getPredecessor(0))
> +        return NULL;
> +
> +    // Look for a trailing MTest branching to this block.
> +    for (MInstructionIterator i = dom->begin(); i != dom->end(); i++) {

Control instructions can only appear as the last instruction in a block (and all blocks must terminate in a control instruction). So you should be able to remove this loop and just test |dom->lastIns()->isTest()|

::: js/src/ion/MIRGraph.h
@@ +332,5 @@
>      void setImmediateDominator(MBasicBlock *dom) {
>          immediateDominator_ = dom;
>      }
>  
> +    MTest *immediateDominatorBranch(bool *pdirection);

This function needs a short comment explaining what it does and what "pdirection" is; that or make the bool an enum.

::: js/src/ion/arm/MacroAssembler-arm.cpp
@@ +1148,5 @@
>  MacroAssemblerARMCompat::cmpPtr(const Register &lhs, const ImmWord &rhs)
>  {
>      ma_cmp(lhs, Imm32(rhs.value));
>  }
> +void

Newline above void (this local ARM style isn't a thing, feel free to use normal spidermonkey style).
Comment 7 Brian Hackett (:bhackett) 2012-01-26 15:59:27 PST
https://hg.mozilla.org/projects/ionmonkey/rev/4e74ada3a64f

Note You need to log in before you can comment on or make changes to this bug.