1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2014 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <limits> 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/graph.h" 8014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/node.h" 9014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/operator.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/value-numbering-reducer.h" 11958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "test/unittests/test-utils.h" 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 17958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierstruct TestOperator : public Operator { 18958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier TestOperator(Operator::Opcode opcode, Operator::Properties properties, 19958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t value_in, size_t value_out) 20958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : Operator(opcode, properties, "TestOp", value_in, 0, 0, value_out, 0, 21958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 0) {} 22958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 25014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstatic const TestOperator kOp0(0, Operator::kIdempotent, 0, 1); 26014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstatic const TestOperator kOp1(1, Operator::kIdempotent, 1, 1); 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass ValueNumberingReducerTest : public TestWithZone { 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ValueNumberingReducerTest() : graph_(zone()), reducer_(zone()) {} 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch protected: 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Reduction Reduce(Node* node) { return reducer_.Reduce(node); } 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Graph* graph() { return &graph_; } 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Graph graph_; 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ValueNumberingReducer reducer_; 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST_F(ValueNumberingReducerTest, AllInputsAreChecked) { 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* na = graph()->NewNode(&kOp0); 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* nb = graph()->NewNode(&kOp0); 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* n1 = graph()->NewNode(&kOp1, na); 48014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* n2 = graph()->NewNode(&kOp1, nb); 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(Reduce(n1).Changed()); 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(Reduce(n2).Changed()); 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST_F(ValueNumberingReducerTest, DeadNodesAreNeverReturned) { 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* n0 = graph()->NewNode(&kOp0); 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* n1 = graph()->NewNode(&kOp1, n0); 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(Reduce(n1).Changed()); 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch n1->Kill(); 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(Reduce(graph()->NewNode(&kOp1, n0)).Changed()); 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 63958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierTEST_F(ValueNumberingReducerTest, OnlyEliminatableNodesAreReduced) { 64958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier TestOperator op(0, Operator::kNoProperties, 0, 1); 65958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* n0 = graph()->NewNode(&op); 66958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* n1 = graph()->NewNode(&op); 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier EXPECT_FALSE(Reduce(n0).Changed()); 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier EXPECT_FALSE(Reduce(n1).Changed()); 69958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 70958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 71958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST_F(ValueNumberingReducerTest, OperatorEqualityNotIdentity) { 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const size_t kMaxInputCount = 16; 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* inputs[kMaxInputCount]; 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (size_t i = 0; i < arraysize(inputs); ++i) { 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Operator::Opcode opcode = static_cast<Operator::Opcode>(kMaxInputCount + i); 77958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier inputs[i] = graph()->NewNode( 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new (zone()) TestOperator(opcode, Operator::kIdempotent, 0, 1)); 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) { 81958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const TestOperator op1(static_cast<Operator::Opcode>(input_count), 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Operator::kIdempotent, input_count, 1); 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* n1 = graph()->NewNode(&op1, static_cast<int>(input_count), inputs); 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Reduction r1 = Reduce(n1); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(r1.Changed()); 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 87958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const TestOperator op2(static_cast<Operator::Opcode>(input_count), 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Operator::kIdempotent, input_count, 1); 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* n2 = graph()->NewNode(&op2, static_cast<int>(input_count), inputs); 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Reduction r2 = Reduce(n2); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_TRUE(r2.Changed()); 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_EQ(n1, r2.replacement()); 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST_F(ValueNumberingReducerTest, SubsequentReductionsYieldTheSameNode) { 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const size_t kMaxInputCount = 16; 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* inputs[kMaxInputCount]; 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (size_t i = 0; i < arraysize(inputs); ++i) { 101014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Operator::Opcode opcode = static_cast<Operator::Opcode>(2 + i); 102958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier inputs[i] = graph()->NewNode( 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new (zone()) TestOperator(opcode, Operator::kIdempotent, 0, 1)); 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) { 106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const TestOperator op1(1, Operator::kIdempotent, input_count, 1); 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* n = graph()->NewNode(&op1, static_cast<int>(input_count), inputs); 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Reduction r = Reduce(n); 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(r.Changed()); 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch r = Reduce(graph()->NewNode(&op1, static_cast<int>(input_count), inputs)); 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ASSERT_TRUE(r.Changed()); 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_EQ(n, r.replacement()); 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch r = Reduce(graph()->NewNode(&op1, static_cast<int>(input_count), inputs)); 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ASSERT_TRUE(r.Changed()); 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_EQ(n, r.replacement()); 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST_F(ValueNumberingReducerTest, WontReplaceNodeWithItself) { 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* n = graph()->NewNode(&kOp0); 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(Reduce(n).Changed()); 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EXPECT_FALSE(Reduce(n).Changed()); 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace compiler 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace internal 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace v8 131