Compute assigned variables and dominance frontiers.

Compute assigned variables and dominance frontiers.

During basic block discovery, compute assigned variables in each
block.  After computing immediate dominators, compute dominance
frontiers.  Both of these will be used for SSA construction.

R=fschneider@google.com,srdjan@google.com
BUG=
TEST=

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

[Kevin Millikin (Google), 2012-05-11 10:38:59]

There's no really simple way to test this.  I'm open to suggestions, though.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1256: virtual void DiscoverBlocks(
All these arguments is a bad smell, I plan to refactor later.

[Florian Schneider, 2012-05-11 13:19:37]

LGTM from my side.  Please also add a unit test for the BitVector class.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder.cc
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:2573: Isolate::Current()->current_zone()));
Maybe it would be useful to have a Zone* zone_ stored in the FlowGraphBuilder
because we will do frequent zone-allocation for auxiliary data structures from
there.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:283:
next->RecordAssignedVars(assigned_vars->Last());
assigned_vars->Last() == vars

The one that's just been added in line 269. Maybe just use vars here instead.

[srdjan, 2012-05-12 00:00:55]

LGTM after addressing comments

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode12
runtime/vm/bit_vector.h:12: 
This class seems to generic for what you currently need, and we already have
another variation of bitmaps for stackmaps. Maybe we want to merge those two
later, but for now it is OK to add a subset of what is here. All functionality
in BitVector must be tested. Please remove all methods that you do not need, and
add tests to those that survive the pruning.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode57
runtime/vm/bit_vector.h:57: data_(zone->AllocateArray<uword>(data_length_)) {
Do not pass in the Zone, instead use
Isolate::Current()->current_zone()->Allocate

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode61
runtime/vm/bit_vector.h:61: static int SizeFor(int length) {
intptr_t instead of int (everywhere).

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder.cc
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:2541: GrowableArray<BitVector*>*
dominance_frontier) {
Maybe add in comment what is the content of parent array (what does the integer
means) and what is the content of dominance_frontier (what do bits mean).

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:2573: Isolate::Current()->current_zone()));
On 2012/05/11 13:19:37, Florian Schneider wrote:
> Maybe it would be useful to have a Zone* zone_ stored in the FlowGraphBuilder
> because we will do frequent zone-allocation for auxiliary data structures from
> there.

That would premature optimization, IMHO. At some point we may want to cache
Isolate and Zone but right now I would eliminate zone parameter, especially
since we do not pass different zones but the current one.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:210: index -= 2;
Note that soon we will add a third word after ebp (upcoming Siva's change). Why
not allocate a BitMap that includes return address, ebp (and the new code
reference entry).  Index would remain unchanged if positive and will be computed
as below if negative.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:90: virtual void
RecordAssignedVars(BitVector* assigned_vars);
Please document what does BitVector represent.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1256: virtual void DiscoverBlocks(
On 2012/05/11 10:39:00, kmillikin wrote:
> All these arguments is a bad smell, I plan to refactor later.

Sounds good.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/zone.h
File runtime/vm/zone.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/zone.h#newcode115
runtime/vm/zone.h:115: }
Remove this code. Do the appropriate allocation computation in BitVector
instead.

[Kevin Millikin (Google), 2012-05-15 11:51:43]

This can be landed after http://codereview.chromium.org/10399026/

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode12
runtime/vm/bit_vector.h:12: 
On 2012/05/12 00:00:55, srdjan wrote:
> This class seems to generic for what you currently need, and we already have
> another variation of bitmaps for stackmaps. Maybe we want to merge those two
> later, but for now it is OK to add a subset of what is here. All functionality
> in BitVector must be tested. Please remove all methods that you do not need,
and
> add tests to those that survive the pruning. 

I've added tests.

It's a bit unfortunate to strip out functionality.  (Contains, Remove, Union,
Intersect, Subtract, IsEmpty, Equals, Print, copy constructor, operator=, and
made it DISALLOW_COPY_AND_ASSIGN because it would no longer work correctly).

Most of this will be needed, and now someone who just wants to get work done
will have to stop and reimplement a bunch of BitVector stuff.  (Not to mention
the risk of discarding and reimplementing code that is already well-used in
production.)

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode57
runtime/vm/bit_vector.h:57: data_(zone->AllocateArray<uword>(data_length_)) {
On 2012/05/12 00:00:55, srdjan wrote:
> Do not pass in the Zone, instead use
> Isolate::Current()->current_zone()->Allocate

OK, but it seems better without the needing to go to TLS.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode61
runtime/vm/bit_vector.h:61: static int SizeFor(int length) {
On 2012/05/12 00:00:55, srdjan wrote:
> intptr_t instead of int (everywhere).

OK, I've done that here.

This class is currently used with LocalVariable indexes as the elements.  Those
are type int.  When you say "everywhere", do you intend me to change
LocalVariable::index_ to intptr_t and propagate that change to all LocalVariable
clients?  :)

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder.cc
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:2541: GrowableArray<BitVector*>*
dominance_frontier) {
On 2012/05/12 00:00:55, srdjan wrote:
> Maybe add in comment what is the content of parent array (what does the
integer
> means) and what is the content of dominance_frontier (what do bits mean).

Done.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:2573: Isolate::Current()->current_zone()));
On 2012/05/12 00:00:55, srdjan wrote:
> On 2012/05/11 13:19:37, Florian Schneider wrote:
> > Maybe it would be useful to have a Zone* zone_ stored in the
FlowGraphBuilder
> > because we will do frequent zone-allocation for auxiliary data structures
from
> > there.
> 
> That would premature optimization, IMHO. At some point we may want to cache
> Isolate and Zone but right now I would eliminate zone parameter, especially
> since we do not pass different zones but the current one.

I've eliminated the parameter, but I disagree that it is premature optimization.

There's a pretty big constant factor involved in paying for TLS on every zone
allocation.  And I think it is much easier to begin now passing the current
isolate and/or zone around where needed, rather than trying to implement a big
change to retrofit it later.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:210: index -= 2;
On 2012/05/12 00:00:55, srdjan wrote:
> Note that soon we will add a third word after ebp (upcoming Siva's change).
Why
> not allocate a BitMap that includes return address, ebp (and the new code
> reference entry).  Index would remain unchanged if positive and will be
computed
> as below if negative.

Well, we either have to deal with the 'magic' extra frame elements here or else
when we allocate the bit vector.

Both of those will each happen one place in the code, so it seems better to not
track them if we don't care about them.  

Unfortunately, I can't find a canonical place with named constants for the frame
description (are they platform independent?  guaranteed so?), so that's why I
have the magic numbers in there for now. :(

What I really want is a 0-based variable index assigned to each frame-allocated
variable (e.g., one that can be used for printing and doesn't need to know the
size of the frame to be computed every time), but it turns out it's not entirely
simple to make the scopes code do that because we sometimes whack variables in
to the frame after scope analysis.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:283:
next->RecordAssignedVars(assigned_vars->Last());
On 2012/05/11 13:19:37, Florian Schneider wrote:
> assigned_vars->Last() == vars
> 
> The one that's just been added in line 269. Maybe just use vars here instead.

Well spotted.  Done.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:90: virtual void
RecordAssignedVars(BitVector* assigned_vars);
On 2012/05/12 00:00:55, srdjan wrote:
> Please document what does BitVector represent.

Done.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/zone.h
File runtime/vm/zone.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/zone.h#newcode115
runtime/vm/zone.h:115: }
On 2012/05/12 00:00:55, srdjan wrote:
> Remove this code. Do the appropriate allocation computation in BitVector
> instead.

OK, but I'm not sure why.  Avoiding reinterpret_cast and sizeof at the call site
seems like the perfect use of a simple convenience function, and I'd rather not
have to write the same type twice in the expression.

[srdjan, 2012-05-15 22:05:32]

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode12
runtime/vm/bit_vector.h:12: 
On 2012/05/15 11:51:44, kmillikin wrote:
> On 2012/05/12 00:00:55, srdjan wrote:
> > This class seems to generic for what you currently need, and we already have
> > another variation of bitmaps for stackmaps. Maybe we want to merge those two
> > later, but for now it is OK to add a subset of what is here. All
functionality
> > in BitVector must be tested. Please remove all methods that you do not need,
> and
> > add tests to those that survive the pruning. 
> 
> I've added tests.
> 
> It's a bit unfortunate to strip out functionality.  (Contains, Remove, Union,
> Intersect, Subtract, IsEmpty, Equals, Print, copy constructor, operator=, and
> made it DISALLOW_COPY_AND_ASSIGN because it would no longer work correctly).
> 
> Most of this will be needed, and now someone who just wants to get work done
> will have to stop and reimplement a bunch of BitVector stuff.  (Not to mention
> the risk of discarding and reimplementing code that is already well-used in
> production.)


Generally we should separate CLs that contribute core libraries to the VM, so
that it can be discussed separately. We should not have dead/unused code in the
VM and its libraries. If you feel confident that you will use it quite soon, I
think it is OK to leave them otherwise they do not belong here (smaller is
better in this case :-).

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode57
runtime/vm/bit_vector.h:57: data_(zone->AllocateArray<uword>(data_length_)) {
On 2012/05/15 11:51:44, kmillikin wrote:
> On 2012/05/12 00:00:55, srdjan wrote:
> > Do not pass in the Zone, instead use
> > Isolate::Current()->current_zone()->Allocate
> 
> OK, but it seems better without the needing to go to TLS.

The interface is more complex when passing Zone, without clear benefit.
Generally, in the VM and at this stage, we should avoid passing isolates or zone
for performance reasons. This way it looks like we need to allocate BitVector in
varying zones.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/bit_vector.h#newcode61
runtime/vm/bit_vector.h:61: static int SizeFor(int length) {
On 2012/05/15 11:51:44, kmillikin wrote:
> On 2012/05/12 00:00:55, srdjan wrote:
> > intptr_t instead of int (everywhere).
> 
> OK, I've done that here.
> 
> This class is currently used with LocalVariable indexes as the elements. 
Those
> are type int.  When you say "everywhere", do you intend me to change
> LocalVariable::index_ to intptr_t and propagate that change to all
LocalVariable
> clients?  :)


The VM rule is that all memory sizes should be in intptr_t. In case of doubt we
should err toward intptr_t. No need to go fix existing code :-).

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder.cc
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:2573: Isolate::Current()->current_zone()));
On 2012/05/15 11:51:44, kmillikin wrote:
> On 2012/05/12 00:00:55, srdjan wrote:
> > On 2012/05/11 13:19:37, Florian Schneider wrote:
> > > Maybe it would be useful to have a Zone* zone_ stored in the
> FlowGraphBuilder
> > > because we will do frequent zone-allocation for auxiliary data structures
> from
> > > there.
> > 
> > That would premature optimization, IMHO. At some point we may want to cache
> > Isolate and Zone but right now I would eliminate zone parameter, especially
> > since we do not pass different zones but the current one.
> 
> I've eliminated the parameter, but I disagree that it is premature
optimization.
> 
> There's a pretty big constant factor involved in paying for TLS on every zone
> allocation.  And I think it is much easier to begin now passing the current
> isolate and/or zone around where needed, rather than trying to implement a big
> change to retrofit it later.

In the VM we do not pass isolates/zones for performance reasons.

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.cc (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:210: index -= 2;
On 2012/05/15 11:51:44, kmillikin wrote:
> On 2012/05/12 00:00:55, srdjan wrote:
> > Note that soon we will add a third word after ebp (upcoming Siva's change).
> Why
> > not allocate a BitMap that includes return address, ebp (and the new code
> > reference entry).  Index would remain unchanged if positive and will be
> computed
> > as below if negative.
> 
> Well, we either have to deal with the 'magic' extra frame elements here or
else
> when we allocate the bit vector.
> 
> Both of those will each happen one place in the code, so it seems better to
not
> track them if we don't care about them.  
> 
> Unfortunately, I can't find a canonical place with named constants for the
frame
> description (are they platform independent?  guaranteed so?), so that's why I
> have the magic numbers in there for now. :(
> 
> What I really want is a 0-based variable index assigned to each
frame-allocated
> variable (e.g., one that can be used for printing and doesn't need to know the
> size of the frame to be computed every time), but it turns out it's not
entirely
> simple to make the scopes code do that because we sometimes whack variables in
> to the frame after scope analysis.

Can we put intelligence into LocalVariable? If you do not like any alternatives,
leave the code here.

Check a new constant in ParsedFunction in Siva's change:

https://chromiumcodereview.appspot.com/10375059/diff/13001/vm/parser.h

http://codereview.chromium.org/10377104/diff/1/runtime/vm/zone.h
File runtime/vm/zone.h (right):

http://codereview.chromium.org/10377104/diff/1/runtime/vm/zone.h#newcode115
runtime/vm/zone.h:115: }
On 2012/05/15 11:51:44, kmillikin wrote:
> On 2012/05/12 00:00:55, srdjan wrote:
> > Remove this code. Do the appropriate allocation computation in BitVector
> > instead.
> 
> OK, but I'm not sure why.  Avoiding reinterpret_cast and sizeof at the call
site
> seems like the perfect use of a simple convenience function, and I'd rather
not
> have to write the same type twice in the expression.

I think there is only one place that needs it, therefore no need to  have it in
a library.