Check elimination improvement: propagation of state through phis is supported, CheckMap narrowing i…

Check elimination improvement: propagation of state through phis is supported, CheckMap narrowing implemented.

R=titzer@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=19102

[titzer, 2014-01-23 18:40:55]

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:292: MapSet narrowed_maps = i->Intersect(a,
phase_->zone());
Would prefer the name "intersection" instead of narrowed_maps

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:310:
instr->DeleteAndReplaceWith(new_check_maps);
I think you want to replace both entry->check_ (if it exists) and instr with the
new check. If the entry->check_ exists, then insert the new check before it.

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:314: instr->id(), instr->value()->id()));
In this case, you haven't actually changed anything, so the trace output would
be incorrect.

[Igor Sheludko, 2014-01-29 12:27:13]

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:292: MapSet narrowed_maps = i->Intersect(a,
phase_->zone());
On 2014/01/23 18:40:55, titzer wrote:
> Would prefer the name "intersection" instead of narrowed_maps

Done.

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:310:
instr->DeleteAndReplaceWith(new_check_maps);
On 2014/01/23 18:40:55, titzer wrote:
> I think you want to replace both entry->check_ (if it exists) and instr with
the
> new check. If the entry->check_ exists, then insert the new check before it.

Done.

https://codereview.chromium.org/141653009/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:314: instr->id(), instr->value()->id()));
On 2014/01/23 18:40:55, titzer wrote:
> In this case, you haven't actually changed anything, so the trace output would
> be incorrect.

Done.

[titzer, 2014-02-04 13:12:26]

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:189: HCheckTable* Merge(HBasicBlock* succ,
HCheckTable* that,
We should rename "that" to be "pred", to be more clear.

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:197: InheritPhiOperands(succ, that,
that_block, MERGE, zone);
Why don't you process the phis after first merging the tables? That way, you can
just go through the phis of this block and then insert (in the case of COPY) or
union (in the case of MERGE) their entries with the entries from the incoming
block. I think that would be significantly simpler, and potentially faster.

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:201: HCheckTableEntry* this_entry =
&entries_[i];
Using the above suggestion, you can simply retain any entries in this table for
phis that are defined in "succ". Then you don't need the dominance check for the
other phis, since "that" can't have entries for anything that doesn't dominate
"succ" (i.e. they are handled implicitly).

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:234: if (succ->predecessors()->length() == 1)
return;
I think you want to check succ->phis()->length() == 0 for the early return here.

[Igor Sheludko, 2014-02-05 11:28:01]

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:189: HCheckTable* Merge(HBasicBlock* succ,
HCheckTable* that,
On 2014/02/04 13:12:26, titzer wrote:
> We should rename "that" to be "pred", to be more clear.

Done.

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:197: InheritPhiOperands(succ, that,
that_block, MERGE, zone);
On 2014/02/04 13:12:26, titzer wrote:
> Why don't you process the phis after first merging the tables? That way, you
can
> just go through the phis of this block and then insert (in the case of COPY)
or
> union (in the case of MERGE) their entries with the entries from the incoming
> block. I think that would be significantly simpler, and potentially faster.

Good idea!

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:201: HCheckTableEntry* this_entry =
&entries_[i];
On 2014/02/04 13:12:26, titzer wrote:
> Using the above suggestion, you can simply retain any entries in this table
for
> phis that are defined in "succ". Then you don't need the dominance check for
the
> other phis, since "that" can't have entries for anything that doesn't dominate
> "succ" (i.e. they are handled implicitly).

Done.

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:234: if (succ->predecessors()->length() == 1)
return;
On 2014/02/04 13:12:26, titzer wrote:
> I think you want to check succ->phis()->length() == 0 for the early return
here.

Done.

[titzer, 2014-02-05 11:47:45]

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:189: HCheckTable* Merge(HBasicBlock* succ,
HCheckTable* that,
On 2014/02/04 13:12:26, titzer wrote:
> We should rename "that" to be "pred", to be more clear.

To be clearer:
"that_block" to "pred_block"

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:53: bool remove_at_compation_;
I don't think we need this; see below

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:148: copy->Insert(phi, NULL,
pred_entry->maps_);
I think you want to make a copy of pred_entry->maps_, since these sets are
mutable and the new entry for the phi would alias the maps for the entry that
was just found.

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:222: continue;
I think in this case you can just immediately process the phi. Look up the
corresponding phi input from pred and union into the entry for this phi. If
there is no entry for the corresponding phi input, kill this entry.

Thus you need only one pass through this table and don't need to iterate over
succ's phi list.

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:526: if (entry->object_ == NULL) continue;
Why did this invariant change?

[Igor Sheludko, 2014-02-05 12:26:10]

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/80001/src/hydrogen-check-elimi...
src/hydrogen-check-elimination.cc:189: HCheckTable* Merge(HBasicBlock* succ,
HCheckTable* that,
On 2014/02/05 11:47:46, titzer wrote:
> On 2014/02/04 13:12:26, titzer wrote:
> > We should rename "that" to be "pred", to be more clear.
> 
> To be clearer:
> "that_block" to "pred_block"

Done.

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:53: bool remove_at_compation_;
On 2014/02/05 11:47:46, titzer wrote:
> I don't think we need this; see below

Done.

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:148: copy->Insert(phi, NULL,
pred_entry->maps_);
On 2014/02/05 11:47:46, titzer wrote:
> I think you want to make a copy of pred_entry->maps_, since these sets are
> mutable and the new entry for the phi would alias the maps for the entry that
> was just found.

Done.

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:222: continue;
On 2014/02/05 11:47:46, titzer wrote:
> I think in this case you can just immediately process the phi. Look up the
> corresponding phi input from pred and union into the entry for this phi. If
> there is no entry for the corresponding phi input, kill this entry.
> 
> Thus you need only one pass through this table and don't need to iterate over
> succ's phi list.

Done.

https://codereview.chromium.org/141653009/diff/110001/src/hydrogen-check-elim...
src/hydrogen-check-elimination.cc:526: if (entry->object_ == NULL) continue;
On 2014/02/05 11:47:46, titzer wrote:
> Why did this invariant change?

Done.

[titzer, 2014-02-05 13:29:08]

lgtm

[Igor Sheludko, 2014-02-05 13:40:00]

Committed patchset #5 manually as r19102 (presubmit successful).