1 /*
2 * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.jtt.optimize;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.HashSet;
30 import java.util.List;
31 import java.util.Random;
32 import java.util.Set;
33 import java.util.stream.Collectors;
34
35 import org.graalvm.compiler.jtt.JTTTest;
36 import org.graalvm.compiler.lir.hashing.HashFunction;
37 import org.graalvm.compiler.lir.hashing.Hasher;
38 import org.junit.Test;
39
40 import jdk.vm.ci.meta.JavaConstant;
41
42 /*
43 * Tests optimization of hash table switches.
44 * Code generated by `SwitchHashTableTest.TestGenerator.main`
45 */
46 public class SwitchHashTableTest extends JTTTest {
47 @Test
48 public void checkHashFunctionInstances() {
49 List<String> coveredByTestCases = Arrays.asList("val >> min", "val", "val >> (val & min)", "(val >> min) ^ val", "val - min", "rotateRight(val, prime)", "rotateRight(val, prime) ^ val",
50 "rotateRight(val, prime) + val", "(val >> min) * val", "(val * prime) >> min");
51 Set<String> functions = HashFunction.instances().stream().map(Object::toString).collect(Collectors.toSet());
52 functions.removeAll(coveredByTestCases);
53 assertTrue("The following hash functions are not covered by the `Switch03` test: " + functions +
54 ". Re-run the `Switch03.TestGenerator.main` and update the test class.", functions.isEmpty());
55 }
56
57 // Hasher[function=rotateRight(val, prime), effort=4, cardinality=16]
58 public static int test1(int arg) {
59 switch (arg) {
60 case 3080012:
61 return 3080012;
62 case 3080017:
63 return 3080017;
64 case 3080029:
65 return 3080029;
66 case 3080037:
67 return 3080037;
68 case 3080040:
69 return 3080040;
70 case 3080054:
71 return 3080054;
72 case 3080060:
73 return 3080060;
74 case 3080065:
75 return 3080065;
76 case 3080073:
77 return 3080073;
78 case 3080082:
79 return 3080082;
80 case 3080095:
81 return 3080095;
82 case 3080103:
83 return 3080103;
84 case 3080116:
85 return 3080116;
86 case 3080127:
87 return 3080127;
88 case 3080130:
89 return 3080130;
90 default:
91 return -1;
92 }
93 }
94
95 @Test
96 public void run1() throws Throwable {
97 runTest("test1", 0); // zero
98 runTest("test1", 3080011); // bellow
99 runTest("test1", 3080012); // first
100 runTest("test1", 3080065); // middle
101 runTest("test1", 3080130); // last
102 runTest("test1", 3080131); // above
103 runTest("test1", 3080013); // miss
104 }
105
106 // Hasher[function=rotateRight(val, prime) ^ val, effort=5, cardinality=28]
107 public static int test2(int arg) {
108 switch (arg) {
109 case 718707335:
110 return 718707335;
111 case 718707336:
112 return 718707336;
113 case 718707347:
114 return 718707347;
115 case 718707359:
116 return 718707359;
117 case 718707366:
118 return 718707366;
119 case 718707375:
120 return 718707375;
121 case 718707378:
122 return 718707378;
123 case 718707386:
124 return 718707386;
125 case 718707396:
126 return 718707396;
127 case 718707401:
128 return 718707401;
129 case 718707408:
130 return 718707408;
131 case 718707409:
132 return 718707409;
133 case 718707420:
134 return 718707420;
135 case 718707431:
136 return 718707431;
137 case 718707436:
138 return 718707436;
139 default:
140 return -1;
141 }
142 }
143
144 @Test
145 public void run2() throws Throwable {
146 runTest("test2", 0); // zero
147 runTest("test2", 718707334); // bellow
148 runTest("test2", 718707335); // first
149 runTest("test2", 718707386); // middle
150 runTest("test2", 718707436); // last
151 runTest("test2", 718707437); // above
152 runTest("test2", 718707337); // miss
153 }
154
155 // Hasher[function=(val * prime) >> min, effort=4, cardinality=16]
156 public static int test3(int arg) {
157 switch (arg) {
158 case 880488712:
159 return 880488712;
160 case 880488723:
161 return 880488723;
162 case 880488737:
163 return 880488737;
164 case 880488744:
165 return 880488744;
166 case 880488752:
167 return 880488752;
168 case 880488757:
169 return 880488757;
170 case 880488767:
171 return 880488767;
172 case 880488777:
173 return 880488777;
174 case 880488781:
175 return 880488781;
176 case 880488794:
177 return 880488794;
178 case 880488795:
179 return 880488795;
180 case 880488807:
181 return 880488807;
182 case 880488814:
183 return 880488814;
184 case 880488821:
185 return 880488821;
186 case 880488831:
187 return 880488831;
188 default:
189 return -1;
190 }
191 }
192
193 @Test
194 public void run3() throws Throwable {
195 runTest("test3", 0); // zero
196 runTest("test3", 880488711); // bellow
197 runTest("test3", 880488712); // first
198 runTest("test3", 880488777); // middle
199 runTest("test3", 880488831); // last
200 runTest("test3", 880488832); // above
201 runTest("test3", 880488713); // miss
202 }
203
204 // Hasher[function=rotateRight(val, prime) + val, effort=5, cardinality=28]
205 public static int test4(int arg) {
206 switch (arg) {
207 case 189404658:
208 return 189404658;
209 case 189404671:
210 return 189404671;
211 case 189404678:
212 return 189404678;
213 case 189404680:
214 return 189404680;
215 case 189404687:
216 return 189404687;
217 case 189404698:
218 return 189404698;
219 case 189404699:
220 return 189404699;
221 case 189404711:
222 return 189404711;
223 case 189404724:
224 return 189404724;
225 case 189404725:
226 return 189404725;
227 case 189404732:
228 return 189404732;
229 case 189404739:
230 return 189404739;
231 case 189404748:
232 return 189404748;
233 case 189404754:
234 return 189404754;
235 case 189404765:
236 return 189404765;
237 default:
238 return -1;
239 }
240 }
241
242 @Test
243 public void run4() throws Throwable {
244 runTest("test4", 0); // zero
245 runTest("test4", 189404657); // bellow
246 runTest("test4", 189404658); // first
247 runTest("test4", 189404711); // middle
248 runTest("test4", 189404765); // last
249 runTest("test4", 189404766); // above
250 runTest("test4", 189404659); // miss
251 }
252
253 // Hasher[function=val - min, effort=2, cardinality=24]
254 public static int test5(int arg) {
255 switch (arg) {
256 case 527674226:
257 return 527674226;
258 case 527674235:
259 return 527674235;
260 case 527674236:
261 return 527674236;
262 case 527674247:
263 return 527674247;
264 case 527674251:
265 return 527674251;
266 case 527674253:
267 return 527674253;
268 case 527674257:
269 return 527674257;
270 case 527674263:
271 return 527674263;
272 case 527674265:
273 return 527674265;
274 case 527674272:
275 return 527674272;
276 case 527674286:
277 return 527674286;
278 case 527674293:
279 return 527674293;
280 case 527674294:
281 return 527674294;
282 case 527674306:
283 return 527674306;
284 case 527674308:
285 return 527674308;
286 default:
287 return -1;
288 }
289 }
290
291 @Test
292 public void run5() throws Throwable {
293 runTest("test5", 0); // zero
294 runTest("test5", 527674225); // bellow
295 runTest("test5", 527674226); // first
296 runTest("test5", 527674263); // middle
297 runTest("test5", 527674308); // last
298 runTest("test5", 527674309); // above
299 runTest("test5", 527674227); // miss
300 }
301
302 // Hasher[function=val, effort=1, cardinality=24]
303 public static int test6(int arg) {
304 switch (arg) {
305 case 676979121:
306 return 676979121;
307 case 676979128:
308 return 676979128;
309 case 676979135:
310 return 676979135;
311 case 676979146:
312 return 676979146;
313 case 676979148:
314 return 676979148;
315 case 676979156:
316 return 676979156;
317 case 676979158:
318 return 676979158;
319 case 676979169:
320 return 676979169;
321 case 676979175:
322 return 676979175;
323 case 676979179:
324 return 676979179;
325 case 676979182:
326 return 676979182;
327 case 676979194:
328 return 676979194;
329 case 676979200:
330 return 676979200;
331 case 676979205:
332 return 676979205;
333 case 676979219:
334 return 676979219;
335 default:
336 return -1;
337 }
338 }
339
340 @Test
341 public void run6() throws Throwable {
342 runTest("test6", 0); // zero
343 runTest("test6", 676979120); // bellow
344 runTest("test6", 676979121); // first
345 runTest("test6", 676979169); // middle
346 runTest("test6", 676979219); // last
347 runTest("test6", 676979220); // above
348 runTest("test6", 676979122); // miss
349 }
350
351 // Hasher[function=(val >> min) ^ val, effort=3, cardinality=16]
352 public static int test7(int arg) {
353 switch (arg) {
354 case 634218696:
355 return 634218696;
356 case 634218710:
357 return 634218710;
358 case 634218715:
359 return 634218715;
360 case 634218720:
361 return 634218720;
362 case 634218724:
363 return 634218724;
364 case 634218732:
365 return 634218732;
366 case 634218737:
367 return 634218737;
368 case 634218749:
369 return 634218749;
370 case 634218751:
371 return 634218751;
372 case 634218758:
373 return 634218758;
374 case 634218767:
375 return 634218767;
376 case 634218772:
377 return 634218772;
378 case 634218786:
379 return 634218786;
380 case 634218792:
381 return 634218792;
382 case 634218795:
383 return 634218795;
384 default:
385 return -1;
386 }
387 }
388
389 @Test
390 public void run7() throws Throwable {
391 runTest("test7", 0); // zero
392 runTest("test7", 634218695); // bellow
393 runTest("test7", 634218696); // first
394 runTest("test7", 634218749); // middle
395 runTest("test7", 634218795); // last
396 runTest("test7", 634218796); // above
397 runTest("test7", 634218697); // miss
398 }
399
400 // Hasher[function=val >> min, effort=2, cardinality=16]
401 public static int test8(int arg) {
402 switch (arg) {
403 case 473982403:
404 return 473982403;
405 case 473982413:
406 return 473982413;
407 case 473982416:
408 return 473982416;
409 case 473982425:
410 return 473982425;
411 case 473982439:
412 return 473982439;
413 case 473982445:
414 return 473982445;
415 case 473982459:
416 return 473982459;
417 case 473982468:
418 return 473982468;
419 case 473982479:
420 return 473982479;
421 case 473982482:
422 return 473982482;
423 case 473982494:
424 return 473982494;
425 case 473982501:
426 return 473982501;
427 case 473982505:
428 return 473982505;
429 case 473982519:
430 return 473982519;
431 case 473982523:
432 return 473982523;
433 default:
434 return -1;
435 }
436 }
437
438 @Test
439 public void run8() throws Throwable {
440 runTest("test8", 0); // zero
441 runTest("test8", 473982402); // bellow
442 runTest("test8", 473982403); // first
443 runTest("test8", 473982468); // middle
444 runTest("test8", 473982523); // last
445 runTest("test8", 473982524); // above
446 runTest("test8", 473982404); // miss
447 }
448
449 // Hasher[function=val >> (val & min), effort=3, cardinality=16]
450 public static int test9(int arg) {
451 switch (arg) {
452 case 15745090:
453 return 15745090;
454 case 15745093:
455 return 15745093;
456 case 15745102:
457 return 15745102;
458 case 15745108:
459 return 15745108;
460 case 15745122:
461 return 15745122;
462 case 15745131:
463 return 15745131;
464 case 15745132:
465 return 15745132;
466 case 15745146:
467 return 15745146;
468 case 15745151:
469 return 15745151;
470 case 15745163:
471 return 15745163;
472 case 15745169:
473 return 15745169;
474 case 15745182:
475 return 15745182;
476 case 15745191:
477 return 15745191;
478 case 15745198:
479 return 15745198;
480 case 15745207:
481 return 15745207;
482 default:
483 return -1;
484 }
485 }
486
487 @Test
488 public void run9() throws Throwable {
489 runTest("test9", 0); // zero
490 runTest("test9", 15745089); // bellow
491 runTest("test9", 15745090); // first
492 runTest("test9", 15745146); // middle
493 runTest("test9", 15745207); // last
494 runTest("test9", 15745208); // above
495 runTest("test9", 15745091); // miss
496 }
497
498 // Hasher[function=(val >> min) * val, effort=4, cardinality=28]
499 public static int test10(int arg) {
500 switch (arg) {
501 case 989358996:
502 return 989358996;
503 case 989359010:
504 return 989359010;
505 case 989359022:
506 return 989359022;
507 case 989359030:
508 return 989359030;
509 case 989359038:
510 return 989359038;
511 case 989359047:
512 return 989359047;
513 case 989359053:
514 return 989359053;
515 case 989359059:
516 return 989359059;
517 case 989359061:
518 return 989359061;
519 case 989359072:
520 return 989359072;
521 case 989359073:
522 return 989359073;
523 case 989359087:
524 return 989359087;
525 case 989359097:
526 return 989359097;
527 case 989359099:
528 return 989359099;
529 case 989359108:
530 return 989359108;
531 default:
532 return -1;
533 }
534 }
535
536 @Test
537 public void run10() throws Throwable {
538 runTest("test10", 0); // zero
539 runTest("test10", 989358995); // bellow
540 runTest("test10", 989358996); // first
541 runTest("test10", 989359059); // middle
542 runTest("test10", 989359108); // last
543 runTest("test10", 989359109); // above
544 runTest("test10", 989358997); // miss
545 }
546
547 public static class TestGenerator {
548
549 private static int nextId = 0;
550 private static final int size = 15;
551 private static double minDensity = 0.5;
552
553 // test code generator
554 public static void main(String[] args) {
555
556 Random r = new Random(0);
557 Set<String> seen = new HashSet<>();
558 Set<String> all = HashFunction.instances().stream().map(Object::toString).collect(Collectors.toSet());
559
560 println("@Test");
561 println("public void checkHashFunctionInstances() {");
562 println(" List<String> coveredByTestCases = Arrays.asList(" + String.join(", ", all.stream().map(s -> "\"" + s + "\"").collect(Collectors.toSet())) + ");");
563 println(" Set<String> functions = HashFunction.instances().stream().map(Object::toString).collect(Collectors.toSet());");
564 println(" functions.removeAll(coveredByTestCases);");
565 println(" assertTrue(\"The following hash functions are not covered by the `Switch03` test: \" + functions +");
566 println(" \". Re-run the `Switch03.TestGenerator.main` and update the test class.\", functions.isEmpty());");
567 println("}");
568
569 while (seen.size() < all.size()) {
570 int v = r.nextInt(Integer.MAX_VALUE / 2);
571 List<Integer> keys = new ArrayList<>();
572 while (keys.size() < 15) {
573 keys.add(v);
574 v += r.nextInt(15);
575 }
576 keys.sort(Integer::compare);
577 double density = ((double) keys.size() + 1) / (keys.get(keys.size() - 1) - keys.get(0));
578 if (density < minDensity) {
579 Hasher.forKeys(toConstants(keys), minDensity).ifPresent(h -> {
580 String f = h.function().toString();
581 if (!seen.contains(f)) {
582 gen(keys, h);
583 seen.add(f);
584 }
585 });
586 }
587 }
588 }
589
590 private static void gen(List<Integer> keys, Hasher hasher) {
591 int id = ++nextId;
592
593 println("// " + hasher + "");
594 println("public static int test" + id + "(int arg) {");
595 println(" switch (arg) {");
596
597 for (Integer key : keys) {
598 println(" case " + key + ": return " + key + ";");
599 }
600
601 println(" default: return -1;");
602 println(" }");
603 println("}");
604
605 int miss = keys.get(0) + 1;
606 while (keys.contains(miss)) {
607 miss++;
608 }
609
610 println("@Test");
611 println("public void run" + id + "() throws Throwable {");
612 println(" runTest(\"test" + id + "\", 0); // zero ");
613 println(" runTest(\"test" + id + "\", " + (keys.get(0) - 1) + "); // bellow ");
614 println(" runTest(\"test" + id + "\", " + keys.get(0) + "); // first ");
615 println(" runTest(\"test" + id + "\", " + keys.get(size / 2) + "); // middle ");
616 println(" runTest(\"test" + id + "\", " + keys.get(size - 1) + "); // last ");
617 println(" runTest(\"test" + id + "\", " + (keys.get(size - 1) + 1) + "); // above ");
618 println(" runTest(\"test" + id + "\", " + miss + "); // miss ");
619 println("}");
620 }
621
622 private static void println(String s) {
623 System.out.println(s);
624 }
625
626 private static JavaConstant[] toConstants(List<Integer> keys) {
627 JavaConstant[] ckeys = new JavaConstant[keys.size()];
628
629 for (int i = 0; i < keys.size(); i++) {
630 ckeys[i] = JavaConstant.forInt(keys.get(i));
631 }
632 return ckeys;
633 }
634 }
635 }