Simple iterative liveness analysis over SSA.

Simple iterative liveness analysis over SSA.

R=fschneider@google.com
BUG=
TEST=

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

[Florian Schneider, 2012-06-25 14:38:29]

LGTM with comments.

Maybe it would make sense to wait until we can iterate backwards in the IL
(pending CL https://chromiumcodereview.appspot.com/10665022/) and update this CL
accordingly.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:66: bool AddAll(BitVector* from) {
Maybe add a test to bit_vector_test.cc that covers the two new functions.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:78: bool KillAndAdd(BitVector* kill, BitVector* gen) {
Add a comment what this computes: sth like

this += (gen \ kill)

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:35: if (def == 0) return -1;
Better def == NULL?

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:50: for (intptr_t j = 0; j <
join->phis()->length(); j++) {
Missing NULL check: join->phis() can be NULL for join blocks that do not contain
any phis.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:148: printf("%s:", tag);
Use OS::Print instead.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:150: printf(" %d", it.Current());
OS::Print

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:152: printf("\n");
OS::Print

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:172: PrintBitVector("  live in",
live_in_[i]);
Maybe print in a different order? e.g. live_in, gen, kill, live_out

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:15: explicit FlowGraphAllocator(const
GrowableArray<BlockEntryInstr*>& postorder,
No explicit necessary.

[Vyacheslav Egorov (Google), 2012-06-25 16:58:25]

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:66: bool AddAll(BitVector* from) {
On 2012/06/25 14:38:29, Florian Schneider wrote:
> Maybe add a test to bit_vector_test.cc that covers the two new functions.

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:78: bool KillAndAdd(BitVector* kill, BitVector* gen) {
On 2012/06/25 14:38:29, Florian Schneider wrote:
> Add a comment what this computes: sth like
> 
> this += (gen \ kill)

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:35: if (def == 0) return -1;
On 2012/06/25 14:38:29, Florian Schneider wrote:
> Better def == NULL?

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:50: for (intptr_t j = 0; j <
join->phis()->length(); j++) {
On 2012/06/25 14:38:29, Florian Schneider wrote:
> Missing NULL check: join->phis() can be NULL for join blocks that do not
contain
> any phis.

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:148: printf("%s:", tag);
On 2012/06/25 14:38:29, Florian Schneider wrote:
> Use OS::Print instead.

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:150: printf(" %d", it.Current());
On 2012/06/25 14:38:29, Florian Schneider wrote:
> OS::Print

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:152: printf("\n");
On 2012/06/25 14:38:29, Florian Schneider wrote:
> OS::Print

Done.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:172: PrintBitVector("  live in",
live_in_[i]);
On 2012/06/25 14:38:29, Florian Schneider wrote:
> Maybe print in a different order? e.g. live_in, gen, kill, live_out

We print blocks in post order so printing live out first seems to match it.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:15: explicit FlowGraphAllocator(const
GrowableArray<BlockEntryInstr*>& postorder,
On 2012/06/25 14:38:29, Florian Schneider wrote:
> No explicit necessary.

Done.

[srdjan, 2012-06-25 17:30:05]

DBC

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:66: bool AddAll(BitVector* from) {
The two methods seem to complex for header file, I would move them to .cc file.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:80: ASSERT(data_length_ == gen->data_length_);
It may be clearer to have Kill without Add, do you expect measurable performance
improvement by merging them?

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/compiler.cc...
runtime/vm/compiler.cc:200: printf("====================================\n");
remove print

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:37: }
return (def == NULL) ? -1 : def->ssa_temp_index();

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:46: BitVector* gen = gen_[i];
ASSERT kill and gen are not NULL.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:94: Instruction* last =
instr->last_instruction();
ASSERT (last != NULL, live_out != NULL) ?

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:95: for (intptr_t i = 0; i <
last->SuccessorCount(); i++) {
SuccessotCount can be 0 or 1, is a loop necessary?

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:96: BlockEntryInstr* succ =
last->SuccessorAt(i);
ASSERT(succ != NULL) ?

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:115: bool changed;
bool changed = false;

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:117: changed = false;
Remove this line.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:120: BlockEntryInstr* block = postorder_[i];
Maybe add comments that you do not need to update live-ins if there was no
change in live outs.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:160: printf("block @%d -> ",
block->block_id());
OS::Print here as well.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:28: 
It woud be nice to have comments describing briefly which state is described by
which instance field, as long as the name does not describe itself.

[Vyacheslav Egorov (Google), 2012-06-25 17:42:23]

Thanks for the DBC, I will address in a separate CL.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/bit_vector....
runtime/vm/bit_vector.h:80: ASSERT(data_length_ == gen->data_length_);
On 2012/06/25 17:30:05, srdjan wrote:
> It may be clearer to have Kill without Add, do you expect measurable
performance
> improvement by merging them?

It's not easy to have Kill without Add because we pass live_out_ as gen, so we
can't kill "in place".

Yes, for big methods with lots of SSA variables.

But in that case it would also be good to have kill pre-negated.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:94: Instruction* last =
instr->last_instruction();
On 2012/06/25 17:30:05, srdjan wrote:
> ASSERT (last != NULL, live_out != NULL) ?

live_out_ != NULL is a fundamental property of initialization code. I don't see
a reason to assert it.

I am also not sure what is the benefit of asserting not-nullness for a values
that are immediately derefed --- we will get SIGSEGV anyways.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:95: for (intptr_t i = 0; i <
last->SuccessorCount(); i++) {
On 2012/06/25 17:30:05, srdjan wrote:
> SuccessotCount can be 0 or 1, is a loop necessary?

it can be 0, 1 (implicit goto), 2 (branch), 1 + #catch entries (graph entry).

if we introduce switch-tables we might get even more different values, so I
prefer to have a loop.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:117: changed = false;
On 2012/06/25 17:30:05, srdjan wrote:
> Remove this line.

I need to reset changed to false after each iteration.

[srdjan, 2012-06-25 17:51:44]

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:94: Instruction* last =
instr->last_instruction();
On 2012/06/25 17:42:23, Vyacheslav Egorov (Google) wrote:
> On 2012/06/25 17:30:05, srdjan wrote:
> > ASSERT (last != NULL, live_out != NULL) ?
> 
> live_out_ != NULL is a fundamental property of initialization code. I don't
see
> a reason to assert it.
> 
> I am also not sure what is the benefit of asserting not-nullness for a values
> that are immediately derefed --- we will get SIGSEGV anyways. 

Agree with the fundamental property. SIGSEGV is much uglier to debug then an
ASSERT, IMHO.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:95: for (intptr_t i = 0; i <
last->SuccessorCount(); i++) {
On 2012/06/25 17:42:23, Vyacheslav Egorov (Google) wrote:
> On 2012/06/25 17:30:05, srdjan wrote:
> > SuccessotCount can be 0 or 1, is a loop necessary?
> 
> it can be 0, 1 (implicit goto), 2 (branch), 1 + #catch entries (graph entry).
> 
> if we introduce switch-tables we might get even more different values, so I
> prefer to have a loop.

Mea culpa.

https://chromiumcodereview.appspot.com/10666026/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:117: changed = false;
On 2012/06/25 17:42:23, Vyacheslav Egorov (Google) wrote:
> On 2012/06/25 17:30:05, srdjan wrote:
> > Remove this line.
> 
> I need to reset changed to false after each iteration. 

I negated the condition while reading. Mea Culpa