Initial support for polymorphic inlining.

Initial support for polymorphic inlining.

Consider each polymorphic variant separately for inlining in frequency
order.  Share inlined bodies for shared targets.

Insert an SSA redefinition of the receiver in each inlined variant to
prevent hoisting.  Hoisting code specialized to the receiver (e.g.,
direct access to internal fields of typed data arrays) out of the
inlined body is not safe.

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

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

[Kevin Millikin (Google), 2013-05-01 15:36:24]

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_allocat...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_allocat...
runtime/vm/flow_graph_allocator.cc:2191: ASSERT(false);
This is unintentional.  I will remove it.

[srdjan, 2013-05-02 20:06:30]

LGTM with Florian's LGTM.
Please run the tests with optimization-counter-threshold=5

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner.cc
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:978: bool
PolymorphicInliner::CheckNonInlinedDuplicate(const Function& target) {
Maybe give it a name that better suits a Boolean result.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1008: // hoisted above the inlined entry.
Could you briefly explain (as comment to the CL) situation where hoisting is
damaging?

https://codereview.chromium.org/14740005/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_ia32.cc:1126: __ testl(object,
Immediate(kSmiTagMask));
We may be able to determine that object is never Smi (e.g., receiver of a class
that is outside the number chain). In that case we could generate better code.

[Florian Schneider, 2013-05-03 10:41:36]

LGTM.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph.cc#newc...
runtime/vm/flow_graph.cc:850: void FlowGraph::RemoveRedefinitions() {
This is very similar to what we do with ConstraintInstr after array bounds check
elimination. Could you share the code?

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_allocat...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_allocat...
runtime/vm/flow_graph_allocator.cc:2191: ASSERT(false);
On 2013/05/01 15:36:25, kmillikin wrote:
> This is unintentional.  I will remove it.

I think this is actually useful for debugging here.

maybe UNREACHABLE() instead?

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner.cc
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:295: public:
struct has public as default.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:947: block->set_dominator(new_join);
Since set_dominator is always coupled with a following AddDominatedBlock,
consider adding a function that does both to BlockEntryInstr.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1064: cursor->LinkTo(load_cid);
This pattern of appending to the cursor is used a couple of times: You could use
a helper that does AddInputUse, LinkTo and possibly updating the cursor :

load_cid->AppendTo(&cursor);

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1218: 1));
Line-end comment: // Number of args tested.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1227: true);
// Line-end comment: With checks.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3622: virtual bool
AttributesEqual(Instruction* other) const { return true; }
This instructions could have AllowsCSE true, and Dependencies  set properly:
 
virtual EffectSet Dependencies() const { return EffectSet::Externalization(); }
virtual bool AllowsCSE() const { return true; }

[Kevin Millikin (Google), 2013-05-03 11:47:38]

Thanks for the review.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph.cc#newc...
runtime/vm/flow_graph.cc:850: void FlowGraph::RemoveRedefinitions() {
On 2013/05/03 10:41:36, Florian Schneider wrote:
> This is very similar to what we do with ConstraintInstr after array bounds
check
> elimination. Could you share the code?

That one uses a maintained list of constraints, this one searches in the graph
for redefinitions.  I don't really want to maintain a list of redefinitions in
the graph as part of this change, so I'll leave it as is.

However, it does point out a bug in this code: it does not properly handle
redefinitions of redefinitions and nothing prevents them from arising.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_allocat...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_allocat...
runtime/vm/flow_graph_allocator.cc:2191: ASSERT(false);
On 2013/05/03 10:41:36, Florian Schneider wrote:
> On 2013/05/01 15:36:25, kmillikin wrote:
> > This is unintentional.  I will remove it.
> 
> I think this is actually useful for debugging here.
> 
> maybe UNREACHABLE() instead?

OK, UNREACHABLE() it is.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner.cc
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:295: public:
On 2013/05/03 10:41:36, Florian Schneider wrote:
> struct has public as default.

I know, but it certainly doesn't hurt.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:947: block->set_dominator(new_join);
On 2013/05/03 10:41:36, Florian Schneider wrote:
> Since set_dominator is always coupled with a following AddDominatedBlock,
> consider adding a function that does both to BlockEntryInstr.

OK.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:978: bool
PolymorphicInliner::CheckNonInlinedDuplicate(const Function& target) {
On 2013/05/02 20:06:30, srdjan wrote:
> Maybe give it a name that better suits a Boolean result.

Suggestions?

I called it this way to parallel CheckInlinedDuplicate.  And I called that one
that way because the emphasis should be on the computation (and mutation) that
it does and not on the value.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1064: cursor->LinkTo(load_cid);
On 2013/05/03 10:41:36, Florian Schneider wrote:
> This pattern of appending to the cursor is used a couple of times: You could
use
> a helper that does AddInputUse, LinkTo and possibly updating the cursor :
> 
> load_cid->AppendTo(&cursor);

I'll come up with something.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1218: 1));
On 2013/05/03 10:41:36, Florian Schneider wrote:
> Line-end comment: // Number of args tested.

OK.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1227: true);
On 2013/05/03 10:41:36, Florian Schneider wrote:
> // Line-end comment: With checks.

OK.

https://codereview.chromium.org/14740005/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/14740005/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3622: virtual bool
AttributesEqual(Instruction* other) const { return true; }
On 2013/05/03 10:41:36, Florian Schneider wrote:
> This instructions could have AllowsCSE true, and Dependencies  set properly:
>  
> virtual EffectSet Dependencies() const { return EffectSet::Externalization();
}
> virtual bool AllowsCSE() const { return true; }

Ouch, good catch.  That was the intent, but CSE infrastructure changed while
this CL was in flight.  I'll fix it.

[Kevin Millikin (Google), 2013-05-06 17:22:37]

Committed patchset #2 manually as r22434 (presubmit successful).