Optimize comparisons with constant Smis. Evaluate comparisons of...

Optimize comparisons with constant Smis.  Evaluate comparisons of
two constant Smis at compile time.  Fix switch statements so that
they work with unconditionally true and false label comparisons.

Committed: http://code.google.com/p/v8/source/detail?r=1249

[Kevin Millikin (Chromium), 2009-02-11 09:35:05]

Mostly comments on the comments.  There might be a bug.

I would refactor Comparison to clean it up (along with getting rid of the
current SmiComparison or reusing it as part of refactoring Comparison).  Feel
free to do that as a separate change.

http://codereview.chromium.org/21211/diff/1/2
File src/codegen-ia32.cc (right):

http://codereview.chromium.org/21211/diff/1/2#newcode1317
Line 1317: void CodeGenerator::Comparison(Condition cc,
I think comparison should take a Token::Value.  There is no reason to convert it
to a Condition until a Condition is actually needed.  (For one thing, it makes
the constant folding part of Comparison become platform-specific when it
actually isn't).

http://codereview.chromium.org/21211/diff/1/2#newcode1336
Line 1336: // If either side is a constant SMI, optimize the comparison.
We usually write "smi" ("Smi" only at the start of a sentence, never SMI).  Try
to be consistent about capitalization.

http://codereview.chromium.org/21211/diff/1/2#newcode1343
Line 1343: if (left_side_constant_smi && right_side_constant_smi) {
It might be better to factor out the compile-time and one-argument known cases
as separate codegen functions.

http://codereview.chromium.org/21211/diff/1/2#newcode1353
Line 1353: // Result is unconditionally true.
Comparison is unconditionally true.

http://codereview.chromium.org/21211/diff/1/2#newcode1359
Line 1359: } else {  // Unconditionally return false.
Don't say "return".  We're not returning anything at compile time, we're not
emitting code to returning (from a function) at runtime, and we're not even
producing a value at runtime yet.

http://codereview.chromium.org/21211/diff/1/2#newcode2024
Line 2024: // Label and compile the test.
Adjust this comment---it no longer applies to "compile the test".

http://codereview.chromium.org/21211/diff/1/2#newcode2032
Line 2032: // We may hit an unconditionally true test.  No further tests are
compiled.
The sense of this comment is wrong (or it just doesn't belong here in the code).
 The point of the code as written is that we have a valid frame if control can
reach the test as the test of the first case, or as a target of a previous test
failure (possibly unconditional)---and we have to compile the test if it is
reachable.

http://codereview.chromium.org/21211/diff/1/2#newcode2041
Line 2041: if (enter_body.is_bound() ||
I prefer a test that we *don't* have to compile the body and a continue in that
case.

http://codereview.chromium.org/21211/diff/1/2#newcode2043
Line 2043: fall_through.is_linked()) {
In the case that we don't have to compile the body, don't we still need to unuse
next_test?  Otherwise when we compile the test the next time around the loop,
next_test is already bound and is a backward jump to the previous test?

http://codereview.chromium.org/21211/diff/1/2#newcode2044
Line 2044: if (next_test.is_bound()) {
This is confusing because next_test.is_bound() and enter_body.is_bound() are
mutually exclusive.  Write it as an if...else.

http://codereview.chromium.org/21211/diff/1/2#newcode2079
Line 2079: }  // End loop compiling all cases of switch statement.
I don't like these end of block comments.  They're redundant, and now they have
to be maintained whenever the structure of the code changes.

http://codereview.chromium.org/21211/diff/1/2#newcode2083
Line 2083: next_test.Bind();
This needs a comment explaining why bind is guarded by is_linked (because
next_test could be bound already if the last test was unconditionally false).

http://codereview.chromium.org/21211/diff/1/2#newcode2088
Line 2088: // If there is a default clause, compile it now.
Adjust this comment to mention that we compile it if (a) it is reachable as a
fall-through or (b) reachable through test failure.  (Or somehow say in which
cases we might have a default clause and not compile it.)

[William Hesse, 2009-02-11 10:46:44]

http://codereview.chromium.org/21211/diff/1/2
File src/codegen-ia32.cc (right):

http://codereview.chromium.org/21211/diff/1/2#newcode1336
Line 1336: // If either side is a constant SMI, optimize the comparison.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> We usually write "smi" ("Smi" only at the start of a sentence, never SMI). 
Try
> to be consistent about capitalization.

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode1343
Line 1343: if (left_side_constant_smi && right_side_constant_smi) {
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> It might be better to factor out the compile-time and one-argument known cases
> as separate codegen functions.

They are pretty short and simple.  I'm not convinced.

http://codereview.chromium.org/21211/diff/1/2#newcode1353
Line 1353: // Result is unconditionally true.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> Comparison is unconditionally true.

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode1359
Line 1359: } else {  // Unconditionally return false.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> Don't say "return".  We're not returning anything at compile time, we're not
> emitting code to returning (from a function) at runtime, and we're not even
> producing a value at runtime yet.

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2024
Line 2024: // Label and compile the test.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> Adjust this comment---it no longer applies to "compile the test".

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2032
Line 2032: // We may hit an unconditionally true test.  No further tests are
compiled.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> The sense of this comment is wrong (or it just doesn't belong here in the
code).
>  The point of the code as written is that we have a valid frame if control can
> reach the test as the test of the first case, or as a target of a previous
test
> failure (possibly unconditional)---and we have to compile the test if it is
> reachable.

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2041
Line 2041: if (enter_body.is_bound() ||
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> I prefer a test that we *don't* have to compile the body and a continue in
that
> case.

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2043
Line 2043: fall_through.is_linked()) {
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> In the case that we don't have to compile the body, don't we still need to
unuse
> next_test?  Otherwise when we compile the test the next time around the loop,
> next_test is already bound and is a backward jump to the previous test?

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2044
Line 2044: if (next_test.is_bound()) {
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> This is confusing because next_test.is_bound() and enter_body.is_bound() are
> mutually exclusive.  Write it as an if...else.

There is a third case, !has_valid_frame(), if the test is not compiled.  Added
as an if..else and commented.

http://codereview.chromium.org/21211/diff/1/2#newcode2079
Line 2079: }  // End loop compiling all cases of switch statement.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> I don't like these end of block comments.  They're redundant, and now they
have
> to be maintained whenever the structure of the code changes.

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2083
Line 2083: next_test.Bind();
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> This needs a comment explaining why bind is guarded by is_linked (because
> next_test could be bound already if the last test was unconditionally false).

Done.

http://codereview.chromium.org/21211/diff/1/2#newcode2088
Line 2088: // If there is a default clause, compile it now.
On 2009/02/11 09:35:05, Kevin Millikin wrote:
> Adjust this comment to mention that we compile it if (a) it is reachable as a
> fall-through or (b) reachable through test failure.  (Or somehow say in which
> cases we might have a default clause and not compile it.)

Done.

[Kevin Millikin (Chromium), 2009-02-11 12:03:11]

LGTM, but I still think the comments are murky about what's going on in the
switch statements.

BTW, the reason to factor out (at least) the constant folding part of operations
is that they are (hopefully) not platform-specific and their implementations can
be shared.  I guess that can come as a separate refactoring change.

http://codereview.chromium.org/21211/diff/5/2002
File src/codegen-ia32.cc (right):

http://codereview.chromium.org/21211/diff/5/2002#newcode2024
Line 2024: // The test is compiled, and linked with the previous and next tests.
This comment still seems wrong.  It is a ways away from the line where the test
is compiled, and the test is only compiled conditionally, and it doesn't have
anything to do with linking to the next test.

What I think the reader cares about is why this code is conditionally guarded,
because knowing that depends on reasoning about the previous loop iterations. 
Try something like "Unless this is the first (non-default) case, some previous
case was unconditionally true, or the immediately previous (non-default) case
had its body compiled, there is a dangling jump to the test."

http://codereview.chromium.org/21211/diff/5/2002#newcode2032
Line 2032: // If the switch value is a constant, we may have unconditional
I wouldn't be so specific about implementation details about why we might have
unconditional control flow (ie, don't say "constant" because we might base
decisions on known type-tags for non-constants or value-range propagation or
something, and it isn't really relevant here anyway).

The important thing that is difficult for the reader to reason out seems to me
to be in which cases the frame can be valid (first non-default case or the
immediately previous test that was compiled was not unconditionally true) and
which cases invalid (the previous compiled test was unconditionally true).

[William Hesse, 2009-02-11 12:54:00]

http://codereview.chromium.org/21211/diff/5/2002
File src/codegen-ia32.cc (right):

http://codereview.chromium.org/21211/diff/5/2002#newcode2024
Line 2024: // The test is compiled, and linked with the previous and next tests.
On 2009/02/11 12:03:11, Kevin Millikin wrote:
> This comment still seems wrong.  It is a ways away from the line where the
test
> is compiled, and the test is only compiled conditionally, and it doesn't have
> anything to do with linking to the next test.
> 
> What I think the reader cares about is why this code is conditionally guarded,
> because knowing that depends on reasoning about the previous loop iterations. 
> Try something like "Unless this is the first (non-default) case, some previous
> case was unconditionally true, or the immediately previous (non-default) case
> had its body compiled, there is a dangling jump to the test."

Done.

http://codereview.chromium.org/21211/diff/5/2002#newcode2032
Line 2032: // If the switch value is a constant, we may have unconditional
On 2009/02/11 12:03:11, Kevin Millikin wrote:
> I wouldn't be so specific about implementation details about why we might have
> unconditional control flow (ie, don't say "constant" because we might base
> decisions on known type-tags for non-constants or value-range propagation or
> something, and it isn't really relevant here anyway).
> 
> The important thing that is difficult for the reader to reason out seems to me
> to be in which cases the frame can be valid (first non-default case or the
> immediately previous test that was compiled was not unconditionally true) and
> which cases invalid (the previous compiled test was unconditionally true).

Done.