Follow up to Bug 699883. There is currently a hack in range analysis to avoid an iloop in the (unreduced) test case jit-test/tests/basic/fannkuch.js. We run a fixed number of iterations (currently, untuned, 4096). This is a feature, sort of. That is, range analysis can run for any number of iterations and always be correct, if imperfect, and we should take advantage of this if there is ever an IonMonkey baseline compiler. But for the most accurate information, it should be run until a fixed point. Currently, fannkuch.js does not reach this fixed point.

The fix wasn't as simple as we'd theorized. It looks like adds were having a similar effect. Namely, adding 1 to a range that included -inf generated INT_MIN+1, since the infinite bit was getting discarded. I propagated the bits in the transformations.

Comment on attachment 636159 [details] [diff] [review] /home/mrosenberg/patches/noILoopInRangeAnalysis-r0.patch Review of attachment 636159 [details] [diff] [review]: ----------------------------------------------------------------- As per our discussion on IRC, while this does stop the iloop, we want to address this in a way which lets us take advantage of the fact that if an instruction executes, then none of its inputs overflowed (all ranges flowing *into* instructions are finite). The current fix, while correct, undoes that effort. In order to fix the bug *and* use this information, we need to implement "widening", which is discussed at least a little bit here: http://lara.epfl.ch/w/sav09:widening_in_variable_range_analysis, and probably elsewhere as well. To summarize, the bug is not an iloop, but a propagation through an *extremely* large lattice (of height 2^31 in this case, but a lattice could be of height up to 2^64). Widening seeks to cut out large parts of the lattice.

(In reply to Ryan Pearl [:rpearl] from comment #2) > In order to fix the bug *and* use this information, we need to implement > "widening", which is discussed at least a little bit here: > http://lara.epfl.ch/w/sav09:widening_in_variable_range_analysis, and > probably elsewhere as well. Yup, I think widening is the way to go.

There is lots of spew output in here, and it hasn't been rebased in quite some time, but it mostly works. Currently there is one assert that I added that trips, and I think that can be fixed by either explicitly tracking ranges that are empty, or by explicitly tracking blocks that are unreachable, and ignoring their inputs.

This patch enables range analysis to mark some blocks as having contradictions in them (e.g. var x = INT_MIN; x =x - 1; or var y = foo % 0) and are known to not run in the jit. The main purpose of this patch is to prevent us from infinite looping on tests like for (var i = 1; i < 1; i++) { for (var j = 1; j < i; j++) c++; } where we mark i as having range INT_MIN to INT_MAX, within the loop since empty ranges are not handled,then getting shifted to INT_MIN+1 to INT_MAX, and finally back to 0 to INT_MAX due to narrowing, which then gets falls back into the case of having no possible values and getting expanded to INT_MIN to INT_MAX

Evidently, I am still bad at using mq's, since this contains a non-trivial amount of the narrowing code.

Comment on attachment 644781 [details] [diff] [review] /home/mrosenberg/patches/rangeNarrowing-r0.patch Review of attachment 644781 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/MIR.h @@ +2569,5 @@ > + int64_t a = Range::abs64((int64_t)rhs->lower()); > + int64_t b = Range::abs64((int64_t)rhs->upper()); > + if (a ==0 && b == 0) { > + // oh god, oh god, oh god, we should never take something % 0. > + Range r(INT_MIN, INT_MAX); It looks like this variable is dead, since it won't flow into range()->update()? @@ +2744,5 @@ > Range r; > +#if 0 > + JS_ASSERT(getOperand(0)->range()->tryNarrowUpper()); > + JS_ASSERT(getOperand(0)->range()->tryNarrowLower()); > +#endif nit: remove #if 0'd block. ::: js/src/ion/RangeAnalysis.h @@ +116,5 @@ > {} > > + Range(int64_t l, int64_t h) : > + lower_narrow_count(0), > + upper_narrow_count(0) { Style nit: the ':' should be on a new line, two-space indented, and the brace on a new line as well: Range(int64_t l, int64_t h) : lower_narrow_count(0), upper_narrow_count(0) { }

Comment on attachment 646058 [details] [diff] [review] /home/mrosenberg/patches/handleDeadCode-r0.patch Review of attachment 646058 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/MIR.cpp @@ +477,5 @@ > + Range r; > +#if 0 > + JS_ASSERT(getOperand(0)->range()->tryNarrowUpper()); > + JS_ASSERT(getOperand(0)->range()->tryNarrowLower()); > +#endif nit: Replace #if 0'd block with a newline @@ +1478,5 @@ > + bool nullRange = false; > + bool ret = range()->update(Range::intersect(val_->range(), &comparison_, &nullRange)); > + if (nullRange) { > + IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id()); > + block()->setEarlyAbort(); nit: Too many indents ::: js/src/ion/MIR.h @@ +2111,5 @@ > } > > bool recomputeRange() { > + if (earlyAbortCheck()) > + return false; Rather than include this check in every recomputeRange, can we hoist it to the caller? ::: js/src/ion/MIRGraph.cpp @@ +96,5 @@ > return MBasicBlock::New(graph, info, pred, pred->pc(), SPLIT_EDGE); > } > > MBasicBlock::MBasicBlock(MIRGraph &graph, CompileInfo &info, jsbytecode *pc, Kind kind) > + : earlyAbort_(false), nit: unindent : by two spaces ::: js/src/ion/RangeAnalysis.cpp @@ +404,5 @@ > } else { > lower_narrow_count = 0; > } > if (upper_ != other->upper_) { > + //JS_ASSERT((other->upper_ < upper_) || (other->upper_ == INT_MAX)); nit: Remove dead assert (here and a few lines above).

Comment on attachment 646062 [details] [diff] [review] /home/mrosenberg/patches/riceRangeAnalysis-r0.patch Review of attachment 646062 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/MIR.h @@ +2746,5 @@ > > AliasSet getAliasSet() const { > return AliasSet::None(); > } > + bool isOSRValuey (MDefinition *def) { This needs a new home... I'd call it IsOSRLikeValue and put it in the ion namespace in MIR.h. ::: js/src/ion/RangeAnalysis.cpp @@ +439,5 @@ > for (MDefinitionIterator iter(*block); iter; iter++) { > MDefinition *def = *iter; > > + // if (!def->isPhi() && !def->isBeta()) > + // continue; Why did this get commented? Should it be uncommented, or removed? @@ +451,5 @@ > // To circumvent this and land the pass, we just run for a fixed number of > // iterations. > // > // (Bug 765119) > + while (!worklist.empty() && iters < MAX_ITERS) { Why do we still need the MAX_ITERS check?

After finding a pair of subtle bugs in range narrowing, and then a third in the fix for the range narrowing bug, I've decided to just re-implement it, in a slightly saner manner.

Comment on attachment 661734 [details] [diff] [review] rework_narrowing-r0.patch Review of attachment 661734 [details] [diff] [review]: ----------------------------------------------------------------- Makes sense, and this is indeed cleaner than the previous approach. r=me with comments below addressed. ::: js/src/ion/MIR.cpp @@ +12,5 @@ > #include "EdgeCaseAnalysis.h" > #include "jsnum.h" > #include "jsstr.h" > #include "jstypedarrayinlines.h" // For ClampIntForUint8Array > +#include "IonSpewer.h" Micro nit: there's a rule that all js* includes come last, but it looks like you can just remove the include. @@ +463,5 @@ > + if (type() != MIRType_Int32) > + return false; > + > + Range r; > + JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue); Nit: indentation. @@ +466,5 @@ > + Range r; > + JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue); > + bool updated = false; > + for (size_t i = 0; i < numOperands(); i++) { > +#if 0 Nit: remove "#if 0" code. @@ +481,5 @@ > + r.unionWith(&changeCounts_[i]); > + else > + r.unionWith(getOperand(i)->range()); > + } else { > + r.update(getOperand(0)->range()); getOperand(0) -> getOperand(i) ::: js/src/ion/MIR.h @@ +2753,5 @@ > return false; > } > + bool recomputeRange(); > + void initCounts() { > + changeCounts_.resize(inputs_.length()); Nit: resize returns "false" on OOM so we should return the bool to the caller. ::: js/src/ion/RangeAnalysis.cpp @@ +81,5 @@ > + MBasicBlock *curBlock = *i; > + if (!curBlock->isLoopHeader()) > + continue; > + for (MPhiIterator pi(curBlock->phisBegin()); pi != curBlock->phisEnd(); pi++) > + pi->initCounts(); If initCounts becomes fallible, this should probably be moved to the start of RangeAnalysis::analyze so that you can propagate failure. @@ +295,5 @@ > > +void > +Range::unionWith(ChangeCount *other) > +{ > + if (other->lowerCount_ <= 2) { A comment explaining why you use "<= 2" here and else reset lowerCount_ to 0 would be good. We should also assert that |other| is "narrower" than |this| to show that it's safe to ignore |other|. @@ +300,5 @@ > + setLower(Min(lower_, other->oldRange.lower_)); > + lower_infinite_ |= other->oldRange.lower_infinite_; > + } else { > + other->lowerCount_ = 0; > + } Nit: indentation is off (and below). ::: js/src/ion/RangeAnalysis.h @@ +108,5 @@ > // modification. This is to avoid a bunch of useless extra > // copying when chaining together unions when handling Phi > // nodes. > + void unionWith(const Range *other); > + void unionWith(ChangeCount *other); Nit: indentation looks wrong, maybe tabs? @@ +175,5 @@ > setUpper(h); > } > }; > > +struct ChangeCount { Maybe RangeChangeCount to make it clear it belongs to range analysis? This struct also needs a default constructor to initialize lowerCount_ and upperCount_ to 0. @@ +179,5 @@ > +struct ChangeCount { > + Range oldRange; > + unsigned char lowerCount_ : 4; > + unsigned char upperCount_ : 4; > + void updateRange(Range *newRange) { Nit: new line before this line. We should also assert how newRange relates to oldRange if possible. @@ +184,5 @@ > + if (newRange->lower() != oldRange.lower()) > + lowerCount_ = lowerCount_ < 15 ? lowerCount_ + 1 : lowerCount_; > + if (newRange->upper() != oldRange.upper()) > + upperCount_ = upperCount_ < 15 ? upperCount_ + 1 : upperCount_; > + new (&oldRange) Range(*newRange); oldRange = *newRange should work AFAICS

It looks like the username autocomplete on reviews isn't working, I'll make sure to fill in that field later.

review autocomplete is still broken, poking on irc

Comment on attachment 664870 [details] [diff] [review] /home/mrosenberg/patches/noILoopInRangeAnalysis-r1.patch Review of attachment 664870 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/RangeAnalysis.cpp @@ +315,3 @@ > Min( Min(a, b), Min(c, d) ), > Max( Max(a, b), Max(c, d) )); > +#if 0 Remove this #if 0'd block. @@ +340,3 @@ > (int64_t)lhs->lower_ << shift, > (int64_t)lhs->upper_ << shift); > +#if 0 Same @@ +356,3 @@ > (int64_t)lhs->lower_ >> shift, > (int64_t)lhs->upper_ >> shift); > +#if 0 Same ::: js/src/ion/RangeAnalysis.h @@ +100,5 @@ > // 2) upper_infinite == true implies upper_ == JSVAL_INT_MAX > int32 lower_; > bool lower_infinite_; > int32 upper_; > + bool upper_infinite_; nit: indentation @@ +115,5 @@ > setLower(l); > setUpper(h); > } > > + Range(const Range &other) : nit: colon should be on next line, like: Range(const Range &other) : lower_(...

Comment on attachment 664873 [details] [diff] [review] /home/mrosenberg/patches/riceRangeAnalysis-r1.patch Review of attachment 664873 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/MIR.h @@ +5510,5 @@ > ins->addUse(this, index); > } > +static inline bool isOSRLikeValue (MDefinition *def) { > + if (def->isOsrValue()) { > + return true; Nit: no {} @@ +5513,5 @@ > + if (def->isOsrValue()) { > + return true; > + } > + if (def->isUnbox()) { > + if (def->getOperand(0)->isOsrValue()) { Same here. ::: js/src/ion/RangeAnalysis.cpp @@ +282,2 @@ > { > + if (!useNarrowing || other->lower_narrow_count >= 2) { The other patch I reviewed reverts this change right? @@ +310,5 @@ > } > +Range > +Range::and_(const Range *lhs, const Range *rhs) > +{ > + uint64_t lower = 0; CS has a Range::Mask function they call, and then they AND/OR these masks together (in HBitwise::InferRange). Not saying you should do the same here, just pointing it out in case you think it's worthwhile or something. @@ +314,5 @@ > + uint64_t lower = 0; > + // If both numbers can be negative, issues can be had. > + if (lhs->lower_ < 0 && rhs->lower_ < 0) > + lower = INT_MIN; > + uint64_t upper = lhs->upper_; Maybe uint64_t upper = Min(lhs->upper_, rhs->upper_); ::: js/src/ion/RangeAnalysis.h @@ +40,5 @@ > + // :TODO: we should do symbolic range evaluation, where we have > + // information of the form v1 < v2 for arbitrary defs v1 and v2, not > + // just constants of type int32. > + // (Bug 766592) > + Nit: trailing whitespace ::: js/src/ion/arm/CodeGenerator-arm.cpp @@ +467,5 @@ > Assembler::Condition c = Assembler::Overflow; > > //masm.imull(ToOperand(rhs), ToRegister(lhs)); > if (mul->canOverflow()) { > + //fprintf(stderr, "Overflow Possible!\n"); Nit: remove commented out lines in this file.

using monky (emacs-hg interface) has presented some unusual challenges in me knowing what patches are around, and relevant for a bug. I hadn't even noticed that this patch was there. It fixes a bunch of bugs that were uncovered by some runtime range checking code that I added.

Comment on attachment 665700 [details] [diff] [review] /home/mrosenberg/patches/fix_range_bugs-r0.patch Review of attachment 665700 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/RangeAnalysis.cpp @@ -155,5 @@ > MDefinition *greater = NULL; > if (jsop == JSOP_LT) { > smaller = left; > greater = right; > - } else if (JSOP_GT) { Ha. ::: js/src/ion/RangeAnalysis.h @@ +86,5 @@ > lower_infinite_(other.lower_infinite_), > upper_(other.upper_), > upper_infinite_(other.upper_infinite_) > {} > + static Range TruncRange(int64_t l, int64_t h) { since this is a member of Range, I'd just call this Truncate().

What are the performance implications of this bug? Can you post some numbers?

landed on m-i, https://hg.mozilla.org/integration/mozilla-inbound/rev/dbc7e1bc48d0 I thought I had posted the perf results, but I guess that only went into the jsapi irc channel. I'll get those numbers in the morning.

Backed out for make check and win mochitest failures: https://tbpl.mozilla.org/?tree=Mozilla-Inbound&rev=dbc7e1bc48d0 https://hg.mozilla.org/integration/mozilla-inbound/rev/15ec3a643b0b https://hg.mozilla.org/integration/mozilla-inbound/rev/c76b04f5a2b5

Last time I tried to commit this, it bounced since refactoring evidently nuked some of the changes that had been present in earlier versions of this patch. I've just run |make check|, which shows all tests passed.

Comment on attachment 667425 [details] [diff] [review] /home/mrosenberg/patches/ForgottenFixes-r0.patch Review of attachment 667425 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/MIR.h @@ +2588,5 @@ > > bool recomputeRange() { > if (specialization() != MIRType_Int32) > return false; > + Range *lhs = getOperand(0)->range(); Nit: lhs is unused. @@ +2594,5 @@ > + int64_t a = Range::abs64((int64_t)rhs->lower()); > + int64_t b = Range::abs64((int64_t)rhs->upper()); > + if (a ==0 && b == 0) { > + // oh god, oh god, oh god, we should never take something % 0. > + Range r(INT_MIN, INT_MAX); This range should be returned ("return range()->update(r)" like below?), and please remove the first part of the comment. @@ +2596,5 @@ > + if (a ==0 && b == 0) { > + // oh god, oh god, oh god, we should never take something % 0. > + Range r(INT_MIN, INT_MAX); > + } > + int64_t bound = Max(1-a, b-1); Nit: remove extra space between the arguments.

(In reply to Marty Rosenberg [:mjrosenb] from comment #22) > patch. I've just run |make check|, which shows all tests passed. Unfortunately the Windows mochitest failures (mentioned in comment 21) still exist, eg: https://tbpl.mozilla.org/php/getParsedLog.php?id=15775439&tree=Mozilla-Inbound https://tbpl.mozilla.org/?tree=Mozilla-Inbound&rev=1d2a2a4ce97c Backed out: https://hg.mozilla.org/integration/mozilla-inbound/rev/809b60046c5b

This has make check failures still: https://tbpl.mozilla.org/php/getParsedLog.php?id=15840622&tree=Mozilla-Inbound https://tbpl.mozilla.org/?tree=Mozilla-Inbound&rev=4a76e692a4ab I've had to back this out three times; please can this be sent to try on all platforms (and the Try link pasted in-bug) before landing again. If you need help interpreting the Try results, just ping me on IRC :-) Backout: https://hg.mozilla.org/integration/mozilla-inbound/rev/f49e4541bb56

gah, I am not a fan of bugs that only crop up on a particular version of gcc. I've fixed the issue, and am actually trying an try, running everything this time (last time I ran windows only, and ran the linuxes locally)

https://tbpl.mozilla.org/?tree=Try&rev=c3500b6b6781 is the try push (not too sure why it didn't post here)

https://hg.mozilla.org/integration/mozilla-inbound/rev/ddcda23710f4 https://hg.mozilla.org/integration/mozilla-inbound/rev/af9e58e86102 https://hg.mozilla.org/integration/mozilla-inbound/rev/94734724e155 https://hg.mozilla.org/integration/mozilla-inbound/rev/c0b305197227 https://hg.mozilla.org/integration/mozilla-inbound/rev/17c3cdc2f5d9 https://hg.mozilla.org/integration/mozilla-inbound/rev/4eb7625e4426 https://hg.mozilla.org/integration/mozilla-inbound/rev/92018e33385d https://hg.mozilla.org/integration/mozilla-inbound/rev/7a0094bcd186 (landed again. philor and edmorley said the tbpl pushed looked good.)

https://hg.mozilla.org/mozilla-central/rev/ddcda23710f4 https://hg.mozilla.org/mozilla-central/rev/af9e58e86102 https://hg.mozilla.org/mozilla-central/rev/94734724e155 https://hg.mozilla.org/mozilla-central/rev/c0b305197227 https://hg.mozilla.org/mozilla-central/rev/17c3cdc2f5d9 https://hg.mozilla.org/mozilla-central/rev/4eb7625e4426 https://hg.mozilla.org/mozilla-central/rev/92018e33385d https://hg.mozilla.org/mozilla-central/rev/7a0094bcd186

I know this bug landed, but I expected to see an impact on AWFY for 64-bit Kraken. Is AWFY acting strange again?