Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(53)

Side by Side Diff: test/unittests/compiler/move-optimizer-unittest.cc

Issue 2585583006: Move register allocation unittests and constrain owners (Closed)
Patch Set: Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « test/unittests/compiler/live-range-unittest.cc ('k') | test/unittests/compiler/regalloc/OWNERS » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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
OLDNEW
« no previous file with comments | « test/unittests/compiler/live-range-unittest.cc ('k') | test/unittests/compiler/regalloc/OWNERS » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698