LCOV - code coverage report
Current view: top level - test/unittests/compiler - graph-reducer-unittest.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 452 464 97.4 %
Date: 2019-04-17 Functions: 70 122 57.4 %

          Line data    Source code
       1             : // Copyright 2014 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/compiler/common-operator.h"
       6             : #include "src/compiler/graph.h"
       7             : #include "src/compiler/node.h"
       8             : #include "src/compiler/node-properties.h"
       9             : #include "src/compiler/operator.h"
      10             : #include "test/unittests/compiler/graph-reducer-unittest.h"
      11             : #include "test/unittests/test-utils.h"
      12             : 
      13             : using testing::_;
      14             : using testing::DefaultValue;
      15             : using testing::ElementsAre;
      16             : using testing::Return;
      17             : using testing::Sequence;
      18             : using testing::StrictMock;
      19             : using testing::UnorderedElementsAre;
      20             : 
      21             : namespace v8 {
      22             : namespace internal {
      23             : namespace compiler {
      24             : namespace graph_reducer_unittest {
      25             : 
      26             : namespace {
      27             : 
      28       55584 : struct TestOperator : public Operator {
      29             :   TestOperator(Operator::Opcode opcode, Operator::Properties properties,
      30             :                const char* op_name, size_t value_in, size_t value_out)
      31       27792 :       : Operator(opcode, properties, op_name, value_in, 0, 0, value_out, 0, 0) {
      32             :   }
      33             : };
      34             : 
      35             : 
      36             : const uint8_t kOpcodeA0 = 10;
      37             : const uint8_t kOpcodeA1 = 11;
      38             : const uint8_t kOpcodeA2 = 12;
      39             : const uint8_t kOpcodeB0 = 20;
      40             : const uint8_t kOpcodeB1 = 21;
      41             : const uint8_t kOpcodeB2 = 22;
      42             : const uint8_t kOpcodeC0 = 30;
      43             : const uint8_t kOpcodeC1 = 31;
      44             : const uint8_t kOpcodeC2 = 32;
      45             : 
      46        3088 : static TestOperator kOpA0(kOpcodeA0, Operator::kNoWrite, "opa1", 0, 1);
      47        3088 : static TestOperator kOpA1(kOpcodeA1, Operator::kNoProperties, "opa2", 1, 1);
      48        3088 : static TestOperator kOpA2(kOpcodeA2, Operator::kNoProperties, "opa3", 2, 1);
      49        3088 : static TestOperator kOpB0(kOpcodeB0, Operator::kNoWrite, "opb0", 0, 1);
      50        3088 : static TestOperator kOpB1(kOpcodeB1, Operator::kNoWrite, "opb1", 1, 1);
      51        3088 : static TestOperator kOpB2(kOpcodeB2, Operator::kNoWrite, "opb2", 2, 1);
      52        3088 : static TestOperator kOpC0(kOpcodeC0, Operator::kNoWrite, "opc0", 0, 1);
      53        3088 : static TestOperator kOpC1(kOpcodeC1, Operator::kNoWrite, "opc1", 1, 1);
      54        3088 : static TestOperator kOpC2(kOpcodeC2, Operator::kNoWrite, "opc2", 2, 1);
      55             : 
      56          24 : struct MockReducer : public Reducer {
      57           0 :   MOCK_CONST_METHOD0(reducer_name, const char*());
      58          60 :   MOCK_METHOD1(Reduce, Reduction(Node*));
      59             : };
      60             : 
      61             : 
      62             : // Replaces all "A" operators with "B" operators without creating new nodes.
      63         199 : class InPlaceABReducer final : public Reducer {
      64             :  public:
      65           0 :   const char* reducer_name() const override { return "InPlaceABReducer"; }
      66         426 :   Reduction Reduce(Node* node) final {
      67         426 :     switch (node->op()->opcode()) {
      68             :       case kOpcodeA0:
      69         202 :         EXPECT_EQ(0, node->InputCount());
      70         101 :         NodeProperties::ChangeOp(node, &kOpB0);
      71             :         return Replace(node);
      72             :       case kOpcodeA1:
      73          14 :         EXPECT_EQ(1, node->InputCount());
      74           7 :         NodeProperties::ChangeOp(node, &kOpB1);
      75             :         return Replace(node);
      76             :       case kOpcodeA2:
      77         580 :         EXPECT_EQ(2, node->InputCount());
      78         290 :         NodeProperties::ChangeOp(node, &kOpB2);
      79             :         return Replace(node);
      80             :     }
      81             :     return NoChange();
      82             :   }
      83             : };
      84             : 
      85             : 
      86             : // Replaces all "A" operators with "B" operators by allocating new nodes.
      87           1 : class NewABReducer final : public Reducer {
      88             :  public:
      89           1 :   explicit NewABReducer(Graph* graph) : graph_(graph) {}
      90             : 
      91           0 :   const char* reducer_name() const override { return "NewABReducer"; }
      92             : 
      93          16 :   Reduction Reduce(Node* node) final {
      94          16 :     switch (node->op()->opcode()) {
      95             :       case kOpcodeA0:
      96           2 :         EXPECT_EQ(0, node->InputCount());
      97           1 :         return Replace(graph_->NewNode(&kOpB0));
      98             :       case kOpcodeA1:
      99           4 :         EXPECT_EQ(1, node->InputCount());
     100           2 :         return Replace(graph_->NewNode(&kOpB1, node->InputAt(0)));
     101             :       case kOpcodeA2:
     102           2 :         EXPECT_EQ(2, node->InputCount());
     103             :         return Replace(
     104           1 :             graph_->NewNode(&kOpB2, node->InputAt(0), node->InputAt(1)));
     105             :     }
     106             :     return NoChange();
     107             :   }
     108             : 
     109             :  private:
     110             :   Graph* const graph_;
     111             : };
     112             : 
     113             : 
     114             : // Wraps all "kOpA0" nodes in "kOpB1" operators by allocating new nodes.
     115           1 : class A0Wrapper final : public Reducer {
     116             :  public:
     117           1 :   explicit A0Wrapper(Graph* graph) : graph_(graph) {}
     118             : 
     119           0 :   const char* reducer_name() const override { return "A0Wrapper"; }
     120             : 
     121           2 :   Reduction Reduce(Node* node) final {
     122           2 :     switch (node->op()->opcode()) {
     123             :       case kOpcodeA0:
     124           2 :         EXPECT_EQ(0, node->InputCount());
     125           1 :         return Replace(graph_->NewNode(&kOpB1, node));
     126             :     }
     127             :     return NoChange();
     128             :   }
     129             : 
     130             :  private:
     131             :   Graph* const graph_;
     132             : };
     133             : 
     134             : 
     135             : // Wraps all "kOpB0" nodes in two "kOpC1" operators by allocating new nodes.
     136           1 : class B0Wrapper final : public Reducer {
     137             :  public:
     138           1 :   explicit B0Wrapper(Graph* graph) : graph_(graph) {}
     139             : 
     140           0 :   const char* reducer_name() const override { return "B0Wrapper"; }
     141             : 
     142           3 :   Reduction Reduce(Node* node) final {
     143           3 :     switch (node->op()->opcode()) {
     144             :       case kOpcodeB0:
     145           2 :         EXPECT_EQ(0, node->InputCount());
     146           2 :         return Replace(graph_->NewNode(&kOpC1, graph_->NewNode(&kOpC1, node)));
     147             :     }
     148             :     return NoChange();
     149             :   }
     150             : 
     151             :  private:
     152             :   Graph* const graph_;
     153             : };
     154             : 
     155             : 
     156             : // Replaces all "kOpA1" nodes with the first input.
     157         210 : class A1Forwarder final : public Reducer {
     158             :  public:
     159           0 :   const char* reducer_name() const override { return "A1Forwarder"; }
     160        1408 :   Reduction Reduce(Node* node) final {
     161        1408 :     switch (node->op()->opcode()) {
     162             :       case kOpcodeA1:
     163        1214 :         EXPECT_EQ(1, node->InputCount());
     164             :         return Replace(node->InputAt(0));
     165             :     }
     166             :     return NoChange();
     167             :   }
     168             : };
     169             : 
     170             : 
     171             : // Replaces all "kOpB1" nodes with the first input.
     172           1 : class B1Forwarder final : public Reducer {
     173             :  public:
     174           0 :   const char* reducer_name() const override { return "B1Forwarder"; }
     175           8 :   Reduction Reduce(Node* node) final {
     176           8 :     switch (node->op()->opcode()) {
     177             :       case kOpcodeB1:
     178           4 :         EXPECT_EQ(1, node->InputCount());
     179             :         return Replace(node->InputAt(0));
     180             :     }
     181             :     return NoChange();
     182             :   }
     183             : };
     184             : 
     185             : 
     186             : // Replaces all "B" operators with "C" operators without creating new nodes.
     187           4 : class InPlaceBCReducer final : public Reducer {
     188             :  public:
     189           0 :   const char* reducer_name() const override { return "InPlaceBCReducer"; }
     190          14 :   Reduction Reduce(Node* node) final {
     191          14 :     switch (node->op()->opcode()) {
     192             :       case kOpcodeB0:
     193           4 :         EXPECT_EQ(0, node->InputCount());
     194           2 :         NodeProperties::ChangeOp(node, &kOpC0);
     195             :         return Replace(node);
     196             :       case kOpcodeB1:
     197           4 :         EXPECT_EQ(1, node->InputCount());
     198           2 :         NodeProperties::ChangeOp(node, &kOpC1);
     199             :         return Replace(node);
     200             :       case kOpcodeB2:
     201           0 :         EXPECT_EQ(2, node->InputCount());
     202           0 :         NodeProperties::ChangeOp(node, &kOpC2);
     203             :         return Replace(node);
     204             :     }
     205             :     return NoChange();
     206             :   }
     207             : };
     208             : 
     209             : 
     210             : // Swaps the inputs to "kOp2A" and "kOp2B" nodes based on ids.
     211         193 : class AB2Sorter final : public Reducer {
     212             :  public:
     213           0 :   const char* reducer_name() const override { return "AB2Sorter"; }
     214        1364 :   Reduction Reduce(Node* node) final {
     215        1364 :     switch (node->op()->opcode()) {
     216             :       case kOpcodeA2:
     217             :       case kOpcodeB2:
     218        1164 :         EXPECT_EQ(2, node->InputCount());
     219             :         Node* x = node->InputAt(0);
     220             :         Node* y = node->InputAt(1);
     221         582 :         if (x->id() > y->id()) {
     222          51 :           node->ReplaceInput(0, y);
     223          51 :           node->ReplaceInput(1, x);
     224             :           return Replace(node);
     225             :         }
     226             :     }
     227             :     return NoChange();
     228             :   }
     229             : };
     230             : 
     231             : }  // namespace
     232             : 
     233             : 
     234          14 : class AdvancedReducerTest : public TestWithZone {
     235             :  public:
     236          14 :   AdvancedReducerTest() : graph_(zone()) {}
     237             : 
     238             :  protected:
     239           7 :   Graph* graph() { return &graph_; }
     240             : 
     241             :  private:
     242             :   Graph graph_;
     243             : };
     244             : 
     245             : 
     246       15444 : TEST_F(AdvancedReducerTest, Replace) {
     247             :   struct DummyReducer final : public AdvancedReducer {
     248             :     explicit DummyReducer(Editor* editor) : AdvancedReducer(editor) {}
     249             :     const char* reducer_name() const override { return "DummyReducer"; }
     250             :     Reduction Reduce(Node* node) final {
     251             :       Replace(node, node);
     252             :       return NoChange();
     253             :     }
     254             :   };
     255           1 :   StrictMock<MockAdvancedReducerEditor> e;
     256             :   DummyReducer r(&e);
     257             :   Node* node0 = graph()->NewNode(&kOpA0);
     258             :   Node* node1 = graph()->NewNode(&kOpA1, node0);
     259           4 :   EXPECT_CALL(e, Replace(node0, node0));
     260           4 :   EXPECT_CALL(e, Replace(node1, node1));
     261             :   EXPECT_FALSE(r.Reduce(node0).Changed());
     262             :   EXPECT_FALSE(r.Reduce(node1).Changed());
     263           1 : }
     264             : 
     265             : 
     266       15444 : TEST_F(AdvancedReducerTest, Revisit) {
     267             :   struct DummyReducer final : public AdvancedReducer {
     268             :     explicit DummyReducer(Editor* editor) : AdvancedReducer(editor) {}
     269             :     const char* reducer_name() const override { return "DummyReducer"; }
     270             :     Reduction Reduce(Node* node) final {
     271             :       Revisit(node);
     272             :       return NoChange();
     273             :     }
     274             :   };
     275           1 :   StrictMock<MockAdvancedReducerEditor> e;
     276             :   DummyReducer r(&e);
     277             :   Node* node0 = graph()->NewNode(&kOpA0);
     278             :   Node* node1 = graph()->NewNode(&kOpA1, node0);
     279           3 :   EXPECT_CALL(e, Revisit(node0));
     280           3 :   EXPECT_CALL(e, Revisit(node1));
     281             :   EXPECT_FALSE(r.Reduce(node0).Changed());
     282             :   EXPECT_FALSE(r.Reduce(node1).Changed());
     283           1 : }
     284             : 
     285             : 
     286             : namespace {
     287             : 
     288             : struct ReplaceWithValueReducer final : public AdvancedReducer {
     289             :   explicit ReplaceWithValueReducer(Editor* editor) : AdvancedReducer(editor) {}
     290             :   const char* reducer_name() const override {
     291             :     return "ReplaceWithValueReducer";
     292             :   }
     293             :   Reduction Reduce(Node* node) final { return NoChange(); }
     294             :   using AdvancedReducer::ReplaceWithValue;
     295             : };
     296             : 
     297        6176 : const Operator kMockOperator(IrOpcode::kDead, Operator::kNoProperties,
     298        3088 :                              "MockOperator", 0, 0, 0, 1, 0, 0);
     299        6176 : const Operator kMockOpEffect(IrOpcode::kDead, Operator::kNoProperties,
     300        3088 :                              "MockOpEffect", 0, 1, 0, 1, 1, 0);
     301        6176 : const Operator kMockOpControl(IrOpcode::kDead, Operator::kNoProperties,
     302        3088 :                               "MockOpControl", 0, 0, 1, 1, 0, 1);
     303             : 
     304             : }  // namespace
     305             : 
     306             : 
     307       15444 : TEST_F(AdvancedReducerTest, ReplaceWithValue_ValueUse) {
     308           1 :   CommonOperatorBuilder common(zone());
     309             :   Node* node = graph()->NewNode(&kMockOperator);
     310           1 :   Node* start = graph()->NewNode(common.Start(1));
     311           1 :   Node* zero = graph()->NewNode(common.Int32Constant(0));
     312           1 :   Node* use_value = graph()->NewNode(common.Return(), zero, node, start, start);
     313           1 :   Node* replacement = graph()->NewNode(&kMockOperator);
     314           2 :   GraphReducer graph_reducer(zone(), graph(), nullptr);
     315             :   ReplaceWithValueReducer r(&graph_reducer);
     316           1 :   r.ReplaceWithValue(node, replacement);
     317           2 :   EXPECT_EQ(replacement, use_value->InputAt(1));
     318           2 :   EXPECT_EQ(0, node->UseCount());
     319           2 :   EXPECT_EQ(1, replacement->UseCount());
     320           2 :   EXPECT_THAT(replacement->uses(), ElementsAre(use_value));
     321           1 : }
     322             : 
     323             : 
     324       15444 : TEST_F(AdvancedReducerTest, ReplaceWithValue_EffectUse) {
     325           1 :   CommonOperatorBuilder common(zone());
     326           2 :   Node* start = graph()->NewNode(common.Start(1));
     327             :   Node* node = graph()->NewNode(&kMockOpEffect, start);
     328           1 :   Node* use_control = graph()->NewNode(common.Merge(1), start);
     329           1 :   Node* use_effect = graph()->NewNode(common.EffectPhi(1), node, use_control);
     330             :   Node* replacement = graph()->NewNode(&kMockOperator);
     331           2 :   GraphReducer graph_reducer(zone(), graph(), nullptr);
     332             :   ReplaceWithValueReducer r(&graph_reducer);
     333             :   r.ReplaceWithValue(node, replacement);
     334           2 :   EXPECT_EQ(start, use_effect->InputAt(0));
     335           2 :   EXPECT_EQ(0, node->UseCount());
     336           2 :   EXPECT_EQ(3, start->UseCount());
     337           2 :   EXPECT_EQ(0, replacement->UseCount());
     338           2 :   EXPECT_THAT(start->uses(),
     339           0 :               UnorderedElementsAre(use_effect, use_control, node));
     340           1 : }
     341             : 
     342             : 
     343       15444 : TEST_F(AdvancedReducerTest, ReplaceWithValue_ControlUse1) {
     344           1 :   CommonOperatorBuilder common(zone());
     345           2 :   Node* start = graph()->NewNode(common.Start(1));
     346             :   Node* node = graph()->NewNode(&kMockOpControl, start);
     347           1 :   Node* success = graph()->NewNode(common.IfSuccess(), node);
     348           1 :   Node* use_control = graph()->NewNode(common.Merge(1), success);
     349             :   Node* replacement = graph()->NewNode(&kMockOperator);
     350           2 :   GraphReducer graph_reducer(zone(), graph(), nullptr);
     351             :   ReplaceWithValueReducer r(&graph_reducer);
     352             :   r.ReplaceWithValue(node, replacement);
     353           2 :   EXPECT_EQ(start, use_control->InputAt(0));
     354           2 :   EXPECT_EQ(0, node->UseCount());
     355           2 :   EXPECT_EQ(2, start->UseCount());
     356           2 :   EXPECT_EQ(0, replacement->UseCount());
     357           2 :   EXPECT_THAT(start->uses(), UnorderedElementsAre(use_control, node));
     358           1 : }
     359             : 
     360             : 
     361       15444 : TEST_F(AdvancedReducerTest, ReplaceWithValue_ControlUse2) {
     362           1 :   CommonOperatorBuilder common(zone());
     363           2 :   Node* start = graph()->NewNode(common.Start(1));
     364             :   Node* effect = graph()->NewNode(&kMockOperator);
     365           1 :   Node* dead = graph()->NewNode(&kMockOperator);
     366           1 :   Node* node = graph()->NewNode(&kMockOpControl, start);
     367           1 :   Node* success = graph()->NewNode(common.IfSuccess(), node);
     368           1 :   Node* exception = graph()->NewNode(common.IfException(), effect, node);
     369           1 :   Node* use_control = graph()->NewNode(common.Merge(1), success);
     370             :   Node* replacement = graph()->NewNode(&kMockOperator);
     371           2 :   GraphReducer graph_reducer(zone(), graph(), dead);
     372             :   ReplaceWithValueReducer r(&graph_reducer);
     373             :   r.ReplaceWithValue(node, replacement);
     374           2 :   EXPECT_EQ(start, use_control->InputAt(0));
     375           2 :   EXPECT_EQ(dead, exception->InputAt(1));
     376           2 :   EXPECT_EQ(0, node->UseCount());
     377           2 :   EXPECT_EQ(2, start->UseCount());
     378           2 :   EXPECT_EQ(1, dead->UseCount());
     379           2 :   EXPECT_EQ(0, replacement->UseCount());
     380           2 :   EXPECT_THAT(start->uses(), UnorderedElementsAre(use_control, node));
     381           2 :   EXPECT_THAT(dead->uses(), ElementsAre(exception));
     382           1 : }
     383             : 
     384             : 
     385       15444 : TEST_F(AdvancedReducerTest, ReplaceWithValue_ControlUse3) {
     386           1 :   CommonOperatorBuilder common(zone());
     387           2 :   Node* start = graph()->NewNode(common.Start(1));
     388             :   Node* effect = graph()->NewNode(&kMockOperator);
     389           1 :   Node* dead = graph()->NewNode(&kMockOperator);
     390           1 :   Node* node = graph()->NewNode(&kMockOpControl, start);
     391           1 :   Node* success = graph()->NewNode(common.IfSuccess(), node);
     392           1 :   Node* exception = graph()->NewNode(common.IfException(), effect, node);
     393           1 :   Node* use_control = graph()->NewNode(common.Merge(1), success);
     394             :   Node* replacement = graph()->NewNode(&kMockOperator);
     395           2 :   GraphReducer graph_reducer(zone(), graph(), dead);
     396             :   ReplaceWithValueReducer r(&graph_reducer);
     397             :   r.ReplaceWithValue(node, replacement);
     398           2 :   EXPECT_EQ(start, use_control->InputAt(0));
     399           2 :   EXPECT_EQ(dead, exception->InputAt(1));
     400           2 :   EXPECT_EQ(0, node->UseCount());
     401           2 :   EXPECT_EQ(2, start->UseCount());
     402           2 :   EXPECT_EQ(1, dead->UseCount());
     403           2 :   EXPECT_EQ(0, replacement->UseCount());
     404           2 :   EXPECT_THAT(start->uses(), UnorderedElementsAre(use_control, node));
     405           2 :   EXPECT_THAT(dead->uses(), ElementsAre(exception));
     406           1 : }
     407             : 
     408             : 
     409          34 : class GraphReducerTest : public TestWithZone {
     410             :  public:
     411          34 :   GraphReducerTest() : graph_(zone()) {}
     412             : 
     413          17 :   static void SetUpTestCase() {
     414             :     TestWithZone::SetUpTestCase();
     415          17 :     DefaultValue<Reduction>::Set(Reducer::NoChange());
     416          17 :   }
     417             : 
     418          17 :   static void TearDownTestCase() {
     419             :     DefaultValue<Reduction>::Clear();
     420             :     TestWithZone::TearDownTestCase();
     421          17 :   }
     422             : 
     423             :  protected:
     424           1 :   void ReduceNode(Node* node, Reducer* r) {
     425           2 :     GraphReducer reducer(zone(), graph());
     426           1 :     reducer.AddReducer(r);
     427           1 :     reducer.ReduceNode(node);
     428           1 :   }
     429             : 
     430           1 :   void ReduceNode(Node* node, Reducer* r1, Reducer* r2) {
     431           2 :     GraphReducer reducer(zone(), graph());
     432           1 :     reducer.AddReducer(r1);
     433           1 :     reducer.AddReducer(r2);
     434           1 :     reducer.ReduceNode(node);
     435           1 :   }
     436             : 
     437           1 :   void ReduceNode(Node* node, Reducer* r1, Reducer* r2, Reducer* r3) {
     438           2 :     GraphReducer reducer(zone(), graph());
     439           1 :     reducer.AddReducer(r1);
     440           1 :     reducer.AddReducer(r2);
     441           1 :     reducer.AddReducer(r3);
     442           1 :     reducer.ReduceNode(node);
     443           1 :   }
     444             : 
     445          49 :   void ReduceGraph(Reducer* r1) {
     446          98 :     GraphReducer reducer(zone(), graph());
     447          49 :     reducer.AddReducer(r1);
     448          49 :     reducer.ReduceGraph();
     449          49 :   }
     450             : 
     451           9 :   void ReduceGraph(Reducer* r1, Reducer* r2) {
     452          18 :     GraphReducer reducer(zone(), graph());
     453           9 :     reducer.AddReducer(r1);
     454           9 :     reducer.AddReducer(r2);
     455           9 :     reducer.ReduceGraph();
     456           9 :   }
     457             : 
     458          96 :   void ReduceGraph(Reducer* r1, Reducer* r2, Reducer* r3) {
     459         192 :     GraphReducer reducer(zone(), graph());
     460          96 :     reducer.AddReducer(r1);
     461          96 :     reducer.AddReducer(r2);
     462          96 :     reducer.AddReducer(r3);
     463          96 :     reducer.ReduceGraph();
     464          96 :   }
     465             : 
     466         282 :   Graph* graph() { return &graph_; }
     467             : 
     468             :  private:
     469             :   Graph graph_;
     470             : };
     471             : 
     472             : 
     473       15444 : TEST_F(GraphReducerTest, NodeIsDeadAfterReplace) {
     474           2 :   StrictMock<MockReducer> r;
     475             :   Node* node0 = graph()->NewNode(&kOpA0);
     476             :   Node* node1 = graph()->NewNode(&kOpA1, node0);
     477             :   Node* node2 = graph()->NewNode(&kOpA1, node0);
     478           5 :   EXPECT_CALL(r, Reduce(node0)).WillOnce(Return(Reducer::NoChange()));
     479           5 :   EXPECT_CALL(r, Reduce(node1)).WillOnce(Return(Reducer::Replace(node2)));
     480           1 :   ReduceNode(node1, &r);
     481           2 :   EXPECT_FALSE(node0->IsDead());
     482           1 :   EXPECT_TRUE(node1->IsDead());
     483           2 :   EXPECT_FALSE(node2->IsDead());
     484           1 : }
     485             : 
     486             : 
     487       15444 : TEST_F(GraphReducerTest, ReduceOnceForEveryReducer) {
     488           2 :   StrictMock<MockReducer> r1, r2;
     489             :   Node* node0 = graph()->NewNode(&kOpA0);
     490           3 :   EXPECT_CALL(r1, Reduce(node0));
     491           3 :   EXPECT_CALL(r2, Reduce(node0));
     492           1 :   ReduceNode(node0, &r1, &r2);
     493           1 : }
     494             : 
     495             : 
     496       15444 : TEST_F(GraphReducerTest, ReduceAgainAfterChanged) {
     497           1 :   Sequence s1, s2, s3;
     498           2 :   StrictMock<MockReducer> r1, r2, r3;
     499             :   Node* node0 = graph()->NewNode(&kOpA0);
     500           3 :   EXPECT_CALL(r1, Reduce(node0));
     501           3 :   EXPECT_CALL(r2, Reduce(node0));
     502           3 :   EXPECT_CALL(r3, Reduce(node0)).InSequence(s1, s2, s3).WillOnce(
     503           4 :       Return(Reducer::Changed(node0)));
     504           3 :   EXPECT_CALL(r1, Reduce(node0)).InSequence(s1);
     505           3 :   EXPECT_CALL(r2, Reduce(node0)).InSequence(s2);
     506           1 :   ReduceNode(node0, &r1, &r2, &r3);
     507           1 : }
     508             : 
     509             : 
     510       15444 : TEST_F(GraphReducerTest, ReduceGraphFromEnd1) {
     511           2 :   StrictMock<MockReducer> r1;
     512             :   Node* n = graph()->NewNode(&kOpA0);
     513             :   Node* end = graph()->NewNode(&kOpA1, n);
     514             :   graph()->SetEnd(end);
     515           1 :   Sequence s;
     516           3 :   EXPECT_CALL(r1, Reduce(n));
     517           3 :   EXPECT_CALL(r1, Reduce(end));
     518           1 :   ReduceGraph(&r1);
     519           1 : }
     520             : 
     521             : 
     522       15444 : TEST_F(GraphReducerTest, ReduceGraphFromEnd2) {
     523           2 :   StrictMock<MockReducer> r1;
     524             :   Node* n1 = graph()->NewNode(&kOpA0);
     525             :   Node* n2 = graph()->NewNode(&kOpA1, n1);
     526             :   Node* n3 = graph()->NewNode(&kOpA1, n1);
     527             :   Node* end = graph()->NewNode(&kOpA2, n2, n3);
     528             :   graph()->SetEnd(end);
     529           1 :   Sequence s1, s2;
     530           3 :   EXPECT_CALL(r1, Reduce(n1)).InSequence(s1, s2);
     531           3 :   EXPECT_CALL(r1, Reduce(n2)).InSequence(s1);
     532           3 :   EXPECT_CALL(r1, Reduce(n3)).InSequence(s2);
     533           3 :   EXPECT_CALL(r1, Reduce(end)).InSequence(s1, s2);
     534           1 :   ReduceGraph(&r1);
     535           1 : }
     536             : 
     537             : 
     538       15444 : TEST_F(GraphReducerTest, ReduceInPlace1) {
     539           1 :   Node* n1 = graph()->NewNode(&kOpA0);
     540             :   Node* end = graph()->NewNode(&kOpA1, n1);
     541             :   graph()->SetEnd(end);
     542             : 
     543             :   // Tests A* => B* with in-place updates.
     544           1 :   InPlaceABReducer r;
     545           7 :   for (int i = 0; i < 3; i++) {
     546           3 :     size_t before = graph()->NodeCount();
     547           3 :     ReduceGraph(&r);
     548           6 :     EXPECT_EQ(before, graph()->NodeCount());
     549           6 :     EXPECT_EQ(&kOpB0, n1->op());
     550           6 :     EXPECT_EQ(&kOpB1, end->op());
     551           6 :     EXPECT_EQ(n1, end->InputAt(0));
     552             :   }
     553           1 : }
     554             : 
     555             : 
     556       15444 : TEST_F(GraphReducerTest, ReduceInPlace2) {
     557           1 :   Node* n1 = graph()->NewNode(&kOpA0);
     558           1 :   Node* n2 = graph()->NewNode(&kOpA1, n1);
     559           2 :   Node* n3 = graph()->NewNode(&kOpA1, n1);
     560           1 :   Node* end = graph()->NewNode(&kOpA2, n2, n3);
     561             :   graph()->SetEnd(end);
     562             : 
     563             :   // Tests A* => B* with in-place updates.
     564           1 :   InPlaceABReducer r;
     565           7 :   for (int i = 0; i < 3; i++) {
     566           3 :     size_t before = graph()->NodeCount();
     567           3 :     ReduceGraph(&r);
     568           6 :     EXPECT_EQ(before, graph()->NodeCount());
     569           6 :     EXPECT_EQ(&kOpB0, n1->op());
     570           6 :     EXPECT_EQ(&kOpB1, n2->op());
     571           9 :     EXPECT_EQ(n1, n2->InputAt(0));
     572           6 :     EXPECT_EQ(&kOpB1, n3->op());
     573           9 :     EXPECT_EQ(n1, n3->InputAt(0));
     574           6 :     EXPECT_EQ(&kOpB2, end->op());
     575           6 :     EXPECT_EQ(n2, end->InputAt(0));
     576           6 :     EXPECT_EQ(n3, end->InputAt(1));
     577             :   }
     578           1 : }
     579             : 
     580             : 
     581       15444 : TEST_F(GraphReducerTest, ReduceNew1) {
     582             :   Node* n1 = graph()->NewNode(&kOpA0);
     583             :   Node* n2 = graph()->NewNode(&kOpA1, n1);
     584             :   Node* n3 = graph()->NewNode(&kOpA1, n1);
     585           1 :   Node* end = graph()->NewNode(&kOpA2, n2, n3);
     586             :   graph()->SetEnd(end);
     587             : 
     588             :   NewABReducer r(graph());
     589             :   // Tests A* => B* while creating new nodes.
     590           7 :   for (int i = 0; i < 3; i++) {
     591           3 :     size_t before = graph()->NodeCount();
     592           3 :     ReduceGraph(&r);
     593           3 :     if (i == 0) {
     594           1 :       EXPECT_NE(before, graph()->NodeCount());
     595             :     } else {
     596           4 :       EXPECT_EQ(before, graph()->NodeCount());
     597             :     }
     598           3 :     Node* nend = graph()->end();
     599           3 :     EXPECT_NE(end, nend);  // end() should be updated too.
     600             : 
     601           3 :     Node* nn2 = nend->InputAt(0);
     602             :     Node* nn3 = nend->InputAt(1);
     603           3 :     Node* nn1 = nn2->InputAt(0);
     604             : 
     605           6 :     EXPECT_EQ(nn1, nn3->InputAt(0));
     606             : 
     607           6 :     EXPECT_EQ(&kOpB0, nn1->op());
     608           6 :     EXPECT_EQ(&kOpB1, nn2->op());
     609           6 :     EXPECT_EQ(&kOpB1, nn3->op());
     610           6 :     EXPECT_EQ(&kOpB2, nend->op());
     611             :   }
     612           1 : }
     613             : 
     614             : 
     615       15444 : TEST_F(GraphReducerTest, Wrapping1) {
     616           1 :   Node* end = graph()->NewNode(&kOpA0);
     617             :   graph()->SetEnd(end);
     618           2 :   EXPECT_EQ(1U, graph()->NodeCount());
     619             : 
     620             :   A0Wrapper r(graph());
     621             : 
     622           1 :   ReduceGraph(&r);
     623           2 :   EXPECT_EQ(2U, graph()->NodeCount());
     624             : 
     625           1 :   Node* nend = graph()->end();
     626           1 :   EXPECT_NE(end, nend);
     627           2 :   EXPECT_EQ(&kOpB1, nend->op());
     628           3 :   EXPECT_EQ(1, nend->InputCount());
     629           3 :   EXPECT_EQ(end, nend->InputAt(0));
     630           1 : }
     631             : 
     632             : 
     633       15444 : TEST_F(GraphReducerTest, Wrapping2) {
     634           1 :   Node* end = graph()->NewNode(&kOpB0);
     635             :   graph()->SetEnd(end);
     636           2 :   EXPECT_EQ(1U, graph()->NodeCount());
     637             : 
     638             :   B0Wrapper r(graph());
     639             : 
     640           1 :   ReduceGraph(&r);
     641           2 :   EXPECT_EQ(3U, graph()->NodeCount());
     642             : 
     643           1 :   Node* nend = graph()->end();
     644           1 :   EXPECT_NE(end, nend);
     645           2 :   EXPECT_EQ(&kOpC1, nend->op());
     646           3 :   EXPECT_EQ(1, nend->InputCount());
     647             : 
     648           2 :   Node* n1 = nend->InputAt(0);
     649           1 :   EXPECT_NE(end, n1);
     650           2 :   EXPECT_EQ(&kOpC1, n1->op());
     651           3 :   EXPECT_EQ(1, n1->InputCount());
     652           3 :   EXPECT_EQ(end, n1->InputAt(0));
     653           1 : }
     654             : 
     655             : 
     656       15444 : TEST_F(GraphReducerTest, Forwarding1) {
     657           1 :   Node* n1 = graph()->NewNode(&kOpA0);
     658             :   Node* end = graph()->NewNode(&kOpA1, n1);
     659             :   graph()->SetEnd(end);
     660             : 
     661           1 :   A1Forwarder r;
     662             : 
     663             :   // Tests A1(x) => x
     664           7 :   for (int i = 0; i < 3; i++) {
     665           3 :     size_t before = graph()->NodeCount();
     666           3 :     ReduceGraph(&r);
     667           6 :     EXPECT_EQ(before, graph()->NodeCount());
     668           6 :     EXPECT_EQ(&kOpA0, n1->op());
     669           6 :     EXPECT_EQ(n1, graph()->end());
     670             :   }
     671           1 : }
     672             : 
     673             : 
     674       15444 : TEST_F(GraphReducerTest, Forwarding2) {
     675           1 :   Node* n1 = graph()->NewNode(&kOpA0);
     676             :   Node* n2 = graph()->NewNode(&kOpA1, n1);
     677           1 :   Node* n3 = graph()->NewNode(&kOpA1, n1);
     678             :   Node* end = graph()->NewNode(&kOpA2, n2, n3);
     679             :   graph()->SetEnd(end);
     680             : 
     681           1 :   A1Forwarder r;
     682             : 
     683             :   // Tests reducing A2(A1(x), A1(y)) => A2(x, y).
     684           7 :   for (int i = 0; i < 3; i++) {
     685           3 :     size_t before = graph()->NodeCount();
     686           3 :     ReduceGraph(&r);
     687           6 :     EXPECT_EQ(before, graph()->NodeCount());
     688           6 :     EXPECT_EQ(&kOpA0, n1->op());
     689           6 :     EXPECT_EQ(n1, end->InputAt(0));
     690           6 :     EXPECT_EQ(n1, end->InputAt(1));
     691           6 :     EXPECT_EQ(&kOpA2, end->op());
     692           6 :     EXPECT_EQ(0, n2->UseCount());
     693           6 :     EXPECT_EQ(0, n3->UseCount());
     694             :   }
     695           1 : }
     696             : 
     697             : 
     698       15444 : TEST_F(GraphReducerTest, Forwarding3) {
     699             :   // Tests reducing a chain of A1(A1(A1(A1(x)))) => x.
     700          17 :   for (int i = 0; i < 8; i++) {
     701           8 :     Node* n1 = graph()->NewNode(&kOpA0);
     702             :     Node* end = n1;
     703          64 :     for (int j = 0; j < i; j++) {
     704             :       end = graph()->NewNode(&kOpA1, end);
     705             :     }
     706             :     graph()->SetEnd(end);
     707             : 
     708           8 :     A1Forwarder r;
     709             : 
     710          56 :     for (size_t i = 0; i < 3; i++) {
     711          24 :       size_t before = graph()->NodeCount();
     712          24 :       ReduceGraph(&r);
     713          48 :       EXPECT_EQ(before, graph()->NodeCount());
     714          48 :       EXPECT_EQ(&kOpA0, n1->op());
     715          48 :       EXPECT_EQ(n1, graph()->end());
     716             :     }
     717             :   }
     718           1 : }
     719             : 
     720             : 
     721       15444 : TEST_F(GraphReducerTest, ReduceForward1) {
     722           1 :   Node* n1 = graph()->NewNode(&kOpA0);
     723             :   Node* n2 = graph()->NewNode(&kOpA1, n1);
     724           1 :   Node* n3 = graph()->NewNode(&kOpA1, n1);
     725             :   Node* end = graph()->NewNode(&kOpA2, n2, n3);
     726             :   graph()->SetEnd(end);
     727             : 
     728           1 :   InPlaceABReducer r;
     729           1 :   B1Forwarder f;
     730             : 
     731             :   // Tests first reducing A => B, then B1(x) => x.
     732           7 :   for (size_t i = 0; i < 3; i++) {
     733           3 :     size_t before = graph()->NodeCount();
     734           3 :     ReduceGraph(&r, &f);
     735           6 :     EXPECT_EQ(before, graph()->NodeCount());
     736           6 :     EXPECT_EQ(&kOpB0, n1->op());
     737           3 :     EXPECT_TRUE(n2->IsDead());
     738           6 :     EXPECT_EQ(n1, end->InputAt(0));
     739           3 :     EXPECT_TRUE(n3->IsDead());
     740           6 :     EXPECT_EQ(n1, end->InputAt(0));
     741           6 :     EXPECT_EQ(&kOpB2, end->op());
     742           6 :     EXPECT_EQ(0, n2->UseCount());
     743           6 :     EXPECT_EQ(0, n3->UseCount());
     744             :   }
     745           1 : }
     746             : 
     747             : 
     748       15444 : TEST_F(GraphReducerTest, Sorter1) {
     749           1 :   AB2Sorter r;
     750          13 :   for (int i = 0; i < 6; i++) {
     751             :     Node* n1 = graph()->NewNode(&kOpA0);
     752             :     Node* n2 = graph()->NewNode(&kOpA1, n1);
     753             :     Node* n3 = graph()->NewNode(&kOpA1, n1);
     754           6 :     Node* end = nullptr;  // Initialize to please the compiler.
     755             : 
     756           7 :     if (i == 0) end = graph()->NewNode(&kOpA2, n2, n3);
     757           7 :     if (i == 1) end = graph()->NewNode(&kOpA2, n3, n2);
     758           7 :     if (i == 2) end = graph()->NewNode(&kOpA2, n2, n1);
     759           7 :     if (i == 3) end = graph()->NewNode(&kOpA2, n1, n2);
     760           7 :     if (i == 4) end = graph()->NewNode(&kOpA2, n3, n1);
     761           7 :     if (i == 5) end = graph()->NewNode(&kOpA2, n1, n3);
     762             : 
     763           6 :     graph()->SetEnd(end);
     764             : 
     765           6 :     size_t before = graph()->NodeCount();
     766           6 :     ReduceGraph(&r);
     767          12 :     EXPECT_EQ(before, graph()->NodeCount());
     768          12 :     EXPECT_EQ(&kOpA0, n1->op());
     769          12 :     EXPECT_EQ(&kOpA1, n2->op());
     770          12 :     EXPECT_EQ(&kOpA1, n3->op());
     771          12 :     EXPECT_EQ(&kOpA2, end->op());
     772          12 :     EXPECT_EQ(end, graph()->end());
     773          18 :     EXPECT_LE(end->InputAt(0)->id(), end->InputAt(1)->id());
     774             :   }
     775           1 : }
     776             : 
     777             : 
     778             : namespace {
     779             : 
     780             : // Generate a node graph with the given permutations.
     781          96 : void GenDAG(Graph* graph, int* p3, int* p2, int* p1) {
     782             :   Node* level4 = graph->NewNode(&kOpA0);
     783             :   Node* level3[] = {graph->NewNode(&kOpA1, level4),
     784         192 :                     graph->NewNode(&kOpA1, level4)};
     785             : 
     786          96 :   Node* level2[] = {graph->NewNode(&kOpA1, level3[p3[0]]),
     787          96 :                     graph->NewNode(&kOpA1, level3[p3[1]]),
     788          96 :                     graph->NewNode(&kOpA1, level3[p3[0]]),
     789         384 :                     graph->NewNode(&kOpA1, level3[p3[1]])};
     790             : 
     791          96 :   Node* level1[] = {graph->NewNode(&kOpA2, level2[p2[0]], level2[p2[1]]),
     792         192 :                     graph->NewNode(&kOpA2, level2[p2[2]], level2[p2[3]])};
     793             : 
     794          96 :   Node* end = graph->NewNode(&kOpA2, level1[p1[0]], level1[p1[1]]);
     795             :   graph->SetEnd(end);
     796          96 : }
     797             : 
     798             : }  // namespace
     799             : 
     800             : 
     801       15444 : TEST_F(GraphReducerTest, SortForwardReduce) {
     802             :   // Tests combined reductions on a series of DAGs.
     803           5 :   for (int j = 0; j < 2; j++) {
     804           2 :     int p3[] = {j, 1 - j};
     805          10 :     for (int m = 0; m < 2; m++) {
     806           4 :       int p1[] = {m, 1 - m};
     807         196 :       for (int k = 0; k < 24; k++) {  // All permutations of 0, 1, 2, 3
     808          96 :         int p2[] = {-1, -1, -1, -1};
     809             :         int n = k;
     810         864 :         for (int d = 4; d >= 1; d--) {  // Construct permutation.
     811         384 :           int p = n % d;
     812        3456 :           for (int z = 0; z < 4; z++) {
     813        1536 :             if (p2[z] == -1) {
     814         960 :               if (p == 0) p2[z] = d - 1;
     815         960 :               p--;
     816             :             }
     817             :           }
     818         384 :           n = n / d;
     819             :         }
     820             : 
     821          96 :         GenDAG(graph(), p3, p2, p1);
     822             : 
     823          96 :         AB2Sorter r1;
     824          96 :         A1Forwarder r2;
     825          96 :         InPlaceABReducer r3;
     826             : 
     827          96 :         ReduceGraph(&r1, &r2, &r3);
     828             : 
     829             :         Node* end = graph()->end();
     830         192 :         EXPECT_EQ(&kOpB2, end->op());
     831          96 :         Node* n1 = end->InputAt(0);
     832          96 :         Node* n2 = end->InputAt(1);
     833          96 :         EXPECT_NE(n1, n2);
     834         288 :         EXPECT_LT(n1->id(), n2->id());
     835         192 :         EXPECT_EQ(&kOpB2, n1->op());
     836         192 :         EXPECT_EQ(&kOpB2, n2->op());
     837         192 :         Node* n4 = n1->InputAt(0);
     838         192 :         EXPECT_EQ(&kOpB0, n4->op());
     839         288 :         EXPECT_EQ(n4, n1->InputAt(1));
     840         288 :         EXPECT_EQ(n4, n2->InputAt(0));
     841         288 :         EXPECT_EQ(n4, n2->InputAt(1));
     842             :       }
     843             :     }
     844             :   }
     845           1 : }
     846             : 
     847             : 
     848       15444 : TEST_F(GraphReducerTest, Order) {
     849             :   // Test that the order of reducers doesn't matter, as they should be
     850             :   // rerun for changed nodes.
     851           5 :   for (int i = 0; i < 2; i++) {
     852           2 :     Node* n1 = graph()->NewNode(&kOpA0);
     853             :     Node* end = graph()->NewNode(&kOpA1, n1);
     854             :     graph()->SetEnd(end);
     855             : 
     856           2 :     InPlaceABReducer abr;
     857           2 :     InPlaceBCReducer bcr;
     858             : 
     859             :     // Tests A* => C* with in-place updates.
     860          14 :     for (size_t j = 0; j < 3; j++) {
     861           6 :       size_t before = graph()->NodeCount();
     862           6 :       if (i == 0) {
     863           3 :         ReduceGraph(&abr, &bcr);
     864             :       } else {
     865           3 :         ReduceGraph(&bcr, &abr);
     866             :       }
     867             : 
     868          12 :       EXPECT_EQ(before, graph()->NodeCount());
     869          12 :       EXPECT_EQ(&kOpC0, n1->op());
     870          12 :       EXPECT_EQ(&kOpC1, end->op());
     871          12 :       EXPECT_EQ(n1, end->InputAt(0));
     872             :     }
     873             :   }
     874           1 : }
     875             : 
     876             : }  // namespace graph_reducer_unittest
     877             : }  // namespace compiler
     878             : }  // namespace internal
     879        9264 : }  // namespace v8

Generated by: LCOV version 1.10