Use same range info when emitting code and computing if instruction can deopt.

Use same range info when emitting code and computing if instruction can deopt.

For BinarySmiOpInstr and ShiftMintOpInstr we use range information to both
decide if instruction can deopt and decide which checks should be emitted
when emitting native code for this instruction.

However because range information is attached to the definition and not
uses it often gets out of sync as we mutate the graph. For example we might
first make a decision that an instruction can't deoptimize based on more
precise range information but then use less precise information in the
backend for deciding which parts of the instruction to emit (because
redifinition or a phi-instruction was removed from the graph). This mismatch
can lead to a crash if less precise information tells backend that one of the
inputs need to be checked - because there is no deoptimization label to jump
to.

This CL is addressing this problem by ensuring that range information is
cached at the use and both ComputeCanDeoptimize() and backend use the same
range information.

Additionally this CL kills overly generic MergedMath instruction and replaces it
with TruncDivModInstr.

BUG=https://github.com/dart-lang/sdk/issues/29620
R=rmacnak@google.com

Committed: https://github.com/dart-lang/sdk/commit/0eb44ec68f87af9a5da233406d8ebcfd42c5d1a5

[Vyacheslav Egorov (Google), 2017-05-18 16:59:13]

Hi Ryan! Could you take a look? Cheers

PS. 

Alternative (simpler) fix would be to change places like:

if (!RangeUtils::IsPositive(right_range)) {
  __ CompareRegisters(right, ZR);
  __ b(deopt, MI);
}

to

if (!RangeUtils::IsPositive(right_range) && (deopt != NULL)) {
  __ CompareRegisters(right, ZR);
  __ b(deopt, MI);
} 

This however feel awful - because our EmitNativeCode can get out of sync with
ComputeCanDeoptimize and we will not know. So I decided against it. 

I also decided against always caching range information at all uses.

In reality the problem here arises from the fact that some of our instructions
are way too smart - they have a lot of decision making inside - and that
decision making logic gets duplicated and triplicated. Maybe we should instead
lower those instructions into simpler instructions, e.g. 

z <- BinarySmiOp(%, x, y) 

could become

y' <- EnsureRange(y, [0, ...])
z <- BinarySmiOp(%, x, y')

That would make certain things simpler.

[Vyacheslav Egorov (Google), 2017-05-18 16:59:31]

vegorov@google.com changed reviewers:
+ rmacnak@google.com

[Vyacheslav Egorov (Google), 2017-05-18 16:59:31]

Hi Ryan! Could you take a look? Cheers

PS. 

Alternative (simpler) fix would be to change places like:

if (!RangeUtils::IsPositive(right_range)) {
  __ CompareRegisters(right, ZR);
  __ b(deopt, MI);
}

to

if (!RangeUtils::IsPositive(right_range) && (deopt != NULL)) {
  __ CompareRegisters(right, ZR);
  __ b(deopt, MI);
} 

This however feel awful - because our EmitNativeCode can get out of sync with
ComputeCanDeoptimize and we will not know. So I decided against it. 

I also decided against always caching range information at all uses.

In reality the problem here arises from the fact that some of our instructions
are way too smart - they have a lot of decision making inside - and that
decision making logic gets duplicated and triplicated. Maybe we should instead
lower those instructions into simpler instructions, e.g. 

z <- BinarySmiOp(%, x, y) 

could become

y' <- EnsureRange(y, [0, ...])
z <- BinarySmiOp(%, x, y')

That would make certain things simpler.

[rmacnak, 2017-05-18 20:02:45]

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:2296: other_binop->ReplaceUsesWith(div_mod);
Aren't these uses already replaced from the ExtactOutput above?

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_range...
File runtime/vm/flow_graph_range_analysis.cc (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_range...
runtime/vm/flow_graph_range_analysis.cc:2896: const Range* range,
I see crashes in some tests because range may be null via
ShiftMintOpInstr::InferRange. Presumably this should start with

if (range == NULL) {
  *slot = NULL;
  return;
}

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_type_...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_type_...
runtime/vm/flow_graph_type_propagator.cc:1522: return CompileType::Dynamic();
Smi?, though I don't think it affects anything since the ExtractOutput was
already told it was Smi.

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language.h:7591: // the emitted pattern. It is not used
for decising whether instruction
deciding

[rmacnak, 2017-05-18 20:04:48]

On 2017/05/18 16:59:31, Vyacheslav Egorov (Google) wrote:
> Hi Ryan! Could you take a look? Cheers
> 
> PS. 
> 
> Alternative (simpler) fix would be to change places like:
> 
> if (!RangeUtils::IsPositive(right_range)) {
>   __ CompareRegisters(right, ZR);
>   __ b(deopt, MI);
> }
> 
> to
> 
> if (!RangeUtils::IsPositive(right_range) && (deopt != NULL)) {
>   __ CompareRegisters(right, ZR);
>   __ b(deopt, MI);
> } 
> 
> This however feel awful - because our EmitNativeCode can get out of sync with
> ComputeCanDeoptimize and we will not know. So I decided against it. 

It also seems a bit confusing to me for instructions that can deopt for multiple
reasons to not remember separately when those cases are proven to not happen.

> 
> I also decided against always caching range information at all uses.

I'm not familiar enough with all the places using range information to have an
opinion on this option :)

> 
> In reality the problem here arises from the fact that some of our instructions
> are way too smart - they have a lot of decision making inside - and that
> decision making logic gets duplicated and triplicated. Maybe we should instead
> lower those instructions into simpler instructions, e.g. 
> 
> z <- BinarySmiOp(%, x, y) 
> 
> could become
> 
> y' <- EnsureRange(y, [0, ...])
> z <- BinarySmiOp(%, x, y')
> 
> That would make certain things simpler.

I like this idea.

[Vyacheslav Egorov (Google), 2017-05-19 08:07:08]

Please take another look.

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:2296: other_binop->ReplaceUsesWith(div_mod);
On 2017/05/18 20:02:45, rmacnak wrote:
> Aren't these uses already replaced from the ExtactOutput above?

This function is a tad funky. ExtractOutput makes ExtractNthOutputInstr which
uses original instruction (see line 2313). Then these ReplaceWith and
ReplaceUsesWith wire up ExtractNthOutputInstr to use TruncDivModInstr... 

We should probably clean this up - but in a separate CL.

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_range...
File runtime/vm/flow_graph_range_analysis.cc (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_range...
runtime/vm/flow_graph_range_analysis.cc:2896: const Range* range,
On 2017/05/18 20:02:45, rmacnak wrote:
> I see crashes in some tests because range may be null via
> ShiftMintOpInstr::InferRange. Presumably this should start with
> 
> if (range == NULL) {
>   *slot = NULL;
>   return;
> }

Ooops. Should have rerun tests after refactoring.

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_type_...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/flow_graph_type_...
runtime/vm/flow_graph_type_propagator.cc:1522: return CompileType::Dynamic();
On 2017/05/18 20:02:45, rmacnak wrote:
> Smi?, though I don't think it affects anything since the ExtractOutput was
> already told it was Smi.

TruncDivModInstr returns a tuple - a pair of Smi-s - so we can't declare it
returns a smi :) Strictly speaking it returns something that can't be considered
singular Dart value. Hence we have no type here.

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/2891113002/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language.h:7591: // the emitted pattern. It is not used
for decising whether instruction
On 2017/05/18 20:02:45, rmacnak wrote:
> deciding

Done.

[rmacnak, 2017-05-19 16:18:17]

LGTM

[Vyacheslav Egorov (Google), 2017-05-21 17:01:53]

Description was changed from

==========
Use same range info when emitting code and computing if instruction can deopt.

For BinarySmiOpInstr and ShiftMintOpInstr we use range information to both
decide if instruction can deopt and decide which checks should be emitted
when emitting native code for this instruction.

However because range information is attached to the definition and not
uses it often gets out of sync as we mutate the graph. For example we might
first make a decision that an instruction can't deoptimize based on more
precise range information but then use less precise information in the
backend for deciding which parts of the instruction to emit (because
redifinition or a phi-instruction was removed from the graph). This mismatch
can lead to a crash if less precise information tells backend that one of the
inputs need to be checked - because there is no deoptimization label to jump
to.

This CL is addressing this problem by ensuring that range information is
cached at the use and both ComputeCanDeoptimize() and backend use the same
range information.

Additionally this CL kills overly generic MergedMath instruction and replaces it
with TruncDivModInstr.

BUG=https://github.com/dart-lang/sdk/issues/29620
==========

to

==========
Use same range info when emitting code and computing if instruction can deopt.

For BinarySmiOpInstr and ShiftMintOpInstr we use range information to both
decide if instruction can deopt and decide which checks should be emitted
when emitting native code for this instruction.

However because range information is attached to the definition and not
uses it often gets out of sync as we mutate the graph. For example we might
first make a decision that an instruction can't deoptimize based on more
precise range information but then use less precise information in the
backend for deciding which parts of the instruction to emit (because
redifinition or a phi-instruction was removed from the graph). This mismatch
can lead to a crash if less precise information tells backend that one of the
inputs need to be checked - because there is no deoptimization label to jump
to.

This CL is addressing this problem by ensuring that range information is
cached at the use and both ComputeCanDeoptimize() and backend use the same
range information.

Additionally this CL kills overly generic MergedMath instruction and replaces it
with TruncDivModInstr.

BUG=https://github.com/dart-lang/sdk/issues/29620
R=rmacnak@google.com

Committed:
https://github.com/dart-lang/sdk/commit/0eb44ec68f87af9a5da233406d8ebcfd42c5d1a5
==========

[Vyacheslav Egorov (Google), 2017-05-21 17:01:55]

Committed patchset #3 (id:40001) manually as
0eb44ec68f87af9a5da233406d8ebcfd42c5d1a5 (presubmit successful).