From d1a6dfaf4d1be19764faa986fd23b9657fbe7f94 Mon Sep 17 00:00:00 2001 From: danno Date: Wed, 22 Jul 2015 11:27:16 -0700 Subject: [PATCH] [turbofan]: Fix tail calls edge cases and add tests Review URL: https://codereview.chromium.org/1245523002 Cr-Commit-Position: refs/heads/master@{#29791} --- src/compiler/linkage.cc | 27 +- .../compiler/linkage-tail-call-unittest.cc | 320 +++++++++++++++++++++ test/unittests/unittests.gyp | 1 + 3 files changed, 344 insertions(+), 4 deletions(-) create mode 100644 test/unittests/compiler/linkage-tail-call-unittest.cc diff --git a/src/compiler/linkage.cc b/src/compiler/linkage.cc index 691a3b3..a460f4a 100644 --- a/src/compiler/linkage.cc +++ b/src/compiler/linkage.cc @@ -53,6 +53,25 @@ bool CallDescriptor::HasSameReturnLocationsAs( bool CallDescriptor::CanTailCall(const Node* node) const { + // Determine the number of stack parameters passed in + size_t stack_params = 0; + for (size_t i = 0; i < InputCount(); ++i) { + if (!GetInputLocation(i).is_register()) { + ++stack_params; + } + } + // Ensure the input linkage contains the stack parameters in the right order + size_t current_stack_param = 0; + for (size_t i = 0; i < InputCount(); ++i) { + if (!GetInputLocation(i).is_register()) { + if (GetInputLocation(i) != + LinkageLocation(static_cast(current_stack_param) - + static_cast(stack_params))) { + return false; + } + ++current_stack_param; + } + } // Tail calling is currently allowed if return locations match and all // parameters are either in registers or on the stack but match exactly in // number and content. @@ -60,10 +79,9 @@ bool CallDescriptor::CanTailCall(const Node* node) const { if (!HasSameReturnLocationsAs(other)) return false; size_t current_input = 0; size_t other_input = 0; - size_t stack_parameter = 0; while (true) { if (other_input >= other->InputCount()) { - while (current_input <= InputCount()) { + while (current_input < InputCount()) { if (!GetInputLocation(current_input).is_register()) { return false; } @@ -96,11 +114,12 @@ bool CallDescriptor::CanTailCall(const Node* node) const { if (input->opcode() != IrOpcode::kParameter) { return false; } + // Make sure that the parameter input passed through to the tail call + // corresponds to the correct stack slot. size_t param_index = ParameterIndexOf(input->op()); - if (param_index != stack_parameter) { + if (param_index != current_input - 1) { return false; } - ++stack_parameter; ++current_input; ++other_input; } diff --git a/test/unittests/compiler/linkage-tail-call-unittest.cc b/test/unittests/compiler/linkage-tail-call-unittest.cc new file mode 100644 index 0000000..cd9ba00 --- /dev/null +++ b/test/unittests/compiler/linkage-tail-call-unittest.cc @@ -0,0 +1,320 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/compiler/common-operator.h" +#include "src/compiler/graph.h" +#include "src/compiler/linkage.h" +#include "src/compiler/node.h" +#include "test/unittests/test-utils.h" + +namespace v8 { +namespace internal { +namespace compiler { + +namespace { + +MachineType kMachineTypes[] = {kMachAnyTagged, kMachAnyTagged, kMachAnyTagged, + kMachAnyTagged, kMachAnyTagged, kMachAnyTagged, + kMachAnyTagged, kMachAnyTagged}; +} + +class LinkageTailCall : public TestWithZone { + protected: + CallDescriptor* NewStandardCallDescriptor(LocationSignature* locations) { + DCHECK(arraysize(kMachineTypes) >= + locations->return_count() + locations->parameter_count()); + MachineSignature* types = new (zone()) MachineSignature( + locations->return_count(), locations->parameter_count(), kMachineTypes); + return new (zone()) + CallDescriptor(CallDescriptor::kCallCodeObject, kMachAnyTagged, + LinkageLocation::AnyRegister(), + types, // machine_sig + locations, // location_sig + 0, // js_parameter_count + Operator::kNoProperties, // properties + 0, // callee-saved + 0, // callee-saved fp + CallDescriptor::kNoFlags, // flags, + ""); + } + + LinkageLocation StackLocation(int loc) { return LinkageLocation(-loc); } + + LinkageLocation RegisterLocation(int loc) { return LinkageLocation(loc); } +}; + + +TEST_F(LinkageTailCall, EmptyToEmpty) { + LocationSignature locations(0, 0, nullptr); + CallDescriptor* desc = NewStandardCallDescriptor(&locations); + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_TRUE(desc->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, SameReturn) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0)}; + LocationSignature locations1(1, 0, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Callee + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations1); + + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc2); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_TRUE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, DifferingReturn) { + // Caller + LinkageLocation location_array1[] = {RegisterLocation(0)}; + LocationSignature locations1(1, 0, location_array1); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Callee + LinkageLocation location_array2[] = {RegisterLocation(1)}; + LocationSignature locations2(1, 0, location_array2); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc2); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_FALSE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MoreRegisterParametersCallee) { + // Caller + LinkageLocation location_array1[] = {RegisterLocation(0)}; + LocationSignature locations1(1, 0, location_array1); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Callee + LinkageLocation location_array2[] = {RegisterLocation(0), + RegisterLocation(0)}; + LocationSignature locations2(1, 1, location_array2); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc2); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_TRUE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MoreRegisterParametersCaller) { + // Caller + LinkageLocation location_array1[] = {RegisterLocation(0), + RegisterLocation(0)}; + LocationSignature locations1(1, 1, location_array1); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Callee + LinkageLocation location_array2[] = {RegisterLocation(0)}; + LocationSignature locations2(1, 0, location_array2); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc2); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_TRUE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MoreRegisterAndStackParametersCallee) { + // Caller + LinkageLocation location_array1[] = {RegisterLocation(0)}; + LocationSignature locations1(1, 0, location_array1); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Callee + LinkageLocation location_array2[] = {RegisterLocation(0), RegisterLocation(0), + RegisterLocation(1), StackLocation(1)}; + LocationSignature locations2(1, 3, location_array2); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc2); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_FALSE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MoreRegisterAndStackParametersCaller) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), RegisterLocation(0), + RegisterLocation(1), StackLocation(1)}; + LocationSignature locations1(1, 3, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Callee + LinkageLocation location_array2[] = {RegisterLocation(0)}; + LocationSignature locations2(1, 0, location_array2); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + const Operator* op = common.Call(desc2); + Node* const node = Node::New(zone(), 1, op, 0, nullptr, false); + EXPECT_FALSE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MatchingStackParameters) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), StackLocation(3), + StackLocation(2), StackLocation(1)}; + LocationSignature locations1(1, 3, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Caller + LocationSignature locations2(1, 3, location_array); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations1); + + CommonOperatorBuilder common(zone()); + Node* p0 = Node::New(zone(), 0, nullptr, 0, nullptr, false); + Node* p1 = Node::New(zone(), 0, common.Parameter(0), 0, nullptr, false); + Node* p2 = Node::New(zone(), 0, common.Parameter(1), 0, nullptr, false); + Node* p3 = Node::New(zone(), 0, common.Parameter(2), 0, nullptr, false); + Node* parameters[] = {p0, p1, p2, p3}; + const Operator* op = common.Call(desc2); + Node* const node = + Node::New(zone(), 1, op, arraysize(parameters), parameters, false); + EXPECT_TRUE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, NonMatchingStackParameters) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), StackLocation(3), + StackLocation(2), StackLocation(1)}; + LocationSignature locations1(1, 3, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Caller + LocationSignature locations2(1, 3, location_array); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations1); + + CommonOperatorBuilder common(zone()); + Node* p0 = Node::New(zone(), 0, nullptr, 0, nullptr, false); + Node* p1 = Node::New(zone(), 0, common.Parameter(0), 0, nullptr, false); + Node* p2 = Node::New(zone(), 0, common.Parameter(2), 0, nullptr, false); + Node* p3 = Node::New(zone(), 0, common.Parameter(1), 0, nullptr, false); + Node* parameters[] = {p0, p1, p2, p3}; + const Operator* op = common.Call(desc2); + Node* const node = + Node::New(zone(), 1, op, arraysize(parameters), parameters, false); + EXPECT_FALSE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MatchingStackParametersExtraCallerRegisters) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), StackLocation(3), + StackLocation(2), StackLocation(1), + RegisterLocation(0), RegisterLocation(1)}; + LocationSignature locations1(1, 5, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Caller + LocationSignature locations2(1, 3, location_array); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations1); + + CommonOperatorBuilder common(zone()); + Node* p0 = Node::New(zone(), 0, nullptr, 0, nullptr, false); + Node* p1 = Node::New(zone(), 0, common.Parameter(0), 0, nullptr, false); + Node* p2 = Node::New(zone(), 0, common.Parameter(1), 0, nullptr, false); + Node* p3 = Node::New(zone(), 0, common.Parameter(2), 0, nullptr, false); + Node* parameters[] = {p0, p1, p2, p3}; + const Operator* op = common.Call(desc2); + Node* const node = + Node::New(zone(), 1, op, arraysize(parameters), parameters, false); + EXPECT_TRUE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MatchingStackParametersExtraCalleeRegisters) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), StackLocation(3), + StackLocation(2), StackLocation(1), + RegisterLocation(0), RegisterLocation(1)}; + LocationSignature locations1(1, 3, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Caller + LocationSignature locations2(1, 5, location_array); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations1); + + CommonOperatorBuilder common(zone()); + Node* p0 = Node::New(zone(), 0, nullptr, 0, nullptr, false); + Node* p1 = Node::New(zone(), 0, common.Parameter(0), 0, nullptr, false); + Node* p2 = Node::New(zone(), 0, common.Parameter(1), 0, nullptr, false); + Node* p3 = Node::New(zone(), 0, common.Parameter(2), 0, nullptr, false); + Node* p4 = Node::New(zone(), 0, common.Parameter(3), 0, nullptr, false); + Node* parameters[] = {p0, p1, p2, p3, p4}; + const Operator* op = common.Call(desc2); + Node* const node = + Node::New(zone(), 1, op, arraysize(parameters), parameters, false); + EXPECT_TRUE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MatchingStackParametersExtraCallerRegistersAndStack) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), StackLocation(3), + StackLocation(2), StackLocation(1), + RegisterLocation(0), StackLocation(4)}; + LocationSignature locations1(1, 5, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Caller + LocationSignature locations2(1, 3, location_array); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + Node* p0 = Node::New(zone(), 0, nullptr, 0, nullptr, false); + Node* p1 = Node::New(zone(), 0, common.Parameter(0), 0, nullptr, false); + Node* p2 = Node::New(zone(), 0, common.Parameter(1), 0, nullptr, false); + Node* p3 = Node::New(zone(), 0, common.Parameter(2), 0, nullptr, false); + Node* p4 = Node::New(zone(), 0, common.Parameter(3), 0, nullptr, false); + Node* parameters[] = {p0, p1, p2, p3, p4}; + const Operator* op = common.Call(desc2); + Node* const node = + Node::New(zone(), 1, op, arraysize(parameters), parameters, false); + EXPECT_FALSE(desc1->CanTailCall(node)); +} + + +TEST_F(LinkageTailCall, MatchingStackParametersExtraCalleeRegistersAndStack) { + // Caller + LinkageLocation location_array[] = {RegisterLocation(0), StackLocation(3), + StackLocation(2), RegisterLocation(0), + RegisterLocation(1), StackLocation(4)}; + LocationSignature locations1(1, 3, location_array); + CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1); + + // Caller + LocationSignature locations2(1, 5, location_array); + CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2); + + CommonOperatorBuilder common(zone()); + Node* p0 = Node::New(zone(), 0, nullptr, 0, nullptr, false); + Node* p1 = Node::New(zone(), 0, common.Parameter(0), 0, nullptr, false); + Node* p2 = Node::New(zone(), 0, common.Parameter(1), 0, nullptr, false); + Node* p3 = Node::New(zone(), 0, common.Parameter(2), 0, nullptr, false); + Node* p4 = Node::New(zone(), 0, common.Parameter(3), 0, nullptr, false); + Node* parameters[] = {p0, p1, p2, p3, p4}; + const Operator* op = common.Call(desc2); + Node* const node = + Node::New(zone(), 1, op, arraysize(parameters), parameters, false); + EXPECT_FALSE(desc1->CanTailCall(node)); +} + +} // namespace compiler +} // namespace internal +} // namespace v8 diff --git a/test/unittests/unittests.gyp b/test/unittests/unittests.gyp index baa186e..7f9d057 100644 --- a/test/unittests/unittests.gyp +++ b/test/unittests/unittests.gyp @@ -66,6 +66,7 @@ 'compiler/js-operator-unittest.cc', 'compiler/js-typed-lowering-unittest.cc', 'compiler/js-type-feedback-unittest.cc', + 'compiler/linkage-tail-call-unittest.cc', 'compiler/liveness-analyzer-unittest.cc', 'compiler/load-elimination-unittest.cc', 'compiler/loop-peeling-unittest.cc', -- 2.7.4