Improve redundant load elimination

Improve redundant load elimination.

Previously it incorrectly computed OUT sets during the fix point iteration: did not propagate changed from IN to OUT.

However just computing bitset representation of IN set was actually not enough because different values might be coming in from different predecessors. 

This algorithm inserts phis at merge points.

R=fschneider@google.com
BUG=

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

[Vyacheslav Egorov (Google), 2012-12-12 18:20:27]

Please take another look.

This version passes all the tests.

[Florian Schneider, 2012-12-13 13:17:13]

LGTM.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.h#ne...
runtime/vm/bit_vector.h:79: bool RemoveAll(const BitVector* from);
Maybe add a short line what it does.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:2886: explicit LoadOptimizer(FlowGraph*
graph,
No explicit needed.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:2995: exposed_values = new
ZoneGrowableArray<Definition*>(5);
max_expr_id should be upper bound. Maybe sth like: Min(max_expr_id,
kMaxInitialSize)

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3017: // When merging incomming loads we
might need to create a phi.
s/incomming/incoming/

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3018: // These phies are not inserted at the
graph immediately because some of them
s/phies/phis/

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3139: // they might contain values that were
replace and removed
s/replace/replaced/

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3142: // as replaced and store a pointer to
the replacement.
Maybe add an assert that:

(*pred_out_values)[expr_id] != NULL

to document that expr_id is expected to be available on all predecessors.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3146: input->set_instruction(phi);
Should we have a helper RegisterUse that does these three operations? They
always belong together.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3161:
!gen_[block->preorder_number()]->Contains(expr_id)) {
I think this can be simplified: upward exposed loads that are not killed are
always in gen, so you'd never enter this if-case.

[Florian Schneider, 2012-12-13 13:21:06]

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.cc
File runtime/vm/bit_vector.cc (right):

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.cc#n...
runtime/vm/bit_vector.cc:65: bool BitVector::RemoveAll(const BitVector* from) {
Please also add a test case to bit_vector_test.cc.

[Vyacheslav Egorov (Google), 2012-12-13 14:02:59]

Thank you for the review!

Landing.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.cc
File runtime/vm/bit_vector.cc (right):

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.cc#n...
runtime/vm/bit_vector.cc:65: bool BitVector::RemoveAll(const BitVector* from) {
On 2012/12/13 13:21:06, Florian Schneider wrote:
> Please also add a test case to bit_vector_test.cc.

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/bit_vector.h#ne...
runtime/vm/bit_vector.h:79: bool RemoveAll(const BitVector* from);
On 2012/12/13 13:17:13, Florian Schneider wrote:
> Maybe add a short line what it does.

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:2886: explicit LoadOptimizer(FlowGraph*
graph,
On 2012/12/13 13:17:13, Florian Schneider wrote:
> No explicit needed.

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:2995: exposed_values = new
ZoneGrowableArray<Definition*>(5);
On 2012/12/13 13:17:13, Florian Schneider wrote:
> max_expr_id should be upper bound. Maybe sth like: Min(max_expr_id,
> kMaxInitialSize)

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3017: // When merging incomming loads we
might need to create a phi.
On 2012/12/13 13:17:13, Florian Schneider wrote:
> s/incomming/incoming/

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3018: // These phies are not inserted at the
graph immediately because some of them
On 2012/12/13 13:17:13, Florian Schneider wrote:
> s/phies/phis/

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3139: // they might contain values that were
replace and removed
On 2012/12/13 13:17:13, Florian Schneider wrote:
> s/replace/replaced/

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3142: // as replaced and store a pointer to
the replacement.
On 2012/12/13 13:17:13, Florian Schneider wrote:
> Maybe add an assert that:
> 
> (*pred_out_values)[expr_id] != NULL
> 
> to document that expr_id is expected to be available on all predecessors.

Done.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3146: input->set_instruction(phi);
On 2012/12/13 13:17:13, Florian Schneider wrote:
> Should we have a helper RegisterUse that does these three operations? They
> always belong together.

I will leave it for a separate CL.

https://codereview.chromium.org/11505002/diff/3001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3161:
!gen_[block->preorder_number()]->Contains(expr_id)) {
On 2012/12/13 13:17:13, Florian Schneider wrote:
> I think this can be simplified: upward exposed loads that are not killed are
> always in gen, so you'd never enter this if-case.

Good observation. Killed the helper.

[srdjan, 2012-12-13 18:27:15]

DBC

https://codereview.chromium.org/11505002/diff/8002/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/11505002/diff/8002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:2884: class LoadOptimizer : public
ValueObject {
This is a long class. Maybe it warrants its own file?