First step to SSA construction: Phi insertion.

First step to SSA construction: Phi insertion.

This CL contains the phi insertion step of the SSA construction algorithmus: The phi instructions inserted are not functional yet. Renaming is not included yet.


I based it on Kevin's CL (http://codereview.chromium.org/10388161/), rebased and fixed a bug (added missing iterator.Advance()) there.

It also reintroduces the Definition IL class because Phi-instructions are also
definitions that are referenced by UseVal.

I also added the set of immediately dominated blocks to each basic block.
This will be needed for pre-order dominator-tree traversal in the renaming pass.
Committed: https://code.google.com/p/dart/source/detail?r=8604

[srdjan, 2012-06-12 17:34:37]

LGTM, but please wait on Slava's comments as well. Thanks.

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

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/bit_vector.h#newcode69
vm/bit_vector.h:69: return (block & (1U << (i % sizeof(uword)))) != 0;
Please add a test

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder.cc
File vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2490: void
FlowGraphBuilder::InsertPhis(GrowableArray<BlockEntryInstr*>* preorder,
const GrowableArray<BlockEntryInstr>&

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2491: GrowableArray<BitVector*>* assigned_vars,
const GrowableArray<BitVector>&

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2493: GrowableArray<BitVector*>* dom_frontier) {
ditto

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2494: int block_count = preorder->length();
const intptr_t

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2498: int* has_already = new int[block_count];
Allocation in C++ heap should be avoided (memory leaks, slow). Use Zone
allocated arrays. In fact I would use GrowableArrays<intptr_t> allocated to
capacity block_count and cleared with the loop below. (both for has_already and
work).

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
File vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.cc:94: Value* BranchInstr::InputAt(intptr_t i) const {
An alternative would be ASSERT(i == 0); return value();, but I am OK with this
as well

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:298: }
Why do you need set_defintion?

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1490: void InsertPhi(intptr_t variable_index) { }
Why is this needed?

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1732: }
Instead of returning a modifieable array, better add:

void AddDominatedBlock(intptr_t block_index) {
  dominated_blocks_.Add(block_index);
}

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1833: ZoneGrowableArray<PhiInstr*>* phis() const {
return phis_; }
const ZoneGrowableArray<...>& ?

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1837: void InsertPhi(intptr_t var_index, intptr_t
var_count);
Get rid of var_count, it is used only to allocate optimal capacity of growable
array.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1956: void set_temp_index(intptr_t index) {
temp_index_ = index; }
Add a comment to something like that this is the common sueprclass of Phis and
Binds and is not allocatable (since it does not DECLARE_INSTRUCTION)

[Florian Schneider, 2012-06-13 10:53:40]

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

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/bit_vector.h#newcode69
vm/bit_vector.h:69: return (block & (1U << (i % sizeof(uword)))) != 0;
On 2012/06/12 17:34:37, srdjan wrote:
> Please add a test

Done. Good point. I fixed a bug here as well.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder.cc
File vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2490: void
FlowGraphBuilder::InsertPhis(GrowableArray<BlockEntryInstr*>* preorder,
On 2012/06/12 17:34:37, srdjan wrote:
> const GrowableArray<BlockEntryInstr>&

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2491: GrowableArray<BitVector*>* assigned_vars,
On 2012/06/12 17:34:37, srdjan wrote:
> const GrowableArray<BitVector>&

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2493: GrowableArray<BitVector*>* dom_frontier) {
On 2012/06/12 17:34:37, srdjan wrote:
> ditto

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2494: int block_count = preorder->length();
On 2012/06/12 17:34:37, srdjan wrote:
> const intptr_t

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2494: int block_count = preorder->length();
On 2012/06/12 17:34:37, srdjan wrote:
> const intptr_t

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2498: int* has_already = new int[block_count];
On 2012/06/12 17:34:37, srdjan wrote:
> Allocation in C++ heap should be avoided (memory leaks, slow). Use Zone
> allocated arrays. In fact I would use GrowableArrays<intptr_t> allocated to
> capacity block_count and cleared with the loop below. (both for has_already
and
> work).

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:298: }
On 2012/06/12 17:34:37, srdjan wrote:
> Why do you need set_defintion?

Renaming. I could leave it out for this CL. Left-over from splitting my CL into
pieces.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1490: void InsertPhi(intptr_t variable_index) { }
On 2012/06/12 17:34:37, srdjan wrote:
> Why is this needed?

Accidental edit.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1732: }
On 2012/06/12 17:34:37, srdjan wrote:
> Instead of returning a modifieable array, better add:
> 
> void AddDominatedBlock(intptr_t block_index) {
>   dominated_blocks_.Add(block_index);
> }

Done.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1833: ZoneGrowableArray<PhiInstr*>* phis() const {
return phis_; }
On 2012/06/12 17:34:37, srdjan wrote:
> const ZoneGrowableArray<...>& ?

phis_ can be NULL.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1837: void InsertPhi(intptr_t var_index, intptr_t
var_count);
On 2012/06/12 17:34:37, srdjan wrote:
> Get rid of var_count, it is used only to allocate optimal capacity of growable
> array.

Growable arrays incur a high cost when not used with good initial size
estimates. (in this case I actually want a fixed-size array). I need some
initial size and this is readily available to avoid reallocating 3 times for
adding very few elements.

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1956: void set_temp_index(intptr_t index) {
temp_index_ = index; }
On 2012/06/12 17:34:37, srdjan wrote:
> Add a comment to something like that this is the common sueprclass of Phis and
> Binds and is not allocatable (since it does not DECLARE_INSTRUCTION)

Done.

[Vyacheslav Egorov (Google), 2012-06-13 13:15:24]

lgtm

[srdjan, 2012-06-13 18:45:26]

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10539108/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1837: void InsertPhi(intptr_t var_index, intptr_t
var_count);
On 2012/06/13 10:53:40, Florian Schneider wrote:
> On 2012/06/12 17:34:37, srdjan wrote:
> > Get rid of var_count, it is used only to allocate optimal capacity of
growable
> > array.
> 
> Growable arrays incur a high cost when not used with good initial size
> estimates. (in this case I actually want a fixed-size array). I need some
> initial size and this is readily available to avoid reallocating 3 times for
> adding very few elements.
> 

Yes, but the 'var_count' looks weird in the API, as it has nothing to do with
the computation of phis. Have we measured a negative performance impact so that
it validates the more complicate API?  We must refrain from premature
optimizations (e.g., passing isolates, zones, best allocation size)!