Douglas Crosher [:dougc] Assignee
	Description • 11 years ago

Accessors of read-only asm.js global variables could be flagged
as movable and this could support LICM and other optimizations.

Asm.js functions are currently checked and converted to MIR
independently, and perhaps in parallel, so it would appear
necessary to note writes to the global variables earlier.  Might
the new parser support this?

It might also be useful to be able to mask a global variable
value when initializing.  If the value is a pointer into the heap
then the compiler could then prove that redundant masking is
unnecessary.

As a workaround, functions can copy the global variable value to
a local variable and mask it if necessary, and this may be
adequate.

	Luke Wagner [:luke]
	Comment 1 • 11 years ago

Great idea.  One problem is that (with or without the new parser) we'll be generating code for function A before we've even *seen* function B, so that makes it hard to know that a global variable is read-only.  At the moment, we do have the whole parse tree and this does link defs to uses, so it could be done w/o too much work atm, but with the asm.js parser, we won't have even seen the *chars* of future functions by the time we're compiling.

On the other hand, it does seem like Emscripten should be able to optimize constant globals by propagating their values.

	Douglas Crosher [:dougc] Assignee
	Comment 2 • 11 years ago

Ok, thank you for explaining the capability of the new parser.

Can you think of anything that could be done to syntactically
declare a global variable as being constant?  If this could
be done then an asm.js syntax error could be generated if a
write were detected?

	Luke Wagner [:luke]
	Comment 3 • 11 years ago

The most direct way would be 'const' ;)  It looks like 'const' isn't currently supported in IE, though.

	Douglas Crosher [:dougc] Assignee
	Comment 4 • 11 years ago

This patch use 'const' to declare asm.js global variables as
read-only.  It could be useful for assessing how important this
is, and if it is important, then perhaps another syntax could be
chosen, for example: '"const"; var = ...;'.

Loads of these constant global variables are flagged as movable,
and without aliases, and this allows them to be hoisted.  This
seems ok, but these changes could use some scrutiny.

Although the code author could be expected to explicitly hoist
expressions that depend on these loads, there are implicit
masking and bounds check operations and the hoisting of these is
being frustrated when they depend on un-hoistable global variable
loads.  For example, about 10% of heap access in the box2d test
depend on a constant global pointer.

The patch opts to check that there are no assignments to a
constant global variable for it to be value asm.js syntax,
rather then silently ignoring it.  The asm.js syntax is
already strict and this might be appropriate.

	Luke Wagner [:luke]
	Comment 5 • 11 years ago

Cool, and, from a quick glance, nice patch!

I'm not really familiar with GVN, but I thought that a little more work was necessary to achieve hoisting (e.g., overriding valueHash/congruentTo).  Perhaps you could confirm that it is indeed being hoisted?

Another thought is that, when the constant global variable has a literal initializer, we could just emit an MConstant instead, which allows further optimizations (folding constants into immediates).

As for landing, I'm still a bit uneasy.  asm.js is supposed to be the *portable* super-optimizable subset and, if it allows 'const', then it will lose that (b/c of IE).  On a related note, any idea of whether 'const' is in that new leaked version of IE (the one that has WebGL)?

	Douglas Crosher [:dougc] Assignee
	Comment 6 • 11 years ago

Thanks for the suggestion Luke. This patch converts loads of constant global variables with a literal numeric value to MConstant.  This will be very handy for hand written code, but is probably not essential for machine translated code.

If this were adopted then do you think it would be reasonable to assume that heap access using these constants as the index will not be out of bounds, just as is being considered for immediate numeric literals? 

Would it be reasonable to also allow them to be used for the discussed heap access index mask?

The changes do allow hoisting (LICM) in the few examples explored so far, and I'll keep an eye out for problems.

This is work-in-progress, and not suggested for landed, but thanks for the quick feedback.

If the use of 'const' were adopted then perhaps it would also be worth considering allowing or requiring it for imported standard constants.

No idea about IE11. Spotty support for 'const' does appear to be a show stopper.

	Douglas Crosher [:dougc] Assignee
	Comment 7 • 11 years ago

Bug 865516 optimizes heap access with a masked literal constant index,
this is extended here to also optimize with a const var mask, and also
optimize heap access with a const var index.

This can reduce code size by allowing a long constant to be replaced
by a short one character variable.

It is also a convenience to the code author and in particular
for hand written code - although a source translator could replace
const vars by literal constants.

	Douglas Crosher [:dougc] Assignee
	Comment 8 • 11 years ago

Rebased after some of the pending patches, just in case you want to consider this.

	Luke Wagner [:luke]
	Comment 9 • 11 years ago

Comment on attachment 800561 [details] [diff] [review]
Rebase.

Review of attachment 800561 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great, nice work!  Other than the nits, the main thing I'd like to see in the patch is a bunch of unit tests using const (including errors for: attempted assignment, bad initializer, duplicate names (2 const vars, const + function, const + var, const + argument), and shadowing names (local variables of a function shadowing the global const, which is allowed).

::: js/src/jit/AsmJS.cpp
@@ +385,5 @@
>      return true;
>  }
>  
> +static bool
> +ParseVarOrConstStatement(AsmJSParser &parser, ParseNode **var)

There is only one other use of ParseVarStatement and that is for the function-pointer tables.  Why don't we allow 'const' there too for regularity?  Then we can have only ParseVarOrConstStatement.

@@ +1405,5 @@
>          global->u.var.type_ = type.which();
> +        global->u.var.isConstant_ = isConstant;
> +        global->u.var.isLitConstant_ = isConstant;
> +        if (isConstant)
> +            global->u.var.value_ = v;

IIUC, u.var.value_ is redundant with the value stored in the AsmJSModule.  I think you can remove it and instead derive u.var.value_ when needed via module_->global(global.varIndex()).

@@ +2041,5 @@
>          unsigned globalDataOffset = module().globalVarIndexToGlobalDataOffset(global.varIndex());
>          MAsmJSLoadGlobalVar *load = MAsmJSLoadGlobalVar::New(type, globalDataOffset);
> +        if (global.varIsConstant()) {
> +            load->setIsConstant(true);
> +            load->setMovable();

Instead of doing this, could you pass an 'isConstant' argument to MAsmJSLoadGlobalVar::New and do these assignments from there?

@@ +2902,5 @@
>      return m.fail(initNode, "expecting c.y where c is either the global or foreign parameter");
>  }
>  
>  static bool
> +CheckModuleGlobal(ModuleCompiler &m, ParseNode *var, bool isConstant)

I think we can remove the 'isConstant' arg since 'var' can be queried with var->isKind(PNK_CONST).

@@ +2921,5 @@
>      if (initNode->isKind(PNK_BITOR) || initNode->isKind(PNK_POS))
> +        return CheckGlobalVariableInitImport(m, var->name(), initNode, isConstant);
> +
> +    if (isConstant)
> +        return m.fail(var, "unexpected constant");

How about "constant initializer must be literal or imported number" and passing 'initNode' as the ParseNode instead of 'var'?

@@ +3162,5 @@
>      return f.failName(varRef, "'%s' not found in local or asm.js module scope", name);
>  }
>  
> +static inline bool
> +IsLiteralUint32OrConst(FunctionCompiler &f, ParseNode *pn, uint32_t *u32)

How about IsLiteralOrConstUint32 (since only literal consts are allowed)?

@@ +3173,5 @@
> +        const ModuleCompiler::Global *global = f.lookupGlobal(name);
> +        if (global && global->which() == ModuleCompiler::Global::Variable &&
> +            global->varIsLitConstant()) {
> +            Value v = global->varValue();
> +            if (v.isInt32()) {

Instead of cascading nested ifs, can you invert all the tests to return false:

  if (pn->getKind() != PNK_NAME)
    return false;
  ...
  if (!global || global->which() != ModuleCompiler::Global::Variable || !global->varIsLitConstant())
    return false;
  ... etc

@@ +3175,5 @@
> +            global->varIsLitConstant()) {
> +            Value v = global->varValue();
> +            if (v.isInt32()) {
> +                int32_t val = v.toInt32();
> +                if (val >= 0) {

It seems like we should accept *any* int32 since a const var lit in the range (INT32_MAX, UINT32_MAX] will be represented as a negative int32_t, so this limitation would, somewhat arbitrarily rule out large unsigned const var lits which are allowed when written as literals.  In that case, for symmetry, we should probably generalize IsLiteralUint32 to be IsLiteralInt (accepting [INT32_MIN,UINT32MAX], still returning its value as a uint32).

::: js/src/jit/MIR.h
@@ +8364,5 @@
> +    AliasSet getAliasSet() const {
> +        if (isConstant_)
> +            return AliasSet::None();
> +        else
> +            return AliasSet::Store(AliasSet::Any);

Note: bug 877338 also defies this function (it's fine if this lands first, just pointing out).

	Luke Wagner [:luke]
	Comment 10 • 11 years ago

For further symmetry, let's allow 'const' for the typed array views (so that 'const' can be used anywhere 'var' can, at global scope).

	Douglas Crosher [:dougc] Assignee
	Comment 12 • 11 years ago

(In reply to Luke Wagner [:luke] from comment #9)
> Comment on attachment 800561 [details] [diff] [review]
> Rebase.
> 
> Review of attachment 800561 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks great, nice work!  Other than the nits, the main thing I'd like to see
> in the patch is a bunch of unit tests using const (including errors for:
> attempted assignment, bad initializer, duplicate names (2 const vars, const
> + function, const + var, const + argument), and shadowing names (local
> variables of a function shadowing the global const, which is allowed).

Some tests have been added, duplicating a lot of the 'var' tests, plus
some new tests.  Not all of the requested tests have been added as they
seem to be cases handled by the parser outside the asm.js code, for example
2 const vars, const | var.
 
> ::: js/src/jit/AsmJS.cpp
> @@ +385,5 @@
> >      return true;
> >  }
> >  
> > +static bool
> > +ParseVarOrConstStatement(AsmJSParser &parser, ParseNode **var)
> 
> There is only one other use of ParseVarStatement and that is for the
> function-pointer tables.  Why don't we allow 'const' there too for
> regularity?  Then we can have only ParseVarOrConstStatement.

Done.
 
> @@ +1405,5 @@
> >          global->u.var.type_ = type.which();
> > +        global->u.var.isConstant_ = isConstant;
> > +        global->u.var.isLitConstant_ = isConstant;
> > +        if (isConstant)
> > +            global->u.var.value_ = v;
> 
> IIUC, u.var.value_ is redundant with the value stored in the AsmJSModule.  I
> think you can remove it and instead derive u.var.value_ when needed via
> module_->global(global.varIndex()).

The varIndex is not usable as an index into the module globals, so the caching
of the value has been retained.
 
> @@ +2041,5 @@
> >          unsigned globalDataOffset = module().globalVarIndexToGlobalDataOffset(global.varIndex());
> >          MAsmJSLoadGlobalVar *load = MAsmJSLoadGlobalVar::New(type, globalDataOffset);
> > +        if (global.varIsConstant()) {
> > +            load->setIsConstant(true);
> > +            load->setMovable();
> 
> Instead of doing this, could you pass an 'isConstant' argument to
> MAsmJSLoadGlobalVar::New and do these assignments from there?

Done.
 
> @@ +2902,5 @@
> >      return m.fail(initNode, "expecting c.y where c is either the global or foreign parameter");
> >  }
> >  
> >  static bool
> > +CheckModuleGlobal(ModuleCompiler &m, ParseNode *var, bool isConstant)
> 
> I think we can remove the 'isConstant' arg since 'var' can be queried with
> var->isKind(PNK_CONST).

var->isKind(PNK_CONST) is not necessarily true here when processing a
set of constant variables, so 'isConstant' has been retained.
 
> @@ +2921,5 @@
> >      if (initNode->isKind(PNK_BITOR) || initNode->isKind(PNK_POS))
> > +        return CheckGlobalVariableInitImport(m, var->name(), initNode, isConstant);
> > +
> > +    if (isConstant)
> > +        return m.fail(var, "unexpected constant");
> 
> How about "constant initializer must be literal or imported number" and
> passing 'initNode' as the ParseNode instead of 'var'?

Done.
 
> @@ +3162,5 @@
> >      return f.failName(varRef, "'%s' not found in local or asm.js module scope", name);
> >  }
> >  
> > +static inline bool
> > +IsLiteralUint32OrConst(FunctionCompiler &f, ParseNode *pn, uint32_t *u32)
> 
> How about IsLiteralOrConstUint32 (since only literal consts are allowed)?

Done.
 
> @@ +3173,5 @@
> > +        const ModuleCompiler::Global *global = f.lookupGlobal(name);
> > +        if (global && global->which() == ModuleCompiler::Global::Variable &&
> > +            global->varIsLitConstant()) {
> > +            Value v = global->varValue();
> > +            if (v.isInt32()) {
> 
> Instead of cascading nested ifs, can you invert all the tests to return
> false:
> 
>   if (pn->getKind() != PNK_NAME)
>     return false;
>   ...
>   if (!global || global->which() != ModuleCompiler::Global::Variable ||
> !global->varIsLitConstant())
>     return false;
>   ... etc

Done.

> @@ +3175,5 @@
> > +            global->varIsLitConstant()) {
> > +            Value v = global->varValue();
> > +            if (v.isInt32()) {
> > +                int32_t val = v.toInt32();
> > +                if (val >= 0) {
> 
> It seems like we should accept *any* int32 since a const var lit in the
> range (INT32_MAX, UINT32_MAX] will be represented as a negative int32_t, so
> this limitation would, somewhat arbitrarily rule out large unsigned const
> var lits which are allowed when written as literals.  In that case, for
> symmetry, we should probably generalize IsLiteralUint32 to be IsLiteralInt
> (accepting [INT32_MIN,UINT32MAX], still returning its value as a uint32).

Good point. Done.

	Luke Wagner [:luke]
	Comment 14 • 11 years ago

Comment on attachment 803809 [details] [diff] [review]
Remove some devo noise.

Review of attachment 803809 [details] [diff] [review]:
-----------------------------------------------------------------

Great, thanks!

::: js/src/jit/AsmJS.cpp
@@ +1021,5 @@
>                  uint32_t index_;
>                  VarType::Which type_;
> +                bool isConstant_;
> +                bool isLitConstant_;
> +                Value value_;

I was thinking, sometimes we write out "constant" and sometimes we abbreviate "const".  How about we use "const" everywhere (so isConst/isLitConst here and as the parameter name below).

Could you name this litConstValue_?

@@ +1058,5 @@
> +            return u.var.isLitConstant_;
> +        }
> +        const Value &varValue() const {
> +            JS_ASSERT(which_ == Variable);
> +            return u.var.value_;

Similarly, litConstValue() and can you JS_ASSERT(varIsLitConst());?

@@ +2014,5 @@
>      {
>          if (!curBlock_)
>              return NULL;
> +        if (global.varIsLitConstant()) {
> +            JS_ASSERT(global.varIsConstant());

JS_ASSERT(global.varIsConstant()) seems a bit redundant.

@@ +3151,5 @@
> +
> +    PropertyName *name = pn->name();
> +    const ModuleCompiler::Global *global = f.lookupGlobal(name);
> +    if (!global || global->which() != ModuleCompiler::Global::Variable ||
> +        !global->varIsLitConstant())

Multi-line condition needs braces around then-branch.

@@ +3160,5 @@
> +        return false;
> +
> +    *u32 = (uint32_t) v.toInt32();
> +
> +    return true;

No need for \n before 'return true'

@@ +3619,5 @@
>      ParseNode *indexNode = BinaryLeft(indexExpr);
>      ParseNode *maskNode = BinaryRight(indexExpr);
>  
>      uint32_t mask;
> +    if (!IsLiteralInt(maskNode, &mask) || mask == UINT32_MAX || !IsPowerOfTwo(mask + 1))

Can you add a test that uses negative ints (-1 and -2147483648) in all the cases that use IsLiteralint?  (Most should be type errors, as they were before.)

	Douglas Crosher [:dougc] Assignee
	Comment 15 • 11 years ago

Some minor renaming, and formatting changes.

Changed IsLiteralInt to also accept negative integers,
and added tests for all the paths using these, and also
added tests to the same paths using constant variables.

So now both constant variable negative integers and
literal negative integers return the same result from
IsLiteralOrConstInt.  I expect this was the behaviour
requested by the reviewer, and was an oversight in the
prior patch.

Carrying forward r+.

	Douglas Crosher [:dougc] Assignee
	Comment 16 • 11 years ago

(In reply to Luke Wagner [:luke] from comment #14)
> Comment on attachment 803809 [details] [diff] [review]
> Remove some devo noise.

Thank you for the quick review and r+.

> ::: js/src/jit/AsmJS.cpp
> @@ +1021,5 @@
> >                  uint32_t index_;
> >                  VarType::Which type_;
> > +                bool isConstant_;
> > +                bool isLitConstant_;
> > +                Value value_;
> 
> I was thinking, sometimes we write out "constant" and sometimes we
> abbreviate "const".  How about we use "const" everywhere (so
> isConst/isLitConst here and as the parameter name below).

Done.

> Could you name this litConstValue_?

Done.
 
> @@ +1058,5 @@
> > +            return u.var.isLitConstant_;
> > +        }
> > +        const Value &varValue() const {
> > +            JS_ASSERT(which_ == Variable);
> > +            return u.var.value_;
> 
> Similarly, litConstValue() and can you JS_ASSERT(varIsLitConst());?

Done.

> @@ +2014,5 @@
> >      {
> >          if (!curBlock_)
> >              return NULL;
> > +        if (global.varIsLitConstant()) {
> > +            JS_ASSERT(global.varIsConstant());
> 
> JS_ASSERT(global.varIsConstant()) seems a bit redundant.

Removed.

> @@ +3151,5 @@
> > +
> > +    PropertyName *name = pn->name();
> > +    const ModuleCompiler::Global *global = f.lookupGlobal(name);
> > +    if (!global || global->which() != ModuleCompiler::Global::Variable ||
> > +        !global->varIsLitConstant())
> 
> Multi-line condition needs braces around then-branch.

Fixed
 
> @@ +3160,5 @@
> > +        return false;
> > +
> > +    *u32 = (uint32_t) v.toInt32();
> > +
> > +    return true;
> 
> No need for \n before 'return true'

Fixed.
 
> @@ +3619,5 @@
> >      ParseNode *indexNode = BinaryLeft(indexExpr);
> >      ParseNode *maskNode = BinaryRight(indexExpr);
> >  
> >      uint32_t mask;
> > +    if (!IsLiteralInt(maskNode, &mask) || mask == UINT32_MAX || !IsPowerOfTwo(mask + 1))
> 
> Can you add a test that uses negative ints (-1 and -2147483648) in all the
> cases that use IsLiteralint?  (Most should be type errors, as they were
> before.)

Done.

	Ryan VanderMeulen [:RyanVM]
	Comment 17 • 11 years ago

https://hg.mozilla.org/integration/mozilla-inbound/rev/b1d65f6b9c1e

	Ryan VanderMeulen [:RyanVM]
	Comment 18 • 11 years ago

https://hg.mozilla.org/mozilla-central/rev/b1d65f6b9c1e