Octane-mandreel has this function: function uint(value) { if (value >= 0) return value; return 4294967296 + value; } We inline this function many times, but in many cases we should be able to eliminate the |value >= 0| comparison, for instance here: r4 = heapU16[(r2+r4)>>1]; r6 = heapU16[(r5+-4)>>1]; if (!(uint(r4) >=uint(r6))) r4 and r6 should always be >= 0 because we read them out of an Uint16Array. V8 is doing this already.

(Ideally, if we combine this with UCE, we should be able to turn: if (!(uint(r4) >= uint(r6))) into an integer comparison... That's more complicated than just eliminating the |value >= 0| check though, and v8 is also still doing a double comparison here, but maybe we can do that as a follow-up?)

On this micro benchmark I obtain the following results: before: runtime = 601.877 ms runtime = 597.155 ms runtime = 599.765 ms after: runtime = 282.058 ms runtime = 274.585 ms runtime = 283.378 ms With the upcoming list of patches.

On my computer, these 3 patches are improving Mandreel & MandreelLatency respectively and approximately from -> to: 14400 -> 14800 && 20100 -> 20500 I will check sunspider and kraken over the night.

Comment on attachment 8340061 [details] [diff] [review] Improve computed range of MPhi by populating the earlyAbort flags. Review of attachment 8340061 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/jit/RangeAnalysis.cpp @@ +1933,5 @@ > MBasicBlock *block = *iter; > > + if (block->earlyAbort()) > + continue; > + This patch and the others are treating the earlyAbort() flag as if it means "unreachable". The name "earlyAbort" suggests that the block might be entered though it won't exit, but I don't think that subtlety is required or even desirable. Please rename earlyAbort() and friends to unreachable() etc. @@ +1974,5 @@ > + if (block->earlyAbort()) { > + size_t numDom = block->numImmediatelyDominatedBlocks(); > + for (size_t d = 0; d < numDom; d++) > + block->getImmediatelyDominatedBlock(d)->setEarlyAbort(); > + } It seems like you could do this immediately in MBasicBlock's setUnreachable() method (renamed from setEarlyAbort() :-)), and it'd make the information available to more clients earlier that way. And going a step further, it seems like setUnreachable() could also drop its successors, and then call setUnreachable() on any former successors which no longer have any predecessors (assuming entry blocks can't be successors). And since loop headers and backedges are labeled, it could even call setUnreachable() on loop headers when their last non-backedge predecessor is removed. If setUnreachable() does these things, would it still be necessary to have a second run of the discrete UnreachableCodeElimination pass, as the other pass does?

Comment on attachment 8340063 [details] [diff] [review] Coerce value to Int32 based on their Ranges. Review of attachment 8340063 [details] [diff] [review]: ----------------------------------------------------------------- What is the difference between truncating and coercing? It seems like there is a lot of similarity between these two things, but I don't understand the differences. For example, would it not be correct and sufficient for a Compare with Compare_Double with operands that both have int32 ranges to just truncate() both operands, and convert to Compare_Int32? That seems like the main purpose coercing is serving here. If there's more going on here, then please add some comments.

Comment on attachment 8340060 [details] [diff] [review] Annotate and modify conditions leading to dead branches. Review of attachment 8340060 [details] [diff] [review]: ----------------------------------------------------------------- FWIW, I investigated the approach of making setUnreachable super smart, and it's more complicated than I initially guessed. I think something like that is doable, but for now this patch is fine.

Comment on attachment 8340061 [details] [diff] [review] Improve computed range of MPhi by populating the earlyAbort flags. Review of attachment 8340061 [details] [diff] [review]: ----------------------------------------------------------------- As with the earlier patch, this patch looks fine for now.

Comment on attachment 8340061 [details] [diff] [review] Improve computed range of MPhi by populating the earlyAbort flags. Review of attachment 8340061 [details] [diff] [review]: ----------------------------------------------------------------- As with the earlier patch, this patch looks fine for now.

Comment on attachment 8340063 [details] [diff] [review] Coerce value to Int32 based on their Ranges. Review of attachment 8340063 [details] [diff] [review]: ----------------------------------------------------------------- It's not clear to me what the distinctin is between coercing and truncating. If there is a clear distinction, a comment describing it would be quite helpful.

(In reply to Dan Gohman [:sunfish] from comment #8) > Comment on attachment 8340063 [details] [diff] [review] > Coerce value to Int32 based on their Ranges. > > Review of attachment 8340063 [details] [diff] [review]: > ----------------------------------------------------------------- > > What is the difference between truncating and coercing? It seems like there > is a lot of similarity between these two things, but I don't understand the > differences. Indeed they are similar in the way they are applied. The idea behind truncating is that any number which is going to be truncated can be truncated ahead as long as a double has enough bits to represent it. The idea behind coercing is that any number which is an Int32 disguise as a Double can be coerced to an int32. Maybe coerced is not the right English term for that and I should use transtyped or projected (as mathematical projections). When we convert a comparisons of double into a comparison of int, because the ranges of both inputs are ints, I do not think we want to eagerly truncate the inputs. I might be wrong, but it sounds safer to duplicate it and restrict the set of changes.

(In reply to Nicolas B. Pierron [:nbp] from comment #13) > (In reply to Dan Gohman [:sunfish] from comment #8) > > Comment on attachment 8340063 [details] [diff] [review] > > Coerce value to Int32 based on their Ranges. > > > > Review of attachment 8340063 [details] [diff] [review]: > > ----------------------------------------------------------------- > > > > What is the difference between truncating and coercing? It seems like there > > is a lot of similarity between these two things, but I don't understand the > > differences. > > Indeed they are similar in the way they are applied. > > The idea behind truncating is that any number which is going to be truncated > can be truncated ahead as long as a double has enough bits to represent it. > > The idea behind coercing is that any number which is an Int32 disguise as a > Double can be coerced to an int32. Maybe coerced is not the right English > term for that and I should use transtyped or projected (as mathematical > projections). > > When we convert a comparisons of double into a comparison of int, because > the ranges of both inputs are ints, I do not think we want to eagerly > truncate the inputs. I might be wrong, but it sounds safer to duplicate it > and restrict the set of changes. Ok, so truncation and coercing have different preconditions for safety. Coercion is safe if a value naturally has an int32 range and there are no rounding errors. Truncation is safe if all users will truncate the value to int32 and there are no rounding errors. Do I have this right? If so, then coercion's precondition can be thought of as a subset of truncation's precondition. The users may not all truncate, but it doesn't matter because the value is already in the int32 range. So it seems like the AllUsesTruncate(*iter) check in Range::truncate() could be safely more aggressive by doing AllUsesTruncate(*iter) || r->isInt32(). Is there a reason why this wouldn't be safe? If so, I think it's a better approach than to have two subtly different copies of this transformation.

(In reply to Dan Gohman [:sunfish] from comment #14) > Ok, so truncation and coercing have different preconditions for safety. > Coercion is safe if a value naturally has an int32 range and there are no > rounding errors. Truncation is safe if all users will truncate the value to > int32 and there are no rounding errors. Do I have this right? This sounds right. Coercion: isInt32 (= hasInt32Bounds && !canHaveFractionalPart) Flow into instructions which are accepting Int32. Truncation: !canHaveRoundingErrors (= max_exponent_ < MaxTruncatableExponent && !canHaveFractionalPart) Flow into instructions which are truncating to Int32. > If so, then coercion's precondition can be thought of as a subset of > truncation's precondition. The users may not all truncate, but it doesn't > matter because the value is already in the int32 range. So it seems like the > AllUsesTruncate(*iter) check in Range::truncate() could be safely more > aggressive by doing AllUsesTruncate(*iter) || r->isInt32(). Is there a > reason why this wouldn't be safe? I agree that isInt32 is a subset of !canHaveRoundingErrors. But I am not convinced that "accepting Int32" is a subset of "truncating to Int32". I agree that "accepting Int32, with Int32 inputs (in the case of compare)" is a subset of "truncating to Int32". Then the question where I still have some doubt, is what does it mean to obtain an Int32 from an operation which is manipulating input ranges which are not int32? Would it be safe to populate with a truncation? Which basically ask, is it safe to truncate any instruction just because it is returning an Int32 range?

Comment on attachment 8340063 [details] [diff] [review] Coerce value to Int32 based on their Ranges. Review of attachment 8340063 [details] [diff] [review]: ----------------------------------------------------------------- Here is a more elaborate review. The trickiest part of doing this review was hopping back and forth between the coercion code and the truncation code to examine the differences between the two. A lot of the code is the same, with minor changes. Unless you anticipate this code continuing to diverge, I think it would be easier to read and maintain if the coercion code were merged back into the truncation code. There are a few cases where coercion is currently more capable than truncation, but I believe truncation could be taught to do the same things that coercion is doing. More details below. ::: js/src/jit/RangeAnalysis.cpp @@ +2280,5 @@ > + > +bool > +MConstant::coerceToInt32() > +{ > + return false; What is intended here? @@ +2332,5 @@ > + > +bool > +MToDouble::isOperandCoercedToInt32(size_t index) const > +{ > + return range() && range()->isInt32(); MToDouble::isOperandTruncated checks for type() of int32. Could it also check for range()->isInt32()? @@ +2347,5 @@ > +{ > + if (isOperandTruncated(index)) > + return true; > + > + return specialization() == MIRType_Int32; Would this line be valid for MMul::isOperandTruncated too? @@ +2365,1 @@ > if (candidate->isUseRemoved()) This code is removed in AllUsesCoerce. Could AllUsesTruncate skip this check too in the case where the candidate also satisfies the coercion criteria? In other words, could you replace this if with this: if (candidate->isUseRemoved() && !candidate->range()->isInt32()) ? @@ +2375,5 @@ > } > > +static bool > +CanTruncate(MInstruction *candidate) > +{ CanCoerceToInt32 has a special check for an MCompare at this point. I believe CanTruncate could do the same thing, if MCompare::coerceToInt32 and friends were converted to MCompare::truncate etc. @@ +2470,5 @@ > +static void > +RemoveCoerceOnOutput(MInstruction *truncated) > +{ > + if (truncated->isCompare()) > + return; As with CanTruncate above, RemoveTruncatesOnOutput could also do this Compare check. @@ +2498,5 @@ > + continue; > + > + JS_ASSERT(Range(input).isInt32()); > + if (input->isToDouble()) { > + truncated->replaceOperand(i, input->getOperand(0)); It looks like MToDouble can have inputs other than int32. Even though you've checked the range, should there also be a check for an actual int32 type here? @@ +2500,5 @@ > + JS_ASSERT(Range(input).isInt32()); > + if (input->isToDouble()) { > + truncated->replaceOperand(i, input->getOperand(0)); > + } else { > + MToInt32 *op = MToInt32::New(alloc, input); The truncate version of this code uses MTruncateToInt32. It looks like the difference between MTruncateToInt32 and MInt32 is that MToInt32 has extra code to check for an inexact conversion. Since coercion is only performed on values which are known to be int32 values, it looks like MTruncateToInt32 would be a better choice. As a bonus, that's what AdjustTruncatedInputs is already using :).

> Which basically ask, is it safe to truncate any instruction just because it is > returning an Int32 range? I think the answer is yes. The key here is that we're considering the *pre-bailout* range. Truncating an instruction disables its bailout checks, but if the value before the bailout checks is already int32, it doesn't need them. Perhaps I can demonstrate this with code. Attached is a verion of your patch with the coercion and truncate code merged back together. I dropped the "specialization() == MIRType_Int32" from MMul::isOperandCoercedToInt32, because an untruncated integer multiply can overflow, depending on its operands. I also dropped the "range()->isInt32()" in MToDouble::isOperandCoercedToInt32, because MToDouble's int32 range may be a result of its operand using bailout checks, and calling the operand truncated may cause it to drop its bailout checks. MToDouble's operand is only truncated if something is truncating the MToDouble. The merge of AllUsesCoerce into AllUsesTruncate is interesting; see the comments in the code. This version of the patch still achieves the same optimization on the micro-benchmark. It also passes jit-tests --tbpl.

Comment on attachment 8344227 [details] [diff] [review] combined.patch Adding r? since this patch is ready for it.

Green try run with the UCE, Phi range, and combined.patch patches: https://tbpl.mozilla.org/?tree=Try&rev=baa3bec3717e

(In reply to Dan Gohman [:sunfish] from comment #16) > ::: js/src/jit/RangeAnalysis.cpp > @@ +2280,5 @@ > > + > > +bool > > +MConstant::coerceToInt32() > > +{ > > + return false; > > What is intended here? In the sense that coerceToInt32 was not supposed to modify the content of the inputs, this means that the constant was supposed to be already an Int32. > @@ +2332,5 @@ > > + > > +bool > > +MToDouble::isOperandCoercedToInt32(size_t index) const > > +{ > > + return range() && range()->isInt32(); > > MToDouble::isOperandTruncated checks for type() of int32. Could it also > check for range()->isInt32()? Yes, we could also check the ranges. > @@ +2347,5 @@ > > +{ > > + if (isOperandTruncated(index)) > > + return true; > > + > > + return specialization() == MIRType_Int32; > > Would this line be valid for MMul::isOperandTruncated too? This line is saying that we already know that both inputs are int32 and that we are doing an int32 operation. If it is safe to eagerly truncate every uses only because we can only consume non-truncated int32, then yes. > @@ +2365,1 @@ > > if (candidate->isUseRemoved()) > > This code is removed in AllUsesCoerce. Could AllUsesTruncate skip this check > too in the case where the candidate also satisfies the coercion criteria? In > other words, could you replace this if with this: > > if (candidate->isUseRemoved() && !candidate->range()->isInt32()) > > ? See comment 21. > @@ +2375,5 @@ > > } > > > > +static bool > > +CanTruncate(MInstruction *candidate) > > +{ > > CanCoerceToInt32 has a special check for an MCompare at this point. I > believe CanTruncate could do the same thing, if MCompare::coerceToInt32 and > friends were converted to MCompare::truncate etc. > > @@ +2470,5 @@ > > +static void > > +RemoveCoerceOnOutput(MInstruction *truncated) > > +{ > > + if (truncated->isCompare()) > > + return; > > As with CanTruncate above, RemoveTruncatesOnOutput could also do this > Compare check. Indeed, the reason being that MCompare does not produce an Int32, and its output is not truncated, so this is a bit of a hack to make it fit in this traversal. > @@ +2498,5 @@ > > + continue; > > + > > + JS_ASSERT(Range(input).isInt32()); > > + if (input->isToDouble()) { > > + truncated->replaceOperand(i, input->getOperand(0)); > > It looks like MToDouble can have inputs other than int32. Even though you've > checked the range, should there also be a check for an actual int32 type > here? If so, then yes. > @@ +2500,5 @@ > > + JS_ASSERT(Range(input).isInt32()); > > + if (input->isToDouble()) { > > + truncated->replaceOperand(i, input->getOperand(0)); > > + } else { > > + MToInt32 *op = MToInt32::New(alloc, input); > > The truncate version of this code uses MTruncateToInt32. It looks like the > difference between MTruncateToInt32 and MInt32 is that MToInt32 has extra > code to check for an inexact conversion. Since coercion is only performed on > values which are known to be int32 values, it looks like MTruncateToInt32 > would be a better choice. As a bonus, that's what AdjustTruncatedInputs is > already using :). Ok :)

Comment on attachment 8344227 [details] [diff] [review] combined.patch Review of attachment 8344227 [details] [diff] [review]: ----------------------------------------------------------------- You might want to change the author or the reviewer of this patch, to get a bit of credit too ;) ::: js/src/jit/RangeAnalysis.cpp @@ +2363,5 @@ > AllUsesTruncate(MInstruction *candidate) > { > + // If the value naturally produces an int32 value that needs no conversion, > + // we don't have to worry about resume points seeing fractional values. > + bool needsConversion = !candidate->range() || !candidate->range()->isInt32(); nit: we don't have to worry about mutated content of resume points in the presence of removed branches. The reason is that if we remove a branch, we might bail with a modified (truncated) input. If the content of the input is unchanged, then there is no need to worry about removed resume points. But if the content of the resume point is changed, then we might bail with an eager truncation which did not consider the missing path. Note that it is safe to mutate the value (truncate) if we know all uses or if we can restore the original value (see Bug 878503). @@ +2369,4 @@ > for (MUseIterator use(candidate->usesBegin()); use != candidate->usesEnd(); use++) { > if (!use->consumer()->isDefinition()) { > + // We can only skip testing resume points, if all original uses are > + // still present, or if the value needs to conversion. Otherwise a typo: … skip testing …, if all original uses are still present, or if the value *does not* need ** conversion. @@ +2443,5 @@ > continue; > > + if (input->isToDouble()) { > + JS_ASSERT(input->range()->isInt32()); > + truncated->replaceOperand(i, input->getOperand(0)); As you mentionned MToDouble can accept other kind of instructions, we should ensure that its input as at least an Int32 type.

https://hg.mozilla.org/integration/mozilla-inbound/rev/96a2c0c25cab https://hg.mozilla.org/integration/mozilla-inbound/rev/fb26d5645076 Try: https://tbpl.mozilla.org/?tree=Try&showall=1&rev=f4560f3fe94f

(In reply to Nicolas B. Pierron [:nbp] from comment #21) > Comment on attachment 8344227 [details] [diff] [review] > combined.patch > > Review of attachment 8344227 [details] [diff] [review]: > ----------------------------------------------------------------- > > You might want to change the author or the reviewer of this patch, to get a > bit of credit too ;) Ok, though you deserve credit too; it's based on your code :). > ::: js/src/jit/RangeAnalysis.cpp > @@ +2363,5 @@ > > AllUsesTruncate(MInstruction *candidate) > > { > > + // If the value naturally produces an int32 value that needs no conversion, > > + // we don't have to worry about resume points seeing fractional values. > > + bool needsConversion = !candidate->range() || !candidate->range()->isInt32(); > > nit: we don't have to worry about mutated content of resume points in the > presence of removed branches. > > The reason is that if we remove a branch, we might bail with a modified > (truncated) input. If the content of the input is unchanged, then there is > no need to worry about removed resume points. But if the content of the > resume point is changed, then we might bail with an eager truncation which > did not consider the missing path. Note that it is safe to mutate the value > (truncate) if we know all uses or if we can restore the original value (see > Bug 878503). Ok, I reworded the comment to clarify this. If the candidate's pre-bailout range is int32, then truncation doesn't change the value, so we don't need to worry about anyone seeing the wrong value. > @@ +2369,4 @@ > > for (MUseIterator use(candidate->usesBegin()); use != candidate->usesEnd(); use++) { > > if (!use->consumer()->isDefinition()) { > > + // We can only skip testing resume points, if all original uses are > > + // still present, or if the value needs to conversion. Otherwise a > > typo: … skip testing …, if all original uses are still present, or if the > value *does not* need ** conversion. Fixed. > @@ +2443,5 @@ > > continue; > > > > + if (input->isToDouble()) { > > + JS_ASSERT(input->range()->isInt32()); > > + truncated->replaceOperand(i, input->getOperand(0)); > > As you mentionned MToDouble can accept other kind of instructions, we should > ensure that its input as at least an Int32 type. Done. https://hg.mozilla.org/integration/mozilla-inbound/rev/9658dbcf4cd7

https://hg.mozilla.org/mozilla-central/rev/96a2c0c25cab https://hg.mozilla.org/mozilla-central/rev/fb26d5645076 https://hg.mozilla.org/mozilla-central/rev/9658dbcf4cd7