Use integer division in a certain case.

Use integer division in a certain case.

This optimization triggers when:
- Both operands are integers
- The result will be truncated to an integer
- The dividend is non-negative
- The divisor is positive

It is done during range analysis because it needs range information for the preconditions and because, if the optimization triggers, the range of the output can also be computed. This optimization also removes the deopt on non-zero remainder since the result is always truncated.

BUG=v8:2258
TEST=test/mjsunit/fast-div-int.js

[Vyacheslav Egorov (Google), 2012-07-30 12:01:44]

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1151: if (change->value()->IsDiv() &&
I am a little bit uncomfortable that we apply this optimization to any d to i
change, even those that are not truncating. 

Changes can be inserted optimistically and they deopt when they see a value not
representable as integer. 

So it seems suspicious that such optimistic change can be removed by an opt.

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1159: if
(div->UseCountIgnoringInputsRequiringNone() == 1) {
I am not sure that your approach to simulates is correct.

First of all simulate does need a resulting value e.g. it can be stored into a
local, so after deopt local will see integer not double.

Secondly, imagine that we have a simulate followed by a map check that ensures
that we actually store into int32 array (and thus we convert to int32) -> if map
check fails simulate we will deopt into an incorrect state with a value
truncated to int32. (Pseudo)HIR to illustrate:

d4 = Div d2, d3 
Simulate push d4
i5 = Change d to i d4
CheckMaps t0
StoreFastKeyedExternalElement t0[i1] = i5

[Evan Wallace, 2012-07-30 16:43:13]

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1151: if (change->value()->IsDiv() &&
These aren't the only conditions that trigger this optimization. It must also be
the case that both operands are integers, the dividend is non-negative, and the
divisor is positive. This ensures that the result of the division can always be
representable as an integer and that the deopt will never be hit. For example,
with the following HIR:

d3 = Div i1, i2
i4 = Change d to i d3

The preconditions are:
- i1 is an int32 in range [a, b] where 0 <= a <= b <= kMaxInt
- i2 is an int32 in range [c, d] where 1 <= c <= d <= kMaxInt

Thus the range of the result is [a / d, b / c] which can always be safely
truncated to int32 range since:
- 0 <= a / d <= a
- 0 <= b / c <= b
- a / d <= b / c

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1159: if
(div->UseCountIgnoringInputsRequiringNone() == 1) {
Thanks for pointing this out! I guess I don't understand HSimulate then. I
needed it for the case in my example of updating an element in a typed array
"x[0] = 0xFF / (x[0] + 1)" but that can be done instead by using "x[0] = 0 |
0xFF / (x[0] + 1)", which doesn't generate a HSimulate pointing to the HDiv.
I'll change this to require an absolute use count of 1 instead.

[Vyacheslav Egorov (Google), 2012-07-30 16:59:26]

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1151: if (change->value()->IsDiv() &&
On 2012/07/30 16:43:13, Evan Wallace wrote:
> These aren't the only conditions that trigger this optimization. It must also
be
> the case that both operands are integers, the dividend is non-negative, and
the
> divisor is positive. This ensures that the result of the division can always
be
> representable as an integer and that the deopt will never be hit. For example,
> with the following HIR:
> 
> d3 = Div i1, i2
> i4 = Change d to i d3
> 
> The preconditions are:
> - i1 is an int32 in range [a, b] where 0 <= a <= b <= kMaxInt
> - i2 is an int32 in range [c, d] where 1 <= c <= d <= kMaxInt
> 
> Thus the range of the result is [a / d, b / c] which can always be safely
> truncated to int32 range since:
> - 0 <= a / d <= a
> - 0 <= b / c <= b
> - a / d <= b / c

I don't dispute that it can be truncated to int32. 
My concern is that it can necessarily be represented as int32 e.g. 1/2 can be
truncated to int32 but it is not representable in int32.

Normal Change d -> i is not truncating, it will deopt on non-integer values
(which corresponds to non-zero remainder).

What do you think about limiting this optimization to truncating Change
instructions?

I suspect we can mark store into int32/int16/int8 array (and associated Change)
as truncating.

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1159: if
(div->UseCountIgnoringInputsRequiringNone() == 1) {
On 2012/07/30 16:43:13, Evan Wallace wrote:
> Thanks for pointing this out! I guess I don't understand HSimulate then. I
> needed it for the case in my example of updating an element in a typed array
> "x[0] = 0xFF / (x[0] + 1)" but that can be done instead by using "x[0] = 0 |
> 0xFF / (x[0] + 1)", which doesn't generate a HSimulate pointing to the HDiv.
> I'll change this to require an absolute use count of 1 instead.

Simulate is a pseudo-instruction that "simulates" changes that happen with the
state of unoptimized code corresponding to a particular position in optimized
code. It is needed to compute how stack frames would look like for unoptimized
code when we deopt. One can say that simulates delta-encode deoptimization
environments as each simulate describes what observable changes happened to the
state since the previous simulate: what was stored into local variables, what
was pushed to expression stack or how many values were poped from it.  

Uses at simulate describe what unoptimized code will see if deopt happens
between this simulate and the next one.

[Evan Wallace, 2012-07-30 19:35:43]

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/10825071/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.cc:1151: if (change->value()->IsDiv() &&
I did not realize normal double to integer representation changes are not
truncating. I will add a check for that flag on "change".

From what I can tell, if the optimization is only applied when the division has
a use count of 1 then marking storing into a typed array as truncating won't
have any effect since "x[0] = 0xFF / (x[0] + 1)" will always generate a simulate
that pushes the division.

What conditions would be necessary to apply this substitution in that case?
Would it be valid to apply this substitution if there are one or more simulate
instructions for which the division is a use but they occur after the change
instruction (instead of before as in your example below)?