Use hash map for the SSA builder constant pool.

Use hash map for the SSA builder constant pool.

This avoid the linear search and quadratic runtime when optimizing
e.g. functions with a large number of constant literals.

R=vegorov@google.com

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

[Vyacheslav Egorov (Google), 2014-06-30 12:13:58]

LGTM

(though this implementation makes a little bit harder to lookup number constants
without allocating whole object first :-/)

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

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:62: if (key.IsDouble()) {
Add mint to cover all common number types.

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:70: return key.GetClassId();
So we still will degrade to linear search when there are a lot of constants of
the same type that are not numbers or strings :-/

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:70: return key.GetClassId();
So we still will degrade to linear search when there are a lot of constants of
the same type that are not numbers or strings :-/

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:74: return kv->value().raw() == key.raw();
identity is not the best equality for numbers and strings.

[Florian Schneider, 2014-06-30 12:38:10]

How does this make looking up number constants harder than it currently is?

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

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:62: if (key.IsDouble()) {
On 2014/06/30 12:13:57, Vyacheslav Egorov (Google wrote:
> Add mint to cover all common number types.

Done.

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:70: return key.GetClassId();
On 2014/06/30 12:13:58, Vyacheslav Egorov (Google wrote:
> So we still will degrade to linear search when there are a lot of constants of
> the same type that are not numbers or strings :-/

Yep. Currently, there is no fast, generic hash-code function. I covered those
that frequenly occur in code, but we can easily add better handling of
individual types, if necessary.

https://codereview.chromium.org/344883009/diff/1/runtime/vm/flow_graph.h#newc...
runtime/vm/flow_graph.h:74: return kv->value().raw() == key.raw();
On 2014/06/30 12:13:58, Vyacheslav Egorov (Google wrote:
> identity is not the best equality for numbers and strings.

Yes, but this is used mostly for canonicalized constants where raw-comparison
works fine. Nothing bad happens if it returns false instead of true in other
cases.

[Vyacheslav Egorov (Google), 2014-06-30 12:41:07]

It makes it harder API wise, previously we could just iterate the list and look
into each individual ConstantInstr if we wanted to implement 

ConstantInstr* GetDoubleConstant(double dbl);

but with hash-table is somewhat harder, you need to do NewCanonical before
calling GetConstant. 

Not a big deal though.

[Florian Schneider, 2014-06-30 12:46:55]

On 2014/06/30 12:41:07, Vyacheslav Egorov (Google wrote:
> It makes it harder API wise, previously we could just iterate the list and
look
> into each individual ConstantInstr if we wanted to implement 
> 
> ConstantInstr* GetDoubleConstant(double dbl);
> 
> but with hash-table is somewhat harder, you need to do NewCanonical before
> calling GetConstant. 
> 
> Not a big deal though.

I see. We still can have GetDoubleConstant(double value) which looks up in a
separate hash map. GetConstant(const Object& obj) dispatches based on the type
of obj to use GetDoubleConstant, or the generic pool.

[Florian Schneider, 2014-06-30 12:52:47]

Committed patchset #2 manually as r37817 (presubmit successful).