1 /*
2 * Copyright (c) 2018, 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.lir.hashing;
26
27 import java.util.ArrayList;
28 import java.util.Collections;
29 import java.util.List;
30 import java.util.function.BiFunction;
31 import java.util.function.Function;
32
33 import org.graalvm.compiler.lir.gen.ArithmeticLIRGenerator;
34
35 import jdk.vm.ci.meta.JavaConstant;
36 import jdk.vm.ci.meta.Value;
37
38 /**
39 * This class provides a set of cheap imperfect hash functions based on the paper "Improving Switch
40 * Statement Performance with Hashing Optimized at Compile Time".
41 * (http://programming.sirrida.de/hashsuper.pdf)
42 */
43 public abstract class HashFunction {
44
45 /**
46 * Applies the hash function.
47 *
48 * @param value the value to be hashed
49 * @param min {@code value} is guaranteed to be greater or equal to this minimum
50 * @return the hash value within int range
51 */
52 public abstract int apply(long value, long min);
53
54 /**
55 * Generates LIR that implements the hash function in terms of value and min.
56 *
57 * @param value the value to be hashed
58 * @param min the lowest key
59 * @param gen the lir generator
60 * @return new lir value with the hash function applied
61 */
62 public abstract Value gen(Value value, Value min, ArithmeticLIRGenerator gen);
63
64 /**
65 * Returns an estimate of number of CPU cycles necessary to apply the hash function.
66 */
67 public abstract int effort();
68
69 /**
70 * @return a list of all available hash functions
71 */
72 public static final List<HashFunction> instances() {
73 return Collections.unmodifiableList(instances);
74 }
75
76 private static List<HashFunction> instances = new ArrayList<>();
77
78 private static int[] mersennePrimes = {3, 7, 31, 127, 8191, 131071, 524287, 2147483647};
79
80 static {
81 //@formatter:off
82
83 add("val", 0,
84 (val, min) -> val,
85 gen -> (val, min) -> val);
86
87 add("val - min", 1,
88 (val, min) -> val - min,
89 gen -> (val, min) -> gen.emitSub(val, min, false));
90
91 add("val >> min", 1,
92 (val, min) -> val >> min,
93 gen -> (val, min) -> gen.emitShr(val, min));
94
95 add("val >> (val & min)", 2,
96 (val, min) -> val >> (val & min),
97 gen -> (val, min) -> gen.emitShr(val, gen.emitAnd(val, min)));
98
99 add("(val >> min) ^ val", 2,
100 (val, min) -> (val >> min) ^ val,
101 gen -> (val, min) -> gen.emitXor(gen.emitShr(val, min), val));
102
103 add("(val >> min) * val", 3,
104 (val, min) -> (val >> min) * val,
105 gen -> (val, min) -> gen.emitMul(gen.emitShr(val, min), val, false));
106
107 addWithPrimes("(val * prime) >> min", 3,
108 prime -> (val, min) -> (val * prime) >> min,
109 (gen, prime) -> (val, min) -> gen.emitShr(gen.emitMul(val, prime, false), min));
110
111 addWithPrimes("rotateRight(val, prime)", 3,
112 prime -> (val, min) -> Long.rotateRight(val, prime),
113 (gen, prime) -> (val, min) -> gen.emitRor(val, prime));
114
115 addWithPrimes("rotateRight(val, prime) + val", 4,
116 prime -> (val, min) -> Long.rotateRight(val, prime) + val,
117 (gen, prime) -> (val, min) -> gen.emitAdd(gen.emitRor(val, prime), val, false));
118
119 addWithPrimes("rotateRight(val, prime) ^ val", 4,
120 prime -> (val, min) -> Long.rotateRight(val, prime) ^ val,
121 (gen, prime) -> (val, min) -> gen.emitXor(gen.emitRor(val, prime), val));
122 //@formatter:on
123 }
124
125 private static void add(String toString, int effort, BiFunction<Long, Long, Long> f, Function<ArithmeticLIRGenerator, BiFunction<Value, Value, Value>> gen) {
126 instances.add(new HashFunction() {
127
128 @Override
129 public int apply(long value, long min) {
130 return f.apply(value, min).intValue();
131 }
132
133 @Override
134 public int effort() {
135 return effort;
136 }
137
138 @Override
139 public String toString() {
140 return toString;
141 }
142
143 @Override
144 public Value gen(Value val, Value min, ArithmeticLIRGenerator t) {
145 return gen.apply(t).apply(t.emitNarrow(val, 32), t.emitNarrow(min, 32));
146 }
147 });
148 }
149
150 private static void addWithPrimes(String toString, int effort, Function<Integer, BiFunction<Long, Long, Long>> f,
151 BiFunction<ArithmeticLIRGenerator, Value, BiFunction<Value, Value, Value>> gen) {
152 for (int p : mersennePrimes) {
153 add(toString, effort, f.apply(p), g -> gen.apply(g, g.getLIRGen().emitJavaConstant(JavaConstant.forInt(p))));
154 }
155 }
156 }