[turbofan]: Fix tail calls edge cases and add tests

test/unittests/compiler/linkage-tail-call-unittest.cc

Index: test/unittests/compiler/linkage-tail-call-unittest.cc
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 0000000000000000000000000000000000000000..04fdff1652603b0f96f0b028f9eb45374f9c3c3d
--- /dev/null
+++ b/test/unittests/compiler/linkage-tail-call-unittest.cc
@@ -0,0 +1,463 @@
+// 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 {
+
+class LinkageTailCall : public TestWithZone {
+ protected:
+  CallDescriptor* NewStandardCallDescriptor(
+      LocationSignature::Builder* locations, MachineSignature::Builder* types) {
+    return new (zone())
+        CallDescriptor(CallDescriptor::kCallCodeObject, kMachAnyTagged,
+                       LinkageLocation::AnyRegister(),
+                       types->Build(),            // machine_sig
+                       locations->Build(),        // 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::Builder locations(zone(), 0, 0);
+  MachineSignature::Builder types(zone(), 0, 0);
+
+  CallDescriptor* desc = NewStandardCallDescriptor(&locations, &types);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 0);

[titzer, 2015/07/21 11:48:52]

You don't have to use the Signature::Builder every time; you can just have a
static array and pass it directly to the constructor of Signature.

+  MachineSignature::Builder types1(zone(), 1, 0);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 0);
+  MachineSignature::Builder types2(zone(), 1, 0);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 0);
+  MachineSignature::Builder types1(zone(), 1, 0);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 0);
+  MachineSignature::Builder types2(zone(), 1, 0);
+  locations2.AddReturn(StackLocation(1));
+  types2.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 0);
+  MachineSignature::Builder types1(zone(), 1, 0);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 1);
+  MachineSignature::Builder types2(zone(), 1, 1);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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, MoreRegisterParametersCalleer) {
+  // Caller
+  LocationSignature::Builder locations1(zone(), 1, 1);
+  MachineSignature::Builder types1(zone(), 1, 1);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 0);
+  MachineSignature::Builder types2(zone(), 1, 0);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 0);
+  MachineSignature::Builder types1(zone(), 1, 0);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 3);
+  MachineSignature::Builder types2(zone(), 1, 3);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(0));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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, MoreRegisterAndStackParametersCalleer) {
+  // Caller
+  LocationSignature::Builder locations1(zone(), 1, 3);
+  MachineSignature::Builder types1(zone(), 1, 3);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(0));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 0);
+  MachineSignature::Builder types2(zone(), 1, 0);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 3);
+  MachineSignature::Builder types1(zone(), 1, 3);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(3));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 3);
+  MachineSignature::Builder types2(zone(), 1, 3);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(3));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 3);
+  MachineSignature::Builder types1(zone(), 1, 3);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(3));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 3);
+  MachineSignature::Builder types2(zone(), 1, 3);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(3));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 5);
+  MachineSignature::Builder types1(zone(), 1, 5);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(3));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 3);
+  MachineSignature::Builder types2(zone(), 1, 3);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(3));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 3);
+  MachineSignature::Builder types1(zone(), 1, 3);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(3));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 5);
+  MachineSignature::Builder types2(zone(), 1, 5);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(3));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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
+  LocationSignature::Builder locations1(zone(), 1, 6);
+  MachineSignature::Builder types1(zone(), 1, 6);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(3));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(RegisterLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(4));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 3);
+  MachineSignature::Builder types2(zone(), 1, 3);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(3));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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_FALSE(desc1->CanTailCall(node));
+}
+
+
+TEST_F(LinkageTailCall, MatchingStackParametersExtraCalleeRegistersAndStack) {
+  // Caller
+  LocationSignature::Builder locations1(zone(), 1, 3);
+  MachineSignature::Builder types1(zone(), 1, 3);
+  locations1.AddReturn(RegisterLocation(0));
+  types1.AddReturn(kMachAnyTagged);
+  locations1.AddParam(StackLocation(3));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(2));
+  types1.AddParam(kMachAnyTagged);
+  locations1.AddParam(StackLocation(1));
+  types1.AddParam(kMachAnyTagged);
+  CallDescriptor* desc1 = NewStandardCallDescriptor(&locations1, &types1);
+
+  // Callee
+  LocationSignature::Builder locations2(zone(), 1, 6);
+  MachineSignature::Builder types2(zone(), 1, 6);
+  locations2.AddReturn(RegisterLocation(0));
+  types2.AddReturn(kMachAnyTagged);
+  locations2.AddParam(StackLocation(3));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(1));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(RegisterLocation(2));
+  types2.AddParam(kMachAnyTagged);
+  locations2.AddParam(StackLocation(4));
+  types2.AddParam(kMachAnyTagged);
+  CallDescriptor* desc2 = NewStandardCallDescriptor(&locations2, &types2);
+
+  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