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