Better typing and type verification

Better typing and type verification

- Extend verifier to check types of JS and Simplified nodes.
- Untyped nodes now contain NULL as types, enforcing hard failure.
- Typer immediately installs itself as a decorator; remove explicit decorator installation.
- Decorator eagerly types all nodes that have typed inputs.
- Cut down typer interface to prevent inconsistently typed graphs.
- Decorators are also used by the constant cache, removing its typing
  side-channel and various spurious dependencies on the typer.
- Fix a couple of bugs on the way that got uncovered.

To do: typing and verifying machine operators.

R=titzer@chromium.org, jarin@chromium.org
BUG=

[titzer, 2014-08-28 13:12:31]

https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-inl.h
File src/compiler/generic-node-inl.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-in...
src/compiler/generic-node-inl.h:26: inputs_.static_ =
reinterpret_cast<Input*>(this + 1);
That's a nice little gift

https://codereview.chromium.org/509343002/diff/1/src/compiler/graph.h
File src/compiler/graph.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/graph.h#newcode83
src/compiler/graph.h:83: bool is_typed() const { return is_typed_; }
Gah, we went through this with the source positions. Please don't make the graph
stateful. That's the whole point of the decorators. Maybe you can have
IsDecoratedWith?

https://codereview.chromium.org/509343002/diff/1/src/compiler/js-graph.cc
File src/compiler/js-graph.cc (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/js-graph.cc#new...
src/compiler/js-graph.cc:157: graph()->Decorate(*loc);
Why are you explicitly calling Decorate all over the place now?

https://codereview.chromium.org/509343002/diff/1/src/compiler/opcodes.h
File src/compiler/opcodes.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/opcodes.h#newcode9
src/compiler/opcodes.h:9: #define INNER_CONTROL_OP_LIST(V) \
I am not a fan of splitting up all the operators into tons of different lists.

[rossberg, 2014-08-28 15:35:50]

https://codereview.chromium.org/509343002/diff/1/src/compiler/graph.h
File src/compiler/graph.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/graph.h#newcode83
src/compiler/graph.h:83: bool is_typed() const { return is_typed_; }
On 2014/08/28 13:12:31, titzer wrote:
> Gah, we went through this with the source positions. Please don't make the
graph
> stateful. That's the whole point of the decorators.

Hm, well, the graph _is_ fundamentally stateful. This is just being honest about
it. :) I could remove the explication in this flag, but it enables more
assertions (which actually were quite helpful so far).

> Maybe you can have IsDecoratedWith?

Then verification would check all the wrong thing when you happen to remove a
decorator. Is that desirable?

A more workable option would be to pass typedness as a flag to the verifier.
That's a version I had earlier, but it's more verbose, and as mentioned, you
loose some useful assertions.

But if you prefer, I can change it that way.

https://codereview.chromium.org/509343002/diff/1/src/compiler/js-graph.cc
File src/compiler/js-graph.cc (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/js-graph.cc#new...
src/compiler/js-graph.cc:157: graph()->Decorate(*loc);
On 2014/08/28 13:12:31, titzer wrote:
> Why are you explicitly calling Decorate all over the place now?

Because new decorators might have been added since the node got cached.

I thought about making these calls only if that was the case, but then you
somehow need to timestamp the last decorator list modification. It's possible,
but seems like a premature micro optimisation at this point. Your call.

https://codereview.chromium.org/509343002/diff/1/src/compiler/opcodes.h
File src/compiler/opcodes.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/opcodes.h#newcode9
src/compiler/opcodes.h:9: #define INNER_CONTROL_OP_LIST(V) \
On 2014/08/28 13:12:31, titzer wrote:
> I am not a fan of splitting up all the operators into tons of different lists.

I know, me neither, really, but what (modular) alternative do you suggest?

[Benedikt Meurer, 2014-08-29 07:00:58]

bmeurer@chromium.org changed reviewers:
+ bmeurer@chromium.org

[Benedikt Meurer, 2014-08-29 07:00:58]

https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-inl.h
File src/compiler/generic-node-inl.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-in...
src/compiler/generic-node-inl.h:26: inputs_.static_ =
reinterpret_cast<Input*>(this + 1);
Ahem, can we please get rid of this undefined behaviour here? Even if we assume
that alignof is less than sizeof the concrete GenericNode (which we do not
ensure in any way), it is still not safe in general.

[rossberg, 2014-08-29 07:23:42]

https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-inl.h
File src/compiler/generic-node-inl.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-in...
src/compiler/generic-node-inl.h:26: inputs_.static_ =
reinterpret_cast<Input*>(this + 1);
On 2014/08/29 07:00:58, Benedikt Meurer wrote:
> Ahem, can we please get rid of this undefined behaviour here? Even if we
assume
> that alignof is less than sizeof the concrete GenericNode (which we do not
> ensure in any way), it is still not safe in general.

I agree. Since this problem has nothing to do with this CL, feel free to fix it.
:)

[titzer, 2014-09-26 10:43:41]

On 2014/08/29 07:23:42, rossberg wrote:
>
https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-inl.h
> File src/compiler/generic-node-inl.h (right):
> 
>
https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-in...
> src/compiler/generic-node-inl.h:26: inputs_.static_ =
> reinterpret_cast<Input*>(this + 1);
> On 2014/08/29 07:00:58, Benedikt Meurer wrote:
> > Ahem, can we please get rid of this undefined behaviour here? Even if we
> assume
> > that alignof is less than sizeof the concrete GenericNode (which we do not
> > ensure in any way), it is still not safe in general.
> 
> I agree. Since this problem has nothing to do with this CL, feel free to fix
it.
> :)

I don't see a new patch, so I'll just repeat my earlier point. Please no fields
in Graph. We discussed the "state" of the graph at various points, and my view
is that the typedness of a graph is really an extra property that you want to
check at specific points in time during compilation and tests, and not a
property of the graph that it itself should carry around. I know that means more
surgery at uses of the verifier, but then I would actually find that clearer.

[rossberg, 2014-09-30 14:54:11]

On 2014/09/26 10:43:41, titzer wrote:
> On 2014/08/29 07:23:42, rossberg wrote:
> >
>
https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-inl.h
> > File src/compiler/generic-node-inl.h (right):
> > 
> >
>
https://codereview.chromium.org/509343002/diff/1/src/compiler/generic-node-in...
> > src/compiler/generic-node-inl.h:26: inputs_.static_ =
> > reinterpret_cast<Input*>(this + 1);
> > On 2014/08/29 07:00:58, Benedikt Meurer wrote:
> > > Ahem, can we please get rid of this undefined behaviour here? Even if we
> > assume
> > > that alignof is less than sizeof the concrete GenericNode (which we do not
> > > ensure in any way), it is still not safe in general.
> > 
> > I agree. Since this problem has nothing to do with this CL, feel free to fix
> it.
> > :)
> 
> I don't see a new patch, so I'll just repeat my earlier point.

Because you never replied to my follow-up comments & questions. ;)

> Please no fields
> in Graph. We discussed the "state" of the graph at various points, and my view
> is that the typedness of a graph is really an extra property that you want to
> check at specific points in time during compilation and tests, and not a
> property of the graph that it itself should carry around. I know that means
more
> surgery at uses of the verifier, but then I would actually find that clearer.

I fundamentally disagree, because the types _are_ part of the graph, but I
removed the flag anyway. As you can see from the patch diff, this loses a few
useful assertions outside the verifier. But I can live with that.

[titzer, 2014-10-01 08:18:11]

https://codereview.chromium.org/509343002/diff/20001/src/compiler/js-graph.cc
File src/compiler/js-graph.cc (right):

https://codereview.chromium.org/509343002/diff/20001/src/compiler/js-graph.cc...
src/compiler/js-graph.cc:34: return c_entry_stub_constant_.is_set()
This decorates the node every time you get it. That sucks!

[titzer, 2014-10-01 08:30:24]

https://codereview.chromium.org/509343002/diff/1/src/compiler/graph.h
File src/compiler/graph.h (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/graph.h#newcode83
src/compiler/graph.h:83: bool is_typed() const { return is_typed_; }
On 2014/08/28 15:35:50, rossberg wrote:
> On 2014/08/28 13:12:31, titzer wrote:
> > Gah, we went through this with the source positions. Please don't make the
> graph
> > stateful. That's the whole point of the decorators.
> 
> Hm, well, the graph _is_ fundamentally stateful. This is just being honest
about
> it. :) I could remove the explication in this flag, but it enables more
> assertions (which actually were quite helpful so far).

Just because nodes and edges can be mutated doesn't mean that the Graph
datastructure, which serves as both a node factory and a handle on a couple of
special nodes, should be tasked with carrying around even more state. E.g. we
don't carry around the "level" of the IR of the nodes in the graph (i.e.
simplified versus JS versus machine). You might argue that we should, and you
might be right, even, but the Graph datastructure isn't really the right place
to store it, IMO.

> 
> > Maybe you can have IsDecoratedWith?
> 
> Then verification would check all the wrong thing when you happen to remove a
> decorator. Is that desirable?
> 
> A more workable option would be to pass typedness as a flag to the verifier.
> That's a version I had earlier, but it's more verbose, and as mentioned, you
> loose some useful assertions.
> 
> But if you prefer, I can change it that way.

https://codereview.chromium.org/509343002/diff/1/src/compiler/js-graph.cc
File src/compiler/js-graph.cc (right):

https://codereview.chromium.org/509343002/diff/1/src/compiler/js-graph.cc#new...
src/compiler/js-graph.cc:157: graph()->Decorate(*loc);
On 2014/08/28 15:35:50, rossberg wrote:
> On 2014/08/28 13:12:31, titzer wrote:
> > Why are you explicitly calling Decorate all over the place now?
> 
> Because new decorators might have been added since the node got cached.
> 
> I thought about making these calls only if that was the case, but then you
> somehow need to timestamp the last decorator list modification. It's possible,
> but seems like a premature micro optimisation at this point. Your call.

This is starting to be a real pain. Now we are adding this weird
double-decoration logic (actually N-decoration) to handle a problem with cached
nodes not being decorated by the typer.

This is why having constants that are always typed immediately is best. It's an
invariant that will hold everywhere, regardless of what "state" the graph is in.

[rossberg, 2014-10-07 16:27:09]

Changed the CL to consistently do eager typing of nodes where possible --
handling of constants now just falls out of that. :)

[titzer, 2014-10-08 10:39:43]

Looks good other than two comments.

https://codereview.chromium.org/509343002/diff/60001/src/compiler/js-graph.cc
File src/compiler/js-graph.cc (right):

https://codereview.chromium.org/509343002/diff/60001/src/compiler/js-graph.cc...
src/compiler/js-graph.cc:20: Node* JSGraph::CacheNode(SetOncePointer<Node>*
cache, Node* node) {
You can inline these methods now, and then you are close to the original node.

https://codereview.chromium.org/509343002/diff/60001/src/compiler/typer.h
File src/compiler/typer.h (right):

https://codereview.chromium.org/509343002/diff/60001/src/compiler/typer.h#new...
src/compiler/typer.h:40: Decorator* decorator_;
Can you make this guy an inlined instance?

[rossberg, 2014-10-08 11:30:19]

https://codereview.chromium.org/509343002/diff/60001/src/compiler/js-graph.cc
File src/compiler/js-graph.cc (right):

https://codereview.chromium.org/509343002/diff/60001/src/compiler/js-graph.cc...
src/compiler/js-graph.cc:20: Node* JSGraph::CacheNode(SetOncePointer<Node>*
cache, Node* node) {
On 2014/10/08 10:39:43, titzer wrote:
> You can inline these methods now, and then you are close to the original node.

Done.

https://codereview.chromium.org/509343002/diff/60001/src/compiler/typer.h
File src/compiler/typer.h (right):

https://codereview.chromium.org/509343002/diff/60001/src/compiler/typer.h#new...
src/compiler/typer.h:40: Decorator* decorator_;
On 2014/10/08 10:39:43, titzer wrote:
> Can you make this guy an inlined instance?

Unfortunately, not without moving the definition of the Decorator class into the
.h file, which isn't worth it.

[titzer, 2014-10-08 11:33:17]

lgtm

[rossberg, 2014-10-14 14:25:42]

Patchset #6 (id:100001) has been deleted

[rossberg, 2014-10-14 14:27:35]

Patchset #6 (id:120001) has been deleted

[rossberg, 2014-10-14 14:30:26]

Patchset #6 (id:140001) has been deleted

[rossberg, 2014-10-14 14:54:57]

rossberg@chromium.org changed reviewers:
+ jarin@chromium.org

[rossberg, 2014-10-14 14:58:37]

Rebased, necessitating various changes and non-trivial conflict resolutions,
which unfortunately weren't easily separable; patch set 6 hence contains both.

[titzer, 2014-10-14 16:13:23]

lgtm with small comments.

https://codereview.chromium.org/509343002/diff/160001/src/compiler/change-low...
File src/compiler/change-lowering.cc (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/change-low...
src/compiler/change-lowering.cc:10: #include
"src/compiler/node-properties-inl.h"
Do we need this header?

https://codereview.chromium.org/509343002/diff/160001/src/compiler/opcodes.h
File src/compiler/opcodes.h (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/opcodes.h#...
src/compiler/opcodes.h:24: #define CONTROL_OP_LIST(V) \
You got this macro twice.

https://codereview.chromium.org/509343002/diff/160001/src/compiler/verifier.cc
File src/compiler/verifier.cc (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/verifier.c...
src/compiler/verifier.cc:59: Bounds bounds(Node* node) {
There is a method for this now, yes?

[Michael Starzinger, 2014-10-14 18:28:27]

One issue that I feel pretty strongly about. Please address it before landing.

https://codereview.chromium.org/509343002/diff/160001/src/compiler/pipeline.h
File src/compiler/pipeline.h (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/pipeline.h...
src/compiler/pipeline.h:13: #include "src/compiler/verifier.h"
Nope! Please don't inlclude any other header in this file from the compiler
directory. The reason is that pipeline.h is the only header allowed to be
included from outside the compiler directory and this leaks all definitions from
the verifier.h file to outside the compiler directory.

[rossberg, 2014-10-15 06:47:58]

https://codereview.chromium.org/509343002/diff/160001/src/compiler/pipeline.h
File src/compiler/pipeline.h (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/pipeline.h...
src/compiler/pipeline.h:13: #include "src/compiler/verifier.h"
On 2014/10/14 18:28:27, Michael Starzinger wrote:
> Nope! Please don't inlclude any other header in this file from the compiler
> directory. The reason is that pipeline.h is the only header allowed to be
> included from outside the compiler directory and this leaks all definitions
from
> the verifier.h file to outside the compiler directory.

Sigh. Proliferation like this is just one ugly consequence of not making the
graph sufficiently self-describing with respect to its being typed or not. You
asked for that.

I will try to make VerifyAndPrintGraph and its dependencies from private methods
into local static functions in pipeline.cc -- or forego best practice and use a
boolean argument. Whatever turns out less hacky.

[rossberg, 2014-10-15 08:59:08]

https://codereview.chromium.org/509343002/diff/160001/src/compiler/change-low...
File src/compiler/change-lowering.cc (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/change-low...
src/compiler/change-lowering.cc:10: #include
"src/compiler/node-properties-inl.h"
On 2014/10/14 16:13:22, titzer wrote:
> Do we need this header?

No.

https://codereview.chromium.org/509343002/diff/160001/src/compiler/opcodes.h
File src/compiler/opcodes.h (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/opcodes.h#...
src/compiler/opcodes.h:24: #define CONTROL_OP_LIST(V) \
On 2014/10/14 16:13:22, titzer wrote:
> You got this macro twice.

Huh. Probably merge weirdness.

https://codereview.chromium.org/509343002/diff/160001/src/compiler/pipeline.h
File src/compiler/pipeline.h (right):

https://codereview.chromium.org/509343002/diff/160001/src/compiler/pipeline.h...
src/compiler/pipeline.h:13: #include "src/compiler/verifier.h"
On 2014/10/15 06:47:58, rossberg wrote:
> On 2014/10/14 18:28:27, Michael Starzinger wrote:
> > Nope! Please don't inlclude any other header in this file from the compiler
> > directory. The reason is that pipeline.h is the only header allowed to be
> > included from outside the compiler directory and this leaks all definitions
> from
> > the verifier.h file to outside the compiler directory.
> 
> Sigh. Proliferation like this is just one ugly consequence of not making the
> graph sufficiently self-describing with respect to its being typed or not. You
> asked for that.
> 
> I will try to make VerifyAndPrintGraph and its dependencies from private
methods
> into local static functions in pipeline.cc -- or forego best practice and use
a
> boolean argument. Whatever turns out less hacky.

Done.

[rossberg, 2014-10-15 12:15:43]

Accidentally committed from wrong branch as
https://codereview.chromium.org/658543002, closing this one.