LCOV - code coverage report
Current view: top level - test/unittests/compiler - dead-code-elimination-unittest.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 181 183 98.9 %
Date: 2019-02-19 Functions: 40 60 66.7 %

          Line data    Source code
       1             : // Copyright 2015 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/dead-code-elimination.h"
       7             : #include "test/unittests/compiler/graph-reducer-unittest.h"
       8             : #include "test/unittests/compiler/graph-unittest.h"
       9             : #include "test/unittests/compiler/node-test-utils.h"
      10             : #include "testing/gmock-support.h"
      11             : 
      12             : using testing::StrictMock;
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : namespace compiler {
      17             : namespace dead_code_elimination_unittest {
      18             : 
      19             : class DeadCodeEliminationTest : public GraphTest {
      20             :  public:
      21             :   explicit DeadCodeEliminationTest(int num_parameters = 4)
      22          18 :       : GraphTest(num_parameters) {}
      23          18 :   ~DeadCodeEliminationTest() override = default;
      24             : 
      25             :  protected:
      26         218 :   Reduction Reduce(AdvancedReducer::Editor* editor, Node* node) {
      27         218 :     DeadCodeElimination reducer(editor, graph(), common(), zone());
      28         218 :     return reducer.Reduce(node);
      29             :   }
      30             : 
      31         214 :   Reduction Reduce(Node* node) {
      32         214 :     StrictMock<MockAdvancedReducerEditor> editor;
      33         428 :     return Reduce(&editor, node);
      34             :   }
      35             : };
      36             : 
      37             : 
      38             : namespace {
      39             : 
      40             : const MachineRepresentation kMachineRepresentations[] = {
      41             :     MachineRepresentation::kBit,     MachineRepresentation::kWord8,
      42             :     MachineRepresentation::kWord16,  MachineRepresentation::kWord32,
      43             :     MachineRepresentation::kWord64,  MachineRepresentation::kFloat32,
      44             :     MachineRepresentation::kFloat64, MachineRepresentation::kTagged};
      45             : 
      46             : 
      47             : const int kMaxInputs = 16;
      48             : 
      49             : 
      50        3037 : const Operator kOp0(0, Operator::kNoProperties, "Op0", 1, 1, 1, 1, 1, 1);
      51             : 
      52             : }  // namespace
      53             : 
      54             : 
      55             : // -----------------------------------------------------------------------------
      56             : // General dead propagation
      57             : 
      58             : 
      59       15189 : TEST_F(DeadCodeEliminationTest, GeneralDeadPropagation) {
      60           1 :   Node* const value = Parameter(0);
      61           1 :   Node* const effect = graph()->start();
      62           1 :   Node* const dead = graph()->NewNode(common()->Dead());
      63             :   Node* const node = graph()->NewNode(&kOp0, value, effect, dead);
      64           1 :   Reduction const r = Reduce(node);
      65           2 :   ASSERT_TRUE(r.Changed());
      66           4 :   EXPECT_THAT(r.replacement(), IsDead());
      67             : }
      68             : 
      69             : 
      70             : // -----------------------------------------------------------------------------
      71             : // Branch
      72             : 
      73             : 
      74       15189 : TEST_F(DeadCodeEliminationTest, BranchWithDeadControlInput) {
      75             :   BranchHint const kHints[] = {BranchHint::kNone, BranchHint::kTrue,
      76           1 :                                BranchHint::kFalse};
      77          19 :   TRACED_FOREACH(BranchHint, hint, kHints) {
      78             :     Reduction const r =
      79             :         Reduce(graph()->NewNode(common()->Branch(hint), Parameter(0),
      80           9 :                                 graph()->NewNode(common()->Dead())));
      81           4 :     ASSERT_TRUE(r.Changed());
      82          12 :     EXPECT_THAT(r.replacement(), IsDead());
      83           3 :   }
      84             : }
      85             : 
      86             : 
      87             : // -----------------------------------------------------------------------------
      88             : // IfTrue
      89             : 
      90             : 
      91       15189 : TEST_F(DeadCodeEliminationTest, IfTrueWithDeadInput) {
      92             :   Reduction const r = Reduce(
      93           3 :       graph()->NewNode(common()->IfTrue(), graph()->NewNode(common()->Dead())));
      94           2 :   ASSERT_TRUE(r.Changed());
      95           4 :   EXPECT_THAT(r.replacement(), IsDead());
      96             : }
      97             : 
      98             : 
      99             : // -----------------------------------------------------------------------------
     100             : // IfFalse
     101             : 
     102             : 
     103       15189 : TEST_F(DeadCodeEliminationTest, IfFalseWithDeadInput) {
     104             :   Reduction const r = Reduce(graph()->NewNode(
     105           3 :       common()->IfFalse(), graph()->NewNode(common()->Dead())));
     106           2 :   ASSERT_TRUE(r.Changed());
     107           4 :   EXPECT_THAT(r.replacement(), IsDead());
     108             : }
     109             : 
     110             : 
     111             : // -----------------------------------------------------------------------------
     112             : // IfSuccess
     113             : 
     114             : 
     115       15189 : TEST_F(DeadCodeEliminationTest, IfSuccessWithDeadInput) {
     116             :   Reduction const r = Reduce(graph()->NewNode(
     117           3 :       common()->IfSuccess(), graph()->NewNode(common()->Dead())));
     118           2 :   ASSERT_TRUE(r.Changed());
     119           4 :   EXPECT_THAT(r.replacement(), IsDead());
     120             : }
     121             : 
     122             : 
     123             : // -----------------------------------------------------------------------------
     124             : // IfException
     125             : 
     126             : 
     127       15189 : TEST_F(DeadCodeEliminationTest, IfExceptionWithDeadControlInput) {
     128             :   Reduction const r =
     129             :       Reduce(graph()->NewNode(common()->IfException(), graph()->start(),
     130           3 :                               graph()->NewNode(common()->Dead())));
     131           2 :   ASSERT_TRUE(r.Changed());
     132           4 :   EXPECT_THAT(r.replacement(), IsDead());
     133             : }
     134             : 
     135             : 
     136             : // -----------------------------------------------------------------------------
     137             : // End
     138             : 
     139             : 
     140       15189 : TEST_F(DeadCodeEliminationTest, EndWithDeadAndStart) {
     141           1 :   Node* const dead = graph()->NewNode(common()->Dead());
     142           1 :   Node* const start = graph()->start();
     143           2 :   Reduction const r = Reduce(graph()->NewNode(common()->End(2), dead, start));
     144           2 :   ASSERT_TRUE(r.Changed());
     145           5 :   EXPECT_THAT(r.replacement(), IsEnd(start));
     146             : }
     147             : 
     148             : 
     149       15189 : TEST_F(DeadCodeEliminationTest, EndWithOnlyDeadInputs) {
     150             :   Node* inputs[kMaxInputs];
     151          91 :   TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
     152         120 :     for (int i = 0; i < input_count; ++i) {
     153         240 :       inputs[i] = graph()->NewNode(common()->Dead());
     154             :     }
     155             :     Reduction const r = Reduce(
     156          15 :         graph()->NewNode(common()->End(input_count), input_count, inputs));
     157          16 :     ASSERT_TRUE(r.Changed());
     158          60 :     EXPECT_THAT(r.replacement(), IsDead());
     159          15 :   }
     160             : }
     161             : 
     162             : 
     163             : // -----------------------------------------------------------------------------
     164             : // Merge
     165             : 
     166             : 
     167       15189 : TEST_F(DeadCodeEliminationTest, MergeWithOnlyDeadInputs) {
     168             :   Node* inputs[kMaxInputs + 1];
     169          91 :   TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
     170         120 :     for (int i = 0; i < input_count; ++i) {
     171         240 :       inputs[i] = graph()->NewNode(common()->Dead());
     172             :     }
     173             :     Reduction const r = Reduce(
     174          15 :         graph()->NewNode(common()->Merge(input_count), input_count, inputs));
     175          16 :     ASSERT_TRUE(r.Changed());
     176          60 :     EXPECT_THAT(r.replacement(), IsDead());
     177          15 :   }
     178             : }
     179             : 
     180             : 
     181       15189 : TEST_F(DeadCodeEliminationTest, MergeWithOneLiveAndOneDeadInput) {
     182           1 :   Node* const v0 = Parameter(0);
     183           1 :   Node* const v1 = Parameter(1);
     184             :   Node* const c0 =
     185           2 :       graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
     186           1 :   Node* const c1 = graph()->NewNode(common()->Dead());
     187           1 :   Node* const e0 = graph()->NewNode(&kOp0, v0, graph()->start(), c0);
     188           1 :   Node* const e1 = graph()->NewNode(&kOp0, v1, graph()->start(), c1);
     189           1 :   Node* const merge = graph()->NewNode(common()->Merge(2), c0, c1);
     190             :   Node* const phi = graph()->NewNode(
     191           1 :       common()->Phi(MachineRepresentation::kTagged, 2), v0, v1, merge);
     192           1 :   Node* const ephi = graph()->NewNode(common()->EffectPhi(2), e0, e1, merge);
     193           1 :   StrictMock<MockAdvancedReducerEditor> editor;
     194           4 :   EXPECT_CALL(editor, Replace(phi, v0));
     195           4 :   EXPECT_CALL(editor, Replace(ephi, e0));
     196           1 :   Reduction const r = Reduce(&editor, merge);
     197           2 :   ASSERT_TRUE(r.Changed());
     198           2 :   EXPECT_EQ(c0, r.replacement());
     199             : }
     200             : 
     201             : 
     202       15189 : TEST_F(DeadCodeEliminationTest, MergeWithTwoLiveAndTwoDeadInputs) {
     203           1 :   Node* const v0 = Parameter(0);
     204           1 :   Node* const v1 = Parameter(1);
     205           1 :   Node* const v2 = Parameter(2);
     206           1 :   Node* const v3 = Parameter(3);
     207             :   Node* const c0 =
     208           1 :       graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
     209           1 :   Node* const c1 = graph()->NewNode(common()->Dead());
     210           1 :   Node* const c2 = graph()->NewNode(common()->Dead());
     211           1 :   Node* const c3 = graph()->NewNode(&kOp0, v3, graph()->start(), c0);
     212           1 :   Node* const e0 = graph()->start();
     213             :   Node* const e1 = graph()->NewNode(&kOp0, v1, e0, c0);
     214             :   Node* const e2 = graph()->NewNode(&kOp0, v2, e1, c0);
     215           1 :   Node* const e3 = graph()->NewNode(&kOp0, v3, graph()->start(), c3);
     216           1 :   Node* const merge = graph()->NewNode(common()->Merge(4), c0, c1, c2, c3);
     217             :   Node* const phi = graph()->NewNode(
     218           2 :       common()->Phi(MachineRepresentation::kTagged, 4), v0, v1, v2, v3, merge);
     219             :   Node* const ephi =
     220           2 :       graph()->NewNode(common()->EffectPhi(4), e0, e1, e2, e3, merge);
     221           1 :   StrictMock<MockAdvancedReducerEditor> editor;
     222           3 :   EXPECT_CALL(editor, Revisit(phi));
     223           3 :   EXPECT_CALL(editor, Revisit(ephi));
     224           1 :   Reduction const r = Reduce(&editor, merge);
     225           2 :   ASSERT_TRUE(r.Changed());
     226           6 :   EXPECT_THAT(r.replacement(), IsMerge(c0, c3));
     227           8 :   EXPECT_THAT(phi,
     228           0 :               IsPhi(MachineRepresentation::kTagged, v0, v3, r.replacement()));
     229           7 :   EXPECT_THAT(ephi, IsEffectPhi(e0, e3, r.replacement()));
     230             : }
     231             : 
     232             : 
     233             : // -----------------------------------------------------------------------------
     234             : // Loop
     235             : 
     236             : 
     237       15189 : TEST_F(DeadCodeEliminationTest, LoopWithDeadFirstInput) {
     238             :   Node* inputs[kMaxInputs + 1];
     239          91 :   TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
     240          30 :     inputs[0] = graph()->NewNode(common()->Dead());
     241         120 :     for (int i = 1; i < input_count; ++i) {
     242         105 :       inputs[i] = graph()->start();
     243             :     }
     244             :     Reduction const r = Reduce(
     245          15 :         graph()->NewNode(common()->Loop(input_count), input_count, inputs));
     246          16 :     ASSERT_TRUE(r.Changed());
     247          60 :     EXPECT_THAT(r.replacement(), IsDead());
     248          15 :   }
     249             : }
     250             : 
     251             : 
     252       15189 : TEST_F(DeadCodeEliminationTest, LoopWithOnlyDeadInputs) {
     253             :   Node* inputs[kMaxInputs + 1];
     254          91 :   TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
     255         120 :     for (int i = 0; i < input_count; ++i) {
     256         240 :       inputs[i] = graph()->NewNode(common()->Dead());
     257             :     }
     258             :     Reduction const r = Reduce(
     259          15 :         graph()->NewNode(common()->Loop(input_count), input_count, inputs));
     260          16 :     ASSERT_TRUE(r.Changed());
     261          60 :     EXPECT_THAT(r.replacement(), IsDead());
     262          15 :   }
     263             : }
     264             : 
     265             : 
     266       15189 : TEST_F(DeadCodeEliminationTest, LoopWithOneLiveAndOneDeadInput) {
     267           1 :   Node* const v0 = Parameter(0);
     268           1 :   Node* const v1 = Parameter(1);
     269             :   Node* const c0 =
     270           2 :       graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
     271           1 :   Node* const c1 = graph()->NewNode(common()->Dead());
     272           1 :   Node* const e0 = graph()->NewNode(&kOp0, v0, graph()->start(), c0);
     273           1 :   Node* const e1 = graph()->NewNode(&kOp0, v1, graph()->start(), c1);
     274           1 :   Node* const loop = graph()->NewNode(common()->Loop(2), c0, c1);
     275             :   Node* const phi = graph()->NewNode(
     276           1 :       common()->Phi(MachineRepresentation::kTagged, 2), v0, v1, loop);
     277           1 :   Node* const ephi = graph()->NewNode(common()->EffectPhi(2), e0, e1, loop);
     278           1 :   Node* const terminate = graph()->NewNode(common()->Terminate(), ephi, loop);
     279           1 :   StrictMock<MockAdvancedReducerEditor> editor;
     280           4 :   EXPECT_CALL(editor, Replace(phi, v0));
     281           4 :   EXPECT_CALL(editor, Replace(ephi, e0));
     282           4 :   EXPECT_CALL(editor, Replace(terminate, IsDead()));
     283           1 :   Reduction const r = Reduce(&editor, loop);
     284           2 :   ASSERT_TRUE(r.Changed());
     285           2 :   EXPECT_EQ(c0, r.replacement());
     286             : }
     287             : 
     288             : 
     289       15189 : TEST_F(DeadCodeEliminationTest, LoopWithTwoLiveAndTwoDeadInputs) {
     290           1 :   Node* const v0 = Parameter(0);
     291           1 :   Node* const v1 = Parameter(1);
     292           1 :   Node* const v2 = Parameter(2);
     293           1 :   Node* const v3 = Parameter(3);
     294             :   Node* const c0 =
     295           1 :       graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
     296           1 :   Node* const c1 = graph()->NewNode(common()->Dead());
     297           1 :   Node* const c2 = graph()->NewNode(common()->Dead());
     298           1 :   Node* const c3 = graph()->NewNode(&kOp0, v3, graph()->start(), c0);
     299           1 :   Node* const e0 = graph()->start();
     300             :   Node* const e1 = graph()->NewNode(&kOp0, v1, e0, c0);
     301             :   Node* const e2 = graph()->NewNode(&kOp0, v2, e1, c0);
     302           1 :   Node* const e3 = graph()->NewNode(&kOp0, v3, graph()->start(), c3);
     303           1 :   Node* const loop = graph()->NewNode(common()->Loop(4), c0, c1, c2, c3);
     304             :   Node* const phi = graph()->NewNode(
     305           2 :       common()->Phi(MachineRepresentation::kTagged, 4), v0, v1, v2, v3, loop);
     306             :   Node* const ephi =
     307           2 :       graph()->NewNode(common()->EffectPhi(4), e0, e1, e2, e3, loop);
     308           1 :   StrictMock<MockAdvancedReducerEditor> editor;
     309           3 :   EXPECT_CALL(editor, Revisit(phi));
     310           3 :   EXPECT_CALL(editor, Revisit(ephi));
     311           1 :   Reduction const r = Reduce(&editor, loop);
     312           1 :   ASSERT_TRUE(r.Changed());
     313           6 :   EXPECT_THAT(r.replacement(), IsLoop(c0, c3));
     314           8 :   EXPECT_THAT(phi,
     315           0 :               IsPhi(MachineRepresentation::kTagged, v0, v3, r.replacement()));
     316           7 :   EXPECT_THAT(ephi, IsEffectPhi(e0, e3, r.replacement()));
     317             : }
     318             : 
     319             : 
     320             : // -----------------------------------------------------------------------------
     321             : // Phi
     322             : 
     323             : 
     324       15189 : TEST_F(DeadCodeEliminationTest, PhiWithDeadControlInput) {
     325             :   Node* inputs[kMaxInputs + 1];
     326          49 :   TRACED_FOREACH(MachineRepresentation, rep, kMachineRepresentations) {
     327         896 :     TRACED_FORRANGE(int, input_count, 1, kMaxInputs) {
     328        1088 :       for (int i = 0; i < input_count; ++i) {
     329        1088 :         inputs[i] = Parameter(i);
     330             :       }
     331         256 :       inputs[input_count] = graph()->NewNode(common()->Dead());
     332             :       Reduction const r = Reduce(graph()->NewNode(
     333         128 :           common()->Phi(rep, input_count), input_count + 1, inputs));
     334         129 :       ASSERT_TRUE(r.Changed());
     335         512 :       EXPECT_THAT(r.replacement(), IsDead());
     336         128 :     }
     337           8 :   }
     338             : }
     339             : 
     340             : 
     341             : // -----------------------------------------------------------------------------
     342             : // EffectPhi
     343             : 
     344             : 
     345       15189 : TEST_F(DeadCodeEliminationTest, EffectPhiWithDeadControlInput) {
     346             :   Node* inputs[kMaxInputs + 1];
     347          97 :   TRACED_FORRANGE(int, input_count, 1, kMaxInputs) {
     348         136 :     for (int i = 0; i < input_count; ++i) {
     349         136 :       inputs[i] = graph()->start();
     350             :     }
     351          32 :     inputs[input_count] = graph()->NewNode(common()->Dead());
     352             :     Reduction const r = Reduce(graph()->NewNode(
     353          16 :         common()->EffectPhi(input_count), input_count + 1, inputs));
     354          17 :     ASSERT_TRUE(r.Changed());
     355          64 :     EXPECT_THAT(r.replacement(), IsDead());
     356          16 :   }
     357             : }
     358             : 
     359             : 
     360             : // -----------------------------------------------------------------------------
     361             : // Terminate
     362             : 
     363             : 
     364       15189 : TEST_F(DeadCodeEliminationTest, TerminateWithDeadControlInput) {
     365             :   Reduction const r =
     366             :       Reduce(graph()->NewNode(common()->Terminate(), graph()->start(),
     367           3 :                               graph()->NewNode(common()->Dead())));
     368           2 :   ASSERT_TRUE(r.Changed());
     369           4 :   EXPECT_THAT(r.replacement(), IsDead());
     370             : }
     371             : 
     372             : }  // namespace dead_code_elimination_unittest
     373             : }  // namespace compiler
     374             : }  // namespace internal
     375        9111 : }  // namespace v8

Generated by: LCOV version 1.10