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