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/effect-control-linearizer.h"
6 : #include "src/compiler/access-builder.h"
7 : #include "src/compiler/compiler-source-position-table.h"
8 : #include "src/compiler/js-graph.h"
9 : #include "src/compiler/linkage.h"
10 : #include "src/compiler/node-origin-table.h"
11 : #include "src/compiler/node-properties.h"
12 : #include "src/compiler/schedule.h"
13 : #include "src/compiler/simplified-operator.h"
14 : #include "test/unittests/compiler/graph-unittest.h"
15 : #include "test/unittests/compiler/node-test-utils.h"
16 : #include "test/unittests/test-utils.h"
17 : #include "testing/gmock-support.h"
18 : #include "testing/gmock/include/gmock/gmock.h"
19 :
20 : namespace v8 {
21 : namespace internal {
22 : namespace compiler {
23 :
24 : using testing::Capture;
25 :
26 4 : class EffectControlLinearizerTest : public GraphTest {
27 : public:
28 4 : EffectControlLinearizerTest()
29 : : GraphTest(3),
30 : machine_(zone()),
31 : javascript_(zone()),
32 : simplified_(zone()),
33 : jsgraph_(isolate(), graph(), common(), &javascript_, &simplified_,
34 12 : &machine_) {
35 4 : source_positions_ = new (zone()) SourcePositionTable(graph());
36 4 : node_origins_ = new (zone()) NodeOriginTable(graph());
37 4 : }
38 :
39 : JSGraph* jsgraph() { return &jsgraph_; }
40 : SimplifiedOperatorBuilder* simplified() { return &simplified_; }
41 : SourcePositionTable* source_positions() { return source_positions_; }
42 : NodeOriginTable* node_origins() { return node_origins_; }
43 :
44 : private:
45 : MachineOperatorBuilder machine_;
46 : JSOperatorBuilder javascript_;
47 : SimplifiedOperatorBuilder simplified_;
48 : JSGraph jsgraph_;
49 : SourcePositionTable* source_positions_;
50 : NodeOriginTable* node_origins_;
51 : };
52 :
53 : namespace {
54 :
55 12 : BasicBlock* AddBlockToSchedule(Schedule* schedule) {
56 12 : BasicBlock* block = schedule->NewBasicBlock();
57 24 : block->set_rpo_number(static_cast<int32_t>(schedule->rpo_order()->size()));
58 12 : schedule->rpo_order()->push_back(block);
59 12 : return block;
60 : }
61 :
62 : } // namespace
63 :
64 15189 : TEST_F(EffectControlLinearizerTest, SimpleLoad) {
65 1 : Schedule schedule(zone());
66 :
67 : // Create the graph.
68 1 : Node* heap_number = NumberConstant(0.5);
69 : Node* load = graph()->NewNode(
70 : simplified()->LoadField(AccessBuilder::ForHeapNumberValue()), heap_number,
71 3 : graph()->start(), graph()->start());
72 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
73 : Node* ret = graph()->NewNode(common()->Return(), zero, load, graph()->start(),
74 2 : graph()->start());
75 :
76 : // Build the basic block structure.
77 1 : BasicBlock* start = schedule.start();
78 1 : schedule.rpo_order()->push_back(start);
79 1 : start->set_rpo_number(0);
80 :
81 : // Populate the basic blocks with nodes.
82 1 : schedule.AddNode(start, graph()->start());
83 1 : schedule.AddNode(start, heap_number);
84 1 : schedule.AddNode(start, load);
85 1 : schedule.AddReturn(start, ret);
86 :
87 : // Run the state effect introducer.
88 : EffectControlLinearizer introducer(
89 : jsgraph(), &schedule, zone(), source_positions(), node_origins(),
90 1 : EffectControlLinearizer::kDoNotMaskArrayIndex);
91 1 : introducer.Run();
92 :
93 8 : EXPECT_THAT(load,
94 : IsLoadField(AccessBuilder::ForHeapNumberValue(), heap_number,
95 0 : graph()->start(), graph()->start()));
96 : // The return should have reconnected effect edge to the load.
97 7 : EXPECT_THAT(ret, IsReturn(load, load, graph()->start()));
98 1 : }
99 :
100 15189 : TEST_F(EffectControlLinearizerTest, DiamondLoad) {
101 1 : Schedule schedule(zone());
102 :
103 : // Create the graph.
104 : Node* branch =
105 1 : graph()->NewNode(common()->Branch(), Int32Constant(0), graph()->start());
106 :
107 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
108 1 : Node* heap_number = NumberConstant(0.5);
109 : Node* vtrue = graph()->NewNode(
110 : simplified()->LoadField(AccessBuilder::ForHeapNumberValue()), heap_number,
111 3 : graph()->start(), if_true);
112 :
113 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
114 1 : Node* vfalse = Float64Constant(2);
115 :
116 1 : Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
117 : Node* phi = graph()->NewNode(
118 1 : common()->Phi(MachineRepresentation::kFloat64, 2), vtrue, vfalse, merge);
119 :
120 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
121 : Node* ret =
122 2 : graph()->NewNode(common()->Return(), zero, phi, graph()->start(), merge);
123 :
124 : // Build the basic block structure.
125 1 : BasicBlock* start = schedule.start();
126 1 : schedule.rpo_order()->push_back(start);
127 1 : start->set_rpo_number(0);
128 :
129 1 : BasicBlock* tblock = AddBlockToSchedule(&schedule);
130 1 : BasicBlock* fblock = AddBlockToSchedule(&schedule);
131 1 : BasicBlock* mblock = AddBlockToSchedule(&schedule);
132 :
133 : // Populate the basic blocks with nodes.
134 1 : schedule.AddNode(start, graph()->start());
135 1 : schedule.AddBranch(start, branch, tblock, fblock);
136 :
137 1 : schedule.AddNode(tblock, if_true);
138 1 : schedule.AddNode(tblock, heap_number);
139 1 : schedule.AddNode(tblock, vtrue);
140 1 : schedule.AddGoto(tblock, mblock);
141 :
142 1 : schedule.AddNode(fblock, if_false);
143 1 : schedule.AddNode(fblock, vfalse);
144 1 : schedule.AddGoto(fblock, mblock);
145 :
146 1 : schedule.AddNode(mblock, merge);
147 1 : schedule.AddNode(mblock, phi);
148 1 : schedule.AddReturn(mblock, ret);
149 :
150 : // Run the state effect introducer.
151 : EffectControlLinearizer introducer(
152 : jsgraph(), &schedule, zone(), source_positions(), node_origins(),
153 1 : EffectControlLinearizer::kDoNotMaskArrayIndex);
154 1 : introducer.Run();
155 :
156 : // The effect input to the return should be an effect phi with the
157 : // newly introduced effectful change operators.
158 11 : ASSERT_THAT(
159 : ret, IsReturn(phi, IsEffectPhi(vtrue, graph()->start(), merge), merge));
160 : }
161 :
162 15189 : TEST_F(EffectControlLinearizerTest, LoopLoad) {
163 1 : Schedule schedule(zone());
164 :
165 : // Create the graph.
166 1 : Node* loop = graph()->NewNode(common()->Loop(1), graph()->start());
167 : Node* effect_phi =
168 1 : graph()->NewNode(common()->EffectPhi(1), graph()->start(), loop);
169 :
170 1 : Node* cond = Int32Constant(0);
171 1 : Node* branch = graph()->NewNode(common()->Branch(), cond, loop);
172 :
173 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
174 :
175 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
176 :
177 1 : loop->AppendInput(zone(), if_false);
178 1 : NodeProperties::ChangeOp(loop, common()->Loop(2));
179 :
180 1 : effect_phi->InsertInput(zone(), 1, effect_phi);
181 1 : NodeProperties::ChangeOp(effect_phi, common()->EffectPhi(2));
182 :
183 1 : Node* heap_number = NumberConstant(0.5);
184 : Node* load = graph()->NewNode(
185 : simplified()->LoadField(AccessBuilder::ForHeapNumberValue()), heap_number,
186 3 : graph()->start(), loop);
187 :
188 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
189 : Node* ret =
190 2 : graph()->NewNode(common()->Return(), zero, load, effect_phi, if_true);
191 :
192 : // Build the basic block structure.
193 1 : BasicBlock* start = schedule.start();
194 1 : schedule.rpo_order()->push_back(start);
195 1 : start->set_rpo_number(0);
196 :
197 1 : BasicBlock* lblock = AddBlockToSchedule(&schedule);
198 1 : BasicBlock* fblock = AddBlockToSchedule(&schedule);
199 1 : BasicBlock* rblock = AddBlockToSchedule(&schedule);
200 :
201 : // Populate the basic blocks with nodes.
202 1 : schedule.AddNode(start, graph()->start());
203 1 : schedule.AddGoto(start, lblock);
204 :
205 1 : schedule.AddNode(lblock, loop);
206 1 : schedule.AddNode(lblock, effect_phi);
207 1 : schedule.AddNode(lblock, heap_number);
208 1 : schedule.AddNode(lblock, load);
209 1 : schedule.AddNode(lblock, cond);
210 1 : schedule.AddBranch(lblock, branch, rblock, fblock);
211 :
212 1 : schedule.AddNode(fblock, if_false);
213 1 : schedule.AddGoto(fblock, lblock);
214 :
215 1 : schedule.AddNode(rblock, if_true);
216 1 : schedule.AddReturn(rblock, ret);
217 :
218 : // Run the state effect introducer.
219 : EffectControlLinearizer introducer(
220 : jsgraph(), &schedule, zone(), source_positions(), node_origins(),
221 1 : EffectControlLinearizer::kDoNotMaskArrayIndex);
222 1 : introducer.Run();
223 :
224 8 : ASSERT_THAT(ret, IsReturn(load, load, if_true));
225 8 : EXPECT_THAT(load, IsLoadField(AccessBuilder::ForHeapNumberValue(),
226 0 : heap_number, effect_phi, loop));
227 : }
228 :
229 15189 : TEST_F(EffectControlLinearizerTest, CloneBranch) {
230 1 : Schedule schedule(zone());
231 :
232 1 : Node* cond0 = Parameter(0);
233 1 : Node* cond1 = Parameter(1);
234 1 : Node* cond2 = Parameter(2);
235 1 : Node* branch0 = graph()->NewNode(common()->Branch(), cond0, start());
236 1 : Node* control1 = graph()->NewNode(common()->IfTrue(), branch0);
237 1 : Node* control2 = graph()->NewNode(common()->IfFalse(), branch0);
238 1 : Node* merge0 = graph()->NewNode(common()->Merge(2), control1, control2);
239 : Node* phi0 = graph()->NewNode(common()->Phi(MachineRepresentation::kBit, 2),
240 1 : cond1, cond2, merge0);
241 1 : Node* branch = graph()->NewNode(common()->Branch(), phi0, merge0);
242 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
243 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
244 1 : Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
245 1 : graph()->SetEnd(graph()->NewNode(common()->End(1), merge));
246 :
247 1 : BasicBlock* start = schedule.start();
248 1 : schedule.rpo_order()->push_back(start);
249 1 : start->set_rpo_number(0);
250 :
251 1 : BasicBlock* f1block = AddBlockToSchedule(&schedule);
252 1 : BasicBlock* t1block = AddBlockToSchedule(&schedule);
253 1 : BasicBlock* bblock = AddBlockToSchedule(&schedule);
254 :
255 1 : BasicBlock* f2block = AddBlockToSchedule(&schedule);
256 1 : BasicBlock* t2block = AddBlockToSchedule(&schedule);
257 1 : BasicBlock* mblock = AddBlockToSchedule(&schedule);
258 :
259 : // Populate the basic blocks with nodes.
260 1 : schedule.AddNode(start, graph()->start());
261 :
262 1 : schedule.AddBranch(start, branch0, t1block, f1block);
263 :
264 1 : schedule.AddNode(t1block, control1);
265 1 : schedule.AddGoto(t1block, bblock);
266 :
267 1 : schedule.AddNode(f1block, control2);
268 1 : schedule.AddGoto(f1block, bblock);
269 :
270 1 : schedule.AddNode(bblock, merge0);
271 1 : schedule.AddNode(bblock, phi0);
272 1 : schedule.AddBranch(bblock, branch, t2block, f2block);
273 :
274 1 : schedule.AddNode(t2block, if_true);
275 1 : schedule.AddGoto(t2block, mblock);
276 :
277 1 : schedule.AddNode(f2block, if_false);
278 1 : schedule.AddGoto(f2block, mblock);
279 :
280 1 : schedule.AddNode(mblock, merge);
281 1 : schedule.AddNode(mblock, graph()->end());
282 :
283 : EffectControlLinearizer introducer(
284 : jsgraph(), &schedule, zone(), source_positions(), node_origins(),
285 1 : EffectControlLinearizer::kDoNotMaskArrayIndex);
286 1 : introducer.Run();
287 :
288 : Capture<Node *> branch1_capture, branch2_capture;
289 27 : EXPECT_THAT(
290 : end(),
291 : IsEnd(IsMerge(IsMerge(IsIfTrue(CaptureEq(&branch1_capture)),
292 : IsIfTrue(CaptureEq(&branch2_capture))),
293 : IsMerge(IsIfFalse(AllOf(CaptureEq(&branch1_capture),
294 : IsBranch(cond1, control1))),
295 : IsIfFalse(AllOf(CaptureEq(&branch2_capture),
296 0 : IsBranch(cond2, control2)))))));
297 1 : }
298 :
299 : } // namespace compiler
300 : } // namespace internal
301 9111 : } // namespace v8
|