Initial implementation of sparse conditional constant propagation.

Initial implementation of sparse conditional constant propagation.

Use the results of SCC to eliminate unreachable code.

BUG=

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

[Kevin Millikin (Google), 2012-09-18 10:34:15]

This is ready for initial reviews.

It's a complicated change because it contains code for abstract evaluation of
instructions on the constant lattice, and also for removing blocks from the
graph while maintaining some of the graph's invariants.

It's fishy that I do not remove definitions (and uses of them) in unreachable
code.  I will add that.

There will be other CLs adding more optimization and cleaning up the approach.

[Florian Schneider, 2012-09-18 12:41:52]

LGTM.

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

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1829: void ConstantPropagator::Join(Object&
left, const Object& right) {
Is it possible to use a pointer for the output parameter? We normally don't pass
non-const references as parameters.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1969: // TODO(kmillikin): Handle constanants.
s/constanants/constants/

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2024: SetValue(instr, non_constant_);
Some instructions can't occur in SSA form: UNREACHABLE()?

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2029: SetValue(instr,
instr->value()->definition()->constant_value());
UNREACHABLE();

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2381: // OS::Print("Working on definition
#%d\n", definition->ssa_temp_index());
Remove print or put it under a flag.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2383:
definition_marks_->Remove(definition->ssa_temp_index());
I don't see definition_marks_ used anywhere. Did you forget to check it to avoid
adding duplicates to the definition_worklist_?

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2391: // OS::Print("Working on block #%d\n",
block->block_id());
Remove print or put it under a flag.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2455: } else if
(!reachable_->Contains(if_false->preorder_number())) {
The code inside this if-statement seems duplicated except the assignment to
join. Maybe change it to sth. like:

JoinEntryInstr* join = NULL;
if (!reachable_->Contains(if_true->preorder_number())) {
  join = new JoinEntryInstr(if_false->try_index());
} else if (!reachable_->Contains(if_false->preorder_number())) {
  join = new JoinEntryInstr(if_true->try_index());
}

if (join != NULL) {
  GotoInstr* jump = new GotoInstr(join);
  Instruction* previous = branch->previous();
  branch->set_previous(NULL);
  previous->set_next(jump);
 
  Instruction* next = if_true->next();
  join->set_next(next);
}

[Florian Schneider, 2012-09-18 12:45:20]

Can you achieve that by just calling ComputeUseLists() again after your
transformation?

> It's fishy that I do not remove definitions (and uses of them) in unreachable
> code.  I will add that.

[Kevin Millikin (Google), 2012-09-19 07:10:01]

Simply calling ComputeUseLists() does not work.  It walks the dominator tree to
clear the existing use lists before recomputing them --- so it will never find
and remove uses in unreachable blocks.

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

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:1829: void ConstantPropagator::Join(Object&
left, const Object& right) {
On 2012/09/18 12:41:52, Florian Schneider wrote:
> Is it possible to use a pointer for the output parameter? We normally don't
pass
> non-const references as parameters.

Done.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2024: SetValue(instr, non_constant_);
On 2012/09/18 12:41:52, Florian Schneider wrote:
> Some instructions can't occur in SSA form: UNREACHABLE()?

Done.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2381: // OS::Print("Working on definition
#%d\n", definition->ssa_temp_index());
On 2012/09/18 12:41:52, Florian Schneider wrote:
> Remove print or put it under a flag.

Removed.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2383:
definition_marks_->Remove(definition->ssa_temp_index());
On 2012/09/18 12:41:52, Florian Schneider wrote:
> I don't see definition_marks_ used anywhere. Did you forget to check it to
avoid
> adding duplicates to the definition_worklist_?

Oops.  It's been added as a check to avoid duplicates in SetValue.

https://codereview.chromium.org/10943007/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2455: } else if
(!reachable_->Contains(if_false->preorder_number())) {
On 2012/09/18 12:41:52, Florian Schneider wrote:
> The code inside this if-statement seems duplicated except the assignment to
> join. Maybe change it to sth. like:
> 
> JoinEntryInstr* join = NULL;
> if (!reachable_->Contains(if_true->preorder_number())) {
>   join = new JoinEntryInstr(if_false->try_index());
> } else if (!reachable_->Contains(if_false->preorder_number())) {
>   join = new JoinEntryInstr(if_true->try_index());
> }
> 
> if (join != NULL) {
>   GotoInstr* jump = new GotoInstr(join);
>   Instruction* previous = branch->previous();
>   branch->set_previous(NULL);
>   previous->set_next(jump);
>  
>   Instruction* next = if_true->next();
>   join->set_next(next);
> }

Done.