Build and use stack maps in the SSA compiler.

Build and use stack maps in the SSA compiler.

Add a stack bitmap to the location summaries for calls that are GC
safepoints.  The bitmap covers the spill slots.  The register
allocator collects these bitmaps into a list and then marks live
pointer values during register allocation.  When emitting code for a
call, a heap-allocated stackmap is built.

BUG=

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

[Kevin Millikin (Google), 2012-08-10 11:08:51]

This passes all our tests, but our GC coverage could be better.

I know it needs some cleanup, but I'd like to get it committed so we can
identify stability problems.

I plan to replace the explicit BitmapBuilders with some sort of SafepointInfo
wrapper, and I plan to introduce wrappers for calls that correctly write the pc
descriptors and safepoints.

[siva, 2012-08-10 18:01:25]

DBC

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/stack_frame.cc
File runtime/vm/stack_frame.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/stack_frame...
runtime/vm/stack_frame.cc:90: visitor->VisitPointers(start_addr, end_addr);
I think this hybrid approach of having a stack map and treating outgoing
arguments specially is pretty confusing. It seems to spread the implementation
into multiple places and can normally leads to confusion.

I liked the earlier approach that a frame either has a stackmap which describes
it completely or just has pure tagged objects. That way the stack frame code
does not need to have any inbuilt knowledge about outgoing argument layout etc.

[Vyacheslav Egorov (Google), 2012-08-10 18:11:42]

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/stack_frame.cc
File runtime/vm/stack_frame.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/stack_frame...
runtime/vm/stack_frame.cc:90: visitor->VisitPointers(start_addr, end_addr);
On 2012/08/10 18:01:25, asiva wrote:
> I think this hybrid approach of having a stack map and treating outgoing
> arguments specially is pretty confusing. It seems to spread the implementation
> into multiple places and can normally leads to confusion.
> 
> I liked the earlier approach that a frame either has a stackmap which
describes
> it completely or just has pure tagged objects. That way the stack frame code
> does not need to have any inbuilt knowledge about outgoing argument layout
etc.

I agree that it might be a little bit confusing and that it might be beneficial
for the debugging to have a code that verifies stack frame size but it has a
solid reasoning behind it. Current calling convention mandates that all outgoing
parameters have to be tagged so all stack maps will have a sequence of 1s at the
end which does not have to be emitted if we accept that everything above spill
slots is an outgoing parameter (and thus is tagged).

Furthermore this decision greatly simplifies implementation because our IR is
not entirely uniform in its management of the stack: some instructions push
outgoing parameters (and sometimes a null to create a space for result!)
internally on the stack while others rely on compiler to generate PushArgument
instructions (end many PushArgument instructions are removed by the optimizer).
Refactoring at this point of time might not be entirely possible because
instructions are used by two different optimization pipelines.

[srdjan, 2012-08-10 23:11:05]

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:438: bool Covers(intptr_t pos) const;
Could you add a brief comment differentiating between 'CanCover' and 'Covers'?

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.h#ne...
runtime/vm/object.h:2455: void set_spill_slot_count(intptr_t count) const {
ASSERT(is_optimized()) ?

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/raw_object....
runtime/vm/raw_object.h:814: intptr_t spill_slot_count_;
Add comment what it means, when it is set.

[Vyacheslav Egorov (Google), 2012-08-13 12:54:46]

lgtm

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:525: for (intptr_t i = 0; i <
safepoints_.length(); ++i) {
Please move this code into a separate function.

It is duplicated in two places.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:224: struct Safepoint {
: public ValueObject ?

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:438: bool Covers(intptr_t pos) const;
I suggest renaming Covers to Contains to match naming of Contains in UseInterval
or maybe even AnySiblingContains()

Also please add comment as Srdjan suggested.

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler.cc:407: if (is_ssa() && (stack_bitmap != NULL)) {
we should make as hard as possible to pass NULLs from ssa pipeline here so that
instructions with no bitmap will not easily come here.

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:784: NULL);
This NULL looks suspicious to me because we already expanded the stack above and
now we can have some garbage in out frame . 

If this call causes GC it might see all kinds of wierdness in the frame.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:812: NULL);
This NULL looks suspicious to me because we already expanded the stack above and
now we can have some garbage in out frame . 

If this call causes GC it might see all kinds of wierdness in the frame.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:936: NULL);
This NULL looks suspicious to me because we already expanded the stack above and
now we can have some garbage in out frame . 

If this call causes GC it might see all kinds of wierdness in the frame.

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:790: NULL);
This NULL looks suspicious to me because we already expanded the stack above and
now we can have some garbage in out frame . 

If this call causes GC it might see all kinds of wierdness in the frame.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:818: NULL);
This NULL looks suspicious to me because we already expanded the stack above and
now we can have some garbage in out frame . 

If this call causes GC it might see all kinds of wierdness in the frame.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:943: NULL);
This NULL looks suspicious to me because we already expanded the stack above and
now we can have some garbage in out frame . 

If this call causes GC it might see all kinds of wierdness in the frame.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:1011: if (is_ssa() && (stack_bitmap !=
NULL)) {
I would prefer to have stack_bitmap always not equal to NULL with assertion.

All call sites should have some kind of bitmap.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language_ia32.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language_ia32.cc:95: locs()->stack_bitmap());
ReturnInstr is marked as NoCall. This code is suspicious.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language_x64.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language_x64.cc:95: NULL);
ReturnInstr is marked as NoCall. This code is suspicious.

NULL does not work here because spill slots are above us.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.cc#n...
runtime/vm/object.cc:6575: "0x%-*" PRIxPTR "\t%s\t%" PRIdPTR "\t%" PRIdPTR "\t%"
PRIdPTR "\n";
please add a comment about *

consider making a define to fold *PRIxPTR into a fixed width format modifier,
something like

#if X64
#  define PRIxPTRW "16" PRIxPTR 
#else
#  define PRIxPTRW "8" PRIxPTR 
#endif

[Kevin Millikin (Google), 2012-08-13 15:10:37]

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:525: for (intptr_t i = 0; i <
safepoints_.length(); ++i) {
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> Please move this code into a separate function.
> 
> It is duplicated in two places.

OK.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:224: struct Safepoint {
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> : public ValueObject ?

Nah.  The comment in that class indicates that ValueObject is not intended to be
passed by value.  :)

A minor issue is that it would no longer be POD (ValueObject has a user-defined
constructor) so I'd have to write a silly constructor here.

I think I'll probably introduce a SafepointInfo class that wraps this and hides
the bitmap builder as part of a future cleanup, anyway.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:438: bool Covers(intptr_t pos) const;
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> I suggest renaming Covers to Contains to match naming of Contains in
UseInterval
> or maybe even AnySiblingContains()
> 
> Also please add comment as Srdjan suggested.

Done.

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler.cc:407: if (is_ssa() && (stack_bitmap != NULL)) {
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> we should make as hard as possible to pass NULLs from ssa pipeline here so
that
> instructions with no bitmap will not easily come here.

Agreed.  I think we'll actually want to just make it non-NULL, even if we have a
few special (constant or nearly so) bitmaps describing the prologue etc.

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:784: NULL);
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> This NULL looks suspicious to me because we already expanded the stack above
and
> now we can have some garbage in out frame . 
> 
> If this call causes GC it might see all kinds of wierdness in the frame.

Yes, it's an existing problem.  We should be able to fix it with stackmaps.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:812: NULL);
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> This NULL looks suspicious to me because we already expanded the stack above
and
> now we can have some garbage in out frame . 
> 
> If this call causes GC it might see all kinds of wierdness in the frame.

Agreed.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:936: NULL);
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> This NULL looks suspicious to me because we already expanded the stack above
and
> now we can have some garbage in out frame . 
> 
> If this call causes GC it might see all kinds of wierdness in the frame.

Agreed.

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

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:1011: if (is_ssa() && (stack_bitmap !=
NULL)) {
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> I would prefer to have stack_bitmap always not equal to NULL with assertion.
> 
> All call sites should have some kind of bitmap.

I agree completely.  With this change we fall back on the existing behavior for
those points, which at least should not introduce new bugs.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language_ia32.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language_ia32.cc:95: locs()->stack_bitmap());
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> ReturnInstr is marked as NoCall. This code is suspicious.

I know.  We really don't want it to be a call because it's pointless to do any
work spilling before return.  Let's see if we can defer the call in the same way
as we plan to do with the stack check.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.cc#n...
runtime/vm/object.cc:6575: "0x%-*" PRIxPTR "\t%s\t%" PRIdPTR "\t%" PRIdPTR "\t%"
PRIdPTR "\n";
On 2012/08/13 12:54:46, Vyacheslav Egorov (Google) wrote:
> please add a comment about *
> 
> consider making a define to fold *PRIxPTR into a fixed width format modifier,
> something like
> 
> #if X64
> #  define PRIxPTRW "16" PRIxPTR 
> #else
> #  define PRIxPTRW "8" PRIxPTR 
> #endif

Blah.  I'd rather use vanilla printf specifiers than invent our own wrappers. 
I'll add a comment, though.

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/object.h#ne...
runtime/vm/object.h:2455: void set_spill_slot_count(intptr_t count) const {
On 2012/08/10 23:11:05, srdjan wrote:
> ASSERT(is_optimized()) ?

Hmmm.  It's called for unoptimized code to set it to zero (maybe -1 is better).

Is there a better way than using the accessor to initialize it for unoptmized
code?

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

https://chromiumcodereview.appspot.com/10831261/diff/1/runtime/vm/raw_object....
runtime/vm/raw_object.h:814: intptr_t spill_slot_count_;
On 2012/08/10 23:11:05, srdjan wrote:
> Add comment what it means, when it is set.

Done.