678952 - Operations on Vector.<C> do not make use of or provide information about C

Status: VERIFIED FIXED

(Tamarin Graveyard :: Virtual Machine, defect, P2)

Description

[Lars T Hansen]

Attachment: Benchmark

Consider:

  var v: Vector.<C> = new Vector.<C>(1);
  var x: C = new C;
  var y: C;

In a read operation such as "y = v[0]", there is a dynamic type check on the assignment because the JIT is not aware that the result of the read operation on v is always a C object.

In a write operation such as "v[0] = x", there is a dynamic type check on the store into the vector because the JIT's information about x being a C is not made use of in the write.

On a simple benchmark, which I will attach, the redundant type checks account for over 30% of the overall running time, and have the effect that using Vector is slower than using Array.

Comment 1

[Lars T Hansen]

Attachment: Patch

Two simple changes:

- In the verifier, set the propType when reading a vector element to the
  parameter type of the vector.

- In the code generator, if the type of the value is known to be a subtype of
  the parameter type of the vector then call a vector setter that omits the
  coercion.

For this we need to store the parameter type with the vector traits, and this adds a field to every Trait structure.  I don't know how much of an issue this is, storage wise; clearly other approaches are possible if it is an issue.

With these changes the benchmark runs in the expected time and Vector is faster than Array (a lot faster for reading, marginally faster for writing).

Comment 2

[Edwin Smith]

Comment on attachment 553146 [details] [diff] [review]
Patch

If the space for the extra Traits* is worrisome (not sure it is) then maybe the field can be overloaded with Traits.itraits.  Only class and function instances have a non-null itraits field.  Traits.builtinType will be BUILTIN_function/class for them, so it could be a union discriminator.

In fact, itraits is a type parameter for Class and Function instances anyway, even though it doesn't have the <> surface syntax.

The verifier versioning hazard is that this can change observable behavior because of pushscope, e.g:

  // vector is Vector.<int>
  getproperty vector[i] // was *, now int
  pushscope             // scope was *, now is int
  findpropstrict toString // would match outer scope before, now matches vector

We could also probably invent some cases where verify errors before become non-errors now (negative results go away) e.g. by feeding the result of getproperty (which is now int) to something requiring int, say lookupswitch.

Its unlikely code like this exists, but the safe option is to version the verifier change (only).

test cases would be good along with the code patch.

Comment 3

[Lars T Hansen]

This is a significant and straightforward optimization, request hereby goes to QRB to consider it for Anza.

Comment 4

[Lars T Hansen]

Recapping an IM discussion: What does it mean to "version" this change?

Seen in isolation from a particular SWF, the versioning is a "static" kind of versioning, it is isolated: If the SWF was compiled as SWF14 and later, say, then it gets the new improved behavior, if it was compiled as SWF13 or earlier then it gets the old behavior.  To test whether the fix should be enabled or not we can test the flag in the "static" bugcompatibility structure for the pool from the verifier:

  abc_env->codeContext()->bugCompatibility()->bugzilla678952

The fly in this ointment is builtin code, because builtin code must run as if it had the version of the last non-builtin caller, it does not have behavior that is tied statically to its "SWF".  Thus if the change can be seen to affect the semantics of builtins then the builtin code must either not have this optimization enabled (thus trivially preserving old behavior) or the builtins must dynamically check the version.  However, there is no sense in which the builtins can "dynamically check the version" for this change because the change we make is a static change to the type information available to the verifier, and verification is done just once, not on every call.  To enable a dynamic check in the builtins would entail compiling the method twice, once with the change and once without, and then choosing among those methods on invocation.

Comment 5

[Lars T Hansen]

Thus the question is, can the builtins be affected by this change?

Edwin brings up two possible changes.  The second of these, verifier errors turning into non-errors, is not a concern for builtin code, and will not affect users of builtin code as builtin APIs don't change at all.

The first problem is that the verifier somehow makes use of type information that is correct but which was previously unavailable, and therefore computes a different result.  It seems to me that this could only happen if the type information /limits/ the view the verifier has of the data, because if it did not then a dynamic operation on * and a (static) operation on T would yield the same result.

Ed's example does not seem entirely coherent to me (a typo in the last comment?) but here's my take on it.  Suppose the global object is the only object on the scope chain, that C is an empty class with a subclass D and that D has a property "P", and that V is Vector<C> containing only D objects.  Then:

   getproperty v[i]
   pushscope
   findpropstrict P

Under the new behavior the verifier will know that a "C" does not have a "P" so the innermost scope object will not be considered; instead the outer global scope will be consulted at run-time.  However, since the value that was pushed onto the scope was really a "D" and it does have a "P", then under the old behavior the verifier would not have known the type of the innermost scope object, so it would have been searched at run-time, and the search would have found the "P".

How much of a problem can this type of change be for builtins?  The mitigating consideration is that the builtins are written in AS3 and that code that could not reasonably be generated by an AS3 compiler or optimizer that we control should not concern us in this particular case.  (Bill has gnomically expressed this as "There's a case-by-case finesse needed to avoid dynamic versioning.")

While this kind of thing is not a problem for "pushwith", for example, an optimizer can validly replace a pushwith by a pushscope if enough static type information is available; the above code would seem to be entirely valid for "with (V[i]) print(P)" if the optimizer knew that V contained all D objects.

And I don't know where else in the instruction set the problem might appear.

Comment 6

[Lars T Hansen]

Factoid: so far as I can tell there are no uses of the 'with' statement in any of the Flash Player builtins (this is not unexpected).

Comment 7

[Lars T Hansen]

Another thing to worry about is the interaction with ASC.

Avik's latest investigations reveal that ASC computes the type '*' for 'new Vector.<T>', so in the case of (new Vector.<T>(1))[0] the type will also be *.  However, ASC appears to compute the type 'Vector.<T>' for an initializer 'new <T>[...]', and so far as I can tell it knows that if 'var v:Vector.<T>' then 'v' yields a 'Vector.<T>'.

The (new Vector.<T>(1))[0] pattern won't appear much in source code unless machine generated, though it could fall out as a result of ABC optimization.  But at that point we're in a different type system and problems in ASC don't matter.

At most we would experience new verifier errors as a result of this behavior and we would catch those during testing of the builtins.

Comment 8

[Lars T Hansen]

At least these instructions are affected by the information available on the scope chain:

  getscopeobject
  getouterscope
  getlex
  findproperty
  findpropstrict

If we have more type information available from an object read from a vector then we get more type information about values read from that object.  But this adds no further complications: it's still a case of having information about a value where none was previously available.

getproperty et al cannot use the extra type information other than for early binding or optimizing lookup (eg, if the class is final and sealed and does not have the property then go directly to the prototype object), they cannot use the type to rule out the presence of a property.

Comment 9

[Lars T Hansen]

And finally, about ASC:

- pushwith is being emitted for 'with' statements and for named function
  expression.  (The latter is a bug because Function objects are dynamic,
  but does not concern us here.)
- pushscope is being emitted for class objects, instance objects, and
  activation objects.  None of those originate in vectors, they are all either
  immediately available ("this", global bindings, immediately created).

The global optimizer is not, to my knowledge, being used at this point for anything, so the output from ASC is the ABC code that goes into the Flash Player and AIR.

As a consequence of all of that I would like to claim that it is not observable to user code whether the new optimization is enabled in the builtins or not.  Ergo simple static versioning will be sufficient, and the optimization will always be enabled in the builtins.

Comment 10

[Lars T Hansen]

Below is an abcasm full test case that shows the divergence in behavior in the new code relative to the old code, under -Ojit.  (Incidentially it can also be used to show that the old code differs in its behavior with -Ojit and -Dinterp.)

The test case requires a modified abcasm (bug #484509) and also some precompiled AS3 helpers, shown subsequently.

    function main()
    {
	getlocal0
	pushscope

	// r1 = new Vector.<C>(1)
        findpropstrict "__AS3__.vec"::Vector
        getproperty    "__AS3__.vec"::Vector
	findpropstrict C
        getproperty    C
        applytype      1
        pushbyte       1
        construct      1
	coerce         # "__AS3__.vec"::Vector C
        setlocal       1

	// r1[0] = new C
	getlocal       1
        pushbyte       0
	findpropstrict C
	getproperty    C
	construct      0
	setproperty    @

	// r2 = P where r1[0] is on the scope chain
        getlocal       1
	pushbyte       0
	getproperty    @
	pushscope
	findpropstrict P
        getproperty    P
	setlocal       2
	popscope

	// print(r2)
	findpropstrict print
        getlocal       2
        callproperty   print 1

	returnvoid
    }

Here are the AS3 helpers:

    public var P = "P from global";

    public class C
    {
        public var P = "P from C";
    }

With the old code, this prints "P from global" with -Ojit and "P from C" with -Dinterp.  With the new code, it prints "P from C" in both cases.

Note that this does not require a subclass D of C to show the changed behavior.  The change in behavior comes from the fact that the jitted code will early-bind when it knows an object contains a property of the desired name, and it will skip the object during run-time search if it does not know that.

(The interpreter, on the other hand, does not use the type information like that - a bug.)

Comment 11

[Lars T Hansen]

Attachment: Patch, v2

The core functionality is unchanged, but I added versioning for the verifier change, see reasoning earlier in this bug.  This patch also adds an abcasm test case to exhibit the changed behavior for SWF >= 14 (Anza).

Comment 12

[Lars T Hansen]

Anza decision still pending.

Comment 13

[Tamarin Bot]

changeset: 6532:6f72616eadd7
user:      Lars T Hansen <[e-mail]>
summary:   Fix 678952 - Operations on Vector.<C> do not make use of or provide information about C (r=edwsmith)

http://hg.mozilla.org/tamarin-redux/rev/6f72616eadd7

Comment 14

[Tommy Reilly]

The tracers need to be regenerated to trace m_paramTraits

Comment 15

[Tommy Reilly]

changeset:   6535:c23c8f1e0bfa
tag:         tip
user:        Tommy Reilly <[e-mail]>
date:        Mon Aug 22 12:20:46 2011 -0400
summary:     Update tracers with new paramTraits field

Comment 16

[Dan Smith]

(In reply to Lars T Hansen from comment #12)
> Anza decision still pending.

Anza, please!

Comment 17

[Brent Baker]

Code coverage notes for this patch on mac64bit release debugger:


CodegenLIR.cpp -> covered
PoolObject.cpp -> covered
Traits-inlines.h -> covered
Traits.cpp -> covered
VectorClass-impl.h -> covered
VectorClass-inlines.h -> After talking with Lars the following methods will never be touched and can be ignored from coverage reporting:
Covered:
- avmplus::VectorBaseObject::atomToValueKnown(Atom,OpaqueAtom&)

Not covered, expected and will be ignored from code coverage reporting:
- avmplus::VectorBaseObject::atomToValueKnown(Atom,double&)
- avmplus::VectorBaseObject::atomToValueKnown(Atom,int32_t&)
- avmplus::VectorBaseObject::atomToValueKnown(Atom,uint32_t&)

Verifier.cpp -> missing false conditions for
  -->t2739a                bool maybeIntegerIndex = !attr &&
  -->t2739b                                                  multiname.isRtname() &&
  -->t2739c                                                                          multiname.containsAnyPublicNamespace();

  -->t2740b                    maybeIntegerIndex && (

Comment 18

[Brent Baker]

(In reply to Brent Baker from comment #17)
> Verifier.cpp -> missing false conditions for
>   -->t2739a     bool maybeIntegerIndex = !attr &&
>   -->t2739b                             multiname.isRtname() &&
>   -->t2739c                                  multiname.containsAnyPublicNamespace();
> 

Does anyone have any pointers on how to cover !attr and multiname.containsAnyPublicNamespace();?

I was able to cover multiname.isRtname() with try to access Vector g using g.foo, but have not been able to figure out/undertand the other 2 conditions.

Comment 19

[Lars T Hansen]

For attr you may need an XML attribute name a la '@whatever'.

Most multinames contain some public namespace.  But you should be able to get to this by using a run-time computed namespace, eg, here's where we'd have a public namespace in the set:

  namespace NS = ""; 
  var ns = NS;
  var x = "hello there";
  print(ns::x);

and here's where we'd not:

  namespace NS = "*ns*"; 
  var ns = NS;
  NS var x = "hello there";
  print(ns::x);

(Arbitrary restrictions in ASC and AS3 mean you may have to wrap that in a package and/or class to get it to compile.)

I haven't tested that but it'd be my first guess.

Comment 20

[Brent Baker]

For some reason I seem to be having some problems with committing this comment.... try this again

(In reply to Lars T Hansen from comment #19)
>   namespace NS = "*ns*"; 
>   var ns = NS;
>   NS var x = "hello there";
>   print(ns::x);
> 
> (Arbitrary restrictions in ASC and AS3 mean you may have to wrap that in a
> package and/or class to get it to compile.)
> 
> I haven't tested that but it'd be my first guess.

Still having some problems with getting the last condition tested here: multiname.containsAnyPublicNamespace();

Trying to distill the example I came up with:

class C
{
    var x: C = null;  // just some field to make the type nontrivial
}
class D
{
    namespace NS = "*ns*";
    var ns = NS;
    NS var foo;
    var b: Vector.<C>;
    function D()
    {
	b = new Vector.<C>;
	b[0] = new C;
	var e = b.ns::foo;
    }
}

var gg = new D();

However it looks like this is just getting caught by multiname.isRtname() being false and never reaches the check for containsAnyPublicNamespace(). I can try and recompile the check here just to see by swapping the 2 checks to see if I am on the right path.

Comment 21

[Brent Baker]

(In reply to Brent Baker from comment #20)
> However it looks like this is just getting caught by multiname.isRtname()
> being false and never reaches the check for containsAnyPublicNamespace(). I
> can try and recompile the check here just to see by swapping the 2 checks to
> see if I am on the right path.

Ok I swapped the code to be:
    bool maybeIntegerIndex = !attr && multiname.containsAnyPublicNamespace() && multiname.isRtname();
and the above code sample does get cover the false condition of multiname.containsAnyPublicNamespace(), but I am not sure how to get this covered normally.

Might have been possible to extend Vector and place a new method on it that was in a nonpublic namespace, but Vector is final so you can't extend it.

Comment 22

[Brent Baker]

Attachment: Verifier change testcase

Comment 23

[Lars T Hansen]

Comment on attachment 555728 [details] [diff] [review]
Verifier change testcase

These are at least redundant:

+a[0] = new C;
+a[10] = new C;
+var f = a[0];

More generally I'm not sure what this test case tests, and it definitely does not test anything related to the patch that was landed, because that only affected the types propagated when properties were read from vectors of known type.  If this is a coverage-driven test then the doc block should say so.  Generally the doc block looks wrong.

I checked in a test case in abcasm/bug_678952.abs and it is being run with the different swf versions and so on.

Comment 24

[Brent Baker]

Attachment: v2. Verifier change testcase

- Removed incorrect documentation section
- Removed unnecessary vector assignment
- Updated documentation section to specify what these 2 testcases are covering, also added comments about each testcase pointing to the condition/branch that it is testing.

Comment 25

[Tamarin Bot]

changeset: 6547:d4c7e051bc79
user:      Brent Baker <[e-mail]>
summary:   Bug 678952: testcase for Verifier changes (r=lhansen)

http://hg.mozilla.org/tamarin-redux/rev/d4c7e051bc79