Odinmonkey: Add support for constant variables.

RESOLVED FIXED in mozilla26

Status

()

defect
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: dougc, Assigned: dougc)

Tracking

(Blocks 1 bug)

unspecified
mozilla26
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [games])

Attachments

(1 attachment, 6 obsolete attachments)

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.
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.
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?
The most direct way would be 'const' ;)  It looks like 'const' isn't currently supported in IE, though.
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.
Assignee: general → dtc-moz
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)?
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.
Attachment #759619 - Attachment is obsolete: true
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.
Attachment #760113 - Attachment is obsolete: true
Posted patch Rebase. (obsolete) — Splinter Review
Rebased after some of the pending patches, just in case you want to consider this.
Attachment #798515 - Attachment is obsolete: true
Attachment #800561 - Flags: review?(luke)
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).
Attachment #800561 - Flags: review?(luke)
For further symmetry, let's allow 'const' for the typed array views (so that 'const' can be used anywhere 'var' can, at global scope).
Posted patch Address review feedback. (obsolete) — Splinter Review
Attachment #800561 - Attachment is obsolete: true
Attachment #803803 - Flags: review?(luke)
(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.
Posted patch Remove some devo noise. (obsolete) — Splinter Review
Attachment #803803 - Attachment is obsolete: true
Attachment #803803 - Flags: review?(luke)
Attachment #803809 - Flags: review?(luke)
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.)
Attachment #803809 - Flags: review?(luke) → review+
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+.
Attachment #803809 - Attachment is obsolete: true
Attachment #804290 - Flags: review+
(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.
Target Milestone: --- → mozilla26
Keywords: checkin-needed
Summary: Consider noting asm.js global variables that are read-only to support optimizing their usage → Odinmonkey: Add support for constant variables.
https://hg.mozilla.org/mozilla-central/rev/b1d65f6b9c1e
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Whiteboard: [games]
You need to log in before you can comment on or make changes to this bug.