Simplify range analysis algorithm.

Simplify range analysis algorithm. 

Replace generic fix point range analysis algorithm based on widening and narrowing operators with an ad hoc single dominator tree pass.

To improve precision discover initial value and direction of the growth for simple induction variables.

R=fschneider@google.com
BUG=

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

[Florian Schneider, 2012-10-25 11:15:43]

lgtm

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1645: enum GrowthDirection {
I'd rename this to just Direction. Growth implies growing numbers which is not
the case with e.g. i--.

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1646: UNKNOWN,
Maybe rename to the more common style

kUnknown, kPositive, kNegative, kBoth

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2002: // The value is comming from outside of
the loop.
s/comming/coming/

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2059: // We transitively discovered all
dependecies of the given phi
s/dependecies/dependencies/

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2060: // and confirmed that it depends on a
sigle value comming from outside of
s/sigle/single/
s/comming/coming/g

[Vyacheslav Egorov (Google), 2012-10-25 11:24:27]

thanks, landing

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1645: enum GrowthDirection {
On 2012/10/25 11:15:43, Florian Schneider wrote:
> I'd rename this to just Direction. Growth implies growing numbers which is not
> the case with e.g. i--.

Done.

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1646: UNKNOWN,
On 2012/10/25 11:15:43, Florian Schneider wrote:
> Maybe rename to the more common style
> 
> kUnknown, kPositive, kNegative, kBoth

Done.

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2002: // The value is comming from outside of
the loop.
On 2012/10/25 11:15:43, Florian Schneider wrote:
> s/comming/coming/

Done.

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2059: // We transitively discovered all
dependecies of the given phi
On 2012/10/25 11:15:43, Florian Schneider wrote:
> s/dependecies/dependencies/

Done.

https://codereview.chromium.org/11283002/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2060: // and confirmed that it depends on a
sigle value comming from outside of
On 2012/10/25 11:15:43, Florian Schneider wrote:
> s/sigle/single/
> s/comming/coming/g

Done.