Boolean literal optimization

[Márcio Faustino]

Hi,

Is there a reason for not translating the boolean literals "true" and
"false" to "!0" and "!1", respectively?

Thanks,

[Alan Leung]

I can't think of any reasons.

I wonder what's the gain we get for post gzipped output.

We do have keyword aliasing (current not on) which do something like

x=false;alert(x);alert(x);alert(x);alert(x);alert(x);alert(x);alert(x);alert(x);

If you have too many references to false,true/null.

Looks like it's a very small change if you want to hack that into FoldConstants.java and try it on your project. Let us know the result too!

-Alan

2010/6/2 Márcio Faustino <m.fau...@gmail.com>

[Nick Santos]

Someone already had this idea and ran the experiment, and the results
were not statistically significant. I can't remember who it was (Bolin
maybe?). The size savings are very small, but you also take a very
small runtime and parse time hit.

On Thu, Jun 3, 2010 at 1:15 PM, Alan Leung <acl...@gmail.com> wrote:
> I can't think of any reasons.
> I wonder what's the gain we get for post gzipped output.
> We do have keyword aliasing (current not on) which do something like
> x=false;alert(x);alert(x);alert(x);alert(x);alert(x);alert(x);alert(x);alert(x);
> If you have too many references to false,true/null.
> Looks like it's a very small change if you want to hack that into
> FoldConstants.java and try it on your project. Let us know the result too!

fwiw, I think you would want to make changes like this in
CodeGenerator, not in FoldConstants. FoldConstants is more for
optimziations that benefit from a fixed-point iteration.

Nick

[John Lenz]

Correct, FoldConstants is trying to converge to stable values by transforming values like "!0" into "true".
 

Nick

[Alan Leung]

Good point!

I guess hacking this in CodeGen would be easier. Almost require no knowledge of the syntax tree at all.

[Mike Samuel]

2010/6/3 Alan Leung <acl...@gmail.com>:

> Good point!
> I guess hacking this in CodeGen would be easier. Almost require no knowledge
> of the syntax tree at all.

You have to be careful around operator precedence so it does require
some knowledge.

In {var x = false.toString()}, depending on where you split lines you
can get either
var x = 1.toString() // syntactically invalid since . is part of
the numeric token
or
var x = 1. // assigns 1 to x instead of "1" due to semicolon insertion
toString() // syntactically valid expression statement.

[Philippe Verdy]

2010/6/3 Mike Samuel <mikes...@gmail.com>:

> In {var x = false.toString()}, depending on where you split lines you
> can get either
>    var x = 1.toString() // syntactically invalid since . is part of
> the numeric token
> or
>    var x = 1.  // assigns 1 to x instead of "1" due to semicolon insertion
>    toString()  // syntactically valid expression statement.

Actually, if your replace a constant variable by its numeric value,
you will have to also evaluate their methods before substituting.

So false.toString() will have to be evaluated to a constant String "0"
as well. This not only requires parsing the syntax tree, but also
parse the semantics, and infer datatypes to correctly evaluate the
methods.

This is a much more complex project than a simple substitution. In
fact for such project, the comoiler would have to become a full
interpreter of Javascript (making additional verifications related to
data paths used in the code, and correctly infer where/when variables
are assigned ; given that all Javascript variables are actually
members in a contextual object, computing the associated class
interfaces for these objects and tracking their modifications is
really a complex work, as complex as writing the full V8 compiler
already built in Chrome, where those optimisations will above will no
longer be necessary as they are immediately infered at runtime),

[Alan Leung]

 

Actually, if your replace a constant variable by its numeric value,
you will have to also evaluate their methods before substituting.
 

So false.toString() will have to be evaluated to a constant String "0"
as well. This not only requires parsing the syntax tree, but also
parse the semantics, and infer datatypes to correctly evaluate the
methods.

I don't fully understand what you are trying to say here. I suspect we might use

a different set of definitions or terminologies. Are you taking about the browser

Javascript interpreter having to re-parse the syntax tree? Why must it do that?

If you are talking about Closure Compiler, we already have an Abstract Syntax Tree

parsed before all our analysis and optimizations. I don't see this as an issue.

I am not sure what you meant by "parsing the semantics", neither.

  

This is a much more complex project than a simple substitution. In
fact for such project, the comoiler would have to become a full
interpreter of Javascript

Again, I am not sure what you meant by making a full Javascript interpreter. Such interpretation

does not guarantee termination and the problem is not computable. We do use a

technique call Abstract Interpretation: (http://en.wikipedia.org/wiki/Abstract_interpretation)

which computes a sounded approximation of the semantics of the Javascript program if that

is what you mean by Javascript interpreter.

(making additional verifications related to
data paths used in the code, and correctly infer where/when variables
are assigned ; given that all Javascript variables are actually
members in a contextual object, computing the associated class
interfaces for these objects and tracking their modifications is
really a complex work,

The replacement Macrio Faustino suggested is a very simple strength reduction where true is replaced

with !0. I don't think the type of analysis you described is needed as it is strictly a peephole type optimization.

I have a feeling you are trying to describe some sort of value propagation optimization.

Unlike other Javascript minimizers, Closure compiler do have the analysis you described.

Closure Compiler understands control flow and data flow of your program. It already have a 

handful of optimizations that does similar to what you described. For example: variable Inlining,

dead assignments removal, merging variable names all does the modification tracking that you 

are trying to get at. Also we already have a flow sensitive type inference system in place.

 

as complex as writing the full V8 compiler
already built in Chrome, where those optimisations will above will no
longer be necessary as they are immediately infered at runtime),

Once again, I don't understand what you meant by immediately inferred. You mean right at the execution

of that code segment the type would be available?

In any case, I personally believe V8 is a great piece of engineering work and an excellent JIT Compiler,

but it that doesn't undermine the work we do as a ahead-of-time compiler. Most of the time the two can go hand-in-hand.

While JIT compiling to machine code is fantastic for performance, V8 runs on a compile time constrain. Closure Compiler

have a much less strict compilation time constraint in which we are able to do more complex analysis and optimizations.

This is especially true in our case where Closure Compiler is main focus is code size downloaded across the network and

V8 is solely for execution speed. Therefore, I don't agree with you that much of the optimizations is too complex to do

or should just be left to be done in V8.

-Alan

[Mike Samuel]

2010/6/5 Alan Leung <acl...@gmail.com>:

Sorry for the confusion. I wrote a bad example.

What I meant to say was that since ! has a lower precedence than some
operators that can be applied to boolean keywords, you have to be
careful to parenthesize in same cases which offsets much of the space
gain.

Here is a less confusing example:

true.methodCall(x)

is semantically equivalent to

(!0).methodCall(x)

which doesn't save any space but not to the syntactically invalid

!0.methodCall(x)

or the syntactically valid
!0.
methodCall(x)

I raised this because Rhino's AST includes a parenthesize expression
node type which suggested to me that maybe the code generator does not
automatically insert parentheses. If that's not the case, then please
ignore.

[Alan Leung]

Sorry for the confusion.  I wrote a bad example.

Actually I understood the point you were trying to make and you are right, hacking it it in codegen might risk having that problem.

Out of curiosity,  Mike, I wonder if Caja has a more extensive set of unit tests for its codegen that we can verify closure compiler with. That could ease the Caja + Closure Compiler backend integration process.

-Alan

[Mike Samuel]

We have some tests of what we call our renderer that test corner cases
around parenthesization, unrenderable regular expression literals,
orphaned else clauses, expression vs statement ambiguity for object
and function expressions, and the like.

But parentheses do not introduce a parse tree node for caja so the
parenthesization stuff is all testing the typical case for us. That
isn't true of curly brackets which do introduce block nodes because
we're looking forward to lexical scopes in some future version of ES.

You'll find some hideous renderer tests like
assertEquals(
"(new (/./.constructor)('', ''))",
render(new RegexpLiteral(FilePosition.UNKNOWN, "//")));
in http://code.google.com/p/google-caja/source/browse/trunk/tests/com/google/caja/parser/js/ParserTest.java
where slashdot shows up twice in a row.

2010/6/11 Alan Leung <acl...@gmail.com>: