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