1 /*
2 * Copyright (c) 2013, 2016, 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 package org.graalvm.compiler.hotspot.replacements.arraycopy;
24
25 import static jdk.vm.ci.hotspot.HotSpotJVMCIRuntimeProvider.getArrayIndexScale;
26 import static org.graalvm.compiler.hotspot.GraalHotSpotVMConfig.INJECTED_VMCONFIG;
27 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.arrayBaseOffset;
28 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.arrayIndexScale;
29 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.layoutHelperHeaderSizeMask;
30 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.layoutHelperHeaderSizeShift;
31 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.layoutHelperLog2ElementSizeMask;
32 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.layoutHelperLog2ElementSizeShift;
33 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.runtime;
34 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.wordSize;
35 import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.NOT_FREQUENT_PROBABILITY;
36 import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.probability;
37 import static org.graalvm.compiler.replacements.SnippetTemplate.DEFAULT_REPLACER;
38 import static org.graalvm.word.LocationIdentity.any;
39
40 import org.graalvm.compiler.api.replacements.Fold;
41 import org.graalvm.compiler.api.replacements.Snippet;
42 import org.graalvm.compiler.core.common.NumUtil;
43 import org.graalvm.compiler.debug.DebugHandlersFactory;
44 import org.graalvm.compiler.hotspot.meta.HotSpotProviders;
45 import org.graalvm.compiler.hotspot.phases.WriteBarrierAdditionPhase;
46 import org.graalvm.compiler.nodes.NamedLocationIdentity;
47 import org.graalvm.compiler.nodes.extended.RawLoadNode;
48 import org.graalvm.compiler.nodes.extended.RawStoreNode;
49 import org.graalvm.compiler.nodes.extended.UnsafeCopyNode;
50 import org.graalvm.compiler.nodes.spi.LoweringTool;
51 import org.graalvm.compiler.options.OptionValues;
52 import org.graalvm.compiler.replacements.SnippetTemplate;
53 import org.graalvm.compiler.replacements.SnippetTemplate.AbstractTemplates;
54 import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;
55 import org.graalvm.compiler.replacements.SnippetTemplate.SnippetInfo;
56 import org.graalvm.compiler.replacements.Snippets;
57 import org.graalvm.compiler.word.ObjectAccess;
58 import org.graalvm.word.LocationIdentity;
59 import org.graalvm.word.UnsignedWord;
60 import org.graalvm.word.WordFactory;
61
62 import jdk.vm.ci.code.TargetDescription;
63 import jdk.vm.ci.meta.JavaKind;
64
65 /**
66 * As opposed to {@link ArrayCopySnippets}, these Snippets do <b>not</b> perform store checks.
67 */
68 public class UnsafeArrayCopySnippets implements Snippets {
69
70 private static final boolean supportsUnalignedMemoryAccess = runtime().getHostJVMCIBackend().getTarget().arch.supportsUnalignedMemoryAccess();
71
72 private static final JavaKind VECTOR_KIND = JavaKind.Long;
73 private static final long VECTOR_SIZE = getArrayIndexScale(VECTOR_KIND);
74
75 private static void vectorizedCopy(Object src, int srcPos, Object dest, int destPos, int length, JavaKind baseKind, LocationIdentity locationIdentity) {
76 int arrayBaseOffset = arrayBaseOffset(baseKind);
77 int elementSize = arrayIndexScale(baseKind);
78 long byteLength = (long) length * elementSize;
79 long srcOffset = (long) srcPos * elementSize;
80 long destOffset = (long) destPos * elementSize;
81
82 long preLoopBytes;
83 long mainLoopBytes;
84 long postLoopBytes;
85
86 // We can easily vectorize the loop if both offsets have the same alignment.
87 if (byteLength >= VECTOR_SIZE && (srcOffset % VECTOR_SIZE) == (destOffset % VECTOR_SIZE)) {
88 preLoopBytes = NumUtil.roundUp(arrayBaseOffset + srcOffset, VECTOR_SIZE) - (arrayBaseOffset + srcOffset);
89 postLoopBytes = (byteLength - preLoopBytes) % VECTOR_SIZE;
90 mainLoopBytes = byteLength - preLoopBytes - postLoopBytes;
91 } else {
92 // Does the architecture support unaligned memory accesses?
93 if (supportsUnalignedMemoryAccess) {
94 preLoopBytes = byteLength % VECTOR_SIZE;
95 mainLoopBytes = byteLength - preLoopBytes;
96 postLoopBytes = 0;
97 } else {
98 // No. Let's do element-wise copying.
99 preLoopBytes = byteLength;
100 mainLoopBytes = 0;
101 postLoopBytes = 0;
102 }
103 }
104
105 if (probability(NOT_FREQUENT_PROBABILITY, src == dest) && probability(NOT_FREQUENT_PROBABILITY, srcPos < destPos)) {
106 // bad aliased case
107 srcOffset += byteLength;
108 destOffset += byteLength;
109
110 // Post-loop
111 for (long i = 0; i < postLoopBytes; i += elementSize) {
112 srcOffset -= elementSize;
113 destOffset -= elementSize;
114 UnsafeCopyNode.copy(src, arrayBaseOffset + srcOffset, dest, arrayBaseOffset + destOffset, baseKind, locationIdentity);
115 }
116 // Main-loop
117 for (long i = 0; i < mainLoopBytes; i += VECTOR_SIZE) {
118 srcOffset -= VECTOR_SIZE;
119 destOffset -= VECTOR_SIZE;
120 UnsafeCopyNode.copy(src, arrayBaseOffset + srcOffset, dest, arrayBaseOffset + destOffset, VECTOR_KIND, locationIdentity);
121 }
122 // Pre-loop
123 for (long i = 0; i < preLoopBytes; i += elementSize) {
124 srcOffset -= elementSize;
125 destOffset -= elementSize;
126 UnsafeCopyNode.copy(src, arrayBaseOffset + srcOffset, dest, arrayBaseOffset + destOffset, baseKind, locationIdentity);
127 }
128 } else {
129 // Pre-loop
130 for (long i = 0; i < preLoopBytes; i += elementSize) {
131 UnsafeCopyNode.copy(src, arrayBaseOffset + srcOffset, dest, arrayBaseOffset + destOffset, baseKind, locationIdentity);
132 srcOffset += elementSize;
133 destOffset += elementSize;
134 }
135 // Main-loop
136 for (long i = 0; i < mainLoopBytes; i += VECTOR_SIZE) {
137 UnsafeCopyNode.copy(src, arrayBaseOffset + srcOffset, dest, arrayBaseOffset + destOffset, VECTOR_KIND, locationIdentity);
138 srcOffset += VECTOR_SIZE;
139 destOffset += VECTOR_SIZE;
140 }
141 // Post-loop
142 for (long i = 0; i < postLoopBytes; i += elementSize) {
143 UnsafeCopyNode.copy(src, arrayBaseOffset + srcOffset, dest, arrayBaseOffset + destOffset, baseKind, locationIdentity);
144 srcOffset += elementSize;
145 destOffset += elementSize;
146 }
147 }
148 }
149
150 @Fold
151 static LocationIdentity getArrayLocation(JavaKind kind) {
152 return NamedLocationIdentity.getArrayLocation(kind);
153 }
154
155 @Snippet
156 public static void arraycopyByte(byte[] src, int srcPos, byte[] dest, int destPos, int length) {
157 JavaKind kind = JavaKind.Byte;
158 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
159 }
160
161 @Snippet
162 public static void arraycopyBoolean(boolean[] src, int srcPos, boolean[] dest, int destPos, int length) {
163 JavaKind kind = JavaKind.Boolean;
164 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
165 }
166
167 @Snippet
168 public static void arraycopyChar(char[] src, int srcPos, char[] dest, int destPos, int length) {
169 JavaKind kind = JavaKind.Char;
170 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
171 }
172
173 @Snippet
174 public static void arraycopyShort(short[] src, int srcPos, short[] dest, int destPos, int length) {
175 JavaKind kind = JavaKind.Short;
176 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
177 }
178
179 @Snippet
180 public static void arraycopyInt(int[] src, int srcPos, int[] dest, int destPos, int length) {
181 JavaKind kind = JavaKind.Int;
182 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
183 }
184
185 @Snippet
186 public static void arraycopyFloat(float[] src, int srcPos, float[] dest, int destPos, int length) {
187 JavaKind kind = JavaKind.Float;
188 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
189 }
190
191 @Snippet
192 public static void arraycopyLong(long[] src, int srcPos, long[] dest, int destPos, int length) {
193 JavaKind kind = JavaKind.Long;
194 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
195 }
196
197 @Snippet
198 public static void arraycopyDouble(double[] src, int srcPos, double[] dest, int destPos, int length) {
199 JavaKind kind = JavaKind.Double;
200 /*
201 * TODO atomicity problem on 32-bit architectures: The JVM spec requires double values to be
202 * copied atomically, but not long values. For example, on Intel 32-bit this code is not
203 * atomic as long as the vector kind remains Kind.Long.
204 */
205 vectorizedCopy(src, srcPos, dest, destPos, length, kind, getArrayLocation(kind));
206 }
207
208 /**
209 * For this kind, Object, we want to avoid write barriers between writes, but instead have them
210 * at the end of the snippet. This is done by using {@link RawStoreNode}, and rely on
211 * {@link WriteBarrierAdditionPhase} to put write barriers after the {@link UnsafeArrayCopyNode}
212 * with kind Object.
213 */
214 @Snippet
215 public static void arraycopyObject(Object[] src, int srcPos, Object[] dest, int destPos, int length) {
216 JavaKind kind = JavaKind.Object;
217 final int scale = arrayIndexScale(kind);
218 int arrayBaseOffset = arrayBaseOffset(kind);
219 LocationIdentity arrayLocation = getArrayLocation(kind);
220 if (src == dest && srcPos < destPos) { // bad aliased case
221 long start = (long) (length - 1) * scale;
222 for (long i = start; i >= 0; i -= scale) {
223 Object a = RawLoadNode.load(src, arrayBaseOffset + i + (long) srcPos * scale, kind, arrayLocation);
224 RawStoreNode.storeObject(dest, arrayBaseOffset + i + (long) destPos * scale, a, kind, getArrayLocation(kind), false);
225 }
226 } else {
227 long end = (long) length * scale;
228 for (long i = 0; i < end; i += scale) {
229 Object a = RawLoadNode.load(src, arrayBaseOffset + i + (long) srcPos * scale, kind, arrayLocation);
230 RawStoreNode.storeObject(dest, arrayBaseOffset + i + (long) destPos * scale, a, kind, getArrayLocation(kind), false);
231 }
232 }
233 }
234
235 @Snippet
236 public static void arraycopyPrimitive(Object src, int srcPos, Object dest, int destPos, int length, int layoutHelper) {
237 int log2ElementSize = (layoutHelper >> layoutHelperLog2ElementSizeShift(INJECTED_VMCONFIG)) & layoutHelperLog2ElementSizeMask(INJECTED_VMCONFIG);
238 int headerSize = (layoutHelper >> layoutHelperHeaderSizeShift(INJECTED_VMCONFIG)) & layoutHelperHeaderSizeMask(INJECTED_VMCONFIG);
239
240 UnsignedWord vectorSize = WordFactory.unsigned(VECTOR_SIZE);
241 UnsignedWord srcOffset = WordFactory.unsigned(srcPos).shiftLeft(log2ElementSize).add(headerSize);
242 UnsignedWord destOffset = WordFactory.unsigned(destPos).shiftLeft(log2ElementSize).add(headerSize);
243 UnsignedWord destStart = destOffset;
244 UnsignedWord destEnd = destOffset.add(WordFactory.unsigned(length).shiftLeft(log2ElementSize));
245
246 UnsignedWord destVectorEnd = null;
247 UnsignedWord nonVectorBytes = null;
248 UnsignedWord sizeInBytes = WordFactory.unsigned(length).shiftLeft(log2ElementSize);
249 if (supportsUnalignedMemoryAccess) {
250 nonVectorBytes = sizeInBytes.unsignedRemainder(vectorSize);
251 destVectorEnd = destEnd;
252 } else {
253 boolean inPhase = srcOffset.and((int) VECTOR_SIZE - 1).equal(destOffset.and((int) VECTOR_SIZE - 1));
254 boolean hasAtLeastOneVector = sizeInBytes.aboveOrEqual(vectorSize);
255 // We must have at least one full vector, otherwise we must copy each byte separately
256 if (hasAtLeastOneVector && inPhase) { // If in phase, we can vectorize
257 nonVectorBytes = vectorSize.subtract(destStart.unsignedRemainder(vectorSize));
258 } else { // fallback is byte-wise
259 nonVectorBytes = sizeInBytes;
260 }
261 destVectorEnd = destEnd.subtract(destEnd.unsignedRemainder(vectorSize));
262 }
263
264 UnsignedWord destNonVectorEnd = destStart.add(nonVectorBytes);
265 while (destOffset.belowThan(destNonVectorEnd)) {
266 ObjectAccess.writeByte(dest, destOffset, ObjectAccess.readByte(src, srcOffset, any()), any());
267 destOffset = destOffset.add(1);
268 srcOffset = srcOffset.add(1);
269 }
270 // Unsigned destVectorEnd = destEnd.subtract(destEnd.unsignedRemainder(8));
271 while (destOffset.belowThan(destVectorEnd)) {
272 ObjectAccess.writeWord(dest, destOffset, ObjectAccess.readWord(src, srcOffset, any()), any());
273 destOffset = destOffset.add(wordSize());
274 srcOffset = srcOffset.add(wordSize());
275 }
276 // Do the last bytes each when it is required to have absolute alignment.
277 while (!supportsUnalignedMemoryAccess && destOffset.belowThan(destEnd)) {
278 ObjectAccess.writeByte(dest, destOffset, ObjectAccess.readByte(src, srcOffset, any()), any());
279 destOffset = destOffset.add(1);
280 srcOffset = srcOffset.add(1);
281 }
282 }
283
284 public static class Templates extends AbstractTemplates {
285
286 private final SnippetInfo[] arraycopySnippets;
287 private final SnippetInfo genericPrimitiveSnippet;
288
289 public Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, HotSpotProviders providers, TargetDescription target) {
290 super(options, factories, providers, providers.getSnippetReflection(), target);
291
292 arraycopySnippets = new SnippetInfo[JavaKind.values().length];
293 arraycopySnippets[JavaKind.Boolean.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyBoolean");
294 arraycopySnippets[JavaKind.Byte.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyByte");
295 arraycopySnippets[JavaKind.Short.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyShort");
296 arraycopySnippets[JavaKind.Char.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyChar");
297 arraycopySnippets[JavaKind.Int.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyInt");
298 arraycopySnippets[JavaKind.Long.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyLong");
299 arraycopySnippets[JavaKind.Float.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyFloat");
300 arraycopySnippets[JavaKind.Double.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyDouble");
301 arraycopySnippets[JavaKind.Object.ordinal()] = snippet(UnsafeArrayCopySnippets.class, "arraycopyObject");
302
303 genericPrimitiveSnippet = snippet(UnsafeArrayCopySnippets.class, "arraycopyPrimitive");
304 }
305
306 public void lower(UnsafeArrayCopyNode node, LoweringTool tool) {
307 JavaKind elementKind = node.getElementKind();
308 SnippetInfo snippet;
309 if (elementKind == null) {
310 // primitive array of unknown kind
311 snippet = genericPrimitiveSnippet;
312 } else {
313 snippet = arraycopySnippets[elementKind.ordinal()];
314 assert snippet != null : "arraycopy snippet for " + elementKind.name() + " not found";
315 }
316
317 Arguments args = new Arguments(snippet, node.graph().getGuardsStage(), tool.getLoweringStage());
318 node.addSnippetArguments(args);
319
320 SnippetTemplate template = template(node.getDebug(), args);
321 template.instantiate(providers.getMetaAccess(), node, DEFAULT_REPLACER, args);
322 }
323 }
324 }