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