Fast codegen: Working break and continue.

Fast codegen: Working break and continue.
Started framework for all intra-functional outward control transfers,
including handling of try/finally.

[Kevin Millikin (Chromium), 2009-12-07 14:27:35]

As we discussed, we might try some variation of NestingStack or
NestingEnvironment as a name.

http://codereview.chromium.org/466033/diff/1/2
File src/arm/fast-codegen-arm.cc (right):

http://codereview.chromium.org/466033/diff/1/2#newcode41
src/arm/fast-codegen-arm.cc:41: // TODO(lrn) - set the constant when
implementing finally.
I don't understand the TODO.  I don't understand why this constant is
platform-dependent.

Even if it has to be platform independent, it should be in the header file.

http://codereview.chromium.org/466033/diff/1/3
File src/arm/macro-assembler-arm.cc (right):

http://codereview.chromium.org/466033/diff/1/3#newcode166
src/arm/macro-assembler-arm.cc:166: ASSERT(stack_elements < (1 << (30 -
kPointerSizeLog2)));
I don't understand the purpose of the assert.  It's too magic to not have a
comment.

http://codereview.chromium.org/466033/diff/1/6
File src/fast-codegen.cc (right):

http://codereview.chromium.org/466033/diff/1/6#newcode235
src/fast-codegen.cc:235: 
This blank line is surely not necessary.

http://codereview.chromium.org/466033/diff/1/6#newcode237
src/fast-codegen.cc:237: 
Likewise.

http://codereview.chromium.org/466033/diff/1/6#newcode238
src/fast-codegen.cc:238: BreakTargetEnvironment break_env(stmt, &end_of_block);
All these classes have the protocol (1) construct, immediately (2) push on
environment_, bracketed by (3) pop.  Perfect candidate for RAII so you just
write:

Break break_target(this, stmt, &end_of_block);
VisitStatements(stmt->statements());
__ bind(&end_of_block);

http://codereview.chromium.org/466033/diff/1/6#newcode241
src/fast-codegen.cc:241: SetStatementPosition(stmt);
Not your code, but I wonder why we SetStatementPosition here.

http://codereview.chromium.org/466033/diff/1/6#newcode326
src/fast-codegen.cc:326: int target_offset =
environment_.FindContinueTargetOffset(stmt->target());
The int seems like it doesn't need to be exposed in the API.  Consider combining
into a single function that searches and exits.

http://codereview.chromium.org/466033/diff/1/7
File src/fast-codegen.h (right):

http://codereview.chromium.org/466033/diff/1/7#newcode42
src/fast-codegen.h:42: // Environments (or scopes) of special significance.
Terminology throughout needs tweaking.  These are not "environments" (they don't
map anything to anything) and they're not "scopes" in any way connected to JS.

They're all statements or blocks.

Idea: just use "Break", "Continue", "TryCatch", "TryFinally", "Finally", "ForIn"
and make them subclasses of the codegenerator to give yourself a namespace.

http://codereview.chromium.org/466033/diff/1/7#newcode52
src/fast-codegen.h:52: class EnvironmentEntry {
It seems strange that an "XXXEnvironment" is a subclass of "EnvironmentEntry".

Also, BASE_EMBEDDED please.

http://codereview.chromium.org/466033/diff/1/7#newcode56
src/fast-codegen.h:56: virtual bool IsReturnTarget() { return false; }
Having both the IsXXX() and AsXXX style of cast operators seeems like overkill
for such a simple utility class.

http://codereview.chromium.org/466033/diff/1/7#newcode92
src/fast-codegen.h:92: ContinueTargetEnvironment(IterationStatement*
continue_statement,
Bad name.  If it's an IterationStatement it's definitely not a continue
statement.

http://codereview.chromium.org/466033/diff/1/7#newcode162
src/fast-codegen.h:162: class ReturnTargetEnvironment : public EnvironmentEntry
{
I would make the return implicit.  It's always and only the last element of the
(reversed) list and has no fields.

http://codereview.chromium.org/466033/diff/1/7#newcode173
src/fast-codegen.h:173: class Environment {
Instead of a separate ZoneList of pointers to stack-allocated objects, I'd just
thread the objects through the stack with a pointer in each.

Probably just because I hate ZoneList.

http://codereview.chromium.org/466033/diff/1/7#newcode262
src/fast-codegen.h:262: environment_(),
No need.

http://codereview.chromium.org/466033/diff/1/11
File src/x64/fast-codegen-x64.cc (right):

http://codereview.chromium.org/466033/diff/1/11#newcode158
src/x64/fast-codegen-x64.cc:158: ReturnTargetEnvironment return_env;
I wonder why the other platforms don't need this?

[William Hesse, 2009-12-08 01:46:59]

http://codereview.chromium.org/466033/diff/1/6
File src/fast-codegen.cc (right):

http://codereview.chromium.org/466033/diff/1/6#newcode235
src/fast-codegen.cc:235: 
I wrote a big comment here, but I came to the conclusion that this design is OK,
as long as the EnvironmentEffect subclasses are created automatically on the
stack, and destroyed automatically, removing themselves from the list.

But is this possible?  The head of the list of environments, which you have in
environment_, but needs to be just somewhere in the codegen, can be passed to
the constructor of the object, but to remove the object from the list, and
restore the saved parent environment, in the destructor of the
BreakTargetEnvironment, requires a pointer to codegen or to Environment in
the BreakTargetEnvironment object (or a safe static access to the current
codegen). That puts a dumb pointer to the codegen in every
BreakTargetEnvironment.

http://codereview.chromium.org/466033/diff/1/6#newcode238
src/fast-codegen.cc:238: BreakTargetEnvironment break_env(stmt, &end_of_block);
On 2009/12/07 14:27:36, Kevin Millikin wrote:
> All these classes have the protocol (1) construct, immediately (2) push on
> environment_, bracketed by (3) pop.  Perfect candidate for RAII so you just
> write:
> 
Yes, exactly.
> Break break_target(this, stmt, &end_of_block);
> VisitStatements(stmt->statements());
> __ bind(&end_of_block);

http://codereview.chromium.org/466033/diff/1/6#newcode245
src/fast-codegen.cc:245: environment_.Drop(1);
To be more clear, this command is hard to do in the destructor of
BreakTargetEnvironment, unless it has a pointer to environment_ or codegen.

http://codereview.chromium.org/466033/diff/1/6#newcode307
src/fast-codegen.cc:307: __ Call(current->AsTryFinally()->finally_entry());
The introduction of Call(Label*) seems really dangerous to me. If we were
calling to a label in the old codegen, it was as part of making an
exception-handler item on the stack, I think.  Putting an address on the stack
is really dangerous to the GC, isn't it?  The introduction of Call in the
assembler makes it look like it is safe to call to someplace other than the
beginning of a code object.  If this code isn't doing exactly what the old code
did, I doubt it is safe, and if it is, it should have warnings on the use of
Call(Label).
Am I misunderstanding this?

http://codereview.chromium.org/466033/diff/1/6#newcode333
src/fast-codegen.cc:333: int target_offset =
environment_.FindBreakTargetOffset(stmt->target());
There is a potential n^2 behavior here, but we are probably okay with that,
right?  Any problem about the number of nested scopes times the number of breaks
that break them all is allowed to be there, I suppose.

http://codereview.chromium.org/466033/diff/1/7
File src/fast-codegen.h (right):

http://codereview.chromium.org/466033/diff/1/7#newcode173
src/fast-codegen.h:173: class Environment {
On 2009/12/07 14:27:36, Kevin Millikin wrote:
> Instead of a separate ZoneList of pointers to stack-allocated objects, I'd
just
> thread the objects through the stack with a pointer in each.
> 
> Probably just because I hate ZoneList.

Are you saying that, for example, VisitIterationStatement would have an
automatic (local, stack-allocated)
ContinueTargetEnvironment object, that would be placed on Environment.stack_ by
its constructor, and removed by its destructor?
That seems quite reasonable.  (Environment.stack_ would just be the top of the
linked list, and the links are in the objects, or this would just be
FastCodeGenerator::environment_stack.  How about "NestedStackUser" instead of
"Environment".  Or StackStuff.  StackDisciplinedStuff?  RuntimeStackMarker? 
longjump_target_?

http://codereview.chromium.org/466033/diff/1/7#newcode330
src/fast-codegen.h:330: void ExitEnvironments(int count);
Does ExitEnvironments actually leave the environments, and remove them from the
Environment stack, or does it emit runtime code to remove those environments'
stack-allocated slots on one runtime control flow path (probably followed by a
jump)?

http://codereview.chromium.org/466033/diff/1/11
File src/x64/fast-codegen-x64.cc (right):

http://codereview.chromium.org/466033/diff/1/11#newcode521
src/x64/fast-codegen-x64.cc:521: int return_offset =
environment_.FindReturnOffset();
This can't be right in the case of try-finally.  Should at least a TODO be put
here so that this is fixed when try-finally is added?

[Lasse Reichstein, 2009-12-09 10:25:13]

Addressed comments, please re-review.

http://codereview.chromium.org/466033/diff/1/2
File src/arm/fast-codegen-arm.cc (right):

http://codereview.chromium.org/466033/diff/1/2#newcode41
src/arm/fast-codegen-arm.cc:41: // TODO(lrn) - set the constant when
implementing finally.
Premature optimization (or complexification, as it may be).
It does turn out that the same value works for all platforms (and it should,
it's the same logical information that is stored).
There are no platform-specific header files, and I wanted to avoid a #ifdef-mess
in fast-codegen.h. 

On second thought, it seems the Finally and ForIn environment classes would be a
better location for the values, especially if the code to remove the stack
elements are moved to those classes as well.

http://codereview.chromium.org/466033/diff/1/3
File src/arm/macro-assembler-arm.cc (right):

http://codereview.chromium.org/466033/diff/1/3#newcode166
src/arm/macro-assembler-arm.cc:166: ASSERT(stack_elements < (1 << (30 -
kPointerSizeLog2)));
Just trying to avoid overflowing in the stack_elements * kPointerSize below. 
However, the argument size becomes ridiculous much earlier (the size of the
stack is likely to be 2MB at most).

I'll just remove the assert. There are so many ways to shoot yourself in the
foot using assembler, if you don't know what you are doing, that one very
permissive test won't make a difference.

http://codereview.chromium.org/466033/diff/1/6
File src/fast-codegen.cc (right):

http://codereview.chromium.org/466033/diff/1/6#newcode235
src/fast-codegen.cc:235: 
Will remove blank line.

http://codereview.chromium.org/466033/diff/1/6#newcode235
src/fast-codegen.cc:235: 
Yes, automatic unlinking will require the destructor to know codegen (or at
least codegen.environment_).

I was thinking something along the lines of
 Somethong(FastCodeGenerator codegen) : codegen_(codegen) {
  codegen->PushNestedStatement(this);
 }
 ~Something() { codegen_->PopNestedStatement(); }
   
(or inline the Push/Pop in constructor/destructor, it's max three lines).

http://codereview.chromium.org/466033/diff/1/6#newcode238
src/fast-codegen.cc:238: BreakTargetEnvironment break_env(stmt, &end_of_block);
I agree, except for my dislike for doing the linking before the object is fully
constructed (which will happen if is done in the superclass constructor. Is that
even safe to do? The VTable hasn't been set up correctly yet at that point).
Then again, we are not multithreaded.

http://codereview.chromium.org/466033/diff/1/6#newcode245
src/fast-codegen.cc:245: environment_.Drop(1);
Exactly.

http://codereview.chromium.org/466033/diff/1/6#newcode307
src/fast-codegen.cc:307: __ Call(current->AsTryFinally()->finally_entry());
We have call(Label*) already in the ia32/x64 assemblers and bl(Label*) in the
ARM assembler, so the functionality isn't new. 
It is true that using it uncritically is dangerous (but this is machine code, so
doing anything uncritically is dangerous). The callee needs to know how to
handle the pointer on the stack, either by hooking into stack traversal and GC
(like the try-handler stack), and in this case finally blocks cook the address
on entry.

We can't, currently, call to a label in the old codegen, since we don't mix
codegens inside a function.

If we start doing that, we can't uncritically assume anything about labels from
the other codegen (in either direction), and we should only jump between them at
controlled points.

http://codereview.chromium.org/466033/diff/1/6#newcode326
src/fast-codegen.cc:326: int target_offset =
environment_.FindContinueTargetOffset(stmt->target());
It was an attempt to avoid duplicating the loop code (with only a difference in
the test), but I agree that this isn't optimal either. 
I'll try avoiding the int.

http://codereview.chromium.org/466033/diff/1/6#newcode333
src/fast-codegen.cc:333: int target_offset =
environment_.FindBreakTargetOffset(stmt->target());
I think it should be ok. The current implementation also shadow all outer labels
for each nesting, so a deeply nested statement with all nesting blocks labeled
will also cause quadratic behavior.

In practical code, it probably won't be measurable.
We can make it even better by marking statements that are actually targets of
breaks or continues, and only pushing the relevant ones in our nesting stack.

http://codereview.chromium.org/466033/diff/1/7
File src/fast-codegen.h (right):

http://codereview.chromium.org/466033/diff/1/7#newcode42
src/fast-codegen.h:42: // Environments (or scopes) of special significance.
Agree that naming is bad.
We are capturing the nesting of statements (but only the ones that we care
about). It is, in a sense, the static evaluation context of the current
statement. However, "context" is such an (over)loaded word too.

How about an abstract superclass called NestedStatement, with Break, Continue,
etc as sub-classes?

I will move them into the code generator.

http://codereview.chromium.org/466033/diff/1/7#newcode52
src/fast-codegen.h:52: class EnvironmentEntry {
Will add BASE_EMBEDDED.

http://codereview.chromium.org/466033/diff/1/7#newcode56
src/fast-codegen.h:56: virtual bool IsReturnTarget() { return false; }
True, especially since AsXXX can be used directly in an if condition.

http://codereview.chromium.org/466033/diff/1/7#newcode92
src/fast-codegen.h:92: ContinueTargetEnvironment(IterationStatement*
continue_statement,
No, but it is a continuation *target*.
Still, with a rename of the superclass to NestedStatement, it should be named
after the iteration statement, not its role as a continue target.

It could even inherit from "Breakable".

http://codereview.chromium.org/466033/diff/1/7#newcode162
src/fast-codegen.h:162: class ReturnTargetEnvironment : public EnvironmentEntry
{
Will do.

http://codereview.chromium.org/466033/diff/1/7#newcode173
src/fast-codegen.h:173: class Environment {
I wanted to make the environments linked too, but didn't find a combination of
creating and linking that didn't seem messy. I should retry. Perhaps it looks
better on the second try.

Having the constructor link itself into a list is ... icky. Probably just a
leftover from codeing Java, but I don't like pointers to a class to escape
before the constructor is completely done.

How about creating the "environemnt object" normally, and thne creating a RAII
linker object on the side. I.e.:

{
 TryFinally nested_finally;
 NestingLinker(&nested_finally);
 .. do something
 // Unlink of nested_finally.
 // Destruction of nested_finally.
}

http://codereview.chromium.org/466033/diff/1/7#newcode262
src/fast-codegen.h:262: environment_(),
Does it hurt? Otherwise, I kindof like it there.

http://codereview.chromium.org/466033/diff/1/7#newcode330
src/fast-codegen.h:330: void ExitEnvironments(int count);
The latter.
It emits code that cleans up the stack and calls finally blocks on the way, so
that, at the end, you end up in a stack state that matches the expectations of
the code at the nesting level you are exiting to.

http://codereview.chromium.org/466033/diff/1/11
File src/x64/fast-codegen-x64.cc (right):

http://codereview.chromium.org/466033/diff/1/11#newcode158
src/x64/fast-codegen-x64.cc:158: ReturnTargetEnvironment return_env;
I would wonder too.
Mostly about why the other platforms don't crash.

http://codereview.chromium.org/466033/diff/1/11#newcode521
src/x64/fast-codegen-x64.cc:521: int return_offset =
environment_.FindReturnOffset();
No, this is correct. The ExitEnvironments call will handle the finally blocks on
the way out.

[Kevin Millikin (Chromium), 2009-12-10 13:09:26]

LGTM, but I think the labels for breakable and continuable statements should be
in the nesting stack (not in the call stack and pointed to by the nesting
stack).  It just seems simpler.

http://codereview.chromium.org/466033/diff/7001/7006
File src/fast-codegen.cc (right):

http://codereview.chromium.org/466033/diff/7001/7006#newcode236
src/fast-codegen.cc:236: Breakable nested_statement(this, stmt, &end_of_block);
If the label is part of the state of the Breakable, you could write

Breakable nested_statement(this, stmt);

http://codereview.chromium.org/466033/diff/7001/7006#newcode239
src/fast-codegen.cc:239: __ bind(&end_of_block);
And

__ bind(nested_statement.break_target());

http://codereview.chromium.org/466033/diff/7001/7006#newcode284
src/fast-codegen.cc:284: NestedStatement* current = nesting_stack_;
Might be nice to have a codegen comment "[ ContinueStatement" here (and below
for BreakStatement).

http://codereview.chromium.org/466033/diff/7001/7006#newcode355
src/fast-codegen.cc:355: Label body, test, exit, stack_limit_hit,
stack_check_success;
exit and test could be fields of the Iteration.

http://codereview.chromium.org/466033/diff/7001/7006#newcode369
src/fast-codegen.cc:369: __ bind(&test);
__ bind(loop_statement.continue_target());

http://codereview.chromium.org/466033/diff/7001/7006#newcode384
src/fast-codegen.cc:384: __ bind(&exit);
__ bind(loop_statement.break_target());

http://codereview.chromium.org/466033/diff/7001/7006#newcode400
src/fast-codegen.cc:400: Iteration loop_stamt(this, stmt, &exit, &test);
loop_statement?  loop_stmt?

http://codereview.chromium.org/466033/diff/7001/7006#newcode440
src/fast-codegen.cc:440: Iteration loop_stamt(this, stmt, &exit, &next);
loop_statement?

http://codereview.chromium.org/466033/diff/7001/7006#newcode616
src/fast-codegen.cc:616: __ Drop(stack_depth);
Good.  I much prefer adjusting the stack pointer to point to the handler rather
than loading the stack pointer from the global handler.

http://codereview.chromium.org/466033/diff/7001/7007
File src/fast-codegen.h (right):

http://codereview.chromium.org/466033/diff/7001/7007#newcode91
src/fast-codegen.h:91: // Generate code to leave the nested statement. This
includes
We should probably document (in several places) that the result register must be
preserved by Exit.

http://codereview.chromium.org/466033/diff/7001/7007#newcode106
src/fast-codegen.h:106: FastCodeGenerator *codegen_;
Space after star.

http://codereview.chromium.org/466033/diff/7001/7007#newcode107
src/fast-codegen.h:107: NestedStatement *previous_;
Same.

http://codereview.chromium.org/466033/diff/7001/7007#newcode124
src/fast-codegen.h:124: Statement* statement() { return target_; }
Might make return type BreakableStatement* in case you want to call
BreakableStatement methods on it.

http://codereview.chromium.org/466033/diff/7001/7007#newcode128
src/fast-codegen.h:128: Label* break_target_label_;
Instead of passing a label pointer to the constructor, you could just have a
label as a field.

[Kevin Millikin (Chromium), 2009-12-10 13:28:28]

http://codereview.chromium.org/466033/diff/7001/7006
File src/fast-codegen.cc (right):

http://codereview.chromium.org/466033/diff/7001/7006#newcode357
src/fast-codegen.cc:357: increment_loop_depth();
Another comment: it seems nicer to properly nest the increment/decrement of loop
depth with the nesting stack, eg:

Iteration loop_statement(this, stmt);
increment_loop_depth();
/* ... */
decrement_loop_depth();

Or else:

increment_loop_depth();
{
  Iteration loop_statement(this, stmt);
  /* ... */
}
decrement_loop-depth();

[Lasse Reichstein, 2009-12-10 13:55:32]

http://codereview.chromium.org/466033/diff/7001/7006
File src/fast-codegen.cc (right):

http://codereview.chromium.org/466033/diff/7001/7006#newcode284
src/fast-codegen.cc:284: NestedStatement* current = nesting_stack_;
Fixed

http://codereview.chromium.org/466033/diff/7001/7006#newcode357
src/fast-codegen.cc:357: increment_loop_depth();
Fixed

http://codereview.chromium.org/466033/diff/7001/7006#newcode400
src/fast-codegen.cc:400: Iteration loop_stamt(this, stmt, &exit, &test);
Odd typo. Fixed.

http://codereview.chromium.org/466033/diff/7001/7007
File src/fast-codegen.h (right):

http://codereview.chromium.org/466033/diff/7001/7007#newcode91
src/fast-codegen.h:91: // Generate code to leave the nested statement. This
includes
It's documented here now, and I'll put it on the functions that are called as
well.

http://codereview.chromium.org/466033/diff/7001/7007#newcode106
src/fast-codegen.h:106: FastCodeGenerator *codegen_;
Fixed

http://codereview.chromium.org/466033/diff/7001/7007#newcode107
src/fast-codegen.h:107: NestedStatement *previous_;
Fixed

http://codereview.chromium.org/466033/diff/7001/7007#newcode124
src/fast-codegen.h:124: Statement* statement() { return target_; }
Fixed.