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/v8.h" | |
6 #include "test/cctest/cctest.h" | |
7 | |
8 #include "src/base/utils/random-number-generator.h" | |
9 #include "test/cctest/compiler/codegen-tester.h" | |
10 #include "test/cctest/compiler/structured-machine-assembler.h" | |
11 #include "test/cctest/compiler/value-helper.h" | |
12 | |
13 #if V8_TURBOFAN_TARGET | |
14 | |
15 using namespace v8::internal::compiler; | |
16 | |
17 typedef StructuredMachineAssembler::IfBuilder IfBuilder; | |
18 typedef StructuredMachineAssembler::LoopBuilder Loop; | |
19 | |
20 namespace v8 { | |
21 namespace internal { | |
22 namespace compiler { | |
23 | |
24 class StructuredMachineAssemblerFriend { | |
25 public: | |
26 static bool VariableAlive(StructuredMachineAssembler* m, | |
27 const Variable& var) { | |
28 CHECK(m->current_environment_ != NULL); | |
29 int offset = var.offset_; | |
30 return offset < static_cast<int>(m->CurrentVars()->size()) && | |
31 m->CurrentVars()->at(offset) != NULL; | |
32 } | |
33 }; | |
34 } | |
35 } | |
36 } // namespace v8::internal::compiler | |
37 | |
38 | |
39 TEST(RunVariable) { | |
40 StructuredMachineAssemblerTester<int32_t> m; | |
41 | |
42 int32_t constant = 0x86c2bb16; | |
43 | |
44 Variable v1 = m.NewVariable(m.Int32Constant(constant)); | |
45 Variable v2 = m.NewVariable(v1.Get()); | |
46 m.Return(v2.Get()); | |
47 | |
48 CHECK_EQ(constant, m.Call()); | |
49 } | |
50 | |
51 | |
52 TEST(RunSimpleIf) { | |
53 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
54 | |
55 int32_t constant = 0xc4a3e3a6; | |
56 { | |
57 IfBuilder cond(&m); | |
58 cond.If(m.Parameter(0)).Then(); | |
59 m.Return(m.Int32Constant(constant)); | |
60 } | |
61 m.Return(m.Word32Not(m.Int32Constant(constant))); | |
62 | |
63 CHECK_EQ(~constant, m.Call(0)); | |
64 CHECK_EQ(constant, m.Call(1)); | |
65 } | |
66 | |
67 | |
68 TEST(RunSimpleIfVariable) { | |
69 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
70 | |
71 int32_t constant = 0xdb6f20c2; | |
72 Variable var = m.NewVariable(m.Int32Constant(constant)); | |
73 { | |
74 IfBuilder cond(&m); | |
75 cond.If(m.Parameter(0)).Then(); | |
76 var.Set(m.Word32Not(var.Get())); | |
77 } | |
78 m.Return(var.Get()); | |
79 | |
80 CHECK_EQ(constant, m.Call(0)); | |
81 CHECK_EQ(~constant, m.Call(1)); | |
82 } | |
83 | |
84 | |
85 TEST(RunSimpleElse) { | |
86 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
87 | |
88 int32_t constant = 0xfc5eadf4; | |
89 { | |
90 IfBuilder cond(&m); | |
91 cond.If(m.Parameter(0)).Else(); | |
92 m.Return(m.Int32Constant(constant)); | |
93 } | |
94 m.Return(m.Word32Not(m.Int32Constant(constant))); | |
95 | |
96 CHECK_EQ(constant, m.Call(0)); | |
97 CHECK_EQ(~constant, m.Call(1)); | |
98 } | |
99 | |
100 | |
101 TEST(RunSimpleIfElse) { | |
102 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
103 | |
104 int32_t constant = 0xaa9c8cd3; | |
105 { | |
106 IfBuilder cond(&m); | |
107 cond.If(m.Parameter(0)).Then(); | |
108 m.Return(m.Int32Constant(constant)); | |
109 cond.Else(); | |
110 m.Return(m.Word32Not(m.Int32Constant(constant))); | |
111 } | |
112 | |
113 CHECK_EQ(~constant, m.Call(0)); | |
114 CHECK_EQ(constant, m.Call(1)); | |
115 } | |
116 | |
117 | |
118 TEST(RunSimpleIfElseVariable) { | |
119 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
120 | |
121 int32_t constant = 0x67b6f39c; | |
122 Variable var = m.NewVariable(m.Int32Constant(constant)); | |
123 { | |
124 IfBuilder cond(&m); | |
125 cond.If(m.Parameter(0)).Then(); | |
126 var.Set(m.Word32Not(m.Word32Not(var.Get()))); | |
127 cond.Else(); | |
128 var.Set(m.Word32Not(var.Get())); | |
129 } | |
130 m.Return(var.Get()); | |
131 | |
132 CHECK_EQ(~constant, m.Call(0)); | |
133 CHECK_EQ(constant, m.Call(1)); | |
134 } | |
135 | |
136 | |
137 TEST(RunSimpleIfNoThenElse) { | |
138 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
139 | |
140 int32_t constant = 0xd5e550ed; | |
141 { | |
142 IfBuilder cond(&m); | |
143 cond.If(m.Parameter(0)); | |
144 } | |
145 m.Return(m.Int32Constant(constant)); | |
146 | |
147 CHECK_EQ(constant, m.Call(0)); | |
148 CHECK_EQ(constant, m.Call(1)); | |
149 } | |
150 | |
151 | |
152 TEST(RunSimpleConjunctionVariable) { | |
153 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
154 | |
155 int32_t constant = 0xf8fb9ec6; | |
156 Variable var = m.NewVariable(m.Int32Constant(constant)); | |
157 { | |
158 IfBuilder cond(&m); | |
159 cond.If(m.Int32Constant(1)).And(); | |
160 var.Set(m.Word32Not(var.Get())); | |
161 cond.If(m.Parameter(0)).Then(); | |
162 var.Set(m.Word32Not(m.Word32Not(var.Get()))); | |
163 cond.Else(); | |
164 var.Set(m.Word32Not(var.Get())); | |
165 } | |
166 m.Return(var.Get()); | |
167 | |
168 CHECK_EQ(constant, m.Call(0)); | |
169 CHECK_EQ(~constant, m.Call(1)); | |
170 } | |
171 | |
172 | |
173 TEST(RunSimpleDisjunctionVariable) { | |
174 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
175 | |
176 int32_t constant = 0x118f6ffc; | |
177 Variable var = m.NewVariable(m.Int32Constant(constant)); | |
178 { | |
179 IfBuilder cond(&m); | |
180 cond.If(m.Int32Constant(0)).Or(); | |
181 var.Set(m.Word32Not(var.Get())); | |
182 cond.If(m.Parameter(0)).Then(); | |
183 var.Set(m.Word32Not(m.Word32Not(var.Get()))); | |
184 cond.Else(); | |
185 var.Set(m.Word32Not(var.Get())); | |
186 } | |
187 m.Return(var.Get()); | |
188 | |
189 CHECK_EQ(constant, m.Call(0)); | |
190 CHECK_EQ(~constant, m.Call(1)); | |
191 } | |
192 | |
193 | |
194 TEST(RunIfElse) { | |
195 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
196 | |
197 { | |
198 IfBuilder cond(&m); | |
199 bool first = true; | |
200 FOR_INT32_INPUTS(i) { | |
201 Node* c = m.Int32Constant(*i); | |
202 if (first) { | |
203 cond.If(m.Word32Equal(m.Parameter(0), c)).Then(); | |
204 m.Return(c); | |
205 first = false; | |
206 } else { | |
207 cond.Else(); | |
208 cond.If(m.Word32Equal(m.Parameter(0), c)).Then(); | |
209 m.Return(c); | |
210 } | |
211 } | |
212 } | |
213 m.Return(m.Int32Constant(333)); | |
214 | |
215 FOR_INT32_INPUTS(i) { CHECK_EQ(*i, m.Call(*i)); } | |
216 } | |
217 | |
218 | |
219 enum IfBuilderBranchType { kSkipBranch, kBranchFallsThrough, kBranchReturns }; | |
220 | |
221 | |
222 static IfBuilderBranchType all_branch_types[] = { | |
223 kSkipBranch, kBranchFallsThrough, kBranchReturns}; | |
224 | |
225 | |
226 static void RunIfBuilderDisjunction(size_t max, IfBuilderBranchType then_type, | |
227 IfBuilderBranchType else_type) { | |
228 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
229 | |
230 std::vector<int32_t> inputs = ValueHelper::int32_vector(); | |
231 std::vector<int32_t>::const_iterator i = inputs.begin(); | |
232 int32_t hit = 0x8c723c9a; | |
233 int32_t miss = 0x88a6b9f3; | |
234 { | |
235 Node* p0 = m.Parameter(0); | |
236 IfBuilder cond(&m); | |
237 for (size_t j = 0; j < max; j++, ++i) { | |
238 CHECK(i != inputs.end()); // Thank you STL. | |
239 if (j > 0) cond.Or(); | |
240 cond.If(m.Word32Equal(p0, m.Int32Constant(*i))); | |
241 } | |
242 switch (then_type) { | |
243 case kSkipBranch: | |
244 break; | |
245 case kBranchFallsThrough: | |
246 cond.Then(); | |
247 break; | |
248 case kBranchReturns: | |
249 cond.Then(); | |
250 m.Return(m.Int32Constant(hit)); | |
251 break; | |
252 } | |
253 switch (else_type) { | |
254 case kSkipBranch: | |
255 break; | |
256 case kBranchFallsThrough: | |
257 cond.Else(); | |
258 break; | |
259 case kBranchReturns: | |
260 cond.Else(); | |
261 m.Return(m.Int32Constant(miss)); | |
262 break; | |
263 } | |
264 } | |
265 if (then_type != kBranchReturns || else_type != kBranchReturns) { | |
266 m.Return(m.Int32Constant(miss)); | |
267 } | |
268 | |
269 if (then_type != kBranchReturns) hit = miss; | |
270 | |
271 i = inputs.begin(); | |
272 for (size_t j = 0; i != inputs.end(); j++, ++i) { | |
273 int32_t result = m.Call(*i); | |
274 CHECK_EQ(j < max ? hit : miss, result); | |
275 } | |
276 } | |
277 | |
278 | |
279 TEST(RunIfBuilderDisjunction) { | |
280 size_t len = ValueHelper::int32_vector().size() - 1; | |
281 size_t max = len > 10 ? 10 : len - 1; | |
282 for (size_t i = 0; i < arraysize(all_branch_types); i++) { | |
283 for (size_t j = 0; j < arraysize(all_branch_types); j++) { | |
284 for (size_t size = 1; size < max; size++) { | |
285 RunIfBuilderDisjunction(size, all_branch_types[i], all_branch_types[j]); | |
286 } | |
287 RunIfBuilderDisjunction(len, all_branch_types[i], all_branch_types[j]); | |
288 } | |
289 } | |
290 } | |
291 | |
292 | |
293 static void RunIfBuilderConjunction(size_t max, IfBuilderBranchType then_type, | |
294 IfBuilderBranchType else_type) { | |
295 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
296 | |
297 std::vector<int32_t> inputs = ValueHelper::int32_vector(); | |
298 std::vector<int32_t>::const_iterator i = inputs.begin(); | |
299 int32_t hit = 0xa0ceb9ca; | |
300 int32_t miss = 0x226cafaa; | |
301 { | |
302 IfBuilder cond(&m); | |
303 Node* p0 = m.Parameter(0); | |
304 for (size_t j = 0; j < max; j++, ++i) { | |
305 if (j > 0) cond.And(); | |
306 cond.If(m.Word32NotEqual(p0, m.Int32Constant(*i))); | |
307 } | |
308 switch (then_type) { | |
309 case kSkipBranch: | |
310 break; | |
311 case kBranchFallsThrough: | |
312 cond.Then(); | |
313 break; | |
314 case kBranchReturns: | |
315 cond.Then(); | |
316 m.Return(m.Int32Constant(hit)); | |
317 break; | |
318 } | |
319 switch (else_type) { | |
320 case kSkipBranch: | |
321 break; | |
322 case kBranchFallsThrough: | |
323 cond.Else(); | |
324 break; | |
325 case kBranchReturns: | |
326 cond.Else(); | |
327 m.Return(m.Int32Constant(miss)); | |
328 break; | |
329 } | |
330 } | |
331 if (then_type != kBranchReturns || else_type != kBranchReturns) { | |
332 m.Return(m.Int32Constant(miss)); | |
333 } | |
334 | |
335 if (then_type != kBranchReturns) hit = miss; | |
336 | |
337 i = inputs.begin(); | |
338 for (size_t j = 0; i != inputs.end(); j++, ++i) { | |
339 int32_t result = m.Call(*i); | |
340 CHECK_EQ(j >= max ? hit : miss, result); | |
341 } | |
342 } | |
343 | |
344 | |
345 TEST(RunIfBuilderConjunction) { | |
346 size_t len = ValueHelper::int32_vector().size() - 1; | |
347 size_t max = len > 10 ? 10 : len - 1; | |
348 for (size_t i = 0; i < arraysize(all_branch_types); i++) { | |
349 for (size_t j = 0; j < arraysize(all_branch_types); j++) { | |
350 for (size_t size = 1; size < max; size++) { | |
351 RunIfBuilderConjunction(size, all_branch_types[i], all_branch_types[j]); | |
352 } | |
353 RunIfBuilderConjunction(len, all_branch_types[i], all_branch_types[j]); | |
354 } | |
355 } | |
356 } | |
357 | |
358 | |
359 static void RunDisjunctionVariables(int disjunctions, bool explicit_then, | |
360 bool explicit_else) { | |
361 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
362 | |
363 int32_t constant = 0x65a09535; | |
364 | |
365 Node* cmp_val = m.Int32Constant(constant); | |
366 Node* one = m.Int32Constant(1); | |
367 Variable var = m.NewVariable(m.Parameter(0)); | |
368 { | |
369 IfBuilder cond(&m); | |
370 cond.If(m.Word32Equal(var.Get(), cmp_val)); | |
371 for (int i = 0; i < disjunctions; i++) { | |
372 cond.Or(); | |
373 var.Set(m.Int32Add(var.Get(), one)); | |
374 cond.If(m.Word32Equal(var.Get(), cmp_val)); | |
375 } | |
376 if (explicit_then) { | |
377 cond.Then(); | |
378 } | |
379 if (explicit_else) { | |
380 cond.Else(); | |
381 var.Set(m.Int32Add(var.Get(), one)); | |
382 } | |
383 } | |
384 m.Return(var.Get()); | |
385 | |
386 int adds = disjunctions + (explicit_else ? 1 : 0); | |
387 int32_t input = constant - 2 * adds; | |
388 for (int i = 0; i < adds; i++) { | |
389 CHECK_EQ(input + adds, m.Call(input)); | |
390 input++; | |
391 } | |
392 for (int i = 0; i < adds + 1; i++) { | |
393 CHECK_EQ(constant, m.Call(input)); | |
394 input++; | |
395 } | |
396 for (int i = 0; i < adds; i++) { | |
397 CHECK_EQ(input + adds, m.Call(input)); | |
398 input++; | |
399 } | |
400 } | |
401 | |
402 | |
403 TEST(RunDisjunctionVariables) { | |
404 for (int disjunctions = 0; disjunctions < 10; disjunctions++) { | |
405 RunDisjunctionVariables(disjunctions, false, false); | |
406 RunDisjunctionVariables(disjunctions, false, true); | |
407 RunDisjunctionVariables(disjunctions, true, false); | |
408 RunDisjunctionVariables(disjunctions, true, true); | |
409 } | |
410 } | |
411 | |
412 | |
413 static void RunConjunctionVariables(int conjunctions, bool explicit_then, | |
414 bool explicit_else) { | |
415 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
416 | |
417 int32_t constant = 0x2c7f4b45; | |
418 Node* cmp_val = m.Int32Constant(constant); | |
419 Node* one = m.Int32Constant(1); | |
420 Variable var = m.NewVariable(m.Parameter(0)); | |
421 { | |
422 IfBuilder cond(&m); | |
423 cond.If(m.Word32NotEqual(var.Get(), cmp_val)); | |
424 for (int i = 0; i < conjunctions; i++) { | |
425 cond.And(); | |
426 var.Set(m.Int32Add(var.Get(), one)); | |
427 cond.If(m.Word32NotEqual(var.Get(), cmp_val)); | |
428 } | |
429 if (explicit_then) { | |
430 cond.Then(); | |
431 var.Set(m.Int32Add(var.Get(), one)); | |
432 } | |
433 if (explicit_else) { | |
434 cond.Else(); | |
435 } | |
436 } | |
437 m.Return(var.Get()); | |
438 | |
439 int adds = conjunctions + (explicit_then ? 1 : 0); | |
440 int32_t input = constant - 2 * adds; | |
441 for (int i = 0; i < adds; i++) { | |
442 CHECK_EQ(input + adds, m.Call(input)); | |
443 input++; | |
444 } | |
445 for (int i = 0; i < adds + 1; i++) { | |
446 CHECK_EQ(constant, m.Call(input)); | |
447 input++; | |
448 } | |
449 for (int i = 0; i < adds; i++) { | |
450 CHECK_EQ(input + adds, m.Call(input)); | |
451 input++; | |
452 } | |
453 } | |
454 | |
455 | |
456 TEST(RunConjunctionVariables) { | |
457 for (int conjunctions = 0; conjunctions < 10; conjunctions++) { | |
458 RunConjunctionVariables(conjunctions, false, false); | |
459 RunConjunctionVariables(conjunctions, false, true); | |
460 RunConjunctionVariables(conjunctions, true, false); | |
461 RunConjunctionVariables(conjunctions, true, true); | |
462 } | |
463 } | |
464 | |
465 | |
466 TEST(RunSimpleNestedIf) { | |
467 StructuredMachineAssemblerTester<int32_t> m(kMachInt32, kMachInt32); | |
468 const size_t NUM_VALUES = 7; | |
469 std::vector<int32_t> inputs = ValueHelper::int32_vector(); | |
470 CHECK(inputs.size() >= NUM_VALUES); | |
471 Node* values[NUM_VALUES]; | |
472 for (size_t j = 0; j < NUM_VALUES; j++) { | |
473 values[j] = m.Int32Constant(inputs[j]); | |
474 } | |
475 { | |
476 IfBuilder if_0(&m); | |
477 if_0.If(m.Word32Equal(m.Parameter(0), values[0])).Then(); | |
478 { | |
479 IfBuilder if_1(&m); | |
480 if_1.If(m.Word32Equal(m.Parameter(1), values[1])).Then(); | |
481 { m.Return(values[3]); } | |
482 if_1.Else(); | |
483 { m.Return(values[4]); } | |
484 } | |
485 if_0.Else(); | |
486 { | |
487 IfBuilder if_1(&m); | |
488 if_1.If(m.Word32Equal(m.Parameter(1), values[2])).Then(); | |
489 { m.Return(values[5]); } | |
490 if_1.Else(); | |
491 { m.Return(values[6]); } | |
492 } | |
493 } | |
494 | |
495 int32_t result = m.Call(inputs[0], inputs[1]); | |
496 CHECK_EQ(inputs[3], result); | |
497 | |
498 result = m.Call(inputs[0], inputs[1] + 1); | |
499 CHECK_EQ(inputs[4], result); | |
500 | |
501 result = m.Call(inputs[0] + 1, inputs[2]); | |
502 CHECK_EQ(inputs[5], result); | |
503 | |
504 result = m.Call(inputs[0] + 1, inputs[2] + 1); | |
505 CHECK_EQ(inputs[6], result); | |
506 } | |
507 | |
508 | |
509 TEST(RunUnreachableBlockAfterIf) { | |
510 StructuredMachineAssemblerTester<int32_t> m; | |
511 { | |
512 IfBuilder cond(&m); | |
513 cond.If(m.Int32Constant(0)).Then(); | |
514 m.Return(m.Int32Constant(1)); | |
515 cond.Else(); | |
516 m.Return(m.Int32Constant(2)); | |
517 } | |
518 // This is unreachable. | |
519 m.Return(m.Int32Constant(3)); | |
520 CHECK_EQ(2, m.Call()); | |
521 } | |
522 | |
523 | |
524 TEST(RunUnreachableBlockAfterLoop) { | |
525 StructuredMachineAssemblerTester<int32_t> m; | |
526 { | |
527 Loop loop(&m); | |
528 m.Return(m.Int32Constant(1)); | |
529 } | |
530 // This is unreachable. | |
531 m.Return(m.Int32Constant(3)); | |
532 CHECK_EQ(1, m.Call()); | |
533 } | |
534 | |
535 | |
536 TEST(RunSimpleLoop) { | |
537 StructuredMachineAssemblerTester<int32_t> m; | |
538 int32_t constant = 0x120c1f85; | |
539 { | |
540 Loop loop(&m); | |
541 m.Return(m.Int32Constant(constant)); | |
542 } | |
543 CHECK_EQ(constant, m.Call()); | |
544 } | |
545 | |
546 | |
547 TEST(RunSimpleLoopBreak) { | |
548 StructuredMachineAssemblerTester<int32_t> m; | |
549 int32_t constant = 0x10ddb0a6; | |
550 { | |
551 Loop loop(&m); | |
552 loop.Break(); | |
553 } | |
554 m.Return(m.Int32Constant(constant)); | |
555 CHECK_EQ(constant, m.Call()); | |
556 } | |
557 | |
558 | |
559 TEST(RunCountToTen) { | |
560 StructuredMachineAssemblerTester<int32_t> m; | |
561 Variable i = m.NewVariable(m.Int32Constant(0)); | |
562 Node* ten = m.Int32Constant(10); | |
563 Node* one = m.Int32Constant(1); | |
564 { | |
565 Loop loop(&m); | |
566 { | |
567 IfBuilder cond(&m); | |
568 cond.If(m.Word32Equal(i.Get(), ten)).Then(); | |
569 loop.Break(); | |
570 } | |
571 i.Set(m.Int32Add(i.Get(), one)); | |
572 } | |
573 m.Return(i.Get()); | |
574 CHECK_EQ(10, m.Call()); | |
575 } | |
576 | |
577 | |
578 TEST(RunCountToTenAcc) { | |
579 StructuredMachineAssemblerTester<int32_t> m; | |
580 int32_t constant = 0xf27aed64; | |
581 Variable i = m.NewVariable(m.Int32Constant(0)); | |
582 Variable var = m.NewVariable(m.Int32Constant(constant)); | |
583 Node* ten = m.Int32Constant(10); | |
584 Node* one = m.Int32Constant(1); | |
585 { | |
586 Loop loop(&m); | |
587 { | |
588 IfBuilder cond(&m); | |
589 cond.If(m.Word32Equal(i.Get(), ten)).Then(); | |
590 loop.Break(); | |
591 } | |
592 i.Set(m.Int32Add(i.Get(), one)); | |
593 var.Set(m.Int32Add(var.Get(), i.Get())); | |
594 } | |
595 m.Return(var.Get()); | |
596 | |
597 CHECK_EQ(constant + 10 + 9 * 5, m.Call()); | |
598 } | |
599 | |
600 | |
601 TEST(RunSimpleNestedLoop) { | |
602 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
603 | |
604 Node* zero = m.Int32Constant(0); | |
605 Node* one = m.Int32Constant(1); | |
606 Node* two = m.Int32Constant(2); | |
607 Node* three = m.Int32Constant(3); | |
608 { | |
609 Loop l1(&m); | |
610 { | |
611 Loop l2(&m); | |
612 { | |
613 IfBuilder cond(&m); | |
614 cond.If(m.Word32Equal(m.Parameter(0), one)).Then(); | |
615 l1.Break(); | |
616 } | |
617 { | |
618 Loop l3(&m); | |
619 { | |
620 IfBuilder cond(&m); | |
621 cond.If(m.Word32Equal(m.Parameter(0), two)).Then(); | |
622 l2.Break(); | |
623 cond.Else(); | |
624 cond.If(m.Word32Equal(m.Parameter(0), three)).Then(); | |
625 l3.Break(); | |
626 } | |
627 m.Return(three); | |
628 } | |
629 m.Return(two); | |
630 } | |
631 m.Return(one); | |
632 } | |
633 m.Return(zero); | |
634 | |
635 CHECK_EQ(0, m.Call(1)); | |
636 CHECK_EQ(1, m.Call(2)); | |
637 CHECK_EQ(2, m.Call(3)); | |
638 CHECK_EQ(3, m.Call(4)); | |
639 } | |
640 | |
641 | |
642 TEST(RunFib) { | |
643 StructuredMachineAssemblerTester<int32_t> m(kMachInt32); | |
644 | |
645 // Constants. | |
646 Node* zero = m.Int32Constant(0); | |
647 Node* one = m.Int32Constant(1); | |
648 Node* two = m.Int32Constant(2); | |
649 // Variables. | |
650 // cnt = input | |
651 Variable cnt = m.NewVariable(m.Parameter(0)); | |
652 // if (cnt < 2) return i | |
653 { | |
654 IfBuilder lt2(&m); | |
655 lt2.If(m.Int32LessThan(cnt.Get(), two)).Then(); | |
656 m.Return(cnt.Get()); | |
657 } | |
658 // cnt -= 2 | |
659 cnt.Set(m.Int32Sub(cnt.Get(), two)); | |
660 // res = 1 | |
661 Variable res = m.NewVariable(one); | |
662 { | |
663 // prv_0 = 1 | |
664 // prv_1 = 1 | |
665 Variable prv_0 = m.NewVariable(one); | |
666 Variable prv_1 = m.NewVariable(one); | |
667 // while (cnt != 0) { | |
668 Loop main(&m); | |
669 { | |
670 IfBuilder nz(&m); | |
671 nz.If(m.Word32Equal(cnt.Get(), zero)).Then(); | |
672 main.Break(); | |
673 } | |
674 // res = prv_0 + prv_1 | |
675 // prv_0 = prv_1 | |
676 // prv_1 = res | |
677 res.Set(m.Int32Add(prv_0.Get(), prv_1.Get())); | |
678 prv_0.Set(prv_1.Get()); | |
679 prv_1.Set(res.Get()); | |
680 // cnt-- | |
681 cnt.Set(m.Int32Sub(cnt.Get(), one)); | |
682 } | |
683 m.Return(res.Get()); | |
684 | |
685 int32_t values[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144}; | |
686 for (size_t i = 0; i < arraysize(values); i++) { | |
687 CHECK_EQ(values[i], m.Call(static_cast<int32_t>(i))); | |
688 } | |
689 } | |
690 | |
691 | |
692 static int VariableIntroduction() { | |
693 while (true) { | |
694 int ret = 0; | |
695 for (int i = 0; i < 10; i++) { | |
696 for (int j = i; j < 10; j++) { | |
697 for (int k = j; k < 10; k++) { | |
698 ret++; | |
699 } | |
700 ret++; | |
701 } | |
702 ret++; | |
703 } | |
704 return ret; | |
705 } | |
706 } | |
707 | |
708 | |
709 TEST(RunVariableIntroduction) { | |
710 StructuredMachineAssemblerTester<int32_t> m; | |
711 Node* zero = m.Int32Constant(0); | |
712 Node* one = m.Int32Constant(1); | |
713 // Use an IfBuilder to get out of start block. | |
714 { | |
715 IfBuilder i0(&m); | |
716 i0.If(zero).Then(); | |
717 m.Return(one); | |
718 } | |
719 Node* ten = m.Int32Constant(10); | |
720 Variable v0 = | |
721 m.NewVariable(zero); // Introduce variable outside of start block. | |
722 { | |
723 Loop l0(&m); | |
724 Variable ret = m.NewVariable(zero); // Introduce loop variable. | |
725 { | |
726 Loop l1(&m); | |
727 { | |
728 IfBuilder i1(&m); | |
729 i1.If(m.Word32Equal(v0.Get(), ten)).Then(); | |
730 l1.Break(); | |
731 } | |
732 Variable v1 = m.NewVariable(v0.Get()); // Introduce loop variable. | |
733 { | |
734 Loop l2(&m); | |
735 { | |
736 IfBuilder i2(&m); | |
737 i2.If(m.Word32Equal(v1.Get(), ten)).Then(); | |
738 l2.Break(); | |
739 } | |
740 Variable v2 = m.NewVariable(v1.Get()); // Introduce loop variable. | |
741 { | |
742 Loop l3(&m); | |
743 { | |
744 IfBuilder i3(&m); | |
745 i3.If(m.Word32Equal(v2.Get(), ten)).Then(); | |
746 l3.Break(); | |
747 } | |
748 ret.Set(m.Int32Add(ret.Get(), one)); | |
749 v2.Set(m.Int32Add(v2.Get(), one)); | |
750 } | |
751 ret.Set(m.Int32Add(ret.Get(), one)); | |
752 v1.Set(m.Int32Add(v1.Get(), one)); | |
753 } | |
754 ret.Set(m.Int32Add(ret.Get(), one)); | |
755 v0.Set(m.Int32Add(v0.Get(), one)); | |
756 } | |
757 m.Return(ret.Get()); // Return loop variable. | |
758 } | |
759 CHECK_EQ(VariableIntroduction(), m.Call()); | |
760 } | |
761 | |
762 | |
763 TEST(RunIfBuilderVariableLiveness) { | |
764 StructuredMachineAssemblerTester<int32_t> m; | |
765 typedef i::compiler::StructuredMachineAssemblerFriend F; | |
766 Node* zero = m.Int32Constant(0); | |
767 Variable v_outer = m.NewVariable(zero); | |
768 IfBuilder cond(&m); | |
769 cond.If(zero).Then(); | |
770 Variable v_then = m.NewVariable(zero); | |
771 CHECK(F::VariableAlive(&m, v_outer)); | |
772 CHECK(F::VariableAlive(&m, v_then)); | |
773 cond.Else(); | |
774 Variable v_else = m.NewVariable(zero); | |
775 CHECK(F::VariableAlive(&m, v_outer)); | |
776 CHECK(F::VariableAlive(&m, v_else)); | |
777 CHECK(!F::VariableAlive(&m, v_then)); | |
778 cond.End(); | |
779 CHECK(F::VariableAlive(&m, v_outer)); | |
780 CHECK(!F::VariableAlive(&m, v_then)); | |
781 CHECK(!F::VariableAlive(&m, v_else)); | |
782 } | |
783 | |
784 | |
785 TEST(RunSimpleExpression1) { | |
786 StructuredMachineAssemblerTester<int32_t> m; | |
787 | |
788 int32_t constant = 0x0c2974ef; | |
789 Node* zero = m.Int32Constant(0); | |
790 Node* one = m.Int32Constant(1); | |
791 { | |
792 // if (((1 && 1) && 1) && 1) return constant; return 0; | |
793 IfBuilder cond(&m); | |
794 cond.OpenParen(); | |
795 cond.OpenParen().If(one).And(); | |
796 cond.If(one).CloseParen().And(); | |
797 cond.If(one).CloseParen().And(); | |
798 cond.If(one).Then(); | |
799 m.Return(m.Int32Constant(constant)); | |
800 } | |
801 m.Return(zero); | |
802 | |
803 CHECK_EQ(constant, m.Call()); | |
804 } | |
805 | |
806 | |
807 TEST(RunSimpleExpression2) { | |
808 StructuredMachineAssemblerTester<int32_t> m; | |
809 | |
810 int32_t constant = 0x2eddc11b; | |
811 Node* zero = m.Int32Constant(0); | |
812 Node* one = m.Int32Constant(1); | |
813 { | |
814 // if (((0 || 1) && 1) && 1) return constant; return 0; | |
815 IfBuilder cond(&m); | |
816 cond.OpenParen(); | |
817 cond.OpenParen().If(zero).Or(); | |
818 cond.If(one).CloseParen().And(); | |
819 cond.If(one).CloseParen().And(); | |
820 cond.If(one).Then(); | |
821 m.Return(m.Int32Constant(constant)); | |
822 } | |
823 m.Return(zero); | |
824 | |
825 CHECK_EQ(constant, m.Call()); | |
826 } | |
827 | |
828 | |
829 TEST(RunSimpleExpression3) { | |
830 StructuredMachineAssemblerTester<int32_t> m; | |
831 | |
832 int32_t constant = 0x9ed5e9ef; | |
833 Node* zero = m.Int32Constant(0); | |
834 Node* one = m.Int32Constant(1); | |
835 { | |
836 // if (1 && ((0 || 1) && 1) && 1) return constant; return 0; | |
837 IfBuilder cond(&m); | |
838 cond.If(one).And(); | |
839 cond.OpenParen(); | |
840 cond.OpenParen().If(zero).Or(); | |
841 cond.If(one).CloseParen().And(); | |
842 cond.If(one).CloseParen().And(); | |
843 cond.If(one).Then(); | |
844 m.Return(m.Int32Constant(constant)); | |
845 } | |
846 m.Return(zero); | |
847 | |
848 CHECK_EQ(constant, m.Call()); | |
849 } | |
850 | |
851 | |
852 TEST(RunSimpleExpressionVariable1) { | |
853 StructuredMachineAssemblerTester<int32_t> m; | |
854 | |
855 int32_t constant = 0x4b40a986; | |
856 Node* one = m.Int32Constant(1); | |
857 Variable var = m.NewVariable(m.Int32Constant(constant)); | |
858 { | |
859 // if (var.Get() && ((!var || var) && var) && var) {} return var; | |
860 // incrementing var in each environment. | |
861 IfBuilder cond(&m); | |
862 cond.If(var.Get()).And(); | |
863 var.Set(m.Int32Add(var.Get(), one)); | |
864 cond.OpenParen().OpenParen().If(m.Word32BinaryNot(var.Get())).Or(); | |
865 var.Set(m.Int32Add(var.Get(), one)); | |
866 cond.If(var.Get()).CloseParen().And(); | |
867 var.Set(m.Int32Add(var.Get(), one)); | |
868 cond.If(var.Get()).CloseParen().And(); | |
869 var.Set(m.Int32Add(var.Get(), one)); | |
870 cond.If(var.Get()); | |
871 } | |
872 m.Return(var.Get()); | |
873 | |
874 CHECK_EQ(constant + 4, m.Call()); | |
875 } | |
876 | |
877 | |
878 class QuicksortHelper : public StructuredMachineAssemblerTester<int32_t> { | |
879 public: | |
880 QuicksortHelper() | |
881 : StructuredMachineAssemblerTester<int32_t>(kMachPtr, kMachInt32, | |
882 kMachPtr, kMachInt32), | |
883 input_(NULL), | |
884 stack_limit_(NULL), | |
885 one_(Int32Constant(1)), | |
886 stack_frame_size_(Int32Constant(kFrameVariables * 4)), | |
887 left_offset_(Int32Constant(0 * 4)), | |
888 right_offset_(Int32Constant(1 * 4)) { | |
889 Build(); | |
890 } | |
891 | |
892 int32_t DoCall(int32_t* input, int32_t input_length) { | |
893 int32_t stack_space[20]; | |
894 // Do call. | |
895 int32_t return_val = Call(input, input_length, stack_space, | |
896 static_cast<int32_t>(arraysize(stack_space))); | |
897 // Ran out of stack space. | |
898 if (return_val != 0) return return_val; | |
899 // Check sorted. | |
900 int32_t last = input[0]; | |
901 for (int32_t i = 0; i < input_length; i++) { | |
902 CHECK(last <= input[i]); | |
903 last = input[i]; | |
904 } | |
905 return return_val; | |
906 } | |
907 | |
908 private: | |
909 void Inc32(const Variable& var) { var.Set(Int32Add(var.Get(), one_)); } | |
910 Node* Index(Node* index) { return Word32Shl(index, Int32Constant(2)); } | |
911 Node* ArrayLoad(Node* index) { | |
912 return Load(kMachInt32, input_, Index(index)); | |
913 } | |
914 void Swap(Node* a_index, Node* b_index) { | |
915 Node* a = ArrayLoad(a_index); | |
916 Node* b = ArrayLoad(b_index); | |
917 Store(kMachInt32, input_, Index(a_index), b); | |
918 Store(kMachInt32, input_, Index(b_index), a); | |
919 } | |
920 void AddToCallStack(const Variable& fp, Node* left, Node* right) { | |
921 { | |
922 // Stack limit check. | |
923 IfBuilder cond(this); | |
924 cond.If(IntPtrLessThanOrEqual(fp.Get(), stack_limit_)).Then(); | |
925 Return(Int32Constant(-1)); | |
926 } | |
927 Store(kMachInt32, fp.Get(), left_offset_, left); | |
928 Store(kMachInt32, fp.Get(), right_offset_, right); | |
929 fp.Set(IntPtrAdd(fp.Get(), ConvertInt32ToIntPtr(stack_frame_size_))); | |
930 } | |
931 void Build() { | |
932 Variable left = NewVariable(Int32Constant(0)); | |
933 Variable right = | |
934 NewVariable(Int32Sub(Parameter(kInputLengthParameter), one_)); | |
935 input_ = Parameter(kInputParameter); | |
936 Node* top_of_stack = Parameter(kStackParameter); | |
937 stack_limit_ = IntPtrSub( | |
938 top_of_stack, ConvertInt32ToIntPtr(Parameter(kStackLengthParameter))); | |
939 Variable fp = NewVariable(top_of_stack); | |
940 { | |
941 Loop outermost(this); | |
942 // Edge case - 2 element array. | |
943 { | |
944 IfBuilder cond(this); | |
945 cond.If(Word32Equal(left.Get(), Int32Sub(right.Get(), one_))).And(); | |
946 cond.If(Int32LessThanOrEqual(ArrayLoad(right.Get()), | |
947 ArrayLoad(left.Get()))).Then(); | |
948 Swap(left.Get(), right.Get()); | |
949 } | |
950 { | |
951 IfBuilder cond(this); | |
952 // Algorithm complete condition. | |
953 cond.If(WordEqual(top_of_stack, fp.Get())).And(); | |
954 cond.If(Int32LessThanOrEqual(Int32Sub(right.Get(), one_), left.Get())) | |
955 .Then(); | |
956 outermost.Break(); | |
957 // 'Recursion' exit condition. Pop frame and continue. | |
958 cond.Else(); | |
959 cond.If(Int32LessThanOrEqual(Int32Sub(right.Get(), one_), left.Get())) | |
960 .Then(); | |
961 fp.Set(IntPtrSub(fp.Get(), ConvertInt32ToIntPtr(stack_frame_size_))); | |
962 left.Set(Load(kMachInt32, fp.Get(), left_offset_)); | |
963 right.Set(Load(kMachInt32, fp.Get(), right_offset_)); | |
964 outermost.Continue(); | |
965 } | |
966 // Partition. | |
967 Variable store_index = NewVariable(left.Get()); | |
968 { | |
969 Node* pivot_index = | |
970 Int32Div(Int32Add(left.Get(), right.Get()), Int32Constant(2)); | |
971 Node* pivot = ArrayLoad(pivot_index); | |
972 Swap(pivot_index, right.Get()); | |
973 Variable i = NewVariable(left.Get()); | |
974 { | |
975 Loop partition(this); | |
976 { | |
977 IfBuilder cond(this); | |
978 // Parition complete. | |
979 cond.If(Word32Equal(i.Get(), right.Get())).Then(); | |
980 partition.Break(); | |
981 // Need swap. | |
982 cond.Else(); | |
983 cond.If(Int32LessThanOrEqual(ArrayLoad(i.Get()), pivot)).Then(); | |
984 Swap(i.Get(), store_index.Get()); | |
985 Inc32(store_index); | |
986 } | |
987 Inc32(i); | |
988 } // End partition loop. | |
989 Swap(store_index.Get(), right.Get()); | |
990 } | |
991 // 'Recurse' left and right halves of partition. | |
992 // Tail recurse second one. | |
993 AddToCallStack(fp, left.Get(), Int32Sub(store_index.Get(), one_)); | |
994 left.Set(Int32Add(store_index.Get(), one_)); | |
995 } // End outermost loop. | |
996 Return(Int32Constant(0)); | |
997 } | |
998 | |
999 static const int kFrameVariables = 2; // left, right | |
1000 // Parameter offsets. | |
1001 static const int kInputParameter = 0; | |
1002 static const int kInputLengthParameter = 1; | |
1003 static const int kStackParameter = 2; | |
1004 static const int kStackLengthParameter = 3; | |
1005 // Function inputs. | |
1006 Node* input_; | |
1007 Node* stack_limit_; | |
1008 // Constants. | |
1009 Node* const one_; | |
1010 // Frame constants. | |
1011 Node* const stack_frame_size_; | |
1012 Node* const left_offset_; | |
1013 Node* const right_offset_; | |
1014 }; | |
1015 | |
1016 | |
1017 TEST(RunSimpleQuicksort) { | |
1018 QuicksortHelper m; | |
1019 int32_t inputs[] = {9, 7, 1, 8, 11}; | |
1020 CHECK_EQ(0, m.DoCall(inputs, arraysize(inputs))); | |
1021 } | |
1022 | |
1023 | |
1024 TEST(RunRandomQuicksort) { | |
1025 QuicksortHelper m; | |
1026 | |
1027 v8::base::RandomNumberGenerator rng; | |
1028 static const int kMaxLength = 40; | |
1029 int32_t inputs[kMaxLength]; | |
1030 | |
1031 for (int length = 1; length < kMaxLength; length++) { | |
1032 for (int i = 0; i < 70; i++) { | |
1033 // Randomize inputs. | |
1034 for (int j = 0; j < length; j++) { | |
1035 inputs[j] = rng.NextInt(10) - 5; | |
1036 } | |
1037 CHECK_EQ(0, m.DoCall(inputs, length)); | |
1038 } | |
1039 } | |
1040 } | |
1041 | |
1042 | |
1043 TEST(MultipleScopes) { | |
1044 StructuredMachineAssemblerTester<int32_t> m; | |
1045 for (int i = 0; i < 10; i++) { | |
1046 IfBuilder b(&m); | |
1047 b.If(m.Int32Constant(0)).Then(); | |
1048 m.NewVariable(m.Int32Constant(0)); | |
1049 } | |
1050 m.Return(m.Int32Constant(0)); | |
1051 CHECK_EQ(0, m.Call()); | |
1052 } | |
1053 | |
1054 #endif | |
OLD | NEW |