OLD | NEW |
| (Empty) |
1 // Copyright 2014 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/move-optimizer.h" | |
6 #include "src/compiler/pipeline.h" | |
7 #include "test/unittests/compiler/instruction-sequence-unittest.h" | |
8 | |
9 namespace v8 { | |
10 namespace internal { | |
11 namespace compiler { | |
12 | |
13 class MoveOptimizerTest : public InstructionSequenceTest { | |
14 public: | |
15 // FP register indices which don't interfere under simple or complex aliasing. | |
16 static const int kF64_1 = 0; | |
17 static const int kF64_2 = 1; | |
18 static const int kF32_1 = 4; | |
19 static const int kF32_2 = 5; | |
20 static const int kS128_1 = 2; | |
21 static const int kS128_2 = 3; | |
22 | |
23 Instruction* LastInstruction() { return sequence()->instructions().back(); } | |
24 | |
25 void AddMove(Instruction* instr, TestOperand from, TestOperand to, | |
26 Instruction::GapPosition pos = Instruction::START) { | |
27 auto parallel_move = instr->GetOrCreateParallelMove(pos, zone()); | |
28 parallel_move->AddMove(ConvertMoveArg(from), ConvertMoveArg(to)); | |
29 } | |
30 | |
31 int NonRedundantSize(ParallelMove* moves) { | |
32 int i = 0; | |
33 for (auto move : *moves) { | |
34 if (move->IsRedundant()) continue; | |
35 i++; | |
36 } | |
37 return i; | |
38 } | |
39 | |
40 bool Contains(ParallelMove* moves, TestOperand from_op, TestOperand to_op) { | |
41 auto from = ConvertMoveArg(from_op); | |
42 auto to = ConvertMoveArg(to_op); | |
43 for (auto move : *moves) { | |
44 if (move->IsRedundant()) continue; | |
45 if (move->source().Equals(from) && move->destination().Equals(to)) { | |
46 return true; | |
47 } | |
48 } | |
49 return false; | |
50 } | |
51 | |
52 // TODO(dcarney): add a verifier. | |
53 void Optimize() { | |
54 WireBlocks(); | |
55 if (FLAG_trace_turbo) { | |
56 OFStream os(stdout); | |
57 PrintableInstructionSequence printable = {config(), sequence()}; | |
58 os << "----- Instruction sequence before move optimization -----\n" | |
59 << printable; | |
60 } | |
61 MoveOptimizer move_optimizer(zone(), sequence()); | |
62 move_optimizer.Run(); | |
63 if (FLAG_trace_turbo) { | |
64 OFStream os(stdout); | |
65 PrintableInstructionSequence printable = {config(), sequence()}; | |
66 os << "----- Instruction sequence after move optimization -----\n" | |
67 << printable; | |
68 } | |
69 } | |
70 | |
71 private: | |
72 bool DoesRegisterAllocation() const override { return false; } | |
73 | |
74 InstructionOperand ConvertMoveArg(TestOperand op) { | |
75 CHECK_EQ(kNoValue, op.vreg_.value_); | |
76 CHECK_NE(kNoValue, op.value_); | |
77 switch (op.type_) { | |
78 case kConstant: | |
79 return ConstantOperand(op.value_); | |
80 case kFixedSlot: | |
81 return AllocatedOperand(LocationOperand::STACK_SLOT, | |
82 MachineRepresentation::kWord32, op.value_); | |
83 case kFixedRegister: { | |
84 MachineRepresentation rep = GetCanonicalRep(op); | |
85 CHECK(0 <= op.value_ && op.value_ < GetNumRegs(rep)); | |
86 return AllocatedOperand(LocationOperand::REGISTER, rep, op.value_); | |
87 } | |
88 case kExplicit: { | |
89 MachineRepresentation rep = GetCanonicalRep(op); | |
90 CHECK(0 <= op.value_ && op.value_ < GetNumRegs(rep)); | |
91 return ExplicitOperand(LocationOperand::REGISTER, rep, op.value_); | |
92 } | |
93 default: | |
94 break; | |
95 } | |
96 CHECK(false); | |
97 return InstructionOperand(); | |
98 } | |
99 }; | |
100 | |
101 | |
102 TEST_F(MoveOptimizerTest, RemovesRedundant) { | |
103 StartBlock(); | |
104 auto first_instr = EmitNop(); | |
105 auto last_instr = EmitNop(); | |
106 | |
107 AddMove(first_instr, Reg(0), Reg(1)); | |
108 AddMove(last_instr, Reg(1), Reg(0)); | |
109 | |
110 AddMove(first_instr, FPReg(kS128_1, kSimd128), FPReg(kS128_2, kSimd128)); | |
111 AddMove(last_instr, FPReg(kS128_2, kSimd128), FPReg(kS128_1, kSimd128)); | |
112 AddMove(first_instr, FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64)); | |
113 AddMove(last_instr, FPReg(kF64_2, kFloat64), FPReg(kF64_1, kFloat64)); | |
114 AddMove(first_instr, FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32)); | |
115 AddMove(last_instr, FPReg(kF32_2, kFloat32), FPReg(kF32_1, kFloat32)); | |
116 | |
117 EndBlock(Last()); | |
118 | |
119 Optimize(); | |
120 | |
121 CHECK_EQ(0, NonRedundantSize(first_instr->parallel_moves()[0])); | |
122 auto move = last_instr->parallel_moves()[0]; | |
123 CHECK_EQ(4, NonRedundantSize(move)); | |
124 CHECK(Contains(move, Reg(0), Reg(1))); | |
125 CHECK(Contains(move, FPReg(kS128_1, kSimd128), FPReg(kS128_2, kSimd128))); | |
126 CHECK(Contains(move, FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64))); | |
127 CHECK(Contains(move, FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32))); | |
128 } | |
129 | |
130 | |
131 TEST_F(MoveOptimizerTest, RemovesRedundantExplicit) { | |
132 int index1 = GetAllocatableCode(0); | |
133 int index2 = GetAllocatableCode(1); | |
134 int s128_1 = GetAllocatableCode(kS128_1, kSimd128); | |
135 int s128_2 = GetAllocatableCode(kS128_2, kSimd128); | |
136 int f64_1 = GetAllocatableCode(kF64_1, kFloat64); | |
137 int f64_2 = GetAllocatableCode(kF64_2, kFloat64); | |
138 int f32_1 = GetAllocatableCode(kF32_1, kFloat32); | |
139 int f32_2 = GetAllocatableCode(kF32_2, kFloat32); | |
140 | |
141 StartBlock(); | |
142 auto first_instr = EmitNop(); | |
143 auto last_instr = EmitNop(); | |
144 | |
145 AddMove(first_instr, Reg(index1), ExplicitReg(index2)); | |
146 AddMove(last_instr, Reg(index2), Reg(index1)); | |
147 | |
148 AddMove(first_instr, FPReg(s128_1, kSimd128), | |
149 ExplicitFPReg(s128_2, kSimd128)); | |
150 AddMove(last_instr, FPReg(s128_2, kSimd128), FPReg(s128_1, kSimd128)); | |
151 AddMove(first_instr, FPReg(f64_1, kFloat64), ExplicitFPReg(f64_2, kFloat64)); | |
152 AddMove(last_instr, FPReg(f64_2, kFloat64), FPReg(f64_1, kFloat64)); | |
153 AddMove(first_instr, FPReg(f32_1, kFloat32), ExplicitFPReg(f32_2, kFloat32)); | |
154 AddMove(last_instr, FPReg(f32_2, kFloat32), FPReg(f32_1, kFloat32)); | |
155 | |
156 EndBlock(Last()); | |
157 | |
158 Optimize(); | |
159 | |
160 CHECK_EQ(0, NonRedundantSize(first_instr->parallel_moves()[0])); | |
161 auto move = last_instr->parallel_moves()[0]; | |
162 CHECK_EQ(4, NonRedundantSize(move)); | |
163 CHECK(Contains(move, Reg(index1), ExplicitReg(index2))); | |
164 CHECK( | |
165 Contains(move, FPReg(s128_1, kSimd128), ExplicitFPReg(s128_2, kSimd128))); | |
166 CHECK(Contains(move, FPReg(f64_1, kFloat64), ExplicitFPReg(f64_2, kFloat64))); | |
167 CHECK(Contains(move, FPReg(f32_1, kFloat32), ExplicitFPReg(f32_2, kFloat32))); | |
168 } | |
169 | |
170 | |
171 TEST_F(MoveOptimizerTest, SplitsConstants) { | |
172 StartBlock(); | |
173 EndBlock(Last()); | |
174 | |
175 auto gap = LastInstruction(); | |
176 AddMove(gap, Const(1), Slot(0)); | |
177 AddMove(gap, Const(1), Slot(1)); | |
178 AddMove(gap, Const(1), Reg(0)); | |
179 AddMove(gap, Const(1), Slot(2)); | |
180 | |
181 Optimize(); | |
182 | |
183 auto move = gap->parallel_moves()[0]; | |
184 CHECK_EQ(1, NonRedundantSize(move)); | |
185 CHECK(Contains(move, Const(1), Reg(0))); | |
186 | |
187 move = gap->parallel_moves()[1]; | |
188 CHECK_EQ(3, NonRedundantSize(move)); | |
189 CHECK(Contains(move, Reg(0), Slot(0))); | |
190 CHECK(Contains(move, Reg(0), Slot(1))); | |
191 CHECK(Contains(move, Reg(0), Slot(2))); | |
192 } | |
193 | |
194 | |
195 TEST_F(MoveOptimizerTest, SimpleMerge) { | |
196 StartBlock(); | |
197 EndBlock(Branch(Imm(), 1, 2)); | |
198 | |
199 StartBlock(); | |
200 EndBlock(Jump(2)); | |
201 AddMove(LastInstruction(), Reg(0), Reg(1)); | |
202 AddMove(LastInstruction(), FPReg(kS128_1, kSimd128), | |
203 FPReg(kS128_2, kSimd128)); | |
204 AddMove(LastInstruction(), FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64)); | |
205 AddMove(LastInstruction(), FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32)); | |
206 | |
207 StartBlock(); | |
208 EndBlock(Jump(1)); | |
209 AddMove(LastInstruction(), Reg(0), Reg(1)); | |
210 AddMove(LastInstruction(), FPReg(kS128_1, kSimd128), | |
211 FPReg(kS128_2, kSimd128)); | |
212 AddMove(LastInstruction(), FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64)); | |
213 AddMove(LastInstruction(), FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32)); | |
214 | |
215 StartBlock(); | |
216 EndBlock(Last()); | |
217 | |
218 auto last = LastInstruction(); | |
219 | |
220 Optimize(); | |
221 | |
222 auto move = last->parallel_moves()[0]; | |
223 CHECK_EQ(4, NonRedundantSize(move)); | |
224 CHECK(Contains(move, Reg(0), Reg(1))); | |
225 CHECK(Contains(move, FPReg(kS128_1, kSimd128), FPReg(kS128_2, kSimd128))); | |
226 CHECK(Contains(move, FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64))); | |
227 CHECK(Contains(move, FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32))); | |
228 } | |
229 | |
230 | |
231 TEST_F(MoveOptimizerTest, SimpleMergeCycle) { | |
232 StartBlock(); | |
233 EndBlock(Branch(Imm(), 1, 2)); | |
234 | |
235 StartBlock(); | |
236 EndBlock(Jump(2)); | |
237 auto gap_0 = LastInstruction(); | |
238 AddMove(gap_0, Reg(0), Reg(1)); | |
239 AddMove(LastInstruction(), Reg(1), Reg(0)); | |
240 | |
241 AddMove(gap_0, FPReg(kS128_1, kSimd128), FPReg(kS128_2, kSimd128)); | |
242 AddMove(LastInstruction(), FPReg(kS128_2, kSimd128), | |
243 FPReg(kS128_1, kSimd128)); | |
244 AddMove(gap_0, FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64)); | |
245 AddMove(LastInstruction(), FPReg(kF64_2, kFloat64), FPReg(kF64_1, kFloat64)); | |
246 AddMove(gap_0, FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32)); | |
247 AddMove(LastInstruction(), FPReg(kF32_2, kFloat32), FPReg(kF32_1, kFloat32)); | |
248 | |
249 StartBlock(); | |
250 EndBlock(Jump(1)); | |
251 auto gap_1 = LastInstruction(); | |
252 AddMove(gap_1, Reg(0), Reg(1)); | |
253 AddMove(gap_1, Reg(1), Reg(0)); | |
254 AddMove(gap_1, FPReg(kS128_1, kSimd128), FPReg(kS128_2, kSimd128)); | |
255 AddMove(gap_1, FPReg(kS128_2, kSimd128), FPReg(kS128_1, kSimd128)); | |
256 AddMove(gap_1, FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64)); | |
257 AddMove(gap_1, FPReg(kF64_2, kFloat64), FPReg(kF64_1, kFloat64)); | |
258 AddMove(gap_1, FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32)); | |
259 AddMove(gap_1, FPReg(kF32_2, kFloat32), FPReg(kF32_1, kFloat32)); | |
260 | |
261 StartBlock(); | |
262 EndBlock(Last()); | |
263 | |
264 auto last = LastInstruction(); | |
265 | |
266 Optimize(); | |
267 | |
268 CHECK(gap_0->AreMovesRedundant()); | |
269 CHECK(gap_1->AreMovesRedundant()); | |
270 auto move = last->parallel_moves()[0]; | |
271 CHECK_EQ(8, NonRedundantSize(move)); | |
272 CHECK(Contains(move, Reg(0), Reg(1))); | |
273 CHECK(Contains(move, Reg(1), Reg(0))); | |
274 CHECK(Contains(move, FPReg(kS128_1, kSimd128), FPReg(kS128_2, kSimd128))); | |
275 CHECK(Contains(move, FPReg(kS128_2, kSimd128), FPReg(kS128_1, kSimd128))); | |
276 CHECK(Contains(move, FPReg(kF64_1, kFloat64), FPReg(kF64_2, kFloat64))); | |
277 CHECK(Contains(move, FPReg(kF64_2, kFloat64), FPReg(kF64_1, kFloat64))); | |
278 CHECK(Contains(move, FPReg(kF32_1, kFloat32), FPReg(kF32_2, kFloat32))); | |
279 CHECK(Contains(move, FPReg(kF32_2, kFloat32), FPReg(kF32_1, kFloat32))); | |
280 } | |
281 | |
282 | |
283 TEST_F(MoveOptimizerTest, GapsCanMoveOverInstruction) { | |
284 StartBlock(); | |
285 int const_index = 1; | |
286 DefineConstant(const_index); | |
287 Instruction* ctant_def = LastInstruction(); | |
288 AddMove(ctant_def, Reg(1), Reg(0)); | |
289 | |
290 Instruction* last = EmitNop(); | |
291 AddMove(last, Const(const_index), Reg(0)); | |
292 AddMove(last, Reg(0), Reg(1)); | |
293 EndBlock(Last()); | |
294 Optimize(); | |
295 | |
296 ParallelMove* inst1_start = | |
297 ctant_def->GetParallelMove(Instruction::GapPosition::START); | |
298 ParallelMove* inst1_end = | |
299 ctant_def->GetParallelMove(Instruction::GapPosition::END); | |
300 ParallelMove* last_start = | |
301 last->GetParallelMove(Instruction::GapPosition::START); | |
302 CHECK(inst1_start == nullptr || NonRedundantSize(inst1_start) == 0); | |
303 CHECK(inst1_end == nullptr || NonRedundantSize(inst1_end) == 0); | |
304 CHECK(last_start->size() == 2); | |
305 int redundants = 0; | |
306 int assignment = 0; | |
307 for (MoveOperands* move : *last_start) { | |
308 if (move->IsRedundant()) { | |
309 ++redundants; | |
310 } else { | |
311 ++assignment; | |
312 CHECK(move->destination().IsRegister()); | |
313 CHECK(move->source().IsConstant()); | |
314 } | |
315 } | |
316 CHECK_EQ(1, redundants); | |
317 CHECK_EQ(1, assignment); | |
318 } | |
319 | |
320 | |
321 TEST_F(MoveOptimizerTest, SubsetMovesMerge) { | |
322 StartBlock(); | |
323 EndBlock(Branch(Imm(), 1, 2)); | |
324 | |
325 StartBlock(); | |
326 EndBlock(Jump(2)); | |
327 Instruction* last_move_b1 = LastInstruction(); | |
328 AddMove(last_move_b1, Reg(0), Reg(1)); | |
329 AddMove(last_move_b1, Reg(2), Reg(3)); | |
330 | |
331 StartBlock(); | |
332 EndBlock(Jump(1)); | |
333 Instruction* last_move_b2 = LastInstruction(); | |
334 AddMove(last_move_b2, Reg(0), Reg(1)); | |
335 AddMove(last_move_b2, Reg(4), Reg(5)); | |
336 | |
337 StartBlock(); | |
338 EndBlock(Last()); | |
339 | |
340 Instruction* last = LastInstruction(); | |
341 | |
342 Optimize(); | |
343 | |
344 ParallelMove* last_move = last->parallel_moves()[0]; | |
345 CHECK_EQ(1, NonRedundantSize(last_move)); | |
346 CHECK(Contains(last_move, Reg(0), Reg(1))); | |
347 | |
348 ParallelMove* b1_move = last_move_b1->parallel_moves()[0]; | |
349 CHECK_EQ(1, NonRedundantSize(b1_move)); | |
350 CHECK(Contains(b1_move, Reg(2), Reg(3))); | |
351 | |
352 ParallelMove* b2_move = last_move_b2->parallel_moves()[0]; | |
353 CHECK_EQ(1, NonRedundantSize(b2_move)); | |
354 CHECK(Contains(b2_move, Reg(4), Reg(5))); | |
355 } | |
356 | |
357 | |
358 TEST_F(MoveOptimizerTest, GapConflictSubsetMovesDoNotMerge) { | |
359 StartBlock(); | |
360 EndBlock(Branch(Imm(), 1, 2)); | |
361 | |
362 StartBlock(); | |
363 EndBlock(Jump(2)); | |
364 Instruction* last_move_b1 = LastInstruction(); | |
365 AddMove(last_move_b1, Reg(0), Reg(1)); | |
366 AddMove(last_move_b1, Reg(2), Reg(0)); | |
367 AddMove(last_move_b1, Reg(4), Reg(5)); | |
368 | |
369 StartBlock(); | |
370 EndBlock(Jump(1)); | |
371 Instruction* last_move_b2 = LastInstruction(); | |
372 AddMove(last_move_b2, Reg(0), Reg(1)); | |
373 AddMove(last_move_b2, Reg(4), Reg(5)); | |
374 | |
375 StartBlock(); | |
376 EndBlock(Last()); | |
377 | |
378 Instruction* last = LastInstruction(); | |
379 | |
380 Optimize(); | |
381 | |
382 ParallelMove* last_move = last->parallel_moves()[0]; | |
383 CHECK_EQ(1, NonRedundantSize(last_move)); | |
384 CHECK(Contains(last_move, Reg(4), Reg(5))); | |
385 | |
386 ParallelMove* b1_move = last_move_b1->parallel_moves()[0]; | |
387 CHECK_EQ(2, NonRedundantSize(b1_move)); | |
388 CHECK(Contains(b1_move, Reg(0), Reg(1))); | |
389 CHECK(Contains(b1_move, Reg(2), Reg(0))); | |
390 | |
391 ParallelMove* b2_move = last_move_b2->parallel_moves()[0]; | |
392 CHECK_EQ(1, NonRedundantSize(b2_move)); | |
393 CHECK(Contains(b1_move, Reg(0), Reg(1))); | |
394 } | |
395 | |
396 TEST_F(MoveOptimizerTest, ClobberedDestinationsAreEliminated) { | |
397 StartBlock(); | |
398 EmitNop(); | |
399 Instruction* first_instr = LastInstruction(); | |
400 AddMove(first_instr, Reg(0), Reg(1)); | |
401 EmitOI(Reg(1), 0, nullptr); | |
402 Instruction* last_instr = LastInstruction(); | |
403 EndBlock(); | |
404 Optimize(); | |
405 | |
406 ParallelMove* first_move = first_instr->parallel_moves()[0]; | |
407 CHECK_EQ(0, NonRedundantSize(first_move)); | |
408 | |
409 ParallelMove* last_move = last_instr->parallel_moves()[0]; | |
410 CHECK_EQ(0, NonRedundantSize(last_move)); | |
411 } | |
412 | |
413 TEST_F(MoveOptimizerTest, ClobberedFPDestinationsAreEliminated) { | |
414 StartBlock(); | |
415 EmitNop(); | |
416 Instruction* first_instr = LastInstruction(); | |
417 AddMove(first_instr, FPReg(4, kFloat64), FPReg(1, kFloat64)); | |
418 if (!kSimpleFPAliasing) { | |
419 // We clobber q0 below. This is aliased by d0, d1, s0, s1, s2, and s3. | |
420 // Add moves to registers s2 and s3. | |
421 AddMove(first_instr, FPReg(10, kFloat32), FPReg(0, kFloat32)); | |
422 AddMove(first_instr, FPReg(11, kFloat32), FPReg(1, kFloat32)); | |
423 } | |
424 // Clobbers output register 0. | |
425 EmitOI(FPReg(0, kSimd128), 0, nullptr); | |
426 Instruction* last_instr = LastInstruction(); | |
427 EndBlock(); | |
428 Optimize(); | |
429 | |
430 ParallelMove* first_move = first_instr->parallel_moves()[0]; | |
431 CHECK_EQ(0, NonRedundantSize(first_move)); | |
432 | |
433 ParallelMove* last_move = last_instr->parallel_moves()[0]; | |
434 CHECK_EQ(0, NonRedundantSize(last_move)); | |
435 } | |
436 | |
437 } // namespace compiler | |
438 } // namespace internal | |
439 } // namespace v8 | |
OLD | NEW |