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