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