Reland r39293.

Reland r39293.

Switch to a fix-point based range analysis to improve its precision.

Dominator based algorithm was very imprecise for loop phis.

Use widening to ensure fast convergence and narrowing to improve precision.

Fixed compared to r39293:

Type propagation is more sophisticated now compared to the time
when range analysis was originally implemented and is able to derive Smi-ness
from more than just CheckSmi instruction (e.g. GuardFieldClass). This creates
situations when use's reaching type is Smi but definition itself is not a Smi
and thus will never have range assigned to it.

It is incorrect to treat ranges of such uses as unknown (_|_), because unknown
means "not yet computed". Instead we must use the widest possible approximation:
full smi range.

InferRange methods were rewritten to use a newly introduced GetRange helper
instead of accessing value()->definition()->range() directly.

As a side-effect we no longer need to insert artificial constraints after CheckSmi instructions.

R=fschneider@google.com

Committed: https://code.google.com/p/dart/source/detail?r=39327

[Vyacheslav Egorov (Google), 2014-08-15 19:13:52]

PTAL

[Florian Schneider, 2014-08-18 10:46:51]

lgtm

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

https://codereview.chromium.org/477193002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.cc:331: (defn->Type()->ToCid() != kSmiCid))
{
Add mint cid here.

[Vyacheslav Egorov (Google), 2014-08-18 10:58:19]

Thanks! Landing.

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

https://codereview.chromium.org/477193002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.cc:331: (defn->Type()->ToCid() != kSmiCid))
{
On 2014/08/18 10:46:51, Florian Schneider wrote:
> Add mint cid here.

All Mint values are defined by UnboxInteger instruction which handles this
internally.

The reason why we have to handle kSmiCid here is because we don't have a
separate Smi representation (and hence an arbitrary instruction returning tag
can be seen here)

[Vyacheslav Egorov (Google), 2014-08-18 11:06:34]

Committed patchset #1 manually as 39327 (presubmit successful).