Simple redundant load elimination.

Simple redundant load elimination.

This analysis uses bit vectors to track side effects. Currently, there is
only one type of side effect which affects all mutable load-field instructions.
The elimination pass is a dominator tree preorder traversal like the existing
CSE pass. Instead of a hash-map it keeps an array with the current dominating
occurrence for each load expression.
Committed: https://code.google.com/p/dart/source/detail?r=12437

[Kevin Millikin (Google), 2012-09-17 12:09:47]

LGTM when comments are addressed.

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

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/bit_vector.cc#n...
runtime/vm/bit_vector.cc:71: bool BitVector::Intersect(const BitVector& other) {
It doesn't look like you use the return value, so we can use the simpler
implementation that doesn't care about changed.

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

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/bit_vector.h#ne...
runtime/vm/bit_vector.h:92: void SetAll() {
There's a subtle interaction between Clear(), SetAll(), and Equals().  The first
two clear and set bits past length_.  The last one compares bits past length_. 
Bit vectors that have all bits in range 0..length_-1 equal might not compare
Equals.

It might be better to choose either:

1. Never set a bit past length_ (requires a mask for the last word of the data
in SetAll), or

2. Ignore bits past length_ for Equals (requires a mask for the last word
comparison in Equals).

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

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1580: static void Propagate(FlowGraph* graph,
Propagate is a generic name.  How about "AnalyzeLoads"?

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1589: for (ForwardInstructionIterator
instr_it(block);
If you iterate backward, you can break from the loop as soon as you see an
instruction with side effects.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1606:
avail_gen[block->preorder_number()]->Add(defn->expr_id());
It might be more straightforward to compute kill and gen in this loop over
instructions in a block, and then just copy gen as the value of avail_out for
the block after this loop.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1637: if (i == 0) temp->SetAll();
I prefer:

if (block->IsGraphEntry()) {
  temp->Clear();
} else {
  temp->SetAll();
  for (intptr_t ....) // Compute intersection.
}

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1643: block_in->Clear();
Seems like we might as well combine Clear and AddAll into a single copy
function, either block_in->CopyFrom(temp) or temp->CopyTo(block_in) or remove
DISALLOW_COPY_AND_ASSIGN and implement the assignment operator and copy
constructor.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1716: intptr_t max_expr_id =
NumberLoadExpressions(graph);
Can we move NumberLoadExpressions(graph) inside an "if (FLAG_load_cse)"?

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1719: GrowableArray<BitVector*>
avail_out(num_blocks);
I'd move avail_gen, and _kill into Propagate so it's more obvious that avail_in
and avail_out is the analysis result.

[Florian Schneider, 2012-09-17 14:20:58]

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

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/bit_vector.cc#n...
runtime/vm/bit_vector.cc:71: bool BitVector::Intersect(const BitVector& other) {
On 2012/09/17 12:09:47, kmillikin wrote:
> It doesn't look like you use the return value, so we can use the simpler
> implementation that doesn't care about changed.

Done.

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

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/bit_vector.h#ne...
runtime/vm/bit_vector.h:92: void SetAll() {
On 2012/09/17 12:09:47, kmillikin wrote:
> There's a subtle interaction between Clear(), SetAll(), and Equals().  The
first
> two clear and set bits past length_.  The last one compares bits past length_.

> Bit vectors that have all bits in range 0..length_-1 equal might not compare
> Equals.
> 
> It might be better to choose either:
> 
> 1. Never set a bit past length_ (requires a mask for the last word of the data
> in SetAll), or
> 
> 2. Ignore bits past length_ for Equals (requires a mask for the last word
> comparison in Equals).

Thanks. I opted for (2) and changed Equals accordingly.

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

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1580: static void Propagate(FlowGraph* graph,
On 2012/09/17 12:09:47, kmillikin wrote:
> Propagate is a generic name.  How about "AnalyzeLoads"?

Done.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1589: for (ForwardInstructionIterator
instr_it(block);
On 2012/09/17 12:09:47, kmillikin wrote:
> If you iterate backward, you can break from the loop as soon as you see an
> instruction with side effects.

Done.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1606:
avail_gen[block->preorder_number()]->Add(defn->expr_id());
On 2012/09/17 12:09:47, kmillikin wrote:
> It might be more straightforward to compute kill and gen in this loop over
> instructions in a block, and then just copy gen as the value of avail_out for
> the block after this loop.

Done.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1637: if (i == 0) temp->SetAll();
On 2012/09/17 12:09:47, kmillikin wrote:
> I prefer:
> 
> if (block->IsGraphEntry()) {
>   temp->Clear();
> } else {
>   temp->SetAll();
>   for (intptr_t ....) // Compute intersection.
> }

Done.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1643: block_in->Clear();
On 2012/09/17 12:09:47, kmillikin wrote:
> Seems like we might as well combine Clear and AddAll into a single copy
> function, either block_in->CopyFrom(temp) or temp->CopyTo(block_in) or remove
> DISALLOW_COPY_AND_ASSIGN and implement the assignment operator and copy
> constructor.

Done.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1716: intptr_t max_expr_id =
NumberLoadExpressions(graph);
On 2012/09/17 12:09:47, kmillikin wrote:
> Can we move NumberLoadExpressions(graph) inside an "if (FLAG_load_cse)"?

Done.

https://codereview.chromium.org/10914314/diff/6002/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1719: GrowableArray<BitVector*>
avail_out(num_blocks);
On 2012/09/17 12:09:47, kmillikin wrote:
> I'd move avail_gen, and _kill into Propagate so it's more obvious that
avail_in
> and avail_out is the analysis result.

Done.