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

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.

BUG=
R=fschneider@google.com

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

[Vyacheslav Egorov (Google), 2014-08-15 00:16:52]

PTAL

[Florian Schneider, 2014-08-15 11:58:02]

Lgtm.

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

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.cc:173: Range*
RangeAnalysis::ConstraintRange(Token::Kind op, Definition* boundary) {
Maybe this should be renamed to ConstraintSmiRange since it handles smi
operations only.

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.cc:520:
CollectDefinitionsRecursive(block->dominated_blocks()[i], set);
Why recursive and dominator-tree order? Wouldn't reverse post-order be better
for reaching a fixed point faster because it all blocks are visited before their
successors?

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.cc:530: for (intptr_t i = 0; i <
definitions_.length(); i++) {
Consider using a worklist-based iteration instead, if iterating over all
definitions turns out to be a performance issue. Maybe add a TODO.

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.cc:1560: OnlyNegativeOrZero(*left_range,
*right_range)) {
Do you think it's worth handling the mixed sign cases as well? Maybe add a TODO
for now

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

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.h:274: : ZoneAllocated(),
explicit super constructor call not needed?

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis.h:517: // All CheckSmi instructions.
s/CheckSmi/CheckArrayBoundInstr/

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

https://codereview.chromium.org/470413002/diff/1/runtime/vm/flow_graph_range_...
runtime/vm/flow_graph_range_analysis_test.cc:618: }
Maybe also add unit tests for JoinMin and JoinMax.

[Vyacheslav Egorov (Google), 2014-08-15 15:29:39]

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