Optimistically hoist SmiCheck through phi when the only value of unknown type coming into the phi i…

Optimistically hoist SmiCheck through phi when the only value of unknown type coming into the phi is an operand corresponding to the loop's pre-header.

R=fschneider@google.com
BUG=

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

[srdjan, 2012-09-07 07:55:26]

DBC

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

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1180: current->deopt_id_ =
last->GetDeoptId();
Could you add tests that have deoptimization caused by optimistic hoisting of
smi checks? Have you observed them on any of benchmarks?

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1223: phi->SetPropagatedCid(kSmiCid);
Could/should we run type propagation after LICM again?

[Florian Schneider, 2012-09-07 09:37:00]

LGTM.

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

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1160: void
LICM::Hoist(ForwardInstructionIterator* it,
You could make this a static top-level functions:

static void Hoist(...

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1184: void
LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it,
You could make this a static top-level functions:

static void TryHoist(...

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1193: if (phi->GetPropagatedCid() == kSmiCid)
{
It should not be necessary to check for redundant smi-checks here since they are
already eliminated in the Canonicalize pass. Right now, this pass is run before
LICM, but maybe we should do another round anyway later to catch secondary
effects.

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1216:
(phi->block()->PredecessorAt(non_smi_input) != pre_header)) {
It's fine to have the restrict the block where the smi-check will be inserted to
only the pre-header for now.

As an improvement, you could allow non-smi predecessors other than the
pre-header.

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1223: phi->SetPropagatedCid(kSmiCid);
On 2012/09/07 07:55:26, srdjan wrote:
> Could/should we run type propagation after LICM again?


Yes, how about building  worklist of changed phis and process the worklist after
LICM finished?

A later pass (OptimizeComputations) would eliminate checks that become redundant
as a secondary effect.

[Vyacheslav Egorov (Google), 2012-09-07 12:06:00]

thanks for the review.

added test. 

landing

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

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1160: void
LICM::Hoist(ForwardInstructionIterator* it,
On 2012/09/07 09:37:00, Florian Schneider wrote:
> You could make this a static top-level functions:
> 
> static void Hoist(...

Unfortunately I can't: it uses friendship relation to access private state.

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1180: current->deopt_id_ =
last->GetDeoptId();
On 2012/09/07 07:55:26, srdjan wrote:
> Could you add tests that have deoptimization caused by optimistic hoisting of
> smi checks? Have you observed them on any of benchmarks?

Done.

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1184: void
LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it,
On 2012/09/07 09:37:00, Florian Schneider wrote:
> You could make this a static top-level functions:
> 
> static void TryHoist(...

See above.

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1193: if (phi->GetPropagatedCid() == kSmiCid)
{
On 2012/09/07 09:37:00, Florian Schneider wrote:
> It should not be necessary to check for redundant smi-checks here since they
are
> already eliminated in the Canonicalize pass. Right now, this pass is run
before
> LICM, but maybe we should do another round anyway later to catch secondary
> effects.

There are might be smi checks that are not dominated or come from the outer loop
after smi in the inner loop was promoted to smi. 

This allows to remove them quickly without any special processing:

outer:
  inner:
    phi1 = phi(v0, v1)
    check-smi phi1
  check-smi phi1 ;; <- this phi

https://chromiumcodereview.appspot.com/10916155/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1223: phi->SetPropagatedCid(kSmiCid);
On 2012/09/07 09:37:00, Florian Schneider wrote:
> On 2012/09/07 07:55:26, srdjan wrote:
> > Could/should we run type propagation after LICM again?
> 
> 
> Yes, how about building  worklist of changed phis and process the worklist
after
> LICM finished?
> 
> A later pass (OptimizeComputations) would eliminate checks that become
redundant
> as a secondary effect.
> 

Yes, we can. For now I would like to keep it minimal to minimize impact on the
compile time.