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 15374 : 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 15374 : 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 15374 : 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 15374 : 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 9222 : } // namespace v8
|
