LCOV - code coverage report
Current view: top level - test/unittests/compiler - branch-elimination-unittest.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 99 101 98.0 %
Date: 2019-04-18 Functions: 12 16 75.0 %

          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/branch-elimination.h"
       6             : #include "src/compiler/js-graph.h"
       7             : #include "src/compiler/linkage.h"
       8             : #include "src/compiler/node-properties.h"
       9             : #include "test/unittests/compiler/compiler-test-utils.h"
      10             : #include "test/unittests/compiler/graph-unittest.h"
      11             : #include "test/unittests/compiler/node-test-utils.h"
      12             : #include "testing/gmock-support.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : namespace compiler {
      17             : 
      18           4 : class BranchEliminationTest : public GraphTest {
      19             :  public:
      20           4 :   BranchEliminationTest()
      21             :       : machine_(zone(), MachineType::PointerRepresentation(),
      22           8 :                  MachineOperatorBuilder::kNoFlags) {}
      23             : 
      24           5 :   MachineOperatorBuilder* machine() { return &machine_; }
      25             : 
      26           4 :   void Reduce() {
      27           4 :     JSOperatorBuilder javascript(zone());
      28             :     JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
      29           4 :                     machine());
      30           8 :     GraphReducer graph_reducer(zone(), graph(), jsgraph.Dead());
      31             :     BranchElimination branch_condition_elimination(&graph_reducer, &jsgraph,
      32           8 :                                                    zone());
      33           4 :     graph_reducer.AddReducer(&branch_condition_elimination);
      34           4 :     graph_reducer.ReduceGraph();
      35           4 :   }
      36             : 
      37             :  private:
      38             :   MachineOperatorBuilder machine_;
      39             : };
      40             : 
      41             : 
      42       15419 : TEST_F(BranchEliminationTest, NestedBranchSameTrue) {
      43             :   // { return (x ? (x ? 1 : 2) : 3; }
      44             :   // should be reduced to
      45             :   // { return (x ? 1 : 3; }
      46           1 :   Node* condition = Parameter(0);
      47             :   Node* outer_branch =
      48           2 :       graph()->NewNode(common()->Branch(), condition, graph()->start());
      49             : 
      50           1 :   Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch);
      51             :   Node* inner_branch =
      52           1 :       graph()->NewNode(common()->Branch(), condition, outer_if_true);
      53           1 :   Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch);
      54           1 :   Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch);
      55             :   Node* inner_merge =
      56           1 :       graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false);
      57             :   Node* inner_phi =
      58           1 :       graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2),
      59           1 :                        Int32Constant(1), Int32Constant(2), inner_merge);
      60             : 
      61           1 :   Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch);
      62             :   Node* outer_merge =
      63           1 :       graph()->NewNode(common()->Merge(2), inner_merge, outer_if_false);
      64             :   Node* outer_phi =
      65           1 :       graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2),
      66             :                        inner_phi, Int32Constant(3), outer_merge);
      67             : 
      68           1 :   Node* zero = graph()->NewNode(common()->Int32Constant(0));
      69           1 :   Node* ret = graph()->NewNode(common()->Return(), zero, outer_phi,
      70             :                                graph()->start(), outer_merge);
      71           1 :   graph()->SetEnd(graph()->NewNode(common()->End(1), ret));
      72             : 
      73           1 :   Reduce();
      74             : 
      75             :   // Outer branch should not be rewritten, the inner branch should be discarded.
      76           6 :   EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start()));
      77          12 :   EXPECT_THAT(inner_phi,
      78             :               IsPhi(MachineRepresentation::kWord32, IsInt32Constant(1),
      79           0 :                     IsInt32Constant(2), IsMerge(outer_if_true, IsDead())));
      80           1 : }
      81             : 
      82             : 
      83       15419 : TEST_F(BranchEliminationTest, NestedBranchSameFalse) {
      84             :   // { return (x ? 1 : (x ? 2 : 3); }
      85             :   // should be reduced to
      86             :   // { return (x ? 1 : 3; }
      87           1 :   Node* condition = Parameter(0);
      88             :   Node* outer_branch =
      89           2 :       graph()->NewNode(common()->Branch(), condition, graph()->start());
      90             : 
      91           1 :   Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch);
      92             : 
      93           1 :   Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch);
      94             :   Node* inner_branch =
      95           1 :       graph()->NewNode(common()->Branch(), condition, outer_if_false);
      96           1 :   Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch);
      97           1 :   Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch);
      98             :   Node* inner_merge =
      99           1 :       graph()->NewNode(common()->Merge(2), inner_if_true, inner_if_false);
     100             :   Node* inner_phi =
     101           1 :       graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2),
     102           1 :                        Int32Constant(2), Int32Constant(3), inner_merge);
     103             : 
     104             :   Node* outer_merge =
     105           1 :       graph()->NewNode(common()->Merge(2), outer_if_true, inner_merge);
     106             :   Node* outer_phi =
     107           1 :       graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2),
     108             :                        Int32Constant(1), inner_phi, outer_merge);
     109             : 
     110           1 :   Node* zero = graph()->NewNode(common()->Int32Constant(0));
     111           1 :   Node* ret = graph()->NewNode(common()->Return(), zero, outer_phi,
     112             :                                graph()->start(), outer_merge);
     113           1 :   graph()->SetEnd(graph()->NewNode(common()->End(1), ret));
     114             : 
     115           1 :   Reduce();
     116             : 
     117             :   // Outer branch should not be rewritten, the inner branch should be discarded.
     118           6 :   EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start()));
     119          12 :   EXPECT_THAT(inner_phi,
     120             :               IsPhi(MachineRepresentation::kWord32, IsInt32Constant(2),
     121           0 :                     IsInt32Constant(3), IsMerge(IsDead(), outer_if_false)));
     122           1 : }
     123             : 
     124             : 
     125       15419 : TEST_F(BranchEliminationTest, BranchAfterDiamond) {
     126             :   // { var y = x ? 1 : 2; return y + x ? 3 : 4; }
     127             :   // should not be reduced.
     128           1 :   Node* condition = Parameter(0);
     129             : 
     130             :   Node* branch1 =
     131           2 :       graph()->NewNode(common()->Branch(), condition, graph()->start());
     132           1 :   Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
     133           1 :   Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
     134           1 :   Node* merge1 = graph()->NewNode(common()->Merge(2), if_true1, if_false1);
     135             :   Node* phi1 =
     136           1 :       graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2),
     137             :                        Int32Constant(1), Int32Constant(2), merge1);
     138             : 
     139           2 :   Node* branch2 = graph()->NewNode(common()->Branch(), condition, merge1);
     140           1 :   Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
     141           1 :   Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
     142           1 :   Node* merge2 = graph()->NewNode(common()->Merge(2), if_true2, if_false2);
     143             :   Node* phi2 =
     144           1 :       graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 2),
     145             :                        Int32Constant(3), Int32Constant(4), merge1);
     146             : 
     147             : 
     148           1 :   Node* add = graph()->NewNode(machine()->Int32Add(), phi1, phi2);
     149           1 :   Node* zero = graph()->NewNode(common()->Int32Constant(0));
     150             :   Node* ret =
     151           1 :       graph()->NewNode(common()->Return(), zero, add, graph()->start(), merge2);
     152           1 :   graph()->SetEnd(graph()->NewNode(common()->End(1), ret));
     153             : 
     154           1 :   Reduce();
     155             : 
     156             :   // Outer branch should not be rewritten, the inner branch condition should
     157             :   // be true.
     158           6 :   EXPECT_THAT(branch1, IsBranch(condition, graph()->start()));
     159           6 :   EXPECT_THAT(branch2, IsBranch(condition, merge1));
     160           1 : }
     161             : 
     162             : 
     163       15419 : TEST_F(BranchEliminationTest, BranchInsideLoopSame) {
     164             :   // if (x) while (x) { return 2; } else { return 1; }
     165             :   // should be rewritten to
     166             :   // if (x) while (true) { return 2; } else { return 1; }
     167             : 
     168           1 :   Node* condition = Parameter(0);
     169             : 
     170             :   Node* outer_branch =
     171           2 :       graph()->NewNode(common()->Branch(), condition, graph()->start());
     172           1 :   Node* outer_if_true = graph()->NewNode(common()->IfTrue(), outer_branch);
     173             : 
     174             : 
     175           1 :   Node* loop = graph()->NewNode(common()->Loop(1), outer_if_true);
     176             :   Node* effect =
     177           1 :       graph()->NewNode(common()->EffectPhi(1), graph()->start(), loop);
     178             : 
     179           1 :   Node* inner_branch = graph()->NewNode(common()->Branch(), condition, loop);
     180             : 
     181           1 :   Node* inner_if_true = graph()->NewNode(common()->IfTrue(), inner_branch);
     182           1 :   Node* zero = graph()->NewNode(common()->Int32Constant(0));
     183           1 :   Node* ret1 = graph()->NewNode(common()->Return(), zero, Int32Constant(2),
     184           1 :                                 effect, inner_if_true);
     185             : 
     186           1 :   Node* inner_if_false = graph()->NewNode(common()->IfFalse(), inner_branch);
     187           1 :   loop->AppendInput(zone(), inner_if_false);
     188           1 :   NodeProperties::ChangeOp(loop, common()->Loop(2));
     189           1 :   effect->InsertInput(zone(), 1, effect);
     190           1 :   NodeProperties::ChangeOp(effect, common()->EffectPhi(2));
     191             : 
     192           1 :   Node* outer_if_false = graph()->NewNode(common()->IfFalse(), outer_branch);
     193             :   Node* outer_merge =
     194           1 :       graph()->NewNode(common()->Merge(2), loop, outer_if_false);
     195           1 :   Node* outer_ephi = graph()->NewNode(common()->EffectPhi(2), effect,
     196             :                                       graph()->start(), outer_merge);
     197             : 
     198           1 :   Node* ret2 = graph()->NewNode(common()->Return(), zero, Int32Constant(1),
     199             :                                 outer_ephi, outer_merge);
     200             : 
     201           1 :   Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop);
     202           1 :   graph()->SetEnd(graph()->NewNode(common()->End(3), ret1, ret2, terminate));
     203             : 
     204           1 :   Reduce();
     205             : 
     206             :   // Outer branch should not be rewritten, the inner branch should be discarded.
     207           6 :   EXPECT_THAT(outer_branch, IsBranch(condition, graph()->start()));
     208           8 :   EXPECT_THAT(ret1, IsReturn(IsInt32Constant(2), effect, loop));
     209           1 : }
     210             : 
     211             : }  // namespace compiler
     212             : }  // namespace internal
     213        9249 : }  // namespace v8

Generated by: LCOV version 1.10