[turbofan] add gap move verifier

[turbofan] add gap move verifier

R=jarin@chromium.org

BUG=

Committed: https://code.google.com/p/v8/source/detail?r=25300

[dcarney, 2014-11-11 12:40:47]

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

[dcarney, 2014-11-11 12:40:56]

ptal

[Jarin, 2014-11-12 08:13:35]

Very cool stuff.

I have bunch of comments and questions.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/pipeline.cc
File src/compiler/pipeline.cc (right):

https://codereview.chromium.org/704193007/diff/260001/src/compiler/pipeline.c...
src/compiler/pipeline.cc:579: RegisterAllocatorVerifier* verifier = NULL;
I think it would be better if we could avoid the pointers and instead just use
lexical scoping and on-stack objects.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
File src/compiler/register-allocator-verifier.cc (right):

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:220: struct OperandLess {
Just use a function here, no need to use a functor.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:318: 
Could we have a comment describing what we verify here?

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:334: auto* outgoing =
outgoing_mappings[block_index];
Perhaps rename outgoing => current.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:340: size_t predecessor_index =
block->predecessors()[0].ToSize();
Could you add the comment here that explains that the rest of the phis is
checked in another pass below?

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:342: auto* incoming =
outgoing_mappings[predecessor_index];
Why is this working with loops? Is it because the backedge is never the first
predecessor?

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:344: // Update incoming map with
phis.  Valid because of edge split form.
Why do not we copy the incoming to the outgoing and then run the phis?

That way there would be tighter correspondence between the mappings and blocks,
no?

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:399: // TODO(dcarney): run a
verification that this mapping is the same as the
Yeah, it would be nice if we could apply the phis during the first phase and
then unmap all the locations where the mappings disagree, but that would not
check loops...

If you want to check the agreement w.r.t. to liveness, then you will also have
to compute the liveness (or get it from the allocator and check it, which could
be easier and give us more coverage).

https://codereview.chromium.org/704193007/diff/260001/test/cctest/compiler/te...
File test/cctest/compiler/test-run-machops.cc (left):

https://codereview.chromium.org/704193007/diff/260001/test/cctest/compiler/te...
test/cctest/compiler/test-run-machops.cc:132: TEST(RunRedundantBranch1) {
Why did you remove the tests?

[dcarney, 2014-11-12 08:53:32]

https://codereview.chromium.org/704193007/diff/260001/src/compiler/pipeline.cc
File src/compiler/pipeline.cc (right):

https://codereview.chromium.org/704193007/diff/260001/src/compiler/pipeline.c...
src/compiler/pipeline.cc:579: RegisterAllocatorVerifier* verifier = NULL;
On 2014/11/12 08:13:35, jarin wrote:
> I think it would be better if we could avoid the pointers and instead just use
> lexical scoping and on-stack objects.

Done.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
File src/compiler/register-allocator-verifier.cc (right):

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:220: struct OperandLess {
On 2014/11/12 08:13:35, jarin wrote:
> Just use a function here, no need to use a functor.

std::map seemed to want this...

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:318: 
On 2014/11/12 08:13:35, jarin wrote:
> Could we have a comment describing what we verify here?

Done.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:334: auto* outgoing =
outgoing_mappings[block_index];
On 2014/11/12 08:13:35, jarin wrote:
> Perhaps rename outgoing => current.

Done.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:340: size_t predecessor_index =
block->predecessors()[0].ToSize();
On 2014/11/12 08:13:35, jarin wrote:
> Could you add the comment here that explains that the rest of the phis is
> checked in another pass below?

Done.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:342: auto* incoming =
outgoing_mappings[predecessor_index];
On 2014/11/12 08:13:35, jarin wrote:
> Why is this working with loops? Is it because the backedge is never the first
> predecessor?

correct

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:344: // Update incoming map with
phis.  Valid because of edge split form.
On 2014/11/12 08:13:35, jarin wrote:
> Why do not we copy the incoming to the outgoing and then run the phis?
> 
> That way there would be tighter correspondence between the mappings and
blocks,
> no?

I need to do this to ensure that I can do RunPhis on the other predecessors
below.

https://codereview.chromium.org/704193007/diff/260001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:399: // TODO(dcarney): run a
verification that this mapping is the same as the
On 2014/11/12 08:13:35, jarin wrote:
> Yeah, it would be nice if we could apply the phis during the first phase and
> then unmap all the locations where the mappings disagree, but that would not
> check loops...
> 
> If you want to check the agreement w.r.t. to liveness, then you will also have
> to compute the liveness (or get it from the allocator and check it, which
could
> be easier and give us more coverage).

I don't want to use this register allocator if I can avoid it, since this code
it supposed to verify the register allocator did the right thing, but that might
be the only reasonable way.

https://codereview.chromium.org/704193007/diff/260001/test/cctest/compiler/te...
File test/cctest/compiler/test-run-machops.cc (left):

https://codereview.chromium.org/704193007/diff/260001/test/cctest/compiler/te...
test/cctest/compiler/test-run-machops.cc:132: TEST(RunRedundantBranch1) {
On 2014/11/12 08:13:35, jarin wrote:
> Why did you remove the tests?

they are not in edge split form.  the register allocator does not complain about
this because there are no phis, but these tests are just wrong.

[dcarney, 2014-11-12 11:20:11]

added second pass - cleaned some stuff up - ptal

[Jarin, 2014-11-12 14:48:47]

lgtm.

https://codereview.chromium.org/704193007/diff/380001/src/compiler/register-a...
File src/compiler/register-allocator-verifier.cc (right):

https://codereview.chromium.org/704193007/diff/380001/src/compiler/register-a...
src/compiler/register-allocator-verifier.cc:390: for (size_t phi =
block->PredecessorCount() - 1; true; --phi) {
Please, rename to phi_input (or something that makes it clearer that is a
predecessor index).

[dcarney, 2014-11-12 14:53:46]

Committed patchset #20 (id:380001) manually as 25300 (presubmit successful).