Assign bailout and type feedback IDs in a post-pass

Assign bailout and type feedback IDs in a post-pass

This will allow us to move expressions from one function to another, for
example when the parser determines that a given cover grammar instance
is actually the default value initializer for an arrow function.

R=svenpanne@chromium.org, marja@chromium.org
BUG=

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

[wingo, 2014-10-13 14:09:09]

Here's a patch to move assignment of bailout/feedback IDs to a post-pass.

Some initial perf discussions:
https://groups.google.com/d/msg/v8-dev/zz2YMlxxaKM/OVNJWqvkovEJ

The actual perf on this is a little better than the mail makes it out to be:
486.00M instructions, compared 487.57M instructions with an "empty" post-pass. 
The baseline is 479.55M before the patch.

Time-wise I can't measure in the same way as we need to assign bailout IDs after
all AST mutations have occurred, so after rewriting and scope analysis.  However
if I run the jquery-parsing-test.js benchmark through d8 with --no-lazy, and
time its runtime using bash's time, do it 100 times and take the best, then the
"before" time is 0.122s and the "after" time is 0.128s.  So still a regression.

What do you think, Marja?  Is this somehow within the realms of possibility?

[marja, 2014-10-13 14:44:55]

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc
File src/ast-numbering.cc (right):

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode256
src/ast-numbering.cc:256: if (visitor.HasStackOverflow()) return false;
Hmm, when can stack overflow happen here?

https://codereview.chromium.org/636403003/diff/1/test/cctest/test-ast.cc
File test/cctest/test-ast.cc (right):

https://codereview.chromium.org/636403003/diff/1/test/cctest/test-ast.cc#newc...
test/cctest/test-ast.cc:43: AstNode::IdGen id_gen;
id_gen now unused

[wingo, 2014-10-13 15:47:24]

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc
File src/ast-numbering.cc (right):

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode256
src/ast-numbering.cc:256: if (visitor.HasStackOverflow()) return false;
On 2014/10/13 14:44:55, marja wrote:
> Hmm, when can stack overflow happen here?

In the ast.h AstVisitor definition:

#define DEFINE_AST_VISITOR_SUBCLASS_MEMBERS()                       \
public:                                                             \
  virtual void Visit(AstNode* node) FINAL OVERRIDE {          \
    if (!CheckStackOverflow()) node->Accept(this);                  \
  }                                                                 \

[marja, 2014-10-13 15:56:26]

Alright, turns out things related to the bailout IDs have changed a lot since we
last discussed!

... and this work might not be needed at all.

Somebody who has more insight into the changes (svenpanne, dslomov or rossberg)
needs to discuss this with you before moving forward.

[Sven Panne, 2014-10-14 06:56:26]

svenpanne@chromium.org changed reviewers:
+ svenpanne@chromium.org

[Sven Panne, 2014-10-14 06:56:27]

Could you please explain how this is supposed to work? As it is, I don't
understand it. Previously things were very simple: For all classes with IDs,
base_id() tells you where the range of num_ids() start, and all of the logic was
local. This should not change even if we do this in a separate pass.

https://codereview.chromium.org/636403003/diff/1/src/ast.h
File src/ast.h (right):

https://codereview.chromium.org/636403003/diff/1/src/ast.h#newcode411
src/ast.h:411: int leaf_base_id() const { return base_id() + 2; }
I don't understand what leaf_base_id() should do. Why do we need both base_id()
and leaf_base_id()? And what is the "+ 2"? Is it actually "+ kBailoutIdCount"?
This is highly confusing...

[Sven Panne, 2014-10-14 06:59:43]

Another hint: Whenever you change something deopt-related, please run the deopt
fuzzer, e.g.:

   ./tools/run-deopt-fuzzer.py --mode optdebug --arch ia32
--distribution-mode=random --coverage=0.4

(you could even bump the coverage to 0.5 or 0.6)

[wingo, 2014-10-14 07:32:38]

On 2014/10/14 06:56:27, Sven Panne wrote:
> Could you please explain how this is supposed to work? As it is, I don't
> understand it. Previously things were very simple: For all classes with IDs,
> base_id() tells you where the range of num_ids() start, and all of the logic
was
> local. This should not change even if we do this in a separate pass.

After this patch, the situation is exactly the same: base_id() tells you where
the ids for a given class start, except that there is no num_ids() function.

The difference is that instead of adding up id counts for each class node in a
type hierarchy (i.e. num_ids() for each type) to get the total number of nodes
to reserve, this patch reserves ids using a similar mechanism as the one that
objects.h uses to reserve slots in HeapObjects: kBailoutIdCount is the
cumulative number of ids to reserve, and every subclass adds on their slots to
the parent.

> https://codereview.chromium.org/636403003/diff/1/src/ast.h
> File src/ast.h (right):
> 
> https://codereview.chromium.org/636403003/diff/1/src/ast.h#newcode411
> src/ast.h:411: int leaf_base_id() const { return base_id() + 2; }
> I don't understand what leaf_base_id() should do. Why do we need both
base_id()
> and leaf_base_id()?

leaf_base_id() is defined by non-final types with bailout ids.  It is the
base_id that direct subclasses should use.

> And what is the "+ 2"? Is it actually "+ kBailoutIdCount"?

No.  kBailoutIdCount is cumulative, like JSObject::kSize.

[Sven Panne, 2014-10-14 11:06:00]

Just a few more quick remarks. I still don't understand why we suddenly need 5
things per node (AllocateBailoutIdRange, InitializeBaseBailoutId, base_id,
leaf_base_id, kBailoutIdCount) instead of the 2 before (base_id, num_ids), so
please don't land it yet.

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc
File src/ast-numbering.cc (right):

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode24
src/ast-numbering.cc:24: #define DEFINE_VISIT(type)                  \
I don't like this 2nd order macro horror, although I understand the motivation
behind it: Separating the recursion scheme from the actual logic per node.

As it is, it obfuscates things more than it helps, so just directly implement
all those VisitFoo directly (where Foo is an AST node type). This takes 10
minutes more to write and saves 10h reading the code later.

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode250
src/ast-numbering.cc:250: bool AstNumbering::Renumber(CompilationInfo* info) {
This is coupled too tightly: Just pass in the FunctionLiteral. It's a pity that
we need the zone in addition (only to get the Isolate and that only for the
stack check :-P ), but that's just the 2nd parameter then.

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode256
src/ast-numbering.cc:256: if (visitor.HasStackOverflow()) return false;
return !visitor.HasStackOverflow();

[marja, 2014-10-14 11:08:36]

marja@chromium.org changed reviewers:
+ dslomov@chromium.org

[marja, 2014-10-14 11:08:37]

dslomov@ had some alternative ideas on how to do the numbering, pls don't land
before syncing with him.

[marja, 2014-10-14 11:10:00]

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc
File src/ast-numbering.cc (right):

https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode24
src/ast-numbering.cc:24: #define DEFINE_VISIT(type)                  \
On 2014/10/14 11:06:00, Sven Panne wrote:
> I don't like this 2nd order macro horror, although I understand the motivation
> behind it: Separating the recursion scheme from the actual logic per node.
> 
> As it is, it obfuscates things more than it helps, so just directly implement
> all those VisitFoo directly (where Foo is an AST node type). This takes 10
> minutes more to write and saves 10h reading the code later.

Acutally, I think it's silly that all visitors need to implement the recursive
AST walking themselves. Can't we have it implemented in one place (in the
superclass) and if the actual visitors want to  do something else than just
visit children, they'd need to override the corresponding func?

[Sven Panne, 2014-10-14 11:37:11]

On 2014/10/14 11:10:00, marja wrote:
> Acutally, I think it's silly that all visitors need to implement the recursive
> AST walking themselves.

That's the silliness of the visitor pattern. :-)

> Can't we have it implemented in one place (in the
> superclass) and if the actual visitors want to  do something else than just
> visit children, they'd need to override the corresponding func?

Things get a bit tricky, because in general you would need hooks for the various
points in the recursion for every node type. If you look e.g. at the pretty
printer:

---------------------------------------------------------------------
void PrettyPrinter::VisitIfStatement(IfStatement* node) {
  Print("if (");
  Visit(node->condition());
  Print(") ");
  Visit(node->then_statement());
  if (node->HasElseStatement()) {
    Print(" else ");
    Visit(node->else_statement());
  }
}
---------------------------------------------------------------------

Note that the recursion (the various calls to Visit) is deeply nested into the
logic of what to do at an IfStatement (the 3 Print calls, actually a 4th one
could be there for an empty else clause). This means that you would need 4 calls
to (virtual) hooks for the IfStatement alone. The pretty printer would override
3, while the renumbering pass would only override 1. Not sure if this is a big
win. The visitor pattern is verbose, but there's no easy way around this in C++.

[wingo, 2014-10-14 12:20:30]

On 2014/10/14 11:06:00, Sven Panne wrote:
> Just a few more quick remarks. I still don't understand why we suddenly need 5
> things per node (AllocateBailoutIdRange, InitializeBaseBailoutId, base_id,
> leaf_base_id, kBailoutIdCount) instead of the 2 before (base_id, num_ids), so
> please don't land it yet.

Yeah I know what you mean.  So before there were actually three things: you also
had the constructors chaining the num_ids_for_subclass through to whatever base
class allocated the base_id_.  To replace chaining we have kBailoutIdCount.  To
replace the initializer in the base constructors we have
InitializeBaseBailoutId.  I'd rather put AllocateBailoutIdRange in
AstNumberingVisitor but base_id_ is protected; perhaps we mark
AstNumberingVisitor as a friend class?

Then we're left with leaf_base_id(), which is weird.  I'd rather replace uses of
it with "base_id_ + super::kBailoutIdCount", for appropriate values of super,
but that only works if base_id_ has been initialized.  Instead in this patch it
uses base_id() (which isn't base_id_ ... :/) in order to take advantage of the
assertion there.

Dunno, if the general approach is sound then we can try to reduce the number of
moving parts here.

> https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc
> File src/ast-numbering.cc (right):
> 
>
https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode24
> src/ast-numbering.cc:24: #define DEFINE_VISIT(type)                  \
> I don't like this 2nd order macro horror, although I understand the motivation
> behind it: Separating the recursion scheme from the actual logic per node.
> 
> As it is, it obfuscates things more than it helps, so just directly implement
> all those VisitFoo directly (where Foo is an AST node type). This takes 10
> minutes more to write and saves 10h reading the code later.

ACK.

>
https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode250
> src/ast-numbering.cc:250: bool AstNumbering::Renumber(CompilationInfo* info) {
> This is coupled too tightly: Just pass in the FunctionLiteral. It's a pity
that
> we need the zone in addition (only to get the Isolate and that only for the
> stack check :-P ), but that's just the 2nd parameter then.

ACK.

>
https://codereview.chromium.org/636403003/diff/1/src/ast-numbering.cc#newcode256
> src/ast-numbering.cc:256: if (visitor.HasStackOverflow()) return false;
> return !visitor.HasStackOverflow();

ACK.

[wingo, 2014-10-14 17:21:02]

Patchset #2 (id:250001) has been deleted

[wingo, 2014-10-14 17:22:03]

Updated a new changeset addressing feedback; ptal :)

I haven't fuzzed it or run the the chromium tests on it yet.

[Sven Panne, 2014-10-15 07:41:56]

https://codereview.chromium.org/636403003/diff/270001/src/ast-numbering.h
File src/ast-numbering.h (right):

https://codereview.chromium.org/636403003/diff/270001/src/ast-numbering.h#new...
src/ast-numbering.h:13: class AstNumbering {
This is not really a class, using a namespace might be more honest.

https://codereview.chromium.org/636403003/diff/270001/src/ast-numbering.h#new...
src/ast-numbering.h:15: // Assign type feedback IDs, bailout IDs, and other
state to an AST node
Remove the "and other state" part for now.

https://codereview.chromium.org/636403003/diff/270001/src/ast-numbering.h#new...
src/ast-numbering.h:19: // failure.
Actually, this is not true: We just failed to set the IDs, nothing else should
have been damaged.

https://codereview.chromium.org/636403003/diff/270001/src/ast.h
File src/ast.h (right):

https://codereview.chromium.org/636403003/diff/270001/src/ast.h#newcode379
src/ast.h:379: base_id_(INT_MIN) {}
Hmmm, INT_MIN is a bit ugly, I think just using -1 (or
BailoutId::None().ToInt()) here and adding

   static_asssert<kNoneId < 0, "kNoneId must be negative">

to the TypeFeedbackId and BailoutId classes is a bit better. Forcing
TypeFeedbackId and BailoutId to have a common superclass containing None() etc.
doesn't sound right, either.

Another option is simply not doing the initialization at all (and remove the
DCHECK below) and rely on our tooling to find uninitialized access (ASAN will do
this).

https://codereview.chromium.org/636403003/diff/270001/src/compiler.cc
File src/compiler.cc (right):

https://codereview.chromium.org/636403003/diff/270001/src/compiler.cc#newcode644
src/compiler.cc:644: if (!AstNumbering::Renumber(info->function(),
info->zone())) return false;
Not a fault of this CL, but we should *really, really* try to unify all those
compilation pipeline fragments, so that there is a single place for this. But
this should not be done in this CL...

https://codereview.chromium.org/636403003/diff/270001/src/parser.cc
File src/parser.cc (right):

https://codereview.chromium.org/636403003/diff/270001/src/parser.cc#newcode882
src/parser.cc:882: zone(), ast_value_factory());
A nice little cleanup which could be done on the way: Remove the Zone* argument
from the AstNodeFactory, the zone can (and should!) be retrieved fromt the
AstValueFactory (add a getter there). It simply doesn't make sense to pretend
that AST nodes and AST values can live in different zones.

[wingo, 2014-10-15 13:53:19]

Fixed nits.

https://codereview.chromium.org/636403003/diff/270001/src/ast-numbering.h
File src/ast-numbering.h (right):

https://codereview.chromium.org/636403003/diff/270001/src/ast-numbering.h#new...
src/ast-numbering.h:13: class AstNumbering {
On 2014/10/15 07:41:56, Sven Panne wrote:
> This is not really a class, using a namespace might be more honest.

Done.

https://codereview.chromium.org/636403003/diff/270001/src/ast.h
File src/ast.h (right):

https://codereview.chromium.org/636403003/diff/270001/src/ast.h#newcode379
src/ast.h:379: base_id_(INT_MIN) {}
Done.  I kept the initialization as the check helps during development --
otherwise it's easy for an AST change to bork because you didn't change the
corresponding place in ast-numbering.cc.

https://codereview.chromium.org/636403003/diff/270001/src/parser.cc
File src/parser.cc (right):

https://codereview.chromium.org/636403003/diff/270001/src/parser.cc#newcode882
src/parser.cc:882: zone(), ast_value_factory());
On 2014/10/15 07:41:56, Sven Panne wrote:
> A nice little cleanup which could be done on the way: Remove the Zone*
argument
> from the AstNodeFactory, the zone can (and should!) be retrieved fromt the
> AstValueFactory (add a getter there). It simply doesn't make sense to pretend
> that AST nodes and AST values can live in different zones.

Done.

[wingo, 2014-10-15 14:04:14]

On 2014/10/14 06:59:43, Sven Panne wrote:
> Another hint: Whenever you change something deopt-related, please run the
deopt
> fuzzer, e.g.:
> 
>    ./tools/run-deopt-fuzzer.py --mode optdebug --arch ia32
> --distribution-mode=random --coverage=0.4
> 
> (you could even bump the coverage to 0.5 or 0.6)

Good tip!  There are some failures that I will fix.

[wingo, 2014-10-20 11:20:19]

Patchset #4 (id:310001) has been deleted

[wingo, 2014-10-20 11:23:58]

Patchset #4 (id:330001) has been deleted

[wingo, 2014-10-20 11:32:10]

Turns out in the previous version I was doing an n² traversal -- it was
recursing into nested functions, always.  I fixed this, and also fixed some
cases where it wasn't reaching all the AST nodes that needed reaching, also in
cases involving invalid redeclarations.  Finally I moved the Renumber() for the
full-codegen case into FullCodegen::MakeCode, as there are a few ways to get
there.

The end result here is that now the time for my --no-lazy benchmark is 0.124s,
rather than 0.128 before (and compared to 0.122 before the patch).  I'm running
the fuzzer now but I think everything's going to go well, and these new numbers
are close enough that I think we can probably land directly.  WDYT?

[wingo, 2014-10-20 13:55:04]

Patchset 4 is just patchset 3, rebased.

[wingo, 2014-10-20 13:57:38]

On 2014/10/20 13:55:04, wingo wrote:
> Patchset 4 is just patchset 3, rebased.

Er, um.  I obviously meant patchset 5 is patchset 4, rebased.

[rossberg, 2014-10-20 14:20:14]

On 2014/10/20 11:32:10, wingo wrote:
> The end result here is that now the time for my --no-lazy benchmark is 0.124s,
> rather than 0.128 before (and compared to 0.122 before the patch).  I'm
running
> the fuzzer now but I think everything's going to go well, and these new
numbers
> are close enough that I think we can probably land directly.  WDYT?

This is great stuff, I'll let Sven do the review.

But independent from that, I still think we need a few measurements on real
benchmark suites before landing this.

[Sven Panne, 2014-10-21 07:03:41]

LGTM, I can land this when we have some performance numbers and the fuzzer is
happy.

[Sven Panne, 2014-10-21 08:51:21]

The benchmarks look OK, I can't see any regression (in all that noise :-P ), so
I'll land it and see if I can reduce the amount of pipeline duplication a bit.
That's really getting out of hands...

[Sven Panne, 2014-10-21 08:52:57]

Committed patchset #5 (id:370001) manually as 24757 (presubmit successful).

[Sven Panne, 2014-10-21 10:51:41]

I'll have to revert this, it breaks the ARM64 simulator build. Simple repro:

out/arm64.debug/d8 -e 'eval("(function(){ const x; var x; })")'

[wingo (chromium), 2014-10-21 11:04:06]

On 2014/10/21 10:51:41, Sven Panne wrote:
> I'll have to revert this, it breaks the ARM64 simulator build. Simple repro:
> 
> out/arm64.debug/d8 -e 'eval("(function(){ const x; var x; })")'

whoops -- will fix and resubmit.  thanks for the help and sorry for the noise!